Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Containment test for concavities Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Raven

July 18, 1999, 12:43 AM

Hello,

I need an efficient algorithm for testing if a point is contained by an arbitrarily concave 3D volume defined by polygons. an EFFICIENT one, please. Also, approximations won't do, it has to be the real thing.

One way to do it is like this: Take a point and shoot 6 rays from it in all 6 directions(+-x,+-y,+-z). Count the intersections of each of the rays with the planes the polys make(they are all planar, but NOT coplanar!). If all of them are greater than 1 then inside. But:


-------------------
/ |
/ |
| |
| |
| |
| /
------------------/

*P

In this 2D case with a simple extension to 3D P is outside the volume(which is convex but that is beside the point, make a concavity on a floor if you like), but all intersections amount to at least one. Go ahead and count them... They all happen with the slanted edges.

Does anyone know a way around this? This seems to be the right track. Somebody has to know since this is invaluable for pure portal rendering with concave sections. Since this is the algorithm of choice for high-poly-count envirnoments with a few portals(most hw games are like that) it's very important. In such envirnoments BSP and non-portal leaf PVS won't do, too many splits/memory required. So ANSWER! Thank you

- Raven

 
Xavier Goaoc

July 23, 1999, 07:57 PM

>> I need an efficient algorithm for testing if a point is contained by an arbitrarily
>> concave 3D volume defined by polygons. an EFFICIENT one, please. Also, approximations
>> won't do, it has to be the real thing.

I do not understand much the method you suggest, but why not try this :
- take one ray starting from your point (any will do)
- count the number of intersections between that line and faces bounding your volume
for each intersection count :

