Categories
Research

Research and Production for Games

Visualizing and Evaluating Skin Weight Transfer

My goal for this project was to implement visualization methods that help artists gauge the accuracy of skin weight transfer methods, which takes the skin weights from an already rigged mesh, and assigns the correct weights to the target mesh. I compared two different weight transfer methods. First, Maya’s built-in copySkinWeights: which takes a vertex on the unrigged mesh, finds the closest point on the source mesh, and interpolates the weights at that point to determine the weights at the vertex. Next, a method developed by EpicGames, which copies the weights from the source mesh that have a high-confidence correspondence. For the remaining vertices, it computes the weights by interpolating from the transferred high-confidence weights.

To begin, I downloaded a character with an animation from Mixamo and imported it into Maya. In my first pass comparison, I unbound the shirt from the character, and then rebound it using Maya’s copySkinWeights and EpicGames’ Weight Inpaint method. Below is a playblast of each character. Notice that with the copySkinWeights there is a jagged concave area in the upper back region, while with the Weight Inpaint method, that area is smooth.

Now, I wanted to develop a method to visually compare the two algorithms. I created a heatmap using the error formula.

Expanding on the previous idea, I wanted to develop a dynamic heat map that shows the areas with the highest deformation error over the entire animation. I created a node that took the display/method mesh and reference mesh as inputs, and then took the 3D vertex position of each of the meshes. To calculate the deformation error, I calculated the Euclidean distance between the 3D vertex positions of the method I was evaluating and the 3D vertex position of the original mesh. This is calculated with:

di(t)=ximethod(t)xioriginal(t)2d_i(t) = \left\| x_i^{\mathrm{method}}(t) – x_i^{\mathrm{original}}(t) \right\|_2

where i represents the ith vertex of the matrix, ximethod(t)x_i^{\mathrm{method}}(t) is the 3D position of vertex i on the method mesh at frame t, xioriginal(t)x_i^{\mathrm{original}}(t) is the 3D position of vertex i on the original method at frame t.

To construct the heat map, we normalize and clamp with:

d~i(t)=min(di(t)c,1)\tilde{d}_i(t) = \min\left(\frac{d_i(t)}{c},\,1\right)

where c is the maximum deformation distance.

We then mapped the errors to colors and wrote all vertex colors to the output mesh with setVertexColors(). We then have our finished output mesh with our desired heatmap. As the animation changes, the input meshes will change, causing the heatmap to update with each frame. This was packaged into a UI for easier use.

Here is the heat map applied to a shirt that was rigged using Maya’s copySkinWeights:

Here is the heat map applied to a shirt that was rigged using EpicGames Inpaint method:

Reference: EpicGames Inpaint Method

TextDeformer: How can words shape the (virtual) world

Researched by: José Pablo Soto Sánchez

Introduction

Imagine handing a sculptor a block of clay and, instead of tools, just a sentence: “make this a giraffe.” No reference photos, no measurements, just words, and the expectation that the clay reshapes itself to match. That’s roughly what TextDeformer (Gao et al., SIGGRAPH 2023) does to a 3D mesh: given a source shape and a target text prompt, it deforms the geometry until a frozen vision-language model agrees that the render looks like the prompt.

What makes this interesting isn’t just the result it’s used purely as a differentiable critic. The actual “learning” happens directly on the geometry: a set of per-triangle Jacobian matrices gets optimized by gradient descent, the same way you’d optimize the weights of a network, except here the “weights” are literally how each triangle is allowed to stretch and rotate.

This post walks through reproducing the official TextDeformer codebase end-to-end on consumer hardware, the math that makes text-to-geometry gradients possible at all, and the specific things that broke along the way and how they got fixed.

Background

A few terms are worth pinning down before the method section, since the pipeline sits at the intersection of graphics and vision-language modeling:

