Getting quadtrees up and running!
Well it’s been a while since there was a quality update, hopefully this will really be it. Quadtrees have been my main focus these days and we’re going to get them running come hell or high water. The first step in getting our quadtrees running is to figure out just how many we are going to need. This is actually a bit easier then it seems (at least in my opinion). At first I was trying to think of a proper algorithm to subdivide the space down to the most efficient level, after my brain started to hurt I decided to go the easier route (pick a number and hope it works).
I went with splitting the terrain all the way down to a 16 x 16 grid for some reason to start. I think a lot of it had to do with the fact that MCNKs happen to be in a 16 x 16 fashion and I thought for some reason that the placement information for models was on a MCNK by MCNK basis (it isn’t if you forgot).
Now just how will the quad trees work? Well we start out with the entire ADT being the top of the tree. Now let’s look at Redridge for an example (my favorite zone to test in):
Now I covered quadtrees in a previous entry, but hopefully this will help enlighten things a bit. The top picture will be our first set of quadtrees that effectively divides the ADT into 4 chunks. Previously if we wanted to check if our character would hit anything we would test it against every single triangle in the scene. This was a complete waste of processing power which normally I wouldn’t care too much about, but it was so bad it would make your mother’s accountant cry (and we both know how much he sucks with a computer).
Using quadtrees the thought process goes like this:
First determine which quad we are in. This is extremely easy as it’s simply finding a point within a rectangle. Now let’s assume we’re in Quad 1 for example. Because we know we are in Quad 1 it’s safe to assume that we do not need to test against any data in Quad’s 2, 3, or 4. We can just ignore them.
After we determine the large quad we are in, we then go ahead and look at the children of that quad (it will have 4) and we see which of those four we are in. We again know that we can ignore the other three.
We repeat this until we hit a quad without children, and then we only test against geometry that is also present in that quadtree.
Now if we are to assume that all of our geometry was equally distributed across the scene (that is to say that there was an equal amount of triangles in every little 1/265th quad) we could also safely assume test would take 1/256th of the time. That means if it took an hour before, it would now just take roughly 15 seconds! Of course that is not exact, but should give you an idea of the benefit of quadtrees (which will later be octrees I think but I’m not there yet).
Now the basic idea is pretty simple, and here’s how we’re going to do it (pseudocode for now, still writing the actual code but I wanted to get a quality update out ASAP).
First is the quadtree class. This is going to be a rather simple class, containing two vectors that represent the tree. The picture on the left shows this with the yellow and blue dot. This class will also happen to contain an array of 4 other quad trees that will be the children (picture on the right).
That pretty much takes care of the entire structure needed to define the actual quadtree, but we still need to link our data to an each tree. To do this we are going to define the starter tree in the ADT class. It’s a simple enough task to get the minimum and maximum vectors for the quadtree when we create our ADT as we always know the X,Y position of it in the 64 x 64 grid as well as it’s width and height (both are constant).
Now subdividing is simple enough, we are just going to divide down until we’re at 16×16. I.e.
1 -> 4 -> 16 -> 64 -> 256
Now the next thing we need is a link to each M2 and WMO within our quad. So the quadtree class is going to have a list that contains a reference to each M2 and WMO that is used by that quad.
The final thing that is needed is the terrain data used by that quad. Doing a 16 x 16 setup makes this easy enough as when we process a MCNK we will simply put that data over into the proper quadtree and call it a day.
Well I hope this was at least semi-helpful to those struggling with quadtrees and if nothing else it should serve as a good post that progress is being made (just slowly these days).
If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.
Comments
Hey,
sorry for this annoying one, but I think I’ve found a small typo in your code:
throw new Exception(”File does not exist: ” + fileName + filePath);
at WMOManager.cs, Line 108.
I’ve been following your work for some time and all I have to say is: Great job so far! 
That’s not a quad-tree, that’s a uniform grid only that you constructed it by subdivisioning.
Go find me on IRC and i’ll explain quadtrees to you. What’s it going to be used for anyway?
@Junior: What I understand of a quadtree is this:
http://e-studioz.de/fooliage/quadtree.jpg
The only “magic” thing is that you stop at a certain layer on some specific conditions. In my case, it stops when there are no obstacles (the red stuff) are within the quad.
Eichi: Try out the latest SVN, it’s most likely fixed there as I removed a lot of the throws.
Junior: If you follow the blog from start to finish you’ll see it’s just an outline of what I learn as I go. I am very careful to make sure I do not claim to be anything close to an expert on anything I post.
That said it is indeed a quadtree even if it’s not what is generally used. Read through the blog posts and you’ll see it’s being put in for collision testing to not waste time on polygons that aren’t anywhere near where the collision test is taking place.
Yeah sure, a quadtree can be used for that, but so can a uniform grid.
Only split cells that needs to be split, like Eichi shows. If there are more than in a cell, then split it, otherwise don’t. Then it’ll look like what eichi shows, and not like a uniform grid.
Most excellent
As always, keep it up ^-^