Bounding Boxes and Vicinity Checking


#1

This is a bit of revisit of some of my previous posts with regards to bounding boxes and detection of walls that intersect within my Wall Plugin.

Perhaps my algorithm for detecting these walls is as efficient as its going to get I’m not entirely sure.

I currently grab all of the wall assemblies with this simple call:

group_list = Sketchup.active_model.entities.grep(Sketchup::Group)
wall_list = group_list.find_all { |e| e.name =~ /_WALL_ASSEMBLY_/ }
wall_list.delete(@maingroup)

Notice I remove the group that I will be checking against. Then I systematically load up some select parameters for each wall and then run a corner and tee intersection check. This all seems to work reasonably well and is fairly stable.

My concern is with larger models where the designer might have 50+ walls (each wall panel is a group). This is where I think the plugin will slow down considerably. It will check each wall panel against the main wall panel in question and look for corner and tee intersections.

It seems that I should be able to somehow remove from my “wall_list” any of those groups that are not in the vicinity of the “maingroup”. In other words cut down the amount of looping required by discarding those wall groups that are far away from the wall group in question.

The bounding box solution will not work since it only looks at the situation where the group or element is fully contained within the bounding box. I guess what I need is bounding box crossing method.

I’m probably not articulating this very clearly, bit of head cold today and not feeling my 100% self, but I think the general gist of the problem has been presented.


#2

Here’s a bit of code and a skp file to run the code against. I think this should(?) work for SU2015 and newer but I’ve been incorrect many times.

model = Sketchup.active_model
ents = model.entities

# for our purposes I'm just using the first entity as the maingroup.
@maingroup = ents[0]
@maingroup.material = "red"

#This bit will only iterate over the entities collection one time and gather up the intersecting walls.
wall_list = ents.find_all{|e| e.is_a?(Sketchup::Group) && e.name =~ /_WALL_ASSEMBLY_/ && !@maingroup.bounds.intersect(e.bounds).empty?} - [@maingroup]

puts "Found #{wall_list.size} intersecting walls"

# highlight the walls on the screen
model.selection.clear
model.selection.add(wall_list)

walls.skp (85.2 KB)


#3

I’m not sure if I understand the problem 100% so forgive me if this suggestion doesn’t pertain to what you’re asking…

One potential solution would be to create zones and first checking which of the zones the chosen wall intersects with and only testing against walls that also intersect those zones. I’m not sure if that’d actually speed up the search by much and may actually slow it down in certain scenarios.

EDIT: Bounds comparison typically isn’t very expensive, maybe it is in SketchUp, couldn’t really tell you.


#4

I don’t know how expensive your test for corner and tee intersections is, so I can’t predict whether you would see a noticeable improvement. The general notion is that if your test is order n-squared (because each element is tested against every other one) and if you can cull the list (reduce n) based on a order n test (i.e. something that tests each element one at a time against some fixed criteria) then there can be a substantial improvement in performance. As an example, there can be a dramatic improvement in finding intersections via Entities#intersect_with if you can eliminate things that can’t possibly intersect using a one-by-one test. The crucial point in your case is how to define “not in the vicinity” in a manner that is fixed and can be checked cheaply. But even then there is usually a minimum list size below which the time to process the culling exceeds the time saved. You’d have to do some experiments to decide. Also I’d point out that finding a way to use compiled C code for the inner calculation vs doing it in Ruby could make a big difference.


#5

I wouldn’t say the corner and tee intersection test is overly expensive, but I’m just hoping to somehow implement a very lightweight check that can rule out most of the wall segments that don’t matter.

Again the system isn’t broken but I’m always interested in a way to improve its performance, and I do think there is a possible performance problem when the number of walls gets larger. As suggested I think it is hard to predict if there can be a noticeable improvement by merely considering the code, I will probably need to do some empirical testing.

I also like the idea of creating a C routine for the culling process, I think this holds a lot of promise.