Metadata-Version: 2.2
Name: untangling26
Version: 2.0
Summary: Type-Free Global Intersection Analysis with Linear Displacement Fields (SIGGRAPH Asia 2026)
Requires-Python: >=3.10
Requires-Dist: numpy
Requires-Dist: trimesh>=4.12.2
Provides-Extra: dev
Requires-Dist: pybind11-stubgen>=2.5; extra == "dev"
Provides-Extra: gui
Requires-Dist: polyscope; extra == "gui"
Description-Content-Type: text/markdown

<div align="center">

# Type-Free Global Intersection Analysis with Linear Displacement Fields

### **ACM SIGGRAPH Asia 2026**

**[Chengzhu He](https://chengzhuuwu.github.io/)** &nbsp;·&nbsp; **[Xudong Feng](https://rullec.github.io/)** &nbsp;·&nbsp; **[Anjun Chen](https://chen3110.github.io/)** &nbsp;·&nbsp; **[Dan Song](https://zengjianhao.github.io/DanSongGroup/)** &nbsp;·&nbsp; **[Shihui Guo](https://www.humanplus.xyz/)** &nbsp;·&nbsp; **[Kui Wu](https://kuiwuchn.github.io/)**


<p align="center">
  <a href="https://chengzhuuwu.github.io/publication/siggraph-asia-2026-untangling/"><img src="https://img.shields.io/badge/Project-Page-blue?style=flat-square&logo=googlechrome&logoColor=white" alt="Project Page"></a>
  <a href="https://chengzhuuwu.github.io/files/untangling_siggraph_asia_2026.pdf"><img src="https://img.shields.io/badge/Paper-PDF-red?style=flat-square&logo=adobeacrobatreader&logoColor=white" alt="Paper PDF"></a>
  <a href="https://chengzhuuwu.github.io/files/untangling_supplemental.pdf"><img src="https://img.shields.io/badge/Supplemental-Material-orange?style=flat-square" alt="Supplemental Material"></a>
  <a href="https://youtu.be/cs_592tRAZQ"><img src="https://img.shields.io/badge/YouTube-Video-red?style=flat-square&logo=youtube&logoColor=white" alt="Video"></a>
</p>

<p align="center">
  <a href="https://github.com/ChengzhuUwU/Untangling26/actions/workflows/build_cmake.yml"><img src="https://github.com/ChengzhuUwU/Untangling26/actions/workflows/build_cmake.yml/badge.svg" alt="Build Status"></a>
  <a href="https://github.com/ChengzhuUwU/Untangling26/actions/workflows/build_wheels.yml"><img src="https://github.com/ChengzhuUwU/Untangling26/actions/workflows/build_wheels.yml/badge.svg" alt="Wheels"></a>
</p>

<p align="center">
  <img src="Document/Resp.jpg" alt="Type-Free Untangling Teaser" width="100%">
</p>

</div>

---

## Overview

Resolving self-intersections and multi-body penetrations without relying on non-penetrating collision history remains a fundamental challenge in physical simulation. Classical global intersection analysis (**GIA**) relies on explicitly classifying intersection contours into topological taxonomies and constructing 2D separating regions—an approach that easily breaks down on open boundary cuts, self-intersecting figure-eights, or complex multi-sheet nesting. Conversely, local intersection contour minimization (**ICM**) avoids explicit topological classification, but its reliance on local gradient descent along intersection lines frequently leads to severe local-minimum trapping under deep penetrations.

This work introduces a **type-free global intersection analysis** framework. For each contour, given a separation direction $\mathbf{r}\in\mathbb{S}^2$ and its (filtered) hit response support $\mathcal{S}(\mathbf{r})$, we evaluate the separation cost using a mass-weighted $L_2$ displacement metric analogous to the inertial term $\sum_i m_i \|\Delta\mathbf{x}_i\|^2$:

$$
\begin{aligned}
D_{\mathcal{C}}(\mathbf{r})
&=\max_{h\in\mathcal{S}(\mathbf{r})}\delta_h(\mathbf{r})\\
J(\mathbf{r})
&= \sum_{h\in\mathcal{S}(\mathbf{r})} m_h\, D_{\mathcal{C}}(\mathbf{r})^2
 = \rho\, D_{\mathcal{C}}(\mathbf{r})^2 \sum_{h\in\mathcal{S}(\mathbf{r})} A_h
\end{aligned} 
$$

where $m_h = \rho\, A_h$ is the mass associated with hit $h$, computed from the area $A_h$ of its source and destination primitives and the surface density $\rho$, and $D_{\mathcal{C}}(\mathbf{r})$ is the maximum ray travel distance of this contour.
All hits in $\mathcal{S}(\mathbf{r})$ share the same contour depth $D_{\mathcal{C}}$; we treat the area density $\rho$ as a uniform constant and drop it. By minimizing $J(\mathbf{r})$, we select separation paths that reconcile geometric untangling with the physical solver's lowest-energy displacement modes.


Given discrete edge--face (EF) intersection pairs, we treat each intersection contour $\mathcal{C}$ as a topological seed for constructing a separation response. 
For each contour, our pipeline alternates between freezing the physical state $\mathbf{x}$ to find the optimal separation direction $\mathbf{r}^\star = \arg\min J(\mathbf{r})$, 
and freezing $\mathbf{r}^\star$ to advance $\mathbf{x}$ via the global IP solver:

1. **Initialize** directed candidates $\mathbf{r} \in \mathcal{D}_0$ from contour-local geometry;
2. **Cast** to find the raw hit set $\mathcal{H}_{\mathrm{raw}}(\mathbf{r})$ via vertex-face (VF), edge-edge (EE), and face-vertex (FV) intersection tests;
3. **Filter** raw hits via dual-sided product-complex cluster culling, retaining only the physical component $\mathcal{S}(\mathbf{r})$ attached to the detected contour;
4. **Refine** selected candidates using projected Newton or Cauchy steps on $\mathbb{S}^2$, re-evaluating the filtered response objective $J(\mathbf{r})$ at each trial;
5. **Assemble** the final optimized hit set into solver constraints $\{C_k\}$ to advance the physical state $\mathbf{x}$.

<p align="center">
  <img src="Document/pipeline.jpg" alt="Ray-casting and hit-selection pipeline: intersection contour, raw VF/EE/FV hits, two-sided hit components, contour-anchored hits, and the applied response." width="100%">
</p>

The entire pipeline is history-independent, requires no topological case distinctions or manual contour taxonomy, and is implemented on the GPU via [LuisaCompute](https://github.com/LuisaGroup/LuisaCompute) across CUDA, DirectX 12, Vulkan, and Metal backends.

> **注意 / Disclaimer:**
> **本方案并不提供严格的解相交保证：对于自相交而言，在穿透较为复杂的区域，我们的 Cluster Culling 流程可能无法筛选出有修正语义的 RayCasting Hits；对于刚体相交而言，我们的方案可能会卡在物体的镂空区域。如何进一步提升系统的适用性与鲁棒性，是值得深入研究的方向。**  
> *(Note: This framework does not provide a strict untangling guarantee: for self-intersections in complex penetration configurations, the Cluster Culling procedure may fail to isolate RayCasting hits with restorative semantics; for rigid-body intersections, the method may become trapped in hollow or concave regions. Improving the general applicability and robustness of the system is an open and promising research direction.)*


## Quick Start (Pre-built Wheels)

### Command-line mesh repair

Version **2.0** includes a pip-installed `untangling26` command, following the
input/output style of [cuacd](https://github.com/eliphatfs/cuacd). With Python
3.13, install the published release using `python -m pip install untangling26==2.0`.
For a downloaded wheel, use `python -m pip install <wheel.whl>`. Earlier GitHub
v0.1/v0.2 assets identify themselves as package version 0.1.0 and do not include
this command. Source builds use `python -m pip install .` (requirements below).

Windows and Linux release builds target Vulkan; macOS builds target Metal.
A compatible GPU and driver are required even when `--physics cpu` is selected.
Wheel availability is platform-specific; an uploaded wheel has to match both
your operating system and Python version.

```bash
# One self-intersecting surface; deformable repair is the default.
untangling26 folded.obj repaired.obj

# Intersecting bodies in a shared world coordinate system.
untangling26 body_a.obj body_b.obj out/ --material rigid

# A scene or disconnected mesh containing several rigid bodies.
untangling26 assembly.glb repaired.glb --material rigid

# Smaller corrections for deeply folded cloth.
untangling26 folded.obj out/ --response-depth 0.005 --max-iters 400

# Select an available backend explicitly, and use GPU contour evaluation.
untangling26 folded.obj repaired.obj --backend vk --gpu-untangling

# Equivalent module invocation.
python -m untangling26 folded.obj repaired.obj
```

The command runs headlessly and requires no Polyscope. Inputs may be OBJ, PLY,
STL, OFF, GLB, or GLTF. Scene-instance transforms and relative body placement
are preserved. All inputs are normalized **together** to a largest extent of 1
for the solve; exported vertices are returned to the original coordinate
system and units. Exports contain triangle geometry and body names; materials,
textures, and animation are not retained.

An OBJ or GLB output contains the complete repaired scene. A directory output
contains `resolved.obj`, a separate OBJ for each body in a multi-body scene,
and `summary.json`. A file output has a sibling JSON report. The report records
the configuration, normalization transform, per-iteration intersection counts,
and whether the exported geometry reached zero detected EF intersections.
The command also exports the last checked mesh when its iteration budget is
exhausted. Exit codes are **0** for zero detected intersections, **1** for an
unresolved mesh, and **2** for an input/configuration/runtime error caught by Python.

| Option | Default | Meaning |
|---|---|---|
| `--material cloth\|rigid` | `cloth` | Deform a surface, or separate bodies using the solver's rigid material. A body's internal self-intersection requires deformable repair. |
| `--split-components` / `--no-split-components` | On for rigid | Register disconnected components as independent bodies. Separate input files and scene nodes are already separate bodies. |
| `--backend auto\|cuda\|vk\|dx\|metal` | `auto` | Select a compute backend bundled with the installed wheel. |
| `--physics cpu\|gpu` | `cpu` | Newton/PCG execution path. Both paths still require a supported compute device for collision detection. |
| `--gpu-untangling` | Off | Evaluate PRP contours on the GPU. |
| `--max-iters` | `200` | Maximum repair updates; 0 checks and exports the input. |
| `--response-depth` | `1.0` | Requested correction cap in normalized units. Smaller values can help deep folds. |
| `--direction-iters` | `0` | Optional direction-refinement trials per Newton iteration. |
| `--pcg-iters` | `200` | Linear-solver iteration budget. |
| `--max-contours` | `256` | Contours processed per repair update. |
| `--no-ccd` | CCD enabled | Disable CCD step-size checking. |
| `--overwrite` | Off | Replace existing outputs. Input files are always protected. |

Use `untangling26 --help` for the full interface. The repair criterion concerns
surface intersections: it does not certify the absence of solid containment,
and the algorithm does not guarantee convergence for every configuration.

Pre-built Python wheels target **Python 3.13** and run without a C++ compiler or
CMake. The [GitHub Releases](https://github.com/ChengzhuUwU/Untangling26/releases)
page also contains earlier demo packages; use version 2.0 for the command above.

We recommend using **[uv](https://docs.astral.sh/uv/)** as the environment manager: it is extremely fast and can **automatically download and isolate Python 3.13** even if you do not have Python 3.13 installed on your machine.

<details>
<summary><b>1. Install uv (if not already installed)</b></summary>

Install `uv` following the [official installation guide](https://docs.astral.sh/uv/getting-started/installation/):

- **Windows (PowerShell)**:
  ```powershell
  powershell -ExecutionPolicy ByPass -c "irm https://astral.sh/uv/install.ps1 | iex"
  ```
- **Linux / macOS**:
  ```bash
  curl -LsSf https://astral.sh/uv/install.sh | sh
  ```
- *Alternative Package Managers*: You can also install `uv` via `pip install uv`, `winget install astral-sh.uv`, or `brew install uv`.

</details>

#### 2. Fetch the repository (for demo scripts and mesh assets)

```bash
git clone https://github.com/ChengzhuUwU/Untangling26.git
cd Untangling26
```

#### 3. Setup Python 3.13 environment

Using **`uv`** (automatically downloads and sets up Python 3.13 without needing manual activation):

```bash
# Create .venv with Python 3.13
uv venv --python 3.13

# Install dependencies into .venv
uv pip install numpy trimesh triangle polyscope
```

<details>
<summary><b>Alternative: Using Conda</b></summary>

```bash
conda create -n untangling python=3.13 -y
conda activate untangling
pip install numpy trimesh triangle polyscope
```
</details>

#### 4. Install the pre-built wheel

Install the release matching your platform into `.venv`:

```bash
uv pip install "untangling26[gui]==2.0"
```

Use `uv pip install path/to/untangling26-2.0-....whl` for a downloaded release
candidate. If no compatible wheel is published for your platform, build from
source using the next section.

*(Note: If using Conda, replace `uv pip install` with `pip install`.)*

#### 5. Run an interactive demo

Launch the canonical unit demo with the Polyscope interactive GUI directly using `uv run` (no environment activation needed!):

```bash
# Interactive Polyscope viewer
uv run python PythonBindings/tests/demo_unit.py --scene_id 0

# Headless mode for automated benchmarks
uv run python PythonBindings/tests/demo_unit.py --scene_id 0 --headless --advance_frames 1
```

---

## Building from Source

If you prefer building the Python module (`lcs_py`) locally from source or wish to develop custom solvers, you can use the unified cross-platform workflow below:

```bash
# 1. Fetch the repository
git clone https://github.com/ChengzhuUwU/Untangling26.git
cd Untangling26
git submodule update --init --recursive

# 2. Setup Python environment (Python 3.13)
uv venv --python 3.13
uv pip install numpy trimesh triangle polyscope

# 3. Configure (CMake automatically detects the local .venv)
cmake -S . -B build -G Ninja \
  -D CMAKE_BUILD_TYPE=Release \
  -D LCS_BUILD_PYBINDINGS=ON

# 4. Build Python module
cmake --build build --target lcs_py -j 4

# 5. (Optional) Editable install into .venv
uv pip install -e . --no-build-isolation -C build-dir=build
```

*(On Windows PowerShell, replace trailing `\` line continuations with backticks `` ` `` or run `cmake` on a single line).*

#### Configurations

In Step `# 3. Configure`:

- **Build Tools**:
  - `CMake` (>= 3.26) is required: install from the [Release Page](https://github.com/Kitware/CMake/releases).
  - `Ninja` is recommended as the build generator: install from the [Release Page](https://github.com/ninja-build/ninja/releases).
  - `Clang/Clang++` (or MSVC / GCC): specify via `-D CMAKE_C_COMPILER=clang -D CMAKE_CXX_COMPILER=clang++`.
- **Python Environment**: When `-D LCS_BUILD_PYBINDINGS=ON` is enabled, CMake **automatically detects** your active virtual environment (`uv`, `conda`, `venv`, or `.venv` in the repository root) without needing manual paths. If you switch environments, CMake automatically invalidates stale cache. You can still explicitly specify an interpreter by passing `-D LCS_PYTHON_EXECUTABLE=/path/to/python`.
- **GPU Computing Backends**: LuisaCompute will automatically configure available backends. To explicitly specify a backend:
  - **Vulkan** (**Cross-platform**, Windows, Linux, and macOS): `-D LUISA_COMPUTE_ENABLE_VULKAN=ON`
  - **CUDA** (NVIDIA GPUs on Windows and Linux): `-D LUISA_COMPUTE_ENABLE_CUDA=ON`
  - **DirectX 12** (Windows): `-D LUISA_COMPUTE_ENABLE_DX=ON`
  - **Metal** (Apple Silicon macOS): `-D LUISA_COMPUTE_ENABLE_METAL=ON`

Vulkan builds default `LCS_ENABLE_DEVICE_LOG=OFF`: kernel printf would select a
legacy compiler path that cannot lower floating-point atomics. Host diagnostics,
device assertions, and BVH health flags remain enabled. Other backend builds
keep kernel printf enabled by default.

The compiled module is placed in `build/bin`. Benchmark scripts add this path to `sys.path` automatically.

## Demos and Benchmarks

Run all commands from the repository root after building `lcs_py` (or installing the pre-built wheel).

Using **`uv run`**, scripts automatically execute in the project's `.venv` without requiring manual environment activation:

```bash
uv run python PythonBindings/tests/demo_unit.py --backend cuda --headless --advance_frames 100 ...
```
*(Alternatively, if you prefer activating your environment beforehand via `.venv\Scripts\activate` or `source .venv/bin/activate`, you can simply run `python PythonBindings/tests/...`).*

On the initial run, LuisaCompute JIT-compiles device kernels (cached under `build/bin/.cache`), so subsequent runs execute significantly faster. Output files are saved to `output/paper_cases/`. Specify `--backend cuda` for NVIDIA GPUs, `--backend metal` on macOS, or `--backend dx` / `--backend vk` for DirectX / Vulkan.

All five demo entry points use **Polyscope GUI by default**. **Remove `--headless` from a demo command to enable the interactive Polyscope GUI shown below.** In the viewer, use **Space / Advance Single Frame** to step and **Run / Start Simulation** to play; pause with **Pause / End Simulation**.

<p align="center">
  <img src="Document/ui1.jpg" alt="Polyscope GUI showing a canonical untangling mesh and interactive simulation controls." width="100%">
  <br><em>Polyscope GUI: inspect meshes and advance the simulation interactively.</em>
</p>

### Canonical Configurations (Wicke et al. 2006)

Evaluates the seven canonical intersecting boundary and closed configurations from Wicke et al. (BBII, BIBI, BLI, Closed, Cross, Eight, and LL). The 2026-09-18 dual-metric Option C validation reached zero reported edge–face (EF) intersections in 2–5 solver iterations on both CPU and GPU contour-evaluation paths. Add `--export_debug` when per-frame OBJ/NPZ files are needed:

<p align="center"><img src="Document/cases_canonical.jpg" alt="The seven canonical contour configurations: inputs on the top row, resolved states on the bottom row." width="95%"></p>

For each case:
```powershell
uv run python PythonBindings/tests/demo_unit.py `
    --backend cuda --headless --advance_frames 100 `
    --use_subdivision --subdiv_levels 3 --scene_id 0
```

Or with batching command:

```powershell
0..6 | ForEach-Object {
  uv run python PythonBindings/tests/demo_unit.py `
    --backend cuda --headless --advance_frames 300 `
    --use_subdivision --subdiv_levels 3 --scene_id $_
  if ($LASTEXITCODE -ne 0) { throw "Canonical unit $_ failed" }
}
```

### Synthetic Fold

A procedurally generated multi-layer folding benchmark exhibiting deep, nested self-intersections:

<p align="center"><img src="Document/cases_synthetic.jpg" alt="Synthetic fold: initial state, initial ray hits, and resolved state." width="85%"></p>

```powershell
uv run python PythonBindings/tests/demo_synthetic.py `
  --backend cuda --headless --advance_frames 400 `
  --start_from_initial 1 --use_ccd_linesearch 0 `
  --untangling_response_depth 0.005 `
  --max_ef_pairs 10000
```

### Jang59 Benchmark

Animated previews of two groups of benchmark cases. Each group contains four animal, four human, and four miscellaneous meshes; red curves mark detected intersections.

<p align="center">
  <img src="Document/jang59_group1.gif" alt="Group 1: untangling four animal, four human, and four miscellaneous meshes." width="100%">
  <br><em></em>
</p>

<p align="center">
  <img src="Document/jang59_group2.gif" alt="Group 2: untangling another four animal, four human, and four miscellaneous meshes." width="100%">
  <br><em></em>
</p>

Evaluates against the [dataset](https://github.com/wonjongg/instant-mesh-intersection-repair) from Instant Self-Intersection Repair (ISIR, Jang et al. 2025) benchmark suite. Sample scenes from the official repository are bundled in the `external/instant-mesh-intersection-repair` submodule:

```powershell
git submodule update --init external/instant-mesh-intersection-repair
```

Validate case ordering and hashes without loading the solver, then run the gate:

```powershell
uv run python PythonBindings/tests/test_batch_method_comparison_enhanced.py `
  --backend cuda --begin 1 --end 59 --dry_run
```

```powershell
uv run python -u PythonBindings/tests/test_batch_method_comparison_enhanced.py `
  --backend cuda --headless --begin 1 --end 59 `
  --advance_frames 100 --timeout 300 --no_export_per_frame
```

The complete 59-case `Dataset_distributed` benchmark is subject to its original distribution terms; request it from the authors (wonjong@postech.ac.kr) and pass `--jang_dataset <directory>` to evaluate the full set. 

To inspect one Jang case, omit `--headless` and select, for example, `--begin 1 --end 1`. For multiple selected cases/methods, close a completed viewer to open the next one; closing before completion cancels the remaining runs and writes the partial report. `--timeout` applies only to headless workers, and `--dry_run` never opens a viewer.

### Static Repair from a Single OBJ

`test_load_from_obj.py` performs static self-intersection repair on any OBJ mesh: it loads the mesh, untangles it in quasi-static mode (no gravity, no floor), and writes the resolved surface as an OBJ, exiting with code 0 only on a clean collision report. The example below repairs the self-intersecting Klein bottle bundled with the ISIR submodule in five iterations (76 initial EF pairs to zero):

```powershell
uv run python PythonBindings/tests/test_load_from_obj.py `
  --backend cuda --headless `
  --input_mesh external/instant-mesh-intersection-repair/data/misc/disc_kleinbottle.obj
```

### Thingi10K Rigid Solids

Tests deep volumetric penetrations between watertight rigid solids (`MaterialType::Rigid`) from the Thingi10K dataset. Enabling `config.PRP_solid_interior_adjacency = True` establishes virtual volumetric chords connecting opposing entry and exit ray hits across the interior volume, avoiding topological disconnection around thick geometry. This benchmark evaluates 8 representative watertight models (300–2,600 faces) across CPU and GPU backends, comparing pure surface adjacency against solid interior adjacency:

```powershell
uv run python PythonBindings/tests/test_thingi10k_rigid_untangling.py `
  --backend cuda --headless --max_frames 35
```


Without `--headless`, Thingi10K previews one of the eight models, selected with `--case_index 1` through `8` (default: `1`). Choose the preview configuration with `--use_gpu 0|1` and `--solid_adj 0|1`; both default to `0`. For example:

```powershell
uv run python PythonBindings/tests/test_thingi10k_rigid_untangling.py `
  --backend cuda --case_index 1 --solid_adj 1 --max_frames 35
```


## Acknowledgments

Special thanks to [Xudong](https://rullec.github.io/) for his guidance and development support from [LuisaCompute](https://github.com/LuisaGroup/LuisaCompute) community.

This project builds upon [LuisaComputeSimulator](https://github.com/ChengzhuUwU/LuisaComputeSimulator) and [LuisaCompute](https://github.com/LuisaGroup/LuisaCompute). 

Reference (on untangling):
- [Unreal Engine](https://github.com/EpicGames/UnrealEngine/blob/release/Engine/Source/Runtime/Experimental/Chaos/Private/Chaos/PBDTriangleMeshCollisions.cpp): Implementation on EF intersection detection, and untangling baseline: ICM and GIA
- [instant-mesh-intersection-repair](https://github.com/wonjongg/instant-mesh-intersection-repair): For mesh-intersection-repair benchmark

## License

The source code is distributed under the [Apache License 2.0](LICENSE).

If you have any questions, feel free to contact with `chengzhuhe@stu.xmu.edu.cn`
