Interactive sculpturing and visualization of unbounded voxel volumes

ABSTRACT

A difficulty of voxel-based sculpturing and modeling is the limitation of the design space by the fixed boundaries of the voxel volume.We present the concept of an infinite voxelized virtual modeling space. A finite shape located in the virtual modeling space is embedded in a voxel window which is enlarged if required by the spatial development of the shape. In order to cope with highly resolved or large shapes, the voxel windows are stored in a virtual voxel memory which implements a paging mechanism to secondary memory. Visualization is performed by meshes obtained by the marching cubes algorithm. Because highly resolved or large shapes may cause a considerable number of triangles, an adaptive meshing approach based on a filtered hierarchy of voxel volumes is presented. The surface mesh is represented in a surface octree which allows for fast rendering by e.g. the Performer library.

REFERENCES

• 1: Jörg Ayasse , Heinrich Müller, Interactive Manipulation of Voxel Volumes with Free-formed Voxel Tools, Proceedings of the Vision Modeling and Visualization Conference 2001, p.359-366, November 21-23, 2001
• 2: Min Chen , Arie Kaufman , Roni Yagel, Volume Graphics, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 3: Yi-Jen Chiang , Cláudio T. Silva , William J. Schroeder, Interactive out-of-core isosurface extraction, Proceedings of the conference on Visualization '98, p.167-174, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 4: P. Cignoni, F. Ganovelli, C. Montani, R. Scopigno. Reconstruction of topologically correct and adaptive trilinear isosurfaces. Computers & Graphics, 24 (3):399--418, 2000
• 5: 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]
• 6: 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
• 7: Taosong He , Lichan Hong , Amitabh Varshney , Sidney W. Wang, Controlled Topology Simplification, IEEE Transactions on Visualization and Computer Graphics, v.2 n.2, p.171-184, June 1996 [doi>10.1109/2945.506228]
• 8: Hugues Hoppe, View-dependent refinement of progressive meshes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.189-198, August 1997 [doi>10.1145/258734.258843]
• 9: K.C. Hui. Solid Sweeping in image space - application in NC simulation, The Visual Computer, 10:306--316, 1994
• 10: F.-L. Krause , J. Lüddemann, Virtual clay modelling, Proceedings of the fifth IFIP TC5/WG5.2 international workshop on geometric modeling in computer aided design on Product modeling for computer integrated design and manufacture, p.162-175, January 1997, Airlie, Virginia, United States
• 11: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 12: J. Lü:uddemann.Virtual clay modeling for sclupturing by sketching in industrial design (in German). Doctoral thesis, IWF of the Technical University of Berlin 1996
• 13: William A. McNeely , Kevin D. Puterbaugh , James J. Troy, Six degree-of-freedom haptic rendering using voxel sampling, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.401-408, July 1999 [doi>10.1145/311535.311600]
• 14: D. Meagher. Geometric modeling using octree encoding. Computer Graphics and Image Processing, 19:129--147, 1982
• 15: G.M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Research Report 1, IBM Ltd., Ottawa, Ontario, 1966
• 16: Valerio Pascucci , Randall J. Frank, Global static indexing for real-time exploration of very large regular grids, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.2-2, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582036]
• 17: 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]
• 18: John Rohlf , James Helman, IRIS performer: a high performance multiprocessing toolkit for real-time 3D graphics, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.381-394, July 1994 [doi>10.1145/192161.192262]
• 19: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 20: Raj Shekhar , Elias Fayyad , Roni Yagel , J. Fredrick Cornhill, Octree-based decimation of marching cubes surfaces, Proceedings of the 7th conference on Visualization '96, p.335-ff., October 28-29, 1996, San Francisco, California, United States
• 21: R. Shu, C. Zhou, M.S. Kankanhalli. Adaptive marching cubes. The Visual Computer, 11(4):202--217, 1995
• 22: Abraham Silberschatz , Peter Baer Galvin, Operating System Concepts, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 23: Y. Takai, N.K. Takai. A deformable object in the active voxel space. In Proceedings of the IASTED International Conference, Computer Graphics and Imaging, October 25--27, 1999, Palm Springs, California, USA
• 24: V. Valsalam. Efficient indexing algorithm for Morton order storage of 2D arrays. Research Report MSSU-COE-ERC-99-3, Mississippi State University, April 1999
• 25: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 26: 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]
• 27: R. Westermann, L. Kobbelt, T. Ertl. Real-time exploration of regular volume data by adaptive reconstruction of isosurfaces. The Visual Computer, 15(2):100--111, 1999

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

General Terms:
Algorithms, Design

Keywords:
adaptive surface extraction, computer-aided sculpturing, external memory data structures, volume modeling