扩展八叉树算法在虚拟雕刻几何建模中的应用.pdf

《扩展八叉树算法在虚拟雕刻几何建模中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、·信息技术·梁云芳，等·扩展八叉树算法在虚拟雕刻几何建模中的应用扩展八叉树算法在虚拟雕刻几何建模中的应用梁云芳，伍铁军(南京航空航天大学机电学院，江苏南京210016)摘要：基于传统的八叉树模型的基础及特点，引人了带表面边界信息的扩展八叉树模型以及相应的扩展八叉树模型的特殊数据结构，并将它们应用于虚拟雕刻的几何建模系统中；叙述了如何将实体从表面边界模型转换成相应的改进八又树模型的方法，同时采用了局部更新技术提高模型更新效率；最后通过运行雕刻实例证明算法的有效性和可行性。关键词：扩展八又树；数据结构；几何建模；局部更新中图分类号：TP391．9文献标志码：B文章编号：1671．5276(201

2、2)01-0102-04UsingExtendedOctreeAlgorithmtoModelVirtualSculptingGeometryLIANGYun—fang．wuTie-jun(CollegeofMechanicalandElectricalEngineering，NanjingUniversityofAeronauticsandAstronautics，Nanjing210016，China)Abstract：AccordingtothebasicfeaturesoftraditionalOctreemodel，weimportsudaceboundafinformationa

3、ndspecialdatastruc-turestoextendoctreemodelandapplythemtothegeometricmodelingofvirtualsculptingsystem；wealsoproposesaconversionmethodthatthepolyhedralBRepmodelisconvertedtoextendedoctreemodelandusepartialupdatingtechniquetoupdatethemod-e1．Then，thealgorithm’sefectivenessandfeasibilityareverifiedwith

4、arealvirtualsculptingprogram．Keywords：extendedoctreemodel；datastructure；geomet~simulation；partialupdating质处理；文献[2]主要侧重于三角片网格形体的局部变形0引言算法和快速虚拟雕刻算法的研究；文献[34]主要侧重于毛坯变形结果的基于索引曲面的表面建模技术；文献[5]虚拟雕刻是另一种全新理念的自由造型方法。在软采用射线跟踪算法以及CSG表示产生高品质的雕刻物硬件的配合下，创作者使用虚拟刻刀，与普通的木雕、牙体；文献[6]采用了基于八又树的体素建模法并应用一种雕、石雕、骨雕一样，一步步通过去

5、材料进行空间立体造型改进立方体遍历方法完成反走样及便捷细分以提高系统设计。这里研究的是基于机器视觉的虚拟雕刻几何建模。速度同时减少存储空间高达20倍；总结以上各种几何建其主要的思想是：首先基于双目视觉及图像处理得到三维模方法，提出的虚拟雕刻几何建模是基于机器视觉的虚拟雕刻轨迹，然后对虚拟毛坯、虚拟雕刻刀等进行j维建模，雕刻。因此为了满足系统实时、快速有效的要求，采用了接着进行虚拟毛坯和虚拟雕刻刀模型的雕刻算法，最后采带曲面边界信息的扩展八又树模型表示方法。用真实感图形动态实时地显示虚拟雕刻过程以及雕刻结果。而三维动态显示实体的基本要求是：首先表示的精确2带曲面边界信息的扩展八叉树模型度要高，

6、其次是快速有效的模型更新，最后还要求存储空间要少。为实现这些要求主要提出了采用改进后的带曲为了解决传统的八叉树表示法精确度低的问题，采用面边界信息的扩展八又树算法以及相应的特殊数据结构将曲面的边界信息加入到八叉树结点的扩展八叉树模型来实现对虚拟毛坯的雕刻及雕刻过程的较精确表示。同表示方法。以八叉树模型在二维空间的特殊情况四叉树时将改进后的八叉树算法和局部更新技术结合不仅可以模型为例。图1(a)是需要表示的正方形，图1(b)是图1大大提高虚拟雕刻过程的计算和模型更新速度，还可以减少存储空间．(a)的给定精确度的四又树模型表示，它需要88个正方形单元。然而，如果直线段和顶点(两条直线的交点)信息

7、可以加入到灰色单元的话，它只要7个正方形单元和四1虚拟雕刻几何建模发展现状条直线段就可以表示这个正方形，如图1(c：)。目前国内外对虚拟雕刻研究处于起步发展阶段。其在这种方法中每个灰色单元允许包括一条直线段或中sedethersls提出用三维控制网格作为变形工具控制物者一个带有两条相交直线段的顶点作为附加信息。相对体变形的自由变形方法；文献[1]主要侧重于基于物理样于传统四叉树它不仅节省了大量空间，同时也较准