Deciding what to render

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

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.