Note: testing if one 3d rectangle has a vertex in the other does not work. Imagine two identical cubes and rotating one by 45 degrees. They intersect, but neither cube has a vertex in the other.
Sorry I don't have code for you. I think you'd need to make a convex solid by intersecting all 6 planes of the first with the second, and then calculate the volume. It'd take me a few hours to think it through and code something and it's my end-of-day, but if nobody has answered by tomorrow I'll write an (unoptimized) version.
You've got me really curious about the project this is needed for, and it is a welcome diversion from my current lifetime-on-generics / abstract borrowing problem that I lost the whole weekend to.
The lazy way is probably to use intersection_test in parry3d::query - Rust with two Cuboid in parry3d::shape - Rust s
What do you need to do with the resulting intersection shape? i.e. render it, compute its volume, or something else?
If you just need to know if there is an intersection then the option proposed by @s3bk is probably good.
Otherwise, another option that occurred to me on the train is to use a more general purpose solids library like Fornjot (https://crates.io/crates/fj), and compose each cuboid from two tetrahedra.
But obviously this won't be as efficient as doing the calculations natively on the cuboids.
Which brings me to the next question: what level of performance do you need? Because, if need to intersect millions (or billions) of cuboids per second, the best solution would be to use the GPU through something like (https://crates.io/crates/ash), although that would certainly complicate your dependencies.
To clarify, you are looking for the intersection of two polygons? So if they are intersecting and non-co-planar, the result is a line segment? (The other commenters seem to think you are asking for the intersection of two solids, where the result may be a solid.)
In this case, you can first compute the intersection of the planes of the two rectangles (a line), then compute the intersection of this line with each of the rectangles.
Do you also need to handle the case where the rectangles are coplanar and their intersection is a polygon?
This is all 3d, not 2d. Objects are 3d-rectangles (I would use 'cube', but width, height, length are not always guaranteed to be the same). These 3d-rectangles / stretched cubes may be rotated. I need to do collision detection on these objects, and am trying to figure out the fastest way, as I need to run it on n^2 pai4rs (for n objects inside a 'cell').
These are also called "rectangular prisms."
OK. I think he means "rectangular solid". All corners are 90 degree angles, correct?
Using "parry3d" is probably the easiest solution. If that won't solve your problem, come back and explain more clearly what you need.
Writing your own is not worth it today. Been there, done that, but you don't need to any more.
I really misinterpreted your question. I thought you were doing something with constructive solid geometry but had some idea to use cuboid primitives. I dreamed up an algorithm last night to calculate the intersection solid which would be a shape with at most 12 faces, 20 vertices, and 30 edges (an irregular dodecahedron with degenerate cases).
Anyway, I see that's totally overkill and a waste of compute power for your use case.
For intersection testing, I think the biggest performance gains are in building an axis-aligned-bounding-box hierarchy around your arbitrary cuboids to reduce the number of tests, rather than to brute-force test every cuboid against every other cuboid and micro-optimizing that test routine.
I believe this is referred to as "broad-phase collision detection", and then the more expensive testing of the cuboids that can rotate is the narrow-phase.
Literally hundreds if not thousands of research papers have been written on the topic of doing this efficiently, so you definitely want to use a library to get the benefit of all that work.
I've personally had good experiences with Bullet Physics, although I have never used the Rust crate. https://crates.io/crates/rubullet
I completely agree. The issue is that after two 3d-rectangle/boxes have intersecting Axis Aligned Bounding Boxes, we then have to run the fine grained algorithm.
Right. Broad-phase doesn't eliminate the need for narrow-phase, but can (in my experience) eliminate 95%* or more of the tests, meaning your hot-spot isn't on the narrow-phase test, unless you're trying to squeeze that last 2% of performance from your system.
*the 95% number is arbitrary and dependent on how off-axis, densely-packed, long and skinny, etc. the cuboids you are testing are.
To help searching I'd also suggest parallelepiped
Use the Hyperplane Separation Theorem. Two convex shapes don't intersect if and only if there is a plane separating them.
The separating plane can be chosen to either be parallel to one of the faces, or to be parallel to an edge of both cuboids.
First pick a set of possible directions orthogonal to the potential separating plane. So it is sufficient to check the following directions:
These directions can be found using cross products. But careful about parallel or almost-parallel edges, because you can run into numerical problems with that.
Once you have a direction orthogonal to the potential separating plane, project all vertices of both cuboids onto that direction (dot product). If all projections of one of them are smaller than all projections of the other one, you have a separating plane. If not, you don't.
@tczajka : Thanks, this is the type of answer I was looking for. I am now convinced that checking these 15 directions suffices.
A naive implementation would be to represent each cube as:
For each of the 15 direction, ignoring the cross product required to get normal to hyperplane, we have to do 4 dot products (center + 3 axis) with each cube. This is 15 * (4 * 2) = 120 dot(v3, v3) total. This puts us at 480 multiples already (or 120 simd ops).
Is this the best low level detail way to do this? (One alternative is representing each cuboid is center: v3, rot: quaternion, dim: v3, but not sure if it's faster).
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.