A real-time virtual sculpting application by using an optimized hash-based octree

The aim of this study is to develop a new 3D virtual sculpting system by using a hash-based octree data structure with an optimized approach to reduce the huge memory and computation cost and also the tree traversal time. The system first reads the selected 3D virtual object model, which must be in a triangular watertight polygon mesh format. Then both the surface and the interior volume of the virtual object is voxelized in order to generate its volumetric dataset. Afterwards, a hash-based data structure with a novel optimized approach is applied to the dataset. After each sculpting process applied to the virtual object, its surface is locally reconstructed and a feedback force is calculated synchronously. Finally, to give the user a realistic sense of interaction, the feedback force is sent back via a haptic device. Creation durations of a traditional octree, a hash-based octree, and our optimized hash-based octree are compared. Tree traversal and surface reconstruction times of our optimized hash-based octree approach are also compared with the pointer-based one in off-line and real-time while sculpting a 3D model. It is shown that the memory requirement and durations of our optimized approach are the lowest

PDF

___

[1] Zhang W. Virtual Prototyping with Surface Reconstruction and Freeform Geometric Modeling Using Level-set Method. PhD, Missouri University of Science and Technology, Rolla, MO, USA, 2008.
[2] Galyean A, Hughes JF, Sculpting: an interactive volumetric modeling technique. Computer Graphics 1991; 25: 268-274.
[3] Perng, KL, Wang WT, Flanagan M, Ouhyoung M. A real-time 3d virtual sculpting tool based on modified marching cubes. In: Proceedings of International Conference on Artificial Reality and Telexistence; 2001. pp. 64-72.
[4] Ho CC, Tu CH, Ouhyoung M. Detail sculpting using cubical marching squares. In: ICAT05-Proceedings of the 2005 International Conference on Augmented Telexistence; 2005. pp. 10-15.
[5] Niu Q, Chi X, Leu MC, Ochoa J. Image processing, geometric modeling and data management for development of a virtual bone surgery system. Computer Aided Surgery 2008; 13: 30-40.
[6] Yau HT, Tsou LS, Tsai MJ. Octree-based virtual dental training system with a haptic device. Computer-Aided Design & Applications 2006; 3: 415-424.
[7] Lorensen WE, Cline HE, Marching Cubes: A high resolution 3D surface construction algorithm. Computer Graphics 1987; 21: 163-169.
[8] Wang S, Kaufman AE. Volume sculpting. In: Symposium on Interactive Graphics 1995; ACM SIGGRAPH.
[9] Barentzen A. Octree-based volume sculpting. In: IEEE Visualization 98, Late Breaking Hot Topics Proceedings; 1998; IEEE Computer Society Press. pp. 9-12.
[10] Ferley E, Cani MP, Gascuel JD. Practical volumetric sculpting. The Visual Computer 2000; 16: 469-480.
[11] Ferley E, Cani MP, Gascuel JD. Resolution adaptive volume sculpting. Journal of Graphical Models 2001; 63: 459-478.
[12] Raffin R, Gesquiere G, Remy E, Thon S. VirSculpt: a virtual sculpting environment. In: International Conference Graphicon; 2004. pp. 184-187.
[13] Heurtebise X, Thon S. Discrete tools for virtual sculpture. In: GRAPP06; 2006. pp. 415-422.
[14] Heurtebise X, Thon S. Multiresolution representation and deformation of very large volume datasets based on Haar wavelets. In: 3rd International Conference on Geometric Modeling and Imaging; 2008. pp. 34-40.
[15] Heurtebise X, Thon S. A repartition structure for collision detection and deformation of discrete objects based on 3D wavelets. International Journal of Computer Information Systems and Industrial Management Applications 2011; 3: 568-577.
[16] C¸it G, Ayar K, Sertta¸s S, Oz C. A real-time virtual sculpting application with a haptic device. Turkic World ¨ Mathematical Society Journal of Applied and Engineering Mathematics 2013; 3: 105-112.
[17] Foley JD, Van Dam A, Feiner SK, Hughes JF. Computer Graphics: Principles and Practice. 2nd Edition. Boston, MA, USA: Addison-Wesley, 1990. pp. 92-99.
[18] Kaufman A, Cohen D, Yagel R. Volume Graphics. IEEE Computer 1993; 26: 51-64.
[19] Dong Z, Chen W, Bao H, Zhang H, Peng Q. Real-time voxelization for complex polygonal models. In: Proceedings of 12th Pacific Conference on Computer Graphics and Applications; 2004. pp. 43-50.
[20] M¨oller AT. Fast 3d triangle-box overlap testing. Journal of Graphics Tools 2001; 6: 29-33.
[21] M¨oller AT, Haines E. Real-Time Rendering, Natick, MA, USA: AK Peters Ltd, 2002.
[22] Feng L, Soon SH. An effective 3D seed fill algorithm. Comput & Graphics 1998; 22: 641-644.
[23] Oz C, C¸it G, Ayar K. Multithreaded voxelization method for virtual sculpting. European Conference of Technology ¨ and Society, 2013.
[24] Knoll A, Wald I, Parker S, Hansen C. Interactive isosurface ray tracing of large octree volumes. In: Proceedings of the IEEE Symposium on Interactive Ray Tracing; 2006. pp. 115-124.
[25] Samet H. Applications of Spatial Data Structures. Boston, MA, USA: Adison-Wesley, 1989.
[26] Gargantini I. Linear octrees for fast processing of three dimensional objects. Computer Graphics and Image Processing 1982; 4: 365-374.
[27] Castro R, Lewiner T, Lopes H, Tavares G, Bordignon A. Statistical optimization of octree searches. Computer Graphics Forum 2008; 27: 1557-1566.
[28] Morton GM. A Computer Oriented Geodetic Database and a New Technique in File Sequencing. IBM Ltd, 1966.
[29] Stocco L, Schrack G. Integer dilation and contraction for quadtrees and octrees. In: Proc. IEEE Pacific Rim Conf. Communications, Computers and Signal Processing (PACRIM 95); 1995. pp. 426-428.
[30] Stocco L, Schrack G. On spatial orders and location codes. IEEE Transactions on Computers 2009; 58: 424-432.
[31] Basdogan C, Srinivasan MA. Haptic Rendering in Virtual Environments. Handbook of Virtual Environments: Design, Implementation, and Applications. Boca Raton, FL, USA: CRC Press, 2002. pp. 117-134.