【XJTUSE计算机图形学】第三章 几何造型技术(4)——三角网格

三角网格

形体表示方法

线框模型；

只能表示一些简单的模型

实体模型；

能够完整地、无歧义地表达三维形状；

不适合物体表面的运算：光照计算、阴影计算和光线求交计算等。

表面模型：

基于连续参数曲面的表示方法：样条等；

离散表面表示方法：三角网格。

三角网格的概念

三角网格delaunay

用三角形组成面片列表近似三维模型；

用于表达物体的原因：

易通过三维扫描技术大量获取原始数据；

采用足够多面片时可任意精度逼近复杂的曲面；

网格模型数据结构简单、适合于光照计算等处理；

适合硬件进行并行处理。

随着图形硬件不断增强，处理三角网格的性能以指数级别的速度不断增长，已成为最为广泛使用的模型表达方法。

三角网格描述

1️⃣ 顶点几何信息：

n个顶点V=(v1,v2,…,vn)。

2️⃣ 三角网络拓扑连接的信息

一维的边：对应顶点的二元组,如(v1,v2)；

二维的面：对应顶点的有序三元组（逆时针），如(v1,v2,v3)。

3️⃣ 附加属性：

与某顶点、边或面关联的法向、纹理坐标等信息

三角网格模型的存储

可通过不同的方法获得：

三维扫描仪，采用特定方法生成三角网格模型；

三维动画和造型软件。

文件格式：

文本：易于阅读和理解；(OBJ和PLY文件格式)

二进制：具有较高的编码效率。

三角网格的半边表示(了解)

精确的表示三角网格：

只需存储顶点和每个面所包含的顶点。

对网格拓扑进行检索和遍历：

按顺时针顺序遍历包含某顶点的所有面。

原始的存储结构：需要遍历整个模型；

改进的存储结构：增加少量的存储量，提供一系列访问的便利，例如三角网格的半边表示结构。

半边结构**（**双向链接表）：把一条无向的边拆分成两条有向的“半边”，规定半边的方向总是沿着逆时针方向。

半边e和半边Opposite(e)对应同一条边；

除顶点、边和面外，存储额外信息

存储的信息

顶点的几何信息，即空间坐标(v)；

一条从该顶点出发的半边(e)：

该半边的源顶点Origin(e)

该半边在同一三角形中的下一半边Next(e)

与该半边同属一条边的对边Opposite(e)

该半边所属面IncFace(e)

此存储结构便于各种网格上的遍历操作。

获得半边e的上一半边： Prev(e)= Next(Next(e))

半边e指向的顶点： Target(e)= Origin(Next(e))

半边表示结构：

存储额外的信息，当网格结构发生变化时，需要进行相应的更新，以保证数据的一致性。

为网格访问操作提供便利，并提高处理效率

网格处理概述

背景：大量高精度的三角网格模型，为了获得符合人们需要的数据，需要进行相关处理。

从应用目标出发，网格处理包括

简化：用较少面片表示几何，提高绘制效率；

细分：以原始网格为基础，按一定规则生成包含更多面片的几何；

重剖：为了获得更规则的网格模型，可能具有更少或更多的面片。

网格简化

减少已有网格的面片数量，仍能表达原三维模型的过程

真实感图形学需要实时绘制的特定视觉效果：

由Lidar扫描真实三维物体而得到网格，采样点稠密，导致存储、传输及绘制带来极大地困难；

通过减少场景的复杂度提高图形绘制的速度。

层次细节网格简化技术Level of Detail(LOD)

基本不影响画面视觉效果的条件下，逐次简化景物的表面细节来减少场景的几何复杂性，提高绘制算法的效率；

实质：降低显示三维场景模型的复杂度，损失一定的图形质量，达到实时绘制目的。

LOD技术的基本原理

对原始多面体模型，建立不同逼近程度的几何模型：

每个模型均保留一定层次的细节；

近处观察物体，静止或运动较慢物体，采用精细的模型；

远处观察物体，运动较快的物体，采用较粗糙的模型；

研究的主要问题

如何建立原始网格模型的不同层次细节的模型；

如何建立相邻层次的网格模型之间的几何形状过渡：

视点连续变化时，两个不同层次的模型之间存在明显跳跃，须在相邻层次的模型之间形成光滑的视觉过渡

LOD算法

1️⃣ 生成不同细节的LOD模型

从原始精细模型中删除重要性小的点、边和面，简化网格；

相对于原始网格，误差是逐步递增的。

