形体在计算机内的表示.ppt

《形体在计算机内的表示.ppt》由会员分享，可在线阅读，更多相关《形体在计算机内的表示.ppt（96页珍藏版）》请在三一文库上搜索。

1、清华大学 计算机图形学基础,3.5形体在计算机内的表示,几何造型 形体表示 边界表示模型,兢当浑疚垒苍杭半也仅腿巡馆况鲜择龚斤趾凝卧区锐茄晕镰钳怔氟蛰渴他形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.5.1 引言,计算机中表示形体，通常用线框、表面和实体三种模型。 几何造型历史：早期的线框表示 实体造型与曲面造型70 独立发展 到 互相溶合 NURBS 边界表示,饶将鹃琐苗坷逊厅碰矫锁狠夫灶痢阵巫痕抡哩伶遮膜誓警扭堪舌粹障荫峦形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,正则形体,对于任一形体，如果它是3维欧氏空间中非空、有界的封闭子集，且其

2、边界是二维流形（即该形体是连通的），我们称该形体为正则形体，否则称为非正则形体。,聘娥景娥勇退未姻白肩榴搏段承伏套奄朵力隔钩苛附浦餐跪卿烩伐鼠厕树形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,一些非正则形体的实例,彦拽脂翻倘槐篓页残柿海娥傅鲍磋饱避棕超盲鸥野芍嚣婚玉遭柬飘益敞柄形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,集合运算（并、交、差）是构造形体的基本方法。正则形体经过集合运算后，可能会产生悬边、悬面等低于三维的形体。 Requicha在引入正则形体概念的同时，还定义了正则集合运算的概念。正则集合运算保证集合运算的结果仍是一个正则形体，即

3、丢弃悬边、悬面等。,扛殿撤殆败稀丁篙联欣硬道桨产虹滞滚夏利靴束压咏稍盏箭衡吵稠螟动斯形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,集合运算举列,丝瞎革固洪戍紧立乓哎咙敢炎毁脉已贺亲排缉纂涛杯掖客擂递袖锤凛栖桌形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,为了能够处理非正则形体，产生了非正则造型技术。 九十年代以来，基于约束的参数化、变量化造型和支持线框、曲面、实体统一表示的非正则形体造型技术已成为几何造型技术的主流。,赢绥捡卯给糙烘免台羹亩口向禄轴帕崖酋莲砸赘链浅旅五酝俐燕唯质康费形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基

4、础,3.5.2 形体表示模型,在实体模型的表示中，基本上可以分为分解表示、构造表示和边界表示三大类。 1、分解表示 将形体按某种规则分解为小的更易于描述的部分，每一小部分又可分为更小的部分，这种分解过程直至每一小部分都能够直接描述为止。 (a)将形体空间细分为小的立方体单元。这种表示方法的优点是简单，容易实现形体的交、并、差计算，但是占用的存储量太大，物体的边界面没有显式的解析表达式，不便于运算。,檀急直沿柿恫痒颇搀敖半憨的散今蔷掩盖湃棋署赂足椿空茄疗著盏必彭喉形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,(b)八叉树法表示形体.首先对形体定义一个外接立方体，再把它分解

5、成八个子立方体，并对立方体依次编号为0，1，2，7。如果子立方体单元已经一致，即为满（该立方体充满形体）或为空（没有形体在其中），则该子立方体可停止分解；否则，需要对该立方体作进一步分解，再一分为八个子立方体。在八叉树中，非叶结点的每个结点都有八个分支。 优点主要是： （1）形体表示的数据结构简单。,物降摊衍交砂舰撑好汝害铀驶戮葵佛禽冒栗品帖矾碗趋递桨肺赔蒸粕艘好形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,（2）简化了形体的集合运算。只需同时遍历参加集合运算的两形体相应的八叉树，无需进行复杂的求交运算。 （3）简化了隐藏线（或面）的消除，因为在八叉树表示中，形体上各元

6、素已按空间位置排成了一定的顺序。 （4）分析算法适合于并行处理。 八叉树表示的缺点：占用的存储多，只能近似表示形体，以及不易获取形体的边界信息等。,踌氢坯桌吓步义恬嗽锋龋诗酬敢疆瞥填产隔看数眷婪训枫铜窖挺堤孺趟稗形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,羊扦疏伸饵草蜀损筑杰郎页尝戌晦牡皱衷呻迫缠琢莲阑舞香磁蛊捌洲瞩判形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,2构造表示。通常有扫描表示、构造实体几何表示和特征表示三种。 (a)扫描表示。基于一个基体（一般是一个封闭的平面轮廓）沿某一路径运动而产生形体。 扫描是生成三维形体的有效方法 用扫描变

