Assignment 2 Discussion

Support Files

For those it might be useful for, I've created a Makefile and a Visual Studio 2005 project for lz-kdtree you can find here. The Makefile will build lz-kdtree.so, and the VS 2005 solution will build Release/lz-kdtree.dll and Debug/lz-kdtree_d.dll. I find this kind of setup useful if you want to keep lz-kdtree.cpp in a "local" directory outside the pbrt source tree (e.g., in a cvs repository without the rest of the pbrt source). Note that you'll have to add your own copy of lz-kdtree to the Source Files in the VS solution file, and you'll have to change the path in the Makefile on line 10 to point to your own copy of pbrt.

Misc Notes

Reporting Build Time (KayvonFatahalian)

The ProgressReporter class is the easiest way to time sections of your code in PBRT. For the purposes of the assignment, you will need to measure both the total time to render the scene and the time spent in the initital build process. The hope is that drastically decreasing the initial build time will help to minimize the total render time of large scenes.

Bracketing the construction of your lazy KD-Tree accelerator with timing calls to the ProgressReporter class times the build time of the KD-tree. Here's what the code would look like for the original PBRT KD-Tree accelerator.

   ProgressReporter progress(1, "Building");
   Primitive* accel = new KdTreeAccel(prims, isectCost, travCost,
                          emptyBonus, maxPrims, maxDepth);
   progress.Update();
   progress.Done();
   return accel;

Questions

Q.1 Default Killeroo Scene (DougJohnston)

Using the scenes includes in the zip file, I get the following statistics:

Geometry
    Total shapes created                                    532.2k
    Triangle Ray Intersections                              673.8k:4826.8k (13.96%)
    Triangles created                                       532.2k
Kd-Tree Accelerator
    Avg. number of primitives in leaf nodes                 3.965M:1.376M (2.88x)
    Interior kd-tree nodes made                             1.376M
    Leaf kd-tree nodes made                                 1.376M
    Maximum number of primitives in leaf node               284

which is significantly different from those in the project description.

A.1

The scene in the zip file has one more level of subdivisions for the killeroo models. That's why the numbers of tree nodes and triangle ray intersections are much higher than the numbers given in the example.

Q.2 Problems with const (LeeHendrickson)

