gdalgorithms-list

RE: [Algorithms] Return of the front clip plane

[Tom F. <to...@mu...>]

Moving the near (and possibly far - depends on your app) clip planes
dynamically works very well indeed. Yes, there is the slight artifact that
walking past a tree affects the Z precision of the far-off building that
you're actually looking at, but then it's pretty hard to think of any system
that will do it any better, apart from the Z-partition trick (which is
expensive in some cases - though dead easy for flight sims).

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Steve Wood [mailto:Ste...@im...]
> Sent: 03 August 2000 20:09
> To: 'gda...@li...'
> Subject: RE: [Algorithms] Return of the front clip plane
> 
> 
> > -----Original Message-----
> > From: Jason Zisk [mailto:zi...@n-...]
> > 
> > Another solution is to just make your player's bounding 
> > volume larger so you can't get close enough to stuff to
> > clip into it, this works okay but I find that you have 
> > to keep the player from getting closer than 3 units with 
> > a 1 unit clip because of viewport rotation (just keeping the 
> > player 1 unit away is fine if you are staring straight at a 
> > wall but as soon as you rotate the edges of your viewport 
> > will clip it).
> > 
> 
> For my FPS I used a wall that I walked up to then looked up 
> and down, then
> adjusted my collision detection to prevent the player's view 
> from clipping
> the wall simply because of the view angle.  It seems to work fine...I
> wouldn't want to get into changing the viewport dimensions 
> cause wouldn't it
> distort the scene?  I'd reserve changing viewport dimensions 
> for special
> effects like underwater wooziness.
> 
> R&R
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

[Algorithms] Quadtree / Octtree neighbors

[Kelvin M. <ke...@re...>]

I need to construct a graph which connects all the neighboring nodes of a
quadtree and octree.  For each leaf node I need to determine all the other
leaves that border on it.  Does anyone know of an elegant way of doing this?

Kelvin McDowell

RE: [Algorithms] Return of the front clip plane

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Jason Zisk [mailto:zi...@n-...]
> 
> Another solution is to just make your player's bounding 
> volume larger so you can't get close enough to stuff to
> clip into it, this works okay but I find that you have 
> to keep the player from getting closer than 3 units with 
> a 1 unit clip because of viewport rotation (just keeping the 
> player 1 unit away is fine if you are staring straight at a 
> wall but as soon as you rotate the edges of your viewport 
> will clip it).
> 

For my FPS I used a wall that I walked up to then looked up and down, then
adjusted my collision detection to prevent the player's view from clipping
the wall simply because of the view angle.  It seems to work fine...I
wouldn't want to get into changing the viewport dimensions cause wouldn't it
distort the scene?  I'd reserve changing viewport dimensions for special
effects like underwater wooziness.

R&R

[Algorithms] water caustics

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

It just occurred to me that this could probably
be hacked pretty convincingly using projective
texturing.  Any object underwater would just get
an extra additive pass from a projective texture
which had some fake caustic lines in it.  If you
wanted to be fancy, you could even use the
heightmap of your water to draw some caustic
lines that resembled the crests of the wave
surface; totally incorrect, but probably great
looking for games.

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

[Algorithms] finding an optimal OBB

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

I'm sure there are lots of papers on this - any
good pointers?  I want to find the tightest
possible OBB for a collection of points.

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

Re: [Algorithms] Return of the front clip plane

[Gil G. <gg...@ma...>]

> For reference we use feet as units, with a front clip of 1 foot and a back
> clip of 1000 feet.

I think we use a near clip plane of about 8 inches and the bbox we use to
keep the player from clipping into walls is entirely reasonable. In my
opinion, even if you could have a near clip plane of 0, you wouldn't really
want it anyway. Putting something right into the players face is
disorienting.
-Gil

----- Original Message -----
From: "Jason Zisk" <zi...@n-...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 10:46 AM
Subject: [Algorithms] Return of the front clip plane


