## 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