[Algorithms] Bounding sphere of spheres

[T.M. Evans <tmadoc@ti...>]

Is there any stupidly fast method of finding the bounding sphere of several
spheres? Ashamed to admit it, I first find the bounding box and then the
sphere from the box centre. Surely there are better ways. I'm not overly
concerned with accuracy, slightly loose spheres would do fine if it's fast.

Cheers,
Madoc

RE: [Algorithms] indexing...

[Jon Watte <hplus@mi...>]

> Well, I know what I'm doing sounds ghastly..but I just can't think of
> another way to do it.

That's because there is no other way to do it with current hardware.

Also, don't forget that when you transform the vertex position, you should 
also be transforming the normals (either _fully_ correctly by regenerating 
them from surrounding mesh properties, or using any one of a number of 
hackish short cuts recently discussed on this list).

Given the write behaviour of AGP memory and all that, I've found it much 
preferrable to put verts and normals in one interleaved buffer and just 
rip through them in order, with auxiliary (non-skinned) vertex data in 
another buffer using the same set of indices.

Cheers,

				/ h+

RE: [Algorithms] BVH compression

[Jon Watte <hplus@mi...>]

> I know which one hits less memory, fits in VertexShaders, requires fewer
> passes over the data and has fewer restrictions on the type of animations
> allowed.

Vertex shaders don't really have constant space for a sufficient number of 
bones.

Of course, by the time we have real displacement maps, that might have 
improved, too :-)

Cheers,

				/ h+

Re: [Algorithms] Constant-rate physics. was: runge Kutta

[Erwin de Vries <erwin@vo...>]

>Compared to those, the minor hassle of doing some linear interpolation when
>drawing the scene (you need to interpolate between adjacent "physics"
frames
>to reduce aliasing problems) is nothing. I'm sure this has been discussed
at
>length in the archives if you want more info.

But that forces you to store the position and rotation for every object
twice. What we do is have a somewhat constant physics framerate. The lower
limit is 30fps. When a frame takes longer to render a physics update of
1/60second is done, and then its checked again. Not completely perfect of
course, but it takes care of the lower limit, and you get away without
lerping between 2 frames.

Erwin

[Algorithms] indexing...

[Andrew <andrew@aw...>]

hi!

I was just wondering if anyone had a good solution to tackling this
problem...

I'm doing soft skinning on the vertices in a mesh, however I'm using
an indexbuffer to draw the polygons.  Since its in an indexbuffer I've had
to duplicate vertices which are not unique(same normal/uv).  I don't want
to perform the skinning calculation on any more vertices than I have to, so
after I do the skinning on the unique vertices I copy the results to the
nonunique
vertices, before uploading them to the vertexbuffer.  Surely there is
another way
to do this without doing this copying.  I thought perhaps if I used 3
vertexbuffers (xyz, normals, uvs)
then each would have a seperate indexbuffer..however this doesn't seem to be
the case.

Well, I know what I'm doing sounds ghastly..but I just can't think of
another way to do it.
Hope you understand the problem I'm trying to explain :)

Andrew

=---=---=---=---=---...---=---...___________________________________________
__
The next two parts are using full processor time so there is no music -
wish/majic12

RE: [Algorithms] BVH compression

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

...and actually thinking about it, when everyone moves to using low-poly
meshes and displacement maps, rather than high-poly meshes, this sort of
stuff may become very relevant. After all, once you have displacement maps,
the only reason have vertices on your base mesh is so that they can move
because of animation. So I reckon the ratio of bones to vertices will become
fairly constant, and something low like 4 or 5.

So the choice is:

-doing all the bone interpolation, renormalisation and blending.

-doing 4 or 5 times as many C-R splines on a few vertex positions (and
normals).

I know which one hits less memory, fits in VertexShaders, requires fewer
passes over the data and has fewer restrictions on the type of animations
allowed.

On the other hand, you can't do IK on a bunch of verts, and you can't apply
the same anims to different meshes unless they have the same underlying base
mesh. And doing any anim blending (rather than just straight replay)
probably muddies the waters somewhat as well. Horses for courses.

Tom Forsyth - Muckyfoot bloke.

What's he up to now (and can I have a go)?
http://www.eidosinteractive.com/downloads/search.html?gmid=86