> Hi everyone, if you all remember our last episode "Attack of the Front
Clip
> Plane", we all learned that the further it is out the better zbuffer
> accuracy you have.  Much was learned by most.  :)
>
> Pushing my front clip out to 1 unit solved all of my zbuffer artifacts
> nicely in the last game.  We are trying some new things for the new game
and
> running into a problem that was mostly glossed over in the prequel to this
> email: collision and clipping of close-by objects.  Our game is first
> person, and when you get within 1 unit of an object it will get clipped
out.
> This is obviously pretty nasty.  :)  I remember one solution to this
> suggested was to dynamically move the front clip each frame depending on
how
> close objects are.
>
> Another solution is to just make your player's bounding volume larger so
you
> can't get close enough to stuff to clip into it, this works okay but I
find
> that you have to keep the player from getting closer than 3 units with a 1
> unit clip because of viewport rotation (just keeping the player 1 unit
away
> is fine if you are staring straight at a wall but as soon as you rotate
the
> edges of your viewport will clip it).
>
> Anyone else have any other ideas?  Right now it looks like I might be
going
> the dynamic front clip route but I really don't want to, I have a feeling
we
> will be seeing lots of artifacts out in the wilderness because the player
> will always be walking by a tree that they might not even be looking at.
>
> For reference we use feet as units, with a front clip of 1 foot and a back
> clip of 1000 feet.
>
> Thanks,
>
> - Jason Zisk
> - nFusion Interactive LLC
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] vipm instancing

[Oscar B. <tr...@te...>]

That's false, it will took 64K*2*3 bytes since we need 16bits per aach vertex
index.

Oscar Blasco wrote:

> You can do it by having a list of faces per object (faces can't be shared).
> Each object will use the same vertex buffer and the same vsplit list, but
> each object is in a different state, with different VB_Len and
> CurrentVsplit.
> This needs memory but if you have a 64k polys object you only need 64K*2
> bytes per object, which isn't very much.
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] vipm instancing

[Oscar B. <tr...@te...>]

You can do it by having a list of faces per object (faces can't be shared).
Each object will use the same vertex buffer and the same vsplit list, but
each object is in a different state, with different VB_Len and
CurrentVsplit.
This needs memory but if you have a 64k polys object you only need 64K*2
bytes per object, which isn't very much.

Re: [Algorithms] On 2D and 3D Sprites

[Doug C. <dc...@d-...>]

Thanks for the response, what I did to solve it was leave the view alone and
stick the view transpose into the worlds rotation components and it works
fine now. I was setting both of the rotational components ( in world and
view ) to identity to cancel out all rotations in both coordinate spaces but
thats not what I wanted to do ( obviously ).

Doug Chism
----- Original Message -----
From: "Stephen J Baker" <sj...@li...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 1:51 PM
Subject: Re: [Algorithms] On 2D and 3D Sprites


> On Thu, 3 Aug 2000, Doug Chism wrote:
>
> > I thought of an easy way to do 2D and 3D sprites but as of yet I cant
get it
> > to work well. The method involves simply grabbing the current world and
view
> > matrices and simply cancelling out the rotational components so the
object
> > can translate in world/view space but is always facing the camera.
>
> That's certainly what most people do.
>
> It's not *perfect* though because it keeps the object parallel to the
> screen - which is not the same thing as "facing the camera".
>
> The difference is usually unimportant unless you have a wide
field-of-view.
>
> > It works
> > great if the object is just sitting there at the origin, moving the
camera
> > in any direction still appears as the object is facing right at you
> >  whether its a 2D sprite or a 3D complex object ). Billboards are easy
> > because you can just allow rotations on one or more of the axes and it
> > appears correct also. The weird thing is when you transform the object
so it
> > is no longer centered at the origin. The object still faces you
perfectly,
> > but it moves in relation to the camera - i.e. if you translate it
along -x
> > it moves along the -x axis with respect to the camera, not the world.
For
> > instance it would always move to the left with a -x translation matrix
> > applied no matter what direction the camera faces it from.
>
> The model will always rotate about its local origin.  If you move it away
> from there (by changing the vertex coordinates) it's still going to rotate
> around the origin - I suppose that might *look* like a translation if
> it's sufficiently far from the origin.
>
> You have to position it billboards using the matrix and THEN nuke the
> rotation parts.
>
> > I cant figure out
> > why it would do this since I am still passing though the world
translation
> > as well as the view, just not their rotations. Any ideas on this, has or
> > anyone else tried doing 2D and 3D sprites in a similar fashon
successfully?
>
> I don't quite understand your explanation of the bug - but I can tell you
that
> I've done this successfully *many* times in the past and if you have it
> implemented right, it will work.
>
> Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
> L3Com/Link Simulation & Training (817)619-2466 (Fax)
> Work: sj...@li...           http://www.link.com
> Home: sjb...@ai...       http://web2.airmail.net/sjbaker1
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>

