gdalgorithms-list

Re: [Algorithms] Tangential Curvature of terrain

[Klaus H. <k_h...@os...>]

Thather, and Ron... Thanks a lot for your replies :)

From: Ron Levine <ro...@do...>
> Only if you can  better explain what is meant by "tangential
> curvature", not a standard mathematical term. It might be a standard
> GIS term, but  I could not find a real definition of the term on the
> uiuc GIS site that you cite.  The image you cite, at first sight,
> suggests to me a couple of possible definitions, but on closer
> examination of its coloring I can eliminate one, and am left with one
> guess:

I knew you would say that, and I cannot blame you :) It took me almost half
a year to find the technical term for what I'm trying to do. Now that I know
that it's called tangential curvature (which is an obsolete name for
meridional curvature) I'm at least able to find some information on the
net... but not too much.

A hopefully good definition of tangential curvature (as used in GIS) can be
found here:
http://www.orbtek.com/glossary/definitions/tangentialcurvature.html

I'm now trying to give you a brief overview of how those GIS people compute
the tangential curvature, and after that I'll briefly explain why I'd like
to implement this.

[1] Tangential curvature

Unfortunately, I'm not a mathematician, and I can only *try* to summarize
what a certain GIS paper says. Basically, I'll just copy some parts of the
paper. I hope that it's enough for you to understand.

"
Surface geometry can be analyzed efficiently when the surface is
interpolated with a bivariate function z = f(x, y), that is continuous up to
second order derivatives and when parameters characterizing surface
geomoetry (topographic parameters) are expressed VIA derivates of this
function. This approach is demonstrated on the computation of basic
topographic parameters: slope, aspect, profile curvature, plan curvature,
tangential curvature, and on the computation of flow path length.
Before deriving mathematical expressions for these parameters, using the
basic principles of differential geometry, the following simplifying
notations are introduced:

fx = Dz/Dx
fy = Dz/Dy
fxx = (D^2)z/Dx^2
fyy = (D^2)z/Dy^2
fxy = (D^2)z/(DxDy)

and

p = (f^2)x + (f^2)y
q = p + 1
"
(Note, that I'm using a capital 'D' here, where the paper uses the Greek
letter delta). Unfortunately, we used a different notation in school. So I
can only guess, that fx and fy are first derivatives, and fxx, fyy, fxy are
second derivatives. But we never differentiated bivariate functions (which
is my biggest problem).

"
For the study of flow divergence/convergence, it is more appropriate to
introduce a curvature measured in the normal plane in the direction
perpendicular to gradient. This curvature will be called here a tangential
curvature because the direction perpendicular to gradient is, in fact, the
direction of tangent to contour at a given point. Equations for these
curvatures can be derived using the general equation for curvature K of a
plane section through a point on a surface:

K = (fxx * cos^2(B1) + 2*fxy*cos(B1)*cos(B2) + fyy*cos^2(B2)) / (sqrt(q) *
cos L)

where L (lamdba) is the angle between the normal to the surface at a given
point and the section plane; B1 (beta 1), B2 (beta 2) are angles between the
tangent of the given normal section at a point and axes x, y, respectively.
"

Whatever that means... And then, a bit later in the text, they give the
formula for tangential curvature:

"The equation for tangential curvature Kt at a given point is derived as the
curvature of normal plane section in a direction perpendicular to gradient
(direction of tangent to the contour line) after setting

cos L = 1
cos B1 = fy / sqrt(p)
cos B2 = -fx / sqrt(p)

and

Kt = (fxx*fy^2 - 2*fxy*fx*fy + fyy*fx^2) / (p * sqrt(q))
"

I only understand fractions of the above, and that's why I'm not able to
implement it.

[2] What I want to do...

Assume that you wanted to synthesize a texture for a height field. A simple
approach is to make each texel's color depend on the elevation E of the
corresponding data point P in the height field. For example, you could say
"Use snow, if the elevation E falls above a lower elevation limit H (say
1000 meters). If E <= H, then just use rock.".

If I now knew the tangantial curvature, T, (as a scalar) at the data point
P, then I could modify the elevation H in the following fashion:
H' = H - T * D,

where D is some scaling factor that increases/decreses the effect (negative
T means convex up, and positive T means concave down). My new classification
would now become: "Use snow, if the elevation E falls above a lower
elevation limit H' (say 1000 meters). If E <= H', then just use rock.".

Using such an approach, I can make the flow of the snow care about the shape
of the terrain. For example, I can make tongues of snow that flow from the
peak of a mountain, through concave down areas, all the way into the valley.
At the same time, the rock 'flows' from the valley, over convex up areas,
towards the peak.

No need to say, that this produces very realistic effects. In Questar
Productions' World Construction Set 2, for example, they call this the
'relative elevation effect'.


Also, thanks for the other pointers you gave. I'll not comment on them now,
because I'd like think about them, before I say something stupid :)

Thanks,
Niki

[Algorithms] Keyframing, bones etc Free to use?

[David P. <eti...@ho...>]

Is Keyframing, bones, or skinning patented in any way?


thanks
dave

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

RE: [Algorithms] portal engines in outdoor environments

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

You can find it perfectly of course, but if you can't be bothered, or you're
doing lots of these (a common case), then a good conservative approximation
of the real size is to find the radius of a circle that is r units closer to
the viewer than S, i.e. just move P closer by r. It's virtually the same
thing for sensible-distance-away spheres, it's only as the sphere gets
really very close that it starts to give poor results, and this is usually
acceptable in things like hierachial culling.

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

