Discussion:
World size vs. floats [bcc][fake adr]
(too old to reply)
Gribb, Gil
2003-10-06 07:20:02 UTC
Permalink
Another way to look at it is that all you have to do is compute the modelview matrix to high precision yourself. Then convert it to floats and give it to your api.

-Gil

-----Original Message-----
From: Martin Bell [mailto:***@NTLWorld.com]
Sent: Friday, October 03, 2003 5:16 PM
To: gdalgorithms-***@lists.sourceforge.net
Subject: Re: [Algorithms] World size vs. floats [bcc][fake adr]


Ahhhhh so...
It's not the Z buffer; It's the fact that the vertex positions on the gfx card are becoming less accurate as their distance
from the origin gets larger.
I'm doing a naive (lack of) conversion from world to camera space whereby I'm just shoving the entire world onto the gfx card.
So I need to keep the world representation the same, but whenever I render I need to 'keep the camera at the origin' on the gfx card.
Sounds like a fundamental requirement for the rendering of geometry of any appreciable scale.
Wonder why it isn't described in the OpenGL red book? It's usually good at describing related concepts as well as the required technical stuff. I suppose I may have missed the wood whilst looking for the trees :o

Thanks for the replies,
Martin




----- Original Message -----
From: Ratcliff, John <mailto:***@soe.sony.com>
To: 'gdalgorithms-***@lists.sourceforge.net'
Sent: Thursday, October 02, 2003 11:08 PM
Subject: RE: [Algorithms] World size vs. floats

The 'camera' is always are 0,0,0. All world geometry should be in object space. Subtract the camera position from the object to world transform to make everything always transform around the eye.



-----Original Message-----
From: Martin Bell [mailto:***@NTLWorld.com]
Sent: Thursday, October 02, 2003 4:56 PM
To: gdalgorithms-***@lists.sourceforge.net
Subject: [Algorithms] World size vs. floats



Hi all,

It seems I have a few problems related to floating point accuracy.
Just wanted to know if there were any 'standard' approaches out there for fitting everything in a world representation, a maximum usable size for a 'world', or just any experiences on the subject..?

I have an island archipelago in the world which can be freely moved around. As the camera gets further away from the world origin, there is more and more z-fighting apparent when changing the camera heading (I'm thinking this is a vertex posn inaccuracy on the gfx card).
I'm using 'float's for absolute positioning - I've read a few posts on here about using int64's for positioning, but wasn't paying full attention because I thought my floats did the job fine and dandy :-/ Presumably though, I'll still get the z-fighting when I convert them to floats away from the origin.

Also, to make the artefacts worse, the sea is a semi-transparent sheet that bobs up n down, with the islands just poking out from underneath. I also read on here about reinitialising the z-buffer near & far to 'fit' the island, but don't think I can do this because of my transparent sea sheet?

I'm hoping that I won't have to 'fudge' the world into small pieces placed on the origin that appear to be contiguous... or a lot of rework my way comes :(

I'm using openGL by the way. The scale of things is roughly 1 metre to 1 unit (1.0f).

Cheers,
Martin
Jon Watte
2003-10-06 22:28:27 UTC
Permalink
Post by Gribb, Gil
Another way to look at it is that all you have to do is compute the
modelview matrix
Post by Gribb, Gil
to high precision yourself. Then convert it to floats and give it to your
api.

That's not good enough! Suppose the modelview says the camera is at
(0,0,6000000) which
is almost as far out as the equator from the earth center. That means the
modelview
matrix will contain a subtraction of 6000000 in the Z coordinate. Then you
feed a vertex
array to the API that has vertices that all have Z values in the range of
6000000. This
will cause horrible popping/jumping because the quantization level of a
float is something
like a meter and a half out at this distance.

You really need to make sure that all the matrices and vertex data you give
to your API
are well conditioned, which means "close to the origin" where "close" is
vague and depends
on specific implementation precision. In the case I outline, and I'm sure
you're thinking
about, you should keep object data in object space, and put the
object-to-world transform
in a high-resolution format, and do the same for the world-to-view
transform; bake these
two together in high resolution and then convert to float, making sure that
the "large
numbers" in these transforms cancel out.

That's probably what you meant, but what you wrote didn't preclude the
problem in the first
paragraph, which is bound to confuse someone who runs into it for the first
time. This
means that for objects that don't have a natural "object space"
(smoke/particles, terrain,
decals, etc) you have to come up with a reasonably accurate "anchor point"
for these
objects and pretend that that's your world position for these objects, to
make the numbers
involved well conditioned. This, in turn, often means that you have to break
really large
particle systems and other effects (fog, footprints, what have you) into
several smaller
pieces. Which you probably should do for culling, anyway :-)

Cheers,

/ h+
Charles Bloom
2003-10-06 23:09:04 UTC
Permalink
Yeah, ignoring the PS2 which is such a pox in the universe, doubles are the
way to go for positions in the future. For future engines I would advocate
storing transforms as a 3x3 float matrix + 3 double position = 60 bytes
total, less than a 4x4 float matrix. All objects should be in some kind of
"object space" with 32-bit positions (or even 16-bit positions quantized
into the bbox of the object space).
Post by Jon Watte
. This, in turn, often means that you have to break
really large particle systems and other effects (fog, footprints, what
have you) into
several smaller pieces. Which you probably should do for culling, anyway :-)
The next time I have a 4 km X 4 km particle system, I'll keep this in mind ;^)


--------------------------------------------------------------------------------------------
Charles Bloom email "cb" http://www.cbloom.com
Gribb, Gil
2003-10-07 06:49:12 UTC
Permalink
I said> Another way to look at it is that all you have to do is compute the
modelview matrix
Post by Gribb, Gil
to high precision yourself. Then convert it to floats and give it to your
api.
Post by Gribb, Gil
That's not good enough!
My two sentence answer is good enough, for a two sentence answer. Yes, the assumption is that the verts are in a local coordinate system, and that the local coordinate system is somewhere near the verts of the objects.

Other thoughts:

No matter what kind of game it is, almost all of the work can be done with floats if you are clever and know what you are doing. If you are not clever or don't know what you are doing using doubles for everything is a reasonable (but very slow) approach. You might still have problems if you graphics API and or GPU doesn't do doubles and I don't think they in general do. I don't think GPU's need to do doubles because a monitor is not a very precise thing.

I can't figure out how gameplay and game design would ever work out with very high spatial dynamic range of say an inch to a lightyear. But I don't do game design.

-Gil



I said> Another way to look at it is that all you have to do is compute the
modelview matrix
Post by Gribb, Gil
to high precision yourself. Then convert it to floats and give it to your
api.

That's not good enough! Suppose the modelview says the camera is at
(0,0,6000000) which
is almost as far out as the equator from the earth center. That means the
modelview
matrix will contain a subtraction of 6000000 in the Z coordinate. Then you
feed a vertex
array to the API that has vertices that all have Z values in the range of
6000000. This
will cause horrible popping/jumping because the quantization level of a
float is something
like a meter and a half out at this distance.

You really need to make sure that all the matrices and vertex data you give
to your API
are well conditioned, which means "close to the origin" where "close" is
vague and depends
on specific implementation precision. In the case I outline, and I'm sure
you're thinking
about, you should keep object data in object space, and put the
object-to-world transform
in a high-resolution format, and do the same for the world-to-view
transform; bake these
two together in high resolution and then convert to float, making sure that
the "large
numbers" in these transforms cancel out.

That's probably what you meant, but what you wrote didn't preclude the
problem in the first
paragraph, which is bound to confuse someone who runs into it for the first
time. This
means that for objects that don't have a natural "object space"
(smoke/particles, terrain,
decals, etc) you have to come up with a reasonably accurate "anchor point"
for these
objects and pretend that that's your world position for these objects, to
make the numbers
involved well conditioned. This, in turn, often means that you have to break
really large
particle systems and other effects (fog, footprints, what have you) into
several smaller
pieces. Which you probably should do for culling, anyway :-)

Cheers,

/ h+



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Stuart Harrison
2003-10-07 08:16:05 UTC
Permalink
Post by Gribb, Gil
I can't figure out how gameplay and game design would ever
work out with very high spatial dynamic range of say an inch
to a lightyear. But I don't do game design.
I'm sure Microsoft could answer this question better than me, but I
expect a simulation game, like Flight Sim or Train Sim, would require
reasonably accuracy in the placement of landmark buildings and details
of those (assuming you can get close enough to resolve that detail) -
let's say millimetre accuracy - but over hundreds, if not thousands of
kilometres of "world". That spans about 30 bits (1000km = 1bn mm) - too
many to fit in a float (which can only deal with 23 bits of accuracy).

-Dino.


Information contained in this e-mail is intended for the use of the addressee only, and is confidential and may be the subject of Legal Professional Privilege. Any dissemination, distribution, copying or use of this communication without prior permission of the addressee is strictly prohibited.The views of the author may not necessarily constitute the views of Kuju Entertainment Ltd. Nothing in this email shall bind Kuju Entertainment Ltd in any contract or obligation.

The contents of an attachment to this e-mail may contain software viruses which could damage your own computer system. While Kuju Entertainment has taken every reasonable precaution to minimise this risk, we cannot accept liability for any damage which you sustain as a result of software viruses. You should carry out your own virus checks before opening the attachment.
Madoc Evans
2003-10-07 08:58:11 UTC
Permalink
I haven't considered this overly much but I always thought I could tackle
this problem by having the world split into chunks/sectors and describing
everything relative to the local sector. So, the local sector (where the
camera is) is always the world coordinate system and only very distant
sectors would suffer from precision issues. Similarly, for physics, where
the interaction can only span to a neighbouring sector.
Obviously, this doesn't solve the problem but merely shifts it to where it's
less critical. I think that, perhaps with a few other tricks (ie LoD,
impostors), it should be sufficient for most apps.


----- Original Message -----
From: "Stuart Harrison" <***@kuju.com>
To: <gdalgorithms-***@lists.sourceforge.net>
Sent: Tuesday, October 07, 2003 4:58 PM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Gribb, Gil
I can't figure out how gameplay and game design would ever
work out with very high spatial dynamic range of say an inch
to a lightyear. But I don't do game design.
I'm sure Microsoft could answer this question better than me, but I
expect a simulation game, like Flight Sim or Train Sim, would require
reasonably accuracy in the placement of landmark buildings and details
of those (assuming you can get close enough to resolve that detail) -
let's say millimetre accuracy - but over hundreds, if not thousands of
kilometres of "world". That spans about 30 bits (1000km = 1bn mm) - too
many to fit in a float (which can only deal with 23 bits of accuracy).

-Dino.


Information contained in this e-mail is intended for the use of the
addressee only, and is confidential and may be the subject of Legal
Professional Privilege. Any dissemination, distribution, copying or use of
this communication without prior permission of the addressee is strictly
prohibited.The views of the author may not necessarily constitute the views
of Kuju Entertainment Ltd. Nothing in this email shall bind Kuju
Entertainment Ltd in any contract or obligation.

The contents of an attachment to this e-mail may contain software viruses
which could damage your own computer system. While Kuju Entertainment has
taken every reasonable precaution to minimise this risk, we cannot accept
liability for any damage which you sustain as a result of software viruses.
You should carry out your own virus checks before opening the attachment.


-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_ida88
Eric Preisz
2003-10-07 09:33:05 UTC
Permalink
I've worked on a similar idea for about 2 years. And like most cases in
programming, the idea of the solution is much easier than the
implementation. The biggest problem I'm having is the overhead of a system
like this. I called my chunks "cells" and each cell is described by the
precision needed for that current simulation(ones, deci, centi, etc). The
complexities begin when you start buildings process that are inter and
extra-zonal (did I just make up a new word?).

For example, when an object moves out of a cell, you must add it to the new
cell. Collisions and ray/segment casts become annoying when you span more
than one zone. They require translation from double space to zone space,
which if your activities are large enough can cause a lot of overhead.
Maybe my life will get easier when/if cards support double precision
translations and 64 bit processors and operating systems are the norm.

Eric Preisz
Dynamic Animation Systems


----- Original Message -----
From: "Madoc Evans" <***@tin.it>
To: <gdalgorithms-***@lists.sourceforge.net>
Sent: Tuesday, October 07, 2003 12:02 PM
Subject: Re: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Madoc Evans
I haven't considered this overly much but I always thought I could tackle
this problem by having the world split into chunks/sectors and describing
everything relative to the local sector. So, the local sector (where the
camera is) is always the world coordinate system and only very distant
sectors would suffer from precision issues. Similarly, for physics, where
the interaction can only span to a neighbouring sector.
Obviously, this doesn't solve the problem but merely shifts it to where it's
less critical. I think that, perhaps with a few other tricks (ie LoD,
impostors), it should be sufficient for most apps.
----- Original Message -----
Sent: Tuesday, October 07, 2003 4:58 PM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Gribb, Gil
I can't figure out how gameplay and game design would ever
work out with very high spatial dynamic range of say an inch
to a lightyear. But I don't do game design.
I'm sure Microsoft could answer this question better than me, but I
expect a simulation game, like Flight Sim or Train Sim, would require
reasonably accuracy in the placement of landmark buildings and details
of those (assuming you can get close enough to resolve that detail) -
let's say millimetre accuracy - but over hundreds, if not thousands of
kilometres of "world". That spans about 30 bits (1000km = 1bn mm) - too
many to fit in a float (which can only deal with 23 bits of accuracy).
-Dino.
Information contained in this e-mail is intended for the use of the
addressee only, and is confidential and may be the subject of Legal
Professional Privilege. Any dissemination, distribution, copying or use of
this communication without prior permission of the addressee is strictly
prohibited.The views of the author may not necessarily constitute the views
of Kuju Entertainment Ltd. Nothing in this email shall bind Kuju
Entertainment Ltd in any contract or obligation.
The contents of an attachment to this e-mail may contain software viruses
which could damage your own computer system. While Kuju Entertainment has
taken every reasonable precaution to minimise this risk, we cannot accept
liability for any damage which you sustain as a result of software viruses.
You should carry out your own virus checks before opening the attachment.
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_ida88
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
CAVEY GERARD
2003-10-07 08:32:10 UTC
Permalink
hola
Dino is right nowadays games use terrain/scenes larger and larger
and a single float can t be enough to cover the whole area
or you ll lose too much precision
but i don t understand your problem ??!!! if you plan to simulate an huge
scene/terrain/world just cut it into pieces ;it ll speed up your frame
processing time
and a float is enough for a scene part !
u just need to reset coordinates for each node in the scene tree and
add some code to make your entities travel from part to part:
mmm my answer is so evident i m wondering if i m missing something :)

GC.
Post by Stuart Harrison
Post by Gribb, Gil
I can't figure out how gameplay and game design would ever
work out with very high spatial dynamic range of say an inch
to a lightyear. But I don't do game design.
I'm sure Microsoft could answer this question better than me, but I
expect a simulation game, like Flight Sim or Train Sim, would require
reasonably accuracy in the placement of landmark buildings and details
of those (assuming you can get close enough to resolve that detail) -
let's say millimetre accuracy - but over hundreds, if not thousands of
kilometres of "world". That spans about 30 bits (1000km = 1bn mm) - too
many to fit in a float (which can only deal with 23 bits of accuracy).
*************************************************************************
Ce message et toutes les pieces jointes (ci-apres le "message") sont
confidentiels et etablis a l'intention exclusive de ses destinataires.
Toute utilisation ou diffusion non autorisee est interdite.
Tout message electronique est susceptible d'alteration.
SG Asset Management et ses filiales declinent toute responsabilite au titre
de ce message s'il a ete altere, deforme ou falsifie.

Decouvrez l'offre et les services de SG Asset Management sur le site
www.sgam.fr

********

This message and any attachments (the "message") are confidential and
intended solely for the addressees.
Any unauthorised use or dissemination is prohibited.
E-mails are susceptible to alteration.
Neither SG Asset Management nor any of its subsidiaries or affiliates shall
be liable for the message if altered, changed or falsified.

*************************************************************************
Jon Watte
2003-10-07 10:15:04 UTC
Permalink
Post by Madoc Evans
everything relative to the local sector. So, the local sector (where the
camera is) is always the world coordinate system and only very distant
sectors would suffer from precision issues. Similarly, for physics, where
the interaction can only span to a neighbouring sector.
Assuming your artists don't build monster collision meshes... (that's what
the +3 Knobbly Stick Of Artist Enlightenment is for, I suppose -- Tom, can
I borrow yours?)

However, there are some subtle dangers with this approach. For example,
you will get rounding problems when objects cross boundaries; the change
in quantization may change "the same" position to something that's
actually different, and gets a different response.