I'm having some issues with dynamically creating new nodes in my lazy kd-tree. The crux of the issue is that both Intersect and IntersectP must be const methods (as they implement pure virtual methods from Primitive which are themselves const); however, in lazy evaluation these are also exactly the methods in which changes do need to be made to the kd-tree (at the very least either 1.) more nodes will need to be allocated, or 2.) nodes already allocated will need to have initLeaf or initInteriorNode called on them, neither of which is a const operation). Hopefully I'm missing something simple, any pointers/hints would be appreciated. (please don't tell me the answer is to make everything mutable...)

A.2

• One possible way would be to const_cast the constant-ness away, then call whatever functions you need on the object. Ugly though...(YiLangMok)
  

• If you define the tree as an array of nodes or some structure, you only need to make the tree mutable, which is not too bad? (MengYu)
  

• But then you'd have to move non-const functions such as buildNode into the node itself, since you cannot make functions mutable. As it stands, Intersect cannot call buildNode because of const restrictions. Moving the functions might work, but it seems to be more work that it's worth. (YiLangMok)
  

Well, what I ended up doing was just going the mutable route, moving as much as I could into a mutable member structure, and setting the building functions const so as to be able to be called from Intersect (even though some variables such as the number of free and alloc'ed nodes need to stay in the tree itself). The problem with const_cast'ing is having to do it on the this pointer that must also be const for all functions called from intersect, which just feels more kludgy. By using mutable members the functions themselves can stay in the top level tree and stay const. Quick and dirty, but given the framework of pbrt I don't see any good way around it. Any better suggestions are welcome. (LeeHendrickson)

• Lee your approach is the best method I can think of as well given the interfaces defined by PBRT. It's not that hacky, really. (KayvonFatahalian)

Q.3 Performance Profiling (LeeHendrickson)

Anybody have a good way of profiling pbrt on the Myths? The problem is that gprof doesn't handle profiling across shared libraries (even when compiled with -pg) and converting pbrt to use static libraries would be a pain and counter-productive. Normally I would use sprof but it's unfortunately absent on the Myths.

A.3

• I hesitate to call this an answer, however, one quick solution would be to drop the parts of the code you're particularly interested in profiling into the files linked together into the core lib, which is linked statically (KayvonFatahalian)

Q.4 Debugging with GDB (YiLangMok)

I remember somewhere (can't find it) that stated that GDB 6+ should be able to debug the .so plugins, but I haven't managed to get this to work. At best, I can get the stack trace, but not the line number that segfaults occur on. Are there any flags I need to set in the Makefile to enable this?

A.4

Silly me, just need to add -g to OPT line in the Makefile.

Q.5 Linking lz_kdtree into core

How do I link my module into the core statically? I find it really really hard to debug because GDB's support for run-time loading of libraries isn't that great.

A.5

PBRT is designed in a way such that external plugins can be easily added to the existing pbrt, without modifying the core files. It's not flexible and efficient to load all modules off-time. If you want to do it for debugging purpose, you need to look into core/dynload.cpp and core/dynload.h. The plugins are dynamically loaded in core/dynload.cpp, specifically

        #if defined(WIN32)
        HMODULE hinstLib;
        #elif defined(__APPLE__)
        NSModule hinstLib;
        #else
        void *hinstLib;
        #endif

It may involve creating additional classes to hold prototypes of the Create* functions.

Regarding to debug dynamically loaded objects, here're some tips from the authors:

Greg recommends: (1) Load up the executable and put a breakpoint in MakeShape(). Then step OVER the code that loads the DLL. Then you can put breakpoints in your code. (2) Use printf.
Matt adds: (1) Best thing to do is set a breakpoint in Scene::Render, then step into the accelerator and then into your intersection code. At that point, you should be able to set other breakpoints in your module. (2) If you want to debug your constructor, set a breakpoint in pbrtShape(), which eventually calls your constructor. (Meng)

Q.6 More const fun from a const newbie

I'm not a C++ guru and this is my first foray into const territory. As I see it, if you make builtTree have the signature: void KdTreeAccel::buildTree(...) const then, how can you call initLeaf? It says:

accelerators/lz-kdtree.cpp:240: error: no matching function for call to `KdAccelNode::initLeaf(int* const&, const int&, MailboxPrim* const&, const MemoryArena&)'
accelerators/lz-kdtree.cpp:26: note: candidates are: void KdAccelNode::initLeaf(int*, int, MailboxPrim*, MemoryArena&)

Then if I add const in front of everything, it yells at me about a ton of things, one being:

accelerators/lz-kdtree.cpp:46: error: passing `const MemoryArena' as `this' argument of `void* MemoryArena::Alloc(unsigned int)' discards qualifiers

How can I call that without changing the whole API? (PaulTarjan)

A.6

* One not-so-good way but works is to do: const_cast<KdTreeAccel *>(this)->buildTree(yadda yadda). There is also a mutable solution, although I didn't use it (and not exactly sure what to make mutable).

* What happened here is that non-const initLeaf was invoked in a const function, the compiler forced the parameters of the function to be const, so that it guaranteed initLeaf wouldn't modify any member variables. This caused the mismatching function error. One trick is to do what Lee described in A.2: define a structure to hold the non-const functions or simply move them to the tree node class, and declare the nodes mutable. (Meng)

Q.7

Do we have to keep the concept of BadRefines, or is it purely a design decision? (Ranjitha)

A. 7

BadRefines is used to prevent poorly refining a node till the maxDepth of the tree. If a split is bad, then this counter is incremented and passed to its children. If after several splittings, the badRefines reaches 3 then the node is just made a leaf and returned. So simply it ensures we dont have more than 3 badly refined nodes while traversing from the root to any leaf children.