计算机图形学(孙家广第三版)-第3章(4)

1、Department of Mathematics3.7归类求交归类求交几何造型中，通常利用集合运算（并、交、差运算）实现复杂形体的构造。集合运算需要大量的求交运算。如何提高求交的实用性、稳定性、速度、精度等，对几何造型系统至关重要。历史上的观念变化:简单体素的精确求交， NURBS统一求交 - 归类求交Department of Mathematics3.7.1求交分类简介求交分类简介多面体模型这种模型的求交计算主要是线段和平面的求交，求交问题的解决相对简单。多面体模型的缺点是明显的。它只能近似表示形体，同时，复杂形体表面的离散会带来巨大的数据量。CSG模型在这种模型中，形体通过基本体素的组

2、合来实现。二次曲面的求交是这些造型系统中必不可少的。Department of Mathematics当前的几何造型系统，大多采用精确的边界表示模型。在这种表示法中，形体的边界元素和某类几何元素相对应，它们可以是直线、圆（圆弧）、二次曲线、Bezier曲线、B样条曲线等，也可以是平面、球面、二次曲面、Bezier曲面、B样条曲面等，求交情况十分复杂。二次曲面与各种自由曲面并存的混合表示模型的采用，导致了归类求交思想的产生。Department of Mathematics“无处不在的求交”：GEMS实例！Department of Mathematics实体建模步骤剖析：草图拉伸、填“体、面、

3、环、点”结构打孔，直径为20cm: 圆柱与立方体的所有面求交线，成环、重填“体面环点”结构打第二个孔，直径为18cm: 圆柱与立方体的所有面、及第一个圆柱面求交线，成环、重填“体面环点”结构Department of Mathematics3.7.2归类求交策略归类求交策略几何造型系统中，用到的几何元素：(25种)点：3D点。线：3D直线段、二次曲线(包括圆弧和整圆、椭圆弧和椭圆、抛物线段、双曲线段)、 Bezier曲线 (有理和非有理)、B样条曲线、NURBS曲线。面：平面、二次曲面(包括球面、圆柱面、圆锥/台面、双曲面、抛物面、椭球面和椭圆柱面)、Bezier曲面 (有理和非有理)、B样条

4、曲面、NURBS曲面。Department of Mathematics将几何元素进行归类，利用同一类元素之间的共性来研究求交算法。同时对每一类元素，在具体求交算法中要考虑它们的特性，以提高算法的效率，发挥混合表示方法的优势。求交方法可分为：点点、点线、点面、线线、线面六种。Department of Mathematics清华大学的GEMS5.0系统采用点、直线、平面、二次曲线等简单的几何元素之间的求交直线、平面、二次曲线等简单的几何元素与二次曲面之间的求交三维点与二次曲线/曲面之间的求交三维点与自由曲线、曲面之间的求交Department of Mathematics二次曲面与二次曲面之间

5、的求交直线自由曲线/自由曲面的求交平面自由曲线/自由曲面的求交自由曲线自由曲线的求交自由曲线自由曲面的求交二次曲线自由曲线的求交 二次曲线自由曲面的求交Department of Mathematics自由曲面自由曲面的求交二次曲面自由曲线的求交二次曲面自由曲面的求交96年10月98年10月，博士后1人，博士生5人 （左、雍、周、魏、杨）。300个求交函数。Department of Mathematics3.7.3基本的求交算法基本的求交算法1. 线与线的求交计算线与线的求交计算（1）二次曲线与二次曲线求交）二次曲线与二次曲线求交（2）二次曲线与）二次曲线与NURBS曲线求交曲线求交（3）N

6、URBS曲线与曲线与NURBS曲线求交曲线求交Department of Mathematics3.7.3基本的求交算法基本的求交算法2. 线与面的求交计算线与面的求交计算（1）二次曲线与二次曲线求交）二次曲线与二次曲线求交（2）二次曲线与）二次曲线与NURBS曲线求交曲线求交（3）NURBS曲线与曲线与NURBS曲线求交曲线求交Department of Mathematics3.7.3基本的求交算法基本的求交算法曲面曲面求交的基本方法主要有:代数方法几何方法离散方法跟踪方法Department of Mathematics1代数方法利用代数运算，特别是求解代数方程的方法求出曲面的交线。根据

