gdalgorithms-list

[Algorithms] ECTS

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

I visited the ECTS computer game trade show in london over the weekend. Bit
dissapointing really, not much cool stuff to see. Metal gear solid 2 looked
amazing, as did the "dinasour" demo at the nvidia stand (Developed by crytek
www.crytek.com) I believe our very own connor stokes has just got a job
there, so connor, give the team my congratulations on producing, in my
opinion,  the best (visible) thing at ECTS!

sam

RE: [Algorithms] FW: [CsMain] Scene Graphs

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

I posted some details about Open Inventor in my other message on this
thread, and about IRIS/OpenGL Performer as well. Mainly some comments and
links.

Of course, VRML97 is a "standard" SG format as well.

Graham Rhodes

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of
> Patrick E. Hughes
> Sent: Wednesday, September 06, 2000 12:01 PM
> To: gda...@li...
> Subject: Re: [Algorithms] FW: [CsMain] Scene Graphs
>
>
> >> but there`s no standart, and now after Fahrenheit blowup,
> seems there`s no
> >> hope for standart SG in nearest future, unfortuntaly
> >
> >The worst part of it is that without a standard SG, there is no
> >way to promote the writing of generic 3D file loaders - which is
>
> So where does Inventor and the *.iv format fit into this now that (I
> believe) it has become an open-source environment?
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

[Algorithms] Extracting scale from matrix

[Jon A. <jan...@on...>]

Are there any good tricks for extracting the scale (x, y, z)  from a 4x4 
matrix?  It seems pretty trivial to do it for matrices that consist of 
rotations about a single axis, but I'm having problems doing it for more 
complex matrices.

Jon

[Algorithms] Re: Heightfield to NURBS conversion

[Dave F. <df...@ra...>]

>Could anyone of you point me to an algorithm on heightfield
>to NURBS conversion i.e an algorithm which takes as input
>an heightfield and returns the control points of the NURBS-
>surface which APPROXIMATES the heightfield to a user given
>error?

 There are many techniques for this, ranging from the top-down
 approach that Dave suggests to the bottom-up approach that
 removes knots from a dense NURBS mesh.

 When you say it must be NURBS, do you mean it must have non-uniform
 knot spacing and non-zero wieghts for the control points, or
 would you be just as happy with a rational form of a standard
 B-spline? (ie. uniform knots + all wieghts at one).

 Do you want quadratic, cubic or quartic surfaces?

 Another way of putting this is to ask if you are happy with a
 smooth approximation or do you want a surface that has sharp
 edges in it? 

 Also do you want just a single surface to do the approximation
 or are multiple surfaces ok? (If the latter then NURBs with triple
 end knots are equivalent to Bezier patches).

 Is the hieghtfield a grid or scattered data?

 What modelling system are you using? Most have some sort of "shrink-wrap"
 facility built-in (or with a plug-in) that you can wrangle
 into doing this for you (though probably quite slowly).

 Finally, how many times do you have to do this? If it is just once,
 then contract a company like Paraform to do the fitting for you.
 (or you can buy their software).

   Dave

Re: [Algorithms] FW: [CsMain] Scene Graphs

[Patrick E. H. <hu...@tr...>]

>> but there`s no standart, and now after Fahrenheit blowup, seems there`s no
>> hope for standart SG in nearest future, unfortuntaly
> 
>The worst part of it is that without a standard SG, there is no
>way to promote the writing of generic 3D file loaders - which is

So where does Inventor and the *.iv format fit into this now that (I
believe) it has become an open-source environment?

Re: [Algorithms] Quaternions in IK

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

Jason Zisk  wrote:

>Can you convert between Quaternion and Euler without any loss of
>information?  I have a routine to convert Euler->Quat but I've never seen
>one that goes from Quat->Euler.  This would be most helpful for my current
>project.
>

It is not a question of loss of information, but of absence of
information from the start.  What I mean by this is that the real
geometric thing is the rotation (or orientation) not an Euler angle
construction of it.  The rotation does not uniquely determine the
Euler angles.  If FREE rotation is allowed (think a ship on the sea or
an aircraft or spacecraft) , then a given rotation can be decomposed
into Euler components in infinitely many ways.

So if you start with an Euler construction to get a rotation matrix
(or a quaternion) then use a routine such as one that Dave Eberly
points to on his site to get Euler angles from that quaternion or
matrix, then there is no guarantee that they will be the same Euler
angles you started with....The rotation does not determine the Euler
angles.

