artem-ogre/CDT

What is the coordinate system for this algorithm?

MWstudios opened this issue · 4 comments

MWstudios commented

I've noticed that predicates.h has been ported from quite an old library and that orient2D() could be replaced with a simpler dot product or something (mainly in locatePointLine() where the function simply checks if point is left or right to the line). I'm trying to test this theory, but in the API that I use (DirectX11), the Y axis is pointing downwards and, given all triangles are CCW, I can't find whether "Left" and "Right" are based on Y up or Y down. The samples don't mention what coordinate system is used.

Edit: I have done a millionfold test of a dot product (p.X - v1.X) * (v1.Y - v2.Y) + (p.Y - v1.Y) * (v2.X - v1.X) vs orient2D() and the results were... interesting. For small vectors (<100), orient2D() took ~22 ms and a dot product took ~28 ms. For large vectors (>1000), orient2D() took 90-110 ms and a dot product took 26-27 ms. Also, looking at the values in debug mode (double format), the dot ultimately ends up being more precise, orient2D() starts shifting off after 12 decimal digits or so. It seems that orient2D() is faster when it comes to conditions, but a dot product runs at the same speed.

artem-ogre commented

The predicates are robust adaptive predicates that use extended precision computations when necessary to guarantee a correct result for every possible floating-point input.
More details can be found in the paper: https://link.springer.com/content/pdf/10.1007/PL00009321.pdf

MWstudios commented

Ah I see. I'm porting the library to C# and was trying to find out how many methods can be stripped off. I keep getting point-out-of-triangle errors around the triangle walk stage and thought this was the issue. I'd like to post the results in here once I'm done fixing the bugs (a lot of typo-hunting is involved).

MWstudios commented

Anyway, for other people reading this, I found the answer:

  • All triangles are counter-clockwise.
  • locatePointTriangle() is processed in order: v1, v2, v3.
  • "Right" to the line (negative result) is considered outside of the triangle.
  • (p.X - v1.X) * (v1.Y - v2.Y) + (p.Y - v1.Y) * (v2.X - v1.X) returned the same as orient2D()

Therefore the system is X right, Y up. Visualisation:
obrazek
On DirectX and similar APIs, Y is down, therefore the triangles will be clockwise. Closing this for now.

  • 👍1
artem-ogre commented

Thanks, @MWstudios. This is correct. I have slightly updated the README to clarify coordinate system the winding applies to.