Completely new node class

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

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

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

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

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)

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

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.