计算机图形学第三章-5(形体表示).ppt

清华大学计算机科学与技术系 计算机图形学基础 清华大学计算机科学与技术系 计算机图形学基础 清华大学国家CAD工程中心开发的几何造型系统GEMS5.0中，采用的数据结构如图 体组 特征表示 单体(零件) 面组 面 线框 环 环边 边 顶点 曲 面 曲 线 点 实体几何数据 实体拓扑数据 参数域曲线 清华大学计算机科学与技术系 计算机图形学基础 该数据结构基于线框、表面、实体和特征统一表示，且具有以下特点： 1）采用自顶向下的设计思想。在形体的表示上，遵循了从大到小，分解表示的原则； 2）支持非流形形体的表示； 3）实体拓扑数据与几何数据双链表连接，存放紧凑； 4）能够支持特征造型。 清华大学计算机科学与技术系 计算机图形学基础 3.2.3.3 欧拉操作 对于任意的简单多面体，其面(f)、边(e)、顶点(v)的数目满足 欧拉公式 v - e + f = 2 对于任意的正则形体，引入形体的其它几个参数：形体所有面上的内孔总数(r)、穿透形体的孔洞数(h)和形体非连通部分总数(s)，则形体满足公式： v - e + f = 2(s-h) + 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，生成一条新的边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，由此也删除了体上的一个通孔。 清华大学计算机科学与技术系 计算机图形学基础 为了方便对形体的修改，还定义了两个辅助的操作： 公共端点。 (11)semv(e1,v,e2)，将边e1分割成两段，生成一个新的点v和一条新的边e2。 (12)jekv(e1,e2)，合并两条相邻的边e1、e2，删除它们的公共端点。 以上十种欧拉操作和两个辅助操作，每两个一组，构成了六组互为可逆的操作。 可以证明：欧拉操作是有效的，即用欧拉操作对形体操作的结果在物理上是可实现的；欧拉操作是完备的，即任何形体都可用有限步骤的欧拉操作构造出来。 清华大学计算机科学与技术系 计算机图形学基础 3.2.3.4 集合运算 正则集与正则集合运算算子 规定正则形体是三维欧氏空间中的正则集合，因此可以将正则几何形体描述如下： 设G是三维欧氏空间中的一个有界区域，且G＝bG∪iG，其中bG是G的n－1维边界，iG是G的内部。G的补空间cG称为G的外部，此时正则形体G需满足： 1）bG将iG和cG分为两个互不连通的子空间； 2）bG中的任意一点可以使iG和bG连通； 3）bG中任一点存在切平面，其法矢指向cG子空间 4）bG是二维流形。 清华大学计算机科学与技术系 计算机图形学基础 设OP是集合运算算子（交、并或差），R3中任意两个正则形体A、B作集合运算： R=AOPB 运算结果R仍是R3中的正则形体，则称OP为正则集合算子。 正则并、正则交、正则差分别记为∪*，∩*、-*。 分类 清华大学计算机科学与技术系 计算机图形学基础 Tilove对分类问题的定义为：设S为待分类元素组成的集合，G为一正则集合，则S相对于G的成员分类函数为： C(S,G)={S in G，S out G，S on G 其中， S in G=S∩iG， S out G=S∩cG， S on G=S∩bG， 清华大学计算机科学与技术系 计算机图形学基础 集合运算算法 包括以下几部分： (1)求交：参与运算的一个形体的各拓扑元素求交，求交的顺序采用低维元素向高维元素进行。用求交结果产生的新元素（维数低于参与求交的元素）对求交元素进行划分，形成一些子元素。 (2)成环：由求交得到的交线将原形体的面进行