Re: [Algorithms] Dynamic lighting and shadows in DOOM3

[Scott LeGrand <varelse@be...>]

> Don't forget, the GF3 also supports the GL_DEPTH_STENCIL texture format
> now (24bit Z, 8bit stencil) that would probably make people here happy
> when they use both methods... the biggest problem with shadow maps in the
> past has been a severe lack of precision in depth component.

Stencil buffers rule, but I am curious about what the NVidians might have
done with shadow buffering in order to improve its quality.  I also dug
the editorial a few weeks back about the hazards of providing cheap and
easy shadows to level designers: something like oh great, now we're going
to have swinging lights, and lights behind swinging gates, and swinging lights
behind rotating fans behind a swinging gate etc etc...

> Also, GF3 support fast FSAA (apparently, can't say till my card gets here)
> that would reduce any 'sparkle' artifacts you currently see...

I look forward to that as well.  FSAA sucked on my GeForce 2 Ultra alas...

Scott

Re: [Algorithms] Dynamic lighting and shadows in DOOM3

[Leath Muller <Leath.Muller@en...>]

Scott LeGrand wrote:
 
> Nope, he said he's not using anything of the sort as he has never been satisfied
> with their quality.  He then conceded he was going to check out the quality of
> those on the GeForce 3...
 
Don't forget, the GF3 also supports the GL_DEPTH_STENCIL texture format
now (24bit Z, 8bit stencil) that would probably make people here happy
when they use both methods... the biggest problem with shadow maps in the
past has been a severe lack of precision in depth component.

Using per pixel pipeline stages in the GF3 you can (in theory) do per pixel
shadowing, although it will take up a lot of passes.

> Quoting his .plan:
> "The shadow map support is good to get in, but I am still unconvinced 
> that a fully general engine can be produced with acceptable quality using 
> shadow maps for point lights. I spent a while working with shadow 
> buffers last year, and I couldn't get satisfactory results. I will revisit
> that work now that I have GeForce 3 cards, and directly compare it with my 
> current approach."

I really have to ask -- does _anybody_ actually use shadow maps with point
light sources??? I gave up trying to do that after about 1 hour... :) In
order to do true shadowing with point sources, you need to calculate a
cube map of shadows -- doable, but not really quick even on GF3... however,
shadow maps with spot lights seem to work quite well.

Also, GF3 support fast FSAA (apparently, can't say till my card gets here)
that would reduce any 'sparkle' artifacts you currently see...

Leathal.

Re: [Algorithms] FloatToInt() assembly for Linux

[<notnot@xs...>]

Ulrich,

I found 'int FloatToInt(float f)' in the mesa sources, it is about
20% faster than your code:

inline int FloatToInt(float f) 
{
 int i;
 asm("fistpl %0" : "=m" (i) : "t" (f) : "st");
 return i;
}

Don't know much about the gcc inline asm syntax, but the code
performs a similar round to nearest integer, only faster. 

Erwin Driessens
 http://www.xs4all.nl/~notnot 


>Here's my code to do a similar thing.  I pieced the GCC stuff together
>from docs I found on the 'net using Google.
>
>inline int frnd(float f)
>// Rounds f to the nearest int.
>{
> int i;
>#ifndef LINUX
> _asm {
> fld f;
> fistp i;
> }
>#else // LINUX (really gcc)
> asm("flds %1; fistpl %0" : "=m" (i) : "m" (f));
>#endif // LINUX (really gcc)
> return i;
>}

RE: [Algorithms] Multi-precision math libraries

[Graham Rhodes <grhodes@se...>]

Graham said,

> > And that's all I'm going to say about that!

and Andy replied,

> Me too, although I grabbed the last word here, sorry. :)

Did you now? I do appreciate the friendly debate once in a while!

Cheers,

Graham

Re: [Algorithms] Distance between 2 OBBs

[Dave Eberly <eberly@ma...>]

