哈尔滨工业大学计算机学院

1、哈尔滨工业大学计算机学院唐好选2022年年4月月14日日几何造型及高级建模技术主要知识点主要知识点 几何造型的定义几何造型的定义 形体在计算机内的表示 高级建模技术分数维造型粒子系统基于纹理的造型基于图像的造型 通过对点、线、面、体等几何元素，经过平移、旋转、变比等几何变换和并交差等集合运算，产生实际的或想象的几何模型 如何用计算机内的一维存储空间来存放由0维、1维、2维、3维等几何元素的集合所定义的形体，无疑是几何造型中最基本的问题关于几何造型的定义关于几何造型的定义 第一代：手工绘制工程图 第二代：二维计算机绘图 第三代：三维线框结构 第四代：曲面造型 第五代：实体造型几何造型技术的发展几

2、何造型技术的发展模型分类模型分类形体表示形体表示线框模型线框模型表面模型表面模型实体模型实体模型数据模型数据模型过程模型过程模型完全以数据描述规则形体的建模方法以过程和控制参数描述不规则形体的建模方法表现物体的骨架表现物体的皮肤表示“有血有肉”的物体模型主要知识点主要知识点 几何造型的定义几何造型的定义 形体在计算机内的表示形体在计算机内的表示 高级建模技术分数维造型粒子系统基于纹理的造型基于图像的造型 顶点(Vertex)：零维的几何元素,包括插值点、型值点和控制点 边(Edge)：一维的几何元素，可以是直线，也可以是曲线 面(Face)：是形体上一个有限非零的区域，是二维的几何元素，至少有

3、一个外环和若干个（可以是零个）内环界定其范围，面的外法线方向是面的方向，可以是平面或曲面 环(Loop)：是有序有向边组成的面的封闭边界，在面上沿一个环前进，其左侧总在面内，右侧总在面外 体(Body)：三维的几何元素，是由封闭表面围成的空间，其边界是有限面的并集表示形体的基本几何元素表示形体的基本几何元素 构成形体的几何元素按六个层次表示：形体、外壳、面、环、边、点 对于任意形体，如果它是三维欧氏空间中的非空有界的封闭子集，其边界上任意一点都存在一个充分小的邻域，该邻域与平面上的封闭圆是同构的，则该形体为正则形体，否则为非正则形体（如下图） 点点(V)边边(E)面面(F)的个数满足公式的个数

4、满足公式V - E + F = 2812345679V-E+F-C=9-20+18-6=1 如果把三维封闭空间分割成如果把三维封闭空间分割成C个多面体，其顶点、边、面和多个多面体，其顶点、边、面和多面体个数满足下列公式：面体个数满足下列公式：V-E+F-C=1 立方体内立方体内1点与点与8个顶点相个顶点相连可以分割出连可以分割出6个多面体个多面体(C) 顶点数顶点数(V)：8+1 = 9 边数边数(E)：12 + 8 = 20 面数面数(F)：6 + 6*4/2 = 18 对于有孔形体，若孔的个数为对于有孔形体，若孔的个数为H,C为形体个数，为形体个数，G为穿透形体为穿透形体的孔洞数，则相应的

5、欧拉公式是的孔洞数，则相应的欧拉公式是:V-E+F-H=2(C-G) 孔个数孔个数(H)：3 形体个数形体个数(C)：1 穿透形体的孔洞数穿透形体的孔洞数(G)：1 顶点数顶点数(V): 3(长方体数长方体数)*8 = 24 边数边数(E): 3 (长方体数长方体数)* 12 = 36 面数面数(F)：3(长方体数长方体数)*6-3 = 15V-E+F-H = 24-36+15-3 = 0 = 2(1-1) = 2(C-G) 边界表示（Boundary Representations） 扫描表示（Sweeps Representations） 空间分解表示（Spatial-Partitioni

