Yet another galaxy

Quad isn't the best?

2010-11-11T11:42:00.001+02:00

While reading some articles over the internet I am deeply starting to thing, that the quad-based LoD algorithm wasn't the best idea. I think so mainly because using such technique on a rather flat surfaces I still will have a lot of unneeded detail.

To demonstrate what I mean, I have found some pictures on the internet.

The picture to the left illustrates something like a hill near the flat ground. The hill itself is more "extruded" from the surface, and it needs more vertexes to represent all it's slopes and caves. It's more logical to add extra detail to the hills, and do not extra detail where the area is completely flat. This is the algorithm I need to implement if I want more complex terrain look more natural. This algorithm is called Optimally Adapted Meshes (OAM).

Unlike previous picture, this one exactly represents the technique I use at the moment. It can be seen with naked eyes that there are way more vertexes used on the areas, where you actually do not need them.

The OAM algorithm, or it's implementation to visualize terrains in realtime (Real-time Optimally Adapted Meshes, or ROAM) uses a height map to determine for each vertex it's error value - the heights around it so see if the area around it is flat or it needs more detail. Based on error value it determines where the extra detail should be added and where it's ok to leave the same amount of vertexes at the moment.

I also need to think in parallel the scaling problem, and implement it inside.

Links

Roam info & papers: 1, 2, 3, 4

Glitches

2010-11-11T09:42:00.001+02:00

I have realized, that something needs to be changed in my code. I did some tests trying to see how program responses to big numbers. I have created a planet with the size exact to Earth's, and tried to fly here and there to see the performance, and then I ran to some unpleasant glitches.

This is taken from the stationary orbit at 1100 km from the surface of the virtual Earth. Strange thing that this artifacts not always appears (maybe I should call them UFO? :) ). It seems that this happens when some other processes run in background and use CPU resources a lot. I haven't tested it on other computers, maybe it's hardware specific.

I also noticed, that memory allocation and garbage collection isn't quite good, because the project constantly drains memory while runs. The problem is in LoD code, definitely.

Scales again

2010-10-29T12:51:00.000+03:00

I've been thinking a lot about scales recently, once again, and those thoughts driving me nuts slowly.

Space is a very very very large thing. Our planet is about 6'300 km in radius, that is 12'600 km in diameter, and that is 12'600'000 meters, 8 digits. Assuming one world unit in the close distance is 1 meter of the planet, I have only 100 more sized object to be able to handle in close distance. So if I will be crazy enough to fly close to the sun (so that is should be rendered in real scale), I would have an float overflow because the radius of the sun is abou 110 times bigger, that the Earth's radius. We can ask why do we need such big numbers to store if we are 10 meters from the surface? Well, even if the part of a surface if 10 meters from you, you still have to take in mind that the center point of an asteroidal body is way far away from you and it is needed to make a proper curvature of a planet. To solve this somehow I have only 3 options in my mind:

Store vertex coordinates in doubles and apply exponential space transformations before converting them to floats.
Store vertex coordinates in doubles and cull vertexes that are very far away.
Make up something else.

And in my opinion, the only reasonable option is the last one..

There are couple of planetary engine demos around the web, I wonder how they solve this problem.

When to split & when to combine

2010-09-02T19:49:00.000+03:00

Today I have almost finished my LoD algorithm. For now I just use simple "divide to 4" technique, and later I will probably use some other, more efficient one, like true ROAM, but for now it's ok.

In the heart of it lies one big question - when to split node to add more detail, and when to combine 4 nodes to one, so to remove unneeded detail. My first thoughts were to make some kind of table with the dependency of distance to node to necessary LoD level, but it was rejected soon because of planet sizes, which varies a lot. For example, using this approach my big planets will be less detailed, rather than small ones because of node's size - it will be bigger for big planets.. like the side of a big cube is bigger that the side of a small one.

Then I tried to calculate the ratio between the distance to node and node's size, and this gave a better result.

