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.


#6

After testing out a model with over 100+ walls I’ve realized that I need to make some improvements to the algorithm, it is running far too slow and even a incremental improvement will be noticeable when you are talking about this many wall panels.


#7

This is by the way called “space partitioning”. It is a good solution to more efficiency, because in each (hierarchical) partition, you need less checks than if you iterate over all items in space.

Checking all items of a list gets expensive as soon as you have to do it more than once.
Then it is better to create a search data structure (an index) first and then query the index. When querying an index, you can take advantage of its ordering and have to do only very little checks (e.g. binary search). For 3D you can use binary space partitioning trees like octrees. However there are a lot of mistakes possible when implementing them on your own. I’m not sure if there exists a generic implementation for Ruby that can be adapted for SketchUp entities.

If the @maingroup is static (it is always the same in every invocation of the function) you could also simply create a sorted list with groups sorted by distance from the main group. When searching through the list you can abort as soon you have found the desired group, which is then more likely to happen earlier, so even without fancy data structures this should give a speedup for the average case.

Note that the sort and sort_by methods accept a block:

wall_list.sort_by{ |group| group.bounds.center.distance(@maingroup.bounds.center) }

Comparing the centers is only approximative but probably good enough. Alternatively you can sort by the shortest distance between all (8)×(8) corners. If groups are not in the same entities context, you need to transform the points that you compare to the same coordinate system. Do not forget to store the index in memory for re-use (class instance relating to @maingroup) and update it when walls are added/removed.


#8

I find grep with a block that uses next if and/or next unless to be the least expensive…

mg_bb = @maingroup.bounds
wall_list = []
group_list = Sketchup.active_model.entities.grep(Sketchup::Group) do |e|
  next if e == @maingroup
  next unless e.name =~ /_WALL_ASSEMBLY_/ && mg_bb.intersect(e.bounds).valid?
  wall_list.push(e)
end
wall_list

I would also check for any translation of the target name…

john


#9

Have you profiled your plugin or narrowed down what causes performance problems?

Filtering a list of 100 items by string/regexp comparison should be insignificant.
Using SketchUp’s methods for bounding box comparison should also be insignificant because SketchUp stores the bounding box (min, max points) with each group.

Any geometry manipulations or intersection tests of the real geometry (contained within the groups) are expensive.


#10

Here is the check I have currently employed, and yes it does speed things up considerably from my previous algorithm which did not limit the selection set (wall_list) and looped through all of the wall panel groups in the entire model:

group_list = Sketchup.active_model.entities.grep(Sketchup::Group)
wall_list = group_list.find_all { |e| e.name =~ /_WALL_ASSEMBLY_/ }
wall_list = wall_list.find_all { |e| !@maingroup.bounds.intersect(e.bounds).empty? }

My only concern is that if the bounding boxes are adjacent (ie. touching) but not overlapping will it still work? I still need to test this further.


#11

I wouldn’t identify walls by name as the user can rename groups to whatever they want. I always use attribute dictionaries to see if an entity “belongs” to my plugin. I also think it’s a bit faster, but haven’t run any benchmark to see.


#12

@eneroth3

I’m tending to agree with you on this one but my concern is that an attribute lookup is slower than checking the name like I am doing.

There is also the possibility where the user does not want the plugin to recognize a wall panel as a “plugin” wall panel, not sure why, but this would give them the ability to rename a particular wall panel so it is excluded from all further plugin operations. Or possibly rename the wall panel back so that it is again recognized by the plugin.

On a different note I’m a little bummed I didn’t get a few minutes to chat with you at basecamp. I got surrounded by a few people at the end of the panel discussion and never really got a chance to break away and say hi. It was nice to at least get to meet you in person, an honor.


#13

If this is the line of code all this thread is about, I doubt it is a major bottleneck of your plugin. Although it has linear time complexity, I would expect that with 100 groups it is faster than other operations in a plugin. Did you investigate if the slowdown could not be caused by something else?

SketchUp’s bounding boxes distinguish between zero size (one point contained) and invalid (no points contained). Testing whether a bounding box contains a point on its surface plane yields true. And testing whether a bounding box intersects with another one that share only one corner point yields also true, although the diagonal is zero. Intersection of two separate bounding boxes gives an invalid bounding box with zero diagonal.


#14

So if I’m understanding this correctly, even if the bounding boxes intersect at a single point then it will return true and hence this method will work for my circumstance.

The problem was that I was checking or looping through all of the wall panels in the wall_list and without first doing the bounds check it was naturally checking every single wall panel. When that number gets large it becomes rather slow since I am pulling from the attribute library of each wall panel group and calculating a number of things in order to check for corner conditions and tee intersections. By limiting this number to just the wall panels in the vicinity of the wall panel in question it significantly speeds of the plugin when the number of wall panels gets large (50+).

The improvement was so dramatic I’ve already released a new version of the plugin even though I will likely test this further to see if I can squeeze any more out of it or check for possible conditions where it might break down.