Langetepe E., Zachmann G. Geometric Data Structures for Computer Graphics

Подождите немного. Документ загружается.

We repeat the process recursively with the constructed subsets. For every split operation, we have to

determine the split axis and the split value. The simplest strategy is to choose the axes in a cyclic manner

(i.e., x-, y-, z-axis, etc.)—this is called a cyclic kd-tree. More precisely, a kd-tree for dimension d is

constructed as follows.

The following is the inductive construction of a kd-tree sketch:

 Input: given a set of points D in dimension d and the split coordinate x

;

 If D is empty, then return an empty node v;

 Otherwise, allocate a node v for the root of the kd-tree with two children v. LeftChild and v.

RightChild. Choose a split value s

with respect to the chosen coordinate x

. Split the set D into

subsets

Algorithm 2.9: Recursive construction of a kd-tree.

KdTreeConstr(D, i) (D is a set of points in , i ∈ {1,

…

, d})

if D = then

v := Nil

else

v := new node

if |D| = 1 then

v.Element := D.Element

v. LeftChild := Nil v. RightChild := Nil

else

s := D. SplitValue(i)

v. Split := s v.Dim := i

:= D. Left(i, s)

:= D. Right(i, s)

j := (i mod d) + 1

v. LeftChild := KdTreeConstr(D

, j)

v. RightChild := KdTreeConstr(D

, j)

end if

return v

 Recursively, build the kd-trees v. LeftChild and v. RightChild for the set D

and D

with respect to

the next coordinate x

, j = (i mod d) + 1, respectively. Finally, return the node v.

The tree will be built up by KdTreeConstr(D, 1). Thus, we simply obtain a binary tree. The balance of the

tree depends on the choice of the split value in procedure SplitValue. In case of d = 2, we obtain a 2D kd-

tree

[2]

of the point set D; see Figure 2.6. Each internal node of the tree corresponds to a split line. For

every node v of the kd-tree, we define the rectangle R(v), the region of v, which is the intersection of half-

planes corresponding to the path from the root to v. For the root r, R(r) is the plane itself; the children of r,

say

and

, correspond to two half-planes R(

) and R(

), and so on. The set of rectangles {R(l)|l is a

leaf} gives a non-overlapping partition of the plane into rectangles. Every R(l) has exactly one point of D

inside. We do not have to store the rectangles explicitly; they are given by the path from the root to the

corresponding node; see Figure 2.6.

Figure 2.6: A 2D kd-tree and a rectangular range query. Each node corresponds to a split line.

Additionally, each node represents a unique rectangular range R(v) according to the path from the root to

the node.

For simplicity, we again consider the 2D case. The kd-tree in 2D efficiently supports range queries of

axis-parallel rectangles. If Q is an axis-parallel rectangle, the set of sites v ∈ D with v ∈ Q can be

computed as follows. We have to compute all nodes v with:

If the condition holds for node v, it will hold also for the predecessor u of v in the kd-tree since R(v) ⊂

R(u). Thus, we can start searching from the root to the leaves. Finally, if we reach a leaf of the tree with

the given property, we still have to check whether the data point of the leaf is inside Q.

For general dimension d, every node v implicitly represents an orthogonal box in dimension d.

Analogously, the box is given by the path from the root to v. For the query operation, we store the current

orthogonal box explicitly during the query process. We obtain the following query procedure.

The following is the d-dimensional axis-parallel query sketch:

 Input: the root r of a kd-tree in dimension d and a d-dimensional orthogonal range R. The d-

dimensional orthogonal box Q(v) defines the range associated with node v. In the beginning, Q(r)

represents the full d-dimensional space for the root r;

 Let v be the current node;

 If v is a leaf, then check whether the element v. Element stored in v lies in R, and if so, report the

element. Stop the procedure;

 Otherwise, the given Q(v) is split into the regions Q(v. LeftChild) and Q(v. RightChild) for the left and

the right child of v by using the split line v. Split;

 If Q(v. LeftChild) or Q(v. RightChild), respectively, is fully contained in R, then report all points in v.

LeftChild or v. RightChild, respectively;

Algorithm 2.10: The query procedure of the d-dimensional kd-tree.

KdTreeQuery(v, Q, R) (v is the node of a kd-tree, Q is its the associated d-dimensional range, and R

is a d-dimensional orthogonal query range)

if v is a leaf and v. Element ∈ R then

return v. Element

else

:= LeftChild(v) v

:= RightChild(v)

:= Q. LeftPart(v. Split)

:= Q. RightPart(v. Split)

if Q

⊂ R then

(v. LeftChild). Report

else if Q