TermPlain-language definition
CLIPA frozen, pretrained model that embeds images and text into the same vector space, so cosine similarity between an image embedding and a text embedding measures “how well does this image match this caption.”
Differentiable renderingTurning a 3D mesh + camera into a 2D image using operations (rasterization, shading) that support backpropagation, so pixel-level loss can flow gradients back to vertex positions.
Jacobian (per-triangle)A 3×3 matrix describing how a single triangle is locally stretched/rotated relative to its original shape. TextDeformer optimizes one of these per face, directly.
Poisson mesh reconstructionGiven a target Jacobian per triangle, solving a linear system to recover the vertex positions whose actual local deformation best matches those targets, in a least-squares sense.
Cotangent LaplacianA sparse matrix built from mesh geometry that encodes how each vertex relates to its neighbors; it’s the operator at the center of the Poisson solve.
ViT patchA Vision Transformer splits an image into fixed-size square tiles (“patches”) and treats each one like a token — patch size determines how fine-grained the model’s spatial resolution is.

Method

CLIP-guided losses

The core signal is cosine similarity between a rendered image’s CLIP embedding and the target text’s CLIP embedding:

Δclip=cos(fimg(I^)fimg(Ibase),  ftext(target)ftext(base))\mathcal{L}_{\Delta\text{clip}} = -\cos\big(f_{\text{img}}(\hat{I}) – f_{\text{img}}(I_{\text{base}}),\ \ f_{\text{text}}(\text{target}) – f_{\text{text}}(\text{base})\big)

But optimizing this alone tends to drift toward whatever image maximizes similarity to the prompt, not necessarily a smooth deformation of the source shape. TextDeformer adds a delta-CLIP term that instead matches the change in image embedding against the *change* in text embedding, relative to a fixed base render/prompt (e.g. “a cow”):

clip=cos(fimg(I^), ftext(“a giraffe”))\mathcal{L}_{\text{clip}} = -\cos\big(f_{\text{img}}(\hat{I}),\ f_{\text{text}}(\text{“a giraffe”})\big)

This directional formulation (used in prior CLIP-guided editing work) keeps the deformation anchored to the source identity instead of collapsing onto an unrelated “giraffe-like” blob.

Per-triangle Jacobians and the Poisson solve

This is the part that replaces a neural decoder entirely. Given the mesh’s gradient operator GG (one 3×3 block per face) and a diagonal mass matrix MM of face areas, the cotangent Laplacian is built as:

L=GMGL = G^\top M G

LL has a one-dimensional null space (constant functions), so the implementation drops the first row/column to pin a single vertex before it’s usable for Cholesky factorization. To go from optimized per-face Jacobians JJ back to vertex positions vv, the code solves the normal equations of a least-squares problem — find the vv whose actual gradient GvGv is as close as possible to the target Jacobians JJ, weighted by face area:

v=argminvGvJM2Lv=GMJv^* = \arg\min_v \| Gv – J \|_M^2 \quad\Longrightarrow\quad L\, v = G^\top M J

That linear system is factorized once per mesh with a sparse Cholesky solver (`cholespy`, GPU-resident) and re-solved every optimization step as JJ changes — cheap after the one-time factorization. A Jacobian regularization term, JI2\| J – I \|^2, keeps triangles from stretching into degenerate shapes.

Rendering and camera augmentation

Each step, a batch of random cameras (elevation drawn from a Beta distribution, azimuth uniform over 360°, random distance/FOV/lighting/background) renders the current mesh via nvdiffrast‘s differentiable rasterizer. Randomizing viewpoint and lighting every step is what prevents the optimizer from exploiting a single “good” camera angle instead of actually deforming the geometry.

Patch-level consistency loss

A second, separate CLIP ViT is used only for its intermediate patch features (via forward hooks on each transformer block). For pairs of cameras within the same batch that are close in elevation/azimuth, the patches that project to the same 3D vertex are compared — encouraging the same surface point to look consistent from nearby viewpoints, which curbs the multi-view incoherence (“Janus-face”-style artifacts) common to CLIP-guided 3D optimization.

Implementation

Getting the reference implementation running at all. 

The repo pins specific commits for nvdiffrast and installs igl unpinned via conda-forge. The unpinned igl immediately caused a break: igl.random_points_on_mesh  in  MeshProcessor.py expected a 2-tuple return (bary, face_idx), but the installed libigl build now returns a 3-tuple (B, FI, P). Fixed by unpacking a third, unused value — a reminder that “no version pin” in a 2023 paper repo means the API surface has already drifted.

