thender@uxh.cso.uiuc.edu (09/27/90)
There has been quite a bit of discussion on the idea of a
point in a polygon. Currently we are needing a routine to find
if a point is in a volume. We feel that the point in a polygon
concept could certainly be extended to a volume, however we were
wondering if there was a better approach that could be used.
The volume in question has two restrictive constraints that
should make the job easier.
1. it is always 6 sided
2. each side is made up of 4 points which may
or may not be planar. the definition of the
surface defined by the four points is also not
defined yet.
(i.e. it is a distorted cube basically)
Any comments, references, or help would be greatly appreciatted by
the CFD Lab at the University of Illinois.
comments can be posted here or e-mailed to:
hender@uicfda.aae.uiuc.edumarkv@gauss.Princeton.EDU (Mark VandeWettering) (09/28/90)
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 VandeWetteringchiuk@iuvax.cs.indiana.edu (Kenneth Chiu) (09/28/90)
In article <11800013@uxh.cso.uiuc.edu> thender@uxh.cso.uiuc.edu writes: >Currently we are needing a routine to find >if a point is in a volume. > >The volume in question has two restrictive constraints that >should make the job easier. > > 1. it is always 6 sided > 2. each side is made up of 4 points which may > or may not be planar. the definition of the > surface defined by the four points is also not > defined yet. Depending on the exact definition of the sides, you may find it possible to test the point against all six surface normals. If the signs are all the same, then it is inside. In the general case, it only works for convex volumes. Of course, your surface normals must all agree to either point outside or inside.
thender@uxh.cso.uiuc.edu (09/28/90)
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 leaway. 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. However, the point in
the polygon routine posted here was new to us. Therefore we felt there
may be something more computationally desirable out there for a point
in a volume.
Todd Henderson
CFD Lab U. of Illinois
===========yesterdays note==========================
There has been quite a bit of discussion on the idea of a
point in a polygon. Currently we are needing a routine to find
if a point is in a volume. We feel that the point in a polygon
concept could certainly be extended to a volume, however we were
wondering if there was a better approach that could be used.
The volume in question has two restrictive constraints that
should make the job easier.
1. it is always 6 sided
2. each side is made up of 4 points which may
or may not be planar. the definition of the
surface defined by the four points is also not
defined yet.
(i.e. it is a distorted cube basically)
Any comments, references, or help would be greatly appreciatted by
the CFD Lab at the University of Illinois.
comments can be posted here or e-mailed to:
hender@uicfda.aae.uiuc.educorkum@csri.toronto.edu (Brent Thomas Corkum) (09/29/90)
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
unhd (Joseph M Joy) (10/02/90)
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