【计算几何 十二章】空间二分：画家算法

本文涉及知识点

数学 几何

预备知识

O (Big O)：表示最坏情况下的时间复杂度，描述的是算法的上限或最差表现。 Ω (Big Omega)：表示最好情况下的时间复杂度，描述的是算法的下限或最佳表现。 Θ(1) — 确界（紧确界）它表示算法的运行时间既不会超过某个常数，也不会低于另一个常数。 圆盘：圆上的点和圆内的点，是一个区域而不是曲线。 奇数x，x/2+x/2+1=x；偶数x,x/2+x/2=x。

矩形不超过2k个点

一定存在合理划分，使得四个象限的点都不超过k。 任意水平直线l上有c2个点，直线上有c1个点，直线下有c3个点。使max(c1,c3)尽快的大，且max(c1,c3)

≤

\\le

≤ c2+Min(c1,c3)。 不失一般性，令

c

1

≤

c

3

c1 \\le c3

c1≤c3且c1在上方，c3在下方。c1及c2一个区分，c3一个区域。由于c3所在区域点数

≤

k

\\le k

≤k，故只需要考虑上半区域，即c1和c2所在区域。 一，c2是偶数，则

c

1

≥

c

3

c1 \\ge c3

c1≥c3。选择任意垂线，将c2上的点平分。假定c1的点全部分到左上，则左上的点数：

c

1

+

c

2

/

2

≤

c

3

+

c

2

/

2

c1+c2/2 \\le c3+c2/2

c1+c2/2≤c3+c2/2。两者相加是

2

k

，故

c

1

+

c

2

/

2

≤

k

2k，故c1+c2/2 \\le k

2k，故c1+c2/2≤k。 二,c2是奇数，则

c

1

+

1

≤

c

3

c1+1 \\le c3

c1+1≤c3选择任意垂线，将c2上的点平分。我们假设c1的点全部落在c2点多的区域，即共有

c

1

+

c

2

/

2

+

1

≤

c

3

+

c

2

/

2

c_1+c_2/2+1 \\le c_3+c_2/2

c1​+c2​/2+1≤c3​+c2​/2，两者之和

≤

2

k

，故

c

1

+

c

2

/

2

+

1

≤

k

\\le 2k，故c1+c2/2+1 \\le k

≤2k，故c1+c2/2+1≤k。

前言

z-缓冲算法(z-buffer algorithm)就是一种非常简明的隐藏面消除法，其过程如下。首先，对场景进行变换，使得视线方向为正的z-方向。接下来，安装任意次序对场景中的物体进行扫描转换。所谓的扫描转换，就是确定被改物体的投影所覆盖的那些像素–只有在这些位置，该物体才有可能是可见的。已经经过处理得到的右各物体的信息，被改算法存放在两个缓冲中–一个称为帧缓冲，另一个称为深度缓冲。帧缓冲中存储了与每个像素当前可见的物体的（光）强度。所谓“当前可见的物体”，就是在当前已经处理过的各物体中，与某像素可见的物体。深度缓冲中存储了当前与各个像素可见物体的z-坐标（更准确地，存储的是物体上与像素可见的那一点出的z-坐标）。现在，假定在对某提进行扫描转换的过程中，正在处理某一像素。若此物体在改像素处的z-坐标比当前存储在深度缓冲中的z-坐标更小，则说明该物体位于当前可见物体的前方。于是，就需要将这一新物体的（光）强度值存入帧缓冲，同时用新的z-坐标更新深度缓冲。反之，若物体在该像素处的z-坐标比深度缓冲中当前的z-坐标更多，则新的这一物体（在此像素处）将不可见，因此帧缓冲和深度缓冲都应该保持原样，z-缓冲算法可以很容易地借助硬件直接实现，因而实际的运行速度很快。正因为此，它称为最常用的隐藏面消除方法。该算法不足之处：深度缓冲需要额外占用大量的存储空间。而且，对于每个物体，被其覆盖的每一个像素都需要进行z-坐标的测试比较。 注释：可以想象自己站在

(

0

,

0

,

−

∞

)

(0,0,-\\infty)

