基于自适应延迟切割的三角网格布尔运算优化
|
摘要
规则化的布尔运算被广泛应用在三维建模系统中.近年来,随着图形硬件的发展,基于三角网格的规则化布尔算法由于输出结果能直接被图形硬件处理,表现出了明显的优势.但是传统的算法由于采用CSG树局部评估策略,使得面片在相交测试中反复被切割,并且由于面片分类在切割后的模型之间直接进行,导致算法无法在保证鲁棒性的同时实现高性能.为了避免这些问题,提出了一种CSG树全局评估算法来统一执行单次和连续布尔运算.算法由两部分组成:自适应的延迟切割和全局化面片分类.在自适应的延迟切割阶段,算法通过仔细处理多个三角面片相交导致的各种情况扩展延迟切割到整个CSG树来避免由于面片的反复切割带来的数值误差累积,并利用自适应的八叉树使得相交测试可在线性时间内完成.在全局化面片分类阶段,算法通过分治法使得分类始终在切割后的面片和原始输入模型之间进行来保证分类的精度;通过结合组分类策略和自适应的八叉树来进一步优化分类性能.实验结果表明,所提算法无论是在执行单次还是在连续布尔运算时,都能在保证鲁棒性的同时性能优于其他算法,因此该算法可广泛应用于交互式建模系统中,如数字雕刻、计算机辅助设计和制造(CAD/CAM)等.
Regularized Boolean operations have been widely used in 3D modeling systems. In recent years, Boolean algorithms based on triangular polyhedron show the distinct advantages aligning with the development of graphic hardware, as their outputs can be processed by graphic hardware directly. But most existing methods rely on localized evaluation strategy over constructive solid geometry(CSG) tree perform regularized set operations. As a result, these methods cannot guarantee robustness while synchronously keeping high efficiency, because a facet may repeatedly split up in the splitting phase and the facets classification is carried out between the split polyhedrons by triangulation. In this paper, a novel algorithm is presented to realize robust, exact and fast regularized Boolean operations through global evaluation of CSG tree. The algorithm is comprised of two steps: adaptive lazy splitting and globalized facets classification. The two steps aim to optimize splitting and facets classification phases of the regularized Boolean algorithms on triangulated polyhedrons respectively. In the adaptive lazy splitting phase, a lazy splitting strategy is applied to the whole CSG tree by coping with all intersection cases of triangular facets in order to eliminate the accumulation of number errors. In the meantime, an adaptive octree is employed to speed up the intersection test process. In the globalized facets classification phase, to ensure the accuracy of classification, the classification method is always executed between the split facet and the original input polyhedrons by divide and conquer algorithm. The performance of classification is further optimized by combining the grouping classification strategy and the octree. Experimental results demonstrate that the proposed approach cannot only guarantee the robustness of Boolean computations but also achieve better performance than existing approaches. Thus, the algorithm offers wide-ranging usage in for interactive modeling systems, such as digital sculpture, and CAD/CAM.
Regularized Boolean operations have been widely used in 3D modeling systems. In recent years, Boolean algorithms based on triangular polyhedron show the distinct advantages aligning with the development of graphic hardware, as their outputs can be processed by graphic hardware directly. But most existing methods rely on localized evaluation strategy over constructive solid geometry(CSG) tree perform regularized set operations. As a result, these methods cannot guarantee robustness while synchronously keeping high efficiency, because a facet may repeatedly split up in the splitting phase and the facets classification is carried out between the split polyhedrons by triangulation. In this paper, a novel algorithm is presented to realize robust, exact and fast regularized Boolean operations through global evaluation of CSG tree. The algorithm is comprised of two steps: adaptive lazy splitting and globalized facets classification. The two steps aim to optimize splitting and facets classification phases of the regularized Boolean algorithms on triangulated polyhedrons respectively. In the adaptive lazy splitting phase, a lazy splitting strategy is applied to the whole CSG tree by coping with all intersection cases of triangular facets in order to eliminate the accumulation of number errors. In the meantime, an adaptive octree is employed to speed up the intersection test process. In the globalized facets classification phase, to ensure the accuracy of classification, the classification method is always executed between the split facet and the original input polyhedrons by divide and conquer algorithm. The performance of classification is further optimized by combining the grouping classification strategy and the octree. Experimental results demonstrate that the proposed approach cannot only guarantee the robustness of Boolean computations but also achieve better performance than existing approaches. Thus, the algorithm offers wide-ranging usage in for interactive modeling systems, such as digital sculpture, and CAD/CAM.
引文
[1]Ertl T.Computer Graphics—Principles and Practice.Springer-Verlag,1996.[doi:10.1007/978-3-7091-2684-4_31]
[2]Requicha A.Mathematical models of rigid solid objects.Technical Memorandum 28,University of Rochester,1977.
[3]Benouamer M,Michelucci D,Peroche B.Error-Free boundary evaluation using lazy rational arithmetic:A detailed implementation.In:Proc.of the 2nd ACM Symp.on Solid Modeling and Applications.ACM,1993.[doi:10.1145/164360.164403]
[4]CGAL.Computational Geometry,2014.http://www.cgal.org
[5]Autodesk.Maya,2014.http://www.autodesk.com
[6]Bernstein G,Fussell D.Fast,exact,linear Booleans.Computer Graphics Forum,2009,28(5):1269–1278.[doi:10.1111/j.1467-8659.2009.01504.x]
[7]Campen M,Kobbelt L.Exact and robust(self-)intersections for polygonal meshes.Computer Graphics Forum,2010,29(2):397–406.[doi:10.1111/j.1467-8659.2009.01609.x]
[8]Hoffmann CM.Geometric and Solid Modeling.Palo Alto:Morgan Kaufmann Publishers,1989.
[9]Feito FR,Ogáyar CJ,Segura RJ,Rivero M.Fast and accurate evaluation of regularized Boolean operations on triangulated solids.Computer-Aided Design,2013,40(3):705–716.[doi:10.1016/j.cad.2012.11.004]
[10]Frisken SF,Perry RN,Rockwood AP,Jones TR.Adaptively sampled distance fields:A general representation of shape for computer graphics.In:Proc.of the 27th Annual Conf.on Computer Graphics and Interactive Techniques.2000.[doi:10.1145/344779.344899]
[11]Museth K,Breen DE,Whitaker RT,Barr AH.Level set surface editing operators.ACM Trans.on Graphics(TOG),2002,21(3):330–338.[doi:10.1145/566654.566585]
[12]Kobbelt LP,Botsch M,Schwanecke U,Seidel HP.Feature sensitive surface extraction from volume data.In:Proc.of the 28th Annual Conf.on Computer Graphics and Interactive Techniques.2001.[doi:10.1145/383259.383265]
[13]Ju T,Losasso F,Schaefer S,Warren J.Dual contouring of hermite data.ACM Trans.on Graphics(TOG),2002,21(3):339–346.[doi:10.1145/566654.566586]
[14]Varadhan G,Krishnan S,Kim YJ,Manocha D.Feature-Sensitive subdivision and isosurface reconstruction.In:Proc.of the Visualization.IEEE,2003.99–106.[doi:10.1109/VISUAL.2003.1250360]
[15]Varadhan G,Krishnan S,Sriram TVN,Manocha D.Topology preserving surface extraction using adaptive subdivision.In:Proc.of the 2004 Eurographics/ACM SIGGRAPH Symp.on Geometry Processing.2004.235–244.[doi:10.1145/1057432.1057464]
[16]Zhang N,Hong W,Kaufman A.Dual contouring with topology-preserving simplification using enhanced cell representation.In:Proc.of the Visualization.IEEE,2004.505–512.[doi:10.1109/VISUAL.2004.27]
[17]Schaefer S,Ju T,Warren J.Manifold dual contouring.IEEE Trans.on Visualization and Computer Graphics,2007,13(3):610–619.[doi:10.1109/TVCG.2007.1012]
[18]Smith JM,Dodgson NA.A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic.Computer-Aided Design,2007,39(2):149–163.[doi:10.1016/j.cad.2006.11.003]
[19]Edelsbrunner H,Mücke EP.Simulation of simplicity:A technique to cope with degenerate cases in geometric algorithms.ACM Trans.on Graphics(TOG),1990,9(1):66–104.[doi:10.1145/77635.77639]
[20]Wang CC.Approximate Boolean operations on large polyhedral solids with partial mesh reconstruction.IEEE Trans.on Visualization and Computer Graphics,2011,17(6):836–849.[doi:10.1109/TVCG.2010.106]
[21]Shade J,Gortler S,He LW,Szeliski R.Layered depth images.In:Proc.of the 25th Annual Conf.on Computer Graphics and Interactive Techniques.1998.[doi:10.1145/280814.280882]
[22]Thibault WC,Naylor BF.Set operations on polyhedra using binary space partitioning trees.ACM SIGGRAPH Computer Graphics,1987,21(4):153–162.[doi:10.1145/37402.37421]
[23]Naylor B,Amanatides J,Thibault W.Merging BSP trees yields polyhedral set operations.ACM SIGGRAPH Computer Graphics,1990,24(4).[doi:10.1145/97880.97892]
[24]Thibault WC.Application of binary space partitioning trees to geometric modeling and ray-tracing[Ph.D.Thesis].Georgia Institute of Technology,1987.
[25]Shewchuk JR.Adaptive precision floating-point arithmetic and fast robust geometric predicates.Discrete&Computational Geometry,1997,18(3):305–363.[doi:10.1007/PL00009321]
[26]Murali TM,Funkhouser TA.Consistent solid and boundary representations from arbitrary polygonal data.In:Proc.of the 1997Symp.on Interactive 3D Graphics.ACM,1997.[doi:10.1145/253284.253326]
[27]Hubbard PM.Constructive solid geometry for triangulated polyhedral[Ph.D.Thesis].Department of Computer Science,Brown University,1990.
[28]Yamaguchi F,Tokieda T.A unified algorithm for Boolean shape operations.Computer Graphics and Applications,1987,4(6):24–37.[doi:10.1109/MCG.1984.275959]
[29]Pilz M,Kamel HA.Creation and boundary evaluation of CSG-models.Engineering with Computers,1987,5(2):105?118.[doi:10.1007/BF01199073]
[30]M?ntyl?M,Tamminen M.Localized set operations for solid modeling.ACM SIGGRAPH Computer Graphics,1983,17(3):279–288.[doi:10.1145/964967.801159]
[31]Kuratowski K,Mostowski A.Set Theory.Elsevier:Academic Press,1968.
[32]Ericson C.Real-Time Collision Detection.Boca Raton:CRC Press,2004.
[33]M?ller T.A fast triangle-triangle intersection test.Journal of Graphics Tools,1997,2(2):25–31.[doi:10.1080/10867651.1997.10487472]
[34]Lee DT,Schachter BJ.Two algorithms for constructing a Delaunay triangulation.Int’l Journal of Computer&Information Sciences,1980,9(3):219–242.[doi:10.1007/BF00977785]
[35]Chew LP.Constrained delaunay triangulations.Algorithmica,1989,4(1/4):97–108.[doi:10.1007/BF01553876]
[36]Horn WP,Taylor DL.A theorem to determine the spatial containment of a point in a planar polyhedron.Computer Vision,Graphics,and Image Processing,1989,45(1):106–116.[doi:10.1016/0734-189X(89)90073-X]
[37]Feito FR,Torres JC.Inclusion test for general polyhedral.Computers&Graphics,1997,21(1):23–30.[doi:10.1016/S0097-8493(96)00067-2]
[38]Ogayar CJ,Segura RJ,Feito FR.Point in solid strategies.Computers&Graphics,2005,29(4):616–624.[doi:10.1016/j.cag.2005.05.012]
[39]Liu J,Chen YQ,Maisog JM,Luta G.A new point containment test algorithm based on preprocessing and determining triangles.Computer-Aided Design,2010,42(12):1143–1150.[doi:10.1016/j.cad.2010.08.002]
[40]Wang W,Li J,Sun H,Wu E.Layer-Based representation of polyhedrons for point containment tests.IEEE Trans.on Visualization and Computer Graphics,2008,14(1):73–83.[doi:10.1109/TVCG.2007.70407]
[41]Veblen O.Theory on plane curves in non-metrical analysis situs.Trans.of the American Mathematical Society,1905,6(1):83–98.[doi:10.1090/S0002-9947-1905-1500697-4]
[42]Revelles J,Urena C,Lastra M.An efficient parametric algorithm for octree traversal.In:Proc.of the WSCG.2000.212?219.
[43]Kornberger B.Fade2D.http://www.geom.at
[2]Requicha A.Mathematical models of rigid solid objects.Technical Memorandum 28,University of Rochester,1977.
[3]Benouamer M,Michelucci D,Peroche B.Error-Free boundary evaluation using lazy rational arithmetic:A detailed implementation.In:Proc.of the 2nd ACM Symp.on Solid Modeling and Applications.ACM,1993.[doi:10.1145/164360.164403]
[4]CGAL.Computational Geometry,2014.http://www.cgal.org
[5]Autodesk.Maya,2014.http://www.autodesk.com
[6]Bernstein G,Fussell D.Fast,exact,linear Booleans.Computer Graphics Forum,2009,28(5):1269–1278.[doi:10.1111/j.1467-8659.2009.01504.x]
[7]Campen M,Kobbelt L.Exact and robust(self-)intersections for polygonal meshes.Computer Graphics Forum,2010,29(2):397–406.[doi:10.1111/j.1467-8659.2009.01609.x]
[8]Hoffmann CM.Geometric and Solid Modeling.Palo Alto:Morgan Kaufmann Publishers,1989.
[9]Feito FR,Ogáyar CJ,Segura RJ,Rivero M.Fast and accurate evaluation of regularized Boolean operations on triangulated solids.Computer-Aided Design,2013,40(3):705–716.[doi:10.1016/j.cad.2012.11.004]
[10]Frisken SF,Perry RN,Rockwood AP,Jones TR.Adaptively sampled distance fields:A general representation of shape for computer graphics.In:Proc.of the 27th Annual Conf.on Computer Graphics and Interactive Techniques.2000.[doi:10.1145/344779.344899]
[11]Museth K,Breen DE,Whitaker RT,Barr AH.Level set surface editing operators.ACM Trans.on Graphics(TOG),2002,21(3):330–338.[doi:10.1145/566654.566585]
[12]Kobbelt LP,Botsch M,Schwanecke U,Seidel HP.Feature sensitive surface extraction from volume data.In:Proc.of the 28th Annual Conf.on Computer Graphics and Interactive Techniques.2001.[doi:10.1145/383259.383265]
[13]Ju T,Losasso F,Schaefer S,Warren J.Dual contouring of hermite data.ACM Trans.on Graphics(TOG),2002,21(3):339–346.[doi:10.1145/566654.566586]
[14]Varadhan G,Krishnan S,Kim YJ,Manocha D.Feature-Sensitive subdivision and isosurface reconstruction.In:Proc.of the Visualization.IEEE,2003.99–106.[doi:10.1109/VISUAL.2003.1250360]
[15]Varadhan G,Krishnan S,Sriram TVN,Manocha D.Topology preserving surface extraction using adaptive subdivision.In:Proc.of the 2004 Eurographics/ACM SIGGRAPH Symp.on Geometry Processing.2004.235–244.[doi:10.1145/1057432.1057464]
[16]Zhang N,Hong W,Kaufman A.Dual contouring with topology-preserving simplification using enhanced cell representation.In:Proc.of the Visualization.IEEE,2004.505–512.[doi:10.1109/VISUAL.2004.27]
[17]Schaefer S,Ju T,Warren J.Manifold dual contouring.IEEE Trans.on Visualization and Computer Graphics,2007,13(3):610–619.[doi:10.1109/TVCG.2007.1012]
[18]Smith JM,Dodgson NA.A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic.Computer-Aided Design,2007,39(2):149–163.[doi:10.1016/j.cad.2006.11.003]
[19]Edelsbrunner H,Mücke EP.Simulation of simplicity:A technique to cope with degenerate cases in geometric algorithms.ACM Trans.on Graphics(TOG),1990,9(1):66–104.[doi:10.1145/77635.77639]
[20]Wang CC.Approximate Boolean operations on large polyhedral solids with partial mesh reconstruction.IEEE Trans.on Visualization and Computer Graphics,2011,17(6):836–849.[doi:10.1109/TVCG.2010.106]
[21]Shade J,Gortler S,He LW,Szeliski R.Layered depth images.In:Proc.of the 25th Annual Conf.on Computer Graphics and Interactive Techniques.1998.[doi:10.1145/280814.280882]
[22]Thibault WC,Naylor BF.Set operations on polyhedra using binary space partitioning trees.ACM SIGGRAPH Computer Graphics,1987,21(4):153–162.[doi:10.1145/37402.37421]
[23]Naylor B,Amanatides J,Thibault W.Merging BSP trees yields polyhedral set operations.ACM SIGGRAPH Computer Graphics,1990,24(4).[doi:10.1145/97880.97892]
[24]Thibault WC.Application of binary space partitioning trees to geometric modeling and ray-tracing[Ph.D.Thesis].Georgia Institute of Technology,1987.
[25]Shewchuk JR.Adaptive precision floating-point arithmetic and fast robust geometric predicates.Discrete&Computational Geometry,1997,18(3):305–363.[doi:10.1007/PL00009321]
[26]Murali TM,Funkhouser TA.Consistent solid and boundary representations from arbitrary polygonal data.In:Proc.of the 1997Symp.on Interactive 3D Graphics.ACM,1997.[doi:10.1145/253284.253326]
[27]Hubbard PM.Constructive solid geometry for triangulated polyhedral[Ph.D.Thesis].Department of Computer Science,Brown University,1990.
[28]Yamaguchi F,Tokieda T.A unified algorithm for Boolean shape operations.Computer Graphics and Applications,1987,4(6):24–37.[doi:10.1109/MCG.1984.275959]
[29]Pilz M,Kamel HA.Creation and boundary evaluation of CSG-models.Engineering with Computers,1987,5(2):105?118.[doi:10.1007/BF01199073]
[30]M?ntyl?M,Tamminen M.Localized set operations for solid modeling.ACM SIGGRAPH Computer Graphics,1983,17(3):279–288.[doi:10.1145/964967.801159]
[31]Kuratowski K,Mostowski A.Set Theory.Elsevier:Academic Press,1968.
[32]Ericson C.Real-Time Collision Detection.Boca Raton:CRC Press,2004.
[33]M?ller T.A fast triangle-triangle intersection test.Journal of Graphics Tools,1997,2(2):25–31.[doi:10.1080/10867651.1997.10487472]
[34]Lee DT,Schachter BJ.Two algorithms for constructing a Delaunay triangulation.Int’l Journal of Computer&Information Sciences,1980,9(3):219–242.[doi:10.1007/BF00977785]
[35]Chew LP.Constrained delaunay triangulations.Algorithmica,1989,4(1/4):97–108.[doi:10.1007/BF01553876]
[36]Horn WP,Taylor DL.A theorem to determine the spatial containment of a point in a planar polyhedron.Computer Vision,Graphics,and Image Processing,1989,45(1):106–116.[doi:10.1016/0734-189X(89)90073-X]
[37]Feito FR,Torres JC.Inclusion test for general polyhedral.Computers&Graphics,1997,21(1):23–30.[doi:10.1016/S0097-8493(96)00067-2]
[38]Ogayar CJ,Segura RJ,Feito FR.Point in solid strategies.Computers&Graphics,2005,29(4):616–624.[doi:10.1016/j.cag.2005.05.012]
[39]Liu J,Chen YQ,Maisog JM,Luta G.A new point containment test algorithm based on preprocessing and determining triangles.Computer-Aided Design,2010,42(12):1143–1150.[doi:10.1016/j.cad.2010.08.002]
[40]Wang W,Li J,Sun H,Wu E.Layer-Based representation of polyhedrons for point containment tests.IEEE Trans.on Visualization and Computer Graphics,2008,14(1):73–83.[doi:10.1109/TVCG.2007.70407]
[41]Veblen O.Theory on plane curves in non-metrical analysis situs.Trans.of the American Mathematical Society,1905,6(1):83–98.[doi:10.1090/S0002-9947-1905-1500697-4]
[42]Revelles J,Urena C,Lastra M.An efficient parametric algorithm for octree traversal.In:Proc.of the WSCG.2000.212?219.
[43]Kornberger B.Fade2D.http://www.geom.at