3 ms·
>Even something seemingly simple such as saying "is point C to the left or right of the line A->B" is very hard in floating point. Is it? ie - construct a norm
by deadsy 10y ago
>Even something seemingly simple such as saying "is point C to the left or right of the line A->B" is very hard in floating point.
Is it? ie - construct a normal and take a dot product. That'll work the vast majority of the time. Near the line you'll start running into the FP precision limits. With 64 (...or even 32) bit floats that sort of distance is likely way smaller than anything that represents a practical distance, so just call it and say you are on the line. Of late I've been messing about with problems of this nature and I can't say it's been all that difficult. https://github.com/deadsy/sdfx https://github.com/deadsy/sdfx
- alkonaut 10y agoIt comes back to bite you in a hurry. You don't need arbitrary precision to represent arbitrarily small things but to not have algorithms break down. Simple things like "is p inside the polygon" changes from true to false by moving both point and polygon 1 unit to the right. See under the heading "geometric predicates can FAIL" here http://groups.csail.mit.edu/graphics/classes/6.838/S98/meetings/m12/pred/m12.html http://groups.csail.mit.edu/graphics/classes/6.838/S98/meeti... You are right that this happens only in edge cases. But you don't want that in a cad program if you have anything doing e.g point-in-polygon, triangulation or other such algorithms. I know from experience that you really should bake this into the very foundation of a cad package (if you see 2003 me, let him know)
- willangley 10y agoThe link didn't work when I tried it. I found "Robust Predicates and Degeneracy" with a search: http://groups.csail.mit.edu/graphics/classes/6.838/S98/meetings/m12/pred/m12.html http://groups.csail.mit.edu/graphics/classes/6.838/S98/meeti...
- alkonaut 10y agoThanks, not sure why my iOS clipboard pasted a link I copied a week ago... (corrected the link now)