(0,0,−∞) 画家算法则可以避免这些计算。该算法首先按照各物体到视点的距离，对其进行排序。然后，从距离视点最远的物体开发，安装所谓的“深度顺序”，对物体进行扫描转换。在对物体进行扫描转换的过程中，我们不需要对其z-坐标做任何的测试比较，即可其(光)强度值直接存入帧缓冲。即使原先帧缓冲中该位置已经存有数字，也可以尽管覆盖。 为了顺利地应用这一方法，必须能够快速地对所有物体进行排序。这样并不容易。按z序会产生循环。

以三个三角形为例，无论它们如何构成一个循环，我们总是能够将其中的一个切分为一个三角形和一个四边形，从而保证在这样的四个物体之间存在一个正确的显示次序。由于深度次序取决于视点的位置，所以在每次视点移动之后，都必须重新进行计算。如果向飞行模拟器这样的环境，要求以实时的速度运行画家算法，我们就需要对场景进行某种预处理，从而使得对任何一个视点，都能够快速计算出正确的显示顺序。这种优雅的数据结构就是 空间二分树(binary space partition tree BSPT)，简称BSP树。

BSP树的定义

任一超平面

h

:

a

1

x

1

+

a

2

x

2

+

⋯

+

a

d

x

d

+

a

d

+

1

=

0

h:a_1x_1+a_2x_2+\\cdots + a_dx_d+a_{d+1}=0

h:a1​x1​+a2​x2​+⋯+ad​xd​+ad+1​=0都确定了两个开的半空间，我们用

h

+

和

h

−

来表示正、负半空间。即

h^+和h^-来表示正、负半空间。即

h+和h−来表示正、负半空间。即。

h

+

:

=

{

(

x

1

,

x

2

,

⋯
 

,

x

d

)

∣

a

1

x

1

+

a

2

x

2

+

⋯

a

d

x

d

+

a

d

+

1

>

0

}

h^+ :=\\{(x_1,x_2,\\cdots ,x_d)|a_1x_1+a_2x_2+\\cdots a_dx_d + a_{d+1}>0\\}

h+:={(x1​,x2​,⋯,xd​)∣a1​x1​+a2​x2​+⋯ad​xd​+ad+1​>0}

h

−

:

=

{

(

x

1

,

x

2

,

⋯
 

,

x

d

)

∣

a

1

x

1

+

a

2

x

2

+

⋯

a

d

x

d

+

a

d

+

1

<

0

}

h^- :=\\{(x_1,x_2,\\cdots ,x_d)|a_1x_1+a_2x_2+\\cdots a_dx_d + a_{d+1}<0\\}

h−:={(x1​,x2​,⋯,xd​)∣a1​x1​+a2​x2​+⋯ad​xd​+ad+1​<0} 这样，对于d维空间任意n个物体所组成的集合S，与之对应的BSP树可以定义一棵具有如下性质的二叉树T: 若card(S)

≤

1

\\le 1

≤1，则T是一片叶子；S中的物体碎片（如果存在的话）被显示地存储在这匹叶子中。若将这匹叶子记作v，则存储于这片叶处的集合（可能是空集）被记作S(v)。 若card(S)>1，则T的根节点v存储的是一张超平面

h

v

h_v

hv​，以及哪些完全落在

h

v

h_v

hv​上的物体所组成的集合S(v)。v的左孩子是一棵BSP子树

T

−

T^-

T−的根，这棵树对应于

S

−

:

=

{

h

v

−

∩

s

∣

s

∈

S

}

S^-:=\\{h_v^- \\cap s| s \\in S\\}

S−:={hv−​∩s∣s∈S};v的右孩子为另一棵BSP子树

T

+

T^+

T+的根，这棵树对应于集合

S

+

:

=

{

h

v

+

∩

s

∣

s

∈

S

}

S^+ :=\\{ h_v^+ \\cap s| s\\in S\\}

S+:={hv+​∩s∣s∈S}。

BSP树的规模，定义为树中所有节点v所对应集合S(v)的总体规模。换而言之，一棵BSP树的规模就是所生成物体的碎片总数。若BSP中没有无用的分割线–即分割空子空间的分割线-则相对于BSP树的规模，树中节点的数目至多成线性正比关系。根据BSP的规模，并不能确定所需存储空间大小。 BSP将导出一个子区域划分,而BSP树中的叶子则分别表示其中的各张面。更一般地说，对于BSP树T中的每一个节点，我们都可以找出一个与之对应的凸子区域–这个子区域，就是半空间

