Search for the intersection of two arbitrary cubes in 3d

Question

So, I would like to find out a function that allows you to determine if two cubes of arbitrary rotation and size intersect.

If the cubes are not arbitrary in their rotation (but tied to a certain axis), the intersection is simple; you check whether they intersect in all three dimensions, checking their boundaries to see if they intersect or are inside each other in all three dimensions. If they intersect or are within only two, they do not intersect. This method can be used to determine if arbitrary cubes are even candidates for intersection, using their highest / lowest x, y and z to create outer borders.

This is the first step. In theory, based on this information, we can determine which side they are from each other, which means that we can eliminate some of the squares (sides) from our intersection. However, I cannot assume that we have this information, since rotating cubes can make it difficult to determine simply.

My idea is to take each pair of ATVs, find the intersection of their planes, and then determine if this line intersects with at least one edge of each of the pairs of sides. If any pair of sides has an intersection line that intersects with any of their edges, then the quadras intersect. If none of them intersect, two cubes do not intersect.

Then we can determine the depth of intersection on the second cube, where the intersection plane intersects its edge (s).

This is just speculative. Is there a better, more efficient way to determine the intersection of these two cubes? I can come up with several different ways to do this, and I can also say that they can be very different in terms of the number of calculations needed.

I work in Java at the moment, but C / C ++ - the solutions are also cool (I can transfer them); even psuedocode, as this is probably a big question.

Answer 1

You should take a look at the field of computer graphics. They have a lot of money. For instance. Weiler-Atherton clipping algorithm . There are also many data structures that could make the process easier for you. To mention AABB ( Bounded by the axis of the frame ).

Answer 2

Try using the dividing axis theorem. It should be applied in 3d, as in 2d.

Answer 3

If you create polygons from the sides of cubes, then another approach is to use constructive space geometry (CSG) operations. By creating a binary spatial partitioning tree (BSP) tree for each cube, you can intersect them. The intersection results in many polygons representing the intersection. In your case, if the number of polygons is zero, the cubes do not intersect.

I would add that this approach is probably not a good real-time solution, but you did not indicate whether this should be done during the frame update or not.

Since porting is an option, you can look at the Javascript library, which contains the CSG located in

http://evanw.imtqy.com/csg.js/docs/

I ported this library to C # in

https://github.com/johnmott59/CGSinCSharp

Answer 4

To find the intersection (contact) points of two arbitrary cubes in three dimensions, you must do this in two stages:

1. Detect collisions. These are usually two phases, but for simplicity, let's just call it “collision detection”.

The algorithm will be either SAT (the dividing axis theorem), or some kind of extension / reduction of the polyhedron. Again, for simplicity, suppose you will use SAT.

I will not explain in detail, as others have already done so many times, and better than I could. It follows that collision detection is not intended to tell you where the collision occurred; just what happened.

2. If an intersection is detected, you need to calculate the contact points. This is done using the polygon clipping algorithm. In this case, let's use https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

There are simpler and better ways to do this, but SAT is easy to understand in 3d, and SH SH is also easy to think about, so this is a good starting point for you.