CODEWITHSUNDEEP
algorithmlanguage-agnosticcomputational-geometry
Kaganar
Kaganar

Reputation: 6570

Integer ops only 3D triangle-triangle collision detection

I've a need for 3D triangle-triangle collision detection using integer math only. Unfortunately, I'm not in a position where I can use 64-bit integers (only 32-bit) and my vertex values can be larger than 24-bit values. This makes overflows a tricky problem -- otherwise I could probably just use fixed point operations.

The good news is I don't need perfect accuracy -- after all, we're using integers. Additionally, it does not need to be continuous collision detection -- the velocities will be zero. But I may have large triangles tested for collision with small triangles, so coarse approximations of normals can lead to gross relative errors.

The triangles themselves are represented as triplets of 32-bit integer vectors.

Is there a way of doing this?

Upvotes: 1

Views: 165

Answers (2)

user1196549
user1196549

Reputation:

What about an axis-parallel bounding box test (which you probably perform anyway), with a recursive subdivision of the triangles in case of doubt ? (A triangle can be split in four sub-triangles by taking the midpoints of the edges).

A much tighter bounding will be achieved with additional planes, based on the evaluation of the max of ±x±y, ±x±y±z and the like (26 directions in total).

Just integer additions and halvings.

Upvotes: 1

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

This can be accomplished by several uses of computing the signed volume of tetrahedra. I described the idea in this MSE posting: "Find whether two triangles intersect or not in 3D."

Then your problem is reduced to ensuring that the cubic volume computation doesn't overflow. You could detect overflow and only resort to floating-point computations when necessary.

Upvotes: 1

Related Questions