An updated version of this paper will appear in the ACM's Ninth Annual Symposium on User Interface Software and Technology

3D Magic Lenses

John Viega, Matthew J. Conway, George Williams, and Randy Pausch

User Interface Group

Department of Computer Science

University of Virginia, Thornton Hall

Charlottesville, VA 22903

{viega, conway, williams, pausch}@cs.virginia.edu

ABSTRACT

This work extends the metaphor of a see-through interface embodied in Magic Lenses(TM) to 3D environments. We present two new see-through visualization techniques: flat lenses in 3D and volumetric lenses. We discuss implementation concerns for platforms that have programmer accessible hardware clipping planes and show several examples of each visualization technique. We also examine composition of multiple lenses in 3D environments, which strengthens the flat lens metaphor, but may have no meaningful semantics in the case of volumetric lenses.

KEYWORDS

Magic lenses, transparent user interfaces, clipping planes, 3D graphics, virtual reality.

INTRODUCTION

Magic lenses [2] are transparent user interface elements for windowing desktop environments that extend the metaphor of a magnifying glass to include any sort of useful visual transformation of application data. Magic lenses are presented to users as translucent sheets that float above application windows, changing the output of the application only within the lens window. Users can create compound transformations (e.g., magnify, then apply a blur) by carefully stacking multiple lenses, which work by applying their effects from back to front. With the exception of a few demonstrations, (see Related Work section) the design space of translucent user interfaces remains largely unexplored in immersive, head-tracked 3D environments. This work explores some of issues involved in creating translucent 3D interfaces, and how they differ from the 2D case. We present two classes of 3D magic lens: flat lenses embedded in a 3D environment and volumetric lenses that change 3D objects in a finite region defined by the extent of the lens.

We have implemented both types of lenses, exploiting SGI Reality Engine hardware support for clipping planes [1] in our implementation.

Figure 1: An X Ray volumetric lens.

FLAT LENSES IN A 3D ENVIRONMENT

The most important properties of traditional 2D Magic Lenses continue to hold when flat lenses are carried into 3D applications. The user can preview changes in a limited region of the scene while maintaining context and multiple flat lenses can be composed to create complex effects by stacking them one in front of another along the user's line of sight.

In 2D environments, lenses apply not to entire objects, but only to the portion of the application covered by the lens. Similarly, to keep with the lens metaphor in a 3D environment, a flat lens should only affect that portion of the scene that is visible through the lens, regardless of its orientation to the viewer. The parts of the 3D scene visible through such a frame is a volume objects we call the lens frustum.

To quickly calculate the lens frustum, we cast a ray from the eye point of the user through each of the corners of the lens. These rays form the walls of a six sided volume, capped at he near end with the lens itself and at the other end with the view frustum's far clipping plane. Note that this lens frustum is not rigid like a standard camera frustum because the lens's orientation changes with the movement of both the lens and the user's head (in a head tracked environment). Now that we know the volume of space that the lens is going to affect, shown in figure 2, we need to change the way the graphics are rendered inside this volume.

To achieve this effect, objects may need to be rendered differently over parts of a polygon. Dynamically subdividing polygons in software would be extremely costly, but can be done efficiently with hardware support for clipping planes. By using hardware to subdivide the polygons and by rendering objects multiple times, we can implement flat lenses in 3D applications.

Figure 2: Flat lenses change parts of the polygons. In perspective this requires intersecting the six faces of the lens frustum with each of the polygons in the scene.

The rendering hardware of the Silicon Graphics Reality Engine 2 [1], allows programmers to define up to six infinite cutting planes. While we can easily arrange three cutting planes at mutual right angles that can cut out three-dimensional corner cross sections of an object [9], it is not possible to arrange six cutting planes together to form a lens frustum that only excludes what falls inside the frustum in a single rendering pass. Six planes arranged in a box-like configuration with the "clip away" direction pointed into the box would clip away all parts of the object. Opposite facing clipping planes each define an infinite half space to remove, the union of which is all of space, leaving nothing behind. Clipping planes of finite extent would be more helpful but most rendering hardware currently supports only infinite clipping planes.

Figure 3: Facing clipping planes clip all of space.

We might consider implementing finite-range clipping planes in software, but we believe that clipping polygons to finite planes would be too computationally expensive to be done efficiently at interactive rates.

Our implementation is a straightforward engineering compromise: we render all objects potentially affected by a given lens once for each side of the lens frustum, for a maximum total of six times in the case of a single lens. If the object intersects a side of the lens frustum, the part of the object that falls outside the lens gets rendered.