The idea is simple. First I calculate the factor (F) which equals to distance to node (actually the it's the distance to closest vertex of a node) divided by node's size. Then I analyze this like so:

If F is less than some number (Kmin), which means that camera is close to node, then extra detail should be added (the node should be split on 4 smaller nodes). Of course here the check should be added if the detail level is at it's maximum.
If F i greater than some number (Kmax), which means, that camera is far enough from the node, then extra detail should be removed. And of course here the check should be added if the detail level is at it's minimum.
And finally, if F is between Kmin and Kmax - do nothing.

Something like this. In this picture I have chosen Kmin to be 2, and Kmax to be 3, but it's obvious, that this is the place to experiment.

This logic needs to be integrated in the procedure that scans all the quadtree, and decides if the leaf should just be rendered, or divided/combined.

Deciding what to render

2010-08-31T13:58:00.000+03:00

For the last two days I was thinking about my quadtree of nodes. Quadtree-based structure is used to store terrain nodes at different level of detail, based on the camera distance to them - more closely is the camera, then more detailed should be terrain. I will later write some text about my quadtree implementation, but for now I want to be detailed in explaining the scheme, which is essential to selecting the quadtree nodes, that needs to be rendered.

The quadtree consists of 2 core elements - node(s) and leaf(s). As I mentoned before, if a node have no child node(s), then this node is a leaf, and it should be rendered (if visible, but for now I do not make any checks on visibility). Each node may be only in two states: a leaf, or a node with 4 children (in that case such node is called a branch). This is the basics of quadtrees.

So, the core problem is to decide what quadtree elements needs to be rendered. This means that there should be some kind of procedure, that runs via quadtree's nodes, and decides what to render and what to not.

Lets assume we have a quadtree like this. This quadtree have 3 "level of detail" levels (LoD levels, to be more shortly), and a lot of branches and leaves. Green circles are leaves, and brown ones are branches. Despite the visibility factor it's logical, that every leaf should be rendered, so that we could see the final terrain.

No matter how deep is the quadtree, the procedure, that finds all leaves in the quadtree so to render them later should scan all the quadtree's levels, and choose only those nodes, that are leaves. It should start from the very top of the quadtree, see if this node has any children. If it has, then "descent" down by one level until it finds the leaf. After the leaf is found it should "ascend" up to check other branches by going down. It should repeat this steps until all elements of quadtree are examined. It is clear, that if we have a rather big quadtree, it will take a lot of time to scan all its elements. Assuming that in this procedure we do not check for leaf's visibility, then yes, it will take some time to scan all the quadtree. Later on, when visibility check will be performed, the amount of nodes, that needs to be checked will decrease a lot. It can be easily understood if we assume that on the picture above, the third node from the left if no visible - then there's no need to scan its children.

Without visibility checks, the block scheme of such procedure can be the following.

Each node have the levelCheck variable, that is by default equals to 0 and is used to store in quadtree the child node number that has been scanned already. If it is equal to 4, that means that on this level we have scanned all children, so we should go up a level. And the lines "this.levelCheck=0" is used to reset the counter after all children of current node are scanned, so that next time when we will need to scan the quadtree, all nodes have this number reset back to zero.

Texture coordinates

2010-08-30T12:33:00.000+03:00

Last two days I was trying to figure out what are texture coordinates. It's name sounds pretty obvious, but in real code it was confusing for me what exactly are texture coordinates and texture buffer, and how they should be properly defined.

I have found a nice picture, that have everything to understand once and for all what they are.

According to OpenGL documentation each texture must have like 2Nx2N for better memory allocation and computation. Each object's vertex should be “bound” to some point on the texture so that when the texture is applied to the object, the graphics card will know how to “wrap” an object with a texture. To do it properly, the corresponding position of each vertex on a 2d texture should be defined. This is called texture coordinates, and they should be defined as [0;1] numbers.

For example, if we have a 3x3 square mesh, that consists from 9 vertices with any dimensions in 3d (lets say 10 by 10), the scheme of defining texture coordinates (and texture buffer lately) should be like this (texture coordinates are always 2d and in range of [0;1] for each vertex):

Black text represent 3d vertex coordinates, and red text - 2d texture coordinates.

Wierd things

2010-03-10T09:19:00.003+02:00

Last night at about 1 a.m. I was trying to put some tests to reveal the difference in calculating floats and doubles. The idea was simple - fix a time when the test stars, put in a loop for 1 million times some equations like multiplying and finding a square root of the number, and then fix the end time so do subtract it from the start time.

In first test floats were used. The number like 123456.78 was multiplied, divided, square rooted and etc. for fixed amount of iterations. And then, using doubles (big numbers from previous post) the same type of test was performed.

I was shocked that rather small float numbers had a higher results than doubles!

This is truly the result that let me think more closely to use doubles instead of floats without any doubts regarding performance.

Matter of scale

2010-03-09T16:05:00.001+02:00

Yesterday I was thinking more closely about numbers to understand the scales of the star system(s), and ways to deal with them.

I started from understanding how far is the distance from our Sun to the last planet. According to Wikipedia, the Neptune is about 30 AU (astronomical units. 1AU = 149’597’871 kilometers, or 92’960’000 miles). Objects of Kuiper belt, or so called trans-Neptunian objects, may be placed at the distance not far from 55 AU in their average radius, and it consists mostly from small objects, like asteroid belt. The biggest body of Kuiper belt is Eris, which has 97 AU in aphelion and 37 AU in perihelion. Beyond Kuiper belt lies The Oort cloud - a hypothesized spherical cloud of comets which may lie roughly 50’000 AU, or nearly a light-year, from the Sun. Oort cloud consists from asteroids, space dust and comets.

So, for the star like our Sun (G2 star), which has a mass of 1.9+E30kg. the distance from its center to the farthest object could be around 1’000 AU, or about 1.49+E11km. A thousand AU came from the idea that if I want to make project close to reality, I may close my eyes on every and very far object in the star system, but, never the less, make enough space to model some really far objects. My guess is that this number can easily be divided even 10 times, and it will be more than enough, and later I will use the number of 100 AU for the stars like our Sun.

But! According to this nice article, O-class stars may have mass from 15 to 90 times more, than the mass of the Sun. Taking in account the dependency of gravity force from objects mass by Newton’s law, such big stars will have the same about of gravitational force at the distance of square root of mass. So, if the mass is 90 times bigger, then the distance will be a bit more less than 10 times.

With all that in mind, I need to be able to operate with the distances of 1’000 AU for a single star.

According to Wikipedia, almost half of the stars in our galaxy are systems of two stars, or binary star systems, where 2 stars floats around their center of mass. It is written there that some binary systems may have more suitable conditions for planet formation, rather than single stars may have.

But let’s fantasize a bit and assume that even star systems with 3 or 4 stars may have a condition to form planets (stable or not), and to be able to make and fly around such star system I will need, let’s say the double space I have calculated.

So, 2’000 AU will be enough for any condition and any star in my virtual galaxy. And it is equal to 299’195’742’000 km, in every direction from the star system center. That is a HUGE space. By the way, if I move with the speed of light (which is equal to 299’792 km/sec.) I will need about 693 days, or almost 2 years to travel from the center of star system to its boundaries. But why should I worry? I have a hyperspace drive, haven’t I? :)

