3D Object Representations Lectured by Hua Yan 开场白： 本章我们将学习如何来表示三维对象，当然，三维千差万别，三维对象类型不同、材质表面也不同，不存在某一种方法可以描述不同的物质的所有特征对象，并应用不同，需要的表示方法也不同 举例： 多边形、二次曲面，欧氏对象 云、草，分形结构和微粒系统 布料动画，基于物理的建模

Contents Representation methods 多边形表面Polygon Surfaces 曲线曲面: Bezier曲线 立体构造Solid - Modeling 八叉树Octrees 分形Fractal …

Representation Methods 三维对象表示方法通常可分为两类 边界表示Boundary representations 空间区分Space-partitioning representations

Representation Methods 边界表示 使用一组曲面描述三维对象 曲面将物体分为内外两部分。 典型例子：多边形平面、样条曲面 画一个简单的立方体，说明边界表示

Representation Methods 用上图，说明边界表示

Representation Methods 空间分区表示 用来描述物体内部性质 将包含一物体的空间区域划分成一组较小的、非重叠的、邻接的实体。 如：八叉树表示 先提出问题：有哪些应用不能用“边界表示”方法？ 以医学图形为例说明，有些应用需要表示物体内部的情况，这时边界表示方法就不能满足要求

Representation Methods 通过上图，说明边界表示与空间分区的区别

8.1 多边形表面 三维图形中运用边界表示的最普遍方式是使用一组包围物体内部的表面多边形。 很多图形系统以一组表面多边形来存储物体的描述。由于所有表面以线性方程加以描述，因此会简化并加速物体的表面绘制和显示。 某些情况下，多边形表示是惟一可用的，但很多图形包也允许以其它方式对物体加以描述，如样条曲面，它在转换到多边形表示后加以处理

8.1 多边形表面 多边形表数据表分为两组进行组织 几何表：顶点坐标和用来标识多边形表面空间方向的参数 属性表：指明物体透明度及表面反射度的参数和纹理特征 多边形表的内容已在3.15节中介绍了，此处简单回顾一下，重点向学生讲解，用“一组包围物体内部的表面多边形”来表示三维对象

多边形表面 v1 v5 v3 v2 v4 E1 E6 E3 S1 S2 E2 E4 E5 顶点表 序号 点坐标 1 x1, y1, z1 2 边表 序号 顶点号 1 v1, v2 2 v2, v3 3 v3, v1 4 v3, v4 5 v4, v5 6 v5, v1 此处仅是回顾3.15的知识 多边形面表 序号 边序号 1 E1, E2, E3 2 E3, E4, E5, E6

Polygon Surfaces 多边形网格 图形系统一般使用多边形网格对3D物体进行建模 Plane Equations Ax+By+Cz+D=0 Usage point (x,y,z) Ax+By+Cz+D<0 Inside Ax+By+Cz+D>0 Outside identify the position of spatial points relative to the plane

8.2 曲线和曲面 曲线曲面的生成方法 给定一组数学函数 给定的一组数据点 图中的茶壶即是由曲线和曲面构成

8.2 曲线和曲面 一旦给定函数，图形包将指定曲线方程投影到显示平面上，且沿着投影函数路径绘制像素位置。 由函数式描述而生成的显示曲面的例子有二次曲面和超二次曲面 (P.334 - P.337) OpenGL二次和三次曲面函数(P.337-P.341) 提问：为什么常用三角形网格逼近曲面？ 三点决定一个平面。 对曲面而言，函数式描述通常嵌入到生成曲面的多边形网格逼近中。通常，使用三角形的多边形曲面片可以确保任一多边形的顶点在一个平面上。有四个或四个以上顶点的多边形其顶点可能会不在一个平面上。 二次曲面与超二次曲面请大家看教材，但简单说明一下球面。

8.3 样条表示 样条的历史 很早的绘图员利用“ducks”和有柔性的木条（样条）来绘制曲线 木质的样条具有二阶连续 并且通过所有的控制点 A Duck (weight) Ducks trace out curve

8.3 样条表示 样条：通过一组指定点集而生成平滑曲线的柔性带。 样条曲线在计算机图形学中的含义 样条曲面 由多项式曲线段连接而成的曲线 在每段的边界处满足特定的连续性条件 样条曲面 使用两组正交样条曲线进行描述 当绘制曲线时，几个较小的加权沿着样条的长度分配分配并固定在绘图表上的相应位置。

