实体建模技术研究进展
Research Progress of Solid Modeling Technology
DOI: 10.12677/CSA.2021.114112, PDF,   
作者: 段忠祥, 杨 钦：北京航空航天大学计算机学院，北京
关键词: 实体建模；计算机图形；隐式几何建模；Solid Modeling； Computer Graphics； Implicit Geometric Modeling
摘要: 实体建模技术是当今科学和工程计算相关领域的重要研究内容。通过实体建模方法对物体外形进行恰当的描述，从而确定给定的计算区域，是科学与工程数值模拟计算的前提。此外，实体建模技术也是计算机图形学，计算机动画，科学计算可视化等领域相关应用实现的基础。本文系统回顾了当前各类主流实体建模方法，其后重点对隐式几何建模技术相关的理论和方法进行了阐述，分析了实体建模领域现在存在的问题和技术局限性，对未来该领域的发展趋势进行了展望。
Abstract: Solid modeling technology is an important research topic in the field of science and engineering computing. It is the premise of scientific and engineering numerical simulation to describe the shape of the object appropriately by solid modeling method, so as to determine the computational domain. In addition, solid modeling is also the foundation of applications in the fields such as computer graphics, computer animation and visualization in scientific computing. This paper reviews various current mainstream solid modeling methods, and focuses on the theories and approaches of implicit geometric modeling. We also analyze the existing problems and technical limitations of current solid modeling methodologies, and give the research prospect of this field.
文章引用：段忠祥, 杨钦. 实体建模技术研究进展[J]. 计算机科学与应用, 2021, 11(4): 1089-1097. https://doi.org/10.12677/CSA.2021.114112

参考文献

