计算机图形学2010-05三维几何造型.doc

《计算机图形学》教案：第五章 三维几何造型 8

二维图形学小结：
线的点阵生成：直线、圆的点阵生成，重点是Bresenham算法；
面的点阵生成及扫描线生成，即区域填充：多边形填充，圆及椭圆填充，种子填充；
裁剪：线段的编码裁剪，多边形的逐边裁剪。
几何变换：通过矩阵运算进行变换，一个变换对应一个矩阵，基本变换包括：平移、缩放、旋转、对称。多个基本变换矩阵顺序相乘得到组合变换矩阵。
样条曲线：二次样条曲线，三次样条曲线，贝济埃样条曲线，B样条曲线。

三维图形学的基本问题：
三维几何造型：如何定义三维图形
三维几何变换
投影变换：将三维图形转换到二维平面
遮挡与消隐计算：只显示转换到二维平面上的可见部分。
光照及明暗处理：显示出光线所形成的明暗效果
纹理映射：将真实感的图像映射到图形表面。
三维空间运算：距离计算，碰撞计算，相交计算。

第五章 三维几何造型
第一节 三维形体的基本定义方式
一、定义三维形体的基本元素
1. 点
三维空间中的点用三维坐标(x, y, z)定义
2. 边
边是两个邻面的交线。可以是直线或曲线。直线由两个端点定义；曲线由一组顶点定义；规则曲线由方程定义。
3. 环
多条边按一定的方向和顺序组成的封闭边线。由一组依次循环相连的边定义环。
4. 面
面是三维空间中无体积（无厚度）的一个有限区域。面由面方程和环进行定义。分为平面和曲面。
5. 体
由面围成的封闭空间。
体分为正则形体和非正则形体。
非正则形体的情形如下：

6. 体素
体素是可以用有限个参数定义的形体。是定义复杂形体的基础。
如长方体，圆球，椭圆球，圆柱，圆台，圆环体等。
二、定义形体三种基本模型
1. 线框模型
定义形体的各条边线。
这种模型的基本数据结构包含两个表，一个是顶点表，记录所有顶点的三维坐标值，二是边表，记录每条边的两个顶点。
顶点表：V1(x,y,z)，V2(x,y,z), V3(x,y,z), ……
边表：E1(v1,v2), E2(v2,v3), ……
其只简单的定义各条边，并不进一步对面和体进行定义，因此这种模型没有对形体作出完整定义，只是用于三维形体的基本显示，对形体的显示具有模糊性、二义性。
在二维线框模型的基础上发展而来，用于工程绘图。

2. 表面模型
在线框模型的基础上进一步对面作出定义。
在数据结构上，增加一个面表，记录形体上的每个面的边界环所包含的边。
面表：F1(e1,e2,…), F2(e1,e2,…), ……
表面模型依然没有对形体作出完整定义。
在面模型的基础上能完成有效的三维显示，在面的基础上可进行消隐处理，光照及明暗处理。
目前三维图形显示处理都是基于表面模型进行的。常用的三维图形显示标准，如OpenGL，Direst3D，都是基于表面模型。

3. 实体模型
对实体作出完整定义。
一种定义方式，就是在表面模型的基础上进一步定义实体。其数据结构中进一步增加一个实体表，记录每个实体的各个表面。
体表：S1(f1, f2, …), S2(f1, f2, …), ……
只有在实体模型的基础上，才能有效进行完全的三维显示及各种三维空间的操作、处理、运算。

第二节 实体表示方法
一、构造的实体几何法（CSG）
在一组基本体素的基础上，通过对各体素的几何变换及多个体素的集合运算来构造复杂实体。
这种构造方式可用一个二叉树来表示。
树的叶节点是各个体素，中间节点则对应于几何变换及集合运算。
多个体素的几何运算都分解为两两之间的几何运算。集合运算的类型包括：并、交、差。
如下图所示。

优点：
(1)可以构造出十分复杂的形体。
(2)能够对形体进行精确表示。
缺点：
(1)造型能力受基本体素类型的限制。
(2)显示处理和空间运算比较复杂。
(3)复杂形体之间的交和差运算比较复杂。
二、边界表示法
定义实体的所有边界面及面的外法线方向。
原理上，边界面可以是平面和各种曲面，但曲面之间很难保证有效的连接和封闭，因此实际应用中大都是基于平面来定义边界面，每个边界面都是一个平面多边形。
优点：
(1)便于进行显示处理；空间中的多边形投影到平面上仍然是一个多边形。
(2)便于进行有关的空间运算。由多边形围成的体总是多面体，所有空间运算都可基于多面体进行，而不需要考虑其它类型体素的空间运算。
(3)能够有效进行任意形状的造型。
缺点：
(1)对实体的表示具有近似性；
(2)复杂形体的造型效率比较低；
(3)实体形状的改变比较困难；
(4)实体的构造容易产生错误，形成无效实体。
三、扫描表示法
将一个二维形体按一定的轨迹进行运动来生成三维实体。
二维形体可以是一个线或面，运动轨迹可以是直线段、圆周线、曲线。
可以简洁地表示出一些形状特殊的实体，不具备全面的实体表达能力，主要用于基本形体的构造。
显示处理和空间运算都比较困难，需要针对具体情况进行分析处理。
四、特征表示法
通过一组参数和约定的规则来表示实体。
简单的包括：立方体，圆柱体，球体，圆锥体等。复杂的如：螺孔，齿轮等在特定领域常用的实体形状。
主要用于构造基本的预定义形体，不用于全面的造型。
五、单元分解表示法
典型的是八叉树表示法。
首先定义一个包含整个实体的立方体，然后将立方体剖分为8个立方体，如实体充满了某个立方体，则将其标识为满，如实体完全不在某个立方体中，则将其标识为空，空或满的立方体不再进行处理，其它立方体则进一步再剖分为8份，如此反复，直到所有立方体都为满或空，或将立方体到了给定的最小尺寸。
这种方法用一套简洁统一的规则对任何形状的实体作出有效表达，有关的空间运算也比较简单。
但：表达具有近似性；显示处理比较困难。

实际应用中主要采用两种方式，一是构造法，二是多边形边界法。扫描法、特征法主要用作辅助的造型手段，用于建立基本形体。
用这些方法所建立的实体模型，在进行显示处理时通常都要转换成多边形表面模型。边界模型可直接对应于表面模型，其它模型则需要进行专门的多边形网格转换。
目前的三维图形的显示输出都是基于多边形表面模型进行的。