Fractal Generation System

[pincushionman]

don't forget fractals for asteroid belts/planetary ring systems too.

-pincushionman

[mkruer]

About the only thing which would be needed to be generated would be planet surfaces.

yup, I did say that.

Anyway... Why even bother generating fractal solar systems if we already have a good database full of nasa data, and it would pose problems with the dynamic universe, whats the point of generating every single object with fractals when they can be done just as good without them?

<Sarcasm> Really Nasa Has a Database of full systems outside the Sol System? Wow I did not know that. </Sarcasm>

Anyway Yes I do agree that you should have overriding control for any system, however I think you will find out after about the 10th one (providing they have some good detail) you will that it is much simpler to generate the systems and add the extras then creating each one by hand. The question remains when to use fractals and when not to. For hundreds of systems you are probably looking at several MB worth of system information, however if that number becomes thousands then it is much easier to design an algorithm to generate the systems, this would also reduce the size of the system from 10’s of MB to maybe about 1/2 a MB.

[hurleybird]

Ok, I guess it would be good for saving a bit of space, as well as for mods which need to have a whole bunch of systems made.

For VS though, we already have more systems than we know what to do with.

IMO having the galaxy generated with fractals would be nice, but not neccesary. If it would require a big effort, i think it would be better spent elsewhere.