∩ R ≠ then

KdTreeQuery(v. LeftChild,Q

,R)

end if

if Q

⊂ R then

(v. RightChild). Report

else if Q

∩ R = then

KdTreeQuery(v. RightChild, Q

, R)

end if

If Q(v. LeftChild) or Q(v. RightChild), respectively, intersect with R, then rerun the procedure with v.

LeftChild and Q(v. LeftChild) or v. RightChild and Q(v. RightChild), respectively.

For convenience, we discuss time and space complexity for the 2D case. It can be shown that in 2D, the

number of nodes that fulfill R(v) ∩ Q ≠ Ø is restricted to , where h denotes the depth of the

tree and k denotes the number of points in Q, i.e., the size of the answer; see [Klein 05] or [de Berg et al.

00]. Altogether, the efficiency of the kd-tree with respect to range queries depends on the depth of the

tree. A balanced kd-tree can be easily constructed. We sort the points with respect to the x- and y-

coordinates. With this order, we recursively split the set into subsets of equal size in time O(log n). The

construction runs in time O(n log n), and the tree has depth O(log n). Altogether, the following theorem

can be proven.

Theorem 2.9. A balanced kd-tree for n points in the plane can be constructed in O(n log n) and needs

O(n) space. A range query with an axis-parallel rectangle can be answered in time O( + a), where a

denotes the size of the answer.

As mentioned earlier, the 2D kd-tree can be easily generalized to arbitrary dimension d, splitting the

points successively with respect to the given axes in a balanced way. Fortunately, the depth of the

balanced tree still is bounded by O(log n), and the tree can be built up in time O(n log n) and space O(n)

for fixed dimension d. Therefore, the kd-tree is optimal in space. A rectangular range query can be

answered in time .

Theorem 2.10. A balanced d-dimensional kd-tree for n points in can be constructed in O(n log n) and

needs O(n) space. A range query with an axis-parallel box in can be answered in time

, where k denotes the size of the answer.

The main advantage of the d-dimensional kd-tree lies in its small size. In the following section, we will see

that rectangular range queries can be answered more efficiently with the help of range trees. A

WeakDelete operation in the kd-tree can be done in O(log n). We simply traverse the tree up to the

corresponding node and mark the node as deleted.

Lemma 2.11. A WeakDelete operation for a balanced d-dimensional kd-tree for n points in can be

performed in O(log n) time.

[2]

According to [de Berg et al. 00], the term k-d tree was meant as a template to be specialized like 2-d

tree, 3-d tree, etc. Today, it is customary to specialize it like 2D kd-tree, etc.

2.5. Range Trees

Range trees are defined for arbitrary dimension d and support exactly the same windowing query as the

kd-tree. A range tree can answer the corresponding query more efficiently. On the negative side, a range

tree requires more space than the kd-tree.

With the help of a d-dimensional range tree, one can efficiently answer (point/axis-parallel box) windowing

queries as follows:

 Input: a set of points S in ;

 Query: an axis-parallel d-dimensional box B;

 Output: all points p ∈ S with p ∈ B.

The range tree is defined similar to the multi-level segment tree (see Section 2.3). The main difference is

that we do not need to represent segments in the tree. Let us first consider a simple balanced one-

dimensional search tree for a set S of points on the x-axis. As mentioned earlier, each node v represents

a uniquely determined interval v.I of points in S. In turn, for a query interval I, the points of S inside I are

covered by a minimal set of intervals v.I; see Figure 2.7. The construction of the one-dimensional search

tree was already discussed in Section 2.2.

Figure 2.7: Every node v in the one-dimensional search tree represents a unique interval v.I. A query

interval I is uniquely covered by a minimal set of intervals v.I.

For the inductive construction of a d-dimensional range tree, let x

denote the ith coordinate. A point x

∈

S is given by ; see Figure 2.8 for a 2D example. A d-dimensional range tree with

respect to (X

, X

…

, X

) is inductively defined as follows.

Figure 2.8: Some parts of the 2D range tree of eight points in 2D. The range tree T

and the relevant

trees for the nodes u

, u

, and u

with , , and for the

query rectangle R = I

× I

with intervals I

⊂ X and I

⊂ Y.

Algorithm 2.11: The inductive construction algorithm of a d-dimensional range tree.

RangeTreeConstr(D, d) (S is a set of points in )

:= S. FirstCoordElements

. Sort

T := S

. SearchTree

T. Dim := d

if d > 1 then

N := T.GetAllNodes

while N ≠ do

u := N. First N. DeleteFirst

L := u.I

S := new list

while L ≠ do

x := L. First L. DeleteFirst

