Abstract
We describe the first image-space ray-tracing algorithm to generate interior views of flat or hyperbolic 3-manifolds, orbifolds, and similar polyhedral complexes. The complexity of our algorithm is linear in the number of echoes for a given number of polygons, compared to exponential complexity for the object-space algorithm chosen as standard.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
In comparison with previous work, our algorithm can render ray paths 25 times deeper than the ones in object-space algorithms (see Sect. 7). This is a significant improvement even if we consider the recent development in graphics hardware.
References
Amenta, N., Levy, S., Munzner, T., Phillips, M.: Geomview: a system for geometric visualization. In: Proceedings of the Eleventh Annual Symposium on Computational Geometry, SCG ’95, pp. 412–413. ACM, New York (1995)
Arvo, J., Kirk, D.: An introduction to ray tracing. A Survey of Ray Tracing Acceleration Techniques, pp. 201–262. Academic Press Ltd., London (1989)
Boileau, M., Maillot, S., Porti, J.: Three-dimensional orbifolds and their geometric structures, volume 15 of Panoramas et Synthèses [Panoramas and Syntheses]. Société Mathématique de France, Paris (2003)
Burton, B.: Introducing regina, the 3-manifold topology software. Exp. Math. 13(3), 267–272 (2004)
Damour, T., Henneaux, M., Nicolai, H.: Cosmological billiards. Class. Quant. Grav. 20, R145–R200 (2003)
Francis, G.K., Goudeseune, C.M.A., Kaczmarski, H.J., Schaeffer, B.J., Sullivan, J.M.: Alice on the eightfold way: exploring curved spaces in an enclosed virtual reality theatre. In: Visualization and Mathematics III, pp. 305–315 (2003)
Gunn, C.: Advances in metric-neutral visualization. In: Skala, V., Hitzer, E. (eds.) GraVisMa 2010, pp. 17–26. Eurographics, http://gravisma.zcu.cz/GraVisMa-2010/GraVisMa-2010-proceedings.pdf (2010)
Gunn, C., Maxwell, D.L.: Not knot, http://www.geom.uiuc.edu/video/NotKnot/ (1991)
Gunn, C.: Discrete groups and visualization of three-dimensional manifolds. In: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’93, pp. 255–262. ACM, New York (1993)
Haefliger, A.: Orbi-espaces. In: Sur les groupes hyperboliques d’après Mikhael Gromov (Bern, 1988), volume 83 of Progr. Math., pp. 203–213. Birkhäuser, Boston (1990)
Hanson, A.J., Munzner, T., Francis, G.: Interactive methods for visualizable geometry. Computer 27(7), 73–83 (1994)
Hudson, R., Gunn, C., Francis, G.K., Sandin, D.J., DeFanti, T.A.: Mathenautics: using vr to visit 3-d manifolds. In: Proceedings of the 1995 Symposium on Interactive 3D Graphics, I3D ’95, pp. 167–170. ACM, New York (1995)
Munzner, T., Burchard, P.: Visualizing the structure of the world wide web in 3d hyperbolic space. In: Proceedings of the First Symposium on Virtual Reality Modeling Language, VRML ’95, pp. 33–38. ACM, New York (1995)
Phillips, M., Gunn, C.: Visualizing hyperbolic space: unusual uses of 4\(\times \)4 matrices. In: Proceedings of the 1992 Symposium on Interactive 3D Graphics, I3D ’92, pp. 209–214. ACM, New York (1992)
Thurston, W.P.: The Geometry and Topology of Three-Manifolds. Princeton University, Princeton (1979)
University of Minnesota. The geometry center, http://www.geom.uiuc.edu/ (1994)
von Gagern, M., Richter-Gebert, J.: Hyperbolization of Euclidean Ornaments. Electron. J. Combin. 16(2), 1–29 (2009)
Weeks, J.: The Shape of Space, http://www.geom.uiuc.edu/video/sos/ (1995)
Weeks, J.: Snappea, http://www.geometrygames.org/SnapPea/ (1999)
Weeks, J.: Real-time rendering in curved spaces. IEEE Comput. Graph. Appl. 22(6), 90–99 (2002)
Weeks, J.: Real-time animation in hyperbolic, spherical, and product geometries. In: Prékopa, A., Molnár, E. (eds.) Non-Euclidean Geometries. Mathematics and Its Applications, vol. 581, pp. 287–305. Springer, Berlin (2006)
Weeks, J.R.: The shape of space. Pure and Applied Mathematics. Marcel Dekker, New York (2002)
Weismann, S., Gunn, C., Brinkmann, P., Hoffmann, T., Pinkall, U.: jreality: a java library for real-time interactive 3d graphics and audio. In: ACM Multimedia’09, pp. 927–928 (2009)
Author information
Authors and Affiliations
Corresponding author
Appendix: Polyhedral complexes that are not orbifolds
Appendix: Polyhedral complexes that are not orbifolds
Here are examples of spaces that are possible to render with this new algorithm, but (presently) not with the previous ones.
A flat polyhedral complex that is not an orbifold Let \(P\) denote the regular planar octagon centered at 0. The angle of \(P\) are all equal to \(3\pi /4\). The product of \(P\) with \([0,1]\) is a polyhedron of the Euclidean space \(\mathbb E^3\). As before, we glue the opposite faces with translations.
The polyhedral complex obtained is topologically the product of torus of genus 2 with a circle. However, it is not anymore diffeomorphic to it. The quotient identifies all the vertical edges and immerses them to a circle; in the polyhedral complexes, around this circle the angle is \(6\pi \). To be an orbifold, the angle must be a divisor of \(2\pi \).
A hyperbolic polyhedral complex that is not an orbifold The same construction can be done for any hyperbolic polyhedron. Then the dihedral angle between the faces is not necessarily a divisor of \(2\pi \) and so the polyhedral complex is not necessarily a differentiable orbifold. Such a generality occurs for instance in [5], where the Einstein equation near a singularity is modeled by the geodesic flow on a (irregular) hyperbolic polyhedron, the faces of which are mirrors.
Rights and permissions
About this article
Cite this article
Berger, P., Laier, A. & Velho, L. An image-space algorithm for immersive views in 3-manifolds and orbifolds. Vis Comput 31, 93–104 (2015). https://doi.org/10.1007/s00371-013-0913-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-013-0913-2