基于半边结构细分曲面的研究与实现

基于半边结构细分曲面的研究与实现 《现代电子技:~}2009年第4期总第291期算廑用撞 基于半边结构细分曲面的研究与实现 杨龙,代 (西北农林科技大学 媛,何东健 陕西杨凌712100) 摘要:作为CAD和计算机辅助几何 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的重要技术之一,细分曲面为实体造型提供了新的离散造型 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 .在阐述细 分曲面主要思想基础上,采用Catmull—Clark四边形模式介绍细分曲面生成算法;并用半边结构表示和存储实体的面,边和 点之间的拓扑关系.以Catmull—Clark模式为例基于半边数据结构演示细分曲面的生成.结果表明,细分曲面具有 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf 简 单,易于实现,且在适当数据结构支持下仅需较少初始控制网格信息就可得到极限曲面的优点,因而细分曲面技术成为三维 实体造型的一种有效途径. 关键词:细分曲面;CAGD;Catmul卜Clark模式;半边结构 中图分类号:TP391文献标识码:B文章编号:1004—373X(2OO9)O4—099—03 ResearchandImplementationofSub—divisionSurfaceBasedonHalf—edgeStructure YANGLong,DAIYuan,HEDongjian (NorthwestA&FUniversity,Yangling,712100,China) Abstract:SubdivisionsurfaceasanimportanttechnologyofCADandCAGD,anewdiscretemethodfor geometricsolid modelingisprovided.Themainthoughtofsubdivisionisilluminatad,Catmull—Clarkmodeisadoptedtointroducethealgo— rithmofsubdivisionsurface.Thetopologicalrelationshipamongface,edgeandvertexofsolidsisreprese ntedandstoredbased onHalf—Edgestructure.TheexampleofsubdivisionsurfaceisdemonstratedthroughCatmull—Clarkmode.Theresultshows thattheruleofsubdivisionsurfaceissimpleandeasytoimplementanditonlyneedslessinformationofthe originalcontrolnet togetthelimitsurfaceaslongassupportedbyproperdatastructure.Therefore,subdivisionsurfacebecom esaneffective approachof3Dsolidmodeling. Keywords:subdivisionsurface;CAGD;Catmull—Clarkmode;half—edgestructure O弓I言点之一. 随着计算机图形学的发展和计算机辅助几何设计 (CAGD)在工业和形体设计中的广泛应用,实体造型中 几何对象的多样性,复杂性和拓扑结构任意性趋势日益 明显,用户对图形系统显示的真实性,实时性和交互性 要求越来越高,以传统的曲面造型技术为主的实体造型 方法已逐渐不能满足上述要求.而细分技术[1]是一种 全新的形体表示思路. 细分技术可以用较少的数据量和简单的规则表示 复杂的几何形体.它具有拓扑任意性,仿射不变性,数 值稳定性,表示一致性以及规则简单性等良好性质,因 此细分造型技术已作为重要的实体造型手段而得到了 广泛的研究与应用.从飞机,轮船,汽车到家电,服装等 工业品,甚至山脉,云,江河等自然现象;从静态模拟到 动态仿真,细分都以其简洁的表示,处理任意拓扑的能 力使得细分技术成为了几何造型领域最活跃的研究热 收稿日期:2008一O8—25 基金项目:陕西省自然科学基金资助项目(2004D12) 1细分技术 细分技术成为曲线曲面造型领域的一种重要方法, 特别是近些年,细分概念在一些复杂形体表示与设计, 动画制作,工业设计以及虚拟现实等方面的成功应用使 得细分技术在实体造型中大有后来居上之势. 细分是一种基于多边形或多面体的技术,指对初始 控制网格依据一定的细分规则通过不断细化产生光滑 的极限曲线或曲面的过程.与传统连续曲线曲面造型 方法相比,它只需 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 少量的初始信息,在指定的规则 下通过若干次分割初始控制网格就可以得到满意精度 的结果曲线或曲面,是一种易于计算机直接生成的离散 造型技术. 1.1细分曲面 细分曲面_2是从给定的初始控制网格Mo出发(一 般为多面体),递归地调用细分规则S加密控制网格, 即M件===SjMj,依次可得到M1,M2,…,最终在极限意 义下,即当一时,网格序列收敛到结果曲面R一 99 杨龙等:基于半边结构细分曲面的研究与实现 上.根据细分规则S,的不同,曲面R或者插值或者 逼近Mo.而且,通常规则s,具有局部性,M升中的顶点 是M中对应有限个控制顶点的仿射组合.细分曲面可 理解为是一种过程化,层次化的采样技术,它将形体属 性巧妙地转换成了细分规则. 细分曲面的主要处理过程为:从初始的控制网格开 始,按照某种规则,递归地产生新点逐渐加密控制网格. 随着细分不断进行,控制网格被逐渐磨光,最终生成离 散点插值或逼近的光滑的曲面.常见的细分曲面方法 有:Catmull—Clark四边形细分模式;Doo,Sabin四边 形模式.;Loop三角形模式;Butterfly三角形模 式[等. 1.2Catmull—Clark细分模式 Catmull—Clark模式是一种基于四边形网格的 1,4面分裂静态逼近细分割模式.当初始控制网格为 任意多边形时,可对其做1次分割得到四边形网格,再 采用细分算法进行递归细分.其细分规则如下: (1)F一顶点(面点):如图1(a)所示,设四边形面的 4个顶点为V.,V,.,V.,则相应的F一顶点取为: VF一(V.+V+V2+V3)/4 (2)E一顶点(边点):如图1(b),设内部边的端点为 .,,共享此边的2个四边形面分别为(,,, V.)和(V.,V,V,V),则与此内部边相对应的E一顶 点为: VE一(3/8)(+V1)+(1/16)? (Vz+V.+V+V) (3)V一顶点:如图1(c),若内部顶点的一环的边 界顶点依次为,一,一,其中偶数下标的顶点 为邻点,奇数下标的顶点为其四边形面上的对角顶点, 相应的一顶点为: V一V+鲁萎V2i+鲁n-121 n— 其中:权值为一3/(272);=1/(4);一1一一 . (4)边界边(.,V)上的E一顶点如图1(d)所示. VE一(1/2)(V0+V) (5)边界边(V.,V)上的V一顶点:如图1(e)所示. V一(1/8)(V.+V)+(3/4)V 1.3半边结构 如何记录几何实体中面,边和点间的拓扑关系,对 提高曲面生成效率,减少数据冗余,有着重要影响.因 此,细分曲面数据结构的研究对曲面的有效生成有着重 1O0 要意义. l/21/2 (d)边界E.顶点 (c)V-顶点 ———— ?——一l 1,83/41/8 (e)边界v.顶点 图1Catmull—Clark细分规则 MarttiMantyla提出的以边为核心组织数据的半 边结构](Half—EdgeStructure)能有效表示几何模型 的拓扑关系.在半边结构中,将1条边一分为二,其中 一 条半边属于它一个相邻面的边环,而另一条半边属于 它另一个相邻面的边环(如图2所示).每一条半边仅 存储它的起点指针,这样2条半边就能够表示1条边的 2个端点,当搜索1个面的各端点时,只需沿着半边顺 序遍历即可. 图2半边结构 半边结构是一个多能的边界表示法,存储了非常明 确的朝向信息在网格几何体中.它可以高效地找出点, 边,面等几何元素间的连接关系,能实现非常快的邻接 查询.而且半边网格结构运行也相当迅速,包围1个顶 点的边的查询,面面相临,所有这些都能够实时的完成 耗时也只是常数时间l8]. 采用半边数据结构可以精确表示物体,其具有覆盖 域大,表示能力强,容易确定几何元素间的连接关系,几 何变换比较容易,绘制速度快的优点. 2细分曲面的实现 在VC中OpenGL环境下,采用半边结构定义 3个结构体分别记录顶点结构,边结构和面结构: struetHE_vert { floatX; floaty; floatz: HE_edgeedge;//oneofthehalf—edgeemanating fromthevertex }; structHE_edge { /\ 边? 2009年第4期第291 HE.vert*vert; HE_edgepair; HE—face*face; HE_edge*next; ); structHEface { //vertexattheendofthehalf_edge //oppositelyorientedadjacenthalf — edge //facethehalf—edgeborders //nexthalf—edgearoundtheface HE—edge*edge;//oneofthehalf—edgesbordering thefaee }; 按Catmull—Clark规则对初始单位正方体控制网 格进行细分割,初始控制网格和第一次细分,第二次细 分结果如图3所示.图4显示结果为经过5次细分割 后的曲面,经多次细分后其逼近极限曲面为球面. (a)第1次细分结果(b)第2次细分结果?图3初始单位正方体及前两次图4第5次细分后 细分后所得曲面所得曲面 由于采用半边数据结构表示实体,仅需要存储实体 的顶点信息,边信息和面信息就能较容易地求得新的面 点,边点和顶点,以及它们之间的拓扑关系.随着细分 次数的增加和数据量增多,其具有比一般矩阵标记法节 省存储空间,查找效率高的优点. 3结语 结合半边数据结构对细分曲面造型技术进行讨论. 说明细分曲面方法在适当的数据结构支持下能够有效 地实现几何形体的离散造型,且具有拓扑任意性,仿射 不变性,数值稳定性以及规则简单,易于实现的优点. 因此,细分曲面技术已经成为新的实体造型的重要手 段.当前许多新的细分模式被不断的提出,尤其在表示 一 些拓扑复杂的三维实体时,在一些特殊点的连续性处 理问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 上以及数值稳定性方面,其展现了传统造型方法 无法比拟的优势. 参考文献 Eli邓军民,宾鸿赞,区士颀,等.细分造型技术在CAD系统中 的应用研究[J].光学精密工程,2002,10(2):226—230. E2]郑立垠,周笑天,于萍,等.基于Euler操作的四边形网格细 分算法设计与实现[J].计算机工程与设计,2007,28(3): 3151—3156. I-3]DooD,SabinM.BehaviourofRecursiveDivisionSurfaces nearExtraordinaryPoints[J].CAD,1978,10 (6):356—360. [4]LoopC.SmoothSubdivisionSurfacesBasedonTriangles[D]. Utah:UniversityofUtah,DepartmentofMathematics,1987. [5]NiraDyn,DavidLevin.TheSubdivisionExperience.In CurvesandSurfacesII,199l:1—17. [6]CatmullE,ClarkJ.RecursivelyGeneratedB—splineSur— facesonArbitraryTopologicalMeshes[J].AD,1978,10 (6):350—355. [7]严宁.李启炎.半边结构的三维实体在OpenGI中的表示 EJ].微型电脑应用,2002,18(9):51—53. [8]MaxMcGuire.TheHalf—edgeDataStructure[EB/OL]. http}{w.flipcode.com/artieles/article—halfedge.shtm1. 2000.8. [9]胡海龙,刘树群.Catmull—Clark细分曲面的纹理映射技术 F-J].微计算机信息,2007(18):274—281,282. [10]陈旭.Catmull—Clark曲面控制网格的收敛性质EJ].数学 研究,2007,40(4):386—391. 作者简介杨龙男,1982年出生,陕西岐山人,硕士研究生.主要从事图形学,虚拟现实技术的研究. 代媛女,1981年出生,硕士研究生.主要从事智能化检测与监控系统的研究. 何东健男,1957年出生,博士,教授,博士生导师.主要从事图像分析与识别,智能化检测与控制及虚拟现实技术应 用等研究工作. (上接第98页) [2]李为,刘嘉勇.一种基于分区引导扇区控制的移动存储介质 安全控制方法[J].成都信息工程学院学报,2007,22(1):92 — 97. [33袁建东,赵强,郑见灵.Windows系统下FAT32分区信息分 析与获取方法[J].河北工业科技,2007,24(1):11—12. [41黄国盛,梁平元,周小清.Windows环境中分区表结构剖析 与安全修复[J].吉首大学学报:自然科学版,2003,24(1):56 — 57. [5]张载鸿,余永进,何渝,等.MS,DOS6技术精萃[M].北京: 清华大学出版社,1994.74—93. [6]佚名.VC实现Win2000下直接读写磁盘扇区[EB/OL]. http:}{.VCZX.corn/article/list.php,2004. 作者简介沈瑜女,1984年出生,陕西西安人,硕士研究生.主要研究方向为指挥自动化. 妙全兴男,1965年出生,陕西岐山人,副教授,研究生导师.主要研究方向为计算机网络,信息安全. 1O1