After we have rendered an object once per face of the lens frustum in this manner, we will have rendered any part of the object not within the clipping volume at least once, leaving a "hole" where the lens frustum passes through the object. All that remains is to render the part of the object that falls inside the lens frustum using whatever effect the lens was supposed to bring (wireframe, color change, scale, etc.). To do this, we reverse the clipping direction of the clipping planes (to exclude everything outside the lens) and render once more. The algorithm in pseudocode is:


for each face F of the lens frustum:
	for each object OBJ in the scene: 
	# render the "un-lensed" graphics outside
	# the lens frustum.
		render OBJ against clip plane F, 
		removing the part of F inside the lens frustum
	# render the "lensed" graphics inside
	render OBJ against this set of clipping planes using "lens
        semantics," removing the part of F outside the lens frustum

Note that parts of individual objects outside the lens may be rendered multiple times.

COMPOSING FLAT LENSES

The ability to create new and interesting effects by overlapping two or more transparent tools is one of the most powerful features of magic lenses.

Figure 4: Overlapping lenses can create concave polygons in the plane.

To compose lenses in 2D requires computing the intersection regions of the lenses and the effects they have on the application underneath.

A similar operation happens in 3D for flat lenses, but the regions being intersected are not simple 2D shapes, but 3D lens frustums. The order of composition is easy: back to front of the stacked "lens planes." Overlapping lenses will of course create irregular shapes as seen in figure 4. In a simple case, where both lenses are parallel to the view volume, the situation looks like the one in figure 5, except that the results are not L-shaped polygons in the plane but concave polyhedra in space.

Figure 5: Overlapping lenses can create concave polygons in the plane.

Overcoming Concave Regions

The "one lens" algorithm given above fails in the face of concave regions; the concavity causes graphics to appear where another plane of the lens frustum would have excluded it.

Figure 6: Clipping objects against concave volumes.

To solve this problem, we first divide concave volumes into multiple convex volumes, and apply our algorithm for each volume. To keep the clipping of one convex sub-volume from rendering into another, we place another clipping plane along the surface that partitions them and we keep that clipping plane on as we iterate over the faces of the lens frustum. Note that as we add more overlapping lenses, the resulting shapes can become very complex and we run the risk of running out of hardware clipping planes, making it impossible to proceed. Currently, we have not implemented this solution.

Handling Regions with More Than Six Sides

An SGI Reality Engine only supports six active clipping planes at any one time in addition to the six that define the camera's view frustum. Unfortunately, with many overlapping lenses, we will create subvolumes that will require modeling a surface of more than six faces at once. We note, however, that it is possible to have different planes on at different times during the traversal of the object data-structure, so long as no more than six planes are active at any given moment. Therefore, when clipping out the exterior of an object, we can clip to volumes with more than six faces by dividing the lens sub-volume into multiple six faced volumes, with the same restrictions we suffer when clipping concave spaces.

Since our approach often requires multiple rendering passes, it lends itself best to systems such as Inventor [14], which uses attribute bundles, and directed acyclic graphs. However, tree-based systems can implement this model with some additional overhead by making multiple copies of objects, and linking their behaviors.

Using the simplest implementation of our approach, one would have to re-render all of the objects that could potentially be affected by the lens once per face of the clip volume. However, we could apply a visible surface determination algorithm [4] to decide which objects only need to be rendered once, and thereby decrease the cost of rendering.

Examples of Flat Lenses in Space

We have implemented several flat lenses in three- dimensional environments that use our techniques, including versions of the lenses used in the Virtual Tricorder [15] that are free standing objects, as opposed to objects conceptually attached to a CRT.

VOLUMETRIC LENSES

While two-dimensional lenses certainly have their place in a three-dimensional environment, there are cases when we might want to limit the effects of a lens to a finite volume. For example, when rendering a large 3D data set, we may need to cull away large parts of the data set. We have implemented several Volumetric Lenses using some of the same techniques as used to create flat lenses in 3D environments.

The 3D lens volume is akin to the lens frustum we calculated to implement 2D lenses, in that it defines the area to be affected. Unlike the flat lens whose frustum changes shape as the user shifts his or her head, the shape of the volume lens is rigid. The other difference between 3D and flat lenses is that flat lenses have their far plane determined by the far clipping plane of the view frustum. 3D lenses must explicitly specify all sides. Other than these minor differences, objects can be clipped to the outside and inside of a 3D volumetric lens using essentially the previously described approach.

