Level set surface editing operators

ABSTRACT

We present a level set framework for implementing editing operators for surfaces. Level set models are deformable implicit surfaces where the deformation of the surface is controlled by a speed function in the level set partial differential equation. In this paper we define a collection of speed functions that produce a set of surface editing operators. The speed functions describe the velocity at each point on the evolving surface in the direction of the surface normal. All of the information needed to deform a surface is encapsulated in the speed function, providing a simple, unified computational framework. The user combines pre-defined building blocks to create the desired speed function. The surface editing operators are quickly computed and may be applied both regionally and globally. The level set framework offers several advantages. 1) By construction, self-intersection cannot occur, which guarantees the generation of physically-realizable, simple, closed surfaces. 2) Level set models easily change topological genus, and 3) are free of the edge connectivity and mesh quality problems associated with mesh models. We present five examples of surface editing operators: blending, smoothing, sharpening, openings/closings and embossing. We demonstrate their effectiveness on several scanned objects and scan-converted models.

REFERENCES

• 1: David Adalsteinsson , James A. Sethian, A fast level set method for propagating interfaces, Journal of Computational Physics, v.118 n.2, p.269-277, May 1995 [doi>10.1006/jcph.1995.1098]
• 2: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 3: Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995 [doi>10.1145/218380.218424]
• 4: BARR, A. 1981. Superquadrics and angle-preserving transformations. IEEE Computer Graphics and Applications 1, 1, 11-23.
• 5: Henning Biermann , Daniel Kristjansson , Denis Zorin, Approximate Boolean operations on free-form solids, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.185-194, August 2001 [doi>10.1145/383259.383280]
• 6: Jules Bloomenthal , Brian Wyvill, Introduction to Implicit Surfaces, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 7: Jean-Yves Bouguet , Pietro Perona, 3D Photography Using Shadows in Dual-Space Geometry, International Journal of Computer Vision, v.35 n.2, p.129-149, Nov.-Dec. 1999 [doi>10.1023/A:1008124523456]
• 8: David E. Breen , Ross T. Whitaker, A Level-Set Approach for the Metamorphosis of Solid Models, IEEE Transactions on Visualization and Computer Graphics, v.7 n.2, p.173-192, April 2001 [doi>10.1109/2945.928169]
• 9: BREEN, D., MAUCH, S., AND WHITAKER, R. 2000. 3D scan conversion of CSG models into distance, closest-point and colour volumes. In Volume Graphics, M. Chen, A. Kaufman, and R. Yagel, Eds. Springer, London, 135-158.
• 10: COHEN, E., RIESENFELD, R., AND ELBER, G. 2001. Geometric Modeling with Splines. AK Peters, Natick, MA.
• 11: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 12: DESBRUN, M., AND CANI, M.-P. 1998. Active implicit surface for animation. In Graphics Interface, 143-150.
• 13: Mathieu Desbrun , Marie-Paule Gascuel, Animating soft substances with implicit surfaces, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.287-290, September 1995 [doi>10.1145/218380.218456]
• 14: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 15: DO CARMO, M. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall, Englewood Cliffs, NJ.
• 16: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 17: EVANS, L., AND SPRUCK, J. 1991. Motion of level sets by mean curvature, I. Journal of Differential Geometry 33, 635-681.
• 18: Nick Foster , Ronald Fedkiw, Practical animation of liquids, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.23-30, August 2001 [doi>10.1145/383259.383261]
• 19: Sarah F. Frisken , Ronald N. Perry , Alyn P. Rockwood , Thouis R. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.249-254, July 2000 [doi>10.1145/344779.344899]
• 20: Tinsley A. Galyean , John F. Hughes, Sculpting: an interactive volumetric modeling technique, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.267-274, July 1991
• 21: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 22: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• 23: Leif P. Kobbelt , Mario Botsch , Ulrich Schwanecke , Hans-Peter Seidel, Feature sensitive surface extraction from volume data, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.57-66, August 2001 [doi>10.1145/383259.383265]
• 24: David H. Laidlaw , W. Benjamin Trumbore , John F. Hughes, Constructive solid geometry for polyhedral objects, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.161-170, August 1986
• 25: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 26: Ravikanth Malladi , James A. Sethian , Baba C. Vemuri, Shape Modeling with Front Propagation: A Level Set Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.2, p.158-175, February 1995 [doi>10.1109/34.368173]
• 27: MARAGOS, P. 1996. Differential morphology and image processing. IEEE Trans. on Image Processing 5, 6 (June), 922-937.
• 28: Stanley Osher , Ronald P. Fedkiw, Level set methods: an overview and some recent results, Journal of Computational Physics, v.169 n.2, p.463-502, May 30, 2001 [doi>10.1006/jcph.2000.6636]
• 29: Stanley Osher , James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, v.79 n.1, p.12-49, Nov. 1988 [doi>10.1016/0021-9991(88)90002-2]
• 30: Danping Peng , Barry Merriman , Stanley Osher , Hongkai Zhao , Myungjoo Kang, A PDE-based fast local level set method, Journal of Computational Physics, v.155 n.2, p.410-438, Nov. 1, 1999 [doi>10.1006/jcph.1999.6345]
• 31: Ronald N. Perry , Sarah F. Frisken, Kizamu: a system for sculpting digital characters, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.47-56, August 2001 [doi>10.1145/383259.383264]
• 32: REQUICHA, A., AND VOELCKER, H. 1985. Boolean operations in solid modeling: Boundary evaluation and merging algorithms. Proceedings of the IEEE 73, 1, 30-44.
• 33: Leonid I. Rudin , Stanley Osher , Emad Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, v.60 n.1-4, p.259-268, Nov. 1, 1992
• 34: SAPIRO, G., KIMMEL, R., SHAKED, D., KIMIA, B., AND BRUCKSTEIN, A. 1993. Implementing continuous-scale morphology via curve evolution. Pattern Recognition 26, 9, 1363-1372.
• 35: Geometric partial differential equations and image analysis, Cambridge University Press, New York, NY, 2001
• 36: Jean Serra, Image Analysis and Mathematical Morphology, Academic Press, Inc., Orlando, FL, 1983
• 37: SETHIAN, J. 1996. A fast marching level set method for monotonically advancing fronts. In Proceedings of the National Academy of Science, vol. 93, 1591-1595.
• 38: SETHIAN, J. 1999. Level Set Methods and Fast Marching Methods, second ed. Cambridge University Press, Cambridge, UK.
• 39: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 40: TSITSIKLIS, J. 1995. Efficient algorithms for globally optimal trajectories. IEEE Trans. on Automatic Control 40, 9, 1528-1538.
• 41: Sidney W. Wang , Arie E. Kaufman, Volume-Sampled 3D Modeling, IEEE Computer Graphics and Applications, v.14 n.5, p.26-32, September 1994 [doi>10.1109/38.310721]
• 42: Sidney W. Wang , Arie E. Kaufman, Volume sculpting, Proceedings of the 1995 symposium on Interactive 3D graphics, p.151-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199430]
• 43: William Welch , Andrew Witkin, Free-form shape design using triangulated surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.247-256, July 1994 [doi>10.1145/192161.192216]
• 44: WHITAKER, R., AND XUE, X. 2001. Variable-conductance, level-set curvature for image denoising. In Proc. IEEE International Conference on Image Processing, 142-145.
• 45: WHITAKER, R., BREEN, D., MUSETH, K., AND SONI, N. 2001. Segmentation of biological datasets using a level-set framework. In Volume Graphics 2001, M. Chen and A. Kaufman, Eds. Springer, Vienna, 249-263.
• 46: Ross T. Whitaker, A Level-Set Approach to 3D Reconstruction from Range Data, International Journal of Computer Vision, v.29 n.3, p.203-231, Sept. 1998 [doi>10.1023/A:1008036829907]
• 47: WYVILL, B., GALIN, E., AND GUY, A. 1999. Extending the CSG tree. warping, blending and Boolean operations in an implicit surface modeling system. Computer Graphics Forum 18, 2 (June), 149-158.
• 48: Hong-Kai Zhao , Stanley Osher , Ronald Fedkiw, Fast Surface Reconstruction Using the Level Set Method, Proceedings of the IEEE Workshop on Variational and Level Set Methods (VLSM'01), p.194, July 13-13, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.4 Graphics Utilities
          Subjects: Graphics editors

General Terms:
Algorithms

Keywords:
deformations, geometric modeling, implicit surfaces, shape blending