CMPT 469
Final Project

Surface Reconstruction
Using Shrinkwrap

by Karl Berg and Ben Hester

April 18, 2005

Surface Reconstruction  

     • Polygonal mesh most popular form of digital geometry
     • Currently, meshes painstakingly designed by hand or scanned with laser scanner
     • With no connectivity, scanned point clouds have limited usefulness
     • Need to build surface from the point set alone
     • Assumptions: points sampled to specified ρ-density, noise limited to δ

Our approach: Shrinkwrap  

     • Shrink a loose approximating surface until tightly conforms to underlying point set
     • Conceptually, like shrinkwrapping an object with plastic
     • Partly designed to address issue with "expanding balloon" deform-to-fit
         technique (touched on briefly in class)
     • Balloon approach needs a starting point "inside" the unknown surface
     • Opposite approach, shrinking, requires only knowing "outside" (use convex hull)


     • Manifold surface interpolating all points
     • No edge lengths greater than ρ
     • Minimize total volume of resulting shape


     1. Start with convex hull
     2. Incrementally refine until all points lie on the surface
     3. Edge swap to improve triangulation
     4. Delete triangles with edges longer than ρ
     5. Retriangulate resulting holes

         Separated into preprocess, refinement, postprocess
         Enabled combining different algorithms for each portion

Original Model  

     Convex Hull  

Shrinkwrap Complete  


Edges Swapped  

Original Model  

     Reconstructed Surface  


     • Big question is, which face should be refined next, and with which vertex?
     • Need a distance metric that can take all these factors into account

Distance metrics  

     • Used to determine next candidate vertex and candidate polygon for refinement
     • Many distance metrics were evaluated with varying results

i) Closest Point to Plane:  

     • Uses bounding planes for quick and efficient culling
     • Like sweeping a polygon along its normal to create a prism
     • Points within prism use distance to plane
     • Points outside prism are given infinite distance

ii) Closest Point to Plane using adaptive slabs:  

     • Using orthogonal bounding planes can cause spiking
     • Caused when point lies near concave edge
     • Attempted to fix by using averaged split plane when concave edge detected
     • Didn't fix all conditions (point directly above edge)
     • Worsened problems with 'snaking'

iii) Distance to plane clipped with 45 degree slabs:  

     • An attempt to eliminate all spiking
     • Rotated bounding slabs 45 degrees away from the normal
     • Results too chaotic to properly examine
     • Extreme problems with snaking and sliding

iv) Distance to min(plane, edges, verts):  

     • Much smarter attempt to eliminate spiking
     • Calculate clipped distances to polygon, edges, and vertices, and take minimum
     • Polygon slabs are built orthogonal to face normal
     • Edges are clipped by testing against two of three bounding slabs
     • Still experienced moderate amounts of snaking and sliding
     • An attempt to prioritize larger triangles for refinement
     • Attempt to decimate convex hull by forcing even refinement
     • Preserved convex hull lines quite nicely
     • Still experiencing problems with snaking and sliding

vi) Distance to min(plane, edges, verts) / max(edge)alpha:  

     • Holds true to our heuristic of shortest possible edges
     • Nicely decimated features created by convex hull
     • Alpha variable allowed us to test various edge length biases
     • We found that alpha = 1/4 provides nice results
     • Still experienced moderate amounts of snaking and sliding

vii) Weighted edge, vertex metric:  

     • Our most stable metric
     • Causes distance metric to smoothly fall off as candidate approaches co-planar
     • Candidates that are actually co-planar are given infinite distance
     • Candidates which lie within prism region are unaffected
     • Utilizes same large edge bias as previously
     • Fixes many problems with snaking and sliding
     • Still experiences problems with inverted reconstruction
     • Performs poorly on large co-planar regions (cube)

