Path: utzoo!attcan!uunet!timbuk!cs.umn.edu!ub.d.umn.edu!rutgers!njin!princeton!gauss!markv
From: markv@gauss.Princeton.EDU (Mark VandeWettering)
Newsgroups: comp.graphics
Subject: Re: point in volume?
Message-ID: <2897@idunno.Princeton.EDU>
Date: 28 Sep 90 13:28:03 GMT
References: <11800013@uxh.cso.uiuc.edu>
Sender: news@idunno.Princeton.EDU
Reply-To: markv@gauss.Princeton.EDU (Mark VandeWettering)
Organization: Princeton University
Lines: 23

In article <11800013@uxh.cso.uiuc.edu> thender@uxh.cso.uiuc.edu writes:

[ asks for point-in-volume primitive testing ]

His particular case is a (possibly) distorted cube.  Let's assume for an 
instant that the sides are planar.  You can obviously use the Jordan curve
theorem again:  Cast a ray from the point, if it crosses an odd number of 
polyhedral faces, the point is inside, else the point is outside.

This could of course be used with nonplanar faces as well, except for the 
fact that the intersection test becomes more complicated.  For instance,
if the "cuboid" is bounded by a bicubic patch, the problem becomes one of
intersecting a ray with a bicubic.  Sections of quadratics could probably
solved quite simply, and are rather common.

The one thing that bothers me about this problem are potential problems
if a given ray crosses an "edge" or leaves through a vertex.  Eric Haines'
nifty scheme to decide either in or out will not work in this instance, 
unless the vertices that form each face are EXACTLY the same (which could
be arranged).  This is equivalent to ensuring that polyhedral faces meet
precisely, without gaps.

Mark VandeWettering