> -----Original Message-----
> From: Jamie Fowlston [mailto:j.f...@re...]
> Sent: 21 August 2000 12:05
> To: gda...@li...
> Subject: Re: [Algorithms] portal engines in outdoor environments
> 
> 
> > Spheres are particularly nice because the sphere radius is 
> the same as the
> > circles radius after projection
> 
> Careful. There's a common misconception here (which you may 
> or may not have made
> :).
> 
> Let the sphere have radius r.
> Let S be the centre of the sphere.
> Let V be some vector perpendicular to the view vector of length r.
> 
> Let P = S + V
> 
> Some people claim that projecting point P gives you a point 
> on the edge of the
> circle which is the rasterisation of the sphere. This is not true.
> 
> Demonstration that this is so (in 2D, so hopefully it's clearer :) :
> 
> Take a circle with centre C.
> Place an arbitrary point P outside the circle. The closer it 
> is to the circle,
> the clearer my point (unintentional... sorry:) should be.
> Let the 2 tangents to the circle passing through P be T1, T2.
> Let P1 be the point of intersection between T1 and C. Define 
> P2 similarly.
> 
> It should be clear that the projections of P1 and P2 are 
> equivalent to points on
> the edge of the rasterisation.
> But (P - C) is not perpendicular to (T1 - C) or (T2 - C).
> 
> Although as | P - C | approaches infinity, they approach 
> perpendicular. If you
> can be sure you'll never be close enough to appreciate the 
> error, then you'll be
> fine :)
> 
> 
> Back to the sphere: this means that the true rasterisation of 
> the sphere is
> larger than the circle calculated by projecting P.
> 
> I'll expand more if anybody needs it... or gives a monkey's :)
> 
> Jamie
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Rotation about arbitrary axis

[Thatcher U. <tu...@tu...>]

From: Pierre Terdiman <p.t...@wa...>
>
> Since I needed a piece of code to do that I searched the web and found:
> http://www.iuk.tu-harburg.de/hypgraph/modeling/mod_tran/3drota.htm
>
> I used the final matrix at the bottom of the page, but it seems to fail
when
> the arbitrary axis actually is the Z axis. The third column gets erased
> where it should at least contain a 1. This is obvious when looking at the
> provided matrix, since the third column of the third row depends on the
> rotation angle - and of course if the input axis already is the Z axis, it
> shouldn't.
>
> Now, it sounds normal regarding the underlying method (mapping the
rotation
> axis to Z, etc). But I wonder whether there's an easy way to perform a
real
> arbitrary rotation about any arbitrary axis without using different code
> paths according to the input axis.
>
> I think it can probably be done by introducing quaternions or better,
> angle-axis, in the story. But err.... maybe there's something simpler.

Here's what I use.  I'm sure it could be streamlined by expanded out the
quaternion stuff and simplifying.

class quaternion {
public:
 quaternion(const quaternion& q) : S(q.S), V(q.V) {}
 quaternion(float s, const vec3& v) : S(s), V(v) {}
 // [...]
 quaternion operator*(const quaternion& q) const;
 // [...]
 void ApplyRotation(vec3* result, const vec3& v);
private:
 float S;
 vec3 V;
};


vec3 Rotate(float Angle, const vec3& Axis, const vec3& Point)
// Rotates the given point through the given angle (in radians) about the
given
// axis.
{
 quaternion q(cos(Angle/2), Axis * sin(Angle/2));

 vec3 result;
 q.ApplyRotation(&result, Point);

 return result;
}

quaternion quaternion::operator*(const quaternion& q) const
// Multiplication of two quaternions.  Returns a new quaternion
// result.
{
 return quaternion(S * q.S - V * q.V, q.V * S + V * q.S + V.cross(q.V));
}


void quaternion::ApplyRotation(vec3* result, const vec3& v)
// Rotates the given vec3 v by the rotation represented by this quaternion.
// Stores the result in the given result vec3.
{
 quaternion q(*this * quaternion(0, v) * quaternion(S, -V)); // There's
definitely a shortcut here.  Deal with later.

 *result = q.V;
}


--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] LightMaps

[Joscha M. <jo...@jo...>]

One solution is to use texture coords that are one pixel smaller than the
texture.
Example:
If you have a 256x256 texture you have to set the texture coords to
xmin=0,0039 ymin=0,0039 xmax=0,9960 ymax=0,9960
This works fine for me. Now you have to make your textures in a way that
they overlap by one pixel.

Yoshi

----- Original Message -----
From: "Maik Gerth" <mai...@gm...>
To: <gda...@li...>
Sent: Monday, August 21, 2000 7:16 PM
Subject: AW: [Algorithms] LightMaps


Hi ... i think i found a solution ... but i didnt implement it yet ...

you got to draw a border around the lightmaps ... with the right
lumel-values ... so the filtering uses the right colors even at the edges of
the triangles

bye

Maik
-----Ursprüngliche Nachricht-----
Von: gda...@li...
[mailto:gda...@li...]Im Auftrag von
Jaakko Westerholm
Gesendet: Montag, 21. August 2000 17:45
An: gda...@li...
Betreff: Re: [Algorithms] LightMaps



> But for the moment I have some difficulties with the bilinear >filtering,
which creates those nasty lines between triangles.

I have the same problem. Is there any solution to this?

--Jaakko--

Get your Free E-mail at http://bosti.zzn.com
___________________________________________________________________
Hae oma Web-perusteinen sähköposti palvelusi http://www.zzn.com:sta

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


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

Re: [Algorithms] Rotation about arbitrary axis

[Pierre T. <p.t...@wa...>]

Thanks everyone, I followed Paul Bourke's steps there and now it works:
http://www.swin.edu.au/astronomy/pbourke/geometry/rotate/

I suppose the matrix in my former link was wrong.


> Absolutely.  You can do it entirely in terms of elementary vector
geometry,
> which I certainly regard as simpler, or at least more elemenary than
> quaternions.

Agreed !


>         A cross (B cross C) = (A dot C)B - (A dot B)C
> (correct up to a sign that I can never remember).

Yup, we call that one the "double produit vectoriel" :)

Thanks Ron, this is always a pleasure to read from someone who enjoys what
he writes about.

P.

Re: [Algorithms] visualizing frustum planes?

[Michael S. H. <mic...@ud...>]

Duh.  This is precisely the reason I like working on teams where more than one person is familiar with a given system.  Sometimes having someone state the obvious is a good kick in the seat.

It hadn't even occurred to me to use an artificial model matrix and draw the simulated frustum planes, in order to check (and help visualize) the camera math

At 07:10 PM 8/21/00, you wrote:
>Hey,
>
>Here's a piece of code which will render the camera frustum, which I find to
>be useful when hunting camera problems. It works best when viewed from a
>second camera though (since the frustum is mostly clipped by the very
>frustum planes it is meant to visualize), with the AABB culling code (or
>whatever you may end up using it for) hardwired to the first camera - only,
>the second camera should just render everything, or only rely on culling
>code of which you're certain that it works.
>
>----8<----
>  float     ax, ay, bx, by, fx, fy;
>  static Vertex verts[8];
>  static ushort indices[24] = {
>   0,1, 1,2, 2,3, 3,0,
>   4,5, 5,6, 6,7, 7,4,
>   0,4, 1,5, 2,6, 3,7
>  };
>
>   // Calculate fov/2 angles in x and y direction.
>  ax = mFov / 2;
>  ay = ax * ((float) mViewport.height / (float) mViewport.width);
>   // Calculate x/y coordinates of the front plane.
>  fx = mFront * (float) tan(ax);
>  fy = mFront * (float) tan(ay);
>   // Calculate x/y coordinates of the back plane.
>  bx = mBack * (float) tan(ax);
>  by = mBack * (float) tan(ay);
>   // Setup frustum verts.
>  verts[0].loc.set(-fx, +fy, mFront);
>  verts[1].loc.set(+fx, +fy, mFront);
>  verts[2].loc.set(+fx, -fy, mFront);
>  verts[3].loc.set(-fx, -fy, mFront);
>  verts[4].loc.set(-bx, +by, mBack);
>  verts[5].loc.set(+bx, +by, mBack);
>  verts[6].loc.set(+bx, -by, mBack);
>  verts[7].loc.set(-bx, -by, mBack);
>  for (short i = 0; i < 8; i++)
>   verts[i].color = Color3(0.8f, 0.8f, 0.8f);
>   // Render frustum.
>  GfxDevice->SetTransform(eTransformWorld, mMatrix);
>  GfxDevice->Draw(GfxDevice::PrimLineList, verts, 8, indices, 24);
>----8<----
>
>If you have any questions about the specifics of the above code, mail me
>offline.
>
>HTH
>
>Jim Offerman
>
>Innovade
>- designing the designer
>----- Original Message -----
>From: "Michael S. Harrison" <mic...@ud...>
>To: <gda...@li...>
>Sent: Monday, August 21, 2000 9:18 AM
>Subject: [Algorithms] visualizing frustum planes?
>
>
>> I'm attempting to implement the AABB culling code talked about here some
>time ago and I'm running into a general problem in visualizing the frustum
>planes used to cull objects based on their AABB's
>>
>> I'm using both Klaus Hartmann's AABBCull sample and the Viewcull sample
>included with the OpenGL FAQ.
>>
>> While the code generally works, I'm having some difficulty visualizing the
>relationship between the plane vector and the "distance" value stored with
>it, which I'm sure is the reason I can't quite figure out why the code
>generates intersection results when it should generate a full cull.
>>
>> As you might guess, I'm fairly new to the world of 3d projection and I'm
>still wrapping my mind around all the transformations that take an object
>from "world" space to screen space.
>>
>> Can anyone suggest a reference or way to visualize exactly what's going on
>with the plane extraction and how the vectors relate back to the AABB?
>>
>>
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list 

RE: [Algorithms] Rotation about arbitrary axis

[Matthew D. <MD...@ac...>]

Hi Pierre,

I wrote some code for just that purpose not so long ago:

	inline void matrix::SetRotation (const vector &axis, f32 radians)
	{
		f32 s, c, t;
		Maths_SinCos(radians,s,c);			// Calculate
sin and cosine
		t = 1 - c;

		assert(axis.IsValid());

		f32 txy = t*(axis.x * axis.y);
		f32 tyz = t*(axis.y * axis.z);
		f32 txz = t*(axis.x * axis.z);

		f32 xs = axis.x * s;
		f32 ys = axis.y * s;
		f32 zs = axis.z * s;

		_14 = _24 = _34 = _41 = _42 = _43 = 0.0f;
		_44 = 1.0f;

		_11 = t*(axis.x*axis.x) + c;
		_22 = t*(axis.y*axis.y) + c;
		_33 = t*(axis.z*axis.z) + c;

		_12 = txy + zs;
		_13 = txz - ys;
		_21 = txy - zs;
		_23 = tyz + xs;
		_31 = txz + ys;
		_32 = tyz - xs;
	}

I'm sure you can adapt that code.  For 4x4 matrices just extend it:

A B C     A B C 0
D E F     D E F 0
G H I     G H I 0
          0 0 0 1

Best regards,
Matt.
 

> -----Original Message-----
> From: Pierre Terdiman [mailto:p.t...@wa...]
> Sent: Monday, August 21, 2000 17:58
> To: gda...@li...
> Subject: [Algorithms] Rotation about arbitrary axis
> 
> 
> Hi,
> 
> Since I needed a piece of code to do that I searched the web 
> and found:
> http://www.iuk.tu-harburg.de/hypgraph/modeling/mod_tran/3drota.htm
> 
> I used the final matrix at the bottom of the page, but it 
> seems to fail when
> the arbitrary axis actually is the Z axis. The third column 
> gets erased
> where it should at least contain a 1. This is obvious when 
> looking at the
> provided matrix, since the third column of the third row 
> depends on the
> rotation angle - and of course if the input axis already is 
> the Z axis, it
> shouldn't.
> 
> Now, it sounds normal regarding the underlying method 
> (mapping the rotation
> axis to Z, etc). But I wonder whether there's an easy way to 
> perform a real
> arbitrary rotation about any arbitrary axis without using 
> different code
> paths according to the input axis.
> 
> I think it can probably be done by introducing quaternions or better,
> angle-axis, in the story. But err.... maybe there's something simpler.
> 
> Pierre
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Rotation about arbitrary axis

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

