By Aditya Abhyankar, Biruk Abere, Francisco Unai Caja López and Sara Ansari

Mentored by Kartik Chandra with help from the volunteer Shaimaa Monem

In this project we are looking for ways to generate physical illusions. More to the point, we would like to generate objects that, similarly to this bird, can be balanced in a surprising way with just one support point. To do this we have considered both the physics of the system and we draw on theories from cognitive science to model human intuition.

1. Introduction

Every day in your life, you make thousands of intuitive physical judgements without noticing. ‘Will this pile of dishes in the sink fall if I move this cup?’, ‘If it does fall, in which way will it fall?’ The judgements we make are accurate in most scenarios, but sometimes mistakes happen. Just like how occasional errors in vision lead to visual
illusions (e.g. the dress and the Muller-Lyer illusion) occasional errors in intuitive physics should lead to physical illusions. To generate new illusions, there are two steps that could be followed.

1. First, we could design a method that appropriately models the way people make intuitive judgements based on their perception of the world. In that regard it’s interesting to read [1] which models intuitive physical judgement via physical simulations.
2. Secondly, we could try to ‘fool our model’ or to find an adversarial example. That is, find a physical scenario in which the output of the model is wrong. If the model is appropriately chosen, the results may also fool humans, thus producing new physical illusions. This approach has been used in [2] to generate images with properties similar to the dress.

In this project we aim to find a different kind of illusion. Consider the following toy (image from Amazon). Many people would guess that the bird would fall if it’s only supported by its beak.

However, the toy achieves a perfectly stable balance in that position. We seek to find other objects that behave similarly: they achieve stable balance given a single support point even when many people guess that it is going to fall.

2. Physical stability vs intuitive stability

Consider a frictionless rigid body with uniform density and a point p on its boundary with unit normal n. For the object to balance at p, its normal n must point ‘downwards’ in the direction of gravity, for otherwise it will slide. Perfect balancing will then be achieved if the line connecting p and the object’s volumetric center of mass (COM) m is parallel to n. This can be achieved for the balancing bird when the point p is the beak as can be approximately seen in the following figure (mesh obtained from thingiverse). Here we have the center of mass in red and the vector showing the direction of m−p.

Since an object can always be rotated so that n points downwards, the quality of the balancing can be assessed by the evaluating the dot product (m−p) · n. To be precise, we use the normalized vectors to compute the dot product. The greater this value, the more stable the balancing at p. If m−p and n are parallel and have the same direction, then a perfect balancing will be achieved, and it will be stable. If they are parallel with opposite direction, a perfect balancing will still be achieved, but it will be unstable; i.e. small perturbations will make it fall. Points with dot product values in between will lie somewhere on a spectrum of stability, determined by their dot product’s closeness to the positive extremum. To illustrate this concept, we have taken a torus and a ‘half coconut’ mesh and plotted the dot product of normalized m−p, n. The center of mass appears in red.

There is some evidence [4] that humans asses a rigid body’s ability to stably balance at a point in a very similar way. The only difference is that instead of considering the object’s actual COM, whose location can be counterintuitive even with uniform density, humans judge stability based on the COM m_ch of the object’s convex hull. Thus to find an object that stably balances in a way that looks counterintuitive to humans, we must search for objects with at least one boundary point p such that (m−p) · n is maximized, but (m_ch−p) · n is minimized.

In general, to compute the center of mass of a region M⊂ℝ³, we would need to compute the volume integral

\(\mathbf m=\left(\int_{M}x\rho(x,y,z)\,dxdydz,\int_{M}y\rho(x,y,z)\,dxdydz,\int_{M}z\rho(x,y,z)\,dxdydz\right)\)

where ρ is the density of the object. However, for watertight surfaces with constant density, this volume integral can be turned into a surface integral thanks to Stokes’ theorem. Therefore, the center of mass can be computed even if we only know the boundary of the object, which for us is encoded as a triangle mesh. The interested reader learn more about this computation in [3].

3. Finding new illusions

Given a mesh, one simple way to find new illusions would be to look for a vertex p such that (m−p) · n is positive and close to its maximum, while (m_ch−p) · n is as small as possible (again, we will use normalized versions of the vectors). Of course, these are two conflicting tasks. In this project we have chosen to maximize a function of the form

\(w\frac{(\mathbf m-\mathbf p)\cdot \mathbf n}{\vert \mathbf m-\mathbf p\vert}-\frac{(\mathbf m_{\text{ch}}-\mathbf p)\cdot \mathbf n}{\vert \mathbf m_{\text{ch}}-\mathbf p\vert}\)

where w is a weight. By increasing w, we are more likely to find points were m−p and n are almost parallel, which is desirable to achieve a stable balance. The most interesting results were found when (m−p) · n ≈ |m−p| and (m_ch−p) · n < 0.7|m_ch−p|. For instance, we have the following chair.