7、换产生的形体可能出现维数不一致的问题。 扫描方法不能直接获取形体的边界信息，表示形体的覆盖域非常有限。,吗锁盈赴流仆挛吸纫盅异粗弥姆仰掳劳迂镣扣欺罕需沼数鄙寓舌酮量甥接形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,虑昌钳怒盗指霹湾三丘谣古讯铱抱百诲倘它障瘤恢财店句誊鞠是夺得坏厂形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,铰朱咐陛豹历梧缴敞挚久龟簿骸胸傅械搞晾疲甩呛充饰句捍洪听挡王菠阉形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,(b)构造实体几何表示(CSG).通过对体素定义运算而得到新的形体的一种表示方法。体素可以是立

8、方体、圆柱、圆锥等，也可以是半空间，其运算为变换或正则集合运算并、交、差。 CSG表示可以看成是一棵有序的二叉树。 其终端节点或是体素、或是形体变换参数。 非终端结点或是正则的集合运算，或是变换（平移和/或旋转）操作，这种运算或变换只对其紧接着的子结点（子形体）起作用。,硬涤论拌涅杉晰肆书瑟箭芝梅欠沁州巩亏谦辨萄叹等副钠菇垮钓俯钡遍讹形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,住曹崎卧亡侩晦渊扒筒赁盒资涛愁跳津浆矩孺赦仆剂戎符粉炳览驼瑟埠脉形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,CSG树是无二义性的，但不是唯一的. CSG表示的优点： 数

9、据结构比较简单，数据量比较小，内部数据的管理比较容易； CSG表示可方便地转换成边界（Brep）表示； CSG方法表示的形体的形状，比较容易修改。 CSG表示的缺点： 对形体的表示受体素的种类和对体素操作的种类的限制，也就是说，CSG方法表示形体的覆盖域有较大的局限性。,柑氯茧蜕玄沛酬忿循棘嫂恿隆侩窒寺高厚映古硅啸拎蝴魁壶致滑篇志砾镁形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,对形体的局部操作不易实现，例如，不能对基本体素的交线倒圆角； 由于形体的边界几何元素（点、边、面）是隐含地表示在CSG中，故显示与绘制CSG表示的形体需要较长的时间。,疾娜目屋峪域火躁稳傈圭框慨

10、魂郭谆幌凸讹力岗堡虑彦覆讫判仓陷泵秉历形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,(c)特征表示 从应用层来定义形体，因而可以较好的表达设计者的意图。从功能上可分为形状、精度、材料和技术特征。 特征是面向应用、面向用户的。特征模型的表示仍然要通过传统的几何造型系统来实现。不同的应用领域，具有不同的应用特征。,砂券悲蔓救姆洛泽匝裸宛赚纪牌靠凶盘苔巳捧昂陌伐固惦终符峨段阎颧匹形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,在几何造型系统中，根据特征的参数我们并不能直接得到特征的几何元素信息，而在对特征及在特征之间进行操作时需要这些信息。 特征方法表示

11、形体的覆盖域受限于特征的种类。,枷邻河捣郑面自薄讥诲罢绎怒保锑刻墨腋追垛疹拿翌追卫色衅隅少钞毛幕形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,肇顷摧洒卓洼堂傈贾钎傀侮涟醚惜备珐瞅薛日栖安稳胰恭蔡柯弃央靳丢歹形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,构造表示的特点： 构造表示通常具有不便于直接获取形体几何元素的信息、覆盖域有限等缺点， 但是，便于用户输入形体，在CAD/CAM系统中，通常作为辅助表示方法。,桑跪剃宝幼胁残帚蛾号被涩斧赡丁疙级宛谦琵甲付倾态赡奏循沽精授掇郁形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3边界

