Categories
Research

Research and Production for Games

Visualizing and Evaluating Skin Weight Transfer

By Shannon Cudworth

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=G⊤MGL = 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∗=arg⁡minv⁡‖Gv−J‖M2⟹Lv=G⊤MJv^* = \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, ‖J−I‖2\| 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=25, train_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=4, train_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/32, ViT-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=4, train_res=256, ViT-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

Linear Subspace Exploration for Mechanical Systems

Project Members: Al Rahim Hossain, Stephanie Jung, Aleksa Milovanović, Reid Tang

Mentors: Otman Benchekroun, Ty Trusty

Introduction

Simulating deformable objects often requires optimizing over a large number of unknowns. For example, a 2D mesh with nn vertices has 2n2n positional variables: an xx and yy coordinate for each vertex. A 3D mesh similarly has 3n3n positional variables.

In a full order model, the deformed shape is represented by a vector 𝐱\mathbf{x} containing all vertex positions. It is found by minimizing the total energy of the object:

𝐱∗=argmin𝐱(Eelastic(𝐱)+Eext(𝐱))\mathbf{x}^*=\underset{\mathbf{x}}{\text{argmin}}\left(E_{\mathrm{elastic}}(\mathbf{x})+E_{\mathrm{ext}}(\mathbf{x})\right)

where EelasticE_{\mathrm{elastic}} measures how much the object resists being deformed from its rest shape and EextE_{\mathrm{ext}} represents external forces. The solution 𝐱∗\mathbf{x}^* is the state with the lowest total energy, where the elastic response and external forces are balanced. However, this solution may be computationally expensive as it treats every vertex position as an independently moving variable.

Figure 1: Comparison of the original 2D mesh (left) and its Neo-Hookean deformation (right) under gravity (g=−0.1g = -0.1), with fixed vertices highlighted in red. This represents the exact solution 𝐱∗\mathbf{x}^* found using Newton’s method.

Reduced-Order Model

Reduced-order modelling reduces the size of this optimization by restricting the solution to a low-dimensional subspace. Instead of tracking every point independently, we choose a small set of meaningful deformation patterns. We then approximate the full configuration as 𝐱≈𝐱𝟎+𝐁𝐳\mathbf{x} \approx \mathbf{x_0 + Bz} where 𝐱𝟎\mathbf{x_0} is the rest state of the object, the columns of matrix 𝐁\mathbf{B} represent the selected deformation patterns, and vector 𝐳\mathbf{z} contains their corresponding coefficients [1]. We can now solve for

𝐳∗=argmin 𝐳E(𝐱𝟎+𝐁𝐳)\mathbf{z}^* = \underset{\mathbf{z}}{\text{argmin }}E(\mathbf{x_0 + Bz})

and the final full-space solution is given by 𝐱∗≈𝐱𝟎+𝐁𝐳∗\mathbf{x}^* \approx \mathbf{x_0 + Bz}^*.

The effectiveness of a reduced-order model depends heavily on the choice of the basis 𝐁\mathbf{B}. Ideally, its columns should capture the important deformation patterns of the object using as few modes as possible. There are several ways to construct such a basis.

Proper Orthogonal Decomposition

Proper Orthogonal Decomposition constructs the basis from a dataset of observed or simulated deformations [2]. It finds the directions that best capture the variation present in the example shapes, making it a data-driven approach. It is found by solving

𝐁=argmin 𝐁||𝐗−𝐁𝐁T𝐗||2\mathbf{B} = \underset{\mathbf{B}}{\text{argmin }} ||\mathbf{X – BB}^T\mathbf{X}||^2 such that 𝐁T𝐁=𝐈\mathbf{B}^T\mathbf{B=I}

Here, 𝐗\mathbf{X} is a matrix whose columns contain example displacement vectors from the rest configuration of the object. We use singular value decomposition, 𝐗=𝐔𝐒𝐕T\mathbf{X} = \mathbf{USV}^T, to find the deformation patterns that best represent these examples. The columns of 𝐔\mathbf{U} are ordered from most to least important so if we want a reduced space with 20 modes, for example, we simply take the first 20 columns 𝐁=𝐔[:,:20]\mathbf{B} = \mathbf{U}[:, :20].