This chair is part of the SHRECK 2017 dataset. We also examined some meshes from Thingi10k and one of the results was the following.

In the previous pictures, assuming constant density, each object is balanced with only one support point. Finally, we have the following hand which can be found in the Utah 3D Animation Repository.

4. Results and future work

Here we list some limitations of our project and ways in which they could be overcome.

1. Are we certain that the results obtained really fool human judgement? Our team finds these balancing objects quite surprising or, at the very least, aesthetically pleasing. We could try giving more definite proof by designing a survey. For example, people could look at different objects supported at a single point and guess if the objects would fall or not.
2. We have only verified that the objects should be stably balanced by computing the location of the center of mass. We could further test this by running physical simulations and by 3-D printing some of the examples.
3. Given a 3-D object that has already been modeled. We checked whether it could be balanced in any surprising way. One step forward would be generating 3-D models of objects that verify the properties we desire. It would be desirable that given a mesh (e.g. of an octopus), we could deform it so that the result (which hopefully still looks like an octopus) can be balanced in a surprising way.

5. Conclusion

Let’s take a step back and see this project has taught us. We started with the question: why do some objects, like the balancing bird, seem so surprising? This led us to study how people perceive objects through their center of mass and, after searching through a variety of 3D data sets, we found objects that also seem to balance in a surprising way. This was a very fun project and we really enjoyed it as a group, it involved playing with a bit of math, the geometry of triangle meshes and making beautiful visualizations while also learning something about human perception. Finally, we would like to thank Justin Solomon for organising the SGI, giving us this wonderful opportunity and Kartik Chandra for offering and mentoring such a fun project.

References

[1] Peter W Battaglia, Jessica B Hamrick, and Joshua B Tenenbaum. Simulation as an engine of physical scene understanding. Proceedings of the National Academy of Sciences, 110(45):18327–18332, 2013.

[2] Kartik Chandra, Tzu-Mao Li, Joshua Tenenbaum, and Jonathan Ragan-Kelley. Designing perceptual puzzles by differentiating probabilistic programs. In ACM SIGGRAPH 2022 Conference Proceedings, pages 1–9, 2022.

[3] Brian Mirtich. Fast and accurate computation of polyhedral mass properties. Journal of graphics tools, 1(2):31–50, 1996.

[4] Yichen Li, YingQiao Wang, Tal Boger, Kevin A Smith, Samuel J Gershman, and Tomer D Ullman. An approximate representation of objects underlies physical reasoning. Journal of Experimental Psychology: General, 2023.

Authors: Sana Arastehfar, Erik Ekgasit, Maria Stuebner

This is a follow up to a previous blogpost. We recommend that you read the previous post before this one.

We devoted our second week to exploring three methods of ensuring temporal consistency between runs of the Latent-NeRF code:

1. fine-tuning

2. retraining a model halfway through

3. deforming Latent-NeRFs with NeRF-Editing.

The overall aim was to keep certain characteristics of the generated images, for example, of a Lego man, consistent between runs of the code. If the following tests were run:

1. Lego man
2. Lego man holding a sword

we would want the Lego man to retain his original colors, hair, and features except for his originally raised hand which we would want to now be lowered slightly and holding a sword.
If we tested for a color change, for example, such as

1. red Lego man
2. green Lego man

we would want the Lego man to retain exactly the same geometry between runs, with only the color of the Lego man changing as noted by the change in text guidance. After discussing ways in which to go about achieving this temporal consistency, we each decided to explore a different method, as outlined below.

1. Fine-tuning

Experimental Setup
The experiments were conducted using the same sketch and text prompt as a basis for animation generation. Different variations of the text prompts and sketch guides were used to observe the changes in the generated animations. The generated animations were evaluated based on color consistency, configuration accuracy, and adherence to the provided prompts.
Consistency Analysis
The initial experiments revealed that the model demonstrated remarkable consistency when animating a Lego man holding a sword (Figure 1). Even when the text prompt was altered to depict a teddy holding a sword (Figure 2), the generated animations still maintained accurate depictions, both in color and shape, demonstrating the model’s robustness.

Influence of Text Prompt and Sketch Guide
Figure 3 presented two different results when using the same shape guidance but different text prompts: “a Lego man” and “a Lego man with left arm up.” This indicated that the text prompt had a more significant impact on the final animation results than the sketch guide.

 Figure 3: latent NeRF outputs using the same sketch guide, different text prompts. “a lego man” (left), and “a lego man with left arm up” (right), demonstrating the weight of text guide in latent NeRF.

Animation Sequence and Consistency To investigate the model’s ability to maintain consistency in an animation sequence, a series of runs were conducted where a Lego man attempted to raise the sword. After four runs, the sword’s color became inconsistent, and after the fifth run, the sword was no longer present (Figure 4).

Figure 4: Prompt: “lego man holding a sword” with different sketch shapes. The 10 sketch shapes for man animation of a humanoid figure holding a sword and raising their arm.

Fine-Tuning Techniques
Three fine-tuning techniques were attempted to enhance the model’s performance on the same sketch shape guide and text prompt:

a. Full-Level Fine-Tuning
Full-level fine-tuning is a technique used in transfer learning, where an entire pre-trained model is fine-tuned on a new task or dataset. This process involves updating the weights of all layers in the model, including both lower-level and higher-level layers. Full-level fine-tuning is typically chosen when the new task significantly differs from the original task for which the model was pre-trained.
In the context of generating animations of a Lego man holding a sword, full-level fine-tuning was employed by using the weights obtained from a run where the generated animations had a completely visible sword. These weights were then utilized to fine-tune the model on runs where the generated animations had no swords. The outcome of this fine-tuning process showed a visible sword in the generated animations, but the boundary for the configuration of the Lego man appeared less-defined as observed in Figure 5. This suggests that while the model successfully retained the ability to depict the sword, some aspects of the Lego man’s configuration might have been compromised during the fine-tuning process. Fine-tuning at the full level can be advantageous when dealing with highly dissimilar tasks, but it also requires careful consideration of potential trade-offs in preserving specific features while adapting to the new task.

Figure 5: The output of sketch guided and text guided “a lego man holding a sword”, where the sword was no longer visible (left) and full level fine tuning output (right).

b. Less Noise Fine-Tuning We performed fine-tuning on the stable diffusion model by increasing the number of training steps. The idea behind this was to take advantage of increased interactions between the model and the input data during training, as larger time steps can provide a better understanding of complex patterns. Surprisingly, this approach resulted in a decline in both configuration and color consistency in the generated animations, as evidenced in Figure 6.

Figure 6: The output of Latent-NeRF after altering the training steps from 1000 to 2000 in the stable diffusion.

In an effort to improve the model’s performance, we experimented with adjusting the noise level in the generated data. Originally, the noise level gradually decreased from the start to the end of training. However, we decided to explore an alternative approach using the squared cosine as a beta scheduler to stabilize training and potentially enhance the quality of generated samples. Unfortunately, this adjustment led to even further degradation in both configuration and color consistency, as shown in Figure 7.

Figure 7: Changing the beta schedule  from “scaled_linear” to “squaredcos_cap_v2” in Stable Diffusion.

These results indicate that finding an optimal balance between noise level and training steps is crucial when fine-tuning the stable diffusion model. The complex interplay between these factors can significantly impact the model’s ability to maintain configuration and color consistency. Further research and experimentation are needed to identify the most suitable combination of hyperparameters for this specific generative model.

c. Freeze Layers
Freezing layers during fine-tuning is a widely used technique to retain learned representations in specific parts of the model while adapting the rest to new data or tasks. In our experiment involving the pre-trained model for “the Lego man holding a sword,” we employed this approach to leverage the visible sword results and enhance the performance on the scenario where the sword was not visible.

To achieve this, we selectively froze layers from different networks responsible for color and background. However, the outcomes were mixed. When we froze the sigma network layer, we observed a visible sword in the generated animations. However, there was a trade-off as the configuration of the Lego man suffered, and the depiction became less defined as shown in Figure 8.

Figure 8: Freezing sigma network layers, you can see the before this fine tuning (top) there are no swords, and after fine tuning (bottom) there is a phantom of the sword.

On the other hand, freezing the background layer led to a different outcome. While the Lego man’s configuration was better preserved, the generated animations lacked the complete depiction of the Lego man and appeared incomplete as depicted in Figure 11.

These results suggest that freezing specific layers can have both positive and negative impacts on the generated animations. It’s important to strike a balance when deciding which layers to freeze, as it can greatly influence the final performance of the model. Fine-tuning a generative model with frozen layers requires careful consideration of the specific characteristics of the task and the trade-offs between preserving existing knowledge and adapting to new data. Further experimentation is necessary to identify the optimal configuration for freezing layers in order to achieve the best results in future fine-tuning endeavors.

Conclusion
The study explored the consistency and fine-tuning techniques of a generative model capable of animating a Lego man holding a sword. The model demonstrated high consistency when generating animations based on different prompts and sketch guides. However, fine-tuning techniques had varying effects on the model’s performance, with some approaches showing improvements in certain aspects but not others. Further research is necessary to achieve more reliable and consistent fine-tuning methods for generative animation models.

2. Can you retrain a NeRF midway through training?

The second approach was to modify text/shape guidance halfway through a training set, with the motivation of ensuring consistency of the elements not changed in the guidance. The idea between this method was to somehow “save” the initial conditions of the trained NeRF from the original text and/or geometry guidance so that the second set of text/geometry instructions would change only the minimal elements needed to align with the new guidance. To test this approach, we looked at three types of changes: 1) a change in the text guidance only, 2) a change in the geometry guidance, and 3) a change in both instructions.

