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}$.

The entire pipeline is history-independent, requires no topological case distinctions or manual contour taxonomy, and is implemented on the GPU via 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. 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.

# 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.

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 page also contains earlier demo packages; use version 2.0 for the command above.

We recommend using 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.

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

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):

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

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

conda create -n untangling python=3.13 -y
conda activate untangling
pip install numpy trimesh triangle polyscope

4. Install the pre-built wheel

Install the release matching your platform into .venv:

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!):

# 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:

# 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.
  • Ninja is recommended as the build generator: install from the Release Page.
  • 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:

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.

Polyscope GUI: inspect meshes and advance the simulation interactively.

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:

For each case:

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:

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:

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.

Evaluates against the dataset 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:

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

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

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

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):

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:

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:

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 for his guidance and development support from LuisaCompute community.

This project builds upon LuisaComputeSimulator and LuisaCompute.

Reference (on untangling):

• Unreal Engine: Implementation on EF intersection detection, and untangling baseline: ICM and GIA
• instant-mesh-intersection-repair: For mesh-intersection-repair benchmark

License

The source code is distributed under the Apache License 2.0.

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