If I want to have a precision of 1 meter in my project, I will need to be able to operate with the numbers from -2.99+E14 to +2.99+E14, which can perfectly be held by double precision floating points. But dealing with doubles every time with every object may significally decrease the performance.

I came up with idea of so called local space and global space to, probably, solve performance issues I might have, if I use doubles everywhere. The idea is to render/calculate everything using global scale units when player’s cam isn’t near any global object of star system (global units have a precision of, let’s say 10000 km), and switch to local (coordinates), when player’s cam enters some certain region near any global space object, for example planet. If we assume that each space body has its global coordinates, then local space would be bounded and centered to the current position of the body.

Switching back and forth from global to local coordinates should probably spare some CPU power and give me necessary precision.

I should post some more thoughts on this idea later.

Core object scheme and hierarchy

2010-03-08T16:07:00.002+02:00

Today I was thinking more closely to the overall object hierarchy of the entire project. As well as the bodies in our solar system “attached” to theirs “parent” bodies (like the moon is a “child” of our Earth, it goes around the Earth, and Earth goes around the Sun), and all the space bodies goes around the Sun, my structure tries to stay closer the same hierarchy.

The scheme of object hierarchy can be seen below. Of course, I believe I will modify it in time due to some new ideas, but the core idea should look that way.

Basically almost every entity on this scheme has a name of “factory”, and it’s pretty self-explanatory. Each this entity handles the generation of the named object in the space, stores it’s parameters and handles some object routines.

For example, PlanetFactory is responsible for generating the planet body with all the stuff, that planet consists of, like surface (that’s been generated by PlanetSurfaceFactory), water (PlanetWaterFactory) or whatever liquid the planet may have, sky (PlanetSkyFactory), and maybe some more later (RiverFactory, CityFactory, etc.). Therefore PlanetFactory is a child to PlanetarySystemFactory – class, that is responsible for processing all the bodies, including the planet itself, that orbits around, let’s say, the center of mass of the planet – Planet itself, planet moons, celestial bodies like Saturn rings, asteroids, debris… If we go higher, there is a SolarSystemFactory, and, as you can guess already, stores and processes all space bodies of the star system, including the star itself, planets, asteroids and asteroid belts, comets and all others.

The scheme looks good and logical for me, and I will definitely try to follow it. Next step will be to define common variables and procedures for each node of the scheme.

Long-awaited update

2010-03-08T09:54:00.003+02:00

It’s been a while since I have posted the last message. A lot of thing have changed and a lot of has been redone. It’s a pity that it is now 4th rework on the simple node tree flow, but because I find it essential to the whole project, I think it’s best to find the right solution first, and then continue to make other things.