Pierre Terdiman wrote
>
> Since I needed a piece of code to do that I searched the web and found:
>......
> I used the final matrix at the bottom of the page, but it seems to fail
when
> the arbitrary axis actually is the Z axis. The third column gets erased
> where it should at least contain a 1. This is obvious when looking at the
> provided matrix, since the third column of the third row depends on the
> rotation angle - and of course if the input axis already is the Z axis, it
> shouldn't.
>

I haven't checked this out, but it must be wrong because it is perfectly
possible to write down the matrix in a form such that it applies to any
ARBITRARY axis, including the z-axis.

> Now, it sounds normal regarding the underlying method (mapping the
rotation
> axis to Z, etc). But I wonder whether there's an easy way to perform a
real
> arbitrary rotation about any arbitrary axis without using different code
> paths according to the input axis.
>
> I think it can probably be done by introducing quaternions or better,
> angle-axis, in the story. But err.... maybe there's something simpler.

Absolutely.  You can do it entirely in terms of elementary vector geometry,
which I certainly regard as simpler, or at least more elemenary than
quaternions.

It is an instructive exercise in elementary vector geometry to derive the
following formula.  Let A be a unit vector that points along the axis of
rotation, let ang be the angle of rotation, and let V be any vector.  The
result of rotating V through angle ang about axis A is the vector

V' = cos(ang)V + (1-cos(ang)) (A dot V) A + sin(ang) A cross V

Notice that this is a vector formula.  You can apply it directly to rotate
any given
vector V.  Or if you want the matrix of this rotation with respect to any
given
coordinate system, simply express A in that coordinate system and
successively
substitute (1, 0, 0), (0, 1, 0), (0, 0,1) for V, and the nine elements of
the three values
you get for V', naturally, form the elements of the 3x3 rotation matrix.
Whether you
arrange these three V' vectors in rows or columns depends on which matrix
convention you are using.

Notice how esthetically satisfying is this vector formula:  it expresses the
result of the rotation in terms of V, A, and the simplest vector that can be
constructed from V and A that is (in  general) linearly independent of V and
A, namely A cross V.  It uses only the elementary vector operations of
vector addition, multiplication by a scalar, dot and cross product, and it
uses all of them.

As for the derivation of this vector formula for rotation about an arbitrary
axis,
start by resolving V into components parallel and perpendicular to A.
Clearly, rotation preserves vector sums so V' must be the sum of the images
of the components under the rotation.   The rotation of the perpendicular
component is rotation in a plane, which you know how to do from elementary
analytic gometry, You need to put all that together with some trig
identities, and, (this is the trickiest part of the derivation), the
following identity from elementary vector analysis, which you will find in
your calculus book
        A cross (B cross C) = (A dot C)B - (A dot B)C
(correct up to a sign that I can never remember).

(You can find the derivation of the vector rotation spelled out in
Goldstein's "Classical Mechanics".  Also pay attention that there is a sign
ambiguity of the sense of A coupled with the sign of ang and also the
handedness of your cross product rule.  The same ambiguity exists, of
course, in any quaternion formulation).

Re: [Algorithms] Rotation about arbitrary axis

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

Quaternions are the baby :)

Unit quaternions can be very simply mapped to / from an axis and angle.

If your axis of rotation is ( x , y , z ) and your angle is r, an associated
quaternion is

{ x * sin ( r / 2 ) , y * sin ( r / 2 ) , z * sin ( r / 2 ) , cos ( r / 2 ) }

There are 2 quaternions for any given axis and angle, because rotating around
the negative vector by the negative angle is equivalent to the original
rotation.

But I don't have any code for the stuff I can give away, I'm afraid :)

I'm sure there are plenty of references to appropriate stuff in the archives of
the list... if they're working. :)

Jamie


Pierre Terdiman wrote:

> Hi,
>
> Since I needed a piece of code to do that I searched the web and found:
> http://www.iuk.tu-harburg.de/hypgraph/modeling/mod_tran/3drota.htm
>
> I used the final matrix at the bottom of the page, but it seems to fail when
> the arbitrary axis actually is the Z axis. The third column gets erased
> where it should at least contain a 1. This is obvious when looking at the
> provided matrix, since the third column of the third row depends on the
> rotation angle - and of course if the input axis already is the Z axis, it
> shouldn't.
>
> Now, it sounds normal regarding the underlying method (mapping the rotation
> axis to Z, etc). But I wonder whether there's an easy way to perform a real
> arbitrary rotation about any arbitrary axis without using different code
> paths according to the input axis.
>
> I think it can probably be done by introducing quaternions or better,
> angle-axis, in the story. But err.... maybe there's something simpler.
>
> Pierre
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] visualizing frustum planes?

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

Hey,

Here's a piece of code which will render the camera frustum, which I find to
be useful when hunting camera problems. It works best when viewed from a
second camera though (since the frustum is mostly clipped by the very
frustum planes it is meant to visualize), with the AABB culling code (or
whatever you may end up using it for) hardwired to the first camera - only,
the second camera should just render everything, or only rely on culling
code of which you're certain that it works.

