Path: utzoo!attcan!uunet!unhd!jmj
From: jmj@uunet!unhd (Joseph M Joy)
Newsgroups: comp.graphics
Subject: Re: point in volume?
Summary: A solution to the point in distorted cube problem
Keywords: point in volume
Message-ID: <1990Oct2.161748.15427@uunet!unhd>
Date: 2 Oct 90 16:17:48 GMT
References: <11800014@uxh.cso.uiuc.edu> and others
Sender: Joseph M. Joy
Reply-To: jmj@unhd.UUCP (Joseph M Joy)
Organization: Computing Information Services, University of New Hampshire
Lines: 76


Todd Henderson (Message-ID: <11800014@uxh.cso.uiuc.edu>) writes:
    Yesterday I posted a question about a point in a volume.  One of the
    things that I did not make clear is that the side can be concave.
    Therefore, we need a general test.  We also left the method for defining
    a surface up to you.  We felt this would give more leeway.  As things
    stand now we will break the 4 points into 2 triangles, and then do a
    similar operation to the point in the polygon.

I shall describe a solution to the "point in distorted cube"
problem that uses only "point in front of plane" tests
(at most 18 of them). I have not attempted to prove if this
is faster than the general "point in polygonal volume algorithm",
but it seems to be.

I consider only the interpretation that each distorted face is represented
by 2 triangles. Further, I assume the faces do not intersect each other.

In the following, by "point in front of
the plane (ax+by+cz>0) of a triangle" I mean in the direction of
the outward facing normal.

The algorithm considers each of the 6 faces in turn: if 
the point is behind each of these distorted faces then the point is inside
the cube else it it not.

The following pseudocode determines if a point is behind a
distorted face (potentially inside the volume) or in front
(definitely not in the volume):

If (a face is convex)
then
    if(point is BEHIND both the planes of the two triangles that 
       make up the face)
    then
	the point is behind the distorted face
    else
	the point is in front of the distorted face
else /* the face is concave */
    if(point is IN FRONT OF both the planes corresponding to the
       two triangles that make up the face)
    then
	the point is  in front of the distorted face
    else
	the point is behind the distorted face

We have to determine if a face is convex. Consider the following
face:

      A +-------+ B      It is divided into triangles ABC and ACD.
	| .     |        If point B is behind the plane of triangle
	|   .   |        ACD then the face is convex, else it is
	|     . |        concave.
      D +-------+ C

Notes: (1) The key insight is changing the test from "behind the face"
	   to "in front of the face" if the face is concave.
       (2) The algorithm works even if the faces are planar.
       (3) There are at most three "point in front of plane" tests
	   per face, so at most 18 such tests overall.
       (4) Use a bounding box to quickly determine if some points
	   are outside the volume.
       (5) If the problem is to determine if MANY points are inside
	   the SAME distorted cube, the code can be optimized in
	   several fairly obvious ways (for example, the tests for
	   convexity need be done only once per face).
       (6) I learned of this problem just this morning, and haven't
	   tested anything yet, so I could be making some big
	   mistake. Let me know!

Joseph
--------------------------------------------------------------------
Joseph M. Joy                        Internet: jmj@unh.edu
University of New Hampshire          Tel:      (603)862-4335 (office)
Dept. of Computer Science                      (603)742-9449 (home)
Durham, NH 03824