I admit that I dont know how hard it would be to implement though. Whomever programs the fractal system (I'm gussing Ace, or Hellcat) will probably be the one to decide if its worth the effort or not.

[richard]

I also have code that generates realistic solar systems. It populates them with star(s), planets, moons (and planetary rings) and asteroid belts. The planets (which may be gas giants, of course) have properties like radius, density, atmosphere type, hydrographics (hence albedo), mean temperature, etc.

This time it's Python code, but it's really fast. It could be called whenever someone wanted info about a particular system.

Again, I'd be happy to provide this code. It's from another project I had that has been "in development" on and off (mostly off ;) for about 6 years.

The point here - like the fractal planet surface generator - is that you can then define the system using a single number - the seed for your "random" number generator. My previous comment noted that you'd want to use a consistent number generator across all platforms - note that Python's whrandom module is.

[richard]

I'd like to attach the files I've been talking about (planet surface generator and system generator), but I don't appear to have permission. How do I get it? :)

[hurleybird]

I've never been able to attach files either... Though if there small you could email them to me or someone else to host.

[richard]

Buggerit, I'll put them on my host :)

Solar System generator (to give it a whirl, just invoke with "python systemgen.py" and it'll generate and give a basic info dump):
http://www.mechanicalcat.net/tech/nsc/systemgen.py

Planet surface generation (just compile the C file and link in the OpenGL libs):
http://www.mechanicalcat.net/tech/nsc/planet.tgz

[mkruer]

Something is up with the posting of attacments. I will look into it. however the PM should work

[Darkmage]

I'm going to have to endorse the fractal terrain engine, it's the best terrain idea propsed so far, shouldn't be too hard to implement either, just needs to be optimized to draw fast. eg, at large distances, make it draw really low res planet spheres not the insane ones it does now, also make it cull parts of the planet the player can't see.

[richard]

Yeah, I think the key will be to get a reasonable LOD routine working that only generates fractal detail where it's needed (ie. for a planet there's going to be more than half a sphere that's not needed, and then as the POV moves around the sphere you can incrementally add new bits).

One of the biggest problems with fractally-generated landscapes has been the quite obvious midpoint lines that run through them like perfectly straight valleys or ridges. The method I've described and made available avoids that problem in the specific case of spherical generation. When you get closer down and need to generate a specific patch of land, you can revert to the midpoint subdivision technique to create minor deviations in the land. Perlin noise methods can also produce interesting results, but the method I described can produce more realistic (ie. seeming to have been tectonically generated) results.

Oh! I'd forgotten about Andras Balogh's efforts which are pretty spectacular: http://web.interware.hu/bandi/ranger.html

The most important point is that the landscape be reproducible. Use a single seed value for each planet's surface, and a reliable number generator. Then you can place non-landscape features, like cities and landing pads and be confident that they'll appear on (and not in or above :) the landscape as you intended. Probably stating the bleeding obvious here though :)

[hurleybird]

wow, that is a very awesome demo. And the source code is available too!

The LOD's are simply amazing and this screen says it all http://web.interware.hu/bandi/screenshots/scr00002.jpg

[richard]

I've only been able to look at the video, since I can't compile the demo (only have Linux)

But I do highly recommend viewing the videos, BTW. It's pretty awesome to realise that in the video you're scooting over the ground and there's a mountain in the distance that's not an environment-mapped mountain image, but a bit of rendered terrain!

[mkruer]

Very nice, I think I have run across this before, or at least the theory of the generation. However this is only part of the equations. There is still a lot more that needs to be done. The first thing is the creation of the master terrain fractal. The one thing I have noticed about almost all terrain fractal so far is that they look like fractals, particularly when it comes to the coastlines or rivers. In all honest fairness, I have not seen any of Richard’s images yet (sorry don’t feeling like installing linux, i.e. can you post some images) Also in my opinion the world tend to be too fragmented. See ( http://www.bottlenose.demon.co.uk/share ... /index.htm ). this seems to be the norm, even on the program I have been using PlanetGen ( http://www.gharat.net/ ) I think this might stem from the fact they all seem to use equally spaced key nodes (if that’s the right term) The best generate planet I have seen is from Raieh Fractal Planet ( http://raieh.homelinux.net/cgi-bin/raie ... actalWorld ) however it also takes forever to render.

What also kills the fractal performance is the number of iterations. So this should be kept to a minimum.

[richard]

Here ya go then.

[image removed, see later post]

[mkruer]

Well that’s a lot better then I expected (I don’t usually set other people stands too high i.e. this way I can never be disappointed LOL) Don’t worry about the color map. That is the easiest thing to fix. You may want to contact Lance Gharat at www.gharat.net , and see if he will release his code. The way it looks like he does it is though vectors, and not though pixel ramping. I also think this is why his generates so fast. The only problem is that there is no or little color ramping between levels. The other thing I noticed that I think will add more realistic textures is apply biome’s to the planet. What this does is tell the color scheme to shift the color so it no longer dependant on height, but rather how the environment effects the terrain.

A good example might be a mountain. One side of the mountain is close to the sea, and the wind blows the wet air onto the mountain, so for vegetation that side will be a lot greener then the side facing away.

If you look at the planet earth, you will see the almost all the eastern coastlines are green and the western coastlines tend to be more desert. This is because the trade winds along the equator are moving west (note the polar trade winds head east)

I am hoping stuff like this could easily be calculated. If so then you are one up on everyone’s planet fractals


Also glad to see that you can post now.

[richard]

PlanetGen and FractalWorld are both produce pretty amazing results.

The code I've got is not fast - generating that sphere of 130k facets takes about 30 seconds for 1000 iterations on my Athlon 2k. Haven't really seriously looked into whether it could be made faster though. Probably can't though - there's not a lot to the actual generation:

Code: Select all

      /* Form the new surface */
      for (i=0;i<niter;i++) {

         /* Choose a random normal */
         n.x = drand48() - 0.5;
         n.y = drand48() - 0.5;
         n.z = drand48() - 0.5;
         Normalise(&n);
         offset = drand48() - 0.5;

         /* Purturb the points dependng on which side they are on */
         for (j=0;j<nface;j++) {
            for (k=0;k<3;k++) {
               if (whichmethod == 1) {
                  p = faces[j].p[k];
               } else {
                  p.x = faces[j].p[k].x - offset * n.x;
                  p.y = faces[j].p[k].y - offset * n.y;
                  p.z = faces[j].p[k].z - offset * n.z;
               }
               if (DotProduct(n,p) > 0)
                  faces[j].c[k]++;
               else
                  faces[j].c[k]--;
            }
         }
      }

:)

The Biome stuff you pointed at looks quite interesting. My system generation code I pointed at previously will determine the atmosphere and mean temperature of planets, which can then be used with the elevation map to figure all the biome stuff out.

This is all much easier when the planet isn't in the "wet" zone of a system, or it's too small to have a viable atmosphere, so the biome calcs only have to be done for a very few planets.

I don't have windows available to me at the moment, so I'll have to take your word that PlanetGen is fast :) It does appear to produce good results though. Perhaps he'd be willing to contribute his code to this project?

[mkruer]

Ok cool but I want to take it back to formula. This is where I am going to need a lot of help, so correct me if I am wrong ok?

The most important thing of a planet is the height mapping. This in effect will determine everything else, so this needs to be spot on before we really can continue.

Form my observations of the fractal systems it looks like most of the planets that are generated from a static grid pattern of points. This is why if you generate the object using one iteration it looks like a honeycomb more hen anything else. This is the first thing that needs to be corrected. The idea is to replace that grid with pattern with fractal web. If you look at fractal that generate planets you will see what I am getting at. This mean that the points on the surface tend to bunch together, and also create broad spaces. Its these bunching of points that will determine continents, so if you are really clever you should be able to specify how many bunches you want, and go from there.

Let me know if this makes sense of if I am totally off the planet (pun intended)

[richard]

