“Level set surface editing operators”

  • ©Ken Museth, David E. Breen, Ross Whitaker, and Alan H. Barr

  • ©Ken Museth, David E. Breen, Ross Whitaker, and Alan H. Barr




    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

ACM Digital Library Publication:

Overview Page: