Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2004-11-12
2008-10-14
Chauhan, Ulka (Department: 2628)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S421000, C345S422000
Reexamination Certificate
active
07436414
ABSTRACT:
The invention describes a method and system for use in occlusion culling of polygons in an interactive environment, such as a game. The invention employs a boundary box to simplify the testing of occludee polygons. Occluders and occludees are also transformed into non-interpenetrating, non-overlapping polygons. Winged-edges are employed to minimize a per occludee computational cost due to precision problems that may arise at non-overlapping edges. The invention then proceeds through an active edge list to identify edge discontinuities (e.g., where an edge is added or removed from the active edge list). Depth analysis is employed to determine whether an occluder occludes an occludee at the edge discontinuity. Moreover, the invention only performs depth analysis for those locations of a screen display where an occludee is determined to reside, thereby minimizing unnecessary computations.
REFERENCES:
patent: 4928250 (1990-05-01), Greenberg et al.
patent: 4987554 (1991-01-01), Kaufman
patent: 5129051 (1992-07-01), Cain
patent: 5241656 (1993-08-01), Loucks et al.
patent: 5303340 (1994-04-01), Gonzalez-Lopez et al.
patent: 5418897 (1995-05-01), Capri et al.
patent: 5630039 (1997-05-01), Fossum
patent: 5777625 (1998-07-01), Rossin
patent: 5877768 (1999-03-01), Jain
patent: 6005574 (1999-12-01), Herrod
patent: 6052128 (2000-04-01), Narayanaswami et al.
patent: 6052129 (2000-04-01), Fowler et al.
patent: 6208352 (2001-03-01), Blackwell
patent: 6271852 (2001-08-01), Kamiyama et al.
patent: 6356271 (2002-03-01), Reiter et al.
patent: 6977652 (2005-12-01), Senda et al.
patent: 7215345 (2007-05-01), Hanko
patent: 7277102 (2007-10-01), Moore
patent: 2002/0063708 (2002-05-01), Senda et al.
patent: 2002/0097241 (2002-07-01), McCormack et al.
patent: 2002/0190995 (2002-12-01), Lim
patent: 2003/0112254 (2003-06-01), Ishihara
patent: 2004/0257607 (2004-12-01), Gupta et al.
patent: 2006/0103645 (2006-05-01), Jacobson
Foley, James D.; van Dam, Andries; Feiner, Steven K.; Hughes, John F.; “Computer Graphics, Principles and Practice;” 1996; Addison-Wesley Publishing Company; 2nd Edition; pp. 68-71, 96-99, 124-127, 545-546, 660-662, 680-685, and 855-856.
Coorg, Satyan; Teller, Seth; “A Spatially and Temporally Coherent Object Space Visibility Algorithm;” 1996, Tech. Report TM-546, Laboratory for Computer Science, MIT; pp. 1-18.
Froment, Jacques; “A Compact and Multiscale Image Model Based on Level Sets;” 1999; Scale-Space Theories in Computer Vision; pp. 1-12.
H. Hey and W. Purgathofer,Occlusion Culling Methods, STAR—State of the Art Report, Eurographics 2001.
R. Germs and F.W. Jansen,Geometric Simplification for Efficient Occlusion Culling in Urban Scenes. 2001.
William Baxter,Occlusion Culling for Walkthroughs of Large Virtual Environments, at http://www.cs.unc.edu/˜baxter/projects/occlusion.html. May 8, 2000.
Pietari Laurila,Geometry Culling in 3D engines, at http://www.gamedev.net/reference/articles/article1212.asp. Oct. 9, 2000.
A. McClennen,Draw a line(intro) at http://www.cc.gatech.edu/grads/m/Aaron.E.McClennen/Bresenham/main.html. Feb. 14, 1995.
V. Shah,Spans, at http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/span.html. Feb. 27, 1995.
V.Shah,Polygon scan conversion—Linear Approach, at http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/polyscan1 . . . Feb. 27, 1995.
V.Shah,The Edge Table Data Structure, at http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/et.html. Feb. 27, 1995.
V. Shah,The Active Edge Table Data Structure, at http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/aet.html. Feb. 27, 1995.
V. Shah,Polygon scan conversion—Background, at http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/background . . . Feb. 27, 1995.
V. Shah,Polygon scan conversion—tutorialat http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/polyscan2 . . . Feb. 27, 1995.
V. Shah,Polygon scan conversion—Definitionsat http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/definitions . . . Feb. 27, 1995.
V. Shah,Polygon scan conversion : Examplesat http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/example.html. Feb. 27, 1995.
V.Shah,Polygon scan conversion: Explanationat http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/explanation . . . Feb. 13, 1995.
V. Shah,Convex and Concave polygonsat http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/polytypes . . . Feb. 27, 1995.
V. Shah,Polygon scan conversion : Pseudo-Codeat http://www.cc.gatech.edu/gvu/multimedia
sfmmedia/graphics/elabor/polyscan/pcode.html. Feb. 21, 1995.
William Shoaff,Rasterization, at http://www.cs.fit.edu/˜wds/classes/graphics/Rasterize/rasterize/rasterize.html. Apr. 4, 2002.
Scan Conversionat http://www.ece.eps.hw.ac.uk/˜dml/cgonline/hyper00/polypipe/render/scanconv.html. Oct. 15, 2004.
A practical Scan Conversion algorithm, at http://www.ece.eps.hw.ac.uk/˜dml/cgonline/hyper00/polypipe/render/scanconv1.html. Oct. 15, 2004.
Hidden Surface Removal, at http://www.ece.eps.hw.ac.uk/˜dml/cgonline/hyper00/polypipe/render/hsremove.html. Oct. 15, 2004.
The Screen Transformationat http://www.ece.eps.hw.ac.uk/˜dml/cgonline/hyper00/polypipe/projection/screentrans.html. Oct. 15, 2004.
The Perspective Transformationat http://www.ece.eps.hw.ac.uk/˜dml/cgonline/hyper00/polypipe/projection/persptrans.html. Oct. 15, 2004.
Scan Conversion, Overview of Rendering Scan Conversion, Drawing lines, Drawing Polygons, Angel 7.8-7.10, Carnegie Mellon presentation, pp. 1-13, Nov. 1, 2001.
James D. Foley et al. “Computer Graphics, Principles and Practice,” 2ndEdition, 1990, pp. 680-686.
Chauhan Ulka
Darby & Darby P.C.
Murdoch Crystal
Valve Corporation
Wiegand Jamie L.
LandOfFree
Method for accelerated determination of occlusion between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for accelerated determination of occlusion between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for accelerated determination of occlusion between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3998316