第1章 四叉树和八叉树 1
) j( n' i7 G* j1.1 定义 1. f& d' c1 Q: B% a% a
1.2 复杂性与构造 24 ?! O# I, J; z% E# z0 a
1.3 高度场可视化 3
1 N3 A( ?% ^0 @2 r6 e* b1.4 等值面生成 7
" d# X0 L, V, j, l1.5 光线发射 10
/ }4 R' ^8 }% V3 L1 Z( T4 G- z0 S! `2 y1.6 3D八叉树 11
" E# d B% N/ q1 k+ _1 z2 e0 Q1.7 5D八叉树 14
: b% ?, p+ U/ t* _. D- f% K第2章 正交截窗和穿刺查询 194 U' t! Y% f: N. N. O; k- x
2.1 区间树 20! K8 T0 n: H- J' w# x3 r, b( S
2.2 线段树 23* z% u3 k( p: n- I9 n) x" d" t5 m
2.3 多层线段树 286 g* u; P* G% y) g. |. e
2.4 kd树 32
( f% `+ r6 |4 S: o {8 U9 m l; S* ?; p+ H2.5 范围树 36
]* N' B, c+ Z8 W/ {6 g2.6 （轴平行框/轴平行框）截窗问题 40
{3 c) W; F, M8 `! ^, w2.7 纹理合成 43 Z4 a/ j- J: \: F3 ]( [
2.8 形状匹配 45. K+ r( o% S) f2 K- r
第3章 BSP树 47
7 \ x3 L# Q3 e I& A0 J3.1 没有Z缓冲区的渲染 48
, B, n' o! r( j# q3.2 使用BSP表示对象 50
8 u" g: a- E- q' e6 K8 r" }2 _6 u3.3 布尔运算 50
/ C. f a' I, x+ z3.4 构造启发式算法 54( g: w, Q, S/ f% g. k1 H
3.4.1 凸面对象 55$ ~' S* o1 A/ r; s
3.4.2 成本驱动的启发式算法 55. j+ f) ?; H2 t& m
3.4.3 非均匀查询 567 D' H* ]8 Z6 C. n, J, y* b
3.4.4 推迟的自组织性BSP 57
3 E. L9 W6 L0 {; n" L6 j0 f( S
1 i" l( U8 U" m. H; m3 p. {第4章 包围体分层结构 59( d a& N7 ~/ ]2 g" c* X9 b8 e
4.1 BVH的构造 63
* k8 `: `4 l- K. I/ T& l: W$ H4.1.1 构造标准 65* \5 V y! z8 q% l
4.1.2 用于碰撞检测的标准 67
' w# L6 {4 e9 M4.1.3 构造算法 68/ ?- i, K5 {4 s4 K. D
4.2 更新渐变对象 70
' i ?3 N0 b4 a4.3 碰撞检测 72
8 }* B" T. ]4 b! w, K- z2 h第5章 距离场 79( |0 }' c: Z! O& I' f8 p. z/ E
5.1 距离场的计算和表示 81( l+ G, s& s+ w+ ?! X; o! W
5.1.1 传播方法 829 P9 n1 p9 H1 i$ x3 B. h
5.1.2 距离函数的投影 83
+ B+ Q) e4 [8 e' V5.2 距离场的应用 84
9 C0 N+ @- f# ^0 ~8 y/ x; I5.2.1 渐变变形 85 B9 l- P6 H% W3 B2 N# `7 `2 L5 M
5.2.2 造型 86( q0 I# S% G2 Q' G% o) F
第6章 Voronoi图 89
4 N/ ^+ H# |6 v0 ~) ]& h# Y+ j( k" q6.1 定义和属性 89
q2 H8 U1 \' _0 @- t" m6.1.1 二维中的Voronoi图 89
4 `/ ^, b& m' d0 Y. a3 ^" i6 t6.1.2 二维中的德洛内三角剖分 91
( l; [+ |" w. V0 t" ^ T6.2 计算 94* e1 n% a2 N5 E6 d% k! J0 r4 z
6.3 Voronoi图的推广应用 102! }3 ^9 C& o8 ~3 ~
6.3.1 在3D中的Voronoi图和德洛内三角剖分 102, W8 S, [/ L4 n, X# D0 a4 z4 Q
6.3.2 受约束的Voronoi图 107
Z) c2 D5 A% u4 I. i5 L; x" |6.3.3 一般化的类型 109, v& I) @$ @3 f4 h3 T3 y
6.4 Voronoi图的应用 113* e* j" U6 N) U, }
6.4.1 近邻或邮局问题 113$ G/ }: p. ?2 W9 b) e
6.4.2 Voronoi图在2D和3D中的其他应用 1203 U5 N% L- O5 w
6.5 计算机图形学中的Voronoi图 123
8 h% \5 i+ O' X6 t, x6.5.1 马赛克 123
: z& h) U; f8 {9 ~0 W! X# d6.5.2 自然邻居插值 130
2 E! S" h8 z" b' p0 g7 a |- K' K0 u1 h7 A9 {+ C& K
5 ?) M" H+ C7 ^, M: |3 Q# p* D6 P2 u
第7章 几何接近图形 1351 U0 r' h" ~7 F* _4 ~* |4 I
7.1 一个很小的接近图形集合 136
0 |4 D5 f, q2 o" d/ E! w7.1.1 初步定义 136
6 U/ ]% `4 I# a$ k7.1.2 一些接近图的定义 137! b& r# L8 A7 S* _9 z/ S* z8 x
7.1.3 包含属性 141- o9 f- V' A7 p$ h' E" l" O
7.1.4 构造算法 143' G: x4 @4 N( u3 M+ y/ ^
7.2 分类 146
0 `6 j H9 _' H: C9 v0 {7.2.1 问题描述 146
- `5 f9 v' r9 Q' e6 k9 k7.2.2 编辑和简化集合 148
1 z( H' g% U* g7.2.3 用于编辑的接近图形 149
* U4 r4 n' c( R# D2 E$ M7.2.4 清除训练集合 151
; Z. [4 p* U' q7.3 由点云定义的表面 152
8 s8 |5 B9 ^, n" C# ?7.3.1 隐式表面建模 153
) D/ J4 a, m3 K: ^* c7 x5 L7.3.2 欧几里得内核 155/ d- u/ k; l' \3 P2 a U( r
7.3.3 测地距离近似 155( o3 t- q! `+ ~ @0 m o; r! Q
7.3.4 自动带宽计算 156
$ K# J! P: I% O2 P; g4 p) g1 k7.3.5 自动边界检测 158
; o8 [6 k" P; W* D7.3.6 函数复杂度评估 158
9 A) \5 ?( P e% q$ a6 W7.4 点云之间的交叉检测 159
* K O5 V e* t7 V+ ^+ T* |' K7.4.1 根划界 160
# L( j1 Q$ N' A, p5 x2 }7.4.2 邻居的大小 161. k0 k( H- s4 T D5 ~ _/ ?
7.4.3 完成划界 1620 Y# l' r1 i! V& O
7.4.4 插值搜索 163
7 C: j1 X2 c( h' v4 C7.4.5 带边界的模型 1640 v" O8 o# M7 c1 P
7.4.6 精确的交点 165
# N* p4 G, W" E% a% e# U5 @7.4.7 运行时间 166* t8 P: I/ l! ~3 }
第8章 运动数据结构 169" O6 U7 |0 B- b6 ~
8.1 通用术语表 170
' P2 S9 I) {/ N4 ~3 v/ {4 t0 ^8.2 静态分段树 171; p9 i) ]* C6 }, y1 P. ^
8.3 运动分段树 172" x! }) @0 k# g! J
8.4 平面中的运动BSP 174) ]: ~7 [7 ?" N' Y# N/ y+ y
$ a2 Q7 N; T1 o! U9 w& b2 {
第9章 退化和鲁棒性 181; H% ^+ H, s; Q! s8 |$ u
9.1 几何算法中的不稳定性示例 183
1 N T+ }+ o$ S. M {8 F! f; s$ ]9.1.1 线段的交点 1838 E1 m; P4 W. ]; L
9.1.2 用超平面切割多面体 187
0 P; s) [; Z5 E. G9.2 鲁棒性和稳定性的正式定义 1892 b( b+ ]2 ?. s
9.3 几何计算与算术 191
( W1 y6 Y+ V" U f% [- l! y9.3.1 浮点运算 191( \& R, R/ j# G3 I$ e# P
9.3.2 精确算术 201) L7 G; p% ?, W; L# O; n, @5 R
9.3.3 鲁棒而高效的运算 206
0 I7 ^9 ^5 c+ r: ~( U9.3.4 精确几何计算（EGC） 223
! [, k7 D" N/ X0 Q( Q9.4 鲁棒的表达式和谓词 224) p% _8 s6 F* |$ R" A$ a
9.4.1 公式重排的示例 225
, S% V7 h9 Y3 |8 D9 C9.4.2 鲁棒表达式综述 2284 u" ?& e* O9 a+ S) \
9.4.3 对行列式的有效评估 238
4 o! G4 q8 n* L) H9.5 退化 239
' { L' h$ B3 j& v9.5.1 退化的形式定义 239) `, i! O1 o$ }2 d' V! q! e
9.5.2 符号扰动 240
4 T. u2 \1 n/ z& }* y9.5.3 直接扰动 248
: }! G- [+ I" v+ ?, ~9.6 不精确的算术方法 250& M Y2 F _( v4 ~6 K
9.6.1 Epsilon算术和近似谓词 250
4 @& u1 b+ d- k' _) O9.6.2 计算凸包 252
" r$ H" T% q9 y# L* m+ s9.7 实用建议和现有软件包 256/ F" i) M1 M4 L1 b, k
9.7.1 不精确算术和精确算术 256
; ?" f1 r3 K/ [/ S2 c- _" a1 v9.7.2 对于EGC的支持 256
# v# G0 t/ `6 F9.7.3 软件包和库 257
1 P0 n8 @( J: U$ T第10章 几何数据结构的动态化 261
- P5 ~8 x, W: B% a$ s- }10.1 动态化示例 262
7 @4 z3 w+ `4 }- J10.1.1 随着时间的推移分摊kd树插入操作 263& ?+ p7 V1 [" L. N9 S
10.1.2 静态kd树的二元分解 264" v+ Z% ~) {; |7 a2 I' d. C% V" t# p
10.1.3 在kd树二进制表示中的查询操作 266* `/ k: A/ e( ?5 W. n4 q/ _
10.1.4 通过半大小规则对kd树执行通用删除操作 2669 }: t. K+ z8 B0 o: D% G% X/ v
10.1.5 kd树的半大小规则和二进制分解 267
3 ]3 P; s0 f" e0 H10.2 动态化的模型 269
+ \- R( `" z* A8 [0 R! [4 X( |java8.com
2 v/ J1 E/ w, s; X10.3 分摊插入和删除 271
7 u$ Y' ~- ]7 t' L; M# `5 g10.3.1 分摊插入：二进制结构 271# {& ~1 R d+ D5 ~2 B* S# f
10.3.2 分摊删除：半大小规则 276
5 m9 ^/ O( D# o& u& Z10.3.3 分摊插入和分摊删除 2772 S% @6 z7 x8 L/ h4 E* N
10.4 坏情况下的动态化 279' }9 [3 Y+ N) D0 D6 r; ?5 {1 Y3 l" `
10.5 搜索查询数据结构的应用 283/ h# [' k4 i$ C* s0 c
参考文献 287
! z" j' _% p* s5 i5 q1 ^+ [
* G. `& p' X! t. X E8 J: P
电子书
2815 人阅读
|
24 人回复
|
2023-09-01
