CODEWITHSUNDEEP
algorithm3dgeometrycollision-detectioncomputational-geometry
treeseal7
treeseal7

Reputation: 749

simple 3d space collision check algorithm

I have a continuous 3d space defined by the inside space of 4 planes which meet at parallel lines (an infinitely long rectangle shape) - Lets call this 'A'. And then also in the model I have a bunch of closed convex 3d shapes which may or may not overlap into space 'A' - let's call each of these 'B'. What I'm looking for is an computationally efficient as possible algorithm process to decipher whether any of the 'B' shapes overlap 'A'.

*each of the 'B' shapes are defined by it's vertices, edges, and faces with planes etc... and the links between them.

*If some of that doesn't make sense I can do a few doodles...

So far my process for checking each 'B' shape against 'A' is as follows:

  1. Check if any of b's points are inside of all 4 of A's planes - if so => overlapping (if they all land in the same out space => no overlap)

  2. Check if any of a's parallel lines intersect with any of b's faces - if so => overlapping.

  3. check if any of b's edges intersect with any of A's 4 faces - if so => overlapping.

I also figured I could create an approximate bounding circle with centre point and radius for each 'B' shape to check first to quickly eliminate far away 'B' shapes...

** for parts 2 and 3 I use a function that checks if an edge intersects with a 3d object. This works by comparing the 2 points against against each plane making up the object to see if they are opposite sides and then if so finding the plane intersection point and checking if this intersection point is inside the 3d object or not.

This seems to work but I want to see if there is a better or quicker way of cracking the same nut? Maybe I've missed something obvious...

Thanks

Upvotes: 0

Views: 1545

Answers (2)

user1196549
user1196549

Reputation:

Continuing MBo's answer, you can find the useful outline of the B shapes by taking the (2D) convexhull of the vertices, which is a convex polygon.

http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull

Then apply the Sutherland-Hodgman clipping algorithm and see if a non-empty intersection remains.

https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

Upvotes: 1

MBo
MBo

Reputation: 80287

Note that for infinite rectangular "tube" you can reduce problem to 2D case: just project all points and edges onto the plane, perpendicular to tube.

Now you have to look for intersection of polylines (polygons) with rectangle (axis-aligned if you use points on generatrices of tube as base point and vectors) - this task is definitely simpler.

If your shapes are convex, polygons are convex too and SAT-method (Separating Axis Theorem) is very good (of course this is not true for links between shapes, they should be treated separately).

Upvotes: 3

Related Questions