Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!rutgers!husc6!harvard!gcc-milo!brad
From: brad@gcc-milo.UUCP
Newsgroups: comp.graphics
Subject: Re: Line-Polygon Intersection
Message-ID: <765@gcc-milo.ARPA>
Date: Fri, 21-Nov-86 13:44:37 EST
Article-I.D.: gcc-milo.765
Posted: Fri Nov 21 13:44:37 1986
Date-Received: Sun, 23-Nov-86 04:18:29 EST
References: <90@onion.cs.reading.ac.uk>
Organization: General Computer Company, Cambridge Ma
Lines: 30

> 
>         Can anyone help me with some 3D geometry? I am looking
> for an algorithm which will enable me to test if a line in a
> three-coordinate system with equation r=a+lambda*b intersects
> a polygon with vertices v1,v2,....,vn (n>=3,v = (x,y,z)) which
> lies in the plane n.r/|n| = p.

Last time I did this was for ray tracing polygons (where is Jim Kajia
when you need him?). And the easiest way I found was to find the point
of intersection between the line and the plane formed by three of the
vertices (let's assume they're co-planer) . This yields a 3d point.
Then, I translated the point and verticies into 2d (actually, I just translated
the point as the plane was defined via a plane equation) and then performed
the following:

	Calculate the sum of the angles formed by two adjacent verticies
	and the point. i.e. draw lines from the point to two adjacent 
	vertices. Do this for all the sets of vertices. If the sum of the
	angles is != 360, you are outside of the polygon.

Does this make sense? The idea is correct, but the particulars may be off.

Anyone have a better way to do this?
-- 

J Bradford Parker
General Computer (HyperDrive Beach, 3rd Cabana)
harvard!gcc-milo!brad

Good Sex is easier than a good slow roll. ("Left Stick! Right Rudder!...")