Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

Quad-Trees and Erratas

Sign in to follow this  


I finished coded and implementing the quad-tree data structure to handle my collision detection geometry. I figured that a quad-tree would do the trick because I see no reason to partition the geometry along the y axis. If my level geometry consists of several rooms above rooms, I don't think it will affect the framerate that much.

Basically I recursively subdivide the collision detection geometry into a 2D quad-tree, ignoring the y values. Then during a collision pass I build a 2D bounding box around my bounding ellipsoid representing the player's current position and the ellipsoid representing the players final position. I then, non-recursively, test this bounding box against the subdivided quads. Each quad that contained the player's bounding box is then passed to the collision detection routine.

It works well, but I need some larger level geometry to test it. With the partial test level I have constructed consisting of 555 triangles, an average of 11 triangles was passed to the collision routine. This was with 3 levels of recursion when building the quad-tree.

Next I will work on finishing the test level geometry in Maya and then texturing and populating the rooms with various geometry. This will give me a good testing environment to finish up the visibility culling. It should also make for some more interesting screenshots.

As far as visibility culling is concerned, I have decided that I will do a basic frustum cull on the bounding boxes of each object. I will then render all the "room" geometry. Finally, I will make a GL_ARB_occlusion_query call on each "non-room" bounding box that passed the frustum cull. If the occlusion query call returns an integer greater than my threshold, I will send the geometry down the pipe. My game will consists primarily of indoor environments so this approach should allow for fast framerates.

I also have a seperate code that allows me to run a Perlin noise filter through a mesh. I want to incorporate this vertex shader into my engine for various animated effects. The first geometry I will tweak with this shader will be flames. Torchlight will play a key role in my game and I would like for it to look nice.


On a different note, I have spent a couple of evenings last week reading Alan Watt's 3D Computer Graphics (Third Edition). This was the textbook we used in Computer Graphics CS594 at the University of Tennessee when I was a teaching assistant for the class. Since then, the professor has changed to Real-Time Rendering (2nd Edition), which I currently have on order from amazon.

In the first chapter entitled, Mathematical Fundamentals of Computer Graphics I noticed several errors.

On page 14, the last sentence on the page reads, "or the angle between two
vectors is the dot product of their normalized versions". This statement
is false. I believe what the author meant to say was "or the cosine of
the angle
between two vectors is the dot product of their normalized

On page 19, the last paragraph second sentence reads "This means that the
ray is in the half space, defined by the plane that does not contain the
polygon". This too is a false statement. I believe what the author meant
to say was "This means that the ray is in the half space, defined by the
plane that does not contain the polyhedron".

On page 24 there are two diagrams at the bottom of the page. The first
has a caption that reads "R = I + 2N cos theta". This is not true. What
the author probably meant was "R = I + 2N cos phi". This error is particularly
brutal because theta is used to describe another angle in the same diagram.

These mistakes are unfortunate, because they can lead the reader in the wrong direction. Watt doesn't do a great job of explaining the math in the first place, often leaving it to the reader to fill in the gaps. This approach might be suitable for a quick refresher for someone that is already familar with the concepts, but the errors might make this text particularly treacherous for someone learning for the first time.

There is also no errata that I could find online.
Sign in to follow this  


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!