Point Lattices in Computer Graphics and Visualization

Visualization 2005

Tutorial 4 - Monday 8:30 - 5:30

Minneapolis, Minnesota, October 24, 2005

Course Organizer	Lecturers
Torsten Möller Simon Fraser University	Reza Entezari Simon Fraser University
	Jim Morey The University of Western Ontario
	Klaus Mueller State University of New York at Stony Brook
	Victor Ostromoukhov University of Montreal
	Dimitri Van De Ville Swiss Federal Institute of Technology Lausanne

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/

Abstract

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 in-depth 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 continuous-domain 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 good-practice 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 solid-state 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.

Index to Course Materials

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:45-99, 112-141, 1946.
  - D.P. Petersen and D. Middleton, "Sampling and reconstruction of wave-number-limited functions in N-dimensional Euclidean spaces," Information and Control, 5(4):279-323, December 1962.
  - R.M. Mersereau, "The processing of hexagonally sampled twodimensional signals," Proceedings of the IEEE, 67(6):930-949, June 1979.
  - D. E. Dudgeon and R. M. Mersereau, "Multidimensional Digital Signal Processing," Prentice-Hall, Inc., Englewood-Cliffs, NJ, 1st edition, 1984.
  - S. Mallat, "A Theory for Multiresolution Signal Decomposition: the Wavelet Representation," IEEE Transactions on Pattern Analysis and Machine Intelligence, 11:674--693, 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):440-449, April 2000.
  - P. Bremaud, "Mathematical Principles of Signal Processing," Springer, 2002.
- Algebraic (Group Theory)
  - B. Grünbaum, "The emperors new clothes: full regalia, g-string, 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, Ray-tracing and 3D Objects Representation in the BCC and FCC Grids Proceedings of the 7th International Workshop on Discrete Geometry for Computer Imagery, pp. 235-242, Sep 1997.
  - L. Ibanez, Ch. Hamitouche, Ch. Roux, "A Vectorial Algorithm for Tracing Discrete Straight Lines in N-Dimensional Generalized Grids" IEEE Transactions on Visualization and Computer Graphics, vol. 7(2), pp. 97-108, April 2001.
  - H. Widjaya, T. Möller, A. Entezari, "Voxelization in Common Sampling Lattices", Proceedings of Pacific Graphics 2003 (PG03), pp. 497-501, 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):247-258, March 1995.
  - T. Blu, M. Unser, "Quantitative Fourier Analysis of Approximation Techniques: Part I-Interpolators and Projectors," IEEE Transactions on Signal Processing, 47(10):2796-2806, October 1999.
  - M. Unser, T. Blu, "Fractional splines and wavelets," SIAM Review, 42 (1):43-67, 2000.
  - P. Thevenaz, T. Blu, M. Unser, "Interpolation Revisited," IEEE Transactions on Medical Imaging, 19(7):739-758, July 2000.
  - T. Blu, M. Unser, "A Complete Family of Scaling Functions: The (\alpha, \tau)-Fractional Splines," Proceedings of the Twenty-Eighth IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'03), Hong Kong SAR, People's Republic of China, April 6-10, 2003, vol. VI, pp. 421-424.
  - P. Thevenaz, M. Unser, "Precision Isosurface Rendering of 3-D Image Data", IEEE Transactions on Image Processing, 12(7):764-775, July 2003.
  - D. Van De Ville, T. Blu, M. Unser, W. Philips, I. Lemahieu, R. Van de Walle, "Hex-splines: A novel spline family for hexagonal lattices," IEEE Transactions on Image Processing, 13(6):758-772, June 2004.
  - M. Unser, T. Blu, "Generalized Smoothing Splines and the Optimal Discretization of the Wiener Filter," IEEE Transactions on Signal Processing, 53(6):2146-2159, 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. 11-18, 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. 39-48, 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," TR-186-2-02-11, Institute of Computer Graphics and Algorithms, Vienna University of Technology, December 2002.
  - B. Csébfalvi, "Prefiltered Gaussian Reconstruction for High-Quality Rendering of Volumetric Data sampled on a Body-Centered Cubic Grid" IEEE Visualization 2005 (Vis 2005), pp. 311-318, 2005.
- Image Processing 3D - Rendering
  - Thomas Theußl, Torsten Möller, Eduard Gröller, "Optimal Regular Volume Sampling", Proceedings of IEEE Visualization 2001, pp. 91-98, October 2001.
  - N. Neophytou, K. Mueller, "Space-time points: 4D Splatting on effcient grids," Symp. Volume Visualization and Graphics '02, pp. 97-106, 2002.
  - J. Sweeney, K. Mueller, "Shear-Warp Deluxe: The Shear-Warp algorithm revisited," Eurographics / IEEE TCVG Symp. Visualization 2002, pp. 95-104, May 2002.
  - T. Welsh, K. Mueller, "A frequency-sensitive point hierarchy for images and volumes," IEEE Visualization '03, pp. 425-432, 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. 81-94, 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. 113--122, October 1982.
  - P. Suetens, Fundamentals of Medical Imaging, Cambridge University Press, 2002.
- Medical - optimal lattices
  - R.M. Lewitt, "Multi-dimensional digital image representations using generalized Kaiser-Bessel window functions," J. Opt. Sec. Am. A, vol. 7, no.10, pp. 1834-1846, 1990.
  - S. Matej, R.M. Lewitt, "Efficient 3D grids for image reconstruction using spherically-symmetric volume elements," IEEE Trans. Nuclear Science, vol. 42, no 4, pp 1361-1370, 1995.
  - S. Matej, R.M. Lewitt, "Practical considerations for 3-D image reconstruction using spherically symmetric volume elements, IEEE Trans. Medical Imaging, vol. 15, no. 1, pp. 68-78, 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. S-66, 1996.
  - K. Mueller, R. Yagel, J.J. Wheller, "Anti-aliased 3D cone-beam reconstruction of low-contrast objects with algebraic methods," IEEE Trans. Medical Imaging, vol. 18, no. 6, pp. 519-537, 1999.
- Crystallography/Modeling
  - J. Morey, K. Sedig, "Adjusting degree of visual complexity: an interactive approach for exploring four-dimensional polytopes," The Visual Computer, Vol 20, Issue 8-9, 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.