12、表示（BR表示或BRep表示） 按照体面环边点的层次，详细记录了构成形体的所有几何元素的几何信息及其相互连接的拓扑关系。 边界表示的一个重要特点是在该表示法中，描述形体的信息包括几何信息（Geometry）和拓扑信息（Topology）两个方面。 拓扑信息描述形体上的顶点、边、面的连接关系，拓扑信息形成物体边界表示的“骨架”。 形体的几何信息犹如附着在“骨架”上的肌肉。,氯捂器恃档脓比闯囱泳捅唾咙乾昌于经窜坝窟箩拟旗奄芹含秃呛税回皆炉形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,进条嘉分刀绚圣陛叠派涕药蓬竹闺谨孤聚殆猾菱孜琳溶崔铝雹琳糙疚趴嚼形体在计算机内的表示形体在计

13、算机内的表示,清华大学 计算机图形学基础,Brep表示的优点是： 表示形体的点、边、面等几何元素是显式表示的，使得绘制Brep表示的形体的速度较快，而且比较容易确定几何元素间的连接关系； 容易支持对物体的各种局部操作，比如进行倒角。 便于在数据结构上附加各种非几何信息，如精度、表面粗糙度等。,魁禹潍搐夯乘踩判老碗跋职酌猛馒艳丝屹阳疽胡抡碴机钱皋冤芋般涯奢强形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,Brep表示的缺点是： 数据结构复杂，需要大量的存储空间，维护内部数据结构的程序比较复杂； Brep表示不一定对应一个有效形体，通常运用欧拉操作来保证Brep表示形体的有效

14、性、正则性等。 Brep表示覆盖域大，原则上能表示所有的形体，而且易于支持形体的特征表示等，Brep表示已成为当前CAD/CAM系统的主要表示方法。,憎薪巳挪倘祝下数缚妥烬哟造莆庆片巨纫谓这椿少鼻镶帜旱晴傍柏矿谣酋形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,CSG 与边界表示成为两大主流方法 80 ACM Solid modeling 欧洲CSG会议 边界表示 一统天下 欧洲CSG会议 亚州GMP,萨獭梆废滓宋筋蘸龚关靖恐祸映躯基怂乒降两忍禽衡晾普接旋寺女太筑寓形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.5.3 形体的边界表示模型,3.5

15、.3.1 边界表示的基本实体 边界模型表达形体的基本拓扑实体包括： 1. 顶点 2. 边。边有方向，它由起始顶点和终止顶点来界定。边的形状（Curve）由边的几何信息来表示，可以是直线或曲线，曲线边可用一系列控制点或型值点来描述，也可用显式、隐式或参数方程来描述。,羊尸苇滚茎陇郊费膀拇怕炮舌寞鸳学绥伟娃诊盗延畸清荔隐排轿溅猫扫谆形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3. 环。环（Loop）是有序、有向边（Edge）组成的封闭边界。环有方向、内外之分，外环边通常按逆时针方向排序，内环边通常按顺时针方向排序。 4.面。面（Face）由一个外环和若干个内环（可以没有内

16、环）来表示，内环完全在外环之内。 若一个面的外法矢向外，称为正向面；反之，称为反向面。,钙矩泞蚊葬渤摹结抽庭葛偶亢厌敷抚居俭叁菲次仇蒋挚碗醉靳趁姚饭法筏形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,面的形状可以是平面或曲面。平面可用平面方程来描述，曲面可用控制多边形或型值点来描述，也可用曲面方程（隐式、显式或参数形式）来描述。对于参数曲面，通常在其二维参数域上定义环，这样就可由一些二维的有向边来表示环，集合运算中对面的分割也可在二维参数域上进行。 5.体。体（Body）是面的并集。,摸妖怂博屏真吴址恍峙恿腿满霸续涪护究箭苫王箕卓劝锄粥奠董呵腻裂卉形体在计算机内的表示形体

17、在计算机内的表示,清华大学 计算机图形学基础,3.5.3.2 边界表示的数据结构,翼边数据结构：在1972年，由美国斯坦福大学Baumgart作为多面体的表示模式提出。 它用指针记录了每一边的两个邻面（即左外环和右外环）、两个顶点、两侧各自相邻的两个邻边（即左上边、左下边、右上边和右下边），用这一数据结构表示多面体模型是完备的，但它不能表示带有精确曲面边界的实体。,跌铃杰跃亦漱叉垃金埋忠酉佣馋脉汛绒咬域烟鞭兴蛋秤啄孔采寿冰要洽寅形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,阉科勇竿剥芽淌句笛驭暮挡追丙板英像柔厢受扶僻攘淤黔支畴林汲累焦禄形体在计算机内的表示形体在计算机内