Fighting the GPU context, not the geometry. 

The next failure had nothing to do with the algorithm:  dr.RasterizeGLContext() threw cudaGraphicsGLRegisterBuffer (CUDA error 304, cudaErrorOperatingSystem) on first render. [VERIFY: root cause inferred from the error code and hybrid-GPU laptop symptoms, not confirmed via driver-level logs] — the working hypothesis is that Windows was creating the OpenGL context on the integrated GPU while CUDA ran on the discrete GPU, breaking the CUDA↔GL interop nvdiffrast relies on. The pinned nvdiffrast commit doesn’t expose the pure-CUDA rasterizer (RasterizeCudaContext isn’t present in this build), so the fix was OS-level: explicitly forcing the Python process to the discrete GPU in Windows’ graphics settings, rather than a code change.

Finding the actual VRAM ceiling. 

With rendering working, the default config (batch_size=25train_res=512) ran out of memory on a 6 GB laptop GPU (RTX 4050) partway through the first step. The batch dimension and the render resolution both scale memory close to linearly, so both got reduced (batch_size=4train_res=256) until a full 2,500-step run completed without OOM. This became the baseline configuration for every later experiment.

Swapping CLIP backbones without breaking assumptions baked into the code. 

clip_model and consistency_clip_model are independently configurable, but the consistency-loss implementation (utilities/clip_spatial.py) hardcodes assumptions that only hold for the “Base” ViT variants: a for i in range(12) loop over transformer blocks (ViT-L/14 has 24), and an assertion that the patch stride evenly divides the patch size (ViT-L/14‘s 14px patch isn’t divisible by the default stride of 8, unlike 32px/16px). RN50 — a convolutional backbone — can’t be used for the consistency loss at all, since that code depends on ViT-style patch tokens that a ResNet simply doesn’t produce. ViT-B/32ViT-B/16, and RN50 (as the primary loss only) were compared under an identical seed/mesh/prompt to keep the comparison controlled; ViT-B/32 was kept as the default going forward, primarily because it fit the VRAM budget without further code changes.

Debugging a mesh, not the code.

A custom tuna.obj mesh failed with CHOLMOD: not positive definite inside the Cholesky factorization. The Laplacian LL is only positive-definite after pinning one null-space direction — which is correct for a single connected mesh, but insufficient if the mesh has multiple disconnected components (each contributes its own null direction). The tuna model’s eyes turned out to be separate, unwelded geometry. Diagnosing this required leaving the codebase entirely and going into Maya: using Mesh → Separate to count connected shells, Combine + Merge (vertex welding by distance) to attempt reattachment, and re-running Separate as the verification step (if it can no longer split the mesh, it’s genuinely one piece). Welding never fully closed the gap without visibly displacing the eyes during remeshing, so the pragmatic fix was deleting the eye geometry outright, producing tunaNoEyes.obj — a reminder that not every mesh bug is worth solving at the mesh level when the pipeline’s actual requirement (single connected component) can be satisfied more simply.

Stale caches and unattended runs.

MeshProcessor caches differential operators and Jacobian .npz files under <output_path>/tmp/ and silently reuses them if present — convenient for resuming, dangerous if the source mesh changes but the output path doesn’t: a later run against a re-exported (different vertex count) tuna.obj crashed in a sparse matrix multiply because the cached operators no longer matched. Once that class of bug was understood, a small driver script (run_batch.py) was written to chain multiple mesh/prompt runs sequentially — the single 6 GB GPU rules out any parallelism — each with a fresh output directory and its own log file, so a several-hour unattended batch could run overnight without one failed run silently corrupting the next.

Results

Five source→target pairs were run to completion on the final configuration (batch_size=4train_res=256ViT-B/32, single RTX 4050 Laptop GPU):

Source → TargetStepsWall-clock
cow → giraffe (spot.obj)5,0001h 14m
fish → shark10,0002h 37m
eiffel tower → rocket10,0003h 21m
tuna → shark (tunaNoEyes.obj, remeshed)10,0002h 33m
guitar → axe6009m 39s