8.3 样条表示 样条在图形学中的应用 设计曲线、曲面 汽车车身设计、飞机和航天飞机表面的设计、船体设计以及家庭应用。 当绘制曲线时，几个较小的加权沿着样条的长度分配分配并固定在绘图表上的相应位置。

8.3 样条表示 曲线的产生 给定一组离散的坐标点，将数据集拟合成指定的曲线函数 根据曲线函数得到曲线的图形

8.3 样条表示 曲线的类型 插值样条曲线：选取的多项式使得曲线通过每个控制点 逼近样条曲线：选取的多项式不一定使曲线通过每个控制点 强调两者的区别 应用范围差别：插值曲线通常用于数字化绘图或指定动画路径。逼近曲线一般作为设计工具来构造对象形体

凸壳 凸壳的定义Convex hull 包含一组控制点的凸多边形边界 凸壳的作用 提供了曲线或曲面与包围控制点的区域之间的偏差的测量 以凸壳为界的样条保证了多项式沿控制点的平滑前进

凸壳 板书：以4个控制点的Beizer为例 画出凸壳

参数连续性条件 参数连续性条件 两个相邻曲线段在相交处的参数导数相等 零阶连续(C0连续)：简单地表示曲线连接 样条曲线的一个重要要求是线段连接平滑过渡，如何才能保证平滑过渡呢？ 下面介绍参数连续性与几何连续性条件

曲线分段构造时参数连续性条件 F(u) f(u) F(1)=f(0) F'(1)=f'(0) F'' (1)=f'' (0) 一阶连续性两个相邻曲线段的总体形状有突变，但已能满足数字化绘图及一些设计应用 二阶连续性对摄影机移动的动画路径和很多精密CAD需求有一定作用。 沿一阶移动镜头，将产生不连续性，但二阶不会。 零阶连续 一阶连续 二阶连续

几何连续性条件 几何连续性条件 两个相邻曲线段在相交处的参数导数成比例 零阶连续（G0连续）：与0阶参数连续性相同，即两个曲线必在公共点处有相同的坐标 一阶连续（G1连续）：表示一阶导数在两个相邻曲线的交点处成比例 二阶连续（G2连续）：表示两个曲线段在相交处的一阶和二阶导数均成比例 几何与参数生成的曲线类似，但有差别 对于几何连续性，曲线将向具有较大切向量的部分弯曲。

插值样条曲线 逼近样条曲线 三次样条插值 自然三次样条插值 Hermite样条插值 Cardinal样条插值 Kochanek_Bartels样条插值 逼近样条曲线 Bezier曲线 B_样条曲线 三次多项式在灵活性和计算速度之间提供了一个合理的折中方案。 与高次相比，计算与储存空间少，较为稳定 与低次相比，在模拟任意曲线形状时显得更加灵活。 本课程将重点介绍Bezier曲线

Bezier曲线和曲面 法国Bezier使用逼近样条设计汽车外形,数学基础简单，容易实现 广泛应用于CAD、3DMax等图形开发工具中

假定给出n+1控制点: pk=(xk,yk,zk), k取值范围为0到n，这些坐标值用于合成向量 P(u), Bézier 构造公式 假定给出n+1控制点: pk=(xk,yk,zk), k取值范围为0到n，这些坐标值用于合成向量 P(u), P(u) = Pk* Bk,n(u) Blending Functions合成函数 Bk,n(u) = C(n,k) * uk*(1-u)n-k C(n,k) = n! / (k!(n-k)!) Bézier Formula Suppose we are given n+1 control-point positions: pk=(xk,yk,zk), with k varying from 0 to n. These coordinate points can be blended to produce the vector P(u), P(u) = Pk* Bk,n(u)

Examples Implementation (P.357-359) quadratic Bézier curve 二次Bézier 曲线 cubic Bézier curve 立方Bézier 曲线 Implementation (P.357-359)

例：二次Bezier曲线 由三个控制点生成 B0,2(u) = (1-u)2 B1,2(u) = 2u(1-u) B2,2(u) = u2

例：三次Bezier曲线 由四个控制点生成 B0,3(u) = (1-u)3 B1,3(u) = 3u(1-u)2 B2,3(u) = 3u2(1-u) B3,3(u) = u3

Bezier曲线举例 P0 P1 P2

Bezier曲线举例 P0 P1 P2 P3 P0 P1 P2 P3

