
Point Lattices in Computer Graphics and Visualization
Visualization 2005
Tutorial 4  Monday 8:30  5:30
Minneapolis, Minnesota, October 24, 2005

Contents
Abstract
Index to Course Materials
Presenter Information
Speaker Biographies
This DVD contains the content of the supplemental material of the tutorial
Point Lattices in Computer Graphics and Visualizations given at
the conference IEEE Visualization 2005 in October 2005. These materials were
prepared before August 1st, 2005. Any additional material added after this
production deadline can also be found in the online repository located at
http://www.cs.sfu.ca/~torsten/Vis2005/
This course is motivated by the deep connections and applications of
point lattice theory in the mathematics of computer graphics and the role
it plays in multidimensional signal processing and tilings. Next to an
introduction to the theory and history of point lattices and the related
sampling and group theories, we present an indepth survey from two
different perspectives:
 Signal processing  Functional analysis and sampling theory
All computational fields in science and engineering have to deal with
discrete representations of continuous phenomena. Clearly, sampling theory
is crucial to provide the essential link between the discrete and the
continuous domain. Digital signal processing algorithms can only act on the
discrete data, but should not loose sight of the continuousdomain aspect
of their operations. As we will show, many interesting practical problems
are best approached from this theoretic framework. Therefore, we will
review general sampling theory in arbitrary dimensions and focus on recent
developments for optimal lattices. This part will contain many examples and
goodpractice in image processing, medical imaging, and volume rendering.
We survey reconstruction filter designs, wavelet techniques, medical
reconstruction, discretization and rendering aspects for 2D, 3D, and 4D
lattices. At the end, the attendee will comprehend how to put a proper
discrete/continuous model for his/her application.
 Crystallography  Geometry and group theory
The study of the formation and structure of crystals has been the
interest of scientists for many centuries. Consequently, the symmetries and
translation invariant properties of point lattices have been studied and
investigated thoroughly in the field of crystallography and solidstate
physics. Group theory brought mathematical rigor to these fields. We take
the opportunity in this course to migrate the most interesting results from
this domain to the computer graphics community. Besides intricate
mathematical concepts, regular structures have a strong aesthetic impact
and have been incorporated into artistic expressions from ancient
ornamental structures to famous works of Escher and general tiling
patterns. In this part, we introduce fundamental group theory related to
point lattices; we also effectively demonstrate geometric tools for the
visualization of tilings and patterns in 2D, 3D, and 4D.
Tutorial Slides
 Introduction by Torsten Möller
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
 Representation and History
 Analytic (Sampling Theory) by Alireza Entezari
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
 Algebraic (Group Theory) by Jim Morey
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
 Applications
 Fundamental Computer Graphics by Torsten Möller
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
 Image Processing 2D by Dimitri Van De Ville
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
 Image Processing 3D  Tools by Alireza Entezari
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
 Image Processing 3D  Rendering by Klaus Mueller
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
 Medical by Klaus Mueller
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
 Modeling by Ostromoukhov
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
 Crystallography by Jim Morey
[PDF, Color, 1 Slide per page],
[PDF, Black/White, 1 Slides per page]
[PDF, Color, 4 Slide per page],
[PDF, Black/White, 4 Slides per page]
Additional Materials
I would like to see whether we can get something like a comprehensive bibliography together here. I started a litte bit and would appreciate your input. This could potentially be it's separate page.
 Representation and History
 Analytic (Sampling Theory)
 I.J. Schoenberg, "Contribution to the problem of approximation of
equidistant data by analytic functions," Quart. Appl. Math, 4:4599,
112141, 1946.
 D.P. Petersen and D. Middleton,
"Sampling and reconstruction of wavenumberlimited functions in Ndimensional Euclidean spaces,"
Information and Control, 5(4):279323, December 1962.
 R.M. Mersereau,
"The processing of hexagonally sampled twodimensional signals,"
Proceedings of the IEEE, 67(6):930949, June 1979.
 D. E. Dudgeon and R. M. Mersereau,
"Multidimensional Digital Signal Processing,"
PrenticeHall, Inc., EnglewoodCliffs, NJ, 1st edition, 1984.
 S. Mallat,
