1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Have you looked at prior art? There's hundreds of 3d collision algortihms out there, each with their own pros and cos. For example, oct-trees are a very efficient collision algorithm for static data which is queried many times, but they can suffer poor performance with dynamic objects because you have to rewrite part of the tree. If you're only doing a single query, it's probably best to project the data into a 2d space (looking down the length of the infinite rectangle) and do your collisions there, but if you have to do multiple queries and objects may rotate over time,that starts to be slow $\endgroup$ – Cort Ammon Jan 24 '18 at 2:33
1
$\begingroup$

If I understand correctly, your $A$ is a 3D rectangular box, while your $B$ objects are polyhedra. Your box $A$ is arbitrarily long ("an infinitely long rectangle shape"), but you could make it finite.

It is common calculation in computer graphics to "clip" objects to a 3D box. There has been a large amount of work on this topic, in 2D and in 3D. For example, both the Cohen-Sutherland and Cyrus-Beck clipping algorithms extend to 3D. These algorithms have been fine-tuned to be efficient. So you might clip each polyhedron $B$ to the box $A$. If some of $B$ is inside $A$, then you have discovered that $B \cap A$ is non-empty, i.e., $B$ "overlaps" $A$ in your terminology.

You might first put a bounding box around each polyhedron $B$, to get quick decisions that $B \cap A = \varnothing$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.