h

u

t

的交集，其中

u

为

v

的祖先。若

v

来自

u

的左子树，则

t

=

−

；若来自右子树，则

t

=

+

h_u^t的交集，其中u为v的祖先。若v来自u的左子树，则t=-；若来自右子树，则t=+

hut​的交集，其中u为v的祖先。若v来自u的左子树，则t=−；若来自右子树，则t=+ BSP可用任意超平面进行分割。假设我们希望针对平面上的一组线段，构造出与之对应的BSP。利用线段所在直线作为分割线，称为一个自动划分。如果三维空间的一组平面多边形，那么此时的自动划分的分割线就是平面多边形所在平面。

2 BSP树及画家算法

假定已经针对三维空间中的一组物体S,已经构造了一棵BST树T。应该如何利用T来得到我们所需要的深度次序。设视点

P

v

i

e

w

P_{view}

Pview​，并假设相对于T根节点所在存储的那张超平面，

p

v

i

e

w

p_{view}

pview​位于其上方。显然，位于分割平面下方的任何物品，都不可能遮挡住位于上方的任何物体。先显示

T

−

，在显示

T

+

T^-，在显示T^+

T−，在显示T+，不会有问题。各子树内部也是如此。 如果

P

v

i

e

w

P_{view}

Pview​正好落在分割平面

h

v

h_v

hv​上时，我们并不画出S(v)中的任何多边形–因为多边形都二维平面物体，所以从与共面的任何一个点来看，它们都是不可见的。 假定，多面体的每个小平面都已经进行三角剖分。因此，我们的任务就是：针对三维空间中给定的一组三角形，构造出一棵规模尽快小的BSP树。

构造BSP树

平面BSP树

设S为平面上一组共n条互不相交的线段。我们暂且要求：只有S中各线段所在的直线，才能做分割线。下面这个构造BSP的递归算法，是不证自明的。任一线段s所在直线，记作l(s)。 算法：2DBsp(S) 输入：一组线段S={

s

1

,

s

2

,

⋯
 

,

s

n

s_1,s_2,\\cdots ,s_n

s1​,s2​,⋯,sn​} 输出：S的一棵BSP树 1 如果(card(S)

≤

1

\\le 1

≤1) 2. then 直接生成一棵只含有一片叶子的树T,集合S显示存储于其中 3. return T 4. else (

∗

将

l

(

s

1

)

作为一条分割线

∗

* 将l(s_1)作为一条分割线*

∗将l(s1​)作为一条分割线∗) 5.

S

+

←

{

s

∩

∣

(

s

1

)

+

∣

s

∈

S

}

;

T

+

←

2

D

B

s

p

(

S

+

)

S^+ \\leftarrow\\{ s \\cap |(s_1)^+| s \\in S\\};T^+ \\leftarrow 2DBsp(S^+)

S+←{s∩∣(s1​)+∣s∈S};T+←2DBsp(S+) 6.

S

−

←

s

∩

∣

(

s

1

)

−

∣

s

∈

S

;

T

−

←

2

D

B

s

p

(

S

−

)

S^- \\leftarrow { s\\cap |(s_1)^-|s \\in S};T^- \\leftarrow 2DBsp(S^-)

S−←s∩∣(s1​)−∣s∈S;T−←2DBsp(S−) 7. 升成一棵BSP树T

(

其根节点为

v

，左子树为

T

−

,

右子树为

T

+

)

,

而且

S

(

v

)

=

{

s

∈

S

∣

s

⊂

∣

(

s

1

)

}

)

(其根节点为v，左子树为T^-,右子树为T^+),而且S(v)=\\{ s \\in S | s \\sub |(s_1)\\})

(其根节点为v，左子树为T−,右子树为T+),而且S(v)={s∈S∣s⊂∣(s1​)}) 8 return T

选择分割线时，只用第一条线段

s

1

s_1

