Better Geometry Through Graph Theory (2018)

Better Geometry Through Graph Theory (2018)(ideolalia.com)

161 points by prospero 6 years ago | 33 comments

amuresan 6 years ago |

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

prospero 6 years ago | |

Hi, author here. I looked into that side of things, but CGAL only offers exact precision implementations for lines and circular arcs. The fact that Bézier curves are left as an exercise for the reader is further proof of the disconnect between computational geometry and modern computer graphics.

amuresan 6 years ago | | |

Fair point. At the same time the exact computation paradigm is proof that problems like these can be solved in a rigorous way if you start with the right foundation.

By the way thanks for writing the article, it was a refreshing read.

perl4ever 6 years ago | | |

I'm curious; I've played with OpenSCAD a little, which uses CGAL, and found it to be painfully slow (with no particular point of comparison). Do you think you have a way to do similar CSG calculations faster, or at least trade speed for accuracy or something?

zozbot234 6 years ago | |

'Exact real arithmetic' is probably the best starting point for what you're describing here. It does have plenty of application areas besides computational geometry. The issue with simple interval arithmetic is that intervals will widen when chaining multiple computations. To cope with this and obtain rigorous answers, one needs to set a required bound on the final result and do arbitrary-precision computations as entailed by that final bound.

ogogmad 6 years ago | | |

I believe Android's built-in calculator app takes this approach: https://dl.acm.org/doi/pdf/10.1145/2911981

It also uses rational numbers and arbitrarily large integer arithmetic.

westoncb 6 years ago | |

I wonder if anyone has thoughts on the approach taken here ("Sound and robust solid modeling via exact real arithmetic and continuity"): https://icfp19.sigplan.org/details/icfp-2019-papers/15/Sound...

kraghen 6 years ago | | |

I work on developing better tools for solving computational geometry problems robustly and efficiently, so I got quite excited when this paper first appeared.

However, while the type theoretic developments based on Abstract Stone Duality is interesting, they mostly ignore the problem of efficiency by simply representing every real number as a Dedekind cut. Thus, it doesn't scale without significant advances in compiling real arithmetic. A problem I'm working on presently, but it might take a few years...

NigelTheCreator 6 years ago |

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.

kmill 6 years ago | |

I'm not familiar with coedges --- they sound like the darts in the dual map of a planar combinatorial map[1] to me. Do you know if they correspond like this?

In short, a combinatorial map is a graph along with a counterclockwise order of incident half-edges ("darts") at each vertex. This is exactly enough data to record the topological information about how a given connected planar graph is embedded in the plane. They also work for graphs in general oriented surfaces, with the proviso that the complement of the graph consists of a bunch of faces homeomorphic to disks. For example, no annulus faces.

When reading the article, it seemed like what the author was doing was to construct something like a combinatorial map from the purported intersections then use that to answer inside/outside questions. (A graph by itself is unable to answer these questions since it's merely abstract vertices and edges. While the code they use shows the use of graphs[2], the graphs contain the geometric information of the vertex locations, which sort of lets you work with it as if it were a combinatorial map.)

[1] https://en.wikipedia.org/wiki/Combinatorial_map

[2] https://github.com/lacuna/artifex/blob/master/src/io/lacuna/...

openfuture 6 years ago |

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.