LiAR isn’t a raytracer

Christer Ericson, author of Real-Time Collision Detection has written a little article on Plücker coordinates and why they are considered harmful. It’s great. I never really understood what all the fuss was about, as I could do the Plücker coord tricks as easily with basic 3D linear algebra and its triple product. So, I’m glad to see some of the big guys agree!

(via Pete Shirley’s Graphics Blog)

“LiAR is entirely Plücker free” ;)

As of 28 June 2007, Sourceforge will decommission the SVN access URLs starting with https://svn.sourceforge.net/svnroot/. They are replaced by URLs with the project names in front. For LiAR, this looks like https://liar.svn.sourceforge.net/svnroot/. The new URL scheme is part of an upgrade of the Subversion access method to improve its stability. If your local working copy uses the old URL, follow the switch instructions so that you can still access the repository after 28 June.

PS: I know LiAR has been silent for the last couple of months. There was just too many other things to take care off. However, the last couple of weeks, I’ve resumed coding on LiAR, albeit slowly, so hopefully I will be able to add some new posts in the near future.

We’ve successfully moved the LiAR home page to http://liar.bramz.net. This should allow us to upload bigger renders, and get better search engine coverage. The old URLs starting with http://liar.sourceforge.net should redirect traffic to the new site so that no links get broken.

Share and Enjoy!

If you’re planning to install Visual Studio 2005 Service Pack 1, keep this in mind:

• Make sure you have at least three gigs of free space on your C: drive. To be on the safe side, make it four gigs.
• Windows Update tries to shove this up your arse as a security update, but don’t let it. Do a manual install instead.
• Log in as Administrator. I know you already have super monkey admin powers, but do it anyway.

The aftermath?

Well, it did solve the test errors we had in the win32_vc8 build of Lass, like the fld loading corrupt data on the FPU stack. It also solved the template class member function overload ambiguity we suffered in testUtilThreadFun.

It did cause some other troubles though. Apparently SP1 screws up on default arguments in function template declarations. In lass::prim, all intersection functions are implemented in *.inl files with the function declarations being listed in the accompanying *.h file. These functions have a parameter tMin that defaults to zero. This worked/works fine on VC6, 7, 7.1 and 8 sans SP1, all GCCs I could get my hands on, but not on VC8 SP1. It still compiles the code, but at runtime, tMin contains garbage when the default value is used. Unfortunately, I was unable to reproduce the problem on a smaller scale. Anyway, the solution to this problem was to move all intersection functions to the header files so that the separate function declarations no longer exist.

While debugging another segmentation fault on linux, I was trying to run LiAR in gdb (actually KDbg). The program crashed somewhere in an allocator, but the reason why was almost impossible to see. The debugging experience was crippled because distutils compiles with full optimization -O3 by default, at least my linux box.

If I was going to debug it properly, I would have to get rid of that switch and use -O0 instead. But for some mysterious reason, distutils always used -DNDEBUG -g -O3 -Wall -Wstrict-prototypes, regardless of the --debug switch. It turns out distutils is getting these from the original Makefile used to build Python and stores them, together with the name gcc, in an attribute compiler_so of the CCompiler object. This attribute is later used to invoke the compiler.

Fortunately, in liar_build_shared_lib and liar_build_ext, we have access to the compiler object. All we have to do is, before building, to grab compiler_so, remove any -O switch and put an -O0 instead:

def force_no_optimisation(compiler):
for i in range(4):
try: compiler.compiler_so.remove("-O%s" % i)
except: pass
compiler.compiler_so.append("-O0")

class liar_build_ext(build_ext):
def build_extension(self, ext):
force_no_optimisation(self.compiler)
...

What was causing the segmentation fault? The std::vector in kernel::Intersection was requesting memory for 0 elements. The lass::util::AllocatorBinned wasn’t really prepared for that. Once identified, it was easily fixed …

When I tried to run a first render in linux, I got a segmentation fault in the photon mapper because there were no lights. Of course, this shouldn’t cause a crash (fixed by now), but why were there no lights? I was pretty sure I defined one, and a quick investigation of the scene graph confirmed this.

Before rendering is started, SceneLight instances are harvested from the scene graph by a visitor LightContextGatherer to collect all instances of SceneLight objects. It’s an acyclic visitor as described by Andrei Alexandrescu.