On the other hand, for the systems at issue in IK problems, viz.,
linked structures with constrained joints, such as robots and animated
characters, the rotation of the end effectors are NOT free, but
constrained. Typically, the Euler axes DO have a mechanical reality in
the construction of your robot as a linkage of defined 1-DOF joints,
and the range of rotation of each joint is limited.  In many such
cases, no doubt, the Euler angles ARE uniquely determined by the
orientation of the end effector, and in principle one could find an
algorithm to determine them from the rotation.  But it would be
fortuitous if one of Dave's routines gave the correct decomposition in
your particular case.

These considerations lead to a question that keeps coming up for me,
but for which I have not found the answer.  I've posted it on various
forums and lists from time to time, without response.  I'm going to
ask it again here, because at least a few will understand its
statement, and maybe Dave or Jeff's grad student or someone will
remember seeing it discussd somewhere:   In the rotation group SO(3),
how can one characterize a maximal neighborhood of the identity that
has a unique analytic Euler angle parametrization?

RE: [Algorithms] FW: [CsMain] Scene Graphs (Open Inventor open source + Performer for Linux)

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

I don't know if you all are aware of this (but some probably are), but SGI
has released their Open Inventor scene graph engine (version 2.1 or maybe
2.2 I think) as open source, see this link:

http://oss.sgi.com/projects/inventor/

It is an extensible/programmable scene graph engine that is quite powerful.
It has a "standard" file format as well, and built-in loaders and writers
for that format. It includes some simple animation engines, but as with all
of the engine you can write your own, customized engines.

I've developed a rather extensive application using Open Inventor (the TGS
versions and SGI versions) for about 4 years now, and I consider myself an
expert. And I'd like to mention these rather large issues that exist with
Open Inventor (SGI's version at least):

1) There be bugs in SGI's version! For example, the SoCalculator animation
engine sometimes locks up and doesn't work when you write vector equations!
That engine also sometimes gets the sign wrong when multiplying terms
together. These two are fixed in (at least 2.5 and later) TGS versions.

2) The SGI version isn't really fantastic for very large models, though that
might not be too much of a problem for some games right now.

3) The TGS version will likely continue to be a commercial product for sale.
A pity (if you want it for free) since it has many enhancements, such as
continuous level of detail for large model display, as well as the bug fixes
mentioned above and more.

4) The SGI version is IRIX only! It probably can be ported to Linux readily.
And it has been ported to Windows by others (TGS of course, plus Portable
Graphics before they were absorbed by TGS, and at least one other company),
but the Windows ports are not open source.

5) Open Inventor is not really designed to deal with large immersive worlds.
Its fine for inspecting CAD models and collections of objects.

If you're a Linux developer, you might consider using IRIS Performer (to be
OpenGL Performer with next version), which is freely available for Linux
(binaries only). It is better suited for large models and environments, and
it is designed to actively manage performance/frame rate. Probably a better
choice for games, but there is no Windows version and likely never will be.
See this link:

http://www.sgi.com/software/performer/

Graham Rhodes

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Ko,
> Manchor
> Sent: Tuesday, September 05, 2000 12:38 PM
> To: gda...@li...
> Subject: RE: [Algorithms] FW: [CsMain] Scene Graphs
>
>
> Yes - and of coz read the classic Performer paper. I believe it
> is Siggraph
> 96 by Ruelfe and Hellman.
>
> -----Original Message-----
> From: Graham S. Rhodes [mailto:gr...@se...]
> Sent: Tuesday, September 05, 2000 7:14 AM
> To: gda...@li...
> Subject: RE: [Algorithms] FW: [CsMain] Scene Graphs
>
>
> At SIGGRAPH 1999 there was a paper/panel session called "Scene
> Graphs: Wired
> or Tired" to discuss this, although not necessarily from a game
> development
> standpoint.
>
> Here are a couple of links that should give you part of the
> content of that
> presentation (if you don't have the SIGGRAPH proceedings already):
>
> http://www.intrinsic.com/technology/presentations.htm
> http://www.cs.brown.edu/research/graphics/research/siggraph99/scenegraph/
>
> Graham Rhodes
>
> > -----Original Message-----
> > From: gda...@li...
> > [mailto:gda...@li...]On Behalf Of Aaron
> > Drew
> > Sent: Saturday, September 02, 2000 7:56 PM
> > To: gda...@li...
> > Subject: [Algorithms] FW: [CsMain] Scene Graphs
> >
> >
> > I've read many discussions on this list as to the pro's and con's
> > of various
> > solutions to storing, rendering and processing 3D objects but the
> > scene-graph hasn't really made much discussion since I've been
> subscribed.
> >
> > I can't seem to find much on the web in regards to their
> usefulness apart
> > from a few papers on VRML and Java3D.
> >
> > I'm having trouble seeing how the added cost of unnecessary traversal of
> > nodes and the memory overheads of parent/child links in a scene would be
> > worth the added effort but I'm curious as to the thoughts of the many
> > experienced developers on this list.
> >
> > Do scene-graphs pay off?
> >
> > If so, how?
> >
> > Managing vertex buffers, textures, multiple instances of objects (with
> > shared vertex data), etc can get rather clumsy without a
> consistant system
> > yet everything I've read about scene-graphs suggests that they
> are simply
> > traversed and the objects in them rendered. How would I
> represent (say) an
> > octree implementation within a construct like
> > this?
> >
> > - Aaron
> >
> > _______________________________________________
> > 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
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] FW: [CsMain] Scene Graphs

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