Changing Text Guidance
When only the text guidance was changed, as shown in the modification to the aforementioned lego_man configuration file below,

log:
  exp_name: 'lego_man'
guide:
  text: 'a red lego man'
  text2: 'a green lego man'
  shape_path: shapes/teddy.obj
optim:
  iters: 10,000
  seed: 10
render:
  nerf_type: 'latent'

the NeRF was able to retrain to the new text guidance with some difficulty. The results below show a snapshot of the final result of the text guidance “a red lego man” and “a green lego man”, as well as the final 3D video of the green lego man. They show how although there are still some remnants of red in the green lego man and the design of his outfit had slightly changes, the basic geometry of the lego man as well as the design in white on the red lego man and then in black on the green lego man is unchanged:

Changing Geometry Guidance
When only the geometry guidance was changed, as shown in the lego_man configuration file below,

log:
  exp_name: 'lego_man'
guide:
  text: 'a lego man'
  shape_path: shapes/teddy.obj
  shape_path2: shape/raise_sword.obj
optim:
  iters: 10,000
  seed: 10
render:
  nerf_type: 'latent'

the NeRF had more difficulties retraining to match the new geometry of the lego man holding a sword. We show the two object files below that were used for these runs.

The results below show a snapshot of the final result of using the teddy.obj file for geometry guidance and then using the raise_sword.obj file, as well as the final 3D video of the second run using the raise_sword.obj file:

Changing Both
When both the text and geometry guidance were changed, as shown below,

log:
  exp_name: 'lego_man'
guide:
  text: 'a lego man'
  text2: 'a lego man holding a sword'
  shape_path: shapes/teddy.obj
  shape_path2: shape/raise_sword.obj
optim:
  iters: 10,000
  seed: 10
render:
  nerf_type: 'latent'

the NeRF was able to retrain to the new guidance with less difficulty than in the case of the only using geometry guidance, yet the sword itself is somewhat translucent, and the outfit of the lego man changed from the original tuxedo look of the first run:

In conclusion, although these runs show promise for this approach of retraining a NeRF halfway through, they also indicate that there are certain initial conditions that either change completely in the retraining of the NeRF, or that inhibit the NeRF from being able to generate an accurate retrained 3D figure that corresponds to the new text and/or geometry guidance. Additionally, training data indicates that the learning curve for NeRFs may complicate the approach of retraining, as the NeRF learns certain final details only at the very end of training.

3. Deforming Latent-NeRFs with NeRF-Editing

Background
Since NeRFs are functions that provide the color and volume density of a scene at a given 3D point, they do not directly generate images. Instead, a NeRF needs to be rendered just like a triangle mesh or other 3D representation would. This is done using a volumetric rendering algorithm. For each pixel in the image, a ray is shot from the camera. The color and volume density is sampled along the ray the pixel’s color is computed from those values.

Nerf-Editing is a method that can be used to deform NeRFs. It extracts a triangle mesh from the surface of the NERF which the user can edit using whatever tools they desire. The original triangle mesh is then used to create a corresponding tetrahedral mesh. Then, the deformation of the triangle mesh is transferred to the tetrahedral mesh. This results in an original and deformed tetrahedral mesh. When the NeRF is rendered, rays are shot into the scene and points on the deformed tetrahedral mesh are sampled. Instead of sampling the NeRF at that point, the NeRF is sampled at the corresponding point on the undeformed mesh. This gives the NeRF the appearance of deformation when it is rendered to an image.

Figure: An overview of NeRF-Editing.

Proposed Process
Latent-NeRF can be guided with a sketch-shape. Ideally a user would able to deform the sketch shape and get a deformed NeRF back. We start with a sketch-shape and train a corresponding Latent-NeRF. We then put the trained NeRF into NeRF-Editing. Instead of extracting a triangle mesh to get an editable representation of the NeRF, we simply use the sketch-shape. The user edits the sketch-shape. We tetrahedralize the original sketch-shape and create a corresponding deformed tetrahedral shape. We then render the NeRF by sampling points on the deformed shape and then sampling the NeRF in the corresponding un-deformed location. It would be interesting to see whether the sketch shape would be enough to guide the deformation instead of a mesh extracted from the NeRF itself.

Challenges
The main challenge is that there are many different NeRF architectures since there are many ways to formulate a function from points in space and view direction to color and volume density. Latent-NeRF uses an architecture called Instant-NGP which stores visual features in a data structure called a hash grid and uses a small neural network to decode those features into color and volume density. NeRF-Editing uses a backend called NeuS. NeuS is an extension on the original NeRF method, which utilized one massive neural network, and embedded a signed distance function better define the boundaries of shapes. In theory, NeRF-Editing’s method is architecture agnostic, but the implementation of Instant-NGP into NeRF-Editing was too time consuming for the 2-week project timeline.