"A Theory for Multiresolution Signal Decomposition: the Wavelet Representation,"
IEEE Transactions on Pattern Analysis and Machine Intelligence, 11:674693, 1989.
 C. deBoor, K. Höllig, S. Riemenschneider,
"Box splines,"
Springer Verlag, 1993.
 T.C. Hales,
"Cannonballs and honeycombs,"
Notices of the AMS, 47(4):440449, April 2000.
 P. Bremaud,
"Mathematical Principles of Signal Processing,"
Springer, 2002.
 Algebraic (Group Theory)
 B. Grünbaum,
"The emperors new clothes: full regalia, gstring, or nothing?,"
Mathematical Intelligencer, 6(4), 1984.
 G. Burns,
"Solid State Physics,"
Academic Press Inc., 1985.
 B. Grünbaum, G.C. Shephard,
"Tilings and Patterns: An Introduction,"
Freeman, New York, 1987.
 D.S. Dummit, R.M. Foote,
"Abstract Algebra,"
Prentice Hall, New Jersey, 1991.
 M. O'Keeffe, B.G. Hyde,
"Crystal Structures: I Patterns and Symmetry,"
Min. Soc. Am., Washingon D.C., 1996.
 J.H Conway and N.J.A. Sloane,
"Sphere Packings, Lattices and Groups,"
Springer, 3rd edition, 1998.
 J. Morey, K. Sedig,
"Archimedean Kaleidoscope: A Cognitive Tool to Support Thinking and Reasoning about Geometric Solids,"
Geometric Modeling: Techniques, Applications, Systems and Tools,
Editor: M. Sarfraz, Kluwer Academic Publisher, 2004.
 Applications
 Fundamental Computer Graphics / Discretization
 L. Ibanez, Ch. Hamitouche, Ch. Roux,
Raytracing and 3D Objects Representation in the BCC and FCC Grids
Proceedings of the 7th International Workshop on Discrete Geometry for Computer Imagery, pp. 235242, Sep 1997.
 L. Ibanez, Ch. Hamitouche, Ch. Roux,
"A Vectorial Algorithm for Tracing Discrete Straight Lines in NDimensional Generalized Grids"
IEEE Transactions on Visualization and Computer Graphics, vol. 7(2), pp. 97108, April 2001.
 H. Widjaya, T. Möller, A. Entezari,
"Voxelization in Common Sampling Lattices",
Proceedings of Pacific Graphics 2003 (PG03),
pp. 497501, Canmore, Alberta, October 2003.
 Image Processing 2D
 M. Unser, A. Aldroubi, M. Eden,
"Enlargement or Reduction of Digital Images with Minimum Loss of Information,"
IEEE Transactions on Image Processing, 4(3):247258, March 1995.
 T. Blu, M. Unser,
"Quantitative Fourier Analysis of Approximation Techniques: Part IInterpolators and Projectors,"
IEEE Transactions on Signal Processing, 47(10):27962806, October 1999.
 M. Unser, T. Blu,
"Fractional splines and wavelets,"
SIAM Review, 42 (1):4367, 2000.
 P. Thevenaz, T. Blu, M. Unser,
"Interpolation Revisited,"
IEEE Transactions on Medical Imaging, 19(7):739758, July 2000.
 T. Blu, M. Unser,
"A Complete Family of Scaling Functions: The (\alpha, \tau)Fractional Splines,"
Proceedings of the TwentyEighth IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'03),
Hong Kong SAR, People's Republic of China, April 610, 2003, vol. VI, pp. 421424.
 P. Thevenaz, M. Unser,
"Precision Isosurface Rendering of 3D Image Data",
IEEE Transactions on Image Processing, 12(7):764775, July 2003.
 D. Van De Ville, T. Blu, M. Unser, W. Philips, I. Lemahieu, R. Van de Walle,
"Hexsplines: A novel spline family for hexagonal lattices,"
IEEE Transactions on Image Processing, 13(6):758772, June 2004.
 M. Unser, T. Blu,
"Generalized Smoothing Splines and the Optimal Discretization of the Wiener Filter,"
IEEE Transactions on Signal Processing, 53(6):21462159, June 2005.
 Image Processing 3D  Tools
 Alireza Entezari, Ramsay Dyer, Torsten Möller,