On Wed, 6 Sep 2000, Timur Davidenko wrote:

> As i see there`s quite a bad situation on SG  scene..
> most engines implements thier own propritary scene graphs,
> some better some worser, this days 3D Engine = proprietary scene graph. (as
> in old days 3D engine was set of fast rasterizers)
> but there`s no standart, and now after Fahrenheit blowup, seems there`s no
> hope for standart SG in nearest future, unfortuntaly
 
The worst part of it is that without a standard SG, there is no
way to promote the writing of generic 3D file loaders - which is
something that's badly needed IMHO.

----
Science being insufficient - neither ancient protein species deficient.

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] Heightfield to NURBS conversion

[Dave E. <eb...@ma...>]

From: "Christian R. M. Koerber" <chr...@pu...>
> Could anyone of you point me to an algorithm on heightfield
> to NURBS conversion i.e an algorithm which takes as input
> an heightfield and returns the control points of the NURBS-
> surface which APPROXIMATES the heightfield to a user given
> error?

From: "Martin Fuller" <mf...@ac...>
> What you're asking for is a easy solution to what is a very
> very complex problem.  I would suggest instead of using
> NURBS looking at a curve equation that actually
> interpolates the control points. (but break the convex hull)
> Catmull Rom splines immediatly spring to mind.

From: "Christian R. M. Koerber" <chr...@pu...>
> Unfortunately it MUST be NURBS. The project I participate in uses them
> and there is no way around that. And it MUST be approximating since I need
> fewer control points than there are samples in the heightfield.

Well, you can always set up the NURBS as (X(s,t),Y(s,t),Z(s,t),1),
a Bezier surface :)

As folks have pointed out, this is a difficult problem if all the
user gets to specify the error.  I suggest a modification that
fits the N_h x M_h height field with N_b x M_b Bezier
surface patches of low degree (say bicubic patches).  The
control points are set up with (x,y) values as a regular lattice
in the plane.  Assuming some continuous representation of
the height field H(s,t), (linear or bilinear would be easiest),
and letting B(s,t) be the Bezier patch (with to-be-determined
control points) that corresponds to part of the height field,
set up a system of linear equations whose unknown are the
control points by minimizing E(control_points) =
Integral |B(s,t)-H(s,t)|^2 ds dt.

For example, you could try to fit the entire N_h x M_h height
field with a single Bezier bicubic patch and get a 3x3 system
of equations for the control points.  While it might be possible
to calculate in closed form the entries of the coefficient matrix,
it is not necessary.  You can compute these numerically.  Of
course a single patch probably is not accurate enough
(actually compare the E(...) value to your specified tolerance).
If not, "subdivide" in a sense and try a 2x2 set of patches
Minimize four integrals, add up the errors.  If still not within
tolerance, subdivide again and try a 4x4 set of patches, etc.

This least-squares method applies equally well, to NURBS.
The entries of the coefficient matrix become integrals of
rational functions.  Not a problem for numerical integrators.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com

Re: [Algorithms] Heightfield to NURBS conversion

[Garry C. M. <wb...@di...>]

Works for me, copy and paste the URL and add the two parts together,
the mailer has split the long line...

Garry.

----- Original Message -----
From: "Christian R. M. Koerber" <chr...@pu...>
> >
> >
http://graphics.cs.ucdavis.edu/CAGDNotes/Catmull-Rom-Spline/Catmull-Rom-Spli
> > ne.html
>
> Though I can't make use of them, I'd like to have a look at those. Could
it be
> that this link is broken?
>
> Christian
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Heightfield to NURBS conversion

[Christian R. M. K. <chr...@pu...>]

Martin Fuller wrote:
> 
> This really is a very very complex problem to attempt to solve, I don't know
> of any algorithms or programs that do this.
> What I would suggest instead is using a curve equation that interpolates all
> the control points. (But will break the convex hull)
> One such spline it the Catmull Rom spline, information about which can be
> found here.
> 
> http://graphics.cs.ucdavis.edu/CAGDNotes/Catmull-Rom-Spline/Catmull-Rom-Spli
> ne.html

Though I can't make use of them, I'd like to have a look at those. Could it be
that this link is broken?

Christian

Re: [Algorithms] Heightfield to NURBS conversion

[Christian R. M. K. <chr...@pu...>]

Martin Fuller wrote:
> 
> What you're asking for is a easy solution to what is a very very complex
> problem. I would suggest instead of using NURBS looking at a curve 
> equation that actually interpolates the control points. (but break the 
> convex hull) Catmull Rom splines immediatly spring to mind.

Unfortunately it MUST be NURBS. The project I participate in uses them 
and there is no way around that. And it MUST be approximating since I need 
fewer control points than there are samples in the heightfield.

Christian

[Algorithms] Bitmap to verts array (vectorization ?)

[Lionel F. <li...@mi...>]

Hello !

I'm currently trying to write an algo that "vectorize" a 2-bits bitmap into
an array of vertices.

The source bitmap is a 256x256x2 bitmap, which is the projection of a 3D
object on the Z plane. Now, I would like to convert this bitmap to an array
of triangle, in a stripped way.

Does anybody knows such an algorithm ?

Thank you for any advice !

Lionel.

RE: [Algorithms] Heightfield to NURBS conversion

[Martin F. <mf...@ac...>]

Sorry accidentally sent that prematurely. (Damm short cut keys)


-----Original Message-----
From: Martin Fuller [mailto:mf...@ac...]
Sent: 06 September 2000 03:05
To: 'gda...@li...'
Subject: RE: [Algorithms] Heightfield to NURBS conversion


What you're asking for is a easy solution to what is a very very complex
problem.
I would suggest instead of using NURBS looking at a curve equation that
actually 
interpolates the control points. (but break the convex hull) Catmull Rom
splines 
immediatly spring to mind.


-----Original Message-----
From: Christian R. M. Koerber
[mailto:chr...@pu...]
Sent: 06 September 2000 02:05
To: gda...@li...
Subject: Re: [Algorithms] Heightfield to NURBS conversion


"Christian R. M. Koerber" wrote:

> 
> I have a question too:
> 
> Could anyone of you point me to an algorithm on heightfield

actually I meant 'easy, ready to use algorithm'


> to NURBS conversion i.e an algorithm which takes as input
> an heightfield and returns the control points of the NURBS-
> surface which APPROXIMATES the heightfield to a user given
> error?
> I'd really like to avoid meddling with the later chapters
> of Piegl & Tillers NURBS book! Maybe you even know a pro-
> gram?
_______________________________________________
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] Heightfield to NURBS conversion

[Martin F. <mf...@ac...>]

This really is a very very complex problem to attempt to solve, I don't know
of any algorithms or programs that do this.
What I would suggest instead is using a curve equation that interpolates all
the control points. (But will break the convex hull)
One such spline it the Catmull Rom spline, information about which can be
found here.

http://graphics.cs.ucdavis.edu/CAGDNotes/Catmull-Rom-Spline/Catmull-Rom-Spli
ne.html

Using Catmull Rom splines in certainly much easier (and quicker) than
dealing with NURBS.
Hope this helps, :)
Cheers,
Martin


-----Original Message-----
From: Christian R. M. Koerber
[mailto:chr...@pu...]
Sent: 06 September 2000 02:05
To: gda...@li...
Subject: Re: [Algorithms] Heightfield to NURBS conversion


"Christian R. M. Koerber" wrote:

> 
> I have a question too:
> 
> Could anyone of you point me to an algorithm on heightfield

actually I meant 'easy, ready to use algorithm'


> to NURBS conversion i.e an algorithm which takes as input
> an heightfield and returns the control points of the NURBS-
> surface which APPROXIMATES the heightfield to a user given
> error?
> I'd really like to avoid meddling with the later chapters
> of Piegl & Tillers NURBS book! Maybe you even know a pro-
> gram?
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] Heightfield to NURBS conversion

[Martin F. <mf...@ac...>]

What you're asking for is a easy solution to what is a very very complex
problem.
I would suggest instead of using NURBS looking at a curve equation that
actually 
interpolates the control points. (but break the convex hull) Catmull Rom
splines 
immediatly spring to mind.


-----Original Message-----
From: Christian R. M. Koerber
[mailto:chr...@pu...]
Sent: 06 September 2000 02:05
To: gda...@li...
Subject: Re: [Algorithms] Heightfield to NURBS conversion


"Christian R. M. Koerber" wrote:

> 
> I have a question too:
> 
> Could anyone of you point me to an algorithm on heightfield

actually I meant 'easy, ready to use algorithm'


> to NURBS conversion i.e an algorithm which takes as input
> an heightfield and returns the control points of the NURBS-
> surface which APPROXIMATES the heightfield to a user given
> error?
> I'd really like to avoid meddling with the later chapters
> of Piegl & Tillers NURBS book! Maybe you even know a pro-
> gram?
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Heightfield to NURBS conversion

[Christian R. M. K. <chr...@pu...>]

"Christian R. M. Koerber" wrote:

> 
> I have a question too:
> 
> Could anyone of you point me to an algorithm on heightfield

actually I meant 'easy, ready to use algorithm'


> to NURBS conversion i.e an algorithm which takes as input
> an heightfield and returns the control points of the NURBS-
> surface which APPROXIMATES the heightfield to a user given
> error?
> I'd really like to avoid meddling with the later chapters
> of Piegl & Tillers NURBS book! Maybe you even know a pro-
> gram?

[Algorithms] Heightfield to NURBS conversion

[Christian R. M. K. <chr...@pu...>]

After lurking around for some months due to 'transient mesage'
replies, which I don't seem to get anymore, probably because
the list moved to sourceforge, I'd like to introduce myself:

I am Christian Körber, German, study Computer Science in
Hamburg and specialize in computer graphics and geometric
modeling. 

I have a question too:

Could anyone of you point me to an algorithm on heightfield
to NURBS conversion i.e an algorithm which takes as input
an heightfield and returns the control points of the NURBS-
surface which APPROXIMATES the heightfield to a user given
error?
I'd really like to avoid meddling with the later chapters 
of Piegl & Tillers NURBS book! Maybe you even know a pro-
gram?

Christian

Re: [Algorithms] FW: [CsMain] Scene Graphs

[Timur D. <ti...@3d...>]

As i see there`s quite a bad situation on SG  scene..
most engines implements thier own propritary scene graphs,
some better some worser, this days 3D Engine = proprietary scene graph. (as
in old days 3D engine was set of fast rasterizers)
but there`s no standart, and now after Fahrenheit blowup, seems there`s no
hope for standart SG in nearest future, unfortuntaly