Students: Francisco Unai Caja López, Shalom Abebaw Bekele and Sara Ansari
Directed by Jorg Peters and Kyle Lo

1. Introduction

The goal of this project is to design a layout simplification procedure. Following [2], we define an integer-linear programming model to find a set of collapsable arcs, and merge sets of arcs to simplify the layout. The algorithm is part of a bigger research project that is currently carried out by Kyle Lo and Jorg Peters. In said project surfaces are approximated using splines and piece-wise Bezier surfaces [7].

1.1 What is a layout and why do we care about layouts?

Definitions. Consider a graph M = (V,E) of a triangle mesh. For us, a layout is defined as another graph G = (N,A) where N is a subset of V called nodes and A is the set of arcs. Each arc a ∈ A is a polyline that connects two nodes via a sequence of edges from the original triangle mesh. For each node n ∈ N, we define its valence as the number of arcs incident to n. Also, a node is said to be a singularity if it has valence different than 4. Singularities are particularly important in quad layouts, that is, layouts in which all patches are 4-sided. This is because singularities usually lie near important regions and features of the surface. In the following figure you can see an example of a quad layout.

Another important concept in this project is that of a trace. Traces are polylines that begin at a singularity and travel through the layout until they reach another singularity. If we are building a trace and encounter a regular node n, the trace will continue through the opposite arc of n. The following figure shows 5 traces that originate at a particular singularity.

Layouts can describe the global structure of the mesh while also defining a partition. Moreover, layouts play a crucial role in tasks such as quadrangulation and embedding Bezier, or NURBS surfaces.

1.2 Layout generation and the objective of this project

There are various methods for generating quad mesh layouts, such as finding a set of separatrix candidates (i.e. paths connecting pairs of prescribed singularities) in topologically distinct ways, from which a subset is chosen to define a full layout [6]. Another method involves computing a cross-field from a given set of linear PDEs based on an imposed set of singularities. These singularities can occur naturally, for example, by minimizing Ginzburg-Landau energy, or as a user-defined singularity pattern [5]. The interested reader can learn more about layouts and quad meshes in [3].

In this project we are given layouts generated by a modified version of Quadwild [1]. These layouts are generated from triangle meshes. The goal is to find a subgraph of the layout with as few partitions as possible while ensuring that each pair of singularities is separated.

2. Finding collapsable arcs via integer programming

In order to simplify a layout, we first need to figure out which elements are removable. Precisely, we want to know when an arc can be collapsed. To do this, for each arc a ∈ A we define an integer variable q_a. We define an integer programming model following [2]. In the paper the layouts are allowed to have T-junctions which makes it so that the variables q_a can take any non negative value 0,1,2,… However, this doesn’t happen with the layouts we are working with so, just for this project, we can assume q_a is binary and defined as

\(q_a =
\begin{cases}
1 & \text{if arc } a \text{ is collapsable} \\
0 & \text{otherwise}
\end{cases}.\)

2.1. Constraints to enforce properties of the resulting layout

We have two main restrictions.

The resulting layout must be a quad layout

Suppose that we want to collapse arc a in the following figure, then we must also collapse all the arcs a’, a”, … Otherwise, we would have a three sided patch and the result would not be a quad layout.

More generally, if arcs a and a’ lie in the same patch and are opposite to each other, then we must have q_a = q_a’.

Singularities must remain separate

In general, singularities tend to appear near important features of the mesh or in regions with high curvature. Thus, it makes sense that we try to preserve their locations. We make sure that different singularities aren’t merged together regardless of the number of collapsed arcs. This is done by forcing that any pair of singularities are at a ”positive Manhattan distance”. More precisely, consider two singularities n₁, n₂ and traces t₁, t₂ with origin in n₁ and n₂ respectively. Assume that both traces go through mid node n_m, then we must have

\(\sum_{a\in t_1}q_{a} + \sum_{a\in t_2}q_{a} \geq 1.\)

In the following figure we can see an example of a pair of intersecting traces t₁ and t_2.

And in the following figure we have the set of arcs that links the origin of each trace to the mid node.

One possibility to avoid collapsing two singularities together would be, for each pair of nodes n₁, n₂, finding intersections of all possible traces t₁, t₂ and add the previous restriction to the model. In that case, the number of restrictions would be quadratic in the number of nodes. However, the same result can be achieved with far fewer restrictions as is stated in [2].

Notation. For every pair of intersecting traces t_i, t_j, we denote the first common node as n_ij. The set of arcs that link the origin on t_i with n_ij is represented by S_ij and the total length of those arcs is denoted by l_ij. Finally, given a trace t_i, we define n_i* as the intersecting node which is closest to the origin of t_i and verifies l_i* > l_*i. The set of arcs that link the origin of t_i with n_i* will be denoted S_i*.

Lemma 1 of [2] asserts that the family of restrictions

\(\sum_{a\in S_{i*}} q_a \geq 1, \quad \text{for every trace }t_i\)

