photonmapper

Program Features
(0) Basic ray tracing, ambient, diffuse, specular, shadow, transparency.
(1) Reflection
(2) Refraction. My program is able to do refraction for continuous changing media without air/vacuum interfering in between. For example, a big ball contains a small ball and both of them are translucent and of different index of refraction.
(3) Geometry includes sphere, general shaped polygon (even including concave polygon) and plane.
(4) Objects include fully opaque, translucent, fully translucent, fully reflective and partially reflective.
(5) Super sampling, soft shadow.
(6) Recursive ray trace controlled by arbitrary user-defined level threshold and ray-traveled distance threshold.
(7) Texture map and bump map on sphere object, checkerboard pattern on infinite plane.
(8) Program runs very faster. A 1200 * 900 resolution rendering is done in 15 mins.
(9) Program is able to output both PPM P6 raw format and 24-bit BMP format.
(10) Use yacc/lex parser to parse POV configuration file.
(11) I wrote my own numerical library for vector and matrix computation, employing template meta-programming and expression template techniques as well as latest features from the incoming new C++ standard.
(12) Photon mapping
(13) Caustic effect
(14) Color Bleeding

Sample Image


Photon Map


Caustic Effect

grab the code here here.

program feature

I implement all required features, including an interactive 2dtree viewer, an interactive viewer to display all phases of the algorithm, from the original data points to the final signed distance field.

Marching cubes is implemented separately. I did not use the code provided on your links, I implement it myself. I also implement a viewer to display the geometry generated by marching and that one is also fully interactive. I did not come up with GUI system, however, my programs are very easy to use and intuitive, using keyboard to interact and mouse to navigate.

The program runs very fast for the mechpart dataset, finished within only seconds. I use a trick that, in the Euclidean graph, if two nodes are not close enough, there is not need to generate a connection for them since the corresponding edge will not be in the MST anyway. This is Jon's observation but I do contribute by discussing with him. The program runs about 20s without the trick and less than 1 second with it.

assignment discription

Divide and conquer the problem into four phases as suggested:
1. Phase 1—tangent planes
Given an unorganized set of points in 3-space (point cloud), compute an estimate of a tangent plane at each point.

2. Phase 2—consistent normals
Given a set of tangent planes at each input point, Tp(xi), each consisting of:

* a neighbourhood of points defining the tangent plane's neighborhood, Nbhd(xi),
* the tangent plane origin, oi, and
* the tangent plane's orientation represented by its normal, ni,

find a consistent global orientation for each connected component of the input data.

3. Phase 3—signed distance function
Given a set of consistently oriented tangent planes at each input point, Tp(xi), each consisting of:

* a neighbourhood of points defining the tangent plane's neighborhood, Nbhd(xi),
* the tangent plane origin, oi, and
* the tangent plane's orientation represented by its normal, ni,

calculate the signed distance function f(p) at each point p situated at the vertex of a cube in a 3D cube lattice, where f(p) is defined as the signed distance between point p and its projection z onto Tp(xi): f(p) = (p - oi) ⋅ ni.

4. Phase 4—contour tracing (marching cubes)

Given the signed distance function f(p) at each point p situated at the vertex of a cube in a 3D cube lattice, where f(p) is defined as the signed distance between point p and its projection z onto Tp(xi): f(p) = (p - oi) . ni, extract the isosurface from the signed distance function (field data). This is accomplished via the marching cubes algorithm. The resulting simplical surface contains triangles oriented at the surface of the point-sampled object.

surface reconstruction

original data points


tangent plane centroids/origins


tangent plane normals (adjusted)


MST of Euclidean distance graph


Enriched Riemannian graph


MST of Riemannian graph


grid points and their associated tangent planes


signed distance field


2dtree viewer


marching cubes shading

grab the code here here.