Figure 2: Top: Full-order solutions with gravity g∈[−0.002,−0.003,−0.004,−0.005,−0.006,−0.007]g \in [-0.002, -0.003, -0.004, -0.005, -0.006, -0.007] used to form the dataset. Bottom: Deformation under gravity g=−0.1g = -0.1 using POD. Fixed vertices highlighted in red.

A main drawback of POD is that it requires collecting a representative set of deformation examples beforehand. The resulting subspace can only represent deformation patterns present in, or similar to, this training data, so unseen motions may be captured poorly.

Figure 3: Deformation under gravity g=−0.1g = -0.1 using the POD basis from Figure 2 but with fixed vertices on the opposite ear. It fails since this configuration is not represented in the basis.

Linear Modal Analysis

Linear Modal Analysis builds the reduced basis from the object’s natural vibration modes around its rest shape [3]. The basis vectors are deformation modes obtained from the mesh’s stiffness and mass matrices, so the subspace is determined by the physics of the object rather than by example deformation data. These modes are found by solving the generalized eigenvalue problem

𝐇ϕ=λ𝐌ϕ\mathbf{H}\phi = \lambda\mathbf{M}\phi.

Here, 𝐇\mathbf{H} is the elastic stiffness of the object and 𝐌\mathbf{M} accounts for its mass. Solving the eigenvalue problem gives the natural deformation patterns ϕ\phi, or modes, of the object. The lowest-frequency modes are usually the most important and are chosen as the columns of the reduced basis 𝐁\mathbf{B}.

Figure 4: Top: Animation of the first 10 deformation modes. Bottom: Deformation under gravity g=−0.1g = -0.1 using an LMA basis with 5 modes (left), 10 modes (center), and 20 modes (right).

However, LMA is based on a linearization around the rest shape, so it works best for small deformations. Large rotations or strongly nonlinear deformations may not be represented well by a basis of linear vibration modes.

Actuation-Aware Subspaces

POD can capture large deformations, but it requires representative simulation data. LMA avoids this data collection, but its basis is not aware of the parameters driving the simulation. Actuation-aware subspaces build the reduced basis directly from how the object deforms as the actuation parameters change. We write

𝐱(𝐚)=argmin 𝐱E(𝐱,𝐚)\mathbf{x(a)} = \underset{ \mathbf{x} } { \text{argmin } } E(\mathbf{x, a})

where 𝐚\mathbf{a} may represent quantities such as spring rest lengths, gravity, muscle activation, or collider parameters. The goal is to approximate how 𝐱(𝐚)\mathbf{x(a)} changes as 𝐚\mathbf{a} changes.

We can first approximate this relationship using a first-order Taylor expansion around a reference actuation 𝐚0\mathbf{a}_0:

𝐱(𝐚)≈𝐱(𝐚0)+∑i(ai−a0,i)∂𝐱∂ai\mathbf{x}(\mathbf{a})\approx\mathbf{x}(\mathbf{a}_0)+\sum_i(a_i-a_{0,i})\frac{\partial\mathbf{x}}{\partial a_i}.

The derivatives ∂𝐱∂ai\frac{\partial \mathbf{x}}{\partial a_i} describe the deformation caused by changing each actuation parameter. For example, if the object is driven by springs, each parameter could control the rest length of one spring. However, this is still a linear approximation and works best for small deformations near 𝐚0\mathbf{a}_0. Larger motions such as bending, rotation, and compression follow curved deformation paths that cannot be represented well using only fixed linear directions.

To capture these effects, we include second-order derivatives, ∂2𝐱∂ai∂aj\frac{\partial^2 \mathbf{x}} {\partial a_i \partial a_j}, for the second-order Taylor expansion:

𝐱(𝐚)≈𝐱(𝐚0)+∑i(ai−a0,i)∂𝐱∂ai+12∑i∑j(ai−a0,i)(aj−a0,j)∂2𝐱∂ai∂aj\mathbf{x}(\mathbf{a}) \approx \mathbf{x}(\mathbf{a}_0) + \sum_i (a_i-a_{0,i}) \frac{\partial \mathbf{x}}{\partial a_i} + \frac{1}{2} \sum_i\sum_j (a_i-a_{0,i})(a_j-a_{0,j}) \frac{\partial^2 \mathbf{x}}{\partial a_i \partial a_j}

