Assignment 3

Fabian Prada

This assignament explores acceleration structures for heightfield rendering and Phong interpolation for texture shading

1) Acceleration Structure: Quadtree + Min-Max Heights

The acceleration structure implemented was a quadtree. The root of the quadtree represents the complete heightfield, and its nodes represent the four (approximately equal) subdivisions on the heightfield. This is, the root correspond to [0,nx]x[0,ny] and its subdivisions correspond to [0,nx/2]x[0,ny/2]; [0,nx/2]x[ny/2,ny];[nx/2,nx]x[0,ny]; and [nx/2,nx]x[ny/2,ny]. The tree is iteratively subdivided and its leaves are squares of the heightfield (i.e [i,i+1]x[j,j+1]).

To each node of the quadtree, I assigned the max and min height attained on the associated region. Therefore, the max and min at the root node is the max and min of the heightfield, and the max and min of a leave is the max and min from the 4 vertices of the square.

The intersection of a ray is done by the following procedure:

1. Proyect the ray to xy plane, which is the support plane for the heightfield. Call ray' to it.
2. Put the root of the quadtree in a priorityList.
3. While priorityList is not empty:
4. Call the last node of the priorityLis as currentNode.
5. Find the In and Out intersections of ray' with the region pointed by the currentNode If there is no intersection. Remove the currentNode and return to 3.
6. Find the height of ray at In and Out. If none of this heights is contained in [currentNode->min,currentNode->max], remove the currentNode and return to 3.
7. If the currentNode is not a leaf:
8. Add the subnodes of the currentNode which are intersected by ray' to the priorityList. This is done according to the order of intersection. Remove the currentNode and return to 3
9. Else:
10. The currentNode is a 1x1 square. Evaluate if ray intersect one of the two triangles in the order given by ray'. If there is intersection, return true, else remove the currentNode and return to 3
11. End If
12. End While
13. Return False

2) Phong Interpolation

1. The normal at each vertex was calculated as the equally-weighted-mean of the normal of 4 adjacent triangles. Call right,up,left and down, the vertices at the respective position of the currentVertex. The four triangles I associate to currentVertex are (currentVertex,right,up);(currentVertex,up,left);(currentVertex,left,down); and (currentVertex,down,right). The normal at currentVertex is the mean of the normals of these triangles.
2. The normal at any point of a traingle was calculated as the baricentric-weighted-mean of the normals at the vertices of the triangle.

3) Renderings: (still on debugging)

	My result with Phong Interpolation	PBRT result without Phong Interpolation
hftest
landsea-0
landsea-big
landsea-big64
Texture

4)Total Running Times (in seconds):

5)Comments

• Running times using quadtree acceleration are similar to PBRT optimized 3D BVH.
• In landscape-big, quadtree improved PBRT performance. This was because the running time to construct the quadtree is shorter than the time required to construct PBRT acceleration structure.
• In landsea-big64 (64 samples per pixel), running time of quadtree was longer than PBRT. This was because the mean time to calculate a single ray intersection is shorter in PBRT implementation than in my quadtree.
• Calculating shading geometry through Phong interpolation improves the image quality a lot. Computational cost of Phong interpolation is reduced in comparision to calculating rays intersection.