> -----Original Message-----
> From: Tom Forsyth [mailto:tomf@...]
> Sent: 28 August 2001 19:07
> To: gdalgorithms-list@...
> Subject: RE: [Algorithms] BVH compression
> 
> 
> Agreed. StarTopia isn't a 3D RTS, but it has the same sort of graphics
> problems - lots of low-poly models. We did finally go for 
> using bones, but
> I'm still not sure it wouldn't have been far quicker in CPU 
> power and taken
> less memory to just store the vertex-by-vertex positions 
> (compressed) in
> each keyframe and done a simple Catmull-Rom spline 
> interpolation between the
> nearest three when drawing.
> 
> As you say, smartness warp-around.
> 
> Tom Forsyth - Muckyfoot bloke.
> 
> What's he up to now (and can I have a go)?
> http://www.eidosinteractive.com/downloads/search.html?gmid=86
> 
> > -----Original Message-----
> > From: Emmanuel Astier [mailto:emmanuel.astier@...]
> > Sent: 28 August 2001 13:40
> > To: gdalgorithms-list@...
> > Subject: RE: [Algorithms] BVH compression
> > 
> > 
> > > Is there any valid reason to use vertex animation these days?
> > >
> > > Erwin
> > 
> > When you're working on a 3D RTS with a lot of characters, you don't
> > always want to compute skeleton animations...
> > 
> > Emmanuel
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Constant-rate physics. was: runge Kutta

[Ray <ray@gu...>]

Tom Forsyth wrote:
> 
> Oh yes indeed. Some people like to run their physics at variable time rates,
> according to how fast the rendering takes, but I think they are in the
> minority. Having a fixed-size timestep (though on a #define or whatever) has
> loads of advantages:
> 
> -Networking.
> -Reproducibility of bugs & game recordings.
> -Lots of FP optimisations (multiplies by constants, etc).
> -No stability problems when the time periods get too long.
> -No rounding problems when the time periods get too short.
> 
> ...etc.
> 
> Compared to those, the minor hassle of doing some linear interpolation when
> drawing the scene (you need to interpolate between adjacent "physics" frames
> to reduce aliasing problems) is nothing. I'm sure this has been discussed at
> length in the archives if you want more info.
> 
> Tom Forsyth - Muckyfoot bloke.
> 
> What's he up to now (and can I have a go)?
> http://www.eidosinteractive.com/downloads/search.html?gmid=86
> 

Heh sorry to barge in on your thread here, but we currently use
variable-frame physics, everything is done in a single game loop, and
have thought of changing the physics over to fixed-timestep physics.

The main reason is not for collision stability, but for network
prediction. We have homing missiles that a client shoots out and to
avoid many many update packets the homing missiles are calculated on all
the clients machines. You all can see how easily the missiles would be
in different places on different machines based on their framerates. 

We were thinking of either running the physics in a different thread or
having the possibility of multiple physics timesteps happening inbetween
a single frame, like if the rendering is 2/3 as fast as the physics or
something, every other render frame 2 physics frames get calculated.
That case would probably only happen if the user is getting very crappy
framerates which is very possible with our different render quality
settings.

- Ray

RE: [Algorithms] BVH compression

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

Agreed. StarTopia isn't a 3D RTS, but it has the same sort of graphics
problems - lots of low-poly models. We did finally go for using bones, but
I'm still not sure it wouldn't have been far quicker in CPU power and taken
less memory to just store the vertex-by-vertex positions (compressed) in
each keyframe and done a simple Catmull-Rom spline interpolation between the
nearest three when drawing.

As you say, smartness warp-around.

Tom Forsyth - Muckyfoot bloke.

What's he up to now (and can I have a go)?
http://www.eidosinteractive.com/downloads/search.html?gmid=86

> -----Original Message-----
> From: Emmanuel Astier [mailto:emmanuel.astier@...]
> Sent: 28 August 2001 13:40
> To: gdalgorithms-list@...
> Subject: RE: [Algorithms] BVH compression
> 
> 
> > Is there any valid reason to use vertex animation these days?
> >
> > Erwin
> 
> When you're working on a 3D RTS with a lot of characters, you don't
> always want to compute skeleton animations...
> 
> Emmanuel

RE: [Algorithms] BVH compression

[Senftner, Blake <bsenftner@pa...>]

>=20
> Several tendencies to begin with:
> 1) storing vertices, Quake-style
> 2) storing sampled PRS for the skeleton only
> 3) storing keyframes
>=20
>=20
> What are you using as a starting point, people?
>=20