Examples of 3D Volumetric Lenses

Graph Culling: We have implemented a 3D lens that culls large data sets. By placing a lens over a collection of points in space, we can see a mesh graph of those points. This is implemented by clipping the points to the inside of the box, and clipping the graph to the outside of the box. Using the lens metaphor on data sets provides computational efficiency, in that one can use such a lens to restrict the parts of a data set being rendered.

X Ray Vision: We have also implemented an X-ray volumetric lens. When the user passes the X-ray lens over an object, the object disappears, revealing what is inside. For example, passing the lens over a model of a hand will reveal a skeletal version of that hand, as shown in figure 1. Of course, while the user sees the hand changing as he passes the lens over it, in this example we are not rendering the hand differently, we are rendering a second model registered to the same X,Y,Z location.

Figure 7: A volumetric lens cuts into a model of the Earth to reveal the structure within.

A volumetric X-ray lens is useful as a tool for peeling away layers of an object. For example, we have built an application consisting of an onion skin lens, along with a model of the earth positioned in front of the user. The user can use the lens to "peel away" layers of the earth, as shown in figure 7.

The Worlds In Miniature (WIM): Previous work in virtual environments that we can also think of as a 3D volumetric lens is the Worlds In Miniature (WIM)[13], shown in figure 8. The WIM is an immersive interaction technique for manipulating objects at a distance, for navigating, gaining a second, exocentric point of view from inside an immersive environment. The immersed user holds a miniature version of his environment in his hand, represented in physical space by a clipboard. When the user makes changes to the miniature world, the change is simultaneously reflected in his virtual environment. The WIM is a small scale active map.

Figure 8: The WIM Interaction technique for immersive worlds can be thought of as a volumetric reduction lens.

We have found it helpful to think of the miniature version of the environment as a "reduction lens" that is a window onto the full scale virtual environment.

COMPOSITION OF 3D LENSES

For 2D lenses, even in a 3D environment, the order of composition is clearly defined by the order in which lenses appear between the user and objects visible behind the lenses. For volumetric lenses, there is no such natural ordering; in some cases where two lenses physically overlap there may be no natural back to front ordering. When this occurs, we can assign priority to the lenses using any scheme that makes sense (e.g., order in which the lenses were applied).

Another problem with composition is that it is difficult to implement complex interactions efficiently. In our implementation, lenses subdivide space. Each time one adds a lens that can partially overlap another lens or multiple lenses, semantically different regions of space are created. Our technique requires that for each space, one establishes a set of clipping planes for that space, and then renders into that space.

Consider a 3D lens that magnifies its contents, and a 3D lens that renders its contents as wireframe. If these two lenses overlap, a separate rendering pass will be required for the following spaces:

Space not in either lens
Space within the magnification lens only
Space within the wireframe lens only
Space within both lenses

In addition to the large number of spaces created, calculating the boundaries of these spaces is a complex computational geometry problem. Also, the spaces formed by lens intersection can easily have more facets than can be supported in a single rendering pass, which would add even more rendering overhead.

This problem is less of a concern with 3D lenses than with 2D lenses, as composition in 3D breaks the lens metaphor which is primarily 2D; physical volumes usually do not intersect each other in the real world.

FUTURE DIRECTIONS

This work is concerned with the output characteristics of 3D lenses and we have only begun to think about the input modifications that a 3D toolglass [2] might offer. Reaching into a space for access to a mode seems like a natural extension to the existing 2D lens metaphor, and will clearly have to be pursued with an eye toward two- handed interaction [5]. We would also like to explore the potential of using 3D lenses to support temporal preview of time-based state (crystal balls), in transportation portals that allow a user to travel from place to place by stepping through lenses [10], and in behavior lenses that allow the user to preview and apply interesting actions to objects.

RELATED WORK

Magic Lenses and Toolglasses [2] use two-dimensional see-through widgets as tools for view filtering and visualization. This idea has been incorporated into many systems including Pad++ [3] and Self [12] and the most recent version of the popular Kai's Power Tools for Adobe Photoshop. Several systems have demonstrated the utility of using three dimensional objects as data filters. Luebke and Georges have developed a system for quickly determining potentially visible parts of the scene to be rendered into a portal [8]. They render the view of another part of the world into the portal, and therefore affect the entire region behind the portal in the user's line of sight. Clip volumes have been used in at least one system for improving 3D spatial reasoning [9]. Osborn's system used the metaphor of a pool of water into which objects could be submerged. Liang's JDCAD is a 3D modeling system in which the user manipulates the clipping planes with a six degree of freedom input device, allowing modelers to dynamically remove a half-space, quarter-space, or an eighth-space of the three-dimensional object being modeled [7]. Hinkley has explored user control of prop-based spatial operations that modify parts of a three-dimensional data-set [6].

