Path: utzoo!utgpu!news-server.csri.toronto.edu!csri.toronto.edu!corkum
Newsgroups: comp.graphics
From: corkum@csri.toronto.edu (Brent Thomas Corkum)
Subject: Re: point in volume?
Message-ID: <1990Sep28.173417.10474@jarvis.csri.toronto.edu>
Organization: Civil Eng., University of Toronto
References: <11800013@uxh.cso.uiuc.edu> <2897@idunno.Princeton.EDU>
Date: 28 Sep 90 21:34:17 GMT
Lines: 34

This question comes at a most interesting time, I just finished writing
a set of routines for calculating whether a point is within a volume
defined by a set of concave or convex polygons. This is of course much
more rigorous than the original poster requires, if the volume is convex
then you can check on which side of each face you are by calculating a
surface normal (all polygons must have there vertices ordered consistently)
and taking a dot product. 

But for the case of concave volumes this will not work. So what I did was
apply the same algorithm for finding whether a point is inside a 2d concave
polygon (ie. number of edges crossed being odd or even, I think people
refer to this as the Jordan Curve algorithm??) and applied it in 3-D.
I take the point and fire a ray in a random direction, this almost certainly
prevents me from EXACTLY intersecting a edge or vertex since I'm working
in floating point coordinates but I check nonetheless. I then rotate the 
vector, along with all my polygons so that the vector coincides with the z 
axis and the point is at the origin. I then trim all polygons completely
behind the point. I then project orthographically the rest of the polygons
on to the x-y plane. I then use my 2d point inside a polygon to count
the number of polygons I'm inside. If its odd, I'm inside the volume, and
if it's even I'm outside. If I intersect an edge or vertex I try another
vector. So far it's worked on every volume I've tried with reasonable
speed (good enough for the number of points I try). There's probably a
faster method but this was fast as I already had all the components
written for other purposes, and heh, my philosophy is make it work
first, optimize, if necessary, later.

The source is not pretty but if anyone wants it there welcome to it,
mail me.

Brent
corkum@ecf.toronto.edu