Reconstruction

Implement a simplified version of the method in “Poisson Surface Reconstruction” by Kazhdan et al. 2006.

Registration

Implement a version of the iterative closest point (ICP).

Smoothing

Smooth a data signal defined over a curved surface.

This data could be a scalar field on the surface and smoothing corresponds to data denoising.

Or the data could be the vector field of the surface’s own geometry. This corresponds to geometric smoothing.

Subdivision

Produce a high-resolution, smooth surface from any coarse triangle mesh by upsampling and loop subdivision.

Decimation

Reduce faces and vertices through shortest edge collapse and quadric error minimization.

Deformation

Implement biharmonic deformation and as-rigid-as-possible deformation algorithms for interactive surface deformation.

Parameterization

Compute a 2D parameterization utilizing Tutte’s mapping as well as the “least squares conformal” energy.

Distances

Implement the heat geodesics algorithm.

Curvature

Compute discrete curvature quantities on a surface.

Normal-Driven Spherical Shape Analogies

Implement the paper “Normal-Driven Spherical Shape Analogies” (SGP 2021).

Introduction

Before the publication of “Normal-Driven Spherical Shape Analogies”, the field lacked a comprehensive method for transferring geometric styles effectively. Previous approaches mainly targeted specific stylization styles for 3D objects, like collage art, manga style, or cubic style, but lacked a unified framework for achieving diverse results. Some techniques focused on transferring 3D geometric details, such as patch-based assembly and voxel-based texture synthesis, while others utilized surface normals in various geometry processing tasks like PolyCube deformation or mesh denoising.

However, there was a notable absence of methods that employed analogy-based approaches for stylization across different styles within a single framework. Additionally, existing techniques for surface normal-based deformations struggled to generalize to various stylization styles beyond specific cases like PolyCube deformation or cubic stylization. The paper addressed these limitations by introducing a novel approach that effectively leveraged analogy-based methods for diverse stylization styles and surface normal-based deformations.

Paper Contribution

The paper proposes a novel method for shape analogy, focusing on transferring geometric styles using surface normals. The approach formulates the problem as finding correspondences between a reference shape (a sphere) and a style shape, and subsequently transferring these correspondences to an input shape to generate an output shape with desired stylistic attributes.

Methodology

The paper employs a three-step process:

  • Computing Correspondences: Correspondences between the style shape and a sphere are computed using either the Gauss map or curvature flow, depending on the complexity of the shape.
  • Transferring Correspondences: Correspondences between the sphere and the input shape are computed, allowing for the transfer of surface normals from the style shape to the input shape.
  • Normal-Driven Optimization: An optimization problem is formulated to deform the input shape based on target normals, ensuring that the output shape possesses desired stylistic attributes.

Impressive Results

The paper demonstrates the efficacy of the proposed method through various examples, showcasing the ability to generate diverse and stylized outputs from input shapes. The method allows for the transformation of shapes with intricate details, such as a cow, into styles represented by simpler geometric forms like cones or cubes. The approach’s flexibility in handling different shapes and styles, as well as its efficiency in computation, are among its most impressive results.

Implementation

The algorithm comprises three simple steps:

  1. Map the surface normal of the target style shape to a unit sphere to compute target normals on this sphere ().
  2. Construct analogous target normals () that relate to the normals of input shape () in the same way that the mapped target normals () relate to .
  3. Utilizing inputs and , generate the stylized shape whose normals approximate through optimization.

Generating

Depending on the provided style shape , a set of target normals on a sphere is obtained by closest normals. For simple convex shapes like an icosahedron, is computed by snapping the normals of the sphere to the nearest normal in the style shape .

Generating

Generating target normals on the input shape using analogy necessitates correspondences between and . This is achieved through the Gauss map, leveraging the fact that is always a unit sphere. The unit normal vector of each element on the input shape can be interpreted as a point on , enabling the mapping of signals from back to . Once the correspondences are obtained via the normals of input shape , can be computed by aligning with . In code implementation, this process can be streamlined into a single function. The function directly derives from the surface normals of the target style shape .

1
2
3
4
5
6
7
8
9
10
11
12
void setTargetN(const Eigen::MatrixXd& styleN, const Eigen::MatrixXd& currentN,
                Eigen::MatrixXd& targetN) {
  targetN.resizeLike(currentN);
  for (int i = 0; i < currentN.rows(); i++) {
    int minIdx;
    (styleN.rowwise() - currentN.row(i))
        .rowwise()
        .squaredNorm()
        .minCoeff(&minIdx);
    targetN.row(i) = styleN.row(minIdx);
  }
}

