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?

  • \$\begingroup\$ Can you check first if a triangle potentially overlaps and if so move one triangle into other's local space and THEN use fixed point? \$\endgroup\$
    – Steven
    Commented Sep 9, 2015 at 14:47
  • \$\begingroup\$ @Steven, How would I do that without either using a wider fixed point format than 32 bits or floating points for conversion to local space? \$\endgroup\$
    – Kaganar
    Commented Sep 9, 2015 at 14:51
  • \$\begingroup\$ @Steven, Although, your comment made me realized I could do fixed point math wider than 32 bits.. I'd just have to emulate the 64-bit multiplies. \$\endgroup\$
    – Kaganar
    Commented Sep 9, 2015 at 14:52
  • \$\begingroup\$ If the deltas between the vertices in local space are small enough then you should have range in 32 bit fixed point, no? \$\endgroup\$
    – Steven
    Commented Sep 9, 2015 at 16:25
  • \$\begingroup\$ @Steven, The deltas are guaranteed to fit in a 32 bit range, but if we use a 32 bit fixed point format (e.g. GLfixed's 16-bit integer and 16-bit fraction) then in my use I'm likely to run into cases where the deltas would no longer fit. \$\endgroup\$
    – Kaganar
    Commented Sep 9, 2015 at 18:23


You must log in to answer this question.

Browse other questions tagged .