6、ng Representations）空间位置枚举表示（Spatial-Occupancy Enumeration）八叉树表示（Octrees）单元分解表示（Cell Decomposition） 构造实体几何表示（Constructive Solid Geometry） 边界所描述的几何信息包括： 几何信息(Geometry)：描述形体几何元素的性质和度量关系，如位置、大小、方向、尺寸和形状信息 拓扑信息(Topology)：描述形体几何元素之间的连接关系、邻近关系及边界关系，形成物体边界表示的骨架 几何元素间典型的连接关系(即拓扑关系)是指一个形体由哪些面组成,每个面上有几个环,每个环由哪

7、些边组成,每条边又由哪些顶点定义等 几何造型中最基本的几何元素是点(V) 、边(E)、面(F),这三种几何元素共有9种连接关系边界表示边界表示- -形体的边界及其连接关系形体的边界及其连接关系1/21/2 VVVVV1V VEEEV1EV1F VFFF EFFE1F EEEEEE1E VVEE1V FFFFFF1F EEEEFF1E VVVVFF1V确定了物体的边界也就确定了物体本身形体是由几何元素构成的,每一种形体的边界每一种形体的边界都是由与其相对应的较低维的几何元素组成的。实体边界通常由面的并集表示,面的边界是边的并集,边由顶点来表示在边界表示的数据结构中,比较著名的有冀边数据结构：冀边

8、数据结构：以边为核心组织数据结构，用指针记录每一条边的两个邻面（左右外环）、两个顶点及两侧各自相邻的两个邻边（左上/下边、右上/下边）半边数据结构：半边数据结构：将一条物理边拆成两条边来表示，使其中的每条边只与一个邻接面相关 以边为核心记录数据（以边为核心记录数据（以边以边E1为例为例） 记录记录E1的两个邻面的两个邻面 左外环左外环F1和右外环和右外环F2 记录记录E1的两个顶点的两个顶点 上顶点上顶点V1和下顶点和下顶点V2 记录记录E1的四个邻边的四个邻边 左上边左上边E2和左下边和左下边E4 右上边右上边E3和右下边和右下边E5 优点可精确表示物体表示覆盖域大，表示能力强容易确定几何元

9、素之间的连接关系，几何变换容易显式表示几何元素，绘制速度快 缺点数据结构复杂，维护不方便需要大量的存储空间不一定表示一个有效形体，有效性难以保证 也称为推移表示，是基于一个基体（一般是一个封闭的二维区域）沿某一路径运动而产生的形体 扫描表示需要两个分量: 一是被运动的基体 另一个是基体运动的路径 如果是变截面的扫描，还要给出截面的变化规律 一个二维区域沿某一路径运动得到的物体称为Sweep体 平移Sweep体：将一个二维区域沿着一个矢量方向扫描指定的距离，得到的曲面称为平移Sweep体，或称为拉伸体(如圆柱、立方体等) 旋转Sweep体：将一个二维区域绕某一给定的旋转轴旋转一个特定的角度得到的

10、曲面称为旋转Sweep体，或称为回转体（如圆锥） 广义Sweep体：将任意剖面沿任意轨迹扫描指定的距离，扫描路径可以用曲线函数来表示，并且可以沿扫描路径变化剖面的形状和大小，就可得到广义的Sweep体 等截面扫描 变截面扫描 优点表示简单、直观适合做图形输入手段 缺点做几何变换困难不能直接获取形体的边界信息表示形体的覆盖域非常有限 空间分解表示也称为空间分割表示，主要分为以下几种方法：空间位置枚举表示（ Spatial-Occupancy Enumeration ）八叉树表示（ Octrees ）单元分解表示（Cell Decomposition）xzy小立方体首先在空间中定义一个能包含所要表

