Milton Renderer Blog

Milton supports the useful distinction between geometric and shading normals.  Though not physically realistic, modeling fine geometry and corresponding materials is often very difficult to do. By allowing the surface normal to vary as a function of position, independent of the geometric normal defined at a point, a modeler is able to instead fake higher resolution geometry by using what’s known as a shading normal.  It is important to note that shading normals have no physical basis whatsoever.  They are generally interpolated in some manner over the surface of a shape; here is a summary of common shading normal techniques:

• Phong shading — interpolates vertex normals across the surface of a polygon
• Bump mapping  — perturbs geometric normal by an amount proportional to the discrete partial derivatives defined in a B&W “heightmap” texture at the current sample point’s UV coordinates
• Normal mapping — replaces geometric normal by an RGB -> XYZ normal found in a texture map (almost identical to bump mapping)
• Displacement mapping — procedurally replaces simplified geometry at run-time with estimate of higher-resolution geometry via a “heightmap” texture (generally very expensive in terms of storage and computation overhead)
• Parallax mapping — displaces texture coordinates of a surface point by a function of the view angle relative to the geometric surface normal and the local value of a “heightmap” at that point
• Steep parallax mapping — utilizes local ray tracing to displace texture coordinates of a surface point similar to parallax mapping, but supporting self-occlusion and a greater sense of depth at grazing angles

None of these techniques are physically “correct”.  They are hacks; very, very cool hacks.  Why then, do several of them appear in Milton?  They seem to go against two of the core principles that Milton is based upon, namely physical realism and being unbiased.  These techniques do, however, have their place in terms of both current utility and precedent.  They are heavily ingrained in both industry and academia, and for the majority of non-academic settings, the drawbacks of unrealism and bias don’t really matter.  That being said, Milton still aims to uphold these principles, and it is this duality which prompted us towards a pretty cool idea that allows us to support both physically “incorrect” phenomena such as shading normals while at the same time retaining our drive for theoretically unbiased realism.

To this end, Milton supports a physicallyValid flag (specified either via the commandline or in the scenefile itself), which when enabled, enforces physical realism throughout Milton (eg, by disabling the usage of shading normals), and when disabled (default), allows the use of physically invalid, albeit useful techniques such as shading normals.  Another post will explain our scenefile format in-depth and the reasons for the design choices we made, but one core concept that’s relevant here is that Milton scenefiles may override any built-in Milton type with an external plugin adhering to a well-defined interface to replace built-in types dynamically at run-time (via DSO libs of DLLs, respectively).  The details of this aren’t important to this post, but one consideration is that this ‘physicallyValid’ contract could be violated if an external plugin were to use shading normals, for instance, without Milton’s explicit knowledge.  We can, however, still ensure physical realism to a high degree of confidence even in the face of external plugins, by stochastically testing the behavior of plugins once at loadtime to ensure, in the case of external BSDFs, that they are symmetric (reciprocal) and energy conserving.

Here are a few test renders which use bump mapping to achieve an effect of more detailed geometry (all scenes contain one ground plane a point light).  For more information on bump mapping, see Blinn’s original 1978 paper in which the technique was invented, Simulation of Wrinkled Surfaces.

The Milton source tree is divided into several main parts:

• Core Milton library, containing all of the real framework internals and algorithms necessary to render anything and everything
• Qt Gui frontend (including a non-graphical ‘nox’ mode) which wraps around the independent core Milton library as a convenient, cross-platform executable that comes packaged along with Milton, and will probably the the main point of entry to users who just want to render scenes without worrying about any of the internals
• A variety of unit tests designed to ensure the stability of Milton and guarantee physical realism in several places (BSDF implementations, for example)
• Documentation; Milton uses doxygen internally to generate comprehensive, thoroughly-commented source code documentation which is auto-generated into html format.  In addition to this class-by-class and function-by-function style documentation, more structured documentation and tutorials will be available online sometime in the near future.

Since the main entrypoint to new users will be the Qt graphical frontent used to invoke Milton and render scenefiles, here is the result of running ‘milton –help‘ from the commandline:

