I know what you mean, Charles. Good idea. The galaxy is already broken down into quadrants (at the moment, each is 8x8x8 LY and there are 128x128x128 of them) so I can just use a star''s position within its quadrant together with the quadrant''s position (or even just its index), and thus sort of use two floats for double precision. Right?

~CGameProgrammer( );

-- Upload up to four 1600x1200 screenshots of your projects, registration optional. View all existing ones in the archives..

Yep it's possible if you can ensure that no planet straddles your quadrant faces. In fact my proposal (I understand it was not very clear) handles such problematic cases.

It's more like this for each coordinate :

Your static data :Xc  : star center in 64 bits,x   : local model coords in 32 bits.The the 'scene' :64 bits coords      X0    X1    X2 Xc X3   X40-------------------|-----|-----|--*--|----|32 bits coords      x0    x1    x2 xc x3   x4 

X0 = origin of your 32 bits coords = k*2^n units
X1 = min galactical boundary of your quadrant.
X2 = your quadrant center
X3 = max ...

X3-X1 = 2*2^n = size of your quadrants
X4-X0 = 4*2^n

x0 = 4*2^n = bias used to fix the floating point.

xc = (Xc-X0) + x0 = center of the star in 32 bits

4*2^n <= xc < 8*2^n

Remark : xc can straddle or even be a bit out of your quadrant, for instance xc < x1 is possible.

Transfo :

x' = R*{x,y,z} + xc

Since xc is small D3D or GL won't mess with precision. In fact

R*{x,y,z} will keep exactly 2^(n-22) units of precision after it's summed to xc.

I hope it's clear, but it ensures that your models will render exactly the same wherever you translate it in the deep space.


[edited by - Charles B on March 2, 2004 1:58:03 PM]

Sorry, I can't follow any of that, Charles. But the way I'm going to do it is... well, take the case of calculating the distance between two points:

Each point has the 32-bit floating-point coordinate relative to the center of its quadrant, and it knows which quadrant it's in. [EDIT: In the following example, the coordinates aren't relative to the center, just the corner, but it's clearer this way.] Since quadrants are equally-sized cubes of space, their position can be described by three integers that are indexes into the 3D array of quadrants that make up the galaxy. To calculate the offset vector from one point to another:

Offset.X = (p2.X - p1.X) + (QUADRANT_SIZE * float(p2.qX - p1.qX));

and ditto for the Y and Z dimensions. So, given the absolute coordinates:

p1.abs = (-16,4,10)
p2.abs = (64,22,12)

...and with QUADRANT_SIZE = 10, the local coordinates would be the absolute coordinates MOD 10. I'll say the center of the array is index 0 just to make things clearer. The local coordinates are then:

p1.loc = (4, 4, 0)
p2.loc = (4, 2, 2)
p1.q = (-2, 0, 1)
p2.q = (6, 2, 1)

In case that's not clear, point #1's absolute X position is -20 + 4, so the -2 quadrant with a local coordinate of 4. Anyway, calculating the offset vector p2 - p1:

Offset.X = (4 - 4) + (10 * (6 - -2)) = 80
Offset.Y = (2 - 4) + (10 * (2 - 0)) = 18
Offset.Z = (2 - 0) + (10 * (1 - 1)) = 2

Conclusion:

p1 + (80, 18, 2) = p2.

Very easy. And that equation deals with small numbers the entire time. Your way, whatever the hell you were talking about, is I assume perfectly good for other situations, but because I have a grid of equally-sized quadrants, mine works very well.

EDIT: Really, what I'm doing is a form of double-precision. I don't have to use the quadrant indices, I can just use any random QUADRANT_SIZE and floating-point indices, since I'm ultimately just doing [Lower + (SHIFT * Upper)]. But since Lower and Upper are evaluated separately, it avoids errors that even doubles would have.

~CGameProgrammer( );

-- Upload up to four 1600x1200 screenshots of your projects, registration optional. View all existing ones in the archives..

[edited by - CGameProgrammer on March 2, 2004 3:54:29 PM]

Your way, whatever the hell you were talking about, is I assume perfectly good for other situations, but because I have a grid of equally-sized quadrants, mine works very well.

Hmm, No it's meant to fit exactly to your problem. I have thought of it 2 years ago, since I already planned how to extend my first embryons of terrain engines to full universes. I know your solution works. It's the first thing that came to my mind before I analysed numerical issues in details. Later I concluded it was not necessary to split the integer (.q) and fractional parts as you do. Because doubles have enough bits to render everything viewed in deep space or even rather close to the planets, near the orbits. So as you will see, I hope I'll be clear enough this time, it works well but splitting coordinates is not the most elegant solution.

Googled: 1 light-year is equivalent to 9.46053 x 10^12 km, 5,880,000,000,000 miles

Remember that 53 bits of precision (doubles) is roughly 10^16. So if your minimum unit in deep space rendering was 1km you could locate objects up to 10^3*(10^13) = 1000 light years. Now if your minimum unit is 100m, You have your initial 128 light years. Well 100 meters is far enough to locate your planets or stars rather accurately, since their radius are thousands of kilometers. Am I right ?

If you use one int and one float for that, you have 31+24 = 55 bits of precision (I count the sign bit in the int). So why complicate things so much for just 2 more bits of precision ?
Using doubles is more simple, concise (less code) and efficient.


I was still probably unclear but the solution I proposed is totally equivalent in functionality to your approach :
Proof (obvious) :
Q.x = int( P.x* inv_Quadrant_Size )
Loc.x = P.x- Q.x*Quadrant_Size

If Quadrant_Size is a power of two, this relation is inversible without a single bit lost. That is : P -> (Q, Loc) -> P gives you exactly the same P. And BTW when you said random quadrant size . It's very important to stick on 2^n sizes. Since it's an arbitrary choice, choose the digits that waste no precision when you multiply or divide. Your previous posts showed you used them so probably you see what I mean.

Another advantage is you'll have less problems when for instance the Death Star straddles your current quadrant boundary. I'll try a sample code this time. It should make it all clearer and thus reading back the two previous posts you should see what I meant with these powers of two.


// First find your quadrant indices
q.x = int(Eye.x*inv_Quadrant_Size); q.y =...; q.z=...;

// Quadrant corner, (Quadrant_Size=2^n)
Q = q * Quadrant_Size

// Eye position in the quadrant.
E = Eye - Q; // E is 3 floats, 0 < E.x < 2^n

// Fix numerical precision to 23 bits (optionnal)
//Note : I loose offe bit less than in my previous post
E+= Bias; // 2^n <= E.x < 2*2^n


// Get the objects centered in this quadrant
// I assume you also use qudrants for space partition and rendering order Right ?
ppStars = Grid[q.z][q.y][q.x];
...
// Render each object
while( pStar )
{
...
C = pStar->Center - Q; // C is 3 floats, 0 < C.x < 2^n
C+= Bias; // Optionnal
... inverse rotate camera, translate by C-E, rotate star
... send the vertices of your star stored as local model coords.
}

... Render the stars in the neighbour quadrants the same way.

... Render far stars by sending 64 bits coordinates

This is the best way to have a constant and secure numerical precision.

Last point, but it may be crucial. Having your star centers stored as doubles enables you to compute distances and interactions between stars easilly. Or at least you'll model their elliptic paths without having to worry with tricky coordinate changes when it crosses a quadrant boundary. In respect to physics computations your 'star system' is more coherent and practical.


[edited by - Charles B on March 2, 2004 8:07:46 PM]

I''ll have to think about your code. I''m in the middle of implementing my solution with a "quadrant size" of 4096. Since my current galaxy is 1024*8192 units per side, that''s equivalent to 2048*4096 so it''s reasonable to just use a quadrant-size (better called a shift size) of 4096. And that''s 2^12 so fine.

Also mine won''t have problems with anything near boundaries, but then again I''m not using it for rendering, just precision. I whipped up a coordinate class that has a 32-bit high and low, with value = Low + (SHIFT * High). It''s like a double except of course high and low are operated on separately before being combined into that equation.

I mentioned I used quadrants for rendering, but that has nothing to do with the precision problem of this post. For distant-star rendering, all stars in a quadrant are packed onto the same vertex buffer and rendered very quickly. Also, of course, it''s very easy to figure out what''s visible, and the memory usage is minimal.

~CGameProgrammer( );

-- Upload up to four 1600x1200 screenshots of your projects, registration optional. View all existing ones in the archives..

K good luck for your implementation, don''t worry it makes sense, particularilly if you want to extend absolute coordinates to even wider ranges. Sorry if I disturbed you with these details. But it helped me to remember an old idea I had in mind. I''ll just add the texts in my doc base. I hope you''ll be able to show us an improved demo soon.

I have equivalent questions to solve, for instance handling physics (Positions) in very large continuous environments. It''s probable I''ll also need to clusterize the scene (based on the quadtree max level). Else I''ll have magnitude conflicts between positions, velocities*dt, and acceleration*dt^2. So anyway it''s good to work on your idea. It makes sense considering the future standards in video gaming.

UPDATE: I''ve gone and implemented a coordinate system like I described. The absolute position of the camera is stored, which is not the best, but it works. Here''s a portion of the coordinate class I wrote, showing the more interesting functions. The class is very simple:

class coord{    public:    //  Build a coordinate from a vector:        coord ( vectorf V )        {            High( floorf(V.X / SHIFT),                  floorf(V.Y / SHIFT),                  floorf(V.Z / SHIFT) );            Low( V.X - float(High.X * SHIFT),                 V.Y - float(High.Y * SHIFT),                 V.Z - float(High.Z * SHIFT) );        }    /*  Change this coordinate, but also allow        for an invalid L. So if SHIFT is 10 and        L is -1 or 10, Low and High are adjusted        so Low is within [0..10). */        inline void Set ( vectorf L, vectorf H )        {            High.X = H.X + floorf(L.X / SHIFT);            High.Y = H.Y + floorf(L.Y / SHIFT);            High.Z = H.Z + floorf(L.Z / SHIFT);            Low = L - (SHIFT * (High - H));        }        inline operator vectorf ( )        {            return Low + (SHIFT * High);        }    /*  See? This kind of function can easily        pass an invalid Low value, which is        why Set needs to do what it does. */        inline coord& operator += ( coord C )        {            Set( Low + C.Low, High + C.High );            return *this;        }    //  Adding a vector is simple.        inline coord& operator += ( vectorf V )        {            Set( Low + V, High );            return *this;        }    private:    //  They''re both 32-bit floats but I''ll change    //  them to doubles later on.        vectorf         Low;        vectorf         High;        static float    SHIFT;        friend          coord;};

~CGameProgrammer( );

-- Upload up to four 1600x1200 screenshots of your projects, registration optional. View all existing ones in the archives..

It''s mathematically correct but it will be a very slow vector class. Benchmark your operations, floor is usually a pity in C. You can optimize a lot (store 1/SHIFT etc...) but still it will be very slow compared to the double float system I explained. If you #define SHIFT=1<
Well this depends on how much you rely on these coords. If it''s just for a few star centers, why not.