Description
For this project, slow functions are indicative of an incorrect implementation.
The programming exercises detailed in the following pages will both be evaluated for code style.
This will not be strict – for example, one bad indent or one subjective variable name are hardly a
problem. However, if your code seems careless or confusing, or if no significant effort was made to
document the code, then points will be deducted.
In further projects we will continue to expect a reasonable attempt at documentation and style as
detailed in this section. If you are confused about the style guide, please talk with a TA.
Note: This is a brand new project. If you notice any errors or have suggestions for improvements, please let us know.
Bounding Volume Hierarchy
A bounding volume hierarchy (BVH) is an essential tool in computer graphics. It’s used in rendering, collision detection, and much more. There are different kinds of acceleration structures,
but the one you’re required to implement is an Axis-Aligned Bounding Box (AABB) tree, with
top-down construction.
The fun thing about acceleration structures is that they make use of several fundamental techniques
in Computer Science, such as trees, recursion, queues/stacks, polymorphism, and more. This is
a good opportunity to make use of the skills and knowledge you’ve acquired in this course in a
(hopefully) fun and interesting final project.
AABB Tree
Geometric objects in space are grouped together in overlapping boxes. Boxes with one object in
them are the leaf nodes of a tree. Larger boxes that enclose smaller ones are parent nodes. The
image below (left) shows various shapes in world space being partioned into a tree (right). Although
its leaf nodes have two objects each, it illustrates the general idea.
See this Wiki page for more details.
How can we use this tree? Let’s say there was a screen open with the geometry of the above figure
and the user wants to select the circle with a mouse by clicking on it. To see if the circle was
selected, we start at the root node (A). Then, based on the coordinates of the mouse, we check
which of its children the pointer is hovering over (B). We traverse to the (B) node, traverse its
children (and so forth), until we reach a leaf and see if the click was in bounds of the shape.
Why not just loop over all of the geometry and test them directly? Consider what happens when
we have one million shapes instead of six. What about ten million? Checking if the cursor is
within the bounds of a box is a lot less expensive to compute than a 15-pointed star. Using a tree
to process the selection of the click will cull millions of these expensive point-in-geometry tests,
making the run time of your interface significantly faster.
This day and age, having to wait a few seconds to process a mouse click ends up with angry users
and 1-star app ratings. We can’t have that…
Objective
You are required to implement the primary function of building and traversing the AABB tree.
Code that generates geometry, rendering, and handling mouse input is provided. The following
files are on moodle:
• AABBTree.java: Contains the code for generating geometry and processing graphics. You
won’t have to change this file, but it might be helpful to look at and understand it.
• Bounds.java: The class for an axis-aligned bounding box. You’ll need to implement this.
• Circle.java: The class for a cicle, containing geometry-intersection tests and rendering.
You won’t have to change this.
• Node.java: The class that makes up our tree! Most of the work you will be doing is here.
• Shape.java: A base class for geometry. You won’t have to change this.
• Vec2.java: The class for points in space. You won’t have to change this.
When running the program, a window should pop up containing a bunch of circles. Once you’ve
finished your BVH implementation, clicking a circle should make it turn red. Clicking again will
make it turn back to gray. For this project, you can assume that no shapes will overlap.
If your tree traversal is correct, this should run in real time. That is, you won’t have to wait for
the object to change colors.
Hint: It’s highly recommended to test your methods with fewer geometry than the default.
In AABBTree.java there is an int max_shapes variable in main. Start by setting this to one
or two when implementing your tree for the first time.
1 Axis-Aligned Bounding Box
The first step is to implement the Axis-Aligned Bounding Box (AABB), found in Bounds.java.
Be sure to fully test your methods. Methods marked with “TODO” are for you to complete. To
get full points for this section you must implement
• boolean isOutside(double x, double y): Returns true if the point (x, y) is outside the
bounds of the box, false otherwise.
• void extend(double x, double y): Grows the box (increases max, decreases min) to enclose the point.
• void extend(Bounds b): Grows the box to enclose another box.
• double exteriorDistance(double x, double y): Distance between the AABB’s surface
and a point in space. If the point is inside the bounds, return 0.
2 Node Constructor
Node(Stack stack, int axis)
The node constructor takes a stack of shapes, a splitting plane axis, and initializes itself. The
splitting plane axis is a number (0 or 1) that describes what axis on which we will do the partitioning.
See §3 for more details.
To get full points for this section, implement the following:
• Extend the AABB to contain all shapes in the stack.
• If stack size is 1, become a leaf node.
• If stack size > 1, partition the stack using the splitStack method, increment the axis, and
create children recursively.
3 Splitting the Stack
void splitStack(Stack stack, int axis,
Stack leftStack, Stack rightStack)
The role of this method is to partition the stack into two new stacks (though not necessarily in
half). The metric we’re using to decide the partion is the spatial median. This is simply the
average centroid of all objects in the stack (for a given axis).
For example, let’s say the splitting axis was 0 (x-axis) and you had two shapes, centered at (1,2)
and (2,3). The spatial median is 1.5. And so, the former shape (1,2) goes on the left stack, and
the latter (2,3) on the right.
Do not create new shapes with the same location/radius. Make sure you are moving around the
same shape object since their references are used internally by the renderer.
To get full points for this section, you must:
• Compute the spatial median.
• Partition the stack into leftStack and rightStack based on the spatial median.
4 Shape Selection
boolean select(double x, double y, int[] counter)
On a left-click, the select method is used to traverse the tree and identify the shape whose
boundary includes the point (x,y). It returns true if an object was selected, false otherwise.
Here you will take advantage of the tree data structure to accelerate the search. That is, if the point
(x,y) is outside the bounds of the node’s AABB, the point is also outside the bounds of children
nodes, thus we can simply return false. Otherwise, continue searching down the tree.
To get full points for this section, implement the following:
• Early exiting if the point (x,y) is outside the bounds of the node.
• If on a leaf, check to see if (x,y) is physically within the bounds of the shape.
• Recursive traversal of the left and right children.
5 Honors
boolean nearest(double x, double y,
double[] currentMin, Shape[] shapeRef, int[] counter)
The nearest method is very similar to the select method from §4. Instead of selecting a shape
when the (x,y) coordinate is above it, however, nearest will select the nearest shape with respect
to the input point. It returns true if it found a shape closer to the point (x,y), false otherwise. This
happens on a right-click.
There are two more arguments to set. Note that both currentMin and shapeRef are single-element
arrays. When you’ve found a candidate nearest object, in that its exterior distance to the point
is the current minimum, set both currentMin[0] and shapeRef[0]. The former is that exterior
distance, while the latter is a reference to shape itself. Remember that exterior distance is zero if
the point is inside the shape.
The other major difference between nearest and select is that you should traverse the node that
is closer to the point (x,y) first. This is because it’s more likely to contain the actual nearest shape,
and possibly cull future traversals!
To get full points for this section, implement the following:
• Early exiting if the node’s boundary is further away than the candidate nearest shape.
• If on a leaf, check to see if the node holds a closer shape. If so, set the necessary references.
• Recursive traversal of the left and right children.
7