Leonidas Guibas.

Ray shooting, implicit point location, and related queries in arrangements of segments online

. (page 1 of 3)
Online LibraryLeonidas GuibasRay shooting, implicit point location, and related queries in arrangements of segments → online text (page 1 of 3)
Font size
QR-code for this ebook

Robotics Research
l^hnical Report




Ray Shooting, Implicit Point Location, and
Related Queries in Arrangements of Segments


Leonidas Guibas

Mark Overmars

Micha Sharir

Technical Report No. 433

Robotics Report No. 191

March, 1989




New York University
. ant Institute of Mathematical Sciences

Computer Science Division

25 1 Mercer Street New York. NX 1 00 1 2



Ray Shooting, Implicit Point Location, and
Related Queries in Arrangements of Segments


Leonidas Guibas

Mark Overmars

Micha Sharir

Technical Report No. 433

Robotics Report No. 191

March, 1989

New York University

Dept. of Computer Science

Courant Institute of Mathematical Sciences

251 Mercer Street

New York, New York 10012

Work on this paper by the third author has been supported by Office of Naval Research
Grant N00014-82-K-0381, by National Science Foundation CER Grant DCR-83-20085, by
grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research
grant from the NCRD — the Israeli National Council for Research and Development.

Ray Shooting, Implicit Point Location, and Related Queries in
Arrangements of Segments

Leonidas Guiba/^-^\ Mark Overmars^^^ and Micha Shari/'^-^

^'' DEC Systems Research Center, Palo Alto, CA

(^^ Computer Science Department, Stanford University

^'^ Computer Science Department, University of Utrecht

^^^ Courant Institute of Mathematical Sciences, New York University

'^^ School of Mathematical Sciences, Tel Aviv University


We extend and modify recent efficient techniques for half-plane range
searching, to obtain algorithms for answering efficiently several types of
queries on planar arrangements of segments and certain related structures.
For example, we show that, given n segments in the plane, we can preprocess
them in 0(n log r) randomized expected time and 0(n) space, so that, given
a query ray, emanating from an arbitrary point in an arbitrary direction, we
can determine the first segment (if any) hit by the ray, in time OCn^'^"*^'), for
any €>0. Other results involve "implicit" point location in an arrangement of
(possibly intersecting) triangles, polygon placement queries, and certain res-
tricted types of ray shooting and hidden surface removal for 3-dimensional
polyhedral scenes.

1. Introdoction

We begin with the following somewhat unusual opening remarks. The results of this
paper have been conceived and developed in the summer of 1987, but for various reasons
were left unpublished for almost two years. Meanwhile, there has been significant progress
on the problems studied here. In particula r, a r ecent work by Agarwal [Ag] present tech-
niques that achieve query time roughly OC^{n)) , and involve deterministic, rather than ran-
domized, preprocessing (however, the preprocessing time no longer remains close to linear).
Agarwal's results are based on a decomposition technique that is different from the one used
in this paper. Still, many of Agarwal's arguments are taken from this paper. As a public ser-
vice, to make our results somewhat more accessible, we have decided to elevate our paper
from the status of "unpublished manuscript" to that of a technical report.

Let G be a collection of n segments «i, ...,0.

