Ray - Polygon Intersection

 

First we test for intersection with the plane of the polygon. If ray intersects plane of polygon, we test to determine if it is inside or outside the polygon (the polygon is assumed to be entirely within plane). There are many different algorithms to determine if a point is inside or outside the polygon. We will use the modified "ray intersection" algorithm.

The basic idea of the algorithm: Shoot a ray from plane intersection point in arbitrary direction in plane and count the number of line segments crossed. If the number is odd then the point is inside else it is outside. (Jordan Curve theorem).

Example: (Note:We must deal with special case of hitting a vertex (later).)

Define polygon as a set of points G = Gn = [Xn Y n Zn] ; n = 0, 1, 2,..., N-1

Plane defined by points is AX + BY + CZ + D = 0

with normal Pn = [A B C] (may not be unit)

and have plane - ray intersection point Ri = [Xi Yi Zi] on the plane.

Step 1. Transform 3D plane to 2D plane with points specified by (U, V).

So we want (U, V) pair for every [X Y Z] in plane.

Could rotate plane about some axis, e.g. X until normal was parallel to another axis, e.g. Z, then just use other 2 axes (X, Y) as (U, V). Disadvantage: must generate and store rotatation matrix with each polygon and matrix multiplication must be done.

Simpler: throw away one of [X Y Z] coordinate and use other two (are using projection of plane onto two chosen coordinate.) Note: Area of polygon not preserved but topology is.

Throw away coordinate with greatest magnitude in plane equation ( the dominant coordinate), e.g. if have Pn = [0 -5 3], throw away Y coord. (Gives best projection)

Notice: if had Pn = [0 0 1] ,the ray then would be parallel to XY plane.

So have mapping X Y Z --> U V, where U V are each one of X Y Z (Do same for intersection pt. Ri)

After polygon projection:

1. Translate polygon so Ri is at origin, i.e. sutract Ui Vi from each vertex to vertices (U', V').

2. Imagine a ray starting from origin and proceeding along + U' axis. Test each edge of polygon against ray and note if crosses.

3. Count crossings: odd means inside
                                        even means outside.

 

For vertices on the ray (V' = 0) define as being on + V' side of ray.

So detailed algorithm:

1. For NV vertices [Xn Yn Zn] where n = 0..Nv-1, project polygon vertices [Xn Yn Zn] onto dominant coordinate plane (Un Vn).

2. Translate (U, V) polygon so intersection point is origin from (Un', Vn').

3. Set number of crossing Nc = 0;

4. Set sign holder SH as f(V' o) ( V' value of 1st vertex of 1st edge)

SH = -1 if V' < 0

SH = +1 if V' >= 0 (= to deal with vertices)

5. For each edge of polygon (Ua' V a') -> (Ub', Vb') where a = 0..Nv-1 and

b = (a + 1) mod Nv

Set next sign holder (Nsh) as f(Vb')

N sh = -1 if Vb' < 0

Nsh = +1 if Vb' >= 0.

If Sh <> NSH then if = then edge doesn't cross +U axis so no ray intersection and ignore

if Ua' > 0 and Ub' > 0 then edge crosses + U' so Nc = Nc + 1

else if either Ua' or U b' > 0 then line might cross +U, so compute intersection of edge with U' axis;

if intersection point is > 0 then must cross, so Nc = Nc + 1;

Set SH = Nsh;

Next edge.

6. If Nc odd, point inside else point outside.

 

Algorithm is efficient since most edges are trivially accepted or rejected. Only serious computation is when end points are in diagonally opposite quadrants.

Possible (general) problem: if Ri is exactly on a polygon edge then arbitrary inside or outside.

Can deal with this but irrelevant since if Ri on edge between 2 polys. and project both polygons onto same plane then algorithm determines Ri is inside one and only one of these polygons.

Also not likely to happen exactly at edge

example: Triangle

G0 = [-3 -3 7]

G1 = [3 -4 3]

G2 = [4 -5 4]

Ri = [-2 -2 4]

P = [1 2 1 -2]

Y coordinate dominant, so discard to get new set of 2d points.

Guv0 = [-3 7] Ruv = [-2 4]

Guv1 = [3 3]

Guv2 = [4 4]

Translate Ruv to UV origin, so have

Gu'v'0 = [-1 3]

Gu'v'1 = [5 -1]

Gu'v'2 = [6 0]

1st edge is: (-1, 3) -> (5, -1)

SH = +1 since Va' = 3 > 0;

Nsh = -1 since Vb' = -1 < 0

SH <> Nsh

Ua' < 0 and Ub' > 0 so must compute true intersection point.

Ua' - Va' * (Ub' - Ua') = -1 - 3 * (5 - (-1)) = 3.5 > 0

(Vb' - Va') (-1 - 3)

so Nc = Nc + 1 = 1;

Set SH = Nsh = -1;

2nd edge is: (5, -1) -> (6, 0)

So Nsh = +1 V' = 0

Thus SH <> Nsh

Ua' (5) > 0 and Ub' (6) > 0 -> NC = NC + 1 = 2;

SH = N sh + 1;

3rd edge is: (6, 0) -> (-1, 3)

Nsh = 1 = SH, thus no crossing;

Thus Nc = 2 => point outside poly.

Note Figure below --> point inside star has 2 crossings so outside, but might want to define polygon so these points are considered inside then modify previous algorithm as follows:

Current: Nc++ when edge crosses U axis

New: Nc++ when edge crosses U axis from +U to -U

Nc++ when edge crosses U axis from -U to +U

If Nc = 0 then point is outside polygon else inside ;

(for the figure below, Nc is winding number)

If polygon is made of string and pencil point is put on Ri

If string pulled taut then winding number is how many times string goes around point so for point in center of star --> string goes around 2 times.


Main ray trace intersections page
HyperGraph Table of Contents.
HyperGraph Home page.

Last changed June 02, 1999, G. Scott Owen, owen@siggraph.org