Micropolygon Ray Tracing With Defocus and Motion Blur
Qiming Hou∗∗

Tsinghua University†

Hao Qin†Wenyao Li†

Baining Guo∗ ‡State Key Lab of CAD&CG, Zhejiang University(a) Perfect focus

Kun Zhou†‡Microsoft Research Asia(b) Motion blur + defocus

Figure 1: A car rendered with defocus, motion blur, mirror reflection and ambient occlusion at 1280 × 720 resolution with 23 × 23
supersampling. The scene is tessellated into 48.9M micropolygons (i.e., 53.1 micropolygons per pixel). The blurred image is rendered in 4
minutes on an NVIDIA GTX 285 GPU. The image rendered in perfect focus takes 2 minutes and is provided to help the reader to assess thedefocus and motion blur effects.

Abstract1

We present a micropolygon ray tracing algorithm that is capable ofefficiently rendering high quality defocus and motion blur effects.
A key component of our algorithm is a BVH (bounding volume hierarchy) based on 4D hyper-trapezoids that project into 3D OBBs
(oriented bounding boxes) in spatial dimensions. This acceleration
structure is able to provide tight bounding volumes for scene geometries, and is thus efficient in pruning intersection tests during
ray traversal. More importantly, it can exploit the natural coherence on the time dimension in motion blurred scenes. The structure
can be quickly constructed by utilizing the micropolygon grids generated during micropolygon tessellation. Ray tracing of defocusedand motion blurred scenes is efficiently performed by traversing thestructure. Both the BVH construction and ray traversal are easily
implemented on GPUs and integrated into a GPU-based micropolygon renderer. In our experiments, our ray tracer performs up to
an order of magnitude faster than the state-of-art rasterizers whileconsistently delivering an image quality equivalent to a maximumquality rasterizer. We also demonstrate that the ray tracing algorithm can be extended to handle a variety of effects, such as secondary ray effects and transparency.

Current cinematic-quality rendering systems are based on the Reyes
architecture [Cook et al. 1987], which uses micropolygons to represent high order surfaces and highly detailed objects. In a Reyes
pipeline, all input geometric primitives are first tessellated into micropolygons (i.e., quads less than one pixel in size). Shading isthen calculated on micropolygon vertices. In the subsequent sampling stage, micropolygons are rasterized into fragments, which arefiltered to produce the final image.

Keywords: GPUs, Reyes, rasterization, depth-of-field, motion
blur, bounding volume hierarchy, hyper-trapezoid

ACM Reference Format
Hou, Q., Qin, H., Li, W., Guo, B., Zhou, K. 2010. Micropolygon Ray Tracing With Defocus and Motion Blur.
ACM Trans. Graph. 29, 4, Article 64 (July 2010), 10 pages. DOI = 10.1145/1778765.1778801
http://doi.acm.org/10.1145/1778765.1778801.
Copyright Notice
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted
without fee provided that copies are not made or distributed for profit or direct commercial advantage
and that copies show this notice on the first page or initial screen of a display along with the full citation.
Copyrights for components of this work owned by others than ACM must be honored. Abstracting withcredit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any
component of this work in other works requires prior specific permission and/or a fee. Permissions may berequested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701, fax +1(212) 869-0481, or permissions@acm.org.
© 2010 ACM 0730-0301/2010/07-ART64 $10.00 DOI 10.1145/1778765.1778801
http://doi.acm.org/10.1145/1778765.1778801

Introduction

Rasterization has long been regarded as the best way to sample micropolygons and widely used in existing micropolygon renderers.
When sampling stationary geometry (i.e., without defocus and motion blur), rasterization is simple to implement and performs efficiently because tight bounding boxes can be easily computed for
micropolygons. However, when rendering defocus and motion blur,tight bounding boxes can no longer be computed and brute-force
rasterization becomes very inefficient. Non-intuitive parameters for
quality and performance tradeoffs have to be exposed to end-users
to achieve a satisfactory balance between artifacts and render time,
as noted in Fatahalian et al. [2009].
In this paper, we tackle the problem of sampling defocused andmotion blurred micropolygons using ray tracing. We propose to
replace the rasterizer in the sampling stage of micropolygon renderers with a ray tracer. Ray tracing does not need to compute tightbounding boxes of micropolygons and is known to work efficiently
for irregular visibility sampling. By designing an effective acceleration structure, we demonstrate that for high quality defocus andmotion blur, the advantage of ray tracing in irregular sampling outweighs its inherent algorithmic overhead. Experiments show that
our ray tracer is up to an order of magnitude faster than the stateof-the-art rasterizers. Moreover, with our algorithm, users do notneed to make non-intuitive tradeoffs between the rendering performance and image quality.
Designing an efficient ray tracing algorithm for micropolygons withdefocus and motion blur is far from straightforward. The key challenge is the acceleration structure. First, the structure has to be
ACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

64:2

•

Q. Hou et al.

flexible to support the 4D space-time extension to handle motion
blur. It also has to be robust such that the traversal complexity will
not degenerate for challenging geometries such as hair and furs represented by spatially-clustered long curves. Furthermore, the memory consumption of the structure has to be minimized to process
millions of micropolygons in-core for parallelism utilization. Secondly, the structure has to be constructed very efficiently without
significantly compromising traversal performance. Since the ray
tracer only processes the sampling stage in the Reyes pipeline, only
a fixed amount of primary rays generated by defocus and motion
blur supersampling are traced. Therefore, the structure construction cost cannot be amortized over a large amount of rays and may
constitute a significant portion of the rendering time. Finally, rays
have to be kept coherent during traversal. While primary rays are
inherently coherent, high quality defocus and motion blur requirerays to be generated using stochastic sampling. Directly tracingrays in their generation order may result in very poor coherence.
As a consequence, the rays have to be reorganized to exploit theinherent coherence.
The basis of our ray tracing algorithm is a novel acceleration structure – a BVH based on 4D hyper-trapezoids that project into 3D
OBBs in spatial dimensions. This structure has several features
making it very suitable for tracing defocused and motion blurred
micropolygons. First, the hyper-trapezoids are able to exploit thenatural coherence on the time dimension in motion blurred scenes.
Second, by using OBBs in spatial dimensions, degeneration is
avoided for challenging geometries. Third, as a BVH, the memory consumption of the structure is naturally bounded. And finally,
the structure can be efficiently constructed by utilizing the micropolygon grid, a natural structure generated during micropolygon tessellation.
Based on the OBB hyper-trapezoid BVH, we develop a micropolygon ray tracing algorithm to render high quality defocus and motion
blur effects. During ray traversal, the algorithm sorts rays using a
coherence heuristic based on the per-ray motion time and ray directions to improve traversal coherence. The ray tracer, including
both the BVH construction and ray traversal, can be efficiently implemented on the GPU, and integrated into existing GPU-based micropolygon renderers [Zhou et al. 2009]. The algorithm can be also
extended to deal with a variety of effects, such as occlusion culling,
secondary ray effects including shadow, reflection and refraction,and memory-bounded (and layer-limited) transparency.
In the rest of the paper, we first briefly review related work. In
Section 3, we detail the acceleration structure and the micropolygon ray tracing algorithm, followed by the description of several
extensions of the algorithm in Section 4. Section 5 evaluates therendering quality and performance of our algorithm using several
examples, and Section 6 concludes the paper.