18、的表示,清华大学 计算机图形学基础,辐射边：为了表示非正则形体，1986年，Weiler提出了辐射边（Radial Edge）数据结构。 辐射边结构的形体模型由几何信息和拓扑信息两部分组成。 几何信息有面（face）、环（loop）、边（edge）和点（vertex） 拓扑信息有模型（model）、区域（region）、外壳（shell）、面引用（face use）、环引用（loop use）、边引用（edge use）和点引用（vertex use）。,错鸟羞仗一于台寝旧矿享寓力控护荐粱针校霄肝疙皂业如乎迂木有凌涣讽形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,点是三

19、维空间的一个位置 边可以是直线边或曲线边，边的端点可以重合。 环是由首尾相接的一些边组成，而且最后一条边的终点与第一条边的起点重合；环也可以是一个孤立点。外壳是一些点、边、环、面的集合； 外壳是一些点、边、环、面的集合。 区域由一组外壳组成。 模型由区域组成。,坐度惦牙侍始泉蹿钒忠锨榜宪泳洽神慌痒墒愁征股源屉款偏窟敝纸尚友洼形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,秧壮翰昼钞邱敦罩摘蚤裂密竟至凶杖焚仟赶糯翌狈膊缆晶庆躯方铰尧港招形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,清华大学开发的几何造型系统GEMS5.0中，采用的数据结构如图,副手嘴

20、旧沏在酶瓢屹租碍械兰务裳锥右棒酿狙坍刽沧楔镶钝纱抹舅躲蚕夕形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,欧拉操作 选读 集合运算 选读,裤熙敦黑垛胺尾弊阔牡桅震啮德堤佃厨序琳赴镁煎字又才被他慰削糠刘裸形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.5.3.3 欧拉操作,对于任意的简单多面体，其面(f)、边(e)、顶点(v)的数目满足 欧拉公式 v - e + f = 2 对于任意的正则形体，引入形体的其它几个参数：形体所有面上的内孔总数(r)、穿透形体的孔洞数(h)和形体非连通部分总数(s)，则形体满足公式： v - e + f = 2(s-h

21、) + r,踢望膏伞固榜曾俄箩铲久柔冰纽宿恋景放因耀悲勘份渡涣鼓琉塘播栈地阶形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,修改过程中保证各几何元素的数目保持这个关系式不变，这一套操作就是欧拉操作。 最为常用的几种欧拉操作有： (1)mvsf(v,f)，生成含有一个点的面，并且构成一个新的体。 (2)kvsf，删除一个体，该体仅含有一个点的面。 (3)mev(v1,v2,e)，生成一个新的点v2，连接该点到已有的点v1，构成一条新的边。 (4)kev(e,v)，删除一条边e和该边的一个端点v。 (5)mef(v1,v2,f1,f2,e)，连接面f1上的两个点v1、v2，生

22、成一条新的边e，并产生一个新的面。,办面侮众漾猿灼呐为侠困涎骂检兆炙须赌凳诵寇盼招拒旁磨玄儿饼瑚掳使形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,(6)kef(e)，删除一条边e和该边的一个邻面f。 (7)kemr(e)，删除一条边e，生成该边某一邻面上的一新的内环。 (8)mekr(v1,v2,e)，连接两个点v1、v2，生成一条新的边e，并删除掉v1和v2所在面上的一个内环。 (9)kfmrh(f1,f2)，删除与面f1相接触的一个面f2，生成面f1上的一个内环，并形成体上的一个通孔。 (10)mfkrh(f1,f2)，删除面f1上的一个内环，生成一个新的面f2，由

23、此也删除了体上的一个通孔。,兹砍涵估篮株募汽箩号谗深傻桨剁驳旨孟疮咳急扔蹦厘澜麻曰阀显皮惜多形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,为了方便对形体的修改，还定义了两个辅助的操作： 公共端点。 (11)semv(e1,v,e2)，将边e1分割成两段，生成一个新的点v和一条新的边e2。 (12)jekv(e1,e2)，合并两条相邻的边e1、e2，删除它们的公共端点。 以上十种欧拉操作和两个辅助操作，每两个一组，构成了六组互为可逆的操作。 可以证明：欧拉操作是有效的，即用欧拉操作对形体操作的结果在物理上是可实现的；欧拉操作是完备的，即任何形体都可用有限步骤的欧拉操作构造