Two reference points:=20

Engine at work- based upon exported data from SoftImage & Maya.
A variation of method 2: storing position & rotation samples=20
only, no scales allowed. Plus a really novel animation tech
I can't discuss.

Engine at home- based upon exported data from 3DSMAX.
A variation of method 3: an initial scale only (per model),
Keyframes for rotation & position only, with analysis of the
keys for lowest memory spline representation. Typically I get
rotation keys only (except for the root node's translation.)
I originally intended to be able to switch spline representations
within arbitary keys- but the data requirements were so small
already, I put that off in favor of more pressing features.

Note that most bones don't translate after their initial positioning,
so those become something I call a "static spline"- which is a
spline interface that always returns the same value.

The analysis of the splines chooses the lowest memory representation
within a supplied error tolerance between linear, cardinal, bezier
and TCB. This also supports key dropping during the analysis, since
I work with motion capture data as well as animator created motion.

Last, a big reason that I based my home engine on BonesPro2 was the
ability to work with keyframes. Character Studio seems to be quite
game unfriendly in multiple ways. I picked up LifeForms for their
walk generator (and huge mocap library) plus BonesPro2 for much less
than Character Studio alone.

-Blake

RE: [Algorithms] Constant-rate physics. was: runge Kutta

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

Oh yes indeed. Some people like to run their physics at variable time rates,
according to how fast the rendering takes, but I think they are in the
minority. Having a fixed-size timestep (though on a #define or whatever) has
loads of advantages:

-Networking.
-Reproducibility of bugs & game recordings.
-Lots of FP optimisations (multiplies by constants, etc).
-No stability problems when the time periods get too long.
-No rounding problems when the time periods get too short.

...etc.

Compared to those, the minor hassle of doing some linear interpolation when
drawing the scene (you need to interpolate between adjacent "physics" frames
to reduce aliasing problems) is nothing. I'm sure this has been discussed at
length in the archives if you want more info.

Tom Forsyth - Muckyfoot bloke.

What's he up to now (and can I have a go)?
http://www.eidosinteractive.com/downloads/search.html?gmid=86

> -----Original Message-----
> From: Idahosa Edokpayi [mailto:idahosae@...]
> Sent: 27 August 2001 20:36
> To: gdalgorithms-list@...
> Subject: RE: [Algorithms] runge Kutta
> 
> 
> So as a rule, most simulations use time steps that are 
> independent of other
> systems? As in the Graphics subsystem runs at 80 HZ and the physics
> simulation runs at say 25 hz with a fixed time step?
> 
> Idahosa Edokpayi
> 
> -----Original Message-----
> From: gdalgorithms-list-admin@...
> [mailto:gdalgorithms-list-admin@...]On 
> Behalf Of Jeff
> Lander
> Sent: Monday, August 27, 2001 1:18 PM
> To: gdalgorithms-list@...
> Subject: RE: [Algorithms] runge Kutta
> 
> 
> Well I know the car game I am on (that I am not doing the 
> physics) uses a
> pure forward Euler and they use pretty stiff springs for the 
> suspension to
> connect rigid bodies.
> 
> The way they keep it from blowing up is use tiny timesteps 
> and reset it as
> you suggest if it starts going out of control.  I offered to 
> help out and
> put a better integrator in for them as a drop in replacement. 
>  But their
> physics guy is "certain" that they are fine.  Of course when 
> it turns up
> that the physics is taking way too long, they will probably 
> want to revisit
> that decision :)  But my job on the project is graphics so I 
> can only offer.
> 
> It is funny the number of times I have looked at source code where the
> physics has a comment like "TODO: using braindead Euler for 
> now, need to
> replace it with a better integrator".  It's almost like 
> people are lifting
> the same rigid body code as a starting point.  :)
> 
> -Jeff
> 
> At 01:17 PM 8/27/2001 -0400, you wrote:
> > > Judging by the number of developers I have talked to that are
> > > still using forward Euler (even for connected rigid bodies in at
> > > least one car game...yikes) I think just moving to something like
> > > the predictor-corrector I use or midpoint would be a big step.
> >
> >Pure forward Euler is unstable in the presence of *any* spring-like
> behavior
> >at all. Its probably almost dumb luck that some of these 
> simulators don't
> >blow up more often. I suspect that people aren't actually 
> implementing pure
> >forward Euler. It must be a modified method that changes 
> stability just a
> >bit for the better. Either that or system stiffness is not 
> very high and
> >integration is stopped or restarted before things go totally haywire.
> >
> >Graham
> 
> 
> _______________________________________________
> 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] BVH compression

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