2

Related Work

Micropolygons are the basic geometric element of the Reyes rendering architecture [Cook et al. 1987].
Several Reyes implementations, including Pixar’s PRMan, havebeen widely used in film production. Recent research efforts focus
on developing data-parallel algorithms for micropolygon rendering.
Patney and Owens [2008] mapped the tessellation algorithms for
micropolygon generation to the GPU. Fatahalian et al. [2009] investigated data-parallel implementations of a variety of micropolygon rasterization algorithms. RenderAnts [Zhou et al. 2009] implements a complete micropolygon-based renderer on the GPU anddemonstrates significant speedups over CPU-based renderers. Our
work provides micropolygon ray tracing as an alternative algorithm
for the sampling stage of micropolygon renderers.
Micropolygon Rendering

ACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

Defocus and motion blur are important and common effects in real-world images. For cinematic rendering, these effects are typically computed using supersampling.
Stochastic sampling is immune to aliasing artifacts [Cook et al.
1984; Cook 1986] while challenging for rasterizers to computetight bounding boxes. Deterministic sampling like the accumulation buffer [Haeberli and Akeley 1990] provides tighter boundingboxes for rasterizers while being more prone to aliasing. Stateof-the-art rasterizers make tradeoffs between sampling randomnessand bounding box tightness to balance the rendering performanceand image quality [Cook et al. 1993; Fatahalian et al. 2009].
Defocus and Motion Blur

A few recent publications seek to accelerate the rendering of defocus and motion blur effects using adaptive sampling and frequency
analysis [Hachisuka et al. 2008; Egan et al. 2009; Soler et al. 2009].
The key difference between our work and theirs is that we focus on
reducing the cost of sampling itself rather than the number of samples computed. Any sampling patterns proposed in their work canbe used in our algorithm. In this paper we assume a uniform sampling strategy is used.
There are a few methods for approximating defocus and motion blureffects [Sung et al. 2002; Demers 2004; Kass et al. 2006; Lee et al.
2009]. These methods are designed to achieve high performanceand may produce artifacts in some image regions. On the contrary,
our method is designed to provide guaranteed quality while running
as fast as possible. Our method guarantees an image quality noworse than a maximum-quality brute force rasterizer.
Distributed ray tracing [Cook et al. 1984] formulates defocus and motion blur rendering as a ray tracing problem while leaving out the acceleration ofsuch formulation. Space-time ray tracing [Glassner 1988] accelerates ray tracing of motion blurred scenes using BVH based on
4D polyhedrons with up to twelve fixed-orientation faces. The
algorithm simply treats the time dimension as an additional spatial dimension and ignores the unique geometry coherence property
along the time dimension. Our work follows the formulation of distributed ray tracing and uses OBB hyper-trapezoids to exploit theinherent temporal coherence in motion blurred scenes to constructa space-time 4D hierarchy with significantly tighter bounding volumes.
Ray Tracing and Acceleration Structures

Micropolygon ray tracing has been proved to be very useful in film
production [Christensen et al. 2003; Christensen et al. 2006]. The
basic idea of our hyper-trapezoid BVH resembles the moving KayKajiya tree in [Christensen et al. 2006]. However, these previous
works focus on tracing secondary rays. Primary-ray effects likedefocus and motion blur are still rendered via rasterization. In contrast, our ray tracing algorithm is designed and optimized for tracing
defocus and motion blur rays. In addition, our algorithm, including
the BVH construction and ray traversal, is highly parallel and efficiently implemented on GPUs, which has never been achieved inprevious micropolygon ray tracing.
Several parallel algorithms for constructing ray tracing acceleration hierarchies have been developed recently [Shevtsov et al. 2007;
Wald 2007]. Parallel hierarchy construction has also been mapped
to GPUs [Zhou et al. 2008; Lauterbach et al. 2009]. All these techniques are designed for axis-aligned hierarchies, which may degenerate for spatially-clustered non-axis-aligned geometries like hairand furs. Oriented hierarchies are less prone to non-axis-aligned
geometries and more efficient in pruning intersection tests during
ray traversal [Ize et al. 2008]. The high construction cost, however,remains an obstacle to the on-the-fly construction of oriented hierarchies. We present a novel oriented hierarchy design that allows
fast GPU construction by utilizing the micropolygon grid, a natural
structure generated during micropolygon tessellation.

Micropolygon Ray Tracing With Defocus and Motion Blur

T=1
Time
axis

n

T=0

Micropolygon Ray Tracing

In this section, we first briefly revisit the ray tracing formulation of
defocus and motion blur in Section 3.1, followed by the descriptionof OBB hyper-trapezoids in Section 3.2. Section 3.3 details ourhyper-trapezoid BVH construction algorithm. In Section 3.4, we
discuss ray generation and coherence reorganization, and present
the BVH traversal algorithm in Section 3.5. Finally, in Section 3.6,
we describe how to integrate our ray tracer into a micropolygon
rendering pipeline.

3.1

n

64:3

motio

3

motio
n
motio

Hyper-trapezoids have been first proposed for collision detection [Hubbard 1995]. This work simply uses axis-aligned hypertrapezoids as approximation geometry for the moving object intersection test and does not construct any hierarchy. We extend their
hyper-trapezoid definition with orientation in spatial dimensions
and develop hyper-trapezoid hierarchy construction and traversal
algorithms for ray tracing.

•(a) A 2D scene with motion(b) Corresponding 3D space-time

Figure 2: A 2D scene with motion and its corresponding 3D spacetime. Each slice perpendicular to the time axis in the space-timecorresponds to the 2D scene at a particular instant of time.

Ray Tracing Formulation

Both defocus and motion blur rendering can be formulated as ray
tracing problems as in distributed ray tracing [Cook et al. 1984].
These formulations can be adapted to micropolygons in a straightforward manner.
Our algorithm takes a set of shaded micropolygons and the camera
configuration as input. A number of subpixel samples with assigned
lens points and time stamps are generated for each pixel to produce
defocus and motion blur effects. One primary ray is then generated
and traced for each sample. For defocus, the ray starts from theassigned lens point of the corresponding subpixel and goes throughthe point on the focal plane corresponding to the subpixel. For motion blur, the ray is extended to 4D space-time with the assigned
time stamp as the fourth dimension coordinate.

3.2

OBB Hyper-trapezoids

