ddQuadtrees and Collision Detection in OpenGL – Part 2 – Making it Work

In the last post I detailed a rough outline for a quadtree data structure and a simple OpenGL program to test that it works. To quickly recap, a quadtree is a way to partition space, usually in two dimensions. Each node in the tree represents a region and a list of objects contained in that space. As you add more objects to this space, it breaks down into 4 smaller children, giving more precise boundaries. A very common use for this is in collision detection which is the program I will be creating below. The user can move a small square around the window, and when it touches a point the user places, the square becomes red. It’s pretty basic but demonstrates the basics of collision detection with quadtrees.
Picking up in the QuadTree header file, I add in the line

, as I’ll be using a set to return all the points later on. Next, in the Point2D struct, a binary less than operator is needed to actually use Point2D’s in a set. Since ordering two dimensional points doesn’t really make sense, I just compare the x-coordinate like so:

In this basic example, the “player” is represented by a square. So, to test if the player is within the boundary of a node in the quadtree, we need a rectangle intersection test, defined below in the Rect2D struct.

You’ll note that the y-axis test might be a bit different than you’d normally see – that’s because OpenGL has opposite the opposite y-axis in other APIs / languages. Interestingly, it does makes more sense in a real-world coordinate sense. With the additional struct functions out of the way, the last thing needed in the QuadTree header file is a function deceleration for what will actually get the points that the player might intersect.

In the QuadTree source file, the actual definition of the getIntersections method is pretty short and sweet. If the player intersects the region of a node, either check the 4 children of a node or add the points of a node if the node is a leaf. This function uses a set to return the points. While it can’t happen with points, should objects be in multiple tree leaves, they would be added more than once to the ultimate collection of points. Not much can be done to combat that then to simply delete any duplicates before the collection is used for more precise collision detection. I use a set because at a certain threshold they actually get rid of duplicates faster than a vector. While a more robust approach might be to use vectors for small amounts of objects and sets for large, we can get away with just picking one or the other. The method definition is below:

Finally, the entirety of the new QuadTreeTest source file is below, with a few modifications to code from the previous post. The user
can place blue points with the left mouse button. The user can also control a green box with the 4 arrow keys. If the player collides with a point, the color changes to red. Purple lines go from the player to all points that are considered possible collisions as well as the command line displaying how many possible collisions there are. Right clicking deletes the tree and player. The code is decently condensed to get to the main point of checking collisions. For example, the movement code is extremely basic and should not be used if you actually want to handle top-down movement. The entire source code is below:


This entry was posted on and is filed under blog, Programming Blog. You can follow any responses to this entry through the RSS 2.0 feed. you can leave your thoughts, or trackback from your own site.