Ch.12: Binary Space Partitions

From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 12.1. The Definition of BSP Trees 12.2. BSP Trees and the Painter's Algorithm 12.3. Constructing a BSP Tree 12.4. The Size of BSP Trees in 3-Space 12.5. BSP Trees for Low-Density Scenes 12.6. Notes and Comments

82 flashcards · Mathematics · by lakesare

Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses

[Binary Space Partitions] What is hidden surface removal, and why is it a bottleneck in flight simulators?
Determining, for each pixel on the screen, which object is visible at that pixel. A flight simulator must render in real time, so shading is kept fast and simple, and hidden surface removal becomes an important part of the rendering time.
[Binary Space Partitions] How does the z-buffer algorithm do hidden surface removal?
Scan-convert the objects in any order; per pixel, keep the zzz -coordinate of the visible object in a z-buffer and overwrite a pixel only if the new object has smaller zzz . The scene is first transformed so that the viewing direction is the positive zzz -direction. The frame buffer stores each pixel's intensity, the z-buffer its zzz -coordinate.
[Binary Space Partitions] What are the two disadvantages of the z-buffer algorithm?
A lot of extra storage for the z-buffer, and an extra zzz -test for every pixel covered by an object. It is still the most popular method: simple and fast in hardware.
[Binary Space Partitions] How does the painter's algorithm do hidden surface removal?
Sort the objects by distance to the view point and scan-convert them back to front, simply overwriting the frame buffer. No z-buffer and no zzz -tests: for each pixel, the last object written is the closest one. Three triangles scan-converted in the order 1, 2, 3.
[Binary Space Partitions] The back-to-front order of the objects that the painter's algorithm needs is called the depth order.
[Binary Space Partitions] Why can the painter's algorithm fail even with unlimited sorting time?
A depth order may not exist: the in-front-of relation can contain cycles (a cyclic overlap). Then some objects must be split into pieces that do have a depth order, e.g. one triangle of a 3-cycle split into a triangle and a quadrilateral. Three triangles, each partly in front of the next.
[Binary Space Partitions] Why should a real-time application preprocess the scene for the painter's algorithm, rather than sort when drawing?
The depth order depends on the view point, so it would have to be recomputed (with splitting) every time the view point moves. The BSP tree is a structure from which a correct order can be read off quickly for any view point.
[The Definition of BSP Trees] How is a binary space partition (BSP) of a set of objects in the plane obtained?
Split the plane recursively with lines until each region contains only one object fragment in its interior. The splitting lines may cut objects into fragments. The recursion is a binary tree: internal nodes store the splitting lines, leaves store the fragments in the faces. ℓ1\ell_1ℓ1 splits the plane, ℓ2\ell_2ℓ2 the half-plane above ℓ1\ell_1ℓ1 , ℓ3\ell_3ℓ3 the half-plane below, and so on.
[The Definition of BSP Trees] For a hyperplane h:a1x1+⋯+adxd+ad+1=0h: a_1x_1 + \dots + a_dx_d + a_{d+1} = 0h:a1x1+⋯+adxd+ad+1=0 , what are h+h^+h+ and h−h^-h− ?
h+h^+h+ : the open half-space where a1x1+⋯+adxd+ad+1>0a_1x_1 + \dots + a_dx_d + a_{d+1} > 0a1x1+⋯+adxd+ad+1>0 ; h−h^-h− : the open half-space where it is <0< 0<0 .
[The Definition of BSP Trees] SSS is a set of objects in Rd\mathbb{R}^dRd . When is a binary tree T\mathcal{T}T a BSP tree for SSS , in the case card⁡(S)≤1\operatorname{card}(S) \le 1card(S)≤1 ?
T\mathcal{T}T is a single leaf, which stores the object fragment of SSS (if one exists). The (possibly empty) set stored at a leaf vvv is denoted S(v)S(v)S(v) .
[The Definition of BSP Trees] SSS is a set of objects in Rd\mathbb{R}^dRd with card⁡(S)>1\operatorname{card}(S) > 1card(S)>1 . What must the root vvv and its children store for a binary tree T\mathcal{T}T to be a BSP tree for SSS ?
vvv stores a hyperplane hvh_vhv and the set S(v)S(v)S(v) of objects fully contained in hvh_vhv ; the left child is a BSP tree for S−={hv−∩s:s∈S}S^- = \{h_v^- \cap s : s \in S\}S−={hv−∩s:s∈S} , the right child one for S+={hv+∩s:s∈S}S^+ = \{h_v^+ \cap s : s \in S\}S+={hv+∩s:s∈S} . For segments in the plane, S(v)S(v)S(v) is the list of segments lying in the splitting line.
[The Definition of BSP Trees] What is the size of a BSP tree?
The total size of the sets S(v)S(v)S(v) over all nodes vvv , i.e. the total number of object fragments generated. The size says nothing about the storage of a single fragment, but it is a good measure for comparing BSP trees of the same set of objects.
[The Definition of BSP Trees] When is the number of nodes of a BSP tree at most linear in its size?
When the BSP contains no useless splitting lines, i.e. lines that split off an empty subspace.
[The Definition of BSP Trees] What is the size of this BSP tree for the five objects o1,…,o5o_1, \dots, o_5o1,…,o5 ?
7. ℓ3\ell_3ℓ3 cuts o4o_4o4 in two, and ℓ2\ell_2ℓ2 cuts o1o_1o1 in two, so the leaves hold o4,o5,o4,o2,o1,o1,o3o_4, o_5, o_4, o_2, o_1, o_1, o_3o4,o5,o4,o2,o1,o1,o3 .
[The Definition of BSP Trees] Which convex region corresponds to a node vvv of a BSP tree T\mathcal{T}T ?
The intersection of the half-spaces hμ⋄h_\mu^\diamondhμ⋄ over all ancestors μ\muμ of vvv , with ⋄=−\diamond = -⋄=− if vvv is in the left subtree of μ\muμ and ⋄=+\diamond = +⋄=+ if in the right subtree. The root corresponds to the whole space; the leaves correspond to the faces of the subdivision the BSP induces. The grey node corresponds to the grey region ℓ1+∩ℓ2−∩ℓ3−\ell_1^+ \cap \ell_2^- \cap \ell_3^-ℓ1+∩ℓ2−∩ℓ3− .
[The Definition of BSP Trees] What is an auto-partition of a set of segments in the plane, and of a set of polygons in 3-space?
A BSP that only splits along extensions of the input objects: the lines containing input segments, or the planes containing input polygons. An auto-partition of a set of segments.
[The Definition of BSP Trees] Do auto-partitions always produce minimum-size BSP trees?
No, but they produce reasonably small ones.
[BSP Trees and the Painter's Algorithm] T\mathcal{T}T is a BSP tree on objects in 3-space, with root vvv and splitting plane hvh_vhv . The view point pviewp_{\text{view}}pview lies in hv+h_v^+hv+ . In which order must the painter's algorithm draw T−\mathcal{T}^-T− (the subtree for hv−h_v^-hv− ), S(v)S(v)S(v) and T+\mathcal{T}^+T+ ?
First T−\mathcal{T}^-T− , then S(v)S(v)S(v) , then T+\mathcal{T}^+T+ , each subtree in recursively computed order. Nothing on the far side of hvh_vhv can obscure anything on the near side.
[BSP Trees and the Painter's Algorithm] In the BSP-based painter's algorithm, the view point pviewp_{\text{view}}pview lies in hv−h_v^-hv− for the root vvv . What is the drawing order?
T+\mathcal{T}^+T+ , then S(v)S(v)S(v) , then T−\mathcal{T}^-T− . Always the subtree on the far side of hvh_vhv first. At a leaf, scan-convert the fragments in S(v)S(v)S(v) .
[BSP Trees and the Painter's Algorithm] In the BSP-based painter's algorithm, the view point pviewp_{\text{view}}pview lies on the splitting plane hvh_vhv . What is drawn, and why?
T+\mathcal{T}^+T+ , then T−\mathcal{T}^-T− ; S(v)S(v)S(v) is not drawn. The polygons of S(v)S(v)S(v) are flat, so they are invisible from points in their own plane.
[BSP Trees and the Painter's Algorithm] What does the running time of the BSP-based painter's algorithm (and of any algorithm using BSP trees) mainly depend on?
The size of the BSP tree, so splitting planes should be chosen to keep fragmentation of the objects low.
[BSP Trees and the Painter's Algorithm] For flight simulation, what objects does the chapter assume when constructing small BSP trees, and why?
Triangles in 3-space: a polyhedral model with triangulated facets. Speed is the main concern, so no curved surfaces.
[Constructing a BSP Tree] S={s1,…,sn}S = \{s_1, \dots, s_n\}S={s1,…,sn} is a set of non-intersecting segments in the plane, and ℓ(s)\ell(s)ℓ(s) is the line containing sss . How does the recursive algorithm 2DBSP build an auto-partition for SSS ?
If card⁡(S)≤1\operatorname{card}(S) \le 1card(S)≤1 , return a leaf storing SSS ; otherwise split with ℓ(s1)\ell(s_1)ℓ(s1) and recurse on S+S^+S+ and S−S^-S− . S±={s∩ℓ(s1)±:s∈S}S^\pm = \{s \cap \ell(s_1)^\pm : s \in S\}S±={s∩ℓ(s1)±:s∈S} . The root stores S(v)={s∈S:s⊂ℓ(s1)}S(v) = \{s \in S : s \subset \ell(s_1)\}S(v)={s∈S:s⊂ℓ(s1)} , with left subtree for S−S^-S− and right subtree for S+S^+S+ .
[Constructing a BSP Tree] When building an auto-partition of segments, why not always split with the segment whose line cuts the fewest other segments?
Too greedy: some configurations give bad BSPs this way, and finding that segment is time consuming.
[Constructing a BSP Tree] What does algorithm 2DRandomBSP do?
Put the segments in a random order, then run 2DBSP (always split with the first segment in the order).
[Constructing a BSP Tree] During the construction of a BSP for segments in the plane, what is a free split?
Splitting a face fff with a segment that crosses fff completely. No other segment inside fff gets cut, and the crossing segment needs no further consideration.
[Constructing a BSP Tree] How can 2DRandomBSP recognise that a segment gives a free split?
Keep two booleans per segment, telling whether its left and right endpoints lie on already added splitting lines; when both are true, it is a free split. The improved strategy makes free splits whenever possible and random splits otherwise. Asymptotically, free splits make no difference.
[Constructing a BSP Tree] Three segments s1,s2,s3s_1, s_2, s_3s1,s2,s3 are split in the order of their indices, in two different labellings (a) and (b). How many fragments does each BSP have?
(a) 5 fragments, (b) 3 fragments. In (b), ℓ(s1)\ell(s_1)ℓ(s1) is used first and shields s3s_3s3 from ℓ(s2)\ell(s_2)ℓ(s2) . The size of a BSP depends heavily on the order, hence the analysis of the expected size over all n!n!n! orders.
[Constructing a BSP Tree] Lemma 12.1 The expected number of fragments generated by 2DRandomBSP on nnn disjoint segments is … ?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) More precisely at most n+2nln⁡nn + 2n \ln nn+2nlnn .
[Constructing a BSP Tree] For segments si,sjs_i, s_jsi,sj of a set SSS of disjoint segments, what is dist⁡si(sj)\operatorname{dist}_{s_i}(s_j)distsi(sj) ?
If ℓ(si)\ell(s_i)ℓ(si) intersects sjs_jsj : the number of segments intersecting ℓ(si)\ell(s_i)ℓ(si) between sis_isi and sjs_jsj ; otherwise +∞+\infty+∞ . ℓ(si)\ell(s_i)ℓ(si) is the line containing sis_isi . For each finite distance there are at most two segments, one on either side of sis_isi .
[Constructing a BSP Tree] 2DRandomBSP processes segments in random order, and dist⁡si(sj)\operatorname{dist}_{s_i}(s_j)distsi(sj) counts the segments crossing the line ℓ(si)\ell(s_i)ℓ(si) between sis_isi and sjs_jsj . Why is Pr⁡[ℓ(si) cuts sj]≤1dist⁡si(sj)+2\Pr[\ell(s_i) \text{ cuts } s_j] \le \dfrac{1}{\operatorname{dist}_{s_i}(s_j) + 2}Pr[ℓ(si) cuts sj]≤distsi(sj)+21 ?
sis_isi must come first in the random order among sis_isi , sjs_jsj and the dist⁡si(sj)\operatorname{dist}_{s_i}(s_j)distsi(sj) segments in between, since any in-between segment that comes earlier shields sjs_jsj from sis_isi .
[Constructing a BSP Tree] 2DRandomBSP processes segments in random order. ℓ(si)\ell(s_i)ℓ(si) cuts sjs_jsj only if sis_isi comes before sjs_jsj and before the dist⁡si(sj)\operatorname{dist}_{s_i}(s_j)distsi(sj) segments crossing ℓ(si)\ell(s_i)ℓ(si) between them.Why is Pr⁡[ℓ(si) cuts sj]≤1dist⁡si(sj)+2\Pr[\ell(s_i) \text{ cuts } s_j] \le \frac{1}{\operatorname{dist}_{s_i}(s_j) + 2}Pr[ℓ(si) cuts sj]≤distsi(sj)+21 an inequality rather than an equality?
A segment not cut by ℓ(si)\ell(s_i)ℓ(si) can still shield sjs_jsj with its extension.
[Constructing a BSP Tree] For 2DRandomBSP on nnn disjoint segments: Pr⁡[ℓ(si) cuts sj]≤1dist⁡si(sj)+2\Pr[\ell(s_i) \text{ cuts } s_j] \le \frac{1}{\operatorname{dist}_{s_i}(s_j) + 2}Pr[ℓ(si) cuts sj]≤distsi(sj)+21 , and at most two segments have each finite distance from sis_isi .What bound on the expected number of cuts generated by sis_isi follows, and how?
2ln⁡n\boldsymbol{2 \ln n}2lnn ∑j≠i1dist⁡si(sj)+2≤2∑k=0n−21k+2≤2ln⁡n\displaystyle \sum_{j \ne i} \frac{1}{\operatorname{dist}_{s_i}(s_j) + 2} \le 2 \sum_{k=0}^{n-2} \frac{1}{k+2} \le 2 \ln nj=i∑distsi(sj)+21≤2k=0∑n−2k+21≤2lnn . By linearity of expectation, all segments together give at most 2nln⁡n2n \ln n2nlnn cuts, so at most n+2nln⁡nn + 2n \ln nn+2nlnn fragments.
[Constructing a BSP Tree] 2DRandomBSP on nnn disjoint segments produces at most n+2nln⁡nn + 2n \ln nn+2nlnn fragments in expectation.How can you get a BSP that is guaranteed to have size at most n+4nln⁡nn + 4n \ln nn+4nlnn ?
Run 2DRandomBSP, and restart with a fresh random permutation if the size exceeds n+4nln⁡nn + 4n \ln nn+4nlnn . At least half of all permutations give a BSP of that size, so the expected number of trials is two. Also, a BSP of size n+2nln⁡nn + 2n \ln nn+2nlnn exists for every set of nnn segments.
[Constructing a BSP Tree] Theorem 12.2. For nnn disjoint segments in the plane, 2DRandomBSP computes a BSP of size O(nlog⁡n)O(n \log n)O(nlogn) in expected time … ?
O(n2log⁡n)\boldsymbol{O(n^2 \log n)}O(n2logn) Apart from the recursive calls, each call takes time linear in its number of fragments, which is at most nnn ; the number of calls is at most the number of fragments, O(nlog⁡n)O(n \log n)O(nlogn) .
[Constructing a BSP Tree] Why is the O(n2log⁡n)O(n^2 \log n)O(n2logn) construction time of 2DRandomBSP usually not a problem in practice?
The construction is done off-line, and it is only quadratic when the BSP is very unbalanced, which is unlikely in practice.
[Constructing a BSP Tree] Can a BSP of size O(nlog⁡n)O(n \log n)O(nlogn) for nnn disjoint segments be built faster than 2DRandomBSP's expected O(n2log⁡n)O(n^2 \log n)O(n2logn) ?
Yes, in O(nlog⁡n)O(n \log n)O(nlogn) time with a deterministic algorithm based on segment trees. That BSP is not an auto-partition, and in practice slightly larger.
[Constructing a BSP Tree] Does every set of nnn disjoint segments in the plane have a BSP of size O(n)O(n)O(n) ?
No: some sets need size Ω(nlog⁡n/log⁡log⁡n)\Omega(n \log n / \log \log n)Ω(nlogn/loglogn) for every BSP. The best known upper bound is O(nlog⁡n)O(n \log n)O(nlogn) , so there is a small gap.
[Constructing a BSP Tree] S={t1,…,tn}S = \{t_1, \dots, t_n\}S={t1,…,tn} is a set of non-intersecting triangles in R3\mathbb{R}^3R3 , and h(t)h(t)h(t) is the plane containing triangle ttt . How does algorithm 3DBSP work?
Like 2DBSP: if card⁡(S)≤1\operatorname{card}(S) \le 1card(S)≤1 return a leaf; otherwise split with h(t1)h(t_1)h(t1) , store {t∈S:t⊂h(t1)}\{t \in S : t \subset h(t_1)\}{t∈S:t⊂h(t1)} at the root, and recurse on S−S^-S− (left) and S+S^+S+ (right). S±={t∩h(t1)±:t∈S}S^\pm = \{t \cap h(t_1)^\pm : t \in S\}S±={t∩h(t1)±:t∈S} . This is an auto-partition.
[Constructing a BSP Tree] Is 3DBSP with the triangles in random order a good algorithm, and what is known about its expected size?
Good in practice, but nobody knows how to analyse its expected size. So a variant (3DRandomBSP2) is analysed instead, although the simple algorithm is probably better in practice.
[The Size of BSP Trees in 3-Space] In 3-space, when is splitting a cell with a triangle of SSS a free split?
When the triangle splits the cell into two disconnected subcells.
[The Size of BSP Trees in 3-Space] How does algorithm 3DRandomBSP2 for nnn disjoint triangles in R3\mathbb{R}^3R3 differ from the recursive 3DBSP with a random order?
A plane h(ti)h(t_i)h(ti) splits every cell it intersects where the split is useful, not only the cells intersected by tit_iti ; and all possible free splits are made. A split of a cell is useless (and skipped) if all triangles in that cell lie on one side. With this rule, a simple recursive implementation is no longer possible. (a) recursive algorithm, (b) modified algorithm, order s1,s2,s3s_1, s_2, s_3s1,s2,s3 : ℓ(s2)\ell(s_2)ℓ(s2) also splits the subspace below ℓ(s1)\ell(s_1)ℓ(s1) ; ℓ(…
[The Size of BSP Trees in 3-Space] Lemma 12.3 The expected number of object fragments generated by 3DRandomBSP2 on nnn disjoint triangles in R3\mathbb{R}^3R3 , over all n!n!n! permutations, is … ?
O(n2)\boldsymbol{O(n^2)}O(n2) So every set of nnn disjoint triangles in R3\mathbb{R}^3R3 has a BSP tree of quadratic size.
[The Size of BSP Trees in 3-Space] Proof that 3DRandomBSP2 on triangles t1,…,tnt_1, \dots, t_nt1,…,tn (random order) gives O(n2)O(n^2)O(n2) fragments: fix a triangle tkt_ktk .Which arrangement on the plane h(tk)h(t_k)h(tk) does the proof study?
The arrangement of the at most k−1k-1k−1 lines ℓi=h(ti)∩h(tk)\ell_i = h(t_i) \cap h(t_k)ℓi=h(ti)∩h(tk) , i<ki < ki<k , and on tkt_ktk the segments si=ℓi∩tks_i = \ell_i \cap t_ksi=ℓi∩tk of the lines that intersect tkt_ktk .
[The Size of BSP Trees in 3-Space] 3DRandomBSP2 treats triangles in random order t1,…,tnt_1, \dots, t_nt1,…,tn ; on the plane of tkt_ktk , the earlier planes give segments si=h(ti)∩tks_i = h(t_i) \cap t_ksi=h(ti)∩tk , i<ki < ki<k .Why does h(tk−1)h(t_{k-1})h(tk−1) cut tkt_ktk only in exterior faces of the arrangement of s1,…,sk−2s_1, \dots, s_{k-2}s1,…,sk−2 on tkt_ktk (faces incident to an edge of tkt_ktk )?
An interior face is already bounded by splits all around, so a free split has been made through it. So the number of new fragments of tkt_ktk caused by h(tk−1)h(t_{k-1})h(tk−1) equals the number of edges sk−1s_{k-1}sk−1 contributes to exterior faces. sk−1s_{k-1}sk−1 only cuts the exterior faces it passes through; the grey interior face is not cut.
[The Size of BSP Trees in 3-Space] In the analysis of 3DRandomBSP2, why does the proof need the modified algorithm (each plane splits all cells it meets) rather than the recursive 3DBSP?
The collection of exterior faces on a triangle tkt_ktk must not depend on the order in which t1,…,tk−1t_1, \dots, t_{k-1}t1,…,tk−1 were treated, which holds only for the modified algorithm.
[The Size of BSP Trees in 3-Space] On triangle tkt_ktk lies the arrangement of the lines ℓi=h(ti)∩h(tk)\ell_i = h(t_i) \cap h(t_k)ℓi=h(ti)∩h(tk) , i<ki < ki<k . Exterior faces are those incident to an edge of tkt_ktk .Why do the exterior faces have O(k)O(k)O(k) edges in total?
These edges lie in the zones of the three lines through the edges of tkt_ktk , and a zone in an arrangement of mmm lines has complexity O(m)O(m)O(m) (zone theorem).
[The Size of BSP Trees in 3-Space] In 3DRandomBSP2, the exterior faces on tkt_ktk have O(k)O(k)O(k) edges in total, lying on the segments s1,…,sk−1s_1, \dots, s_{k-1}s1,…,sk−1 , and t1,…,tnt_1, \dots, t_nt1,…,tn is a random order.How does the proof conclude that tkt_ktk is cut into O(k)O(k)O(k) fragments in expectation?
A random segment sis_isi carries O(1)O(1)O(1) exterior-face edges on average, so each of the planes h(t1),…,h(tk−1)h(t_1), \dots, h(t_{k-1})h(t1),…,h(tk−1) adds O(1)O(1)O(1) expected fragments. Summing over all triangles: O(∑k=1nk)=O(n2)O(\sum_{k=1}^n k) = O(n^2)O(∑k=1nk)=O(n2) .
[The Size of BSP Trees in 3-Space] Lemma 12.4. What lower bound holds for auto-partitions of nnn non-intersecting triangles in 3-space?
Some sets need size Ω(n2)\Omega(n^2)Ω(n2) for any auto-partition.
[The Size of BSP Trees in 3-Space] Which configuration forces every auto-partition in 3-space to have size Ω(n2)\Omega(n^2)Ω(n2) ?
A set R1R_1R1 of rectangles parallel to the xyxyxy -plane stacked below a set R2R_2R2 of rectangles parallel to the yzyzyz -plane. The minimum auto-partition size is G(n1,n2)=(n1+1)(n2+1)−1G(n_1, n_2) = (n_1 + 1)(n_2 + 1) - 1G(n1,n2)=(n1+1)(n2+1)−1 for n1=card⁡(R1)n_1 = \operatorname{card}(R_1)n1=card(R1) , n2=card⁡(R2)n_2 = \operatorname{card}(R_2)n2=card(R2) . Triangles work as well.
[The Size of BSP Trees in 3-Space] R1R_1R1 : n1n_1n1 rectangles parallel to the xyxyxy -plane; R2R_2R2 : n2n_2n2 rectangles parallel to the yzyzyz -plane above them. G(n1,n2)G(n_1, n_2)G(n1,n2) is the minimum auto-partition size; claim G(n1,n2)=(n1+1)(n2+1)−1G(n_1, n_2) = (n_1 + 1)(n_2 + 1) - 1G(n1,n2)=(n1+1)(n2+1)−1 .What is the induction step when the auto-partition first splits with a rectangle r∈R1r \in R_1r∈R1 that has mmm rectangles of R1R_1R1 above it?
The plane of rrr cuts all of R2R_2R2 , and both sides have the same form: G(n1,n2)=1+G(m,n2)+G(n1−m−1,n2)G(n_1, n_2) = 1 + G(m, n_2) + G(n_1 - m - 1, n_2)G(n1,n2)=1+G(m,n2)+G(n1−m−1,n2) . =1+((m+1)(n2+1)−1)+((n1−m)(n2+1)−1)=(n1+1)(n2+1)−1= 1 + ((m+1)(n_2+1) - 1) + ((n_1 - m)(n_2+1) - 1) = (n_1+1)(n_2+1) - 1=1+((m+1)(n2+1)−1)+((n1−m)(n2+1)−1)=(n1+1)(n2+1)−1 . Base cases G(1,0)=G(0,1)=1G(1,0) = G(0,1) = 1G(1,0)=G(0,1)=1 ; starting with R2R_2R2 is symmetric.
[The Size of BSP Trees in 3-Space] Rectangles parallel to the xyxyxy -plane lie below rectangles parallel to the yzyzyz -plane, so every auto-partition has quadratic size. How does an unrestricted BSP do better?
First separate the two groups with a plane parallel to the xzxzxz -plane; then the BSP has linear size.
[The Size of BSP Trees in 3-Space] Which configuration of nnn lines (or long skinny triangles) in 3-space forces every BSP to have size Ω(n2)\Omega(n^2)Ω(n2) ?
A skewed grid on a hyperbolic paraboloid: {y=i,z=ix}∪{x=i,z=iy+ε}\{y = i, z = ix\} \cup \{x = i, z = iy + \varepsilon\}{y=i,z=ix}∪{x=i,z=iy+ε} , 1≤i≤n/21 \le i \le n/21≤i≤n/2 , with small ε>0\varepsilon > 0ε>0 . The lines are skewed so that no plane fits through the four openings at the corners of a grid cell, so any BSP cuts one of the four lines around each of the Θ(n2)\Theta(n^2)Θ(n2) cells.
[The Size of BSP Trees in 3-Space] Theorem 12.5. What is the worst-case size of BSP trees for nnn non-intersecting triangles in R3\mathbb{R}^3R3 ?
Θ(n2)\boldsymbol{\Theta(n^2)}Θ(n2) : a BSP of size O(n2)O(n^2)O(n2) always exists, and some configurations need Ω(n2)\Omega(n^2)Ω(n2) for any BSP.
[BSP Trees for Low-Density Scenes] BSP trees for triangles in 3-space have worst-case size Θ(n2)\Theta(n^2)Θ(n2) . Why is that not the end of the story?
In practice BSP trees perform fine: realistic inputs have well-separated objects, unlike the grid lower bound. So the analysis needs a parameter besides nnn that tells easy inputs from difficult ones. The parameter must measure distance relative to object size, since scaling the scene should not change the result.
[BSP Trees for Low-Density Scenes] What is the density of a set SSS of objects in Rd\mathbb{R}^dRd ?
The smallest λ\lambdaλ such that any ball BBB intersects at most λ\lambdaλ objects o∈So \in So∈S with diam⁡(o)≥diam⁡(B)\operatorname{diam}(o) \ge \operatorname{diam}(B)diam(o)≥diam(B) . BBB is any ball (any radius, any center), not an object of SSS . Eight segments with density 3: BBB intersects five segments, but two are smaller than BBB and do not count.
[BSP Trees for Low-Density Scenes] What is the density of: (a) a set of nnn lines, (b) nnn unit balls with pairwise distance more than 1, (c) nnn disjoint balls of arbitrary sizes?
(a) nnn , (b) 1, (c) Θ(1)\Theta(1)Θ(1) . The grid lower-bound construction for BSPs has density Θ(n)\Theta(n)Θ(n) , even with segments instead of full lines.
[BSP Trees for Low-Density Scenes] Does the randomized algorithm 3DRandomBSP2 produce small BSPs for scenes of low density?
No: even for constant density, its expected size can be quadratic. So low-density scenes need a new algorithm.
[BSP Trees for Low-Density Scenes] In the low-density BSP algorithm in the plane, what are the guards of an object ooo , and what is G(S)G(S)G(S) ?
The four vertices of the bounding box bb⁡(o)\operatorname{bb}(o)bb(o) (the smallest axis-parallel rectangle containing ooo ). G(S)G(S)G(S) is the multiset of the 4n4n4n guards of all nnn objects. A multiset: coinciding bounding-box vertices are put in once per object.
[BSP Trees for Low-Density Scenes] Lemma 12.6. SSS is a set of objects in the plane with density λ\lambdaλ and guards G(S)G(S)G(S) (bounding-box vertices). An axis-parallel square contains kkk guards in its interior. At most how many objects of SSS does it intersect?
k+4λ\boldsymbol{k + 4\lambda}k+4λ Only an upper bound: a square can contain many guards without intersecting any object.
[BSP Trees for Low-Density Scenes] Proof that an axis-parallel square σ\sigmaσ with kkk guards (bounding-box vertices) in its interior intersects at most k+4λk + 4\lambdak+4λ objects of a set with density λ\lambdaλ .An object ooo intersects σ\sigmaσ but has no guard inside σ\sigmaσ . Why is diam⁡(o)≥diam⁡(σ)/2\operatorname{diam}(o) \ge \operatorname{diam}(\sigma)/\sqrt{2}diam(o)≥diam(σ)/2 ?
bb⁡(o)\operatorname{bb}(o)bb(o) meets σ\sigmaσ without a vertex inside, so its projection on the xxx -axis or the yyy -axis contains that of σ\sigmaσ : ooo is at least as wide (or tall) as the side of σ\sigmaσ .
[BSP Trees for Low-Density Scenes] Proof that an axis-parallel square σ\sigmaσ with kkk guards in its interior intersects at most k+4λk + 4\lambdak+4λ objects of a set with density λ\lambdaλ . The objects without a guard in σ\sigmaσ have diameter ≥diam⁡(σ)/2\ge \operatorname{diam}(\sigma)/\sqrt{2}≥diam(σ)/2 .How does the proof bound those objects by 4λ4\lambda4λ ?
Cover σ\sigmaσ with four discs D1,…,D4D_1, \dots, D_4D1,…,D4 of diameter diam⁡(σ)/2\operatorname{diam}(\sigma)/2diam(σ)/2 ; each object is larger than each disc, so by density each disc is charged by at most λ\lambdaλ of them. diam⁡(o)≥diam⁡(σ)/2>diam⁡(σ)/2\operatorname{diam}(o) \ge \operatorname{diam}(\sigma)/\sqrt{2} > \operatorname{diam}(\sigma)/2diam(o)≥diam(σ)/2>diam(σ)/2 . Plus at most kkk objects with a guard in σ\sigmaσ .
[BSP Trees for Low-Density Scenes] What are the two phases of the BSP algorithm for low-density scenes in the plane?
Phase 1: a quadtree-like subdivision on the guards G(S)G(S)G(S) , whose leaf regions each meet few objects. Phase 2: separate the objects inside each leaf region (for segments, with 2DRandomBSP). A quadtree split is a vertical line followed by a horizontal line on each side, so the subdivision is a BSP tree.
[BSP Trees for Low-Density Scenes] Why can't phase 1 of the low-density BSP algorithm be a plain quadtree on the guards (subdividing until each square has at most one guard)?
The number of leaf regions can be very large, e.g. when two guards lie very close together near a corner.
[BSP Trees for Low-Density Scenes] In PHASE1 (σ,G,k)(\sigma, G, k)(σ,G,k) of the low-density BSP algorithm, when does the recursion stop, and when does it do a quadtree split?
Stop when σ\sigmaσ has at most kkk guards. Quadtree split when at least two quadrants, or none, have more than kkk guards in their interior. If no quadrant has more than kkk guards, all four quadrants become leaves. If exactly one does, a shrinking step is done instead.
[BSP Trees for Low-Density Scenes] In PHASE1 of the low-density BSP algorithm, exactly one quadrant σ′\sigma'σ′ (say north-west) of σ\sigmaσ has more than kkk guards. What is the shrinking step?
Shrink σ′\sigma'σ′ by moving its bottom-right corner diagonally to the north-west until at least kkk guards are outside its interior; split σ\sigmaσ with a vertical line ℓv(σ)\ell_v(\sigma)ℓv(σ) through the right edge and a horizontal line ℓh(σ)\ell_h(\sigma)ℓh(σ) through the bottom edge of the shrunk σ′\sigma'σ′ . The shrunk σ′\sigma'σ′ stays a square, is the only region that may need further splitting, and has at least one guard on its boundary. k=4k = 4k=4 .
[BSP Trees for Low-Density Scenes] In PHASE1 of the low-density BSP algorithm, what does one quadtree split or shrinking step add to the BSP tree?
Three internal nodes: the root stores ℓv(σ)\ell_v(\sigma)ℓv(σ) , both children store ℓh(σ)\ell_h(\sigma)ℓh(σ) . Then each of the four leaves is replaced by a recursively computed tree on its region and the guards inside.
[BSP Trees for Low-Density Scenes] Lemma 12.7. SSS has nnn objects in the plane, density λ\lambdaλ , guards G(S)G(S)G(S) , bounding square UUU . What does PHASE1 (U,G(S),k)(U, G(S), k)(U,G(S),k) produce?
A BSP tree with O(n/k)O(n/k)O(n/k) leaves, each leaf region intersecting at most k+4λk + 4\lambdak+4λ objects.
[BSP Trees for Low-Density Scenes] N(m)N(m)N(m) is the maximum number of internal nodes PHASE1 (σ,G,k)(\sigma, G, k)(σ,G,k) creates for mmm guards. Each quadtree split or shrinking step creates 3 internal nodes.What bound on N(m)N(m)N(m) does the proof of Lemma 12.7 prove by induction?
N(m)≤max⁡(0,6m/k−3)\boldsymbol{N(m) \le \max(0, 6m/k - 3)}N(m)≤max(0,6m/k−3) So O(m/k)=O(n/k)O(m/k) = O(n/k)O(m/k)=O(n/k) leaves, since m=4nm = 4nm=4n and the leaves are one more than the internal nodes.
[BSP Trees for Low-Density Scenes] Induction for PHASE1: N(m)≤max⁡(0,6m/k−3)N(m) \le \max(0, 6m/k - 3)N(m)≤max(0,6m/k−3) , where N(m)N(m)N(m) is the maximum number of internal nodes for mmm guards and a step creates 3 nodes.Why does the bound hold when at least two quadrants have more than kkk guards (the set III of such quadrants, with mim_imi guards each)?
N(m)≤3+∑i∈IN(mi)≤3+∑i∈I6mi/k−3card⁡(I)≤6m/k−3N(m) \le 3 + \sum_{i \in I} N(m_i) \le 3 + \sum_{i \in I} 6m_i/k - 3\operatorname{card}(I) \le 6m/k - 3N(m)≤3+∑i∈IN(mi)≤3+∑i∈I6mi/k−3card(I)≤6m/k−3 Using ∑mi≤m\sum m_i \le m∑mi≤m and card⁡(I)≥2\operatorname{card}(I) \ge 2card(I)≥2 . If no quadrant has more than kkk guards, N(m)=3≤6m/k−3N(m) = 3 \le 6m/k - 3N(m)=3≤6m/k−3 since m>km > km>k .
[BSP Trees for Low-Density Scenes] Induction for PHASE1: N(m)≤max⁡(0,6m/k−3)N(m) \le \max(0, 6m/k - 3)N(m)≤max(0,6m/k−3) , where N(m)N(m)N(m) is the maximum number of internal nodes for mmm guards and a step creates 3 nodes.Why does the bound hold after a shrinking step?
The shrunk quadrant has fewer than m−km - km−k guards and the other regions are leaves, so N(m)≤3+N(m−k)≤3+6(m−k)/k−3≤6m/k−3N(m) \le 3 + N(m - k) \le 3 + 6(m-k)/k - 3 \le 6m/k - 3N(m)≤3+N(m−k)≤3+6(m−k)/k−3≤6m/k−3 .
[BSP Trees for Low-Density Scenes] PHASE1 leaves contain at most kkk guards; square leaves meet at most k+4λk + 4\lambdak+4λ objects, because a square with kkk guards inside meets at most k+4λk + 4\lambdak+4λ objects.Why does a non-square leaf region σ′′\sigma''σ′′ (made by a shrinking step) also meet at most k+4λk + 4\lambdak+4λ objects?
Fewer than kkk guards lie outside the shrunk square σ′\sigma'σ′ (not on its boundary), so σ′′\sigma''σ′′ is covered by a square with at most kkk guards in its interior. The grey square covers σ′′\sigma''σ′′ .
[BSP Trees for Low-Density Scenes] PHASE1 with parameter kkk gives O(n/k)O(n/k)O(n/k) leaf regions, each meeting at most k+4λk + 4\lambdak+4λ objects ( λ\lambdaλ = density). Why is k=λk = \lambdak=λ a good choice?
It cuts the number of leaf regions by a factor λ\lambdaλ (compared with k=1k = 1k=1 ), while the objects per leaf only go from 1+4λ1 + 4\lambda1+4λ to 5λ5\lambda5λ .
[BSP Trees for Low-Density Scenes] The low-density BSP algorithm wants to run PHASE1 with k=λk = \lambdak=λ , but the density λ\lambdaλ is unknown. What does it do?
Guess k=2k = 2k=2 ; run PHASE1 and check that every leaf region meets at most 5k5k5k objects; if not, double kkk and repeat. Then phase 2 computes a BSP tree for the fragments S(μ)S(\mu)S(μ) of each leaf μ\muμ and replaces μ\muμ by that tree (algorithm LowDensityBSP2D).
[BSP Trees for Low-Density Scenes] LowDensityBSP2D doubles kkk (starting at 2) until every leaf region of PHASE1 (U,G(S),k)(U, G(S), k)(U,G(S),k) meets at most 5k5k5k objects. Each leaf region meets at most k+4λk + 4\lambdak+4λ objects.Why is the final value k∗k^*k∗ at most 2λ2\lambda2λ ?
Once k≥λk \ge \lambdak≥λ , k+4λ≤5kk + 4\lambda \le 5kk+4λ≤5k , so the test is sure to pass; since kkk doubles, it stops by k≤2λk \le 2\lambdak≤2λ .
[BSP Trees for Low-Density Scenes] Theorem 12.8. Every set SSS of nnn disjoint segments in the plane with density λ\lambdaλ has a BSP of size … ?
O(nlog⁡λ)\boldsymbol{O(n \log \lambda)}O(nlogλ) LowDensityBSP2D with 2DRandomBSP in phase 2: O(n/k∗)O(n/k^*)O(n/k∗) leaf regions with at most 5k∗5k^*5k∗ segments each, so expected size O(k∗log⁡k∗)O(k^* \log k^*)O(k∗logk∗) per leaf, total O(nlog⁡k∗)O(n \log k^*)O(nlogk∗) with k∗≤2λk^* \le 2\lambdak∗≤2λ .
[BSP Trees for Low-Density Scenes] How does the O(nlog⁡λ)O(n \log \lambda)O(nlogλ) BSP for nnn disjoint segments of density λ\lambdaλ compare with 2DRandomBSP?
Never worse: O(nlog⁡n)O(n \log n)O(nlogn) in the worst case, and O(n)O(n)O(n) when the density is constant.
[BSP Trees for Low-Density Scenes] Theorem 12.9. Every set of nnn disjoint triangles in R3\mathbb{R}^3R3 with density λ\lambdaλ has a BSP of size … ?
O(nλ)\boldsymbol{O(n\lambda)}O(nλ) This interpolates between O(n)O(n)O(n) and O(n2)O(n^2)O(n2) as λ\lambdaλ goes from 1 to nnn , and is optimal for every λ\lambdaλ : for any nnn and 1≤λ≤n1 \le \lambda \le n1≤λ≤n some set of nnn triangles with density λ\lambdaλ needs size Ω(nλ)\Omega(n\lambda)Ω(nλ) .
[Notes and Comments] Which two well-known data structures are special cases of BSP trees?
Kd-trees and quadtrees: BSP trees with only orthogonal splitting planes.
[Notes and Comments] What BSP sizes did Paterson and Yao prove for (d−1)(d-1)(d−1) -simplices in Rd\mathbb{R}^dRd ( d≥3d \ge 3d≥3 ) and for orthogonal rectangles in R3\mathbb{R}^3R3 ?
O(nd−1)O(n^{d-1})O(nd−1) for simplices; O(nn)O(n\sqrt{n})O(nn) for orthogonal rectangles, tight in the worst case. Paterson and Yao started the theoretical study of BSP trees; the randomized bounds for segments and triangles come from their paper.
[Notes and Comments] Which sets of nnn disjoint segments in the plane are known to admit a BSP of size O(n)O(n)O(n) ?
Segments that are all horizontal or vertical (Paterson and Yao), also segments with a limited number of orientations, segments of roughly the same length, and sets of constant density. For general segments, Tóth showed a lower bound of Ω(nlog⁡n/log⁡log⁡n)\Omega(n \log n / \log \log n)Ω(nlogn/loglogn) .
[Notes and Comments] When is a triangle β\betaβ -fat, and how does fatness relate to density?
All its angles are at least β\betaβ . Any set of disjoint β\betaβ -fat objects has density O(1/β)O(1/\beta)O(1/β) , so low-density results apply to them. Fatness has been generalized from triangles to arbitrary convex and even non-convex objects.