7、参与求交的两曲面的表示形式的不同，可以把求交分为三种情况。Department of Mathematics隐式表示和参数表示的曲面求交，通过把参数方程代入隐式方程的方法，可以将交线表示为g(u,v)=0的形式。此时得到的交线方程是平面代数曲线方程，可根据平面代数曲线理论的方法求解交线。两个曲面都是参数表示的情形，只需要将其中之一隐式化，然后用前面的方法求解。而参数多项式或有理多项式曲面的隐式化通过消元来实现。Department of Mathematics两个曲面都是隐式曲面。一种方法是将其中一个曲面参数化，然后用第一种情况来求解。但是，一般情况下这种参数化很困难，对于某些情况可以采用另外

8、的方法计算参数化的曲面。代数法的弱点是对误差很敏感这是因为代数法经常需要判别某些量是否大于零、等于零或小于零，而在计算机中的浮点数近似表示的误差常常会使这种判别出现错误。Department of Mathematics代数法实例：园与椭圆求交，化为求解4次方程，有公式解。园与圆环求交，化为求解8次方程，迭代求解。8次方程达到求解，不稳定。Department of Mathematics2几何方法利用几何的方法，对参与求交的曲面的形状大小、相互位置以及方向等进行计算和判断，识别出交线的形状和类型，从而可精确求出交线。几何求交适应性不是很广，一般仅用于平面以及二次曲面等简单曲面的求交Depar

9、tment of Mathematics对于一些交线退化或相切的情形，交线往往是点、直线或圆锥曲线，用几何方法求交可以更加迅速和可靠。Department of Mathematics几何法实例：平面与圆柱求交1. 平面、圆柱参数的合法性检查2. 平面变换到圆柱的局部坐标系 3. 几何求交： 如果平面与圆柱平行，不交或交于两条直线 如果平面与圆柱垂直，不交或交于一个圆 Department of Mathematics 否则，交于椭圆或椭圆弧 先求出平面与无限长圆柱交得的椭圆 (在圆柱的局部坐标系下) 根据椭圆在长轴上的两点与圆柱的 关系，确定交于点、椭圆、椭圆弧等Department of

10、Mathematics3离散方法离散方法求交是利用分割的方法，将曲面不断离散成较小的曲面片，直到每一子曲面片均可用比较简单的面片，然后用这些简单面片求交得一系列交线段，连接这些交线段即得到精确交线的近似结果。Department of Mathematics离散求交一般包括下面的过程：用包围盒作分离性检查排除无交区域；根据平坦性检查判断是否终止离散过程；连接求出的交线段作为求交结果。由于Bezier曲面，B样条曲面具有离散性质，使得它们最适合于离散法求交。Department of Mathematics缺点：离散法求出的交线逼近精度不高。如果要求的精度较高，需要增加离散层数。这将大大增加了数

11、据储存量和计算量。处于不同离散层数的相邻子曲面片，由它们产生的交线段可能会出现裂缝。Department of Mathematics4跟踪方法通过先求出初始交点，然后从已知的初始交点出发，相继跟踪计算出下一交点，从而求出整条交线的方法。跟踪法的本质是构造交线满足的微分方程组，先求出满足方程组的某个某个初值解，通过数值求解微分方程组的方法来计算整个交线。Department of Mathematics跟踪方法在计算相继交点的时候，利用了曲面的局部微分性质，一般采用数值迭代的方法求解，使得计算效率较高。Department of Mathematics跟踪法求交中考虑的主要问题包括：如何求出初

12、始交点并保证每一交线分支都有初始交点被求出；如何计算奇异情况下的跟踪方向以及合理选取跟踪的前进步长；如何处理相切的情况。Department of Mathematics跟踪法实例：MAF方法曲线曲面求交近似交点，切线求交，投影曲面曲面求交球变换中点变换Department of Mathematics3.8 实体造型系统简介实体造型系统简介在早期开发的实体造型系统中，值得提及的是剑桥大学的BUILD-1系统。该研究小组的一部分人组建了Shape Data公司，并开发出实体造型系统Romulus，Romulus孕育了最著名的两个实体造型系统开发环境：Parasolid和ACIS。3.8.1 P