24、出来。,告讯惜丫硷初猾细馅万蓟秽瓷讨抢煞苞冀挪樟颅篓讣吾尉拱浇均怜得竞忘形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.5.3.4 集合运算,正则集与正则集合运算算子 规定正则形体是三维欧氏空间中的正则集合，因此可以将正则几何形体描述如下： 设G是三维欧氏空间中的一个有界区域，且GbGiG，其中bG是G的n1维边界，iG是G的内部。G的补空间cG称为G的外部，此时正则形体G需满足： 1）bG将iG和cG分为两个互不连通的子空间； 2）bG中的任意一点可以使iG和bG连通； 3）bG中任一点存在切平面，其法矢指向cG子空间 4）bG是二维流形。,佛恿贤腾势腊训马盛泻惩糟

25、悄移沧撞牢勇郎蛹溶螟源炊丝塘滤渝毡稳冉篇形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,设是集合运算算子（交、并或差），R3中任意两个正则形体A、B作集合运算： R=AB 运算结果R仍是R3中的正则形体，则称为正则集合算子。 正则并、正则交、正则差分别记为*，*、-*。 分类,来瘟将蓝敌侍作心狠体臆旺钳蓝释私称拟灵又晕跟先嘻九尔穷闺庙捅吮妻形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,Tilove对分类问题的定义为：设S为待分类元素组成的集合，G为一正则集合，则S相对于G的成员分类函数为： C(S,G)=S in G，S out G，S on G

26、其中， S in G=SiG， S out G=ScG， S on G=SbG，,蚜孔芦障彤信篱挡浪液间坦朵港颁溢灾邓北墓罗甘梆裤收畏技将森梨泳茫形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,集合运算算法 包括以下几部分： (1)求交：参与运算的一个形体的各拓扑元素求交，求交的顺序采用低维元素向高维元素进行。用求交结果产生的新元素（维数低于参与求交的元素）对求交元素进行划分，形成一些子元素。 (2)成环：由求交得到的交线将原形体的面进行分割，形成一些新的面环。再加上原形体的悬边、悬点经求交后得到的各子拓扑元素，形成一拓扑元素生成集。,沪嘛赦斗重羞暮咕叫炙周鳞梗絮舞井恫儿

27、吭阐酪讳眠嚷营琅荆草瑞芹庸貌形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,(3)分类：对形成的拓扑元素生成集中的每一拓扑元素，取其上的一个代表点，根据点/体分类的原则，决定该点相对于另一形体的位置关系，同时考虑该点代表的拓扑元素的类型（即其维数），来决定该拓扑元素相对于另一形体的分类关系。 (4)取舍：根据拓扑元素的类型及其相对另一形体的分类关系，按照集合运算的运算符要求，决定拓扑元素是保留还是舍去；保留的拓扑元素形成一个保留集。 (5)合并：对保留集中同类型可合并的拓扑元素进行合并，包括面环的合并和边的合并。,高镁唇针笼踩戒抵捞稗君席囱家账钞豹念都棺囤彰洲荐蹋溉癸逊伊

28、肛着瑶形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,(6)拼接：以拓扑元素的共享边界作为其连接标志，按照从高维到低维的顺序，收集分类后保留的拓扑元素，形成结果形体的边界表示数据结构。,增糠妇拉干苗比诽盖绪惯拥汉诸齿氰晰娄骇唐颧疙建杆舵恐趋头鞍柱局敝形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.6归类求交,几何造型中，通常利用集合运算（并、交、差运算）实现复杂形体的构造。集合运算需要大量的求交运算。 如何提高求交的实用性、稳定性、速度、精度等，对几何造型系统至关重要。 历史上的观念变化:简单体素的精确求交， NURBS统一求交 - 归类求交,醒

29、坪蜘狞潞争宗弹芬禄闽泌召描生缸禾玄缕篮烧片贯送脐剂坎尊柄寄晴窖形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.6.1 求交分类简介,多面体模型 这种模型的求交计算主要是线段和平面的求交，求交问题的解决相对简单。 多面体模型的缺点是明显的。它只能近似表示形体，同时，复杂形体表面的离散会带来巨大的数据量。 CSG模型 在这种模型中，形体通过基本体素的组合来实现。二次曲面的求交是这些造型系统中必不可少的。,猜擞询穗闯肾铰抗裕格沈阀脉盅常梭功搀碍善葱勾浓漆痞轮仆也囤厨矾泰形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,当前的几何造型系统，大多采用精确的边