If it's multi-player, and you expect remote nodes to be able to re-simulate
what the local node is doing, you need to make sure that all instances of
the same object across the network use the same local sector for the same
simulation work.

Typically, in this system, your global position address looks something
like:

int sectorId;
float x, y, z;

Another problem with this representation is that calculating distance to
other
objects becomes harder; at a minimum, you have to look up a "global center"
for each using the sectorId; if distances can grow large and you need good
precision, then those global centers have to be stored in doubles and the
math
has to be done in doubles anyway. Not to mention that the table of global
centers for something as big as a planet would be huge; at that point, using

double x, y, z;

starts looking pretty good :-) Not for render data, say, but for object
position in world type data, which by extension then includes much physics
code.

Cheers,

/ h+
Jason Dent
2003-10-07 10:19:02 UTC
Permalink
Dino is right. The 23-bits of a float cannot accurately represent the position of an object on the earth. This isn't really an issue for most games, because they do not have worlds large enough to cause a problem. But, the earth does provide a great set of numbers to test out accuracy.



The earth is roughly 40,000 km in circumference and about 6366 km in radius. Given that, we have to pick a coordinate system. Common ones are polar and Cartesian. Forgive me if you know all this. Most often when people talk about positions on the earth, they do it in latitude, longitude, and altitude. Which is just the polar coordinates with the radius of the earth subtracted out to get the altitude. In an earlier post, Jon Watte very accurately pointed out that a coordinate value of (0,0,6000000m) would introduce a large amount of in accuracy. Subtracting off the radius of the earth when storing the position of an object is key to preserving accuracy. For example, let's say an object is 5 m above sea level. If we stored that value in relation to the distance from the center of the earth, it would be 6366.005 km. As you can see the .005 is a rounding error. If we stored it in a float we could only represent object to the nearest 0.76m = 6366000m / 2^23. Talk about an ugly world if objects would only be represented in Ÿ m units.



Storing the latitude and longitude values in a float can also be a problem. For example if we tried to position an object on the equator near E 180, we could only place it to the nearest 2.4m = 20,000,000 / 2^23, again a very inaccurate number. A 32-bit integer will buy you 1cm accuracy, which is good enough for the placement of most objects. If you live in California, your house most likely shifted that much during the course of the year.



What about Cartesian? In terms of representing the location of items on the Earth relative to the center, unless you are planning on using doubles, it is a bad idea.



But there is a problem, most graphics cards do not handle polar coordinates little lone latitude, longitude, and altitude. The key is to store the object on the disk in polar form and convert it to a local Cartesian origin relative to the camera position. You don't need to do this every frame, just convert it and keep it. If the camera position changes by more than a km or two, then convert it to a new relative origin based upon the updated camera position.



I have rambled on long enough. The key here is to be willing to store the position of an object in a form optimized for accuracy and convert it into a form optimized for rendering relative to the camera position when it needed.



Jason






________________________________

From: gdalgorithms-list-***@lists.sourceforge.net on behalf of CAVEY GERARD
Sent: Tue 10/7/2003 8:31 AM
To: 'gdalgorithms-***@lists.sourceforge.net'
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]



hola
Dino is right nowadays games use terrain/scenes larger and larger
and a single float can t be enough to cover the whole area
or you ll lose too much precision
but i don t understand your problem ??!!! if you plan to simulate an huge
scene/terrain/world just cut it into pieces ;it ll speed up your frame
processing time
and a float is enough for a scene part !
u just need to reset coordinates for each node in the scene tree and
add some code to make your entities travel from part to part:
mmm my answer is so evident i m wondering if i m missing something :)

GC.
Post by Stuart Harrison
Post by Gribb, Gil
I can't figure out how gameplay and game design would ever
work out with very high spatial dynamic range of say an inch
to a lightyear. But I don't do game design.
I'm sure Microsoft could answer this question better than me, but I
expect a simulation game, like Flight Sim or Train Sim, would require
reasonably accuracy in the placement of landmark buildings and details
of those (assuming you can get close enough to resolve that detail) -
let's say millimetre accuracy - but over hundreds, if not thousands of
kilometres of "world". That spans about 30 bits (1000km = 1bn mm) - too
many to fit in a float (which can only deal with 23 bits of accuracy).
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Bryan Wagstaff
2003-10-07 13:12:51 UTC
Permalink
Post by Jason Dent
they do not have worlds large enough to cause a problem. But, the earth does
provide a great set of numbers to test out accuracy.
...
Post by Jason Dent
get the altitude. In an earlier post, Jon Watte very accurately pointed out
that a coordinate value of (0,0,6000000m) would introduce a large amount of in
accuracy. Subtracting off the radius of the earth when storing the position of
...
Post by Jason Dent
Storing the latitude and longitude values in a float can also be a problem.
...
Post by Jason Dent
But there is a problem, most graphics cards do not handle polar coordinates
little lone latitude, longitude, and altitude. The key is to store the object
on the disk in polar form and convert it to a local Cartesian origin relative
to the camera position. You don't need to do this every frame, just convert it
and keep it. If the camera position changes by more than a km or two, then
convert it to a new relative origin based upon the updated camera position.
After re-reading the thread, I doubt that this is what the original poster was
interested in, although it is still interesting.

This whole issue reminds me too much of what I was doing a few years ago in my
college lab. In our graduate work, we were modeling a large area (about 250 miles
by 150 miles).

To begin with -- When talking in this scale, using floating point numbers but not
having a deep understanding of them is a Bad Thing(tm). It's like using a float
to represent currency: don't do it. If you have to ask about exceptions to the
rule, then you don't know enough about it.

Our data sources included the USGS DEMs and grayscale DOQs, our own (color)
back-projected terrain images from a flight around the area, custom hand-modeled
objects at places of interest (campus, our CS building, the lab, the grad students
in the lab, an unflattering model of our advisor, etc. ) and computer generated
objects (mainly trees, but some were trying to auto-detect buildings from the DOQs
and airplane movies).

It is painfully apparent when working at this scale that you cannot do a lot of
things that you can do in games. You can't use square or regular-shaped blocks,
due to the curvature of the Earth. You cannot be naive about the use floating
point, because the properties of the numbers comes into play. You must use a
great deal of offline processing and expect many gigabytes of real-world data.
You must use interesting and possibly novel techniques for progressive loading,
managing detail in memory, occlusion checking, automated object placement, etc.

Our solution was to group geographic areas into non-homogonous blocks and have
several processing steps. We had parallel data trees that were essentially
quad-trees over each large block. The parallel trees included one for quickly
estimating occlusion, one with LOD model data, and another with LOD terrain data.

If you understand floating point numbers (and sadly, most programmers don't take
the time), you can use pairs of numbers and treat points as range values with
relative errors based on FLT_EPSILON or DBL_EPSILON. Using those pairs the
relative error estimate, you can easily use low-res data for most distant objects,
then use high-res data when you have potential contention.

Once we determined what blocks and quad-tree LOD patches were visible, we would
process and render each patch. When a model patch had a good chance of contention
(as listed in the occlusion data tree) we would construct a custom projection
matrix and render that patch independently into a small buffer. The pre-rendered
patch was assigned an error value so we knew when to redraw the thing, then we
would use the pre-rendered buffer when drawing that patch.

We didn't have to use Latitude and Longitude, but instead indicated the location
in terms of a fixed-point value of x/y/z over a given chunk.

So in more common terms, we used a combination of imposters, progressive network
and local data storage, CLOD with geo-morphing, and pre-computed occlusion data.
Our group put out papers that were frequently cited as references in the early
ROAM and CLOD research.

Our drawing rate on an SGI O2 ranged from 15-25 FPS over most of the terrain.
When we got our hands on a $5000(?) machine with a Brand New GeForce 2 card, a
Really Fast 1 Ghz dual-cpu processor, and 2 GB of memory, we could get 120+ FPS.

We also realized with that purchase that future interesting research on CLOD
terrain was basically doomed because of the new GPUs and fast CPUs.

Finally, and on a side note, while I was there we had a few different people from
Microsoft Research come and visit the lab, in exchange for them giving rather
interesting presentations and Q/A sessions to us. I think that the students got
the better end of the deal, since all our work was ready for publishing.

-Bryan.
Martin Bell
2003-10-08 16:14:05 UTC
Permalink
From: "Bryan Wagstaff" <***@xmission.com>
To: <gdalgorithms-***@lists.sourceforge.net>
Sent: Tuesday, October 07, 2003 8:42 PM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Bryan Wagstaff
After re-reading the thread, I doubt that this is what the original poster was
interested in, although it is still interesting.
Yes, still interesting :)
Post by Bryan Wagstaff
To begin with -- When talking in this scale, using floating point numbers but not
having a deep understanding of them is a Bad Thing(tm). It's like using a float
to represent currency: don't do it. If you have to ask about exceptions to the
rule, then you don't know enough about it.
It can be said I don't know enough about floats (hence my post) -- I made
the assumption that +/- 50k would be ok, by looking at the max storable
float value. I've always stuck to doubles where accuracy (not speed)
mattered before now :)

Looking at the size and content of that doc you posted, I'd be surprised if
I was alone there (ok maybe not on this list ;)
Tom Forsyth
2003-10-07 11:00:07 UTC
Permalink
I prefer using a WorldPosition class. Then you can store whatever you like
in it. The only way you can get a vector of floats out of a WorldPosition is
relative to another WorldPosition (usually the camera for rendering, or
something handy for gameplay stuff).

Personally I like u32 (if you can) or u64 (for big worlds) inside the class
rather than using doubles - it's a lot more portable. Since the only
operations you can do on them are subtract two of them or add two of them,
it's faster or equivalent speed on pretty much everything (definately on PS2
of course).

Biggest advantage is absolutely predictable precision. You never have to
worry about something working near the origin but not working further away.


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 07 October 2003 18:15
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Madoc Evans
everything relative to the local sector. So, the local
sector (where the
Post by Madoc Evans
camera is) is always the world coordinate system and only
very distant
Post by Madoc Evans
sectors would suffer from precision issues. Similarly, for
physics, where
Post by Madoc Evans
the interaction can only span to a neighbouring sector.
Assuming your artists don't build monster collision meshes...
(that's what
the +3 Knobbly Stick Of Artist Enlightenment is for, I
suppose -- Tom, can
I borrow yours?)
However, there are some subtle dangers with this approach.
For example,
you will get rounding problems when objects cross boundaries;
the change
in quantization may change "the same" position to something that's
actually different, and gets a different response.
If it's multi-player, and you expect remote nodes to be able
to re-simulate
what the local node is doing, you need to make sure that all
instances of
the same object across the network use the same local sector
for the same
simulation work.
Typically, in this system, your global position address looks
something
int sectorId;
float x, y, z;
Another problem with this representation is that calculating
distance to
other
objects becomes harder; at a minimum, you have to look up a
"global center"
for each using the sectorId; if distances can grow large and
you need good
precision, then those global centers have to be stored in
doubles and the
math
has to be done in doubles anyway. Not to mention that the
table of global
centers for something as big as a planet would be huge; at
that point, using
double x, y, z;
starts looking pretty good :-) Not for render data, say, but
for object
position in world type data, which by extension then includes
much physics
code.
Cheers,
/ h+
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
p***@playstation.sony.com
2003-10-07 12:58:32 UTC
Permalink
Post by Charles Bloom
Yeah, ignoring the PS2 which is such a pox in the universe, doubles are
the way to go for positions in the future.

Anticipating 4x64 bit hardware anytime soon?

Cheers,
Phil
Mark Wayland
2003-10-08 21:05:02 UTC
Permalink
Do any of you guys use fixed point for this sort of thing - I presume this is what Tom's talking about with the WorldPosition type class? We (have to) use fixed-point everywhere on our hand-held and low-end stuff, but tend not to on our high-end although in this case (and indeed the case with huge streaming worlds), I presume that fixed-point would be almost ideal? (Sorry if this has been discussed already)

Mark
Post by Gribb, Gil
-----Original Message-----
Sent: Thursday, 9 October 2003 9:18 AM
Subject: Re: [Algorithms] World size vs. floats [bcc][fake adr]
Sent: Tuesday, October 07, 2003 8:42 PM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Bryan Wagstaff
After re-reading the thread, I doubt that this is what the
original poster
was
Post by Bryan Wagstaff
interested in, although it is still interesting.
Yes, still interesting :)
Post by Bryan Wagstaff
To begin with -- When talking in this scale, using floating
point numbers
but not
Post by Bryan Wagstaff
having a deep understanding of them is a Bad Thing(tm).
It's like using a
float
Post by Bryan Wagstaff
to represent currency: don't do it. If you have to ask
about exceptions
to the
Post by Bryan Wagstaff
rule, then you don't know enough about it.
It can be said I don't know enough about floats (hence my
post) -- I made
the assumption that +/- 50k would be ok, by looking at the
max storable
float value. I've always stuck to doubles where accuracy (not speed)
mattered before now :)
Looking at the size and content of that doc you posted, I'd
be surprised if
I was alone there (ok maybe not on this list ;)
Jonathan Blow
2003-10-08 21:47:03 UTC
Permalink
Integer representations are generally the right thing for storing world positions, because
you want the same amount of accuracy everywhere. This might be fixed point, but it
might also be something else (e.g. you have your world coordinates defined to be within
some floating-point range, f_0 to f_1, and you quantize that into 1 million pieces, so then
your coordinates are just integers between 0 and 999,999... though 1 million really
isn't enough for a big map).

-J.

----- Original Message -----
From: "Mark Wayland" <***@torus.com.au>
To: <gdalgorithms-***@lists.sourceforge.net>
Sent: Wednesday, October 08, 2003 10:59 PM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Mark Wayland
Do any of you guys use fixed point for this sort of thing - I presume this is what Tom's talking about with the WorldPosition type
class? We (have to) use fixed-point everywhere on our hand-held and low-end stuff, but tend not to on our high-end although in this
case (and indeed the case with huge streaming worlds), I presume that fixed-point would be almost ideal? (Sorry if this has been
discussed already)
Post by Mark Wayland
Mark
Post by Gribb, Gil
-----Original Message-----
Sent: Thursday, 9 October 2003 9:18 AM
Subject: Re: [Algorithms] World size vs. floats [bcc][fake adr]
Sent: Tuesday, October 07, 2003 8:42 PM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Bryan Wagstaff
After re-reading the thread, I doubt that this is what the
original poster
was
Post by Bryan Wagstaff
interested in, although it is still interesting.
Yes, still interesting :)
Post by Bryan Wagstaff
To begin with -- When talking in this scale, using floating
point numbers
but not
Post by Bryan Wagstaff
having a deep understanding of them is a Bad Thing(tm).
It's like using a
float
Post by Bryan Wagstaff
to represent currency: don't do it. If you have to ask
about exceptions
to the
Post by Bryan Wagstaff
rule, then you don't know enough about it.
It can be said I don't know enough about floats (hence my
post) -- I made
the assumption that +/- 50k would be ok, by looking at the
max storable
float value. I've always stuck to doubles where accuracy (not speed)
mattered before now :)
Looking at the size and content of that doc you posted, I'd
be surprised if
I was alone there (ok maybe not on this list ;)
Leath Muller
2003-10-08 22:44:02 UTC
Permalink
Post by Jonathan Blow
Integer representations are generally the right thing for storing
world positions, because you want the same amount of accuracy
everywhere. This might be fixed point, but it might also be
something else (e.g. you have your world coordinates defined to be
within some floating-point range, f_0 to f_1, and you quantize that
into 1 million pieces, so then your coordinates are just integers
between 0 and 999,999... though 1 million really isn't enough for a
big map).
ESRI GIS systems generally store 'exents' in some coordinate form
(geographic, etc) to ~ 2^31 - 4 values. When specifying datasets
that work in that coordinate range, you provide a precision value.

As strange as it seems, this works quite well, if you negate the
fact the Earth is really potato shaped, not a sphere (but who would
really notice or care in a game?).

Consider a single degree distance at the equator which is about
111,120 metres. If you dataset has a precision (or scale) or
40,000 then you get 111,120/40,000 = ~2.778 meter accuracy.

Naturally, a scale of 111,120 gives 1 meter accuracy. To have
an accuracy of say 1 cm, you need a scale of 11,112,000 'integer
blocks' to store one degree. For 360 degrees, you need a little
over 4 billion in your coordinate range.

So, for integer coordinates using an unsigned 32 bit value,
you can theoretically store every point on Earth at 1 cm
accuracy.

I think... someone might check that and not agree... :)

