Publication: SPIE Proc. Practical Holography XIX: Materials and Applications, SPIE#5742, San Jose, California, 25–32(2005).

25

Exact hidden-surface removal in digitally synthetic
full-parallax holograms
K. Matsushimaaa Department of Electrical Engineering and Computer Science, Kansai University

Yamate-cho 3-3-35, Suita, Osaka 564-8680, Japan
ABSTRACTA new algorithm for removing hidden surfaces from reconstruction of computer-generated holograms is presented.
The object used in the algorithm is deﬁned by surface model and each polygon composing the object provides amask for blocking the incident ﬁeld into the backside of the polygon. The computational cost of the proposed
algorithm is 2 FFT/polygon by handling ﬁeld transmission in Fourier space and integrating the surface diﬀraction
method for generating ﬁelds. Reconstruction of a hologram synthesized by using the presented algorithm isdemonstrated.
Keywords: Hidden surface removal, Computer generated hologram, digitally synthetic hologram, surface diﬀraction method

1. INTRODUCTION
In the CGHs, algorithms for hidden-surface removal found in literature are either the geometrical method1, 2
suitable for the ray tracing in the point-source model or the wave optical method based on layered model.3 The
former is usually much time-consuming algorithm and only handle horizontal-parallax-only holograms, i.e., it can
not deal with full-parallax holograms. The latter, proposed by A. Lohmann, is capable of removing hidden partfrom reconstruction of full-parallax holograms, but the objects must be sliced in planes parallel to the hologram.
Thus, it is diﬃcult to apply some standard rendering techniques used for realistic reconstruction of 3-D objects,
such as shading and texture mapping.
In the last meeting, we presented a novel algorithm for hidden-surface removal.4 The algorithm basedon the rotational transformation5 of wave ﬁelds has resulted in a method by silhouette approximation. The
presented algorithm is simple in principle and able to using for full-parallax holograms. However, the silhouetteapproximation is valid under paraxial conditions, i.e., utilization of the silhouette approximation is limited inholograms with narrow viewing zone.
In this report, more exact algorithm is presented for hidden-surface removal. This new method is also basedon the rotational transformation of wave ﬁelds, as well as the former algorithm, but do not use the Silhouetteapproximation. The proposed new algorithm rigorously calculates obstruction of the ﬁeld by a tilted surface.
Further author information:
E-mail: matsu@kansai-u.ac.jp, Telephone/Fax: +81-6-6368-0933

(a)

(b)

(c)

Figure 1. The principle of painter’s algorithm.

26

Publication: SPIE Proc. Practical Holography XIX: Materials and Applications, SPIE#5742, San Jose, California, 25–32(2005).

(a)hˆn ( xˆ , yˆ )hˆn+1 ( xˆ , yˆ )hˆn ( xˆ , yˆ )(a)Emissive cross sectionhˆn+1 ( xˆ , yˆ )Emissive Surface
Silhouette Mask

Sectional mask

(b)

(b)

ObjectObjectHologram

Hologram

Obstructed fields
Unobstructed fields

Leakage fields

Figure 2. The principle of algorithm used in layered
holograms.

Figure 3. The principle of algorithm based on silhouette approximation.

This kind of rigorous obstruction, in general, leads to a high computational cost. For example, it requires FFT
operation four times to process ﬁeld-obstruction by a surface. However, the presented algorithm can reduce thecomputational cost to 2 FFT/Surface by handling ﬁeld transmission in Fourier space instead of real space.

2. LAYERED HOLOGRAMS AND SILHOUETTE APPROXIMATION
Painter’s algorithm, a well-known method for removing hidden surface in the ﬁeld of computer graphics (CG),gets its name from the process that painters render a scene in paints. Fig.1 (a)–(c) show the principle of painter’salgorithm. An artist might draws the background scenery such as mountains or a forest in their canvas ﬁrst andthe foreground objects last. This is a very simple and primitive method for hidden surface removal.
Mechanism of hidden surface removal in layered holograms and algorithm by using the silhouette approximation4 are analogous with the painter’s algorithm. In these methods, an object is composed of planes, i.e. planar
surfaces or cross sections. These planes are sorted by depth so that the calculation of the object ﬁelds proceedsfrom farthest to closest to the hologram.