"Linear and Cubic Box Splines for the Body Centered Cubic Lattice",
Proceedings of IEEE Visualization 2004 (Vis04), pp. 1118,
Austin, TX, October 2004.
 Hamish Carr, Thomas Theußl, Torsten Möller,
"Isosurfaces on Optimal Regular Samples",
Joint EUROGRAPHICS 
IEEE VGTC Symposium on Visualization (VisSym 2003),
pp. 3948, Grenoble, May 2003.
 T. Theußl, O. Mattausch, T. Möller, E. Gröller,
"Reconstruction schemes for high quality raycasting of the bodycentered cubic grid,"
TR18620211, Institute of Computer Graphics and Algorithms,
Vienna University of Technology, December 2002.
 B. Csébfalvi,
"Prefiltered Gaussian Reconstruction for HighQuality Rendering of Volumetric Data sampled on a BodyCentered Cubic Grid"
IEEE Visualization 2005 (Vis 2005), pp. 311318, 2005.
 Image Processing 3D  Rendering
 Thomas Theußl, Torsten Möller, Eduard Gröller,
"Optimal Regular Volume Sampling",
Proceedings of IEEE Visualization 2001, pp. 9198, October 2001.
 N. Neophytou, K. Mueller,
"Spacetime points: 4D Splatting on effcient grids,"
Symp. Volume Visualization and Graphics '02, pp. 97106, 2002.
 J. Sweeney, K. Mueller,
"ShearWarp Deluxe: The ShearWarp algorithm revisited,"
Eurographics / IEEE TCVG Symp. Visualization 2002, pp. 95104, May 2002.
 T. Welsh, K. Mueller,
"A frequencysensitive point hierarchy for images and volumes,"
IEEE Visualization '03, pp. 425432, October 2003.
 Medical  basics
 A.H. Andersen, A.C. Kak,
"Simultaneous Algebraic Reconstruction Technique (SART): a superior implementation of the ART algorithm,"
Ultrasonic Imaging, vol. 6, pp. 8194, 1984.
 A.C. Kak, M. Slaney,
"Principles of Computerized Tomographic Imaging,"
IEEE Press, 1988.
 L. Shepp, Y. Vardi,
"Maximum likelihood reconstruction for emission tomography,"
IEEE Trans. Medical Imaging, vol. 1, no. 2, pp. 113122, October 1982.
 P. Suetens,
Fundamentals of Medical Imaging,
Cambridge University Press, 2002.
 Medical  optimal lattices
 R.M. Lewitt,
"Multidimensional digital image representations using generalized KaiserBessel window functions,"
J. Opt. Sec. Am. A, vol. 7, no.10, pp. 18341846, 1990.
 S. Matej, R.M. Lewitt,
"Efficient 3D grids for image reconstruction using sphericallysymmetric volume elements,"
IEEE Trans. Nuclear Science, vol. 42, no 4, pp 13611370, 1995.
 S. Matej, R.M. Lewitt,
"Practical considerations for 3D image reconstruction using spherically symmetric volume elements,
IEEE Trans. Medical Imaging, vol. 15, no. 1, pp. 6878, 1996.
 K. Mueller, R. Yagel,
"The use of hexagonal grids to improve the efficiency of the Algebraic Reconstruction Technique (ART),"
Annals of Biomedical Engineering, Special issue,
1996 Annual Conference of the Biomedical Engineering Society, p. S66, 1996.
 K. Mueller, R. Yagel, J.J. Wheller,
"Antialiased 3D conebeam reconstruction of lowcontrast objects with algebraic methods,"
IEEE Trans. Medical Imaging, vol. 18, no. 6, pp. 519537, 1999.
 Crystallography/Modeling
 J. Morey, K. Sedig,
"Adjusting degree of visual complexity: an interactive approach for exploring fourdimensional polytopes,"
The Visual Computer, Vol 20, Issue 89, 2004.
 J. Morey, K. Sedig, R. Mercer, W. Wilson,
"Crystal Lattice Automata,"
Proceedings of the Sixth International Conference on Implementations and Applications of Automata (Pretoria, South Africa, July 2001),
Lecture Notes in Computer Science, Springer Verlag, 2002.
Reza Entezari
School Of Computing Science
Simon Fraser University
8888 University Drive
Burnaby, British Columbia, V5A 1S6
Canada
 Klaus Mueller