Usage: ./milton <options> <scenefile>*
   Note: if no scenefile is specified, the default scenefile 'scenes/default.js' will be used

Options: (convenience, shortcut flags)
                	 (options later in commandline will override those
                	  listed earlier)
   --help       	: prints out this usage information
   -nox         	: disables the Qt gui frontend for environments without
                	  X support)
   -gui         	: enables the Qt gui frontend
   -verbose -v  	: enables extra debugging printouts
   -nopreview   	: disables forcing of OpenGL preview of loaded scenes
   -preview     	: overrides renderer specified in scenefiles to default
                	  to an OpenGL preview
   -pause       	: disable rendering right away upon initialization when
                	  Qt gui is enabled
   -output=%s   	: quickly specifies an output file to store rendered
                	  results to. if the suffix for the filename given is
                	  a valid image format, the results of rendering will
                	  be saved as an image in the specified format,
                	  otherwise, raw output of film plane positions ->
                	  spectral radiance values will be recorded in a simple,
                	  unordered ASCII format:
                	  x y L0 L1 ... LN
                	  x y L0 L1 ... LN
                	  ...

The following options use standard Milton JSON syntax to override possible equivalent definitions which may be listed in the scenefile(s) given
   Example:
    	-output={"type":"naive","width":640,"height":480}
   -output=%s
   -renderer=%s
   -camera=%s

An N-dimensional kd-Tree is an axis-aligned binary spatial partitioning data structure where N = d.  Each internal node is split along one of the N principle axes, where the split plane is typically chosen at each node based on some sort of heuristic.

The kd-Tree implementation in Milton supports several common split plane generation methods, namely:  spatial midpoint, median of geometry, and surface area heuristic (SAH).  Note that a kd-Tree constructed by choosing the spatial midpoint along the current split axis as the next split plane is equivalent to an octree.  Also note that though the SAH produces the best quality tree greedily with respect to visibility tests, it can take a long time to build and is thus mainly suitable for static scenes (whereas other acceleration data structures may be more appropriate for dynamic geometry & animations).

The SAH kd-Tree may be tweaked with several parameters.  See kdTreeAccelParams for more info.  The O(nlog n) SAH construction has been implemented as opposed to the O(n) or O(n^2) alternatives (using std::sort for internal sorting).  This choice was made because the O(n) solutions which exist both have large constants (which diminish their utility in practice), and are nowhere near as readable or easy to understand as the relatively straightforward O(nlog n) alternative.

Notes on debugging kd-Trees:

If issues arise, the first thing you want to do is determine whether the problem is in tree construction or tree traversal.  To narrow this down, I’d recommend replacing the traversal with a really simple / naive DFS that will traverse the entire data structure without any pruning at all, recording the minimum t-value along the way.  If you’re still experiencing problems, then the problem is likely with the construction of your tree.  Needless to say, you should also test with no acceleration data structure at all (linear traversal through all primitives in the scene ala NaiveSpatialAccel), to determine whether the problem lies in a primitive intersection routine of in the acceleration data structure itself.  Note the presense of kdNode::preview which recursively draws a version of the kd-Tree (starting with the root kdNode) in OpenGL. This method has been invaluable in visualizing and debugging edge cases with planar primitives and subtle, yet complex scenes.

Below are several test scenes which depict canonical edge-cases that can be hard to get right in a highly optimized kd-Tree implementation, but are necessary to get right to be robust in the face of numerical inprecision issues.  The first scene consists of 4 coplanar planes, and the second consists of 4 coplanar triangles.

Materials are very much physically-based in Milton.  Every Shape is coupled with a Material, defined over the surface of the Shape.  Whenever we want to attenuate incident light at a point on a shape or sample an exitant reflected direction, we defer to the Material’s BSDF, which at a high level defines the “color” at a single point on a surface.  While color is a perceptual phenomenon, the material properties that make up a surface determine how incident radiance (light) is changed after interacting with it, and the concept of a surface’s “color” arises by whether or not the surface reflects or absorbs different wavelengths of light.  Other surface properties such as dullness (a chalkboard) or sharpness (ie, a mirror) are determined by the very much related distribution of exitant light energy given incident light.  For example, a specular mirror has a very focused exitant distribution of radiance for any given incident stream of light.