2.1. Layered holograms
An object sliced in several planes parallel to the hologram. The planes are sorted in depth order, and eachcross section functions as a mask blocking the incident ﬁeld and plays the role of a light source. The planes arenumbered 1 to N from farthest to closest to the hologram. When a ﬁeld ĥn (x̂, ŷ) comes into the nth plane asshown in Fig.2 (a), ﬁeld passing through the nth plane is given byĥ (x̂, ŷ) = ĥn (x̂, ŷ)m̂n (x̂, ŷ),(1)where m̂n (x̂, ŷ) is a mask function that is unity within the cross section of the object or zero otherwise.
A cross section works not only as the mask but also a light source. If complex amplitudes of the light source
on a cross section is given by ô(x̂, ŷ) in the nth plane. The incident ﬁeld of the (n + 1)th plane is written asĥn+1 (x̂, ŷ)= Pdn {ĥn (x̂, ŷ) + ôn (x̂, ŷ)}= Pdn {ĥn (x̂, ŷ)m̂n (x̂, ŷ) + ôn (x̂, ŷ)},(2)

Publication: SPIE Proc. Practical Holography XIX: Materials and Applications, SPIE#5742, San Jose, California, 25–32(2005).

27

Figure 4. Gaps owing to leakage fields between silhouette masks.4

where Pd {u(x̂, ŷ)} is deﬁned as the propagation operator of the ﬁeld u(x̂, ŷ) in distance d.
The object ﬁeld is calculated from ĥ1 (x̂, ŷ) = ô1 (x̂, ŷ) to ĥN (x̂, ŷ) as if an artist paints his picture, as shownin Fig.2 (b), and ﬁnally obtained in the hologram plane as follows:ĥHologram (x̂, ŷ) = PdN {ĥN (x̂, ŷ)m̂N (x̂, ŷ) + ôN (x̂, ŷ)}.

(3)2.2. Silhouette approximation in surface objects
Main drawback of the simple layered holograms is that object must be sliced in a set of planes parallel to thehologram. Since any surfaces are not deﬁned in this object model, it is diﬃcult to render the object by using
several major techniques such as shading or texture mapping.
For surface objects, ray-oriented algorithm for hidden surface removal has been reported in several literature,
but these are generally too slow to apply for full-parallax holograms, and therefore, used only for horizontal
parallax only holograms.
Algorithm based on silhouette approximation was proposed for full-parallax synthetic holograms of surface
objects. The idea is very simple. Suppose that an object is constructed of many planar surface, polygon, andnumbered in order of depth. A part of the incident ﬁeld into backside of a polygon is clipped out by a mask thatis the silhouette of the polygon as shown in Fig. 3 (a).
The ﬁeld obstructed by the silhouette mask is given asĥn (x̂, ŷ) = ĥn (x̂, ŷ)m̂s,n (x̂, ŷ),(4)

where m̂s,n (x̂, ŷ) denotes a function of the silhouette mask for the nth surface, which is the silhouette of thepolygon onto a plane parallel to the hologram.
The ﬁeld emitted from the polygon itself must be calculated by using some ordinal methods, for example,
superposition of spherical waves from point sources ﬁlled in the polygon. Suppose that the ﬁeld generated fromthe nth polygon is given as O(x̂, ŷ) in the next (n + 1)th plane. The recurrence formula is given as follows:ĥn+1 (x̂, ŷ) = Pdn {ĥn (x̂, ŷ)m̂s,n (x̂, ŷ)} + O(x̂, ŷ).

(5)2.3. Rigorous hidden surface removal for surface objects
If the ﬁeld is paraxial, i.e. the light propagate almost along the optical axis, the silhouette approximation is agood trade-oﬀ between the computational cost and quality of the reconstructed image. However, if viewing zoneof a hologram is enough large for the hologram to reconstruct the auto-stereoscopic image, the ﬁeld is no longer
paraxial, and therefore leakage ﬁelds passing through the gap between silhouette masks increase as shown in
Fig. 3 (b).
An example of leakage of ﬁelds is shown in Fig. 4. In this case, the light emitted from the farside of theobject passes through the inside of the object and is observed in reconstruction. Since the light from the farside

28

Publication: SPIE Proc. Practical Holography XIX: Materials and Applications, SPIE#5742, San Jose, California, 25–32(2005).

(a)

(a)
R Rotation

Fourier
space

Emissive Surface
Surface Mask

Real
space

(b)

F

F -1

hˆ( xˆ , yˆ )h ( x, y )Complexamplitude(b)

ObjectFourier
space Rotation
Real
space

Hologram
Obstructed fields
Unobstructed fieldsFhˆ( xˆ , yˆ )Translational
propagationRP( d )

Complexamplitude

F -1
h ( x, y )Figure 6. A diagram of steps to perform rotational transformation without (a) and with (b)translational propagation.

Figure 5. The principle of complete blocking the fields thatshould be obstructed.