Per-step cost stayed in a fairly narrow band (~0.89–1.2 s/step) across meshes of similar triangle count, and scaled with batch_size × train_res as expected from the rendering cost analysis above — the guitar → axe run at 600 steps was deliberately short (~10 minutes) as a fast-iteration sanity check rather than a converged result, and looks correspondingly less refined than the 10k-step runs.

Future Work

Validate mesh topology before the Poisson solve, not during it. 

The tuna.obj failure surfaced as a Cholesky exception deep inside training, three layers of traceback away from the actual cause (disconnected components). A pre-flight check — counting connected components with igl and failing fast with a clear message before any GPU work starts — would turn a confusing runtime crash into an immediate, actionable one, and is a small, self-contained addition to MeshProcessor.py.

Generalize the consistency-loss encoder beyond the “Base” ViT assumption. 

The hardcoded 12-layer loop and stride-divisibility requirement in clip_spatial.py make ViT-L/14 unusable for the consistency loss without a code change, and rule out testing community-trained checkpoints (e.g. LAION’s ViT-B-32 retrained on LAION-2B via open_clip) that share the same architecture but arrive through a different loading path than OpenAI’s clip package. Both are architecture-family limitations, not fundamental ones — worth fixing before running a broader backbone ablation.

Reference

https://threedle.github.io/TextDeformer

ShapeFlow: Morphing Between 3D Shapes

We also explored a method for morphing one 3D shape into another target 3D shape. We worked with ShapeFlow, a neural network that learns to deform an existing 3D shape into another through a continuous flow field. Given latent space encodings of a source and target shape, the model outputs a velocity field describing how each point on the source should move to arrive at the target. Because the flow is continuous and (under the right conditions) bijective, the resulting deformation is guaranteed to be free of self-intersections, and can optionally preserve volume. Both of these properties can be desirable for artists working with meshes, which makes ShapeFlow attractive for toolification.

The Model

ShapeFlow’s creators frame the deformation of source shape XiX_i into target shape XjX_j as an advection process–the movement of a conserved property through fluid flow. Each point xx on the source is carried along a flow field f(x,t)f(x,t) over an interpolation parameter t[0,1]t\in[0,1]. Then, the points of the deformed source shape ϕij\phi_{ij} are described as:

Φij(x)=x(1), where x(t)=x(0)+0tfij(x(τ),τ)dτ\Phi_{ij}(x)=x(1) , \text{ where } x(t)=x(0)+\int_0^t f_{ij}(x(\tau),\tau)\;d\tau

Training seeks the mapping Φθij\Phi_{\theta}^{ij} that minimizes the symmetric Chamfer distance between the deformed source and the target:

minθC(Φθij(Xi),Xj)+C(Xi,Φθji(Xj))min_\theta \quad C(\Phi_{\theta}^{ij}(X_i), X_j) + C(X_i, \Phi_{\theta}^{ji}(X_j))

So the output of ShapeFlow is this flow field or mapping Φθij\Phi_{\theta}^{ij} that describes how each point on the source shape should advect in order for the source to become the target shape. How are the inputs to ShapeFlow created? What do we feed to the model?

Recall, we said that the input to ShapeFlow is the pair of latent space encodings from the source and target shapes. For our implementation, we use an encoder that maps a mesh’s vertices to a latent space encoding using a single forward pass. The encoder is trained jointly with the deformer model, using the same Chamfer distance loss, so it learns to produce encodings that are useful for conditioning the flow field.

The Toolification

Our goal was to implement ShapeFlow as a Maya plug-in for artists’ use in stylization and retopology of one mesh to another. To increase usability, we added blendshapes between the source mesh and the deformed source mesh by extracting and exporting intermediate results along the deformation path (sampling ϕij(x)ϕ_{ij}(x) at intermediate values of tt). This way, an artist can scrub through the flow and select whichever stage best fits their needs.

Future Exploration & Improvement