11、示的物体的立方体，立方体的棱边分别与x,y,z轴平行，然后将其均匀划分为一些单位小立方体，用三维数组Cxyz表示数组中的元素与单位小立方体是一一对应，当Cxyz=1时，表示对应的小立方体被实体占据，否则，对应的小立方体没有被实体所占据优点：可以表示任何形状的物体缺点：是物体的一种非精确表示，占用的存储空间较大 将物体所在的立方体自适应划分成一些不同大小的立方体，然后将其表达为一种树形层次结构 八叉树表示形体的算法可表示为： 首先对形体定义一个外接的立方体作为八叉树的根节点，对应整个物体空间，将其分解为8个子立方体，分别对应八叉树的八个节点 如果立方体单元完全被物体所占据，则该节点标记为F(Fu

12、ll)，停止对该子立方体的分解 如果子立方体单元内没有物体，则将该节点标记为E(Empty) 如果子立方体单元部分被物体部分占据，则将该节点标记为P(Partial) ,并对该立方体作进一步分解，进一步分割成8个子立方体，对每一个子立方体进行同样的处理 当分割生成的每一个小立方体均被标记为F或 E以后，算法结束，否则，如果标记为P 的每个小立方体的边长均为单位长度，这时应将其重新标记为F后结束算法xzyEEEEEFEEEEFFEFPPE棱锥体素 长方体体素 体素并集 将单一体素分解改进为多种体素分解，将多种体素组织在一起表示物体单元分解表示的优点：表示简单，基本体素可以按需选择，表示范围较广，

13、可以精确表示物体缺点：分解的方法很多，物体的表示不惟一 通过对基本体素定义各种运算而得到新的实体，其运算可以为几何变换或正则化的并交差集合运算 常用的体素有长方体、立方体、圆柱、圆锥、圆台、棱锥、棱柱、环和球等 基本步骤首先确定要构造三维实体的初始体素集每次操作时从中选择两个体素，按照一定的相对位置关系放置到空间某位置，对其进行体素的并、交、差集合运算，生成一新的实体利用基本体素和每一步新创建的新形体的组合，继续构造新的形体，直到形成最后所需要的三维实体为止 U* -* -* U*主要知识点主要知识点 几何造型的定义几何造型的定义 形体在计算机内的表示形体在计算机内的表示 高级建模技术高级建模

14、技术分数维造型粒子系统基于纹理的造型基于图像的造型 雪花的形状是什么样的?第一步第二步第三步 雪花的每一部分经过放大都可以与它的整体一模一样(自相似形)自相似形的另一个例子 雪花的形状 分数维分数维(维数为分数),不同于拓朴维(整数维) 自相似性自相似性:部分与整体以某种形式相似的形 分形集都具有任意小尺度下的比例细节，或者说它具有精细的结构 分形集不能用传统的几何语言来描述，它既不是满足某些条件的点的轨迹，也不是某些简单方程的解集 分形集具有某种自相似形式，可能是近似的自相似或者统计的自相似 一般，分形集的“分形维数”，严格大于它相应的拓扑维数 在大多数令人感兴趣的情形下，分形集由非常简单的

15、方法定义，可能以变换的迭代产生 首先，分形形态是自然界普遍存在的分形形态是自然界普遍存在的，研究分形，是探讨自然界的复杂事物的客观规律及其内在联系的需要，分形提供了新的概念和方法 其次，分形具有广阔的应用前景分形具有广阔的应用前景，在分形的发展过程中，许多传统的科学难题，由于分形的引入而取得显著进展。 分形作为一种新的概念和方法，正在许多领域开展应用探索。80年代初国外开始的“分形热”经久不息。美国著名物理学家惠勒说过：今后谁不熟悉分形，谁就不能被称为科学上的文化人。 随机插值模型：可以模拟海岸线和山等自然景象 正规文法模型：用正规文法生成结构性强的植物的拓扑结构，再通过进一步几何解释形成逼真的画面 迭代函数系统模型：选取合适的映射集合、概率集合及初始点，使得生成的无穷点集能模拟某种景物 Koch曲线 随机L系