Description
BOUNDING VOLUME HIERARCHY 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… 3 CSCI 1933 PROJECT 5 OBJECTIVE 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. 4 CSCI 1933 PROJECT 5 1. AXIS-ALIGNED BOUNDING BOX 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. 5 CSCI 1933 PROJECT 5 3. SPLITTING THE STACK 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. 6 CSCI 1933 PROJECT 5 5. HONORS 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