›› 2010, Vol. 25 ›› Issue (3): 562-571.

• Computer Graphics and Visualization • Previous Articles     Next Articles

Harmonic Field Based Volume Model Construction from Triangle Soup

Chao-Hui Shen1 (沈超慧), Guo-Xin Zhang1(张国鑫), Student Member, CCF, Yu-Kun Lai2 (来煜坤), Shi-Min Hu1 (胡事民), Senior Member, CCF, and Ralph R. Martin2   

  1. 1Tsinghua National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
    2School of Computer Science, Cardiff University, Cardiff, U.K.
  • Received:2010-01-12 Revised:2010-02-24 Online:2010-05-05 Published:2010-05-05
  • About author:
    Chao-Hui Shen received the Bachelor's degree in computer science from Tsinghua University, Beijing, in 2008. He is currently a Ph.D. candidate in the Department of Computer Science and Technology, Tsinghua University. His research interests include computer graphics, geometric modeling, and processing.
    Guo-Xin Zhang received the Bachelor's degree in computer science from Tsinghua University, Beijing, in 2007, and is currently a Ph.D. candidate in the Department of Computer Science and Technology, Tsinghua University. His research interests include computer graphics, geometric modeling, and image processing. He is a student member of CCF.
    Yu-Kun Lai received his Bachelor's and Ph.D. degrees in computer science from Tsinghua University in 2003 and 2008, respectively. He is currently a lecturer of visual computing in the School of Computer Science and Informatics, Cardiff University, Wales, UK. His research interests include computer graphics, geometry processing, computer-aided geometric design and computer vision.
    Shi-Min Hu is currently a chair professor in the Department of Computer Science and Technology, Tsinghua University, Beijing. He received the Ph.D. degree from Zhejiang University in 1996. His research interests include digital geometry processing, video processing, rendering, computer animation, and computer-aided geometric design. He is on the editorial boards of Computer Aided Design (Elsevier) and Journal of Computer Science and Technology (Springer). He is a senior member of CCF.
    Ralph R. Martin has been working in geometric computing since 1979, obtaining his Ph.D. degree in 1983 from Cambridge University. Since then he has been at Cardiff University, as professor after 2000. He is also a guest professor at Tsinghua University and Shandong University in China, and the deputy director of Scientific Programmes of the Welsh Institute of Visual Computing. His publications include about 200 papers and 10 books covering such topics as solid modelling, surface modelling, reverse engineering, intelligent sketch input, mesh processing, video processing, computer graphics, vision based geometric inspection, and geometric reasoning. He is a fellow of the Institute of Mathematics and Its Applications, and a member of the British Computer Society. He is on the editorial boards of Computer Aided Design, Computer Aided Geometric Design, the International Journal of Shape Modelling, CAD and Applications, and the International Journal of CADCAM.
  • Supported by:

    This work was supported by the National Basic Research 973 Program of China under Grant No. 2006CB303106, the National Natural Science Foundation of China under Grant Nos. 90718035 and U0735001.

Surface triangle meshes and volume data are two commonly used representations of digital geometry. Converting from triangle meshes to volume data is challenging, since triangle meshes often contain defects such as small holes, internal structures, or self-intersections. In the extreme case, we may be simply presented with a set of arbitrarily connected triangles, a ``triangle soup''. This paper presents a novel method to generate volume data represented as an octree from a general 3D triangle soup. Our motivation is the Faraday cage from electrostatics. We consider the input triangles as forming an approximately closed Faraday cage, and set its potential to zero. We then introduce a second conductor surrounding it, and give it a higher constant potential. Due to the electrostatic shielding effect, the resulting electric field approximately lies in that part of space outside the shape implicitly determined by the triangle soup. Unlike previous approaches, our method is insensitive to small holes and internal structures, and is observed to generate volumes with low topological complexity. While our approach is somewhat limited in accuracy by the requirement of filling holes, it is still useful, for example, as a preprocessing step for applications such as mesh repair and skeleton extraction.

[1] Lorensen W E, Cline H E. Marching cubes: A high resolution 3D surface construction algorithm. In Proc. SIGGRAPH1987, Anaheim, USA, July 27-31, 1987, pp.163-169.