implies the inequality we previously mentioned. Therefore, we can enforce the desired property using O(⎮N⎮) restrictions where ⎮N⎮ is the number of nodes.

Finally, if we just want to collapse as many arcs as possible, we could set the objective function as ∑_aq_a where the sum is over all arcs. This yields the following linear integer programming model

\(\begin{cases}
\min & \sum_{a}q_a\\
\text{s.t.} & q_a = q_{a’} \text{ whenever } a,a’ \text{ are oposites in the same patch} \\
& \sum_{a\in S_{i*}} q_a \geq 1 \quad \text{for every trace }t_i\\
& q_a\in{0,1} \quad \text{ for every arc } a
\end{cases}\)

Said model will be optimized by Gurobi, a comercial solver. The output is a set of arcs that can be collapsed while maintaining the properties we desire. In the following figure we have in red the collapsable arcs according to an optimal solution to the model

We can see that many of the original arcs are collapsable.

2.2. How do we simplify a layout?

Suppose we have chosen to collapse an arc a, then we will need to collapse a whole set of arcs in order to preserve the quad structure of the layout. This collapse will be done by merging two sets of arcs together. In the following figure we see an example with the arcs to collapse in red and the arcs to merge in purple.

In this project we have chosen to ”move one of the arcs on top of the other” although there are many other choices to do this. In the following figure you can see the simplification procedure.

3. Results and future work

In this project we have learned about layouts and developed a procedure to simplify them iteratively. In addition, solving the integer programming problem has proved to be quite fast (under 0.05 seconds for the examples tested), as the model wasn’t too big. In the following figures you can see the result of applying the simplification several times on two different layouts.

Of course, there are a lot of aspects that can be improved and directions to continue the work

1. The code we developed is far from finished. For instance, we run into problems when some of the arcs to collapse are incident to singularities. All of these special cases should be considered and dealt with appropriately.
2. Weights could be added to variables in the objective function of the integer programming model. The objective function would look like ∑_aw_aq_a. For instance, we could define

\(\qquad \qquad \qquad \qquad \qquad \qquad \qquad \bar{k}_a = \frac{\sum{r\in R}\vert k_p^r\vert }{\vert R\vert},\quad p = \underset{i=1,2}{\text{arg max }}\vert k_i^r \cdot \vec a \vert\)

where R denotes a set of vertices close to arc a and k^r_p is the principal curvature at vertex r that better aligns with the direction vector of the arc. Then, we could define

\(
\qquad \qquad \qquad \qquad \qquad \qquad \qquad w_{b}=\frac{\max_{a}\overline k_{a}-\overline k_{b}}{\max_{a}\overline k_{a}-\min_{a}\overline k_{a}}
\)

The motivation is that we want to preserve arcs that lie in sections with very high curvature. Having a really big patch in the layout that contains very different and intricate details is undesirable. For example, if we wanted to approximate them with splines, then we would need to use a very high degree. Such weighting scheme could be helpful to prevent the creation of such patches.

3. When merging two different arcs, we have chosen to place the new arc in the location of one of the arcs to be merged. Other strategies may be more successful, for instance, we could create a new arc that passes through a region of high curvature. This could help align arcs with features.

4. After the layout simplification, a smoothing procedure like [8] could be applied on all arcs to improve the quality of the results.

Finally, we would like to thank Justin Solomon for giving us such a wonderful opportunity by organizing SGI 2023 as well as Jorg Peters and Kyle for guiding us through this project.

References

[1] Pietroni, N., Nuvoli, S., Alderighi, T., Cignoni, P., & Tarini, M. (2021). Reliable feature-line driven quad-remeshing. ACM Transactions on Graphics (TOG), 40(4), 1-13.

[2] Lyon, M., Campen, M., & Kobbelt, L. (2021). Quad layouts via constrained t-mesh quantization. Computer Graphics Forum, 40(5), 305-314.

[3] Campen, M. (2017). Partitioning surfaces into quadrilateral patches: A survey. Computer Graphics Forum, 36(2), 567-588.

[4] Schertler, N., Panozzo, D., Gumhold, S., & Tarini, M. (2018). Generalized motorcycle graphs for imperfect quad-dominant meshes. ACM Transactions on Graphics (TOG), 37(6), 1-14.

[5] Jezdimirovic, J., Chemin, A., Reberol, M., Henrotte, F., & Remacle, J. F. (2021). Quad layouts with high valence singularities for flexible quad meshing. Retrieved from https://internationalmeshingroundtable.com/assets/papers/2021/08-Jezdemirovic.pdf

[6] Razafindtazaka, F. H., Reitebuch, U., & Polthier, K. (2015). Perfect matching quad layouts for manifold meshes. Computer Graphics Forum, 34(5), 219-228.

[7] Peters, J., Lo, K., & Karčiauskas, K. (2023). Algorithm 1032: Bi-cubic splines for polyhedral control nets. ACM Transactions on Mathematical Software (TOMS), 49(1), 1-12.