2️⃣ 基于某种原则选取某个LOD模型

视点、视线相关的。

3️⃣ 实现几何形状光滑过渡

建立相邻层次的多边形网格模型之间的几何形状过渡：采用某种方法从一种LOD模型切换到另一种模型；

插值对应网格基本元素的位置，实现平滑过渡，避免突变。

4️⃣ 建立原始网格模型的不同层次细节的模型

顶点删除：删除一个顶点，对相邻三角形形成的空洞作三角剖分，保持网格的拓扑一致性

边压缩：把一条边压缩为顶点，与该边相邻两个三角形退化，两个顶点融合为一个新的顶点

面片收缩：把面片收缩为顶点，本身极其相邻三个三角形都退化，三个顶点收缩为一个新顶点

5️⃣ LOD模型生成

确定每次操作给网格场景带来的误差，以此作为权值，插入到按权值增序排列的队列中；

开始循环进行网格基本简化操作：

选取队首权值最小的操作，执行之；

更新变化的网格信息，并重新计算改变了的网格基本元素的误差，插入到队列；

再开始下一个循环，直到队列的最小误差达到用户设定的阀值或者用户希望的化简网格数目已经达到。

6️⃣ 几何形状过渡

通过插值对应网格基本元素的位置实现光滑过渡；

确定相邻层次网格模型的基本元素之间的对应关系：

顶点删除和面片收缩操作：用被操作的对象与其相邻的基本元素之间建立对应关系；

边压缩操作：只要简单的把压缩边上的两点与压缩后的新点建立对应关系。

LOD技术

广泛地应用于实时真实感图形学中；

简化场景复杂度，满足某些关键任务的实时性要求：

采用不同分辨率的模型显示复杂场景的不同物体，保证真实感图象质量满足要求的前提下，实时地产生真实感图象

网格细分

网格细分：通过按一定规则给网格增加顶点和面片数量，让网格模型变得更加光滑。

Loop细分法

最早的基于三角网络的细分法；

步骤：

增加顶点：调增网格的拓扑结构；

顶点位置调整：平滑网格的粗糙程度。

生成两类顶点，E-顶点和V-顶点。

特征敏感网格重剖

特征敏感网格重剖

在网格简化后的模型中，三角形形状的规则性难以有较好的保证；

三角网格模型的规则性指标：

网格中顶点的度数尽可能接近于6；

每个三角面的顶角尽可能的接近于60度；

构成网格的各边的边长尽可能相近。

网格重剖：生成较规则的网格模型，并尽可能与原网格在几何上相近。

特征敏感度量

特阵区域:具有至少一个较大主曲率的区域

对于几何模型的外观及表达尤为重要；

特征区域曲面上单位法向发生变化：尖锐特征,平滑特征,平坦区域。

特阵敏感度量：通过改变度量，为与特阵相关的网格处理提供一种统一的解决方案

欧氏度量；

马氏距离

特阵敏感距离

把网格视作连续曲面的近似，设曲面

Φ

\\Phi

Φ上一点

x

∈

Φ

x\\in \\Phi

x∈Φ处的单位法向量为

n

(

x

)

n(x)

n(x)，可以将曲面的上任意一点x映射到空间

R

6

R^6

R6中的一点

x

f

=

(

x

,

w

n

)

x_f=(x,wn)

xf​=(x,wn)，其中

w

w

w是一个非负的权重；

假设网格是连续曲面足够好的近似，那么网格上两个顶点v1和 v2，坐标和法向量分别是(

x

1

,

n

1

x_1,n_1

x1​,n1​)和(

x

2

,

n

2

x_2,n_2

x2​,n2​)，则特征敏感度量下的距离：

很多网格处理算法或多或少依赖于度量：网格重剖、特征分析和编辑等；

与欧氏度量相比，综合考虑了位置和法向的变化，有助于更好地处理和保持特征。

举例

1️⃣ 各向同性重剖：生成尽可能均匀的模型——只考虑欧氏距离

调整采样点的位置至均匀分布，利用局部参数化将局部区域映射到平面上，并使用带约束的Delaunay参数化来恢复网格的连接关系；

虽然三角形形状较好，但特征区域由于和其它区域一样进行采样，因而变得模糊。

2️⃣ 基于特征敏感度量的重剖——考虑了法向量

调整w的取值，改变生成网格对于特征的保持程度；

虽在三维空间，三角形的形状沿特征方向拉伸，但度仍接近6，特征敏感度量下均匀，且改进了特征区域的保持，用较少面片精确地表示几何模型。