_______________________
 Timur Davidenko.
 3Dion Inc. (www.3dion.com)
 e-mail: ti...@3d...


----- Original Message -----
From: "Ko, Manchor" <MAN...@ca...>
To: <gda...@li...>
Sent: Tuesday, September 05, 2000 11:48 PM
Subject: RE: [Algorithms] FW: [CsMain] Scene Graphs


> I completely agrees with akbar and Stephen on this. Even if you decided
not
> to use an off the shelf scene graph API. Do built one yourself. If you
think
> you can do a good one. It is not a trivial task to built a good one. This
is
> an area that I have done quite a lot of work on.
>
> The SGI/Microsoft ill-fated Fahrenheit would be the cross-platform
Opengl++.
> You know what happened to it. Fahrenheit is actually architected quite
well.
> But that is another story....
>
> -----Original Message-----
> From: Akbar A. [mailto:sye...@ea...]
> Sent: Tuesday, September 05, 2000 1:20 PM
> To: gda...@li...
> Subject: RE: [Algorithms] FW: [CsMain] Scene Graphs
>
>
> hey,
>
> >Hence, whilst it's theoretically possible to make your game
> >run faster by writing it all in machine code
> you would have to be one very smart person to pull this one off. topping
of
> what the compilers' are generating is getting harder and harder (iirc vc7
is
> coming out later this year), plus there is the time it takes to write good
> low-level code :|
>
> >When it first appeared, everyone wanted to get at some lower level
> >'bare metal' interface to the hardware for speed.
> yes, i find this quite funny. remeber when everyone was like "give us the
> metal" and saying other things like this. then when they finnally got it
> with the psx2 a lot of them ran into problems (but they learnt a lot ;)
>
>
> >lots of people complained that it stifled their
> >creativity and wouldn't let them get at pixels in the
> this is somewhat true. there where some really cool demos back in the dos
> days that never made the converge to OpenGL.
>
> in general scenegraphs are good, they lay out a lot of foundation work so
> you don't have to reinvent "to much" of the wheel.
>
> btw, new movies up at www.sgi.com.
>
>
>
>
> peace,
> akbar A.
>
>
> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of
> Stephen J Baker
> Sent: Tuesday, September 05, 2000 1:22 PM
> To: gda...@li...
> Subject: RE: [Algorithms] FW: [CsMain] Scene Graphs
>
>
>
> > At SIGGRAPH 1999 there was a paper/panel session called "Scene Graphs:
> Wired
> > or Tired" to discuss this, although not necessarily from a game
> development
> > standpoint.
>
>
> I think scene graphs are like so many other aspects of making high
> performance applications - we used to write machine code - compilers
> were considered terribly inefficient.  Now compilers are getting
> better (so they are less wasteful) - machines are getting faster
> (so we care less) - and machines and our programs are getting
> COMPLICATED (so writing machine code is less possible).
>
> Hence, whilst it's theoretically possible to make your game
> run faster by writing it all in machine code - nobody does
> that anymore.
>
> I think the same thing happens with API's like OpenGL.  When
> it first appeared, everyone wanted to get at some lower level
> 'bare metal' interface to the hardware for speed.  I don't think
> anyone is advocating that anymore...for much the same reason
> that we don't use raw machine code anymore.
>
> Well, Scene Graph API's are quite possibly the next stage of
> evolution.  There is no doubt that IF YOU KNOW WHAT YOU ARE
> DOING you can get better performance by writing your own
> low level engine to the 'raw' OpenGL.  But as multi-pass
> rendering, shadows, etc get more and more complicated and
> the machines get faster and the scene graph API's get better,
> I believe there comes a point where you shrug your shoulders
> and say "who cares" about the small performance loss that
> comes from a generic rendering API versus something more
> optimised to your application that you could have written
> yourself.
>
> Just as with compiler technology, the point where you decide
> to switch depends a lot on how demanding your application
> is and how skilled you are.  Red hot x86 machine coders
> writing state of the art games were writing machine code
> long after the amateur Tetris clone writers had switched
> to C compilers.
>
> Another aspect to this was that when OpenGL first appeared
> on the PC, lots of people complained that it stifled their
> creativity and wouldn't let them get at pixels in the
> frame buffer.  It's really noticable how those sorts of
> complaints have tailed off over the last few years...I
> think we hear the same things about scene graph API's.
>
>   For some people "it forces us all into the same mold"
>   For other people "it liberates me from having to think
>      about the polygons so I can concentrate on higher
>      level stuff"  -- like physics for example.
>
> Finally, what forced people into using OpenGL (or D3D
> for that matter) was sheer hardware necessity - and it's
> my view that this too will happen to scene graph API's.
>
> We are already seeing with nVidia T&L cards that you
> need to lock your data into particular chunks of memory
> and send data to the card in carefully chosen chunk sizes
> if you want to get the very best performance.  Those are
> the kinds of *ugly* things that applications shouldn't
> have to deal with - they should be hidden inside a well
> written scene graph API - and if it were standardized
> across various cards, it could hide these kinds of
> hardware differences that OpenGL and D3D cannot.
>
> SGI's new 'shader language' is an example of this too -
> it's not a 'scene graph' API - but another way to look
> at a higher level rendering API.  As scene graph API's
> are to geometry, so shader languages are to state. They
> can play nicely together too.
>
> Scene Graph/Shader API's *will* be the next step - it's
> just a matter of when the balance tips in their favor.
>
> One thing that DOES concern me though is the lack of any
> prior 'open' standardization efforts in this area.  I was
> saddened that OpenGL++ didn't ever appear.
>
> 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
>
> _______________________________________________
> 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
>