CONCLUSION

We have extended the metaphor of Magic Lenses to three-dimensional graphics. Traditional Magic Lenses and Toolglasses map nicely to three-dimensional applications, but are difficult to implement due to hardware limitations. We have also introduced the 3D lens, which is a Magic Lens or Toolglass with a volume, that affects objects contained within the volume. We have demonstrated how such tools can be efficiently implemented on common rendering hardware.

ACKNOWLEDGEMENTS

We would like to thank Joe Shochet and Dale Newfield for their help in preparing this paper. Artists Liz West and Beth Mallory contributed the hand-painted textures; Rich Stoakley and Steve Audia built the 3D models used in this paper. All of our applications were built using Alice [11], an interactive 3D graphics programming environment developed by the User Interface Group at the University of Virginia. Magic Lenses (TM) is a Trademark of Xerox Corporation.

REFERENCES

[1] Kurt Akeley, RealityEngine Graphics, Proceedings of 1993 ACM SIGGRAPH Conference, 109-116.

[2] Eric A. Bier, Maureen C. Stone, Ken Pier, William Buxton, Tony D. DeRose, Toolglass and Magic Lenses: The See-Through Interface, Proceedings of 1993 ACM SIGGRAPH Conference, 73-80.

[3] Benjamin B. Bederson, James D. Hollan, Pad++: A Zooming Graphical Interface for Exploring Alternate Interface Physics, Proceedings of the 1994 ACM UIST Conference. 17-26.

[4] James D. Foley, Andires van Dam, Steven K. Feiner, John F. Hughes, Computer Graphics Principles and Practice, Addison Wesley, 1990. 649-720.

[5] Yves Guiard, Asymmetric Division of Labor in Human Skilled Bemanual Action: The Kinematic Chain as a Model, Journal of Motor Behavior, Volume 19, Number 4, 1987, 486-517.

[6] Ken Hinckley, Randy Pausch, John C. Goble, Neal F. Kassell, Passive Real-World Interface Props for Neurosurgical Visualization, Proceedings of the 1994 ACM SIGCHI Conference. 452-458.

[7] Jiandong Liang, Mark Green, JDCAD: A Highly Interactive 3D Modeling System, Proceedings of the 3rd International Conference on CAD and Computer Graphics, 1993. 217-222.

[8] David Luebke and Chris Georges, Portals and Mirrors: Simple, Fast Evaluation of Potentially Visible Sets, Proceedings of the 1995 ACM Symposium on Interactive 3D Graphics, 105-106.

[9] James R. Osborn, Alice M. Agogino, An Interface for Interactive Spatial Reasoning and Visualization, Proceedings of the 1992 ACM SIGCHI Conference, 75-82.

[10] Randy Pausch, Tommy Burnette, Dan Brockway, Michael E. Weiblen, Navigation and Locomotion in Virtual Worlds via Flight into Hand-Held Miniatures, Proceedings of the 1995 ACM SIGGRAPH Conference, 399-400.

[11] Randy Pausch, et al., Alice: A Rapid Prototyping System for Vitrual Reality, IEEE Computer Graphics and Applications, May 1995 8-11. http://www.cs.virginia.edu/~alice

[12] Randall B. Smith, John Maloney and David Ungar, The Self-4.0 User Interface: Manifesting a System- wide Vision of Concreteness, Uniformity, and Flexibility, Proceedings of the 1995 ACM OOPSLA Conference. 47-60.

[13] Richard Stoakley, Matthew Conway, Randy Pausch, Virtual Reality on a WIM: Interactive Worlds in Minature, Proceedings of the 1995 ACM SIGCHI Conference.

[14] Paul S. Strauss and Rikk Carey, An Object- Oriented 3D Graphics Toolkit, Proceedings on the 1992 ACM SIGGRAPH Conference, 341-349.

[15] Matthias M. Wloka and Eliot Greenfield, The Virtual Tricorder: A Uniform Interface for Virtual Reality, Proceedings of the 1995 ACM UIST Conference, 39-40.