EXHIBIT 1001
`
`EXHIBIT 1001
`
`

`

`(12) United States Patent
`Lim
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006172679Bl
`US 6,172,679 Bl
`Jan. 9,2001
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) VISIBILITY CALCULATIONS FOR 3D
`COMPUTER GRAPHICS
`
`(76)
`
`Inventor: Hong Lip Lim, 35 Ellie Park Avenue,
`Singapore, 1545 (SG)
`
`( *) Notice:
`
`Under 35 U.S.c. 154(b), the term of this
`patent shall be extended for 0 days.
`
`(21) Appl. No.: 08/935,150
`
`(22) Filed:
`
`Sep. 22, 1997
`
`5,159,663 * 10/1992
`5,253,335 * 10/1993
`5,268,996 * 12/1993
`5,295,243 * 3/1994
`5,299,298 * 3/1994
`5,313,568 * 5/1994
`5,377,313
`12/1994
`5,402,532
`3/1995
`5,414,801
`5/1995
`5,448,686
`9/1995
`5,914,721 * 6/1999
`
`Fossum ................................ 345/422
`Mochizuki et al.
`................. 345/422
`Steiner et al.
`....................... 345/426
`Robertson et al.
`.................. 345/348
`Elmquist et al.
`.................... 345/421
`Wallace et al. ...................... 345/426
`Scheibl.
`Epstein.
`Smith.
`Borrel .
`Hong Lip Lim
`
`345/421
`
`FOREIGN PATENT DOCUMENTS
`
`Related U.S. Application Data
`
`0481 581
`2228850
`
`4/1992 (EP).
`9/1990 (GB).
`
`(63) Continuation of application No. 08/182,096, filed on Jun. 1,
`1994.
`
`(30)
`
`Foreign Application Priority Data
`
`Jun. 28, 1991
`Jul. 19, 1991
`Oct. 1, 1991
`Oct. 1, 1991
`Oct. 30, 1991
`
`(AU) ................................................. PK 6942
`(AU) ................................................. PK 7305
`(AU) ................................................. PK 8643
`(AU) ................................................. PK 8645
`(AU) ................................................. PK 9218
`
`Int. CI? ..................................................... G06T 15/40
`(51)
`(52) U.S. CI. ............................................. 345/421; 345/422
`(58) Field of Search ........................... 345/418-22, 433-9
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,594,673 * 6/1986 Holly ................................... 345/421
`4,625,289 * 11/1986 Rockwood ........................... 345/422
`4,697,178
`9/1987 Heckel.
`4,819,192
`4/1989 Kuragano et al. .
`4,825,391 * 4/1989 Merz .................................... 345/431
`4,855,938 * 8/1989 Gonzalez-Lopez et al.
`........ 345/422
`4,901,252
`2/1990 Fitzgerald et al. .
`4,918,626 * 4/1990 Watkins et al. ...................... 345/421
`4,928,250 * 5/1990 Greenberg et al. .................. 345/426
`5,027,292 * 6/1991 Matsumoto .......................... 345/422
`5,058,042 * 10/1991 Hanna et al.
`........................ 345/427
`5,081,698
`1/1992 Kohn.
`5,084,830 * 1/1992 Doornink et al.
`5,086,496
`2/1992 Mulmuley.
`5,088,054
`2/1992 Paris, II .
`
`............... 345/139 X
`
`OTHER PUBLICATIONS
`
`"Stabbing Isothetic Boxes & Rectangles ini O(n 19 n) time",
`M. Hohmeyer S. 1. Teller, 1991.*
`"A Characterization of Ten Hidden-Surface Algorithms", I.
`E. Sutherland, R.F. Sproull, R. A. Schumacker Computing
`Surveys, vol. 6, No.1, 1975. *
`"Fast Algorithms for 3D-Graphics", G. Glaeser, 1994. *
`
`(List continued on next page.)
`
`Primary Examiner-Mark R. Powell
`Assistant Examiner---Chante' Harrison
`(74) Attorney, Agent, or Firm-Oppedahl & Larson LLP
`
`(57)
`
`ABSTRACT
`
`Disclosed is a method of reducing the complexity of hidden
`surface removal in 3D grapghic systems. A fuzzy projection
`(FF) of a surface (SU) as seen from a number of viewpoints
`(VP) in a bounding box (BB) is stored in a buffer (FA)
`having elements (FE). A combination of all the patches (PT)
`of the surface (SU) viewed form a fuzzy region (FR) where
`surfaces can be either visible, hidden, or unable to be
`determined with certainty as to whether or not visible/
`hidden. A non-fuzzy region (NF) describes those patches
`(PT) that are always visible.
`
`32 Claims, 17 Drawing Sheets
`
`

