gdalgorithms-list

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

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

Ok, so the Moller+Haines triangle-segment test is about
as good as it gets without any precomputation.  The
question is, how fast can you get with arbitrary
precomputation?  For example, I can precompute the
plane of the triangle, and the three perpendicular
planes which go through the edges.  Then the intersections
are all rays that hit the plane of the triangle and
whose intersection point is inside the three planes.
(BTW I don't care about computing the barycentric
coordinates).

Oh, BTW I also don't have the ray normal, so the 'd' used
in Moller+Haines requires a sqrt() for me to find, so
that's quite bad.  I think I could probably get the sqrt
out of there and push the length-squared of the ray through
the math to help it a bit.

The application here is when I have one triangle and I'm
about to do thousands of segment-triangle intersection tests
(actually, lots of bbox-triangle tests, but that requires
a segment-triangle test).


--------------------------------------
Charles Bloom           www.cbloom.com

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

[Norman V. <nh...@ca...>]

Charles Bloom writes:
>
>Ok, so the Moller+Haines triangle-segment test is about
>as good as it gets without any precomputation.  The
>question is, how fast can you get with arbitrary
>precomputation?  For example, I can precompute the
>plane of the triangle, and the three perpendicular
>planes which go through the edges.  Then the intersections
>are all rays that hit the plane of the triangle and
>whose intersection point is inside the three planes.
>(BTW I don't care about computing the barycentric
>coordinates).

Hey I want to know the same thing !

Here is a naive beginning :-)

Norman


// check to see if the intersection point is  actually inside this face
static bool PointInTriangle( Vec3 point, Vec3 tri[3] )
{
    REAL xmin, xmax, ymin, ymax, zmin, zmax;

    // punt if outside bouding cube
    if ( point[0] < (xmin = MIN3 (tri[0][0], tri[1][0], tri[2][0])) ) {
        return false;
    } else if ( point[0] > (xmax = MAX3 (tri[0][0], tri[1][0], tri[2][0])) )
{
        return false;
    } else if ( point[1] < (ymin = MIN3 (tri[0][1], tri[1][1], tri[2][1])) )
{
        return false;
    } else if ( point[1] > (ymax = MAX3 (tri[0][1], tri[1][1], tri[2][1])) )
{
        return false;
    } else if ( point[2] < (zmin = MIN3 (tri[0][2], tri[1][2], tri[2][2])) )
{
        return false;
    } else if ( point[2] > (zmax = MAX3 (tri[0][2], tri[1][2], tri[2][2])) )
{
        return false;
    }

    // drop the smallest dimension so we only have to work in 2d.

    REAL dx = xmax - xmin;
    REAL dy = ymax - ymin;
    REAL dz = zmax - zmin;
    REAL min_dim = MIN3 (dx, dy, dz);

    REAL x1, y1, x2, y2, x3, y3, rx, ry;

    if ( fabs(min_dim-dx) <= MY_EPSILON ) {
        // x is the smallest dimension
        x1 = point[1];
        y1 = point[2];
        x2 = tri[0][1];
        y2 = tri[0][2];
        x3 = tri[1][1];
        y3 = tri[1][2];
        rx = tri[2][1];
        ry = tri[2][2];
    } else if ( fabs(min_dim-dy) <= MY_EPSILON ) {
        // y is the smallest dimension
        x1 = point[0];
        y1 = point[2];
        x2 = tri[0][0];
        y2 = tri[0][2];
        x3 = tri[1][0];
        y3 = tri[1][2];
        rx = tri[2][0];
        ry = tri[2][2];
    } else if ( fabs(min_dim-dz) <= MY_EPSILON ) {
        // z is the smallest dimension
        x1 = point[0];
        y1 = point[1];
        x2 = tri[0][0];
        y2 = tri[0][1];
        x3 = tri[1][0];
        y3 = tri[1][1];
        rx = tri[2][0];
        ry = tri[2][1];
    } else {
        // all dimensions are really small so lets call it close
        // enough and return a successful match
        return true;
    }

    // check if intersection point is on the same side of p1 <-> p2 as p3
    REAL tmp = (y2 - y3) / (x2 - x3);
    int side1 = SIGN (tmp * (rx - x3) + y3 - ry);
    int side2 = SIGN (tmp * (x1 - x3) + y3 - y1);
    if ( side1 != side2 ) {
        // printf("failed side 1 check\n");
        return false;
    }

    // check if intersection point is on correct side of p2 <-> p3 as p1
    tmp = (y3 - ry) / (x3 - rx);
    side1 = SIGN (tmp * (x2 - rx) + ry - y2);
    side2 = SIGN (tmp * (x1 - rx) + ry - y1);
    if ( side1 != side2 ) {
        // printf("failed side 2 check\n");
        return false;
    }

    // check if intersection point is on correct side of p1 <-> p3 as p2
    tmp = (y2 - ry) / (x2 - rx);
    side1 = SIGN (tmp * (x3 - rx) + ry - y3);
    side2 = SIGN (tmp * (x1 - rx) + ry - y1);
    if ( side1 != side2 ) {
        // printf("failed side 3  check\n");
        return false;
    }

    return true;
}

Re: [Algorithms] Volumetric lighting question

[Scott B. <Sc...@Ma...>]

This may have been discussed in previous threads but I couldn't find any
info on the subject. Anyway, here goes.

