Our current mesh boolean evaluation depends on the Manifold library, which (as
the name implies) is restricted to manifold mesh inputs.
https://github.com/unageek/kigumi is an interesting additional option to explore
in that it explicitly supports partially bounded meshes, which might expand our
tolerance in facetization for non-closed inputs - except it currently depends on
CGAL.  The LGPL portions of CGAL we can manage as a dependency (similarly to how
we manage Qt) but it's currently using a GPL component as well - that rules it out,
unless we can replace that component with something like detria.

Below is a ChatGPT proposal for how we might go about seeing if we can make a
kigumi version that doesn't require the GPL aspects of CGAL.

Note that even if this works, we would still need the LGPL CGAL kernel and the
Boost.Multiprecision backend at a minimum.

# Objective

We want to modify `kigumi` so that it no longer depends on CGAL's GPL-licensed 2D triangulation component, while preserving the correctness and exactness properties of its Boolean/corefinement algorithms.

The proposed replacement is based on a fork/adaptation of [`detria`](https://github.com/Kimbatt/detria), which is MIT/WTFPL licensed and implements constrained Delaunay triangulation. The preferred approach is to retain `kigumi`'s existing CGAL exact geometry kernel for all geometric construction/predicates outside triangulation, while replacing only the GPL `CGAL::Constrained_Delaunay_triangulation_2` layer.

An alternative/fallback approach is to convert the exact planar coordinates to scaled integer coordinates and use detria's integer-coordinate path, provided we can establish that coordinate magnitudes can be kept safely within `int64_t` (or otherwise bounded appropriately). This should be treated as a fallback/experimental route, not assumed to be universally valid without proving the necessary bounds.

## Relevant repositories

* `kigumi`: [https://github.com/unageek/kigumi](https://github.com/unageek/kigumi)
* `detria`: [https://github.com/Kimbatt/detria](https://github.com/Kimbatt/detria)

## Current licensing situation

`kigumi` itself is MIT licensed.

It uses CGAL for geometric computations, including an exact kernel. Those kernel components are not the licensing problem of interest here.

The problematic dependency is CGAL's 2D constrained Delaunay triangulation:

```cpp
CGAL::Constrained_Delaunay_triangulation_2
```

which brings in CGAL's GPL-licensed 2D triangulation component (or requires a commercial CGAL license).

The goal is therefore specifically to remove this GPL dependency while continuing to use whatever CGAL exact-kernel functionality `kigumi` legitimately needs.

Do NOT assume that replacing the triangulator removes CGAL entirely. The expected architecture still uses CGAL's exact geometric kernel unless a separate future effort replaces that as well.

---

# Findings from tracing the current code

The important discovery is that the CGAL CDT dependency is unusually well isolated.

The primary wrapper is:

```text
include/kigumi/Triangulation.h
```

and the primary consumer is `Corefine`.

The `Triangulation` wrapper is relatively small and exposes only a very narrow abstraction to the rest of `kigumi`.

Conceptually, the current interface does the following:

1. Construct a triangulation associated with one original 3D triangle.
2. Insert the original triangle vertices.
3. Insert exact intersection points, retaining their original `kigumi` point IDs.
4. Add constraint edges between intersection points.
5. Later enumerate the resulting finite triangles as triples of original point IDs.

The rest of the code does NOT appear to depend on CGAL's half-edge topology, face data structure, vertex data structure, or other CDT internals.

This is extremely favorable for replacing the backend.

---

# What Corefine actually needs from triangulation

`Corefine` performs the geometric intersection work before triangulation.

For each affected source face, it constructs a `Triangulation` and inserts the points generated by the intersection process.

The intersection points already exist by the time triangulation happens. The triangulation backend is therefore not responsible for discovering arbitrary edge intersections.

The constraint structure is also explicitly constructed by `Corefine`.

For a set of three or more intersection points forming a closed boundary, the conceptual structure is:

```text
p0 -> p1 -> p2 -> ... -> pn -> p0
```

with each consecutive pair added as a constrained edge.

This means detria's lack of automatic edge-intersection resolution is not necessarily a problem here. `kigumi` has already performed the relevant intersection computation and point insertion.

The triangulator's responsibility is essentially:

> Given a planar point set, an enclosing original triangle, and a set of explicit non-crossing constraints, produce a constrained triangulation and return its triangles as original point IDs.

That is a much narrower problem than general 3D Boolean geometry.

---

# Current CGAL-specific behavior that must be understood

The existing implementation uses CGAL's:

* `CGAL::Projection_traits_3`
* `Triangulation_vertex_base_with_info_2`
* constrained triangulation face/data structures
* `CGAL::Constrained_Delaunay_triangulation_2`

The `Projection_traits_3` part is important.

`kigumi` is working with 3D points, but each individual triangulation is associated with one planar source triangle. CGAL's projection traits allow the 3D points to be treated as 2D points in the plane of that triangle.

A detria replacement cannot simply reinterpret the 3D coordinates as `(x,y)`.

Instead, establish a local 2D affine coordinate system for each source triangle.

For source triangle vertices `A`, `B`, and `C`, represent a point `P` in the triangle plane as:

```text
P = A + u(B-A) + v(C-A)
```

and use:

```text
A = (0,0)
B = (1,0)
C = (0,1)
```

for the local 2D representation.

This affine projection is preferable to introducing an arbitrary floating-point orthonormal projection because the existing CGAL kernel can calculate the coordinates exactly.

The resulting triangle indices still refer to the original `kigumi` point IDs; the local coordinates are only needed for triangulation predicates.

---

# Why stock detria is not automatically an exact replacement

This is the main technical concern.

`kigumi` uses an exact CGAL kernel in its exact configuration, specifically the equivalent of:

```cpp
CGAL::Exact_predicates_exact_constructions_kernel
```

The triangulation therefore receives exact geometric values.

Stock detria, by contrast, is designed around ordinary floating-point/integer coordinate representations and uses robust predicates derived from Shewchuk's adaptive floating-point expansion algorithms.

Those predicates are excellent for making robust decisions on the floating-point coordinates actually supplied to them.

However:

> Robust floating-point predicates do not make an arbitrary conversion from CGAL exact coordinates to `double` exact.

Therefore this is NOT an acceptable final design:

```text
CGAL exact 3D point
    -> to_double()
    -> detria double
```

if `kigumi` is to retain its exact Boolean guarantees.

The issue is not merely numerical precision in the final mesh. A single incorrect orientation or in-circle decision during triangulation can change the topology of the subdivision and consequently change a Boolean result.

---

# Proposed architecture: detria fork with exact predicates

The preferred implementation should investigate modifying/forking detria so that its triangulation algorithm can operate with an exact 2D point/predicate backend.

The important design principle is:

> Reuse detria's triangulation/topology algorithm, but do not force kigumi's exact coordinates through detria's floating-point coordinate representation.

A conceptual architecture is:

```text
kigumi
  |
  +-- existing exact CGAL 3D geometry
  |
  +-- Corefine
       |
       +-- exact intersection points
       |
       +-- Triangulation adapter
              |
              +-- exact affine projection
              |
              +-- exact 2D point representation
              |
              +-- detria triangulation algorithm
                     |
                     +-- exact orient2d
                     +-- exact incircle
                     |
                     +-- triangle indices
```

The exact predicate layer should be designed carefully rather than simply changing a typedef.

Delaunay triangulation requires at least:

* orientation tests;
* in-circle tests.

For an exact coordinate type, these should ultimately be evaluated exactly.

Since `kigumi` already has CGAL's exact kernel, one possible implementation is to represent local coordinates using the kernel's exact `FT` and implement the required predicates/constructions using CGAL's exact arithmetic, while keeping detria's topology/triangulation machinery.

The goal is to avoid bringing CGAL's GPL triangulation package back into the dependency chain. Using an LGPL-compatible/existing CGAL exact kernel for arithmetic is acceptable under the project's current licensing objective; the GPL CDT itself is what must disappear.

The detria-derived code should remain under a compatible permissive license, respecting detria's MIT/WTFPL licensing and the licensing of any copied/modified source components.

---

# Do not assume detria's API is a perfect drop-in

The current CGAL wrapper is incremental.

Conceptually it does:

```text
insert(point)
insert(point)
insert(point)
insert_constraint(a,b)
insert_constraint(c,d)
...
get_faces()
```

detria is more naturally batch-oriented:

```text
set/add points
add outline
add constrained edges
triangulate()
enumerate triangles
```

This is not a fundamental problem.

`Corefine` already builds the complete set of points and constraints before the triangles are ultimately requested.

Therefore the replacement `kigumi::Triangulation` can retain its existing external API while internally buffering:

```text
original triangle IDs
point IDs
local 2D coordinates
constraint edges
```

and then constructing/running the detria triangulation lazily when `get_faces()` is called.

The existing CGAL `Vertex_handle` abstraction can probably become a simple index-like handle, such as a `size_t` identifying an entry in the triangulation's point table.

There is no evidence that callers depend on CGAL vertex/face handles having any deeper semantics.

---

# Enclosing triangle / outline

The original source face is already the triangulation domain.

For local coordinates:

```text
A = (0,0)
B = (1,0)
C = (0,1)
```

the source triangle can be represented directly as a detria outline:

```text
{ A, B, C }
```

with the intersection points added as additional vertices.

This should be preferable to trying to reproduce CGAL's insertion/location mechanics.

The resulting constrained triangulation should cover the source triangle and respect all intersection constraints.

---

# Constraint handling

The constraints generated by `Corefine` are already explicit.

For example:

```text
p0 -> p1
p1 -> p2
p2 -> p3
p3 -> p0
```

can be passed directly to detria as constrained edges.

This is one of the strongest reasons detria is a good candidate.

The replacement should preserve the identity of every point: detria's output triangle should ultimately be translated back into the original `kigumi` point IDs.

Do not introduce duplicate geometric points merely because detria has a different internal point representation. If two vertices are intentionally the same `kigumi` point, their identity must remain consistent with the existing algorithm.

---

# Error/degeneracy behavior

The existing code has special handling for a CGAL exception corresponding to intersecting constraints / invalid self-intersecting input.

The replacement cannot blindly map every detria failure to the same exception.

Instead:

1. Identify all triangulation failure modes currently expected by `kigumi`.
2. Identify detria's corresponding failure/error conditions.
3. Define a small `kigumi`-level triangulation error abstraction if appropriate.
4. Translate detria failures into the existing user-visible behavior where the semantics genuinely match.

In particular, investigate:

* crossing constraints;
* duplicate constraints;
* duplicate points;
* collinear points;
* constraints sharing endpoints;
* points lying exactly on constraints;
* points lying exactly on the source triangle boundary;
* zero-area triangles;
* coincident/interior vertices;
* degeneracies affecting the Delaunay incircle predicate.

Do not assume that "detria triangulate returned false" is semantically identical to every CGAL exception.

---

# Important question: does kigumi actually require Delaunay quality?

The current implementation uses:

```text
Constrained_Delaunay_triangulation_2
```

and enumerates its finite faces.

The Boolean algorithm appears to care about the subdivision being correctly triangulated, not about triangle quality.

This raises the possibility that a generic constrained triangulation could suffice.

However, the first implementation should preserve Delaunay behavior because it is the closest semantic replacement for the existing code.

Only after establishing correctness should we investigate whether `triangulate(false)` or another simpler constrained triangulation mode is sufficient.

Do not make this simplification as part of the initial port.

---

# Preferred implementation sequence

## Phase 1: isolate the adapter

Rewrite only `kigumi::Triangulation`.

Do not modify the core Boolean algorithm.

The adapter should:

* accept the same logical inputs;
* perform exact affine projection;
* buffer points and constraints;
* invoke detria;
* return exactly the same type of triangle IDs.

Keep the rest of `Corefine` as unchanged as practical.

## Phase 2: fork/adapt detria

Create a small vendored/forked detria component.

Avoid unnecessarily changing detria's triangulation algorithm.

Instead, identify the minimal predicate/point abstractions required to support:

```text
exact Point2
exact orient2d
exact incircle
```

while retaining detria's triangulation logic.

Document every modification and preserve upstream provenance/licensing.

## Phase 3: differential testing

For every triangulation input generated by existing `kigumi` tests:

1. Run the existing CGAL CDT implementation.
2. Run the detria implementation.
3. Compare the resulting planar subdivision.

Do NOT initially require the exact same triangle diagonals if multiple valid triangulations are possible.

Instead compare the induced subdivision/topology appropriately.

For example, canonicalize each triangle using point IDs and verify that:

* all triangles lie within the source face;
* all constraint edges are respected;
* all expected regions are covered;
* no forbidden crossing occurs;
* triangle interiors do not overlap;
* all required vertices occur;
* the resulting subdivision is topologically equivalent.

If Delaunay behavior is retained, exact triangle-set comparison may often be possible, but do not make that assumption prematurely.

## Phase 4: final Boolean differential tests

Run the entire existing `kigumi` test suite with both backends.

Compare final Boolean results, not just triangulation output.

Use especially difficult cases involving:

* coplanar faces;
* touching edges;
* shared vertices;
* nearly coincident geometry;
* very small intersection regions;
* multiple intersection constraints;
* degenerate/collinear configurations;
* self-intersecting inputs;
* cases specifically designed to exercise exact predicates.

---

# Possible fallback: exact affine coordinates scaled to int64

If implementing exact predicates over CGAL's exact coordinate type proves too invasive, investigate a second approach:

```text
exact 3D CGAL point
       |
       v
exact local affine coordinates (u,v)
       |
       v
common-denominator scaling
       |
       v
integer (U,V)
       |
       v
detria integer-coordinate mode
```

For a source triangle:

```text
A = (0,0)
B = (1,0)
C = (0,1)
```

and every point:

```text
P = (u,v)
```

choose a common positive denominator `D` and transform all points:

```text
(U,V) = (D*u, D*v)
```

The transformation is a uniform positive scale, so it preserves:

* orientation;
* collinearity;
* side-of-line relationships;
* in-circle relationships;
* the combinatorial geometry relevant to triangulation.

This could allow stock detria's integer path to perform the triangulation without floating-point conversion.

However, this is only acceptable if coordinate magnitudes can be bounded safely.

CGAL's exact number types can represent values whose numerators/denominators are much larger than `int64_t`.

Therefore:

> Do not treat the int64 route as universally exact merely because the source geometry looks ordinary.

We need either:

1. a formal bound showing all generated coordinates fit safely;
2. an application-level documented coordinate/range restriction;
3. or a runtime overflow/range check that rejects cases outside the supported domain.

If none of those is acceptable, the exact-predicate detria fork is the correct solution.

---

# Why the int64 fallback is nevertheless worth implementing as an experiment

The int64 route could be substantially simpler and faster.

It also gives us a useful empirical test:

* generate exact affine coordinates from the existing `kigumi` test suite;
* determine the actual numerator/denominator sizes;
* calculate the maximum required common denominator;
* determine whether realistic Boolean workloads remain comfortably within signed 64-bit range.

If they do, the integer path may be a practical production solution even if a theoretical unrestricted EPECK proof is unavailable.

But the project should distinguish clearly between:

```text
mathematically unrestricted exact kigumi
```

and:

```text
exact for inputs satisfying documented integer-coordinate bounds
```

Those are different guarantees.

---

# Important licensing constraint for the fork

The replacement must be reviewed as a licensing/dependency exercise, not just an algorithmic exercise.

The desired final dependency graph is approximately:

```text
kigumi (MIT)
|
+-- CGAL exact geometry/kernel functionality
|     (existing permissible components)
|
+-- kigumi/detria-derived constrained triangulation
      (MIT-compatible licensing)
```

The final distribution must not accidentally pull in:

```text
CGAL::Constrained_Delaunay_triangulation_2
```

or another GPL CGAL triangulation component through an indirect include or library dependency.

If copying portions of detria into `kigumi`, preserve its license/copyright notices and document the provenance of modified code.

Also identify the provenance/license of any third-party predicate implementation copied into the fork.

This is a technical/legal dependency-removal project, so the final source tree and build system should make the dependency boundary obvious.

---

# Expected scope of kigumi changes

The likely primary changes are:

### `include/kigumi/Triangulation.h`

Replace the CGAL CDT implementation with the detria adapter.

This is expected to be the largest source change.

### `Corefine`

Potentially make small changes to:

* vertex-handle representation;
* triangulation error handling;
* exception translation.

Avoid modifying the core intersection algorithm unless testing demonstrates a genuine semantic mismatch.

### Build files

Modify `CMakeLists.txt` and related dependency configuration so that the GPL CGAL triangulation component is no longer required.

CGAL itself may remain required for the exact geometry kernel.

### Tests

Add a triangulation-backend differential test suite.

Ideally make it possible to build/run:

```text
CGAL reference triangulation
detria triangulation
```

side-by-side during development, while the production build only needs the detria implementation.

---

# Architectural principle

The key architectural boundary should become:

```text
                 exact geometry
                       |
                       v
                   Corefine
                       |
              planar triangulation
                       |
          +------------+------------+
          |                         |
   CGAL CDT backend         detria backend
       reference                production
```

The CGAL backend is useful during development as an oracle/reference implementation.

The detria backend is intended to become the production implementation.

Eventually the GPL CGAL CDT dependency can be removed entirely from the production build.

This separation also gives `kigumi` a cleaner architecture: the Boolean algorithm depends on an abstract "constrained triangulation of an exact planar subdivision", rather than on a particular CGAL data structure.

---

# Key technical questions the implementation session must answer

1. Exactly which detria source functions implement:

   * `orient2d`
   * `incircle`
   * point comparison
   * constraint handling
   * Delaunay edge flipping?

2. Can the detria predicate layer be cleanly parameterized for an exact 2D scalar/predicate implementation?

3. Does detria's topology algorithm assume any properties of floating-point coordinates beyond what exact predicates provide?

4. What exact operations are actually needed from the point type?

5. Can CGAL EPECK's exact `FT` be used directly for those operations without introducing GPL CGAL triangulation code?

6. How should exact affine `(u,v)` coordinates be calculated from a 3D source triangle?

7. Does the source triangle ever have degeneracy that makes the chosen affine basis invalid? If so, how does current kigumi handle that case?

8. What are the exact semantics of `kigumi`'s current insertion of points "inside", "on an edge", and "on a face"? Which of those distinctions are actually required by the final triangulation?

9. Are all constraints guaranteed to be non-crossing by the time they reach `Triangulation`, apart from intentionally invalid/self-intersecting input?

10. Which CGAL CDT error/exception conditions are observable by `Corefine` and must be reproduced?

11. Does final Boolean correctness depend on the particular Delaunay triangulation, or only on a valid constrained triangulation?

12. Can the output of CGAL CDT and detria be compared as planar subdivisions rather than exact triangle sets?

13. What happens for duplicate/collinear/coincident vertices?

14. Can the integer-coordinate fallback safely use `int64_t`, and if not, how quickly do exact affine-coordinate numerators/denominators grow on realistic inputs?

15. Does detria's integer implementation itself have any multiplication/intermediate-overflow limitations that require additional headroom beyond the nominal coordinate range?

---

# Success criteria

A successful implementation should satisfy all of the following:

* No production dependency on CGAL's GPL 2D triangulation component.
* Existing exact CGAL geometry functionality remains intact.
* No conversion of exact geometry to `double` in the production triangulation path unless exactness is explicitly proven unnecessary.
* Existing `kigumi` Boolean tests continue to pass.
* Differential testing against the CGAL implementation shows equivalent planar subdivisions/results.
* Degenerate and adversarial exact cases are tested explicitly.
* Self-intersection/error behavior remains compatible with existing `kigumi` behavior.
* Point IDs remain stable and correctly map through triangulation.
* The detria-derived source and any modifications have a clearly documented compatible license.
* The build system makes it possible to verify that the GPL CGAL triangulation dependency is actually gone.

---

# Recommended priority

The preferred order is:

1. **Understand and isolate detria's predicate/topology interfaces.**
2. **Implement the `kigumi::Triangulation` adapter using exact local affine coordinates.**
3. **Fork detria so its predicates can operate on the exact coordinate representation required by kigumi.**
4. **Differential-test against the current CGAL CDT implementation.**
5. **Only if exact predicates prove impractical, investigate the scaled-int64 detria path.**
6. **Do not compromise exactness merely to make stock detria usable.**

The central insight is that this should not be approached as "replace CGAL with a different geometry library."

It is better understood as:

> **Keep kigumi's exact 3D Boolean geometry intact, remove one isolated GPL triangulation backend, and replace that backend with detria's constrained-triangulation algorithm plus an exact predicate/coordinate layer.**

The existing code structure makes this unusually feasible. The principal engineering risk is numerical exactness, not API integration or the constrained-triangulation algorithm itself.