Ideally, one would have the ability to define an arbitrary mapping between surface points (or for that matter, any point — participating media / subsurface effects, etc.) and an associated BSDF defined at a given point.  A Material would then, from a design standpoint, be a function which takes in a surface point (generally specified by u, v coordinates on the surface) to a specific BSDF defined at that point.  This is a very generic and physically-based solution to the design of a material system for a rendering engine such as Milton, but we have chosen to go with a slightly simpler option.  In Milton, instead of having a completely arbitrary mapping between surface points and their associated BSDFs, each surface and its associated Material define a mapping to a single BSDF, whose inputs are allowed to vary with respect to the given surface point.  This is useful for a variety of empirically or physically-based BSDF models with user-defined inputs that allow a single BSDF model to capture the appearance of a wide range of real-world materials.  Examples of such models include the Lambertian, Phong, and perfectly Specular BSDFs (including many, many others).  The lambertian BRDF models a perfectly diffuse surface whose exitant energy distribution is uniform over the hemisphere without respect to the incident angle of light.  It takes as input a single parameter per sampled wavelength, referred to as kd, representing the fraction [0, 1] of reflected versus absorbed spectral radiance at a given wavelength.  This parameter, kd, is allowed to vary along the surface of the Material as input to the single DiffuseBSDF, via lookup in an image defined over the (u, v) coordinates of the surface.  This is commonly known as a texture map, though it is fundamentally more general in that it can be used to parameterize BSDFs in many more ways than just modulating the surface “color” with position.

You can now apply maps to generate spectra values referenced in BSDFs (kd, ks, etc.).   These screenshots depict a DiffuseBSDF’s “kd” parameter being  evaluated depending on the SamplePoint’s UV coordinates.  The scene consists of a plane mapped with various textures, illuminated with a planar area light.

Milton contains the concept of a SampleGenerator, which is a pure virtual C++ class, whose purpose is to generate sample points over a 2D domain, possibly being constrained in the number of samples to be generated or the preferred “bin” size if the domain represents underlying pixels on an image, for instance.  Examples of SampleGenerator implementations include:

• uniform sampling over the 2D domain, where n samples are distributed evenly along a regularly-spaced grid within the domain
• stochastic sampling, where n samples are chosen completely randomly within the bounds of the domain
• jittered sampling, where n samples are chosen randomly from within m subdomains s.t. the overall distribution of samples is guaranteed to have at worst no higher variance than stochastically distributing the samples
• low discrepancy quasi monte carlo methods, which can be combined with other sampling techniques such as jittered sampling to try and space out samples in a more well-defined yet non-regular manner

These SampleGenerators are used in several places throughout Milton, where an integral needs to be estimated using Monte Carlo integration, which involves generating n sample points over the given domain.  Examples of where this type of common behavior comes up include with respect to 2D domains includes:  point sampling the film plane for stochastic ray tracing or within an individual pixel for standard ray tracing, or sampling visibility from an area light source.

For more details and a clear, high-level description of the problem at hand, I’d recommend taking a look at 2dsamplingtechniques.ppt, a concise, easy-to-understand Powerpoint depicting the intuition behind the pros and cons of uniform sampling, stochastic sampling, stratified / jittered sampling, supersampling and adaptive sampling, motivated by the common example case of sampling a function defined over a 2D domain (a film plane, for instance).   I originally created these slides for CS123 in the Fall of 2008 (Brown University).

Here are some experiments of variance reduction for a simple scene containing a single area light source shining on an infinite “ground” plane.  The camera’s eye point is located above the area light source, looking straight down towards the origin, which is why the middle of each image contains a black square (the single-sided planar emitter, which is occluding the ground plane from the viewer’s vantage point).