viii) Centroid weighted metric:  

     • Designed to improve results on mostly co-planar input data
     • Divides by dot product between normal and (candidate - centroid)
     • Causes distance to approach infinity as point approaches coplanar
     • Biases candidates closer to the centroid higher then edges
     • Greatly improves cube example, but in general performs worse


     • Shrinkwrap leaves many edges of length > ρ
     • Edge swapping a few times removes most of these long edges
     • However, long appendages on the mesh (like limbs) are often still joined
     • To deal with the remaining overlength edges, we perform a snip
     • Snipping is done by growing "snip patches"
          -- sets of connected faces with overlength edges
     • As we grow the snip patch, we keep track of its boundary
     • After deleting the patch, we then retriangulate along the boundary ring


     • Truly robust retriangulation algorithms are difficult to implement
     • We use the ring heuristic, but combine it with a greedy shortest-new-edge metric
     • In practice, this has given reasonable results for its complexity





Shrinkwrap for simplification  

     • Andrea Bottino, Wim Nuij and Kees van Overveld, 1996 [5]
     • Start with an iso-surface (eg sphere)
     • Iteratively shrink iso-surface, error metric created when object 'hits' surface
     • When error metric reaches a threshold, surface is split at that point

Shrinkwrap for remeshing  

     • Leif P. Kobbelt, Jens Vorsatz, Ulf Labsik and Hans-Peter Seidel, 1999 [6]
     • Starts with simplified surface (eg sphere) with subdivision connectivity
     • Iteratively projects down towards object
     • Movement is balanced between an attracting and relaxing force
     • Attraction 'shrinks' the surface, relaxing conforms surface to object underneath

     • Both algorithms experience many of the same problems
     • Extra bits left over from shrinkwrap process (long edges)
     • Extra attention required for genus > 0

Problems and Limitations  

Inverted Regions
     • One of the key problems: shrinkwrap can sometimes invert and build inside-out
     • Manifests itself as what appear to be inverted normals, but mesh is manifold
     • Mesh actually twists and passes through itself = complications in later stages
     • Means two points near each other in 3-space not necessarily nearby on surface
     • Tends to leave what look like long cracks and ruptures in the surface
     • Unfortunately, not solved by snipping and retriangulating
     • Rupture edges generally of acceptable length, won't be included in snip patch
     • Probably need to devise yet another modification to the distance metric

     • Our retriangulation scheme is simple and far from robust
     • Sometimes creates nonmanifold retriangulations
     • Greedy choice (shortest edge first) may force overlength edges later
     • Highly undesirable, since that was the very purpose of snipping and retriangulating!

Edge Swap Reliance
     • We rely heavily on edge swapping to clean up poor triangulations
     • We always swap edges if by doing so we create a shorter edge than the original
     • Destroys contours and features
     • On sparse meshes, can significantly affect reconstructed surface quality
     • (compare Isis to Isis-edgeswap)
     • Even on dense meshes, fine details and small contours are easily lost
     • Solution: detect features like contours and avoid swapping them

Future Work  

     • Solve inside-out construction
     • Implement robust retriangulation algorithm
     • Preserve features on edge swap
     • Improve speed using heaps and perhaps lazy evaluation of distance metrics
     • Ability to connect disjoint rings (torus)
     • Ability to separate disjoint objects


      [1] M. Kass, A. Witkin, and D. Terzopoulos, "Active contour models," International Journal of Computer Vision 1(4), pp. 321-331, 1987

      [2] W. Schroeder, J. Zarge, and W. Lorensen. Decimation of Triangle Meshes. Computer Graphics, Volume 25, No. 3, (Proc. SIGGRAPH `92), July, 1992

      [3] F. Bernardini, C. Bajaj, J. Chen, D. Shikore, "A Triangulation-Based Object Reconstruction Method," In 6th Annual Video Review of Computational Geometry, 13th ACM Symposium on Computational Geometry, pp. 1-4, 1997

      [4] Rick Parent, Computer Animation: Algorithms and Techniques, Morgan Kaufmann Publishers, pp. 437-447. 2002

      [5] Andrea Bottino, Wim Nuij and Kees van Overveld, How to Shrinkwrap through a Critical Point: an Algorithm for the Adaptive Triangulation of Iso-Surfaces with Arbitrary Topology, 1996

      [6] Leif P. Kobbelt, Jens Vorsatz, Ulf Labsik and Hans-Peter Seidel, A Shrink Wrapping Approach to Remeshing Polygonal Surfaces, 1999