大规模网格模型间的快速视觉布尔运算
|
摘要
为了解决产品设计阶段中大规模网格模型间的布尔运算无法实现立等可得的速度瓶颈,提出了一种新算法。该算法利用离散化采样获得射线段点云模型,将三角面片间的3D布尔运算转换为射线段间的1D布尔运算,对相交处的交点进行高精度的求解和插值处理,使得布尔运算速度大为提高,从而大大提升复杂拓扑结构的产品设计效率。通过该算法所获得射线段点云模型可获得等同于基于三角网格的渲染效果,该方法可进行工程应用。
A new algorithm was proposed to meet the instantaneous response requirements of the Boolean operation between large-scale mesh models in the product design. Discrete sampling was performed on mesh models to obtain the raysegment point clound model and the three-dimensional Boolean operation among triangular mesh was then converted into onedimensional one among ray segments; the intersection points could be accurately solved and interpolated around the overlapped regions of mesh models, so the Boolean operation was significantly speeded and the design efficiency of products of complex topology was greatly improved in turn. The point cloud model obtained by the proposed algorithm could be rendered with the same effect as that by the triangular mesh model. The proposed method can be adopted in engineering applications.
A new algorithm was proposed to meet the instantaneous response requirements of the Boolean operation between large-scale mesh models in the product design. Discrete sampling was performed on mesh models to obtain the raysegment point clound model and the three-dimensional Boolean operation among triangular mesh was then converted into onedimensional one among ray segments; the intersection points could be accurately solved and interpolated around the overlapped regions of mesh models, so the Boolean operation was significantly speeded and the design efficiency of products of complex topology was greatly improved in turn. The point cloud model obtained by the proposed algorithm could be rendered with the same effect as that by the triangular mesh model. The proposed method can be adopted in engineering applications.
引文
[1]姜旭东,盛斌,马利庄,等.基于自适应延迟切割的三角网格布尔运算优化[J].软件学报,2016,27(10):2473-2487.(JIANG XD,SHENG B,MA L Z,et al.Optimization of set operations on triangulated polyhedrons using adaptive lazy splitting[J].Journal of Software,2016,27(10):2473-2487.)
[2]蔡闯,成思源,杨雪荣.基于特征分解的逆向建模技术研究[J].现代制造工程,2016(2):119-122.(CAI C,CHENG S Y,YANGX R.Research of reverse modeling technology based on feature decomposition[J].Modern Manufacturing Engineering,2016(2):119-122.)
[3]王翀,安伟强,王红娟.基于圆柱体-轴向包围盒检测的巷道相交建模[J].计算机应用,2015,35(12):3592-3596.(WANG C,ANW Q,WANG H J.Tunnel intersection modeling based on cylinderaxis aligned bounding box[J].Journal of Computer Applications,2015,35(12):3592-3596.)
[4]VAN DEN BERGEN G.Efficient collision detection of complex deformable models using AABB trees[J].Journal of Graphics Tools,1997,2(4):1-13.
[5]GOTTSCHALK S,LIN M C,MANOCHA D.OBB tree:a hierarchical structure for rapid interference detection[C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM,1996:171-180.
[6]HUBBARD P M.Collision detection for interactive graphics applications[J].IEEE Transactions on Visualization and Computer Graphics,1998,1(3):218-230.
[7]KLOSOWSKI J T,HELD M,MITCHELL J S B,et al.Efficient collision detection using bounding volume hierarchies of k-DOPs[J].IEEE Transactions on Visualization and Computer Graphics,1998,4(2):21-36.
[8]PAVIC D,CAMPEN M,KOBBELT L.Hybrid Booleans[J].Computer Graph Forum,2010,29:75-87.
[9]LORENSEN W E,CLINE H E.Marching cubes:a high resolution3D surface construction algorithm[J].ACM SIGGRAPH Computer Graphics,1987,21(4):163-169.
[10]KIM Y,VARADHAN G,LIN M C,et al.Fast swept volume approximation of complex polyhedral models[C]//Proceedings of the Eighth ACM Symposium on Solid Modeling and Application.New York:ACM,2004:1013-1027.
[11]CHEN Y,WANG C C L.Robust and accurate Boolean operations on polygonal models[C]//ASME 2007:Proceedings of the 2007International Design Engineering Technical Conferences and Computers and Information in Engineering Conference.New York:ACM,2007:357-369.
[12]JONES M W,BARENTZEN J A,SRAMEK M.3D distance fields:a survey of techniques and applications[J].IEEE Transactions on Visualization and Computer Graphics,2006,12(4):581-599.
[13]MUSETH K,BREEN D E,WHITAKER R T,et al.Level set surface editing operators[J].ACM Transactions on Graphics,2002,21(3):330-338.
[14]ADAMS B,DUTRE P.Interactive Boolean operations on surfelbounded solids[J].ACM Transactions on Graphics,2003,22(3):651-656.
[15]MENON J P,VOELCKER H B.On the completeness and conversion of ray representations of arbitrary solids[C]//Proceedings of the 1995 International Proceedings of ACM Symposium on Solid Modeling and Applications.New York:ACM,1995:175-286.
[16]WANG C L.Approximate Boolean operations on large polyhedral solids with partial mesh reconstruction[J].IEEE Transactions on Visualization and Computer Graphics,2011,17(6):836-849.
[17]HEIDELBERGER B,TESCHNER M,GROSS M.Detection of collisions and self-collisions using image space techniques[J].Journal of WSCG,2004,12(1/2/3):145-152.
[18]FEITO F R,OGAYAR C J,SEGURA R J,et al.Fast and accurate evaluation of regularized Boolean operations on triangulated solids[J].Computer-Aided Design,2013,45(3):705-716.
[19]WANG C C L,LEUNG Y S,CHEN Y.Solid modeling of polyhedral objects by layered depth-normal images on the GPU[J].Computer-Aided Design,2010,42(6):535-544.
[20]ADAMS B,DUTRE P.Interactive Boolean operations on surfelbounded solids[J].ACM Transactions on Graphics,2003,22(3):651-656.
[21]WANG C L.Approximate Boolean operations on large polyhedral solids with partial mesh reconstruction[J].IEEE Transactions on Visualization and Computer Graphics,2011,17(6):836-849.
[22]WANG Z J,LIN X,FANG M E,et al.RE2L:an efficient outputsensitive algorithm for computing Boolean operations on circular-arc polygons and its applications[J].Computer-Aided Design,2017,83:1-14.
[23]LANDIER S.Boolean operations on arbitrary polygonal and polyhedral meshes[J].Computer-Aided Design,2016,85:138-153.
[24]JIANG X,PENG Q,CHENG X,et al.Efficient Booleans algorithms for triangulated meshes of geometric modeling[J].Computer-Aided Design and Applications,2016,13(4):1-12.
[25]CHEN M,CHEN X Y,TANG K,et al.Efficient Boolean operation on manifold mesh surfaces[J].Computer-Aided Design and Applications,2010,7(3):405-415.
[2]蔡闯,成思源,杨雪荣.基于特征分解的逆向建模技术研究[J].现代制造工程,2016(2):119-122.(CAI C,CHENG S Y,YANGX R.Research of reverse modeling technology based on feature decomposition[J].Modern Manufacturing Engineering,2016(2):119-122.)
[3]王翀,安伟强,王红娟.基于圆柱体-轴向包围盒检测的巷道相交建模[J].计算机应用,2015,35(12):3592-3596.(WANG C,ANW Q,WANG H J.Tunnel intersection modeling based on cylinderaxis aligned bounding box[J].Journal of Computer Applications,2015,35(12):3592-3596.)
[4]VAN DEN BERGEN G.Efficient collision detection of complex deformable models using AABB trees[J].Journal of Graphics Tools,1997,2(4):1-13.
[5]GOTTSCHALK S,LIN M C,MANOCHA D.OBB tree:a hierarchical structure for rapid interference detection[C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM,1996:171-180.
[6]HUBBARD P M.Collision detection for interactive graphics applications[J].IEEE Transactions on Visualization and Computer Graphics,1998,1(3):218-230.
[7]KLOSOWSKI J T,HELD M,MITCHELL J S B,et al.Efficient collision detection using bounding volume hierarchies of k-DOPs[J].IEEE Transactions on Visualization and Computer Graphics,1998,4(2):21-36.
[8]PAVIC D,CAMPEN M,KOBBELT L.Hybrid Booleans[J].Computer Graph Forum,2010,29:75-87.
[9]LORENSEN W E,CLINE H E.Marching cubes:a high resolution3D surface construction algorithm[J].ACM SIGGRAPH Computer Graphics,1987,21(4):163-169.
[10]KIM Y,VARADHAN G,LIN M C,et al.Fast swept volume approximation of complex polyhedral models[C]//Proceedings of the Eighth ACM Symposium on Solid Modeling and Application.New York:ACM,2004:1013-1027.
[11]CHEN Y,WANG C C L.Robust and accurate Boolean operations on polygonal models[C]//ASME 2007:Proceedings of the 2007International Design Engineering Technical Conferences and Computers and Information in Engineering Conference.New York:ACM,2007:357-369.
[12]JONES M W,BARENTZEN J A,SRAMEK M.3D distance fields:a survey of techniques and applications[J].IEEE Transactions on Visualization and Computer Graphics,2006,12(4):581-599.
[13]MUSETH K,BREEN D E,WHITAKER R T,et al.Level set surface editing operators[J].ACM Transactions on Graphics,2002,21(3):330-338.
[14]ADAMS B,DUTRE P.Interactive Boolean operations on surfelbounded solids[J].ACM Transactions on Graphics,2003,22(3):651-656.
[15]MENON J P,VOELCKER H B.On the completeness and conversion of ray representations of arbitrary solids[C]//Proceedings of the 1995 International Proceedings of ACM Symposium on Solid Modeling and Applications.New York:ACM,1995:175-286.
[16]WANG C L.Approximate Boolean operations on large polyhedral solids with partial mesh reconstruction[J].IEEE Transactions on Visualization and Computer Graphics,2011,17(6):836-849.
[17]HEIDELBERGER B,TESCHNER M,GROSS M.Detection of collisions and self-collisions using image space techniques[J].Journal of WSCG,2004,12(1/2/3):145-152.
[18]FEITO F R,OGAYAR C J,SEGURA R J,et al.Fast and accurate evaluation of regularized Boolean operations on triangulated solids[J].Computer-Aided Design,2013,45(3):705-716.
[19]WANG C C L,LEUNG Y S,CHEN Y.Solid modeling of polyhedral objects by layered depth-normal images on the GPU[J].Computer-Aided Design,2010,42(6):535-544.
[20]ADAMS B,DUTRE P.Interactive Boolean operations on surfelbounded solids[J].ACM Transactions on Graphics,2003,22(3):651-656.
[21]WANG C L.Approximate Boolean operations on large polyhedral solids with partial mesh reconstruction[J].IEEE Transactions on Visualization and Computer Graphics,2011,17(6):836-849.
[22]WANG Z J,LIN X,FANG M E,et al.RE2L:an efficient outputsensitive algorithm for computing Boolean operations on circular-arc polygons and its applications[J].Computer-Aided Design,2017,83:1-14.
[23]LANDIER S.Boolean operations on arbitrary polygonal and polyhedral meshes[J].Computer-Aided Design,2016,85:138-153.
[24]JIANG X,PENG Q,CHENG X,et al.Efficient Booleans algorithms for triangulated meshes of geometric modeling[J].Computer-Aided Design and Applications,2016,13(4):1-12.
[25]CHEN M,CHEN X Y,TANG K,et al.Efficient Boolean operation on manifold mesh surfaces[J].Computer-Aided Design and Applications,2010,7(3):405-415.