The key difference between traditional BVHs and our BVH is theshape of the bounding volume. The bounding shapes we use are
4D OBB hyper-trapezoids that project to 3D OBBs in the spatial
dimensions. For the sake of simplicity, in the following we describe
our hyper-trapezoids in the 3D space-time of motion-blurred 2D
scenes. We also assume all motion to be linear, i.e., the geometry
at time T = Ti is a linear interpolation of the geometry at time
T = 0 and T = 1. Non-linear motions can be easily handled bypiecewise-linear approximation [Christensen et al. 2006].
Consider a 2D dynamic scene shown in Fig. 2(a). By adding a thirdtime axis, we can get a 2D space translated continuously in time,i.e., the 3D space-time shown in Fig. 2(b). Motion rays with timestamps in the 2D space are mapped to ordinary rays perpendicular
to the time axis in the 3D space-time. Motion blurred renderingof the original scene may thus be performed by tracing rays in thespace-time using a 3D ray tracer.
Note that it is inefficient to use general-purpose 3D acceleration hierarchies in the space-time ray tracing. All shapes in the space-time
are prismatoids that span across the entire time dimension. Axisaligned hierarchies would be unable to utilize the time dimension
at all and produce highly inefficient bounding volumes as shownin Fig. 3(a). General oriented hierarchies can produce tight bounding volumes, but would be forced to introduce rotation in the time
dimension which destroys time-perpendicular properties and complicates intersection tests. Without special handling of the time dimension, direct 3D space-time ray tracing risks performance degradation due to such a special geometry distribution.

(a) Axis-aligned bound. volumes (b) Hyper-trapezoid bound. volumes

Figure 3:
Axis-aligned bounding volumes and OBB hypertrapezoid bounding volumes in a 3D space-time.

We solve this problem by using OBB hyper-trapezoids as bounding volumes. We define an OBB hyper-trapezoid to be the linear
combination of two oriented boxes with the same orientation lying on plane T = 0 and T = 1 respectively. Fig. 3(b) illustrates
an example of OBB hyper-trapezoids. Intuitively, an OBB hypertrapezoid in the 3D space-time corresponds to a moving oriented
box in the 2D space whose start and end poses correspond to the top
and bottom bases of the 3D hyper-trapezoid. Our hyper-trapezoids
are able to adapt to motion and bound moving objects more tightly
than axis-aligned volumes in space-time. The effectiveness of OBB
hyper-trapezoids is proved in our experiments as described in Section 5.2. In addition, OBB hyper-trapezoids in space-time have thefollowing property:
Property 1 An OBB hyper-trapezoid bounds a moving object inthe space-time if and only if the hyper-trapezoid bounds the object’s
start and end poses.
This property allows some key hyper-trapezoid operations to be
performed conveniently on the start and end poses in the original
space. We utilize the property to design efficient BVH construction
and traversal algorithms. Proof of Property 1 is straightforward:
OBB hyper-trapezoids are convex shapes. If a hyper-trapezoid
bounds an object’s start and end poses, all points formed by thelinear combination of the start and end poses are enclosed in thecorresponding hyper-trapezoid, i.e., the hyper-trapezoid bounds themoving object.
The hyper-trapezoid described above can be extended to the 3D
space (i.e., 4D space-time) in a straightforward manner. A 4D OBB
hyper-trapezoid is defined to be the linear combination of two 3D
OBBs with the same orientation at the start and end of a motion.
ACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

64:4

3.3

•

Q. Hou et al.

BVH Topology and Construction

Our BVH construction follows the general process of a top-down
SAH-based BVH constructor [Wald et al. 2007]. We begin with
one root node containing all input micropolygons and recursively
perform node partitioning until a termination criterion is met. Whena node is partitioned, all micropolygons inside it are partitioned into
its two child nodes. This top-down recursive partitioning process
generates a BVH topology, i.e., a binary tree where each leaf nodestores a list of micropolygons. After the topology is constructed, abounding shape is computed for each node in a bottom-up mannerto get the traversal-ready BVH. As aforementioned, the bounding
shapes are 4D hyper-trapezoids with 3D OBBs as bases.
While the OBB hyper-trapezoid allows compact bounds of arbitrarily moving objects, it also significantly increases the number ofpossible node-splitting candidates [Ize et al. 2008], leading to highconstruction overheads. To address this issue, we exploit the temporal coherence in motion and the micropolygon grid structure used intypical micropolygon tessellation algorithms to constrain the split
candidates within a small subset. First, we only consider the scenepose at T = 0.5 during BVH topology construction. Due to temporal coherence, the topology of this pose is expected to work reasonably well for temporally-close scene poses [Wald et al. 2007]. Second, we assume that the input data structure is an unorganized soupof micropolygon grids where each grid is a collection of micropolygons with a 2D parametric space. The majority of current micropolygon generation algorithms [Patney and Owens 2008; Fisher
et al. 2009] consist of a recursive splitting stage and a regular or
semi-regular tessellation stage. Such algorithms naturally generate
the micropolygon grid structure we need as illustrated in Fig. 4.
Our BVH topology construction consists of two stages to match thegrid data structure. We first build a top-level SAH BVH of the grids
using the centroid-based SAH partitioning algorithm [Wald et al.
2007]. Grids in each node are recursively partitioned into childnodes with respect to their centroids using axis-aligned planes. During SAH computation, the traversal cost of each grid is computed
as the number of micropolygons it contains. We continue splitting
even if no split candidate can reduce the SAH cost. This guarantees
that each leaf node in this top-level BVH contains at most one grid.
Once the top-level BVH is constructed, each of its leaf nodes is replaced with an in-grid BVH constructed using approximated SAH
splits. Within each grid, we approximate the optimal SAH split bysimply splitting at the midpoint of the longer axis in the parametricspace of the grid. The midpoint split stops once a node has less thaneight micropolygons. Note that for uniform grids, the optimal SAH
split coincides with the midpoint split. As micropolygon grids map
to uniform grids in the parametric space, intuitively the midpoint
split in the parametric space is an accurate approximation of the
optimal SAH split in the world space when the mapping between
the two spaces is sufficiently uniform. This intuition is verified inour experiments. In 94% of the cases we experimented with, thefinal SAH cost of the output subtrees produced by our parametric space algorithm is within 120% of the SAH cost produced bygreedy SAH optimization. For details about the SAH experiments,
please refer to Section 5.2.
The top-level BVH topology construction described above onlyuses axis-aligned partition planes, and is thus prone to degenerate geometries like dense non-axis-aligned curves in hair and fur
scenes. We address this issue by switching to an orientation-aware
split strategy when no split candidate can reduce the SAH cost or
when a predefined depth limit is reached. The orientation-aware
strategy constructs the BVH topology using 1D sorting. All grids
in the node to be processed are sorted with respect to a 5D Morton
code [Morton 1966] consisting of the grid orientation and centroid
position. The orientation of a grid is computed as the average miACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

Figure 4: Example micropolygon grids generated by a micropolygon renderer.

