_
`
`3D GRAPHICS
`
`Symposium Chair
`Michael Zyda
`Program C0-Chairs
`Pat Hanrahan
`Jim Winger
`
`Sponsored by the Association for
`Computing Machinery's Special
`Interest Group on Computer
`Graphics
`
`BUNGIE - EXHIBIT 1006 - PART 1 OF :14
`
`BUNGIE - EXHIBIT 1006 - PART 1 OF 14
`
`

`
`I Proceedings
`1995 Symposium on
`Interactive 3D Graphics
`
`Monterey, California
`April 9 -12, 1995
`
`Symposium Chair
`
`Michael Zyda, Naval Postgraduate School
`
`Program Co-Chairs
`
`Pat Hanrahan, Stanford University
`Jim Winget, Silicon Graphics, Inc.
`
`Program Committee
`
`Frank Crow, Apple Computer
`Andy van Dam, Brown University
`Michael Deezing, Sun Microsystems
`Steven Feiner, Columbia University
`Henry Fuchs, UNC - Chapel Hill
`Thomas Funkhouser, Bell Labs
`Fred Kjtson, Hewlett—Packard
`Randy Pausch, University of Virginia
`Paul Strauss, Silicon Graphics, Inc.
`Andy Witkin, Carnegie-Mellon University
`David Zeltzer, Massachusetts Institute of Technology
`
`Financial support provided by the following organizations:
`
`Office of Naval Research, Advanced Research Projects Agency
`U.S. Army Research Laboratory
`Apple Computer
`G AT&T Bell Laboratories
`Cyberware
`Hewlett—Packard
`
`Microsoft Corporation
`Silicon Graphics, Inc.
`Sun Microsystems
`
`Production Editor
`
`Stephen Spencer, The Ohio State University
`
`
`
`Sponsored by the Association for Computing Machinery's Special Interest Group on Computer Graphics
`
`