s1​。能否选用使得l(s)与尽可能少的线段相交的那条线段

s

∈

S

s \\in S

s∈S？不行，找出这样的线段，需要大量时间。较好的办法是随机选择。 算法 2DRandomBsp(S) 1 生成集合S中各线段的一个随机排列S’=

s

1

,

⋯
 

,

s

n

s_1,\\cdots,s_n

s1​,⋯,sn​ 2

T

←

2

D

B

s

p

(

S

′

)

T \\leftarrow 2DBsp(S')

T←2DBsp(S′) 3 return T

引理12.1：算法2DRandomBsp所生成碎片的期望数目为O(nlogn)。 定理12.2：可以在O(nnlogn)期望时间内，构造出一个规模为O(nlogn)的BSP。

4 三维 BSP 树的规模

选修内容，略。 定理12.5：对于

R

3

R^3

R3中任意一组共n个互不相交的三角形，都存在一棵规模为O(n^2)的BSP树。此外，的确存在某些构形，其任何BSP的规模至少是O(nn)。

5 低密度场景的BSP树

将物体o的直径记作diam(o)。对

R

d

R^d

Rd中的任意一组物体S，其密度为满足以下条件的最小

λ

\\lambda

λ。任意球体B最多与S中满足daim(o)

≥

\\ge

≥diam(B)的

λ

\\lambda

λ个物体

o

∈

S

o\\in S

o∈S相交。B本身不属于S，但中心位置、半径可以任取。 任意n个互不相交球体的密度均为Θ(1)。 设S为

R

2

中的一组物体

(

线段、圆盘、三角形等等

)

R^2中的一组物体(线段、圆盘、三角形等等)

R2中的一组物体(线段、圆盘、三角形等等),S的密度为

λ

\\lambda

λ。为每个物体

o

∈

S

定义少量的一组点

−

−

称为哨兵

(

g

u

a

r

d

)

o \\in S定义少量的一组点–称为哨兵(guard)

o∈S定义少量的一组点−−称为哨兵(guard)，使得哨兵的分布反应物体的分布，并进而依靠这些哨兵的辅助来构造BSP。 将o的包围框–即包围o、与坐标轴平行的最小矩形–记作bb(o)。于是，可以直接选取bb(o)的四个顶点作为o的哨兵。S中所有的物体的4n个哨兵。这4n个哨兵，组成一个多键集合(multiset),记作J(S)。低密度S的G(S)中的哨兵的确可以反映S中物体的分布；S中与任一正方形

σ

\\sigma

σ相交的物体，不会超过落在

σ

\\sigma

σ内部的哨兵数。用圆盘来定义二维空间的密码。 引理12.6：平行于坐标轴、内含G(S)中k各哨兵的正方形，至多与S中的

k

+

4

λ

k+4\\lambda

k+4λ个物体相交。 证明：任取平行于坐标轴，内含G(S)中k个哨兵的一个正方形

σ

\\sigma

σ。显然，

σ

\\sigma

σ内的哨兵至多来自k个物体。S中其余的物体，构成集合S’。S’的密度不超过

λ

\\lambda

λ。以下只需证明，S’中至多

4

l

a

m

b

d

a

个物体与

σ

相交

4lambda 个物体与\\sigma 相交

4lambda个物体与σ相交。 若物体

o

∈

S

′

与

σ

相交，则显然

b

b

(

o

)

也必然和

σ

o\\in S'与\\sigma相交，则显然bb(o)也必然和\\sigma

o∈S′与σ相交，则显然bb(o)也必然和σ相交。由S’的定义，bb(o)的顶点均不会落在正方形

σ

\\sigma

σ内部。于是如图12-21所示，要么bb(o)到x-轴的投影覆盖

σ

到

x

轴的投影

\\sigma 到x轴的投影

σ到x轴的投影，要么bb(o)到y-轴的投影覆盖

σ

\\sigma

σ到y轴的投影，甚至兼而有之。这就意味着，o的直径不会小于

σ

\\sigma

σ的边长。即

d

a

i

m

(

o

)

≥

d

i

a

m

(

σ

)

/

2

daim(o) \\ge diam(\\sigma)/\\sqrt 2

daim(o)≥diam(σ)/2

​。若以4个顶点圆心，直径为

d

i

a

m

(

σ

)

/

2

的圆盘

D

1

,

D

2

,

D

3

,

D

4

覆盖

σ

diam(\\sigma)/2的圆盘D_1,D_2,D_3,D_4覆盖\\sigma

diam(σ)/2的圆盘D1​,D2​,D3​,D4​覆盖σ，则物体o必与其中至少一个圆盘

D

i

D_i

Di​相交。将o计入

D

i

D_i

Di​的名下。于是有：

d

i

a

m

(

o

)

≥

d

i

a

m

(

σ

)

/

2

≥

d

i

a

m

(

σ

)

/

2

=

d

i

a

m

(

D

i

)

diam(o) \\ge diam(\\sigma)/\\sqrt 2 \\ge diam(\\sigma) /2 = diam(D_i)

diam(o)≥diam(σ)/2

​≥diam(σ)/2=diam(Di​) 既然S’的密度不超过

λ

\\lambda

λ，故每个

D

i

D_i

Di​至多有

λ

项入账

\\lambda项入账

λ项入账。因此，

s

i

g

m

a

至多与

S

′

中的

4

λ

个物体相交

sigma至多与S'中的4\\lambda个物体相交

sigma至多与S′中的4λ个物体相交

由引理12.6，可以导出以下两段式BSP构成算法。令U为包含S中所有物体的一个正方形。第一阶段：递归地对U做正方形划分，直到每个正方形包含的哨兵不超过一个。就是递归建立四叉树，每个象限一个子树。第二阶段：四叉树导出BSP树。 可能的问题，叶子的数量很多。调整一：适当选取一个参数k，任一区域一旦只包含不超过k个（而不是一个）哨兵，则不再细分。另一项调整如下。递归划分的过程中，需要对某一个正方形

σ

\\sigma

σ做细分。考察

σ

\\sigma

σ的四个象限，若其中的至少两个象限的内部含有超过k个哨兵，则沿用此前的方法实施一次四叉树分裂。如果某个象限哨兵均不超过k个。也要执行一次四叉树分裂。如果只有其中一个象限

σ

′

\\sigma'

σ′内包含多余k个哨兵，则需要进行一次紧缩(shrinking)操作,直观效果是不断压缩

σ

′

\\sigma'

σ′，直到至少有k个哨兵落到

σ

′

\\sigma'

σ′的外部。这意味着2k个哨兵后，只需要递归一次。 任一非正方形叶子

σ

′

′

\\sigma''

σ′′，都是某次紧缩的产物，一旦有k活更多个哨兵不再落在被紧缩象限

σ

′

\\sigma'

σ′的内部，紧缩操作旋即终止。这些哨兵中，至少有一个被

σ

′

\\sigma '

σ′的边界穿过，故而实际落在

σ

′

\\sigma'

σ′外包的哨兵不足k个。

引理12.7：构造的BSP树中，叶子数不超过O(n/k)，其中每块叶子区域至多

k

+

4

λ

k+4\\lambda

k+4λ个物体相交。 选取最佳k值应遵循如下原则：既能尽可能地减少叶子区域，同时也不至于显著增加各块叶子区域包含的物体。较好的值

k

:

=

λ

k:= \\lambda

k:=λ。我们并不知道

λ

\\lambda

λ，令 k=2，如果叶子区域相交的物体没有超过2k，则进行算法的下一阶段；否则k=2k，重新尝试。 定理12.8：由平面上任意n个互不相交物体组成的每一个集合S，都拥有一个规模为O(nlog

λ

)

\\lambda)

λ)的BSP，其中

λ

\\lambda

λ为S的密度。 定理12.9:由

R

3

R^3

R3中任意n个互不相交三角形组成的每一个集合S，都拥有一个规模为O(n

λ

)

的

B

S

P

，其中

λ

为

S

的密度

\\lambda)的BSP，其中\\lambda为S的密度

λ)的BSP，其中λ为S的密度。

扩展阅读

测试环境

操作系统：win7 开发环境： VS2019 C++17 或者 操作系统：win10 开发环境： VS2022 C++17 如无特殊说明，本算法用**C++**实现。