Assignment 1: Heightfield Intersection using Simple 2D-Tree
Due: Tuesday, Feb 26 2008 at 11:59pm
For this assignment, you will improve
's support for rendering terrain in scenes like landscapes and seascapes. Terrain is often represented as an elevation map, or what we will call a heightfield
: a 2D table indicating the height of a surface above each point of a uniform grid of
resolution. In other words, a heightfield is tabulated form of a height function
stored in a 2D array. The
values are implicit and range from
has no native support for rendering directly from heightfield data. Instead, it converts a heightfield into a triangle mesh by connecting adjacent height values in the array. This approach is general but relatively inefficient; by converting to triangles we lose the ordered structure of the heightfield, which can be exploited to render more efficiently. Your assignment is to implement a kd-tree acceleration structure (in this particular case, a 2D-tree) to develop a fast intersection routine for heightfields.
Step 1: Download starter code and scene
Click the link below to download a zip file containing starting code and several
scene files and textures:
The Linux version of pbrt should build the heightfield shape plugin by default. If you're using Windows, copy the
and add the project file in the
solution. After you have built the heightfield plugin, run
, and you should see output images (
) that look like this:
(left image) is designed for debugging; use this file as you develop and test your intersection algorithm. The
heightfields (land and sea) and there are two other views of this scene:
. Finally, there are two bigger test scenes:
heightfield converted directly from a digital elevation map (DEM) downloaded online (check
). These two bigger test scenes will take a while to render, especially at very high image resolution.
Step 2: Heightfield KD-tree
and make sure you understand how the
interface works. The default
shape is non-intersectable, meaning its
function always returns false; this will force the ray tracer to call its
function at run-time to turn it into intersectable elements -- in this case, a triangle mesh. Following that,
will create a scene-wise KD-tree as the acceleration structure. This is actually pretty fast already since
uses a highly optimized KD-tree. The point of this assignment is not to compare directly with
's existing accelerator; rather, the comparison should be made with a brute force approach that does not take use of any acceleration structure.
Your task is to turn heightfield into an intersectable shape, and then create a specialized KD-tree (in particular, a 2D-tree) for accelerating ray-heightfield intersection. Although this is hard to beat
's built-in KD-tree in terms of the net ray tracing time, we do gain the benefits that our specialized heightfield KD-tree is extremely fast to build, thus the overall ray tracing time (including the tree construction times) compares favorably with existing
To get started, you need to
- Make a backup copy of the existing
heightfield.cpp for comparisons later. This is the only file you need to modify for this assignment.
Heightfield::CanIntersect to always return
- Build a KD-tree structure for heightfieds (see below); this part of the code should be placed in the constructor function
- Implement the two interface functions
Heightfield::IntersectP, which allows the renderer to intersect a ray directly with the heightfield.
The brute force way to implement intersection is by testing a ray against each triangle defined by the heightfield. This is equivalent to having no acceleration structure, thus is a bad idea. What you need to do is to build a KD-tree acceleration structure to improve the intersection speed. Note that given the structure of heightfields (which represents height values
on a uniform 2D grid
), you only need to pick, at each subdivision step, a splitting plane along the
axis. So essentially you will be building a simple 2D-tree like this:
The left image shows the heightfied rendering, and the next four images shows the first few steps of the tree construction. At each step you should pick a splitting plane in either
, depending on which dimension is the longest; this splits the volume into two halves; you then recursively build the left and right half. Note that the plane should be placed along the grid line
(in other words, a row or a column of the height field grid) to make sure that you do not end up splitting any triangle apart. Therefore all KD-tree nodes should contain whole triangles with no partial triangles. The recursion step stops when the number of triangles to subdivide falls below a threshold
, which often varies between 2-16. You can experiment with this threshold afterwards to find the sweet spot.
At each node of the KD-tree, you should at least store the following information: 1) the bounding box; 2) the position of the splitting plane, and whether it's on
; 3) a pointer to the actual triangles if this is a leaf node. Note that you are recommended to reuse
shape class defined in
to represent triangles. This will save you time of having to write your own ray-triangle intersection routine. You may need to duplicate the code if the interface does not allow direct sharing of the code.
Once the tree is built, your next step is to implement
by following the KD-tree traversal algorithm. When a ray reaches down at the leaf node, you should intersect it with all the triangles belonging to the node to find out the closest hit point.
Step 3: Interpolating Normals (691MM only)
: This step is required for 691MM students only.
: After setting the interpolated normal (
), use these lines
CoordinateSystem(Vector(dg->nn), &dg->dpdu, &dg->dpdv);
dg->dpdu *= dpdu.Length() / dg->dpdu.Length();
dg->dpdv *= dpdv.Length() / dg->dpdv.Length();
to update the tangent vectors (also update their magnitudes). Otherwise the reflection from the sea water will look incorrect. ]
After you have the basic intersection routines working, add the following additional feature:
- Perform smooth interpolation of the normals across each heightfield triangle, allowing for smooth shading results.
In order to do so, you should first estimate the per-vertex normal by averaging the normals of all its neighboring triangles. This should happen during the initialization step of heightfields. Next, when an intersection point is found, you should modify your triangle's intersection code to properly return the interpolated normal. Here are some example images of what you should see after you make the modifications:
- Make sure you understand how
pbrt handles transformations (e.g. ObjectToWorld and WorldToObject). Note that upon calling
Intersect, the ray is given in World coordinate system while your KD-tree may have been built based on Local (object space) coordinate system. In this case you need to do proper conversion and make sure to return hit point in World coordinate system.
- You should try to take use of existing
pbrt classes to reduce the amount of work you have to do. For example, bounding boxes should be defined using the
BBox class; and you can reuse the
Triangle shape class to define triangles (may require duplicating the code).
For this assignment, you should pack the following files in a single .zip file and email it to the instructor:
- Your modified
heightfield.cpp; you shouldn't need to submit any other source code;
- One rendering for each of the following 6 scene files:
saltlake.pbrt. You can submit them as either
.exr file or any other image format. Note that the last two scenes are fairly big so should be good stress tests for your algorithm.
- (691MM only) Two renderings of
landsea-0.pbrt: one with interpolated normals and one without.
- Report timings comparisons of your implemented algorithm. For all the 6 test scenes mentioned above, report:
- The time to construct the tree using your algorithm vs. using the old
- The net ray tracing time using your algorithm vs. using the old
- You should Write the timing comparisons in a
.txt file, and write a short discussion/conclusion on your findings.
The grading for this assignment is on a scale of
, based on the following criteria:
: Little or no work was done.
: Significant effort was put into the assignment, but neither the tree construction nor the intersection works fully.
: Both the tree construction and the intersection are functional, but rendering has noticeable artifacts or missing geometry, or does not work under all viewpoints.
: Rendering has no noticeable artifacts, but the performance is significantly slower than expected.
: All requirements satisfied, and the implementation compares favorably in speed with the original. For 691MM students
: normal interpolation must work correctly without artifacts to qualify for 4 points.
Note that an implementation of the brute force intersection method only qualifies for 1 point.