Refining procedures on mesh via algebraic fitting

Tibor Stanko, Pavel Chalmovianský
Comenius University in Bratislava, Slovakia
2014, CESCG

A new nonlinear refinement algorithm for surfaces is presented in this work. Our scheme operates on triangular meshes and interpolates input data. Each triangle is associated with a small set of neighbouring points and normals. A low degree algebraic surface (quadric) is fitted to this set with respect to the chosen objective function. The new vertex is taken from the computed quadric. Such a setup overcomes the limitations of the linear schemes. Our experiments show the scheme might be capable of reconstructing quadratic surfaces from a coarse approximating mesh. A comparison of the proposed method with the linear schemes is shown, as well as an application to the compression of a large-scale mesh.



@inproceedings{ Stanko:2014:CESCG,
  title = {Refining procedures on mesh via algebraic fitting},
  author = {Tibor Stanko and Pavel Chalmovianský},
  booktitle = {Proc. CESCG 2014},
  editor = {M. Wimmer and J. Hladůvka and M. Ilčík},
  isbn = {978-3-9502533-6-8},
  month = {April},
  year = {2014}

Choosing the weights

The proposed method allows the specification of the weights for each vertex. We demonstrate the effect of different sets of weights on the Stanford bunny.

bunny_3000F_00 bunny_3000F_01 bunny_3000F_04 bunny_3000F_02 bunny_3000F_03

bunny_3000F_00 bunny_3000F_01 bunny_3000F_02 bunny_3000F_04 bunny_3000F_03

Bunny refined with various sets of weights.
Bottom row shows the curvature (red = smaller, blue = higher).

The influence of normals

To show how the change in the prescribed normals influences the limit surface, we applied our method on the Stanford bunny with alternative set of vertex normals. This alternative set of normals was generated randomly from a noise function.

bunny_02 bunny_03 bunny_random02 bunny_random03

Left: original normals. Right: random normals.

Comparison with linear schemes

To compare the proposed algorithm with the linear schemes, we have used the large-scale mesh of the Venus of Dolní Věstonice. This mesh is a discretized version of the small nude female statuette found in Moravia south of Brno. Dated to 29,000-25,000 BCE, it is considered one of the oldest known pieces of ceramic in the world.

venus statuette venus mesh venus decimation

Left: the statuette dating to 29,000-25,000 BCE.
Middle: scanned mesh, 131114 vertices.
Right: decimted mesh, 1356 vertices.

venus QFR venus sqrt3 venus MB venus Loop

The decimated mesh refined four times.
Left to right: our method, √3-subdivision, Modified butterfly, Loop.

venus QFR color venus sqrt3 color venus MB color venus Loop color

venus QFR histogram venus sqrt3 histogram venus MB histogram venus Loop histogram

Hausdorff distance of the refined meshes from the ground truth (scanned mesh).

Reconstruction of quadratic surfaces

The proposed method can also be used to reconstruct quadratic surfaces from a coarse approximating mesh. For instance, with the right choice of weights, it is possible to reconstruct a close approximation of the units sphere from the cube. The initial mesh along with the first 8 iterations is shown below. The last picture is the visualisation of the Hausdorff distance of the limit surface from the original sphere. [red = zero distance, blue = distance ≥ 0.0025 units]


cube 0 cube 1 cube 2 cube 3 cube 4 cube 5 cube 6 cube 7 cube 8 cube dist


cylinder 0 cylinder 1 cylinder 2

cylinder 3 cylinder 4 cylinder 5

cylinder 6 cylinder 7 cylinder 8

Elliptic paraboloid

elliptic 0 elliptic 1 elliptic 2

elliptic 3 elliptic 4 elliptic 5

elliptic 6 elliptic 7 elliptic 8

Hyperbolic paraboloid

hyperbolic 0 hyperbolic 1 hyperbolic 2

hyperbolic 3 hyperbolic 4 hyperbolic 5

hyperbolic 6 hyperbolic 7 hyperbolic 8


The proposed method was implemented using OpenMesh and Armadillo. All figures were created in MeshLab.