I have concocted a camera dependent / texture based method for simulating
volume lighting which will give very realistic results. Now that is not the
hard part, I'm wondering how in gods name I will try to shade or fog out the
objects passing though the light cone. If I just let the textured cone alpha
blend over the object, this does not accurately depict the true volume
lighting because objects in the cone near the edges might be fully foged
even though there is not enough density to fog it out.

-Have anyone successfully implemented volumetric lighting (and not just a
cone with one alpha value :)  ?

-If so, do you have a way to properly blend objects with it?

-If so, have you been able to incorperate it with your shadowing methods to
produce any kind of shadow bleeding (or whatever you call it)?

And I'm not looking for 200 f/s algorithms here since it's for a 3D software
program and not for a game. :)

Thanks
Scott Bean

----- Original Message -----
From: Charles Bloom <cb...@cb...>
To: <gda...@li...>
Sent: Wednesday, August 02, 2000 9:44 PM
Subject: [Algorithms] fast triangle-segment test *with precomputation*


>
> Ok, so the Moller+Haines triangle-segment test is about
> as good as it gets without any precomputation.  The
> question is, how fast can you get with arbitrary
> precomputation?  For example, I can precompute the
> plane of the triangle, and the three perpendicular
> planes which go through the edges.  Then the intersections
> are all rays that hit the plane of the triangle and
> whose intersection point is inside the three planes.
> (BTW I don't care about computing the barycentric
> coordinates).
>
> Oh, BTW I also don't have the ray normal, so the 'd' used
> in Moller+Haines requires a sqrt() for me to find, so
> that's quite bad.  I think I could probably get the sqrt
> out of there and push the length-squared of the ray through
> the math to help it a bit.
>
> The application here is when I have one triangle and I'm
> about to do thousands of segment-triangle intersection tests
> (actually, lots of bbox-triangle tests, but that requires
> a segment-triangle test).
>
>
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

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

[Ignacio C. <i6...@ho...>]

Hi,
for box-triangle test i use an algorithm similar to the one used to test convex volumes via plane
shifting. I simply take the plane of the triangle, the antiplane, the edge bevels and the axis
aligned bevels to build a 'fake' convex volume. Then shift the planes of the volume depending on the
distance of the plane to the center of the box and last clip the movement segment against the
volume. I have found this algorithm to be the fastest, however it requieres a lot of precomputation,
and is in many cases a waste of space.


Ignacio Castano
ca...@cr...


Charles Bloom wrote:
> Ok, so the Moller+Haines triangle-segment test is about
> as good as it gets without any precomputation.  The
> question is, how fast can you get with arbitrary
> precomputation?  For example, I can precompute the
> plane of the triangle, and the three perpendicular
> planes which go through the edges.  Then the intersections
> are all rays that hit the plane of the triangle and
> whose intersection point is inside the three planes.
> (BTW I don't care about computing the barycentric
> coordinates).
>
> Oh, BTW I also don't have the ray normal, so the 'd' used
> in Moller+Haines requires a sqrt() for me to find, so
> that's quite bad.  I think I could probably get the sqrt
> out of there and push the length-squared of the ray through
> the math to help it a bit.
>
> The application here is when I have one triangle and I'm
> about to do thousands of segment-triangle intersection tests
> (actually, lots of bbox-triangle tests, but that requires
> a segment-triangle test).

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

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

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.

At 07:15 PM 8/4/2000 +0200, you wrote:
>
>Hi,
>for box-triangle test i use an algorithm similar to the one used to test
convex volumes via plane
>shifting. I simply take the plane of the triangle, the antiplane, the edge
bevels and the axis
>aligned bevels to build a 'fake' convex volume. Then shift the planes of
the volume depending on the
>distance of the plane to the center of the box and last clip the movement
segment against the
>volume. I have found this algorithm to be the fastest, however it
requieres a lot of precomputation,
>and is in many cases a waste of space.
>
>
>Ignacio Castano
>ca...@cr...
>
>
>Charles Bloom wrote:
>> Ok, so the Moller+Haines triangle-segment test is about
>> as good as it gets without any precomputation.  The
>> question is, how fast can you get with arbitrary
>> precomputation?  For example, I can precompute the
>> plane of the triangle, and the three perpendicular
>> planes which go through the edges.  Then the intersections
>> are all rays that hit the plane of the triangle and
>> whose intersection point is inside the three planes.
>> (BTW I don't care about computing the barycentric
>> coordinates).
>>
>> Oh, BTW I also don't have the ray normal, so the 'd' used
>> in Moller+Haines requires a sqrt() for me to find, so
>> that's quite bad.  I think I could probably get the sqrt
>> out of there and push the length-squared of the ray through
>> the math to help it a bit.
>>
>> The application here is when I have one triangle and I'm
>> about to do thousands of segment-triangle intersection tests
>> (actually, lots of bbox-triangle tests, but that requires
>> a segment-triangle test).
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com

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

[Ignacio C. <i6...@ho...>]

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.

yes, i'm calculating the intersection between triangles and moving bboxes, for that reason i need
the axis aligned planes so that the box slides over triangle vertexes. The good thing of this
algorithm is that you clip the movement segment, and for this reason you don't have to iterate and
test for intersection recursively. Also the axis aligned planes allow me to do fast rejection of the
segment, so at the end the only added cost is the antiplane, that is the last check, and usually
doesn't happen.


Ignacio Castano
ca...@cr...