----8<----
  float     ax, ay, bx, by, fx, fy;
  static Vertex verts[8];
  static ushort indices[24] = {
   0,1, 1,2, 2,3, 3,0,
   4,5, 5,6, 6,7, 7,4,
   0,4, 1,5, 2,6, 3,7
  };

   // Calculate fov/2 angles in x and y direction.
  ax = mFov / 2;
  ay = ax * ((float) mViewport.height / (float) mViewport.width);
   // Calculate x/y coordinates of the front plane.
  fx = mFront * (float) tan(ax);
  fy = mFront * (float) tan(ay);
   // Calculate x/y coordinates of the back plane.
  bx = mBack * (float) tan(ax);
  by = mBack * (float) tan(ay);
   // Setup frustum verts.
  verts[0].loc.set(-fx, +fy, mFront);
  verts[1].loc.set(+fx, +fy, mFront);
  verts[2].loc.set(+fx, -fy, mFront);
  verts[3].loc.set(-fx, -fy, mFront);
  verts[4].loc.set(-bx, +by, mBack);
  verts[5].loc.set(+bx, +by, mBack);
  verts[6].loc.set(+bx, -by, mBack);
  verts[7].loc.set(-bx, -by, mBack);
  for (short i = 0; i < 8; i++)
   verts[i].color = Color3(0.8f, 0.8f, 0.8f);
   // Render frustum.
  GfxDevice->SetTransform(eTransformWorld, mMatrix);
  GfxDevice->Draw(GfxDevice::PrimLineList, verts, 8, indices, 24);
----8<----

If you have any questions about the specifics of the above code, mail me
offline.

HTH

Jim Offerman

Innovade
- designing the designer
----- Original Message -----
From: "Michael S. Harrison" <mic...@ud...>
To: <gda...@li...>
Sent: Monday, August 21, 2000 9:18 AM
Subject: [Algorithms] visualizing frustum planes?


> I'm attempting to implement the AABB culling code talked about here some
time ago and I'm running into a general problem in visualizing the frustum
planes used to cull objects based on their AABB's
>
> I'm using both Klaus Hartmann's AABBCull sample and the Viewcull sample
included with the OpenGL FAQ.
>
> While the code generally works, I'm having some difficulty visualizing the
relationship between the plane vector and the "distance" value stored with
it, which I'm sure is the reason I can't quite figure out why the code
generates intersection results when it should generate a full cull.
>
> As you might guess, I'm fairly new to the world of 3d projection and I'm
still wrapping my mind around all the transformations that take an object
from "world" space to screen space.
>
> Can anyone suggest a reference or way to visualize exactly what's going on
with the plane extraction and how the vectors relate back to the AABB?
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

AW: [Algorithms] LightMaps

[Maik G. <mai...@gm...>]

Hi ... i think i found a solution ... but i didnt implement it yet ...

you got to draw a border around the lightmaps ... with the right
lumel-values ... so the filtering uses the right colors even at the edges of
the triangles

bye

Maik
-----Ursprüngliche Nachricht-----
Von: gda...@li...
[mailto:gda...@li...]Im Auftrag von
Jaakko Westerholm
Gesendet: Montag, 21. August 2000 17:45
An: gda...@li...
Betreff: Re: [Algorithms] LightMaps



> But for the moment I have some difficulties with the bilinear >filtering,
which creates those nasty lines between triangles.

I have the same problem. Is there any solution to this?

--Jaakko--

Get your Free E-mail at http://bosti.zzn.com
___________________________________________________________________
Hae oma Web-perusteinen sähköposti palvelusi http://www.zzn.com:sta

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

[Algorithms] Rotation about arbitrary axis

[Pierre T. <p.t...@wa...>]

Hi,

Since I needed a piece of code to do that I searched the web and found:
http://www.iuk.tu-harburg.de/hypgraph/modeling/mod_tran/3drota.htm

I used the final matrix at the bottom of the page, but it seems to fail when
the arbitrary axis actually is the Z axis. The third column gets erased
where it should at least contain a 1. This is obvious when looking at the
provided matrix, since the third column of the third row depends on the
rotation angle - and of course if the input axis already is the Z axis, it
shouldn't.

Now, it sounds normal regarding the underlying method (mapping the rotation
axis to Z, etc). But I wonder whether there's an easy way to perform a real
arbitrary rotation about any arbitrary axis without using different code
paths according to the input axis.

I think it can probably be done by introducing quaternions or better,
angle-axis, in the story. But err.... maybe there's something simpler.

Pierre

Re: [Algorithms] Tangential Curvature of terrain

[Thatcher U. <tu...@tu...>]

From: Ron Levine <ro...@do...>

> Klaus Hartmann  wrote:
>
> >Again, I've reached a point, where I wished that my math skills were
better.
> >At least I hope that the answer to my question is not too easy, so that
> >maybe some math guys are interested. I cannot even promise that I'll be
able
> >to follow your replies, but I'm sure someday I will (after re-reading,
> >re-re-reading, ... :)
> >
>
> See your calculus book for the notion of "concave up" vs "concave
> down" as applied to the graph of a function.  I would take issue with
> Ulrich's use of the term "convex" where I use "concave down", because
> it corresponds poorly with other important connotations in the usual
> meaning of the term "convex".

Fair enough, I abused the calculus terms.  In the context of a heightfield
for GIS though, "concave up" and "concave down" are less intuitive than
"concave" and "convex" in the geometric sense, since we're talking about a
solid (the earth) with a well defined inside and outside.

> [snip]

Thanks for the interesting curvature stuff.

--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] LightMaps

[Jaakko W. <za...@bo...>]

> But for the moment I have some difficulties with the bilinear >filtering, which creates those nasty lines between triangles.

I have the same problem. Is there any solution to this?

--Jaakko--

Get your Free E-mail at http://bosti.zzn.com
___________________________________________________________________
Hae oma Web-perusteinen sähköposti palvelusi http://www.zzn.com:sta

Re: [Algorithms] Tangential Curvature of terrain

[Thatcher U. <tu...@tu...>]