- if it lies in the interior of the face you're testing, add 1.
- if it lies on the border of the face (on an edge), well you have to look closer
(or choose another ray for lazy implementation :)). your ray and the segment it intersects
define a plane (let's call it P), and the segment is the borderline between two faces.
if the plan P separate the faces, count 1 for the set of the two faces (this means
count 1 for one of the 2 faces, and do not test the other that share this edge) ;
otherwise count 1 for each face, ie 2 for both.
- if it lies on a vertice V of a face... I think (but I'm tired :)) that you should do
the same test as before for any of the segment sharing this edge. If one pair of
faces (sharing an edge of which V is a vertice) is not separated by the plane P,
count 2 for the set of all the faces that share this vertex ; if not, count 1 for the
set of all the faces that share this vertex.

when this is done (it means testing all the faces, maybe dropping some when edges or
vertices are encountered), just sum up ; this result represents the number of time
your ray crossed the surface defining your volume. If it's even, you're outside, if it's odd,
you're inside.

there may be mistakes, so feel free to ask for comments / questions... or to email me

 
Raven

July 23, 1999, 09:08 PM

Xavier Goaoc wrote:
>>when this is done (it means testing all the faces, maybe dropping some when edges or
>>vertices are encountered), just sum up ; this result represents the number of time
>>your ray crossed the surface defining your volume. If it's even, you're outside, if it's odd,
>> you're inside.

Consider a box aligned with the coordinate system. A point is inside the box by dotproduct tests. Now, if we shoot a ray straight up it will intersect only one face and it will return and odd result. But we're inside.

My method(i though about it more since then, this is the more robust version):

Take a point, shoot six rays to the six sides(+-x, +-y, +-z if you are in 3D) of the point. If you've intersected with a face remove it from the list and go on to next ray. If there is at least one intersection from all sides then we are inside. This is like looking around yourself to check if there are walls everywhere.

 
Raven

July 23, 1999, 09:08 PM

Xavier Goaoc wrote:
>>when this is done (it means testing all the faces, maybe dropping some when edges or
>>vertices are encountered), just sum up ; this result represents the number of time
>>your ray crossed the surface defining your volume. If it's even, you're outside, if it's odd,
>> you're inside.

Consider a box aligned with the coordinate system. A point is inside the box by dotproduct tests. Now, if we shoot a ray straight up it will intersect only one face and it will return and odd result. But we're inside.

My method(i though about it more since then, this is the more robust version):

Take a point, shoot six rays to the six sides(+-x, +-y, +-z if you are in 3D) of the point. If you've intersected with a face remove it from the list and go on to next ray. If there is at least one intersection from all sides then we are inside. This is like looking around yourself to check if there are walls everywhere.

 
xavier goaoc

July 24, 1999, 07:37 AM



Raven wrote:
>>
>>Consider a box aligned with the coordinate system. A point is inside the box by dotproduct tests. Now, if we shoot a ray straight up it will intersect only one face and it will return and odd result. But we're inside.
>>

well, I don't see the problem, since I stated that 'odd = inside & even = outside'

>>My method(i though about it more since then, this is the more robust version):
>>
>>Take a point, shoot six rays to the six sides(+-x, +-y, +-z if you are in 3D) of the point. If you've intersected with a face remove it from the list and go on to next ray. If there is at least one intersection from all sides then we are inside. This is like looking around yourself to check if there are walls everywhere.

you do not need to look everywhere around you... a single direction is enough
apart from that, I think it is the same basic idea... anyway, you needn't launch 6 rays.
why ? because a line intersects the surface an even number of time (you just have to fix some problems like intersecting the edge between two faces but let's not care for now) so you can walk along the line and figure out when you're inside, when you're outside :

# of crossings | state
----------------------------
0 outside (we are at the point at infinity on the line)
1 just entered... inside
2 outside again
3 inside again
...
even outside
odd inside

that's why one ray is sufficient. Now dealing with bad choices of rays (one that intersect edges for instance) is a bit more complicated, and I guess my explainations weren't clear enough. If so, just ask me and I'll try to improve them.
anyway, I believe my method to be mathematically exact ; there is just one case I forgot : when the intersection between your ray and the face is a segment... but we may deal with it after I think.

Do we agree ?

 
Raven

July 24, 1999, 05:35 PM

xavier goaoc wrote:
>>well, I don't see the problem, since I stated that 'odd = inside & even = outside'

Yes I don't see any problem either:)

>># of crossings | state
>>----------------------------
>> 0 outside (we are at the point at infinity on the line)
>> 1 just entered... inside
>> 2 outside again
>> 3 inside again
>> ...
>> even outside
>> odd inside
>>
>>that's why one ray is sufficient.

Ok I get it now. Yes you are absolutely right this will work, and it's quite trivial to prove it will. Thanks.

>> Now dealing with bad choices of rays (one that intersect edges for instance) is a bit more >> complicated, and I guess my explainations weren't clear enough. If so, just ask me and I'll >> try to improve them.
>> anyway, I believe my method to be mathematically exact ; there is just one case I forgot : >> when the intersection between your ray and the face is a segment... but we may deal with it >> after I think.

I think the simplest way to avoid all such situations is to just consider as if you intersected a single face and jitter the ray(nudge it to the side a little) so that it will not intersect the other faces in the next iteration. The problem it seems is to figure out if it intersected on an edge or a vertex, though that depends on my datastructures and not on the algorithm

>>Do we agree ?

Yes:) Thanx

- Raven

 
Raven

July 24, 1999, 05:35 PM

xavier goaoc wrote:
>>well, I don't see the problem, since I stated that 'odd = inside & even = outside'

Yes I don't see any problem either:)

>># of crossings | state
>>----------------------------
>> 0 outside (we are at the point at infinity on the line)
>> 1 just entered... inside
>> 2 outside again
>> 3 inside again
>> ...
>> even outside
>> odd inside
>>
>>that's why one ray is sufficient.

Ok I get it now. Yes you are absolutely right this will work, and it's quite trivial to prove it will. Thanks.

>> Now dealing with bad choices of rays (one that intersect edges for instance) is a bit more >> complicated, and I guess my explainations weren't clear enough. If so, just ask me and I'll >> try to improve them.
>> anyway, I believe my method to be mathematically exact ; there is just one case I forgot : >> when the intersection between your ray and the face is a segment... but we may deal with it >> after I think.

I think the simplest way to avoid all such situations is to just consider as if you intersected a single face and jitter the ray(nudge it to the side a little) so that it will not intersect the other faces in the next iteration. The problem it seems is to figure out if it intersected on an edge or a vertex, though that depends on my datastructures and not on the algorithm

>>Do we agree ?

Yes:) Thanx

- Raven

 
xavier goaoc

July 24, 1999, 07:10 PM

you're welcome :)


 
This thread contains 8 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.