cropolygon normal for surfaces and the average segment direction
for curves. The orientations are converted to 2D using a low distortion sphere-disk map [Shirley and Chiu 1997] and packed in the
more significant position during Morton code construction. This
Morton code sort groups grids with coherent orientation together toattempt to make the oriented bounding boxes to be computed morecompact. A subtree topology is constructed from the sorted list byrecursively median partitioning the sorted list.
After the BVH topology is constructed, we perform a bottomup bounding and merging pass to compute the bounding hypertrapezoids. A bounding hyper-trapezoid is first computed for eachleaf node. Then for each inner node in the bottom-up order, thebounding hyper-trapezoids of its child nodes are merged to generate the bounding hyper-trapezoid of this inner node. Although thehyper-trapezoids are 4D, these two hyper-trapezoid operations canbe implemented with only 3D operations:• To compute the bounding hyper-trapezoid of a set of micropolygons, we compute two 3D OBBs with the same orientation forthe start and end poses of the moving micropolygons as the respective hyper-trapezoid bases.
• To merge two hyper-trapezoids into their bounding hypertrapezoid, the two bases of the two input hyper-trapezoids are
separately joined into two 3D OBBs with the same orientationthat are used as the bases of the final hyper-trapezoid.
Both operations require the orientation of the resulting hypertrapezoid as input. Therefore, an orientation needs to be computed for each node before its bounding hyper-trapezoid is computed. Again, we utilize the micropolygon grid structure to efficiently compute orientations that allow compact bounding boxes.
Specifically, we first compute the orientation for each micropolygon grid. For each grid, a main direction for each of its two tessellation directions is computed as the average of all respective micropolygon edges. The two main directions are then orthogonalized and combined with the normal vector of the plane they form toyield the per-grid orientation. We intentionally avoid PCA (Principal Component Analysis) during the main direction computation to
reduce computational cost and improve numerical stability. Aftereach per-grid orientation is computed, it is assigned to all nodes inthe sub-tree the grid corresponds to. The orientations are then propagated bottom-up to top-level nodes. For each top-level node, twobounding hyper-trapezoids are computed according to the orientations of its two child nodes respectively. The orientation that leads
to the bounding hyper-trapezoid with smaller surface area is chosen
as the final orientation.

Micropolygon Ray Tracing With Defocus and Motion Blur

3.4

Ray Generation and Organization

We generate subpixel, defocus and motion blur sampling rays using jittered stratified sampling [Cook 1986]. To generate N × N
rays for a given pixel, the three sampling domains, i.e., subpixel,
lens and time, are each divided into N × N regions of equal area.
One sample is taken from each region in each sampling domain.
All samples are randomly jittered within the corresponding regions.
Finally, one lens sample and one time sample are assigned to each
subpixel sample using two independent permutations for lens andtime. Fig. 5 illustrates the sampling domains and permutations.
Note that we use a per-pixel time permutation to eliminate thecorrelation between time and lens. Such per-pixel permutation isvery challenging for rasterizers as the permutation conflicts withassumptions required for computing tight rasterization boundingboxes. The only rasterization method capable of handling our sampling pattern is to test all samples covered by the expanded bounding boxes of all micropolygons in a brute-force manner.
We generate all the random numbers required in the ray generation in parallel by repeatedly hashing the ray index using the final
avalanching step of the SuperFastHash [Hsieh 2004]. The lens permutation we use is a magic square [Weisstein ] and the time permutation is a shuffled version of the defocus magic square shiftedby the hash of the pixel ID. This shift is omitted if defocus is disabled. For lens samples, currently we support disk and regularpolygon-shaped lenses to enable a variety of bokeh effects. We
first generate lens samples on a square and then map them to a disk
using a low distortion disk-square map [Shirley and Chiu 1997].
Polygon-shaped lenses are handled by modifying the radius in the
disk-square mapping.
As pointed out by Aila and Laine [2009], SIMD efficiency is critical for GPU ray traversal performance. Therefore, we group together rays that are likely to yield similar branch decisions during
traversal to improve the SIMD efficiency. First, we generate rays
in 16 × 16 tiles in the image space. Within each tile, the 256 rays
are organized in a Z-order curve [Morton 1966]. If motion blur isenabled, the rays are sorted by the 4-bit quantized motion time using a stable-sort. If defocus is enabled, the rays are sorted by the x
and y components (each quantized to 4 bits) of ray direction vectors
using a stable-sort. If both motion blur and defocus are enabled, thedefocus sort is performed after the motion blur sort as maintaining
coherence in defocus rays is more significant performance-wise.

3.5

BVH Traversal

Our BVH ray traversal algorithm follows the per-ray persistentwhile-while traversal algorithm [Aila and Laine 2009]. The main
challenge in designing the algorithm is the intersection tests.
Namely, we need to intersect motion rays with the 4D space-time
hyper-trapezoids and moving micropolygons. Note that a spacetime hyper-trapezoid may be interpreted as a moving OBB. Intersecting a motion ray with a hyper-trapezoid is thus equivalent to intersecting the ray with the corresponding OBB at the ray’s assigned
time. The same scheme can be applied to moving micropolygons.
The problems are thus converted to intersecting rays with OBBs
and micropolygons in the 3D spatial dimensions.
We convert oriented box intersection tests to axis-aligned box intersection tests by transforming rays into the per-box local frame. An
advantage of our constructed BVH is that the box orientations do
not change frequently during top-down hierarchy traversal. Therefore, ray transformation is performed less frequently than box intersections and does not introduce significant overhead comparedto pure axis-aligned BVH traversal.
The micropolygon intersection test is more complicated. From a

1

2

3

4

5

6

1 2 3
4 5 6

7

8

9

7 8 9

Subpixel
1

2

3

Lens

4

5

6

7

8

9

Time

1 4 2 9 3 2 1 4 2
1682
4 3 5 5 6 7 4 3 59241
7 8 8 1 9 6 7 8 8
753
6Pixel (0,0)(a) Sampling domains andjittering regions

•
9 3
7
5 6
3
1 9
8

64:5
2
9
7
5
6
4

Pixel (1,0)(b) Permutations

Figure 5: Example ray generation for 3 × 3 supersampling.
mathematical point of view, the 3D geometry of micropolygons
is inherently ill-defined. The four vertices of a micropolygon are
typically not coplanar. The edges may be concave or degenerate.
It is difficult, if not impossible, to define an intersection-friendly
3D geometry for an arbitrary micropolygon. Therefore, we use arasterization-like method to compute pseudo-intersections for micropolygons. The four vertices of the micropolygon to be tested
and the ray termination point are first perspectively projected to 2D
space along the z-axis as in a rasterizer. A 2D quad is constructed byconnecting pairs of projected vertices that correspond to the original micropolygon edges. An even-odd rule 2D point-in-polygon
test between the projected ray termination point and the 2D quadis then performed. If the point-in-polygon test returns positive, apotential intersection point is computed by bilinearly interpolating
the z component of the four micropolygon vertices and inverseprojecting the projected ray termination point with the computedz. The selection of interpolation weights is insignificant as long as
all weights are valid, i.e., the sum of the four weights is 1 and allweights are non-negative. If the minimum and maximum z of micropolygon vertices and the minimum and maximum z of the ray
overlap, the intersection test returns positive and the potential intersection point is returned. Otherwise the intersection test returns
negative.
The use of the projection-based pseudo-intersection test guarantees
two important properties of our algorithm. First, our micropolygon intersection test is equivalent to a coverage test in a rasterizer. Therefore, our algorithm produces no visual artifacts otherthan those produced by rasterization. Second, despite that our intersection test does not correspond to any well-defined 3D geometry,adding a bounding volume intersection test before the micropolygon intersection test does not result in cracks. The reason is asfollows. All bounding volumes in our BVH are convex and boundall vertices of the contained micropolygons. Pseudo-intersection
points inside the convex hull of the micropolygon vertices are neverpruned by bounding volumes, and the potential pseudo-intersection
points still form a water-tight shape.