spreads inside the object and its intensity is weaker than that on the surface of the nearside, the leakage ﬁeld isobserved as a dark gap between polygons.
More exact methods are required for preventing leakage and blocking the ﬁelds completely. Fig. 5 shows theprinciple of the exacter method. An incident ﬁeld into the backside of a polygon is obstructed by a tilted mask,of which shape and position is same as the polygon itself. There is not any gap that ﬁelds pass through.
An procedure for realizing the ﬁelds obstruction by tilted masks is described in the following section.

3. OBSTRUCTION BY A TILTED PLANE
We have already reported the basic procedure for obstruction by a tilted mask in the last meeting (Ref. 4). Let
us summarize this for convenience bellow.

3.1. Rotational transformation
Complex amplitudes of an incident ﬁeld in a plane not parallel to the hologram must be obtained to block
the incident ﬁeld by a tilted polygon. The rotational transformation of a ﬁeld given in a local parallel plane(x̂, ŷ, ẑ = 0) is written as(6)h(x, y) = F −1 Rψ F {ĥ(x̂, ŷ)},where (x, y, z = 0) is a tilted plane in which a polygon is laid and h(x, y) is the complex amplitudes of the ﬁeld
on it. Here, F {·} and F −1 {·} denote Fourier and inverse Fourier transformation, respectively, as follows:Ĥ(û, v̂) =h(x, y) =F {ĥ(x̂, ŷ)},F−1{H(u, v)}.

(7)
(8)

where (û, v̂) and (u, v) are Fourier coordinates in the parallel and the tilted plane to the hologram, respectively.
Suppose that a transformation matrix for coordinates rotation is deﬁned as
⎛ ⎞
⎛ ⎞
⎞
⎛
x̂
x
â1 â2 â3⎝ ŷ ⎠ = Tψ ⎝ y ⎠ , Tψ = ⎝ â4 â5 â6 ⎠ .
(9)â7 â8 â9ẑz

Publication: SPIE Proc. Practical Holography XIX: Materials and Applications, SPIE#5742, San Jose, California, 25–32(2005).

29

Rotational transformation in Fourier space is given as
H(u, v) ==Rψ {Ĥ(û, v̂)}(10)Ĥ(â1 u + â2 v + â3 w(u, v), â4 u + â5 v + â6 w(u, v)),(11)

where w(u, v) is Fourier frequency in z direction perpendicular to the tilted plane and given byw(u, v) = λ−2 − u2 − v 2 .

(12)

The computational process for the rotational transformation is summarized as a diagram shown in Fig. 6 (a).
If translational propagation of the ﬁeld follows rotational transformation, the propagated ﬁeld after rotation
is given by(13)h(x, y) = F −1 Rψ F {ĥ(x̂, ŷ)} × P(d) ,where P(d) = exp[i2πd(λ−2 −u2 −v 2 )1/2 ] is the phase factor in Fourier space to propagate the ﬁeld translationallyfor a distance of d.6 The diagram for the rotational transformation followed by translational propagation isshown in Fig. 6 (b).

3.2. Masking fields in the tilted plane
Fig. 7 (a) shows the procedure for masking a ﬁeld in a tilted plane. The mask function for the polygon must be
multiplied by the incident ﬁeld in the tilted plane that the polygon laid on. Therefore, when the ﬁeld ĥn (x̂, ŷ)denotes the incident ﬁeld into the backside of the nth polygon, the obstructed ﬁeld is given by use of eq. (6) as
follow:(14)hn (x, y) = F −1 R−ψn F {ĥn (x̂, ŷ)} × mn (x, y).
Complex amplitudes of the obstructed ﬁeld in a plane parallel to the hologram is obtained by inverse rotationof h (x, y).
ĥn (x̂, ŷ) ==(a)

F −1 R+ψn F {hn (x, y)}F −1 R+ψn F F −1 R−ψn F {ĥn (x̂, ŷ)} × mn (x, y)hˆn¢ ( xˆ , yˆ )¢ 1 ( xˆ , yˆ )hˆn+hˆn ( xˆ , yˆ )Ã+ÃOn ( x, y )(b)mn ( x, y )

(15)

+Ã

( x , y ,0)hn ( x, y )( xˆ , yˆ ,0)( x , y ,0)( xˆ , yˆ ,0)(c)
Fourier
space
Real
space

Rotation R-Ã

Rotation R+Ã

F

F -1

hˆn ( xˆ , yˆ )mn ( x, y )FMaskingP( d n)Translational
propagation

F -1
On ( xˆ , yˆ )Object fieldhˆn+1 ( xˆ , yˆ )Figure 7. The procedure for exact hidden surface removal: masking (a) and generating (b) a field, and the diagram forcomputation(c).