While implementing ShapeFlow as a Maya tool for artists, we ran into some areas of exploration for the performance of the tool. With more time we would have done more experimenting and development to ensure the model’s capabilities are consistent and high-performing for our desired use cases. On the SGI timeline we ultimately decided to balance exploration and execution and forge ahead with building out the tool while noting areas for improvement:

  • Initialization Sensitivity: Since the initialization of the model weights are random, results can vary widely based on whether one initialization was “good” for the specific meshes being used.
  • Loss Function Limitations: One of the use cases we wanted to develop ShapeFlow for was to create intermediate expressions for a given face mesh with certain extreme expressions. However, when morphing between meshes that differ only in a small region–for example puckered lips vs. a neutral expression–the region may be too small to affect the Chamfer distance loss during optimization. Other loss functions are worth evaluating for these cases.
  • Pretraining: If there are certain use cases (classes of objects, faces) that ShapeFlow will be used for, it might be beneficial to do pretraining on those types of shapes. Currently, our tool trains the deformer model from scratch every time. (This is also why the initialization sensitivity affects the results so strongly.) As a result, the model either will take an extremely long time with an appropriate amount of training iterations, or be used after a lower number of training iterations with reduced fidelity.

We did some manual tuning to get workable results on our test meshes, but making this robust enough for an artist’s workflow requires additional experimentation, testing, and development.

Results

Below is a video demonstrating the Maya tool workflow. For the sake of time, in the video the model is only trained for 200 iterations (very low), which is one source of the poor or unfinished-looking output flow.

Below is an image showing how ShapeFlow can be used to produce a blend of two meshes. The ShapeFlow output (middle) is result of Toilet 1 (left) morphing into toilet 2 (right).

Reference

ShapeFlow

Categories
Research

Teaching a Mesh Which Way to Swim: Intrinsic Triangulations and the Anisotropic Laplacian

Introduction

Swimming with a current feels effortless; swimming across it is exhausting — even over the same distance in meters. That asymmetry isn’t a fact about water, it’s a fact about which notion of “distance” you’re using. This week’s project builds exactly that idea into a triangle mesh: a metric that makes some directions cheaper to move through than others. Along the way we needed two core tools from discrete differential geometry — intrinsic triangulations and the anisotropic Laplacian — and had to make both of them survive a real 3D shark scan, not just a hand-drawn toy mesh.

Background

A quick glossary before the derivations:

  • Mesh (V, F): vertex positions and the triangles connecting them.
  • Halfedge: a directed half of an edge, belonging to one triangle; its twin is the matching half from the triangle on the other side. This lets code ask “what’s across this edge?” in constant time.
  • Tensor field / metric S: a small symmetric, positive-definite matrix per triangle (2×2 in 2D, 3×3 on a 3D surface) describing how expensive movement is in each direction. S = I recovers ordinary Euclidean distance.
  • Intrinsic triangulation: a different triangulation of the same surface, changing only connectivity — never vertex positions.
  • Edge flip: the only move allowed — swap the diagonal of the quad formed by two triangles sharing an edge.
  • Delaunay triangulation: every edge satisfies the empty-circumcircle property; avoids thin, needle-like triangles.
  • Cotangent weight (wij): built from the two angles opposite an edge; decides both whether to flip it and what enters the Laplacian.
  • Harmonic field: a function solving Lf=0Lf=0 with fixed boundary values — “ink diffusing smoothly” between two fixed points.

Method: Intrinsic Triangulations

An intrinsic triangulation keeps a mesh’s lengths and angles — what an ant walking on the surface could measure — while reconnecting vertices via edge flips:

  i                 i
 /|\               / \
/ | \             /   \
m |  k   ====>   m --- k
\ | /             \   /
 \|/               \ /
  j                 j

This matters because it can fix badly-shaped triangles without adding a single vertex — useful whenever an algorithm only needs lengths and angles, not raw coordinates.

The special case is the Delaunay triangulation, equivalent to:
wij=12(cotα+cotβ)0    α+β180°w_{ij} = \tfrac12(\cot\alpha+\cot\beta) \geq 0 \iff \alpha+\beta \leq 180°

