Visualizing 3D scenes using non-linear projections and data mining of previous camera movements

ABSTRACT

We describe techniques for exploring 3D scenes by combining non-linear projections with the interactive data mining of camera navigations from previous explorations. Our approach is motivated by two key observations: First, that there is a wealth of information in prior explorations of a scene that can assist in future presentations of the same scene. Second, current linear perspective camera models produce images that are too limited to adequately capture the complexity of many 3D scenes. The contributions of this paper are two-fold. First, we show how spatial and temporal subdivision schemes can be used to store camera navigation information that is data mined and clustered to be interactively applicable to a number of existing techniques. Second, we show how the movement of a traditional linear perspective camera is closely tied to non-linear projections that combine space and time. As a result, we present a coherent system where the navigation of a conventional camera is data mined to provide both the understandability of linear perspective and the flexibility of non-linear projection of a 3D scene in real-time. Our system's generality is illustrated by three visualization techniques built with a single data mining and projection infrastructure.

REFERENCES

• 1: Maneesh Agrawala , Denis Zorin , Tamara Munzner, Artistic Multiprojection Rendering, Proceedings of the Eurographics Workshop on Rendering Techniques 2000, p.125-136, June 26-28, 2000
• 2: Doug A. Bowman , David Koller , Larry F. Hodges, Travel in Immersive Virtual Environments: An Evaluation of Viewpoint Motion Control Techniques, Proceedings of the 1997 Virtual Reality Annual International Symposium (VRAIS '97), p.45, March 01-05, 1997
• 3: Nicholas Burtnyk , Azam Khan , George Fitzmaurice , Ravin Balakrishnan , Gordon Kurtenbach, StyleCam: interactive stylized 3D navigation using integrated spatial & temporal controls, Proceedings of the 15th annual ACM symposium on User interface software and technology, October 27-30, 2002, Paris, France [doi>10.1145/571985.572000]
• 4: M. S. T. Carpendale , Catherine Montagnese, A framework for unifying presentation space, Proceedings of the 14th annual ACM symposium on User interface software and technology, November 11-14, 2001, Orlando, Florida [doi>10.1145/502348.502358]
• 5: Marianne Sheelagh Therese Carpendale , F. David Fracchia, A framework for elastic presentation space, 1999
• 6: Rudolph P. Darken , John L. Sibert, Wayfinding strategies and behaviors in large virtual worlds, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.142-149, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238459]
• 7: Drucker, S. M., & Zeltzer, D. (1994). Intelligent camera control in a virtual environment. Graphics Interface. p. 190--199.
• 8: T. Todd Elvins , David R. Nadeau , Rina Schul , David Kirsh, Worldlets: 3D thumbnails for 3D browsing, Proceedings of the SIGCHI conference on Human factors in computing systems, p.163-170, April 18-23, 1998, Los Angeles, California, United States [doi>10.1145/274644.274669]
• 9: G. W. Furnas, Generalized fisheye views, Proceedings of the SIGCHI conference on Human factors in computing systems, p.16-23, April 13-17, 1986, Boston, Massachusetts, United States
• 10: Tinsley A. Galyean, Guided navigation of virtual environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.103-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199421]
• 11: Michael Gleicher , Andrew Witkin, Through-the-lens camera control, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.331-340, July 1992
• 12: Jonas Gomes , Lucia Darsa , Bruno Costa , Luiz Velho, Warping and morphing of graphical objects, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 13: Andrew J. Hanson , Eric A. Wernert, Constrained 3D navigation with 2D controllers, Proceedings of the 8th conference on Visualization '97, p.175-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 14: Li-wei He , Michael F. Cohen , David H. Salesin, The virtual cinematographer: a paradigm for automatic real-time camera control and directing, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.217-224, August 1996 [doi>10.1145/237170.237259]
• 15: Takeo Igarashi , Rieko Kadobayashi , Kenji Mase , Hidehiko Tanaka, Path drawing for 3D walkthrough, Proceedings of the 11th annual ACM symposium on User interface software and technology, p.173-174, November 01-04, 1998, San Francisco, California, United States [doi>10.1145/288392.288599]
• 16: Inakage, M. (1991). Non-linear perspective projections. IFIP WG5.10. p. 203--215.
• 17: Susanne Jul , George W. Furnas, Critical zones in desert fog: aids to multiscale navigation, Proceedings of the 11th annual ACM symposium on User interface software and technology, p.97-106, November 01-04, 1998, San Francisco, California, United States [doi>10.1145/288392.288578]
• 18: Kaufman, L., & Rousseeuw, P. (1990). Finding groups in data: An introduction to cluster analysis. John Wiley & Sons.
• 19: Laurini, R., & Thompson, D. (1992). Fundamentals of spatial information systems. Academic Press..
• 20: Levene, J. (1991). A framework for non-realistic projections. Masters Thesis thesis. MIT.
• 21: Jock D. Mackinlay , Stuart K. Card , George G. Robertson, Rapid controlled movement through a virtual 3D workspace, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.171-176, September 1990, Dallas, TX, USA
• 22: D. Martín , S. García , J. C. Torres, Observer dependent deformations in illustration, Proceedings of the 1st international symposium on Non-photorealistic animation and rendering, p.75-82, June 05-07, 2000, Annecy, France [doi>10.1145/340916.340926]
• 23: Shmuel Peleg , Benny Rousso , Alex Rav-Acha , Assaf Zomet, Mosaicing on Adaptive Manifolds, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1144-1154, October 2000 [doi>10.1109/34.879794]
• 24: Gregory Piateski , William Frawley, Knowledge Discovery in Databases, MIT Press, Cambridge, MA, 1991
• 25: Paul Rademacher, View-dependent geometry, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.439-446, July 1999 [doi>10.1145/311535.311612]
• 26: Paul Rademacher , Gary Bishop, Multiple-center-of-projection images, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.199-206, July 1998 [doi>10.1145/280814.280871]
• 27: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.151-160, August 1986
• 28: Steven M. Seitz , Charles R. Dyer, View morphing, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.21-30, August 1996 [doi>10.1145/237170.237196]
• 29: Singh, K. (2002). A fresh perspective. Graphics Interface. p. 17--24.
• 30: Anthony Steed, Efficient navigation around complex virtual environments, Proceedings of the ACM symposium on Virtual reality software and technology, p.173-180, September 1997, Lausanne, Switzerland [doi>10.1145/261135.261167]
• 31: Desney S. Tan , George G. Robertson , Mary Czerwinski, Exploring 3D navigation: combining speed-coupled flying with orbiting, Proceedings of the SIGCHI conference on Human factors in computing systems, p.418-425, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365307]
• 32: Eric A. Wernert , Andrew J. Hanson, A framework for assisted exploration with collaboration, Proceedings of the conference on Visualization '99: celebrating ten years, p.241-248, October 1999, San Francisco, California, United States
• 33: George Wolberg, Digital Image Warping, IEEE Computer Society Press, Los Alamitos, CA, 1994
• 34: Daniel N. Wood , Adam Finkelstein , John F. Hughes , Craig E. Thayer , David H. Salesin, Multiperspective panoramas for cel animation, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.243-250, August 1997 [doi>10.1145/258734.258859]
• 35: Robert Zeleznik , Andrew Forsberg, UniCam—2D gestural camera controls for 3D environments, Proceedings of the 1999 symposium on Interactive 3D graphics, p.169-173, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300546]
• 36: Robert C. Zeleznik , Andrew S. Forsberg , Paul S. Strauss, Two pointer input for 3D interaction, Proceedings of the 1997 symposium on Interactive 3D graphics, p.115-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253316]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Viewing algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

General Terms:
Algorithms, Design, Human Factors

Keywords:
camera visualization, data mining, non-linear projection