Publication: SPIE Proc. Practical Holography XIX: Materials and Applications, SPIE#5742, San Jose, California, 25–32(2005).

30

Furthermore, the obstructed ﬁeld in the next plane is given by substituting hn (x, y) of eq. (14) into (13) insteadof ĥ(x̂, ŷ) as follows:ĥn+1 (x̂, ŷ) = F −1 R+ψn F F −1 R−ψn F {ĥn (x̂, ŷ)} × mn (x, y) × P(d)(16)
As a result, the recurrence formula is given byĥn+1 (x̂, ŷ)= ĥn+1 (x̂, ŷ) + On (x̂, ŷ)= F −1 R+ψn F F −1 R−ψn F {ĥn (x̂, ŷ)} × mn (x, y) × P(dn ) + On (x̂, ŷ),(17)

where On (x̂, ŷ) given in the (n + 1) plane is again the ﬁeld emitted from the nth polygon as shown in Fig. 7 (b).
Computational procedure for calculating eq. (17) is indicated as a diagram shown in Fig. 7 (c)4. COMBINATION WITH THE SURFACE DIFFRACTION METHOD
A wave optical method to generate ﬁelds emitted from a surface object has been proposed.7, 8 In the method,
called surface diﬀraction method, an object are composed of some polygons, and ﬁelds from each polygons arecalculated by using the rotational transformation mentioned above. Therefore, the surface diﬀraction method
has close aﬃnity with the method for hidden surface removal described in the previous section.
In the surface diﬀraction method, each polygon has its own complex function sn (x, y), called the property
function of the surface, to keep characteristics of the polygon such as the shape and texture. The ﬁeld emitted
from a polygon is calculated by rotational transformation and propagation of eq. (13).
On (x̂, ŷ) = F −1 {R−ψn F {sn (x, y)} × P(dn )} .

(18)

Recurrence formula can be rewritten by substituting eq. (18) into (17) as follows:ĥn+1 (x̂, ŷ) = F −1 R+ψn F F −1 R−ψn F {ĥn (x̂, ŷ)} × mn (x, y) + sn (xn , yn ) × P(dn ) .

(19)

Fourier transform appears four times in eq. (19). However, the number of times performing Fourier transform
can be reduced by Fourier transform of both sides and substituting eq. (7) into (19). The recurrence formula ofcomplex amplitudes is rewritten as that of spectrum of the ﬁeld as follows:Ĥn+1 (û, v̂) = R+ψn F {F −1 R−1−ψn {Ĥn (û, v̂)}mn (xn , yn ) + sn (xn , yn )} × P(dn ).

(20)

The total ﬁeld on the hologram is given by
hHologram (x̂, ŷ) = F −1 {ĤN +1 (û, v̂)}.

(21)

The diagram for numerical calculation of eq. (20) is shown in Fig. 8. In this case, wave ﬁelds is handled in its
spectrum Ĥ(û, v̂), i.e. the ﬁeld is transmitted from a segment to the next in Fourier space. As a result, therecurrence formula is simpliﬁed and the number of times performing FFT is reduced in compared with ﬁeld
transmission in real space. The computational cost is estimated as 2 FFT/polygon in this algorithm.
Fourier Hˆ (uˆ , vˆ)
n
space
Real
space

R-Ã Rotation

Rotation R+Ã

F -1

F

m ( x, y )Maskings ( x, y )Hˆ n+1 (uˆ , vˆ)P( d )
Translational
propagation

Surface diffraction

Figure 8. The diagram for the procedure of computation by using field transmission in Fourier space.

31

Publication: SPIE Proc. Practical Holography XIX: Materials and Applications, SPIE#5742, San Jose, California, 25–32(2005).

5. SORTING POLYGONS
Polygons must be numbered in order of the depth before starting calculation by the recurrence formula ofeq. (20). However, determining the order is not always easy depending on disposition of polygons. Fig. 9 shows
how determine which polygon to be processed ﬁrst. In Fig. 9 (a), polygons do not obscure each other, because
one polygon is placed outside the maximum region of the ﬁeld emitted from the other. The maximum region
can be obtained from the maximum angle of diﬀraction θd . The polygon P2 partially obscure P1 in (b), while
P2 completely obstructs the ﬁeld from P1 in (c).
Fig. 9 (c) shows some cases in which it is complicated to determine the order of processing. However, evenin these cases, we usually be able to judge the order by use of information on the position of the intersectionof one polygon and the extension of the other (P1 and P2 ), or the intersection of one polygon and the normal
vector of the other(P3 and P4 ).
Several cases, in which the judgment of the processing order fails, are shown in Fig. 10. The case shown in(a) is commonly known in the painter’s algorithm of CG. The processing order of polygons can not be deﬁned
because polygons cyclically obscure each other. The case in (b) is peculiar to this algorithm; each of the polygons
obstructs the other’s ﬁeld. In the both cases, it is necessary to divide a polygon into several pieces.

