Practical Holography XXIII: Materials and Applications, eds. H. I. Bjelkhagen, R. K. Kostuk, SPIE#7233, 72330E(2009).

1

Region segmentation and parallel processing for creatinglarge-scale CGHs in polygon source method
Kyoji Matsushimaa and Sumio Nakaharaba Department of Electrical and Electronic Engineering; b Department of Mechanical Engineering

Kansai University, Yamate-cho 3-3-35, Suita, Osaka 564-8680, Japan
ABSTRACT
A novel technique is presented for calculating large-scale CGHs by using polygon-based method. In the technique,wave ﬁelds are regionally segmented and propagated by using the shifted Fresnel method. As a result, large CGHs
can be calculated even in the case that the whole frame buﬀer can not be stored in main memory. The produced
full-parallax CGH has the size of four billion pixels and reconstructs the ﬁne image of a smooth surface object
accompanied with a strong depth sensation.
Keywords: Computer-generated hologram, Polygon, Surface model, Segmentation

1. INTRODUCTION
Computer-generated holograms (CGH), sometimes called digitally synthetic holograms, make it possible to create
the hologram of virtual objects that exist only as the numerical model. In the process of making CGHs, theobject ﬁelds emitted from the virtual object is, ﬁrst, calculated from its numerical model. Secondly, the object
ﬁeld represented with distribution of complex-valued amplitude is encoded into either distribution of amplitude
or phase. Finally, the spatial distribution obtained is printed by using some fringe-drawing device or displayedelectronically on the screen by using some spatial light modulator such as LCD.
For the last decade, object ﬁelds in the ﬁrst step is obtained by superimposing spherical waves on thehologram, which are emitted from point sources of light spreading over the surface of the virtual object. Thismethod is very simple, but there is a big problem in its computation time. The computation time of this method
is proportional to the product of the number of point sources and sampling points on the hologram. The productcan be a tremendous number when one calculates a high-deﬁnition and large-scaled full-parallax CGH based ona surface model, and thus computation time is very long.
Recently one of the authors has proposed another technique1 based on polygon sources of light instead ofpoint sources. In this technique a virtual object is composed of some planar and arbitrarily tilted polygons.
Object ﬁelds emitted from the polygons are individually calculated in a plane parallel to the hologram by using
rotational transformation2, 3 and then propagated into the hologram. These computational processes are executed
polygon-by-polygon, and then the individual polygon ﬁelds are totaled on the hologram or intermediate planes
in a layered scene structure. Calculation by this technique is essentially faster than that using the point-based
method, because of using FFT. In addition, this technique treats objects as a set of polygons and is closer toordinary CG techniques than the point-based one. Thus, some researchers have proposed similar polygon-based
methods4, 5 to improve our original idea mainly in computation time.
However, in the polygon-based method, region segmentation and parallel processing are diﬃcult, because thealgorithm requires calculation of numerical propagation/diﬀraction. Thus, producing large-scale CGHs are noteasy. In this article it is intended to describe techniques to create high-deﬁnition and large-scaled CGHs withsize of more than 109 pixels by using segmentation of frame buﬀers and parallel processing. The shifted Fresnel
method6 recently proposed is used for the numerically translational propagation in the segmented frame buﬀers.
Further author information: (Send correspondence to K. Matsushima)
K. Matsushima: E-mail: matsu@kansai-u.ac.jp
S. Nakahara: E-mail: nakahara@ipcku.kansai-u.ac.jp

Practical Holography XXIII: Materials and Applications, eds. H. I. Bjelkhagen, R. K. Kostuk, SPIE#7233, 72330E(2009).

y 3

C u b ic
o b je c t

z3

z1

P 1

x 3 L o cal

P 3

c o o rd in a te s

y 2

3

P 2

2

1

y 1

2

x 2

L o c a lc o o rd in a te sy^x 1
L o c a l c o o rd in a te s

z2

x^

z^

G lo b a l c o o rd in a te s

Figure 1. The object model and deﬁnitions of the global and local coordinates.

2. CALCULATION OF POLYGON FIELD
An example to calculate the object ﬁelds from a cubic object is shown in Fig. 1. The object model is given as
a set of vertices and can be resolved into three polygons P1,···,3 . Note that techniques of exact hidden surface
removal7–9 are out of the scope of this article. Only back-face culling is made by relation between the surface
and hologram, and thus far side polygons are ignored.
Each polygon Pn has their own local coordinates (xn , yn , zn ). Any local coordinates can be adopted arbitrarily
as long as a rotation matrix is well-deﬁned. The polygon and the local coordinates is rotated by the rotation
matrix so as to be parallel to the hologram or the global coordinates (x̂, ŷ, ẑ)(a )T ilte d fra m e
b u ffe r

