Categories
Research

Piecewise Developable Surfaces

Fellows: Yufan Hu, Robiul Islam Hannan, Kabir Sahni
Mentor: Yusuf Sahillioglu
Volunteer: Vivien van Veldhuizen

Introduction:

Developable surfaces are surfaces that can be unfolded onto a plane without stretching, compression, or other geometric distortion. They are relevant to applications in geometric design, digital fabrication, manufacturing, architecture, and related areas where three-dimensional geometry must be represented or fabricated from planar material. In continuous setting developable surface is charecterized by Gaussian curvature. The Gaussian curvature is formulated as:

K(v)=2π−∑Δ∋vθΔ(v)K(v) = 2\pi – \sum_{\Delta \ni v} \theta_{\Delta}(v) \quad
  • K>0 K>0 means surface is locally a bowl-like shape
  • K=0 K=0  means surface is locally flat in at least one direction 
  • K<0 K<0 means surface is locally a saddle-like shape

Our objective was to minimize non-flat curvature regions while preserving the geometric characteristics of the original surface. To address this problem, we formulated three vertex-based optimization techniques- normal one-ring, double-cone, and virtual-sphere– to relocate vertices through constrained directional searches while minimizing local angle-defect curvature. A complementary 3D-grid-based local search method explores possible vertex movements in the local normal and tangent directions. It then selects the movement that reduces the curvature while maintaining the surface geometry and preventing changes in triangle orientation.

Algorithm 1: Vertex relocation methods

Overview
All three methods restrict vertex motion to one-dimensional directions. However, only the double-cone and virtual-sphere methods explicitly sample and search along multiple rays, while the normal-constrained method jointly optimizes scalar displacements along vertex normals.

Normal joint optimizer
We use the angle defect to measure discrete Gaussian curvature at each interior vertex. A vertex is considered approximately developable when its absolute angle defect is below a prescribed threshold:

|Ωi|≤ϵ|\Omega_i|\leq\epsilon
  • Vertices satisfying ϵ<|Ωi|≤1\epsilon < |\Omega_i| \leq 1 are classified as moderate-defect vertices and selected as optimization targets.
  • Vertices whose initial angle defects satisfy |Ωi|>1|\Omega_i|>1 are treated as singular vertices and remain fixed, since the unavoidable curvature of the surface should be preserved somewhere.


Moving one vertex changes the corner angles and angle defects of its neighbors. Therefore, we jointly optimize each moderate-defect vertex together with its one-ring neighborhood. During one optimization step, each movable vertex is restricted to move along its current normal

𝐱i′=𝐱i+δi𝐧i\mathbf{x}_i’ = \mathbf{x}_i+\delta_i\mathbf{n}_i

Here, 𝐧i\mathbf{n}_i is the fixed vertex normal during the current optimization step, and δi\delta_i is the scalar displacement being optimized. This converts the vertex relocation problem from three variables per vertex to one variable per vertex, while still allowing neighboring vertices to move together.

The main objective penalizes only the part of the angle defect that exceeds the threshold:

Eκ=1|ℋ|∑i∈ℋ(max⁡(|Ωi|−ϵ,0)ϵ)2E_{\kappa} = \frac{1}{|\mathcal{H}|} \sum_{i\in\mathcal{H}} \left( \frac{\max(|\Omega_i|-\epsilon,0)}{\epsilon} \right)^2

The monitored set ℋ\mathcal{H} contains the movable vertices and their neighbors. A vertex contributes zero energy once it satisfies |Ωi|≤ϵ|\Omega_i|\leq\epsilon. Evaluating the energy over the neighborhood is important because reducing curvature at one vertex may transfer curvature to nearby vertices.
The complete objective combines this curvature term with regularization terms:

E=Eκ+λ0E0+λsEs+λpEp+λlEl+λeEeE = E_{\kappa} +\lambda_0E_0 +\lambda_sE_s +\lambda_pE_p +\lambda_lE_l +\lambda_eE_e

The remaining energy terms control how the mesh is deformed:

  • E0E_0 weakly encourages smaller angle defects
  • EsE_s preserves curvature around singular vertices
  • EpE_p limits vertex displacement
  • ElE_l encourages neighboring vertices to move smoothly, and
  • EeE_e penalizes relative edge-length changes.

Together, these terms prevent the optimizer from reducing angle defect by introducing excessive displacement, irregular local motion, or severe geometric distortion.

Figure1: Normal-constrained joint optimization.

