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)

Goals

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

Overview

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

 Snaking Spiking

Sliding
• 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

Snipping

• 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

Retriangulation

• 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

Reconstructed

Results

 Original Reconstructed

Shrinkwrap for simplification

• Andrea Bottino, Wim Nuij and Kees van Overveld, 1996 [5]
• 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

Retriangulation
• 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

References

 [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