摘要
二维折线集、三角网格和点是几何模型表示中的基本元素,分别被广泛用于二维矢量地图和三维物体模型的表示。如何快速地传输和操作由它们表示的几何模型是实时图形处理的主要任务。本文以几何压缩理论与方法为基础,分别分析了矢量地图和三维几何模型中的拓扑数据和几何数据的特点,首先,提出了基于折线简化和单纯复形的矢量地图多分辨率表示和渐进式传输方法,该方法在保持视觉一致性的条件下,将较小分辨率地图的数据量降低为最大分辨率地图的数据量的1/10,提高了矢量地图渐进传输的效率。其次,提出了基于扇形带的三角网格拓扑关系表示方法,该方法在不考虑顶点分裂与融合的情况下,可以保证连接关系的最低压缩率为log 2 (274)比特/顶点。第三,提出了基于广义三角形带的三角网格数据压缩和多分辨率表示方法,该方法可以充分发挥图形处理器的功能,统一了单分辨率和多分辨率三角网格的表示方法。最后,提出了基于KD-树的点模型各向异性量化方法。对KD-树广度优先的遍历可以构造出多分辨率点模型。该方法可以将点与多边形相结合混合表示几何模型,克服了点模型在表示大平面时效率低的缺点。以上方法有效地提高了图形在存储、传输以及绘制等方面的效率,增强了图形处理的实时性。
The two-dimension polyline set, triangle mesh and point sampled model are primary methods of geometric model representation and are widely employed to represent the vector map and three-dimension geometric model corresponsively. How to transmit and operate these geometric models is the important task of real-time graphics. Basing on the principle and methodologies of geometric compression, we analyzed the properties of the topological and geometric data contained in vector map and proposed new strategies for saving, transmitting and rendering these data as well as triangle mesh and point sampled model. The first strategies presented in this dissertation is the multiresolution representation and progressive transmission of vector map based on polyline simplification and Simplicial Multi-Complex by which the volume of coarser level data can generally be reduced to one tenth of that of the finest level while preserving the visual consistency between them and the progressive transmission of vector map data is speeded up. The second is the fan strip based topological data representation for simple triangle mesh by which the connectivity between vertice can be encoded less than log 2 (274) bit/vertex when the split vertex and merge vertex is ignored. The third is the generalized triangle strip based data compression and multiresolution representation for simple triangle mesh. The single and multi resolution representations have same codec strategies in this method which is appropriate to the architecture of modern graphic process unit in personal computer. At last, KD-tree based anisotropic quantization was developed to reduce the volume of geometric data, i.e. coordinates of point sample, for a 2-manifold point sampled model. The breadth-first traversal of KD-tree was used to construct the multiresolution presentation. In this method, the hybrid point and polygon rendering surmounts the obstacle of large flat surface representation by point sample set. All these strategies increase the efficiency of realtime graphics processing.
引文
[1] M. Pharr and R. Fernando. GPU Gems 2: Programming Techniques for High-Performance Graphics and General Purpose Computation. Boston, MA: Addison Wesley, 2005. 453-508.
[2] U. J. Kapasi, S. Rixner, W. J. Dally, B. Khailany, J. H. Ahn, P. Mattson, and J. D. Owens. Programmable stream processors. IEEE Computer, 2003, 36(8):54-62.
[3] M. Deering. Geometry compression. R. Cook. SIGGRAPH 95 Conference Proceedings. Boston, MA: Addison Wesley, 1995.13-20.
[4] P. V. Oosterom. The Reactive-tree: A Storage Structure for a Seamless Scaleless Geographic Database. Proceedings of Auto-Carto 10, 1991. 393-407.
[5] Edward P.F. Chan and Kevin K.W. Chow. On Multi-Scale Display of Geometric Objects. Data & Knowledge Engineering. 2002, 40(1):91-119.
[6] L. De Floriani, P. Magillo, Multiresolution Meshes, Principles of Multiresolution in Geometric Modeling. PRIMUS01 summer school, 2001. 193-234.
[7] M. Bertolotto and M. Egenhofer. Progressive Transmission of Vector Map Data over the World Wide Web. GeoInformatica. 2001, 5(4):345-373.
[8] M. Bertolotto and M. Egenhofer, Progressive Vector Transmission, Proceedings ACMGIS99, Kansas City, MO: ACM press, 1999. 152-157.
[9] M. Bertolotto. Geometric Modeling of Spatial Entities at Multiple Levels of Resolution. Ph.D. Thesis. Department of Computer and Information Sciences, University of Genova, Italy, 1998.
[10] E. Puppo and G. Dettori. Towards a formal model for multiresolution spatial maps, In 4th International Symposium on Large Spatial Databases. Portland, Maine, USA: Springer. 1995.152–169.
[11] R. Estkowski. No Steiner point subdivision simplification is NP-Complete. In Proc. 10th Canadian Conf. Computational Geometry. Montréal, Québec, CANADA. 1998.
[12] R. Estkowski and J. S. B. Mitchell. Simplifying a Polygonal Subdivision While Keeping it Simple. Proceedings of 17th ACM SCG. Medford, Massachusetts:ACM press. 2001.40-49.
[13] D. H. Douglas and T. K. Peucker. Algorithms for the Reduction of Points Requiredto Represent a Digitized Line or its Caricature. Canadian Cartographer. 1973. 10(2):112-122。
[14] M. de Berg, M. van Kreveld, and S. Schirra. A new approach to subdivision simplification. ACMS/ASPRS Annual Convention and Exposition. 1995. 4(2):79–88.
[15] N. Mustafa, E. Koutsofias, S. Krishnan, and. S. Venkatasubramanian, Hardware assisted view-dependent map simplification, Medford: Manuscript, 2000.
[16] A. Mantler and J. Snoeyink, Safe sets for line simplification, In 10th Annual Fall workshop on Computational Geometry. 2000.
[17] V. Gaede and O. Gunther. Multidimensional Access Methods, ACM Computing Surveys. 1998.30(2):170-231.
[18] A . Hutfesz, H-W. Six and P. Widmayer. The R-File: An Efficient Access Structure for Proximity Queries.Proceedings of IEEE 6th International Conference on Data Engineering. Los Angeles,CA. 1990.372-379.
[19] J. Popovic and H. Hoppe. Progressive simplicial complexes. Computer Graphics Proceedings,Annual Conference Series SIGGRAPH. ACM Press.1997.217-224.
[20] E. Danovaro, L. De Floriani, P. Magillo, and E. Puppo, Representing vertex-based simplicial multi-complexes. G. Bertrand, A. Imiya, and R. Klette. Digital and Image Geometry. Lecture Notes in Computer Science 2243. New York: Springer-Verlag. 2001.128-147.
[21] R. Klein and S. Gumhold. Data compression of multiresolution surfaces. Visualization in Scientific Computing '98. New York: Springer-Verlag. 1998.13~24.
[22] D. P. Huttenlocher, G. A. Klauderman, W. J. Rucklidge. Comparing images using the Hausdorff distance. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1993. 15(9): 850-863.
[23] H. Alt, B. Behrends, and J. Bl?mer. Approximate matching of polygonal shapes. Annals of Mathematics and Artificial Intelligence. 1995. 251–265.
[24] M. Mantyla. An Introduction to Solid Modeling. Rockville,MD: Computer Science Press,1988.
[25] G. Turan. Succinct Representations of Graphs. Discrete Applied Mathematics. 1984.8(1):289-294.
[26] R.C-N. Chuang, A.Garg, X. He, M-Y. Kao and H-I Lu. Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses. In ICALP: Annual International Colloquium on Automata, Languages and Programming,. 1998. 118-129.
[27] J. Li and C.-C. Jay Kuo. Mesh Connectivity Coding by the Dual Graph Approach. Dublin. MPEG98 Contribution Document No. M3530. Ireland. 1998.
[28] Keeler and Westbrook. Short Encodings of Planar Graphs and Maps. Discrete Appl. Math., 1995.58(1):239-252.
[29] E. Arkin, M. Held, J. Mitchell, and S. Skiena. Hamiltonian triangulations for fast rendering. In Second Annual European Symposium on Algorithms, Lecture Notes in Computer Science. New York: Springer-Verlag. 1994. 855:36–47.
[30] E. Arkin, M. Held, J. Mitchell, and S. Skiena. Hamiltonian triangulations for fast rendering. Visual Computer. 1996.2(9):429–444.
[31] W. Tutte. A census of planar triangulations. Canadian Journal of Math. 1962.14:21-38.
[32] Open GL Architecture Review Board. OpenGL Reference Manual. Reading, MA:Addison-Wesley. 1993.
[33] J. Neider, T. Davis and M.Woo. Open GL Architecture Review Board. OpenGL Programming Guide. Reading, MA:Addison-Wesley. 1993.
[34] GL Programming Guide. Silicion Graphics Inc. 1991.
[35] K. Akeley, P. Haeberli and D. Burns. tomesh.c : C Program on SGI Developer’s Toolbox CD,1990.
[36] F. Evans, S. S. Skiena and Amitabh Varshney. Optimizing triangle strips for fast rendering. In IEEE Visualization’96. IEEE press. 1996. 319–326
[37] R. Bar-Yehuda and C. Gotsman. Time/space tradeoffs for polygon mesh rendering. ACM Transactions on Graphics. 1996.15(2):141–152.
[38] S. Gumhold and W. Stra?er. Real time compression of triangle mesh connectivity. Proceedings Siggraph'98. New York: ACM Press.1998.133–140.
[39] G. Taubin and J. Rossignac. Geometric compression through topological surgery. ACM Transactions on Graphics,1998.17(2):84–115.
[40] J. Rossignac, 3D Geometry Compression: Just-in-time upgrades for triangle meshes, in 3D Geometry Compression, Course Notes 21, Siggraph 98, Orlando, Florida,.1998.18-24.
[41] C. Gotsman, S. Gumhold and L. Kobbelt. Simplification and Compression of 3D Meshes. A. Iske, E. Quak, M.S. Floater. Tutorials on Multiresolution in Geometric Modelling, New York: Springer, 2002.
[42] J. Rossignac. Edgebreaker. Compressing the incidence graph of triangle meshes, IEEE Trans. Visualization Computer Graphics. 1999.5(1):47-61.
[43] M.Isenburg and J. Snoeyink. Face Fixer: Compressing polygon meshes withproperties. SIGGRAPH 2000, 263-270.
[44] C. Touma and C. Gotsman. Triangle mesh compression. W. Davis, K. Booth, and A. Fourier. Proceedings of the 24th Conference on Graphics Interface. San Francisco .1998. 26-34.
[45] P. Alliez and M. Desbrun. Valence-driven connectivity encoding for 3D meshes. Computer Graphics Forum. 2001. 20(3):480-489.
[46] S. Gumhold and W. Stra?er. Real time compression of triangle mesh connectivity. Proceedings Siggraph'98, New York: ACM Press. 1998.133-140.
[47] W. Tutte. A Census of Planar Maps. Canadian Journal of Mathematics. 1963. 15:249–271.
[48] D. King and J. Rossignac. Guaranteed 3.67v bit encoding of planar triangle graph. 11th Can. Conf. on Comp. Geom. 1999.146-149.
[49] S. Gumhold. New bounds on the encoding of planar triangulations. Tech. Rep. WSI-2000-1, Univ. of Tübingen, 2000.
[50] A. Szymczak, D. King and J. Rossignac. An EdgeBreaker-based efficient compression scheme for regular meshes. Computational Geometry: Theory and Applications. 2001. 20(1-2):53-68.
[51] A. Khodakovsky, P. Alliez. M. Desbrun and P. Schreuder. Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes. Journal of the Graphical Models. 2002. 64(3-4):147–168.
[52] D. King, J.Rossignac, and A. Szymczak. Connectivity compression for irregular quadrilateral meshes. Tech. Rep. Tr-99-36, GVU, Georgia Tech,1999.
[53] B. Kronrod and C. Gotsman. Efficient coding of non-triangular meshes. Proc. 8-th Pacific Graphics. Hong Kong. 2000.235-242.
[54] R. M. G. Y. Linde and A. Buzo. An algorithm for vector quantization design. IEEE Trans. on Communications. 1980. 28(1):84-95.
[55] A. Gersho and R. Grey. Vector quantization and signal compression. Kluwer, Boston,1992.
[56] E. Lee and H. Ko. Vector data compression for trianglar meshes. Proc. Pacific Graphics. Hong Kong. 2000. 225-234.
[57] R. Balan and G. Taubin, 3D Mesh Geometry Filtering Algorithms for Progressive Transmission Schemes. Computer-Aided Design. 2000.32(13):825-846, Special Issue on Multi-Resolution Geometric Models.
[58] G. Taubin. A signal processing approach to fair surface design. Proceedings of Siggraph’95. 1995.351–358.
[59] Z. Karni, C. Gotsman. Spectral Compression of Mesh Geometry. K. Akeley. Proceedings of SIGGRAPH 2000. New York:ACM Press. 2000. 279-286.
[60] A. Khodakovsky, P. Schroeder and W. Sweldens. Progressive Geometry Compression. Proceedings of SIGGRAPH 2000. New York:ACM Press. 2000. 271-278
[61] H. Hoppe. Progressive meshes. Proceedings of SIGGRAPH ’96. ACM SIG GRAPH. New Orleans,1996.99-108
[62] G. Taubin, A. Gueziec, W.Horn and F.Lazarus. Progressive forest split compression. Proceedings of SIGGRAPH 1998,1998.123-132.
[63] D.Cohen-Or, D. Levin and O. Remez. Progressive compression of arbitrary triangle meshes. IEEE Visualization Conf. Proc. San Francisco,1999.67-72.
[64] O. Devillers and P-M. Gandoin. Geometric Compression for Interactive Transmission. Proc.of the IEEE Conference on Visualization,Salt Lake City,2000.319～326.
[65] P-M. Gandoin and O. Devillers. Progressive Lossless Compression of Arbitrary Simplicial Complexes. ACM Transactions on Graphics. 2002. 21(3):372-379. ACM SIGGRAPH Conference Proceedings.
[66] H. Hoppe. Efficient implementation of progressive meshes. Computers and Graphics. 1998. 22(1): 27-36.
[67] R. Pajarola and J. Rossignac. Compressed Progressive Meshes. IEEE Trans. on Vis. and Comp. Graph. 2000.6(1):79-93.
[68] P. Alliez and M. Desbrun. Progressive Encoding for Lossless Transmission of 3D Meshes. In ACM SIGGRAPH Conference Proceedings. ACM SIGGRAPH. Los Angeles. 2001. 198-205.
[69] J. Rossignac and P. Borrel. Multi-resolution 3D approximation for rendering complex scenes. 2nd Conf. on Geom. Model. In Comp. Graph. Genova, Italy. 1993. 453-465.
[70] J. Peng and C.-C.J. Kuo, Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition. ACM Transactions on Graphics. 2005. 24(3) :609-616.
[71] D. Luebke and C. Erikson. View-dependent simplification of arbitrary polygonal environments. Proceedings of SIGGRAPH ’97. Los Angeles. ACM SIGGRAPH. 1997. 198-208.
[72] H. Hoppe. View-dependent refinement of progressive meshes. Proceedings of SIGGRAPH ’97. Los Angeles. ACM SIGGRAPH. 1997.189–197.
[73] J. Xia, J. El-Sana, and A. Varshney. Adaptive real-time level-of-detail-based rendering for polygonal models. IEEE Transactions on Visualization and Computer Graphics. 1997. 3(2):171–83.
[74] A. Gueziec, F. Lazarus, G. Taubin and W. Horn. Surface partitions for progressive transmission and display, and dynamic simplification of polygonal surfaces. S. N. Spencer.Proceedings VRML 98: third Symposium on the Virtual Reality Modeling Language. Monterey, California. 1998. 25–32.
[75] L. De Floriani, P. Magillo, and E. Puppo. Efficient implementation of multi-triangulation. H. Rushmeier D. Elbert and H. Hagen. Proceedings Visualization ’98. 1998. 43–50.
[76] J. El-Sana, F. Evans, A. Kalaiah, A. Varshney, S. Skiena, E. Azanli. Efficiently computing and updating triangle strips for real-time rendering. Computer-Aided Design. 2000.32(13): 753-772.
[77] M. Segal and K. Akeley. The OpenGL Graphics System: A Specification, Silicon Graphics, Inc., 2004.
[78] M. Duchaineau, M.Wolinsky, D. Sigeti,M. Miller and C. Aldrich and M. Mineev-Weinstein. Roamingterrain: Real-time optimally adapting meshes. In Proceedings of the IEEE Visualization ’97. ACM/SIGGRAPH Press. 1997. 81– 88.
[79] Levoy M, Whitted T. The use of points as a display primitive. Technical Report TR 85-022, University of North Carolina at Chapel Hill, 1985.
[80] J.P. Grossman and William J. Dally. Point sample rendering. In Proceedings Eurographics Rendering Workshop 98. Eurographics. 1998. 181–192.
[81] M. S. Floater and M. Reimers. Meshless parameterization and surface reconstruction. Comput. Aided Geom. Des. 2001.18(2):77–92.
[82] L. Linsen. Point Cloud Representation. Tech. rep., Faculty of Computer Science, University of Karlsruhe, 2001.
[83] M. Sainz, R. Pajarola, A. Susin and A. Mercade. SPOC: Simple point-based object capturing. IEEE Computer Graphics & Applications. 2004. 24 (4):24-33.
[84] M.Zwicker, M. Pauly, O. Knoll, M. Gross. Pointshop 3d: an interactive system for point-based surface editing. Proceedings of the 29th annual conference on Computer graphics and interactive techniques. ACM Press. 2002.322–329.
[85] Mark Pauly, Richard Keiser, Leif Kobbelt, and Markus Gross. Shape modeling with point-sampled geometry.In Proceedings ACM SIGGRAPH 2003. ACM Press. 2003. 641–650.
[86] Mark Pauly, Markus Gross, and Leif P. Kobbelt. Efficient simplification ofpoint-sampled surfaces. Proceedings IEEE Visualization 2002, Computer Society Press, 2002.163–170.
[87] Mark Pauly and Markus Gross. Spectral processing of point-sampled geometry. In Proceedings ACM SIGGRAPH 2001. ACM Press, 2001.379–386.
[88] J. Niloy Mitra and An Nguyen. Estimating surface normals in noisy point cloud data. Symposium on Computational Geometry, ACM, 2003.322–328.
[89] Baoquan Chen and Minh Xuan Nguyen. POP: A hybrid point and polygon rendering system for large data. Proceedings IEEE Visualization’01. 2001.45–52.
[90] Liviu Coconu and Hans-Christian Hege. Hardware-oriented point-based rendering of complex scenes. In Proceedings Eurographics Workshop on Rendering. 2002. 43–52.
[91] Jonathan D. Cohen, Daniel G. Aliaga, and Weiqiang Zhang. Hybrid simplification: Combining multi-resolution polygon and point rendering. In Proceedings IEEE Visualization’01. Computer Society Press. 2001.37–44.
[92] Tamal K. Dey and James Hudson. PMR: Point to mesh rendering, a feature-based approach. In Proceedings IEEE Visualization’02. Computer Society Press. 2002.155–162. 2002.
[93] Szymon Rusinkiewicz and Marc Levoy. Qsplat: A multiresolution point rendering system for large meshes. In Proceedings SIGGRAPH 2000. ACM SIGGRAPH. 2000.343–352.
[94] Mario Botsch, Andreas Wiratanaya, and Leif Kobbelt.Efficient high quality rendering of point sampled geometry. In Proceedings Eurographics Workshop on Rendering. 2002.53–64.
[95] Liu Ren, Hanspeter Pfister, and Matthias Zwicker. Object space EWA surface splatting: A hardware accelerated approach to high quality point rendering. Computer Graphics Forum. 2002. 21(3): 461-470. Proceedings EUROGRAPHICS 2002.
[96] Mario Botsch and Leif Kobbelt. High-quality point-based rendering on modern GPUs. In Proceedings Pacific Graphics 2003, IEEE, Computer Society Press. 2003. 335–343.
[97] Renato Pajarola, Miguel Sainz, and Yu Meng. DMesh:Fast depth-image meshing and warping. International Journal of Image and Graphics. 2004. 4(4):1-29 .
[98] Carsten Dachsbacher, Christian Vogelgsang, and Marc Stamminger. Sequential point trees. In Proceedings ACM SIGGRAPH 03. ACM Press. 2003. 657–662.
[99] Hanspeter Pfister, Matthias Zwicker, Jeroen van Baar, and Markus Gross. Surfels:Surface elements as rendering primitives. In Proceedings SIGGRAPH 2000. ACM SIGGRAPH, 2000.335–342.
[100] Matthias Zwicker, Hanspeter Pfister, Jeroen van Baar, and Markus Gross. Surface splatting. In Proceedings SIGGRAPH 2001. ACM SIGGRAPH. 2001. 371–378.
[101] Aravind Kalaiah and Amitabh Varshney. Differential point rendering. Proceedings of the 12th Eurographics Workshop on Rendering. London, UK. 2001. 139-150.
[102] Aravind Kalaiah and Amitabh Varshney. Modeling and rendering points with local geometry. IEEE Transactions on Visualization and Computer Graphics,. 2003. 9(1):30–42.
[103] Renato Pajarola. Efficient level-of-details for point based rendering. In Proceedings IASTED Invernational Conference on Computer Graphics and Imaging (CGIM 2003), 2003.
[104] Renato Pajarola, Miguel Sainz, and Patrick Guidotti. Object-space point blending and splatting. In ACM SIGGRAPH Sketches & Applications Catalogue, 2003.
[105] Renato Pajarola, Miguel Sainz, and Patrick Guidotti. Confetti: Object-space point blending and splatting. IEEE Transactions on Visualization and Computer Graphics. 2004. 10(5): 598-60.
[106] 周培德. 计算几何——算法分析与设计.北京:清华大学出版社. 2000.
[107] Wenland H. Piecewise polynomial, positive definite and compactly supported radial basis functions of minimal degree. Advances in Computational Mathematics. 1995. 4 (10): 389–396.
[108] P. Lancaster, K. Alkauskas. Surfaces generated by moving least squares methods. Mathematics of Computation. 1981. 37 (155): 141–158.
[109] D. Levin. The approximation power of moving least-squares. Math. Comp. 1998. 67 (224): 1517–1531.
[110] R. Franke, G. Nielson. Smooth interpolation of large sets of scattered data. InternationalJournal of Numerical Methods in Engineering.1980.15(2), 1691–1704.
[111] D. Shepard. A two dimensional interpolation function for irregular spaced data.In Proceedings of 23rd ACM National Conference. Washington DC. 1968. 517–524.
[112] I. Jolliffe. Principal Component Analysis. Springer Verlag, 1986.
[113] H. Hoppe, T. DeRose, T. Duchamp. Halstead M., Jin H., McDonald J.,Schweitzer J., Stuetzle W. Piecewise smooth surface reconstruction. Computer Graphics Annual Conferences Series. ACM SIGGRAPH. Orlando,Florida. 1994.295-302.
[114] M. Garland. Quadric-Based Polygonal Surface Simplification. PhD thesis, Computer Science Department, Carnegie Mellon University, 1999.
[115] J. Rossignac, P. Borrel. Multi-resolution 3d approximations for rendering complex scenes. Proceedings of Modeling in Computer Graphics: Methods and Applications. Berlin. 1993. 455～465
[116] E. Shaffer, M. Garland. Efficient adaptive simplification of massive meshes. In Proceedings of the conference on Visualization’01. IEEE Computer Society. 2001.127–134.
[117] R. Sedgewick. Algorithms in C++ (3rd edition). Boston, MA:Addison Wesley, 1998.
[118] D. Brodsky, B. Watson. Model simplification through refinement. In Graphics Interface. Montreal, Canada. 2000. 221–228.
[119] P. Davis. Interpolation and Approximation. Dover Publications.1975.
[120] D. Saupe, J. Kuska, Compression of iso-surfaces, IEEE Proc.Vision, Modeling, and Visualization. 2001. 333 – 340.
[121] J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM. 1975.18( 9): 509–517.
[122] J. H. Freidman, J. L. Bentley, R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw. 1977.3(3): 209-226.
[123] R. L. Sproull. Refinements of nearest neighbor searching in k-dimensional trees. J. Algorithmica.1991. 6 (4):579-589.
[124] S. Arya, H.-Y. A Fu. Expected-case complexity of approximate nearest neighbor searching. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics. 2000.379–388.
[125] H. Samet: The Design and Analysis of Spatial Data Structures. Boston, MA:Addison-Wesley, 1990.
[126] A.G. Requicha and H.B.Voelcker. Boolean Operations in Solid Modeling: Boundary Evaluation and Merging Algorithms, In Proceedings of IEEE. 198573(1):30–44.
[127] C. M. Hoffmann. Geometric and Solid Modeling: An Introduction. MorganKaufmann, 1989.
[128] Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, H. Seidel. Multi-level Partition of Unity Implicits, In Proceedings of Siggraph 2003. ACM SIGGRAPH. 2003.463-470.
[129] B.Adams and P.Dutre. Interactive boolean operations on surfel bounded solids. Proc. of ACM SIGGRAPH 03. ACM SIGGRAPH.. 2003. 651–656.
[130] A.Barr. Global and Local Deformations of Solid Primitives . ACM SIGGRAPH Computer Graphics, Proceedings of ACM SIGGRAPH 84. 1984.18(3):21-30.
[131] T. W. Sederberg and S. R. Parry. Free-Form Deformation of Solid Geometric Models. Computer Graphics. Proceedings of ACM SIGGRAPH 86.1986.20(4):151-160.
[132] 詹海生,李广新,马志欣. 基于 ACIS 的几何造型技术与系统开发.北京:清华大学出版社.2002.
[133] M. Müller, R. Keiser, A.Nealen, M. Pauly, M. Gross,and M. Alexa. Point based animation of elastic, plastic and melting objects. Proceedings of 2004 ACM SIGGRAPH Symposium on Computer Animation.2004.141-151.
[134] M. Pauly, R. Keiser, B. Adams, P. Dutré, M.H. Gross, L.J.Guibas. Meshless animation of fracturing solids. ACM Trans. Graph., 2005.24(3):957-964.
[135] D. Terzopoulos and K. Fleischer. Modeling inelastic deformation: viscolelasticity, plasticity, fracture. In Proceedings of the 15th annual conference on Computer graphics and interactive techniques. New York: ACM Press. 1988.269-278.
[136] D. Terzopoulos, J. Platt, A.Barr and K.Fleischer. Elastically deformable models. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH 87. New York: ACM Press. 1987.205-214.
[137] M. Carlson, P. Mucha, B. Van horn III and G. Turk. Melting and flowing. Proceedings of the 2002 ACM SIGGRAPH Symposium on Computer Animation. New York: ACM Press. 2002.167-174.
[138] D. Q.Nguyen, R. Fedkiw, and H. W. Jensen. Physically based modeling and animation of fire. ACM Transactions on Graphics.2002. 21(3): 721-728.
[139] R. Fedkiw,J. Stam and H.W. Jensen. Visual simulation of smoke. Proc. of the SIGGRAPH. New York: ACM Press. 2001. 15-22
[140] B. E. Feldman, J. F. O'Brien, and O.Arikan. Animating suspended particle explosions. In Proceedings of ACM SIGGRAPH 2003. New York: ACM Press. 2001.708-715.
[141] N.Sukumar, N.Mos, B.Moran, and T.Belytschko. Extended finite element method for three-dimensional crack modeling. International Journal for Numerical Methods in Engineering. 2000.48(11):1549-1570.
[142] T. Belytschko, H.Chen, J.Xu, and G. Zi. Dynamic crack propagation based on loss of hyperbolicity and a new discontinuous enrichment. Int. J. Numer. Meth. Engng. 2003. 58(12):1873-1905.
[143] 刘新国.三维几何压缩:[博士学位论文].杭州:浙江大学 CAD&CD 国家重点实验室,2001.