3.6

Reyes Pipeline Integration

Our micropolygon ray tracer can be used in the sampling and composition stages in a Reyes pipeline. The ray tracer takes the shaded
micropolygon grids from the preceding shading stage, constructs a
BVH for the micropolygons, traces rays and returns a set of subpixel sample colors to the subsequent filtering stage.
We have implemented the described BVH construction and traversal algorithms on GPUs using the BSGP language [Hou et al. 2008].
Since most operations in our algorithms (e.g., SAH-based splitting
and ray traversal) have available GPU implementations in previous
publications [Zhou et al. 2008; Lauterbach et al. 2009], implementing our ray tracer on the GPU is straightforward. We also integrated
the ray tracer into RenderAnts [Zhou et al. 2009], an open source
GPU-based Reyes renderer. We removed their original accumulation buffer based defocus and motion blur implementation and
ACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

64:6

•

Q. Hou et al.

UVT-2

UVT-4

UVT-2

UVT-4

UVT-2

UVT-4

(a)

Interval

Trace

Interval

Trace

Interval

Trace

(c)

(a) Defocus only(b) Motion blur only(c) Defocus + motion blur(b)(d) Perfect focus

Figure 6: Render quality comparison. The small images in the bottom rows are close-up views for the boxes in the top. All large images
shown here are generated by our ray tracer. Images are rendered at 1280 × 720 with 13 × 13 supersampling.

modified their pipeline to call our ray tracer.

4

Extensions

In this section, we describe several extensions of our micropolygon
ray tracing algorithm.
Secondary Rays An obvious extension is to use our ray tracer
to compute secondary ray effects like hard shadow, reflection andrefraction. However, directly tracing secondary rays on Reyesgenerated micropolygons would yield incorrect results as Reyes
micropolygons are generated using view-dependent tessellation.
Therefore, we first generate a secondary ray friendly micropolygon
representation of the scene using non-culled view-independent tessellation. Ray tracing interfaces on this representation are then provided to shaders. We currently provide two ray tracing interfaces,
one only tests whether there is an intersection and one computes
shading at the intersection point. Using these interfaces, we implemented ray-traced hard shadow, reflection and refraction. These
effects are rendered in our fur ball and car scenes shown in Fig. 1
and Fig. 7(a).

The geometric precision for secondary intersections with parametric surfaces are limited by the available memory because we currently do not support out-of-core BVH traversal. For strongly enlarging reflection/refraction effects, parametric surface silhouettes
may not be very smooth. On the other hand, shading quality forreflection/refraction is less affected by this limitation as we recompute surface parameters for parametric surfaces at secondary ray hit
points during shading. In practice, we find that our secondary effectquality is acceptable for near-flat reflective/refractive surfaces andfor hard shadows at non-extreme angles.
Ray-micropolygon intersection for secondary rays has a minor difference with primary ray intersection. Instead of projecting micropolygons along the z axis, we project micropolygons along the axis
on which the ray direction has the maximum absolute value.
Memory-bounded transparency and layer-limited
transparency can be conveniently implemented using ray tracing.
One important property of ray tracing is that it can start at any
point, and can return the nearest m intersections instead of justone. This allows us to process transparency in multiple passes in
the front-to-back order and only compute a limited number of layTransparency

ACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

ers in one pass. For memory-bounded transparency, we restrict the
total number of transparent layers processed in one pass according
to the available memory. After each pass, all generated layers areaccumulated to the final image and all memory used during the passis freed. This property guarantees that the algorithm never fails due
to out-of-memory errors, even in extreme cases where the transparent layers on a single subpixel sample cannot fit in memory. For
layer-limited transparency, we simply ignore all transparent samples beyond the nearest m layers, where m is a user-specified value.
With a proper m, rendering of hair/fur scenes may be significantly
accelerated without introducing visible artifacts. Our fur ball scene
shown in Fig. 7(a) requires memory-bounded transparency to correctly render in-core, and its number of transparent layers is limited
to five to accelerate rendering.
Ray tracing can be also used as a visibility testing tool
for pre-shading culling. Prior to shading, we detect visible micropolygon grids by tracing a few primary rays on random points ofeach grid and only shade the grids that are hit by at least one ray.
Other grids are only shaded when they are intersected during thesubsequent sampling stage. In our experiments, the culling may reduce shading workload by approximately 40%. However, the parallelism during the shading stage becomes fragmented and the GPU
becomes under-utilized. Although we do not observe any acceleration in our test scenes, we expect that such culling would be more
effective for film production scenes with more complicated shaders.
Culling5

Experimental Results

In this section, we evaluate the described ray tracing algorithm using several scenes on a machine with one NVIDIA GTX 285 GPU.
Our evaluation consists of two parts. Rendering performance andquality comparisons are reported in Section 5.1, and statistical dataobtained through controlled study are analyzed in Section 5.2.
We compare our algorithm with the INTERVAL and INTERLEAVEUVT rasterizers described in Fatahalian et al. [2009]. Codeoptimized GPU implementations of the rasterizers are used in thecomparisons. The rasterizers do not perform any occlusion culling,as GPU occlusion culling in the presence of defocus and motion
blur is a challenging problem in itself. Note that both rasterizers make performance/quality tradeoffs. The INTERVAL rasterizer
splits the sampling domain to S intervals and uses jittered stratified

Micropolygon Ray Tracing With Defocus and Motion Blur(a) Furball Family, defocus
17.6M mpolys, 1280 × 960 (13 × 13)
14.3 mpolys per pixel(b) Ladybug, defocus
24.1M mpolys, 1280 × 960 (23 × 23)
19.6 mpolys per pixel

•

64:7

(c) Fairy, defocus + motion blur
5.96M mpolys, 1280 × 720 (13 × 13)
6.47 mpolys per pixel

Figure 7: Images and statistics of several test scenes. “mpolys” is the total number of micropolygons in the scene.

Our RAYTRACE
INTERVALINTERLEAVEUVT, k = 2
INTERLEAVEUVT, k = 4

DOF (a) MB (b) DOF + MB (c)
10.5
13.2
17.2
42.9
18.6
91.9
77.1
68.7
80.7
261.3
227.8
266.8

Table 1: Render time (in seconds) for all method/effect combinations shown in Fig. 6.

sampling to generate a subpixel sample in each interval. We set S
to be the same as our super-sampling rate. Jittering allows aliasfree rendering of individual effects. However, INTERVAL always
pairs the same time region with the same lens region. This pairing
creates correlation between defocus and motion blur and may result in aliasing if both effects are combined. The INTERLEAVEUVT
rasterizer disables jittering and uses a fixed number of subpixellens-motion tuples in the entire screen while allowing each pixel
to contain a different set of tuples. The lack of jittering produces
aliasing and the algorithm hides aliasing by permutating tuple-pixel
assignments. The amount of subpixel-lens-motion tuples is controlled by a parameter called tile size. In the following we use theletter k to represent tile sizes. Increasing k improves quality while
also increasing render time.
Four test scenes are used in our evaluation:• Furball Family shown in Fig. 7(a). A static scene of two furballs rendered with only defocus. The scene contains 495K
transparent hairs. The marble floor is reflective.
• Ladybug shown in Fig. 7(b). A flower field with a ladybug and a
few dewdrops. The scene has multiple layers of grass and flowers. Out-of-focus dewdrop highlights produce hexagonal bokeh
effects. Some mild HDR glow effects are added as a postprocess.