[1] Jamin, C., Alliez, P., Yvinec, M. and Boissonnat, J.-D. (2015) CGALmesh: A Generic Framework for Delaunay Mesh Generation. ACM Transactions on Mathematical Software, 41, 1-24. [Google Scholar] [CrossRef] 
[2] Guo, J., Ding, F., Jia, X. and Yan, D.-M. (2019) Automatic and High-Quality Surface Mesh Generation for CAD Models. Computer-Aided Design, 109, 49-59. [Google Scholar] [CrossRef] 
[3] Sabin, M. (1968) The Use of Potential Surfaces for Numerical Geometry. British Aircraft Corporation, Weybridge.
[4] Ricci, A. (1973) A Construc-tive Geometry for Computer Graphics. The Computer Journal, 16, 157-160. [Google Scholar] [CrossRef] 
[5] Jamriška, O. (2010) Interactive Ray Tracing of Distance Fields. The 14th Central European Seminar on Computer Graphics, Budmerice, 10-12 May 2010, 1-7.
[6] Bloomenthal, J., Bajaj, C., Blinn, J., Cani, M.-P., Rockwood, A., Wyvill, B., et al. (1997) Introduction to Implicit Surfaces. Morgan Kaufmann, Burlington.
[7] Kazhdan, M., Bolitho, M. and Hoppe, H. (2006) Poisson Surface Reconstruction. Proceedings of the 4th Eurographics Symposium on Geometry Processing, Sardinia, 26-28 June 2006, 61-70.
[8] Pan, M., Tong, W. and Chen, F. (2016) Compact Implicit Surface Reconstruction via Low-Rank Tensor Approximation. Computer-Aided De-sign, 78, 158-167. [Google Scholar] [CrossRef] 
[9] Pasko, A., Adzhiev, V., Sourin, A. and Savchenko, V. (1995) Function Representation in Geometric Modeling: Concepts, Implementation and Applications. The Visual Computer, 11, 429-446. [Google Scholar] [CrossRef] 
[10] Cani-Gascuel, M. and Desbrun, M. (1997) Animation of Deformable Models using Implicit Surfaces. IEEE Transactions on Visualization and Computer Graphics, 3, 39-50. [Google Scholar] [CrossRef] 
[11] Wyvill, B., Guy, A. and Galin, E. (1999) Extending the CSG Tree. Warping, Blending and Boolean Operations in an Implicit Surface Modeling System. Computer Graphics Forum, 18, 149-158. [Google Scholar] [CrossRef] 
[12] McInemey, T. and Terzopoulos, D. (1999) Topology Adaptive Deformable Surfaces for Medical Image Volume Segmentation. IEEE Transactions on Medical Im-aging, 18, 840-850. [Google Scholar] [CrossRef] [PubMed]
[13] Shapiro, V. (2002) Solid Modeling. In: Farin, G., Hoschek, J. and Kim, M.-S., Eds., Handbook of Computer Aided Geometric Design, North Holland, Amsterdam, 473-518. [Google Scholar] [CrossRef] 
[14] Stroud, I. (2006) Boundary Representation Modelling Techniques. Springer-Verlag, London.
[15] Baumgart, B.G. (1974) Geometric Modelling for Computer Vi-sion. Stanford University, Suburban.
[16] Weiler, K. (1985) Edge-Based Data Structures for Solid Modeling in Curved-Surface Environments. IEEE Computer Graphics and Applications, 5, 21-40. [Google Scholar] [CrossRef] 
[17] Goldman, R. (2009) An Integrated Introduction to Computer Graphics and Geometric Modeling. CRC Press, Boca Raton. [Google Scholar] [CrossRef] 
[18] Foley, J.D. (1996) 12.7 Constructive Solid Geometry. In: Foley, J.D., van Dam, A., Feiner, S.K., Hughes, J., McGuire, M., Sklar, D.F. and Akeley, K., Eds., Computer Graphics: Principles and Practice, Addison-Wesley Professional, Boston, 557-558.
[19] Wikipedia (2019) Constructive Solid Geometry.
https://en.wikipedia.org/wiki/Constructive_solid_geometry
[20] Kuchkuda, R. (1988) An Introduction to Ray Tracing. In: Earnshaw, R.A., Theoretical Foundations of Computer Graphics and CAD, Springer, Berlin, Heidelberg, 1039-1060. [Google Scholar] [CrossRef] 
[21] Yamaguchi, K., Kunii, T., Fujimura, K. and Tori-ya, H. (1984) Octree-Related Data Structures and Algorithms. IEEE Computer Graphics and Applications, 4, 53-59. [Google Scholar] [CrossRef] 
[22] Foley, J.D., Van Dam, A., Feiner, S.K., Hughes, J. and McGuire, M. (1996) Computer Graphics: Principles and Practice. Addison-Wesley Professional, Boston.
[23] Rao, S.S. (2018) The Finite Element Method in Engineering. 6th Edition, Elsevier, Amsterdam.
[24] Cheng, S., Dey, T.K. and Levine, J.A. (2008) A Practical Delaunay Meshing Algorithm for a Large Class of Domains. In: Brewer, M.L. and Marcum, D., Eds., Proceedings of the 16th International Meshing Roundtable, Springer, Berlin, Heidelberg, 477-494. [Google Scholar] [CrossRef] 
[25] Löhner, R. (2014) Recent Advances in Parallel Advancing Front Grid Generation. Archives of Computational Methods in Engineering, 21, 127-140. [Google Scholar] [CrossRef] 
[26] De Araújo, B.R., Lopes, D.S., Jepp, P., Jorge, J.A. and Wyvill, B. (2015) A Survey on Implicit Surface Polygonization. ACM Computing Surveys (CSUR), 47, Article No. 60. [Google Scholar] [CrossRef] 
[27] Barthe, L., Mora, B., Dodgson, N. and Sabin, M. (2002) Interactive Implicit Modelling Based on C1 Continuous Reconstruction of Regular Grids. International Journal of Shape Modeling, 8, 99-117. [Google Scholar] [CrossRef] 
[28] Reiner, T., Mückl, G. and Dachsbacher, C. (2011) Interactive Modeling of Implicit Surfaces Using a Direct Visualization Approach with Signed Distance Functions. Computers & Graphics, 35, 596-603. [Google Scholar] [CrossRef] 
[29] Barbier, A., Galin, E. and Akkouche, S. (2005) A Framework for Modeling, Animating, and Morphing Textured Implicit Models. Graphical Models, 67, 166-188. [Google Scholar] [CrossRef] 
[30] Rigaudière, D., Gesquière, G. and Faudot, D. (2000) Shape Modelling with Skeleton Based Implicit Primitives. International Conference Graphicon 2000, Moscow, 174-178.
[31] Blinn, J.F. (1982) A Generalization of Algebraic Surface Drawing. ACM Transactions on Graphics, 1, 235-256. [Google Scholar] [CrossRef] 
[32] Wyvill, G., McPheeters, C. and Wyvill, B. (1986) Data Structure for Soft Objects. The Visual Computer, 2, 227-234. [Google Scholar] [CrossRef] 
[33] Nishimura, H. (1985) Object Modeling by Distribution Function and a Method of Image Generation. Transactions on Electrical and Electronic Engineering, 68, 718-725.
[34] Muraki, S. (1991) Volumetric Shape Description of Range Data Using “Blobby Model”. ACM SIGGRAPH Computer Graphics, 25, 227-235. [Google Scholar] [CrossRef] 
[35] Bloomenthal, J. and Shoemake, K. (1991) Convolution Surfaces. ACM SIGGRAPH Computer Graphics, 25, 251-256. [Google Scholar] [CrossRef] 
[36] Turk, G. and O’Brien, J.F. (1999) Shape Transformation Using Vari-ational Implicit Functions. Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Tech-niques, Los Angeles, 8-13 August 1999, 335-342. [Google Scholar] [CrossRef] 
[37] Carr, J.C., Beatson, R.K., Cherrie, J.B., Mitchell, T.J., Fright, W.R., McCallum, B.C., et al. (2001) Reconstruction and Representation of 3D Objects with Radial Basis Functions. Proceed-ings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, Los Angeles, 12-17 August 2001, 67-76. [Google Scholar] [CrossRef] 
[38] Morse, B.S., Yoo, T.S., Rheingans, P., Chen, D.T. and Subramanian, K.R. (2001) Interpolating Implicit Surfaces from Scattered Surface Data Using Compactly Supported Ra-dial Basis Functions. Proceedings of the International Conference on Shape Modeling and Application, Genova, 7-11 May 2001, 89-98. [Google Scholar] [CrossRef] 
[39] Tobor, I., Reuter, P. and Schlick, C. (2006) Reconstructing Multi-Scale Variational Partition of Unity Implicit Surfaces with Attributes. Graphical Models, 68, 25-41. [Google Scholar] [CrossRef] 
[40] Berger, M., Tagliasacchi, A., Seversky, L., Alliez, P., Levine, J.A., Sharf, A., et al. (2014) State of the Art in Surface Reconstruction from Point Clouds. 35th Eurographics 2014: Strasbourg, France-State of the Art Reports, Strasbourg, 7-11 April 2014, 161-185.
[41] Allègre, R., Galin, E., Chaine, R. and Akkouche, S. (2006) The HybridTree: Mixing Skeletal Implicit Surfaces, Triangle Meshes, and Point Sets in a Free-Form Modeling System. Graphical Models, 68, 42-64. [Google Scholar] [CrossRef] 
[42] Shapiro, V. and Tsukanov, I. (1999) Implicit Functions with Guaranteed Differential Properties. Proceedings of the 5th ACM Symposium on Solid Modeling and Applications, Ann Arbor, June 1999, 258-269. [Google Scholar] [CrossRef] 
[43] Gourmel, O., Barthe, L., Cani, M., Wyvill, B., Bernhardt, A., Paulin, M., et al. (2013) A Gradient-Based Implicit Blend. ACM Transactions on Graphics, 32, Article No. 12. [Google Scholar] [CrossRef] 
[44] Osher, S. and Sethian, J.A. (1988) Fronts Propagating with Cur-vature-Dependent Speed: Algorithms Based on Hamilton-Jacobi Formulations. Journal of Computational Physics, 79, 12-49. [Google Scholar] [CrossRef] 
[45] Adalsteinsson, D. and Sethian, J.A. (1995) A Fast Level Set Method for Propagating Interfaces. Journal of Computational Physics, 118, 269-277. [Google Scholar] [CrossRef] 
[46] Losasso, F., Gibou, F. and Fedkiw, R. (2004) Simulating Water and Smoke with an Octree Data Structure. SIGGRAPH04: Special Interest Group on Computer Graphics and Interactive Techniques, Los Angeles, August 2004, 457-462. [Google Scholar] [CrossRef] 
[47] Museth, K. (2013) VDB: High-Resolution Sparse Volumes with Dynamic Topology. ACM Transactions on Graphics, 32, Article No. 27. [Google Scholar] [CrossRef] 
[48] Nielsen, M.B. and Museth, K. (2006) Dynamic Tubular Grid: An Efficient Data Structure and Algorithms for High Resolution Level Sets. Journal of Scientific Computing, 26, 261-299. [Google Scholar] [CrossRef] 
[49] Houston, B., Wiebe, M. and Batty, C. (2004) RLE Sparse Level Sets. SIGGRAPH’04, Los Angeles, August 2004, 137. [Google Scholar] [CrossRef] 
[50] Houston, B., Nielsen, M.B., Batty, C., Nilsson, O. and Museth, K. (2006) Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation. ACM Transactions on Graphics, 25, 151-175. [Google Scholar] [CrossRef] 
[51] Setaluri, R., Aanjaneya, M., Bauer, S. and Sifakis, E. (2014) SPGrid: A Sparse Paged Grid Structure Applied to Adaptive Smoke Simulation. ACM Transactions on Graphics, 33, Article No. 205. [Google Scholar] [CrossRef] 
[52] Losasso, F., Shinar, T., Selle, A. and Fedkiw, R. (2006) Multiple Interacting Liquids. ACM Transactions on Graphics, 25, 812-819. [Google Scholar] [CrossRef] 
[53] Heo, N. and Ko, H. (2010) Detail-Preserving Fully-Eulerian Inter-face Tracking Framework. ACM Transactions on Graphics, 29, Article No. 176. [Google Scholar] [CrossRef] 
[54] Mitchell, N., Aanjaneya, M., Setaluri, R. and Sifakis, E. (2015) Non-Manifold Level Sets: A Multivalued Implicit Surface Representation with Applications to Self-Collision Processing. ACM Transactions on Graphics, 34, Article No. 247. [Google Scholar] [CrossRef] 
[55] Dan, K., Deul, C. and Bender, J. (2016) Hierarchical Hp-Adaptive Signed Distance Fields. Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Zurich, July 2016, 189-198.
[56] Dan, K., Deul, C., Brand, M. and Bender, J. (2017) An Hp-Adaptive Discretization Algorithm for Signed Distance Field Generation. IEEE Transactions on Visualization and Computer Graphics, 23, 2208-2221. [Google Scholar] [CrossRef]