Double-cone optimizer
The double-cone optimizer processes moderate-defect vertices sequentially, starting with the vertex having the largest absolute angle defect. At each target vertex, it samples movement directions from two cones centered on the positive and negative vertex-normal directions.
Using the local orthonormal frame (𝐧i,𝐭i1,𝐭i2\mathbf{n}_i,\mathbf{t}_{i1},\mathbf{t}_{i2}), an outward ray is defined as

𝐫j+=cj𝐧i+1−cj2(cos⁡ϕj𝐭i1+sin⁡ϕj𝐭i2),𝐫j−=−𝐫j+.\mathbf{r}_j^{+} = c_j\mathbf{n}_i+ \sqrt{1-c_j^2} \left( \cos\phi_j\,\mathbf{t}_{i1} + \sin\phi_j\,\mathbf{t}_{i2} \right), \qquad \mathbf{r}_j^{-}=-\mathbf{r}_j^{+}.


We sample 30 rays using a cone half-angle of (60∘60^\circ). The golden-angle sequence distributes the rays around the vertex normal.
Along each ray, candidate positions are parameterized by


𝐱i(t)=𝐱ik+t𝐫j,0≤t≤Li.\mathbf{x}_i(t)=\mathbf{x}_i^k+t\mathbf{r}_j, \qquad 0\leq t\leq L_i.


The search distance LiL_i limits both the current movement and the total displacement from the original mesh. We first evaluate five coarse intervals along each ray. If two consecutive samples contain a sign change in the angle defect, binary search is used to locate a near-zero-defect position.
A candidate is accepted only if it reduces the curvature objective and passes the geometric safety checks, including triangle orientation, area preservation, edge distortion, and cumulative displacement limits.
The cone construction is used only to generate search directions; the method does not compute the Shape Diameter Function.

Figure2: Double-cone ray search.

Virtual-sphere optimizer
The virtual-sphere optimizer uses the same search procedure, binary search, objective function, sequential updates, and geometric safety checks as the double-cone method. The only difference is how the ray directions are generated.
Instead of restricting the directions to two cones around the vertex normal, we use a Fibonacci sphere to distribute (m) rays over the entire unit sphere:
zj=1−2(j+1/2)m,ϕj=jπ(3−5)𝐫j=(1−zj2cos⁡ϕj,1−zj2sin⁡ϕj,zj)z_j=1-\frac{2(j+1/2)}{m}, \qquad \phi_j=j\pi(3-\sqrt{5}) \mathbf{r}_j= \left( \sqrt{1-z_j^2}\cos\phi_j,\, \sqrt{1-z_j^2}\sin\phi_j,\, z_j \right)
This allows the vertex to move in unrestricted normal, tangential, and oblique directions. Our current experiment uses (m=30) rays.

Figure3: Virtual-sphere ray search.

Algorithm 2: Grid-based method

Overview
This method proposes a local derivative-free optimization approach for reducing the non-flat curvatures of the triangle mesh while preserving the shape. We first describe the mathematical background of the algorithm and later explain how it reduces non-flat curvatures.

3D-grid local search with orientation protection

Step1:Gaussian curvature approximation
The algorithm uses the Gauss-Bonnet standard discretization formula for triangulated surfaces to estimate discrete Gaussian curvature at each vertex.

K(v1)=2π−∑Δ∋vθΔ(v)K(v1) = 2\pi – \sum_{\Delta \ni v} \theta_{\Delta}(v) \quad
K(v2)=π−∑Δ∋vθΔ(v)K(v2) = \pi – \sum_{\Delta \ni v} \theta_{\Delta}(v) \quad

Here,v1v1 and v2v2 denote the sets of interior and boundary vertices. θΔ(v)\theta_{\Delta}(v) \quadrepresents the interior angle of triangle Δ​ at vertex vv. θΔ(v)\theta_{\Delta}(v) \quad is calculated using the following formula:

θ=arctan2⁡(‖u×v‖,u⋅v)\theta = \operatorname{arctan2}(\Vert u \times v \Vert, u \cdot v)

u⋅vu \cdot v is the cross product proportional to the cos⁡θ\cos\theta and ∥u×v∥\|u \times v\| is proportional to the sin⁡θ\sin\theta .

Figure4: Gaussian curvature approximation.

Step2:
Local Coordinate Frame Construction:

u^=n^×e|n^×e|\hat{u} = \frac{\hat{n} \times e}{|\hat{n} \times e|}

v^=n^×u^\hat{v} = \hat{n} \times \hat{u}

To parameterize the local search space around a vertex, the algorithm constructs a customized local coordinate frame (n^,u^,v^)(\hat{n}, \hat{u}, \hat{v}) using the vertex unit normal vector n^\hat{n} and two orthogonal tangent vectors u^,v^\hat{u}, \hat{v}. ee is an arbitrary reference axis not parallel to n^\hat{n}

