Graphics Reference
In-Depth Information
D
UV
O
'
UV
D
UV
O
UV
O
UV
Figure 2.7.
Epipolar slice origin and direction in shadow map
UV
space as well as
locations of sampling points for creating min/max trees.
2.7.2 Constructing Min/Max Trees
To construct a binary tree for the slice, we need to define the intersection of the
slice with the shadow map. Since all camera rays in the slice project onto this
line, this can be done by taking any two points on the ray and transforming them
into the shadow map
UV
space. In our implementation, we use camera location
as the first point. Its projected position
O
UV
gives us the zeroth sample in the
1D height map. To compute the direction
D
UV
, we take the termination point of
the ray casted through the slice exit point, transform it into the
UV
space and
compute direction from
O
UV
to the resulting point. Then we normalize
D
UV
so that the maximum of its projections on
u
and
v
axes equals 1. If
O
UV
falls
outside the shadow map boundary [0
,
1]
[0
,
1] (which is a very common case in
multi-cascade set-up), we continue the line along the
D
UV
and move the origin
to the first intersection with the boundary (Figure 2.7, right).
Now when we know the location
O
UV
of the zeroth sample in the 1D height
map and direction
D
UV
, we can determine the location of
i
ith sample as
O
UV
+
i
×
D
UV
. The first level of the tree can be constructed by computing the min/max
of every 2
i
th and (2
i
+ 1)th samples. All the coarser levels can be built by
propagating these min/max values upwards. As Figure 2.7 shows, the locations
of the original samples on the shadow map do not fall in texel centers. To obtain
correct results, we compute the conservative min/max bound by considering the
nearest four samples, which would be used for PCF filtering (see Section 2.8).
Note that the number of samples in the 1D height map built as described above
is always not greater than the maximum shadow map dimension.
·
2.7.3 Ray Marching with 1D Min/Max Trees
In our optimized ray marching algorithm we adopted the method proposed by
Tevs et al. [Tevs et al. 08] and reused by Chen et al. [Chen et al. 11]. Min/max
tree traversal is implemented without recursion in this method. Transitions to
coarser levels are performed one at a time so that the transition from level
l
to
