Path: chuka.playstation.co.uk!tjs
From: tjs@cs.monash.edu.au (Toby Sargeant)
Newsgroups: scee.yaroze.programming.3d_graphics
Subject: Re: Poly Intersections
Date: 3 Jan 1999 22:09:48 GMT
Organization: PlayStation Net Yaroze (SCEE)
Lines: 30
Message-ID: <slrn78vqlb.f0.tjs@longford.cs.monash.edu.au>
References: <3689671E.AA01BBAB@hinge.mistral.co.uk>
NNTP-Posting-Host: longford.cs.monash.edu.au
X-Newsreader: slrn (0.9.4.3 UNIX)

On Tue, 29 Dec 1998 23:34:55 +0000, Craig Graham wrote:
>Anyone got a nice quick way of doing the ray plane intersect?
>(an O(1) algorithm would be good)

Express plane one in terms of the generic plane equation
ax+by+cz+d=0 (1).
(n.b. - (a,b,c) is the vector of the polygon normal, and d can be calculated
via substitution)
express the ray in parametric form:
x=u_1.t+v_1, y=u_2.t+v_2, z=u_3.t+v_3. (2)
substitute (2) into (1):
a(u_1.t+v_1)+b(u_2.t+v_2)+c(u_3.t+v_3)+d=0 (3)
solve for t using (3).
solve for x,y,z using (2).

If you want to calculate the intersection only if the point is inside the
polygon (odd, but who knows...) then:
if it's a convex polygon:

compute intersection of plane.
compute dot product of vector from poly.p1->intersection and poly.p1->poly.p2
compute dot product of vector from poly.p2->intersection and poly.p2->poly.p3
if the signs are the same, then the point is inside the polygon.

if it's not convex, there are more complex algorithms that do this fast,
but I don't know them.

Hope this is what you want,

Toby.