Re: [Algorithms] Return of the front clip plane

[Jamie F. <j.f...@re...>]

We're looking at that now.

Current plan:

Clip important scenery.
Cull unimportant objects / scenery when they get tricky.
Clamp important objects to viewport.

But we'll fiddle it for quality later. Our primary goal is to maintain the
illusion of solidity of objects, so that if the camera gets close to something /
in it, you don't start losing polys and seeing things you shouldn't. Having
decent enough collision code to (usually) keep your camera out of objects is a
good thing :)

We've plenty of Z buffer, and know we will always have, so we don't have to be
too careful there.

Anyone have any better ideas?

Jamie


Jason Zisk wrote:

> Hi everyone, if you all remember our last episode "Attack of the Front Clip
> Plane", we all learned that the further it is out the better zbuffer
> accuracy you have.  Much was learned by most.  :)
>
> Pushing my front clip out to 1 unit solved all of my zbuffer artifacts
> nicely in the last game.  We are trying some new things for the new game and
> running into a problem that was mostly glossed over in the prequel to this
> email: collision and clipping of close-by objects.  Our game is first
> person, and when you get within 1 unit of an object it will get clipped out.
> This is obviously pretty nasty.  :)  I remember one solution to this
> suggested was to dynamically move the front clip each frame depending on how
> close objects are.
>
> Another solution is to just make your player's bounding volume larger so you
> can't get close enough to stuff to clip into it, this works okay but I find
> that you have to keep the player from getting closer than 3 units with a 1
> unit clip because of viewport rotation (just keeping the player 1 unit away
> is fine if you are staring straight at a wall but as soon as you rotate the
> edges of your viewport will clip it).
>
> Anyone else have any other ideas?  Right now it looks like I might be going
> the dynamic front clip route but I really don't want to, I have a feeling we
> will be seeing lots of artifacts out in the wilderness because the player
> will always be walking by a tree that they might not even be looking at.
>
> For reference we use feet as units, with a front clip of 1 foot and a back
> clip of 1000 feet.
>
> Thanks,
>
> - Jason Zisk
> - nFusion Interactive LLC
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] On 2D and 3D Sprites

[Stephen J B. <sj...@li...>]

On Thu, 3 Aug 2000, Doug Chism wrote:

> I thought of an easy way to do 2D and 3D sprites but as of yet I cant get it
> to work well. The method involves simply grabbing the current world and view
> matrices and simply cancelling out the rotational components so the object
> can translate in world/view space but is always facing the camera.

That's certainly what most people do.

It's not *perfect* though because it keeps the object parallel to the
screen - which is not the same thing as "facing the camera".

The difference is usually unimportant unless you have a wide field-of-view.

> It works
> great if the object is just sitting there at the origin, moving the camera
> in any direction still appears as the object is facing right at you
>  whether its a 2D sprite or a 3D complex object ). Billboards are easy
> because you can just allow rotations on one or more of the axes and it
> appears correct also. The weird thing is when you transform the object so it
> is no longer centered at the origin. The object still faces you perfectly,
> but it moves in relation to the camera - i.e. if you translate it along -x
> it moves along the -x axis with respect to the camera, not the world. For
> instance it would always move to the left with a -x translation matrix
> applied no matter what direction the camera faces it from.

The model will always rotate about its local origin.  If you move it away
from there (by changing the vertex coordinates) it's still going to rotate
around the origin - I suppose that might *look* like a translation if
it's sufficiently far from the origin.

You have to position it billboards using the matrix and THEN nuke the
rotation parts.

> I cant figure out
> why it would do this since I am still passing though the world translation
> as well as the view, just not their rotations. Any ideas on this, has or
> anyone else tried doing 2D and 3D sprites in a similar fashon successfully?

I don't quite understand your explanation of the bug - but I can tell you that
I've done this successfully *many* times in the past and if you have it
implemented right, it will work.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

[Algorithms] Return of the front clip plane

[Jason Z. <zi...@n-...>]

Hi everyone, if you all remember our last episode "Attack of the Front Clip
Plane", we all learned that the further it is out the better zbuffer
accuracy you have.  Much was learned by most.  :)

Pushing my front clip out to 1 unit solved all of my zbuffer artifacts
nicely in the last game.  We are trying some new things for the new game and
running into a problem that was mostly glossed over in the prequel to this
email: collision and clipping of close-by objects.  Our game is first
person, and when you get within 1 unit of an object it will get clipped out.
This is obviously pretty nasty.  :)  I remember one solution to this
suggested was to dynamically move the front clip each frame depending on how
close objects are.

Another solution is to just make your player's bounding volume larger so you
can't get close enough to stuff to clip into it, this works okay but I find
that you have to keep the player from getting closer than 3 units with a 1
unit clip because of viewport rotation (just keeping the player 1 unit away
is fine if you are staring straight at a wall but as soon as you rotate the
edges of your viewport will clip it).

Anyone else have any other ideas?  Right now it looks like I might be going
the dynamic front clip route but I really don't want to, I have a feeling we
will be seeing lots of artifacts out in the wilderness because the player
will always be walking by a tree that they might not even be looking at.

For reference we use feet as units, with a front clip of 1 foot and a back
clip of 1000 feet.

Thanks,

- Jason Zisk
- nFusion Interactive LLC

[Algorithms] On 2D and 3D Sprites

[Doug C. <dc...@d-...>]

I thought of an easy way to do 2D and 3D sprites but as of yet I cant get it
to work well. The method involves simply grabbing the current world and view
matrices and simply cancelling out the rotational components so the object
can translate in world/view space but is always facing the camera. It works
great if the object is just sitting there at the origin, moving the camera
in any direction still appears as the object is facing right at you
 whether its a 2D sprite or a 3D complex object ). Billboards are easy
because you can just allow rotations on one or more of the axes and it
appears correct also. The weird thing is when you transform the object so it
is no longer centered at the origin. The object still faces you perfectly,
but it moves in relation to the camera - i.e. if you translate it along -x
it moves along the -x axis with respect to the camera, not the world. For
instance it would always move to the left with a -x translation matrix
applied no matter what direction the camera faces it from. I cant figure out
why it would do this since I am still passing though the world translation
as well as the view, just not their rotations. Any ideas on this, has or
anyone else tried doing 2D and 3D sprites in a similar fashon successfully?
Our old method involved transforming the coordinate center of the object
into view space and then reconstructing the object there ( slow - especially
for 3D objects ).

Doug Chism

RE: [Algorithms] vipm instancing

[Tom F. <to...@mu...>]

The only memory that needs to be replicated is index memory - that's what
we're talking about, right? The vertex memory can be shared between all
instances, since you never change the vertex data when collapsing/expanding
edges.

I did have a vague outline of a scheme to get better vertex cache coherency
(which normal VIPM lacks), and which, almost as a side-effect, allows you to
share much more index data between instances. Here's a quick brain-dump. One
day I'll write it up properly.

This could be improved by having several versions of the index buffer, but
pre-optimised for polygon number ranges:

For the range 100-200 triangles, I stripify the first 100 tris in the index
buffer, and then the rest are in collapse order. Over 200, I switch to the
200-400 range, which has the first 200 indices stripified, and the next 200
in collapse order. So this just involves switching index lists every power
of two triangles. Note that I haven't actually tried this yet!

You could also make the switches more often, i.e. every 100 tris. Also note
that some of the non-vanishing tris need to be modified during
expands/collapses, so they need to be in the un-optimised chunk as well.

I did write this all down properly somewhere - I've lost it now.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Paul Firth [mailto:pa...@ar...]
> Sent: 03 August 2000 11:30
> To: gda...@li...
> Subject: [Algorithms] vipm instancing
> 
> 
> Hi,
> 
> I was wondering if anyone can offer any advice about how to
> save memory when instancing multiple vipm models in a scene.
> 
> Ideally what I'd like to have is each instance only taking enough
> memory for as many tris as it currently has in its LoD, but I can't
> see any way to neatly increase this amount without some kind of
> crazy slow memory re-organisation.
> 
> I could use buckets but I really don't want to waste all that 
> luvly ram,
> does anyone have any ideas?
> 
> Cheers, Paul.
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

[Algorithms] vipm instancing

[Paul F. <pa...@ar...>]

Hi,

I was wondering if anyone can offer any advice about how to
save memory when instancing multiple vipm models in a scene.

Ideally what I'd like to have is each instance only taking enough
memory for as many tris as it currently has in its LoD, but I can't
see any way to neatly increase this amount without some kind of
crazy slow memory re-organisation.

I could use buckets but I really don't want to waste all that luvly ram,
does anyone have any ideas?

Cheers, Paul.

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*

[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;
}

[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] Rotation Matrices

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

Actually, the fact that rotations in 2d are commutative
and rotations in 3d are not is quite a deep fact.  It's
why we have fermions, so that all of us are solid objects,
not collapsed in some big degenerate bose condensate.

In 2d, the rotation group is equivalent to U(1), that is
the unitary group in 1d.  This is because a rotation in 2d
about the origin has the rule :

R(a)R(b) = R(a+b)

Which obviously implies commutation :

R(a)R(b) - R(b)R(a) = R(a+b) - R(a+b) = 0

[X,Y] = XY - YX

is the commutator.  When [X,Y] = 0 it means two
variables commute.

It also means that a valid group representation is the
complex exponential :

R(a) = e^(ia) = cos(a) + isin(a)

since

R(0) = 1  (the do-nothing operator is the identity)
R(2pi) = 1

which is also true for the complex exponential, and
obviously :

R(a)R(b) = e^(ia) e^(ib) = e^(i(a+b)) = R(a+b)

Some neat notes in 2d that will get you in the right
mind-set.  A rotation by 180 is the same as multiplying
by (-1), that is, it's an inversion, which the U(1)
form e^(i pi) = -1 confirms.  Also, we can see that
rotation by 180 must be (-1), since if you do it twice
(square it) then you must get 1, the identity.  Similarly,
rotation by 90 is (i), since if you do it twice you must
get a rotation by 180, which is (-1).  If you think of the
plane as a complex plane, you can easily confirm that
multiplying by pi takes (x+iy) to (ix-y), which is indeed
the 2d matrix

0 -1
1  0

which is a rotation by 90, and is the 2d real form of "i",
it's a square-root of minus one (it's also a Pauli Spin
matrix, but now we're getting ahead of ourselves!).

Now, in 3d, we have three axes.  We'll try to write this
in the complex exponential form again.  We write

Rx(a) = e^(a Jx) 

similarly for x,y,z.  The J's are the "generators" of the
group.  The Jx is a 3x3 matrix, and the identity here is
the 3x3 identity.  We know what a rotation by X needs to
be, so we can figure out the Jx quite easily.

Jx = 
0  0  0
0  0  1
0 -1  0

Jy =
0  0 -1
0  0  0
1  0  0

Jz =
0  1  0
-1 0  0
0  0  0

So Rx(a) = = {1 in the xx, and cos(a) in the yy and zz} + sin(a) Jx

      = 1xx + cos(a) * Jx^2 + sin(a) Jx

which follows since

-Jx^2 =
0  0  0
0  1  0
0  0  1

= {1 - 1xx}

We get the cos/sin version of R by actually expanding out the exponential
using its Taylor series polynomial and doing the matrix multiplies :

e^x = 0 + x + x^2/2 + ... x^n/n!

These J's are cute; they're actually the "basis" of the
3x3 antisymmetric matrices, and you should all know that
antisymmetric matrices is what rotations are all about.
In fact, rotations are the SO(n) group or orthonormal
matrices.  What I said earlier about U(1) is the statement
that SO(2) = U(1).  The quaternion-rotation matrix
corresponds state that SO(3) = SU(2) * Z2 , where the Z2
is the damned "Gimbal Lock", which is frequently said
as "SU(2) is a double-cover of SO(3)"; eg. in SU(2),
if you rotate by 2pi, you get a minus sign in there which
wasn't there before; you have to rotate by 4pi to get
the identity; this is the double-cover; this double-cover
corresponds to the two matrices in SO(3) which give
you the same rotation : rotation by theta around n, and
rotation by (2pi-theta) around -n (confining the angles
to be in (0,2pi)).

These J's are actually a 3x3 matrix representation of the
quanternions, BTW, since :

[Jx,Jy] = JxJy - JyJx = - Jz

In fact

[Ji,Jj] = - Eijk Jk

where Eijk is the "antisymmetric tensor", 
(Eijk = 1 if ijk is a cyclic permutation of xyz,
and -1 if it's anti-cyclic, and 0 otherwise.
eg. Exyz = 1, Eyxz = -1, Exxy = 0)
Which is the multiplication rule for the quaternion
basis (in commutator form).  (The quaternion bases
are also equal to the rotations by pi times i; that
is

I = i Rx(pi)
J = i Ry(pi)
K = i Rz(pi)

so that I K = - K and so on, which you can varify by
matrix multiplication, and I^2 = -1, etc.)

Some of you may be familiar with the J's ; they're used
in going from a quaternion to a matrix.

In fact, if you have a quaternion q = {w,x,y,z} then the
matrix equivalent is M(q) with M(q) = L * R  (here M,L
and R are all 4x4), and

L = 
J*q   -x
      -y
      -z
x y z -w

R =
J*q    x
       y
       z
-x-y-z-w

Where J*q is a 3x3 matrix created by treating J as a 4-vector
of matrices and doing the 4-dot product :

J = { 1 , Jx, Jy, Jz }

(and there's a (-1) in the 4-dot product on the 0th component :
V*W = -VwWw + VxWx + VyWy + VzWz )

The generators, J, are actually the infinitesimal rotations.
That is,

Rx(a) = lim(N->infinity) { (1 + a Jx/N)^N }

Obviously,

Rx(a) ~= (1 + a Jx)

when a is very small.  This is actually a good way to derive
the rotation matrices, starting from that infinitesimal
rotation (which is easy to derive by looking at what a vector
does when you rotate it a tiny bit; a tiny rotation is just
a linear transformation).  You then just exponentiate it like
the limit above, which gives you the exponential, which then
leads the sine and cosine!

Anyway, we've seen that the generators, J, don't commute, which
means that the rotations can't commute.  We'll use a convenient
form for the rotation matrices :

Rx(a) = 1xx + cos(a) * Jx^2 + sin(a) Jx
      = (1 - cos(a)) * 1xx + cos(a) + sin(a) Jx

[Rx(a),Ry(b)] = [ sin(a) Jx , sin(b) Jy ]

All the other terms have dropped out, since they are diagonal
matrices, and a diagonal matrix commutes with all matrices.
So

[Rx(a),Ry(b)] = sin(a) sin(b) [Jx,Jy] = - sin(a) sin(b) Jz

So, for example

[Rx(pi),Ry(pi)] = 0

and

[Rx(pi/2),Ry(pi/2)] = - Jz

In fact, it should be obvious that this commutator is equal to
zero, because it obviously must be zero whenever a or b is an
integer multiple of pi, and it must increase and decrease
smoothly around those points, so naturally we should have guessed
that form.

Anyway, the point is that if I rotate a vector in x then y, and I
rotate it in y then x, and take the difference, that difference is
"like" a rotation in Z.

Note Rx(pi/2) = 1xx + Jx
so Jz = (Rz(pi/2) - 1zz)
A rotation in Z by 90, projected onto the XY plane, that is,
the perpendicular of the projection of the vector in the XY plane.

For more jazz like this, see

http://math.ucr.edu/home/baez/README.html

or

http://www-physics.lbl.gov/~rncahn/book.html

and search the net for Lie Algebras and Rotations Groups such.

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

Re: [Algorithms] Rotation Matrices

[Ron L. <ro...@do...>]

> The deal is that 2D rotations always happen about the same axis
> (there IS only one after all) - so multiplication of rotation
> matrices is just like adding the angles - and addition is
> commutative.
>
Indeed, when you consider rotations about a common center in the plane, say
the origin, then concatenating rotations is isomorphic to adding angles
modulo 2pi.
Since addition of numbers is commutative you can conclude that concatenation
of plane rotations about a common center is also commutative.

However, it is worth mentioning that when you are considering affine
mappings of the plane, you need to consider the problem of concatenating
rotations about different centers (or, considered as 3D rotations, about
different but parallel axes).
These plane rotations about different centers, of course, do not have to
commute. But of course, you cannot represent them by 2x2 rotation matrices,
either.

RE: [Algorithms] FPS Questions

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Stephen J Baker [mailto:sj...@li...]
> 
> Motion blur is the way to fix that - and in theory, 
> you always need it in any system that has a discreet 'frame rate'.
>

I think the playing experience would be increased if there is always motion
blur in a multiplayer game to account for players that have faster
connections.  It always tweaks me to see a player disappear and reappear
several virtual feet away as I die from what seems like no reason except the
non-visual but all-powerful ping weapon.  At least with blur I'd see
something even if it is a stretched out player like the special effects in
John Carpenter's "The Thing" that has what appears to be several pikes
sticking into me.

> 
> Unfortunately, doing *good* motion blur (not just averaging together
> a bunch of static images - which doesn't really fix the temporal
> antialiasing problem) is incredibly difficult - you really have
> to render in four dimensions or something.
> 

hmm, why couldn't a card streak a tris or even a mesh for us? It would be
costly to blur in code, but wouldn't it be fairly cheap for the hardware to
copy the tris and just streaking the last few bits interleaved with bits
which form an outline of the form being blurred?  Actually, a proper blur
would probably take a sampling of bits across the mesh...I think a good
reference for the visual effect would be "Flash" comic books....just
multiple copies as in Mel Brooks' "SpaceBalls The Movie" when time is
compressed.

R&R

[Algorithms] Re:

[gl <gl...@nt...>]

(? that one got scrambled)


> Exactly, but just as with anti-aliasing, if you can afford to render at 4
> times the resolution, you might aswell just use 4 times the resolution,

Well, two times the resolution maybe ;)
--
gl

----- Original Message -----
Sent: Wednesday, August 02, 2000 9:09 PM


>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> Pø¤`ú¤

Re: [Algorithms] Rotation Matrices

[Steve B. <st...@li...>]

On Wed, 2 Aug 2000 Nik...@ao... wrote:

> Why isn't the multiplication of rotational matrices commutative?

Well, look at the top-left corner element and see how it's computed:

    dst[0][0] = m2[0][0] * m1[0][0] +
                m2[0][1] * m1[1][0] +
                m2[0][2] * m1[2][0] +
                m2[0][3] * m1[3][0] ;                                                        

Clearly, in general: m2[0][1]*m1[1][0] != m1[0][1]*m2[1][0] ...and so on,
so from the definition of how you multiply them, it's clearly not
commutative.

>  For example 
> if I have one rotation matrix which rotates 20 degrees around the Z axis, and 
> another which rotates 50 degrees around the X axis, depending on the order in 
> which I multiply them, I get different results.  Why is this?

Because that's how rotation works in the real world.

>  When rotating 
> an object there is no visible difference when it is first rotated on one axis 
> and then on another, is there?

Yes there is - you need a concrete example!

Do this - *really* do it - I MEAN NOW!

  1) Fold yourself a paper airplane.

...OK - finished?  Now do this:

[ Roll ==Rotation about Z axis,
  Pitch==Rotation about X axis ... for the sake of this example ]

  2) Hold the paper plane level, right side up with it's nose
     pointing away from you.
  3) Roll it 90 degrees so the left wing is pointing at the
     floor and the right wing is pointing up towards the ceiling.
  4) Now pitch the plane 90 degrees so the nose is pointing at
     the floor and the left wing is pointing towards your chest
     and the right wing is pointing away from you.
  5) Remember how it looks.

That was 90 roll followed by 90 pitch.  Now let's do the reverse:

  2) Hold the paper plane level, right side up with it's nose
     pointing away from you.
  3) Pitch it 90 degrees so the nose is pointing at the
     floor and the tail is pointing up towards the ceiling.
  4) Now roll the plane 90 degrees so the nose is pointing to
     your right and the tail to your left.
  5) Notice that your paper plane is in a different position now.

So, you can clearly see that rotations in the real world are definitely *not*
commutative.

>  I first looked in an elementary linear 
> algebra book for the answer; however it stated that the multiplication of 
> rotation matrices is commutative (although it was only covering 2D rotation 
> matrices). Any help would be appreciated.
 
Well, that's only true for 2x2 *rotation* matrices - if you do something
like:

   Take a square.
   Rotate 90 degrees.               (Still a square)
   Scale by 0.5 in the X direction. (Now a tall, thin rectangle)

...you get something different than:

   Take a square
   Scale by 0.5 in the X direction. (Now a tall, thin rectangle)
   Rotate 90 degrees.               (Now a short, fat rectangle)

...so arbitary 2x2 matrix multiplication *certainly* isn't commutative.

The math book was strictly correct - hopefully it didn't imply
that arbitary 2x2's could be multiplied commutatively.

The deal is that 2D rotations always happen about the same axis
(there IS only one after all) - so multiplication of rotation
matrices is just like adding the angles - and addition is
commutative.

If you do multiple 3D rotations that are all about the same axis
then they commute too.  The problem is when you have a pair
of rotations about DIFFERENT axes - that can't happen in 2D
so the non-commutative nature of arbitary axis rotations
doesn't show up.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

Re: [Algorithms] FPS Questions

[gl <gl...@nt...>]

> Exactly, but just as with anti-aliasing, if you can afford to render at 4
> times the resolution, you might aswell just use 4 times the resolution,

Well, two times the resolution maybe ;)
--
gl

Re: [Algorithms] FPS Questions

[gl <gl...@nt...>]

> > Well, strictly, you should still use motion blur even at 60Hz or higher
> > because motion blur is really just *temporal* antialiasing.

Exactly, but just as with anti-aliasing, if you can afford to render at 4
times the resolution, you might aswell just use 4 times the resolution,
rather than downsample.  Where it is useful (as someone touched on earlier)
is where you are limited by the refresh rate of a particular monitor, and
you have the option to render faster - you could then create real blur and
get more movement info into each frame.  But just as with anti-aliasing, you
need a factor of 2 ideally, so you'd have to be able to run at least twice
as fast, preferrably 4 times.
--
gl