Perhaps the most interesting application that we have is that of ray shooting in non-
simple polygons, or, more generally, in an arbitrary arrangement of (intersecting) segments.
In this problem we wish to preprocess the given segments so that, given any query ray p,
emanating from an arbitrary point in an arbitriiry direction, we can determine the first seg-
ment (if any) hit by p. Using a somewhat complex partition-tree technique, and an interesting
development of a linear ordering of the segments which is consistent with the order in which
they arc hit by certain types of rays, we obtain an algorithm that uses 0{n polylog(n))
preprocessing time and space, and achieves 0(«^'^"^*) query time, for any €>0. In the case
of a simple polygon, Chazelle and Guibas [CG] have developed a ray shooting procedure that
uses 0(n log log n) preprocessing time and 0{n) space, and achieves optimal O(log n) query
time; however, no efficient solution was known for the non-simple case (see some further
discussion on this problem in Section 3).

We also present additional applications of our technique, including

(i) Polygon placement queries. Here, given an arbitrary polygonal object P and a collection of
polygonal obstacles, we wish to determine whether a specific query translation of P will move
it to a free placement, in which it does not intersect any obstacle.

(ii) Implicit hidden surface removal in three dimensions . Here, given certain collections of tri-
angles in three dimensions, we wish to preprocess them so as to be able to answer efficiently
ray shooting queries, each asking for the first triangle (if any) hit by a given query ray. This
is a central subproblem of the ray-tracing problem in computer graphics [SML]. '

An important variant of these problems is when all the queries are known in advance,
as is the case in many applications. We call this variant the "batched" version of these prob-
lems. We show that batched problems can be solved considerably more efficiently than
unbatched ones, by constructing "customized" partition trees, which are tailored to handle
efficiently only the given queries, disregarding efficiency considerations for any other query.

An important theme of this paper is to point out the versatility of the partition tree tech-
niques, and their applicability to problems which do not always seem directly related to range
searching. In particular we note that the batching techniques introduced in [EGSh] can be
applied to a large variety of problems, much beyond the specific applications studied in
[EGSh]. This theme has also been observed and exploited by Dobkin and Edelsbrunner
[DE], where a weaker form of partition trees (that is, "conjugation trees") is used for space
intersection queries, in a manner similar to the one used here.

The paper is organized as follows. In section 2 we present efficient techniques to handle
(certain variants of) the implicit point location problem. Section 3 analyzes the planar ray
shooting problem. Section 4 presents techniques for handling certain three-dimensional ray
shooting problems. Section 5 handles polygon placement queries. Concluding comments and
discussion is given in Section 6.

2. Implicit Point Location

The planar point location problem is one of the most fundamental problems in computa-
tional geometry. It was studied in many papers, culminating in several optimal algorithms
[Ki], [EOS], [ST]. In this problem one is given a planar subdivision (or map) M, consisting
of n faces (and 0(n) edges and vertices), and the goal is to preprocess M into a data structure
which supports fast point location queries, in which, given a query point x, we wish to deter-
mine the face of M containing x. The algorithms in [Ki], [EGS], [ST] achieve this goal in
0{n log n) preprocesing time, 0(n) storage, and O(log n) query time; if the given map has
some favorable properties (e.g. is a convex subdivision) then preprocessing can be done in
linear time [Ki], [EGS].

A related (and simpler) problem is when the points to be located in M are all known in
advance. In this case, if m points are to be located, one can use a simpler sweeping algorithm
whose complexity is 0((m -t-/i) log n) [Pr]. This complexity is comparable with what one
could get using the preprocessing approach, but the algorithm is much simplified. We call this
version of the problem the "batched" version.

In this section we study the following generalization of the problem. Suppose the map
M is not given to us explicitly, but rather it is defined as the arrangement of n (usually inter-
secting) geometric objects of some simple shape. We will assume that the given objects are
line segments (or sometimes full or half lines); this will also enable us to handle general
polygonal objects. As will be demonstrated below, this situation arises in many applications,
including several visibility and placement problems. A naive approach to this modified prob-
lem is of course to calculate the arrangement M formed by the given segments, and then
preprocess it for point location as above. Calculating the arrangement can be accomplished in
time O(n^) and space O(n^), e.g. by calculating the arrangement of the lines containing the
segments as in [EOS]. However, since the input size is only 0{n), we face the challenge to
improve upon this naive approach, and obtain subquadratic solutions.

This goal is not always possible. For example, if the number m of points eventually to
be located in Af is a n^, the above method is optimal, and no subquadratic performance is


possible. Even in this case, however, there still remains the problem of reducing the space
requirement of the algorithm to subquadratic.

Another issue at hsmd is why point location in Af is desired. Often this is needed for
determining some "local" property of the query point. For example, if M is defined as the
arrangement of n triangles, then we might want to determine, for a query point x, whether it
is contained in the union of these triangles, or how many triangles contain x, or, if each trian-
gle is assigned some weight, what is the sum of the weights of the triangles containing x, or
the minimum -weight triangle containing x, etc. Similarly, for an arrangement of segments,
we might seek, for a query point x, which segment lies directly below x. We think of these
problems as being local, because they do not seek precise knowledge about the position of
the query point x in the entire arrangement, but rather confine themselves to combining
pieces of data, each obtained by "confronting" x with one of the objects, in some associative
manner (which can be done naively in linear time).

This section assumes that point location in M is indeed required for such a "local" task.
We show that in many cases these problems can be solved efficiently in subquadratic time
and space, by avoiding explicit calculation of M, and by storing instead some implicit
representation of it.

2.1. Statement of the Problem

For the sake of exposition, we will study the following specific problem. Given a col-
lection G = {*i, . . . ,e„} of n segments in the plane. With each segment «€G we associate a
function , defined on the entire plane which assumes values in some associative and com-
mutative semigroup S (whose operation will be conveniently denoted by "+"). We assume
that evaluation of 4),(x) at a point x, as well as addition of two elements in 5, takes constant
time. Two versions of the problem concern us. In the preprocessing version, we want to
preprocess the data into a data structure so that, given any query point x, we can calculate