State University of New York at Stony Brook, USA
Department of Computer Science
2428 Computer Science
Stony Brook, NY 117944400
USA

Jim Morey
Cognitive Engineering Lab
Department of Computer Science
Middlesex College
The University of Western Ontario
London, Ontario, N6A 5B7
Canada
 Victor Ostromoukhov
University of Montreal, Dept.Comp.Sc.& Op.Res
2920, chemin de la Tour, office 2347/2153(secr)
C.P. 6128, Succ. CentreVille
Montreal, Quebec, H3C 3J7
Canada

Torsten Möller
School Of Computing Science
Simon Fraser University
8888 University Drive
Burnaby, British Columbia, V5A 1S6
Canada
 Dimitri Van De Ville
Swiss Federal Institute of Technology Lausanne, Switzerland
Biomedical Imaging Group
EPFLIOALIB BM 4140; Station 17
CH1015 Lausanne
Suisse

Alireza Entezari
is a PhD candidate at Simon Fraser University. He received
his bachelor of science in Computing Science from Simon Fraser University
in 2001. His current research focus lies in the interpolation and
reconstruction issues on optimal sampling structures used in scientific
computing and visualization.
Jim Morey
received his PhD in computer science from the University of
Western Ontario (2004), a MSc in pure mathematics from the University of
British Columbia (1996), and a BSc in mathematics from the University of
Guelph (1993). His work combines human computer interactions, mathematics,
and theoretical computer science in designing tools for investigating
repetitive geometric artifacts like tilings, crystal lattices, and
polytopes. The tools have incorporated a number of novel interactive
techniques, interactive representations, and repetitive artifacts. (for
examples see http://www.csd.uwo.ca/~morey/CogEng)
Klaus Mueller
is currently an Assistant Professor at the Computer Science
Department at Stony Brook University, where he also holds coappointments
at the Biomedical Engineering and the Radiology Departments. He earned an
MS degree in Biomedical Engineering in '91 and a PhD degree in Computer
Science in '98, both from Ohio State University. His current research
interests are computer graphics, visualization, medical imaging, and
computer vision. He won the NSF CAREER award in 2001 and has served as a
program cochair at various conferences, such the Volume Graphics Workshop,
IEEE Visualization, and the Symposium on Volume Visualization and Graphics.
He has authored over 70 journal and conference papers.
Victor Ostromoukhov
studied mathematics, physics and computer science at
Moscow Institute of Physics and Technology (PsysTech, MFTI). After
graduating in 1980, he spent several years with prominent European and
American industrial companies (SG2, Paris; Olivetti, Paris and Milan; Canon
Information Systems, Cupertino, CA) as a research scientist and/or computer
engineer. He completed his Ph.D. in CS at Swiss Federal Institute of
Technology (EPFL, Lausanne, 1995), where he continued to work as a lecturer
and senior researcher. Invited professor at University of Washington,
Seattle, WA, in 1997. Research scientist at Massachusetts Institute of
Technology, Cambridge, MA, in 19992000. Associate Professor at University
of Montreal, since August 2000. His research interests are mainly in
computer graphics, and more specifically in nonphotorealistic rendering,
sampling, tiling theory, color science, halftoning, and digital art.
Dimitri Van De Ville
received the Engineering and Ph.D. degrees in Computer
Sciences in July 1998 and January 2002, respectively, from Ghent
University, Belgium. He is now with the Biomedical Imaging Group at the
Swiss Federal Institute of Technology Lausanne (EPFL). His current research
interests include splines, wavelets, approximation and sampling theory, and
biomedical signal and imaging applications such as fMRI and microscopy
imaging. Dr. Van De Ville is associate editor of the IEEE Signal Processing
Letters. He is also editor and webmaster of the Wavelet Digest, the
electronic newsletter of the wavelet community.
Torsten Möller
is an associate professor at the School of Computing Science
at Simon Fraser University. His research interests include the fields of
Scientific Visualization and Computer Graphics, especially the mathematical
foundations of visualization and graphics. He is codirector of the
Graphics, Usability and Visualization Lab and serves on the Board of
Advisors for the Centre for Scientific Computing at Simon Fraser
University. He has been appointed Vice Chair for Publications of the IEEE
Technical Committee of Visualization and Graphics.