Here is my updated quadtree. This is only a very simple quadtree with the following features:

• Able to create terrain from height map data.
• Able to define the subdivision levels you want.
• Able to draw only parts of the quadtree you want.
• Only uses lines to draw the tree since adding texture will complicate things.
  

[Entire part of the quadtree is drawn]



[Certain part of the quadtree is drawn]

You can download the full source code here.


Next up, i'll add the following things on my quadtree:

• Textured terrain
• Be able to easily add models
• Be able to cull the parts of the quadtree that is visible to the camera.

Labels: quadtree, xna

I have finished my quadtree that is able to draw a terrain from an input height map image. Unfortunately, i still cannot post the code because I'm still working to associate each of the terrain's vertices to a the subdivision region on the the quadtree.

here's the latest screenshot:



[quadtree with terrain from height map data]


the terrain(green) and the quadtree(white) is the same in terms of width and height although they look as if the terrain is bigger than the quadtree. I think this is just normal because objects that are closer to the camera is projected bigger.

Labels: xna quadtree height heightmap

After programming for a couple of hours, i have finished my prototype of a simple quadtree. Here are some questions noobs like me asked when i was trying to understand what a quadtree is like:

1. What is a quadtree ?

- it is a space partitioning system/concept where a plane is divided into 4 parts. Each of this parts can in turn be divided into 4 parts and so on.

Depending on the subdivision level you want.


2. Where do i use it?

- its main purpose is to speed up the process when rendering or calculating something.

like for example when you are checking if your object collided with your terrain. instead of checking all the vertices of your terrain if it collided with your object which is obviously a very costly task, you can first check if your object in on a certain part of your plane before your check if it collided with your terrain's vertices.

another use of a quadtree is when rendering your scene. imagine rendering the entire scene even if your camera is not looking at it. obviously it is too costly to do that especially if you have a very large map. rendering only what your camera sees will greatly improve your game's performance. this technique is also called as "frustum culling".

you can also use your quadtree to easily place your object on your scene.


[helpful links]

http://www.gamedev.net/reference/articles/article1303.asp

http://en.wikipedia.org/wiki/Quadtree


Here are some screenshots of my quadtree:



[Quadtree with 1 subdivision level]



[Quadtree with 2 subdivision levels]



[Quadtree with 5 subdivision levels]


In a couple of days, I'll be posting my code since right now I only have finished the part where the tree is subdivided into different parts.

Labels: quadtree, xna

I started yet another programming blog. This blog will cover topics about game development using XNA Framework and 3D Game Development. This blog site will basically be used to document my progress and the things I'm learning.

I wont be covering some elementary stuffs like drawing triangles, primitives, lines and etc instead I'll start with a more intermediate stuffs such as octree, terrain, lighting, shadow mapping and things that are mostly used in the scene.

If you want to study the very basic of xna and 3d programming, you can use the following sites:

Riemers XNA Tutorial

Basics of 3D

3D Math