第7章：几何建模基础
7.1 几何表示
7.1.1 几何表示的分类
在计算机图形学中，3D 几何体有多种表示方法，每种方法有其优缺点和适用场景。
几何表示方法分类
┌────────────────────────────────────────────────────────────┐
│ 几何表示 │
├────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────────┐ ┌──────────────────┐ │
│ │ 边界表示 │ │ 体积表示 │ │
│ │ (B-Rep) │ │ (Volume) │ │
│ ├──────────────────┤ ├──────────────────┤ │
│ │ • 多边形网格 │ │ • 体素 │ │
│ │ • 曲面 │ │ • CSG │ │
│ │ • 细分曲面 │ │ • 隐式曲面 │ │
│ └──────────────────┘ └──────────────────┘ │
│ │
│ ┌──────────────────┐ ┌──────────────────┐ │
│ │ 参数表示 │ │ 过程表示 │ │
│ │ (Parametric) │ │ (Procedural) │ │
│ ├──────────────────┤ ├──────────────────┤ │
│ │ • 贝塞尔曲面 │ │ • 分形 │ │
│ │ • NURBS │ │ • L-系统 │ │
│ │ • B-样条曲面 │ │ • 噪声 │ │
│ └──────────────────┘ └──────────────────┘ │
│ │
└────────────────────────────────────────────────────────────┘7.1.2 各种表示的对比
| 表示方法 | 优点 | 缺点 | 应用场景 |
|---|---|---|---|
| 多边形网格 | GPU 友好、简单 | 不精确 | 游戏、实时渲染 |
| NURBS | 精确、光滑 | 复杂 | CAD/CAM |
| 细分曲面 | 任意拓扑、光滑 | 计算量大 | 动画、电影 |
| 体素 | 布尔运算简单 | 内存大 | 医学成像 |
| CSG | 精确、便于编辑 | 渲染复杂 | CAD |
| 隐式曲面 | 拓扑变化自然 | 渲染困难 | 特效 |
7.2 多边形网格
7.2.1 网格的基本概念
多边形网格的组成
多边形网格由三种基本元素组成：
1. 顶点（Vertex）：3D 空间中的点
2. 边（Edge）：连接两个顶点的线段
3. 面（Face）：由边围成的多边形
三角形网格示例：
V2
/\
/ \
/ \
/ F1 \
/ \
V0────────V1
顶点：V0, V1, V2
边： E0(V0-V1), E1(V1-V2), E2(V2-V0)
面： F1(V0, V1, V2)
欧拉公式：
V - E + F = 2（对于简单多面体）
例如：立方体
V = 8, E = 12, F = 6
8 - 12 + 6 = 2 ✓7.2.2 网格数据
网格包含的数据
基本几何数据：
- 顶点位置 (x, y, z)
附加属性（per-vertex）：
- 法向量 (nx, ny, nz)
- 纹理坐标 (u, v)
- 顶点颜色 (r, g, b, a)
- 骨骼权重（动画用）
拓扑信息：
- 顶点索引（定义面）
- 邻接关系（可选）
示例数据结构：
vertices = [
{ position: [0, 0, 0], normal: [0, 1, 0], uv: [0, 0] },
{ position: [1, 0, 0], normal: [0, 1, 0], uv: [1, 0] },
{ position: [1, 0, 1], normal: [0, 1, 0], uv: [1, 1] },
{ position: [0, 0, 1], normal: [0, 1, 0], uv: [0, 1] }
]
indices = [
0, 1, 2, // 第一个三角形
0, 2, 3 // 第二个三角形
]7.2.3 JavaScript 网格实现
javascript
/**
* 三角形网格类
*/
class TriangleMesh {
constructor() {
this.vertices = []; // 顶点位置数组
this.normals = []; // 法向量数组
this.uvs = []; // 纹理坐标数组
this.indices = []; // 索引数组
}
/**
* 添加顶点
*/
addVertex(position, normal = null, uv = null) {
const index = this.vertices.length;
this.vertices.push({ ...position });
if (normal) this.normals.push({ ...normal });
if (uv) this.uvs.push({ ...uv });
return index;
}
/**
* 添加三角形（通过索引）
*/
addTriangle(i0, i1, i2) {
this.indices.push(i0, i1, i2);
}
/**
* 计算面法向量
*/
computeFaceNormal(i0, i1, i2) {
const v0 = this.vertices[i0];
const v1 = this.vertices[i1];
const v2 = this.vertices[i2];
// 边向量
const e1 = {
x: v1.x - v0.x,
y: v1.y - v0.y,
z: v1.z - v0.z
};
const e2 = {
x: v2.x - v0.x,
y: v2.y - v0.y,
z: v2.z - v0.z
};
// 叉积
const normal = {
x: e1.y * e2.z - e1.z * e2.y,
y: e1.z * e2.x - e1.x * e2.z,
z: e1.x * e2.y - e1.y * e2.x
};
// 归一化
const len = Math.sqrt(
normal.x * normal.x +
normal.y * normal.y +
normal.z * normal.z
);
if (len > 0) {
normal.x /= len;
normal.y /= len;
normal.z /= len;
}
return normal;
}
/**
* 计算所有顶点的法向量（平滑着色）
*/
computeVertexNormals() {
// 初始化法向量
this.normals = this.vertices.map(() => ({ x: 0, y: 0, z: 0 }));
// 累加每个面对顶点法向量的贡献
for (let i = 0; i < this.indices.length; i += 3) {
const i0 = this.indices[i];
const i1 = this.indices[i + 1];
const i2 = this.indices[i + 2];
const faceNormal = this.computeFaceNormal(i0, i1, i2);
// 累加到顶点
for (const idx of [i0, i1, i2]) {
this.normals[idx].x += faceNormal.x;
this.normals[idx].y += faceNormal.y;
this.normals[idx].z += faceNormal.z;
}
}
// 归一化
for (const normal of this.normals) {
const len = Math.sqrt(
normal.x * normal.x +
normal.y * normal.y +
normal.z * normal.z
);
if (len > 0) {
normal.x /= len;
normal.y /= len;
normal.z /= len;
}
}
}
/**
* 计算包围盒
*/
computeBoundingBox() {
let min = { x: Infinity, y: Infinity, z: Infinity };
let max = { x: -Infinity, y: -Infinity, z: -Infinity };
for (const v of this.vertices) {
min.x = Math.min(min.x, v.x);
min.y = Math.min(min.y, v.y);
min.z = Math.min(min.z, v.z);
max.x = Math.max(max.x, v.x);
max.y = Math.max(max.y, v.y);
max.z = Math.max(max.z, v.z);
}
return { min, max };
}
/**
* 计算表面积
*/
computeSurfaceArea() {
let area = 0;
for (let i = 0; i < this.indices.length; i += 3) {
const v0 = this.vertices[this.indices[i]];
const v1 = this.vertices[this.indices[i + 1]];
const v2 = this.vertices[this.indices[i + 2]];
// 三角形面积 = |AB × AC| / 2
const e1 = { x: v1.x - v0.x, y: v1.y - v0.y, z: v1.z - v0.z };
const e2 = { x: v2.x - v0.x, y: v2.y - v0.y, z: v2.z - v0.z };
const cross = {
x: e1.y * e2.z - e1.z * e2.y,
y: e1.z * e2.x - e1.x * e2.z,
z: e1.x * e2.y - e1.y * e2.x
};
area += Math.sqrt(
cross.x * cross.x +
cross.y * cross.y +
cross.z * cross.z
) / 2;
}
return area;
}
/**
* 转换为 WebGL 缓冲区格式
*/
toBuffers() {
const positions = new Float32Array(this.vertices.length * 3);
const normals = this.normals.length > 0
? new Float32Array(this.normals.length * 3)
: null;
const uvs = this.uvs.length > 0
? new Float32Array(this.uvs.length * 2)
: null;
const indices = new Uint16Array(this.indices);
for (let i = 0; i < this.vertices.length; i++) {
positions[i * 3] = this.vertices[i].x;
positions[i * 3 + 1] = this.vertices[i].y;
positions[i * 3 + 2] = this.vertices[i].z;
if (normals && this.normals[i]) {
normals[i * 3] = this.normals[i].x;
normals[i * 3 + 1] = this.normals[i].y;
normals[i * 3 + 2] = this.normals[i].z;
}
if (uvs && this.uvs[i]) {
uvs[i * 2] = this.uvs[i].u;
uvs[i * 2 + 1] = this.uvs[i].v;
}
}
return { positions, normals, uvs, indices };
}
}7.3 网格数据结构
7.3.1 索引面集
索引面集（Indexed Face Set）
最简单的网格表示，分离存储顶点和面：
顶点数组：
V0: (0, 0, 0)
V1: (1, 0, 0)
V2: (1, 1, 0)
V3: (0, 1, 0)
面数组（索引）：
F0: [0, 1, 2]
F1: [0, 2, 3]
优点：
- 简单、紧凑
- GPU 友好
缺点：
- 查询邻接关系需要遍历
- 不便于局部编辑7.3.2 半边结构
半边数据结构（Half-Edge）
每条边存储为两个相反方向的"半边"：
V2
/\
/ \
h3/ \h2
/ F0 \
/ \
V0───h0───►V1
◄──h1──
\ F1 /
\ /
h4\ /h5
\/
V3
每个半边存储：
- 起点（vertex）
- 所属面（face）
- 下一条半边（next）
- 相反半边（twin/opposite）
半边的遍历：
绕顶点遍历所有邻接面：
从任意出射半边开始，不断取 twin->next
绕面遍历所有顶点：
从任意半边开始，不断取 next7.3.3 半边结构实现
javascript
/**
* 半边
*/
class HalfEdge {
constructor() {
this.vertex = null; // 终点顶点
this.face = null; // 所属面
this.next = null; // 下一条半边（同一面内）
this.prev = null; // 上一条半边
this.twin = null; // 对偶半边
}
}
/**
* 顶点
*/
class HEVertex {
constructor(x, y, z) {
this.x = x;
this.y = y;
this.z = z;
this.halfEdge = null; // 一条出射半边
}
}
/**
* 面
*/
class HEFace {
constructor() {
this.halfEdge = null; // 面上的一条半边
}
/**
* 获取面的所有顶点
*/
vertices() {
const result = [];
let he = this.halfEdge;
do {
result.push(he.vertex);
he = he.next;
} while (he !== this.halfEdge);
return result;
}
}
/**
* 半边网格
*/
class HalfEdgeMesh {
constructor() {
this.vertices = [];
this.faces = [];
this.halfEdges = [];
}
/**
* 从索引网格创建半边结构
*/
static fromIndexedMesh(positions, indices) {
const mesh = new HalfEdgeMesh();
// 创建顶点
for (let i = 0; i < positions.length; i += 3) {
const v = new HEVertex(
positions[i],
positions[i + 1],
positions[i + 2]
);
mesh.vertices.push(v);
}
// 用于查找对偶半边
const edgeMap = new Map();
function edgeKey(v1, v2) {
return `${Math.min(v1, v2)}_${Math.max(v1, v2)}`;
}
// 创建面和半边
for (let i = 0; i < indices.length; i += 3) {
const face = new HEFace();
mesh.faces.push(face);
const faceIndices = [indices[i], indices[i + 1], indices[i + 2]];
const faceHalfEdges = [];
// 创建三条半边
for (let j = 0; j < 3; j++) {
const he = new HalfEdge();
he.vertex = mesh.vertices[faceIndices[(j + 1) % 3]];
he.face = face;
mesh.halfEdges.push(he);
faceHalfEdges.push(he);
// 设置顶点的出射半边
if (!mesh.vertices[faceIndices[j]].halfEdge) {
mesh.vertices[faceIndices[j]].halfEdge = he;
}
}
// 设置 next 和 prev
for (let j = 0; j < 3; j++) {
faceHalfEdges[j].next = faceHalfEdges[(j + 1) % 3];
faceHalfEdges[j].prev = faceHalfEdges[(j + 2) % 3];
}
face.halfEdge = faceHalfEdges[0];
// 查找并设置对偶半边
for (let j = 0; j < 3; j++) {
const v1 = faceIndices[j];
const v2 = faceIndices[(j + 1) % 3];
const key = edgeKey(v1, v2);
if (edgeMap.has(key)) {
const twin = edgeMap.get(key);
faceHalfEdges[j].twin = twin;
twin.twin = faceHalfEdges[j];
} else {
edgeMap.set(key, faceHalfEdges[j]);
}
}
}
return mesh;
}
/**
* 获取顶点的所有邻接面
*/
getVertexFaces(vertex) {
const faces = [];
let he = vertex.halfEdge;
const start = he;
do {
if (he.face) faces.push(he.face);
he = he.twin?.next;
} while (he && he !== start);
return faces;
}
/**
* 获取顶点的所有邻接顶点
*/
getVertexNeighbors(vertex) {
const neighbors = [];
let he = vertex.halfEdge;
const start = he;
do {
neighbors.push(he.vertex);
he = he.twin?.next;
} while (he && he !== start);
return neighbors;
}
/**
* 获取边的两个邻接面
*/
getEdgeFaces(halfEdge) {
return [halfEdge.face, halfEdge.twin?.face].filter(f => f);
}
/**
* 边翻转（用于网格优化）
*/
flipEdge(halfEdge) {
if (!halfEdge.twin) return false; // 边界边
const he = halfEdge;
const twin = he.twin;
// 获取四个顶点
const a = he.next.vertex;
const b = twin.next.vertex;
const c = he.vertex;
const d = twin.vertex;
// 更新半边连接
// ... （复杂的指针操作）
return true;
}
}7.4 细分曲面
7.4.1 细分曲面的概念
细分曲面（Subdivision Surface）
通过递归细分低分辨率网格，生成光滑曲面。
初始 一次细分 多次细分
┌────────┐ ┌──┬──┬──┐ 更加光滑...
│ │ ├──┼──┼──┤
│ │ ──► ├──┼──┼──┤ ──►
│ │ ├──┼──┼──┤
└────────┘ └──┴──┴──┘
常见的细分方案：
1. Catmull-Clark（四边形网格）
- 应用最广泛
- 极限曲面是 C² 连续的双三次 B-样条
2. Loop（三角形网格）
- 专用于三角形
- 极限曲面是 C² 连续的
3. Doo-Sabin
- 较早的方案
- 双二次 B-样条7.4.2 Catmull-Clark 细分
Catmull-Clark 细分规则
步骤：
1. 面点（Face Point）：面的中心点
F = 面所有顶点的平均
2. 边点（Edge Point）：
E = (V1 + V2 + F1 + F2) / 4
其中 V1, V2 是边端点，F1, F2 是邻接面点
3. 新顶点位置（Vertex Point）：
V' = (Q + 2R + (n-3)V) / n
其中：
- Q = 邻接面点平均
- R = 邻接边中点平均
- n = 顶点的度（邻接边数）
图示：
原始网格： 细分后：
V1────────V2 V1──E1──F──E2──V2
│ │ │ │ │ │
│ F │ ──► E4──●───●───E5
│ │ │ │ │ │
V4────────V3 V4──E3──F──E6──V3
F: 面点
E1-E6: 边点
V1'-V4': 新顶点位置7.4.3 Catmull-Clark 实现
javascript
/**
* Catmull-Clark 细分
*/
class CatmullClarkSubdivision {
/**
* 执行一次细分
* @param mesh 输入网格（四边形面）
* @returns 细分后的网格
*/
static subdivide(mesh) {
const newMesh = new TriangleMesh();
// 1. 计算面点
const facePoints = [];
for (const face of mesh.faces) {
const vertices = face.vertices();
const fp = {
x: vertices.reduce((s, v) => s + v.x, 0) / vertices.length,
y: vertices.reduce((s, v) => s + v.y, 0) / vertices.length,
z: vertices.reduce((s, v) => s + v.z, 0) / vertices.length
};
facePoints.push(fp);
}
// 2. 计算边点
const edgePoints = new Map();
for (const he of mesh.halfEdges) {
if (edgePoints.has(he) || (he.twin && edgePoints.has(he.twin))) {
continue;
}
const v1 = he.prev.vertex;
const v2 = he.vertex;
let ep;
if (he.twin) {
// 内部边：使用面点
const f1 = mesh.faces.indexOf(he.face);
const f2 = mesh.faces.indexOf(he.twin.face);
const fp1 = facePoints[f1];
const fp2 = facePoints[f2];
ep = {
x: (v1.x + v2.x + fp1.x + fp2.x) / 4,
y: (v1.y + v2.y + fp1.y + fp2.y) / 4,
z: (v1.z + v2.z + fp1.z + fp2.z) / 4
};
} else {
// 边界边：简单中点
ep = {
x: (v1.x + v2.x) / 2,
y: (v1.y + v2.y) / 2,
z: (v1.z + v2.z) / 2
};
}
edgePoints.set(he, ep);
if (he.twin) edgePoints.set(he.twin, ep);
}
// 3. 计算新顶点位置
const vertexPoints = [];
for (let i = 0; i < mesh.vertices.length; i++) {
const v = mesh.vertices[i];
// 获取邻接信息
const adjacentFaces = mesh.getVertexFaces(v);
const adjacentEdges = [];
let he = v.halfEdge;
const start = he;
do {
adjacentEdges.push(he);
he = he.twin?.next;
} while (he && he !== start);
const n = adjacentEdges.length;
if (n < 3) {
// 边界顶点：保持位置或使用边界规则
vertexPoints.push({ ...v });
continue;
}
// Q: 邻接面点平均
const Q = { x: 0, y: 0, z: 0 };
for (const face of adjacentFaces) {
const fi = mesh.faces.indexOf(face);
Q.x += facePoints[fi].x;
Q.y += facePoints[fi].y;
Q.z += facePoints[fi].z;
}
Q.x /= adjacentFaces.length;
Q.y /= adjacentFaces.length;
Q.z /= adjacentFaces.length;
// R: 邻接边中点平均
const R = { x: 0, y: 0, z: 0 };
for (const edge of adjacentEdges) {
const mid = {
x: (v.x + edge.vertex.x) / 2,
y: (v.y + edge.vertex.y) / 2,
z: (v.z + edge.vertex.z) / 2
};
R.x += mid.x;
R.y += mid.y;
R.z += mid.z;
}
R.x /= n;
R.y /= n;
R.z /= n;
// 新顶点位置
const vp = {
x: (Q.x + 2 * R.x + (n - 3) * v.x) / n,
y: (Q.y + 2 * R.y + (n - 3) * v.y) / n,
z: (Q.z + 2 * R.z + (n - 3) * v.z) / n
};
vertexPoints.push(vp);
}
// 4. 构建新网格
// 每个原始面变成多个四边形
// ... （创建新顶点和面的连接）
return newMesh;
}
}
/**
* Loop 细分（三角形网格）
*/
class LoopSubdivision {
/**
* 执行一次细分
*/
static subdivide(mesh) {
const newMesh = new TriangleMesh();
// 计算边点（每条边的中点，加权）
const edgeVertices = new Map();
// 计算新顶点位置
const newPositions = [];
for (let i = 0; i < mesh.vertices.length; i++) {
const v = mesh.vertices[i];
const neighbors = mesh.getVertexNeighbors(mesh.vertices[i]);
const n = neighbors.length;
// Loop 细分的 beta 系数
let beta;
if (n === 3) {
beta = 3 / 16;
} else {
beta = 3 / (8 * n);
}
// 新位置 = (1 - n*beta) * v + beta * sum(neighbors)
const sumNeighbors = { x: 0, y: 0, z: 0 };
for (const neighbor of neighbors) {
sumNeighbors.x += neighbor.x;
sumNeighbors.y += neighbor.y;
sumNeighbors.z += neighbor.z;
}
newPositions.push({
x: (1 - n * beta) * v.x + beta * sumNeighbors.x,
y: (1 - n * beta) * v.y + beta * sumNeighbors.y,
z: (1 - n * beta) * v.z + beta * sumNeighbors.z
});
}
// ... 继续构建细分网格
return newMesh;
}
}7.5 网格简化
7.5.1 简化的目的
网格简化（Mesh Simplification）
目的：减少网格的面数，同时尽量保持外观。
高细节网格（10000 面）: 简化后（1000 面）:
╱╲╱╲╱╲╱╲ ╱╲╱╲
╱╲╱╲╱╲╱╲╱╲ ╱╲╱╲╱╲
╱╲╱╲╱╲╱╲╱╲╱╲ ──► ╱╲╱╲╱╲╱╲
╲╱╲╱╲╱╲╱╲╱ ╲╱╲╱╲╱
╲╱╲╱╲╱╲╱ ╲╱╲╱
应用场景：
- LOD（Level of Detail）
- 实时渲染优化
- 网络传输
- 存储优化7.5.2 边折叠算法
边折叠（Edge Collapse）
将一条边的两个端点合并为一个点。
V1 V1 V1
/|\ / \ / \
/ | \ / \ / \
/ | \ ──► / V01 \ ──► / V01 \
V2──●───V3 V2─────V3 V2─────V3
V0
边 V0-V1 折叠，V0 和 V1 合并为 V01
简化策略：
1. 计算每条边的"代价"（误差度量）
2. 选择代价最小的边进行折叠
3. 更新受影响边的代价
4. 重复直到达到目标面数
常用误差度量：
1. 边长度（简单但效果差）
2. 二次误差度量（QEM）★
3. 曲率7.5.3 QEM 简化实现
javascript
/**
* 二次误差度量（QEM）网格简化
*/
class QEMSimplification {
constructor(mesh) {
this.mesh = mesh;
this.quadrics = []; // 每个顶点的 Q 矩阵
this.edgeHeap = []; // 边的优先队列
}
/**
* 计算顶点的 Q 矩阵
*/
computeVertexQuadric(vertexIndex) {
const Q = this.createZeroMatrix4();
const vertex = this.mesh.vertices[vertexIndex];
const faces = this.mesh.getVertexFaces(vertex);
for (const face of faces) {
// 计算面的平面方程 ax + by + cz + d = 0
const normal = this.mesh.computeFaceNormal(face);
const d = -(
normal.x * vertex.x +
normal.y * vertex.y +
normal.z * vertex.z
);
// Q += p * p^T（外积）
const p = [normal.x, normal.y, normal.z, d];
for (let i = 0; i < 4; i++) {
for (let j = 0; j < 4; j++) {
Q[i][j] += p[i] * p[j];
}
}
}
return Q;
}
/**
* 计算边折叠的代价
*/
computeEdgeCost(v1Index, v2Index) {
const Q1 = this.quadrics[v1Index];
const Q2 = this.quadrics[v2Index];
// Q_bar = Q1 + Q2
const Q_bar = this.addMatrices(Q1, Q2);
// 找最优收缩点（使误差最小的位置）
// 简化版本：使用边中点
const v1 = this.mesh.vertices[v1Index];
const v2 = this.mesh.vertices[v2Index];
const midpoint = {
x: (v1.x + v2.x) / 2,
y: (v1.y + v2.y) / 2,
z: (v1.z + v2.z) / 2
};
// 计算误差 v^T * Q_bar * v
const v = [midpoint.x, midpoint.y, midpoint.z, 1];
let cost = 0;
for (let i = 0; i < 4; i++) {
for (let j = 0; j < 4; j++) {
cost += v[i] * Q_bar[i][j] * v[j];
}
}
return { cost, position: midpoint };
}
/**
* 执行简化
* @param targetFaceCount 目标面数
*/
simplify(targetFaceCount) {
// 初始化 Q 矩阵
for (let i = 0; i < this.mesh.vertices.length; i++) {
this.quadrics.push(this.computeVertexQuadric(i));
}
// 初始化边堆
this.initializeEdgeHeap();
// 迭代折叠边
while (this.mesh.faces.length > targetFaceCount &&
this.edgeHeap.length > 0) {
// 取出代价最小的边
const edge = this.popMinCostEdge();
if (!this.isValidCollapse(edge)) {
continue;
}
// 执行折叠
this.collapseEdge(edge);
// 更新受影响顶点的 Q 和边代价
this.updateAffectedEdges(edge.newVertex);
}
return this.mesh;
}
/**
* 检查折叠是否有效（防止网格翻转等问题）
*/
isValidCollapse(edge) {
// 检查拓扑有效性
// 检查法向量翻转
// ...
return true;
}
// 辅助方法
createZeroMatrix4() {
return [[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]];
}
addMatrices(A, B) {
const result = this.createZeroMatrix4();
for (let i = 0; i < 4; i++) {
for (let j = 0; j < 4; j++) {
result[i][j] = A[i][j] + B[i][j];
}
}
return result;
}
}7.6 布尔运算
7.6.1 CSG 布尔运算
构造实体几何（CSG）
通过基本体素的布尔运算构造复杂几何体。
基本运算：
1. 并（Union）：A ∪ B
┌───┐ ┌───────┐
│ A │ ∪ │ A ∪ B │
│ └───┐ │ │
└───┤ B │ = └───────┘
└───┘
2. 交（Intersection）：A ∩ B
┌───┐
│ A │ ∩ ┌─┐
│ └───┐ │ │ ← A 和 B 的重叠部分
└───┤ B │ = └─┘
└───┘
3. 差（Difference）：A - B
┌───┐ ┌──┐
│ A │ - │ │ ← A 减去与 B 重叠的部分
│ └───┐ │ │
└───┤ B │ = └──┘
└───┘7.6.2 网格布尔运算
javascript
/**
* 网格布尔运算（简化实现）
* 实际生产中推荐使用专业库如 libigl、CGAL
*/
class MeshBoolean {
/**
* 计算两个网格的并集
*/
static union(meshA, meshB) {
// 1. 找到所有相交的三角形
const intersections = this.findIntersections(meshA, meshB);
// 2. 细分相交的三角形
const subdividedA = this.subdivideAtIntersections(meshA, intersections);
const subdividedB = this.subdivideAtIntersections(meshB, intersections);
// 3. 分类三角形（在内部/外部）
const classifiedA = this.classifyTriangles(subdividedA, meshB);
const classifiedB = this.classifyTriangles(subdividedB, meshA);
// 4. 组合：A 外部 + B 外部
const result = new TriangleMesh();
for (const tri of classifiedA.outside) {
result.addTriangleFromMesh(tri);
}
for (const tri of classifiedB.outside) {
result.addTriangleFromMesh(tri);
}
return result;
}
/**
* 计算两个网格的交集
*/
static intersection(meshA, meshB) {
// 类似并集，但保留 A 内部 + B 内部
// ...
}
/**
* 计算 A - B（差集）
*/
static difference(meshA, meshB) {
// 保留 A 外部 + B 内部（翻转法向）
// ...
}
/**
* 找到两个网格之间的所有三角形相交
*/
static findIntersections(meshA, meshB) {
const intersections = [];
// 使用 BVH 加速
const bvhA = new BVH(meshA);
const bvhB = new BVH(meshB);
// 找到可能相交的三角形对
const candidates = bvhA.intersectBVH(bvhB);
// 精确测试每对三角形
for (const [triA, triB] of candidates) {
const intersection = this.triangleTriangleIntersection(triA, triB);
if (intersection) {
intersections.push(intersection);
}
}
return intersections;
}
/**
* 三角形与三角形相交测试
*/
static triangleTriangleIntersection(triA, triB) {
// Möller 算法或其他方法
// 返回交线段或 null
// ...
return null;
}
/**
* 判断点是否在网格内部
*/
static isPointInsideMesh(point, mesh) {
// 射线法：从点发射射线，计算与网格的交点数
// 奇数个交点 → 在内部
// 偶数个交点 → 在外部
const ray = {
origin: point,
direction: { x: 1, y: 0, z: 0 } // 任意方向
};
let count = 0;
for (let i = 0; i < mesh.indices.length; i += 3) {
const v0 = mesh.vertices[mesh.indices[i]];
const v1 = mesh.vertices[mesh.indices[i + 1]];
const v2 = mesh.vertices[mesh.indices[i + 2]];
if (this.rayTriangleIntersection(ray, v0, v1, v2)) {
count++;
}
}
return count % 2 === 1;
}
}7.7 本章小结
核心概念
| 概念 | 说明 | 应用 |
|---|---|---|
| 多边形网格 | 顶点、边、面组成的结构 | 实时渲染 |
| 半边结构 | 方便查询邻接关系的数据结构 | 网格编辑 |
| 细分曲面 | 递归细分生成光滑曲面 | 动画、电影 |
| 网格简化 | 减少面数保持外观 | LOD |
| 布尔运算 | 网格的交、并、差 | CAD |
数据结构对比
| 结构 | 存储复杂度 | 邻接查询 | 编辑效率 |
|---|---|---|---|
| 索引面集 | O(V + F) | O(F) | 低 |
| 半边结构 | O(E) | O(1) | 高 |
| 邻接列表 | O(V + E) | O(degree) | 中 |
关键要点
- 多边形网格是最常用的几何表示
- 半边结构方便邻接查询和网格编辑
- Catmull-Clark 是最常用的细分方案
- QEM 是高质量网格简化的标准方法
- 布尔运算在 CAD 中广泛应用
下一章预告：在第8章中，我们将学习可见性与遮挡算法，包括深度缓冲、背面剔除和遮挡剔除。
文档版本：v1.0
字数统计：约 11,000 字