“Level set surface editing operators”

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.

1. ADALSTEINSSON, D., AND SETHIAN, J. 1995. A fast level set method for propagating interfaces. Journal of Computational Physics 118, 269-277. Google Scholar
2. AMENTA, N., BERN, M., AND KAMVYSSELIS, M. 1998. A new voronoi-based surface reconstruction algorithm. In Proc. SIGGRAPH ’98, 415-421. Google Scholar
3. BAJAJ, C., BERNARDINI, F., AND XU, G. 1995. Automatic reconstruction of surfaces and scalar fields from 3D scans. In Proc. SIGGRAPH ’95, 109-118. Google Scholar
4. BARR, A. 1981. Superquadrics and angle-preserving transformations. IEEE Computer Graphics and Applications 1, 1, 11-23.Google Scholar
5. BIERMANN, H., KRISTJANSSON, D., AND ZORIN, D. 2001. Approximate Boolean operations on free-form solids. In Proc. SIGGRAPH 2001, 185-194. Google Scholar
6. BLOOMENTHAL, J., ET AL., Eds. 1997. Introduction to Implicit Surfaces. Morgan Kaufmann, San Francisco. Google Scholar
7. BOUGUET, J.-Y., AND PERONA, P. 1999. 3D photography using shadow in dual space geometry. International Journal of Computer Vision 35, 2 (Nov/Dev), 129-149. Google Scholar
8. BREEN, D., AND WHITAKER, R. 2001. A level set approach for the metamorphosis of solid models. IEEE Trans. on Visualization and Computer Graphics 7, 2, 173-192. Google Scholar
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.Google Scholar
10. COHEN, E., RIESENFELD, R., AND ELBER, G. 2001. Geometric Modeling with Splines. AK Peters, Natick, MA.Google Scholar
11. CURLESS, B., AND LEVOY, M. 1996. A volumetric method for building complex models from range images. In Proc. SIGGRAPH ’96, 303-312. Google Scholar
12. DESBRUN, M., AND CANI, M.-P. 1998. Active implicit surface for animation. In Graphics Interface, 143-150.Google Scholar
13. DESBRUN, M., AND GASCUEL, M. 1995. Animating soft substances with implicit surfaces. In Proc. SIGGRAPH 95 Conference, 287-290. Google Scholar
14. DESBRUN, M., MEYER, M., SCHRÖDER, P., AND BARR, A. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In Proc. SIGGRAPH ’99, 317-324. Google Scholar
15. DO CARMO, M. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
16. EDELSBRUNNER, H., AND MÜCKE, E. 1994. Three-dimensional alpha shapes. ACM Trans. on Graphics 13, 1, 43-72. Google Scholar
17. EVANS, L., AND SPRUCK, J. 1991. Motion of level sets by mean curvature, I. Journal of Differential Geometry 33, 635-681.Google Scholar
18. FOSTER, N., AND FEDKIW, R. 2001. Practical animation of liquids. In Proc. SIGGRAPH 2001, 23-30. Google Scholar
19. FRISKEN, S., PERRY, R., ROCKWOOD, A., AND JONES, T. 2000. Adaptively sampled distance fields: A general representation of shape for computer graphics. In SIGGRAPH 2000 Proceedings, 249-254. Google Scholar
20. GALYEAN, T., AND HUGHES, J. 1991. Sculpting: An interactive volumetric modeling technique. In Proc. SIGGRAPH ’91, 267-274. Google Scholar
21. HOFFMANN, C. 1989. Geometric and Solid Modeling. Morgan Kaufmann, San Francisco. Google Scholar
22. KOBBELT, L., CAMPAGNA, S., VORSATZ, J., AND SEIDEL, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In Proc. SIGGRAPH ’98, 105-114. Google Scholar
23. KOBBELT, L. P., BOTSCH, M., SCHWANECKE, U., AND SEIDEL, H.-P. 2001. Feature sensitive surface extraction from volume data. In Proc. SIGGRAPH 2001, 57-66. Google Scholar
24. LAIDLAW, D., TRUMBORE, W., AND HUGHES, J. 1986. Constructive solid geometry for polyhedral objects. In Proc. SIGGRAPH ’86, 161-170. Google Scholar
25. LORENSEN, W., AND CLINE, H. 1987. Marching Cubes: A high resolution 3D surface construction algorithm. In Proc. SIGGRAPH ’87, 163-169. Google Scholar
26. MALLADI, R., SETHIAN, J., AND VEMURI, B. 1995. Shape modeling with front propagation: A level set approach. IEEE Trans. on Pattern Analysis and Machine Intelligence 17, 2, 158-175. Google Scholar
27. MARAGOS, P. 1996. Differential morphology and image processing. IEEE Trans. on Image Processing 5, 6 (June), 922-937. Google Scholar
28. OSHER, S., AND FEDKIW, R. 2001. Level set methods: An overview and some recent results. Journal of Computational Physics 169, 475-502. Google Scholar
29. OSHER, S., AND SETHIAN, J. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. Journal of Computational Physics 79, 12-49. Google Scholar
30. PENG, D., MERRIMAN, B., OSHER, S., ZHAO, H.-K., AND KANG, M. 1999. A PDE-based fast local level set method. Journal of Computational Physics 155, 410-438. Google Scholar
31. PERRY, R., AND FRISKEN, S. 2001. Kizamu: A system for sculpting digital characters. In Proc. SIGGRAPH 2001, 47-56. Google Scholar
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.Google Scholar
33. RUDIN, L., OSHER, S., AND FATEMI, C. 1992. Nonlinear total variation based noise removal algorithms. Physica D 60, 259-268. Google Scholar
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.Google Scholar
35. SAPIRO, G. 2001. Geometric Partial Differential Equations and Image Analysis. Cambridge University Press, Cambridge, UK. Google Scholar
36. SERRA, J. 1982. Image Analysis and Mathematical Morphology. Academic Press, London. Google Scholar
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.Google Scholar
38. SETHIAN, J. 1999. Level Set Methods and Fast Marching Methods, second ed. Cambridge University Press, Cambridge, UK. Google Scholar
39. TAUBIN, G. 1995. A signal processing approach to fair surface design. In Proc. SIGGRAPH ’95, 351-358. Google Scholar
40. TSITSIKLIS, J. 1995. Efficient algorithms for globally optimal trajectories. IEEE Trans. on Automatic Control 40, 9, 1528-1538.Google Scholar
41. WANG, S., AND KAUFMAN, A. 1994. Volume-sampled 3D modeling. IEEE Computer Graphics and Applications 14, 5 (September), 26-32. Google Scholar
42. WANG, S., AND KAUFMAN, A. 1995. Volume sculpting. In Proc. Symposium on Interactive 3D Graphics, ACM SIGGRAPH, 151-156. Google Scholar
43. WELCH, W., AND WITKIN, A. 1994. Free-form shape design using triangulated surfaces. In Proc. SIGGRAPH ’94, 247-256. Google Scholar
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.Google Scholar
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. Google Scholar
46. WHITAKER, R. 1998. A level-set approach to 3D reconstruction from range data. International Journal of Computer Vision 29, 3, 203-231. Google Scholar
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.Google Scholar
48. ZHAO, H.-K., OSHER, S., AND FEDKIW, R. 2001. Fast surface reconstruction using the level set method. In Proc. 1st IEEE Workshop on Variational and Level Set Methods, 194-202. Google Scholar