From: "Charles Bloom" <cbloom@...>
> This is an iteration.  I believe that the points P_A and P_B
> tend towards the two closest points on A and B (obviously if
> there's a degeneracy of closest points then there will be
> an arbitrary selection based on the initial choice).  If the
> boxes point at each other with hard corner, the series converges
> after only one step.  If their closest points are at the sides
> of faces, then the two points will march along the faces to get
> closer to each other.  I'm not sure if this technique is useful
> at all (it does give a pretty close rough estimate), but I
> thought it was cute anyway.

Looks interesting, but I'd definitely want to check if it
has convergence behavior like steepest descent.  If it
does, better would be to use a conjugate gradient
approach that is recursive in dimension.  I am also curious
if GJK behaves like steepest descent or like conjugate
gradient.  I have looked at the conjugate gradient idea for
my next book, but have not had sufficient time to look
deeply into it.  The algorithm for distance between points,
linear components, and polygons at my web site I believe
is effectively the conjugate gradient idea.

> Why not just use the projections along the separating axes?
> I'm pretty sure that's what Dave Eberly does...

Eric Haines had posted something using separating axis
information.  I had posted a response to Pierre's question
in comp.graphics.algorithms (not posted to here) that
suggests using separation axis test information to localize
the search.  Text below:

-----
Here is an idea in 2D for oriented rectangles.  I have not thought about
complexities that arise when extending it to 3D.

Use the method of separating axes, two potential separating directions per
rectangle.  If all four do not separate, then distance is zero.  If one of
the directions separates, then you determined that by projecting the
rectangles onto a line with that direction and found that the projection
intervals are disjoint.  If the direction is D, an edge normal of one
rectangle, and if P is a point from the other rectangle that projects to the
interval end point that is closest to the interval of the first rectangle,
then project P onto a line with the other direction Perp(D) and project the
first rectangle onto that line to get interval [min,max].  Let projection of
P be v.  If v in [min,max], then P is the closest point to first rectangle.
If v < min, then the vertex of first rectangle corresponding to min is the
closest point to second rectangle.  Similar argument for v > max.  Computing
squared distance between point and oriented rectangle can be done very
quickly (P in coordinates of rectangle, squared distance between P and
rectangle can be accumulated a dimension at a time).

--
Dave Eberly
eberly@...
http://www.magic-software.com
http://www.wild-magic.com

Re: [Algorithms] Multi-precision math libraries

[Christopher Husband <chusband@ca...>]

I accidently erased your message, but if I remember right you asked for
suggestions on a library or news group.  Have you tried oonumerics.org?  I
imagine that either they will have links to a library that could help or
the mail list would have some more info.  

Chris

RE: [Algorithms] red faction / geomod

[Brian Smith <Brian.Smith@RealPage.com>]

As far as I know, no such "demos" exist.  Conceptually it's not too hard to
grasp though; do some searches on Volition's Red Faction message board and
you'll bring up some info on how they're doing things.  

From what I can tell, in the RF engine, you need to predefine what areas can
be "geomodded"... this is probably used by a preprocessing tool.  Ultimately
they're doing fairly simple and dirty CSG routines on the geometry.  They
might even prorate the calculations over a few frames by throwing in some
dust and "structure gibs" to hinder initial visibility (cube csg
subtract->add detail cuts->patch pvs).

If your engine is BSP-based than it would be a straightforward
implementation, but it's doable in any visibility schema.  Check out Dan
Royer's CSG tutorial here: http://aggrav8d.cfxweb.net/tutorials/csg.html

-Brian

-----Original Message-----
From: Matt Harmon [mailto:harmon@...]
Sent: Monday, March 12, 2001 12:43 PM
To: 'gdalgorithms-list@...'
Subject: [Algorithms] red faction / geomod


are there are links to demos with source that support the Geo Mod effects
talked about in Red Faction?  Geo Mod is where the environment's geometry
can deform due to explosions

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

Re: [Algorithms] Dynamic lighting and shadows in DOOM3

[Jake Cannell <jcannell@cs...>]

Oles V. Shishkovtsov wrote:

> Hi, developers.
> I think every one of yours had seen the Ge3 and DOOM3 presentation.
> I'd like to hear ideas how J.Carmack was able to calculate such high
quality
> lighting and shadowing effects in REALTIME ?
> I am simply impressed.

