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.

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.

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

- Make a backup copy of the existing
`heightfield.cpp`

for comparisons later. This is the**only**file you need to modify for this assignment. - Modify
`Heightfield::CanIntersect`

to always return`true`

. - Build a KD-tree structure for heightfieds (see below); this part of the code should be placed in the constructor function
`Heightfield::Heightfield`

. - 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:

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.

**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:

- Your modified
`heightfield.cpp`

; you shouldn't need to submit any other source code; - 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. - (
**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
`heightfield.cpp`

; - The net ray tracing time using your algorithm vs. using the old
`heightfield.cpp`

.

- The time to construct the tree 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.

**Grading**

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.

Copyright © 2008-2018 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

Ideas, requests, problems regarding UMass CS EdLab? Send feedback