Just how much do people really want? ;)

Leathal.
Jon Jansen
2003-10-09 01:08:06 UTC
Permalink
'1cm accuracy' sounds like a lot until you see what happens when a
slow-moving object (e.g. a slow-moving character) is quantised to a
1cm grid.

Imagine a character moving at 0.6m/s (just over one mile an hour)
updated at 60FPS and quantised to 1cm. Each frame the character
moves 1cm, so from any given position there are effectively only
8 possible new positions i.e. the direction of the character's
movement is also quantised.

Not sure if there's any better solution to this other than increasing
your resolution, speeding your characters up (!) or dropping your
framerate (!!).

Regards
Jon

-----Original Message-----
From: Leath Muller [mailto:***@gbrmpa.gov.au]
Sent: 09 October 2003 06:49
To: gdalgorithms-***@lists.sourceforge.net
Subject: Re: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Jonathan Blow
Integer representations are generally the right thing for storing
world positions, because you want the same amount of accuracy
everywhere. This might be fixed point, but it might also be
something else (e.g. you have your world coordinates defined to be
within some floating-point range, f_0 to f_1, and you quantize that
into 1 million pieces, so then your coordinates are just integers
between 0 and 999,999... though 1 million really isn't enough for a
big map).
ESRI GIS systems generally store 'exents' in some coordinate form
(geographic, etc) to ~ 2^31 - 4 values. When specifying datasets
that work in that coordinate range, you provide a precision value.

As strange as it seems, this works quite well, if you negate the
fact the Earth is really potato shaped, not a sphere (but who would
really notice or care in a game?).

Consider a single degree distance at the equator which is about
111,120 metres. If you dataset has a precision (or scale) or
40,000 then you get 111,120/40,000 = ~2.778 meter accuracy.

Naturally, a scale of 111,120 gives 1 meter accuracy. To have
an accuracy of say 1 cm, you need a scale of 11,112,000 'integer
blocks' to store one degree. For 360 degrees, you need a little
over 4 billion in your coordinate range.

So, for integer coordinates using an unsigned 32 bit value,
you can theoretically store every point on Earth at 1 cm
accuracy.

I think... someone might check that and not agree... :)

Just how much do people really want? ;)

Leathal.



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Allan Murphy
2003-10-09 02:02:04 UTC
Permalink
Another problem with this representation is that calculating distance to other
objects becomes harder; at a minimum, you have to look up a "global center"...
Scott Bilas' excellent GDC talk about the continuous streaming world in Dungeon Siege actually touched on a couple of the issues coming up here.
He noted that because float wasn't anywhere near accurate enough for the size of their world (since it is one continuous world across something like 40hrs of wandering around gameplay), they had this exact system of sector/chunk world positions and to calculate the distance between objects, they had to do a kind of route find from source chunk to target chunk and accumulation of distances instead of a straight geometric distance since there was no world space, really.

He noted plenty of other non-obvious implications too, as you say - for example if all the game objects won't fit in memory at once, deciding which to keep cached and which to throw out, and all the horrible implications this has for game logic.

Al

-----Original Message-----
From: Jon Watte [mailto:***@mindcontrol.org]
Sent: 07 October 2003 18:15
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
everything relative to the local sector. So, the local sector (where the
camera is) is always the world coordinate system and only very distant
sectors would suffer from precision issues. Similarly, for physics, where
the interaction can only span to a neighbouring sector.
Assuming your artists don't build monster collision meshes... (that's what
the +3 Knobbly Stick Of Artist Enlightenment is for, I suppose -- Tom, can
I borrow yours?)

However, there are some subtle dangers with this approach. For example,
you will get rounding problems when objects cross boundaries; the change
in quantization may change "the same" position to something that's
actually different, and gets a different response.

If it's multi-player, and you expect remote nodes to be able to re-simulate
what the local node is doing, you need to make sure that all instances of
the same object across the network use the same local sector for the same
simulation work.

Typically, in this system, your global position address looks something
like:

int sectorId;
float x, y, z;

Another problem with this representation is that calculating distance to
other
objects becomes harder; at a minimum, you have to look up a "global center"
for each using the sectorId; if distances can grow large and you need good
precision, then those global centers have to be stored in doubles and the
math
has to be done in doubles anyway. Not to mention that the table of global
centers for something as big as a planet would be huge; at that point, using

double x, y, z;

starts looking pretty good :-) Not for render data, say, but for object
position in world type data, which by extension then includes much physics
code.

Cheers,

/ h+



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188

**********************************************************************
The information contained in this email and its attachments is
confidential. It is intended only for the named addressees
and may not be disclosed to anyone else without consent from
Blue 52 Limited. Blue 52 gives no warranty that this email
message (including any attachments to it) is free of any virus
or other harmful matter and accepts no responsibility for any
loss or damage resulting from the recipient receiving, opening
or using it.
**********************************************************************
Chris Chapman
2003-10-09 02:08:02 UTC
Permalink
I was considering this one with respect to a networking engine I've been
working on designed to operate in a complex universe, where the scales could
range from cm accurate or better in, for example, a FPS on a space station
up to massive Star Destroyer sized ships flying around the universe.

My idea was similar - to have a FrameOfReference class to store a reference
origin and scale. All world positions would be relative to a particular FOR,
and have manipulator code to be able to convert into other FOR space to
allow normal vector operations to be done in the same coordinate space.
Obviously the conversions are much cheaper if you don't allow different
scales, but means you need more FORs to encompass the same world-space. I
would assume that if your world space is of a fixed size and you can create
a small enough set of reference origins which encompass your game area and
still allow the accuracy you need, then you don't need to bother with
scales.

What I really need to do though is to write an algorithm which, given a set
of objects each of which has a set scale (i.e. a required accuracy level in
world space distance) and position, can come up with a reasonably minimal
set of FORs which encompass those objects. That way you get the minimal
number of conversions betwen FORs, while still preserving accuracy over
large scale complex environments. Dynamic objects are fine, as long as they
stay within the tolerance limits of a FOR - if they move out of it then a
new FOR can be created and they shift into it - essentially allowing moving
objects to carry their own accuracy with them.

I don't think this helps rendering issues at all (although you might save
accuracy by doing camera->FOR->object transforms in an efficient way), it
was just to sort out dynamics problems with scale.

ChrisC


-----Original Message-----
From: Tom Forsyth [mailto:***@muckyfoot.com]
Sent: 07 October 2003 18:56
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]


I prefer using a WorldPosition class. Then you can store whatever you like
in it. The only way you can get a vector of floats out of a WorldPosition is
relative to another WorldPosition (usually the camera for rendering, or
something handy for gameplay stuff).

Personally I like u32 (if you can) or u64 (for big worlds) inside the class
rather than using doubles - it's a lot more portable. Since the only
operations you can do on them are subtract two of them or add two of them,
it's faster or equivalent speed on pretty much everything (definately on PS2
of course).

Biggest advantage is absolutely predictable precision. You never have to
worry about something working near the origin but not working further away.


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 07 October 2003 18:15
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Madoc Evans
everything relative to the local sector. So, the local
sector (where the
Post by Madoc Evans
camera is) is always the world coordinate system and only
very distant
Post by Madoc Evans
sectors would suffer from precision issues. Similarly, for
physics, where
Post by Madoc Evans
the interaction can only span to a neighbouring sector.
Assuming your artists don't build monster collision meshes...
(that's what
the +3 Knobbly Stick Of Artist Enlightenment is for, I
suppose -- Tom, can
I borrow yours?)
However, there are some subtle dangers with this approach.
For example,
you will get rounding problems when objects cross boundaries;
the change
in quantization may change "the same" position to something that's
actually different, and gets a different response.
If it's multi-player, and you expect remote nodes to be able
to re-simulate
what the local node is doing, you need to make sure that all
instances of
the same object across the network use the same local sector
for the same
simulation work.
Typically, in this system, your global position address looks
something
int sectorId;
float x, y, z;
Another problem with this representation is that calculating
distance to
other
objects becomes harder; at a minimum, you have to look up a
"global center"
for each using the sectorId; if distances can grow large and
you need good
precision, then those global centers have to be stored in
doubles and the
math
has to be done in doubles anyway. Not to mention that the
table of global
centers for something as big as a planet would be huge; at
that point, using
double x, y, z;
starts looking pretty good :-) Not for render data, say, but
for object
position in world type data, which by extension then includes
much physics
code.
Cheers,
/ h+
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
De Boer
2003-10-09 02:48:04 UTC
Permalink
Post by Jon Jansen
'1cm accuracy' sounds like a lot until you see what happens when a
slow-moving object (e.g. a slow-moving character) is quantised to a
1cm grid.
I had a similar problem using the quake3 engine. I needed 1 millimetre
accuracy and it had about 1cm accuracy. The house I had used bolts on
rafters and they turned into really strange shapes and objects appeared on
top of each other increasing Z fighting due to the rounding. By increasing
the scale the problems reduced, but since there was a maximum grid size you
couldn't scale very much. Quake used different method for drawing "objects"
than "brushes" (and a bolt could aguably be an object) but even some of my
walls needed better than 1 cm accuracy.

Anyhow I think mm accuracy is better, at least for situations like building
a house from a set of plans that use mm accuracy.

-Ryan De Boer
Tom Forsyth
2003-10-09 02:51:02 UTC
Permalink
I'm not sure why you need multiple frames of reference. Storing your
positions with int64s gives you enough precision to store the entire solar
system at micrometer precision.

I'm pretty sure the only operations you do with object positions are to
increment them when you're moving stuff about, and subtract one from another
(to produce a standard 3*float vector) when you're doing collision detection
and rendering.

If you have a frame of reference with a scale, then you're basically doing
floating-point anyway. Your binary point is floating. :-) And that brings
along all the wierdness of floating-point - lumpy precision, etc. So if you
do need to store bigger worlds than a solar-system, then I would simply move
to larger integers in your WorldPosition class, rather than go to all the
evilness and hassle of multiple frames of reference.

Even on CPUS that don't handle int64s (and larger) natively, adds and subs
are extremely quick indeed.


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 09 October 2003 10:07
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
I was considering this one with respect to a networking
engine I've been
working on designed to operate in a complex universe, where
the scales could
range from cm accurate or better in, for example, a FPS on a
space station
up to massive Star Destroyer sized ships flying around the universe.
My idea was similar - to have a FrameOfReference class to
store a reference
origin and scale. All world positions would be relative to a
particular FOR,
and have manipulator code to be able to convert into other
FOR space to
allow normal vector operations to be done in the same
coordinate space.
Obviously the conversions are much cheaper if you don't allow
different
scales, but means you need more FORs to encompass the same
world-space. I
would assume that if your world space is of a fixed size and
you can create
a small enough set of reference origins which encompass your
game area and
still allow the accuracy you need, then you don't need to bother with
scales.
What I really need to do though is to write an algorithm
which, given a set
of objects each of which has a set scale (i.e. a required
accuracy level in
world space distance) and position, can come up with a
reasonably minimal
set of FORs which encompass those objects. That way you get
the minimal
number of conversions betwen FORs, while still preserving
accuracy over
large scale complex environments. Dynamic objects are fine,
as long as they
stay within the tolerance limits of a FOR - if they move out
of it then a
new FOR can be created and they shift into it - essentially
allowing moving
objects to carry their own accuracy with them.
I don't think this helps rendering issues at all (although
you might save
accuracy by doing camera->FOR->object transforms in an
efficient way), it
was just to sort out dynamics problems with scale.
ChrisC
-----Original Message-----
Sent: 07 October 2003 18:56
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
I prefer using a WorldPosition class. Then you can store
whatever you like
in it. The only way you can get a vector of floats out of a
WorldPosition is
relative to another WorldPosition (usually the camera for
rendering, or
something handy for gameplay stuff).
Personally I like u32 (if you can) or u64 (for big worlds)
inside the class
rather than using doubles - it's a lot more portable. Since the only
operations you can do on them are subtract two of them or add
two of them,
it's faster or equivalent speed on pretty much everything
(definately on PS2
of course).
Biggest advantage is absolutely predictable precision. You
never have to
worry about something working near the origin but not working
further away.
Tom Forsyth - Muckyfoot bloke and Microsoft MVP.
This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 07 October 2003 18:15
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Madoc Evans
everything relative to the local sector. So, the local
sector (where the
Post by Madoc Evans
camera is) is always the world coordinate system and only
very distant
Post by Madoc Evans
sectors would suffer from precision issues. Similarly, for
physics, where
Post by Madoc Evans
the interaction can only span to a neighbouring sector.
Assuming your artists don't build monster collision meshes...
(that's what
the +3 Knobbly Stick Of Artist Enlightenment is for, I
suppose -- Tom, can
I borrow yours?)
However, there are some subtle dangers with this approach.
For example,
you will get rounding problems when objects cross boundaries;
the change
in quantization may change "the same" position to something that's
actually different, and gets a different response.
If it's multi-player, and you expect remote nodes to be able
to re-simulate
what the local node is doing, you need to make sure that all
instances of
the same object across the network use the same local sector
for the same
simulation work.
Typically, in this system, your global position address looks
something
int sectorId;
float x, y, z;
Another problem with this representation is that calculating
distance to
other
objects becomes harder; at a minimum, you have to look up a
"global center"
for each using the sectorId; if distances can grow large and
you need good
precision, then those global centers have to be stored in
doubles and the
math
has to be done in doubles anyway. Not to mention that the
table of global
centers for something as big as a planet would be huge; at
that point, using
double x, y, z;
starts looking pretty good :-) Not for render data, say, but
for object
position in world type data, which by extension then includes
much physics
code.
Cheers,
/ h+
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
De Boer
2003-10-09 02:51:07 UTC
Permalink
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous streaming world in
Dungeon Siege actually touched on a >couple of the issues coming up here.

There are also many papers on using multiple sectors, typically they are
about large multi user environments.
Here is one paper almost all cite:

Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments. Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/

I thought that many of the MMPOG games would use similar algorithms. Anyone
developing a MMPOG game using this type of algorithm?

-Ryan De Boer
Charles Bloom
2003-10-09 08:27:09 UTC
Permalink
Storing position in integers sounds nice, and in fact 32-bits of integer
position is mighty good. You generally need about 0.1 mm accuracy, so you
have about 250 miles of range.

The problem I have with this is that you end up having to do a lot of
float-to-int conversions, which are still mighty slow. You want to use
doubles to do your intermediate math, for accuracy reasons, and because
velocities and accelerations and such will be much easier to deal with as
doubles. I suppose this ftoi() is ok on a per-game-object basis, but
probably not ok for little bits of shrapnel and projectiles and things of
which there will be very many.


--------------------------------------------------------------------------------------------
Charles Bloom email "cb" http://www.cbloom.com
Chris Chapman
2003-10-09 08:28:04 UTC
Permalink
A MMOG is exactly the environment I am developing for. I hadn't run across
that paper yet - it described fairly closely the system I was talking about.
Nice to know I'm 7 years behind the times :).

With regards to Tom's point, I wanted multiple frames of reference for two
main reasons: 1) The differences between scales in the system are going to
be massive. So FPS need micrometer precision, but space combat simulators
deal with objects travelling at thousands of meters per second, and these
objects will all be existing in the same universe. While it is unlikely the
objects defined in reference frames with such a massive difference would be
able to interact, it seemed cleaner to come up with a coordinate system
which didn't make that assumption.

2) I wanted objects in the same frame of reference to be able to describe
each other without having to do any reference conversion, i.e. in terms of a
3 float single precision vector, which the bulk of code I have at the moment
assumes. In terms of network traffic, communicating 64-bit reference points
for everything is infeasible - object interaction needs to be represented in
the minimal amount of data.

I did make the assumption that the reference points would be fixed in space
- mostly for network bandwidth issues, but also because of the cost of
converting objects between reference frames.

It may be that I have over-estimated the problem of precision and am
over-engineering a solution to compensate, but I didn't want the engine to
be limited by precision isses. :)


-----Original Message-----
From: De Boer [mailto:***@iinet.net.au]
Sent: 09 October 2003 10:50
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous streaming world in
Dungeon Siege actually touched on a >couple of the issues coming up here.

There are also many papers on using multiple sectors, typically they are
about large multi user environments.
Here is one paper almost all cite:

Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments. Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/

I thought that many of the MMPOG games would use similar algorithms. Anyone
developing a MMPOG game using this type of algorithm?