Hint: he's not using 'traditional' techniques. ;)

>
> For our current project we use 'traditional' techniques for shading. This
> means use of statically generated lightmaps and per-vertex lighting on
> dynamic models. 'Cause our models are typically high poly ones, we didn't
> use DOT3 lighting, it looks even better to light per vertex not per pixel.
> Shadows from dynamic stuff are shadowing textures projected onto static
> geometry, textures are genereted via render to texture technique.

In almost all cases, per pixel lighting looks vastly better than vertex
lighting.  Think of it this way: you could evalute perhaps 100 to 300
thousand vertex lighting calculations per frame, or you could evaluate
around 3 to 10 million pixel lighting calculations per frame.  Increasing
the lighting sampling density by an order of magnitude results in a
comparable increase in quality for most surfaces.  The only real exceptions
are very smooth surfaces.

You would think that you could just wait until hardware was fast enough so
that you could have triangles smaller than pixels, at which point the vertex
lighting quality should surpass texel/pixel lighting quality  (because
vertex lighting has 32-bit float precision per component) ... in reality you
have to pay enormous cost in properly oversampling multiple triangles per
pixel to get the same quality you would get from texel/pixel
lighting/shading.

Carmack's talked about what he's been working on for the new engine in his
.plan files and he's mentioned:
1.) Per pixel shading everywhere
2.) Dynamic shadowing on all surfaces using stencil techniques
3.) large number of rendering passes, sometimes dozens

Re: [Algorithms] Multi-precision math libraries

[Ron Hay <rhay@cy...>]

Ok, I'll answer several different emails in a lump here.

First off, yes I can do math(s), and yes I do realize 128-bit gives a
ridiculous amount of precision.  Next, yes I do understand that graphics
cards use floats, so I can't just hand it 128-bit data and expect it
to render away contentedly.  

The other questions can be responded to best by describing the system we
are developing.  Its basically a networked solar-system sim, where participants
can play around on the surface of planets (and other bodies) to watch
eclipses, see how Stonehenge works, sundials, etc, as well as view the solar
system in a position "above" the orbital plane to see all the orbit's shapes
and orientations, follow comets around, see how the sun wobbles from really
far away, etc.   If they were contained solely in the solar system, we could be 
fine with 64-bit doubles, since Pluto's orbit is 5.9x10^12 meters, and if we 
used millimeters, we'd still be at 10^15 and doubles are 10^19.  However, the 
Oort cloud is at roughly 7.5x10^18 millimeters, and there are a number of 
interesting objects that interact (in big time scales) with the solar system 
that are further out.  Plus we'd like to use the same system to be able to jump 
to galactic scale in the future (given funding).  

But even for the solar system, 64 bits is a bit tight.  So I guess the question
is, does anyone know of a 70-bit (or so) math library?  However, I figured it'd 
probably be easier to just ask for a 128-bit library (although a 96-bit would be
just dandy).  Silly me ;)

We currently get by on a prototype system that represents positions using floats (!)
but it has lots of nasty hacks in it.  We'd prefer the simple, clean approach of
defining a single coordinate system for all of our uses.  

So that's where we stand (the project is the "Astronomicon" and is funded by the
NSF).

Again I ask, does anyone know of a fast, robuts, simple 128-bit (or 96-bit, or 
74 and 3/16ths bit, or anything over 70 bit) library?  Or maybe know of a good
email list to re-ask the question?

Thanks!

  Ron Hay
  Cybernet Systems Corp

(I really hope I didn't screw up my math - that would be 128-bits of embarrassment)

RE: [Algorithms] Generating random rotation matrix fast

[Christer_Ericson@Playstation.sony.com]

Actually, for speed it's probably better to have a double-size table
where the sin and cos values are interleaved like so:

... sin(x-1), cos(x-1), sin(x), cos(x), sin(x+1), cos(x+1), ...

as you're only likely to suffer from one cache miss this way.


Also, note that there is an entry in Graphics Gems II on how to
generate random rotation matrices.


Christer Ericson
Sony Computer Entertainment, Santa Monica




                                                                                                                                                  
                    "Jason Dorie"                                                                                                                 
                    <jason.dorie@...>            To:     <gdalgorithms-list@...>                                  
                    Sent by:                                   cc:                                                                                
                    gdalgorithms-list-admin@...        Subject:     RE: [Algorithms] Generating random rotation matrix fast               
                    eforge.net                                                                                                                    
                                                                                                                                                  
                                                                                                                                                  
                    03/12/2001 10:57 AM                                                                                                           
                    Please respond to gdalgorithms-list                                                                                           
                                                                                                                                                  
                                                                                                                                                  





Jason,

  Cos(Angle) = Sin(Angle + 90 degrees)

  If your table is a power of two size, it's probably faster to do the (A +
90) & Mask than a sqrt()

Jason


-----Original Message-----
From: gdalgorithms-list-admin@...
[mailto:gdalgorithms-list-admin@...]On Behalf Of Jason
Zisk
Sent: Monday, March 12, 2001 10:47 AM
To: gdalgorithms-list@...
Subject: Re: [Algorithms] Generating random rotation matrix fast


Thanks to everyone who replied, a sin/cos table is the obvious answer that
I
totally didn't think of.  Lots of sneaky ideas from everyone but I think I
have the memory to spare for at least a sin table (then just calc cos, hope
the sqrt isn't too slow there).

Thanks again,

- Jason Zisk
- nFusion Interactive LLC

----- Original Message -----
From: "Thatcher Ulrich" <tu@...>
To: <gdalgorithms-list@...>
Sent: Monday, March 12, 2001 12:03 AM
Subject: Re: [Algorithms] Generating random rotation matrix fast


> On Mar 11, 2001 at 11:25 -0500, Jason Zisk wrote:
> > I have a ton of objects that all need to have a random rotation matrix
about
> > the Y axis created for them each frame.  If I use a standard axis+angle
to
> > matrix conversion (axis is 0,1,0 and angle is random) there is a sin
and
a
> > cos in there, and that kills performance.
> >
> > Is there a way to generate a rotation matrix like that with as few
> > operations as possible?  It will be used about 300 times per frame.
> >
> > I'm actually leaning towards creating a table of random matrices (or
> > quaternions, or even just the z vector) but there might be a better,
and
> > less memory intensive, way to solve this.
>
> sin/cos table...
>
> --
> Thatcher Ulrich <tu@...>
> ==  Soul Ride -- pure snowboarding for the PC -- http://soulride.com
> ==  real-world terrain -- physics-based gameplay -- no view limits



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


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

Re: [Algorithms] Multi-precision math libraries

[Andy Ross <andy@ne...>]

Graham Rhodes wrote:
> Andy wrote,
> > The intent of my harangue about 128 bit numbers was not to say that they
> > aren't useful at all, clearly they are.  The original poster, however,
> > seemed to be thinking that they'd be necessary to represent some level
> > of precision in a program.  This is the absurd part: NOTHING needs that
> > kind of accuracy; I believe the most accurately measured number in
> > science has its last significant digit somewhere around the 11th or 12th
> > place -- a 128 bit mantissa gives you 38 digits.
> 
> I actually disagree with your conclusion in theory. If you want to solve
> big, completely coupled problems that involve characteristic length scales
> that vary by many orders of magnitude, then it can be necessary to have very
> high precision. But in practice, I tend to agree. There are usually
> workarounds (e.g., decouple the problems or normalize so the length scales
> are collapsed) and the workarounds often lead to lower memory requirements,
> fewer calculations and 98% of the results of the big fully coupled problem
> for a billionth the cost.

We seem to be in disagreement more about words than facts here.  I
interpret your point above as something like:

"A naive implementation of solutions to some problems requires more
than double precision, but smarter code can make it work with 64 bit
doubles in most cases".

... and to my mind, your use of "theory" and "practice" are reversed.
I see the limitations of the naive implementations as the PRACTICAL
effect of limited precision math, and the fact that the problems CAN
be solved with less precision as a reflection of their INHERENT
(i.e. theoretical) characteristics.

It kinda comes down to arguing about how much precision the "problem"
needs vs. how much a particular algorithm/solution requires.  I view
the former as the important bit, you prefer to look at the latter.

That really was my point: that problems that truly require more
precision than an IEEE double are extrordinarily rare, and that a game
developer would be well advised to look at their problem more
carefully if they think they need a 128 bit math library.  They almost
certainly don't.

> And that's all I'm going to say about that!

Me too, although I grabbed the last word here, sorry. :)

Andy

-- 
Andrew J. Ross                NextBus Information Systems
Senior Software Engineer      Emeryville, CA
andy@...              http://www.nextbus.com
(510)420-3126                 Why Wait?

RE: [Algorithms] Dynamic lighting and shadows in DOOM3

[Scott LeGrand <varelse@be...>]

> I'd say he's using shadow buffers support for gf3 - not available in DX8 but
> in OpenGL extension from NVidia.

Nope, he said he's not using anything of the sort as he has never been satisfied
with their quality.  He then conceded he was going to check out the quality of 
those on the GeForce 3...

Quoting his .plan:
"The shadow map support is good to get in, but I am still unconvinced 
that a fully general engine can be produced with acceptable quality using 
shadow maps for point lights. I spent a while working with shadow 
buffers last year, and I couldn't get satisfactory results. I will revisit
that work now that I have GeForce 3 cards, and directly compare it with my 
current approach."

Scott

Re: [Algorithms] Generating random rotation matrix fast

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

On Mon, 12 Mar 2001, Jason Zisk wrote:

> Thanks to everyone who replied, a sin/cos table is the obvious answer that I
> totally didn't think of.  Lots of sneaky ideas from everyone but I think I
> have the memory to spare for at least a sin table (then just calc cos, hope
> the sqrt isn't too slow there).

I was going to say, and apparently I forgot to:

cos(angle) = sin(angle + PI/2)

so no need for a square root.

-Thatcher

RE: [Algorithms] red faction / geomod

[Tom Forsyth <tomf@mu...>]

I reckon GeoMod is a fancy name for "there's lots of things in the game that
can be blown up", which includes walls and other big structures like that.
Nothing _that_ fancy about it. You have to modify your portals system and AI
system to deal with bits that can be there or not be there (blown up), but
it's just the same problem as doors that can open and close.


Tom Forsyth - Muckyfoot bloke.

What's he up to now?
http://www.muckyfoot.com/startopia/cam.html



> -----Original Message-----
> From: Matt Harmon [mailto:harmon@...]
> Sent: 12 March 2001 18:43
> To: 'gdalgorithms-list@...'
> Subject: [Algorithms] red faction / geomod
> 
> 
> are there are links to demos with source that support the Geo 
> Mod effects
> talked about in Red Faction?  Geo Mod is where the 
> environment's geometry
> can deform due to explosions

RE: [Algorithms] Generating random rotation matrix fast

[Norman Vine <nhv@ca...>]

Jason Zisk writes:
>
>Thanks to everyone who replied, a sin/cos table is the obvious
>answer that I totally didn't think of.  Lots of sneaky ideas from everyone
>but I think I have the memory to spare for at least a sin table (then just
>calc cos, hope the sqrt isn't too slow there).

why do a sqrt()
<when in integer degrees>
sin(a) = cos((a+90)%360)

Norman Vine

Re: [Algorithms] Generating random rotation matrix fast

[Kent Quirk <kent_quirk@co...>]

Jason Zisk wrote:
> Thanks to everyone who replied, a sin/cos table is the 
> obvious answer that I totally didn't think of.  Lots of sneaky 
> ideas from everyone but I think I
> have the memory to spare for at least a sin table (then just calc 
> cos, hope the sqrt isn't too slow there).

WAIT! If you have a sin table...you have the cos table, remember? You
just have to offset the angle. Don't do the sqrt.

-- 
-----------------------------------------------------------------------
Kent Quirk                   | MindRover: "Astonishingly creative."
Game Architect               | Check it out!
kent_quirk@...      | http://www.mindrover.com/
_____________________________|_________________________________________

Re: [Algorithms] Generating random rotation matrix fast

[Jeffrey Rainy <jrainy@dy...>]

> Thanks to everyone who replied, a sin/cos table is the obvious answer that
I
> totally didn't think of.  Lots of sneaky ideas from everyone but I think I
> have the memory to spare for at least a sin table (then just calc cos,
hope
> the sqrt isn't too slow there).

Isn't sin( x ) == cos( x-90 ) ?
Then you would need only one table and a add plus some clipping/warping
around, one quarter of the time.

[Algorithms] red faction / geomod

[Matt Harmon <harmon@ui...>]

are there are links to demos with source that support the Geo Mod effects
talked about in Red Faction?  Geo Mod is where the environment's geometry
can deform due to explosions

RE: [Algorithms] Generating random rotation matrix fast

[Jamie Fowlston <jfowlston@re...>]

Also remember sin( theta ) = cos( theta - pi / 2 ), so you can use the same
LUT for each :)

Jamie


-----Original Message-----
From: Jason Zisk [mailto:ziskj@...]
Sent: 12 March 2001 18:47
To: gdalgorithms-list@...
Subject: Re: [Algorithms] Generating random rotation matrix fast


Thanks to everyone who replied, a sin/cos table is the obvious answer that I
totally didn't think of.  Lots of sneaky ideas from everyone but I think I
have the memory to spare for at least a sin table (then just calc cos, hope
the sqrt isn't too slow there).

Thanks again,

- Jason Zisk
- nFusion Interactive LLC

----- Original Message -----
From: "Thatcher Ulrich" <tu@...>
To: <gdalgorithms-list@...>
Sent: Monday, March 12, 2001 12:03 AM
Subject: Re: [Algorithms] Generating random rotation matrix fast


> On Mar 11, 2001 at 11:25 -0500, Jason Zisk wrote:
> > I have a ton of objects that all need to have a random rotation matrix
about
> > the Y axis created for them each frame.  If I use a standard axis+angle
to
> > matrix conversion (axis is 0,1,0 and angle is random) there is a sin and
a
> > cos in there, and that kills performance.
> >
> > Is there a way to generate a rotation matrix like that with as few
> > operations as possible?  It will be used about 300 times per frame.
> >
> > I'm actually leaning towards creating a table of random matrices (or
> > quaternions, or even just the z vector) but there might be a better, and
> > less memory intensive, way to solve this.
>
> sin/cos table...
>
> --
> Thatcher Ulrich <tu@...>
> ==  Soul Ride -- pure snowboarding for the PC -- http://soulride.com
> ==  real-world terrain -- physics-based gameplay -- no view limits



_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-list@...
http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
-Virus scanned and cleared ok

RE: [Algorithms] Generating random rotation matrix fast

[Jason Dorie <jason.dorie@bl...>]

Jason,

  Cos(Angle) = Sin(Angle + 90 degrees)

  If your table is a power of two size, it's probably faster to do the (A +
90) & Mask than a sqrt()

Jason


-----Original Message-----
From: gdalgorithms-list-admin@...
[mailto:gdalgorithms-list-admin@...]On Behalf Of Jason
Zisk
Sent: Monday, March 12, 2001 10:47 AM
To: gdalgorithms-list@...
Subject: Re: [Algorithms] Generating random rotation matrix fast


Thanks to everyone who replied, a sin/cos table is the obvious answer that I
totally didn't think of.  Lots of sneaky ideas from everyone but I think I
have the memory to spare for at least a sin table (then just calc cos, hope
the sqrt isn't too slow there).

Thanks again,

- Jason Zisk
- nFusion Interactive LLC

----- Original Message -----
From: "Thatcher Ulrich" <tu@...>
To: <gdalgorithms-list@...>
Sent: Monday, March 12, 2001 12:03 AM
Subject: Re: [Algorithms] Generating random rotation matrix fast


> On Mar 11, 2001 at 11:25 -0500, Jason Zisk wrote:
> > I have a ton of objects that all need to have a random rotation matrix
about
> > the Y axis created for them each frame.  If I use a standard axis+angle
to
> > matrix conversion (axis is 0,1,0 and angle is random) there is a sin and
a
> > cos in there, and that kills performance.
> >
> > Is there a way to generate a rotation matrix like that with as few
> > operations as possible?  It will be used about 300 times per frame.
> >
> > I'm actually leaning towards creating a table of random matrices (or
> > quaternions, or even just the z vector) but there might be a better, and
> > less memory intensive, way to solve this.
>
> sin/cos table...
>
> --
> Thatcher Ulrich <tu@...>
> ==  Soul Ride -- pure snowboarding for the PC -- http://soulride.com
> ==  real-world terrain -- physics-based gameplay -- no view limits



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

Re: [Algorithms] Generating random rotation matrix fast

[Jason Zisk <ziskj@op...>]

Thanks to everyone who replied, a sin/cos table is the obvious answer that I
totally didn't think of.  Lots of sneaky ideas from everyone but I think I
have the memory to spare for at least a sin table (then just calc cos, hope
the sqrt isn't too slow there).

Thanks again,

- Jason Zisk
- nFusion Interactive LLC

----- Original Message -----
From: "Thatcher Ulrich" <tu@...>
To: <gdalgorithms-list@...>
Sent: Monday, March 12, 2001 12:03 AM
Subject: Re: [Algorithms] Generating random rotation matrix fast


> On Mar 11, 2001 at 11:25 -0500, Jason Zisk wrote:
> > I have a ton of objects that all need to have a random rotation matrix
about
> > the Y axis created for them each frame.  If I use a standard axis+angle
to
> > matrix conversion (axis is 0,1,0 and angle is random) there is a sin and
a
> > cos in there, and that kills performance.
> >
> > Is there a way to generate a rotation matrix like that with as few
> > operations as possible?  It will be used about 300 times per frame.
> >
> > I'm actually leaning towards creating a table of random matrices (or
> > quaternions, or even just the z vector) but there might be a better, and
> > less memory intensive, way to solve this.
>
> sin/cos table...
>
> --
> Thatcher Ulrich <tu@...>
> ==  Soul Ride -- pure snowboarding for the PC -- http://soulride.com
> ==  real-world terrain -- physics-based gameplay -- no view limits

Re: [Algorithms] Distance between 2 OBBs

[Charles Bloom <cbloom@cb...>]

Here's an interesting algorithm :

start with any point in Box A
call this point P(0)

clamp point P(n) into the space of Box B
   (this means, transform into the space where B is axis-aligned,
    and then clamp xyz to the extents of B).
   this makes P(n)_B
clamp P(n)_B into the space of Box A
   this makes P(n)_A

This is an iteration.  I believe that the points P_A and P_B
tend towards the two closest points on A and B (obviously if
there's a degeneracy of closest points then there will be
an arbitrary selection based on the initial choice).  If the
boxes point at each other with hard corner, the series converges
after only one step.  If their closest points are at the sides
of faces, then the two points will march along the faces to get
closer to each other.  I'm not sure if this technique is useful
at all (it does give a pretty close rough estimate), but I
thought it was cute anyway.

Why not just use the projections along the separating axes?
I'm pretty sure that's what Dave Eberly does...

----------------------------------------------------
Charles Bloom    cbloom@...    http://www.cbloom.com

RE: [Algorithms] Multi-precision math libraries

[Graham Rhodes <grhodes@se...>]

Andy wrote,

> The intent of my harague about 128 bit numbers was not to say that they
> aren't useful at all, clearly they are.  The original poster, however,
> seemed to be thinking that they'd be necessary to represent some level
> of precision in a program.  This is the absurd part: NOTHING needs that
> kind of accuracy; I believe the most accurately measured number in
> science has its last significant digit somewhere around the 11th or 12th
> place -- a 128 bit mantissa gives you 38 digits.

I actually disagree with your conclusion in theory. If you want to solve
big, completely coupled problems that involve characteristic length scales
that vary by many orders of magnitude, then it can be necessary to have very
high precision. But in practice, I tend to agree. There are usually
workarounds (e.g., decouple the problems or normalize so the length scales
are collapsed) and the workarounds often lead to lower memory requirements,
fewer calculations and 98% of the results of the big fully coupled problem
for a billionth the cost.

And that's all I'm going to say about that!

Graham Rhodes

RE: [Algorithms] Multi-precision math libraries

[Graham Rhodes <grhodes@se...>]

Tom wrote,

> Surely they fall into two categories:
>
> (1) Stable systems that don't accumulate errors, for which
> double-precision
> is fine.
>
> (2) Chaotic systems that do accumulate errors, and in very dramatic ways
> (such as the bovine vortex flight simulator you mention). However, the
> problem here is not that your intermediate results don't have enough
> precision, but that you can never have enough precision, especially in the
> starting conditions. Surely if your simulator requires 128bits of
> precision
> to give meaningful results, then it's useless for showing what happens in
> the real world because the movement of my eyeballs as I read this message
> will put off your experiment.

Yes, in terms of physical systems, there are both stable systems and chaotic
or otherwise unstable systems.

I should have explained that by "error" I meant numerical
error----truncation and roundoff----not physical error or chaos. It is
possible to simulate some (but maybe not all) chaotic or unstable physical
systems using a numerical method that does not exhibit unbounded numerical
error growth even at lower precisions, and so physical chaos does not
necessarily mean there will be floating point precision problems---in terms
of error growth. (Although it is much harder, sometimes impossible, to find
an appropriate method when the physical system is unstable and usually the
method will be applicable only for simulating a small portion of the system
lifetime.)

I agree with your comment regarding the general uselessness of very high
precision. There are so many scientists in universities and research labs
doing research to get the flame shape just right or slightly improve the
shock wave resolution. Ten thousand times the effort for 1% gain in results.
I'd like to think there is a more practical way. The treatment of
uncertainties has an important role in real-world engineering.

> So while double-precision may not give _correct_ results in any absoloute
> mathematical sense, it will give representative results.

Yes, absolutely. The representative results maybe zero or constant for
low-priority length scales.

>
>
> On the other hand, there may well be actual applications that do require >
> double-precision. Cryptographics requires very large numbers.

Yes, again true. Actually, fluid dynamics situations such as the bovine one
can require > double-precision. Of course, probably no one would study the
fluid dynamics around a flying cow, but replace cow with airplane modeled
from fine detail in the boundary layer to global movement in an atmosphere,
and you have another actual application.

My head hurts,

Graham Rhodes

Re: [Algorithms] Dynamic lighting and shadows in DOOM3

[Keith Z. Leonard <keithle@dr...>]

That would be my guess also.
If you look at the OpenGL SDK recently
released by nVidia, you will see that they
are supporting 2 SGIX extensions that are
involved in shadow mapping.  Also they have
some downloadable demos of shadow mapping
running in OpenGL.

SGIX_depth_texture
and
SGIX_shadow
are the extensions I believe.

I would assume that the lighting is probably hardware
lighting, since it is also dynamic.

Keith

MartinV wrote:

> HI
>
> I'd say he's using shadow buffers support for gf3 - not available in DX8 but
> in OpenGL extension from NVidia.
>
> Dream
>
> -----Original Message-----
> From: oles [mailto:oles@...]
> Sent: 23 February 2001 10:29
> To: gdalgorithms-list@...
> Subject: [Algorithms] Dynamic lighting and shadows in DOOM3
>
> Hi, developers.
> I think every one of yours had seen the Ge3 and DOOM3 presentation.
> I'd like to hear ideas how J.Carmack was able to calculate such high quality
> lighting and shadowing effects in REALTIME ?
> I am simply impressed.
>
> For our current project we use 'traditional' techniques for shading. This
> means use of statically generated lightmaps and per-vertex lighting on
> dynamic models. 'Cause our models are typically high poly ones, we didn't
> use DOT3 lighting, it looks even better to light per vertex not per pixel.
> Shadows from dynamic stuff are shadowing textures projected onto static
> geometry, textures are genereted via render to texture technique.
>
> As I understand from presentation, whole lighting / shadowing in Doom3 is
> dynamically calculated in realtime.
> How it can be done, even if we have such powerfull instruments as vertex and
> pixel shaders? Even if we has this incredible horsepower of GeForce3?
>
> Oles V. Shishkovtsov
> GSC GameWorld
> oles@...
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list