Thoughts on Scale: Space Gerbils back

(L) [2009/02/06] [phresnel] [Thoughts on Scale: Space Gerbils] Wayback!

I've decided to rewrite the kernel of picogen. That means basically I will rewrite picogen ([LINK http://greenhybrid.deviantart.com/art/redshift-logo-111437922] , heya lyc). The reason is that at the moment, picogen is more or less based on a general purpose architecture. As long as it's so general it will never win an award. Also, it doesn't scale that fine.
The next kernel will be called "redshift", implying the order of magnitude I am targetting. Also implying that I am basically not sane, of course.
So my first thought was to base the acceleration structure on the orders of magnitude. Another thought was to base the acceleration structure and LOD measures on the diameter projected onto the hemisphere, combined with some roughness (e.g. for planets, the roughness could be a measure on the minimum and the maximum radius).
Also, as for coordinates, floating point numbers can't be used as is. One solution could be that each space coordinate is made of several numbers, each corresponding to a group of magnitudes. Or I think in terms of Einstein, and will only define local coordinates, in relation to some base. Or I trust in int64: 2^64=18,446,744,073,709,551,616. Playing with that though, let's say the fractional part is for meters (for convenience), and let me cut out 2 bytes for the fractional part (so the lowest length quantum has size 0.000015259), I can span 281,474,976,710,656 meters = 281,474,976,710 kilometers = int48.km.max. This would be enough to span 28 times the radius of our solar system, based on the distance between the sun and the farthes known dwarf planet, or 62 times the radius Sun/Neptune (the farthest of the "true" planets), at the resolution of roughly 0.00002 meters.
Yay, so int64 ftw?
What would you do?
What I have researched so far is the following list, also posted for future reference:
(Planet sizes are are diameters)
< 0.000 01m - profit< 0.000 1m - int64 smallest unit: 0.000 02 meters.< 0.001m - profit< 0.01m - Paramecia + stuff< 0.1m - Plants, Small animals< 1m - Plants, young trees< 10m - Older trees, Buildings, Dinosuars, Horses< 100m - Gardens, Groups of houses< 1km - Cities, Forests< 10km - Cities, Small Mountains (in cosmic measure), Depth of the Seas< 100km - Reasonable Mountains, Nuclear Mushrooms, Atmosphere (Tropo-/Strato-/Mesosphere), Range of Big Bertha with light ammo (13km), "Range" of Reasonable Cities(end of my personal guesses, now follows data from wikipedia)
< 1,000km / 1Mm - Range of the Paris Gun (130km), Countries, Very Small Moons< 10,000km / 10Mm - Dwarf Planet Eris 1,300km, Dwarf Planet Pluto 2,400km, Moon 3,400km, Mercury 5,000km (innermost of solar system planets), Mars 6,800km< 100,000km / 100Mm - Earth 12,700km, Neptune 50,000km (outermost of solar system regular planets), Uranus 52,000km< 1,000,000km / 1Gm - Jupiter 143,000km, Distance Earth/Moon (approx. avg. 385,000km),< 10,000,000km / 10Gm - Sun (1.4Gm)< 100,000,000km / 100Gm - Distance Sun/Mercury 58,000,000km1 Astronomical Unit (approx. = Distance Sun/Earth)
< 1,000,000,000km / 1Tm - Distance Sun/Earth (approx. avg. 149,598,000km),< 10,000,000,000km / 10Tm - Distance Sun/Neptune (outermost of solar system regular planets) 4,554,000,000km< 100,000,000,000km / 100Tm - Distance Sun/Eris 10,100,000,000km (farthest of the known dwarf planets)< 1,000,000,000,000km / 1Pm - 281,474,976,710 kilometers = int48.km.max (from the mind play above)Gone so far. Yet all we have managed is to leave the Solarsystem
Oh, and feel free to report any error in my mindplay! Your help is very very much appreciated!
References:
[LINK http://en.wikipedia.org/wiki/Orders_of_magnitude_(length])
[LINK http://en.wikipedia.org/wiki/List_of_largest_stars]

(L) [2009/02/06] [beason] [Thoughts on Scale: Space Gerbils] Wayback!

Maybe just move to double's? And have planets/stars in their own coordinate system which you switch to as the ray arrives there?
Also keep in mind that objects that are thousands of km away appear very small. The sun for instance is very small on film even though it is massive, due to that 1/r^2. Even if you compensate by making your far away objects bigger, the fine detail will be lost on viewing. If you had a telescope things might be different, but the telescope limits your fov and amount of visible objects.

(L) [2009/02/06] [phresnel] [Thoughts on Scale: Space Gerbils] Wayback!

The reason why I come with the int64 was that it would enable me to move everything at quantum scale (the mentioned example unit of 0.00002), without having to "fiddle the objects between different einstein elevators", plus I'd like to have a quasi constant, absolute precision. Using floating point math this could be really tricky, I guess, and so I though the twofold int/float combination (where the float could also mean double) would be the one with the least overhead.
sidenote: I think I can, for now, ignore the beyond solar system scale, as I haven't plans to simulate telescopes.
edit: Either I have to meditate, or you edited your post [SMILEY :D] You are right about that, and I had an initial (yet irrelevant) thought about a solid angle based approach, and I came to the conclusion (for now) that I definitely want to be able to zoom smoothly from the sun towards the earth surface (once in a future).

(L) [2009/02/06] [moomin] [Thoughts on Scale: Space Gerbils] Wayback!

>> beason wrote: Even if you compensate by making your far away objects bigger, the fine detail will be lost on viewing
Quoted for truth. I think a high precision (or high scale) system is an awesome idea, but I can't see that this is any use unless you are generating extreme resolution images...

(L) [2009/02/06] [phresnel] [Thoughts on Scale: Space Gerbils] Wayback!

sidenote: I once in the beginning of picogen had serious 32bit-fp precision issues with sphere of size 100000.0f (hence I switched to double), and when I think about it, I don't think double precision will be enough for ant-to-solar-system-scale; but I am not competent enough to argue about that [SMILEY :P]
sidenote: I initally opened another topic, but felt I'd better merge it in to here. Here it comes:
---------------------------------------------------------
Probably I am a fool. But in another thread ([LINK http://ompf.org/forum/viewtopic.php?f=4&t=1209 Thoughts on Scale: Space Gerbils]) I am talking about using int64 as the base type for it all.
Now a technique comes into mind for which I am unsure whether it already exists. For those who are not going to read my whole space-gerbils post: Basically I am maybe going to choose int64 as the base type, instead of float or double, so that no epsilon issues arise in a gerbil->space scaled environment. But then my interest in doing everything in fixed point, including square root computation, is not that high.
So, I though I would translate the object to intersect and the ray into a unit space of floating point numbers (whereas even that could be problematic for objects like [LINK http://en.wikipedia.org/wiki/VY_Canis_Majoris VY Canis Majoris] (*), but let that for now be an implementation detail; maybe this can be solved by tesselation). For that to be not too slow, I thought I would store for each intersectable object in fact two vectors, one in int64-absolute-space, one in float-unit-space, plus a corresponding transformation unit (probably just a translation vector), for the ray.
Now, for each intersection to be performed on object A, I would transform the ray given A's transformation unit, and perform the intersection between the ray and the object's floating point representation. Example:

struct Sphere {
    Vector<int64> absolutePosition;    int64 absoluteRadius;
    Vector<float> unitSpacePosition;    float unitSpaceRadius;
    Transform<int64, float> rayTransform;
};
intersect (sphere, ray) {
    unitisedRay = sphere.rayTransform (ray);
    perform canonicalRaySphereIntersection (unitisedRay, sphere.unitSpacePosition, sphere.unitSpaceRadius);
}

Now my questions:
0) Do you see any issues with this approach, or better alternatives?
1) Does such an approach already exist?

Footnotes:
[LINK http://ompf.org/forum/viewtopic.php?f=4&t=1209 Thoughts on Scale: Space Gerbils](*) VY Canis Majoris:
[IMG #1 Image]

---

[IMG #1]:

(L) [2009/02/06] [moomin] [Thoughts on Scale: Space Gerbils] Wayback!

>> 1) Does such an approach already exist?
Yes, for a space-simulator-game in development [LINK http://www.infinity-universe.com/].
The developer of that game decided upon the exact system you did (floats with int64.) The link is to the development journals website, couldn't find the relevant entries on first glace though as that original design decision was made >3 years ago I believe.

(L) [2009/02/06] [phresnel] [Thoughts on Scale: Space Gerbils] Wayback!

Is that not Ysaneya? I have often looked into his journals for his terrain/space rendering, but obviously not deep enough [SMILEY #-o] Thank you for that link.
edit: can't find anything on the technique either [SMILEY :(] Did it also include the unit-space idea? (though obviously it would slightly vary towards rasterization)

(L) [2009/02/06] [moomin] [Thoughts on Scale: Space Gerbils] Wayback!

It is Ysaneya yes. I think his gamedev.net [LINK http://www.gamedev.net/community/forums/mod/journal/journal.asp?jn=263350] contains info about his coordinate system in the entries around 2005, the sheer number of entries prevents me from locating it so far.
Orignally he dabbled with 32/64 bit floats I believe, but didnt like 32bit floats due to lack of precision, and doubles because GPU's don't like them (I don't think he found an issue with precision of doubles.)
I'm quite sure his system uses a 32bit float and 64bit integer, where the integer references a kind of 'zone'. All objects in the same zone as the camera are sent to the renderer ... but I'm not sure how he handles objects in different zones (and it will be most likely optimized for a rasterizer.)
edit: I say referenced a zone, but they were still simple integer coordinates (64*(x+y+z))

(L) [2009/02/07] [tbp] [Thoughts on Scale: Space Gerbils] Wayback!

[LINK http://home.comcast.net/~tom_forsyth/blog.wiki.html][[A%20matter%20of%20precision]]
edit: annoying url, sorry.

(L) [2009/02/07] [phresnel] [Thoughts on Scale: Space Gerbils] Wayback!

>> tbp wrote:http://home.comcast.net/~tom_forsyth/blog.wiki.html#[[A%20matter%20of%20precision]]
edit: annoying url, sorry.
Yay, thanks for that link. It's funny to see his mindplay in one paragraph:
 >> Tom Forsyth wrote:The nice thing about fixed point is it's consistent. You get the same precision everywhere. If your time step and physics epsilons work at the origin, they work everywhere. And before you moan that fixed-point doesn't have the range - 32 bits of fixed-point gets you anywhere on Earth to about 3mm. Not enough? Well 64 bits of precision gets you to the furthest distance of Pluto from the Sun (7.4 billion km) with sub-micrometer precision. And it's all consistent precision - no lumpy parts or fine parts or places where you suddenly get denormals creeping in and your performance goes through the floor for no well-identifiable reason.
So that really sound promising. And if I am really going to do intergalactic travels, I could still use int128 or even int256 [SMILEY :D]
footnotes
number of unique large integer states:
int32: 4,294,967,296int64: 18,446,744,073,709,551,616int128: 340,282,366,920,938,463,463,374,607,431,768,211,456int256: 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936

(L) [2009/02/07] [Screeb] [Thoughts on Scale: Space Gerbils] Wayback!

Hmm, I haven't worked out the maths, but wouldn't a float128 suffice? I imagine that even in the outer reaches of the solar system you could still get very good accuracy. Or maybe not. I can't be bothered doing the maths [SMILEY :P]

(L) [2009/02/07] [Guest] [Thoughts on Scale: Space Gerbils] Wayback!

>> Tom Forsyth wrote:The nice thing about fixed point is it's consistent. You get the same precision everywhere. If your time step and physics epsilons work at the origin, they work everywhere. And before you moan that fixed-point doesn't have the range - 32 bits of fixed-point gets you anywhere on Earth to about 3mm. Not enough? Well 64 bits of precision gets you to the furthest distance of Pluto from the Sun (7.4 billion km) with sub-micrometer precision. And it's all consistent precision - no lumpy parts or fine parts or places where you suddenly get denormals creeping in and your performance goes through the floor for no well-identifiable reason.

(L) [2009/02/07] [Screeb] [Thoughts on Scale: Space Gerbils] Wayback!

Yes, but what I'm saying is that perhaps float128 is good enough that those issues won't arise / be noticeable.

(L) [2009/02/07] [Guest] [Thoughts on Scale: Space Gerbils] Wayback!

That kind of argument is exactly what Forsyth debunks. Some floating point types have hardware support, but they all suck the farther you are from origin. Have an offset in fixed precision, and a local floating point coordinate and stop throwing double/float128/float4096 around everytime an entirely expectable relative precision issue arises.
Float128? Haha.

(L) [2009/02/07] [Paapaa] [Thoughts on Scale: Space Gerbils] Wayback!

What about performance of sqrt() and trigonometric functions with integers as opposed to floats?

(L) [2009/02/07] [tbp] [Thoughts on Scale: Space Gerbils] Wayback!

The idea is that you don't even try. You only need to support fast basic operations in fixed point, and switch to fancier floating points for local/relative coordinates (once you are reasonably sure you're not going to shift that mantissa out).
Note: gcc has an extension for fixed point types.

(L) [2009/02/08] [soren renner] [Thoughts on Scale: Space Gerbils] Wayback!

You could have nested spaces as a tree of objects. But earth gerbils at least burrow in the ground, and are never found in trees.

(L) [2009/02/09] [phresnel] [Thoughts on Scale: Space Gerbils] Wayback!

>> soren renner wrote:You could have nested spaces as a tree of objects.
While something like that would enable me a kind of infinite and arbitrary scale, this was exactly what I wanted to avoid when I said that I don't want to "fiddle the objects between different einstein elevators" [SMILEY :D]
 >> But earth gerbils at least burrow in the ground, and are never found in trees.
I will take the potential of this optimisation into account for a standards compliant Earth-200x mode.

(L) [2009/04/20] [wizzard0] [Thoughts on Scale: Space Gerbils] Wayback!

Pretty interesting. As well as raytracing itself is a 'generic approach', I look forward to the 'engine that can handle anything' with hope [SMILEY :)]
What is the current status, though?
//subscribed

(L) [2009/04/21] [phresnel] [Thoughts on Scale: Space Gerbils] Wayback!

>> wizzard0 wrote:Pretty interesting. As well as raytracing itself is a 'generic approach', I look forward to the 'engine that can handle anything' with hope
What is the current status, though?
//subscribed
Current status is that I am wrestling a lot with a QT frontend [SMILEY :D]
[IMG #1 Image][IMG #2 Image]
(the rendering preview window shows what the new version is able to render atm  [SMILEY :|] )
I am currently doing a complete rewrite of picogen. Note that anyways that rewrite will be done faster than coding the previous picogen, as I am losing less time with experimentation like [LINK http://ompf.org/forum/viewtopic.php?f=8&t=999 this] or [LINK http://ompf.org/forum/viewtopic.php?f=6&t=1012 that], but rather try to code straight.
According to dA-fellow [LINK http://kram1032.deviantart.com/ kram], int256 should be enough to simulate the universe at planck length [SMILEY :P]
Btw, you can bet that I keep you up in date, either here on ompf, or on [LINK http://greenhybrid.deviantart.com/] , or on that buzzy [LINK http://twitter.com/picogen] (or even maybe on picogen's homepage).

---

[IMG #1]:Not scraped: https://web.archive.org/web/20110723054140im_/http://th02.deviantart.com/fs43/150/f/2009/106/9/4/picogen__Visual_Coding_by_greenhybrid.png
[IMG #2]:Not scraped: https://web.archive.org/web/20110723054140im_/http://th00.deviantart.com/fs44/150/f/2009/103/8/d/terrabite__a_picogen_frontend_by_greenhybrid.png

(L) [2009/04/22] [wizzard0] [Thoughts on Scale: Space Gerbils] Wayback!

Wow. Code/shader generation from a visual frontend-preview is something I've been thinking about for years, but never got dreamed too much to actually implement [SMILEY :)]
I'll add you to my DeviantWatch.
Also... *got some thoughts about voxel raytracing, but can't explain right there right now. Maybe later [SMILEY :)]