Assignment 1: Heightfield Intersection using Simple 2D-Tree

Due: Tuesday, Feb 26 2008 at 11:59pm


For this assignment, you will improve pbrt '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 mxn resolution. In other words, a heightfield is tabulated form of a height function z(x,y) stored in a 2D array. The x and y values are implicit and range from [0,1].

pbrt 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 pbrt scene files and textures:

The Linux version of pbrt should build the heightfield shape plugin by default. If you're using Windows, copy the heightfield.vcproj file to pbrt/win32/Projects/ and add the project file in the pbrt solution. After you have built the heightfield plugin, run pbrt on scenes: hftest.pbrt and landsea-0.pbrt, and you should see output images (hftest.exr and landsea-0.exr) that look like this:


The 4x4 heightfield in hftest.pbrt (left image) is designed for debugging; use this file as you develop and test your intersection algorithm. The landsea-0.pbrt contains two 64x64 heightfields (land and sea) and there are two other views of this scene: landsea-1.pbrt and landsea-2.pbrt. Finally, there are two bigger test scenes: landsea-big.pbrt contains a 1000x1000 heightfield; and saltlake.pbrt contains a 584x588 heightfield converted directly from a digital elevation map (DEM) downloaded online (check saltlake.jpg). These two bigger test scenes will take a while to render, especially at very high image resolution.

Step 2: Heightfield KD-tree

Read through heightfield.cpp and make sure you understand how the Shape interface works. The default heightfield shape is non-intersectable, meaning its CanIntersect() function always returns false; this will force the ray tracer to call its Refine function at run-time to turn it into intersectable elements -- in this case, a triangle mesh. Following that, pbrt will create a scene-wise KD-tree as the acceleration structure. This is actually pretty fast already since pbrt uses a highly optimized KD-tree. The point of this assignment is not to compare directly with pbrt '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 pbrt '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 pbrt.

To get started, you need to

  1. Make a backup copy of the existing heightfield.cpp for comparisons later. This is the only file you need to modify for this assignment.
  2. Modify Heightfield::CanIntersect to always return true.
  3. Build a KD-tree structure for heightfieds (see below); this part of the code should be placed in the constructor function Heightfield::Heightfield.
  4. Implement the two interface functions Heightfield::Intersect and 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 z on a uniform 2D grid xy), you only need to pick, at each subdivision step, a splitting plane along the x or y axis. So essentially you will be building a simple 2D-tree like this:

hexamples.jpg hexamples.jpg hexamples.jpg hexamples.jpg hexamples.jpg

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 x or y, 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 MAXCHILDREN, 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 x or y; 3) a pointer to the actual triangles if this is a leaf node. Note that you are recommended to reuse the Triangle shape class defined in trianglemesh.cpp 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 Intersect and IntersectP 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)

Note: This step is required for 691MM students only.

[ Update : After setting the interpolated normal (dg->nn), 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:

  1. Your modified heightfield.cpp; you shouldn't need to submit any other source code;
  2. One rendering for each of the following 6 scene files: landsea-0.pbrt, landsea-1.pbrt, landsea-2.pbrt, hftexture.pbrt, landsea-big.pbrt, 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.
  3. (691MM only) Two renderings of landsea-0.pbrt: one with interpolated normals and one without.
  4. 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 heightfield.cpp;
    • The net ray tracing time using your algorithm vs. using the old heightfield.cpp.
  5. 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 0 to 4, based on the following criteria:

0: Little or no work was done.
1: Significant effort was put into the assignment, but neither the tree construction nor the intersection works fully.
2: Both the tree construction and the intersection are functional, but rendering has noticeable artifacts or missing geometry, or does not work under all viewpoints.
3: Rendering has no noticeable artifacts, but the performance is significantly slower than expected.
4: 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.

Topic revision: r8 - 2008-02-23 - RuiwanG
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback

mersin escort adana escort izmir escort gaziantep escort