`
`The Association for Computing Machinery, Inc.
`1515 Broadway, 17th Floor
`New York, NY 10036
`
`Copyright © 1995 by the Association for Computing Machinery, Inc. Copying without fee is permit-
`ted provided that the copies are not made or distributed for direct commercial advantage and credit to
`the source is given. Abstracting with credit is permitted. For other copying of articles that carry a code
`at the bottom of the first page, copying is permitted provided that the per—copy fee is paid through the
`Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923. For permission to republish
`write to Director of Publications, Association for Computing Machinery. To copy otherwise, or re-
`publish, requires a fee andfor specific permission.
`
`Orders from ACM Members:
`
`A limited number of copies are available at
`the ACM member discount. Send order with
`payment in U.S. dollars to:
`
`ACM Order Department
`P.O. Box 12114
`Church Street Station
`New York, NY 10257
`
`OR, for information on accepted European
`currencies and exchange rates, Contact
`
`ACM European Service Center
`Avenue Marcel Thiry 204
`1200 Brussels
`
`Belgium '
`Tel: +32 2 774 9602
`Fax: +32 2 774 9690
`Email: acm_europa@acm.org'
`
`Credit card orders from US. and Canada:
`1-800-342-6626
`-
`
`Credit card orders may also be placed by
`mail.
`
`Credit card orders from the New York
`metropolitan area and outside the
`U.S.:
`
`+1 212-626-0500
`
`Single-copy orders placed by fax:
`+1 212-944-1318
`
`Electronic mail inquiries may be directed to
`acmhe lp@-acm.o:t:g.
`
`Please include your ACM member
`number and the ACM order number
`with your order:
`
`ACM Order Number: 429953
`ACM ISBN: 0-89791-736-7
`
`

`
`Table of Contents and Symposium Program
`
`Preface .............................................................................................................................................................-4
`Monday, April 10, 1995
`
`8:00 — 8:15
`
`Welcome
`
`8:15 — 10:15
`
`Session 1: Virtual Reality
`Chair: Henry Fuchs — University ofNorth Carolina, Chapel Hill
`
`Resolving Occlusion in Augmented Reality .................................................................................................... 5
`Matthias M.‘ Wloka and Brian G. Anderson
`
`Surface Modification Tools in a Virtual Environment Interface to a Scanning Probe Microscope ............ .. 13
`M. Finch, M. Falvo, ‘VL. Chi, S. Washburn, M. Taylor, and R. Sapeifine
`Color Plates ............................................................................................................................................... .. 203
`Combatting Rendering Latency .................................................................................................................. .. 19
`Marc Olano, Jon Cohen, Mark Mine and Gary Bishop
`Color Plates ............................................................................................................................................... .. 204
`Underwater Vehicle Control from a Virtual Environment Interface ..................... .. ..................................... 25
`Stephen D. Fleischer, Stephen M. Rock and Michael J. Lee
`Color Plates
`Session 2: Geometric Modeling
`Chair: Paul Strauss — Silicon Graphics, Inc.
`
`Interactive Design, Analysis, and Illustration of Assemblies ....................................................................... 27
`Elana Driskill and Elaine Cohen
`
`Hierarchical and Variational Geometric Modeling with Wavelets ............................................................ .. 35
`Steven J. Gortler and Michael F. Cohen
`Color Plates ............................................................................................................................................... ..205
`
`Interactive Shape Metamorphosis ............................................................................................................... ..43
`David T. Chen, Andrei State and David Banks
`Color Plates ............................................................................................................................................... .. 205
`Lunch
`
`Session 3: Rendering Systems
`Chair: Michael Deering — San Microsystems
`
`Shadow Volume BSP Trees for Computation of Shadows in Dynamic Scenes
`Yiorgos Chrysanthoti and Mel Slater
`
`11:00 — 12:05
`
`12:05 — 1:30
`
`1:30 — 3: 10
`
`Interactive Display of Large—Scale NURBS Models .................................................................................. .. 51
`Sabodh Kmnar, Dinesh Manocha and Anselmo Lastra
`Color Plates
`Real—Tin1e Programmable Shading
`Anselmo Lastra, Steven Molnar, Marc Olano and Ynlan Wang
`Color Plates
`
`59
`
`...207.
`
`4:00 »— 5:00
`
`8:00 — 9:30
`
`Interactive Full Spectral Rendering
`Mark S. Peercy, Benjamin M. Zhn and Daniel R. Baarn
`Color Plates
`Session 4: Benefits of Exchange Between Computer Scientists and Perceptual Scientists
`Chair: Randy Patisch — University of Virginia
`Panel: Robert Egglesron — Wright-Patterson AFB, Steve Ellis a NASA Ames, Mary Kaiser — NASA
`Ames, Jack Loomis — UCSB, Dennis Profiitt — University of Virginia
`Session 5: Government Programs on Virtual Environments 8: Real-Time Interactive 3})
`Chair: Michael Zyda, Naval Postgraduate School
`Panel: Rick Satava — ARPA, Craig Wier —ARPA, Ralph Wachter — ONR, Patti Stay — ARL
`
`