From: Joe Ante <jo...@ti...>
> Thatcher wrote:
> > Basically, the curvature of a function is its second derivative.
> I think geometrically viewn this is not the correct answer. Take as an
> simplyfied
> example: f(x) = x^2 f''(x) = 2
>
> Which meant that for every point the concavity/convexity is the same over
> the entire graph.

Whoops, you're right, I made a totally bogus statement.  The curvature of a
function is actually much more than just the second derivative.  According
to my calc book it's:

for a parametric curve with x = f(t), y = g(t):

k = | x'y'' - y'x'' | / ((x'^2 + y'^2) ^ (3/2))

I'm not sure that corrected definition impacts the original problem or its
solution much.

> What this concavity/convexity value actually specifies is how high a
heixel
> is in respect to the heixels in some distance around it. Maybe even in
> respect to all heightsamples in the heightmap.
>
> Consider for example an huge crater landscape and in the middle of this
> crater there is a small hill.
>
> The question now is, is the heixel on top of this small hill inside the
huge
> crater, more convex or concave?
>
>
> So what you want is that heixels that are near have more influence than
> heixels that are far away from the heixel, whose concavity/convexity you
> want to find out.
>
>
> So what you need to define is a function with a maximum distance, which
> gives you out a value between 0...1 when you give it a value from
> 0...maximumdistance.
> y = f (x)
> x e [0...maximumDistance]
> y e [0...1]
>
> A gauss-like curve is propably best suited:
> y = 360^-((x/maximumDistance)^5)
> (This function has worked out for me just fine.)
>
>
> Pseudocode:
>
> float ConcaveConvex (long inX, long inZ, float inMaxDistance)
> {
>     float itsHeight = GetHeight (inX, inZ);
>     float c = 0;
>
>     for (z=0;z<HowmanyHeixels;z++)
>     {
>         for (z=0;z<HowmanyHeixels;z++)
>         {
>             float difference = itsHeight - GetHeight (x, z);
>             float d = sqrt ((x-inX)*(x-inX) + (z-inZ)*(z-inZ));
>             c += difference  * GaussFunction (d, inMaxDistance);
>         }
>     }
>
>     c /= HowmanyHeixels* HowmanyHeixels;
>     return c;
> }
>
> float GaussFunction (float inX, float inMax)
> {
>     return powf (360.0F, -powf (inX / (inMax), 5.0F)
> }
>
> float GetHeight () should give back a height scaled to [0...1] in this
> context.

That will give a nice smoothed scalar field, but it loses the directionality
of the tangent/profile curvature that I think Klaus was looking for.  If I
read Ron correctly then you're computing something similar to the "mean
curvature", although not exactly the same thing because you're averaging
over all directions and across a potentially large area.  But it's probably
still useful for ecosystem stuff.

--
Thatcher Ulrich
http://tulrich.com

[Algorithms] Re: SSV and other bounding volumes

[Brian M. <bma...@ra...>]

    I know that there has been a lot of discussion about the merits of OBB's
and whether or not the code for them works but has anyone tried out a wider
range or bounding volumes or combinations?
    For my target platform memory is a scarce resource so OBB's are not so
appealing. I know there are a lot of ways to optimize memory usage for OBB's
but the paper tests I've run suggest that it's still going to need too much
memory.
    Again due to memory issues against polygon performance a lot of geometry
is going to be created on the fly from base representations so I'm trying to
come up with a solution that allows the collision structure to be built on
demand as well. I've been thinking of storing the decisions required to
build a good tree rather than the tree itself - the theory being that
deciding splitting points etc is more time consuming than just classifying
triangles.
    There are 2 papers that seem to suggest approaches:

    'Fast Proximity Queries with Swept Sphere Volumes'. and
    'Efficient Collision Detection of Complex Deformable Models using AABB
Trees'

   Anyone any thoughts? The traditional academic approach has both more
memory available and less triangles to test... so I'd welcome any insights
so hopefully I won't have to implement a whole load of options and time them

-Brian.

RE: [Algorithms] Massive spaces

[Graham S. R. <gr...@se...>]

Sam,

You should *definitely* look at the Hayden Planetarium work, done by

See this link: http://www.sgi.com/features/2000/feb/hayden/

I've seen this application running, at SIGGRAPH 99. It is *really*
impressive. It is similar to what you're talking about, but it models the
entire galaxy not just a solar system. And it doesn't let you zoom in and
see the surface details of a planet. (You can fly through volumetric
nebulae, though, and zoom in to see how constellations look in 3D.)
Graphics-wise, consumer gaming hardware is coming darned close to the
capability of  the 7-graphics-pipe Onyx2 system they use (with a capability
of a maximum of 70 million polys/second), but they do have 28 processors to
generate stars, stream textures from disk, etc.

1/100000 meter? Whoa. You'd want an awesome amount of texture storage, very
very fast disk access, and smooth, seamless texture
zooming/mipmapping/cliptexturing.

Graham Rhodes
  -----Original Message-----
  From: gda...@li...
[mailto:gda...@li...]On Behalf Of Sam Kuhn
  Sent: Sunday, August 20, 2000 9:33 PM
  To: gda...@li...
  Subject: [Algorithms] Massive spaces


  Hey,

  I've got a little mind game for you lot.

  Say you needed to render an entire solar system, in which you can zoom
down to a planet surface and see detail of about 1/100000 meter, or shoot
over to the sun and see the same sort of detail. There are a couple of
immediate problems:

  You would need need an enormous view volume (what say 20 lightyears big)
which gives an appauling zbuffer resolution.
  So whats are you to do? Render the distant objects closer than they
actually are (i.e. at the far end of a planet-sized view volume) and scale
them down accordingly?. This surely would give incorrect parralax between
the distant objects

  Also you need the planets to be of enormous size so that the front
clipping plane doesn't cut through the planets fine detail when you are in
very close (lets say an ant view for example). Which again buggers the
zbuffer, since you're using a planet sized view volume.

  Any ideas?

  Regards,

  Sam.

RE: [Algorithms] Spline Surface Extremal Points ?

[Graham S. R. <gr...@se...>]

By "extremal" I assume you mean maxima and minima with respect to a given
(possibly axis-aligned) coordinate frame. These maxima and minima can define
the height of the optimum bounding box in the given frame. Are you wanting a
solution that runs in real-time (which may not always be possible)? Here's a
rambling discussion, just my thoughts on the matter, from my work in the
past on numerical optimization.

Obviously, the control points can provide good clues to finding the extremal
points, and may be used to find a good default result. A quick and dirty
(non-exact) method is to tesselate the surface, and then iterate through the
points. This is a very reliable method that can be quite fast for coarse
tesselations. Obviously, such brute force methods are not optimum if you
have tons and tons of polygons on a surface----way too slow.

To find the maxima and minima, you are looking for points where the dz/dx
and dz/dy (when looking for the extremes in the z direction) derivatives are
both zero. You also have to check the boundary points, since these points
may be lower or higher than the valleys and peaks of the "hills" of the
surface. Here, the x and y directions are two orthogonal directions in your
coordinate frame of interest. Lets say that uv space happens to be exactly
the xy plane - the easiest case. Your surface can then be written as three
equations:

x = u
y = v
z = f(x, y).

Along a line of constant u (or v), the problem is fairly easy. Just set x =
constant (or y = constant) and solve for y (or x) on the following
equations:

dz/dy = 0 (or dz/dx = 0, if v is constant)

Your solution will yield x (given), y (solved for), and z (computed by
function f) for the *local* maxima and minima along the line of constant x.
You may find multiple values of y and z (1 for 1st and 2nd order curves, up
to 2 for 3rd order curves, etc.). Given a collection of *local* maxima and
minima, you can just go and find the absolute min and max values of z to
determine which points are the true max and min. Again, remember to check
the boundary points as well. For surfaces that are 2nd order in x and y,
this is a problem that is solvable closed form.

The preceeding paragraph does not give the min and max for the entire
surface----only along a line of constant x (or y). To find the local minima
and maxima on an entire surface, you have to simultaneously solve dz/dy = 0
*and* dz/dx = 0 rather than just one of the two. If f(x,y) is linear in both
x and y, you'll have a nice set of linear equations. If f(x,y) is higher
order (e.g., quadratic, etc.) in x or y, then you'll have a nonlinear set of
equations, harder to solve. Look for special cases.

The problem gets worse for a general surface in space, where u and v do not
correspond to the xy plane. The surface may fold over so z is not a
single-valued function in you coordinate frame of interest when you look at
z = f(x,y). You are no longer solving for just the maxima and minima of z,
but also of x and y. Requires that you work in uv space in order to avoid
the possible multi-valued-ness of the surface.

For a general surface, this is an optimization problem that cannot be solved
in closed form. It requires a gradient-based numerical optimization method
such as sequential quadratic programming. For smooth (read continuous)
surfaces that do not have many local maxima and minima, these numerical
methods are fairly robust----and not too slow either---converging in just a
few iterations, but for weird bumpy surfaces they aren't robust and
heuristic methods for choosing a starting point that is near the true
minima/maxima are required. For low-order spline patches, without actually
working out the math, there may sometimes actually be a closed form
solution... Obviously, there are nice special cases where a closed form
solution is known.

I know this is sort of a rambling discussion. As a first cut, you can always
check the control points themselves. If it helps or doesn't help, let me
know. I have a reference or two floating around.

Graham Rhodes

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Tim
> Thomas
> Sent: Friday, August 18, 2000 5:27 PM
> To: gda...@li...
> Subject: [Algorithms] Spline Surface Extremal Points ?
>
>
> Hi !
>
> How do i calculate the extremal points of a given ( tangents, 4 points )
> spline patch ?
>
> Any help welcome, even little hints or links
>
> Thanks in advance
>
> Tim
>
> --
> Sent through GMX FreeMail - http://www.gmx.net
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Tangential Curvature of terrain

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

Klaus Hartmann  wrote:

>Hi,
>
>I'd like to enhance my texture synthesizer for terrain. In particular, I'd
>like to make my ecosystem-classification depend on the tangential curvature
>of the terrain. I guess that may require some explanation.
>
>.....
>To make it easier for you to understand, you can have a loot at the
>following web-site:
>http://www2.gis.uiuc.edu:2280/modviz/
>
>The fifth terrain image (from above) shows the tangential curvature of some
>terrain. This is exactly what I'd like to do.>....
>.....
>
>Finally, my question is this. Does anyone know of a more detailed and
>I-don't-expect-you-know-everything resource on calculating the tangential
>curvature? Or maybe some readable source? Or even better... can someone
>explain this to me?
>

Only if you can  better explain what is meant by "tangential
curvature", not a standard mathematical term. It might be a standard
GIS term, but  I could not find a real definition of the term on the
uiuc GIS site that you cite.  The image you cite, at first sight,
suggests to me a couple of possible definitions, but on closer
examination of its coloring I can eliminate one, and am left with one
guess:

Namely, at points where the Gaussian curvature is non-negative, the
absolute value of the tangential curvature is the Gaussian curvature
(or some monotonic function of the Gaussian curvature) and it is
positive or negative according to whether the surface is concave up or
concave down at that point. At points where the Gaussian curvature is
negative (i.e. at saddle points), the tangental curvature is zero, or
better, undefined.   Leaving it undefined at saddle points might be OK
in view of the fact that the text of the cited image suggests that the
GIS people are interested in this concept in connection with the
distinction between "convergent" and "divergent" flow of water, and it
seems to me that it too would be undefined at a saddle point.

>Again, I've reached a point, where I wished that my math skills were better.
>At least I hope that the answer to my question is not too easy, so that
>maybe some math guys are interested. I cannot even promise that I'll be able
>to follow your replies, but I'm sure someday I will (after re-reading,
>re-re-reading, ... :)
>