The proof is short: cotα+cotβ=sin(α+β)sinαsinβ\cot\alpha+\cot\beta = \frac{\sin(\alpha+\beta)}{\sin\alpha\sin\beta}​, and since α,β(0°,180°)\alpha,\beta\in(0°,180°) the denominator is always positive — so the sign of wij​ depends only on sin(α+β). Empty-circumcircle and angle-sum are the same condition. In code, this is a queue: flip any edge with negative weight, re-check its neighbors, repeat until none remain.

Method: The Anisotropic Laplacian

To make distance direction-dependent, attach a metric MMM to each triangle: vM=vMv\|v\|_M=\sqrt{v^\top Mv}​. M must be symmetric (for real eigenvalues/perpendicular axes) and positive-definite (so no length comes out negative or imaginary).

The pleasant surprise: the Delaunay proof above never used Euclidean angles specifically — only that they’re triangle angles in (0°,180°). Measuring α,β with M instead, the same algebra holds, so the criterion is unchanged in form. On a fixed test quad, switching S from identity to diag(1,16) flips the verdict entirely (w: +0.72 → -1.37) — same vertices, different verdict on whether the edge should exist.

The same wijw_{ij}​ assembles the Laplacian (Lij=wijL_{ij}=-w_{ij}, Lii=jwijL_{ii}=\sum_j w_{ij}​), which must satisfy: rows sum to zero, symmetric, constants in the kernel. When all wij0w_{ij}\geq0 (i.e., Delaunay), LL also satisfies the maximum principle — solutions to Lf=0Lf=0 extremize only on the boundary. That guarantee is the entire reason the flip exists before building anything on top of LL.

Implementation

The build order, including what broke:

Synthetic 2D test bed: HalfedgeMesh with flip_edge/flip_to_delaunay, validated on a hand-built non-Delaunay quad and a randomly-scrambled disc.

Toy 2D fish: solved a harmonic field (nose=0, tail=1) with the ordinary Laplacian, took its per-triangle gradient as the “body direction” dd, and built S=αdd+β(Idd)S=\alpha\,dd^\top+\beta(I-dd^\top), α<β\alpha<\beta— cheap along the body, expensive across it.

Real 3D shark scan — the actual porting work:

Cleanup: weld coincident vertices, drop degenerate (zero-area) faces, since these send cotangent weights to nan and corrupt connectivity.

Automatic nose/tail: SVD on centered vertices finds the principal axis; nose and tail are its two extremes.

A genuinely 3D gradient: no single “perpendicular” exists on a surface, so the normal nn and cross product replace 2D rotation: f=12Aifi(n×ei)\nabla f = \frac{1}{2A}\sum_i f_i(n\times e_i), and the tensor grows to 3×3 with a transverse direction t=n×dt=n\times d.

Hardening the flip queue: index by (face, corner) instead of hashing mutable Halfedge objects; return None instead of nan for degenerate triangles; reject flips that would duplicate an existing edge.

Results

The Polyscope UI toggles between the original mesh and the re-triangulated one, with a live counter of non-Delaunay edges before/after and total flips performed. Recomputing the direction field after flipping shows the payoff: geometry never moved, but connectivity reorganized to better respect the metric — the field still tracks the shark’s body, now on better-conditioned triangles.

Categories
Research

Navigating the Galaxy: RRT-Connect, C-Space, and Narrow Passages

Have you ever tried moving a sofa through a narrow staircase? Every twist, turn, and pivot matters, and one wrong angle means you’re stuck. In robotics and computational geometry, this is famously known as the “Piano Mover’s Problem.”

But what if the “piano” is a highly intricate, symmetrically interlocked mathematical sculpture?

For my project, I decided to tackle the challenge of computationally disassembling the beautiful, mind-bending geometric sculptures designed by George Hart.

George Hart with a physical sculpture

To do this, I built a motion planning pipeline using the Open Motion Planning Library (OMPL) to find collision-free paths, Polyscope to visualize the 3D physical world, and Matplotlib to peek into the “brain” of the algorithm by plotting the 2D Configuration Space (C-Space).