`
`Tuesday, April 11, 1995
`
`8:30 -10:10
`
`Session 6: Parallel and Distributed Algorithms
`Chair.‘ Frank Crow —Apple Computer
`
`Interactive Volume Visualization on a Heterogeneous Message—Passing Multicomputer
`A. State, J. McAlh'sier, U. Neamarm, H. Chen, T. J. Cullip, D. T. Chen and H. Fuchs
`Color Plates ............................................................................................................................................... .. 208
`
`69
`
`The Sort-First Rendering Architecture for High-Performance Graphics ................................................... .. 75
`Carl Mueller
`
`Color Plates
`RING: A Client—Server System for Mu1ti—User Virtual Environments ...................................................... .. 85
`Thomas A. Fmikhoaser
`Color Plates
`
`NPSNET: A Multi—Player 3D Virtual Environment over the Internet
`M. R. Macedonia, D. P. Brutzman, M. J. Zyda, D. R. Pratt, P. T. Barham, J. Falby and J. Locke
`Color Plates ............................................................................................................................................... .. 210
`
`93
`
`11:00 -12:10
`
`Session 7: Virtual Environments
`Chair: Thomas Fimkhoaser — AT&T Bell Laboratories
`
`Visual Navigation of Large Environments Using Textured Clusters ......................................................... .. 95
`Paulo W. C. Maciel and Peter Shirley
`"
`Color Plates
`
`Guided Navigation of VirtualEnvironments 103
`Tirisley A. Galyeari
`Color Plates
`
`Portals and Mirrors: Simple, Fast Evaluation of Potentially Visible_ Sets
`David Laebke and Chris Georges
`Color Plates ............................................................................................................................................... .. 212
`
`105
`
`Interactive Playing with Large Synthetic Environments .......................................................................... .. 107
`Bruce F. Naylor
`ColorPlates
`
`l2:10— 1:30
`
`Lunch
`
`1:30-2:50
`
`Session 8: Input and Output Techniques
`Chair: Randy Pausch — University of Virginia
`
`Of Mice and Monkeys: A Specialized Input Device for Virtual Body Animation .................................. .. 109
`Chris Esposito, W. Bradford Paiey and JueyChong Ong
`Color Plates ............................................................................................................................................... .. 213
`
`A Virtual Space Teleconferencing System that Supports Intuitive Interaction
`for Creative and Cooperative Work
`M. Yoshida, Y. Tijerino, S. Abe and F. Kishiao
`
`Haptic Rendering: Prograrnrning Touch Interaction With Virtual Objects
`K. Salisbury, D. Brock, T. Massie, N. Swamp and C. Zilles
`
`115
`
`123
`
`4:00 — 5:00
`
`Session 9: Invited Speaker
`
`
`
`

`
`Wednesday, April 12, 1995
`
`8:30-10:10
`
`Session 10: Interactive Manipulation
`Chair: David Zeltzer — MIT Research Laboratory ofElectronics
`
`Object Associations: A Simple and Practical Approach to Virtual 3D Manipulation ............................. .. 131
`Richard W. Bakowski and Cario H. Sequin
`Color Plates ............................................................................................................................................... ..214
`
`Ca1nDroid: A System for Implementing Intelligent Camera Control ................. .: ................................... .. 139
`Steven M. Dracker and David Zeltzer
`
`3D Painting on Scanned Surfaces ............................................................................................................. ..145
`Maneesh Agrawaia, Andrew C. Beers and Marc Levoy
`Color Plates ............................................................................................................................................... .. 215
`
`Volume Sculpting
`Sidney W. Wang and Arie L‘. Kaufinan
`Color Plates ............ ..‘.............................................................................................
`
`151
`
`.................................. .. 214
`
`11:00 ~ 12:10
`
`Session 11: Applications
`Chair: Steven Feiner — Columbia University
`
`l2:10~ 1:30
`
`l:30~2:45
`
`The Tecate Data Space Exploration Utility .............................................................................................. .. 157
`Peter Kochevar and Len Wanger
`
`An Environment for Real—Lime Urban Simulation
`William Jepson, Robin Liggett and Scott Friedman
`Color Plates ............................................................................................................................................... .. 216
`
`165
`
`Mathenautics: Using Virtual Reality to Visit 3-D Manifolds ................................................................... ..167
`R. Hudson, C. Gann, G. K. Francis. D. J. Sandin and T. A. DeFanti
`
`Tracking A Turbulent Spot in an Immersive Environment ...................................................................... ..171
`David C. Banks and Michael Kelley
`Color Plates ............................................................................................................................................... .. 216
`Lunch
`
`Session 12: Physical and Behavioral Simulation
`Chair: Fred Kitson - HewletI—Packara' Labs
`
`Behavioral Control for Real-Time Simulated Human Agents
`John P. Granieri, Welton Becket, Barry D. Reich, Jonathan Crabtree and Norman 1. Badier
`
`173
`
`Impulse-based Simulation of Rigid Bodies .............................................................................................. .. 181
`Brian Mirtich and John Canny
`Color Plates ............................................................................................................................................... ._ 217
`
`I—COLL]DE: An Interactive and Exact Collision Detection System for Large—Scale Environments
`J. D. Cohen, M. C. Lin, D. Manocha and M. K. Ponamgi
`Color Plates ............................................................................................................................................... ..218
`
`189
`
`3:30 —4:30
`
`Keynote Address: Interactive 3D Graphics: Challenges and Opportunities
`Henry Fuchs — University of North Carolina, Chapel Hill
`Chair: Andy van Dam w Brown University
`
`Closing Remarks
`Conference Chairs: Pal Hanrahan, Jim Winger and Michael Zyda
`
`AuthorIndex 197
`Cover Image
`199
`Color PlateSection
`
`

`
`Preface
`
`This proceedings represents the technical papers and pro-
`gram for the 1995 Symposium on Interactive 3D Graphics. This
`symposium is the fourth in a series of what is hopefully a per-
`manent conference whose focus is on the topic: Where is the
`frontier today in real—time interactive 3D graphics? 3D graph-
`ics is becoming ever more prevalent as our workstations and
`personal computers speed up. We have in-home users of 3D
`today with 486 PCs and Doom. By the end of 1995, we will be
`seeing $250 home 3D gaming machines running 100,000 tex-
`tured polygons per second. Because of this impending wide-
`spread usage of 3D graphics, we need a conference dedicated
`to real-time, interactive 3D graphics and interactive techniques.
`
`We received 96 paper submissions for this symposium.
`This is a record for the symposium series and is particularly
`notable in that we did not even have a conference chair for the
`
`symposium untilthe last day of SIGGRAPH '94. We accepted
`22 full length papers and 11 short papers. The reasoning be-
`hind the short papers category was that ther were some inter-
`esting submissions that would provide a great live demo but
`for which there was not sufficient material for a full length
`technical paper. We have such flexibility in this smaller con-
`ferenoe.
`
`One of the major changes for the 1995 symposium is our
`status with respect to ACM SIGGRAPH. ACM SIGGRAPH
`has always provided “in cooperation” status in the past but none
`of the past symposium chairs has wanted to fill out the “daunt-
`ing” paperwork required for “sponsored by" status. Donna
`Baglio of ACM convinced the symposium chair that it wasn’t
`so difficult and it wasn’t. “Sponsored by” means ACM
`SIGGRAPH guaranteed that all bills are paid. Such guarantees
`allow the symposium’s chair to sleep easier. The “sponsored
`by" status was facilitated by supporters on the SIGGRAPH
`Executive Committee. In particular, Steve Cunningham and
`Mary Whitton helped out enormously, getting the TMRF signed
`off and approved rapidly! Steve also pointed us in the right
`direcion for getting ACM SIGGRAPH to include the proceed-
`ings in the SIGGRAPH Member Plus program, which means
`distribution of the proceedings to more than 4,000 individuals.
`
`When we started circulating the call for participation for
`the symposium, we had a major coup. Robert McDermott called
`and volunteered to be Media Coordinator for the symposium.
`He had helped us with the AV for the 1990 symposium at Snow-
`bird. He volunteered to edit and produce a videotape of the
`accepted symposium papers, another symposium first. He also
`volunteered to plan the AV and computer setup for the confer-
`ence. We have plans of a significant AV setup for the sympo-
`sium, with live demos and Internet at the podium. It is very
`nice to have someone who has done this before.
`
`We had a smaller, more compact program committee than
`in the past. Our program committee contains many of the
`world’s outstanding leaders in the field of computer graphics:
`
`Frank Crow, Apple Computer
`Michael Deering, Sun Microsystems
`Steven Feiner, Columbia University
`Henry Fuchs, UNC — Chapel Hill
`Thomas Funkhonser, AT&T Bell Laboratories
`Fred Kitson, Hewlett-Packard Labs
`
`Randy Pausch, University of Virginia
`Paul Strauss, Silicon Graphics, Inc.
`Andy van Dam, Brown University
`Andy Witkin, Carnegie Mellon University
`David Zeltzer, Massachusetts Institute of Technology
`
`We take this opportunity to thank our supporters who
`helped us with equipment loans or with financial contributions
`to assure that this symposium would indeed happen. We would
`like to recognize for their generous support: Office of Naval
`Research (Ralph Wachter), Advanced Research Projects Agency
`(Rick Satava and Craig Wier), U.S. Army Research Labora-
`tory (Paul Stay), Apple Computer (Frank Crow), AT&T Bell
`Laboratories (S. Kicha Ganapathy), Cyberware (David
`Addlemau and George Dabrowski), Hewlett—Packard (Fred
`Kitson and Phil Ebersole), Microsoft Corporation (Dan Ling),
`Silicon Graphics, Inc. (Forrest Baskett), Patrick Barrett (Sun
`Microsystems), Jim Rose for his assistance with the sympo-
`sium video review and the NSF Science and Technology Cen-
`ter for Computer Graphics and Scientific Visualization. With-
`out the suppoxt of these individuals and organizations, we could
`not hold this conference. Many of these individuals have pro-
`vided financial support every year the symposium has been
`offered. Thank you very much!
`
`The Symposium is still four months away, and close to
`fully sold out! We expect that we will have to disappoint many
`dozens of people whom we simply cannot accommodate. This
`enthusiastic response attests to the wide interest that the field
`
`of 3D interactive graphics has garnered. We can only hope and
`recommend that we will not have to wait again so long to en-
`joy the next Symposium on 3D Interactive Graphics.
`
`Pat Hanrahan, Jim Winger & Michael Zyda
`January 1995
`
`
`
`

