Hi all,
I’m working on a model for laser cutting. There are a lot of taps made to lock into holes to make pieces connect precisely. However, as it is a quite complex model, it’s easy to forget drawing some of these connections and I sometimes accidentally end up with overlapping pieces.
Is there an extension for SketchUp that warns when two solids take up the same space?
there have been discussions on how difficult collision detection is using ruby, but I don’t recall any leading to an actual extension being made ‘publicly’ available…
in my own efforts, I found and sorted all nearest neighbours with a.bounds.intersect(b.bounds).valid? and then ran split to see if an additional object is created, if yes, I tagged the items and ran undo…
after this initial run, I opened each pair in a new model for manual repair and ‘paste and replace’ back into the original…
that part of it took advantage of the mac having multiple models and may not port to windows very well…
if you don’t find anything I’ll see if I can pull out useful tonight…
john
Some part of MSPhysics may be of use.
This probably is not exactly what you are looking for, but we made something similar some years ago. Perhaps the code can be modified.
Hide overlapping geometry
https://sketchucation.com/forums/viewtopic.php?f=323&t=61842
If I remember correctly MSPhysics only checks for collision between meshes and primitives, not mesh and mesh.
This seems to be finding adjacent meshes, not meshes taking up the same space.
It would be possible to iterate the meshes, check if the bounding boxes intersect, copy them and do a boolean intersect of the copies, but it would be a very slow algorithm that modifies the model when i really ant just to analyze it.
Another algorithm could be to iterate over a 3D grid of points, check what entity bounds the points are within and count the number of solids they are within (I already have code to see if a point is inside a solid). That would however fail if there aren’t any points just where two solids overlap.
Here’s an example ofthe kind of overlap I want to detect. Here it’s quite visible due to Z-fighting, but in other cases it is not.
Two solids are either non-overlapping, or one is within the other, or one intersects the surface of the other (or vice versa).
That means in a bad case, both solids have no vertex within the volume of the other solid, but still one solid intersects the middle of an edge of the other solid. And in the worst case, you don’t find such edges, but still one solid intersects the middle of a face of the other solid.
So the exact algorithm (finding space elements that contain entities of both solids and testing whether they would intersect) comes pretty close to actually intersecting entities with SketchUp’s method, only that it does not make changes to the model. The API gives us no efficient intersection tests, so implementing this in Ruby would be slower than SketchUp’s implementation. It can be accelerated with space partitioning tree datastructures (and checking bounding boxes before actual entity intersection), but the API does not give us access to the internal search datastructures.
You are right, the grid search has no guarantee to ever halt if there is no intersection, and only if the number of entities is very high (small facets where the other algorithm performs poorly) it has a good likelyhood to find an intersection faster.
If you just want to do it for one project and are satisfied with an approximate solution with high likelyhood, I would use your point-in-solid check for all vertices of one solid against the other (and vice versa). But it needs to consider points on the boundary as within the solid (and that is tricky).
just a thought…
all your tabs will be within a certain length tolerance, i.e. based on common material thickness…
if you find all these ‘short’ edges by length they should be in pairs, i.e. one in each piece at identical global positions…
if not one or the other piece is not cut…
john
In this case I think the simplest approach is very close to optimal. Assuming you don’t have more than say 300 groups and that the groups are fairly simple (a few hundred entities each) then the fastest way is probably to find all pairs of bounding box intersections and test those pairs with intersect_with. The intersection geometry can be put in a temp group that is reused for every intersect and the intersect part of the script can be contained in a model.start_operation - model.abort_operation.
Something like:
module OverlapChecker2000
def self.bb_intersect?(bb0, bb1)
return false if bb0.min.x > bb1.max.x || bb0.max.x < bb1.min.x
return false if bb0.min.y > bb1.max.y || bb0.max.y < bb1.min.y
return false if bb0.min.z > bb1.max.z || bb0.max.z < bb1.min.z
return true
end
def self.main
gs = Sketchup.active_model.selection.grep(Sketchup::Group)
intersection_pairs = []
t0 = Time.now
Sketchup.active_model.start_operation("Check Overlaps", true)
temp_group = Sketchup.active_model.entities.add_group
(0..gs.length - 2).each { |idx0|
(idx0 + 1..gs.length - 1).each { |idx1|
if bb_intersect?(gs[idx0].bounds, gs[idx1].bounds)
to_cut_tr = gs[idx1].transformation.inverse * gs[idx0].transformation
to_place_tr = gs[idx1].transformation.inverse
es = gs[idx0].entities.intersect_with(false, to_cut_tr, temp_group.entities, to_place_tr, false, gs[idx1].entities.to_a )
intersection_pairs << [gs[idx0], gs[idx1]] if es.length > 0
temp_group.entities.clear!
end
}}
Sketchup.active_model.abort_operation
t1 = Time.now
puts 'Pairs: '+intersection_pairs.length.to_s+" Time: "+(t1 - t0).to_s+" s"
end
main
end
Note that the bb_intersect? method is needed because the bounds.intersect method does not report an intersection if one box is fully contained in another (if my memory serves me…).
intersect_with is very fast for simple X simple or complex X simple, but very slow for complex X complex geometry, in which case it pays to introduce spatial data structures.
Also, if you want to always capture co-planarity you need to make two intersects:
es = g0.intersect_with(...g1) + g1.intersect_with(..g0)
That’s the annoying part. Otherwise I could just iterate all vertices on one and check if they are within the other using a ray casting algorithm. I’ve already written that code for my solid tools. For my specific case I may be able to take the midpoint of each edge and check if it’s inside another solid, but of course I want a general solution.
That’s a quite simple way to solve this specific case.
In a former life, I wrote Fortran code to calculate the intersection of arbitrary manifold volumes. The “general solution” involved incrementally iterating samples using a gradient search algorithm. If the incremental steps were too small, the calculations took forever. If it was too large, you risked jumping over a common interior point, but the computations completed in a reasonable amount of time (at least for 1970) . If all of your shapes are rectilinear, the solution becomes much simpler, but the general solution might consume a lengthy amount of time (especially in Ruby).
I think that this is a reasonable approach, but (obviously) the steps need to be small enough to make sure you don’t overlook anything. If you know in advance the potential amount of overlap with which you’re concerned, you could maybe size the steps accordingly.
This seems like a nice way to leverage the built-in SketchUp fuctionality to solve the problem.
A note on MSPhysics … the code is documented here:
https://www.rubydoc.info/github/AntonSynytsia/MSPhysics/MSPhysics
Without doing a lot of research, it appears to be based on a finite element model composed of types of shapes and their interactive properties. If your shapes are well-correlated with respect to the actual geometry, the results will be quite good. Otherwise …
Actually, this is a somewhat tricky problem since you probably want to accept coplanar overlaps, which means that we are looking for intersection volumes. A bare intersect_with is not enough in this case, you need some kind of solid operations. I would recommend to use inbuilt tools, they are hard to beat as long as the solids are fairly simple.
Here’s another try. The previous version is now used to filter out pairs that we do know intersect, to find the actual volumes we use boolean intersect on those pairs.
module OverlapChecker2001
def self.bb_intersect?(bb0, bb1)
return false if bb0.min.x > bb1.max.x || bb0.max.x < bb1.min.x
return false if bb0.min.y > bb1.max.y || bb0.max.y < bb1.min.y
return false if bb0.min.z > bb1.max.z || bb0.max.z < bb1.min.z
return true
end
def self.main
gs = Sketchup.active_model.selection.grep(Sketchup::Group)
intersection_pairs = []
t0 = Time.now
Sketchup.active_model.start_operation("Check Overlaps", true)
temp_group = Sketchup.active_model.entities.add_group
(0..gs.length - 2).each { |idx0|
(idx0 + 1..gs.length - 1).each { |idx1|
if bb_intersect?(gs[idx0].bounds, gs[idx1].bounds)
to_cut_tr0 = gs[idx1].transformation.inverse * gs[idx0].transformation
to_place_tr0 = gs[idx1].transformation.inverse
es0 = gs[idx0].entities.intersect_with(false, to_cut_tr0, temp_group.entities, to_place_tr0, false, gs[idx1].entities.to_a )
intersection_pairs << [gs[idx0], gs[idx1]] if es0.length > 0
temp_group.entities.clear!
end
}}
t1 = Time.now
intersection_pairs.each { |pair|
temp_group.entities.add_instance(pair[0].entities.parent, pair[0].transformation)
temp_group.entities.add_instance(pair[1].entities.parent, pair[1].transformation)
temp_group2 = temp_group.entities[0].intersect(temp_group.entities[1])
if temp_group2.entities.length > 0
# copy relevant information about the intersection volume from temp_group2 here...
######
######
temp_group2.entities.clear!
end
temp_group.entities.clear!
}
Sketchup.active_model.abort_operation
t2 = Time.now
puts "Find Pairs: "+intersection_pairs.length.to_s+" Time: "+(t1 - t0).to_s+" s"
puts "Boolean Intersect Pairs: Time: "+(t2 - t1).to_s+" s"
end
main
end