> From: Pierre Terdiman [mailto:p.terdiman@...]
> 
> > It's written by Miguel Gomez, so you could search for an online
> > version by him.  It only works for AABB trees.
> 
> Could you explain his method ? (there's no online version apparently)

You could always buy the book. (ever so slightly biased, being a contributor
and all, but...)

[snip]

> Pierre


Tom Forsyth - Muckyfoot bloke.

What's he up to now (and can I have a go)?
http://www.eidosinteractive.com/downloads/search.html?gmid=86

RE: [Algorithms] runge Kutta

[Patrick E. Hughes <hughes@tr...>]

>Also you don't want the physics locked to the graphics framerate in any
case because a lot of things can slow or speed up the graphics rendering
but you don't want the gameplay to change depending on the visual 

Plus, and you know it will happen, a producer will come to you and say "Why
aren't we doing bullet-time like matrix?"

Always nice to keep your options open.

Re: [Algorithms] BVH compression

[Conor Stokes <cstokes@tp...>]

This method doesn't just apply to aabbs actually. I recall some paper
quantising spheres relative to another (was it the Q-splat paper?) in a
sphere tree. A sphere can be turned into a cube with diameter length edges
to encode any sphere centre points and you can easily represent the radius
relative to the radius of the last sphere. That give you 4 0->1 values per
sphere that you can easily quantize down to bytes (if you conservatively
remap the sphere a tiny bit). A sphere bounding triangles could also be
represented as indices to 2 vertices.

As shown in the I-Collide paper, you can also obtain the same cube for an
OBB (meaning you can quantify in terms of that).

Conor Stokes


> Damn!
> ...sigh.... That's what I called "tree coherence".
> Wanted to add this in Opcode. But he's been faster than me.
>
> Damn!
>
>
> ...probably gonna drink my way into oblivion now...
>
>
> ----- Original Message -----
> From: Charles Bloom <cbloom@...>
> To: <gdalgorithms-list@...>
> Sent: Monday, August 27, 2001 9:38 PM
> Subject: Re: [Algorithms] BVH compression
>
>
> >
> > It's quite simple.  He makes a binary AABB tree.  At the root
> > node, you store a full floating-point AABB.  At each node, you
> > must define the two AABB's of the two children.  He takes
> > advantage of the way the tree is defined :
> >
> > 1. The two children boxes are contained in the parent
> > 2. The extents of the parent are defines by the union of the children
> >
> > So, #1 means that you can store the child min/max's as a fraction
> > (0->1) of the parent extents.  This fraction you can then quantize to
> > an byte (you just have to round down the min, and round up the max).
> >
> > #2 means that of the four corners for the two child boxes, you know
> > that the two corners of the parent will be a part.  So, you only need
> > to define 6 new floating values, and the other 6 come from the parent.
> > He stores a bit-mask to indicate which values come from the parent.
> >
> > The result is that an AABB node is 11 bytes (or so).
> >
> > At 09:06 PM 8/27/2001 +0200, you wrote:
> > > > It's written by Miguel Gomez, so you could search for an online
> > > > version by him.  It only works for AABB trees.
> > >
> > >Could you explain his method ? (there's no online version apparently)
> >
> >
> > ----------------------------------------------------
> > Charles Bloom    cbloom@...    http://www.cbloom.com
> >
> >
> > _______________________________________________
> > 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] BVH compression

[Odin Jensen <odin@ps...>]

> Is there any valid reason to use vertex animation these days?
>
> Erwin

You can also easily remove redundant frames which would occure normally
by interpolation so it doesn't have to take up that much space

Odin

RE: [Algorithms] BVH compression

[Emmanuel Astier <emmanuel.astier@wi...>]

> Is there any valid reason to use vertex animation these days?
>
> Erwin

When you're working on a 3D RTS with a lot of characters, you don't
always want to compute skeleton animations...

Emmanuel




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

RE: [Algorithms] BVH compression

[Awen Limbourg <alimbourg@ed...>]

>1) storing vertices, Quake-style
>2) storing sampled PRS for the skeleton only
>3) storing keyframes

>What are you using as a starting point, people?

Mmmh. An Hybrid way between 2 and 3 ?
We are using totally insane animation data from 3rd Party IKsolver/mad
animators/Mocap  ('insane' means: a very big skeleton (90 nodes) animated
with many many many keys).
When exporting anims, we spend some time in packing theses TRS keys for each
skeleton node : packing is working independantly on each TRS component. We
compute 'what is animated' from our reference skeleton and 'what is static
all along animation'. Finally we are packing animated datas using some
interpolation tests with ADAPTIVE (depending of the node contribution in the
skeleton) error bounds for each node, for each transform component.

During animation, a node instant TRS key is computed into a common 'perfect
to blend' transform representation (Quaternion for rot, Vector3 otherwise)

Well, it works not so badly, and produces 'normal weighted' files. Comparing
to the original mocap-ed one :)

Re: [Algorithms] BVH compression

[Erwin de Vries <erwin@vo...>]

>> Haven't had time to read the book yet and by the subject I thought Pierre
>was talking about compressing motion capture files.
>>
>> We need a new acronym for bounding volumes because I think Biovision
>trademarked BVH :)
>>
>> Luckily I am interested in both topics...
>
>Actually I'm interested in both as well. And while we're at it, let's
>discuss this as well. So, what's the usual way to deal with big amounts of
>animation data ?
>
>Several tendencies to begin with:
>1) storing vertices, Quake-style
>2) storing sampled PRS for the skeleton only
>3) storing keyframes
>
>1) is obsolete, I just mention it for historical reasons, let's say.
>
>2) is what I do out of Character Studio, because AFAIK CS doesn't expose
>keyframes.
>
>3) would be the best regarding compression, but I don't feel like doing 50
>hybrid bezier spline interpolations each frame, for the 50 bones of a
single
>character. That's ok for a camera, probably not for a bone. (because once
>the original PRS has been interpolated you still have to perform motion
>blending and/or IK on top of it, for example).
>
>What are you using as a starting point, people?

We use version 2. We really didnt want to, but in our game there isnt much
animationdata so we can get away with it. Our artists make the animations in
this really cool program called Animation Master (www.hash.com). It basicly
has 3 different interpolators for its keyframes which can be easlyly
reproduced at runtime. Euler interpolate, Quaternion slerp, and Vector (i
think i understand how it works). Like i said before our game just uses 30
samples/second, and it even gets away without interpolating them. (Low poly
models).

>Then, regardless of the method used, you want to compress the data.
>Compressing with 1) is easy, just do like Quake. With 2), you can probably
>get good results with simple quantization + delta + RLE, as usual. Can we
do
>really better ? Same story with 3), but the quantization errors are
probably
>more sensible since a single error on a given keyframe actually changes all
>values inbetween.

Is there any valid reason to use vertex animation these days?

Erwin

Re: [Algorithms] BVH compression

[Pierre Terdiman <p.terdiman@wa...>]

> Haven't had time to read the book yet and by the subject I thought Pierre
was talking about compressing motion capture files.
>
> We need a new acronym for bounding volumes because I think Biovision
trademarked BVH :)
>
> Luckily I am interested in both topics...

Actually I'm interested in both as well. And while we're at it, let's
discuss this as well. So, what's the usual way to deal with big amounts of
animation data ?

Several tendencies to begin with:
1) storing vertices, Quake-style
2) storing sampled PRS for the skeleton only
3) storing keyframes

1) is obsolete, I just mention it for historical reasons, let's say.

2) is what I do out of Character Studio, because AFAIK CS doesn't expose
keyframes.

3) would be the best regarding compression, but I don't feel like doing 50
hybrid bezier spline interpolations each frame, for the 50 bones of a single
character. That's ok for a camera, probably not for a bone. (because once
the original PRS has been interpolated you still have to perform motion
blending and/or IK on top of it, for example).

What are you using as a starting point, people?


Then, regardless of the method used, you want to compress the data.
Compressing with 1) is easy, just do like Quake. With 2), you can probably
get good results with simple quantization + delta + RLE, as usual. Can we do
really better ? Same story with 3), but the quantization errors are probably
more sensible since a single error on a given keyframe actually changes all
values inbetween.

That's one of the thing I always want to try but never do because time is
lacking. I'd be interested to know what are the standard methods here. I
suppose that's not a very active / hot topic anyway, since there aren't many
games out there with that amount of animation data. Textures usually take
most of the space. I recently reverse-engineered animations from Oni, and
they seem to use quantized keyframed euler angles. (from what I found, for
the rotation tracks you get a number of frames followed by 3 shorts for a
given bone) They admittedly have a lot more animations than your average FPS
(there's something insane like 1700 character animation chunks in the first
data file!), so I guess they had no choice but compressing them.


Pierre

Re: [Algorithms] CVS line feeds

[Devrim Erdem <devrim@in...>]

It should be sth with the settings of the server. We have CVS Server on linux
and VC6 on PC with WinCVS. There is no problem. maybe the CVSNT server thinks
that it is serving to a unix system.

Oscar Blasco wrote:

> Hi,
>
> We are using CVS for version control and VC6 for programming. We have to
> deal every day with an small problem that is very annoying...The problem
> happens when we load a source file inside VC6 after a merging was done with
> CVS, it reports a missing line feeds and it adds them, putting spaces
> between lines...Does anyone know how to handle this issue? We are using
> CVSNT for the server.
>
> Thanks in advance,
>
> Oscar Blasco.
>
> P.S.: I know...this is not an algorithm related stuff...but I think I can
> find some help here too.... or hope so ;)
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

--
/*===============================================
M. Devrim Erdem            devrim@...
Software Engineering

info(+)TRON, Turkey
Tel: +90 216 4921002, Ext 138
Fax: +90 216 3432132
Http://www.infotron.com.tr
Http://www.machsim.com/devrimerdem
===============================================*/

RE: [Algorithms] Closest point queries

[John Mckenna <jmckenna@re...>]

>From: Bert Peers [mailto:bert.peers@...]

>  I'm trying to find the closest point to a given point; I have
>about 60000 of those points, each of them having about 200
>components (ie pts in R^200).  Regular L2 distance norm.

I did a quick search for this recently.  It's quite probable that I missed
something (it was a very quick search), but what I found wasn't encouraging.
Things like time increasing exponentially with the number of dimensions,
which doesn't sound good for your case.

If you can live with an approximation, you might be able to do better.  I
haven't looked into this in any depth, but I have one pointer that might be
useful:

http://www.cs.umd.edu/~mount/ANN/

They only claim decent results for up to 20 dimensions.  But the manual
seems to have plenty of references to papers.  It might give you some ideas.
-Virus scanned and cleared ok

RE: [Algorithms] runge Kutta

[Jeff Lander <jeffl@da...>]

For a race game or space sim it may be more necessary for the collision detection than the integration.  Tunneling of objects can be a real problem and you can imagine that if you have objects that are moving really fast like 500+ MPH then if you only look at the physics every 1/60 of a second you could easily have an object pass right through another without noticing.  There are a lot of ways to deal with this but running the physical sim at a faster rate then the display is one of them.

Also you don't want the physics locked to the graphics framerate in any case because a lot of things can slow or speed up the graphics rendering but you don't want the gameplay to change depending on the visual framerate.  For example if the frame rate slowed, you don't want the controls to become sluggish.

-Jeff

At 10:41 PM 8/27/2001 -0500, you wrote:
>Wow! 100hz? if they are using anything other than a Euler integrator is that
>necessary? I think FPS do their physics on a per frame basis. In fact, for
>the most part physics isn't a big thing in shooters, they don't have
>anything resembling realistic physics models.
>
>Idahosa Edokpayi

Re: [Algorithms] BVH compression

[Pierre Terdiman <p.terdiman@wa...>]

Damn!
...sigh.... That's what I called "tree coherence".
Wanted to add this in Opcode. But he's been faster than me.

Damn!


...probably gonna drink my way into oblivion now...


----- Original Message ----- 
From: Charles Bloom <cbloom@...>
To: <gdalgorithms-list@...>
Sent: Monday, August 27, 2001 9:38 PM
Subject: Re: [Algorithms] BVH compression


> 
> It's quite simple.  He makes a binary AABB tree.  At the root
> node, you store a full floating-point AABB.  At each node, you
> must define the two AABB's of the two children.  He takes
> advantage of the way the tree is defined :
> 
> 1. The two children boxes are contained in the parent
> 2. The extents of the parent are defines by the union of the children
> 
> So, #1 means that you can store the child min/max's as a fraction
> (0->1) of the parent extents.  This fraction you can then quantize to
> an byte (you just have to round down the min, and round up the max).
> 
> #2 means that of the four corners for the two child boxes, you know
> that the two corners of the parent will be a part.  So, you only need
> to define 6 new floating values, and the other 6 come from the parent.
> He stores a bit-mask to indicate which values come from the parent.
> 
> The result is that an AABB node is 11 bytes (or so).
> 
> At 09:06 PM 8/27/2001 +0200, you wrote:
> > > It's written by Miguel Gomez, so you could search for an online
> > > version by him.  It only works for AABB trees.
> >
> >Could you explain his method ? (there's no online version apparently)
> 
> 
> ----------------------------------------------------
> Charles Bloom    cbloom@...    http://www.cbloom.com
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDAlgorithms-list@...
> http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

RE: [Algorithms] runge Kutta

[Idahosa Edokpayi <idahosae@sw...>]

Wow! 100hz? if they are using anything other than a Euler integrator is that
necessary? I think FPS do their physics on a per frame basis. In fact, for
the most part physics isn't a big thing in shooters, they don't have
anything resembling realistic physics models.

Idahosa Edokpayi

-----Original Message-----
From: gdalgorithms-list-admin@...
[mailto:gdalgorithms-list-admin@...]On Behalf Of
Michael Pohoreski
Sent: Monday, August 27, 2001 3:53 PM
To: gdalgorithms-list@...
Subject: RE: [Algorithms] runge Kutta


Independent? Sort of. Although the rate and the type (fixed / dynamic)
depends on the game genre.

i.e.
Need For Speed (PSX1)
Graphics 30 or 33 Hz (was choosen to be a multiple of physics)
Physics 100 Hz

Virtual Fighter (Dreamcast)
Graphics  60 Hz (these 2 are locked together)
"Physics" 60 Hz

Also, don't forget the networking Hz as well. (Capped so as not to
saturate a modem connection.)
Maybe Gil can say what Quake/Shooters are using for it's networking
rate?

Would be interesting to find out what other developers are having their
engines run at.

RE: [Algorithms] Target leading

[Douglas Cox <ziflin@ho...>]

I thought about averaging the velocities like you mentioned, but also 
figured there was a more elegant way.  Oh well, I'll play around with it 
some more -- it just seemed like someone would have run into it before in a 
3rd person game.

Oh, and they're not Star Wars lasers, they're Robotech lasers.. ;)

-doug

-------------
Perhaps each entity could cache it's present target's last several
velocities (or at least orientations).  Do a fast average of how the
velocities changed from one to the next (to get VecDiff), and create a fake
velocity (VecFake = CurVec + VecDiff); then sum this with the cached
velocities to get a possible future location...  Thus the more erratic the
movement, the less accurate the lead, which makes sense.  There's probably a
much more elegant way to do this though.

Btw, I always thought "Star Wars lasers" were more like plasma cannons or
something; this would be much more acceptable to me than a small and slothly
segment of light.  (Of course, presenting lasers in such a manner has great
cinematic value.)  Regardless, plasma discharges or other ordinary
fire-and-forget projectile weapons can't have their path altered (unless
they're large and slow enough, I suppose).



_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp

RE: [Algorithms] runge Kutta

[Jeff Lander <jeffl@da...>]

Yep.  For example, physics in the game may run at 100hz or so no matter what the graphics are doing.  That means that it needs to run multiple physics steps per frame.  This is can be important both for simulation stability and collision detection to prevent tunnelling.

You definitely want to unlink the two.

-Jeff

At 02:35 PM 8/27/2001 -0500, you wrote:
>So as a rule, most simulations use time steps that are independent of other
>systems? As in the Graphics subsystem runs at 80 HZ and the physics
>simulation runs at say 25 hz with a fixed time step?
>
>Idahosa Edokpayi