4971f0254d
Re-evaluated cost/benefit of Phase 8 vs Phase 9 after distinguishing three
concurrent goals:
• Goal A (Port): ~90% done, ~3 weeks remaining
• Goal B (CGAL): speculative, 12+ months, uncertain submission
• Goal C (Tool): research utility with novel features
Phase 8 full (3–4 weeks) would mostly serve Goal C plus optional Goal B.
Phase 9 (3 weeks) finishes Goal A unconditionally. Building Phase 8 in
full before Phase 9 risks 3-4 weeks of speculative architecture for a
hypothetical CGAL submission.
New strategy: Hybrid MVP.
Phase 8 MVP (3–5 days):
Conformal_map_traits.h concept + Default<Surface_mesh,K>
Discrete_conformal_map.h ONE entry: _euclidean()
4 named parameters Theta-map, max_iter, tol, pin
Concept-check header + Doxygen
Phase 9a (3–5 days): Inversive-Distance vs MVP API = acceptance test
Phase 9b + 9c (~2 weeks): Port truly complete
Phase 8 extensions: Only on concrete trigger
8a.2 generic FaceGraph trigger: Polyhedron_3 user
8c full doc trigger: submission planned
8d CGAL-format tests trigger: submission planned
8e YAML pipeline orthogonal, any time
Net committed budget: ~4 weeks for "port complete + CGAL MVP",
not 6–8 weeks for full Phase 8 + Phase 9.
Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
404 lines
21 KiB
Markdown
404 lines
21 KiB
Markdown
# Phase 8 — CGAL Package Design
|
||
|
||
> **Status: design frozen, implementation planned.**
|
||
> This document captures the strategic decisions taken before the first
|
||
> line of Phase 8 code is written. The decisions were taken on 2026-05-19
|
||
> after the docstring/architecture audit at the end of Phase 7.
|
||
>
|
||
> The design is informed by the CGAL package submission guidelines at
|
||
> https://www.cgal.org/developers.html and by reading the existing
|
||
> `Polygon_mesh_processing` and `Surface_mesh_parameterization` packages.
|
||
|
||
---
|
||
|
||
## Strategic position
|
||
|
||
| Question | Decision | Rationale |
|
||
|---|---|---|
|
||
| Submission to CGAL? | **Pre-submission-ready, not submission-bound.** 12+ months horizon, optional. | Keep design freedom, no editor-review pressure. Structure is valuable on its own. |
|
||
| License | **MIT preserved.** | CGAL submission would require LGPL — deferred. Current users (academic + industrial) profit from MIT. |
|
||
| Mesh-type flexibility | **Generic `FaceGraph + HalfedgeGraph`.** | Maximum CGAL value: works with `Surface_mesh`, `Polyhedron_3`, OpenMesh-adapter, pmp. |
|
||
| Parameter style | **Named Parameters** (`CGAL::parameters::vertex_curvature_map(...).max_iterations(50)`). | CGAL standard; identical UX to `PMP::triangulate_*`. |
|
||
| Default kernel | **`CGAL::Simple_cartesian<double>`.** | Status quo. Conformal geometry does not require exact predicates. |
|
||
| Backward compatibility | **Dual-layer wrapper.** `code/include/*.hpp` stays as implementation; `include/CGAL/*.h` is thin wrapper. | Existing 176 + 36 tests unchanged. New API gets new tests. |
|
||
| Algorithm code | **No duplication.** New CGAL headers delegate to existing code via property-map adapters. | Single source of truth; no parallel maintenance. |
|
||
|
||
---
|
||
|
||
## Architecture
|
||
|
||
### Three-layer model
|
||
|
||
```
|
||
┌──────────────────────────────────────────────────────────────────┐
|
||
│ Layer 3: Public CGAL API include/CGAL/*.h │
|
||
│ ───────────────────────── │
|
||
│ • Conformal_map_traits.h ← concept + default model │
|
||
│ • Discrete_conformal_map.h ← user-facing entry │
|
||
│ • Conformal_layout.h, ... │
|
||
│ Named parameters, generic over FaceGraph, Doxygen-documented. │
|
||
└──────────────────────────────────────────────────────────────────┘
|
||
▲
|
||
│ thin wrapper, no algorithm code
|
||
│
|
||
┌──────────────────────────────────────────────────────────────────┐
|
||
│ Layer 2: Adapter / Traits include/CGAL/Conformal_map/ │
|
||
│ ───────────────────────── │
|
||
│ • Default_traits.h ← maps generic FaceGraph to │
|
||
│ Surface_mesh property maps │
|
||
│ • Property_map_adapter.h ← read/write u, θ, α via │
|
||
│ boost::property_map traits │
|
||
└──────────────────────────────────────────────────────────────────┘
|
||
▲
|
||
│ uses existing algorithms as-is
|
||
│
|
||
┌──────────────────────────────────────────────────────────────────┐
|
||
│ Layer 1: Implementation code/include/*.hpp │
|
||
│ ───────────────────────── │
|
||
│ euclidean_functional.hpp, layout.hpp, newton_solver.hpp, ... │
|
||
│ Hardcoded to Surface_mesh + Simple_cartesian — unchanged. │
|
||
└──────────────────────────────────────────────────────────────────┘
|
||
```
|
||
|
||
---
|
||
|
||
## 8a — Traits class & concepts
|
||
|
||
### `ConformalMapTraits` concept
|
||
|
||
The concept lists the types and operations every Traits model must provide.
|
||
|
||
```cpp
|
||
namespace CGAL {
|
||
|
||
// Concept (documentation only; no code):
|
||
struct ConformalMapTraits {
|
||
// Types
|
||
using Triangle_mesh = ...; // model of FaceGraph + HalfedgeGraph
|
||
using FT = ...; // typically double
|
||
using Vertex_descriptor = boost::graph_traits<Triangle_mesh>::vertex_descriptor;
|
||
using Halfedge_descriptor = ...;
|
||
using Face_descriptor = ...;
|
||
|
||
// Read access (input geometry)
|
||
using Vertex_point_map = ...; // model of ReadablePropertyMap
|
||
// key: Vertex_descriptor
|
||
// value: K::Point_3
|
||
|
||
// Read/write access (conformal data)
|
||
using Lambda_pmap = ...; // u_v (scale factor) RW
|
||
using Theta_pmap = ...; // Θ_v (target curvature) R
|
||
using Vertex_index_pmap = ...; // DOF index (−1 = pinned) RW
|
||
using Edge_alpha_pmap = ...; // α_e (hyperbolic only) RW
|
||
using Face_type_pmap = ...; // geometry tag per face R
|
||
|
||
// Optional output
|
||
using UV_pmap = ...; // halfedge → (u, v) ∈ ℝ² W
|
||
using Holonomy_pmap = ...; // seam edge → ω ∈ ℂ W
|
||
};
|
||
|
||
}
|
||
```
|
||
|
||
### `Default_conformal_map_traits<TM>`
|
||
|
||
The default model wraps `Surface_mesh` property maps so existing code keeps
|
||
working through the new public API.
|
||
|
||
```cpp
|
||
template <class TriangleMesh,
|
||
class K = CGAL::Simple_cartesian<double>>
|
||
struct Default_conformal_map_traits;
|
||
|
||
// Specialisation for Surface_mesh:
|
||
template <class K>
|
||
struct Default_conformal_map_traits<CGAL::Surface_mesh<typename K::Point_3>, K> {
|
||
using Triangle_mesh = CGAL::Surface_mesh<typename K::Point_3>;
|
||
using FT = typename K::FT;
|
||
using Vertex_point_map = typename Triangle_mesh::Point_property_map;
|
||
using Lambda_pmap = typename Triangle_mesh::template Property_map<vertex_descriptor, FT>;
|
||
// ... etc, using "conformal:lambda" property names
|
||
};
|
||
|
||
// Generic specialisation for other FaceGraph models will be added in 8a.2.
|
||
```
|
||
|
||
### Concept-checks
|
||
|
||
```cpp
|
||
// include/CGAL/Conformal_map_concept_checks.h
|
||
template <class Traits>
|
||
struct Conformal_map_traits_check {
|
||
static_assert(boost::is_same<...>::value, "Traits::FT must be a floating-point type");
|
||
static_assert(is_face_graph<Traits::Triangle_mesh>::value);
|
||
// ...
|
||
};
|
||
```
|
||
|
||
---
|
||
|
||
## 8b — Public CGAL header hierarchy
|
||
|
||
### User-facing entry
|
||
|
||
```cpp
|
||
// include/CGAL/Discrete_conformal_map.h
|
||
namespace CGAL {
|
||
|
||
template <class TriangleMesh, class NamedParameters = parameters::Default_named_parameters>
|
||
bool discrete_conformal_map_euclidean(TriangleMesh& mesh,
|
||
const NamedParameters& np = parameters::default_values());
|
||
|
||
template <class TriangleMesh, class NamedParameters = ...>
|
||
bool discrete_conformal_map_spherical(TriangleMesh& mesh,
|
||
const NamedParameters& np = ...);
|
||
|
||
template <class TriangleMesh, class NamedParameters = ...>
|
||
bool discrete_conformal_map_hyperbolic(TriangleMesh& mesh,
|
||
const NamedParameters& np = ...);
|
||
|
||
} // namespace CGAL
|
||
```
|
||
|
||
### Named parameter vocabulary
|
||
|
||
| Parameter | Type | Default | Meaning |
|
||
|---|---|---|---|
|
||
| `vertex_curvature_map(pmap)` | ReadablePropertyMap | `2π` at interior, `π` at boundary | Θᵥ values |
|
||
| `fixed_vertex_pmap(pmap)` | ReadablePropertyMap<bool> | First vertex pinned | Which vertices are pinned (gauge) |
|
||
| `max_iterations(n)` | int | 200 | Newton iteration limit |
|
||
| `gradient_tolerance(eps)` | FT | 1e-10 | `‖G‖∞` threshold |
|
||
| `vertex_index_map(pmap)` | LvaluePropertyMap | DOF auto-assigned | Allows user to override DOF assignment |
|
||
| `output_uv_map(pmap)` | WritablePropertyMap | none | If set, writes UV layout into pmap |
|
||
| `cut_graph(cg)` | `Conformal_cut_graph` | auto-computed | Pre-computed seam edges (mandatory for closed surfaces) |
|
||
| `geom_traits(t)` | model of ConformalMapTraits | `Default_*` | Custom traits |
|
||
|
||
### Modular headers
|
||
|
||
```
|
||
include/CGAL/
|
||
├── Discrete_conformal_map.h ← user-facing entry (1 include for casual use)
|
||
├── Conformal_map_traits.h ← concept + Default_conformal_map_traits
|
||
├── Conformal_map_concept_checks.h
|
||
├── Conformal_newton_solver.h ← standalone Newton (advanced users)
|
||
├── Conformal_layout.h ← layout + holonomy
|
||
├── Conformal_cut_graph.h ← orthogonal algorithm
|
||
├── Conformal_period_matrix.h ← genus-1 τ (conformallab++ unique)
|
||
├── Conformal_holonomy.h ← Möbius holonomy (conformallab++ unique)
|
||
└── Conformal_map/ ← CGAL convention: implementation details
|
||
├── Default_traits.h
|
||
├── Property_map_adapter.h
|
||
├── Newton_iteration.h
|
||
└── Internal_helpers.h
|
||
```
|
||
|
||
---
|
||
|
||
## 8c — CGAL-style documentation
|
||
|
||
```
|
||
doc/Conformal_map/
|
||
├── PackageDescription.txt ← CGAL Doxygen package file
|
||
├── Conformal_map.txt ← Doxygen User_manual
|
||
├── examples.txt ← linkable example code
|
||
├── dependencies ← textual list
|
||
└── fig/ ← pipeline diagrams, math figures
|
||
```
|
||
|
||
All public functions, concepts, and types require Doxygen. See **Phase 7.5** (below).
|
||
|
||
---
|
||
|
||
## 8d — CGAL test format
|
||
|
||
```
|
||
test/Conformal_map/
|
||
├── CMakeLists.txt ← CGAL-format, uses find_package(CGAL)
|
||
├── test_euclidean_traits.cpp ← traits concept checks
|
||
├── test_polyhedron_3_backend.cpp ← tests with Polyhedron_3 as mesh
|
||
├── test_named_parameters.cpp
|
||
└── data/ ← test meshes
|
||
```
|
||
|
||
The existing GTest suite at `code/tests/cgal/` remains; CGAL-format tests are
|
||
added alongside as a separate target. CI runs both.
|
||
|
||
---
|
||
|
||
## 8e — Declarative YAML pipeline
|
||
|
||
A lightweight YAML format for reproducible experiments. CLI accepts
|
||
`--pipeline experiment.yml`; the validator checks `require`/`provide` tokens
|
||
before execution.
|
||
|
||
**Full spec:** [doc/concepts/declarative-pipeline.md](../concepts/declarative-pipeline.md)
|
||
— token vocabulary, validation algorithm, 5 complete examples.
|
||
|
||
```yaml
|
||
pipeline:
|
||
name: flat_torus_period
|
||
geometry: euclidean
|
||
input: { source: data/torus.off }
|
||
steps:
|
||
- { id: setup, unit: setup_euclidean_maps, provide: [maps_initialised] }
|
||
- { id: gb, unit: enforce_gauss_bonnet, require: [maps_initialised], provide: [gauss_bonnet_satisfied] }
|
||
- { id: solve, unit: newton_euclidean, require: [gauss_bonnet_satisfied], provide: [x_converged] }
|
||
- { id: cut, unit: compute_cut_graph, require: [mesh_closed], provide: [cut_graph] }
|
||
- { id: layout, unit: euclidean_layout, require: [x_converged, cut_graph], provide: [layout_uv, holonomy] }
|
||
- { id: period, unit: compute_period_matrix, require: [holonomy], provide: [tau] }
|
||
output:
|
||
layout: out/torus_layout.off
|
||
json: out/torus_result.json
|
||
```
|
||
|
||
---
|
||
|
||
## Phase 7.5 — Doxygen infrastructure (prerequisite)
|
||
|
||
Before any Phase 8 code, the existing API surface must be extractable.
|
||
This is the prerequisite that bridges Phase 7 → Phase 8.
|
||
|
||
```
|
||
Phase 7.5 — Doxygen infrastructure
|
||
──────────────────────────────────
|
||
• Doxyfile (CGAL-conform: INPUT=code/include + include/CGAL,
|
||
EXCLUDE_PATTERNS="* 2.hpp")
|
||
• doxygen-awesome-css as theme (matches CGAL house style)
|
||
• CMake target: cmake --build build --target doc
|
||
• CI job: doc-build → publishes to Codeberg Pages or gitea-pages
|
||
• Extract baseline once → snapshot what is actually exported today
|
||
• Top-5 central headers (3 functional + conformal_mesh + layout)
|
||
upgraded to Doxygen comments; the rest follows during Phase 8 implementation
|
||
```
|
||
|
||
The baseline snapshot doubles as the API-design review tool: before designing
|
||
the public CGAL wrapper, we see exactly which functions, classes and free
|
||
operators exist and need to be wrapped or hidden.
|
||
|
||
---
|
||
|
||
## Validation criteria
|
||
|
||
Phase 8a is "done" when:
|
||
|
||
1. `cgal.ConformalTraits.Polyhedron_3_works` passes.
|
||
2. `cgal.ConformalTraits.Surface_mesh_default_works` passes — identical results to the legacy API.
|
||
3. The Inversive-Distance functional (Phase 9a) is implementable as the *first* new client of the traits API without architectural changes — no breaking changes to the trait concept.
|
||
4. A user can write `#include <CGAL/Discrete_conformal_map.h>` and call `discrete_conformal_map_euclidean(mesh, parameters::vertex_curvature_map(theta))` against a `Polyhedron_3` and get a valid layout.
|
||
|
||
If any of these fail, the design is iterated before continuing.
|
||
|
||
---
|
||
|
||
## Implementation strategy — "Hybrid MVP" (decided 2026-05-19)
|
||
|
||
After cost/benefit re-evaluation, the plan is **not** to build Phase 8 in full
|
||
before resuming the port. Instead:
|
||
|
||
```
|
||
┌────────────────────────────────────────────────────────────────────┐
|
||
│ PHASE 8 MVP (3–5 days) │
|
||
│ ───────────────────── │
|
||
│ Just enough CGAL-style architecture for Phase 9a to validate it. │
|
||
│ │
|
||
│ • Conformal_map_traits.h concept + Default<Surface_mesh,K> │
|
||
│ • Discrete_conformal_map.h ONE entry: _euclidean() │
|
||
│ • 4 named parameters Θ-map, max_iter, tol, pin │
|
||
│ • Concept-check header │
|
||
│ • Doxygen on these 3 headers │
|
||
└────────────────────────────────────────────────────────────────────┘
|
||
▼
|
||
┌────────────────────────────────────────────────────────────────────┐
|
||
│ PHASE 9a — Inversive-Distance (3–5 days) │
|
||
│ ────────────────────────────────── │
|
||
│ Built directly against the new traits API. This is the │
|
||
│ acceptance test for the MVP. │
|
||
│ │
|
||
│ If painless → MVP design is sound, continue with Phase 9b/9c │
|
||
│ If painful → iterate the traits design before going further │
|
||
└────────────────────────────────────────────────────────────────────┘
|
||
▼
|
||
┌────────────────────────────────────────────────────────────────────┐
|
||
│ PHASE 9b — Analytic HyperIdeal Hessian (1 week) │
|
||
│ PHASE 9c — 4g-polygon fundamental domain (1 week) │
|
||
│ ──────────────────────────────────────── │
|
||
│ Port really finished. v0.9.0 release possible. │
|
||
└────────────────────────────────────────────────────────────────────┘
|
||
▼
|
||
┌────────────────────────────────────────────────────────────────────┐
|
||
│ PHASE 8 EXTENSIONS — only on demand │
|
||
│ ───────────────────────────────── │
|
||
│ • 8a.2 generic FaceGraph specialisation when Polyhedron_3 user │
|
||
│ • 8b extend to spherical + hyperbolic when 9a pattern proven │
|
||
│ • 8c full User_manual + Reference_manual when submission planned│
|
||
│ • 8d CGAL-format test directory when submission planned│
|
||
│ • 8e YAML pipeline + CLI flag orthogonal, any time │
|
||
│ │
|
||
│ Each extension only when there is a concrete trigger. No │
|
||
│ speculative architecture for a hypothetical CGAL submission. │
|
||
└────────────────────────────────────────────────────────────────────┘
|
||
```
|
||
|
||
**Why this order?**
|
||
|
||
- Port-completion (Phase 9) is the higher-confidence value: well-defined,
|
||
~3 weeks of work, finishes Goal A.
|
||
- Full Phase 8 (3–4 weeks) speculative — only pays off if CGAL submission
|
||
actually happens, which is uncertain.
|
||
- Phase 8 MVP captures the architectural insight (traits + named params)
|
||
without the long tail. If the rest of Phase 8 is ever wanted, it's
|
||
additive — nothing built in the MVP needs to be thrown away.
|
||
|
||
**Total committed budget: 2 weeks (MVP + 9a) + 2 weeks (9b + 9c) = ~4 weeks
|
||
net work, 6–8 weeks calendar.** After that, the port is finished.
|
||
|
||
## Phase 8 MVP scope — what is and isn't in the first cut
|
||
|
||
| Item | MVP | Later | Reason |
|
||
|---|:---:|:---:|---|
|
||
| `Conformal_map_traits.h` concept | ✅ | — | Core abstraction |
|
||
| `Default_conformal_map_traits<Surface_mesh, K>` | ✅ | — | Status-quo wrapper |
|
||
| Generic `FaceGraph` specialisation | — | ✅ 8a.2 | Speculative until asked |
|
||
| `Discrete_conformal_map.h` — `_euclidean()` | ✅ | — | First entry function |
|
||
| `Discrete_conformal_map.h` — `_spherical()`, `_hyperbolic()` | — | ✅ 8b.2 | Pattern-replicates once 9a works |
|
||
| Named parameters: `vertex_curvature_map`, `max_iterations`, `gradient_tolerance`, `fixed_vertex_pmap` | ✅ | — | Essential 4 |
|
||
| Named parameters: rest (`output_uv_map`, `cut_graph`, …) | — | ✅ 8b.2 | Additive |
|
||
| Doxygen on MVP headers | ✅ | — | Same time anyway |
|
||
| Doxygen on legacy `code/include/*` | partial | ✅ 8c | Bulk later |
|
||
| `PackageDescription.txt` | — | ✅ 8c | Only if submitting |
|
||
| User_manual.md | — | ✅ 8c | Only if submitting |
|
||
| `test/Conformal_map/` CGAL-style | — | ✅ 8d | Only if submitting |
|
||
| YAML pipeline + CLI flag | — | ✅ 8e | Orthogonal, any time |
|
||
|
||
---
|
||
|
||
## TODO checklist
|
||
|
||
### MVP track (committed work, ~4 weeks)
|
||
- [x] Phase 7.5: Doxyfile + CMake doc target + duplicate cleanup
|
||
- [ ] **Phase 8 MVP — Traits + one wrapper**
|
||
- [ ] `Conformal_map_traits.h` — concept documentation
|
||
- [ ] `Default_conformal_map_traits<Surface_mesh, K>`
|
||
- [ ] `Conformal_map_concept_checks.h`
|
||
- [ ] `Discrete_conformal_map.h` with `_euclidean()` only
|
||
- [ ] 4 named parameters: Θ-map, max_iter, tol, pin
|
||
- [ ] Test: `cgal.ConformalTraits.Surface_mesh_default_works`
|
||
- [ ] **Phase 9a — Inversive-Distance (acceptance test for MVP)**
|
||
- [ ] `inversive_distance_functional.hpp` against new traits
|
||
- [ ] Gradient check + Newton convergence tests
|
||
- [ ] Doxygen on new headers
|
||
- [ ] **Phase 9b — Analytic HyperIdeal Hessian**
|
||
- [ ] Replace FD in `hyper_ideal_hessian.hpp`
|
||
- [ ] Symmetry + PSD checks unchanged
|
||
- [ ] **Phase 9c — 4g-polygon for genus g > 1**
|
||
- [ ] Extend `compute_fundamental_domain()` beyond genus 1
|
||
|
||
### On-demand track (only with concrete trigger)
|
||
- [ ] 8a.2: Generic `FaceGraph` specialisation (trigger: Polyhedron_3 user)
|
||
- [ ] 8b.2: `_spherical()` + `_hyperbolic()` entry functions (trigger: pattern proven)
|
||
- [ ] 8b.2: `Conformal_layout.h`, `Conformal_cut_graph.h` wrappers
|
||
- [ ] 8c: `doc/Conformal_map/PackageDescription.txt` (trigger: submission planned)
|
||
- [ ] 8c: User_manual + Reference_manual (trigger: submission planned)
|
||
- [ ] 8d: `test/Conformal_map/` CGAL-style tests (trigger: submission planned)
|
||
- [ ] 8e: YAML validator + CLI `--pipeline` flag (orthogonal, any time)
|