Leonidas Guibas. # Ray shooting, implicit point location, and related queries in arrangements of segments online

. **(page 1 of 3)**

Online Library → Leonidas Guibas → Ray shooting, implicit point location, and related queries in arrangements of segments → online text (page 1 of 3)

Font size

Robotics Research

l^hnical Report

n!W

Mf

^^&

Ray Shooting, Implicit Point Location, and

Related Queries in Arrangements of Segments

by

Leonidas Guibas

Mark Overmars

Micha Sharir

Technical Report No. 433

Robotics Report No. 191

March, 1989

\

\

.V^lul

New York University

. ant Institute of Mathematical Sciences

Computer Science Division

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

..-^.*w^^'^'*'^-'*'i*r**i*'Â«^*

/M%r'Â«aÂ»

Ray Shooting, Implicit Point Location, and

Related Queries in Arrangements of Segments

by

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

ABSTRACT

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

-4

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

eiC

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

l^hnical Report

n!W

Mf

^^&

Ray Shooting, Implicit Point Location, and

Related Queries in Arrangements of Segments

by

Leonidas Guibas

Mark Overmars

Micha Sharir

Technical Report No. 433

Robotics Report No. 191

March, 1989

\

\

.V^lul

New York University

. ant Institute of Mathematical Sciences

Computer Science Division

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

..-^.*w^^'^'*'^-'*'i*r**i*'Â«^*

/M%r'Â«aÂ»

Ray Shooting, Implicit Point Location, and

Related Queries in Arrangements of Segments

by

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

ABSTRACT

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

-4

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

eiC

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

Online Library → Leonidas Guibas → Ray shooting, implicit point location, and related queries in arrangements of segments → online text (page 1 of 3)