efficiently. In the batched version, we are given m points p,, . . . ,p„, and we want to calcu-
late are assumed to satisfy certain properties, which make their cal-
culation closely related to point location. One assumption is that is constant on each face of
the arrangement A formed by the segments in G (or at least that can be obtained at constant cost per face as this arrangement
is calculated.

To facilitate the following algorithms, we also need to make certain additional assump-
tions concerning the function . Roughly speaking, these assumptions require that the result-
ing data structure can facilitate especially fast calculation of 0, the partition Hy = Hi '\% & convex planar subdivision of Q^ having
A/ = 0((— log — )"*) faces, such that any line / cuts at most c = 0((— log — )^) faces of H^,

€ € € €

and the total number of points of Gt in the faces cut by / is at most en. Such a subdivision
always exists, and can be constructed in constant randomized time [HW]. We then create M
children wj, . . . ,wm of v, one per face of H^, associate with each child Wj the corresponding
;'-th face Qy^j of H^, and the subset G'^ of the points of Gt in Q^j, and continue this partition-
ing process recursively at each Wj, thereby obtaining the desired tree T.

The tree T is used to process a query point p, or rather its dual line p ', as follows. We

propagate p* through T, starting at the root of T. For each node v of T, let ^"[p) =

2 f(p)- Suppose p* reaches some node v of r during propagation. If v is a leaf, then

^"{p) is simply 4),(/j), where e is the single element of G^ Otherwise, by the properties of
Hy mentioned above, p* cuts at most c faces of H^, and "misses" all the other faces. Let Wj
be a child of v. Up* cuts the face Q^j of H^ associated with Wj (this will be reflected by say-
ing that p * "reaches" Wj), then we obtain ^ at each of these points. All this can
be easily done in time 0{nl + Wy log n^) = 0{m^ log /ly), and space 0{m^).

For each child w of v, we collect all the points p,(.Ly whose dual lines have missed the
face Cw. and place them in a special "bucket" B^. associated with w. As above, if p ,, . . . ,p,
are in B^ then, for each i, the point p, lies either above all the lines Ij containing the seg-
ments ej € Gy, or below all these lines. Condition A implies that the values ^ip), forp iBy^,
can all be calculated in total time 0{by^ log n^), where by^ = |5h,|.

For an inner node v of T, we obtain (^"(pj) for all the points Pj(.L„, by propagating
these lines to the children w,, . . . ,wi^ of v, obtaining "''(p;) either recursively, if p^€Lh,,,
or from the bucket By^, otherwise. Then the values of 4>^ at all these points is readily obtained
by summing these partial results, as above.

It follows that the time T{m,n) needed to calculate the value of

1 3

Online LibraryLeonidas GuibasRay shooting, implicit point location, and related queries in arrangements of segments → online text (page 1 of 3)