4

I have programmed a triangle-triangle intersection algorithm, which have I have successfully tested for all distinctly different situations I could think of. I did this by manually inspecting all these situations using an online visualisation tool.

To be certain there are no bugs in the code, I would now like to test more comprehensively. My plan is to run an automated test for every possible configuration in a 100x100x100 grid in 3D space. Thus I either need a list with these coordinates and whether there is an intersection or not, or I need another algorithm that I can trust to produce the correct results.

Suggestions?

2
  • Could add some images to show exactly what you are looking for
    – PDHide
    Jun 1 '20 at 15:12
  • 1
    Excellent question!
    – dzieciou
    Oct 29 '20 at 12:59
1

I think you need 2 things:

  • a list of coordinates, that's your input you're gonna feed into your algorithm and into some good oracle
  • another algorithm, an oracle, that you can trust it solves the problem successfully

The second point might be a bit more complicated, but my quick search revealed there might be some implementation freely lying around on stackoverflow for instance, or another algorithm that's posted in the same stackoverflow discussion under one of the posts.

I'd get one of such algorithms and feed the test data both to your implementation and to this 3rd party algorithm and check whether or not the results are the same.

3
  • 1
    This does make me wonder why someone would roll their own implementation - i.e if you're going to trust another implementation as your source of truth for an A/B type of test, why wouldn't you just use that implementation?
    – ernie
    Jun 1 '20 at 17:22
  • 1
    @ernie: people constantly reinvent the wheel, that's why we have so many developers in the first place :D
    – pavelsaman
    Jun 1 '20 at 18:32
  • @ernie Another reason might be that another implementation might be in a different language or is bound to some specific technologies. In that case you may want to use another implementation as an oracle or re-use their test base for your implementation. This happens all the time when you port an algorithm from one language to another, e.g., Java to Python.
    – dzieciou
    Oct 29 '20 at 11:17
1

Danger! You're heading down a rabbit-hole here.

You will need to think very carefully about how you define triangle-triangle intersection and how you define correctness of the intersection algorithm. Some details to consider:

  • How are you representing the triangle vertices? Are the coordinates integers? Are they floating-point real numbers, that you assume are exact? Are they floating-point real numbers, that you assume are approximating the "true" locations of the vertices up to some error interval?
  • How are you defining intersection in the case where the two triangles are exactly coplanar? Coplanar up to machine precision? What about when the triangles lie on exactly parallel planes?
  • What is the expected behavior in the literal corner case where the two triangles intersect at exactly one point? When they share a common edge? The same concerns as above regarding exact arithmetic vs. machine precision also apply here.

There are algorithms that perform exact triangle-triangle intersection, carefully accounting for all of the above complications. The keyword to search for is exact geometric predicates (see also this survey about geometric robustness).

Practical intersection algorithms used in rendering or game collision detection are not exact: they live somewhere on the correctness-performance Pareto front where some false positives and false negatives are acceptable in "tough" cases where triangles are nearly coplanar or nearly intersection-free.

Testing is not trivial regardless of if you're testing an exact predicate or a "practical" approximate algorithm. Coverage will almost necessarily be incomplete (unless you assume the triangle vertices are restricted to some bounded integer lattice). The distribution on triangle pairs you will encounter in practice (arising from 3D geometry animated by an artist, or generated via physical simulation) will not look at all the same as the distribution of triangle pairs where each vertex is uniformly sampled from a cube or sphere. In particular, automated testing based on random triangles will miss all of the most important corner cases (where triangles are barely intersecting or non-intersecting; where triangles are on nearly-coincident parallel planes; etc.)

My advice is:

  • if you need exact geometric predicates, download an existing software package (which has been proved correct using formal verification). Don't try to roll your own.
  • if you need a high-performance approximate algorithm, download an existing software package (there are many that have survived extensive testing on large-scale real-world data). Don't try to roll your own.
  • If you are implementing an algorithm yourself for learning purposes, your approach is reasonable, but keep in mind that (a) it will be very difficult to get good coverage of all cases with randomized automated tests and (b) you will need to think very carefully about how to quantify correctness.

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.