“Feature sensitive surface extraction from volume data” by Kobbelt, Schwanecke, Botsch and Seidel

  • ©Leif Kobbelt, Ulrich Schwanecke, Mario Botsch, and Hans-Peter Seidel




    Feature sensitive surface extraction from volume data



    The representation of geometric objects based on volumetric data structures has advantages in many geometry processing applications that require, e.g., fast surface interrogation or boolean operations such as intersection and union. However, surface based algorithms like shape optimization (fairing) or freeform modeling often need a topological manifold representation where neighborhood information within the surface is explicitly available. Consequently, it is necessary to find effective conversion algorithms to generate explicit surface descriptions for the geometry which is implicitly defined by a volumetric data set. Since volume data is usually sampled on a regular grid with a given step width, we often observe severe alias artifacts at sharp features on the extracted surfaces. In this paper we present a new technique for surface extraction that performs feature sensitive sampling and thus reduces these alias effects while keeping the simple algorithmic structure of the standard Marching Cubes algorithm. We demonstrate the effectiveness of the new technique with a number of application examples ranging from CSG modeling and simulation to surface reconstruction and remeshing of polygonal models.


    1. N. Amenta, M. Bern, M. Kamvysselis, A New Voronoi-Based Surface Reconstruction Algorithm, Computer Graphics (SIGGRAPH 98 Proceedings), 1998, 415 – 422
    2. J. Arvo, D. Kirk, A Survey of Ray Tracing Acceleration Techniques, An Introduction to Ray Tracing (A. Glassner, ed.), Academic Press, 1989, 201 – 262
    3. J. Bloomental, Polygonization of implicit surfaces, CAGD 5, 1988, 341 – 355
    4. J. Bloomental, C. Bajaj, J. Blinn, M. Cani-Gascuel, A. Rockwood, B. Wyvill, G. Wyvill, Introduction to implicit surfaces, Morgan Kaufmann Publishers, 1997
    5. D. Breen, S.Mauch, R. Whitaker, 3D scan conversion of CSG models into distance volumes, IEEE Symposium on Volume Visualization, 1998, 7 – 14
    6. P. Brunet, I. Navazo, Solid representation and operation using extended octrees, ACM Trans. on Graphics 9 (1990) 2, 170 – 197
    7. B. Curless, M. Levoy, A Volumetric Method for Building Complex Models from Range Images, Computer Graphics (SIGGRAPH 96 Proceedings), 1996, 303 – 312
    8. M. Desbrun, M. Meyer, P. Schroder, A. H. Barr, Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow, Computer Graphics (SIGGRAPH 99 Proceedings), 1999, 317 – 324
    9. P. Dutre, P. Tole, D. Greenberg, Approximate visibility for illumination computations using point clouds, Technical report PCG-00-1, Cornell University, 2000
    10. M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, W. Stuetzle, Multiresolution Analysis of Arbitrary Meshes, Computer Graphics (SIGGRAPH 95 Proceedings), 1995, 173 – 182
    11. K. Hoff, T. Culver, J. Keyser, M. Lin, D, Manocha, Fast computation of generalized Voronoi diagrams using graphics hardware, Computer Graphics (SIG-GRAPH 99 Proceedings, 1999, 277 – 286
    12. J. Foley, A. van Dam, S. Feiner, J. Hughes, Computer Graphics: Principles and Practice, Addison-Wesley, 1992
    13. S. Frisken, R. Perry, A. Rockwood, T. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, Computer Graphics (SIGGRAPH 00 Proceedings), 2000, 249 – 254
    14. M. Garland, P. S. Heckbert, Surface Simplification Using Quadric Error Metrics, Computer Graphics (SIGGRAPH 97 Proceedings), 1997, 209 – 218
    15. S. Gibson, Using Distance Maps for Accurate Surface Representation in Sampled Volumes, IEEE Symposium on Volume Visualization, 1998, 23 – 30
    16. G. Golub, C. van Loan, Matrix Computations, 3rd, Johns Hopkins Univ Press, 1996
    17. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle, Surface Reconstruction from Unorganized Points, Computer Graphics (SIGGRAPH 92 Pro-ceedings), 1992, 71 – 78
    18. H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald, J. Schweitzer, W. Stuetzle, Piecewise smooth surface reconstruction, Computer Graphics (SIGGRAPH 1994 Proceedings), 1994, 295 – 302
    19. H. Hoppe, Progressive Meshes, Computer Graphics (SIGGRAPH 96 Proceedings), 1996, 99 – 108
    20. Y. Livnat, H. Shen, C. Johnson, A near optimal isosurface extraction algorithm using span space, IEEE Trans. Visualization and Computer Graphics, 1996
    21. W. Lorensen, H. Cline, Marching Cubes: a high resolution 3D surface construction algorithm, Computer Graphics (SIGGRAPH 87 Proceedings), 1987, 163 – 169
    22. J. Huang, R. Yagel,V. Filippov, Y. Kurzion, An Accurate Method for Voxelizing Polygon Meshes, ACM 1998 Symposium on Volume Visualization, 1998, 119 – 126
    23. M. Kass, A.Witkin, D. Terzopoulus, Snakes: Active Contour Models, International Journal of Computer Vision, 1988, 321 – 331
    24. D. Kalra, A. Barr, Guaranteed ray intersections with implicit surfaces, Computer Graphics (SIGGRAPH 89 Proceedings), 1989, 297 – 306
    25. A. Kaufman, Efficient Algorithms for 3D Scan-Conversion of Parametric Curves, Surfaces, and Volumes, Computer Graphics, 21, 4, 1987, 171 – 179
    26. A. Kaufman, D. Cohen, R. Yagel, Volume Graphics, IEEE Computer, Vol. 26, No. 7, July 1993, 51 – 64
    27. L. Kobbelt, S. Campagna, J. Vorsatz, H-P. Seidel, Interactive Multi-Resolution Modeling on Arbitrary Meshes, Computer Graphics (SIGGRAPH ’98 Proceedings), 1998, 105 – 114
    28. L. Kobbelt, S. Campagna, H-P. Seidel, A general framework for mesh decimation, Graphics Interface ’98 Proceedings, 1998, 43 – 50
    29. A. Lee, W. Sweldens, P. Schroder, L. Cowsar, D. Dobkin, Multiresolution adaptive parameterization of surfaces, Computer Graphics (SIGGRAPH 98 Proceedings), 1998, 95 – 104
    30. C. Lurig, L. Kobbelt, T. Ertl, Deformable surfaces for feature based indirect volume rendering, Computer Graphics International, IEEE Proceedings, 1998,752 – 760
    31. C. Montani, R. Scateni, R. Scopigno, Discretized marching cubes, IEEE Visualization Conference Proceedings, 1994, 281 – 287
    32. C. Montani, R. Scateni, R. Scopigno, A modified look-up table for implicit disambiguation of Marching Cubes, The Visual Computer (10), 1994, 353 – 355
    33. G. Nielson, B. Hamann, The asymptotic decider: resolving the ambiguity in marching cubes, Visualization ’91, IEEE Computer Society Press, 1991, 83 – 91
    34. A. Rappoport, S. Spitz, Interactive boolean operations for conceptual design of 3D solids, Computer Graphics (SIGGRAPH 97 Proceedings), 1997, 269 – 278
    35. H. Samet, The Design and Analysis of Spatial Data Structures, Addison- Wesley, 1989
    36. G. Schaufler, H. Wann Jensen, Ray tracing point sampled geometry, Eurographics Rendering Workshop Proceedings, 2000, 319 – 328
    37. R. Shekhar, E. Fayyad, R. Yagel, J. Cornhill, Octree-based Decimation of Marching Cubes Surfaces, Visualization ’96, IEEE Conference Proceedings, 1996, 335 – 342
    38. K. Siddiqi, B. Kimia, C. Shu, Geometric Shock-Capturing ENO Schemes for Subpixel Interpolation, Computation and Curve Evolution, Graphical models and image processing (59), 1997, 278 – 301
    39. B. Stander, J. Hart, Guaranteeing the topology of an implicit surface polygonization for interactive modeling, Computer Graphics (SIGGRAPH 97 Proceedings), 1997, 279 – 286
    40. D. Terzopoulus, Regularization of Inverse Visual Problems Involving Discontinuities, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986
    41. G. Taubin, A Signal Processing Approach to Fair Surface Design, Computer Graphics (SIGGRAPH 95 Proceedings), 1995, 351 – 358
    42. G. Turk, J. O’Brien, Shape transformation using variational implicit functions, Computer Graphics (SIGGRAPH 99 Proceedings), 1999, 335 – 342
    43. Z. Wood, M. Desbrun, P. Schroder, D. Breen, Semi-Regular Mesh Extraction from Volumes, Proceedings of Visualization 2000

ACM Digital Library Publication: