gdalgorithms-list

Re: [Algorithms] 3d Lines Intersection

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

Steve Wood  wrote:

>> -----Original Message-----
>> From: ro...@do... [mailto:ro...@do...]
>> 
>[snip]
>> 
>
>What if we test by projecting against the yz plane? Using your example:
>
>The projection of line1 on the yz plane is the point (0,0,0)
>The projection of line 2 on the yz plane is the line z = y+1
>There is no intersection.
>

Exactly.  I constructed the counterexample that way so that it would
be plain as the nose on your face that there is no intersection.  It
doesn't change the fact that it is a counterexample to the algorithm
as stated. 

Another counter example in which the non-intersection is not quite as
plain.

Line 1 :
Parametric (s, s, 0)
Implicit    y = x, z=0

Line2 :  (same as before)
Parametric (0,t, t+1)
Implicit   z = y+1, x=0

Projections on xy plane:
Line 1  y= x , z=0
Line 2 x=0, z = 0, i.e, the y axis
Intersection (0,0,0)

Projections on xz plane
Line 1 z=0, y=0  i.e. the x axis
Line 2  x=0 y=0 i.e the z axis,
Intersection (0,0,0)

So the putative algorithm says that the lines intersect at (0,0,0)
when in fact they still don't intersect anywhere (an exercise for the
reader),

In this counterexample the projections onto the yz plane do intersect
at  (0,-1, 0), so it is a little harder for you to show
non-intersection.  

This suggests that  maybe one could try modify the suggested algorithm
to involve comparing the x coordinates of the intersections of the xy
and xz projections AND comparing the y coordinates of the
intersections of the xy and yz projections AND comparing the z
coordinates of the intersections of the xz and yz projections. I do
think you'd have to do all three projection directions to unravel all
the special cases, as when two lines project onto the same line (which
can happen when they intersect and also when they don't intersect).  

And then of course, you will never get exact equality in ANY of the
tests due to rounding errors and the fact that lines in space hardly
ever intersect anyway, but  the algorithm does not give a clue how to
estimate the distance of closest approach of the lines in space  from
the differences in the respective x, y, and z coordinates of the
intersections of the various projections.    For example, for the
algorithm as originally stated, I can construct a counter example
where x1 and x2 are pretty damned close but the lines in space miss by
a mile.  

No, the whole project would be a pretty big and expensive mess
compared to just solving the simple 2x2 system that I showed how to
derive in two different ways based on elementary mathematics, and
which is based directly on measuring the distance of closest approach.
(Of course it, too, has special cases to deal with as well. I think
that the only case where the 2x2 system fails to have a unique
solution is the case that it has infinitely many solutions, which is
the case that the two lines are parallel and so have infinitely many
mutual perpendiculars, so infinitely many pairs of nearest points, all
at the same distance, and this special case is immediately detectable
in the solution of the simple 2x2 system). 

[Algorithms] Triangulated Irregular Networks

[Chris B. <Chr...@ma...>]

[First post, Hello All]

I'm also rather new to 3d graphics and like many here am writing a game, that also will use a terrain engine. Something that has been inspiring me recently was some papers I've been reading on TIN's Triangulated Irregular Networks. Something tells me that this will be much cooler for creating accurate and efficent terrain structures over the default ROAM structure

I've spoken to a few people about TIN's but as of yet havent found anyone who has actually implemented them. 

I've a few problems with TIN's however, :
-How do you efficiently determine the error without scanning the entire bitmap each pass?
-I don't get the 'remove a line' part. ie, which line do you remove?

Links to any well commented source would eb helpful.

Thanks

Chris 

Re: [Algorithms] 3d Lines Intersection

[Conor S. <cs...@tp...>]

Well, the best way to start is to see if the lines intersect. This can be
done with a Plücker space dot product (see
http://www.flipcode.com/tutorials/tut_pluecker.shtml).

Then, you can simply find where one line intersects a plane which the other
line is on (in Plücker space this is incredibly easy to find).

Conor Stokes

RE: [Algorithms] 3d Lines Intersection

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

> -----Original Message-----
> From: ro...@do... [mailto:ro...@do...]
> 
> But the explanation of the math behind an algorithm, or maybe a couple
> of different algorithms, is a lot more informative than a pointer to
> somone else's code, isn't it?
> 

Many of the people here would rather have the code than the
explanation...code they can use. If they could use the explanation then they
probably could have been worked it out themselves as it sounds you might be
able to.  They probably came to this list because they couldn't find the
code library to use...i.e. a function that returns a point when giving it
two lines.  Or, they want to write the code themselves in which case they
just want the formula/algorithm in a format that they can code with.

> > You also will not find it in analytical geometry books.
> >
> 
> And in how many such books have you searched?  And don't forget to
> check the exercises.
> 

Checking a book is usually the first step...and yes, sometimes problems not
covered in the topics are presented as an exercise.  However, the solution
of the intersection of 2 lines in R3 does not present any new material and
thus is usually not included in a text book even as an exercise.  If you
find such a book that contains solutions to problems such as intersection of
2 lines in 3D then please let us know.

R&R

RE: [Algorithms] 3d Lines Intersection

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

> -----Original Message-----
> From: ro...@do... [mailto:ro...@do...]
> 
[snip]
> 

What if we test by projecting against the yz plane? Using your example:

The projection of line1 on the yz plane is the point (0,0,0)
The projection of line 2 on the yz plane is the line z = y+1
There is no intersection.

R&R

Re: [Algorithms] Terrain Organization

[James C. <jj...@us...>]

Give  the message board over at Longbow Digital Arts
(www.longbowdigitalarts.com) a try, under the programming forum there are
many great discussions on ROAM as well as several other CLOD algorithms, as
well as all kinds of general useful terrain rendering information.

-----Original Message-----
From: Pai-Hung Chen <pa...@ac...>
To: gda...@li...
<gda...@li...>
Date: Saturday, July 29, 2000 8:32 PM
Subject: Re: [Algorithms] Terrain Organization


>Fred wrote:
>
>> Hi,
>>
>> I'm new to terrain rendering, but at this right moment I was
>reading an
>> article about ROAM ; looks very interesting and not so hard,
>when it's well
>> explained as it is on
>> http://www.psky.com/prog/terrain.htm
>> Have a look !
>> It seems that you do NOT have to reconstruct all the stuff for
>each frame,
>> and it's precisely one of the interests of ROAM.
>
>Actually I've read the original ROAM paper and another one on
>Gamasutra, and was helplessly frustrated. :-(  I'll look at the
>one you suggested to see if it makes any more sense to me.  Thanks
>a lot!
>
>Pai-Hung Chen
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] 3d Lines Intersection

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

Steve Wood  wrote:

>> -----Original Message-----
>> From: Albert_J [mailto:Alb...@te...]
>> 
>> Is there a good algo for finding a point of intersection 
>> between two *3D lines*?
>>
>
>Somewhere there might be something already coded.
>

But the explanation of the math behind an algorithm, or maybe a couple
of different algorithms, is a lot more informative than a pointer to
somone else's code, isn't it?


>> I've searched the web, but all of them seems to eYplain about 
>> 2D lines intersection only.
>> 
>
>That's because not many people need it. 

Yeah, right, tell that to an air traffic controller.  
Or even a game programmer. 

> You also will not find it in
>analytical geometry books.
>

And in how many such books have you searched?  And don't forget to
check the exercises.

Re: [Algorithms] 3d Lines Intersection

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

Steve Wood  wrote:

>> -----Original Message-----
>> From: Jim Offerman [mailto:j.o...@in...]
>> 
>> - calculate (x, y) intersection (result <x1, y>)
>>
>
>OK, the intersection of the two lines as projected onto the x,y coordinate
>plane.
>
>>
>> - calculate (x, z) intersection (result <x2, z>)
>>
>
>OK, the intersection of the two lines as projected onto the x,z coordinate
>plane.
>
>>
>> - if (x1 == x2) the lines intersect at <x1, y, z>
>>
>
>That sounds right...good work.
>

Unfortunately, there is no logical basis for it and it is quite wrong.

Re: [Algorithms] 3d Lines Intersection

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

Jim Offerman  wrote:

>> Is there a good algo for finding a point of intersection between two *3D
>lines*?
>> The lines is specified by their point (x,y,z) and their direction
>(dx,dy,dz)
>
>When I wrote my first renderer, I used a simple 3D intersection algorithm in
>my (very alternative) projection system:
>
>- calculate (x, y) intersection (result <x1, y>)
>- calculate (x, z) intersection (result <x2, z>)
>- if (x1 == x2) the lines intersect at <x1, y, z>
>
>Of the top of my head I can't say whether this algorithm is 100% correct

It is my sad duty to have to inform you (and I dearly hope that the
news causes no undue emotional stress), that this putative algorithm
is wrong.  

Here is the clearest, simplest to understand counterexample that I
could construct (and there are clearly a bazillion others).

Let line 1 be the x axis, so the line with parametric representation
(s, 0, 0)   

Let line 2 be the line with parametric representation (0, t, t+1).
Thus line 2 lies in the yz plane where it has the implicit equation 
z = y+1.

The projection of line 1 on the xy plane is just the x axis.
The projection of line 2 on the xy plane is the y axis,
The intersection of these projections is (0,0,0).

The projection of line1 on the xz plane is the x axis
The projection of line 2 on the xz plane is the z axis
The intersection of these projections is (0,0,0)

So in your notation  x1 = 0 = x2,  and by your algorithm you claim
that the lines intersect at (0,0,0).  In fact they do not.  Line 2
does not even pass through the point (0,0,0),  In fact these two lines
do not intersect at all, ever, nowhere, no way.  In fact, it is a
problem in freshman analytic geometry to show that the distance of
closest approach of these two lines is sqrt(1/2), but I could as
easily have made it a billion units. 

> (I
>am not a math guy...),

Which is no license to post wrong stuff..

> but, if properly implemented, it will certainly be
>fast and provide at least a reasonable estimation.
>

Bah.

I'm growing weary of playing math cop.  Soon gonna turn in my badge.

Re: [Algorithms] Terrain Organization

[Pai-Hung C. <pa...@ac...>]

Fred wrote:

> Hi,
>
> I'm new to terrain rendering, but at this right moment I was
reading an
> article about ROAM ; looks very interesting and not so hard,
when it's well
> explained as it is on
> http://www.psky.com/prog/terrain.htm
> Have a look !
> It seems that you do NOT have to reconstruct all the stuff for
each frame,
> and it's precisely one of the interests of ROAM.

Actually I've read the original ROAM paper and another one on
Gamasutra, and was helplessly frustrated. :-(  I'll look at the
one you suggested to see if it makes any more sense to me.  Thanks
a lot!

Pai-Hung Chen

Re: [Algorithms] Terrain Organization

[<fa...@no...>]

Hi,

I'm new to terrain rendering, but at this right moment I was reading an
article about ROAM ; looks very interesting and not so hard, when it's well
explained as it is on
http://www.psky.com/prog/terrain.htm
Have a look !
It seems that you do NOT have to reconstruct all the stuff for each frame,
and it's precisely one of the interests of ROAM.

Good luck.

Fred

----- Original Message -----
From: Pai-Hung Chen <pa...@ac...>
To: <gda...@li...>
Sent: Sunday, July 30, 2000 1:51 AM
Subject: [Algorithms] Terrain Organization



> (2) ROAM:
> This is way too complicated for my poor brain...  Tjhe idea of LOD
> is great but I really doubt if ROAM is really worth its extra
> management cost since you have to re-construct everything in each
> frame.  This leads me to the thinking of whether ROAM has other
> better targeted applications than real-time 3D games running on
> PCs.

[Algorithms] Terrain Organization

[Pai-Hung C. <pa...@ac...>]

Hi,

I have a terrain of 5000~6000 triangles (I would like to make it
higher) in my upcoming 3D RPG game (my master thesis).  (I am
using an ELSA Erazor X^2 GeForce card with Direct3D IM.)  I am
always wondering what is the best terrain orgnization algorithm to
organize and render my terrain.  Meanwhile I am planning to split
the terrain up to several _hierarchical_ chunks (with bounding
boxes) and, for each frame, I test each chunk against the current
viewing frustum (VF) to _recursively_ determine if it has to be
submitted to the transformation and rendering pipeline.  If an
_upper-level_ chunk is rejected, there is no need to go down to
the _lower-level_ chunks inside it, which can quickly reject a
huge amount of geometry.  This technique sounds extremely crude,
but, with its relatively low geometry management overhead, I think
it is very efficient, despite its "obviousness."  (Please correct
me if I am wrong.)  I know there are lots of other more
sophisticated/advanced techniques such as BSP and ROAM, but I
doubt if they are really worth their extra huge geometry
management cost in real-time 3D applications.  Here are my
opinions about the BSP and ROAM:  (Please correct me if I am
wrong.)

(1) BSP:
I think a basic BSP can only tell you what is _in front of_ you.
But most of the time you don't really want to draw everything that
is in front of you, but only those that are inside the current VF,
which still requires the VF testing.  Also, since BSP is in
triangle level, there will potentially be more texture stage
changes when rendered.

(2) ROAM:
This is way too complicated for my poor brain...  Tjhe idea of LOD
is great but I really doubt if ROAM is really worth its extra
management cost since you have to re-construct everything in each
frame.  This leads me to the thinking of whether ROAM has other
better targeted applications than real-time 3D games running on
PCs.

Apart from the three techniques mentioned above, are there other
universally agreed better ways to handle richly-textured terrain
in 3D game?  Any comments are highly appreciated!  (Relating to
D3D would be great!)

Thank you,

Pai-Hung Chen

Re: [Algorithms] Scaling Models

[Tom H. <to...@3d...>]

At 04:57 AM 7/29/2000 +0000, you wrote:
>It is a very good question what the API does when the modelview matrix
>contains scaling, uniform or non-uniform.  If it applies the modelview
>matrix (except the translation) to normals when the modelview matrix
>contains non-uniform scaling, it is incorrect.   Does it detect when
>the linear part of the modelview matrix is non-orthogonal, and do the
>right thing?  That would be very expensive.  Or it could just do  the
>transpose(inverse(L)) routine to transform normals in all cases?  That
>would be very wasteful in the majority of cases that the app uses only
>orthogonal linear parts of the model and view transformations.

The transpose(inverse) for normals slipped my mind. Oops. OpenGL does do 
the transpose(inverse) of course.

The transpose(inverse) operation only needs to be performed once when the 
matrix is loaded, and only if the API has state currently enabled that uses 
normals (directional lighting or spherical environment mapping). If these 
states are enabled after the fact, the matrix can be created when the state 
changes. In the case where it needs to do the computation, whether or not 
it checks for linearity depends on the expense of the check I guess. The 
driver writers are usually pretty good at doing minimal amounts of work to 
speed things up as best they can.

Tom

RE: [Algorithms] 3d Lines Intersection

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

> -----Original Message-----
> From: Jim Offerman [mailto:j.o...@in...]
> 
> - calculate (x, y) intersection (result <x1, y>)
>

OK, the intersection of the two lines as projected onto the x,y coordinate
plane.

>
> - calculate (x, z) intersection (result <x2, z>)
>

OK, the intersection of the two lines as projected onto the x,z coordinate
plane.

>
> - if (x1 == x2) the lines intersect at <x1, y, z>
>

That sounds right...good work.

> 
> Of the top of my head I can't say whether this algorithm is 
> 100% correct (I
> am not a math guy...), but, if properly implemented, it will 
> certainly be
> fast and provide at least a reasonable estimation.
> 
> Jim Offerman
> 
> Innovade
> - designing the designer
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] 3d Lines Intersection

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

> -----Original Message-----
> From: Albert_J [mailto:Alb...@te...]
> 
> Is there a good algo for finding a point of intersection 
> between two *3D lines*?
>

Somewhere there might be something already coded.

>
> The lines is specified by their point (Y,y,z) and their 
> direction (dY,dy,dz)
> 

I'm assuming you meant (X,Y,Z) and (DX, DY, DZ).

>
> I've searched the web, but all of them seems to eYplain about 
> 2D lines intersection only.
> 

That's because not many people need it.  You also will not find it in
analytical geometry books.

Here is the math:

PROBLEM:
2 Lines: a and b where they intersect at point (X,Y,Z)

DEFINITIONS:
Line a is: Known point (Xa, Ya, Za) with "normalized" direction numbers
(DXa, DYa, DZa)
with Ta = distance between known point on line and the intersection
Ta = sqr[ (Xa - X)^2 + (Ya - Y)^2 + (Za - Z)^2 ]

Line b is: Known point (Xb, Yb, Zb) with "normalized" direction numbers
(DXb, DYb, DZb)
with Tb = distbnce between known point on line bnd the intersection
Tb = sqr[ (Xb - X)^2 + (Yb - Y)^2 + (Zb - Z)^2 ]

SOLUTION:
If (X,Y,Z) is on both lines then the solution can be:

Tb = (Xa * Dxa * Dza + DXa * Zb - Za - Xb * DZa)/(Dxb * Dza - Dzb)
and
Ta = (Zb + DZb * Tb - Za)/DZa

Plug Ta and Tb into 1, 2, and 3 below (use tolerances to account for
rounding) to see if they intersect.

If they do then plug Ta into:

X = Xa + DXa * Ta, Y = Ya + DYa * Ta, Z = Za + DZa * Ta

PROOF:

1. Xa + DXa * Ta = Xb + DXb * Tb
and
2. Ya + DYa * Ta = Yb + DYb * Tb
and
3. Za + DZa * Ta = Zb + DZb * Tb

That's three equations with 2 unknowns.

My preferred method is to solve for Ta in equation 3:

4. Ta=(Zb + DZb * Tb - Za)/DZa

Then solve for Tb with the first equation:

5. Tb = (Xa + DXa * Ta - Xb)/DXb

Then substitue Ta in 4 into Ta in 5:

6. Tb = [Xa + DXa * (Zb + DZb * Tb - Za)/DZa - Xb]/DXb

Then solve for Tb:

Tb * DXb = Xa + DXa * (Zb + DZb * Tb - Za)/DZa - Xb
Tb * DXb * DZa = Xa * Dxa * Dza + DXa * Zb + DZb * Tb - Za - Xb * DZa
Tb * Dxb * Dza - Tb * DZb = Xa * Dxa * Dza + DXa * Zb - Za - Xb * DZa
Tb (Dxb * Dza - Dzb) = Xa * Dxa * Dza + DXa * Zb - Za - Xb * DZa

7. Tb = (Xa * Dxa * Dza + DXa * Zb - Za - Xb * DZa)/(Dxb * Dza - Dzb)

Plug Tb into equation 1.

Then use Ta and Tb in equation 2...if it's true then they intersect at
(X,Y,Z).

Steve

Re: [Algorithms] 3d Lines Intersection

[Jim O. <j.o...@in...>]

> Is there a good algo for finding a point of intersection between two *3D
lines*?
> The lines is specified by their point (x,y,z) and their direction
(dx,dy,dz)

When I wrote my first renderer, I used a simple 3D intersection algorithm in
my (very alternative) projection system:

- calculate (x, y) intersection (result <x1, y>)
- calculate (x, z) intersection (result <x2, z>)
- if (x1 == x2) the lines intersect at <x1, y, z>

Of the top of my head I can't say whether this algorithm is 100% correct (I
am not a math guy...), but, if properly implemented, it will certainly be
fast and provide at least a reasonable estimation.

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] 3d Lines Intersection

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

Albert_J  wrote:

>Hi,
>
>Is there a good algo for finding a point of intersection between two *3D lines*?
>The lines is specified by their point (x,y,z) and their direction (dx,dy,dz)
>
>I've searched the web, but all of them seems to explain about 2D lines intersection only.

The problem is that in 3D almost all pairs of lines do not intersect
(as opposed to 2D where every pair of non parallel lines intersects).

Even if the logic of the construction of the two lines is such that
you know they must intersect, any computational intersection test will
be subject to rounding errors which, in all probability, will yield a
negative result.

The best you can do computationally  is to find the two points, one on
each line, which are nearest.  You may or may not want to call the
lines "intersecting" depending on the distance between these two
points and your error tolerance.

So if your two lines are specified by  vectors X1, DX1, X2, DX2,
namely
          X1= (x1, y1, z1), 
          DX1 = (dx1, dy1, dz1) 
         X2 = (x2, y2, z2), 
        DX2 = (dx2, dy2, dz2)

write down the vector parametric representations of the general point
one each of the two lines

       X1 + s DX1
       X2  + t DX2.

where s and t are INDEPENDENT real parameters.

You want to find the values of s and t that make the distance between
these two points as small as possible.  Write down the expression for
the distance between the two points, or rather the square of the
distance ( more convenient to avoid square roots), in terms of these
two parameters.   Using elementary vector geometry this squared
distance is 

  distance squared = 
 | (X1 + sDX1) - (X2 +  tDX2) |^2
 = |(X1 - X2) + s DX1 - t DX2)|^2
 = ((X1 - X2) + s DX1 - t DX2) . ( (X1 - X2) + s DX1 - t DX2))
where . means dot product.

Apply the elementary algebraic properties of dot product and collect
terms that are like in s and t and you get
 s^2 DX1.DX1 + t^2 DX2.DX2 - 2st DX1.DX2 + 
 s DX1. (X1 - X2) -  t DX2. (X1 - X2) + (X1 - X2).(X1 - X2)

This distance-squared function is of the form
as^2 + bt^2 + c st + ds + et + f
where a, b, c, d, e, f are known scalars computed from your line data
and s and t are independent variables.

This is a general quadratic function of two independent variables s
and t.  We seek to find the values of s and t that make it as small as
possible.  The best tool for this minization problem is the elementary
differential calculus of two variables, which tells us that the
minimum value occurs where the first partial derivatives with respect
to each of the variables is zero.  So differentiating first with
respect to s and then with respect to t gives two equations
 
	2as + ct + d = 0
                2bt  + cs + e = 0

This is a system of two linear equations in two unknowns s and t,
which you know how to solve from high school algebra.  It will have a
unique solution if the lines are not parallel.

Plug the resulting values of s and t back into the distance-squared
formula and see if that is close enough to zero so that you want to
call it an intersection.  In any case, if you plug the values of s and
t back into the parametric expressions for the two lines you get the
two closest points, one on each line.

P.S. You can avoid calculus and still find the two nearest points by
using the fact from Euclidean solid geometry that the closest two
points are the two feet of the mutual perpendicular between the two
lines, the mutual perpendicular being unique if the lines are not
parallel.  Write down the expression for the vector joining a general
point of each line, as a function of s and t, and write down the
equations that say that the dot product of this vector with each of
DX1 and DX2 is zero (this is the mutual perpendicularity condition). 
 
i.e. 	DX1. ((X1 - X2) + s DX1 + t DX2) = 0
                DX2. ((X1 - X2) + s DX1 + t DX2)) = 0

 The resulting two equations is a 2x2 linear system equivalent to the
one above.  The reason I chose the calculus approach is because I
didn't just want to find the two closest points, but also to test for
(near) intersection, which means I would have had to know the distance
function anyway, so I chose to start with the distance function, and
followed my nose from there.

RE: [Algorithms] 3d Lines Intersection

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

Albert_J writes:
>
>Is there a good algo for finding a point of intersection 
>between two *3D lines*?
>The lines is specified by their point (x,y,z) and their 
>direction (dx,dy,dz)

You can find source for this and other common 
Intersection routines in PLib.sg.sgIsect.cxx

http://plib.sourceforge.net

Norman VIne

Re: [Algorithms] 3d Lines Intersection

[Sam K. <sa...@ip...>]

Albert,

It seems to me the chances of two 3d lines intersecting in space is
*enormously slim* exept in a few obvious situations, like two lines crossing
each other from the corners of a cube etc.

It might help if you outlined your reasons for wanting to do this.

sam



>Hi,
>
>Is there a good algo for finding a point of intersection between two *3D
lines*?
>The lines is specified by their point (x,y,z) and their direction
(dx,dy,dz)
>
>I've searched the web, but all of them seems to explain about 2D lines
intersection only.
>
>Thanks in advance.
>Albert J
>
>
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

[Algorithms] Scorch marks on arbitrary geometry (was: Bullets on walls)

[Noel L. <ll...@ho...>]

So, after the interesting thread about putting bullets on
walls, I was wondering what people usually do to put
scorch marks (or any other decals) on arbitrary geometry.

It seems that most methods work well for regular or
"known" geometry: height fields, quads, etc.

The two ways I could think of so far are:
- Use projective textures. I haven't used this before. What kind
   of performance hit does it involve?

- Try to "face-map" the geometry we want to scorch to use
   texture coordinates from 0.0 to 1.0 in a regular way, and then
   draw it again with the scorched texture. This is particularly
   tricky if the geometry isn't face-mapped to start with, and especially
   if we want to do it without modifying the geometry at all (would need
   to find a texture transform that maps the original uvs into what we
   need).

How are people doing that today in games? Any recommendations
or ideas would be most welcome.
Cheers.


--Noel
ll...@ho...

Re: [Algorithms] Scaling Models

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

I wrote:

>....    Let P be a particular plane through the organ and ... 

A frightening demonstration of the folly of relying on spell checkers,
rather than careful proof reading, in the wee small hours.

[Algorithms] 3d Lines Intersection

[Albert_J <Alb...@te...>]

Hi,

Is there a good algo for finding a point of intersection between two *3D lines*?
The lines is specified by their point (x,y,z) and their direction (dx,dy,dz)

I've searched the web, but all of them seems to explain about 2D lines intersection only.

Thanks in advance.
Albert J

Re: [Algorithms] Scaling Models

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

Peter Warden  wrote:


>Just out of interest, one thing I did a while back when I needed to treat
>both normals and vertex positions uniformly when applying an animation
>matrix to them was set the W component of the normals to 0, whilst leaving
>the W component of the positions at 1. This worked because the animation
>matrix never contained a scale, and I just wanted to not translate the
>normals. Is this a well-known technique that I just haven't run across
>before, and is there any theoretical basis for it?
>

This is  the correct way to treat the w components WHETHER OR NOT
the transformation contains a scale. You never need to "translate
normals" because the translation of a vector (as opposed to the
translation of a point) is always the vector itself.   It is inherent
in the meaning of "vector".  See my response to the original post of
this thread.

Re: [Algorithms] Scaling Models

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

John White  wrote:

>If you set a scaling matrix as part of the transformation pipeline what 
>happens to the normals?

The transformations we are talking about are all invertible affine
mappings  of 3-space. (We are not considering projection mappings in
this discussion).  Affine mappings are mappings that can be realized
as a linear transformation  (leaving some point fixed, which we call
the origin) followed by a translation.  The linear part is represented
by a system of 3 equations in the 3 coordinate variables, i.e by a 3x3
matrix, in a coordinate system whose origin is at the fixed point.
The translation is represented by a vector.  Computer graphicists have
formed the unfortunate (I think) habit of combining the 3x3 matrix and
the 3 components of the translation vector into a 4x4 matrix,
containing a row or column (0,0,0,1) which carries no useful
information.

The affine mappings of the transformation pipeline are applied to
geometric models consisting of sets of points.  In graphics we use
mostly models that are made of planar polygons defined by special
points called vertices.  One of the nice properties of affine
transformations is that they map planes to planes, so planar polygons
to planar polygons, one of the reasons we focus on affine
transformations.

Now one of the two important defining parameters of any plane is its
normal vector.  The general question at the root of your specific
question about scale mappings is:  Given the matrix of the affine
mapping that is applied to the vertices of a domain polygons, how can
I get the normal vector of the transformed polygon from the normal
vector of the domain polygon?  I will give the answer to the general
question and then see how it applies in the absence of change of scale
as well as in the presence of change of scale.  

First, it should be clear that the translation part of the affine
mapping, i.e. the last row or column of the 4x4 matrix, is irrelevant
to mapping the normals.  This is because the very concept of "vector"
involves independence of position,  You can translate a vector
anywhere in the space, keeping it always parallel to its original
direction and of constant length, and it is considered the same
vector. At every point, a plane has the same normal vector as at every
other point. Translation has no effect on normal vectors, because
translation maps a plane to a parallel plane, which has the same
normal vector.

Thus when considering how to find the normal vector of the transformed
plane from the normal vector of the original plane, we only have to be
concerned with the linear part of the affine transformation, the part
that is represented by the upper left 3x3 matrix, call it L.

Let us make no assumptions about L except that it is invertible (as
are all the transformations of the graphics pipeline, up to
projection).    Let P be a particular plane through the organ and let
n be a unit normal vector to P.  Then it can be shown that the unit
normal vector to the transformed plane LP must be the normalization of

	transpose(inverse(L))n
(where I am using the OperatorOnLeft convention). You can find a
demonstration of this fact in FvDFH Sec 5.7, so I won't repeat it
here.   So in general for ANY affine transformation with L as the 3x3
matrix of its linear part, to get the unit normal of the transform of
a plane, you multiple the unit normal of the plane by
transpose(inverse(L)) and then renormalize.  For some applications,
such as back face culling, it is not important that the normal have
unit length, so you can leave off the renormalization.  I think that
most APIs give wrong lighting if you supply them with non-unit normal
vectors.

Note first that if L is invertible, then so is transpose(L) and 
inverse(transpose(L)) = transpose(inverse(L)) which you can show by
elementary linear algebra.

Now suppose that L is a rotation (or more generally an orthogonal
transformation). Then, as we all know inverse(L) = transpose(L), so 
transpose(inverse(L)) =
 transpose(transpose(L)) = 
inverse(inverse(L)) = L.

That is, for rotations, or for affine transformations consisting of a
rotation followed by a translation  (i.e., most of the affine
transformation we use in graphics), the correct operator to use on
normal vectors is just L.  And indeed if L is orthogonal then it can
be shown (again elementary linear algebra) that it preserves vector
lengths, so there is no need to renormalize Ln.  If L is an orthogonal
transformation that is not a rotation, i.e. if L is a rotation
combined with a reflection in a plane, then you have to watch out
because Ln might point to the "wrong side" of the image plane,

Now suppose that L is a uniform scaling by scale factor s.  This means
that in any coordinate system, L is diagonal with every diagonal
element = s and the off diagonal elements all 0, in other words 
L = sI where I is the identity, transpose(L) = sI = L and 
inverse(L) = (1/s)I.  (Check it out).
So transpose(inverse(L)) = (1/s)I.  When you multiply a vector n by
this you get (1/s)n, which is really easy to renormalize, just
multiply it by s, or better yet, recognize from the start that the
transformation has no effect whatever on the unit normal of any plane,
the unit normals are all unchanged.  I'm not sure what any particular
API does in this case, but this tells you how to do the math.

Now suppose that L is a non-uniform scaling.  Then there is some
coordinate system with respect to which  L has three diagonal elements
sx, sy, sz and the off diagonal elements are all zero.  Call this
matrix diag(sx, sy, sz).   Notice that unlike the orthogonal
transformations and the uniform scaling, a non-uniform scaling DOES
NOT PRESERVE ANGLES, so it does not preserve perpendicularity of a
line to a plane.   Further  inverse(L) = (1/sx., 1/sy, 1/sz).
Further transpose(L) = L and transpose(inverse(L)) = inverse(L).   So
the correct the way to transform the normal vector is  to multiply it
by the matrix inverse(L) = diag(1/sx, 1/sy, 1/sz) and renormalize
Notice that this vector diag(1/sx, 1/sy, 1/sz) n = (nx/sx, ny/sy,
nz/sz) is no longer parallel to n, so there is no shortcut, you
actually have to do the normalization if you want accurate unit normal
vectors to the transformed surface.  Again, I am not sure what any
particular API does here, but I have just given you the true math.

Note in particular for the non-uniform scaling it is NOT CORRECT to
apply the matrix L to the normals then renormalize (as I think someone
else suggests in this thread).  You will get a unit vector that way,
but it will no longer be perpendicular to the surface, so it won't
even be useful for back face culling, let alone accurate lighting.

I could extend this to more general transformations, say adding shear,
but I won't because it starts to get messy, but in any case the true
correct accurate formula to apply in any case is to multiply the
normals by the matrix  transpose(inverse(L)) and renormalize.

For a general linear transformation composed of some of these
elementary transformations, rotations, uniform or nonuniform scalings,
shears, etc., you use the general identities that
transpose(AB) = transpose(B) transpose(A) and
inverse(AB) = inverse(B) inverse(A), so that
transpose(inverse(AB)) = transpose(inverse(B)inverse(A)) =
transpose(inverse(A))transpose(inverse(B)).

So for a general concatenation of transformations ABC...Z
the correct way to transform the normals to multiply them by 
transpose(inverse(A))....transpose(inverse(Z) and renormalize.
The above discussion helps you simplify the product for special cases.



  

Re: [Algorithms] Scaling Models

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

Tom Hubina  wrote:

>
>In GL the normals are scaled and rotated by the modelview matrix 
>(homogenous matrix stuff ... translations are ignored). GL allows you to 
>normalize the transformed normals with:
>

It is a very good question what the API does when the modelview matrix
contains scaling, uniform or non-uniform.  If it applies the modelview
matrix (except the translation) to normals when the modelview matrix
contains non-uniform scaling, it is incorrect.   Does it detect when
the linear part of the modelview matrix is non-orthogonal, and do the
right thing?  That would be very expensive.  Or it could just do  the
transpose(inverse(L)) routine to transform normals in all cases?  That
would be very wasteful in the majority of cases that the app uses only
orthogonal linear parts of the model and view transformations.