Our RAYTRACE
INTERVALINTERLEAVEUVT, k = 2
INTERLEAVEUVT, k = 4

Furball Ladybug Fairy Car
52.7
44.4
10.9 28.2
119.3
163.4 32.3 178.0
57.5
148.1 20.2 214.4
155.9
484.4 64.2 710.6

Table 2: Sampling time (in seconds) for all test scenes. For animations, only the statistics of the frame shown in Fig. 7 or Fig. 1 isreported.

Tessellation
Shading
Sampling
Composition
Total

Furball
1.4
8.1
52.7
158.8
221.0

Ladybug
2.6
81.0
44.4
5.5
133.5

Fairy
0.1
7.7
10.9
44.6
63.3

Car
1.1
213.2
28.2
15.9
258.4

Table 3: Total render time and per-stage time of our renderingsystem for all test scenes. All timings are in seconds.

5.1

Quality and PerformanceFig. 6 illustrates the rendering quality of our method and therasterization-based approaches under different effect combinationsin the Car scene. Render time for the images in Fig. 6 is provided inTable 1. Our method consistently achieves higher performance than
the rasterization-based approaches. Compared with INTERVAL, ourmethod does not produce aliasing artifacts for combined defocus
and motion blur effects and achieves higher performance. For relatively mild, non-combined effects, our method and INTERVAL arecomparable. Compared with INTERLEAVEUVT, our method produces less noise and achieves significantly higher performance thanhigh-quality settings of INTERLEAVEUVT.

• Fairy shown in Fig. 7(c). We exported 189 frames of the Fairy
animation in the Utah Animation Repository. The scene contains a dancing fairy, a dragonfly flying in and out of focus and amoving camera.

Table 2 shows the sampling time for the test scenes. All scenes are
rendered within a few minutes at supersampling rates above 11×11,
PRMan’s “production” preset. As illustrated, our method is up to
an order of magnitude faster than INTERLEAVEUVT with k = 4
and several times faster than INTERVAL. The total render time andper-stage time of our rendering system are also reported in Table 3.

• Car shown in Fig. 1. A car driving in a tunnel. The defocus
blur of distant and bright traffic lights requires very high supersampling to render smoothly. The body of the car is reflective.
The scene contains ambient occlusion rendered using a GPU implementation of the point-based approximate color bleeding algorithm [Christensen 2008]. HDR glow effects are added as a
postprocess.

We evaluate the efficiency of our OBB hyper-trapezoid BVH bycomparing with alternative acceleration structures, including a simple 4D AABB BVH, an AABB-based hyper-trapezoid BVH and agreedy SAH BVH. The topology of all BVHs are the same. Table 4shows the comparison results. As illustrated, the hyper-trapezoid
is orders of magnitude more efficient than simple 4D AABBs. Up
to 200× traversal speedups have been observed for high-motion
ACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

64:8

•

Q. Hou et al.

Ours
AABB Hyper.
3D/4D AABB
No parametric-space split
No orientation-aware split
No orientation
propagation
No ray sort

Build
Trace
Build
Trace
Build
Trace
Build
Trace
Build
Trace
Build
Trace
Trace

Furball

Ladybug

Fairy

Car

Furball

5.0
47.6
4.4
62.3
51.5
60.9
5.1
47.6
5.1
43.6
51.2

6.7
38.2
5.6
79.2
67.8
84.0
6.8
42.9
6.6
57.2
38.1

0.8
10.0
0.7
13.5
0.7
16.9
8.2
10.0
0.8
10.0
0.7
10.3
10.2

4.6
23.5
3.6
60.0
3.7
5077.4
104.3
53.0
4.7
23.5
4.3
26.7
23.3

RAYTRACE
INTERVAL
UVT-2
UVT-4

Table 4: Build and trace time comparison for our OBB hypertrapezoid BVH, AABB hyper-trapezoid BVH, 3D/4D AABB BVH
and several other alternative build/trace schemes. All timings are
in seconds. For defocus-only scenes, our approach falls back to
OBBs and we only compare with 3D AABB BVH. For motion blur
scenes, we compare with 4D AABB BVH.

scenes like Car. OBB hyper-trapezoids also achieve significant
traversal speedups compared with AABB hyper-trapezoids. The
construction time for all other BVHs only takes a small fraction of
the total rendering time and the difference in construction time isnegligible with respect to the choice of bounding shapes.
We also evaluate the performance impact of several algorithmic optimizations by comparing build/trace time with individual optimizations disabled. As illustrated in Table 4, the parametric-space split
is the most critical part of our algorithm. Without it, the BVH construction time is significantly increased and ray tracing time is also
increased. The orientation propagation helps traversal performance
considerably for most scenes. The orientation-aware split is mainly
a fallback for special cases and it only helped the Ladybug scene.
The performance impact of ray pre-sorting depends on the percentage of blurry pixels and blur radius. In some cases (e.g., Ladybug
and Car) the cost of sorting rays may cancel out the benefit of coherence improvement.
The peak memory consumption of our algorithm is about 10 bytes
per micropolygon during BVH construction and 650 bytes per ray
during ray traversal with the input data allocated by the Reyes
pipeline excluded. Assuming 100MB GPU memory is available
in the sampling stage, we are able to process millions of micropolygons and hundreds of thousands of rays in parallel, which is
sufficient for full utilization of modern GPUs.
Note that all algorithms implemented in this paper consume allavailable GPU memory to process as many micropolygons andrays as possible in parallel to maximize the rendering performance.
We utilize the dynamic scheduling system described in RenderAnts [Zhou et al. 2009] to recursively subdivide the rendering region until the memory required by an algorithm is less than theavailable GPU memory. As a result, the memory consumption differences between the algorithms are converted to execution timedifferences.
Our algorithm is designed for off-line software rendering and it
does not necessarily perform well under real-time level parametersettings. One important reason is that the BVH construction becomes a major bottleneck at lower sampling rates. Table 5 shows
the ray-tracing/rasterization performance comparison for several
scenes at various polygon sizes (controlled via shading rates) andsampling rates. As illustrated, INTERLEAVEUVT becomes fasterthan ray tracing at lower sampling rates. However, our ray tracing
ACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

Ladybug
RAYTRACE
INTERVAL
UVT-2
UVT-4

Fairy
RAYTRACE
INTERVAL
UVT-2
UVT-4

Car
RAYTRACE
INTERVAL
UVT-2
UVT-4

1×1
5.2
18.7
0.6
1.2
1×1
3.0
7.2
0.5
1.1
1×1
1.0
3.6
0.2
0.4
1×1
4.4
13.5
0.8
1.7