S := S. ListAdd(x. Point(d − 1))

end while

Pointer(u):= RangeTreeConstr(S, d − 1)

end while

end if

return T

The following is the d-dimensional range tree construction sketch:

 Build a one-dimensional balanced search tree T

for all points x

with respect to X

;

 For every node u of T

o Build a (d − 1)-dimensional range tree for the set of points

where u.I represents the interval at node u in T

;

o Associate a pointer in T

from u to .

The time and space complexity analysis for range a trees is very similar to the multi-level segment tree

analysis; see the proof of Theorem 2.7. Since we do not have to insert segments into the trees, we can

neglect a log factor.

The query operation for an axis-parallel query box q = I

× I

× ··· × I

⊂

and a d-dimensional range

tree T

of a set of points p

…

, p

is explained in the following sketch; see Figure 2.8 for an example.

The following is the range tree query sketch:

Algorithm 2.12: The inductive query operation for a d-dimensional range tree.

RangeTreeQuery(T, B, d) (T is the root of a d-dimensional range tree, B is a d-dimensional box)

if d = 1 then

L := SearchTreeQuery(T, B)

A := L. GetPoints

else

A := new list

L := MinimalCoveringIntervals(T, B. First)

while L ≠ do

t := (L. First). Pointer

D := RangeTreeQuery(t, B. Rest, d − 1)

A. ListAdd(D)

L. DeleteFirst

end while

return A

end if

 If d = 1, answer the question with the corresponding one-dimensional search tree T

;

 Otherwise, traverse T

and find the nodes u

…

, u

so that the intervals of the nodes (u

).I minimally

cover I

;

 For 1 ≤ i ≤ l, answer the query I

× ··· × I

⊂

(d−1)

recursively with the trees of the data point

sets of (u

).I.

Theorem 2.12. A d-dimensional range tree for a set of n points in dimension d can be built up in O(n

log

(d−1)

n) time and needs O(n log

(d−1)

n) space. An axis-parallel box windowing query can be answered in

O(k + log

n) time.

Proof: First, we sort the segments endpoints with respect to every dimension. The first range tree T

built up in O(n), has space O(n log n), and has O(n) nodes. Next, we construct (d − 1)-dimensional

segment trees for the set of points in the interval v.I of every node v in T

. Let |v.I| denote the number of

data points in v.I. By induction, we can assume that the (d − 1)-dimensional segment tree for node v ∈ T

with all points in v.I is computed in O(|v.I| log

(d−2)

|v.I|). Additionally, every data point p occurs in O(log n)

intervals v.I; i.e., in only O(log n) (d − 1)-dimensional segment trees. Therefore, the overall running time

is given by

The required space is measured as follows. The structure T

consists only of one-dimensional range trees

. In how many trees will a data point p

appear? Since p lies inside O(log n) intervals of T

, the point p

appears in O(log n) trees . In each of these trees, the data point p again lies inside O(log n)

intervals and will be a data point in the corresponding trees. Altogether, a data point p appears in

nodes. Summing up over all n data points gives O(n log

(d−1)

n) entries. By the same argument, the

number of trees is also in O(log

(d−1)

n), so that the number of empty nodes is bounded by O(n log

(d−1)

n).

On the other hand, a query traverses along O(log

n) nodes. For the first tree T

, the query traverses

O(log n) nodes and O(log n) new queries must be considered. Recursively, O(log n) nodes of O(log n)

new trees may be traversed. In the final range trees, k boxes may also be reported. Altogether,

nodes are visited, and the running time for a query is O(k + log

n).

A WeakDelete operation (see Chapter 10) for a point p in the d-dimensional range tree can be performed

in O(log

n) time due to the number of nodes that must be traversed to find all entries belonging to p.

Lemma 2.13. A WeakDelete operation for a balanced d-dimensional range tree for n points in can be

performed in O(log

n) time.

Finally, with the help of the given results, we will answer a more general windowing query.

2.6. The (Axis-Parallel Box/Axis-Parallel Box) Windowing Problem

We consider the problem of answering the following (axis-parallel box/axis-parallel box) windowing query.

For a set of rectangular boxes, we want to find all boxes that are intersected by a query box B:

 Input: a set S of rectangular boxes in 2D;

 Query: a rectangular box B in 2D;

 Output: all boxes of S that intersect with B.

Let us assume that a set S of n rectangular boxes B

, B

…

, B

is given. A rectangular box B

has points

inside B in the following three cases (see Figure 2.9):

 The query B is fully contained in B

;

 An endpoint of B

lies inside B;

 A segment of B

crosses B, and no endpoint of B

is inside B.

