Procedural landscape generating algorithm.

Hi.

I was trying to figure out a method to solve the following problem. I
wanted to build a program, like a game (although not with any
objective), where you could explore a whole virtual "galaxy" of
planets and stars in a star ship. But the thing is that I want it so
you can fly from the "space" all the way to the surface of the planets
_seamlessly_, and then be able to fly all over their surfaces to every
point, with the planets realistically-sized (1000s of miles across).
The old games "Elite", "Frontier", and "Frontier: First Encounters"
had this capability. But how can one program something like that?
Obviously it would have to be able to generate the surface
procedurally (as it is pretty much impossible to store pregenerated
data for a galaxy of several hundred billion planets and stars), and
we're working on a sphere here, not a plane, which has quite different
topological properties. Plus one probably needs some sort of "level-of-
detail" algorithm in there to avoid creating so many facets as to be
impossible to store (if you want to render down to 1 m^2 resolution an
_entire_ planet the size of Earth you'd need something like 10^21
facets -- many zettabytes of information. But you don't need to since
the resolution of your monitor is limited and the further away things
are the more they can be smplified.), not to mention calculate.

So how would one go about that, anyway? The LOD stuff, the spherical-
topology terrain generator (which is harder than a plane and even
harder still if you want some constraints like certain areas having
mountains and others not to break up the monotony, as well as
"unusual" features like FOOMs. Not to mention more-difficult forms of
terrain like craterized planets (examples: Mercury & Moon in our solar
system).), and most importantly, how to marry the two together.

"mike3" <mike4ty4@yahoo.com> wrote in message
news:e040c309-c410-4458-a90d-4043bd87f901@p10g2000prf.googlegroups.com...
> Hi.
>
> I was trying to figure out a method to solve the following problem. I
> wanted to build a program, like a game (although not with any
> objective), where you could explore a whole virtual "galaxy" of
> planets and stars in a star ship. But the thing is that I want it so
> you can fly from the "space" all the way to the surface of the planets
> _seamlessly_, and then be able to fly all over their surfaces to every
> point, with the planets realistically-sized (1000s of miles across).
> The old games "Elite", "Frontier", and "Frontier: First Encounters"
> had this capability. But how can one program something like that?
> Obviously it would have to be able to generate the surface
> procedurally (as it is pretty much impossible to store pregenerated
> data for a galaxy of several hundred billion planets and stars), and
> we're working on a sphere here, not a plane, which has quite different
> topological properties. Plus one probably needs some sort of "level-of-
> detail" algorithm in there to avoid creating so many facets as to be
> impossible to store (if you want to render down to 1 m^2 resolution an
> _entire_ planet the size of Earth you'd need something like 10^21
> facets -- many zettabytes of information. But you don't need to since
> the resolution of your monitor is limited and the further away things
> are the more they can be smplified.), not to mention calculate.
>

yes, and to think any of this would be possible to render would be a rather
severe overestimation of the GPU...

FFS it is a pretty damn hard strain to render even the local scene (maybe a
few thousand polygons) with many "modern" graphical techniques, in real
time.


for example, simply rendering a scene with maybe 12000 polygons, purely with
flat texturemaps and no real culling, on my video card only pulls around
10-15 fps. actually, it leads to the ammusing effect that my renderer is
actually much faster with all the fancy lighting effects/shadows/... turned
on, if anything, because it culls the scene, whereas fullbright causes the
world to drag because it simply/stupidly just draws everything...


> So how would one go about that, anyway? The LOD stuff, the spherical-
> topology terrain generator (which is harder than a plane and even
> harder still if you want some constraints like certain areas having
> mountains and others not to break up the monotony, as well as
> "unusual" features like FOOMs. Not to mention more-difficult forms of
> terrain like craterized planets (examples: Mercury & Moon in our solar
> system).), and most importantly, how to marry the two together.


well, an idea here could be this:
several different renderers are used.

for example, you have your space-based renderer, which would render things
mostly as just spheres (no big complex stuff here, use a sphere and have a
texturemap for the planet).

as one approaches the planet (such as reentry), a secondary renderer is
used, which may draw local atmospheric effects and an approximate "large
area" / "horizon line" for the planet being approached (only really
mountains are drawn, and faces are probably very large, such as 1km or 10km
or more).

as one nears the surface, they switch to their ground-level renderer, which
draws all of the stuff in their nearby vicinity.

now, the other renderers could still have use, but due to limitations and
similar, all this stuff can't be represented in realistic scale in the
z-buffer (typically, these are confined in terms of range and precision, so
rendering a larger space means it is much more approximate, leading to
graphical issues, and rendering a space more accurately means that one is
limited to rendering a much smaller space, with anything too far away simply
disappearing...).


the idea then is to calculate the position on the planet as a position and
orientation in space, and render this to a texture (of course, likely
leaving out the current planet).

then, in a similar way the sky renderer is invoked, and rendered to a
texture (or, this may have already invoked the space renderer, simply
drawing some effects on top of the prior texture).

this way, space and the sky can be effectively rendered in real-time from
the ground (them being drawn similar to a skydome or skybox).


the ground renderer does not need to take into account a spherical world,
but may actually only render for a local area (such as a rectangle), but may
use some info from the sky renderer, such as general topological
information, ..., to avoid obvious seams.

for example, the sky renderer gives you distant mountains, and the ground
and similar is generated and refined on approach, and simply disappears when
one moves away (although, any cities or "important areas" may have static
terrain, and it may well make sense to keep a prebuilt version of the
general topology around, which could probably be represented as something
analogous to an image file).

potentially, it could make sense also to keep a cache of recently-visited
stuff, to allow someone to go back somewhere without having it be completely
different (all of this info likely being stored in something analogous to
tile-maps, and probably not as renderable geometry...).

effects like global position and altitude could be faked, in effect, by
having the world move partly relative to the camera (at least at ground
level). an idea here would be to effectively confine the camera to a largish
box, and then "teleport" it (and also the terrain) whenever it crosses a
border (a somewhat larger box being used for the area of currently visible
terrain).


so, the result is that it may look like an entire solarsystem or galaxy is
being rendered, but really, it is much more local.

mike3 wrote:
> I was trying to figure out a method to solve the following problem. I
> wanted to build a program, like a game (although not with any
> objective), where you could explore a whole virtual "galaxy" of
> planets and stars in a star ship. But the thing is that I want it so
> you can fly from the "space" all the way to the surface of the planets
> _seamlessly_, and then be able to fly all over their surfaces to every
> point, with the planets realistically-sized (1000s of miles across).
> The old games "Elite", "Frontier", and "Frontier: First Encounters"
> had this capability. But how can one program something like that?

I see you are mainly interested in planet drawing, but really can't resist:

The galaxy itself in Frontier and FFE requires a base image (a seed): a
top down view of the Milky Way. This image is extrapolated to the
desired 'resolution' in light years, then the seed is used to generate
individual stars -- including binary, triple, and even sextuple star
systems, complete with planets and moons.
In case you're interested how this works, I would normally refer you to
my web site, but it seems to be hijacked by an evil advertiser![*]

Normal services should resume as soon as I killed them.

[JongWARe]
[*] In casu, Adxtn.com, active since Feb. 08, powered by Directi
Internet Solutions.
An automated statistics site remarks "This site attracts a less affluent
audience."; and "There is a high index of people with no college here."
Praying on the defenseless, eh?

On Aug 28, 8:59*pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
> "mike3" <mike4...@yahoo.com> wrote in message
>
> news:e040c309-c410-4458-a90d-4043bd87f901@p10g2000prf.googlegroups.com...
>
>
>
> > Hi.
>
> > I was trying to figure out a method to solve the following problem. I
> > wanted to build a program, like a game (although not with any
> > objective), where you could explore a whole virtual "galaxy" of
> > planets and stars in a star ship. But the thing is that I want it so
> > you can fly from the "space" all the way to the surface of the planets
> > _seamlessly_, and then be able to fly all over their surfaces to every
> > point, with the planets realistically-sized (1000s of miles across).
> > The old games "Elite", "Frontier", and "Frontier: First Encounters"
> > had this capability. But how can one program something like that?
> > Obviously it would have to be able to generate the surface
> > procedurally (as it is pretty much impossible to store pregenerated
> > data for a galaxy of several hundred billion planets and stars), and
> > we're working on a sphere here, not a plane, which has quite different
> > topological properties. Plus one probably needs some sort of "level-of-
> > detail" algorithm in there to avoid creating so many facets as to be
> > impossible to store (if you want to render down to 1 m^2 resolution an
> > _entire_ planet the size of Earth you'd need something like 10^21
> > facets -- many zettabytes of information. But you don't need to since
> > the resolution of your monitor is limited and the further away things
> > are the more they can be smplified.), not to mention calculate.
>
> yes, and to think any of this would be possible to render would be a rather
> severe overestimation of the GPU...
>
> FFS it is a pretty damn hard strain to render even the local scene (maybea
> few thousand polygons) with many "modern" graphical techniques, in real
> time.
>
> for example, simply rendering a scene with maybe 12000 polygons, purely with
> flat texturemaps and no real culling, on my video card only pulls around
> 10-15 fps. actually, it leads to the ammusing effect that my renderer is
> actually much faster with all the fancy lighting effects/shadows/... turned
> on, if anything, because it culls the scene, whereas fullbright causes the
> world to drag because it simply/stupidly just draws everything...
>
> > So how would one go about that, anyway? The LOD stuff, the spherical-
> > topology terrain generator (which is harder than a plane and even
> > harder still if you want some constraints like certain areas having
> > mountains and others not to break up the monotony, as well as
> > "unusual" features like FOOMs. Not to mention more-difficult forms of
> > terrain like craterized planets (examples: Mercury & Moon in our solar
> > system).), and most importantly, how to marry the two together.
>
> well, an idea here could be this:
> several different renderers are used.
>
> for example, you have your space-based renderer, which would render things
> mostly as just spheres (no big complex stuff here, use a sphere and have a
> texturemap for the planet).
>
> as one approaches the planet (such as reentry), a secondary renderer is
> used, which may draw local atmospheric effects and an approximate "large
> area" / "horizon line" for the planet being approached (only really
> mountains are drawn, and faces are probably very large, such as 1km or 10km
> or more).
>
> as one nears the surface, they switch to their ground-level renderer, which
> draws all of the stuff in their nearby vicinity.
>
> now, the other renderers could still have use, but due to limitations and
> similar, all this stuff can't be represented in realistic scale in the
> z-buffer (typically, these are confined in terms of range and precision, so
> rendering a larger space means it is much more approximate, leading to
> graphical issues, and rendering a space more accurately means that one is
> limited to rendering a much smaller space, with anything too far away simply
> disappearing...).
>
> the idea then is to calculate the position on the planet as a position and
> orientation in space, and render this to a texture (of course, likely
> leaving out the current planet).
>
> then, in a similar way the sky renderer is invoked, and rendered to a
> texture (or, this may have already invoked the space renderer, simply
> drawing some effects on top of the prior texture).
>
> this way, space and the sky can be effectively rendered in real-time from
> the ground (them being drawn similar to a skydome or skybox).
>
> the ground renderer does not need to take into account a spherical world,
> but may actually only render for a local area (such as a rectangle), but may
> use some info from the sky renderer, such as general topological
> information, ..., to avoid obvious seams.
>
> for example, the sky renderer gives you distant mountains, and the ground
> and similar is generated and refined on approach, and simply disappears when
> one moves away (although, any cities or "important areas" may have static
> terrain, and it may well make sense to keep a prebuilt version of the
> general topology around, which could probably be represented as something
> analogous to an image file).
>
> potentially, it could make sense also to keep a cache of recently-visited
> stuff, to allow someone to go back somewhere without having it be completely
> different (all of this info likely being stored in something analogous to
> tile-maps, and probably not as renderable geometry...).
>
> effects like global position and altitude could be faked, in effect, by
> having the world move partly relative to the camera (at least at ground
> level). an idea here would be to effectively confine the camera to a largish
> box, and then "teleport" it (and also the terrain) whenever it crosses a
> border (a somewhat larger box being used for the area of currently visible
> terrain).
>
> so, the result is that it may look like an entire solarsystem or galaxy is
> being rendered, but really, it is much more local.