Generating

After obtaining a set of target normals for each vertex , the objective is to derive a deformed output shape that approximates the surface normals to . Let’s denote as a matrix comprising vertex locations with a size of -by-3. As a deformation of the input shape, our output shape uses to signify the -by-3 matrix of the deformed vertex locations. The energy optimization process, driven by normal deformation, can be expressed as:

Here, symbolizes a regularization energy preserving the details of the input mesh, while the second portion quantifies the squared distance from the output unit surface normal to the target output normal at vertex . To denote the Voronoi area of vertex , we use , with serving as a weighting parameter that mediates between the two terms. The variables outline the input (output) location of vertex . With a smaller value of , the method maintains the input shape ; employing a larger promotes shape deformation towards the style of . The selection of is dependent on the user’s objectives and different results can be achieved with varying regularizations.

Normal-Driven Optimization with ARAP

We can use to denote the edge vector between vertices on the original mesh, and e for the edge vectors on the deformed mesh. We can write down the energy that uses ARAP regularization as

We use to denote the edge vectors of the spokes and rims at vertex , to denote a 3-by-3 rotation matrix defined on , and is the cotangent weight of edge . However, this energy is difficult to optimize because the term is non-linear in .

We adapt the observation that the space of unit vectors can be captured by rotations. Thus, we can perform a change of variables by replacing with the rotated unit normal of the input mesh as

where is the th unit vertex normal of the input mesh computed via area-weighted average of face normals, which is constant throughout the optimization. This can be perceived as an approximation of the area-weighted vertex normals of the output mesh

We minimize this energy via the local/global strategy, where the local step involves solving a set of small Orthogonal Procrustes problems and the global step amounts to a linear solve.

Local Step with

Given a fixed , we obtain the optimal rotation for each vertex by solving the following minimization problem

The above optimization is an instance of the Orthogonal Procrustes which finds the best rotation matrix to map a set of vectors to another set of vectors . We can re-write it into a more compact expression as:

where is a -by- diagonal matrix of the cotangent weights , and are -by- matrices concatenating the edge vectors of the face one-ring at the rest and deformed states, respectively. One can then derive the optimal from the SVD of :

up to changing the sign of the column of so that .

Global Step with

The global step updates the deformed vertex positions from a
fixed set of rotations obtained via the local step. This boils down to solving the following problem

We can expand this energy as

It is often convenient to express the summation in terms of matrices.
We introduce a directed incidence matrix with size -by- to represent the edge vectors in as , and we use to represent a -by- diagonal matrix of the weights . Then we can re-write the energy in terms of matrices as

where is the concatenation of all the rotations, is a -by- symmetric matrix, and is a -by- matrix stacking the constant terms which can be computed during the precomputation. We can then find the optimal by solving a linear system

is the cotangent Laplacian. We can pre-factorize to speed up runtime performance. With these pieces in hand, we can minimize our energy by iteratively performing the local and the global steps.

Validation

Results

Higher lambda values result in greater style changes.

By changing , it was observed that the degree to which style affects the original object can indeed be adjusted, with larger values resulting in more significant changes.

Different target normal settings lead to distinct results.

Setting the target normal as a constant or treating it as a function of the output mesh leads to different local minima. Therefore, setting as a constant may yield different results in some cases, such as the ears of the bunny.

In terms of convergence, when is constant, the convergence behaves similarly to the original ARAP, with the energy decreasing monotonically. However, when depends on , a monotonic decrease in energy is not guaranteed. But the optimization still converges in my experiments.

Limitations

While the proposed algorithm presents a direct and efficient approach to style transfer, it still grapples with several unresolved issues. For instance, it remains uncertain whether randomly provided target normals can be achieved through deformation, and if so, whether such alterations might result in surface inversion or other undesired behaviors.

Presently, the method struggles with high-genus style shapes, which entail topological changes. For instance, attempting to utilize curvature flow to morph such shapes into spheres proves unfeasible without addressing essential topological adjustments.

Additionally, the method overlooks area distortion concerns. The adoption of techniques like curvature flow or Gauss maps can induce significant area distortions.