Programming Assignment 1 - Hierarchical Radiosity ================================================= Submission date: May 4, 2004. The goal of this exercise is to implement a Hierarchical Radiosity algorithm. 1) You should start by carefully reading the description of the Hierarchical Radiosity (HR) algorithm (Ch. 7.4 in the Cohen & Wallace book), to make sure that you understand it well. 2) To aid you in the implementation, I am providing you with most of the necessary code. You will need to implement a few key routines (specified below). Thus, having understood the algorithm, the next step will be to understand what the code I am giving to you does, so you can use it correctly. Unfortunately, the code is only sparsely documented, so feel free to ask me about things you don't understand there. Of course, you are are also free to write your own code from scratch, if you prefer. 3) The code can be found under ~danix/public/pgr2004/ex1 It should compile quietly under Debian (Libranet) Linux, as installed and maintained by our system group). The file MyRad.cpp lists the functions that you should implement (feel free to split your implementation over several files, you'll only need to modify the Makefile accordingly). in order to minimize your disk usage, you should only copy the files Makefile, main.cpp, MyRad.cpp to you working directory, and create symbolic links to /cs/staff/teach/danix/public/pgr2004/ex1/guilib /cs/staff/teach/danix/public/pgr2004/ex1/danixlib and /cs/staff/teach/danix/public/pgr2004/ex1/radlib This way, if I fix a bug in one of my libraries, the next time you build your program, it will be with the up-to-date versions of the libraries. 4) You'll need to implement the following routines (the exact names and prototypes can be found in MyRad.cpp): * creation of initial links between pairs of surfaces * refinement of links until they satisfy a given threshold: implement and experiment with at least F and BF refinement. * Solve linear system represented by the links connecting nodes in the hierarchies to each other: implement and experiment with both Jacobi and Gauss-Seidel iterations. * Implement at least two oracle functions, which determine whether a link should be refined (corresponding to F and BF refinement). * Experiment with strategies for deciding which end of the link to subdivide, once it has been decided to refine it. * Implement the Gather and PushPull operations (you'll need them for solving the linear system). 5) Input file format: very simple. A regular ASCII file. Lines beginning with a "%" are comments. First come material definitions, such as "light 0 0 0 50 50 50" "red 0.8 0.1 0.1 0 0 0" The first line defines a material called "light" which has reflectivities (0,0,0), that is, reflects nothing, and emissivities (50,50,50). The second line defines a material called "red" which has reflectivities (0.8,0.1,0.1), and emissivities (0,0,0). Following the material definitions, come the scene polygons. These lines look something like: "4 10 0 10 0 0 10 0 10 10 10 10 10 red", which means that the polygon has 4 vertices, whose 3D world coordinates follow, followed by the name of the material. Triangles and convex quadrilaterals should work fine, no guarantees regarding polygons with more (>= 5) vertices. You have several "*.dat" scene files under /cs/staff/danix/public/pgr2004/ex1/scenes. Before trying anything complicated, make sure your program works on a simple scene, such as ybox/ybox.dat 6) School solution: you may want to try running /cs/staff/danix/public/pgr2004/ex1/school-sol -d scenes/ybox.dat Important code and useful routines: =================================== The most important code has to do with link refinement and solving the system, that is exactly the stuff that you should implement. These routines used to reside in radlib/hlink.cpp and radlib/hnode.cpp, and there are still a few important routines remaining there. In addition you should be aware at least of the following routines in other files: anvis.cpp: Real hsrFormFactor(const Point3d& p, Surface* s, const Polygon3d& src, Surface* ss, const Llist& blockers) // Returns the form factor from point p on surface s to the visible // parts of polygon src, using analytical hidden surface removal. // Obviously, p is assumed to lie on s. It is also assumed that // p is in front of src, and that src is not split by s. hlink.cpp: Boolean faceEachOther(const Hnode& p1, const Hnode& p2) // Return TRUE is there is a vertex of p1 in front of p2 // AND a vertex of p2 in front of p1. Much of the stuff in visinfo.cpp and visibility.cpp is also important. There are routines for computing visibility in various ways. For maximum efficiency, the routines which use blocker lists should be used. Important classes: ================== Model (radlib/model.h) contains a list of the top-level patches (i.e., input polygons) in the scene. It also stores the bounding box hierarchy used to accellerate various operations (ray-polygon intersections, etc.) You can get the number of patches, retrieve a handle to each patch, inquire and set the solution method (Jacobi or GaussSeidel), and other parameters, such as the maximum number of iterations. For this class, you need to implement the methods InitializeLinks, RefineLinks, and SolveSystem. Hpatch (radlib/hierarchy.h) is a class representing a top-level patch. Most importantly it contains the root of the hierarchy for that patch. Its most important member functions for your purposes are: Refine, Gather, and Update (which initiates a PushPull for the hierarchy rooted at this patch). It's derived from a Patch (radlib/patch.h), so some functionality that you might need from Hpatch will be available to you via public methods of the Patch class. In SolveSystem you'll want to use Hpatch::Gather() and Hpatch::Update(). Hnode (radlib/hierarchy.h) is a class representing the nodes in the hierarchy. This object contains a list of links, its children, area, radiosity, and some other information which should not be of interest to you for your purposes. Important member functions include: isLeaf, Children, Right, Left, Radiosity, Rho, Area, normal. For this class you'll need to implement the methods Gather() and PushPull(). Hlink (radlib/hlink.h) is a class representing a link between two Hnodes. Links are not symmetrical - they distinguish between the source and the receiver in each interaction. Hlink is derived from LinkError (defined in the same file), which contains the information necessary to estimate the error associated with each interaction between two Hnodes. It's also derived from VisInfo (radlib/visinfo.h) which is a class that computes and represents the visibility conditions between the two ends of a link. You'll need to implement the predicate Hlink::shouldRefine() and the refinement of a link Hlink::Refine(). In order to do this you'll also need to implement the two LinkError methods listed in MyRad.cpp Other usefull stuff: * Radiosities and reflectances are instances of Spectrum, which supports many different operations (danixlib/include/color.h), such as addition, multiplication by a scalar, coordinate-wise multiplication of two Spectrums, taking the brightness of a Spectrum, etc. * Polygon3d (danixlib/include/polygon3d.h) also has a lot of useful functionality: you can get the polygon's plane equation, compute the polygon's area, test relationship between a polygon and a plane, split/clip a polygon with a plane, and compute the analytical point-to-polygon form factor.