If the first derivatives describe the response to actuation, the second derivatives describe how that response changes as the actuation changes. These terms help capture deformation patterns that appear together during larger motions, allowing the reduced space to follow nonlinear deformation paths more closely.

The reduced subspace can therefore be formed by

𝐁=[∂𝐱∂a1 ⋯ ∂𝐱∂ap ∂2𝐱∂a12 ⋯ ∂2𝐱∂ai∂aj]\mathbf{B} = \left[ \frac{\partial \mathbf{x}}{\partial a_1} \ \cdots\ \frac{\partial \mathbf{x}}{\partial a_p} \ \frac{\partial^2 \mathbf{x}}{\partial a_1^2} \ \cdots\ \frac{\partial^2 \mathbf{x}}{\partial a_i \partial a_j} \right]

such that this space is tailored to the parameters driving the simulation.

This idea is similar to modal derivatives [1], which describe how linear vibration modes change and interact. Here, we apply the same idea to actuation parameters, so the basis is tailored to the forces that will actually drive the simulation.

Figure 5: Deformation under spring actuation as the spring is made tighter using (from left to right): first-order approximation, second-order approximation, LMA, and an exact solution using Newton’s method.
Figure 6: Deformation error as the spring contracts for the first-order, second-order, and LMA reduced models compared with the exact solution.

Conclusion

Reduced-order models can make deformable simulations more efficient by representing motion with a small number of deformation patterns. In this project, we explored an actuation-aware basis that is built from how the equilibrium shape changes with the parameters driving the simulation. First-order derivatives capture the main response to actuation, while second-order derivatives help represent larger and more nonlinear deformations.

There are still several directions for future work. Hyper-reduction is needed to further reduce computational cost [4], and the current method relies on a PSD-projected Hessian for stable basis construction. The number of basis terms also grows with the number of actuation parameters. Future work could address these limitations and extend the method to more complex 3D scenes and different types of actuation.

References

[1] J. Barbič and D. L. James. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Transactions on Graphics, 2005.

[2] L. Sirovich. Turbulence and the Dynamics of Coherent Structures. I. Coherent Structures. Quarterly of Applied Mathematics, 45(3), 561–571, 1987.

[3] A. Pentland and J. Williams. Good Vibrations: Modal Dynamics for Graphics and Animation. SIGGRAPH, 1989.

[4] C. Brandt, E. Eisemann, and K. Hildebrandt. Hyper-Reduced Projective Dynamics. ACM Transactions on Graphics, 2018.

Categories
Research

3D Object Reconstruction using 2D Medial Axis

During Week 3, we had the incredible opportunity to dive into an amazing project on 3D object reconstruction using medial axis. This journey wouldn’t have been possible without the guidance of Professor Kathryn Leonard and Professor Geraldine Morin. They were truly wonderful advisors, offering us their insight and support every step of the way. We’re so excited to share our thoughts and results with you all! Let’s start with some basic background.

by Stephanie Jung, Evelyn Zhu and Anja Milutinović
  • What is a Medial axis ?

The medial axis is the “skeleton” of a shape. In 2D, the medial axis of a shape is the set of all points that are equidistant from at least two points on the boundary, i.e. the centers of the largest circles you can inscribe inside it. Paired with the radius at each point, it’s a compact yet near-complete description of a shape: sweeping those inscribed disks/balls back along the axis reproduces the original subject. For a straight rod, the medial axis is a line, for a bent tube it’s a curve, and for a torus it’s a circle. The axis really captures a shape’s essential structure in far fewer numbers than the full surface. 

One of the nice properties of the medial axis is that it preserves topology and geometry of the original shape. Given the medial axis of a 2D shape and the corresponding radius of each medial axis point, the original shape can be reconstructed.

  • How do we Compute Medial axis using Voronoi diagrams?

The medal axis is defined with respect to the continuous boundary of a shape and computing exact medial axis is then difficult. It’s then easier to approximate it using Voronoi diagrams of sample points on the boundary.

If we have a set of sample points P = {p1, p2, … , pn}, the Voronoi cell of the sample point pi is a set of all points that are closer to pi, then any other pj:

