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.