-Ryan De Boer



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Gribb, Gil
2003-10-09 08:29:08 UTC
Permalink
Actually, in this day and age, the clocks that an indivdual instruction takes are very rarely an issue. It almost always comes down to memory bandwidth...i.e. getting the stuff in and out of the cpu, not what you do when it in the cpu. So when I say "doubles are slow" I am simply talking about the fact that they take twice the memory bandwidth. There are exceptions to this, of course, but mostly instruction clocks aren't very important anymore.

-Gil

-----Original Message-----
From: Stuart Harrison [mailto:***@kuju.com]
Sent: Thursday, October 09, 2003 3:44 AM
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
[snip]
Another deciding factor for me is speed; integral types are generally
*much* faster on the CPU, considering how (Pentium 2 and above) have
multiple integer processors that can run multiple operations
per cycle.
I've done some investigation on this recently and (apologies for getting
slightly off-topic at this point) Pentium 4s are actually listed as
being *slower* at doing some integer maths than doing floating-point
maths, notably multiplication and division.

The expensive floating point operations are (for the Pentium family at
least, I can't speak for any others with any authority):
1, compare "if (fp1 < 0.0f)" - this case will almost certainly turn up
as a bottleneck in most applications when profiled. There was a
discussion thread on this list about this very problem recently (raised
by me, IIRC).
2, add / subtract (certainly compared to integer equivalents).
3, trigonometrics (sin, cos, etc).

You also need to bear in mind that (again, on Pentiums) there is a
floating-point precision flag that can be altered to speed calculations
up if accuracy is not important (or vice versa), and if left unset
defaults to high precision, hence slow speed (IIRC).

Your example appears to play to the strengths of integers (adding /
subtraction / comparison), and the weakness of floats. You may also
find your compiler is not optimising some of the fp code paths (did you
run an fully-optimised version as the test bed, or a 'debug' version?).

I'd be interested in seeing your code for the steady-state problem, and
so convince myself that fixed point can be faster - any chance you could
email it to me (***@kuju.com)?

Thanks,
-Dino.


Information contained in this e-mail is intended for the use of the addressee only, and is confidential and may be the subject of Legal Professional Privilege. Any dissemination, distribution, copying or use of this communication without prior permission of the addressee is strictly prohibited.The views of the author may not necessarily constitute the views of Kuju Entertainment Ltd. Nothing in this email shall bind Kuju Entertainment Ltd in any contract or obligation.

The contents of an attachment to this e-mail may contain software viruses which could damage your own computer system. While Kuju Entertainment has taken every reasonable precaution to minimise this risk, we cannot accept liability for any damage which you sustain as a result of software viruses. You should carry out your own virus checks before opening the attachment.


-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_ida88
Tom Forsyth
2003-10-09 09:10:05 UTC
Permalink
...except on PS2. Doubles are complete and utter doom, even in the
frighteningly rare case that the data is already in the cache.

Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 09 October 2003 16:28
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Actually, in this day and age, the clocks that an indivdual
instruction takes are very rarely an issue. It almost always
comes down to memory bandwidth...i.e. getting the stuff in
and out of the cpu, not what you do when it in the cpu. So
when I say "doubles are slow" I am simply talking about the
fact that they take twice the memory bandwidth. There are
exceptions to this, of course, but mostly instruction clocks
aren't very important anymore.
-Gil
-----Original Message-----
Sent: Thursday, October 09, 2003 3:44 AM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
[snip]
Another deciding factor for me is speed; integral types are
generally
*much* faster on the CPU, considering how (Pentium 2 and above) have
multiple integer processors that can run multiple operations
per cycle.
I've done some investigation on this recently and (apologies
for getting
slightly off-topic at this point) Pentium 4s are actually listed as
being *slower* at doing some integer maths than doing floating-point
maths, notably multiplication and division.
The expensive floating point operations are (for the Pentium family at
1, compare "if (fp1 < 0.0f)" - this case will almost certainly turn up
as a bottleneck in most applications when profiled. There was a
discussion thread on this list about this very problem
recently (raised
by me, IIRC).
2, add / subtract (certainly compared to integer equivalents).
3, trigonometrics (sin, cos, etc).
You also need to bear in mind that (again, on Pentiums) there is a
floating-point precision flag that can be altered to speed
calculations
up if accuracy is not important (or vice versa), and if left unset
defaults to high precision, hence slow speed (IIRC).
Your example appears to play to the strengths of integers (adding /
subtraction / comparison), and the weakness of floats. You may also
find your compiler is not optimising some of the fp code
paths (did you
run an fully-optimised version as the test bed, or a 'debug'
version?).
I'd be interested in seeing your code for the steady-state
problem, and
so convince myself that fixed point can be faster - any
chance you could
Thanks,
-Dino.
Information contained in this e-mail is intended for the use
of the addressee only, and is confidential and may be the
subject of Legal Professional Privilege. Any dissemination,
distribution, copying or use of this communication without
prior permission of the addressee is strictly prohibited.The
views of the author may not necessarily constitute the views
of Kuju Entertainment Ltd. Nothing in this email shall bind
Kuju Entertainment Ltd in any contract or obligation.
The contents of an attachment to this e-mail may contain
software viruses which could damage your own computer system.
While Kuju Entertainment has taken every reasonable
precaution to minimise this risk, we cannot accept liability
for any damage which you sustain as a result of software
viruses. You should carry out your own virus checks before
opening the attachment.
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_ida88
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_ida88
Chris Chapman
2003-10-09 09:13:14 UTC
Permalink
A MMOG is exactly the environment I am developing for. I hadn't run across
that paper yet - it described fairly closely the system I was talking about.
Nice to know I'm 7 years behind the times :).

With regards to Tom's point, I wanted multiple frames of reference for two
main reasons: 1) The differences between scales in the system are going to
be massive. So FPS need micrometer precision, but space combat simulators
deal with objects travelling at thousands of meters per second, and these
objects will all be existing in the same universe. While it is unlikely the
objects defined in reference frames with such a massive difference would be
able to interact, it seemed cleaner to come up with a coordinate system
which didn't make that assumption.

2) I wanted objects in the same frame of reference to be able to describe
each other without having to do any reference conversion, i.e. in terms of a
3 float single precision vector, which the bulk of code I have at the moment
assumes. In terms of network traffic, communicating 64-bit reference points
for everything is infeasible - object interaction needs to be represented in
the minimal amount of data.

I did make the assumption that the reference points would be fixed in space
- mostly for network bandwidth issues, but also because of the cost of
converting objects between reference frames.

It may be that I have over-estimated the problem of precision and am
over-engineering a solution to compensate, but I didn't want the engine to
be limited by precision isses. :)


-----Original Message-----
From: De Boer [mailto:***@iinet.net.au]
Sent: 09 October 2003 10:50
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous streaming world in
Dungeon Siege actually touched on a >couple of the issues coming up here.

There are also many papers on using multiple sectors, typically they are
about large multi user environments.
Here is one paper almost all cite:

Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments. Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/

I thought that many of the MMPOG games would use similar algorithms. Anyone
developing a MMPOG game using this type of algorithm?

-Ryan De Boer



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Simon Fenney
2003-10-09 09:36:04 UTC
Permalink
Post by Charles Bloom
Storing position in integers sounds nice, and in fact 32-bits
of integer
position is mighty good. You generally need about 0.1 mm
accuracy, so you
have about 250 miles of range.
The problem I have with this is that you end up having to do a lot of
float-to-int conversions, which are still mighty slow. You
want to use doubles to do your intermediate math, for accuracy reasons,
and because velocities and accelerations and such will be much easier to
deal with as
doubles. I suppose this ftoi() is ok on a per-game-object basis, but
probably not ok for little bits of shrapnel and projectiles
and things of
which there will be very many.
You want to do a lot of fast float to int conversions?

Why not use the old kludge trick that adds a pre-determined float constant
to your values?
(It's some power of 2 that I can't remember). You then save your converted
doubles "to memory" and then pick up the int by reading the least-sig 32
bits.

I used to use this in a prehistoric (well ~1995) PowerVR driver.

Simon
Pierre Terdiman
2003-10-09 10:41:09 UTC
Permalink
Post by Simon Fenney
Why not use the old kludge trick that adds a pre-determined float constant
to your values?
You can also compile with /QIfist and forget about the issue.
Tom Forsyth
2003-10-09 10:11:08 UTC
Permalink
I assert (with only hand-wavy proofs) that:

(1) using a vector of int32s to store position always has fewer precision
problems than using a vector of floats, and speed is the same or better.

(2) if you find that a vector of int32s does not give you sufficient
precision for your game then there is _no way_ that a vector of floats is
suitable either.

(3) using int64s always has fewer precision problems than using floats, and
the speed and size difference is trivial (i.e. unimportant) in most cases.

(4) using int64s always has fewer precision problems than using doubles, and
speed is usually better on most machines, possibly the same (because it's
limited by memory size not execution), or a gajillion times better because
the platform is software-emulating floating-point doubles.


If your network traffic is predictive deltas rather than exact lockstep
data, then floats will work either way for the transmitted data. Though you
can probably use float16s instead and not notice the difference in quality.


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 09 October 2003 15:56
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
A MMOG is exactly the environment I am developing for. I
hadn't run across
that paper yet - it described fairly closely the system I was
talking about.
Nice to know I'm 7 years behind the times :).
With regards to Tom's point, I wanted multiple frames of
reference for two
main reasons: 1) The differences between scales in the system
are going to
be massive. So FPS need micrometer precision, but space
combat simulators
deal with objects travelling at thousands of meters per
second, and these
objects will all be existing in the same universe. While it
is unlikely the
objects defined in reference frames with such a massive
difference would be
able to interact, it seemed cleaner to come up with a
coordinate system
which didn't make that assumption.
2) I wanted objects in the same frame of reference to be
able to describe
each other without having to do any reference conversion,
i.e. in terms of a
3 float single precision vector, which the bulk of code I
have at the moment
assumes. In terms of network traffic, communicating 64-bit
reference points
for everything is infeasible - object interaction needs to be
represented in
the minimal amount of data.
I did make the assumption that the reference points would be
fixed in space
- mostly for network bandwidth issues, but also because of the cost of
converting objects between reference frames.
It may be that I have over-estimated the problem of precision and am
over-engineering a solution to compensate, but I didn't want
the engine to
be limited by precision isses. :)
-----Original Message-----
Sent: 09 October 2003 10:50
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous
streaming world in
Dungeon Siege actually touched on a >couple of the issues
coming up here.
There are also many papers on using multiple sectors,
typically they are
about large multi user environments.
Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments.
Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/
I thought that many of the MMPOG games would use similar
algorithms. Anyone
developing a MMPOG game using this type of algorithm?
-Ryan De Boer
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Tom Forsyth
2003-10-09 10:16:11 UTC
Permalink
Also, most of your ops will be itof - when you subtract one position from
another and return a vec(3*float). The only time you do ftoi is when moving
an object around. Which is once per object per frame (unless your code is
very strange). I refuse to believe this will appear in your profile if you
use the trick Simon talks about.

Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 09 October 2003 17:35
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Charles Bloom
Storing position in integers sounds nice, and in fact 32-bits
of integer
position is mighty good. You generally need about 0.1 mm
accuracy, so you
have about 250 miles of range.
The problem I have with this is that you end up having to do
a lot of
Post by Charles Bloom
float-to-int conversions, which are still mighty slow. You
want to use doubles to do your intermediate math, for
accuracy reasons,
Post by Charles Bloom
and because velocities and accelerations and such will be
much easier to
Post by Charles Bloom
deal with as
doubles. I suppose this ftoi() is ok on a per-game-object
basis, but
Post by Charles Bloom
probably not ok for little bits of shrapnel and projectiles
and things of
which there will be very many.
You want to do a lot of fast float to int conversions?
Why not use the old kludge trick that adds a pre-determined
float constant
to your values?
(It's some power of 2 that I can't remember). You then save
your converted
doubles "to memory" and then pick up the int by reading the
least-sig 32
bits.
I used to use this in a prehistoric (well ~1995) PowerVR driver.
Simon
Jonathan Blow
2003-10-09 10:53:08 UTC
Permalink
Post by Tom Forsyth
Also, most of your ops will be itof - when you subtract one position from
another and return a vec(3*float). The only time you do ftoi is when moving
an object around. Which is once per object per frame (unless your code is
very strange). I refuse to believe this will appear in your profile if you
use the trick Simon talks about.
Thirded. Doing your own float-to-int is really fast; the slowness when doing
it in C comes from crap to set and reset the floating-point rounding mode (to
ensure rounding semantics that meet the language spec) that you really
don't care about. Though I suspect Charles knows this already (?!) and
is objecting to something else?
Charles Bloom
2003-10-09 11:52:06 UTC
Permalink
At 12:52 PM 10/9/2003 -0500, Jonathan Blow wrote:
Kenneth Baird
2003-10-09 12:58:04 UTC
Permalink
Hmm back in 69 when I actually did asm, fistp was 6 clocks. I could be
off but that's what I remember. BUT it did stall every other operation
till it finished.

The beauty of the magic number trick was that you could get the adds
running concurrently and mix in the integer subracts and movs and such
to keep from boggin down the instruction decoder. If you had multiple
floats to store out that is. I think fistp was actually faster if you
just had a single float to store out.

Kenneth
Jonathan Blow
2003-10-09 16:01:04 UTC
Permalink
Yeah, fistp was 6 clocks on the Pentium 1, not sure how it went
on later chips. I would be kinda surprised if it were really 20
clocks on a p4 because you can emulate it in a small number of
instructions -- but then again I don't know how many locks loads
and adds are on a p4 either. So out of it these days.

----- Original Message -----
From: "Kenneth Baird" <***@darktidings.com>
To: <gdalgorithms-***@lists.sourceforge.net>
Sent: Thursday, October 09, 2003 2:49 PM
Subject: Re: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Kenneth Baird
Hmm back in 69 when I actually did asm, fistp was 6 clocks. I could be
off but that's what I remember. BUT it did stall every other operation
till it finished.
The beauty of the magic number trick was that you could get the adds
running concurrently and mix in the integer subracts and movs and such
to keep from boggin down the instruction decoder. If you had multiple
floats to store out that is. I think fistp was actually faster if you
just had a single float to store out.
Kenneth
Chris Chapman
2003-10-09 10:29:02 UTC
Permalink
A MMOG is exactly the environment I am developing for. I hadn't run across
that paper yet - it described fairly closely the system I was talking about.
Nice to know I'm 7 years behind the times :).

With regards to Tom's point, I wanted multiple frames of reference for two
main reasons: 1) The differences between scales in the system are going to
be massive. So FPS need micrometer precision, but space combat simulators
deal with objects travelling at thousands of meters per second, and these
objects will all be existing in the same universe. While it is unlikely the
objects defined in reference frames with such a massive difference would be
able to interact, it seemed cleaner to come up with a coordinate system
which didn't make that assumption.

2) I wanted objects in the same frame of reference to be able to describe
each other without having to do any reference conversion, i.e. in terms of a
3 float single precision vector, which the bulk of code I have at the moment
assumes. In terms of network traffic, communicating 64-bit reference points
for everything is infeasible - object interaction needs to be represented in
the minimal amount of data.

I did make the assumption that the reference points would be fixed in space
- mostly for network bandwidth issues, but also because of the cost of
converting objects between reference frames.

It may be that I have over-estimated the problem of precision and am
over-engineering a solution to compensate, but I didn't want the engine to
be limited by precision isses. :)


-----Original Message-----
From: De Boer [mailto:***@iinet.net.au]
Sent: 09 October 2003 10:50
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous streaming world in
Dungeon Siege actually touched on a >couple of the issues coming up here.

There are also many papers on using multiple sectors, typically they are
about large multi user environments.
Here is one paper almost all cite:

Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments. Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/

I thought that many of the MMPOG games would use similar algorithms. Anyone
developing a MMPOG game using this type of algorithm?

-Ryan De Boer



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
p***@playstation.sony.com
2003-10-09 10:49:09 UTC
Permalink
Post by Charles Bloom
The problem I have with this is that you end up having to do a lot of
float-to-int conversions, which are still mighty slow.

If you know your float is in a particular range, you can do ftoi's (and
itof's) very quickly using bit tricks. Our PS2 engine does the final ftoi
in the projection transform.
Post by Charles Bloom
You want to use doubles to do your intermediate math,
Again, is anyone anticipating 4x64 bit fp hardware anytime soon? Using
double precision for games is overkill.

Cheers,
Phil
Paul Du Bois
2003-10-09 11:32:07 UTC
Permalink
Post by Charles Bloom
float-to-int conversions, which are still mighty slow. You
Yeah, even the fastest ftol replacements I've seen are still a
big pile of instructions.

But at the risk of getting a little platform-specific, it seems
to me that for the purposes of this float-to-int conversion you'd
actually want to round instead of truncate. If you keep your rounding
mode at the default "round to even" then you can get away (on ia32) with
just doing a fld/fistp, which I don't think would be a problem even if
you
were doing it a few 100K times a frame.

p
Tom Forsyth
2003-10-09 12:25:07 UTC
Permalink
For projectiles and particles it probably doesn't matter too much if you
have a dodgy bottom bit. So the add-big-number hack should be fine.

It's crazy that fistp is so slow. Stuff like the PowerPC does it in under a
clock cycle (depends how well it pipelines, etc)

Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 09 October 2003 18:58
Subject: Re: [Algorithms] World size vs. floats [bcc][fake adr]
Daniel Vogel
2003-10-09 13:24:07 UTC
Permalink
There are some neat SSE instructions for float to int that even do
truncation.

SSE1: cvttss2si
SSE2: cvttps2dq

-- Daniel, Epic Games Inc.
Post by Gribb, Gil
-----Original Message-----
Behalf Of Charles Bloom
Sent: Thursday, October 09, 2003 1:58 PM
Subject: Re: [Algorithms] World size vs. floats [bcc][fake adr]
Jamie Fowlston
2003-10-09 14:13:06 UTC
Permalink
is it safe to assume your points of reference don't move (in world space)?
If you have a space station, its centre may be a sensible point of
reference, but if it's orbiting a planet....

Jamie


-----Original Message-----
From: gdalgorithms-list-***@lists.sourceforge.net
[mailto:gdalgorithms-list-***@lists.sourceforge.net]On Behalf Of Chris
Chapman
Sent: 09 October 2003 15:56
To: 'gdalgorithms-***@lists.sourceforge.net'
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]


A MMOG is exactly the environment I am developing for. I hadn't run across
that paper yet - it described fairly closely the system I was talking about.
Nice to know I'm 7 years behind the times :).

With regards to Tom's point, I wanted multiple frames of reference for two
main reasons: 1) The differences between scales in the system are going to
be massive. So FPS need micrometer precision, but space combat simulators
deal with objects travelling at thousands of meters per second, and these
objects will all be existing in the same universe. While it is unlikely the
objects defined in reference frames with such a massive difference would be
able to interact, it seemed cleaner to come up with a coordinate system
which didn't make that assumption.

2) I wanted objects in the same frame of reference to be able to describe
each other without having to do any reference conversion, i.e. in terms of a
3 float single precision vector, which the bulk of code I have at the moment
assumes. In terms of network traffic, communicating 64-bit reference points
for everything is infeasible - object interaction needs to be represented in
the minimal amount of data.

I did make the assumption that the reference points would be fixed in space
- mostly for network bandwidth issues, but also because of the cost of
converting objects between reference frames.

It may be that I have over-estimated the problem of precision and am
over-engineering a solution to compensate, but I didn't want the engine to
be limited by precision isses. :)


-----Original Message-----
From: De Boer [mailto:***@iinet.net.au]
Sent: 09 October 2003 10:50
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous streaming world in
Dungeon Siege actually touched on a >couple of the issues coming up here.

There are also many papers on using multiple sectors, typically they are
about large multi user environments.
Here is one paper almost all cite:

Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments. Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/

I thought that many of the MMPOG games would use similar algorithms. Anyone
developing a MMPOG game using this type of algorithm?

-Ryan De Boer



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188


-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Chris Chapman
2003-10-09 14:45:05 UTC
Permalink
A MMOG is exactly the environment I am developing for. I hadn't run across
that paper yet - it described fairly closely the system I was talking about.
Nice to know I'm 7 years behind the times :).

With regards to Tom's point, I wanted multiple frames of reference for two
main reasons: 1) The differences between scales in the system are going to
be massive. So FPS need micrometer precision, but space combat simulators
deal with objects travelling at thousands of meters per second, and these
objects will all be existing in the same universe. While it is unlikely the
objects defined in reference frames with such a massive difference would be
able to interact, it seemed cleaner to come up with a coordinate system
which didn't make that assumption.

2) I wanted objects in the same frame of reference to be able to describe
each other without having to do any reference conversion, i.e. in terms of a
3 float single precision vector, which the bulk of code I have at the moment
assumes. In terms of network traffic, communicating 64-bit reference points
for everything is infeasible - object interaction needs to be represented in
the minimal amount of data.

I did make the assumption that the reference points would be fixed in space
- mostly for network bandwidth issues, but also because of the cost of
converting objects between reference frames.

It may be that I have over-estimated the problem of precision and am
over-engineering a solution to compensate, but I didn't want the engine to
be limited by precision isses. :)


-----Original Message-----
From: De Boer [mailto:***@iinet.net.au]
Sent: 09 October 2003 10:50
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous streaming world in
Dungeon Siege actually touched on a >couple of the issues coming up here.

There are also many papers on using multiple sectors, typically they are
about large multi user environments.
Here is one paper almost all cite:

Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments. Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/

I thought that many of the MMPOG games would use similar algorithms. Anyone
developing a MMPOG game using this type of algorithm?

-Ryan De Boer



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Chris Chapman
2003-10-10 02:53:05 UTC
Permalink
Nope, you're absolutely right. I do remember considering that case in my
original design, but it seems to have been lost in later revisions (possibly
it scared me enough that my subconscious blocked it out :)

I don't think that should change the logic of the system, only the
management of the reference points. It does make the transition between
reference frames more vulnerable to lag issues, although it could be argued
that moving reference frames should have entirely predicable motion.

Let me throw out a sample implementation just to see if I am thinking along
the same lines as others here. Assuming objects in the same reference frame
use a 3 x float vector to describe their position/motion, and that reference
frames themselves are described with 3 x 64-bit integers. The scale of the
coordinate system for the reference frames can be defined with a single
float scale.

To convert from one frame of reference to another would be

position[B] = position[A] + ((origin[A] - origin[B]) * RefScale)

Given that ((origin[A] - origin[B]) * scale) is 3 64 bit additions, 3 64
bit->float conversions and a multiply, and which doesn't change per object,
that leaves the conversion as just a 3 float vector addition per game
object.

If we allow reference frames to have different scales then the conversion
becomes
position[B] = ((position[A] / scaleA) + ((origin[A] - origin[B]) *
RefScale)) * scaleB)

which expands to a 3 float vector scalar multiply, then add, then multiply
again per game object


If it was to be implemented in all integer form with a conversion to floats
at the end, the first form (no scaling) would be okay, you would just
convert ((origin[A] - origin[B]) * RefScale) back into a 64-bit (or probably
more usefully 32-bit) integer form at the end, and all position conversions
become integer additions. However, wouldn't that make the scaling conversion
nasty? The scaled conversion has to do a ((integer vector/float) + integer
vector) * float, with a final float->integer vector conversion to make
position[B].

-----Original Message-----
From: Jamie Fowlston [mailto:***@qubesoft.com]
Sent: 09 October 2003 22:12
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]


is it safe to assume your points of reference don't move (in world space)?
If you have a space station, its centre may be a sensible point of
reference, but if it's orbiting a planet....

Jamie


-----Original Message-----
From: gdalgorithms-list-***@lists.sourceforge.net
[mailto:gdalgorithms-list-***@lists.sourceforge.net]On Behalf Of Chris
Chapman
Sent: 09 October 2003 15:56
To: 'gdalgorithms-***@lists.sourceforge.net'
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]


A MMOG is exactly the environment I am developing for. I hadn't run across
that paper yet - it described fairly closely the system I was talking about.
Nice to know I'm 7 years behind the times :).

With regards to Tom's point, I wanted multiple frames of reference for two
main reasons: 1) The differences between scales in the system are going to
be massive. So FPS need micrometer precision, but space combat simulators
deal with objects travelling at thousands of meters per second, and these
objects will all be existing in the same universe. While it is unlikely the
objects defined in reference frames with such a massive difference would be
able to interact, it seemed cleaner to come up with a coordinate system
which didn't make that assumption.

2) I wanted objects in the same frame of reference to be able to describe
each other without having to do any reference conversion, i.e. in terms of a
3 float single precision vector, which the bulk of code I have at the moment
assumes. In terms of network traffic, communicating 64-bit reference points
for everything is infeasible - object interaction needs to be represented in
the minimal amount of data.

I did make the assumption that the reference points would be fixed in space
- mostly for network bandwidth issues, but also because of the cost of
converting objects between reference frames.

It may be that I have over-estimated the problem of precision and am
over-engineering a solution to compensate, but I didn't want the engine to
be limited by precision isses. :)


-----Original Message-----
From: De Boer [mailto:***@iinet.net.au]
Sent: 09 October 2003 10:50
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous streaming world in
Dungeon Siege actually touched on a >couple of the issues coming up here.

There are also many papers on using multiple sectors, typically they are
about large multi user environments.
Here is one paper almost all cite:

Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments. Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/

I thought that many of the MMPOG games would use similar algorithms. Anyone
developing a MMPOG game using this type of algorithm?

-Ryan De Boer



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188


-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Chris Chapman
2003-10-10 03:46:21 UTC
Permalink
Nope, you're absolutely right. I do remember considering that case in my
original design, but it seems to have been lost in later revisions (possibly
it scared me enough that my subconscious blocked it out :)

I don't think that should change the logic of the system, only the
management of the reference points. It does make the transition between
reference frames more vulnerable to lag issues, although it could be argued
that moving reference frames should have entirely predicable motion.

Let me throw out a sample implementation just to see if I am thinking along
the same lines as others here. Assuming objects in the same reference frame
use a 3 x float vector to describe their position/motion, and that reference
frames themselves are described with 3 x 64-bit integers. The scale of the
coordinate system for the reference frames can be defined with a single
float scale.

To convert from one frame of reference to another would be

position[B] = position[A] + ((origin[A] - origin[B]) * RefScale)

Given that ((origin[A] - origin[B]) * scale) is 3 64 bit additions, 3 64
bit->float conversions and a multiply, and which doesn't change per object,
that leaves the conversion as just a 3 float vector addition per game
object.

If we allow reference frames to have different scales then the conversion
becomes
position[B] = ((position[A] / scaleA) + ((origin[A] - origin[B]) *
RefScale)) * scaleB)

which expands to a 3 float vector scalar multiply, then add, then multiply
again per game object


If it was to be implemented in all integer form with a conversion to floats
at the end, the first form (no scaling) would be okay, you would just
convert ((origin[A] - origin[B]) * RefScale) back into a 64-bit (or probably
more usefully 32-bit) integer form at the end, and all position conversions
become integer additions. However, wouldn't that make the scaling conversion
nasty? The scaled conversion has to do a ((integer vector/float) + integer
vector) * float, with a final float->integer vector conversion to make
position[B].

-----Original Message-----
From: Jamie Fowlston [mailto:***@qubesoft.com]
Sent: 09 October 2003 22:12
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]


is it safe to assume your points of reference don't move (in world space)?
If you have a space station, its centre may be a sensible point of
reference, but if it's orbiting a planet....

Jamie


-----Original Message-----
From: gdalgorithms-list-***@lists.sourceforge.net
[mailto:gdalgorithms-list-***@lists.sourceforge.net]On Behalf Of Chris
Chapman
Sent: 09 October 2003 15:56
To: 'gdalgorithms-***@lists.sourceforge.net'
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]


A MMOG is exactly the environment I am developing for. I hadn't run across
that paper yet - it described fairly closely the system I was talking about.
Nice to know I'm 7 years behind the times :).

With regards to Tom's point, I wanted multiple frames of reference for two
main reasons: 1) The differences between scales in the system are going to
be massive. So FPS need micrometer precision, but space combat simulators
deal with objects travelling at thousands of meters per second, and these
objects will all be existing in the same universe. While it is unlikely the
objects defined in reference frames with such a massive difference would be
able to interact, it seemed cleaner to come up with a coordinate system
which didn't make that assumption.

2) I wanted objects in the same frame of reference to be able to describe
each other without having to do any reference conversion, i.e. in terms of a
3 float single precision vector, which the bulk of code I have at the moment
assumes. In terms of network traffic, communicating 64-bit reference points
for everything is infeasible - object interaction needs to be represented in
the minimal amount of data.

I did make the assumption that the reference points would be fixed in space
- mostly for network bandwidth issues, but also because of the cost of
converting objects between reference frames.

It may be that I have over-estimated the problem of precision and am
over-engineering a solution to compensate, but I didn't want the engine to
be limited by precision isses. :)


-----Original Message-----
From: De Boer [mailto:***@iinet.net.au]
Sent: 09 October 2003 10:50
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous streaming world in
Dungeon Siege actually touched on a >couple of the issues coming up here.

There are also many papers on using multiple sectors, typically they are
about large multi user environments.
Here is one paper almost all cite:

Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments. Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/

I thought that many of the MMPOG games would use similar algorithms. Anyone
developing a MMPOG game using this type of algorithm?

-Ryan De Boer



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188


-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Tom Forsyth
2003-10-10 03:48:22 UTC
Permalink
Post by Chris Chapman
If it was to be implemented in all integer form with a
conversion to floats
at the end, the first form (no scaling) would be okay, you would just
But if it was all integers, there would be no need for any reference frames
at all. To find relative directions you do 3 integer subtracts, 3
int-to-float conversions, and then a constant scale to change from the
fixed-point representation to something useful like meters.

Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Chris Chapman
-----Original Message-----
Sent: 10 October 2003 10:47
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Nope, you're absolutely right. I do remember considering that
case in my
original design, but it seems to have been lost in later
revisions (possibly
it scared me enough that my subconscious blocked it out :)
I don't think that should change the logic of the system, only the
management of the reference points. It does make the
transition between
reference frames more vulnerable to lag issues, although it
could be argued
that moving reference frames should have entirely predicable motion.
Let me throw out a sample implementation just to see if I am
thinking along
the same lines as others here. Assuming objects in the same
reference frame
use a 3 x float vector to describe their position/motion, and
that reference
frames themselves are described with 3 x 64-bit integers. The
scale of the
coordinate system for the reference frames can be defined
with a single
float scale.
To convert from one frame of reference to another would be
position[B] = position[A] + ((origin[A] - origin[B]) * RefScale)
Given that ((origin[A] - origin[B]) * scale) is 3 64 bit
additions, 3 64
bit->float conversions and a multiply, and which doesn't
change per object,
that leaves the conversion as just a 3 float vector addition per game
object.
If we allow reference frames to have different scales then
the conversion
becomes
position[B] = ((position[A] / scaleA) + ((origin[A] -
origin[B]) *
RefScale)) * scaleB)
which expands to a 3 float vector scalar multiply, then add,
then multiply
again per game object
If it was to be implemented in all integer form with a
conversion to floats
at the end, the first form (no scaling) would be okay, you would just
convert ((origin[A] - origin[B]) * RefScale) back into a
64-bit (or probably
more usefully 32-bit) integer form at the end, and all
position conversions
become integer additions. However, wouldn't that make the
scaling conversion
nasty? The scaled conversion has to do a ((integer
vector/float) + integer
vector) * float, with a final float->integer vector conversion to make
position[B].
-----Original Message-----
Sent: 09 October 2003 22:12
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
is it safe to assume your points of reference don't move (in
world space)?
If you have a space station, its centre may be a sensible point of
reference, but if it's orbiting a planet....
Jamie
-----Original Message-----
Behalf Of Chris
Chapman
Sent: 09 October 2003 15:56
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
A MMOG is exactly the environment I am developing for. I
hadn't run across
that paper yet - it described fairly closely the system I was
talking about.
Nice to know I'm 7 years behind the times :).
With regards to Tom's point, I wanted multiple frames of
reference for two
main reasons: 1) The differences between scales in the system
are going to
be massive. So FPS need micrometer precision, but space
combat simulators
deal with objects travelling at thousands of meters per
second, and these
objects will all be existing in the same universe. While it
is unlikely the
objects defined in reference frames with such a massive
difference would be
able to interact, it seemed cleaner to come up with a
coordinate system
which didn't make that assumption.
2) I wanted objects in the same frame of reference to be
able to describe
each other without having to do any reference conversion,
i.e. in terms of a
3 float single precision vector, which the bulk of code I
have at the moment
assumes. In terms of network traffic, communicating 64-bit
reference points
for everything is infeasible - object interaction needs to be
represented in
the minimal amount of data.
I did make the assumption that the reference points would be
fixed in space
- mostly for network bandwidth issues, but also because of the cost of
converting objects between reference frames.
It may be that I have over-estimated the problem of precision and am
over-engineering a solution to compensate, but I didn't want
the engine to
be limited by precision isses. :)
-----Original Message-----
Sent: 09 October 2003 10:50
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Allan Murphy
Scott Bilas' excellent GDC talk about the continuous
streaming world in
Dungeon Siege actually touched on a >couple of the issues
coming up here.
There are also many papers on using multiple sectors,
typically they are
about large multi user environments.
Locales and Beacons: Effcient and Precise Support
For Large Multi-User Virtual Environments
Barrus, J. W., Waters, R. C., and Anderson, D. B. (1996). Locales and
Beacons: Effcient and
Precise Support For Large Multi-User Virtual Environments.
Retrieved: March
1, 2003, from
http://www.merl.com/papers/TR95-16a/
I thought that many of the MMPOG games would use similar
algorithms. Anyone
developing a MMPOG game using this type of algorithm?
-Ryan De Boer
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Mike Biddlecombe
2003-10-10 14:03:11 UTC
Permalink
Maintaining a Frame of Reference (FoR) identifier, along with an offset
vector from the origin of that frame, was the key to the 'node space
position' that was used in Dungeon Siege.

The vector <X,Y,Z> becomes the 'SiegePos' <X,Y,Z,N>, where 'N' is some value
used to identify the FoR you are in. In GPG-speak, the FoR is a 'Siege
Node'.

Initially, the terrain system was designed (over-designed?) to eliminate the
precision problem in a continuous world. All of the other goodies were a
benefit of the time and effort we put into making it work and maintaining
it. As Scott mentions in his paper, there were wins with this system that
only came about once we starte to exploit the that fact that objects are
anchored only to their FoR.

The mantra of "there is no world space" was crucial in allowing
self-intersecting worlds. In our system, there's no reason why a series of
linked nodes can't wrap back upon itself, so that the 'distance' between
distinct positions <X0,Y0,Z0,N0> and <X1,Y1,Z1,N1> appears to be zero. This
opened up a ton of options for the level designers.

I know I don't have the math background to do a deep analysis (so I won't
try) but it seems to me that it doesn't matter how many bits you use for
your offset vector, you need some extra info if you want to allow your space
to be twisted around this way. Non-manifold? Non-Euclidean? Escherian? ...if
you know the proper name to call it, help me out here!

This brings me to the Achilles heel of the system. How do you explain it?
How can you convince people that its worth the hassle, especially when there
are much simpler ways to solve the precision problem?

I wish I'd done better job with my hand waving when I described the system
to the other programmers, most of whom just wanted a good old unified world
space where A-B=B-A and |A-B| == d (with d constant if A & B are constant!).
It can be confusing to grasp, especially if all it seems to do is make your
life even more complicated. My experience is that people really don't
appreciate hearing comments like "You need to call it Node Space and not
World Space..." for four years.

Having said that, if I was to do it over again I'd keep it all. In fact I'd
ditch vec3s altogether.

IMO, having the legacy vec3 around, and not implementing a really clear and
easy to use 'space' class, held us back and added extra cost to the project.
People kept converting to and from a SiegePos and 'camera relative' vec3 to
get their math done. This was a potentially expensive operation, so they'd
maintain a copy of this vector and then everything would break when the
camera moved. A general purpose system that instantiated a temporary FoR (to
track something like the flight of an arrow across multiple nodes) would
have gone a long way towards eliminating wasted/duplicated effort.

I'd also seriously consider using fixed point for the vector offsets. This
is something that we debated for a little while, but at the time it was
easier to augment our vec3 math code with a nodeid longword. I suppose it's
analogous to determining the best representation for a quaternion; once
you've decided that quats are a good thing. Essentially, if you can
determine the 'difference' between <0,0,0,N0> and <0,0,0,N1> to high enough
precision on the fly, you can limit the values in the vector offsets to as
few bits as possible by restricting the size of the space referenced by a
particular FoR.

If you are interested in more info, check out the GDC paper. Scott has it at
http://www.drizzle.com/~scottb/gdc/continuous-world.htm

Mike Biddlecombe
Gas Powered Games

-----Original Message-----
From: gdalgorithms-list-***@lists.sourceforge.net
[mailto:gdalgorithms-list-***@lists.sourceforge.net] On Behalf Of Allan
Murphy
Sent: Thursday, October 09, 2003 2:01 AM
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Jon Watte
Another problem with this representation is that calculating distance
to other objects becomes harder; at a minimum, you have to look up a
"global center"...
Scott Bilas' excellent GDC talk about the continuous streaming world in
Dungeon Siege actually touched on a couple of the issues coming up here. He
noted that because float wasn't anywhere near accurate enough for the size
of their world (since it is one continuous world across something like 40hrs
of wandering around gameplay), they had this exact system of sector/chunk
world positions and to calculate the distance between objects, they had to
do a kind of route find from source chunk to target chunk and accumulation
of distances instead of a straight geometric distance since there was no
world space, really.

He noted plenty of other non-obvious implications too, as you say - for
example if all the game objects won't fit in memory at once, deciding which
to keep cached and which to throw out, and all the horrible implications
this has for game logic.

Al
Tom Forsyth
2003-10-10 15:17:06 UTC
Permalink
I saw the GDC talk - I think I remember chatting to you there. It's
really cool tech, but I just wonder if it's cool tech for cool tech's
sake.

The benefits of a non-euclidian space seemed to be fairly minor (and in
fact quite irritating in places) compared to the problems you had.
There's nothing to stop people having multiple segments of the world
that co-exist even with a single world coordinate space - you just have
to make sure your long-range stuff is all done through portal/links, and
that nobody tries to ask questions like "I am here, so which sector am I
in?" because it doesn't have a single answer. But that's pretty easy to
do when you have the class that holds the answer or the question
(SiegePos/WorldPos/whatever) tightly controlled - just don't implement
those functions. But it sure makes shorter-range stuff like shooting
arrows over gorges, and creatures that fly, and long-range sniper
scopes, a fair bit easier.

I don't want to be dismissive, but what exactly _are_ the advantages?
The major one I can see is that if designers A, B and C are editing
sections that are linked in that order, designer B can shorten or
lengthen their bit arbitrarily, and you don't have to fiddle the
coordinate systems of the other two while they do it. But that seems a
bit of a small advantage - it's not exactly rocket-science to add an
offset to all the coordinates in a "chunk" when you burn it to CD.

TomF.
Post by Gribb, Gil
-----Original Message-----
Behalf Of Mike Biddlecombe
Sent: 10 October 2003 22:02
Subject: RE: [Algorithms] World size vs. floats
Maintaining a Frame of Reference (FoR) identifier, along with
an offset
vector from the origin of that frame, was the key to the 'node space
position' that was used in Dungeon Siege.
The vector <X,Y,Z> becomes the 'SiegePos' <X,Y,Z,N>, where
'N' is some value
used to identify the FoR you are in. In GPG-speak, the FoR is a 'Siege
Node'.
Initially, the terrain system was designed (over-designed?)
to eliminate the
precision problem in a continuous world. All of the other
goodies were a
benefit of the time and effort we put into making it work and
maintaining
it. As Scott mentions in his paper, there were wins with this
system that
only came about once we starte to exploit the that fact that
objects are
anchored only to their FoR.
The mantra of "there is no world space" was crucial in allowing
self-intersecting worlds. In our system, there's no reason
why a series of
linked nodes can't wrap back upon itself, so that the
'distance' between
distinct positions <X0,Y0,Z0,N0> and <X1,Y1,Z1,N1> appears to
be zero. This
opened up a ton of options for the level designers.
I know I don't have the math background to do a deep analysis
(so I won't
try) but it seems to me that it doesn't matter how many bits
you use for
your offset vector, you need some extra info if you want to
allow your space
to be twisted around this way. Non-manifold? Non-Euclidean?
Escherian? ...if
you know the proper name to call it, help me out here!
This brings me to the Achilles heel of the system. How do you
explain it?
How can you convince people that its worth the hassle,
especially when there
are much simpler ways to solve the precision problem?
I wish I'd done better job with my hand waving when I
described the system
to the other programmers, most of whom just wanted a good old
unified world
space where A-B=B-A and |A-B| == d (with d constant if A & B
are constant!).
It can be confusing to grasp, especially if all it seems to
do is make your
life even more complicated. My experience is that people really don't
appreciate hearing comments like "You need to call it Node
Space and not
World Space..." for four years.
Having said that, if I was to do it over again I'd keep it
all. In fact I'd
ditch vec3s altogether.
IMO, having the legacy vec3 around, and not implementing a
really clear and
easy to use 'space' class, held us back and added extra cost
to the project.
People kept converting to and from a SiegePos and 'camera
relative' vec3 to
get their math done. This was a potentially expensive
operation, so they'd
maintain a copy of this vector and then everything would
break when the
camera moved. A general purpose system that instantiated a
temporary FoR (to
track something like the flight of an arrow across multiple
nodes) would
have gone a long way towards eliminating wasted/duplicated effort.
I'd also seriously consider using fixed point for the vector
offsets. This
is something that we debated for a little while, but at the
time it was
easier to augment our vec3 math code with a nodeid longword.
I suppose it's
analogous to determining the best representation for a
quaternion; once
you've decided that quats are a good thing. Essentially, if you can
determine the 'difference' between <0,0,0,N0> and <0,0,0,N1>
to high enough
precision on the fly, you can limit the values in the vector
offsets to as
few bits as possible by restricting the size of the space
referenced by a
particular FoR.
If you are interested in more info, check out the GDC paper.
Scott has it at
http://www.drizzle.com/~scottb/gdc/continuous-world.htm
Mike Biddlecombe
Gas Powered Games
-----Original Message-----
Behalf Of Allan
Murphy
Sent: Thursday, October 09, 2003 2:01 AM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Jon Watte
Another problem with this representation is that
calculating distance
Post by Jon Watte
to other objects becomes harder; at a minimum, you have to
look up a
Post by Jon Watte
"global center"...
Scott Bilas' excellent GDC talk about the continuous
streaming world in
Dungeon Siege actually touched on a couple of the issues
coming up here. He
noted that because float wasn't anywhere near accurate enough
for the size
of their world (since it is one continuous world across
something like 40hrs
of wandering around gameplay), they had this exact system of
sector/chunk
world positions and to calculate the distance between
objects, they had to
do a kind of route find from source chunk to target chunk and
accumulation
of distances instead of a straight geometric distance since
there was no
world space, really.
He noted plenty of other non-obvious implications too, as you
say - for
example if all the game objects won't fit in memory at once,
deciding which
to keep cached and which to throw out, and all the horrible
implications
this has for game logic.
Al
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_ida88
Conor Stokes
2003-10-11 01:56:01 UTC
Permalink
Post by Tom Forsyth
I don't want to be dismissive, but what exactly _are_ the advantages?
The major one I can see is that if designers A, B and C are editing
sections that are linked in that order, designer B can shorten or
lengthen their bit arbitrarily, and you don't have to fiddle the
coordinate systems of the other two while they do it. But that seems a
bit of a small advantage - it's not exactly rocket-science to add an
offset to all the coordinates in a "chunk" when you burn it to CD.
Doesn't one of the main advantages come back to the topic of precision for
really large worlds?

Conor
Tom Forsyth
2003-10-11 02:20:01 UTC
Permalink
Not really. In both cases you have to wrap your position stuff up in a
fairly opaque class. Even using a vec3 of full-monty 202-bit integers seems
to be less hassle and quicker than the GPG solution, if that's all you're
trying to solve.

Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 11 October 2003 09:55
Subject: Re: [Algorithms] World size vs. floats
Post by Tom Forsyth
I don't want to be dismissive, but what exactly _are_ the
advantages?
Post by Tom Forsyth
The major one I can see is that if designers A, B and C are editing
sections that are linked in that order, designer B can shorten or
lengthen their bit arbitrarily, and you don't have to fiddle the
coordinate systems of the other two while they do it. But
that seems a
Post by Tom Forsyth
bit of a small advantage - it's not exactly rocket-science to add an
offset to all the coordinates in a "chunk" when you burn it to CD.
Doesn't one of the main advantages come back to the topic of
precision for
really large worlds?
Conor
Mark Wayland
2003-10-12 17:37:12 UTC
Permalink
I think I remember reading somewhere that a major disadvantage was something to do with problems with the pathfinding from one section of the world to another that the player wasn't near. Can anyone verify my ramblings?

Mark
Post by Gribb, Gil
-----Original Message-----
Sent: Saturday, 11 October 2003 8:17 AM
Subject: RE: [Algorithms] World size vs. floats
I saw the GDC talk - I think I remember chatting to you there. It's
really cool tech, but I just wonder if it's cool tech for cool tech's
sake.
The benefits of a non-euclidian space seemed to be fairly
minor (and in
fact quite irritating in places) compared to the problems you had.
There's nothing to stop people having multiple segments of the world
that co-exist even with a single world coordinate space - you
just have
to make sure your long-range stuff is all done through
portal/links, and
that nobody tries to ask questions like "I am here, so which
sector am I
in?" because it doesn't have a single answer. But that's
pretty easy to
do when you have the class that holds the answer or the question
(SiegePos/WorldPos/whatever) tightly controlled - just don't implement
those functions. But it sure makes shorter-range stuff like shooting
arrows over gorges, and creatures that fly, and long-range sniper
scopes, a fair bit easier.
I don't want to be dismissive, but what exactly _are_ the advantages?
The major one I can see is that if designers A, B and C are editing
sections that are linked in that order, designer B can shorten or
lengthen their bit arbitrarily, and you don't have to fiddle the
coordinate systems of the other two while they do it. But that seems a
bit of a small advantage - it's not exactly rocket-science to add an
offset to all the coordinates in a "chunk" when you burn it to CD.
TomF.
Post by Gribb, Gil
-----Original Message-----
Behalf Of Mike Biddlecombe
Sent: 10 October 2003 22:02
Subject: RE: [Algorithms] World size vs. floats
Maintaining a Frame of Reference (FoR) identifier, along with
an offset
vector from the origin of that frame, was the key to the 'node space
position' that was used in Dungeon Siege.
The vector <X,Y,Z> becomes the 'SiegePos' <X,Y,Z,N>, where
'N' is some value
used to identify the FoR you are in. In GPG-speak, the FoR
is a 'Siege
Post by Gribb, Gil
Node'.
Initially, the terrain system was designed (over-designed?)
to eliminate the
precision problem in a continuous world. All of the other
goodies were a
benefit of the time and effort we put into making it work and
maintaining
it. As Scott mentions in his paper, there were wins with this
system that
only came about once we starte to exploit the that fact that
objects are
anchored only to their FoR.
The mantra of "there is no world space" was crucial in allowing
self-intersecting worlds. In our system, there's no reason
why a series of
linked nodes can't wrap back upon itself, so that the
'distance' between
distinct positions <X0,Y0,Z0,N0> and <X1,Y1,Z1,N1> appears to
be zero. This
opened up a ton of options for the level designers.
I know I don't have the math background to do a deep analysis
(so I won't
try) but it seems to me that it doesn't matter how many bits
you use for
your offset vector, you need some extra info if you want to
allow your space
to be twisted around this way. Non-manifold? Non-Euclidean?
Escherian? ...if
you know the proper name to call it, help me out here!
This brings me to the Achilles heel of the system. How do you
explain it?
How can you convince people that its worth the hassle,
especially when there
are much simpler ways to solve the precision problem?
I wish I'd done better job with my hand waving when I
described the system
to the other programmers, most of whom just wanted a good old
unified world
space where A-B=B-A and |A-B| == d (with d constant if A & B
are constant!).
It can be confusing to grasp, especially if all it seems to
do is make your
life even more complicated. My experience is that people
really don't
Post by Gribb, Gil
appreciate hearing comments like "You need to call it Node
Space and not
World Space..." for four years.
Having said that, if I was to do it over again I'd keep it
all. In fact I'd
ditch vec3s altogether.
IMO, having the legacy vec3 around, and not implementing a
really clear and
easy to use 'space' class, held us back and added extra cost
to the project.
People kept converting to and from a SiegePos and 'camera
relative' vec3 to
get their math done. This was a potentially expensive
operation, so they'd
maintain a copy of this vector and then everything would
break when the
camera moved. A general purpose system that instantiated a
temporary FoR (to
track something like the flight of an arrow across multiple
nodes) would
have gone a long way towards eliminating wasted/duplicated effort.
I'd also seriously consider using fixed point for the vector
offsets. This
is something that we debated for a little while, but at the
time it was
easier to augment our vec3 math code with a nodeid longword.
I suppose it's
analogous to determining the best representation for a
quaternion; once
you've decided that quats are a good thing. Essentially, if you can
determine the 'difference' between <0,0,0,N0> and <0,0,0,N1>
to high enough
precision on the fly, you can limit the values in the vector
offsets to as
few bits as possible by restricting the size of the space
referenced by a
particular FoR.
If you are interested in more info, check out the GDC paper.
Scott has it at
http://www.drizzle.com/~scottb/gdc/continuous-world.htm
Mike Biddlecombe
Gas Powered Games
-----Original Message-----
Behalf Of Allan
Murphy
Sent: Thursday, October 09, 2003 2:01 AM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Jon Watte
Another problem with this representation is that
calculating distance
Post by Jon Watte
to other objects becomes harder; at a minimum, you have to
look up a
Post by Jon Watte
"global center"...
Scott Bilas' excellent GDC talk about the continuous
streaming world in
Dungeon Siege actually touched on a couple of the issues
coming up here. He
noted that because float wasn't anywhere near accurate enough
for the size
of their world (since it is one continuous world across
something like 40hrs
of wandering around gameplay), they had this exact system of
sector/chunk
world positions and to calculate the distance between
objects, they had to
do a kind of route find from source chunk to target chunk and
accumulation
of distances instead of a straight geometric distance since
there was no
world space, really.
He noted plenty of other non-obvious implications too, as you
say - for
example if all the game objects won't fit in memory at once,
deciding which
to keep cached and which to throw out, and all the horrible
implications
this has for game logic.
Al
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_ida88
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Tom Forsyth
2003-10-12 20:05:05 UTC
Permalink
The world was only loaded off disk in bubbles around the characters. So
if two characters were far enough apart that their bubbles didn't
overlap, the nav couldn't see how to go between them. And with no
concept of "world space" it didn't even know which direction to start
looking. Scary.

TomF.
Post by Gribb, Gil
-----Original Message-----
Behalf Of Mark Wayland
Sent: 13 October 2003 01:37
Subject: RE: [Algorithms] World size vs. floats
I think I remember reading somewhere that a major
disadvantage was something to do with problems with the
pathfinding from one section of the world to another that the
player wasn't near. Can anyone verify my ramblings?
Mark
Post by Gribb, Gil
-----Original Message-----
Sent: Saturday, 11 October 2003 8:17 AM
Subject: RE: [Algorithms] World size vs. floats
I saw the GDC talk - I think I remember chatting to you there. It's
really cool tech, but I just wonder if it's cool tech for
cool tech's
Post by Gribb, Gil
sake.
The benefits of a non-euclidian space seemed to be fairly
minor (and in
fact quite irritating in places) compared to the problems you had.
There's nothing to stop people having multiple segments of the world
that co-exist even with a single world coordinate space - you
just have
to make sure your long-range stuff is all done through
portal/links, and
that nobody tries to ask questions like "I am here, so which
sector am I
in?" because it doesn't have a single answer. But that's
pretty easy to
do when you have the class that holds the answer or the question
(SiegePos/WorldPos/whatever) tightly controlled - just
don't implement
Post by Gribb, Gil
those functions. But it sure makes shorter-range stuff like shooting
arrows over gorges, and creatures that fly, and long-range sniper
scopes, a fair bit easier.
I don't want to be dismissive, but what exactly _are_ the
advantages?
Post by Gribb, Gil
The major one I can see is that if designers A, B and C are editing
sections that are linked in that order, designer B can shorten or
lengthen their bit arbitrarily, and you don't have to fiddle the
coordinate systems of the other two while they do it. But
that seems a
Post by Gribb, Gil
bit of a small advantage - it's not exactly rocket-science to add an
offset to all the coordinates in a "chunk" when you burn it to CD.
TomF.
Post by Gribb, Gil
-----Original Message-----
Behalf Of Mike Biddlecombe
Sent: 10 October 2003 22:02
Subject: RE: [Algorithms] World size vs. floats
Maintaining a Frame of Reference (FoR) identifier, along with
an offset
vector from the origin of that frame, was the key to the
'node space
Post by Gribb, Gil
Post by Gribb, Gil
position' that was used in Dungeon Siege.
The vector <X,Y,Z> becomes the 'SiegePos' <X,Y,Z,N>, where
'N' is some value
used to identify the FoR you are in. In GPG-speak, the FoR
is a 'Siege
Post by Gribb, Gil
Node'.
Initially, the terrain system was designed (over-designed?)
to eliminate the
precision problem in a continuous world. All of the other
goodies were a
benefit of the time and effort we put into making it work and
maintaining
it. As Scott mentions in his paper, there were wins with this
system that
only came about once we starte to exploit the that fact that
objects are
anchored only to their FoR.
The mantra of "there is no world space" was crucial in allowing
self-intersecting worlds. In our system, there's no reason
why a series of
linked nodes can't wrap back upon itself, so that the
'distance' between
distinct positions <X0,Y0,Z0,N0> and <X1,Y1,Z1,N1> appears to
be zero. This
opened up a ton of options for the level designers.
I know I don't have the math background to do a deep analysis
(so I won't
try) but it seems to me that it doesn't matter how many bits
you use for
your offset vector, you need some extra info if you want to
allow your space
to be twisted around this way. Non-manifold? Non-Euclidean?
Escherian? ...if
you know the proper name to call it, help me out here!
This brings me to the Achilles heel of the system. How do you
explain it?
How can you convince people that its worth the hassle,
especially when there
are much simpler ways to solve the precision problem?
I wish I'd done better job with my hand waving when I
described the system
to the other programmers, most of whom just wanted a good old
unified world
space where A-B=B-A and |A-B| == d (with d constant if A & B
are constant!).
It can be confusing to grasp, especially if all it seems to
do is make your
life even more complicated. My experience is that people
really don't
Post by Gribb, Gil
appreciate hearing comments like "You need to call it Node
Space and not
World Space..." for four years.
Having said that, if I was to do it over again I'd keep it
all. In fact I'd
ditch vec3s altogether.
IMO, having the legacy vec3 around, and not implementing a
really clear and
easy to use 'space' class, held us back and added extra cost
to the project.
People kept converting to and from a SiegePos and 'camera
relative' vec3 to
get their math done. This was a potentially expensive
operation, so they'd
maintain a copy of this vector and then everything would
break when the
camera moved. A general purpose system that instantiated a
temporary FoR (to
track something like the flight of an arrow across multiple
nodes) would
have gone a long way towards eliminating
wasted/duplicated effort.
Post by Gribb, Gil
Post by Gribb, Gil
I'd also seriously consider using fixed point for the vector
offsets. This
is something that we debated for a little while, but at the
time it was
easier to augment our vec3 math code with a nodeid longword.
I suppose it's
analogous to determining the best representation for a
quaternion; once
you've decided that quats are a good thing. Essentially,
if you can
Post by Gribb, Gil
Post by Gribb, Gil
determine the 'difference' between <0,0,0,N0> and <0,0,0,N1>
to high enough
precision on the fly, you can limit the values in the vector
offsets to as
few bits as possible by restricting the size of the space
referenced by a
particular FoR.
If you are interested in more info, check out the GDC paper.
Scott has it at
http://www.drizzle.com/~scottb/gdc/continuous-world.htm
Mike Biddlecombe
Gas Powered Games
-----Original Message-----
Behalf Of Allan
Murphy
Sent: Thursday, October 09, 2003 2:01 AM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Jon Watte
Another problem with this representation is that
calculating distance
Post by Jon Watte
to other objects becomes harder; at a minimum, you have to
look up a
Post by Jon Watte
"global center"...
Scott Bilas' excellent GDC talk about the continuous
streaming world in
Dungeon Siege actually touched on a couple of the issues
coming up here. He
noted that because float wasn't anywhere near accurate enough
for the size
of their world (since it is one continuous world across
something like 40hrs
of wandering around gameplay), they had this exact system of
sector/chunk
world positions and to calculate the distance between
objects, they had to
do a kind of route find from source chunk to target chunk and
accumulation
of distances instead of a straight geometric distance since
there was no
world space, really.
He noted plenty of other non-obvious implications too, as you
say - for
example if all the game objects won't fit in memory at once,
deciding which
to keep cached and which to throw out, and all the horrible
implications
this has for game logic.
Al
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_ida88
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_ida88
Jon Watte
2003-10-13 09:18:03 UTC
Permalink
Post by Tom Forsyth
The world was only loaded off disk in bubbles around the characters. So
if two characters were far enough apart that their bubbles didn't
overlap, the nav couldn't see how to go between them. And with no
concept of "world space" it didn't even know which direction to start
looking. Scary.
I suppose you could build a global connectivity map, where each of the
zone neighbors is expressed in the coordinates of the zone itself. That
should scale by just a hundred bytes or so per zone, so until you get
into thousands of zones, it's doable even on small hardware. This would
let pathfinding give itself an idea of where to go, and it would also
allow for querying for rough distance (assuming center-to-center
travel).

It seems that if you do a super-sector system like this, you would have
to do something like that.

Speaking of which: Marathon, on the Mac, in 1995, did the same thing, as
its internal data was basically "floor polygons" with specific ceiling
and floor heights, and everything was expressed in the connectivity
between them. Anyone remember the map "5D" ? :-)

Cheers,

/ h+
Bryan Wagstaff
2003-10-13 10:52:08 UTC
Permalink
Post by Jon Watte
I suppose you could build a global connectivity map, where each of the
zone neighbors is expressed in the coordinates of the zone itself. That
should scale by just a hundred bytes or so per zone, so until you get
into thousands of zones, it's doable even on small hardware. This would
let pathfinding give itself an idea of where to go, and it would also
allow for querying for rough distance (assuming center-to-center
travel).
That sounds like it could balloon to much more than a small constant per zone --
especially in a maze-type level where the best/only route in a zone to zone [that
is, map segment to map segment] connectivity map could easily enter and exit a
particular zone many times.

I'm assuming that the world size means you can't have some sort of unified
connectivity tree in which all map segments are combined. Even in the best cases,
the (imagined) complexity in that connection graph is much bigger than what I've
historically seen. In addition to the normal mapping from points to connected
areas {rooms, halls, etc}, you would need to have cross-segment connections that
could describe large cross-zone connected areas [you would want to have at least a
few rooms split between boundaries or your world would have obvious map-segment
boundaries], which could (in my imagined, bad-case maze example) double the work
needed for beliveable pathfinding: You must now manage two connectivity graphs
rather than one. Granted, I don't usually do path finding, but from what I know
about it and have had to do, it seems like it COULD add much more work.

In a very large real-world example you would normally have the equivalent of
highways and major roads that can be used for large segments of the path. In a
maze world at this scale, even the major roads could be intracate enough to add a
signficant overhead.

It could just be my paranoia kicking in from not comfortable with pathfinding, but
I'm skeptical of adding complexity to something that can already be a very nasty
problem, especially in the bad case of mazes.

bryanw.
Chris Butcher (BUNGIE)
2003-10-13 10:02:09 UTC
Permalink
Post by Gribb, Gil
-----Original Message-----
[mailto:gdalgorithms-
Post by Gribb, Gil
Sent: Monday, October 13, 2003 09:16
Subject: RE: [Algorithms] World size vs. floats
Speaking of which: Marathon, on the Mac, in 1995, did the same thing,
as
Post by Gribb, Gil
its internal data was basically "floor polygons" with specific ceiling
and floor heights, and everything was expressed in the connectivity
between them. Anyone remember the map "5D" ? :-)
5D Space was cool, but what was even more cool was the fact that there
were still some calculations that took place in world coordinates. It
was possible to get hit by a missile travelling in an overlapped
parallel dimension - not all of the time (that would have been easy to
catch) but only in certain edge cases. Ah, simpler times.

I definitely think that the GPG approach of having fully local
coordinate systems has merit, but I haven't seen the biggest benefit
cited on this thread so far - being able to move pieces of your world
relative to one another. IMHO, this is one of the largest remaining
limitations of current 3D engine architecture. If only the Prey engine
was still around. (Obviously the Unreal engine has a number of ways of
faking it which work for most of the typical FPS cliche cases - train,
spaceship, etc.)

--
Chris Butcher
Networking & Simulation Lead
Halo 2 | Bungie Studios
***@bungie.com
Jon Watte
2003-10-13 11:47:03 UTC
Permalink
Post by Bryan Wagstaff
Post by Jon Watte
I suppose you could build a global connectivity map, where each of the
zone neighbors is expressed in the coordinates of the zone itself. That
should scale by just a hundred bytes or so per zone, so until you get
into thousands of zones, it's doable even on small hardware. This would
let pathfinding give itself an idea of where to go, and it would also
allow for querying for rough distance (assuming center-to-center
travel).
That sounds like it could balloon to much more than a small
constant per zone --
especially in a maze-type level where the best/only route in a
zone to zone [that
is, map segment to map segment] connectivity map could easily
enter and exit a
particular zone many times.
So don't build such zones if you want to use global pathfinding in a
system with localized zone coordinate systems. Saying that zones have
to have connectivity between all the exits seems like a reasonable
restriction to put upon such a system.
Post by Bryan Wagstaff
historically seen. In addition to the normal mapping from points
to connected
areas {rooms, halls, etc}, you would need to have cross-segment
connections that
could describe large cross-zone connected areas [you would want
I'm assuming that most large-scale path-finding set-ups already have
this, as you don't want to path-find on your smallest-movable cell
size when planning how to get from here to Kuala Lumpur.

Thus, pathfinding would first run a query to figure out which zones
to travel through, and then it would run queries to figure out how to
get through each zone when it got to that point. Thus, the upper-level
zone connectivity graph would work a little bit like planning your
route around highways and airports.

If you feature destroyable infrastructure (taking out bridges, tunnels
etc) then you have to put a zone boundary at each such connecting
point, and remember to change the global connectivity map when these
connections change state.

Cheers,

/ h+
Mike Biddlecombe
2003-10-13 12:05:17 UTC
Permalink
Keep in mind that the real headaches we encountered, the ones that kept us
up late at night, were in the logistics of actually streaming content and
not in the representation of the 'space' that the content was loaded into.
In the end our problem wasn't that we had precision issues, but rather that
our design spec allowed you to leave party members wandering around behind
as you as you walked from one end of the world to the other and then collect
them back up again on your return trip to the starting point; all the time
ensuring that the player was able to flip the view back and forth between
any separated party members on the fly.

During regular play, if it is possible that no path from P to Q exists,
because the A* search is exhausted, because the space around P is not
connected to Q, because your P and Q characters have moved so far apart that
you were forced to unload the nodes that might contain a path between them,
you have some decisions to make.

I see this as a game play issue: What does P need a long range path to Q
for?

If you and I are adventuring through a forest and we get so separated that I
can no longer see you, should I always be able to click on your icon and be
provided with a path I can walk along that returns me to you? Should the
system put a marker on screen that tells me that you are 'north' of me so
that I can walk in your direction? What if we are in a maze and I actually
need to head south locally in order to meet up with you to the north of me?
Should that marker point south? Should there be two markers, one pointing
north while the other points south? What happens when there are 8 characters
in your party? When do all these helper arrows become confusing clutter?

DS didn't provide these helpers and we didn't write the code required to
build those long range paths. If we did want to add them, we might have
tackled it by maintaining a dynamic 'bridge' connection that linked the two
'bubbles'. As soon as you detect that two frustums (Frustum: GPG-speak for
'bubble around a character') are going to separate, you a calculate a bridge
that keeps them linked by finding the difference between their origins
(while you still can). The accuracy of this bridge isn't super, but it
doesn't have to be as you're only building a long range
'walk-in-the-general-direction' path. If you follow it you'll link the
frustums up again when the 'bubbles' overlap. Happily, the relative
precision will continue improve as you close on the destination. If you move
so far apart that you invalidate the bridge you built (and thus separate the
frustums again) you just update the bridge's offsets with the revised
origins and continue on.

Dynamically attaching objects and nodes to the world 'on the fly' using this
kind of temporary FoR solves assorted arrows over gorges, flying, and long
range sniping problems. It also enables you to move the relative positions
of the nodes around dynamically, creating elevators (and other irritating
places)

We took the initial design requirement for "an enormous world with no
loading screens that you can walk back and forth across and never see a
hitch" and added to it the wrinkle that we would not require any artificial
choke points to break the terrain into manageable pieces. No 90 degree turns
in a long thin corridor would be required to partition the world up. Those
requirements led us to establish our variation on world space. It may not
qualify as rocket science, but it definitely involved a lot of housekeeping.


Of course, once we had our trusty Siege Engine in hand, we were able to
empirically establish that choke points in a continuous experience are
actually kinda useful ...from a story telling perspective.

Is it all just cool tech for cool tech's sake?

Perhaps.

All I can do in defense is toss back the usual Frost 101:

"I took the one less travelled by, And that has made all the difference"

.mb

-----Original Message-----
From: gdalgorithms-list-***@lists.sourceforge.net
[mailto:gdalgorithms-list-***@lists.sourceforge.net] On Behalf Of Tom
Forsyth
Sent: Sunday, October 12, 2003 8:05 PM
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats


The world was only loaded off disk in bubbles around the characters. So if
two characters were far enough apart that their bubbles didn't overlap, the
nav couldn't see how to go between them. And with no concept of "world
space" it didn't even know which direction to start looking. Scary.

TomF.
Post by Gribb, Gil
-----Original Message-----
Behalf Of Mark Wayland
Sent: 13 October 2003 01:37
Subject: RE: [Algorithms] World size vs. floats
I think I remember reading somewhere that a major disadvantage was
something to do with problems with the pathfinding from one section of
the world to another that the player wasn't near. Can anyone verify my
ramblings?
Mark
Post by Gribb, Gil
-----Original Message-----
Sent: Saturday, 11 October 2003 8:17 AM
Subject: RE: [Algorithms] World size vs. floats
I saw the GDC talk - I think I remember chatting to you there. It's
really cool tech, but I just wonder if it's cool tech for
cool tech's
Post by Gribb, Gil
sake.
The benefits of a non-euclidian space seemed to be fairly minor (and
in fact quite irritating in places) compared to the problems you
had. There's nothing to stop people having multiple segments of the
world that co-exist even with a single world coordinate space - you
just have
to make sure your long-range stuff is all done through
portal/links, and
that nobody tries to ask questions like "I am here, so which
sector am I
in?" because it doesn't have a single answer. But that's
pretty easy to
do when you have the class that holds the answer or the question
(SiegePos/WorldPos/whatever) tightly controlled - just
don't implement
Post by Gribb, Gil
those functions. But it sure makes shorter-range stuff like shooting
arrows over gorges, and creatures that fly, and long-range sniper
scopes, a fair bit easier.
I don't want to be dismissive, but what exactly _are_ the
advantages?
Post by Gribb, Gil
The major one I can see is that if designers A, B and C are editing
sections that are linked in that order, designer B can shorten or
lengthen their bit arbitrarily, and you don't have to fiddle the
coordinate systems of the other two while they do it. But
that seems a
Post by Gribb, Gil
bit of a small advantage - it's not exactly rocket-science to add an
offset to all the coordinates in a "chunk" when you burn it to CD.
TomF.
Post by Gribb, Gil
-----Original Message-----
Behalf Of Mike Biddlecombe
Sent: 10 October 2003 22:02
Subject: RE: [Algorithms] World size vs. floats
Maintaining a Frame of Reference (FoR) identifier, along with an
offset vector from the origin of that frame, was the key to the
'node space
Post by Gribb, Gil
Post by Gribb, Gil
position' that was used in Dungeon Siege.
The vector <X,Y,Z> becomes the 'SiegePos' <X,Y,Z,N>, where 'N' is
some value used to identify the FoR you are in. In GPG-speak, the
FoR
is a 'Siege
Post by Gribb, Gil
Node'.
Initially, the terrain system was designed (over-designed?) to
eliminate the precision problem in a continuous world. All of the
other goodies were a
benefit of the time and effort we put into making it work and
maintaining
it. As Scott mentions in his paper, there were wins with this
system that
only came about once we starte to exploit the that fact that
objects are
anchored only to their FoR.
The mantra of "there is no world space" was crucial in allowing
self-intersecting worlds. In our system, there's no reason why a
series of linked nodes can't wrap back upon itself, so that the
'distance' between
distinct positions <X0,Y0,Z0,N0> and <X1,Y1,Z1,N1> appears to
be zero. This
opened up a ton of options for the level designers.
I know I don't have the math background to do a deep analysis (so
I won't
try) but it seems to me that it doesn't matter how many bits
you use for
your offset vector, you need some extra info if you want to
allow your space
to be twisted around this way. Non-manifold? Non-Euclidean?
Escherian? ...if
you know the proper name to call it, help me out here!
This brings me to the Achilles heel of the system. How do you
explain it? How can you convince people that its worth the hassle,
especially when there
are much simpler ways to solve the precision problem?
I wish I'd done better job with my hand waving when I described
the system to the other programmers, most of whom just wanted a
good old unified world
space where A-B=B-A and |A-B| == d (with d constant if A & B
are constant!).
It can be confusing to grasp, especially if all it seems to
do is make your
life even more complicated. My experience is that people
really don't
Post by Gribb, Gil
appreciate hearing comments like "You need to call it Node Space
and not World Space..." for four years.
Having said that, if I was to do it over again I'd keep it all. In
fact I'd ditch vec3s altogether.
IMO, having the legacy vec3 around, and not implementing a really
clear and easy to use 'space' class, held us back and added extra
cost to the project.
People kept converting to and from a SiegePos and 'camera
relative' vec3 to
get their math done. This was a potentially expensive
operation, so they'd
maintain a copy of this vector and then everything would
break when the
camera moved. A general purpose system that instantiated a
temporary FoR (to
track something like the flight of an arrow across multiple
nodes) would
have gone a long way towards eliminating
wasted/duplicated effort.
Post by Gribb, Gil
Post by Gribb, Gil
I'd also seriously consider using fixed point for the vector
offsets. This is something that we debated for a little while, but
at the time it was
easier to augment our vec3 math code with a nodeid longword.
I suppose it's
analogous to determining the best representation for a
quaternion; once
you've decided that quats are a good thing. Essentially,
if you can
Post by Gribb, Gil
Post by Gribb, Gil
determine the 'difference' between <0,0,0,N0> and <0,0,0,N1> to
high enough precision on the fly, you can limit the values in the
vector offsets to as
few bits as possible by restricting the size of the space
referenced by a
particular FoR.
If you are interested in more info, check out the GDC paper. Scott
has it at http://www.drizzle.com/~scottb/gdc/continuous-world.htm
Mike Biddlecombe
Gas Powered Games
-----Original Message-----
Of Allan Murphy
Sent: Thursday, October 09, 2003 2:01 AM
Subject: RE: [Algorithms] World size vs. floats [bcc][fake adr]
Post by Jon Watte
Another problem with this representation is that
calculating distance
Post by Jon Watte
to other objects becomes harder; at a minimum, you have to
look up a
Post by Jon Watte
"global center"...
Scott Bilas' excellent GDC talk about the continuous streaming
world in Dungeon Siege actually touched on a couple of the issues
coming up here. He
noted that because float wasn't anywhere near accurate enough
for the size
of their world (since it is one continuous world across
something like 40hrs
of wandering around gameplay), they had this exact system of
sector/chunk
world positions and to calculate the distance between
objects, they had to
do a kind of route find from source chunk to target chunk and
accumulation
of distances instead of a straight geometric distance since
there was no
world space, really.
He noted plenty of other non-obvious implications too, as you say
- for example if all the game objects won't fit in memory at once,
deciding which
to keep cached and which to throw out, and all the horrible
implications
this has for game logic.
Al
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects. See the
http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects. See the
http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects. See the people
http://sourceforge.net/supporters.php
_______________________________________________
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_ida88
De Boer
2003-10-14 01:26:08 UTC
Permalink
(covering what I think advantages of algorithms like dungeon seige)

Lets assume you wanted an engine that had potentially infinite world space
and that you could keep designing pieces of it and adding it to the world.
And say you wanted no loading screens (apart from at the beginning).

Precision will be an issue, and multiple coordinate systems using algorithms
like dungeon seige do seem a good solution. You don't have to make it as
small scale as dungeon seige, where a node is very small. But the smaller
your nodes the easier it is probably easier to stream. My nodes are
reasonably large, but even so if you went up to a boundary and shot an arrow
you still need to switch between coordinate systems like dungeon siege. You
could make each node so large that they make ample use of the precision of
whatever unit of measurement you use. Then if you wanted streaming you could
stream "sub chunks" of the node or something.

But no matter what I don't see how you can have a extremely large world
space without having multiple coordinate systems and switching between them.
Unless you have loading screens and each "level" you do not need to shoot an
arrow back to the previous level (and you reuse the same coordinate system).
For example just about every FPS. HL1 tried to have very small loading times
between sections and it felt a bit more continuous. It will be interesting
to see if any FPS improves on this. GTA3 may have had a separate coordinate
system for each island (correct me if I'm wrong), and short loading screens
between them. There is nothing wrong with loading screens, but sometimes you
don't want to convert everyting into separate levels, and you want to walk
between areas almost transparently.

-Ryan De Boer
Tom Forsyth
2003-10-14 09:59:11 UTC
Permalink
I think there's two separate things here. First is - what co-ordinate system
do you use - local-with-connections, or a global one? Second is - how do you
section your world so you can do everything with dynamic loading? I think
these two questions are othogonal.

Most of what the DS tech did was to solve the second problem, and it's
certainly a difficult problem, and they did solve it in a cool way. But it
doesn't require any particular decision on the first question. There have
been a fair number of large streamed worlds that did use a single
world-space (anyone know what coordinate system Jak and Daxter used for
example?).

Dungeon Siege's nodes could get really big apparently - I think Scott
mentioned in his talk that one of the castles in the game was a single huge
node (?)


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 14 October 2003 09:26
Subject: RE: [Algorithms] World size vs. floats
(covering what I think advantages of algorithms like dungeon seige)
Lets assume you wanted an engine that had potentially
infinite world space
and that you could keep designing pieces of it and adding it
to the world.
And say you wanted no loading screens (apart from at the beginning).
Precision will be an issue, and multiple coordinate systems
using algorithms
like dungeon seige do seem a good solution. You don't have to
make it as
small scale as dungeon seige, where a node is very small. But
the smaller
your nodes the easier it is probably easier to stream. My nodes are
reasonably large, but even so if you went up to a boundary
and shot an arrow
you still need to switch between coordinate systems like
dungeon siege. You
could make each node so large that they make ample use of the
precision of
whatever unit of measurement you use. Then if you wanted
streaming you could
stream "sub chunks" of the node or something.
But no matter what I don't see how you can have a extremely
large world
space without having multiple coordinate systems and
switching between them.
Unless you have loading screens and each "level" you do not
need to shoot an
arrow back to the previous level (and you reuse the same
coordinate system).
For example just about every FPS. HL1 tried to have very
small loading times
between sections and it felt a bit more continuous. It will
be interesting
to see if any FPS improves on this. GTA3 may have had a
separate coordinate
system for each island (correct me if I'm wrong), and short
loading screens
between them. There is nothing wrong with loading screens,
but sometimes you
don't want to convert everyting into separate levels, and you
want to walk
between areas almost transparently.
-Ryan De Boer
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Mark Wayland
2003-10-14 17:35:08 UTC
Permalink
I think Stephen White mentioned at the GDC that they did run into precision problems
at the outer chunks of the game world because of a global coordinate system, but I
could be wrong...

Mark
Post by Gribb, Gil
-----Original Message-----
Sent: Wednesday, 15 October 2003 2:55 AM
Subject: RE: [Algorithms] World size vs. floats
I think there's two separate things here. First is - what
co-ordinate system
do you use - local-with-connections, or a global one? Second
is - how do you
section your world so you can do everything with dynamic
loading? I think
these two questions are othogonal.
Most of what the DS tech did was to solve the second problem, and it's
certainly a difficult problem, and they did solve it in a
cool way. But it
doesn't require any particular decision on the first
question. There have
been a fair number of large streamed worlds that did use a single
world-space (anyone know what coordinate system Jak and
Daxter used for
example?).
Dungeon Siege's nodes could get really big apparently - I think Scott
mentioned in his talk that one of the castles in the game was
a single huge
node (?)
Tom Forsyth - Muckyfoot bloke and Microsoft MVP.
This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 14 October 2003 09:26
Subject: RE: [Algorithms] World size vs. floats
(covering what I think advantages of algorithms like dungeon seige)
Lets assume you wanted an engine that had potentially
infinite world space
and that you could keep designing pieces of it and adding it
to the world.
And say you wanted no loading screens (apart from at the beginning).
Precision will be an issue, and multiple coordinate systems
using algorithms
like dungeon seige do seem a good solution. You don't have to
make it as
small scale as dungeon seige, where a node is very small. But
the smaller
your nodes the easier it is probably easier to stream. My nodes are
reasonably large, but even so if you went up to a boundary
and shot an arrow
you still need to switch between coordinate systems like
dungeon siege. You
could make each node so large that they make ample use of the
precision of
whatever unit of measurement you use. Then if you wanted
streaming you could
stream "sub chunks" of the node or something.
But no matter what I don't see how you can have a extremely
large world
space without having multiple coordinate systems and
switching between them.
Unless you have loading screens and each "level" you do not
need to shoot an
arrow back to the previous level (and you reuse the same
coordinate system).
For example just about every FPS. HL1 tried to have very
small loading times
between sections and it felt a bit more continuous. It will
be interesting
to see if any FPS improves on this. GTA3 may have had a
separate coordinate
system for each island (correct me if I'm wrong), and short
loading screens
between them. There is nothing wrong with loading screens,
but sometimes you
don't want to convert everyting into separate levels, and you
want to walk
between areas almost transparently.
-Ryan De Boer
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
Jeremiah Zanin
2003-10-15 07:23:00 UTC
Permalink
I remember him saying that also about the mountain level.

-----Original Message-----
From: Mark Wayland [mailto:***@torus.com.au]
Sent: Tuesday, October 14, 2003 7:34 PM
To: gdalgorithms-***@lists.sourceforge.net
Subject: RE: [Algorithms] World size vs. floats


I think Stephen White mentioned at the GDC that they did run into precision
problems
at the outer chunks of the game world because of a global coordinate system,
but I
could be wrong...

Mark
Post by Gribb, Gil
-----Original Message-----
Sent: Wednesday, 15 October 2003 2:55 AM
Subject: RE: [Algorithms] World size vs. floats
I think there's two separate things here. First is - what
co-ordinate system
do you use - local-with-connections, or a global one? Second
is - how do you
section your world so you can do everything with dynamic
loading? I think
these two questions are othogonal.
Most of what the DS tech did was to solve the second problem, and it's
certainly a difficult problem, and they did solve it in a
cool way. But it
doesn't require any particular decision on the first
question. There have
been a fair number of large streamed worlds that did use a single
world-space (anyone know what coordinate system Jak and
Daxter used for
example?).
Dungeon Siege's nodes could get really big apparently - I think Scott
mentioned in his talk that one of the castles in the game was
a single huge
node (?)
Tom Forsyth - Muckyfoot bloke and Microsoft MVP.
This email is the product of your deranged imagination,
and does not in any way imply existence of the author.
Post by Gribb, Gil
-----Original Message-----
Sent: 14 October 2003 09:26
Subject: RE: [Algorithms] World size vs. floats
(covering what I think advantages of algorithms like dungeon seige)
Lets assume you wanted an engine that had potentially
infinite world space
and that you could keep designing pieces of it and adding it
to the world.
And say you wanted no loading screens (apart from at the beginning).
Precision will be an issue, and multiple coordinate systems
using algorithms
like dungeon seige do seem a good solution. You don't have to
make it as
small scale as dungeon seige, where a node is very small. But
the smaller
your nodes the easier it is probably easier to stream. My nodes are
reasonably large, but even so if you went up to a boundary
and shot an arrow
you still need to switch between coordinate systems like
dungeon siege. You
could make each node so large that they make ample use of the
precision of
whatever unit of measurement you use. Then if you wanted
streaming you could
stream "sub chunks" of the node or something.
But no matter what I don't see how you can have a extremely
large world
space without having multiple coordinate systems and
switching between them.
Unless you have loading screens and each "level" you do not
need to shoot an
arrow back to the previous level (and you reuse the same
coordinate system).
For example just about every FPS. HL1 tried to have very
small loading times
between sections and it felt a bit more continuous. It will
be interesting
to see if any FPS improves on this. GTA3 may have had a
separate coordinate
system for each island (correct me if I'm wrong), and short
loading screens
between them. There is nothing wrong with loading screens,
but sometimes you
don't want to convert everyting into separate levels, and you
want to walk
between areas almost transparently.
-Ryan De Boer
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
SourceForge.net hosts over 70,000 Open Source Projects.
See the people who have HELPED US provide better services:
Click here: http://sourceforge.net/supporters.php
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_ida88

Loading...