Bézier曲线特性 Bezier多项式次数＝控制点个数-1 Bézier曲线总是通过第一和最后一个控制点 P(0) = p0, P(1) = pn 任何 Bézier曲线总是落在控制点的凸壳内 Bk,n(u) = 1 Properties of Bézier Curves Bézier curve is always passes through the first and last control points. P(0) = p0, P(1) = pn Any Bézier curve lies within the convex polygon boundary of the control points

P0 P1 P2 P0 P1 P2 P3 P0 P1 P2 P3 P0 P1 P2 P3 P4 P0 P1 P2 P3

第一和最后一个控制点重合生成封闭Bézier 曲线 多个控制点位于同一位置会对该位置加以更多的权 零阶参数连续 Bézier 曲线的构造 Design techniques 第一和最后一个控制点重合生成封闭Bézier 曲线 多个控制点位于同一位置会对该位置加以更多的权 零阶参数连续 Bézier 曲线的构造 一阶参数连续Bézier 曲线的构造 Design techniques specify the first and last control points at the same position to generate closed Bézier curves specify multiple control points at a single position to pull nearer the curve to this position zero-order continuity Bézier curve first-order continuity Bézier curve

p1 p0=p5 p4 p2 p3 p0 p1=p2 p3 p4 p0 p1 p2 P0’ P1’ P2’ P3’

Bezier曲面 使用两组正交的Bezier曲线来设计 (m+1)*(n+1)个控制点

8.4 实体构造技术 由简单的物体来构成复杂的物体 扫描表示 结构实体几何法

扫描表示 思想： 通过平移、旋转及其他对称变换来构造三维对象 通过指定一个二维形状以及在空间区域内移动该形状的扫描来描述该三维物体

z o y x A 平移扫描 二维图形A沿Z轴平移

z B y x A 旋转扫描 二维图形A绕Z轴旋转

结构实体几何法 思想 通过对两个指定三维对象进行并、交或差等集合操作产生一个新的三维对象

结构实体几何法 并 交 物体A和B 差 差

8.5 八叉树 分层树形结构，称为八叉树。 思想 利用实体的空间相关性 优点 减少了三维物体的存储需求 提供了存储有关物体内部信息的方便表示 需求显示对象剖面的医学图像

四叉树 二维平面 八叉树 三维空间 三维空间的八叉树编码过程是四叉树编码的二维空间编码方法的扩展

四叉树 四叉树 数据结构 思想 同质象限 1 2 3 1 2 3 四叉树上的每个节点有四个数据元素 四分象限 均质象限不再划分

四叉树 用于二维平面的分解 对二维区域递归地等分4个小正方形，这个分解过程可表示为一棵树，除叶节点，其每个节点都有四个分支，分别表示4个小正方形 若小正方形是同质的，则不必再分解； 若小正方形是非同质的，则需将它再一分为四 分解是递归的。

四叉树 例 1 2 3 1 1 2 3 2 3 1 2 3

具有子孙的节点 空节点 实节点 2 4 5 13 9 10 7 8 11 12 3 14 15 20 21 16 17 22 23 18 19 24 25 1 6 四叉树 当空间区域存在较大的单一颜色区域时，四叉树编码能节省存储空间 对于含有2n*2n个像素的区域，四叉树表示至多有n层 四叉树中每个节点至多有4个直接后代 1 2 3 4 5 25 19 24 18 20 21 22 23 7 11 12 8 9 10 14 15 16 17 6 13

八叉树 三维形体的分解 对三维空间进行前后、左右、上下等分为8个小立方体， 小立方体单元均质，则停止分解； 小立方体单元非均质，需进一步分解为8个子立方体 直至所有小立方体单元均质，或已分解到规定的分解精度为止。

八叉树 具有子孙的节点 空节点 实节点 6 7 2 3 7 1 2 3 5 1 3

8.6 分形Fractal 欧氏几何法&分形几何法 分形基本特征 分形生成过程 分形分类 分形维数概念 欧氏几何方法：对象形状由方程来描述，具有平滑的表面和规则的形状 如何表示自然景物呢？分形几何方法，使用过程来对对象进行建模

欧氏几何法&分形几何法 Euclidean - Geometry Methods -- use equations to describe objects which have smooth surfaces and regular shapes. Fractal - Geometry Methods -- use procedures to model natural objects which have irregular or fragmented features. 传统欧氏几何： 物体形状由方程来描述 具有平滑的表面和规则的形状 分形几何： 从整体上看，分形几何图形是处处不规则的 在不同尺度上，图形的规则性又是相同的 使用过程而不是使用方程来对物体进行建模 自然景物：山、树、海岸线等