4×4
10.2
34.6
5.6
15.0
4×4
4.2
15.8
4.6
15.0
4×4
1.9
7.9
1.9
6.1
4×4
5.3
9.3
6.8
21.6

8×8
24.9
65.2
21.9
59.1
8×8
7.9
32.9
17.9
59.4
8×8
4.5
16.5
7.7
24.3
8×8
7.5
24.4
26.0
85.2

Ref
52.7
119.3
57.5
155.9
Ref
44.4
163.4
148.1
484.4
Ref
10.9
32.3
20.2
64.2
Ref
28.2
178.0
214.4
710.6

SR×4
64.4
74.0
33.3
70.2
SR×4
40.7
137.3
124.4
406.9
SR×4
8.4
15.6
9.3
23.9
SR×4
24.3
57.0
53.2
177.7

SR×16
153.4
71.6
31.6
52.2
SR×16
38.1
52.3
35.0
74.6
SR×16
7.7
11.3
5.7
11.7
SR×16
24.7
27.8
28.3
72.5

Table 5: Performance comparison at different sampling rates andshading rates (i.e., polygon sizes). The 1×1, 4×4, 8×8 numbers
are sampling rates. SR×4 means 4× polygon size, i.e., 4× coarser
shading rate. SR×16 means 16× polygon size. The “Ref” column
contains the reference performance data where sampling/shading
rate settings are the same as the measurements in Table 2. The
detailed shading rate assignment is: Furball (0.8), Ladybug (1 forgrass and sky, 0.1 for ladybug, flowers and dewdrops), Fairy (0.3),
Car (0.2).

remains faster than INTERVAL as low sampling rates lead to fewer
intervals and more bloated bounding boxes.
Polygon sizes have different impacts on ray tracing and rasterizers. For ray tracing, polygon sizes take effect indirectly by affecting the memory access coherence during BVH traversal. Larger
polygons make ray-micropolygon intersection tests more coherent.
However, they are more likely to overlap and harder to separate during BVH construction, decreasing the BVH quality. Furball is anextreme example of BVH quality degradation for larger polygons.
Rasterizers are significantly more efficient for larger and coarser
polygons. It should be noted that the shading rates in our scenes
are manually tweaked by our artist. Specifically, as Reyes only
computes shading at micropolygon vertices, the artist purposefully
over-tessellated reflective/bumpy objects to improve shading antialiasing. At the coarser shading rates where rasterizers become efficient, bumpy faces look flat and the reflections/refractions containsevere aliasing artifacts. Therefore, such settings are not suitablefor off-line rendering.

5.2

Controlled Study

Our controlled studies are performed in a stand-alone program using a simple test scene shown in Fig. 8 in order to minimize theinfluence of external factors. The simple scene does not require thevarious scheduling operations in a Reyes pipeline to render and its
motion and defocus scales may be easily controlled.
To evaluate the SAH approximation accuracy of the parametricspace split algorithm in our bottom-level BVH construction, we
tested the algorithm on the micropolygon grids in the halberd scene.
For each grid, we compute the relative difference in SAH cost between our approximation and the greedy SAH optimization in WaldMicropolygon Ray Tracing With Defocus and Motion Blur
Raytrace

Interval•

64:9InterleaveUVT

35

Render Time (s)

30
25
20
15
10
5
0
0

20

40

60

80

100

120

140

160

180

8

9

Motion scale in pixels
60
400

Zoom out(a) Perfect focus

Render Time (s)50(b) Defocus + Motion blur

Figure 8: The simple scene used for controlled study.

40
0

30
20
10

2800

0

2400

0

Grid count

2000

1

2

3

4

5

6

7

Defocus scale

1600

Figure 10: Render time at different motion and defocus scales.
Top: fixed defocus scale and varied motion scale. Bottom: fixedmotion scale and varied defocus scale.

1200
800
400
0
-100% -80%

-60%

-40%

-20%

0%

20%

40%

60%

80%

100%

6

Conclusion and Future Work

SAH Difference

Figure 9: Relative SAH difference distribution in SAH approximation evaluation. A negative value indicates our method has smaller
SAH costs.

et al. [2007]. Since the original greedy optimization only considers axis-aligned splits, we modify it to consider splits aligned witheach grid’s final bounding box orientation to make the comparison
fair. For simplicity, the comparison is performed in 3D without
regarding motion blur. Fig. 9 illustrates the distribution of the relative differences. Negative values indicate that our method produces
smaller SAH costs. The average difference is −7.4%. We outperform the greedy SAH optimization in 75% of the cases, and perform no worse than 20% in 94% of the cases. The minimum andmaximum differences are −76% and +101% respectively. This
comparison demonstrates that our parametric space split performs
competitively to the greedy SAH optimization, and may achieve
better results in certain cases.
Theoretically, the time complexity of our ray tracing algorithm
stays constant with respect to motion and defocus scales. In practice, however, our GPU implementation suffers from decreased
control flow and memory coherence as the motion and defocus scale
increases. To evaluate such behaviors, we plot the render time of INTERVAL, INTERLEAVEUVT (k = 4) and our algorithm at different
motion and defocus scales. The render times are for the halberd
scene at motions of 0 − 190 pixels and 0 − 9.5× defocus scales.
Larger defocus scales correspond to larger circles of confusion. As
illustrated in Fig. 10, compared with INTERVAL, the render timeof our method is significantly less sensitive to the defocus scale
and we are able to achieve higher speedups for large defocus blurs.
Compared with INTERLEAVEUVT (k = 4), our method is moresensitive to motion and defocus scales. Nevertheless, our rendertime does not degrade in an unbounded manner like INTERVAL andour method remains faster than INTERLEAVEUVT even at extreme
motion and defocus scales.

We have presented a micropolygon ray tracing algorithm that ismore efficient than existing rasterization-based methods for rendering high quality defocus and motion blur effects. To the best of
our knowledge, this is the first ray tracing algorithm with on-thefly acceleration structure construction that outperforms the stateof-the-art rasterization methods under certain circumstances (i.e.,high quality defocus and motion blur). We are able to eliminate thequality-performance tradeoff in defocus and motion blur renderingand provide maximum quality with superior performance.
Although our tracing algorithm greatly accelerates the samplingstage, the speedup in overall rendering time may not be significant
if rendering cost is dominated by very complicated shaders, as is
typically the case in off-line movie rendering systems. But for simpler shaders, the speed-ups can be significant. In both cases, our ray
tracing algorithm serves as a competitive alternative to rasterizationand can fundamentally dictate the design of the remainder of thesesystems.
One limitation of our algorithm is the inefficiency of transparency
handling. While our algorithm is able to process large sets oftransparent samples in-core, our cost of processing each transparent
sample is higher than rasterizers. The BVH becomes considerably
less efficient in pruning intersection tests when tracing rays inside
objects. Improving ray tracing performance for transparent scenes
is an interesting direction for future work.
There are a number of future work directions in addition to improving transparency efficiency. First, we are interested in combining
recent adaptive sampling techniques [Hachisuka et al. 2008; Overbeck et al. 2009] with our ray tracing pipeline. Such combination
would combine the strengths of adaptive sampling and shadingsampling decoupling in micropolygon pipelines to further accelerate the rendering. Second, faster micropolygon BVH construction
suitable for realtime ray tracing is also an interesting research direction.
ACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

