Terrain started, and quadtree vs. block based LOD.

I put pathfinding on hold because when implementing a hexagonal coordinate based path finding algorithm, I realized that there would be various difficulties with dealing with constructs imposed on the world such as the terrain grid or quadtree and any other space partitioning systems.

So to know whether it’s really worth it to use hexagonal path finding, I decided to delay it until I have some other space partitioning data structures in place.

Most of today was spent on class work, in particular I made progress on the SMT solver due on Monday.

I did find a few hours today and yesterday to begin writing the terrain engine.

I’ve built a terrain in XNA before, however where I previously used quadtrees, this time I will use a grid based block partitioning scheme (more on this later).

The reasons for partitioning the terrain into fixed size blocks rather than a quadtree are:

  • Simpler to texture terrain as all blocks are always the same size.
  • Simpler to calculate lighting as the grid will match the geographic grid registration which I intend to use to partition scene lights.
  • Closer to circular level of detail degradation around the camera, as blocks are a fixed size.

Block based subdivision. Every block is the same size. Four green center blocks represent the highest level of detail chunks, and concentric rings of progressively lower level of detail chunks extend toward the outside of the diagram.

For example, all blocks might represent a 16×16 unit size of terrain (therefore, each block would represent 256 height points on the terrain). The inner most blocks in this case would then use 16×16 triangles and take up 16×16 units of space. The next blue ring would use 8×8 blocks but still take up 16×16 units of space. The next red ring would use 4×4 blocks, but still take up 16×16 units of space, and so on.


Quad tree subdivision. The smallest green block represents the camera position, where the level of detail is highest. Blocks get larger and larger further from the camera, but use the same number of triangles, and therefore present a lower level of detail.

In the quadtree implementation, all blocks are the same size. The inner most green block would be a 16×16 grid, representing 256 height points. The next blue blocks surrounding it would also be 16×16 grids, but these blocks would each take up four times as much space (32×32 units large, but still using 256 triangles). The next teal blocks would be 64×64 large, but still use the same 16×16 triangle grid.

Using fixed size blocks means more draw calls, but I will use hardware instancing, so really there will only be one draw call per level of detail.

The biggest drawback is that there are many more blocks that the CPU must examine (cull/light/texture) compared to a quadtree.


This is a quad tree terrain I wrote over a year ago. Notice the display of the block subdivisions, and their varying sizes.


Here are two chunks after today's beginnings on the new terrain engine.

More class work tomorrow, but after this assignment, I’ll have lots of time to finish up the terrain engine.



This entry was posted in Coding, DBP2011, XNA and tagged , , . Bookmark the permalink.

2 Responses to Terrain started, and quadtree vs. block based LOD.

  1. Pingback: The CPU vs GPU XBOX360 speed disparity. | Olhovsky

  2. Pingback: Quadtree vs multiple resolution grids for terrain rendering | Question and Answer

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>