Graphics Reference
In-Depth Information
V
10
V
9
V
11
V
8
V
0
V
7
P
0
P
1
P
2
V
1
V
6
V
2
V
5
V
3
V
4
Figure 9.5
The Dobkin-Kirkpatrick hierarchy of the convex polygon
P
=
P
0
.
H
+
H
-
P
0
S
S
P
1
R
2
R
1
P
2
H
+
P
1
H
-
(a)
(b)
Figure 9.6
The supporting plane
H
, for (a)
P
2
and (b)
P
1
, through the point on the poly-
hedron closest to a query point
S
.
Starting at the innermost polyhedra
P
i
,
i
2, the closest point
R
i
on
P
i
to
S
is
found through straightforward calculation (see Section 5.1.6). If
R
i
=
S
, then
S
is
contained in
P
and the algorithm stops. Otherwise, knowing
R
i
, the closest point for
P
i
−
1
is found as follows. Let
H
be the supporting plane for
P
i
through
R
i
.
P
i
−
1
can
now be described as consisting of the part in front of
H
and the part behind
H
:
=
=
P
i
−
1
H
+
∪
P
i
−
1
H
−
.
P
i
−
1
∩
∩
H
+
The closest point
R
i
−
1
is therefore realized either between
P
i
−
1
∩
and
S
or
H
−
and
S
. The closest point between
P
i
−
1
H
−
and
S
is directly given
between
P
i
−
1
∩
∩
H
+
(due to the construction of the hierarchy) is defined by one
vertex and two edges, the closest point between
P
i
−
1
by
R
i
. Because
P
i
−
1
∩
H
+
and
S
is computed in
constant time. Consequently, the point on
P
closest to the query point
S
is located in
O
(log
n
) steps and in
O
(log
n
) time.
A DK hierarchy can also be used to locate the extreme vertex in direction
d
through
a relatively simple recursive procedure. First, the most extreme vertex
V
k
of the inner-
most polyhedron
P
k
is located by examining all four of its vertices. Knowing
V
k
, only
∩
