gdalgorithms-list

RE: [Algorithms] fast triangle-segment test *with precomputation*

[<Chr...@Pl...>]

Charles Bloom wrote:
>Ok, you have a good point, but isn't it even simpler than that?
>
>I have one plane for the triangle, and 3 planes through the edges that
>are perpendicular to the plane of the triangle.
>
>To test for bbox-triangle do :
>
>1. bbox must intersect the plane of the triangle.
>2. bbox must be intersect or behind all 3 edge planes.
>
>That's it !  Four tests, all of them providing great quick-rejection.
>This is simpler, I guess, because my BBox is not moving, and I guess
>you're doing moving-BBox tests like Quake.

That only works as a conservative test, but not as an exact test.

If the box, straddling the triangle plane, is just outside one of the
vertices of the triangle, then both criteria are met, but there's no
actual intersection.


Christer Ericson
SCEA, Santa Monica

RE: [Algorithms] fast triangle-segment test *with precomputation*

[<Chr...@Pl...>]

Charles Bloom wrote:
>Urgh; of course you're right; boxes that are outside but
>near the corners are classified wrong.  I think you could
>probably detect that case and handle it from there; eg.
>when the box straddles two edge planes, look at the vertex
>those planes share, and then test whether the box is away
>or towards the center of the triangle relative to that vertex
>(or something).

I kinda seems that way, doesn't it, but it's not quite that
easy I'm afraid.

Consider all the relative orientations that the triangle and
the box can be in, and I think you'll find that what you'll end
up with is going to be equivalent to doing all the required
separating axis tests.

Let's see... 3 for the edges/face normals of the box, 1 triangle
face normal, 3 triangle edges, and 9 for combination of edges of
both, so 16 axes.

Christer Ericson
SCEA, Santa Monica

Re: [Algorithms] fast triangle-segment test *with precomputation*

[<SHA...@ao...>]

In a message dated 05/08/00 01:53:24 !!!First Boot!!!, 
Chr...@Pl... writes:

<< That only works as a conservative test, but not as an exact test.
 
 If the box, straddling the triangle plane, is just outside one of the
 vertices of the triangle, then both criteria are met, but there's no
 actual intersection. >>

I am currently doing a triangle/aabb test for an octree implimentation. This 
test is as near as exact as I can think of. It does 3 tests, each one more 
time consuming than the last...

1) Are any of the 3 tri vertices inside bbox...if so return true
2) Does any tri edge intersect bbox face...if so return true
3) Generate 8 lines, each one connects a corner of the aabb to it's diagonal 
opposite then test, does this line intersect tri face...if so return true
return false.

The last test is in case any corner of the aabb punches through the face of 
the tri, in which case the tri is technically inside the aabb.

How do you do yours??

John.

RE: [Algorithms] fast triangle-segment test *with precomputation*

[Alex P. <al...@Ex...>]

A few questions about your 3rd test:
- Are you testing line or line segment intersection?
- Why do you need to use the diagonal?
- Doesnt the test hold for any bbox edge as well.
- Also why are you testing 8 lines?  Four parrallel
  bbox edges should be enough to cover any case where
  a corner 'punches through the triangle'

Alex

-----Original Message-----
From: SHA...@ao... [mailto:SHA...@ao...]
Sent: Saturday, August 05, 2000 4:55 AM
To: gda...@li...
Subject: Re: [Algorithms] fast triangle-segment test *with
precomputation*


In a message dated 05/08/00 01:53:24 !!!First Boot!!!,=20
Chr...@Pl... writes:

<< That only works as a conservative test, but not as an exact test.
=20
 If the box, straddling the triangle plane, is just outside one of the
 vertices of the triangle, then both criteria are met, but there's no
 actual intersection. >>

I am currently doing a triangle/aabb test for an octree implimentation.
This=20
test is as near as exact as I can think of. It does 3 tests, each one
more=20
time consuming than the last...

1) Are any of the 3 tri vertices inside bbox...if so return true
2) Does any tri edge intersect bbox face...if so return true
3) Generate 8 lines, each one connects a corner of the aabb to it's
diagonal=20
opposite then test, does this line intersect tri face...if so return
true
return false.

The last test is in case any corner of the aabb punches through the face
of=20
the tri, in which case the tri is technically inside the aabb.

How do you do yours??

John.

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] fast triangle-segment test *with precomputation*

[<SHA...@ao...>]

In a message dated 07/08/00 17:36:44 !!!First Boot!!!, 
al...@ex... writes:

<< A few questions about your 3rd test:
 - Are you testing line or line segment intersection?
 - Why do you need to use the diagonal?
 - Doesnt the test hold for any bbox edge as well.
 - Also why are you testing 8 lines?  Four parrallel
   bbox edges should be enough to cover any case where
   a corner 'punches through the triangle'
 
 Alex >>

This third test is done because of the possibility of a triangle location 
which has 

1) No vertices inside the box
2) No edges which intersect any box face

In this case I compute 4 ( you are right, I overestimated when I tried to 
visualise this! :) ) line segments and test if these intersect the face of 
the triangle.

Having just looked at your reply you are also right in that 4 parallel box 
edges would do exactly the same thing as 4 diagonal lines.

My bbox structure does not actually contain edges, only 2 3d points which are 
enough to describe a square cube so for me it is just a matter of choice 
whether to use parallel or diagonal edges/lines.

Regards,

John.

RE: [Algorithms] fast triangle-segment test *with precomputation*

[Robert D. <RD...@ac...>]

> This third test is done because of the possibility of a 
> triangle location which has 
> 
> 1) No vertices inside the box
> 2) No edges which intersect any box face
> 
> In this case I compute 4 ( you are right, I overestimated 
> when I tried to visualise this! :) ) line segments and test if these 
> intersect the face of the triangle.
> 
> Having just looked at your reply you are also right in that 4 
> parallel box edges would do exactly the same thing as 4 diagonal lines.

Actually this is not true ... if the triangle was also parallel to the
chosen four parallel box edges, then it could fall between all of them, not
intersect with any of them, and yet still intersect with the box.

The four diagonal lines on the other hand will cover every possible case,
since it is impossible for a plane to pass through the cube without crossing
at least one diagonal somewhere.

Robert

RE: [Algorithms] fast triangle-segment test *with precomputation*

[Charles B. <cb...@cb...>]

Urgh; of course you're right; boxes that are outside but
near the corners are classified wrong.  I think you could
probably detect that case and handle it from there; eg.
when the box straddles two edge planes, look at the vertex
those planes share, and then test whether the box is away
or towards the center of the triangle relative to that vertex
(or something).

At 06:51 PM 8/4/2000 -0700, you wrote:
>
>
>
>
>Charles Bloom wrote:
>>Ok, you have a good point, but isn't it even simpler than that?
>>
>>I have one plane for the triangle, and 3 planes through the edges that
>>are perpendicular to the plane of the triangle.
>>
>>To test for bbox-triangle do :
>>
>>1. bbox must intersect the plane of the triangle.
>>2. bbox must be intersect or behind all 3 edge planes.
>>
>>That's it !  Four tests, all of them providing great quick-rejection.
>>This is simpler, I guess, because my BBox is not moving, and I guess
>>you're doing moving-BBox tests like Quake.
>
>That only works as a conservative test, but not as an exact test.
>
>If the box, straddling the triangle plane, is just outside one of the
>vertices of the triangle, then both criteria are met, but there's no
>actual intersection.
>
>
>Christer Ericson
>SCEA, Santa Monica
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com