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

This entry was posted by Rey Jexter Bumalay, on Saturday, March 03, 2007. You can leave your response.