6. FABRICATION AND RECONSTRUCTION OF A HOLOGRAM
A hologram, of which the object ﬁeld were synthesized by using eq. (20), was fabricated and optically reconstructed. Number and sizes of pixels of the hologram are 16384 × 4096 and 1.5µm×2.0µm, respectively.
Wavelength for reconstruction is 633nm.
Fig. 11 shows the object model. There are three planes: one is a black and white check pattern as the
background, and the others are gray triangles that are rotated at angles of 60 or 80 degree for the hologram.
Fig. 12 shows optical reconstruction of the hologram. The observed images change in (a) and (b) as the
viewpoint moves left and right. Therefore, the eﬀect of the proposed algorithm for hidden surface removal canbe veriﬁed.

(a)

(b)
P1

qd

P1
qd

P2

P2
(a)
y

Hologramxz(c)Hologramz(b)
Hologram

x

P1
P2

(d)

P1
P3

P2

P1

P1
x
P2

P4

HologramzxNormalVectorz

Hologram

Hologramx

Figure 10. Two cases in which the sequence of processing
polygons fails to be determine.

P3

P2

z

x

Figure 9. Some cases that one polygon obscures the other(a)–(c) and judgment of the order is complicated (d).

Publication: SPIE Proc. Practical Holography XIX: Materials and Applications, SPIE#5742, San Jose, California, 25–32(2005).

(a)

32

(a)

(b)
Check pattern
Triangle

P1
P1
Check pattern

Triangle

60°
80°

(b)

P2

P2
Hologram

Hologram

Figure 11. The object model in bird’s view (a) andtop view (b).

Figure 12. Optical reconstruction of the fabricatedhologram.

7. CONCLUSION
In conclusion, algorithm for hidden surface removal, which is more exact than the silhouette approximation,
has been proposed. Unlike the silhouette approximation, in the presented algorithm, the incident ﬁeld into thebackside of a tilted polygon is blocked by the tilted mask with the same shape of the polygon. As a result, any
leakage ﬁeld does not occur even in synthetic holograms with a extremely large viewing zone.
Rotational transformation must be performed twice to process ﬁeld obstruction of a tilted polygon. This
leads to execute FFT four times to process a surface. However, handling the ﬁeld transmission in Fourier spaceinstead of real space makes it possible to decrease the number of times executing FFT.
Furthermore, the presented algorithm has a high compatibility with the surface diﬀraction method to generateﬁelds from tilted surfaces. As a result, the computational cost for hidden surface removal by the presented
algorithm is reduced to 2 FFT/polygon by integrating the surface diﬀraction method.

REFERENCES
1. J. Underkoﬄer, “Occlusion processing and smooth surface shading for fully computed synthetic holography,”
SPIE Proc. Practical Holography XI 3011, pp. 19–29, 1997.
2. T. Hamano and M. Kitamura, “Computer-generated holograms for reconstructing multi-3-D images by spacedivision recording method,” SPIE Proc. Practical Holography XIV and Holographic Materials VI #3956,
pp. 23–32, 2000.
3. A. W. Lohmann, “Three-dimensional properties of wave-ﬁelds,” Optik 51, pp. 105–117, 1978.
4. K. Matsushima and A. Kondoh, “A wave optical algorithm for hidden-surface removal in digitally synthetic
full-parallax holograms for three-dimensional objects,” SPIE Proc. Practical Holography XVIII #5290, p. 90,
2004.
5. K. Matsushima, H. Schimmel, and F. Wyrowski, “Fast calculation method for optical diﬀraction on tilted
planes by use of the angular spectrum of plane waves,” J. Opt. Soc. Am. A20, pp. 1755–1762, 2003.
6. J. W. Goodman, Introduction to Fourier Optics, 2nd ed., ch. 3.10. McGraw-Hill, 1996.
7. K. Matsushima and A. Kondoh, “Wave optical algorithm for creating digitally synthetic holograms of threedimensional surface objects,” SPIE Proc. Practical Holography XVII and Holographic Materials IX #5005,
pp. 190–197, 2003.
8. K. Matsushima, “Computer-generated holograms for three-dimensional surface objects with shade and texture,” Appl. Opt. , 2005. in press.