[2] Ju T, Losasso F, Schaefer S, Warren J. Dual contouring of hermite data. In Proc. SIGGRAPH 2002, San Antonio, USA, July 21-36, 2002, pp.339-346.

[3] Huang J, Yagel R, Filippov V, Kurzion Y. An accurate method for voxelizing polygon meshes. In Proc. 1998 IEEE Symposium on Volume Visualization, Research Triangle Park, USA, Oct. 24, 1998, pp.119-126.

[4] Oomes S, Snoeren P, Dijkstra T. 3D shape representation: Transforming polygons into voxels. In Proc. SCALESPACE1997, Utrecht, The Netherlands, July 2-4, 1997, pp.349-352.

[5] Frisken S F, Perry R N, Rockwood A P, Jones T R. Adaptively sampled distancefields: A general representation of shape for computer graphics. In Proc. SIGGRAPH 2000, New Orleans, USA, July 23-28, 2000, pp.249-254.

[6] Ju T. Fixing geometric errors on polygonal models: A survey. J. Comput. Sci. Technol., 2009, 24(1): 19-29.

[7] Ju T. Robust repair of polygonal models. ACM Trans. Graph., 2004, 23(3): 888-895.

[8] Ju T, Baker M L, Chiu W. Computing a family of skeletons of volumetric models for shape description. Computer-Aided Design, 2007, 39(5): 352-360.

[9] Nooruddin F S, Turk G. Simplification and repair of polygonal models using volumetric techniques. IEEE Transactions on Visualization and Computer Graphics, 2003, 9(2): 191-205.

[10] Nooruddin F S, Turk G. Interior/exterior classification of polygonal models. In Proc. VIS 2000, Salt Lake City, USA, Oct. 8-13, 2000, pp.415-422.

[11] Zhang E, Turk G. Visibility-guided simplification. In Proc. VIS 2002, Boston, USA, Oct. 27-Nov. 1, 2002, pp.267-274.

[12] Dachille F, Kaufman A E. Incremental triangle voxelization. In Proc. Graphics Interface 2000, Montreal, Canada, May 15-17, 2000, pp.205-212.

[13] Andujar C, Brunet P, Ayala D. Topology-reducing surface simplification using a discrete solid representation. ACM Trans. Graph., 2002, 21(2): 88-105.

[14] Sigg C, Peikert R, Gross M. Signed distance transform using graphics hardware. In Proc. VIS 2003, Seattle, USA, October 19-24, 2003, pp.83-90.

[15] Carr J C, Beatson R K, Cherrie J B, Mitchell T J, FrightWR, McCallum B C, Evans T R. Reconstruction and representation of 3D objects with radial basis functions. In Proc. SIGGRAPH2001, Los Angeles, USA, Aug. 12-17, 2001, pp.67-76.

[16] Kazhdan M, Bolitho M, Hoppe H. Poisson surface reconstruction. In Proc. SGP 2006, Cagliari, Italy, June 26-28, 2006, pp.61-70.

[17] Shen C, O'Brien J F, Shewchuk J R. Interpolating and approximating implicit surfaces from polygon soup. In Proc. SIGGRAPH 2004, Los Angeles, USA, Aug. 8-12, 2004, pp.896-904.

[18] Griffiths D J, Inglefield C. Introduction to Electrodynamics. Prentice Hall, 1999.

[19] Li X, Guo X, Wang H, He Y, Gu X, Qin H. Harmonic volumetric mapping for solid modeling applications. In Proc. SPM2007, Beijing, China, June 4-6, 2007, pp.109-120.

[20] Kreyszig E. Advanced Engineering Mathematics. John Wiley, 2005.

[21] Rosell J, Iniguez P. A hierarchical and dynamic method to compute harmonic functions for constrained motion planning. In Proc. IROS 2002, Lausanne, Switzerland, Sept. 30-Oct. 4, 2002, pp.2335-2340.

[22] Grady L. Random walks for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 2006, 28(11): 17681783.

[23] Zhou Q Y, Ju T, Hu S M. Topology repair of solid models using skeletons. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(4): 675-685.

No related articles found!
Full text



No Suggested Reading articles found!

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved