Hello GameDevs, Here's a question I and perhaps a few others as well am pondering at the moment. (I'm planning a simulation of a realistically sized 3D universe.) When making a 3D game engine, it is said that you can't make it contain any size world you want because the further away you get from the origin of your coordinate system, the bigger the floating point error gets. So big in fact, that with a standard float, you can more or less only create a 3D engine which manages a realistically sized "sanbox" the size of San Francisco. – If you make it bigger, you will run into severe problems of the floating point number resulting in popping and bouncing, etc. Moving on to a double (64 bits instead of 32) certainly makes the maximum size of the virtual world bigger, but does NOT solve the problem on a general level, making it go away entirely and making it possible to build a realistically sized or measured universe of *ANY* size. That's what I want to do: I want to solve this problem once and for good (if possible). It seems noteworthy to say, that apparently there is no software up until today which solves this problem (or is there?). While there are amazing projects, like Celestia and Infinity - The Quest for Earth, even these projects are limited in their space. Celestia is limited to about 100'000 stars and Infinity - The Quest for Earth is using doubles and I'm not sure how big the Infinity universe really is. Here's an existing GameDev thread on a similar topic: Planet rendering and floating point precision From what I've found out so far is that one (or the only?) solution is to hierarchically nest coordinate systems within each other. And that's exactly what this thread should be about and what I would like to learn more about. Here's an interesting link I'd like to share: www.spatial-effects.com Please share any resources or knowledge you might have on this particular topic. Books, tutorials, articles, etc? Here's one book I found which might deal with the subject: Multi-Hierarchical Representation of Large-Scale Space: Applications to Mobile Robots (Microprocessor-Based and Intelligent Systems Engineering) (Hardcover) by Juan A. Fernandez (Author), Javier Gonzalez, ISBN-10: 1402001053 Link to www.Amazon.com Any additional information and resources on this topic added here is greatly appreciated! Mark

You can always use sectors in your game.

You won't be loading all of the huge world anyway. You'd only want to load things that are close to the player (camera). And having something like sectors would actually make it easier on you to only load those near areas...

So, you can have float coordinates within the sector, and then have int sector coordinates within the world.

If necessary (if your world is really THAT big), you can go even further, and put those sectors in something bigger. So basically, you can have the world as big as you want without ever loosing precision.

Quote:Original post by Markie
Celestia is limited to about 100'000 stars and Infinity - The Quest for Earth is using doubles and I'm not sure how big the Infinity universe really is.

To be clear, it is using two coordinate systems:

- the galactic coordinates: one single 64-bits integer that represents packed XYZ coordinates of a solar system in the galaxy. Basically, the galaxy is a grid of cubes that are 1 LY.

- inside a solar system, coordinates are represented as 3x doubles, giving an accuracy of 1 millimeter at 100 AU.

That's not infinite precision, but that's "good enough" for our goals :)

Y.

Quote:Original post by Sc4Freak
TomF's blog

He's absolutely right, fixed point is a perfect solution to this kind of problem.

Thanks! I forgot to mention that resource!
Actually I read his comments just before I made this post. :-)
IMO fixed-point isn't the right solution either though.
After all, all that fixed point does is guarantee a certain mantissa, isn't it? That's a little like using doubles instead of floats. If your world will fit inside a fixed-point or double coordinate system, fine, if not, you still have this problem, no?

Quote:Original post by Paulius Maruska
You can always use sectors in your game.

You won't be loading all of the huge world anyway. You'd only want to load things that are close to the player (camera). And having something like sectors would actually make it easier on you to only load those near areas...

So, you can have float coordinates within the sector, and then have int sector coordinates within the world.

If necessary (if your world is really THAT big), you can go even further, and put those sectors in something bigger. So basically, you can have the world as big as you want without ever loosing precision.

Yes, I've thought about this a lot. Basically your idea is to box coordinate systems within each other hierarchically, which I suppose is the only way to go. But you're not right that everything outside a "sector" as you call it has no effect on what happens inside the sector. - If it were that easy, I would not be doing this research. - The thing is this: Once again, I don't know how Infinity handles this, perhaps Ysaneya does it more or less the way you describe (?), but I *know* that I want interaction between all kinds of nested world-coordinate systems.

For instance:
Imagine you're lying down in a filed of grass at night or you're transformed into an ant or a mouse and you're looking up at the night sky:
What you see is this:
1.) You'll see some grass leaves at the edge of the view, which will be in your current coordinate system.
2.) Then you might see a moon or another planet which will be in another, higher coordinate system.
3.) And finally, you'll see hundreds of stars which are light years away, which are in yet in another coordinate system.

Now, what happens when a *death-ray* or a spaceship / meteorite from outer space or one of those stars that is light years away is directed at earth?
I want to know where it hits! Does it hit me or does it miss me by inches / miles? Of course, I also want the moon and stars to be rendered correctly, depending on earth's position and its rotation. - Most (or all?) games don't render real night skies with stars, they just use some "painting" which they pull over the sky.
So you see, in the game (or simulation) I would like to make, I want to be able to have interaction between the different coordinate systems, just like it were in one!!
- And this is causing me some headaches because I can't find any information on how others might have done this before.

To calculate this interaction between a smaller and a larger coordinate system, are simple matrix transforms all that's needed?

Admittedly, with stationary objects it's not so difficult, because with them, you can just express any location as a tree of nested coordinate systems with whatever subdivision you like. But with moving objects it's probably much more complicated:
If you have a smaller and a larger coordinate system, both subdivided by an integer or a float, let's say the smaller one has a unit of 1mm and the larger one has a unit of 1'000 km, what happens when I fly my spaceship outside the smaller one? I'll probably have to connect an adjacent cube of space with the same coordinate system next to it like in a portal engine, thus moving one unit in the bigger system and setting my position in the next adjacent smaller system at the very boundary of the cube I just left.

But what happens when I try to land a spaceship on a planet who's exact location is described only in the larger coordinate system? If planets' location and movement is described only in the larger coordinate system they can only move 1'000 km as the minimal movement, right? So how would I break down that movement into smaller bits to land my spaceship on it?
Wouldn't this result in the same kind of precision loss and "jumping" objects like when using floats or doubles for the entire universe?

Quote:Original post by Ysaneya
To be clear, it is using two coordinate systems:

- the galactic coordinates: one single 64-bits integer that represents packed XYZ coordinates of a solar system in the galaxy. Basically, the galaxy is a grid of cubes that are 1 LY.

- inside a solar system, coordinates are represented as 3x doubles, giving an accuracy of 1 millimeter at 100 AU.

That's not infinite precision, but that's "good enough" for our goals :)

Thanks a lot for clearing that up!! :-)
Wow, direct information from the source is always the best!
:-)))

Am I assuming correctly then, that you have pretty much implemented your two different coordinate systems as Paulius Maruska suggested, meaning simply without considering anything happening outside of a 1 LY cube for movement, etc. within?

If not, I'd sure be interested how complicated it is to transgress the boundaries of different coordinate systems to calculate movement, angles, etc.


If it's very complicated to transgress and calculate movement and angles between different coordinate systems, it's probably best to use as few different coordinate systems as possible.
However, if it's easy to do so, perhaps it would be best to use coordinate systems which are only a little bigger than their children. Perhaps only twice as big as in an octtree would be good because then the distance increases by the power of 2 (!) when transgressing among coordinate systems.

Hmm...
Questions questions...
Perhaps I just need to study a lot more before I even ask the right questions.
But I sure appreciate all help and feedback whenever I can get it to point me in the right direction. Thanks a lot for your help!!
:-)

Regards,
Mark

Just use sectors and coordinates that are valid only for each sector. These local coordinates are relative to the center of the sector, or some other fixed coordinate which is represented on a different scale or by using bigger number types. When an object leaves a sector it is just placed into the new sector it is in, and its relative coordinates are updated so that its global coordinates stay constant.

For something like a death ray that shoots instantly across the solar system you can use the global coordinates in the calculations so that you can get full precision results for the effect something might have on something else across the galaxy.

A similar issue was discussed in
"The Continuous World of Dungeon Siege" by Scott Bilas

http://www.drizzle.com/~scottb/gdc/continuous-world.htm

Hi all!

Wow! THANKS for the BRAIN-MATTER!
:-))

I notice one fascinating effect of sharing information and posting your ideas and problems to forums like this:
Even IF you do not get the perfect finished answer you might want, or actually, even IF you do not get *any* answer at all, just writing about your problem and making a public post of it will give you yourself a new angle and side to look at your problem! After writing my last post, I think I made some progress on how to realize my idea!

But first some replies:

Quote:Original post by aCynic2
This is what I devised as a solution to the problem of FP data going to sci notation when I first started my shooter:

You'll want to partition space into a hierarchical grid system that you can represent in a multi-term polynomial:

x_rel = x3*c^3 + x2*c^2 + x1*c + x0;

same for y and z;
<snip>

Awesome! This is something I've been thinking about!
I had no idea there was a word for it: "SCI Notation"!
It's great to see others come to similar ideas!

Quote:Original post by aCynic2
My first attempt 10 years ago saw planet earth spinning out into deep space. I didn't know calculus then. I still don't know the ODEs necessary. You'll need to use an effecient methodology for orbits. Orbiter uses the Runge-Kutta method, and I suspect I will need it as well.

I had calculus in school, but didn't pay too much attention and especially forgot all about it because I *never* ever used it for anything except for passing a test. I'll have to re-learn it from scratch if I need it.
No idea what the Runge-Kutta method is (sorry, link only in German so far). - I'll have to look into it.

Quote:Original post by aCynic2
Also, keep in mind, if we were to consider our galaxy as the norm, the closest star system to us is 4.36 light years away, meaning you'd need to figure out where the target would be 4.36 years from the time of firing.:)

Yes... :-)
No doubt. I'm not sure yet if I will include an option to simulate light speed with all its effects. But you're right, it needs to be considered BEFORE IF you do.

Quote:Original post by Vorpy
Just use sectors and coordinates that are valid only for each sector. These local coordinates are relative to the center of the sector, or some other fixed coordinate which is represented on a different scale or by using bigger number types. When an object leaves a sector it is just placed into the new sector it is in, and its relative coordinates are updated so that its global coordinates stay constant.

For something like a death ray that shoots instantly across the solar system you can use the global coordinates in the calculations so that you can get full precision results for the effect something might have on something else across the galaxy.

Yes, this seems to be getting "warm" / closer to my problem...!
:-)

Quote:Original post by tag
"The Continuous World of Dungeon Siege" by Scott Bilas

http://www.drizzle.com/~scottb/gdc/continuous-world.htm

Awesome!!! That engine contains GOOPS and goops of stuff I had planned for my engine!! It seems sometimes different people dream the same dreams! :-)))
That text really contains fantastic treasure for designing the type of engine I want! Really useful! Especially the point of simply switching "Nodes" or coordinate systems when a small object (spaceship) comes into the vicinity of a larger object (planet to land on, etc). FANTASTIC!!!
Continuous loading, no borders, "world frustum" (space which is kept in memory and updated) are all things which are a *must* for MRPGS and which I had planned!
Dungeon Siege will be a *HUGE* treasure chest for me once I really get started!!
This much seems clear so far!
Thanks! :-))


A little more of my own thoughts now:
When you face a big problem you can't get to grips with, the solution is often finding a (good) way to break it down into smaller problems and attack / solve those. That's what I did:
While it's not hard to partition space in a hierarchical manner, such as with an octtree or nested coordinate systems for stationary objects, it's something else for moving objects which traverse the boundaries between different hierarchical coordinate system levels.
So one of the problems seems to be "movement".
Linear movement (in a straight line) is not such a big problem, because it can be expressed as a direction (expressible in any coordinate system) and a starting point (which is the same as a stationary point = easy).
What is a bigger problem is movement in a circle (or other fancy equation), because you need to describe the movement with an equation which maps it to specific points / vertices in a coordinate system (such as the circle of a planet around a sun or moon around a planet).

So for a coordinate system to allow circular movement, you NEED to have one single coordinate system where the entire movement circle fits into so you can express it as a fluid continuation of changing coordinates.
These coordinates need to be of sufficiently small units so the movement is as fluid as possible.
So it seems logic to give every object with a circular movement, such as a solar system an own coordinate system which has the smallest possible units your computer can still handle (integers, floats, doubles, whatever).

At the same time, you need to divide space (the universe) to handle the vast amount of objects, such as with an octtree.

So really, we have SEVERAL different coordinate systems or spatial partitioning and the key perhaps is just fitting these two together or "linking" them together properly.

If I give every object which has moving parts such as a solar system an own coordinate space with smallest possible units the computer can handle, I have a *lot* of different coordinate systems with a lot of different unit lengths.

Now perhaps all these different coordinate systems could be tied together into the "universe" octtree, simply by making the unit size of each such coordinate system the next bigger cube size of a cube of the octtree at a certain level.
Eh...
Here's an example:
Say we have the universe with an octtree and going down the octtree 100 levels will bring us to (this is just a guess!) 1 mile cube size.
Now say we have any kind of object which needs an own ENTIRE coordinate system to describe it's internal movement, such as a solar system with its planets.
Say we have such a solar system which measures 0.9 x 2power32 (4'294'967'296) miles in diameter. In ideal conditions (the smallest possible unit of this coordinate system which would fit into a 32 bit integer), the unit size of the coordinate system for this solar system would be 0.9 miles, giving us the most fluid ("unjumpy") movement of the planets we can get with a 32 bit integer.
Now if we map or "link" that to the next bigger cube size available from our universe octtree, we simply use 1 mile cubes and then have the same size as a cube from the octtree at level 100. We describe the center of the solar system as one point at level 100 and the movement of the planets is described at this level of precision.
Admittedly, this also leaves some imprecision, but we don't have any limits how big or small our universe / world can get.

Anyway, what it all boils down to is probably using several existing techniques such as:

1.) Divide the universe with an octtree to place all objects and give unit sizes of all possible (object) coordinate systems.
2.) Give each object an own coordinate systems with as many and as small as possible units as will fit into the CPU / GPU (int, float, double) with the size of a universe-octtree-cube. This allows fluid movement within an object while having positions describable in the universe octtree / space (SCI Notation).
3.) Link cubes like in a portal engine.
4.) Change coordinate systems on the fly and update object trees when smaller objects move from one coordinate system / object to the next.
5.) Render scenes which involve several coordinate systems (looking at night sky from within a field of grass) by rendering each relevant coordinate system (in the view frustum and the "world" frustum) in turn.

Or something some such...

Anyway, gotta go, been fun mulling this over once more!
And I'm sure this wasn't the last time!
(I want to get this right!)
:-)

Greetings,
Mark

Quote:Original post by aCynic2
...

So, a 3x3 matrix will be more than enough to hold a galaxy...but you wouldn't want to model a galaxy too realistically. People would be traveling for years to find a fight.

...

This statement, IMO, is much, much more important than trying to figure out how to realistically model a galaxy / universe.

Space is boring. It's 99.99999% nothing, and the stuff that does exist is so far away our minds just can't comprehend the distances.

Freelancer, my favorite example of this, completely threw out any sort of realism to make a fun game. It also uses sectors connected by jump holes and small, closely aligned planets, so I think they don't even worry about precision issues because you don't get far enough out from the origin

The real question that always pops into my mind when universe rendering comes up is this: how are you going to make it fun? It's the reason that I haven't started on my own space sim; it's a thorny problem.

Back on topic, don't take too much from the Dungeon Siege article, as their approach suffers from a problem that will make space sims worthless: the ability to locate other players in the world. Because of the floating frame system, the engine has absolutely no idea how to locate to another player (aka, you cannot map a player on the map, you can't draw an arrow pointing to said player's location, etc).

Otherwise, from my research, I do believe that a floating origin system, coupled with hierarchical transformations (which galaxy => which sector => where in that sector) is the way to go.

Hi all,

Thanks once again for your contributions!

First off, aCynic2, here are some resources to real space info I like:
An Atlas of the Universe
(Our galaxy is about 90'000 light years in DIAMETER. - 200 billion stars... - I *know* I won't be able to put them all in one coordinate system. I'll have to cluster them and make them sub-objects of galaxy sub-cubes. :-)

Cosmos - A Dimensional Journey
(Real Sizes, from Electron to Universe!)

You can find these links and more at: Wikipedia - Universe


The reason why I want to model a REALISTIC universe is this:
MRPGS is supposed to cover AS MANY pen & paper RPGs as possible.
As each game probably uses its own model, I have no idea what kinds of models MRPGS must be able to simulate. Therefore I am taking REALITY as a worst-case scenario. There might be an RPG out there which uses realistic measurements so MRPGS must be able to run that. Besides, I'm a fan of realistic simulations. Even games which don't involve space travel (such as D&D for instance), I'd like to have a realistic sky and realistically simulated day & night, moon, and the consequential lighting! :-)

I've thought some more about the text about the Dungeon Siege engine.
One point especially: Memory management!
In Dungeon Siege, they had a big problem with memory. In fact, it seems a lot of 3D engines must manage their memory very carefully, especially if they are to run with 256MB of RAM.
What this boils down to is, if I want to simulate the position of stars accurately and display them in a night sky, I *MUST* use discrete Level Of Detail. There's no way how any memory could hold all the vertices of multiple stars, their planets and all that's one them. Actually even loading them and then using an algorithm to reduce them is a huge waste. Stars on a night sky *must* be displayed as single pixels or tiny objects.

I really am going to have to work with multiple kinds of objects, LOD's, etc.
The same goes for planets. Imagine a planet like a city-planet all covered with one big city, or worse, something like the death star!
There's no way how all those vertices (no matter weather created procedurally, or stored on disk) can be taken into computation all at once. I'll have to work with a sphere and individual subsections which are dynamically moved in and out of memory if someone flies over the surface of such a thing.

Currently I'm working on an update for the webpage of www.mrpgs.net and hope to have a self-made forum running in about 3-4 days.

Regards,
Mark