Ah, what you're talking about is having more that one dimension of deviation when performing the grid manipulation. Typical fractally-generated landscapes take a quadrialateral on the X-Z axis and subdivide it into four new quads down the midlines. The new points generated are deviated on the Y axis by some amount. The problem with this approach is that you tend to have straight valleys or ridges along the lines generated initial couple of iterations.

A way around this is to deviate the new points along all three axes. This can reduce the occurance of the straight landmarks, and in some cases more pronounced features (pointier hills, flatter plains).

I actually toyed with this many years ago and produced some interesting results. Something I never got around to doing was to perform a filtering operation after each iteration, to smooth out the really nasty pointy bits that look nothing like landscape (mostly I didn't do it then because I didn't learn about filters until a couple of semesters later ;)

The spherical routine I posted works on a sphere of triangles that are deviated away from the center of the sphere. Because the line of deviation is different every time, you don't get those obvious straight landmarks.

I think that perhaps some sort of hybrid approach might be the best - the spherical generation for the coarse granularity, down to a resolution that a more typical subdivision generator can use as a base, or the perlin noise generator like that use in the ranger code.

Various levels of cheating may be used - for a given planet, we can pre-generate a texture based on the coarse planetary-scale information. A friend suggested that we could just generate a projection once every now and then and billboard it - a player's view of a planet isn't going to change that often. Or a combination of both, and progressively generate new strips of texture as a player moves around a planet.

The ranger code definitely looks interesting, but I get the feeling that a) it takes a long time to load up the structures for a given landscape and b) a more coarse level of detail would be needed that sits between the out-of-atmosphere scale view and the down-near-the-ground view.

Switching between those two is easy, BTW. Just insert a "re-entry" animation that plays while the new LOD information is being compiled :)

[I'd meant to mention that in another thread about the pause after jumping when the new local scene is generated - why not generate it *during* the jump, while some simple graphic animates, then clear it. That's what Freelancer would be doing with its jumping.]

Nuff brain dump for now :)

I've attached some samples (sorry, they're not the best examples) of, in clockwise order:

1. Regular grid, smaller deviations (note somewhat regular features)
2. Irregular grid, small deviations
3. Regular grid, larger deviations (slight straight ridge noticeable through middle to top)
4. Irregular grid, large deviations (note quite jagged, un-landscape-like features)

Anyway, again, this code is available if anyone wants it (Makefile / main.c for Linux only, sorry). I *think* I wrote this code - it's not attributed anywhere, and I have written this stuff many times over the last 10 years or so :)

[edited to clean up BBCode and add image / description]

[mkruer]

I think we are on the same page, mostly, but what I was referring to was everything stars from equal distant points. What I am saying is there should be another layer. Instead of trying to explain its might be easier to show.

The first image is the standard grid that all terrains seem to start off from
The second image is the one with pre grid tweaking. The idea is that you are trying to force the fractals to be more dominant in that area. This is why I said that you should be able to specify continents just by saying the grid need to have density changes. The problem with this is that for mapping to a sphere, you could end up with abnormally flat surfaces.

The final one (sorry I didn’t feel like doing it all) is to pre-subdivide existing triangle into smaller parts, and sub divide those new triangles. What you are doing is creating density variations in the grid before you start the fractal process. What this mean is that when the fractal start they will automatically bunch at these key points. In addition you should be able to get away with a few less iteration to boot.

Now this is where it becomes really cool for me and just about everyone else. Because the continents are being generated from the variations in density, it would not be do difficult for say myself to create a custom planet by asking use this mesh to start from.

[richard]

I suppose that these results could be achieved by just skipping the subdivision of some facets earlier on during iteration. It could result in some very strange results though; very flat triangles in the terrain.

Another problem that I can see with this approach is that you can no longer use a tristrip to render the planet. That'd be a performance hit :(

[Guest]

"Just insert a "re-entry" animation that plays while the new LOD information is being compiled "

Well one thing we want to avoid is not keeping the planet entry seemless .

[richard]

If there's one thing that entering atmosphere is, it's not seamless :)

My point here is that there's certain places in the game where there's an opportunity to take over the display with some simple animation while some other complex calculation / pre-buffering goes on in the background. Jumps (hitting the 'a' key) and entering an atmosphere are a couple of those. I've not done the other kind of inter-system jump, but I assume there'd be the same opportunity there.

[richard]

Another terrain LOD engine. I can't try it, windows only. Seems to make heavy use of shader programs (DX type, not OGL) though.

http://gameprog.it/hosted/typhoon/

Food for thought, anyway.

[hurleybird]

Too bad its not opensource though

[richard]

Probably worth contacting the author to find out whether they'd be interested in contributing to VS.