分形基本特征 infinite detail at every point每点具有无限细节 distant Closer Closer yet infinite detail at every point每点具有无限细节 self-similarity between the object parts and the overall features对象整体和局部之间的自相似性 利用一个过程来描述分形物体，该过程为产生物体局部细节指定了重复操作 Basic characteristics infinite detail at every point每点具有无限细节 self-similarity between the object parts and the overall features

分形生成过程 Idea Examples (P399) 分形图形的生成过程是重复使用指定的变换函数作用于空间区域中的点的过程 Initial point P0, transformation function F P1 = F(P0), P2 = F(P1), P3 = F(P2) …… Examples (P399) Fractal-Generation Procedures A fractal object is generated by repeatedly applying a specified transformation function to points within a region of space. Initial point P0, transformation function F P1 = F(P0), P2 = F(P1), P3 = F(P2) …… 分形物体本身具有无限细节，但我们运算的次数有限的 按显示器分辨率的限制，不可能显示比像素还小的细节变化 为了看到物体的更多细节，放大、并重复变换函数

Von koch snowflake

树形生成元及对应曲线

树形生成元及对应曲线

分形分类 类型 自相似分形：组成部分是整个物体的收缩形式 自仿射分形：组成部分为不同坐标方向上的不同缩放因子形成。 不变分形集：由非线性变换形成。 自平方分形 自逆分形：由自逆过程形成。 自相似分形：从初始形状开始，对整个形体应用缩放参数s来构造物体的子部件，s相同或不同。如果使用随机变量，则称为统计自相似，即各部分有相同的统计性质，适合用于对模拟树、灌木和其他植物 自仿射分形：可用随机变量，则为随机仿射分形。岩层、水和云 不

分形分类 Self-similar Fractal自相似分形 Types Deterministic self-similar 确定自相似分形 Statistically self-similar 统计自相似分形 用于模拟树木、灌木和其他植物(彩页12) Self-similar Fractal Self-similar fractals have parts that are scaled-down versions of the entire object. Starting with an initial shape, we construct the object subparts by apply a scaling parameter s to the overall shape. We can use same s for all subparts, or we can use different scaling factors for different scaled-down parts of the object. If we apply random variations to the scaled-down subparts, the fractal is said to be statistically self-similar。 Statistically self-similar fractals are commonly used to model trees, shrubs, and other plants.

分形分类 Self-affine Fractal 自仿射分形 Types 自仿射分形的组成部分由不同坐标方向上的不同缩放参数sx、sy、sz形成 Types Deterministic self-affine fractals确定自仿射分形 Statistically self-affine fractals统计自仿射分形 用于模拟岩层、水和云等自然景物(彩页13) Self-affine Fractal Self-affine fractals have parts that are formed with different scaling parameters, sx, sy, sz in different coordinate directions. We can also include random variations to obtain statistically self-affine fractals. Terrain, water, and clouds are typically modeled with statistically self-affine fractal construction methods.

Invariant Fractal Sets 不变分形集 Types 分形分类 Invariant Fractal Sets 不变分形集 由非线性变换形成 Types self-squaring fractals 自平方分形 self-inverse fractals 自逆分形 彩页14 Invariant Fractal Sets Invariant fractal sets are formed with nonlinear transformation. The class of fractals includes self-squaring fractals, such as the Mandelbrot set, and self-inverse fractals, which formed with inversion procedures.

Mandelbrot set Julia set Quartic fractals

复数基本概念 Z = x(实部)+iy(虚部) i2 =-1 Re(z) = x, Im(z) = y 例如：z = 3+5i |z|2 = x2+y2 zz = (x2-y2) + i2xy z1*z2 = (x1x2-y1y2)+i(x1y2+x2y1)

Julia集(p.408) f(z)= λz(1-z) Mandelbrot 集平方变换(p.412) zk = zk-12+z0 |z| < 2

视区 Im 窗口 1.25 -2.25 0.75 Re -1.25

分形的维数 定义 描述分形对象细节的变化量，是对象粗糙性或细碎性的度量。 用D描述 举例 确定性自相似分形维数计算D = ln n / ln(1/s) 其中：n是再分数目、s是缩放因子 有较大锯齿形的物体其分形维数大 分形维数较难计算

Koch曲线 n=4，每一步各小段分形数 s=1/3，比例因子 D=ln n / ln(1/s) = ln 4 / ln3 = 1.2619

分形图案欣赏 绚丽多彩的人工分形图案

分形图案欣赏

分形图案欣赏