Let’s dive into how we can use geometry to escape the cage, navigate the galaxy, and eventually… get completely snarled.

The Setup: Workspace vs. Configuration Space

To disassemble these symmetric sculptures, all identical pieces must move away from the center simultaneously. To simplify our problem, we define our state by a translation displacement “d” and a local rotation. While our algorithm supports rotation in “x”, “y”, and “z”, we found that moving outward with respect to the origin and rotating around the Z-axis is often the key to unlocking these puzzles.

This gives us two very different ways to look at the same problem:

The C-Space (Matplotlib): The Configuration Space is a theoretical space where the entire sculpture is represented as a single point. I used Matplotlib to take 2D slices of this space (Displacement “d” vs. Rotation in Z). We evaluate thousands of states using the FCL (Flexible Collision Library). If a state has overlapping meshes, we color it red (Collision). If it’s safe, we color it green (Free Space).

The Workspace (Polyscope): This is the 3D physical space where the meshes actually exist and move. It’s what we see with our eyes.

The Algorithm: Growing Trees with OMPL

To find a valid path from the assembled state (Start) to the fully separated state (Goal), I used RRT-Connect from OMPL.

Imagine two vines growing blindly—one from the Start state and one from the Goal state. They branch out randomly into the free space of our C-Space, hoping to eventually touch and connect.

RRT-Connect is incredibly fast in wide-open spaces. However, it has a famous Achilles’ heel: The Narrow Passage Problem. If the only way to solve a puzzle is through a tiny, precise series of movements, the random vines have a very low probability of growing exactly into that microscopic corridor.

To test this, I ran the planner on three different George Hart sculptures. Here is what happened.

Experiment 1: Cagework (The Walk in the Park)

We started with Cagework. In the physical world, it looks like a complex cage of intersecting edges. But what does the algorithm see?

Because the C-Space has wide, forgiving green areas, our RRT-Connect algorithm has no trouble finding a path. Any random sample is likely to fall in a valid state.

The result in the workspace is a smooth, immediate disassembly.

Experiment 2: Galaxy (The Narrow Passage)

Next, we tried Galaxy. This is where things got interesting. The pieces are much more tightly packed, requiring a very specific twisting motion to separate.

This is a classic narrow passage. OMPL’s RRT-Connect had to work much harder here. The algorithm threw thousands of random branches, most of them hitting the red “collision” walls, until one lucky branch managed to thread the needle through the bottleneck.

When we animate the OMPL path in Polyscope, you can see exactly why this was so hard: the pieces barely scrape past each other, requiring a perfectly timed Z-rotation paired with the outward displacement.

Experiment 3: Snarl (The Impossible Snag)

Finally, we tested Snarl. As the name implies, this sculpture is a geometric knot. I set up the planner, hit run, and… nothing. The planner timed out. Instead of staring at a blank screen, we can use our Matplotlib C-Space plots to diagnose why it failed.

The 2D C-Space slice tells the whole story. The green space is completely disconnected, or the required passage is so microscopically narrow that it falls below our collision_tolerance (0.0001) and state_validity_resolution. The vines of our RRT-Connect were trapped in a cage of collisions, unable to reach the goal.

While a pure symmetrical displacement + rotation couldn’t solve Snarl, this “failure” is actually a success in visualization. It proves that the topology of the sculpture inherently locks itself in place under these symmetric constraints!

Conclusion & Future Work

Working on this project was a fantastic journey into how robots “think” about space. What looks like a physical interlocking puzzle to us is just a maze of high-dimensional obstacles to an algorithm.

By bridging OMPL, Polyscope, and Matplotlib, I learned that:

  1. Visualization is debugging: I wouldn’t have understood why Snarl failed without plotting the C-Space.
  2. Topology dictates performance: An algorithm is only as fast as the width of its narrowest passage.

In the future, it would be fascinating to expand the Matplotlib visualization to 3D slices (adding Rx or Ry into the mix) to see if Snarl has a hidden escape route in higher dimensions, or to implement path smoothing to make the Galaxy disassembly look less erratic.

A huge thank you to the SGI mentors and the amazing community for this experience!