See your calculus book for the notion of "concave up" vs "concave
down" as applied to the graph of a function.  I would take issue with
Ulrich's use of the term "convex" where I use "concave down", because
it corresponds poorly with other important connotations in the usual
meaning of the term "convex".  

For discussions of the various kinds of curvatures of surfaces, see
any text on introductory classical differential geometry, an
enormously beautiful and powerful subject with many applications in
computer graphics.   Some facility in the calculus of several
variables, and, of course, elementary vector analysis, would be the
prerequisites.  My two favorite books at the introductory level are
the ones by Dirk Struik, and by Barrett O'Neill. I'm not sure whether
either is still in print, but they, and others, should be available in
college libraries. 

Differential geometry actually defines four different notions of
curvature of a surface at a point, all involving the second partial
derivatives of a parametric representation, but in different ways:
normal curvatures, principal curvatures, mean curvature and Gaussian
curvature. 

Note the distinction between plurals and singulars:  A smooth surface
can have infinitely many normal curvatures at a point, one for each
possible tangent vector direction. It can have only two different
principal curvatures at each point, namely the maximum and minimum of
the normal curvatures.  But at each point it has only one mean
curvature (the average of the two principal curvatures) and one
Gaussian curvature (the product of the two principal curvatures). 

The Gaussian curvature is the most telling single surface shape
parameter at a point--it occurs in the statements of the deepest and
most powerful theorems of the differential geometry of surfaces. Its
generalization to the 4D space-time manifold of general relativity is
the famous "curvature" of the "curved space-time" that measures the
gravitational field, but I digress.