64:10•Q. Hou et al.

Acknowledgements
We would like to thank the anonymous reviewers for their helpful comments, Shuitian Yan for artistry support, and Steve Lin for
proofreading this paper. Kun Zhou was partially funded by the NSF
of China (No. 60825201).

References
A ILA , T., AND L AINE , S. 2009. Understanding the efficiency of
ray traversal on GPUs. In Proceedings of HPG ’09, ACM, New
York, NY, USA, 145–149.
C HRISTENSEN , P. H., L AUR , D. M., F ONG , J., W OOTEN , W. L.,
AND BATALI , D. 2003. Ray differentials and multiresolution geometry caching for distribution ray tracing in complex scenes. In
Proceedings of Eurographics 2003, Blackwell Publishers, 543–
552.
C HRISTENSEN , P., F ONG , J., L AUR , D., AND BATALI , D. 2006.
Ray tracing for the movie ‘cars’. In Proceedings of IEEE Symposium on Interactive Ray Tracing, 1–6.
C HRISTENSEN , P. H. 2008. Point-based approximate color bleeding. Tech. rep., Pixar Technical Memo #08-01.
C OOK , R. L., P ORTER , T., AND C ARPENTER , L. 1984. Distributed ray tracing. SIGGRAPH Comput. Graph. 18, 3, 137–
145.
C OOK , R. L., C ARPENTER , L., AND C ATMULL , E. 1987.
The Reyes image rendering architecture. SIGGRAPH Comput.
Graph. 21, 4, 95–102.
C OOK , R. L., P ORTER , T. K., AND C ARPENTER , L. C., 1993.
Pseudo-random point sampling techniques in computer graphics,
US Patent 5239624.
C OOK , R. L. 1986. Stochastic sampling in computer graphics.
ACM Trans. Gr. 5, 1, 51–72.
D EMERS , J. 2004. Depth of field: A survey of techniques. GPU
Gems, 375–390.
E GAN , K., T SENG , Y.-T., H OLZSCHUCH , N., D URAND , F., AND
R AMAMOORTHI , R. 2009. Frequency analysis and sheared reconstruction for rendering motion blur. ACM Trans. Gr. 28, 3,
1–13.
FATAHALIAN , K., L UONG , E., B OULOS , S., A KELEY, K.,
M ARK , W. R., AND H ANRAHAN , P. 2009. Data-parallel rasterization of micropolygons with defocus and motion blur. In
Proceedings of HPG ’09, 59–68.
F ISHER , M., FATAHALIAN , K., B OULOS , S., A KELEY, K.,
M ARK , W. R., AND H ANRAHAN , P. 2009. Diagsplit: parallel, crack-free, adaptive tessellation for micropolygon rendering.
ACM Trans. Graph. 28, 5, 1–10.
G LASSNER , A. S. 1988. Spacetime ray tracing for animation.
IEEE Comput. Graph. Appl. 8, 2, 60–70.
H ACHISUKA , T., JAROSZ , W., W EISTROFFER , R. P., DALE , K.,
H UMPHREYS , G., Z WICKER , M., AND J ENSEN , H. W. 2008.
Multidimensional adaptive sampling and reconstruction for ray
tracing. ACM Trans. Gr. 27, 3, 1–10.
H AEBERLI , P., AND A KELEY, K. 1990. The accumulation buffer:
hardware support for high-quality rendering. In Proceedings of
ACM SIGGRAPH ’90, 309–318.
ACM Transactions on Graphics, Vol. 29, No. 4, Article 64, Publication date: July 2010.

H OU , Q., Z HOU , K., AND G UO , B. 2008. BSGP: Bulksynchronous GPU programming. ACM Trans. Gr. 27, 3, 9.
H SIEH , P., 2004. Hash functions.
http://www.azillionmonkeys.com/qed/hash.html.
H UBBARD , P. M. 1995. Collision detection for interactive graphics
applications. IEEE TVCG 1, 3, 218–230.
I ZE , T., WALD , I., AND PARKER , S. G. 2008. Ray tracing with
the BSP tree. In Proceedings of IEEE Symposium on Interactive
Ray Tracing, 159–166.
K ASS , M., L EFOHN , A., AND OWENS , J. 2006. Interactive depthof field. Tech. rep., Pixar Technical Memo #06-01.
L AUTERBACH , C., G ARLAND , M., S ENGUPTA , S., L UEBKE , D.,
AND M ANOCHA , D. 2009. Fast BVH construction on GPUs.
Computer Graphics Forum 28, 2, 375–384.
L EE , S., E ISEMANN , E., AND S EIDEL , H.-P. 2009. Depth-offield rendering with multiview synthesis. ACM Trans. Gr. 28, 5,
1–6.
M ORTON. 1966. A computer oriented geodetic data base and a
new technique in file sequencing. Tech. Rep. Ottawa, Ontario,
Canada.
OVERBECK , R. S., D ONNER , C., AND R AMAMOORTHI , R. 2009.
Adaptive wavelet rendering. ACM Trans. Graph. 28, 5, 1–12.
PATNEY, A., AND OWENS , J. D. 2008. Real-time reyes-style
adaptive surface subdivision. ACM Trans. Gr. 27, 5, 1–8.
S HEVTSOV, M., S OUPIKOV, A., AND K APUSTIN , A. 2007.
Highly parallel fast kd-tree construction for interactive ray tracing of dynamic scenes. In Proceedings of Eurographics ’07,
395–404.
S HIRLEY, P., AND C HIU , K. 1997. A low distortion map between
disk and square. Journal of Graphics Tools 2, 3, 45–52.
S OLER , C., S UBR , K., D URAND , F., H OLZSCHUCH , N., ANDS ILLION , F. 2009. Fourier depth of field. ACM Trans. Gr. 28, 2,
1–12.
S UNG , K., P EARCE , A., AND WANG , C. 2002. Spatial-temporalantialiasing. IEEE TVCG 8, 2, 144–153.
WALD , I., B OULOS , S., AND S HIRLEY, P. 2007. Ray tracing
deformable scenes using dynamic bounding volume hierarchies.
ACM Trans. Gr. 26, 1, 6.
WALD , I. 2007. On fast construction of SAH-based bounding
volume hierarchies. In Proceedings of IEEE Symposium on Interactive Ray Tracing, 33–40.
W EISSTEIN , E. W. Magic square.
http://mathworld.wolfram.com/MagicSquare.html.
Z HOU , K., H OU , Q., WANG , R., AND G UO , B. 2008. Real-time
kd-tree construction on graphics hardware. ACM Trans. Gr. 27,
5, 126.
Z HOU , K., H OU , Q., R EN , Z., G ONG , M., S UN , X., AND G UO ,B. 2009. RenderAnts: interactive Reyes rendering on GPUs.
ACM Trans. Gr. 28, 5, 1–11.