Better Geometry Through Graph Theory (2018)

  • One geometric model that actually handles numerical approximations is called exact geometric computation. It's pretty interesting and starts by explicitly tracking arithmetic errors in the operations you do. At its core it's a mix of interval arithmetics and multi-precision floating point. This is something you can do since the floating point implementations on most (all?) CPUs give you strong guarantees on the error bound of floating point arithmetic operations and these are usually within 1 ulp (unit in the last place) of the correct result. Now you have an interval for the result and can build your geometric constructs on interval arithmetic rather than classic, single point scalar arithmetic.

    Geometry works with constructs, not numbers. An intersection is a construct, collinearity is a construct, orientation / handedness is a construct, etc. If you define your fundamental constructs to be rigorous then the algorithms you build on top will also be rigorous. If we consider the article's inside-outside test example, this result would be computed based on the intersections (intervals) we've computed. Since we know for sure the correct result is within our interval of error then inside-testing boils down to comparing intervals and we know there are three possible situations here: 1. [a, b] < [c, d]; 2 [a, b] > [c, d]; 3. [a, b] overlaps with [c, d]. In case 1 and 2 we have a robust conclusion and in case 3 we recompute the whole predicate with higher precision until it becomes decidable.

    The golden standard for exact geometric computation is CGAL [1]. All the research around it is very interesting and refreshing to read.

    [1] cgal.org

  • Sounds like a reinvention of coedges to me, boundary representations track topology and geometry in separated structures. The approximation errors are always a nasty issue and that is the no trivial work on a BREP modeling libraries, for different edge cases you need different algorithms and maybe even transform the geometry into a different parameter space to minimize the approximation errors on computing an intersection between geometries.

  • Bivector.net

    Implementing computer graphics should be done with geometric algebra.

    I don't know anything about this field but I know the difference between a clean, consistent API and a random hodgepodge of hacks.

    Since I don't know anything I'm not sure if GA allows you to avoid errors such as the one in the article but in typical HN fashion I'll be derailing with some left- field claim and a link to some other project.