intersect_pairs

The entries of two meshes that cut each other. One thread per triangle of mesh A walks the bounding volume hierarchy of mesh B (the bvh family builds it, one primitive a triangle) and, for every triangle of B whose bounds overlap, lists each part of the cut of the two triangles that intersect_core states (the ordinary cut, the coplanar clips, the points on shared edges).

An entry is three words: a, b and the part. Two stages with an exclusive prefix sum (the scan kernel) between them: STAGE count writes how many entries each triangle of A has, STAGE write writes the entries at the offsets the sum gives, ordered by a and, within a triangle of A, in the order the tree is walked and the parts of a pair in increasing order. Exact: the entries and their order are the same on every run.

Bind apts, atri, bpts, btri, nodes and, in the write stage, start; params nb (triangles of B) and total (the sum of the counts, which sizes pairs, three words an entry). The count stage writes cnt. Over a live count (COUNT=device, see the abi README) a triangle of A past the live ones has no entries.

The intersect family

intersect is a kernel family: intersect_pairs, intersect_cuts, intersect_unify and intersect_retri (shared by intersect_core). Two triangulated meshes A and B go in; the pieces of both, cut along their common curve and along the regions they share, come out. geometry.boolean composes the family with bvh, scan, sort, compact and gather:

1. Build the hierarchy of B (bvh_codes, sort, bvh, bvh_pyramid per level, bvh_internal), one primitive a triangle (vstart 3 t, vcount 3).
2. intersect_pairs STAGE count, an exclusive scan of the counts, STAGE write: pairs (a, b, part), ordered by a. total is the scan's total, the number of entries.
3. intersect_cuts over total entries: the endpoint records, slot 2 * entry + e. Word 0 to 2 of a record are the position as f32 bits.
4. intersect_unify (three stages) over 2 * total slots: rep. compact of the slots with rep[s] == s numbers the cut points; a cut endpoint's point is the number of rep[s], and its position is the record's position.
5. intersect_retri for A with runs from the counts and start and order the entry indices, side 0, then for B with the entry indices stably sorted by b (sort on the b words) as order, runs the first and count of each b and side 1. STAGE count, scan, STAGE write. Vertex references at or above npts are cut endpoint slots, mapped through rep.

The pieces of each mesh share the cut points, so the two results agree along the curve and along the boundary of every shared region. Each piece lies on one side of the other mesh, or on its surface.

What a boolean reads

A boolean keeps pieces by what lies just outside and just inside each piece's centre, probed along the piece's normal against the other mesh (ray winding at both probe points). Pieces on the other mesh's surface read the same way:

• Same normal (the two surfaces coincide and face one way): the probe outside the piece is outside the other mesh and the probe inside it is inside the other mesh.
• Opposite normals (the surfaces coincide and face each other): the probe outside the piece is inside the other mesh and the probe inside it is outside.

Operation	Pieces of A kept	Pieces of B kept
union	outside probe outside B	outside probe outside A and inside probe outside A
intersect	inside probe inside B	outside probe inside A and inside probe inside A
subtract (A minus B)	inside probe outside B	outside probe inside A and inside probe inside A, flipped

A region shared with the same normal is kept once from A in a union and an intersection and dropped from both in a subtract; a region shared with opposite normals is dropped from both in a union and an intersection, and kept from A in a subtract.