三维实体建模及布尔运算造型技术优秀毕业论文.pdf

分类号：分类号： tp391tp391密密级：级：公公 开开 u du d c c ：单位代码：单位代码：1042410424 学学 位位 论论 文文 三维实体建模及布尔运算造型技术三维实体建模及布尔运算造型技术三维实体建模及布尔运算造型技术 三维实体建模及布尔运算造型技术 王王 红红 娟娟 申请学位级申请学位级别别：硕士学位硕士学位专业专业名名称：称：计算机系统结构计算机系统结构 指导教师姓名指导教师姓名：卢卢 新新 明明职职称：称：教教授授 山山 东东 科科 技技 大大 学学 二零零七年五月二零零七年五月 论文题目：论文题目：论文题目： 论文题目： 三维实体建模及布尔运算造型技术三维实体建模及布尔运算造型技术三维实体建模及布尔运算造型技术 三维实体建模及布尔运算造型技术 作者姓名：作者姓名：作者姓名： 作者姓名： 王红娟王红娟入学时间：入学时间：入学时间： 入学时间： 20042004 年年 9 9 月月 专业名称：专业名称：专业名称： 专业名称： 计算机系统结构计算机系统结构研究方向：研究方向：研究方向： 研究方向： 多媒体技术多媒体技术 指导教师：指导教师：指导教师： 指导教师： 卢新明卢新明职职职 职 称：称：称： 称： 教教授授 论文提交日期：论文提交日期：论文提交日期： 论文提交日期： 20072007 年年 5 5 月月 论文答辩日期：论文答辩日期：论文答辩日期： 论文答辩日期： 20072007 年年 6 6 月月 1212 日日 授予学位日期：授予学位日期：授予学位日期： 授予学位日期： 3d solid modeling and boolean operation modeling technique a dissertation submitted in fulfillment of the requirements of the degree of master of philosophy from shandong university of science and technology by wang hongjuan supervisor: professor lu xinming college of information science and engineering maymaymay may 200720072007 2007 声声明明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公公 认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于 其它任何学术机关作鉴定。其它任何学术机关作鉴定。 硕士生签名：硕士生签名： 日日期：期： affirmationaffirmationaffirmation affirmation i i i i declaredeclaredeclare declare thatthatthat that thisthisthis this dissertation,dissertation,dissertation, dissertation, submittedsubmittedsubmitted submitted ininin in fulfillmentfulfillmentfulfillment fulfillment ofofof of thethethe the requirementsrequirementsrequirements requirements forforfor for thethethe the awardawardaward award ofofof of mastermastermaster master ofofof of philosophyphilosophyphilosophy philosophy ininin in shandongshandongshandong shandong universityuniversityuniversity university ofofof of sciencesciencescience science andandand and technology,technology,technology, technology, is is is is whollywhollywholly wholly mymymy my ownownown own workworkwork work unlessunlessunless unless referencedreferencedreferenced referenced ofofof of acknowledge.acknowledge.acknowledge. acknowledge. thethethe the documentdocumentdocument document hashashas has notnotnot not beenbeenbeen been submittedsubmittedsubmitted submitted forforfor for qualificationqualificationqualification qualification atatat at anyanyany any otherotherother other academicacademicacademic academic institute.institute.institute. institute. signature:signature:signature: signature: date:date:date: date: 山东科技大学硕士学位论文目录 摘摘要要 三维造型技术是计算机辅助设计（cad）系统中的高级技术，同时又是虚拟现实 （vr）中虚拟模型的基础技术，三维造型技术已迅速成为 cad 技术的主流。实体交、 并、差布尔运算是实体造型领域最为重要、最为复杂的问题之一，是实体造型中构造复 杂实体的必要手段之一，在许多领域都得到了广泛地应用。本文对实体造型技术中的实 体建模及实体间的布尔运算进行了研究，提出了旋转和拉伸的建模方法及实体间的交、 并、差运算算法。在实体建模设计中，对简单的物体，可通过对其进行结构分析，将其 分解成若干基本体，其中基本体有长方体、球体、圆柱体、圆锥体、圆环体、楔体等， 对基本实体建模后再进行交、并、差布尔运算，便可生成物体的三维实体模型。对于有 些复杂的物体，往往难以分解成若干个基本体,为此，可在二维几何元素构造中先定义 物体的截面轮廓，然后在三维实体造型中通过旋转、拉伸方法得到新的“基本体”，进 而通过交、并、差运算得到所需要物体的三维实体造型。在实体交、并、差运算算法中 ， 主要以交运算算法为基础，介绍了交、并、差运算过程中所涉及到的算法。图形求交及 点在体内外的判断是实现交、并、差布尔运算的基础,文中也对图形求交中的求交点算 法和求交边算法及点与实体的位置关系判断算法进行了介绍。 关键词：关键词：实体造型，布尔运算，交，并，差 山东科技大学硕士学位论文目录 abstractabstract the 3d modeling technique is the advanced technique in the computer aided design(cad) system and the basic technique of model in virtual reality(vr). it has already become the main current of cad technique quickly. the solid intersection, union, difference boolean operation is one of the most important and complicated problems in the solid modeling realm. it is one of the necessary means for constructing complicated solid in the solid modeling and gets extensive application in many realms. this thesis takes comprehensive research on solids modeling and boolean operation of solids, bringing forward revolvingandextrudingmodelingandintersection,union,difference operation algorithm. in solids modeling through analyzing its structure, the simplyobjectisdecomposedintoalotofbasicsolidssuchas box,sphere,cylinder,cone,torus,wedge etc. after the basis solid modeling we cangetthe3dsolidmodelingoftheobjectbyintersection,union, difference operation. for some complicated objects, it is difficult to be decomposed into some basic bodies.so, we can define the section outline of object in the two dimensions geometry element structure. then we get new basic body by revolving or extruding in the 3d solid modeling and create the3dsolidmodelingoftheobjectbyintersection,union,difference operation.intheintersection,union,differenceoperationalgorithm,the intersectionoperationasthebasis,introducingmanyalgorithmswhich intersection, union ,difference operation involve. the graphics intersection and judging points in or out body is the basis which realizes intersection, union ,difference operation ,this thesis also introduces the algorithm of point intersection and edge intersection and point and polyhedron position relation judgement algorithm. keywordskeywords：solid modeling, boolean operation, intersection, union, difference 山东科技大学硕士学位论文目录 目录目录目录 目录 1 1 1 1 绪论绪论绪论 绪论 1 1 1 1 1.1 三维几何造型技术理论概述 1 1.2 实体造型的发展状况及表示方法 2 1.3 论文的选题以及主要研究内容 5 2 2 2 2 基本概念及数据结构基本概念及数据结构基本概念及数据结构 基本概念及数据结构 8 8 8 8 2.1 几何信息和拓扑信息 8 2.2 形体的定义 9 2.3 集合运算10 2.4 数据结构12 3 3 3 3 实体建模实体建模实体建模 实体建模 151515 15 3.3.3. 3. 1 基本实体建模 16 3.3.3. 3. 2 旋转 18 3.3.3. 3. 3 拉伸 20 3.3.3. 3. 4 三维旋转变换 22 4 4 4 4 几何元素求交几何元素求交几何元素求交 几何元素求交 242424 24 4.4.4. 4. 1 求交点算法 24 4.4.4. 4. 2 求交线算法 26 5 5 5 5 点与实体位置关系的判断点与实体位置关系的判断点与实体位置关系的判断 点与实体位置关系的判断 292929 29 5.5.5. 5. 1 点在平面多边形内的算法描述 29 5.5.5. 5. 2 点在空间面内的算法描述 31 5.5.5. 5. 3 点在任意实体内的算法描述 32 5.5.5. 5. 4 对几种特殊情况的处理 33 6 6 6 6 实体布尔运算实体布尔运算实体布尔运算 实体布尔运算 373737 37 6.6.6. 6. 1 交、并、差运算关系框图 37 山东科技大学硕士学位论文目录 6.6.6. 6. 2 交运算算法分析与描述 38 6.6.6. 6. 3 差运算和并运算 45 6.6.6. 6. 4 实体建模及实体运算实例 49 7 7 7 7 总结和展望总结和展望总结和展望 总结和展望 535353 53 7.7.7. 7. 1 总结 53 7.7.7. 7. 2 展望 53 参考文献参考文献参考文献 参考文献 545454 54 致致致 致 谢谢谢 谢 565656 56 攻读硕士学位期间的研究成果攻读硕士学位期间的研究成果攻读硕士学位期间的研究成果 攻读硕士学位期间的研究成果 575757 57 山东科技大学硕士学位论文目录 山东科技大学硕士学位论文目录 contentscontentscontents contents 1 1 1 1 prefaceprefacepreface preface 1 1 1 1 1.1thesummarizationof 3dgeometricmodelingtechnique 1 1.2 the development current and express method of solid modeling2 1.3 main researches of this thesis . 5 2the2the2the 2the basicbasicbasic basic conceptionconceptionconception conception andandand and datadatadata data structurestructurestructure structure .8.8.8 .8 2.1thegeometryinformationand topologyinformation. 8 2.2thedefinationofthesolid. .9 2.3thesetoperation.10 2.4 data structure.12 3 3 3 3 thethethe the solidsolidsolid solid modelingmodelingmodeling modeling . . . . 151515 15 3.1 the basic solid modeling .16 3.2 the rotationmodeling.18 3.3 the extrudemodeling.20 3.4the3d rotationtransform 22 4 4 4 4 thethethe the i i i i ntersectionntersectionntersection ntersection ofofof of graphicsgraphicsgraphics graphics 242424 24 4.1theagorithm ofpointofintersection.24 4.2theagorithmoflineof intersection.26 5 5 5 5 thethethe the judgementjudgementjudgement judgement ofofof of positionpositionposition position relationrelationrelation relation ofofof of pointpointpoint point andandand and polygonpolygonpolygon polygon 292929 29 5.1the algorithmdescriptionof pointinanypolygonand pointinanyspaceface29 5.2the judgementofpoint inany polygon.31 5.3the judgementof pointinanysolid.32 5.4thespecialcircumstancesdealingwith.33 6 6 6 6 thethethe the algorithmalgorithmalgorithm algorithm descriptiondescriptiondescription description ofofof of intersection,intersection,intersection, intersection, unionunionunion union andandand and differencedifferencedifference difference ofofof of solidssolidssolids solids 373737 37 6.1therelationframeofintersection、union anddifferenceoperation.37 6.2the analysisand descriptionof intersectionalgorithm.38 6.3thedifferenceoperationand unionoperation45 6.4the examplesof solidmodelingand solidoperation 49 7 7 7 7 thethethe the c c c c onclusiononclusiononclusion onclusion s s s s andandand and prospectsprospectsprospects prospects .53.53.53 .53 山东科技大学硕士学位论文目录 7.1 conclusions 53 7.2 prospects.53 r r r r eferenceeferenceeference eference s s s s .54.54.54 .54 acknowledgementacknowledgementacknowledgement acknowledgement 565656 56 mmm m ainainain ain workworkwork work achievementsachievementsachievements achievements ofofof of thethethe the authorauthorauthor author duringduringduring during workingworkingworking working ononon on mastermastermaster master degreedegreedegree degree 575757 57 山东科技大学硕士学位论文绪论 1 1 1 1 1 绪论绪论绪论 绪论 1.1 三维几何造型技术理论概述三维几何造型技术理论概述三维几何造型技术理论概述 三维几何造型技术理论概述 三维几何造型的理论与技术是计算机科学、计算几何学与交互式图形显示技术的 完美结合。1971 年，英国的 a.r.forrest 首次提出了计算几何学的定义：计算几何学就 是形体的几何外形信息的计算机表示、 变换、 分析与综合。 形体的几何外形信息有两类 ： 几何信息和拓扑信息。几何信息规定了形体要素的空间位置与几何特性，而拓扑信息则 规定了形体要素之间的邻接关系或结构关系。经过近 10 多年的努力，国际上对三维几 何造型的理论与技术的研究无论在线框造型、曲面造型、实体造型等方面均取得了长足 的进展，在不断更新的 cad/cam 系统中取得了成功的应用。 常用的三维造型类型有线框造型、表面造型、实体造型，其中表面造型和实体造 型为当前各种主流 cad/cam 系统所采用。 1.线框造型 线框造型所关注的是形体边界上的棱线。线框造型开始于 60 年代初期，当时主要 是为了解决自动化绘图中的形体在计算机内部的表示问题，线框造型中的棱线、面框和 独立体框模型，就是这一时期三维几何造型的主流模型。线框造型对于平面形体是十分 有效的，但对于含有曲面的形体却有明显不足，因为含有曲面的形体其轮廓线并非都是 棱线。凡不为棱线的轮廓线都是不能确定的，它随着观察者视点和视角的变化而变化。 这类问题必须由表面造型来解决。 2.表面造型 若把在线框模型中边线包围的部分定义为面，则所形成的模型就是表面模型。表 面模型又分为平面模型和曲面模型，前者以多边形网格为基础，后者是以参数曲面块为 基础， 曲面模型技术主要研究曲面的表示、 分析和控制。 表面模型在线框模型的基础上 ， 增加了物体中面的信息，用面的集合来表示物体，而用环来定义面的边界。表面模型扩 大了线框模型的应用范围，能够满足面面求交、线面消隐、明暗色彩图、数控加工等需 要。 表面模型克服了线框模型的很多缺点，比较完整的定义了三维立体的表面，无法 解析和非解析的目标均可用表面模型来描述。但表面模型也存在一些不足，这主要是它 只能表示物体的表面边界，而没有表达出真实体属性，如质量、转动惯量、质心等。但 山东科技大学硕士学位论文绪论 2 在该模型中，只有一张张面的信息，物体究竟存在于表面的哪一侧，并没有给出明确的 定义，无法计算和分析物体的整体性质，也不能将这个物体作为一个整体去考察它与其 它物体相互关联的性质，如是否相交等。 3.实体造型 实体造型的概念早在 60 年代初期就已提出来了， 因当时在理论和技术上不甚成熟， 所以直到 70 年代才开始在 cad/cam 系统中获得应用。1973 年，英国的 i.c.braid 提 出，采用立方体、圆柱体和锥体等基本体素做“积木块”，通过交、并、差集合运算拼 合的方法构造复杂实体。以此为契机，实体造型的理论和技术迅速发展。80年代后， 一批实用性较强的实体造型系统相继推出。 实体模型是目前最高级的三维物体模型，它能完整地表示物体的所有形状信息。 可 以无歧义地确定一个点在物体外部、 内部或表面上， 这种模型能够进一步满足物性计算 、 有限元分析等应用的要求。 实体模型是在表面模型的基础上再定义物体是存在于面的哪一侧而建立的。 实体模 型具有关于立体的各种信息。因而可用来计算物体质量、质心、体积、转动惯量等物质 特性，还可以对物体进行实体剖切、有限元网格划分分析和优化设计等。实体模型被广 泛应用于 cad/cam 的各种领域中。作为立体的一种表示方法，实际上实体造型通常 并不是按点、线、面、体的过程来完成物体的造型，而是由一些基本体素(如圆柱体、 长方体、楔形体等等)的交、并、差组合来表示物体的形状，即所谓的体素几何造型。 实体造型技术既带来了算法的改进和未来发展的希望，也带来了数据计算量的极度 膨胀。在当时的硬件条件下，实体造型的计算及显示速度很慢，在实际应用中做设计显 得比较勉强。由于以实体模型为前提的计算机辅助工程（cae）本来就属于较高层次技 术，普及面较窄，反映还不强烈；另外，在算法和系统效率的矛盾面前，许多赞成实体 造型技术的公司并没有下大力量去开发它，而是转去攻克相对容易实现的表面模型技 术。实体造型技术也就此没能迅速在整个行业全面推广开。在上世纪的后 10 年里，随 着硬件性能的提高，实体造型技术又逐渐为众多 cad 系统所采用。11 1.2 实体造型的发展状况及表示方法实体造型的发展状况及表示方法实体造型的发展状况及表示方法 实体造型的发展状况及表示方法 实体造型是一个构造对象的过程，该对象具有一个实际实体的所有属性。实体造型 山东科技大学硕士学位论文绪论 3 通过基本体素，利用体素的集合运算或基本变形操作实现，完整地定义了三维物体的信 息，它包含物体的体、面、边和顶点的信息。 经过二十多年的探索，实体造型技术已经更加实用和成熟。把这一过程划分为两 个阶段：第一阶段是从 1973 年 braid 提出用体素进行机械设计的思想到 1982、1983 年 左右。这十年是奠基和成长阶段。实体表面大多用平面近似表示，数据结构采用翼边结 构，实体构造采用半空间表示、欧拉操作、csg、 b-rep、八叉树和扫描(sweeping)等 方法。第二阶段是从 1983 年到 1992 年，是应用和发展阶段。在国外，实体造型系统在 cad/cam 领域已形成一定的产业规模。在理论研究上提出了实体造型的正则集理论， 近几年又扩展为非正则集理论，用来描述非流形实体。一些拓扑学概念如流形、复形 (complex)、单元复形(cellcomplex)被引入到几何造型中。已不仅仅限于用平面构造实 体，广泛引入了二次曲面、自由型曲面和裁剪曲面。数据结构上相继出现了改进的翼边 结构、对称结构、半边结构、混合边结构和辐射边结构。特征造型的出现为实体模型向 产品模型的转化铺平了道路。特征造型是面向 cad/cam 集成的，向生产过程提供全 面完整的产品信息的造型方法。 它不仅包含产品的几何信息， 更包含了产品的特征信息 。 所谓特征是指产品描述的信息的集合，这主要包括形状特征、精度特征、技术特征和材 料特征。以特征为基础的造型方法是 cad 建模方法的一个里程碑，它可以充分提供制 造所需要的几何数据，从而可用于制造可行性方案的评价、功能分析、过程选择、工艺 过程设计等。把设计过程和生产过程紧密结合，有良好的发展前景。从实体造型的发展 上可以看出：这一技术与其它造型技术的联系越来越密切，各种造型技术相互融合、协 调发展己成为今后发展的大趋势。 随着实体造型理论的应用和发展，出现了几种典型的实体模型的表示方法，主要 有： 边界表示法 b_rep (boundary representation)、 实体几何构造法 csg(constructive solid geometry)、引例和参数表示法(instance and parameterized shape)、扫描表示法(sweep)、 分割表示法、d-rep (decomposition preseration)、单元分解法(cell decomposition)、空 间占据法(spatialoccupancy enumeration)等。其中最常用的表示方法有两种：csg 和 b_rep。 1. 构造体素法(（constuctive solidgeometry，简称 csg）) csg 建模方法是先对基本体素（如长方体、圆柱体、圆锥体、球体等）建模，然 后用实体的布尔运算把体素组合成复杂的形体。 实体的布尔运算是任何实体造型系统必 不可少的组成部分，它完成实体间的交、并、差等布尔操作。 山东科技大学硕士学位论文绪论 4 形体的 csg 表示可看成是一棵有序的二叉树，其终端节点或是体素，或是刚体运 动的变换参数。非终端节点或是正则的集合运算或是刚体的几何变换，这种运算或变换 只对其紧接着的子节点(子形体)起作用。每棵子树(非变换叶子节点)表示了其下两个节 点组合的结果，树根表示了最终的节点，即整个形体。csg 树可定义为： = csg 树的叶结点为基本体素， 中间结点为集合运算符号或经集合运算生成的中间形 体，树根为生成的最终形体，可见 csg 树完整地记录了一个形体的生成过程。它造型简 便， 存储的信息量少， 所占内存量也少。 但是它不能查询到形体较低层次的信息，如面 、 边和顶点等有关的几何信息和拓扑信息。 2.边界表示法(b-rep) b-rep 边界法就是利用形体边界上的点、线、面及其拓扑关系来描述三维实体，即 一个物体可以通过包容它的面来表示,而每一个面又可通过构成此面的边描述,边通过 点,点通过三个坐标值来定义。该表示法着重于形体边界的细节，用形体边界所围成的 封闭空间来定义形体。任意形体的边界是由有限个称为面的元素构成的；而每个面又可 用它的边界，一组构成封闭环的边来表示；边可以由它的两个端点唯一确定；点是由其 在三维空间中的坐标来定义。这种模型有利于进行以点、线、面为单位的儿何计算和用 于形体构形的欧拉算子操作，它既取了线框模型和表面模型的长处，又弥补了它们的不 足。 边界表示法的优点是能设计出一套合适的数据结构，方便的检索面、边和顶点之 间的连接关系，有利于生成和绘制线框图、投影图，有利于计算几何特性，有利于二维 绘图功能衔接生成工程图；缺点是由于它的核心为面，对几何物体的整体描述能力差， 无法提供实体生成过程的信息。 实体造型模块中形体的输入主要采用 csg 及扫描两种方法，即采用系统提供的基 本体素及经扫描(拉伸或旋转)生成的体素，通过交、并、差集合运算生成新的实体。实 体在计算机内部采用边界表示法显示和处理实体，用八叉树法进行有关体积方面的计 算。6 山东科技大学硕士学位论文绪论 5 1.3 论文的选题以及主要研究内容论文的选题以及主要研究内容论文的选题以及主要研究内容 论文的选题以及主要研究内容 三维造型是最基本的、 应用最广泛的计算机辅助技术， 也是实施其他各种 cad/cae 技术的必要前提。cad/cam 系统的开发主要可分为三种方式：基于 cad/cam 软件平台的 开发，如 acis，parasolid 等；基于某个通用 cad 系统的二次开发，如基于 autocad 软 件的二次开发；完全自主版权的开发，一切从底层做起。无论是基于平台的开发，还是 基于某个系统的二次开发， 现在国际、 国内大型系统采用的大都是以 acis 和 parasolid 作为造型内核。蓝光数字化平台是一个具有完全独立自主版权的平台级软件，它集 cad、 gis、mis 和三维可视化于一体，是一个功能十分强大的 cad 平台，本文就是基于这个 平台进行研究与开发的。 三维造型