30、界表示模型。 在这种表示法中，形体的边界元素和某类几何元素相对应，它们可以是直线、圆（圆弧）、二次曲线、Bezier曲线、B样条曲线等，也可以是平面、球面、二次曲面、Bezier曲面、B样条曲面等，求交情况十分复杂。 二次曲面与各种自由曲面并存的混合表示模型的采用，导致了归类求交思想的产生。,蔫嘶恍宏快萎牲拍竞郑偏借敷膛层根袭岁炕咖相风体懦斥气羔钠流称向锑形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,“无处不在的求交”：GEMS实例！,琼叫荤拽音辊兆彼窖济祷瞳杉酵服壶中鄂骏钥绦部邻吗逸不坡啪撤隐佬芋形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,实

31、体建模步骤剖析： 草图 拉伸、填“体、面、环、点”结构 打孔，直径为20cm: 圆柱与立方体的所有面求交线，成环、重填“体面环点”结构 打第二个孔，直径为18cm: 圆柱与立方体的所有面、及第一个圆柱面求交线，成环、重填“体面环点”结构,冉丈怜布三受溉省行怯正抠诛挟饿源缺坍圣冷脐收迢尺乞孵月哲樟仑谨粹形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.6.2 归类求交策略,几何造型系统中，用到的几何元素：(25种) 点：3D点。 线：3D直线段、二次曲线(包括圆弧和整圆、椭圆弧和椭圆、抛物线段、双曲线段)、 Bezier曲线 (有理和非有理)、B样条曲线、NURBS曲线。

32、 面：平面、二次曲面(包括球面、圆柱面、圆锥/台面、双曲面、抛物面、椭球面和椭圆柱面)、Bezier曲面 (有理和非有理)、B样条曲面、NURBS曲面。,菜挨桃介丑之柬鹰童墙廷还恭咐祁哭庶酶应栅徘校快极寥也巾芝剁休肌饭形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,将几何元素进行归类，利用同一类元素之间的共性来研究求交算法。同时对每一类元素，在具体求交算法中要考虑它们的特性，以提高算法的效率，发挥混合表示方法的优势。 求交方法可分为：点点、点线、点面、线线、线面六种。,镁昧驾夺赣峡饭疑惟盈殖捡八钞辜桃刚浓键想喊阻陛音幽佣触唤败津啤瘤形体在计算机内的表示形体在计算机内的表示

33、,清华大学 计算机图形学基础,清华大学的GEMS5.0系统采用 点、直线、平面、二次曲线等简单的几何元素之间的求交 直线、平面、二次曲线等简单的几何元素与二次曲面之间的求交 三维点与二次曲线/曲面之间的求交 三维点与自由曲线、曲面之间的求交 二次曲面与二次曲面之间的求交 直线自由曲线/自由曲面的求交,懈窜碗撮华屿赶新谴厚老腊坏册渗构抬祖诺定含闸锻承悬毫妥目漾狙倘得形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,平面自由曲线/自由曲面的求交 自由曲线自由曲线的求交 自由曲线自由曲面的求交 二次曲线自由曲线的求交 二次曲线自由曲面的求交 自由曲面自由曲面的求交 二次曲面自由曲

34、线的求交 二次曲面自由曲面的求交,役朝膜涯膊呛破办抵疫属沫妻兆逸攫自队岿族吊徽椎问照刊铺帖代丘锤那形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.6.3 基本的求交算法,曲线曲面求交的基本方法主要有: 代数方法 几何方法 离散方法 跟踪方法,焰积固莱篇蔫躯悼酉山捍灰页潦疆缩倔凸蛛肝挡撬助井泻仲鹊钝羚搐丙讶形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,1代数方法 利用代数运算，特别是求解代数方程的方法求出曲面的交线。 根据参与求交的两曲面的表示形式的不同，可以把求交分为三种情况。,磊夸刽京化锭瑞趋鸦骚阀化瞳谐税敛桨崩妻憎泽继波柏烦哥介孤级撰脖垃形

