第七篇 三维实体的表示.ppt

计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 实体表示方法——构造实体几何表示 * * 实体表示方法——构造实体几何表示 用于构造CSG树的节点的一种实用数据结构是： struct node { short Opcode; float M[4][4]; short Primtype; Unsigned char *Prim; struct node *LeftSubtree; struct node *RightSubtree; } 其中，Opcode为节点的类型，根据取值分别表示基本体素或正则运算。 * 实体表示方法——构造实体几何表示 当Opcode=0，此时Primtype表示基本体素的类型，Prim为指向该基本体素的指针，M为在对该基本体素做正则集合运算之前所需的几何变换，此时指向左右子树的指针LeftSubtree和RightSubtree为空。 当Opcode=1,2,3时，分别表示该节点为正则并、交、差节点，此时，Prim为空，M仍为变换矩阵， LeftSubtree和RightSubtree分别指向该节点的左、右子树。 在构造实体几何表示法中，基本体素可以是半空间。一张面(无限大)将整个三维空间分成两个无限的区域，称为半空间。若面的方程为f(x,y,z)=0，则两个半空间为{P|f(P)?0}和{P|f(P)?0}。 * 实体表示方法——构造实体几何表示 将半空间{P|f(P)?0}作为面f(P)=0唯一确定的基本体素，记为h。那么任意凸多面体H可以表示为一组半空间的交，即： 任一复杂的体F都可以表示成多个凸多面体的并，即： 构造实体几何表示法能表示物体的范围依赖于基本体素的提取，基本体素的种类越多，表示域越宽，但同时需要更多的算法支持。 * 实体表示方法比较 本章介绍了五种主要的实体表示方法，每种方法各有优劣，适用于不同的应用环境，它们的比较需要有一定的标准： 精确性、唯一性、表示域、封闭性、有效性、简洁性等， 考虑到实体表示方法是实体造型系统的核心，还应考察每种表示方法对输入输出的支持。 没有哪一种表示方法在任何应用场合是最好的。事实上，大多数三维实体造型系统中都是多种表示法并存，以一种表示法为主，其它为辅助。它们之间互相依赖、互相补充。 * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * 计算机图形学 * * * 实体表示方法——边界表示 边界表示的数据结构 最简单的边界表示方法 将多面体表示成其边界的一列多边形，每个多边形又由一列顶点坐标来表示。将顶点统一按一个方向(如逆时针或顺时针)排列。 由于每个顶点属于多个多边形，在多边形中只保存各顶点的序号，将多面体的所有顶点存放在一个数组中。这里，边的信息是隐含的，即多边形顶点序列中相邻两个顶点构成一条边。 * 实体表示方法——边界表示 边界表示的数据结构 此法数据结构简单，但效率不高。如查找共享某条边的两个多边形，则需要遍历组成该多面体边界的所有多边形，才能确定哪两个多边形包含这条边。(原因：数据结构中包含多面体边界的拓扑信息不完整。) * 实体表示方法——边界表示 几何信息 指的是顶点、边、面的位置、大小、形状等几何数据。 拓扑信息 指的是顶点、边、面之间的连接关系。 多面体的顶点、边、面之间的拓扑关系可用九中不同的形式描述：v?{v}, v?{e}, v?{f}, e?{