Vi={x∈ℝn|‖x−pi‖≤‖x−pj‖, ∀j}V_i = \left\{ x \in \mathbb{R}^n \;\middle|\; \|x – p_i\| \le \|x – p_j\|,\ \forall j \right\}

The Voronoi diagram is a collection of all Voronoi cells.

The medial axis and Voronoi diagram’s edges both have in common that they are defined by points that are equidistant from multiple boundary locations. The algorithm to compute medal axis then becomes:

  1. Sample the boundary of the given object
  2. Construct the Voronoi diagram of the sample points
  3. Keep only the Voronoi vertices that are inside the object
  4. Connect the neighboring vertices with existing Voronoi edges
A visual example showing the medial axis of a 2D Baymax silhouette. This particular image actually shows a faulty medial axis. Based on the definition of medial axis, you can determine visually which branches should not be there.

With this foundational understanding of medial axes and Voronoi diagrams under our belts, we were ready to tackle the core of our Week 3 project. We wanted to see if we could take these 2D ‘skeletons’ and use them to solve a much more complex problem: bringing flat images to life by reconstructing a full 3D object from them.

Reconstructing 3d object from its 2d images using medial axis

Method 1:

  • We reconstruct a 3D object from a set of binary silhouettes taken from viewpoints spread over a sphere. For each view we compute an orthographic projection of the mesh to get a silhouette, then extract its 2D medial axis and radius via the Voronoi diagram of the boundary. We then fuse the views in 3D by carving a voxel grid (keeping only voxels whose projection lands inside every silhouette) and thin the result with a 3D skeletonization to recover the object’s 3D medial axis. Finally, we rebuild the surface by sweeping balls of the recovered radius along that axis, which reproduces the original shape. 

Pipeline Visualization:

Method 2:

  • Each point on a 2D medial axis represents the center of a maximal inscribed circle. All of the possible centers lie along the camera’s viewing direction. So then, every circle naturally defines a cylinder in 3D space whose axis is the same direction as the camera viewing direction and whose radius equals the radius of the medial circle. Each orthographic image generates an entire set of cylinders, or as we called them “swept cylinders”.
  • We position the “swept cylinders” by setting the medial axis from each camera view in a world space and using the camera parameters (orthographic scale, location with respect to the object, viewing direction) to position each 2D medial axis about the world origin such that it reflected the camera view about the original 3D object. 
N model: Medial axes from 3 different camera views, projected into a world space. Line propagating from the center of each camera view indicates camera forward direction. Blue point (where all camera forwards intersect) indicates the point all cameras were focused on (center of the original 3D object).
N model: Visualization of swept cylinders.

Intersecting the “sweep cylinders” from multiple views in 3D space, gives us a feasible reconstruction region:

Ω=⋂swept cylinders(⋃cylinders in swept cylinderC)\Omega = \bigcap_{\text{swept cylinders}} \left( \bigcup_{\text{cylinders in swept cylinder}} C \right)

Method 2a:

To compute the radii of each sphere we use a signed distance function for a cylinder. Since the center point can belong to multiple cylinders, in each “swept cylinder”, we take the one where the point has a maximum SDF. The sphere must be contained in the intersection of each chosen “swept cylinder”, so the final radius is taken as minimum.

R(p)=minswept cylinders⁡(maxcylinders in swept cylinder⁡SDF⁡(c,p))R(p)=\min_{\text{swept cylinders}} \left( \max_{\text{cylinders in swept cylinder}} \operatorname{SDF}(c,p) \right)
One of the view of the object with it’s 2d medial axis
Reconstruction using maximal spheres with sampled sphere centers

Method 2b:

In an alternative method, to compute the radii of each sphere we use the signed distance field of the binary image for each view, which evaluates a point’s distance from the nearest boundary of the shape. We sample points in 3D space at regular intervals and project them down into each view’s 2D image plane, then compute the signed distance for the point in that view. This method is functionally equivalent to using a 3D signed distance field in world space; it evaluates a point’s distance from the nearest boundary of the swept cylinder for that camera view. Then, the radius of a sphere centered at a point is the minimum signed distance across all camera views, since the sphere must be contained in the intersection of all swept cylinders.

N model (3D)
N model: binary image of the N model from one camera view
N model: Reconstruction of N model, from images taken from 3 different camera views