class LightContextGatherer:
public util::VisitorBase,
public util::Visitor,
public util::Visitor
{
void doVisit(SceneObject&);
void doVisit(SceneLight&);
};

The way it works is that if a scene object, for example a LightArea, accepts a visitor, it tries to cast the visitor to util::Visitor. If it succeeds, it will call the appropriate doVisit function. Otherwise, it tries again using its parent type, in this case SceneLight. As a result, all lights instances end up in doVisit(SceneLight&), and all other objects in doVisit(SceneObject&).

But for some reason, neither doVisit was ever called. It turned out that the dynamic_cast, used to cast the visitor to the appropriate type, always returned null, even when trying to cast to util::Visitor. Huh?

Some googling revealed that GCC 3.0 uses address comparisons to determine type equality. This obviously has a performance advantage over string comparisons, but doesn’t work quite well if left and right have a different set of typeinfo instances. This can when using dynamic linkage, and it certainly doesn’t help that Python uses dlopen to load extension modules.

Fortunately, the GCC FAQ also mentions a solution which is to link with the -E flag to add all symbols to the dynamic symbol table, and to use dlopen with the RTLD_GLOBAL flag set. For LiAR, the former means adding -Wl,-E to extra_link_args in setup.py. The latter can be done using sys.setdlopenflags. Proper try/except wrapping ensures that it is only called if appropriate. At least one linux system did not provide the dl module, but fortunately the same constants also live in DLFCN (also not always available), so that’s why the heavy nesting. The code is put at the beginning of __init__.py.

try:
try:
import dl
except:
try:
import DLFCN as dl
except:
pass
sys.setdlopenflags(dl.RTLD_NOW | dl.RTLD_GLOBAL)
except:
pass

The description of LiAR says: “‘LiAR isn’t a raytracer’ is an open source, cross platform, object-oriented and extendable ray tracer written in C++ and Python by Bram de Greve”. However, that’s not entirely true since currently, LiAR only runs on the Windows platform. It’s time to live up to the promise. To be honnest, I’ve attempted it before but I ran into troubles and I gave up. Now I want to pursue it to the end, however. And while I encounter and overcome the obstacles, I’ll try to document them.

The goal is to use Python’s distutils and write a single setup.py to build and install LiAR. So no make or autotools are allowed. The idea is that eventually, the setup.py can be used to build LiAR on Windows as well. I’ve decided against using setuptools (eggs) and SCons because distutils is already included in the standard libraries of Python. But first, I’ll be trying to get it working on linux alone, what is already good for quite some challenges.

First, a recap of how LiAR is built. It consists of different (extension) modules organized in a star topology. The center module is called the kernel and provides general definitions (Spectrum, Intersection, …) and abstract classes (SceneObject, Shader, Texture, …) that are used as vessels and ports by which the concrete modules (scenery, shaders, textures) must communicate. Each concrete module only depends on kernel (and of course 3rd party libraries if appropriate), and since LiAR is implemented in C++ this means including its headers and linking to it dynamically.

Unfortunately, distutils is not designed for architecture like that. It can build multiple extension modules in a single package, but they’re supposed to be independent of each other. They cannot be linked in a binary way, communication should be done through Python. Modules don’t have the usual libfoo.so name anyway. However, distutils does support the build of C libraries that the extension modules can link against, but only for static libraries and what we need is dynamic linkage.

This calls for a bit of hacking. Luckily, distutils has a mechanism that allows to add extra custom commands. This can be used to hijack the build_clib command (for static libraries) and use it to build shared libraries. A new command liar_build_shared_lib is derived from build_clib and the relevant methods are overridden. It’s a bit too long to post here (you can see for yourself in the code repository), but basically it’s a blend between build_clib and build_ext. The cmdclass argument in setup() is used to inject liar_build_shared_lib as the new build_clib.

The concrete modules need to be linked to kernel, but a Python extension module does not have the regular libfoo.so name, but simply foo.so instead. What I’ve done to solve this, is to create libkernel.so which is kernel sans kernel_init.cpp, and a shallow module kernel.so that consists only of kernel_init.cpp. This way, all modules can link to a regular library, and kernel.so exposes its content to Python.

By now, things pretty much compile. I can even import liar in Python, though I must use the LD_LIBRARY_PATH environment variable hack to tell the modules where they can find libkernel.so. And once I start running some scripts I quickly get segmentation faults. So there are still some things to solve =)