[Algorithms] test, my apologies

[Christian R. M. K. <chr...@pu...>]

I seem to get strange replies.

Christian

Re: [Algorithms] Quaternions in IK

[Dave E. <eb...@ma...>]

From: "Jeff Lander" <je...@di...>
> Since the Matrix->Euler solution has a dependency
> on order of rotations, a general solution would handle
> any order.  I typically only use either XYZ or YXZ (HPB)
> so I have just two versions.

I have all six converters (XYZ, XZY, YXZ, YZX, ZXY, ZYX)
at my MgcCore.html page (MgcMatrix3.*), among other
conversions to/from various forms.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com

Re: [Algorithms] Quaternions in IK

[Jeff L. <je...@di...>]

The process is really Quat->Matrix->Euler.  Since Quat->Matrix is a pretty easy operation, you can use it as basically Quat->Euler.

I am sure others here have more robust or flexible routines like this but this is what I use.
Since the Matrix->Euler solution has a dependency on order of rotations, a general solution would handle any order.  I typically only use either XYZ or YXZ (HPB) so I have just two versions.  This returns the XYZ decomposition of a Quaternion (x,y,z,w)

You can run this into a EulerToQuat routine to check the results and as long as the EulerToQuat is XYZ order, it should be equal.  The HPB version can be calculated from this easily but if you need it, you can email me.

void QuatToEuler(const tQuaternion *quat, tVector *euler)
{
/// Local Variables ///////////////////////////////////////////////////////////
         float matrix[3][3];
         float cx,sx,x;
         float cy,sy,y,yr;
         float cz,sz,z;
///////////////////////////////////////////////////////////////////////////////
         // CONVERT QUATERNION TO MATRIX - I DON'T REALLY NEED ALL OF IT
         matrix[0][0] = 1.0f - (2.0f * quat->y * quat->y) - (2.0f * quat->z * quat->z);
//      matrix[0][1] = (2.0f * quat->x * quat->y) - (2.0f * quat->w * quat->z);
//      matrix[0][2] = (2.0f * quat->x * quat->z) + (2.0f * quat->w * quat->y);
         matrix[1][0] = (2.0f * quat->x * quat->y) + (2.0f * quat->w * quat->z);
//      matrix[1][1] = 1.0f - (2.0f * quat->x * quat->x) - (2.0f * quat->z * quat->z);
//      matrix[1][2] = (2.0f * quat->y * quat->z) - (2.0f * quat->w * quat->x);
         matrix[2][0] = (2.0f * quat->x * quat->z) - (2.0f * quat->w * quat->y);
         matrix[2][1] = (2.0f * quat->y * quat->z) + (2.0f * quat->w * quat->x);
         matrix[2][2] = 1.0f - (2.0f * quat->x * quat->x) - (2.0f * quat->y * quat->y);

         sy = -matrix[2][0];
         cy = sqrt(1 - (sy * sy));
         yr = (float)atan2(sy,cy);
         euler->y = (yr * 180.0f) / (float)M_PI;

         // AVOID DIVIDE BY ZERO ERROR ONLY WHERE Y= +-90 or +-270 
         // NOT CHECKING cy BECAUSE OF PRECISION ERRORS
         if (sy != 1.0f && sy != -1.0f)  
         {
                 cx = matrix[2][2] / cy;
                 sx = matrix[2][1] / cy;
                 euler->x = ((float)atan2(sx,cx) * 180.0f) / (float)M_PI;        // RAD TO DEG

                 cz = matrix[0][0] / cy;
                 sz = matrix[1][0] / cy;
                 euler->z = ((float)atan2(sz,cz) * 180.0f) / (float)M_PI;        // RAD TO DEG
         }
         else
         {
                 // SINCE Cos(Y) IS 0, I AM SCREWED.  ADOPT THE STANDARD Z = 0
                 // NEED SOME MORE OF THE MATRIX TERMS NOW
                 matrix[1][1] = 1.0f - (2.0f * quat->x * quat->x) - (2.0f * quat->z * quat->z);
                 matrix[1][2] = (2.0f * quat->y * quat->z) - (2.0f * quat->w * quat->x);
                 cx = matrix[1][1];
                 sx = -matrix[1][2];
                 euler->x = ((float)atan2(sx,cx) * 180.0f) / (float)M_PI;        // RAD TO DEG

                 cz = 1.0f;
                 sz = 0.0f;
                 euler->z = ((float)atan2(sz,cz) * 180.0f) / (float)M_PI;        // RAD TO DEG
         }
}
// QuatToEuler  ///////////////////////////////////////////////////////////////


At 10:45 PM 9/5/2000 -0400, you wrote:
>Can you convert between Quaternion and Euler without any loss of
>information?  I have a routine to convert Euler->Quat but I've never seen
>one that goes from Quat->Euler.  This would be most helpful for my current
>project.
>
>- Jason Zisk
>- nFusion Interactive LLC

Re: [Algorithms] Quaternions in IK

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

Can you convert between Quaternion and Euler without any loss of
information?  I have a routine to convert Euler->Quat but I've never seen
one that goes from Quat->Euler.  This would be most helpful for my current
project.

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Jeff Lander" <je...@di...>
To: <gda...@li...>
Sent: Tuesday, September 05, 2000 8:06 PM
Subject: Re: [Algorithms] Quaternions in IK


> I looked into this for quite a while some time ago.  I asked quite a few
people about it as well.  The consensus is that everyone converts from
Quaternion to Euler and back to handle DOF restrictions.  Intuitively it
seems that there should be a way to restrict the motion of a quaternion to a
particular portion of the hypersphere.  It is a bit beyond my math skills
though.  I have a math grad starting work for me this month so I can put her
on the task. :) No better research tool then a graduate student.
>
> In implementation, for me the conversion isn't too severe.  I only
calculate the IK solution when needed and I classify joints that are 1 DOF
so they are not effected.
>
> -Jeff
>
> At 05:36 AM 9/3/2000 -0700, you wrote:
> >Hi all ,
> >
> >Does any one know an efficient way of constraining quaternions in IK
without factorizing them into 3 axis quaternions ?
> >Finding the required rotation quaternion in IK is pretty easy , but how
can we make sure that it doesn't violate or 3 constrains of the 3DOFs of the
joint ? what I'm doing now is factorizing the IK result quaternion of the
joint into xrotation quaternion yrotation quaternion and zrotation
quaternion , constrain them by their maximums and recombine them again ,
which is obviously a very expensive process.
> >
> >any ideas ? or maybe references ?
> >
> >Thanks
> >
> >Auday
> >
> >_______________________________________________
> >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] Quaternions in IK

[Jeff L. <je...@di...>]

I looked into this for quite a while some time ago.  I asked quite a few people about it as well.  The consensus is that everyone converts from Quaternion to Euler and back to handle DOF restrictions.  Intuitively it seems that there should be a way to restrict the motion of a quaternion to a particular portion of the hypersphere.  It is a bit beyond my math skills though.  I have a math grad starting work for me this month so I can put her on the task. :) No better research tool then a graduate student.

In implementation, for me the conversion isn't too severe.  I only calculate the IK solution when needed and I classify joints that are 1 DOF so they are not effected.

-Jeff

At 05:36 AM 9/3/2000 -0700, you wrote:
>Hi all ,
>
>Does any one know an efficient way of constraining quaternions in IK without factorizing them into 3 axis quaternions ?
>Finding the required rotation quaternion in IK is pretty easy , but how can we make sure that it doesn't violate or 3 constrains of the 3DOFs of the joint ? what I'm doing now is factorizing the IK result quaternion of the joint into xrotation quaternion yrotation quaternion and zrotation quaternion , constrain them by their maximums and recombine them again , which is obviously a very expensive process.
>
>any ideas ? or maybe references ?
>
>Thanks
>
>Auday
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] an opengl problem

[Frag_ D. <fra...@ho...>]

     One reason might be your video card's messed up with different modes.  
For example, for one of my test things awhile ago, I got lazy and just told 
OpenGL that I wanted 16-bit color, but didn't take the effort to set it up 
that way.  The video mode was set in 32-bit color (on a Voodoo 3 card), and 
it ran at about 1.5-3.0 fps, when it ran at nearly 200-250 fps when I set it 
to the proper bpp.  That's one reason that could be.  Other than that, I 
don't know with that info.  Anyone else want to take a wild guess (or does 
anyone else have a reason?)?


>From: "tSG" <ts...@ma...>
>Reply-To: gda...@li...
>To: <gda...@li...>
>Subject: [Algorithms] an opengl problem
>Date: Tue, 5 Sep 2000 22:34:53 +0200
>
>Hi!
>
>I'm new on this list, so i describe myself. :)
>I'm Gabor Simko (tSG), and I'm hungarian.
>I like visualc,asm,free pascal and opengl.
>This was that. :)
>
>So my question:
>   i have made a little program in opengl.
>   It puts out 500 textured cube, but the
>   problem is that it is very slow.
>   I don't use any lights or fog etc...
>   The resolution is 640x480x16million colors.
>   Why could it be so slow?
>
>Thx to everybody
>     tSG
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

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

Share information about yourself, create your own public profile at 
http://profiles.msn.com.