Figure 2.9: The box B

reported by a (axis-parallel box/axis-parallel box) windowing query for B contains

B for i = 1, has a vertex inside B for i = 2, and has a segment that crosses B for i = 3.

For the first case, we can use a 2D segment tree of the boxes of S; see Section 2.3. We answer (axis-

parallel box/point) stabbing queries for the four end-points of B. These operations require O(k

+ log

time and O(n + log

n) space, where k

denotes the number of boxes in S that fully contain B.

In the second case, we can use a range tree in 2D and answer a rectangular (point/axis-parallel box)

windowing query for the endpoints of the B

s with respect to B; see Section 2.5. This can be performed in

time O(k

+ log

n) and O(n log n) space, where k

denotes the number boxes B

with endpoints in B.

The third case cannot be solved directly with the former approaches. We have to answer the following

(horizontal line segment/vertical line segment) stabbing query for the vertical line segments of box B and

the horizontal line segments of all boxes B

for i = 1,

…

, n.

 Input: a set S of horizontal line segments in 2D;

 Query: a vertical line segment s in 2D;

 Output: all segments of S intersected by s.

Of course, we have to answer also a (vertical line segment/horizontal line segment) stabbing query. This

is done by a simple rotation of 90 degrees.

A subset of horizontal line segments of S is stabbed by the line passing through the vertical line segment

s. Obviously, among these line segments, we must report all line segments whose left endpoints lie in a

rectangular range grounded in s and going to ∞; see Figure 2.10. If s is given by (x, y

) and (x, y

), the

corresponding box is represented by [−∞, x] × [y

, y

Figure 2.10: A rectangular range query by an infinite box grounded in s will answer the windowing query

in the third case.

Now, we have a stabbing query and a range query, and we adapt an interval tree accordingly. The

horizontal segments of S are stored in an interval tree for the x-coordinates of the segments. We have to

report the horizontal segments h stabbed by the x-coordinate x of s. For the left endpoints of such a

segment h, we have to take care that the y-coordinate of h lies also in the interval [y

, y

]. A node v of a

regular interval tree contains the list S

med

of the segments hit by x

med

; see Section 2.1. We replace the

sorted list M

and M

of the left and right endpoints of S

med

by two range trees. A 2D range tree M

for the

left endpoints of the segments in S

med

and a 2D range tree M

for the right endpoints of the segments in

med

In Algorithm 2.1, we simply replace

with

This gives an additional log factor for the space of the structure. For an interval query and a node v, it

suffices to check the corresponding 2D range trees. Note that all segments in S

med

are crossed by the line

X = x

med

. For example, if x < x

med

, we use the range tree M

of the left endpoints of S

med

; see Figure 2.11.

We answer the range query for [y

, y

] × [−∞, x]. Algorithm 2.2 is extended in a straightforward manner.

Figure 2.11: At the node v with a median v. x

med

in an interval tree, there is also a 2D range tree v. M

the left endpoints of the segments in v. S

med

. v. M

answers the query [y

, y

] × [−∞, x] for a segment s =

[(x, y

), (x, y

)].

In time O(log n + k

), we can report the k

segments of S

med

at node v that hit s and go on with the left

children and L

med

in the interval tree query. Altogether, we traverse log n nodes and report all k

intersecting segments, which gives O(k + log

n) query time.

With the results from the previous section, we can construct the extended interval tree in O(n log n) with

O(n log n) space.

Theorem 2.14. A 2D (axis-parallel box/axis parallel box) windowing query can be answered in O(log

+k)

time where k denotes the number of reported boxes. The corresponding data structures require O(n log

n) space and are built up in O(n log n) time.

As a subresult, we have shown how to report all horizontal line segments that are crossed by a single

vertical line segment.

Theorem 2.15. A (horizontal line segment/vertical line segment) stabbing query can be answered in

O(log

+k) time, where k denotes the number of reported line segments. The corresponding data

structures require O(n log n) space and are built up in O(n log n) time.

A WeakDelete operation for the combined interval range tree can be done in O(log

n) time, since we

additionally have to make a WeakDelete in the 2D range tree.

Lemma 2.16. A WeakDelete operation for the combined interval range tree for n boxes in 2D can be

performed in O(log

n) time.

2.7. Texture Synthesis

Textures are visual details of the rendered geometry. Textures have become very important in the past

few years because the cost of rendering with texture is the same as the cost without texture. Virtually all

real-world objects have texture, so it is extremely important to render them in synthetic worlds, too.

Texture synthesis generally tries to synthesize new textures, from given images, from a mathematical

description, or from a physical model. Mathematical descriptions can be as simple as a number of sine

waves to generate water ripples. Physical models try to describe the physical or biological effects and

phenomena that lead to some texture (such as patina or fur). In all of these ―model-based‖ methods, the

knowledge about the texture is in the model and the algorithm. The other class of methods starts with one

or more images, tries to find some statistical or stochastic description (explicitly or implicitly) of these, and

finally generates a new texture from the statistic.

Basically, textures are images with the following properties:

 Stationary: if a window with the proper size is moved about the image, the portion inside the window

always appears the same;

 Local: each pixel‘s color in the image depends on only a relatively small neighborhood.

Of course, images not satisfying these criteria can be used as textures as well (such as façades), but if

you want to synthesize such images, a statistical or stochastic approach is probably not feasible.

In the following, we will describe a stochastic algorithm that is very simple and efficient, and works

remarkably well [Wei and Levoy 00]. Given a sample image, it does not, like most other methods, try to

compute explicitly the stochastic model. Instead, it uses the sample image itself, which implicitly contains

that model already.

We will use the following terminology:

Initially, T is cleared to black. The algorithm starts by adding a suitably sized border at the left and the top,

filled with random pixels (this will be thrown away again at the end). Then it performs the following simple

loop in scan line order (see Figure 2.12):

1: for all p ∈ T do

2: find the p

∈ I that minimizes |N(p) − N(p

3: p := p

4: end for

Figure 2.12: The texture synthesis algorithm proceeds in scan line order through the texture and

considers only the neighborhood around the current pixel as shown.

The search in line 2 is exactly a nearest-neighbor search! This can be performed efficiently with the

algorithm presented in Section 6.4.1: if N(p) contains k pixels, then the points are just 3k-dimensional

vectors of RGB values, and the distance is just the Euclidean distance.

Obviously, all pixels of the new texture are deterministically defined, once the random border has been

filled. The shape of the neighborhood N(p) can be chosen arbitrarily; it must just be chosen such that all

pixels but the current pixel are already computed. Likewise, other ―scans‖ of the texture are possible and

sensible (for instance, a spiral scan order); they must just match the shape of N(p).

The quality of the texture depends on the size of the neighborhood N(p). However, the optimal size itself

depends on the ―granularity‖ in the sample image. In order to make the algorithm independent, we can

synthesize an image pyramid (see Figure 2.13). First, we generate a pyramid I

, I

…

, I

for the sample

image I

. Then we synthesize the texture pyramid T

, T

…

, T

level by level with the above algorithm,

starting at the coarsest level. The only difference is that we extend the neighborhood N(p) of a pixel p

over k levels, as depicted by Figure 2.13. Consequently, we have to build a nearest-neighbor search

structure for each level, because as we proceed downwards in the texture pyramid, the size of the

neighborhood grows.

Figure 2.13: Using an image pyramid, the texture synthesis process becomes fairly robust against

different scales of detail in the sample images.

Of course, now we have replaced the parameter of the best size of the neighborhood by the parameter of

the best size per level and the best number of levels to consider for the neighborhood. However, as Wei

and Levoy [Wei and Levoy 00] report, a neighborhood of 9 × 9 (at the finest level) across two levels

seems to be sufficient in almost all cases.

Figure 2.14 shows two examples of the results that can be achieved with this method.

Figure 2.14: Some results of the texture synthesis algorithm [Wei and Levoy 00]. In each pair, the image

on the left is the original one, and the one on the right is the (partly) synthesized one. (See Color Plate

IV.) (Courtesy of L.-Y. Wei and M. Levoy, and ACM.)

2.8. Shape Matching

As the availability of 3D models on the Internet and in databases increases, searching for such models

becomes an interesting problem. Such a functionality is needed, for instance, in medical image databases

or CAD databases. One question is how to specify a query. Usually, most researchers pursue the ―query

by content‖ approach, where a query is specified by providing a (possibly crude) shape, for which the

database is to return best matches.

[3]

The fundamental step here is the matching of shapes; i.e., the

calculation of a similarity measure.

Almost all approaches perform the following steps:

1. Define a transformation function that takes a shape and computes a so-called feature vector in

some high-dimensional space, which (hopefully) captures the shape in its essence. Naturally,

those transformation functions that are invariant under rotation and/or translation and tessellation

are preferred;

2. Define a similarity measure d on the feature vectors, such that if d(f

, f

) is large, then the

associated shapes s

, s

do not look similar. Obviously, this is (partly) a human factor issue. In

almost all algorithms, d is just the Euclidean distance;

3. Compute a feature vector for each shape in the database and store the vectors in a data structure

that allows for fast nearest-neighbor search;