[8] Field, D. A. (1988). Laplacian smoothing and Delaunay triangulations. Communications in Applied Numerical Methods, 4(6), 709-712.

Advisor: Ryan Capouellez 

Volunteer: Kinjal Parikh 

Fellows: Erik Ekgasit, Maria Stuebner, and Anna Cole

1: Introduction

Triangles are a nice way to represent the surface of a 3D shape, but they are not smooth. The tangent vectors on a triangle mesh are not continuous.

When it comes to representing curves, we can approximate a curve using a polyline, a set of points connected with straight lines. Alternatively, we could use a spline which provides a smooth way to form a curve that passes through a set of points. Splines that represent curves are piecewise polynomial functions that trace out a curve:

\(f: \mathbb{R} \rightarrow \mathbb{R}^n\).

Similarly a 3D shape’s surface can be represented using splines that are piecewise polynomial functions:

\(g: \mathbb{R}^2 \rightarrow \mathbb{R}^3\).

The Powell-Sabin construction is a type of spline whose pieces are essentially curved triangles that can represent smooth surfaces. In this project, we aim to augment the Powell-Sabin construction to accommodate sharp features on meshes.

1.2: The Powell-Sabin Construction

A triangle mesh can be fed into an optimization algorithm that constructs a spline surface that contains (or is very close to) the points occupied by vertices of the triangle mesh. The surface is also optimized to be smooth. This is done by assigning every triangle in the original mesh a Powell-Sabin patch, the parameters of which are then chosen during optimization. Additionally, the mesh must have a UV map, which assigns each point on the mesh to a point on the plane.

Suppose we have a triangle with indices \((i, j, k)\). Its corresponding Powell-Sabin patch can be specified using 12 vectors in \(\mathbb{R}^3\). Three position vectors \(p_i, p_j, p_k\) describe the positions of the vertices. During optimization, the vertices can move a small amount to create a smoother surface. Each vertex also gets two additional vectors to describe the derivative of the surface going out of each incident edge (labelled with \(d\) in the image below). Finally, each edge of the triangle has an associated vector to describe the derivative of the surface perpendicular to the edge at the midpoint (labelled with \(h\) in the image below).

1.3: Global Parameters

These parameters are not directly optimized. Instead they are derived from global degrees of freedom, which do get directly optimized. This allows more data to be shared between different triangles to ensure continuity. Each vertex in the mesh is assigned 3 vectors in \(\mathbb{R}^3\). One for position and two for a pair of tangent vectors, which are the gradients in the u and v directions in the local parametric domain chart. These gradients should be linearly independent unless the surface is somehow degenerate. Additionally, each edge gets one tangent vector. An illustration of these degrees of freedom is shown below.

The vectors are flattened and stored in \(q\) as follows:

\begin{equation}
q= \begin{bmatrix}
p_1 & p_2 & … & p_n & g_1^u & g_1^v & … & g_n^u & g_n^v & g_1^m & … & g_m^m
\end{bmatrix}
\end{equation}

Where \(p_i\) is the position of vertex \(i\), \(g_i^u\) and \(g_i^v\) are tangent vectors of vertex \(i\) in directions \(u\) and \(v\) (from the UV map), and \(g_j^m\) is a tangent vector for the midpoint of edge \(j\). Since the vectors are flattened, each value here ends up being three actual values in the \(q\).

Unfortunately, we lose sharp features because in \(q\) requires the tangents along an edge to be co-planar since each edge only gets 1 tangent vector. To fix this, we rip creases in half to remove the co-planarity constraint. So, we need to implement new constraints in \(q\) to ensure continuity at these cuts.

2: Experiments with Edge Ripping

We tested ripping edges on various models. For the sake of brevity, here are the results with the chess rook model. By default the triangle mesh looks like this:

Running the base unconstrained optimization on a model of a chess rook results in a model with pretty smooth edges.

Using Blender’s Edge Split modifier, we can split each edge into two edges if the angle between their triangles (dihedral angle) exceeds 30 degrees.

As we can see, the split edges result in gaps as the optimization process shrinks the boundaries where edges are split. There is a wave pattern at many of the edges. The pointy sections correspond to vertices and the arches correspond to edges. However, at seams where the artifacts are minimal, sharp edges definitely remain sharp.

We can force the algorithm to fit vertices near perfectly, but that still results in gaps and compromises overall smoothness.

Ripping edges results in a segmentation fault for any mesh that does not have disc topology. This is likely caused by imperfections in the UV parameterization of other shapes.

3: Quadratic Optimization with Contraints

Currently, we use unconstrained optimization. Where we find the value \(q\) that minimizes \(E(q) = \frac{1}{2}q^THq – wq^TH^fq_0 + const\). Here \(H\) is a matrix that combines fitting and smoothness energies. \(H^f\) is a matrix for just fitting energy and \(q_0\) is a vector that’s the same as \(q\) but only contains the positions of the vertices of the mesh. All other entries are 0.

