Game Engine Gems 2

 119

8

ImplementingaFastDDOFSolver

Holger Grün

Advanced Micro Devices, Inc.

This gem presents a fast and memory-efficient solver for the diffusion depth-of-

field (DDOF) technique introduced by Michael Kass et al. [2006] from Pixar.

DDOF is a very high-quality depth-of-field effect that is used in motion pictures.

It essentially works by simulating a heat diffusion equation to compute depth-of-

field blurs. This leads to a situation that requires solving systems of linear

equations.

Kass et al. present an algorithm for solving these systems of equations, but

the memory footprint of their solver can be prohibitively large at high display

resolutions. The solver described in this gem greatly reduces the memory foot-

print and running time of the original DDOF solver by skipping the construction

of intermediate matrices and the execution of associated rendering passes. In con-

trast to the solver presented by Shishkovtsov and Rege [2010], which uses Di-

rectX 11, compute shaders, and a technique called parallel cyclic reduction

[Zhang et al. 2010], this gem utilizes a solver that runs only in pixel shaders and

can be implemented on DirectX 9 and DirectX 10 class hardware as well.

8.1Introduction

DDOF essentially relies on solving systems of linear equations described by

tridiagonal systems like the following:

11 1 1

222 2 2

333 3 3

0

0

nn n n

bc y x

abc y x

abc y x

ab y x



  





  





  





  







  





  





  





  



  

. (8.1)

120 8.ImplementingaFastDDOFSolver

It needs to solve such a system of equations for each row and each column of the

input image. Because there are always only three coefficients per row of the ma-

trix, the system for all rows and columns of an input image can be packed into a

four-channel texture that has the same resolution as the input image.

The

i

x

represent the pixels of one row or column of the input image, and the

i

y

represent the pixels of one row or column of the yet unknown image that is

diffused by the heat equation. The values

i

a

,

i

b

, and

i

c

are derived from the circle

of confusion (CoC) in a neighborhood of pixels in the input image [Riguer et al.

2004]. Kass et al. take a single time step from the initial condition

ii

y

x and

arrive at the equation













111ii ii i i ii

yx

β

yyβ yy





   . (8.2)

Here, each

i

β

represents the heat conductivity of the medium at the position i.

Further on,

0

β

and

n

β

are set to zero for an image row of resolution n so that the

row is surrounded by insulators. If one now solves for

i

x

, then the resulting equa-

tion reveals a tridiagonal structure:





11 1 1

1

iii ii iii

x

β

y ββ y β y



 

     . (8.3)

It is further shown that

i

β

is the square of the diameter of the CoC at a certain

pixel position i. Setting up

i

a

,

i

b

, and

i

c

now is a trivial task.

As in Kass et al., the algorithm presented in this gem first calculates the dif-

fusion for all rows of the input image and then uses the resulting horizontally-

diffused image as an input for a vertical diffusion pass.

Kass et al. use a technique called cyclic reduction (CR) to solve for the

i

y

.

Consider the set of equations

12 11 1 1

11

111121

.

ii ii ii i

ii ii ii i

ii ii ii i

ay by cy x

ay by cy x

ay by cy x

   





  

 

 



(8.4)

CR relies on the simple fact that a set of three equations containing five un-

knowns

2i

y



,

1i

y



,

i

y

,

1i

y



, and

2i

y



, like those shown in Equation (8.4), can be

reduced to one equation by getting rid of

1i

y



and

1i

y



. This is done by multiply-

ing the first equation by

1ii

ab





and multiplying the third equation by

1ii

cb





to

produce the equations