`

`US 6,172,679 Bl
`Page 2
`
`OlliER PUBLICATIONS
`
`"Advances in Fuzzy Sets, Possibility and Applications",
`1983.*
`H. Xu Q. Peng, "Accelerated radiosity method for complex
`environments", Eurographics '89, 1989.*
`Application Challenges to Computational Geometry, CG
`Impact Task Force Report CG Impact Task Force Technical
`Report TR-521-96, Princeton University 1996. *
`Computer Graphics, Principles and Practice, 2nd edition
`J.D. Foley A. van Dam S. K. Feiner J.P. Hughes.*
`New Trends in Animation and Visualization N. Thalmann D.
`Thalmann 1991.*
`Graphics Systems; Architecture & Realization R. Andreov
`1993.*
`Analysis of Radiosity Techniques in Computer Graphics B.
`Kwok MSc Thesis York University, May 1992.*
`Image display data computer forming method-uses per(cid:173)
`spective transformation with calculation time reduction on
`shadow and hidden surface processing Sony 86.233751/36. *
`Stabbing and ray shooting in 3 dimensional space M.
`Pellegrini 1990.*
`The Geometry of Beam Tracing N. Dadoun D. Kirkpatrick
`1985.*
`Algorithms for line transversals in space D. Avis CG1987.
`Optimization of the binary space partition algorithm (BSP)
`for the visualization of dynamic scenes E. Torres Eurograph(cid:173)
`ics'90.*
`A mathematical Scm antics of Rendering II. Approximation
`E. Fiume CVGIP: Graphical Models and Image Processing
`vol. 53, No.1, Jan. 1991. *
`A Characterization of Ten Rasterization Techniques N. Ghu(cid:173)
`rachorloo S. Gupta R. Sproull I. Sutherland Computer
`Graphics, vol. 23, No.3 (Siggraph'89) 1989.*
`The use of projective geometry in Computer Graphics I.
`Herman 1992.*
`Ray Tracing with Cones J. Amanatides Computer Graphics,
`vol. 18, No.3 (Siggraph'84) 1984.*
`The A-buffer, an Antialiased hidden surface method L.
`Carpenter Computer Graphics, vol. 18, No.3, (Siggraph'84)
`1984.*
`Principles and Applications of Pencil Tracing M. Shinya T.
`Takahashi S. Naito Computer Graphics, vol. 31, No.4,
`(Siggraph'87) 1987. *
`Light-water interaction using backward beam tracing M.
`Wall Computer Graphics, vol. 24, No. 4 (Siggraph'90)
`1990.*
`Rendering CSG Model with a ZZ-buffer D. Salcsin J. Stolli
`Computer Graphics, vol. 24, No.4 (Siggraph'90) 1990.*
`A solution to the hidden-line problem for computer-drawn
`polyhedra P. Loulrel IEEE Transactions on Computers, Mar.
`1970.*
`Sorting and the hidden-surface problem I. Sutherland R.
`Sproull R. Schumacker National Computer Conference,
`1970.*
`The Notion of quanitative invisibility and the machine
`rendering of solids A Appel ACM National Meeting 1967. *
`An analytic visible surface algorithm for independent pixel
`processing E. Catmull Computer Graphics, vol. 18, No.3
`(Siggraph'84) 1984. *
`Computing the lines piercing four lines S. Teller M. Hohm(cid:173)
`eyer Technical Report 92-665, University of California,
`Berkeley. *
`
`Computing the antipenumbra of an area light source S.
`Teller Computer Graphics, vol. 36, No.2, (Siggraph'92)
`1992.*
`Computer animation, theory and practice, second revised
`edition N. Thalmann D. Thalmann 1990, Image Sythesis M.
`Brest 1992.*
`Management of large amounts of data in interactive building
`walkthroughs T. Funkhouser C. Sequin S. Teller Symposium
`on Interactive 3D Graphics, 1992.*
`Temporal Coherence in Ray Tracing S. H. Badt PhD thesis,
`University of Texas at Dallas, 1989. *
`Near real-time shadow generation using BSP trees N. Chin
`S. Feiner Computer Graphics, vol. 23, No.3 (Siggraph'89)
`1989.*
`Adaptive Display algorithm for interactive frame rates dur(cid:173)
`ing visualization of complex virtual environments T. Funk(cid:173)
`houser C. H. Sequin Siggraph'93 1993. *
`Modeling global diffuse illumination for image synthesis A.
`Campbell, III. PhD Thesis University of Texas at Austin
`1991.*
`A 3--dimensional representation for fast rendering of com(cid:173)
`plex scenes S. Rubin T. Whitted 1980.*
`Radiosity redistribution for dynamic environment D. George
`F. Sillion D. Greenberg IEEE Computer Graphics & Appli(cid:173)
`cations, vol. 4, 1990.*
`A survey of shadow algorithms A. Woo, F. Poulin A.
`Fournier IEEE Computer Graphics & Applications, vol. 6,
`1990.*
`Error-bounded antialiased rendering of complex environ(cid:173)
`ments N. Greene M. Kass Siggraph'94 1994.*
`Fast computation of shadow boundaries using spatial coher(cid:173)
`ence and backprojections A. Stewart S. Ghali Siggraph'94
`1994.*
`A fast shadow algorithm for area light sources using back(cid:173)
`projection G. Drettakis E. Fiume Siggraph'94 1994.*
`Stabbing oriented convex polygons in randomized O(n-2)
`time. S. Teller M. Hohmeyer Contemporary Mathematics,
`1994.*
`Obscuration culling on parallel graphics architecture C.
`George Technical report TR95-017 University of North
`Carolina at Chapel Hill 1995.*
`Visibility between two edges of a simple polygon D. Avis T.
`Gum G. Goussaint The Visual Computer, 1986, No. 2.*
`Increasing update rates in the building walkthrough system
`with automatic model-space subdivision and potentially
`visible set calculations J. M. Airey PhD Thesis, University
`of North Carolina, 1990.*
`Realism in computer graphics: a survey. J.Amanatides IEEE
`Computer Graphics and Applications, vol. 7, No.1, 1987.*
`Finding a line transversal of axis objects in three dimensions
`N. Amenta Proc. 3rd Annual ACM-SIAM Symposium on
`Discrete Algorithms, 1992.*
`Beyond the third dimension, geometry, computer graphics
`and higher dimension Banchoff T. F. Scientific American
`Library 1990. *
`A general version of crow's shadow volumes Bergeron P.
`IEEE Computer Graphics and Applications, vol. 6, No.9,
`Sep. 1986.*
`Me and my (fake shadow) Blinn, J. F. IEEE Computer
`Graphics and Applications, vol. 8, No.1 1988.*
`Generating soft shadows with a depth buffer algorithm
`Brotman L. S. IEEE Computer Graphics and Applications
`vol. 4, No. 10, 1984.*
`
`

`

`US 6,172,679 Bl
`Page 3
`
`A multiresolution spline with application to image mosaics
`Burt P.J. Adelson E. H. ACM Transactions on Graphics, vol.
`2, Oct. 1983. *
`Hierarchical geometric models for visible surface algo(cid:173)
`rithms Clark, J. H. Communications of the ACM, vol. 19,
`No. 10, Oct. 1976.*
`An overview of rendering techniques Dennis A. R. Com(cid:173)
`puter & Graphics, vol. 14, No.1, 1990.*
`Hybrid shadow testing scheme for ray tracing Eo K. S.
`Kyung C. M. Computer Aided Design vol. 21, No. 1 Jan.
`1989.*
`Hierarchical rendering of complex environments Greene, N.
`PhD dissertation, University of California, Santa Cruz
`1995.*
`Bibliography of hidden-line and hidden-surface algorithms
`Griffiths, J. G. Computer-Aided Design, vol. 10, May
`1978.*
`The light buffer: a shadow-testing accelerator Haines, E.A.
`Greenberg, D. IEEE Computer Graphics and Applications,
`vol. 6, No.9, Sep. 1986.*
`Algorithms for antialiased cast shadows Houreade J. C.
`Nicolas A. Computer and Graphics, vol. 9, No.3 1985.*
`Hemi-cube ray-tracing; a method for generating soft shad(cid:173)
`ows Meyer U. Proceedings, Eurographics'90, 1990. *
`Principles of interactive computer graphics, 2nd edition
`Newman, W. M. Sproull, R. E 1979.*
`Principles of interactive computer graphics, 1st edition
`Newman, W. M. Sproull, R. E 1973.*
`A comparison of four visibility acceleration techniques for
`radiosity Ng, A. The visual computer, 1996, vol. 12, pp.
`307-316.*
`Shading models for point and linear sources Nishita, T.
`Okamura, I. Nakamse, E. ACM transactions on graphics,
`vol. 4, No.2, Apr. 1985.*
`Radiosity of dynamic scenes in flatland with the visibility
`complex Orti, R. Riviere S. Durand E Pucch C. Proceedings,
`Eurographics'96 1996.*
`Visibility, occlusion, and the aspect graph Plantinga H. Dyer
`C. R. International Journal of computer vision, vol. 5, No.2,
`1990.*
`Necessary and sufficient conditions for hyperplane transver(cid:173)
`sal Pollack R. Wenger R. Proc. 5th Annual Symposium on
`Computational Geometry, 1989.*
`Shading and shadowing with linear light sources Poulin P.
`Amanatides J. Proceedings, Eurographics '90 1990. *
`Rendering antialiased shadows with depth maps Reeves W.
`Salesin D. Cook R. Proceedings, Siggraph'87 1987.*
`Machine perception of three-dimensional solids Roberts L.
`G. Optical and Electro-Optical Information Processing, J.
`Tippett (editor) MIT Press, 1965.*
`Procedureal elements for computer graphics Rogers D. P.
`McGraw-Hill(publisher) 1985. *
`Optics B. Rossi Addison-Wesley(publisher) 1957.*
`An optimal algorithm for detecting weak visibility of a
`polygon J. Sack S. Suri IEEE transactions on computers,
`vol. 39, No. 10, Oct. 1990. *
`Shaded rendering and shadow computation for polyhedral
`animation Seales W. B. Dyer C. R. Proceedings, Graphics
`Interface '90, May 1990.*
`Optics, third edition Sears F. W. Addison-Wesley Publishing
`Co. 1949.*
`Linear programming and convex hulls made easy Seidol R.
`Proc. 6th ACM Symposium on COmputational Geometry,
`1990.*
`
`Output-sensitive visibility algorithms for dynamic scenes
`with applications to virtual reality Sudarsky O. Gotsman C.
`Proceedings, Eurographics' 96 1996. *
`Automatic view function generation for walk-through ani(cid:173)
`mation using a reeb graph Shinagawa Y. kunii T. Nomura Y.
`Okuna T. Young Y. Computer Animation '90 1990.*
`Octant priority for radiosity image rendering Wang Y. Davis
`W. Proceedings, Graphics Interface'90 1990.*
`Casting curved shadows on curved surfaces Williams L.
`Proceedings, Siggraph'78 1978.*
`Pyramidal parametrics William L., Proceedings, Sig(cid:173)
`graph'83 1983. *
`Accelerated radiosity method for complex environments Xu
`II. Peng Q. Liang Y. Proceedings, Eurographics'89 1989. *
`Pyramid clipping for efficient ray traversal Zwann M. Rein(cid:173)
`hard E. Jansen F. Proceedings of the Sixth Eurographics
`Rendering Workshop 1995.*
`Application challenges to computational geometry, CG
`impact task force report CG impact task force Princeton
`University Computer Science Dept. Technical Report
`TR -521-96
`http://graphics.les.mit.edu/-seth/pubs/task -
`-force/techrep.html http://www.cs.princeton.edu/--chazelle/
`taskforce/CGreport.ps.Z
`http://graphics.les.mit.edu/-seth/
`pubs/pubs.htmI1996.*
`My response to application challenges to computational
`geometry Franklin R. http://www.ecse.rpi.edu/Homepages/
`wrf/geom_response.html http://netlib.boll-Iabs.com/netlib/
`compgeom/discuss/archive/96/ta skforce.htmI1996. *
`Comments on the report "Application challenges to com(cid:173)
`putational geometry" Heckbert P. http://www.cs.duke.edu/
`-jette/compgeom/files/heckbert.html http://netlib.bell-Iab-
`-s.com/netlib/compgeom/discuss/archive/96/ta
`skforce.htmI1996. *
`Follow-up comments on the report "Application challenges
`to computational geometry" Coulson T. http://www.cs.du(cid:173)
`ke.edu/-jette/compgeom/files/coulson.html
`http://netlib(cid:173)
`.bell-Iabs.com/netlib/compgeom/discuss/archive/96/ta
`skforce.htmI1996. *
`Inside Quake: visible surface determination http://www(cid:173)
`.gamers.org/dEngine/quake/papers/ddjpvs.html 1996. *
`CGDC Quake Talk http://www.gamers.org/dEngine/quake/
`papers/mikeab-egde.html 1996.*
`Quake hidden surface removal http://www.gamers.org/
`dEngine/quake/papers/ddjzsort.html 1996. *
`Quake editing tools information http://www.gamers.org/
`dEngine/quake/QuakeEd/qedit-infor.html 1996. *
`Zen of graphics programming Abrash M. 1996.*
`Computer graphics: more unsolved problems Siggraph'91
`panel 1991. *
`Global illumination in architecture and entertainment Sig(cid:173)
`graph'96 course notes 1996.*
`Interactive walkthrough of large geometric database Sig(cid:173)
`graph'96 course notes 1996.*
`Imprecise computation and load sharing in computer gen(cid:173)
`erated imaging system Berger M. Zhao W. Graphics Inter(cid:173)
`face '90 1990.*
`Exploiting temporal coherence in ray tracing Chapman J.
`Calvert T. Sill J. Graphics Interface' 90 1990. *
`Approximate ray tracing Dauenhauer D. Graphics Interface
`'90 1990.*
`Approximate and probabilistic algorithms for shading and
`rendering structured particle systems Reeves W. Siggraph
`1985 1985.*
`
`

`

`US 6,172,679 Bl
`Page 4
`
`Fundamentals of interactive computer graphics Foley J.D.
`van Dam A Addison-Wesley Publishing Co. 1982.*
`Multi-pass multi-resolution algorithm for the determination
`of hidden surfaces Lim, H. L. Inter-faculty symposium on
`computer graphics and image processing 1987.*
`Ten Unsolved Problems in Rendering Heckbert P. S. Work(cid:173)
`shop on Rendering Algorithms and Systems, Gaphics Inter(cid:173)
`face'87 www addr: http://www.cs.cmu/-ph (index page)
`1987.*
`3D comes alive Ozer, J. PC magazine, Jun. 25, 1996.*
`Affordable 3-D workstations Hummel, R. L. Byte Dec.
`1996.*
`Gaming: in the next dimension Case, L. Salvator, D. Com(cid:173)
`puter Gaming Jul. 1996.*
`3D engine list Isakovic, K. www addr: http://www.cs.lum(cid:173)
`berline.de/-ki/engines.html 1996.*
`OpenGL the leading visual programming interface www
`addr: http://www.agi.com/ProductslDev_environ_ds.html
`1996.*
`3D computer graphics (second edition) Glassner A S.
`Design Press 1989.*
`The UC Berkeley system for interactive visualization of
`large architectural models T. Funkhouser S. Teller C. Sequin
`D. Khorramabadi Presence, vol. 5, No.1, Winter 1996. *
`Visibility computation for efficient walkthrough of complex
`environment R. Yagel R. William Presence, vol. 5, No.1,
`Winter 1996.*
`Large models for virtual environments; A review of work by
`the architectual walkthrough project at UNCM, R. Mine H.
`Weber Presence, vol. 5, No.1, Winter 1996. *
`A hidden-line algorithm for hyperspace R. P. Burton D. R.
`Smith SIAM Journal of Computing vol. 11, No.1, Feb.
`1982.*
`Canonic representations for the geometrics of multiple pro(cid:173)
`jective views Q. T. Luong T. Vieville University of Califor(cid:173)
`nia at Berkely CS Dept. Tech. Report UCB/CSD093-773
`1993.*
`Multidimensional graphing in two-dimensional spaces T.
`Mihalisin E. Gawlinski J. Timlin J. Schwegler Computers in
`Physics, Nov.lDec. 1989.*
`A framework for global illumination in animated environ(cid:173)
`ments J. Mineroll J. Dorsey H. Rushmeier Rendering Tech(cid:173)
`niques'95 (Proceedings of the Eurographics Workshop in
`Dublin, Ireland Jun. 1995.*
`Shadows for bump-mapped surfaces N. L. Max Advanced
`Computer Graphics (Proceedings of Computer Graphics
`Tokyo '86) 1986. *
`The simulation of natural features using cone tracing D. Kirk
`Advanced Computer Graphics (Proceedings of Computer
`Graphics Tokyo '86) 1986.*
`Simulating soft shadows with graphics hardward P. S. Heck(cid:173)
`bert M. Hert Carnegie-Melon University CS Dept. Techni(cid:173)
`cal Report CMU-CS-97-104 1997.*
`Spatial transformation for rapid scan-line surface shadow(cid:173)
`ing P. Robertson IEEE computer graphics & applications
`Mar. 1989.*
`Incremental update of the visibility map as seen by a moving
`viewpoint in two dimensions S. Ghali A J. Steward Euro(cid:173)
`graphics Workshop on Animation and Simulation, Aug.
`1996.*
`Z. H. Zhao D. Dobkin Continuous algorithms for visibility:
`the space searching approach fourth eurographics workshop
`on rendering 1993.*
`
`Y. Shinagawa S. Miyoshi T. Kunii Viewpoint analysis of
`drawings and paintings rendered using multiple viewpoints:
`cases containing rectangular objects Fourth Eurographics
`Workshop on Rendering 1993. *
`E Jansen A Chalmers Realism in real time Fourth Euro(cid:173)
`graphics Workshop on Rendering 1993.*
`E. Catmull, "Computer display of curved surfaces" in IEEE
`Transactions of Computers, p. 309-315, 1971.*
`M.P. Cohen et aI., "The hemi-cube: A Radiosity solution for
`complex environment", Computer Graphics (Siggraph '85),
`vol. 19, No.3, p. 31-40, 1985.*
`G.A. Crocker, "Invisibility coherence for faster scan-line
`hidden surface algorithms", Computer Graphics, vol. 18,
`No.3, p. 95-102, 1984.*
`H. Hubschman et aI., "Frame-to-frame coherence and the
`hidden surface computations: Constraints for a Convex
`World", Computer Graphics, vol. 15, No.3, p. 45-54,
`1981.*
`H.L. Lim, "Fast hidden surface removal through structural
`analysis and representation of objects and their contours",
`Computer Graphics International'87, p. 75-88, 1987. *
`H.L. Lim, "Toward a fuzzy hidden surface algorithm",
`Computer Graphics International '92, p. 621-635, 1992.*
`H.L. Lim, "An efficient hidden surface algorithm for poly(cid:173)
`hedral surfaces" in International Conference on Computer &
`Communications in Science & Technology, Beijing, China,
`1986.*
`C. Hornung, "A method for solving the visibility problem",
`IEEE Computer Graphics & Applications, vol. 4, p. 26-33,
`1984.*
`J. Griffiths, "A depth-coherence scanline algorithm for
`displaying curved surfaces", Computer-aided Design, vol.
`16, No.2, p. 91-101, 1984.*
`E.A. Haines et aI., "Shaft culling for efficient ray-traced
`radiosity", Proceedings of Eurographics Workshop on Ren(cid:173)
`dering, Jul., 1991. *
`H. Plantinga et aI., "Real-time hidden-line elimination for
`a rotating polyhedral scene using the aspect representation",
`in Graphics Interface '90 Proceedings, p. 9-16, 1990.*
`J.M. Airey et aI., "Towards image realism with interactive
`update rates in complex virtual building environment", in
`ACM Siggraph Special Issue on the 1990 Symposium on
`Interactive 3D Graphics vol. 24, p. 41-50, 1990.*
`Y. Wang, "Image synthesis using front-to-back based radi(cid:173)
`osity methods", Ph.D. thesis, University of Alberta, 1992.*
`D.R. Baum et aI., "The back-buffer algorithm: an extension
`of the radiosity method to dynamic environments", The
`Visual Computer, vol. 2, No.5, p. 298-306, 1986.*
`S.J. Teller er aI., "Visibility preprocessing for interactive
`walkthroughs", Computer Graphics, vol. 25, No.4, p.
`61-69, 1991.*
`J. Marks et aI., "Image and intervisibility coherence in
`rendering", Graphics Interface '90 Proceedings, p. 17-30,
`1990.*
`H.L. Lim, "Rendering techniques in three-dimensional
`computer graphics", Ph.D. thesis, University of Sydney,
`1993.*
`S.J. Teller, "Visibility computations in densely occluded
`polyhedral environment", Ph.D. thesis, University of Cali(cid:173)
`fornia at Berkeley, 1992.*
`AS. Glassner, "Principles of Digital Image Synthesis", vol.
`2, Morgan Kaufmann Publisher, San Francisco, 1995. *
`
`

`

`US 6,172,679 Bl
`Page 5
`
`D. Gordon et aI., "Front-to-back display of BSP trees",
`IEEE Computer Graphics & Applications, vol. 11, p. 79-85,
`1991.*
`KL. Shelley et aI., "Path specification and path coherence",
`Computer Graphics, vol. 16, No.3, p. 157-161, 1982.*
`1. Vilaplana et aI., "Exploiting coherence for clipping and
`view transformations in radiosity algorithms", in Eurograph(cid:173)
`ics Workshop on Photosimulation, Realism and Physics in
`Computer Graphics, Rennes, France, p. 137-149, 1989.*
`e.B. lones, "Anew approach to the 'hidden line' problem",
`Computer lournal, vol. 14, No.3, p. 232-236, 1971.*
`F.e. Crow, "Shadow algorithms for computer graphics",
`Computer Graphics, vol. 11, No.2, p. 442-448, 1977.*
`X. Pueyo, "The use of visibility coherence for radiosity
`computation", in First International Conference on Visual(cid:173)
`ization and Intelligent Design in Engineering and Architec(cid:173)
`ture, p. 17-28, 1993.*
`T. Nishita et aI., "Continuous tone representation of
`three-dimensional objects taking account of shadows and
`interrefiection", Computer Graphics, vol. 19, No.3, p.
`23-30,1985.*
`T. Funkhouser, "Database and display algorithms for inter(cid:173)
`active visualization of architectural models", Ph.D. thesis,
`University of California at Berkeley, 1993.*
`S.l. Teller et aI., "Global visibility algorithms for illumina(cid:173)
`tion computations", in Computer Graphics (Siggraph '93),
`vol. 27, p. 239-46, 1993. *
`S. Coorg et aI., "Temporally coherent conservative visibil(cid:173)
`ity", in Twelfth AnnualACM Symposium on Computational
`Geometry, Philadelphia, ACM Press, New York, p. 1-10,
`1996.*
`S. Coorg et aI., "A spatially and temporally coherent object
`space visibility algorithm", Laboratory of Computer Sci(cid:173)
`ence, MIT, Technical Report TM-546, 1996.*
`D.P. Luebke et aI., "Portal and mirrors: simple, fast evalu(cid:173)
`ation of potentially visible sets", in Proceedings 1995 Sym(cid:173)
`posium on Interactive 3-D Graphics, ACM Press, New
`York, 1995.*
`H. Planting a, "Conservative visibility preprocessing for effi(cid:173)
`cient walkthroughs of 3D scenes", Graphics Interface '93
`Proceedings, p. 166-173, 1993.*
`E. Catmull, "A subdivision algorithm for computer display
`of curved surfaces", Ph.D. thesis, Utah University, Dec.
`1974.*
`1. Arvo et aI., "A survey of ray tracing acceleration tech(cid:173)
`niques" in An Introduction to Ray Tracing, editor: AS.
`Glassner, Academic Press, London, p. 201-262, 1989.*
`A Watt et aI., "Advanced Animation and Rendering Tech(cid:173)
`niques, Theory and Practice", ACM Press, New York,
`1992.*
`F. Sillion et aI., "Radiosity and Global Illumination", Mor(cid:173)
`gan Kaufmann Publisher, San Francisco, 1994. *
`D.R. Baum et aI., "Improving radiosity solutions through the
`use of analytically determined form-factors", Computer
`Graphics, vol. 23, No.3, p. 325-334, 1989.*
`A. Fournier et aI., "On the power of the frame buffer", ACM
`Transaction on Graphics, vol. 7, No.2, 103-128, 1988.*
`e.W. Grant, "Integrated analytic spatial & temporal anti(cid:173)
`-aliasing for polyhedra in 4-Space", Computer Graphics,
`vol. 19, No.3, p. 79-84, 1985.*
`P. Hsiung et aI., "T -Buffer: fast visualization of relativistic
`effects in spacetime", ACM Siggraph Special Issue on the
`1990 Symposium on Interactive 3D Graphics 24, p. 83-88,
`1990.*
`
`A Inselberg, "The Plane with parallel coordinates", The
`Visual Computer, vol. 1, p. 69-91, 1985.*
`N.L. Max et aI., "A two-and-a-half-D motion-blur algo(cid:173)
`rithm", Computer Graphics (Siggraph '85), vol. 19, No.3, p.
`85-93, 1985.*
`KY. Steiner et aI., "Hidden volumes: the 4th dimension",
`Computer Graphics World, p. 71-74, Feb. 1987.*
`L.A. Zadeh, "Fuzzy Sets", Information and Control, vol. 8,
`p. 338-353, 1965.*
`W. Siedleckiet aI., "Mapping techniques for exploratory
`pattern analysis" in Pattern Recognition and Artificial Intel(cid:173)
`ligence, E.S. Gelsema, L.N. Kanal (eds), Elsevier, New
`York, p. 277-299, 1988.*
`S. Chang, "On fuzzy mapping and control", IEEE Transac(cid:173)
`tions on Systems, Man & Cybernetics, vol. SMC-2, No.1,
`p. 30-34, 1972.*
`R. lain et aI., "Imprecision in computer vision" in Advances
`in Fuzzy Sets, Possibility and Applications, P. Wang, (ed),
`Plenum Press, New York, p. 217-236, 1983. *
`N. Greene et aI., "Hierarchical z-buffer visibility", Com(cid:173)
`puter Graphics (Siggraph '93), vol. 27, p. 231-238, 1993.*
`D. Greenberg et aI., "Radiosity: a method for computing
`global illumination", The Visual Computer, vol. 2, p.
`291-297, 1986.*
`H. Fuchs et aI., "New real-time shaded display of rigid
`objects", Computer Graphics, vol. 17, No.3, p. 65-72,
`1983.*
`e.M. Hoffman et aI., "Some techniques for visualizing
`surfaces
`in four-dimensional space", Computer-aided
`Design, vol. 23, No.1, p. 83-91, 1991. *
`1.M. Lane et aI., "Scan line methods for displaying para(cid:173)
`metrically defined surfaces", Communications of the ACM,
`vol. 23, No.1, p. 23-34, 1980.*
`1.A. Gualtieri et aI., "The visual potential: one convex
`polygon", Computer Vision, Graphics and Image Process(cid:173)
`ing, vol. 46, No.1, p. 96-130, 1989.*
`Z. Gigus et aI., "Computing the aspect graph for line
`drawings of polyhedral objects", in Proceedings of IEEE
`Conference on Computer Vision and Pattern Recognition,
`Computer Society Press, New York, p. 654-661, 1988. *
`P.S. Heckbert et aI., "Beam tracing polygonal objects",
`Computer Graphics, vol. 18, No.3, p. 119-127, 1984.*
`1. Zhou, "Visualization of four dimensional space and its
`applications", Ph.D. thesis, Purdue University, 1991.*
`R. lain, "Application of fuzzy sets for the analysis of
`complex scenes" in Advances in Fuzzy Set Theory and
`Applications, M.M. Gupta et al. (eds), North-Holland,
`Amsterdam, p. 577-583, 1979.*
`D. Tost et aI., "A definition of frame-to-frame coherence",
`Computer Animation '90, p. 207-221, 1990.*
`Y. Leung, "Spatial Analysis and Planning under Impreci(cid:173)
`sion", North Holland, Amsterdam, 1988.*
`1.R. Wallace et aI, "A ray tracing algorithm for progressive
`radiosity", Computer Graphics, vol. 23, No.3, p. 315-324,
`1989.*
`H. Fuchs et aI., "On visible surface generation by a priori
`tree structure", Computer Graphics (Siggraph'80), vol. 14,
`p. 124-133, 1980.*
`M.F. Cohn et aI., "A progressive refinement approach to fast
`radiosity image generation", Computer Graphics, vol. 22,
`No.4, p. 75-84, 1988.*
`K Kanatani, "Group-theoretical Methods in Image Under(cid:173)
`standing", Springer Verlag, Berlin, 1990. *
`
`

`

`US 6,172,679 Bl
`Page 6
`
`J.K. Aggarwal et aI., "Dynamic scence analysis" in Image
`Sequence Processing and Dynamic Scene Analysis, T.S.
`Huang (ed), Springer Verlag, Berlin, p. 40-73, 1983. *
`N.I. Badler et aI., "Motion: Representation and Perception"
`Elsevier, New York, 1986.*
`Subbarao, "Interpretation of visual motion: A computational
`study", Pitman, London, 1988. *
`P. Sillion et aI., "A general two-pass method integrating
`specular and diffuse reflection", Computer Graphics, vol. 23,
`No.3, p. 335-344, 1989.*
`R.J. Recker et aI., "Acceleration Techniques for Progressive
`Refinement Radiosity", ACM Siggraph Special Issue on the
`1990 Symposium on Interactive 3D Graphics, vol. 24, p.
`59-66, 1990. *
`E. H. Ruspini, "A new approach to clustering", Information
`and Control 15, p. 22-32, 1969. *
`A. Kaufmann, "Theory of Fuzzy Subsets. Vol. I, Fundamen(cid:173)
`tal Theorectical Elements", Academic Press, London,
`1975.*
`T.S. Huang, "Image Sequence Processing", Springer Verlag,
`Berlin, 1981. *
`P.A. Ligomenides, "Modeling uncertainty in human percep(cid:173)
`tion" in Uncertainty in Knowledge-Based Systems, B. Bou(cid:173)
`chon, R. Yager (eds), Springer Verlag, Berlin, p. 337-346,
`1986.*
`A. Inselberg, "N-Dimensional Graphics. Part I. Lines &
`Hyperplanes", IBM Scientific Center Report G320-2711,
`Jul. 1981. *
`
`A.S. Glassner, "3D Computer Graphics: A User's Guide for
`Artists & Designers", 2nd edition, Design Press, New York,
`p. 139-158, 1989.*
`M.P. Cohen et aI., "Radiosity & realistic image synthesis",
`Academic, New York, 1993.*
`J. Aggarwal et aI., "Analysing dynamic scenes containing
`multiple moving objects" in Image Sequence Analysis,
`editor: T.S. Huang, Springer-Verlag, Berlin, p. 355-380,
`1981.*
`A. Appel, "The Notion of quantitative invisibility and the
`machine rendering of solids", Proceedings ACM National
`Conference, Thompson Books, Washington, DC, p.
`387-393, 1967.*
`J. Vince, "Computer Animation", Addison-Wesley, New
`York, 1992.*
`Y. Chrysanthou et aI., "Computing dynamic changes to
`'92, vol. 11, No.3, p.
`BSP-trees", Eurographics
`C-321-C-332, 1992.*
`S. Ansoldi et aI., "Geometric modeling of solid objects by
`using a face adjacency graph presentation" Computer
`Graphics (Siggraph '85), vol. 19, No.3, p. 131-138, 1985.*
`N. Chin et aI., "Fast object-precision shadow generation for
`area light sources using BSP trees", Proceedings 1992
`Symposium on Interactive 3D Graphics, p. 21-30, 1992.*
`D.S. Immel et aI., "A radiosity method for non-diffuse
`environments", Comuter Graphics, vol. 4, p. 133-142,
`1986.*
`* cited by examiner
`
`

`

`u.s. Patent
`
`Jan. 9,2001
`
`Sheet 1 of 17
`
`US 6,172,679 Bl
`
`FI G. 1A
`
`VPs
`
`FIG. 18
`
`

`

`u.s. Patent
`
`Jan. 9,2001
`
`Sheet 2 of 17
`
`US 6,172,679 Bl
`
`PT
`
`IP
`
`1'(cid:173)I """N= (Nx, Ny, Nz)
`' ".
`""
`'-
`
`I
`I
`I
`~ ___ __ -1.._
`
`I
`
`"
`
`"
`
`PO = x., y, z
`
`I
`
`I
`
`I)
`
`(
`
`I'"
`'"
`'"
`I
`I
`"",
`I
`I
`"'"
`I
`' i i -
`I
`I
`I
`I
`I
`vp= (x, y, z) i
`I
`~----I-*-
`"'"
`I ' "
`'
`"'"
`'"
`"'"
`I
`",
`"'"
`'-.
`' ......
`-L_ \ ____ ~::---
`",
`\
`PB
`' I
`'......
`I
`'-...J
`
`....
`.... ""
`
`'-~
`I
`i
`
`y
`
`f 1"4,---+--d ~k-----------1~Z :
`
`X
`
`i,,----PP
`i
`
`PF
`
`FI G. 2
`
`

`

`u.s. Patent
`
`US. Patent
`
`Jan. 9,2001
`Jan. 9, 2001
`
`Sheet 3 0f 17
`Sheet 3 of 17
`
`US 6,172,679 Bl
`US 6,172,679 B1
`
`x
`
`CI)
`U
`
`N
`
`
`
`...-
`a..
`>
`
`Intel Exhibit 1001 Page 9
`
`

`

`u.s. Patent
`
`Jan. 9,2001
`
`Sheet 4 of 17
`
`US 6,172,679 Bl
`
`0::
`I.L.
`
`I.L.
`Z
`
`-=>
`.....
`l(cid:173)e..
`
`(f)
`
`,
`
`.............
`-::::~--­
`.......
`"
`',(cid:173)
`\
`\
`I
`/
`--/
`
`C\I e..
`>
`
`.....
`co
`co
`
`\
`\
`
`\ \>
`\
`\
`
`/
`I
`
`\ \ i
`\\
`'\
`\
`
`---- ..-
`
`....
`CD e..
`
`-------:;..-:::----
`/
`/
`
`"'-
`
`I
`/
`I
`I
`\
`\
`" \
`
`1'0
`
`W e..
`
`-....
`
`"'-
`
`"-
`
`\
`
`\
`\
`\
`I
`I
`/
`I
`
`I
`
`/
`
`/
`. . - / '
`
`1'0
`CIl
`Q..
`
`\
`
`\
`"
`\
`-\---
`"'-
`\ --~-
`I
`I
`/
`
`/
`
`/
`
`/
`/ '
`
`C\I
`CD
`0..
`
`

`

`u.s. Patent
`
`Jan. 9,2001
`
`Sheet 5 of 17
`
`US 6,172,679 Bl
`
`FIG. 5A
`
`PTn
`
`LEGEND:
`
`1'--""
`\
`) BORDER OF THE FUZZY REGION
`"'---"
`
`THE FUZZY REGION OF A
`BOUNDARY EDGE
`
`NON-FUZZY REG ION
`
`FIG. 58
`
`

`

`u.s. Patent
`
`Jan. 9,2001
`
`Sheet 6 of 17
`
`US 6,172,679 Bl
`
`LEGEND:
`
`REGION COMBINING THE FUZZY
`EXTENT OF BOUNDARY EDGES
`
`APPRO