Loosely speaking, \(H^f\) sums euclidean distances between vertices in the original mesh and their corresponding points on the optimized mesh. The smoothness energy is an approximation of the thin plate energy functional and discourages high curvature.

In the energy function, the first term is quadratic with respect to \(q\), the second term is linear with respect to \(q\) (since \(H^fq_0\) is a column vector that does not depend on \(q\)), and the last term is constant. Since this function is quadratic, its derivative is linear, so it’s easy to find the minimum where the derivative is equal to 0. Differentiating the function, we get \(E'(q) = Hq – wH^fq_0\). Setting this equal to 0, we get \(Hq = wqH^fq_0\) so the solution without any constraints is \(q = wH^{-1}H^fq_0\).

Suppose you have a quadratic function \(E(x) = \frac{1}{2}x^TBx – x^Tb\) and you want to minimize it subject to the constraint \(Ax = c\). If \(A\) is full row-rank (i.e. there are no redundant constraints), then the global minimizer \(x^*\) is a section of the solution to the following equation:

\(\begin{bmatrix} B & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x^*\\ \lambda^* \end{bmatrix} = \begin{bmatrix} b \\ c \end{bmatrix}\).

4: Position Constraints

4.1: Data Organization

We want to construct and matrix \(A\) and vector \(c\) such that \(Aq = c\) is a constraint that forces duplicate vertices in \(q\) to have the same location. That is, \(Aq = c\) is true if and only if duplicate vertices share the same location. Suppose we have a pair of duplicate vertices with indices \(i, j\) where \(i \neq j\). The \(x, y, z\) coordinates of these vertices are stored in \(q\) as follows:

$$q = \begin{bmatrix}
… & p_{i, x} & p_{i, y} & p_{i, z} & …
& p_{j, x} & p_{j, y} & p_{j, z} & …
\end{bmatrix}$$

To obtain pairs of vertices that occupy the same location, we perform a naive \(O(n^2)\) sweep comparing every vertex location to every other vertex location.

4.2: Constructing Constraints

We want to constrain \(q\) such that both vertices occupy the same position. So, we want the following.

Moving all the degrees of freedom to one side, we get:

If we’re careful with our indices, we can write the constraints as a matrix. Since each vertex in \(a\) is described with 3 entries, the indices of the \(x, y, z\) values of a vertex with index \(i\), \(p_i\) is equal to \(3i, 3i + 1, 3i + 2\) respectively. In the system \(Aq = c\), the \(k\)th entry of \(c\) will be equal to the dot product between the \(q\) and the \(k\)th row of \(A\). So, the constraint with the \(x\) coordinates can be written as \(\begin{bmatrix} 0 & … & 1 & 0 & … & -1 & 0 & …\end{bmatrix}q=0\), where 1 “lines up” with \(p_{i, x}\) and “lines up” with \(p_{j, x}\). Stacking these into a full matrix, we get something like: \(\begin{bmatrix}
… & 1 & …& & & & … & -1 & … & & \\
& … & 1 & … & & & & … & -1 & … & \\
& & … & 1 & … & & & & … & -1 & …
\end{bmatrix}q = 0\).

Where the right hand side is the zero vector. Each constraint gets it own row and each coefficient’s column in the matrix is the same as the index of its corresponding degree of freedom in \(q\).

4.3: Implementation Details

Due to restrictions with our C++ linear algebra library, Eigen, it’s actually most straightforward to insert these as entries into \(K = \begin{bmatrix}
B & A^T \\ A & 0
\end{bmatrix}\) as opposed to just \(A\). \(K\) is represented as a sparse matrix, so values can be inserted by specifying a row index, column index, and number. We can add the number of rows in $B$ to the row index to the entries in \(A\) to get the index of that corresponding point in \(K\). For values of block \(A^T\) we can just swap the row and column indices of values of block \(A\).

Proof:
Suppose you have a matrix \(K = \begin{bmatrix}
B & A^T \\ A & 0
\end{bmatrix}\) where \(B\) is square. Then, \(K_{i,j} = K_{j,i}\) if \(i, j\) index a point in block A. By the properites of block matrices, \(K^T = \begin{bmatrix}
B^T & A^T \\ (A^T)^T & 0
\end{bmatrix} = \begin{bmatrix}
B^T & A^T \\ A & 0
\end{bmatrix}\) For all entries that are not in block \(B\), \(K = K^T\), so swapping the row and column indices results in the same value. Since entries in block \(A\) are not in block \(B\), \(K_{i,j} = K_{j,i}\) for all \(i, j\) in block \(A\).

Next Steps

As of time of writing, this project is not yet complete. Several pieces of code must be combined to get position constraints working. After that, we must formulate and implement constraints on vertex tangents.