y n

zn
x n

P a ra lle l fra m e
b u ffe r
(b )

(c )

C o n s ta n t p h a s e(d )D iffu s iv e p h a s e

Figure 2. Conﬁguration of surface functions.

Practical Holography XXIII: Materials and Applications, eds. H. I. Bjelkhagen, R. K. Kostuk, SPIE#7233, 72330E(2009).

3

2.1 Deﬁnition of Surface Function
A polygon source of light is represented by two dimensional distribution of complex-valued amplitude in the(xn , yn , 0) plane. This distribution is called the surface function or material function. This function plays animportant role to give appearance of the polygon in optical reconstruction.
The surface functions are generally given as the following form:sn (xn , yn ) = an (xn , yn ) exp[iϕn (xn , yn )],where the real-valued amplitude an (xn , yn ) gives the shape of the polygon as follows:{
An · · · inside polygon
an (xn , yn ) =0 · · · outside polygon

(1)

(2)

The amplitude An is diﬀerent value for each polygon in order to shade the object appropriately as intended by
the designer.1 The texture of polygon can be also given as modulation of amplitude. In this case, An is notconstant but a function of xn and yn . In this report, complex-valued buﬀers that store the surface functions innumerical calculation is called the tilted frame buﬀer as shown in Fig. 2 (a).
If the surface function is a simple polygon-shaped distribution of real-valued amplitude, the surface function
behaves as if it was an aperture that shapes the polygon. As a result, light from the polygon does not spreadover the hologram, as shown in Fig. 2 (b). Therefore, phase ϕn (xn , yn ) of the surface function is necessary forgiving diﬀusiveness to the wave ﬁeld of the polygon source. Random functions are candidates for the diﬀusive
phase ϕn (xn , yn ). But full random functions are not appropriate, because the random phases are discontinuousand have a large spatial frequency that causes speckles in the reconstruction. Therefore, quasi-random phase
distribution proposed as a digital diﬀuser10 in Fourier holograms is used for the phase distribution.
The wave ﬁeld of polygon is diﬀused by using the diﬀuser phase as shown in Fig. 2 (c). However, if the spatial
carrier frequency of the surface function is zero, the wave ﬁeld mainly propagates in the normal direction to thepolygon, and thus light from polygon can not reach the hologram eﬀectively. The center of spectrum of thesurface function must be shifted so that light travels along optical axis and almost perpendicularly intersects theplane parallel to the hologram. This shift operation is a part of rotational transformation described in Sec. 2.2.
Examples of local coordinates and surface functions stored in the tilted frame buﬀer are shown in Fig. 3.
These are of the case of the cubic object given in Fig. 1. The surface functions deﬁned for polygons P1 , · · · , P2 in(a) are shown in (b), respectively. The amplitude of the surface function sn (xn , yn ) is zero outside the polygon,
while the amplitude of the inside is a constant value that is diﬀerent for each polygon and determined so as togive appropriate shade to the object in optical reconstruction.1

2.2 Rotational Transformation
The polygons forming the object surfaces are usually not parallel to the hologram, and thus wave ﬁelds in thehologram plane can not be obtained by using ordinary formulas for diﬀraction or propagation of wave ﬁelds, suchas Fresnel diﬀraction formula. Therefore, the surface functions must be transformed into wave ﬁelds given in aplane parallel to the hologram. This section brieﬂy summarizes the procedure.
First, surface functions are Fourier transformed as follows:
S(un , vn ) = F{sn (xn , yn )},(3)

where F and F−1 stands for Fourier and inverse Fourier transform, respectively. The Fourier spectrum S(un , vn )of polygon n is numerically obtained by using fast Fourier transform (FFT). Here, un and vn are Fourier
frequencies.
Second, transformation matrix for changing the local coordinates into diﬀerent coordinates parallel to thehologram is deﬁned as,
a1 a2 a3
 a4 a5 a6  .
T−1
(4)
n =
a7 a8 a9Practical Holography XXIII: Materials and Applications, eds. H. I. Bjelkhagen, R. K. Kostuk, SPIE#7233, 72330E(2009).

z1

A m p litu d e im a g e

y 1

P 1

4

A m p litu d e im a g e

P h a s e im a g e

y

x

x 1

y 2
P 2
x 2

S 1(x 1, y 1)yz2x

S 2(x 2, y 2)
y 3

y

z3

x 3

P 3

x

S 3(x 3, y 3)(b ) T ilte d fra m e b u ffe r(a ) L o c a l
c o o rd in a te s(c ) P a ra lle l fra m e
b u ffe r

Figure 3. Examples of the surface functions.

Note that the matrix elements ai depends on the polygon, but the subscript n is omitted for simplifying notation.
Suppose that a local parallel coordinates is deﬁned as r̂n = (x̂n , ŷn , ẑn ). This coordinates share the origin withthe local coordinates rn = (xn , yn , zn ) but the (x̂n , ŷn , 0) plane is parallel to the hologram. The coordinatesrotation from a local parallel coordinates r̂n = (x̂n , ŷn , ẑn ) to the local coordinates rn = (xn , yn , zn ) is given as
rn

= T−1
n r̂n

(5)

There is somewhat of arbitrariness in the means for determining the matrix T−1 . We used Rodrigues’ rotation
formula for obtaining the matrix in calculating the practical hologram of the following section.
Fourier frequencies (û, v̂) in the parallel coordinates is mapped into Fourier frequencies (un , vn ) in the local
coordinates by
un
vn

=
=

α(ûn , v̂n ) = a1 ûn + a2 v̂n + a3 ŵ(ûn , v̂n ),β(ûn , v̂n ) = a4 ûn + a5 v̂n + a6 ŵ(ûn , v̂n ),(6)

where ŵ(ûn , v̂n ) = (λ−2 − û2n − v̂n2 )1/2 is the Fourier frequency in ẑn axis. This mapping moves the originof spectrum to a non-zero frequency. However, FFT algorithm can only work well around the zero frequency,
therefore spectrum Ŝ(ûn , v̂n ) in the global coordinates should be obtained by remapping spectrum S(un , vn ) onto
the Fourier space (ûn , v̂n ) as follows:Ŝ(ûn , v̂n ) ∼
=
(0)

(0)
S(α(ûn , v̂n ) − u(0)n , β(ûn , v̂n ) − vn ).

(7)

(0)

where un and vn give shift values of the carrier frequencies, i.e. the center of spectrum. This remapping does
not only rotate the coordinates but also change the direction in which polygon light travels. In most of polygons,
the most appropriate shift values areu(0)n= α(0, 0) = a3 /λ,

(8)

vn(0)

= β(0, 0) = a6 /λ,(9)Practical Holography XXIII: Materials and Applications, eds. H. I. Bjelkhagen, R. K. Kostuk, SPIE#7233, 72330E(2009).

O b je c t

P 1
T ilte dfra m e b u ffe r

5

P 2

P 3
S e g m e n t

Figure 4. Segmentation in the object ﬁeld.

Figure 5. Numerical propagation of segmented wave ﬁelds.

because the carrier frequency is changed to zero in parallel coordinates and thus the polygon ﬁelds forced totravel perpendicular to the hologram. However, there are a few exceptions. In some polygons of which normal
vector are almost parallel to the hologram, ﬁne adjustments should be made to the shift values.
Note that the nearly equal sign in eq.(7) states that an interpolation is required, because coordinates rotation
does not only move the origin but also distorts the sampling grid.3
Finally, the wave ﬁeld from the polygon is obtained in the parallel coordinates by using inverse Fouriertransform as follows:hn (xn , yn ) = F−1 {Ŝ(ûn , v̂n )}(10)
In numerical implement, the spectrum Ŝ(ûn , v̂n ) and wave ﬁeld hn (xn , yn ) are accumulated in a complex-valued
buﬀer called parallel frame buﬀer as shown in Fig. 2 (a). Examples of hn (xn , yn ) are shown as amplitude images
in Fig. 3 (c).

3. FRAME BUFFER SEGMENTATION
The polygon-based techniques for synthesizing object ﬁeld is the method based on wave optics or Fourier optics.
In this branch of optics, wave ﬁelds are generally represented by distribution of complex amplitudes and treatedas a sampled two-dimensional array of two ﬂoating-point values in computers. Therefore, when the array size
is N 2 and single-precision ﬂoating point are used for calculation, the memory size needed for the array is 8N 2
bytes. We created a CGH with pixels of 216 × 216 in this investigation. Therefore, the frame buﬀer storing thewhole CGH needs the memory size of 32 G Bytes. This estimation is only for a single frame buﬀer. Anothermemory spaces required for running the program, such as OS area, code area, temporary frame buﬀer, work
space and I/O buﬀer etc., are not included at all. As a result, regional segmentation of CGH is essential toproducing the large-scale CGH.

3.1 Segmentation in Calculating Object Fields
Both sizes of the tilted frame buﬀer and the parallel frame buﬀer in Fig. 2 depends on the polygon size. These
are relatively small if the object have curved surfaces and is constructed of many polygons. The wave ﬁeld ofeach polygon, stored in the parallel frame buﬀer, is numerically propagated into a intermediate plane. Then all
polygon ﬁelds are gathered and summed up in a large frame buﬀer. This large frame buﬀer storing the whole
object ﬁeld in intermediate plane must be segmented because its size is same as the hologram one. Since thewhole of the large frame buﬀer can not be in memory, the summing-up processes are made for each segment of
the large buﬀer. When the summing-up process is ﬁnished for a segment, the segment is saved as a ﬁle on thedisk, and then next segment is processed in memory. This process is parallelized for each segment in threads
level. Therefore, the number of segments, simultaneously processed in memory, is same as the number of CPU
cores. Furthermore, as shown in Fig. 4, polygons of which light reach to the currently processed segment are
selected before calculating the polygon ﬁeld. The selection is carried out by obtaining diﬀraction area of thepolygon to the intermediate plane. For example, the wave ﬁelds of the polygon P2 and P3 are calculated andsummed up but polygon P1 is ignored when processing the segment (2, 1) of Fig. 4.

Practical Holography XXIII: Materials and Applications, eds. H. I. Bjelkhagen, R. K. Kostuk, SPIE#7233, 72330E(2009).

6

Table 1. Parameters used for calculating the object ﬁeld and fabricating the hologram.

Total number of pixels

4.3 × 109 (65, 536 × 65, 536)

Pixel pitches

1 µm × 1 µm

Dimension of hologram

65.5 × 65.5 mm2

Number of segments

8×4

Hologram coding

Binary amplitude

Reconstruction wavelength632.8 nm

Total number of polygons of Venus

1396

Number of visible polygons of Venus

718

Dimension of Venus (W × H × D)

26.7 × 57.8 × 21.8 mm3Dimension of wallpaper (W × H)

65.5 × 65.5 mm2

Distance of Venus from hologram

150 mmDistance of wallpaper from hologram

300 mm

3.2 Segmentation in Translational Propagation
The object ﬁeld obtained in intermediate plane is numerically propagated into a next plane or the hologram. This
numerical propagation must be regionally segmented again. Shifted Fresnel method6 for numerical propagation
features the capability of calculating the target wave ﬁeld from the source wave ﬁeld whose center position is not
same as the target. Therefore, the method allows us to calculate the wave ﬁeld, for example, in the segment (0,3) of plane #2 from the segment (2, 2) of plane #1, as shown in Fig. 5. This calculation can be also parallelized
in threads level. As a result, memory is required only for one segment in plane #1 and same number of segments
as CPU cores in plane #2.

4. CREATING THE HOLOGRAM “VENUS”
Fig. 6 shows the geometry for producing a large-scale CGH named “Venus” in this investigation. The Venus
object is placed at 15 cm behind the hologram. In addition, a wallpaper object is placed at 15 cm behind theVenus. The Venus is a surface-modeled object constructed of 1396 polygons, while the wallpaper object is a
simple planar image. Some parameters of the Venus hologram is summarized in Table 1.

4.1 Masking Wallpaper Field
If the ﬁeld of the wallpaper was simply added to that of the Venus object, the Venus would be optically reconstructed as a phantom image, because simple superposition of these ﬁelds involves the Venus object transmitting
wallpaper light. To prevent transmission of light, propagation process was divided into two steps. First, thewallpaper ﬁeld is propagated into the object plane, as shown in Fig. 6. Then, the ﬁeld is masked with thesilhouette of the Venus.7, 8 Second, the ﬁeld is propagated into the hologram after adding the Venus ﬁeld.

4.2 Computation Time
The procedure described above is implemented by using Intel C++ Compiler 10 and Visual Studio 2008. Intel
Math Kernel Library is also used for FFT. Numerical calculation was executed in a PC with 4 CPU of AMD
Opteron 852 (2.6GHz) and 32 G Bytes RAM. Total computation time was 45 hours. Itemized computation
times are shown in Fig. 7. Longest time was consumed in translational propagation. The amount is 37 hours
and account for 82% of total computation time.

Practical Holography XXIII: Materials and Applications, eds. H. I. Bjelkhagen, R. K. Kostuk, SPIE#7233, 72330E(2009).

W a llp a p e r

O b je c t p la n e
6 .5 c m

H o lo g ra m

5 .7 c m

T ra n s la tio n a lp ro p a g a tio n

6 .5 c m

T ra n s la tio n a lp ro p a g a tio n+

7

6 .5 c m=

S ilh o u e tte -m a s k e d fie ld
o f w a llp a p e r

O b je c c t fie ld
S u p e rim p o s e d fie ld
in o b je c t p la n e

Figure 6. Geometry of the objects and masking by silhouette.

4.3 Optical Reconstruction of the Venus
The CGH “Venus” was fabricated by DWL 66 laser lithography system made by Heidelberg Instruments, GmbH.
Optical reconstruction of the fabricated hologram is shown in Fig. 8. The pictures (a)–(d) were captured in various
points of view. The frame of printed pictures in this ﬁgure is just same as the hologram frame. The shifts of
the Venus and the wallpaper object in the picture frame are caused by parallax in the reconstructed ﬁeld. This
motion parallax gives a strong sensation of depth to observer’s perception.

5. CONCLUSION
We numerically synthesized a large-scale CGH with 4 G pixels by using polygon-based method, which numericallygenerates object ﬁelds from polygon sources of light instead of point sources. In the technique, computation timeis generally shorter as compared with the point-based methods. However, region segmentation and parallel
processing was more diﬃcult because of requirement of propagation of wave ﬁelds. We resolved this problem by
G e n e ra tin g
w a llp a p e r fie ld

0 .2 hT ra n s la tio n a l
P ro p a g a tio n

0 .0

5 .0

1 0 .01 8 .5 h

1 5 .0G e n e ra tin go b je c t fie ld

7 .6 h

2 0 .02 5 .0

T ra n s la tio n a l
P ro p a g a tio n

3 0 .0C o m p u ta tio n tim e [h o u r]

3 5 .01 8 .5 h

4 0 .0Figure 7. Computation time for producing the Venus.

4 5 .0Practical Holography XXIII: Materials and Applications, eds. H. I. Bjelkhagen, R. K. Kostuk, SPIE#7233, 72330E(2009).

(a ) L e ft(b ) R ig h t(c ) U p

8(d ) D o w n

Figure 8. Pictures of optical reconstruction of the fabricated hologram from various viewpoints.

using shifted Fresnel method. The created full-parallax CGH named Venus has good appearance and causes astrong depth sensation owing to a silhouette-masking technique.

ACKNOWLEDGMENTS
The mesh data of the Venus object is provided courtesy of INRIA by the AIM@SHAPE Shape Repository.

REFERENCES[1] Matsushima, K., “Computer-generated holograms for three-dimensional surface objects with shade andtexture,” Appl. Opt. 44, 4607–4614 (2005).
[2] Matsushima, K., Schimmel, H., and Wyrowski, F., “Fast calculation method for optical diﬀraction on tilted
planes by use of the angular spectrum of plane waves,” J. Opt. Soc. Am. A20, 1755–1762 (2003).
[3] Matsushima, K., “Formulation of the rotational transformation of wave ﬁelds and their application to digitalholograph,” Appl. Opt. 47, D110–D116 (2008).
[4] Ahrenberg, L., Benzie, P., Magnor, M., and Watson, J., “Computer generated holograms from three dimensional meshes using an analytic light transport model,” Appl. Opt. 47, 1567–1574 (2008).
[5] Kim, H., Hahn, J., and Lee, B., “Mathematical modeling of triangle-mesh-modeled three-dimensional surface
objects for digital holography,” Appl. Opt. 47, D117–D127 (2008).
[6] Muﬀoletto, R. P., Tyler, J. M., and Tohline, J. E., “Shifted fresnel diﬀraction for computational holography,”Opt. Express 15, 5631–5640 (2007).
[7] Matsushima, K. and Kondoh, A., “A wave optical algorithm for hidden-surface removal in digitally synthetic
full-parallax holograms for three-dimensional objects,” SPIE Proc. Practical Holography XVIII #5290, 90(2004).
[8] Kondoh, A. and Matsushima, K., “Hidden surface removal in full-parallax CGHs by silhouette approximation,” Systems and Computers in Japan 38, 53–61 (2004).
[9] Matsushima, K., “Exact hidden-surface removal in digitally synthetic full-parallax holograms,” SPIE Proc.
Practical Holography XIX and Holographic Materials XI #5742, 25–32 (2005).
[10] Bräuer, R., Wyrowski, F., and Bryngdahl, O., “Diﬀusers in digital holography,” J. Opt. Soc. Am. A8,
572–578 (1991).