I have now switched back to Java Monkey Engine due to simplicity of coding from all my platforms that I work on every day. The experience with Ogre3d engine in that area wasn’t very good from the perspective of switching the development platform each day due to the fact that in my work time, I like to put the work away and return to the project, if I have some ideas I want to try. And in that time I work under windows. And at home I have my beautiful iMac with MacOS X in it, of course. Switching back to jME took away the problem of reconfiguring the project settings for each platform each time I put the code written form windows to mac, and vice versa. I know that it’s solvable and my lack of knowledge in that area gives me pain, but for now, it’s better for me to stay with jME to avoid them. Anyway, if you understand the problem completely (and for now, understanding the routines to handle trees for planet surface rendering is the problem), it isn’t very hard to switch to another engine in future.

At the moment I have completely decided what scheme is better for my needs of creating and handling the planet surface, and it’s ROAM. I do not remember whether I posted the link to the ROAM PDF paper or not, but I will do it now anyway. So, here’s the link.

Why ROAM is good? Well, the best way to see it is to define how I want the planet surface to be born and handled. I have found the following scheme the best:

1. Using complex procedural algorithms generate a planetary map (the vision of what the planet will look like with all the coasts, mountains, valleys, etc.) that later can be modified to add crates, rivers, cliffs, and many more.
2. Using the same algorithm make a height map.
3. Make a spherical planet body and apply map to it.
4. Using altitude as the parameter, adjust the height of the planet mesh, and add extra geometry when we approach closer to surface. This means that form space you will see a bump mapped sphere, and as you get closer to surface, the surface will slowly and smoothly change to reveal all the “heights”.

For that scheme I find ROAM is a perfect choice. Later on I will post some updates on the node and tree routines.

Completely new node class

2009-10-08T22:21:00.001+03:00

During my last days I've been working on implementing new class for my nodes. I took the conception to make each node not 1 by 1 quad, by n by n quads. This means that each my node will consist of n by n nodes (16x16 for example). After the node is being created, it's transformed into a single mesh and then attacked to the scene. The reason for this was bad frame-per-second rate with previous ways, because each frame each my quad was send to GPU for rendering. And because of huge amount of quads, each sending slowed down the performance. GPU can handle complex meshes very fast if sent to GPU as a single mesh.

So, by rewriting the Node class to this new approach, the fps increased more than 100 times! Now that's what I call HUGE :)

Also, the node's constructor allows now to set the desired amount of quads on each side. The example below shows the cube with 128x128 quads on each cube's face.

And with this one it's still over 150 frames per second.

Performance issues and ideas

2009-10-05T13:11:00.001+03:00

It seems that performance issues are caused by too many nodes attached to the rootNode manager (the one that handles all the geometry in the scene). I have asked the question on the forum (here) and there were some solutions gives, as well as some ideas made up in my mind.

Well, one way is to somehow lower the amount of custom nodes while saving the same amount of triangles in the scene. This can be done if I make a constant mesh from many nodes and only then add it to the rootNode manager. So I have to write a procedure that reads all my quad tree, finds all nodes that have to be rendered (i.e. are leafs) that are on the same level in my quad tree, and makes a constant mesh (TriMesh to be exact by java terminology) and then pass it to the scene manager. And that for all tree levels.

Another thought that I had was related with splitting. In my previous posts I mentioned that according to my splitting procedure the quad splits on 4 smaller. In future the idea was to split the quad if camera is close o it so to add more detail. But splitting only one segment each time won't add much of a nice picture, imho. I think I need to "split" quads for some segment bigger than one parent quad. That way adding more detail won't be so.. mmm... so rude, maybe. Somehow like this.

So, I believe I will focus on this.

Cube to Sphere mapping

2009-10-01T23:35:00.001+03:00

Whooah...

Finaly I have managed to solve all bugs in my way to map coordinates for each vertex from primary cube so to form a sphere. Planet should look like a sphere, because nobody likes cubic planets :)

The main equations for transforming coordinates of cube to spherical are the following:

For that reasons I have made a "final" class called c_MyMath for keeping all the future equation functions there.

After a bit of testing I found that it was a bad idea to store spherical coordinates of each vertex multiplied by planetary scale factor (the radius of the planet) because while doing scaling in the node's constructor, I needed to take care of scaling during quad splitting also. I thought it's whatever if I do the scaling for each vertex in the constructor and in splitting procedure, and doing it just before the prerender function, which finds all the quads that should be rendered and then apply the scaling. I understand that it's better to handle everything from the start (not just before th rendering) but for now I have decided to leave things as they were.

Now the protoplanet looks finally like a sphere!

