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 . All the research around it is very interesting and refreshing to read.
By the way thanks for writing the article, it was a refreshing read.
Unfortunately, it's probably way beyond my ability to delve in to it.
It also uses rational numbers and arbitrarily large integer arithmetic.
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...
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, 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.)
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.
However, some of the issues raised in that article will still be a problem, and the solutions in either vector algebra or geometric algebra would similarly benefit from this approach.
One related trick I've seen recently is to purposefully degrade floating point performance (e.g.: using fp16 or just zooming in a lot) so that rounding errors and numerical instability can be "visually inspected". This is an under-utilised method that reveals that many common graphics algorithms are designed for infinite precision reals and aren't optimal for IEEE 754 reals.
And perhaps, certain other problems, like computational geometry, are in fact just really fucking hard, no matter how you express them. Having some familiarity with the space, where the only really quality implementations are a massive GPL research code base in C++ (CGAL) and commercial C Libraries (Parasolid, SMLib), I lean towards this view.
I'm referring to computational geometry for manufacturing and engineering simulation applications, which is an entirely different beast (in particular, accurately tracking topology is much more important, and generally requires arbitrary-precision floats for degenerate cases).
I also implemented other algorithms from scratch for solid body operations, and here indeed arbitrary precision rationals were needed first, but then I could get it working with normal double arithmetic in a lot of cases later on; I didn't use Metal here though.
I find that libraries like CGAL etc. are just either too slow or not general enough for my purposes. The whole sector seems ripe for disruption via proper algorithms implemented on graphics cards.
Making a game is a hard problem.
See Lisp on Playstation 2: https://en.wikipedia.org/wiki/Game_Oriented_Assembly_Lisp
Check out the demo https://observablehq.com/@enkimute/animated-orbits
Watch the SIGGRAPH talk https://youtu.be/tX4H_ctggYo
Join the discord https://discord.gg/vGY6pPk