13、arasolid系统3.8.2 ACIS系统Department of Mathematics3.8.1 Parasolid的主要功能的主要功能Parasolid有较强的造型功能，但是只能支持正则实体造型。主要功能包括：1Parasolid采用自由曲面和解析曲面的混合表示，共提供了10种标准的曲面类型和7种标准的曲线类型，并且是完全集成的。2Parasolid可用简单的方法生成复杂的实体，实体之间可有多种方式的操作。3.用户可用自己理解的工程特征进行设计4.能够提供非拓扑和非几何数据，称为属性Department of Mathematics 属性包括系统定义的属性和用户定义的属性两种，且依附

14、于模型实体（Entities）。5.支持局部操作。包括：改变面几何、变换面几何、使面成锥形、摆动面、扫描面及删除面。提供了多半径、变半径的过渡功能。Department of MathematicsParasolid的模型结构的模型结构模型实体包括三种：拓扑、几何和相关数据Department of Mathematics1拓扑实体（1）体（Body）：Parasolid模型通常包括一个或多个体（Bodies）（2）壳（Shell）：壳是实体（Solid）和空气之间封闭的边界（3）面（Face）、边（Edge）和顶点（Vetex）（4）翼（Fin）：翼（Fins）表示一条边的一侧每一条边有一个

15、左翼和一个右翼（5）环（Loop）：由一个面上封闭的翼组成。Department of Mathematics（7）装配件（Assembly）和实例（Instance）：一个装配件是一个对其它装配件或体的指针的集合。每一个指针被称为一个实例。（8）世界（World）：世界是一个独特的实体（Entity），它包含模型中的所有的体（Bodies）和装配件（Assemblies）。Department of Mathematics2几何实体（Entities）点。主要依附于顶点，它们也依附于体和装配件作为构造几何。曲线。主要依附于面，但也依附于体和装配件作为构造几何。曲面。主要依附于模型的边或翼，但

16、也依附于体和装配件作为构造几何。变换。变换表示几何操作：平移、修剪等，主要依附于实例。Department of Mathematics3相关的数据实体（1）特征（feature）：是实体的集合，依附于体和装配件。（2）表（List）：提供了结构化数据的方法，它们一般独立使用，也可依附于体和装配件。表有三种：整数表（Integer）、实数表（Real）和标志表（Tag）。（3）属性（Attribute）：是用于附着信息到实体的数据结构。Department of MathematicsParasolid的界面的界面Parasolid有两个界面。一个在造型器顶部，称为核心界面（KI），通过KI，

17、用户可以造型、操作对象和控制造型器。另一个在造型器下部，它包括三个部分：Frustrum、GO（Graphics Output）和FG（Foreign Geometry）。Department of MathematicsDepartment of MathematicsFrustrum：Frustrum是用户写的函数集，当数据被存储、提取，或进行内存分配时，它们被核心调用。图形输出（GO）：图形输出（GO）函数也是被用户写的。从这些函数输出的通是要求核心（Kernel）绘图的指令。外部几何（FG）：Parasolid通过FG模块界面访问用户定义的曲线、曲面，使得用户可以使用Parasolid

18、造型出的曲线、曲面及标准的Parasolid曲线、曲面类型。Department of Mathematics3.8.2 ACIS系统系统ACIS是由美国Spatial Technology于1990年首次推出。ACIS的重要特点是支持线框、曲面、实体统一表示的非正则形体造型技术，能够处理非流形形体。ACIS产品采用了组件技术，其核心是几何造型器（Geometric Modeler），还包括一些可与核心集成的组件，称为外壳（Husk）。Department of MathematicsACIS的结构的结构参数曲线和曲面求值器参数曲线和曲面的界面类对象方法ACICS核心API图3.4.3 ACI

19、S核心结构参数曲线和曲面求值器参数曲线和曲面的界面类对象方法ACICS核心API图3.4.4 与ACIS核心集成均衡的外壳可视化2D投影约束动画Department of Mathematics核心只提供一些基本的几何造型功能，其它高级功能在外壳中提供。外壳可以是Spatial Technology公司提供的，如高级渲染（Advanced Rendering）外壳、三维工具箱（3D Toolkit）外壳等，也可以是用户开发的。Department of MathematicsACIS的模型表示的模型表示ACIS模型表示由各种属性（Attributes）、几何（Geometries）和拓扑（Topologies）成。几何是指模型的物理描述，如点、曲线、曲面、直线、椭圆等；拓扑是指各种几何实体在空间的关联，如体、壳、面、环、边和顶点等；属性依附于模型实体。ACIS是用C+开发的，C+类的层次如图所示。Department of Mathematics用户类BODYLUMPSHELLSUBSHE