Dealing with quadtrees 3: The cube

2009-10-01T14:58:00.001+03:00

I have managed to draw a single quad on the window, and make split algorithm work properly. It uses parent quad's vertex coordinates and makes new 4 quads and calculates it's vertex coordinates.

I have realized, that basically I need to store in some king of list all my new quads, and later on I also need to make a procedure (at the moment just a simple one) that looks through this lists and makes another one, containing only leafs - quads that have to be rendered.

To store it I used LinkedList class. Very useful.

I needed to make a cube that consist of 6 quads (6 sides) at the moment of creation. The problem was that by defining a tree (as it should be defined) it should have only one root (quad, or whatever). By making 6 sides, I basically create 6 roots, and I was afraid that I will have problems later when I will have to make some kind of procedure, that will need to find all quads that have to be rendered, because that way I will need to call it for each 6 primary quads. The solution with lists I found quite resultive.

This is the result of primary cube. At the moment I have decided to draw cube so that it's center is in the (0;0;0) and vertexes have by default +1 or -1 in all direction, multiplied by scale factor. Later on I will have to add algorithm that could place the cube in any coordinates so that all formulas stay consistant and correct. But that will be later.

This is the result of splitting the primary cube 3 times (6 sides times 4^3 gives 384 quads).

By now it works, by the framerate results doesn't make me happy, because by dividing the prime cube 5 times gives only 20 fps and that's odd.

Next step will be finding out why the hell fps are so small :) and second make a sphere out of cube - it should be spherical planet, not cube like :)

Dealing with quadtrees 2: Points

2009-09-29T13:49:00.002+03:00

Continuing to make a quadtree. Next step is to understand the splitting process. In simple words I need to split a parent quad on to 4 small quads with proper coordinate for each vertex of the each child node.

To understand the concept I took a very simple quad with coordinates from (0;0;0) to (1;1;0). It’s frame and numbers are black on the screenshot. It has 4 points:

Point 0 - (0;0;0)
Point 1 - (0;1;0)
Point 2 - (1;0;0)
Point 3 - (1;1;0)

Because of jME tutorial page about drawing vertices has algorithm, that draws quad as two triangles exactly the same way (coordinates) as I mentioned before (like from point 0 to 3) I used the same concept here, but later on I have found that in my draft papers I have mistaken X coordinate with Y. That gave me that the point #1 is under point #0, but in reality it point #1 should be from the right from point #0. But actualy that was not important :)

As it can be seen from the picture, 4 child quads are numbered the same way as points (although as I have mentioned that isn't quite right, but it works), and in the table I wrote coordinates for each point of each child just as I see them.

Dealing with quadtrees (part 1)

2009-09-28T15:03:00.004+03:00

My next step is to deal with quadtrees.

Best described in wiki, quadtree is:

..is a tree data structure in which each internal node has up to four children.

Imagine a plane, that consist of a single quad only. If we move closer to it, and we want to add more detail, we need to split this quad (so it become more detailed). Because the name of quad speaks for itself, the best way to split is to divide it on 4 small quads. If we had one quad before (called root or branch), these 4 new quads will become children (or leafs) of the previous quad.

So, the quadtree is a structure, that holds "branches" and their leafs (if any). Each branch may have 4 children or 0 children. The node that do not have any children called "leaf", all others are branches. Quite simple, isn't it? You may look also here for more detailed explanation if you haven't caught something.

So my first task is to "make" a test quad and then try to split it. The main problem that anyone can encounter is to calculate all points of child nodes correctly.

Blog to keep everything in mind

2009-09-25T12:34:00.003+03:00

This is the first post.

I have opened this blog for 2 reasons.

First, somebody might find the info described here useful.

Second, I will try to put this information for myself to remember everything and practice a bit in writing useful information.

Now, it's time to tell what exactly I am planning to achieve. Some may remember the game called Elite. One feature of this game that truly inspired me is that it has almost unlimited space to fly to. The universe has number of stars almost the same as real universe, and all of them are created using pseudo random sequence of data.

Next feature is that player have an ability to fly not only in space, but fly close to planet surface, and even land on it. The way how space body can be seen with quite a rich resolution when you approach closer to it is done, using techniques called "Level of Detail", or LOD. LOD algorithms add on the fly more detail to the mesh as you approach closer to it. You might want to read more about it on the wiki.

So, my start point is to make an LOD algorithm. As to the engine itself, I have chosen jME engine so to be really cross-platform, but maybe I will have to switch to OGRE rendering engine in the future. There are several issues why maybe I will have to switch to OGRE, and main of them are that OGRE have already some nice addons to handle water and sky. We'll see.