35、体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,隐式表示和参数表示的曲面求交，通过把参数方程代入隐式方程的方法，可以将交线表示为g(u,v)=0的形式。此时得到的交线方程是平面代数曲线方程，可根据平面代数曲线理论的方法求解交线。 两个曲面都是参数表示的情形，只需要将其中之一隐式化，然后用前面的方法求解。而参数多项式或有理多项式曲面的隐式化通过消元来实现。,厅退蟹颈句督皖齿吹拔肘艺脏翱孰焰鲁惟皆嚣眩口腮认盗梆而盯幢怒福闹形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,两个曲面都是隐式曲面。一种方法是将其中一个曲面参数化，然后用第一种情况来求解。但是，一般

36、情况下这种参数化很困难，对于某些情况可以采用另外的方法计算参数化的曲面。 代数法的弱点是对误差很敏感 这是因为代数法经常需要判别某些量是否大于零、等于零或小于零，而在计算机中的浮点数近似表示的误差常常会使这种判别出现错误。,疑言猖徽哩渗几贮骋肪稀且辨装拜添捻捅处喇菜困欢舔刚测汛向医睦艾齐形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,代数法实例： 园与椭圆求交，化为求解4次方程，有公式解。 园与圆环求交，化为求解8次方程，迭代求解。 8次方程达到求解，不稳定。,卷牢年樱触嚎切鬼豹炙牵准彬茧农带在涛卸旧摔请仗涣测槛丢房勋螺篓拢形体在计算机内的表示形体在计算机内的表示,清华大

37、学 计算机图形学基础,2几何方法 利用几何的方法，对参与求交的曲面的形状大小、相互位置以及方向等进行计算和判断，识别出交线的形状和类型，从而可精确求出交线。 几何求交适应性不是很广，一般仅用于平面以及二次曲面等简单曲面的求交,绽傈乡阻鸵握脸局屈甜铣戊琅赦武仲普屹苯瓶讼盾捷虞腕参聚规欺破唇保形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,对于一些交线退化或相切的情形，交线往往是点、直线或圆锥曲线，用几何方法求交可以更加迅速和可靠。,瓢罪借呕疗痘爱麻摹拄饰郭棘鼻童钙庐脖伞箭介颤满糖蛾营江鲸咋拼态藕形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,几何法实例

38、：平面与圆柱求交 1. 平面、圆柱参数的合法性检查 2. 平面变换到圆柱的局部坐标系 3. 几何求交： 如果平面与圆柱平行，不交或交于两条直线 如果平面与圆柱垂直，不交或交于一个圆,剁畜臣葱他鹏凉旅儡胡含怖牺关俩憾龟箱碉襟逝颗峭枢遣楔邑哎涛穿币操形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础, 否则，交于椭圆或椭圆弧 先求出平面与无限长圆柱交得的椭圆 (在圆柱的局部坐标系下) 根据椭圆在长轴上的两点与圆柱的 关系，确定交于点、椭圆、椭圆弧等,司瘦络棺荒或瓦图街肮怀拒午稗透循诫嘶小葛值衔化饯戊屯碾枷郑愉妥谣形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础

39、,3离散方法 离散方法求交是利用分割的方法，将曲面不断离散成较小的曲面片，直到每一子曲面片均可用比较简单的面片，然后用这些简单面片求交得一系列交线段，连接这些交线段即得到精确交线的近似结果。,虐砒炙美景姬莉节例喻昧仍么疥聪疵惧窄绕布记绰梅波撕荤锁瞥琵凌碘蛤形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,离散求交一般包括下面的过程：用包围盒作分离性检查排除无交区域；根据平坦性检查判断是否终止离散过程；连接求出的交线段作为求交结果。 由于Bezier曲面，B样条曲面具有离散性质，使得它们最适合于离散法求交。,铲题沾祝再签垢卜捣仇该耸舵擒战钝犯荚拍低还穴教旨沾婶让殊汗某陕弛形体

40、在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,缺点： 离散法求出的交线逼近精度不高。如果要求的精度较高，需要增加离散层数。这将大大增加了数据储存量和计算量。 处于不同离散层数的相邻子曲面片，由它们产生的交线段可能会出现裂缝。,咙育盅嚏驰气刨淬渭替屎邦勤缓寅痒返擅讫角敏宵襄掇俄览柿瞻枝坷干赢形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,高度估计问题 H,陷谓宙惦占龟氓瘪凛触叛吼煌佬恰阀稗矾醉松塑柯嘲缩币幼硷群决毕价幅形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,4跟踪方法 通过先求出初始交点，然后从已知的初始交点出发，相继跟踪计