Here are a bunch of cool OpenGL visualizations I’ve been messing around with to view the internal structure of kd-Trees used for spatial acceleration queries (finding the closest intersection between a ray and a collection of objects composing a scene, for instance).  All kd-Trees in these examples are really instances of more specific octrees, the difference being that kd-Trees can split nodes along an arbitrary axis-aligned split axis and split position, whereas octrees are confined to split in a round-robin order with respect to split axis and at the spatial center of the current node with respect to split position along the current split axis.  If you switch off splitting a kd-Tree along the x, y, and z axes respectively, and always split the node into two evenly sized subnodes, then that’s fundamentally equivalent to constructing an octree.  The spatial acceleration data structures available in Milton favor the use of kd-Trees, but it wouldn’t be hard to add other alternatives (BIH, BVH, grid, etc.).  The core, default spatial acceleration data structure in Milton is a thoroughly hand-optimized kd-Tree built with an O(nlog n) Surface Area Heuristic (SAH).

Several of these screenshots depict kd-Tree visualizations which draw transparent split planes in order to view more of the internal structure.  Having the ability to view the structure of spatial data structures is very useful, both in terms of debugging corner cases, and also for optimizing tree construction and analyzing structure in different types of environments.  I’ve come to the conclusion that one’s intuition is often wrong when dealing with spatial acceleration data structures, especially with respect to debugging them, so having a way to make problems more concrete by actually visualizing them is priceless — and it doesn’t hurt that the visualizations look cool, too.

I’ve just added support to Milton for blobby objects as a primitive shape, composed out of a collection of metaobjects, the most well-known of which are known as metaballs.  Why, you ask?  Because they’re friekin baller!!  Seriously, though, supporting blobby objects is pretty cool and not that hard to add to a renderer which already supports triangular meshes.

Blobby objects are defined by and composed of a set of metaobjects, each of which exert some influence or charge over a region, whose cumulative effects can be viewed as describing a scalar field around the blobby object.  By selecting a particular isocontour within this field as the boundary of interest, interesting surfaces are created that blend nearby metaobjects smoothly into each other.  These surfaces can be integrated seemlessly into an existing renderer by performing any variant of the well-known Marching Cubes algorithm over the scalar field, polygonizing the blobby object’s surface into triangles which can be handled just like any ordinary triangular mesh.

A MetaObject exerts a positive or negative ‘charge’ in a scalar field, whose isocontours (level sets) define blobby surfaces with different threshold values corresponding to the contour level.  MetaObjects positively or negatively affect their neighboring MetaObjects depending on their ’strength’ and ‘negative’ attributes.  ’strength’ defines the initial charge of the object, and ‘negative’ is a boolean which defaults to false, denoting whether or not this MetaObject has a positive or a negative impact on surrounding MetaObjects.  MetaObject is an abstract class, and specific implementations define how its initial charge dissipates throughout the field.

In addition to metaballs, Milton supports many of the standard geometric primitive types you’ve come to expect and love from rendering engines of this type, namely:  cone, cube, cylinder, triangular mesh, plane, point, sphere, and triangle.

Below you’ll find four pictures of metaballs created in Milton (rendered w/ OpenGL).  The four pics show the effect of different threshold values on the aggregate “blobby” shape (composed of three distinct metaballs).  The threshold value specifies the particular isocontour boundary which defines the surface of the blob.  The fourth image is an example of when the surface gets so thin that the marching cubes algorithm isn’t using a fine enough grid to capture parts of it which just disappear.  There are more dynamic algorithms which exist to polygonize a scalar field that try to handle this problem, but since metaballs are a small sidetrack anyhow, the current implementation will suffice for the purposes of Milton, at least for now.

Milton now supports loading of external meshes in OBJ and PLY formats.  Our hacked-up, custom OBJ loader was replaced by a generic loader with more robust loading implementations, courtesy of libobj and libply, both of which were written by Area Lagae.

OBJ Mesh created with TopMod

Welcome to Milton, a highly extensible and robust global illumination renderering system. Milton is still in development, but when it becomes more stable, the code will be released under an open source license for educational purposes. This blog will feature tutorials and development news.

Check back for updates.