Also, I need to clean up setup.py a bit, because things were simply thrown together until it worked. Options are still pretty much hardcoded. And also, I would like to be install the kernel headers so that custom LiAR extensions can be build using the installed LiAR.

I’ve added clip mapping (*) to LiAR, which is some sort of alpha channel for surfaces. It can be used to create holes in a surface using a texture. The texture is compared to a threshold to determine where the surface should be removed, so that rays can travel undisturbed through the removed parts.

This is different from using a fully transparent BSDF because the latter will split ray paths by inserting a no-op scattering event. This is especially a major difference for shadow rays in a direct lighting pass: they block on the first scattering event causing the transparent parts to cast shadows. When using clip mapping, no scattering event will be inserted because the surface is not present, and thus shadows will be casted as expected.

It’s implemented as a special scene object ClipMap that takes a child object and a clip texture. When the object is tested for ray intersections, a candidate intersection with the child object is searched for, and if one is found the clip texture is evaluated using the local intersection context of the child object. If this yields a value above a threshold, the intersection is accepted. Otherwise, a new candidate intersection is searched for with an adjusted near limit of the bounded ray.

It was pretty easy to implement, however not without cost. The intersection context needs to be evaluated independently of the one used for shading. Worse, the used intersection context may be different depending on which level the shader is defined. Also, the function isIntersecting can no longer use any shortcuts, but must perform a full intersection test.

while (true)
{
child_->intersect(sample, ray, intersection);
if (!intersection)
{
result.swap(intersection);
return;
}
child_->localContext(sample, ray, intersection,
context);

if (clipMap_->lookUp(sample, context).average()
>= threshold_)
{
intersection.push(this);
result.swap(intersection);
return;
}
ray = bound(ray, intersection.t(), ray.farLimit());
}

You can try it out for yourself using the clip_map.py example in the examples/scenery directory.

(*) The term clip mapping is being used in LightWave 3D and some other renders, and also appears in the book Digital Lighting & Rendering by Jeremy Birn. However is also used for naming the act of loading small parts of huge mipmaps to reduce memory requirements.

I’m trying to use the subdivision surfaces I’ve implemented to get a smoother surface for car i’m rendering for PHD Motorsports. The original model has UV coordinates that need to be interpolated as well. As each triangle is split in four, each edge is split two. I’ve been using the naive assumption that for the UV coordinates of the new vertices, I can use the average of the two original vertices of the edge. As can be seen from the following renders, that doesn’t quite work. The UV mapping gets severely distorted.

So, I’ll have to search for something more clever. Probably something similar as for the vertex coordinates. However, I wonder what to do with seams in the texture mapping … To be continued …

I’ve implemented subdivision surfaces for the TriangleMesh using the Loop’s scheme. Triangles are split in four, and the vertices are weighted using masks to produce a smoother surface. This process is repeated a few times, indicated by the subdivision level.

The implementation also supports the concept of creases. If an edge of the mesh has a crease level different than zero, the subdivision must leave the edge sharp for a number of iterations equal to the crease level. For example, if an edge has crease level three, and a subdivision of five levels is applied, then the algorithm must leave the edge sharp for the first three iterations, and may only smooth it for the last two. This will give the edge a sharper appearance than the rest of the mesh. If the crease level is equal or greater than the subdivision level (for example both level five), then the edge will stay ultra sharp, since the algorithm will never be allowed to smooth it.

In the following image, the same cube is shown for different subdivision and crease levels. There are no vertex normals used, to clearly show the different faces of each resulting triangle mesh. So no sneaky normal interpolation to give the mesh a smooth appearance!

At three o’clock, there’s a perfect cube with subdivison level zero. Going in counterclockwise order, the subdivision is each time increased by one level. At nine o’clock, subdivision level six is reached, resulting in a very smooth object. Remember there are no vertex normals here!

Continuing in counterclockwise order, the subdivision level is now kept at constant of six, but the crease level of the cube’s edges is each time increased by one. The circle would be closed again at three o’clock with both the subdivision and creasing at level six, but this is virtually the same as the original cube (both at level zero), only with a much finer triangle mesh.

You can try all this for yourself using the example loop_subdivision.py in the examples/scenery subdirectory.

PS: you will have to update your Lass installation to use this, since the actual subdivision code is part of Lass.