For a terrain in GIS (as opposed to an abstract surface in pure math),
you also have the notions of "up" and "horizontal", and it is  clear
that the intended meaning of "tangential curvature" has something to
do with how the surface is oriented with respect to "up". 

Re: [Algorithms] Massive spaces

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

> Of course if your planet doesn't even have an atmosphere then...
> erm...

... well, then it's just not cool to hang out there anyway, right? ;)
--
gl

Re: [Algorithms] Massive spaces

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

On Mon, 21 Aug 2000, Sam Kuhn wrote:

> Ah the old, through the clouds and "fwip!" :)
> Love it!
 
For variety (and planets without clouds) you can do the "burning
up in the atmosphere" thing - lots of nice red fire...and *then*
"fwip!" (that's a technical term - right? :-)

Of course if your planet doesn't even have an atmosphere then...
erm...

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] Tangential Curvature of terrain

[Joe A. <jo...@ti...>]

> Basically, the curvature of a function is its second derivative.
I think geometrically viewn this is not the correct answer. Take as an
simplyfied 
example: f(x) = x^2 f''(x) = 2

Which meant that for every point the concavity/convexity is the same over
the entire graph.

What this concavity/convexity value actually specifies is how high a heixel
is in respect to the heixels in some distance around it. Maybe even in
respect to all heightsamples in the heightmap.

Consider for example an huge crater landscape and in the middle of this
crater there is a small hill.

The question now is, is the heixel on top of this small hill inside the huge
crater, more convex or concave?


So what you want is that heixels that are near have more influence than
heixels that are far away from the heixel, whose concavity/convexity you
want to find out.


So what you need to define is a function with a maximum distance, which
gives you out a value between 0...1 when you give it a value from
0...maximumdistance.
y = f (x)
x e [0...maximumDistance]
y e [0...1]

A gauss-like curve is propably best suited:
y = 360^-((x/maximumDistance)^5)
(This function has worked out for me just fine.)


Pseudocode:

float ConcaveConvex (long inX, long inZ, float inMaxDistance)
{
    float itsHeight = GetHeight (inX, inZ);
    float c = 0;
    
    for (z=0;z<HowmanyHeixels;z++)
    {
        for (z=0;z<HowmanyHeixels;z++)
        {
            float difference = itsHeight - GetHeight (x, z);
            float d = sqrt ((x-inX)*(x-inX) + (z-inZ)*(z-inZ));
            c += difference  * GaussFunction (d, inMaxDistance);
        }
    }
    
    c /= HowmanyHeixels* HowmanyHeixels;
    return c;
}

float GaussFunction (float inX, float inMax)
{
    return powf (360.0F, -powf (inX / (inMax), 5.0F)
}

float GetHeight () should give back a height scaled to [0...1] in this
context.



There is plenty room for optimization here (tables, tables, tables)
But even then it will be very slow. But it doesnt matter that much because
you dont want to calculate the ecomap in realtime or as a preprocessing
phase step anyways.


Note that I havent integrated this into my terrain engine yet, I have only
spent some thought on it, so I cant really guarentee that it works.

bye joe

Re: [Algorithms] Massive spaces

[jason w. <jas...@po...>]

> Ah the old, through the clouds and "fwip!" :)
> Love it!


Yeah, it's a nice cinematic moment reguardless of weither you need it... :)

Re: [Algorithms] Massive spaces

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

Ah the old, through the clouds and "fwip!" :)
Love it!

Sam.


-----Original Message-----
From: jason watkins <jas...@po...>
To: gda...@li...
<gda...@li...>
Date: 21 August 2000 3:28 AM
Subject: Re: [Algorithms] Massive spaces


>imperium galactica has some some very nice transitions from solar system
>level down to surface level. If you want a real mathematical approach, I'm
>sure there is one out there.. the principle is one of scaling the viewspace
>1 unit to something that matches the current scope. The other approach is
>the animators approach: as you fly down to the ground, you go through
>clouds, which obscure the screen enough to swap to a completely different
>scene database.
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list