`
`Resolving Occlusion in Augmented Reality
`
`Matthias M. Wloka* and Brian G. Anderson*
`
`Science and Technology Center for Computer Graphics and Scientific Visualization,
`Brown University Site
`
`Abstract
`
`Current state-of-the-art augmented reality systems simply overlay
`computer-generated visuals on the real-world imagery, for example
`via video or optical see-through displays. However, overlays are not
`effective when displaying data in three dimensions, since occlusion
`between the real and computer-generated objects is not addressed.
`We present a video see-through augmented reality system ca-
`pable of resolving occlusion between real and computer-generated
`objects. The heart of our system is a new algorithm that assigns
`depth values to each pixel in a pair of stereo video images in near-
`real-time. The algorithm belongs to the class of stereo matching
`algorithms and thus works in fully dynamic environments. We de-
`scribe our system in general and the stereo matching algorithm in
`particular.
`
`real-time, stereo matching, occlusion, augmented re-
`Keywords:
`ality, interaction, approximation, dynamic environments
`
`I
`
`Introduction
`
`Augmented reality systems enhance the user’s vision with computer-
`generated imagery. To make such systems and their applications
`effective, the synthetic or virtual imagery needs to blend convinc-
`ingly with the real images. Towards this goal, researchers study
`such areas as minimizing object registration errors [2] and overall
`systemlag [2] [17] so as to increase the "realness” of virtual objects.
`Since occlusion provides a significant visual cue to the human
`perceptual system when displaying datain three dimensions, proper
`occlusion resolution between real and virtual objects is highly desir-
`able in augmented reality systems. However, solving the occlusion
`problem for augmented reality is challenging: little is known about
`the real world we wish to augment. For example,
`in an optical
`see-through head-mounted display (l-IMD), no information at all is
`available about the surrounding real world. In a video see-through
`HMD, however, at least a pair of 2D intensity bitmaps is available
`in digital memory.
`
`“Box 1910, Department of Computer Science, Brown Uni-
`versity, Providence, RI 02912. Phone:
`(401) 863 7600, email:
`{mmw|bga}@cs .brown. edu.
`
`Permission to copy without fee all or part of this material is
`granted provided that the copies are not made or distributed for
`direct commercial advantage, the ACM copyright notice and the
`title of the publication and its date appear, and notice is given
`that copying is by permission of the Association of Computing
`Machinery. To copy otherwise, or to republish, requires a fee
`and/or specific permission.
`1995 Symposium on Interactive 3D Graphics, Monterey CA USA
`© 1995 ACM 0-89791-736-7/95l00O4...$3.50
`
`Typical augmented reality scenarios further complicate the prob-
`lem. Because they do not restrict the real environment to be static,
`precomputing depth maps to resolve occlusion is impossible. As
`a result, occlusion between virtual and real objects needs to be
`detennined for every frame generated, i.e., at real-time rates.
`We introduce here a video see-through system capable of resolv-
`ing occlusion between real and virtual objects at close to real-tirne
`rates. We achieve these near-real-time rates by computing depth
`maps for the left and right views at half the original video image
`resolution (depth maps are thus 320 by 240 pixels). Few addi-
`tional assumptions are made on the real and virtual environments;
`in particular, both can be fully dynamic.
`The heart of our video see-through system is a new stereo match-
`ing algorithm that infers dense depth maps from a stereo pair of
`intensity bitmaps. This new algorithm trades accuracy for speed
`and thus outperfonns known stereo matching algorithms except for
`those that run on custom-built hardware. Furthermore, our algo-
`rithrn is robust:
`it does not require a fully calibrated pair of stereo
`cameras.
`
`1.1 Overview
`
`We briefly review related work in Section 2. In Section 3 we outline
`the architecture of our video see-through augmented reality system.
`The basic algorithm for stereo matching video images in close to
`real-time is explained in Section 4. Several extensions, described in
`Section 5, make the basic algorithm faster and more robust. Finally,
`in Section 6 we discuss drawbacks of the algorithm and propose
`possible future work.
`
`2 Related Work
`
`While several other augmented reality systems are described in the
`literature [3] [7] [9], none of these systems addresses the occlusion
`problem. We know of only one augmented reality system other
`than our own that attempts to correct this deficiency [10]. The
`envisioned application of the competing project E10], i.e. vinual
`teleconferencing, is more ambitious than our own, i.c. augmented
`interior design, but the basis of both systems is to compute dense
`depth maps for the surrounding real world. Preliminary results
`in [10] indicate process times of several minutes per depth map
`on an high-end workstation [1]. In contrast, we claim sub-second
`performance for depth maps of similar resolution, although our
`depth maps are not as accurate.
`
`The work by Koch [l2I also applies computer vision techniques
`to infer dense, accurate depth maps from image pairs, and uses
`this information to construct 3D graphical representations of the
`surveyed world. Unfortunately, his methods are far from real-time,
`restricted to static environments, and thus not suitable for augmented
`reality applications.
`
`

`
`Like Koch, we use a computer vision technique known as stereo
`matching to infer depth from stereo image pairs. Stereo matching
`is a Well-established research area in the computer vision literature
`[8] [5]. Nonetheless, real-time algorithms for stereo matching are
`only a recent development.
`We believe that our near-real-time stereo matching algorithm is
`new. It is faster than other published near-real-time algorithms [13]
`[15], and is excelled only by algorithms running on custom-built
`hardware [15] [14] [11] (see Table 1). However, since our algorithm
`runs on general—purpose workstations,
`it is more affordable (no
`expensive, single-use, custom-built hardware is required) and more
`flexible (none of the parameters are hard-wired) than those.
`Even though our algorithm is faster than some of those previously
`published efforts, our resulting depth maps are also less accurate.
`
`Stereo cameras
`mounted on Boom
`
`Fakespace Boom
`
` Head position
`and orientation
`
`Hardware
`l-proc. SGI Onyx
`2~proc. SGI Onyx
`2-proc. SGI Onyx
`68020 w/8
`image proc. cards
`2460ms
`256x240x16
`Sun Sparc ll
`150ms
`256x240xl6
`64 Cell iWarp
`2l80ms
`5l2x480x88
`64 Cell iWarp
`33ms
`512x512x ‘.7
`custom-design
`33ms
`256x240x30
`custom-design
`
`
`
`
`
`Matthies [12]
`
`
`
`Video out
`
`tR=left View
`G=right view):
`
`
`I-<
`match
` SGI Onyx with two 150MHz R4400 Processors
`
`
`and Rea1ityEngine II
`
`'
`
`Figure 1: Schematic of our video see—through augmented reality
`system. The inputs and outputs R, G, and B correspond to the red,
`green, and blue channels, respectively. Zr and Zg are the depth- or
`z-values for the red and green channels. respectively. Since only
`one 2-buffer is available in double-buffering mode, we first render
`the left view (red channel) completely and then the right View (green
`channel).
`
`Time
`320x240
`Stereo matching algorithm
`
`320x240
`z-value transfer per frame
`
`640x240
`RGB-value transfer per frame
`
`640x240
`Video capture
`
`1280x1024
`Rendering per frame
`
`1280x1024
`Total for stereo image pair
`
`
`
`
`
`
`
`
`
`Table 2: Results of timing tests for the various parts of our sys-
`tem, running on a 150MHz two-processor SGI Onyx with a Real-
`ityEngine II. Capturing images from video does not use the CPU,
`but does introduce an additional lag of at least l00ms. Rendering
`is highly scene-dependent— our extremely simple test scenes take
`less than l0ms to render.
`
`the right video image into the green frame-buffer, and finally render
`all computer graphics objects for the right view.
`The Fakespace Boom then displays the redfgreen augmented re-
`ality image pairs so generated as a stereo image pair. Figures 6
`and 8 and Figures 7 and 9 show two examples. The Boom also
`allows us to couple the virtual camera pair position and orientation
`
`Resolution
`320x240x30
`
`Time
`620ms
`
`32(Jx240x30
`370ms
`
`160x 1 20x15
`100ms
`64x 60x 6
`1000ms
`
`
`
`
`
`
`
`
`
`Ross [15]
`Ross [15]
`Ross [15]
`Nishihara [l3]
`Kanade [10]
`
`
`
`
`
`
`Table 1: Running times of our stereo matching algorithm com-
`pared with previous real-time or near-real-time stereo matching
`algorithms. Resolution is the resolution of the generated depth map
`in r, y, and depth, i.e., the range of possible disparity values for a
`matched point.
`
`3 System Description
`
`Figure 1 outlines the architecture of our augmented reality sys-
`tem. Two black and white video cameras are mounted on top of
`a Fakespace Boom. The cameras need to be aligned so that their
`epipolar lines‘ roughly coincide with their horizontal scan-lines.
`Unfortunately, simply aligning the cameras’ outer housings is in-
`sufficient due to large manufacturing tolerances in internal image
`sensor-array alignments (for example, our cameras had a pitch dif-
`ference of several degrees). While we achieved alignment of :l:3
`pixels manually by trial and error, less time-consuming options are
`available; for example, the images could be aligned in software [4]
`or by using calibrated off-the-shelf hardware [16].
`The cameras continuously transmit gen-locked left/right video
`image pairs, such as shown in FigLu'es 2 and 4,
`to die red and
`green inputs of a Sirius video card. The Sirius video card digitizes
`the analogue video signal and transfers the bitmaps into the main
`memory of an SGI Onyx.
`We then apply the stereo matching algorithm described in Sec-
`tion 4 to the image pair. Figures 3 and 5 show the resulting depth
`maps. We copy the z-values for the left image into the z-buffer and
`transfer the left video image to the red frame-buffer. Since every
`pixel of the video image now has an associated z-value, we simply
`render all computer graphics objects for the left view — z-buffering
`- resolves all occlusion relations.
`The procedure is repeated for the right view: we clear the 2-
`~ buffer, copy the generated z—values for the right View into it, transfer
`
`‘An epi-polar line is the intersection of the image plane with the
`plane defined by the projection centers of the two cameras and an
`arbitrary point in the 3D world space.
`
`

`
`
`
`Figure 2: Left video camera image. Using this and the right video
`image, we infer depth for every pixel in the video image in near-
`real-time.
`
`Figure 4: Right video camera image.
`
`directly with those of the video camera pair. Therefore, the com-
`puter graphics objects are rendered with the same perspective as the
`video images.
`While our system is video see-through, the same setup is used
`for optical see-through systems. Instead of a Fakespace Boom, the
`user wears a head-mounted optical see-through display and a pair
`of head-mounted video cameras. The video signal is processed as
`before, except that the video images are never transferred to the
`frame-buffer. Therefore, only the computer graphics objects —
`properly clipped by the generated z-values to occlude only more
`distant objects — are displayed on the optical see-through display.
`The various parts of our system require varying amounts of com-
`pute time. Table 2 shows the results of our timing tests. While
`the stereo-frame rate of roughly two updates per second is still an
`order of magnitude too slow for practical augmented reality sys-
`tems, our work may guide hardware architects to address the needs
`for faster and more affordable video processing hardware. AIterna~
`
`tively, resolution of the depth maps or video images may be reduced
`further.
`
`4 Basic Algorithm
`
`The new stereo matching algorithm we use to infer depth for the
`video images is central to our occlusion-resolving augmented reality
`system. Like all other stereo matching algorithms, it works by
`matching points in the left image to points in the right image and
`vice versa. Once the relative image positions of a pair of matched
`points are established, triangulation is used to infer the distance of
`the matched points to the cameras [8}.
`Our algorithm is area-based, i.e., it attempts to match image areas
`to one another. It works in five phases.
`
`4.1
`
`Phase One
`
`In the first phase, we subsample the original video image. Currently,
`we operate at half the resolution of tlie video images. Higher (lower)
`resolution gives more (less) accurate results while slowing down
`
`
`
`Figure 3: Our new stereo matching algorithm produces a half-
`resolution, approximate depth map for the left and right camera-
`view in near-real-time. The depth map for Figure 2 is shown here.
`
`Figure 5: The computed depth map for Figure 4.
`
`
`
`

`
`
`
`Figure 6: Real and virtual imagery are combined via the standard
`z-buffer algorithm. Here, a virtual sphere occludes and is occluded
`by real-World objects in the left camera view.
`
`Figure 8: The right view of the scene in Figure 6.
`
`(speeding up) the algorithm.
`
`4.2 Phase Two
`
`The second phase analyzes the vertical pixel spans of the subsam-
`pled video images for sudden changes in intensities; the vertical
`pixel span is split at the points at which such a change occurs.
`Figures 10 and 12 illustrate the result of this operation.
`
`4.3 Phase Three
`
`The third phase generates the individual areas or blocks. A block
`is part of a vertical pixel span whose length is delimited by the
`splits introduced in the second phase of the algorithm. Therefore,
`all the pixels belonging to a particular block vary little in intensity
`(otlierwise the second phase would have generated a split). Ac-
`cordingly, only a few parameters suffice to describe a block:
`its
`
`2: and 3: position, its length, the average intensity of all its pixels,
`and the standard deviation of the intensities. To ensure that average
`intensity and standard deviation properly characterize a block. we
`impose aminimum length of3 pixels.
`
`4.4 Phase Four
`
`The fourth phase of our algorithm matches blocks in the left image
`to blocks in the right image and vice versa. We compare every
`given block with all blocks in the other image that share the same
`horizontal scan-lines to find the best match.
`(This is less work
`than a full search because the range of possible disparity values
`restricts the number of blocks we must examine; see Figure It
`and also Section 5.2.) Two blocks match if the differences in their
`y~p0sition. their length, their average intensity, and their standard
`deviation are below preset tolerances. The resulting depth estimates
`for the left and right block are entered intothe depth map for the
`left and right image, respectively. The differences in the matching
`blocks’ parameters are also recorded and used to weight the depth
`
`
`
`Figure 7: To visualize depth we let a virtual screen—aligned disk
`occlude and be occluded by real-World objects. Due to errors in the
`computed depth map for the video image, occlusion is not always
`