3 ms·

Sounds like a reinvention of coedges to me, boundary representations track topology and geometry in separated structures. The approximation errors are always a

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 6y 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 https://en.wikipedia.org/wiki/Combinatorial_map [2] https://github.com/lacuna/artifex/blob/master/src/io/lacuna/artifex/utils/regions/Clip.java#L136 https://github.com/lacuna/artifex/blob/master/src/io/lacuna/...

kmill 6y 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 https://en.wikipedia.org/wiki/Combinatorial_map [2] https://github.com/lacuna/artifex/blob/master/src/io/lacuna/artifex/utils/regions/Clip.java#L136 https://github.com/lacuna/artifex/blob/master/src/io/lacuna/...