That's right, it doesn't need to do it "brute force", just render what
is visible
and to an acceptable level of resolution and toss away all the rest.
So the
planets, viewed far out, would have procedurally-generated surface
texture
based on the large-scale characteristics of the "full" heightmap
(encoded as
mathematical formulas, not stored, of course, as remember the concerns
I mentioned.). Probably not just a texture map but a bump map as well
to
simulate varied terrain.

The simplest algorithm I thought of was one where the poly resolution
falls
off by some amount according to distance out from the camera: so if
you are
high above the planetary surface, polygons may be many kms across. If
you are hugging the terrain you'd polys only a few m or less across in
the
closest parts, and getting lower the further out, with distant
mountains and
stuff rendered using only a few hundred polygons max, and very distant
stuff
vague with only a few tens or less. I.e. have one single unified
renderer that
just renders at variable levels of detail, determined by the camera
position
and quality settings.

I'm sure it would not be too difficult to do with a flat sphere, but
you need to
procedurally generate and regenerate this geometry as you move... how
do
you do that quick? Is there some way to buffer the already-generated
geometry,
so that as you move it can be reused, saving regeneration time to many
fewer
vertices?

The problem with _star systems_ though is, of course, running out of
math
precision. Vertices will lose resolution due to the huge displacement
terms.
Although at double-precision we can go to 4 x 10^15 m before error
becomes
larger than 1m, the furthest planets in a star system may be at like
10^13 m
or beyond. This is enough to start getting (somewhat) visible
quantization
artifacts. Which would mean the star-system data would likely have to
be stored
via some arbitrary-precision format (quad-precision would be plenty, I
think,
that's 104 bits of mantissa. Even 64 bits of mantissa would work), or
still in
DP format, but constantly repositioned so it all works in viewer-
relative
coordinates, not related to some fixed point in the system (actually
this would
apply to both -- arbitrary precision calculations are notoriously CPU-
intensive
and we need to be able to switch to fast CPU-sized math as much as
possible
and keep AP math to a minimum, which means lots of clever and tricky
heuristics.).

This is obviously a very complicated programming problem. I'd really
be curious
as to how those old games I mentioned managed to pull off a
reasonably-
good (for their time) solution to this.

"mike3" <mike4ty4@yahoo.com> wrote in message
news:91b76340-7f68-4d18-a5d1-c636ecaa56c8@s9g2000prg.googlegroups.com...
On Aug 28, 8:59 pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
> "mike3" <mike4...@yahoo.com> wrote in message
>
> news:e040c309-c410-4458-a90d-4043bd87f901@p10g2000prf.googlegroups.com...
>
>


note, I will be using <-- and --> for block quoting (the annoyance from some
people using google groups, and other people using MS usenet clients...).

<--
That's right, it doesn't need to do it "brute force", just render what
is visible
and to an acceptable level of resolution and toss away all the rest.
So the
planets, viewed far out, would have procedurally-generated surface
texture
based on the large-scale characteristics of the "full" heightmap
(encoded as
mathematical formulas, not stored, of course, as remember the concerns
I mentioned.). Probably not just a texture map but a bump map as well
to
simulate varied terrain.
-->

you can generate much lower quality textures, and make use of "caching",
where one can store, say, 64 or 256MB of stuff at each major level, and
discarding older stuff as needed. likewise, caching approaches can also be
applied to the use of texture maps.

now, if the each planetary surface is, say, a 512x256 or 1024x512 texture,
this should be acceptable to retain a planet-wide height image in reasonable
quality.

with a radius of say, 1000km, and a 1024x512 texture, each pixel will be
about 6.14km at the equator (sphere mapping, it will majorly compress at the
poles), or much more linearly if using hemisphere mapping (although the
faces would expand to about 8.68km near the borders, however hemisphere
mapping leaves a certain amount of the texture unused, namely around 58.257
ktexel, or about 21.46% of the image area).


for what all may go in the video card, be sure to keep mind of video
memory...
absent texture compression, 1024x512 textures would require about 2MB each
(the onboard DXTn and friends usually reduce this down to about 256kB each).
of course, keep in note that texture compression also somewhat hurts
precision (this can matter a good amount in many cases...).


<--
The simplest algorithm I thought of was one where the poly resolution
falls
off by some amount according to distance out from the camera: so if
you are
high above the planetary surface, polygons may be many kms across. If
you are hugging the terrain you'd polys only a few m or less across in
the
closest parts, and getting lower the further out, with distant
mountains and
stuff rendered using only a few hundred polygons max, and very distant
stuff
vague with only a few tens or less. I.e. have one single unified
renderer that
just renders at variable levels of detail, determined by the camera
position
and quality settings.
-->

potentially, but the problem then is keeping the generation consistent, and
dealing with depth precission issues.


<--
I'm sure it would not be too difficult to do with a flat sphere, but
you need to
procedurally generate and regenerate this geometry as you move... how
do
you do that quick? Is there some way to buffer the already-generated
geometry,
so that as you move it can be reused, saving regeneration time to many
fewer
vertices?
-->

you could buffer, or you could only generate the geometry at fixed LODs (in
this case, probably log-scaled, such as log^e or log^10).

IMO, it is probably better though to make use of intermediate numerical
buffers, and cache this. possibly, if really needed, there maps could use a
deterministic algo and simply store the RNG seeds, or similar (some storage
is needed in any case, as I don't think it will be practical to have a fully
scalable deterministic RNG sysyem).


<--
The problem with _star systems_ though is, of course, running out of
math
precision. Vertices will lose resolution due to the huge displacement
terms.
Although at double-precision we can go to 4 x 10^15 m before error
becomes
larger than 1m, the furthest planets in a star system may be at like
10^13 m
or beyond. This is enough to start getting (somewhat) visible
quantization
artifacts. Which would mean the star-system data would likely have to
be stored
via some arbitrary-precision format (quad-precision would be plenty, I
think,
that's 104 bits of mantissa. Even 64 bits of mantissa would work), or
still in
DP format, but constantly repositioned so it all works in viewer-
relative
coordinates, not related to some fixed point in the system (actually
this would
apply to both -- arbitrary precision calculations are notoriously CPU-
intensive
and we need to be able to switch to fast CPU-sized math as much as
possible
and keep AP math to a minimum, which means lots of clever and tricky
heuristics.).
-->

you think the video card actually stores full double, or larger, values in
its buffers?...

most newer cards give you 32-bit floating point for most things, but nothing
more.
many older cards only give you 16 or 24 bits for the depth buffer, and one
has to make due.

now, all this is simply not precise enough to render scenes as you describe
them, in a single rendering pass. as noted, it will be probably necessary to
render to textures at multiple stages along these lines, and use different
renderers for each stage.

for example, planets in the current system could be spheres.
other solar systems and stars could be points or sprites.


now, a trick here, could be to disable depth buffering for everything far
away, allowing one to make use of smaller regions of space.


a single unified renderer as you seem to be imagining, I don't think will
actually work on modern hardware, even if you keep poly counts low enough...


the depth buffer is a killer, and it can cause issues even for plain
FPS-style renderers...


<--
This is obviously a very complicated programming problem. I'd really
be curious
as to how those old games I mentioned managed to pull off a
reasonably-
good (for their time) solution to this.
-->

don't ignore hackish assumptions and tricks.

the actual engine mechanics of most games are typically neither simple nor
elegant...

On Aug 30, 6:25*am, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
> "mike3" <mike4...@yahoo.com> wrote in message
>
> news:91b76340-7f68-4d18-a5d1-c636ecaa56c8@s9g2000prg.googlegroups.com...
> On Aug 28, 8:59 pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
>
> > "mike3" <mike4...@yahoo.com> wrote in message
>
> >news:e040c309-c410-4458-a90d-4043bd87f901@p10g2000prf.googlegroups.com....
>
> note, I will be using <-- and --> for block quoting (the annoyance from some
> people using google groups, and other people using MS usenet clients...).
>
> <--
> That's right, it doesn't need to do it "brute force", just render what
> is visible
> and to an acceptable level of resolution and toss away all the rest.
> So the
> planets, viewed far out, would have procedurally-generated surface
> texture
> based on the large-scale characteristics of the "full" heightmap
> (encoded as
> mathematical formulas, not stored, of course, as remember the concerns
> I mentioned.). Probably not just a texture map but a bump map as well
> to
> simulate varied terrain.
> -->
>
> you can generate much lower quality textures, and make use of "caching",
> where one can store, say, 64 or 256MB of stuff at each major level, and
> discarding older stuff as needed. likewise, caching approaches can also be
> applied to the use of texture maps.
>
> now, if the each planetary surface is, say, a 512x256 or 1024x512 texture,
> this should be acceptable to retain a planet-wide height image in reasonable
> quality.
>
> with a radius of say, 1000km, and a 1024x512 texture, each pixel will be
> about 6.14km at the equator (sphere mapping, it will majorly compress at the
> poles), or much more linearly if using hemisphere mapping (although the
> faces would expand to about 8.68km near the borders, however hemisphere
> mapping leaves a certain amount of the texture unused, namely around 58.257
> ktexel, or about 21.46% of the image area).
>
> for what all may go in the video card, be sure to keep mind of video
> memory...
> absent texture compression, 1024x512 textures would require about 2MB each
> (the onboard DXTn and friends usually reduce this down to about 256kB each).
> of course, keep in note that texture compression also somewhat hurts
> precision (this can matter a good amount in many cases...).
>

This is right. Although as you do the close approach (although still
hundreds of km
away from the surface), where the planet now starts to make a curved
"horizon" around
you, you need to render the bit right under your ship with a higher-
detail texture.
Once you get to the surface, of course, then you can just use
conventional texturing
techniques for the near stuff.

> <--
> The simplest algorithm I thought of was one where the poly resolution
> falls
> off by some amount according to distance out from the camera: so if
> you are
> high above the planetary surface, polygons may be many kms across. If
> you are hugging the terrain you'd polys only a few m or less across in
> the
> closest parts, and getting lower the further out, with distant
> mountains and
> stuff rendered using only a few hundred polygons max, and very distant
> stuff
> vague with only a few tens or less. I.e. have one single unified
> renderer that
> just renders at variable levels of detail, determined by the camera
> position
> and quality settings.
> -->
>
> potentially, but the problem then is keeping the generation consistent, and
> dealing with depth precission issues.
>
> <--
> I'm sure it would not be too difficult to do with a flat sphere, but
> you need to
> procedurally generate and regenerate this geometry as you move... how
> do
> you do that quick? Is there some way to buffer the already-generated
> geometry,
> so that as you move it can be reused, saving regeneration time to many
> fewer
> vertices?
> -->
>
> you could buffer, or you could only generate the geometry at fixed LODs (in
> this case, probably log-scaled, such as log^e or log^10).
>
> IMO, it is probably better though to make use of intermediate numerical
> buffers, and cache this. possibly, if really needed, there maps could usea
> deterministic algo and simply store the RNG seeds, or similar (some storage
> is needed in any case, as I don't think it will be practical to have a fully
> scalable deterministic RNG sysyem).
>

Hmm. That might work.

Of crouse I'm still stumped as to how to make the spherical-topology,
variable-
resolution terrain calculation algorithm... The sphere's surface has
no edges,
and that's what makes it so tricky.

> <--
> The problem with _star systems_ though is, of course, running out of
> math
> precision. Vertices will lose resolution due to the huge displacement
> terms.
> Although at double-precision we can go to 4 x 10^15 m before error
> becomes
> larger than 1m, the furthest planets in a star system may be at like
> 10^13 m
> or beyond. This is enough to start getting (somewhat) visible
> quantization
> artifacts. Which would mean the star-system data would likely have to
> be stored
> via some arbitrary-precision format (quad-precision would be plenty, I
> think,
> that's 104 bits of mantissa. Even 64 bits of mantissa would work), or
> still in
> DP format, but constantly repositioned so it all works in viewer-
> relative
> coordinates, not related to some fixed point in the system (actually
> this would
> apply to both -- arbitrary precision calculations are notoriously CPU-
> intensive
> and we need to be able to switch to fast CPU-sized math as much as
> possible
> and keep AP math to a minimum, which means lots of clever and tricky
> heuristics.).
> -->
>
> you think the video card actually stores full double, or larger, values in
> its buffers?...
>
> most newer cards give you 32-bit floating point for most things, but nothing
> more.
> many older cards only give you 16 or 24 bits for the depth buffer, and one
> has to make due.
>

So then you need some sort of heuristic, like multilayering (e.g.
render the far
stuff at smaller scales that will fit in the 32-bit floats, sort of
akin to a miniature
model in movie production, then composite on top of this the near
stuff), or
something like that, or do some calculations on the CPU to prepare the
scene
for feeding to the graphics card to render, although that might slow
it down too
much.

> now, all this is simply not precise enough to render scenes as you describe
> them, in a single rendering pass. as noted, it will be probably necessaryto
> render to textures at multiple stages along these lines, and use different
> renderers for each stage.
>
> for example, planets in the current system could be spheres.
> other solar systems and stars could be points or sprites.
>
> now, a trick here, could be to disable depth buffering for everything far
> away, allowing one to make use of smaller regions of space.
>
> a single unified renderer as you seem to be imagining, I don't think will
> actually work on modern hardware, even if you keep poly counts low enough....
>
> the depth buffer is a killer, and it can cause issues even for plain
> FPS-style renderers...
>

So then what would you do there, anyway? Since we have to be able to
handle
things that are hundreds, even thousands, of kms away. (For _very_ far
distances,
where the angular size of the planet is tiny, one can approximate it
very well by a
single pixel or tiny one-color disk if it should be visible at all.)

> <--
> This is obviously a very complicated programming problem. I'd really
> be curious
> as to how those old games I mentioned managed to pull off a
> reasonably-
> good (for their time) solution to this.
> -->
>
> don't ignore hackish assumptions and tricks.
>
> the actual engine mechanics of most games are typically neither simple nor
> elegant...

I guess not. It probably takes quite a few not-so-pretty heuristics to
make it work
and to smooth out the "seams" to give as seamless an experience as
possible.
Of course, actually being able to find out what methods were used by
those games
could be very helpful indeed.

I found this on Youtube:
http://www.youtube.com/watch?v=Nps5SmEBtt4

which seems to show about what I want (although the terrain is kind of
monotonous,
and certainly it would not have the colored squares! Although the
latter seems to be
because this is just a test prototype so I'll forgive that.). Maybe I
should ask the author?

"mike3" <mike4ty4@yahoo.com> wrote in message
news:6a509b31-f186-41f0-8852-b2e0b48ed5ab@z6g2000pre.googlegroups.com...
On Aug 30, 6:25 am, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
> "mike3" <mike4...@yahoo.com> wrote in message
>
> news:91b76340-7f68-4d18-a5d1-c636ecaa56c8@s9g2000prg.googlegroups.com...
> On Aug 28, 8:59 pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
>
> > "mike3" <mike4...@yahoo.com> wrote in message
>
> >news:e040c309-c410-4458-a90d-4043bd87f901@p10g2000prf.googlegroups.com...
>
> note, I will be using <-- and --> for block quoting (the annoyance from
> some
> people using google groups, and other people using MS usenet clients...).
>
> <--
> That's right, it doesn't need to do it "brute force", just render what
> is visible
> and to an acceptable level of resolution and toss away all the rest.
> So the
> planets, viewed far out, would have procedurally-generated surface
> texture
> based on the large-scale characteristics of the "full" heightmap
> (encoded as
> mathematical formulas, not stored, of course, as remember the concerns
> I mentioned.). Probably not just a texture map but a bump map as well
> to
> simulate varied terrain.
> -->
>
> you can generate much lower quality textures, and make use of "caching",
> where one can store, say, 64 or 256MB of stuff at each major level, and
> discarding older stuff as needed. likewise, caching approaches can also be
> applied to the use of texture maps.
>
> now, if the each planetary surface is, say, a 512x256 or 1024x512 texture,
> this should be acceptable to retain a planet-wide height image in
> reasonable
> quality.
>
> with a radius of say, 1000km, and a 1024x512 texture, each pixel will be
> about 6.14km at the equator (sphere mapping, it will majorly compress at
> the
> poles), or much more linearly if using hemisphere mapping (although the
> faces would expand to about 8.68km near the borders, however hemisphere
> mapping leaves a certain amount of the texture unused, namely around
> 58.257
> ktexel, or about 21.46% of the image area).
>
> for what all may go in the video card, be sure to keep mind of video
> memory...
> absent texture compression, 1024x512 textures would require about 2MB each
> (the onboard DXTn and friends usually reduce this down to about 256kB
> each).
> of course, keep in note that texture compression also somewhat hurts
> precision (this can matter a good amount in many cases...).
>

<--
This is right. Although as you do the close approach (although still
hundreds of km
away from the surface), where the planet now starts to make a curved
"horizon" around
you, you need to render the bit right under your ship with a higher-
detail texture.
Once you get to the surface, of course, then you can just use
conventional texturing
techniques for the near stuff.
-->

these maps will be approximate, and as one gets nearer the ground, one can
either:
make more detailed maps;
switch to a different rendering style.

for example, one can take the relevant section of the texuture, and make it
bigger, and add some noise.
the geometry is then rendered from this texture...


> <--
> The simplest algorithm I thought of was one where the poly resolution
> falls
> off by some amount according to distance out from the camera: so if
> you are
> high above the planetary surface, polygons may be many kms across. If
> you are hugging the terrain you'd polys only a few m or less across in
> the
> closest parts, and getting lower the further out, with distant
> mountains and
> stuff rendered using only a few hundred polygons max, and very distant
> stuff
> vague with only a few tens or less. I.e. have one single unified
> renderer that
> just renders at variable levels of detail, determined by the camera
> position
> and quality settings.
> -->
>
> potentially, but the problem then is keeping the generation consistent,
> and
> dealing with depth precission issues.
>
> <--
> I'm sure it would not be too difficult to do with a flat sphere, but
> you need to
> procedurally generate and regenerate this geometry as you move... how
> do
> you do that quick? Is there some way to buffer the already-generated
> geometry,
> so that as you move it can be reused, saving regeneration time to many
> fewer
> vertices?
> -->
>
> you could buffer, or you could only generate the geometry at fixed LODs
> (in
> this case, probably log-scaled, such as log^e or log^10).
>
> IMO, it is probably better though to make use of intermediate numerical
> buffers, and cache this. possibly, if really needed, there maps could use
> a
> deterministic algo and simply store the RNG seeds, or similar (some
> storage
> is needed in any case, as I don't think it will be practical to have a
> fully
> scalable deterministic RNG sysyem).
>

<--
Hmm. That might work.

Of crouse I'm still stumped as to how to make the spherical-topology,
variable-
resolution terrain calculation algorithm... The sphere's surface has
no edges,
and that's what makes it so tricky.
-->

I have usually had experience generating things like this first as
heightmaps, and then building the geometry from this.

upscaling a texture is easy, and noisifying it is also not so difficult.

> <--
> The problem with _star systems_ though is, of course, running out of
> math
> precision. Vertices will lose resolution due to the huge displacement
> terms.
> Although at double-precision we can go to 4 x 10^15 m before error
> becomes
> larger than 1m, the furthest planets in a star system may be at like
> 10^13 m
> or beyond. This is enough to start getting (somewhat) visible
> quantization
> artifacts. Which would mean the star-system data would likely have to
> be stored
> via some arbitrary-precision format (quad-precision would be plenty, I
> think,
> that's 104 bits of mantissa. Even 64 bits of mantissa would work), or
> still in
> DP format, but constantly repositioned so it all works in viewer-
> relative
> coordinates, not related to some fixed point in the system (actually
> this would
> apply to both -- arbitrary precision calculations are notoriously CPU-
> intensive
> and we need to be able to switch to fast CPU-sized math as much as
> possible
> and keep AP math to a minimum, which means lots of clever and tricky
> heuristics.).
> -->
>
> you think the video card actually stores full double, or larger, values in
> its buffers?...
>
> most newer cards give you 32-bit floating point for most things, but
> nothing
> more.
> many older cards only give you 16 or 24 bits for the depth buffer, and one
> has to make due.
>

<--
So then you need some sort of heuristic, like multilayering (e.g.
render the far
stuff at smaller scales that will fit in the 32-bit floats, sort of
akin to a miniature
model in movie production, then composite on top of this the near
stuff), or
something like that, or do some calculations on the CPU to prepare the
scene
for feeding to the graphics card to render, although that might slow
it down too
much.
-->

minatures+multilayering is the basic idea.

for example, in deep space, 1 unit is something like 1 lightyear, and in the
local solarsystem, it is in AU, near a planet, it is in kilometers, and if a
near-surface renderer is added, it can be in meters.

the idea here is that each layer would be drawn independently, and then each
former layer would be included in the next as a kind of initial background
texture (or, alternatively, one can clear the depth buffer, which would
serve a similar purpose).


for example, in my engine, I use multi-pass multi-layering for various
effects as well, such as lighting and shadowing (this is its own stage,
which simply saves a texture of its output, which is later applied to the
geometry being rendered when rendering the scene).

later on, for example, effects light sun-rays/light-volumes are drawn over
the top of the scene, as well as effects like translucent surfaces and
water.


> now, all this is simply not precise enough to render scenes as you
> describe
> them, in a single rendering pass. as noted, it will be probably necessary
> to
> render to textures at multiple stages along these lines, and use different
> renderers for each stage.
>
> for example, planets in the current system could be spheres.
> other solar systems and stars could be points or sprites.
>
> now, a trick here, could be to disable depth buffering for everything far
> away, allowing one to make use of smaller regions of space.
>
> a single unified renderer as you seem to be imagining, I don't think will
> actually work on modern hardware, even if you keep poly counts low
> enough...
>
> the depth buffer is a killer, and it can cause issues even for plain
> FPS-style renderers...
>

<--
So then what would you do there, anyway? Since we have to be able to
handle
things that are hundreds, even thousands, of kms away. (For _very_ far
distances,
where the angular size of the planet is tiny, one can approximate it
very well by a
single pixel or tiny one-color disk if it should be visible at all.)
-->

as noted, multiple scales may use different units...

precision is very coarse in space, but covers a very large area, and it is
much finer near nearby objects.


> <--
> This is obviously a very complicated programming problem. I'd really
> be curious
> as to how those old games I mentioned managed to pull off a
> reasonably-
> good (for their time) solution to this.
> -->
>
> don't ignore hackish assumptions and tricks.
>
> the actual engine mechanics of most games are typically neither simple nor
> elegant...

<--
I guess not. It probably takes quite a few not-so-pretty heuristics to
make it work
and to smooth out the "seams" to give as seamless an experience as
possible.
Of course, actually being able to find out what methods were used by
those games
could be very helpful indeed.

I found this on Youtube:
http://www.youtube.com/watch?v=Nps5SmEBtt4

which seems to show about what I want (although the terrain is kind of
monotonous,
and certainly it would not have the colored squares! Although the
latter seems to be
because this is just a test prototype so I'll forgive that.). Maybe I
should ask the author?
-->


yes, may be a good idea.

as can be noted, my main expertise is much smaller simulations, like those
in a human-scale 3D world...

mike3 wrote:

>>> I was trying to figure out a method to solve the following problem.
>>> I wanted to build a program, like a game (although not with any
>>> objective), where you could explore a whole virtual "galaxy" of
>>> planets and stars in a star ship. But the thing is that I want it so

> The problem with _star systems_ though is, of course, running out of
> math
> precision. Vertices will lose resolution due to the huge displacement
> terms.
> Although at double-precision we can go to 4 x 10^15 m before error
> becomes
> larger than 1m, the furthest planets in a star system may be at like
> 10^13 m
> or beyond. This is enough to start getting (somewhat) visible
> quantization
> artifacts. Which would mean the star-system data would likely have to
> be stored
> via some arbitrary-precision format (quad-precision would be plenty, I
> think,

I think 64-bit floats will be plenty. In a galaxy 100000 light years
(10^18)km across, with an origin in the centre say, you can specify a
star's position to 10 or 100km resolution. That's not bad, given that
a star might be millions of km across.

Then you store positions within each star-system relative to the
centre of the star, already giving you resolution better than 1m. And
then perhaps relative to the centre of each planet (now you can
specify things to the nearest micron).

When you work out the maths, the result only needs to be accurate to
the nearest pixel (or sub-pixel) on your screen.

Your star-data may also have to be procedurely generated as well as
the planets, as there might be 10^11 stars in your galaxy (although
being your own galaxy, you can choose a rather sparse one compared
with ours).

This way you might as well put a few extra galaxies floating around,
while you're about it.

You might want to look at Celestia, if you haven't already done so,
for a couple more ideas.

--
Bartc

On Aug 30, 10:46*pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
<snip>

Thanks for your response, but I'm still hung up on how to do the
spherical
heightmap calculations. You can't calculate the entire heightmap
(remember
that it would take like 10^21 elements as I mentioned), so you have to
be able
to calculate a piece of it, and that must cover the sphere like a
"patch". The
problem though is the nature of the sphere itself: the generator must
not
distort too much near the poles and it must _not_ have seams. You do
not
want there to be a big seam running from the north to south poles
whereby
a mountain is abruptly sheared off and the ocean begins or something
like
that, where whole continents just _end_ suddenly... Also you want
continuity
over the poles too, again with minimum possible distortion.

"mike3" <mike4ty4@yahoo.com> wrote in message
news:0e997e1a-33f2-4e39-a5cd-69f01d9b3a4e@w39g2000prb.googlegroups.com...
On Aug 30, 10:46 pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
<snip>

<--
Thanks for your response, but I'm still hung up on how to do the
spherical
heightmap calculations. You can't calculate the entire heightmap
(remember
that it would take like 10^21 elements as I mentioned), so you have to
be able
to calculate a piece of it, and that must cover the sphere like a
"patch". The
problem though is the nature of the sphere itself: the generator must
not
distort too much near the poles and it must _not_ have seams. You do
not
want there to be a big seam running from the north to south poles
whereby
a mountain is abruptly sheared off and the ocean begins or something
like
that, where whole continents just _end_ suddenly... Also you want
continuity
over the poles too, again with minimum possible distortion.
-->


the main important thing is the planetwide heightmap, but this can be
low-density.
as I mentioned before, a 512x256 hemisphere map should be sufficient.

now, one generates the heightmap for each side, and then does a special
blend across the borders (the usual approach I am fammiliar with is to use
several levels of RNGs at different levels of detail, and then to seriously
blur the results).

an alternative approach is to do the calculations themselves in spherical
space (rather than a cartesian space projected onto a sphere).


now, for subsets, as noted, one cuts out part of this image, and uses
special tricks to wrap it around the border if needed. then it is upscaled,
and more noise is added, which could be done recursively until the desired
level of detail is reached.

planet-scale, starting at a particular coord, one can find a 256x256 image
representing that side of the sphere (basically, a tweaky set of
calculations to "project" the 512x256 sphere map to the 256x256 hemisphere
map for that particular location).

at this point, the calculations can pretend they are operating on a
rectangular region, only that it is rendered as a curved surface.


of course, there may well be better ways to do all this, I am no expert on
this particular style of rendering myself.


or such...