i
i
i
i
i
i
i
i
12.5. Tiling Multidimensional Arrays 301
Note that, as in the simpler 2D one-level case, this expression can be written as
index = F
x
(x)+F
y
(y)+F
z
(z),
where
F
x
(x)=((x ÷n) ÷ m)n
3
m
3
((N
z
÷ n) ÷ m)((N
y
÷ n) ÷ m)
+((x ÷ n)modm)n
3
m
2
+(x mod n)n
2
,
F
y
(y)=((y ÷ n) ÷ m)n
3
m
3
((N
z
÷ n) ÷ m)
+((y ÷ n)modm)n
3
m +
+(y mod n)n,
F
z
(z)=((z ÷ n) ÷ m)n
3
m
3
+((z ÷ n)modm)n
3
+(z mod n).
Frequently Asked Questions
• Does tiling really make that much difference in performance?
On some volume rendering applications, a two-level tiling strategy made as much
as a factor-of-ten performance difference. When the array does not fitinmain
memory, it can effectively prevent thrashing in some applications such as image
editing.
• How do I store the lists in a winged-edge structure?
For most applications it is feasible to use arrays and indices for the references.
However, if many delete operations are to be performed, then it is wise to use
linked lists and pointers.
Notes
The discussion of the winged-edge data structure is based on the course notes of
Ching-Kuang Shene (Shene, 2003). There are smaller mesh data structures than
winged-edge. The trade-offs in using such structures is discussed in Directed
Edges—A Scalable Representation for Triangle Meshes (Campagna et al., 1998).
i
i
i
i
i
i
i
i
302 12. Data Structures for Graphics
The tiled-array discussion is based on Interactive Ray Tracing for Volume Visual-
ization (Parker, Martin, et al., 1999). A structure similar to the triangle neighbor
structure is discussed in a technical report by Charles Loop (Loop, 2000). A dis-
cussion of manifolds can be found in an introductory topology text (Munkres,
2000).
Exercises
1. What is the memory difference for a simple tetrahedron stored as four in-
dependent triangles and one stored in a winged-edge data structure?
2. Diagram a scene graph for a bicycle.
3. How many look-up tables are needed for a single-level tiling of an n-
dimensional array?
4. Given N triangles, what is the minimum number of triangles that could be
added to a resulting BSP tree? What is the maximum number?
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.