3D Grid Vector:

δ(tn,tu,tv)=tnn^+tuu^+tvv^,tn∈κS,tu,tv∈S,S=−η,0,η\delta(t_n, t_u, t_v) = t_n \hat{n} + t_u \hat{u} + t_v \hat{v}, \quad t_n \in \kappa S, \quad t_u, t_v \in S, \quad S = {-\eta, 0, \eta}

We introduce a 3D sampling grid using δ(tn,tu,tv)=tnn^+tuu^+tvv^\delta(t_n, t_u, t_v) = t_n \hat{n} + t_u \hat{u} + t_v \hat{v}the equation by choosing a linear combination of the basis vectors. Here, the step offsets are sampled from a uniform range bounded by a maximum displacement step η\eta. Crucially, the normal displacement tnt_n is scaled down by a damping factor κ\kappa which helps preserve mesh structure and fine geometric details.

Figure5: Local coordinate frame and 3D grid sampling.



Step4: Triangle normal calculation and orientation protection

𝐧Δ′=(p1−p0)×(p2−p0)‖(p1−p0)×(p2−p0)‖,𝐧Δ′⋅𝐧Δ0≥0.2∀Δ∋v\mathbf{n}’_{\Delta} = \frac{(p_1 – p_0) \times (p_2 – p_0)}{\Vert (p_1 – p_0) \times (p_2 – p_0) \Vert}, \quad \mathbf{n}’_{\Delta} \cdot \mathbf{n}^0_{\Delta} \ge 0.2 \quad \forall \Delta \ni v

The algorithm enforces a strict face-inversion constraint of all triangles Δ\Delta incident to the moving vertex vv to ensure that the vertex displacement does not compromise the topological integrity. For any candidate vertex position, the updated unit normal vector 𝐧Δ′\mathbf{n}’_\Delta is calculated via(p1−p0)×(p2−p0)(p_1 – p_0) \times (p_2 – p_0). The algorithm then evaluates the dot product between this candidate normal and the face’s original, unmodified normal
𝐧Δ0\mathbf{n}^0_\Delta. By requiring 𝐧Δ′⋅𝐧Δ0≥0.2\mathbf{n}’_\Delta \cdot \mathbf{n}^0_\Delta \ge 0.2, the algorithm imposes a lower strict bound that rejects any vertex update causing an adjacent triangle distortion. This function prevents mesh flipping, severe distortion, and self-intersection during local search.

Figure6: Orientation protection.



Step5:

Energy objective function:

E(pv)=|K(v)|+∑u∈N(v)[|K(u)|+W⋅1[|K(u)|>ε]]+λ‖pv−pv(0)‖E(p_v) = |K(v)| + \sum_{u \in N(v)} \left[ |K(u)| + W \cdot 1\big[ |K(u)| > \varepsilon \big] \right] + \lambda \| p_v – p_v^{(0)} \|

|K(v)||K(v)| minimizes the local Gaussian curvature defect at vertex vv to smooth irregularities. (∑u∈N(v))(\sum_{u \in N(v)}) evaluates Gaussian curvature changes on all 1-ring neighbour vertices u∈N(v)u \in N(v). [|K(u)|>ε]\mathbb[|K(u)| > \varepsilon] this indicator term applies a penalty ww if a move creates curvature spikes above threshold ε\varepsilon. The regularization term λ\lambda penalizes to prevent excessive surface drift.

Optimization:

pvopt=arg min⁡p∈{pvorig}∪{pvorig+δi}E(p)p_v^{\text{opt}} = \underset{p \in \{p_v^{\text{orig}}\} \cup \{p_v^{\text{orig}} + \delta_i\}}{\operatorname{arg\,min}} E(p)

The optimization evaluates candidate positions pp from the discrete 3D sampling grid set {pvorig+δi{p_v^{\text{orig}} + \delta_i}} alongside the original position pvorigp_v^{\text{orig}}. It greedily selects the candidate position pvoptp_v^{\text{opt}} that minimizes the energy objective E(p)E(p), ensuring the orientation protection constraint.

Figure7: Energy minimization and optimization.

Curvature Reduction and Geometry Preservation

We compare the four operators from two perspectives: curvature reduction and geometry preservation. Curvature-related metrics evaluate how effectively each operator reduces non-flat regions, while geometry-related metrics measure the corresponding deformation and mesh-quality loss.

Table 1: Curvature-state changes.

The transition counts are selected to distinguish corrected curvature violations from newly introduced ones. The final moderate-gray count measures the remaining non-flat vertices, while threshold energy describes the severity of these violations..

FamilyOperatorGray → Yellow ↑Yellow → Gray ↓Net reduction ↑Final moderate gray ↓Threshold energy ↓
Vertex-basedNormal one-ring432553771560.676
Vertex-basedDouble cone369383312023.659
Vertex-basedVirtual sphere349293202133.782
Figure8: From left to right: the original mesh, normal one-ring operator, double-cone operator, virtual-sphere operator, and 3D-grid operator.

Table2: Curvature state transition in Algorithm 2

We evaluated the proposed 3D grid based algorithm on five models namely Cheburashka, Fandisk, Stanford-bunny, Homer, Suzanne. The optimal threshold epsilon was set to 0.1 and the penalty was fixed at 50. The table summrizes the before and after curvature counts with the algorithm run time.

ModelEpsilonPenaltyFlat Vertices
(Before)
Non-Flat Vertices
(Before)
Flat Vertices
(After)
Non-Flat Vertices
(After)
Flat Vertex
Gain
Run time
Cheburashka0.15062933766411258+118308.198s
Fandisk0.150642748642946+258.310s
Stanford-bunny0.1503407154034444167+373410.793s
Homer0.15053136895526476+213535.254s
Suzanne0.150115350193272+78317.417s
Figure9: Visualization of the Cheburashka before(left) and after(right) applying the algorithm. Red, yellow, and blue color point out non-flat, flat, and regions converted non-flat to flat.
Figure10: Visualization of the Fandisk before(right) and after(left) applying the algorithm. Red, yellow, and blue color point out non-flat, flat, and regions converted non-flat to flat.

Table 3: Geometry preservation.
Normalized RMS displacement measures the overall surface change relative to the model size, while maximum edge change captures the worst local edge-length distortion. Minimum area ratio measures the strongest triangle compression, with values closer to one indicating better area preservation. Minimum triangle quality ranges from zero to one, where values near zero indicate thin or nearly degenerate triangles. Maximum normal change measures the largest local surface-orientation deviation, and the flipped-face count detects invalid face inversions.

FamilyOperatorNormalized RMS ↓Max edge change ↓Min area ratio ↑Min quality ↑Max normal change ↓Flipped faces
Vertex-basedNormal one-ring0.00569%24.71%0.3040.0084128.29°0
Vertex-basedDouble cone0.00373%19.14%0.3130.0139029.19°0
Vertex-basedVirtual sphere0.00407%23.97%0.5940.0139073.81°0
Grid-based3D grid0.01315%21.99%0.3510.0139230.00°0

Overall result:
The results indicate no operator dominates across all criteria. The double cone achieved the highest normalized RMS and maximum edge change, with a competitive minimum quality. The virtual sphere preserves triangle area best, but at the cost of a much larger maximum normal change. The normal one ring yields the smallest normal deviation but the lowest minimum quality and the largest edge change. The 3D grid is competitive in quality and normal change but has the highest RMS displacement. All the operators produced zero flipped faces.

Future directions:

  • Extending these algorithm for real time use will likely require cost reduction strategies such as principal component analysis (PCA), proper orthogonal decomposition (POD).
  • The evaluation covers geometric fidelity and mesh validity only. A systematic study of memory scaling and computational cost reduction strategies is a natural direction for future work.
  • Testing on more complex models is needed to check the generalizability of the algorithms.

Reference:

  • R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu, A Limited Memory Algorithm for Bound Constrained Optimization, pp. 1190–1208, 1995. https://doi.org/10.1137/0916069
  • L. Shapira, A. Shamir, and D. Cohen-Or, Consistent Mesh Partitioning and Skeletonisation using the Shape Diameter Function, vol. 24, no. 4, pp. 249–259, 2008. https://doi.org/10.1007/s00371-007-0197-5
  • B. Keinert, M. Innmann, M. S\”anger, and M. Stamminger, Spherical Fibonacci Mapping, vol. 34, no. 6, article 193, 2015. https://doi.org/10.1145/2816795.2818131
  • D. Zint, R. Grosso, and F. Lunz, “Discrete mesh optimization on surface and volume meshes,” in Proc. 28th Int. Meshing Roundtable (IMR), 2019, pp. 159–174.
  • A. Nealen, T. Igarashi, O. Sorkine, and M. Alexa, “Laplacian mesh optimization,” in Proc. 4th Int. Conf. Computer Graphics and Interactive Techniques in Australasia and Southeast Asia (GRAPHITE ‘06), 2006, pp. 381–389.