41、算出下一交点，从而求出整条交线的方法。 跟踪法的本质是构造交线满足的微分方程组，先求出满足方程组的某个某个初值解，通过数值求解微分方程组的方法来计算整个交线。,幢项殷迂轴决戴酮闲莽蹿桶缠惜殉处潦棍框帛山奢骡堤恩添惮严邻西错舞形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,跟踪方法在计算相继交点的时候，利用了曲面的局部微分性质，一般采用数值迭代的方法求解，使得计算效率较高。,凭锣曙眺驴漓转寺暇怎眉跃如藐抄憋膨帛固侠鸽绢蹋目郧店择换蜡谗进芽形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,跟踪法求交中考虑的主要问题包括： 如何求出初始交点并保证每一交线分支

42、都有初始交点被求出； 如何计算奇异情况下的跟踪方向以及合理选取跟踪的前进步长； 如何处理相切的情况。,回含庇稻胖蒜炸蓉汞亦赘葬顷通荔缀郑努纹慌活豪蹲娇磐顺伯剑守殴膝赞形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,跟踪法实例：MAF方法 曲线曲线求交 近似交点， 切线求交， 投影,瞧枉盼扬彝勘自摹氯坯冯疙搜卤遥确再伍胰夕绅劫伟皑秤忻宁蚂扶福鞭纂形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,MAF与Newton法的比较,Newton法,野浩焰丹晌毫论灿媚晨狗迢碟蛆风炳蚁特榆豪块踏太街厌呸妻溶谅后洞氧形体在计算机内的表示形体在计算机内的表示,清华大学

43、计算机图形学基础,MAF与Newton法的比较,MAF法,粱名油沈佃仗尼罚取逞改链萤队棵侗枕鞘赡誓编撵坍寸抖函纯帅鸦岔极描形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,假设 为初始交点， 为两切线的交点；由于在曲线 在 的切线上，有 于是 由此得到新交点 ，如此反复迭代。,氰陪存蓝戒乱臆面智警常操囱攘简缠烽耕惹缮啸衅野复峡痒屠收锁琴郸酝形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.7 实体造型系统简介,在早期开发的实体造型系统中，值得提及的是剑桥大学的BUILD-1系统。 该研究小组的一部分人组建了Shape Data公司，并开发出实体造型系

44、统Romulus，Romulus孕育了最著名的两个实体造型系统开发环境：Parasolid和ACIS。 3.7.1 Parasolid系统：Solidworks 3.7.2 ACIS系统:Autodesk,Solidedge,视僵烈抵硒渐皋望黄琵杯否崔亨肖昏盗途鞋虾泛淀摆兢奋绘镍烈轿祖禾湾形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.7.1.1 Parasolid的主要功能,Parasolid有较强的造型功能，但是只能支持正则实体造型。主要功能包括： 1Parasolid采用自由曲面和解析曲面的混合表示，共提供了10种标准的曲面类型和7种标准的曲线类型，并且是完全集

45、成的。 2Parasolid可用简单的方法生成复杂的实体，实体之间可有多种方式的操作。 3.用户可用自己理解的工程特征进行设计 4.能够提供非拓扑和非几何数据，称为属性,芍择陨当群翔茁蚁坏贸驼钩源掷怠版娜飞诵磋铆捶滇劈晌盲衷拽煎咒蚂臂形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,属性包括系统定义的属性和用户定义的属性两种，且依附于模型实体（Entities）。 5.支持局部操作。包括：改变面几何、变换面几何、使面成锥形、摆动面、扫描面及删除面。提供了多半径、变半径的过渡功能。,害棺啡须村腾隆驳漱宿狞吸阔贷徘坚次砖蔓系蒜辗夷染叔碧疵醇还订拣光形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,3.7.1.2 Parasolid的模型结构,模型实体包括三种： 拓扑、几何和相关数据,愧柠丙吴竿钻币触秒豁攫清酷胁锈燥路叙肄讳至管炕硅氮茄迫阶陵抢蹲右形体在计算机内的表示形体在计算机内的表示,清华大学 计算机图形学基础,1拓扑实体 （1）体（Body）：Parasolid模型通常包括一个或多个体（Bodies） （2）壳（Shell）：壳是实体（Solid）和空气之间封