intersect_retri

The triangles of one mesh retriangulated along the segments that cut them. One thread per triangle: a triangle no segment reaches is written as itself; a cut triangle is worked in its own plane, in world lengths, where its corners and the cut endpoints are the points and its sides and the cut segments are the constraints. The triangulation holds every constraint first (each cut out by the points that lie on it), then holds the remaining candidate edges shortest first, a length class at a time (the exponent and top three mantissa bits of the squared length), each when it crosses no held edge and has no point on it. The held edges are a planar graph: the neighbours of each point are sorted by direction, the faces are walked with their inside on the left, a face of three points is a triangle and a face of more is cut ear by ear (each ear a corner that turns left with no other point of the face inside it or on its sides), and the face outside the triangle is left out. Every triangle is wound the way the source triangle was, so the pieces of a triangle agree on the direction of every side they share however thin the sliver between two cut points. A triangle whose three points stand on one line in the world has no area and is left out. Every cut segment is a union of edges of the result, and the pieces of a triangle tile it. Points and distances are compared within a few steps of the coordinates' precision (5e-7 of the largest coordinate of the triangle, and no less than 1e-7 of its longest side), the same measure for a triangle of either mesh, so cut points a few millionths apart are told apart by the triangles of both meshes alike.

Param side names the mesh the pass cuts, 0 for A and 1 for B; a segment cuts the mesh when its endpoint records say so (intersect_core). A triangle takes every point of its entries, a segment of no length giving a point on an edge and nothing more.

STAGE count writes how many triangles each triangle becomes; STAGE write writes them at the offsets of the prefix sum, four words each (three vertex references, the source triangle) from word 4 of out. A reference below npts is a point of the mesh; npts + s is the cut endpoint in slot s, which intersect_unify's rep names. out[0] is 1 when a triangle ran out of working space, which the sizing below prevents. geometry.boolean builds the pieces of each mesh from out.

It binds pts, tri, cut, runs, order and out, with cnt in the count stage and off (the exclusive prefix sum of the counts) in the write stage; the params are npts, total, entries and side. Over a live count (COUNT=device, see the abi README) a triangle past the live ones becomes no triangle.

Working space

A triangle takes a slice of working memory sized by its entries, so the number of points a triangle can carry follows the data: a run of m entries gives at most 3 + 2 m points, 3 + m segments and three edges a point, and the slice is 64 + 40 m words. The slices of consecutive triangles follow one another and make the tail of out, after its 4 header words and the 4 * total words of the triangles (total is 0 in the count stage): the slice of triangle t starts 64 * t + 40 * first(t) words into the tail, first(t) the first entry of its run, so the runs' firsts are the exclusive prefix sum of their counts (the start of intersect_pairs for mesh A, the offsets of the per-b counts for mesh B). out is sized 4 + 4 * total + 64 * n + 40 * entries words from the params total and entries (the number of entries of intersect_pairs).

The triangles of mesh A are grouped by a already (runs is start and the counts of intersect_pairs, order the identity); for mesh B the entries are stably sorted by b first and order holds the sorted entry indices. Exact: each triangle is worked alone and in a fixed order.