Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2011-06-28
2011-06-28
Broome, Said (Department: 2628)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000, C345S421000
Reexamination Certificate
active
07969434
ABSTRACT:
For ray tracing scenes composed of primitives, systems and methods accelerate intersection testing by testing rays against elements of geometry acceleration data (GAD) arranged in a graph of nodes, where pairs of nodes are connected by edges, and each element bounds a varying granularity selection of the primitives. Upon detection of intersections between rays and elements, references to the rays are added to respective collections associated with the elements. Further processing of those rays is deferred until rays of a given collection are determined ready, and then rays from such a ready collection are tested for intersection with elements of GAD connected by edges to the element associated with the ready collection. When a primitive is bounded by no higher granularity GAD element, it is tested for intersection, and indications of intersection are output. Some examples encourage production of many secondary rays and collect such rays for parallelized testing, regardless of traversal order, camera ray association, or a time when each ray was spawned.
REFERENCES:
patent: 4625289 (1986-11-01), Rockwood
patent: 5313568 (1994-05-01), Wallace
patent: 5933146 (1999-08-01), Wrigley
patent: 5973699 (1999-10-01), Kent
patent: 6023279 (2000-02-01), Sowizral et al.
patent: 6028608 (2000-02-01), Jenkins
patent: 6111582 (2000-08-01), Jenkins
patent: 6344837 (2002-02-01), Gelsey
patent: 6489955 (2002-12-01), Newhall, Jr.
patent: 6556200 (2003-04-01), Pfister et al.
patent: 6559843 (2003-05-01), Hsu
patent: 6731304 (2004-05-01), Sowizral et al.
patent: 7009608 (2006-03-01), Pharr et al.
patent: 7012604 (2006-03-01), Christie et al.
patent: 7030879 (2006-04-01), Pharr
patent: 7098907 (2006-08-01), Houston et al.
patent: 7212207 (2007-05-01), Green
patent: 7250948 (2007-07-01), Hayes
patent: 7289118 (2007-10-01), Schmittler et al.
patent: 7348975 (2008-03-01), Reshetov et al.
patent: 7362332 (2008-04-01), Gritz
patent: 7483024 (2009-01-01), Maillot
patent: 7688320 (2010-03-01), Shearer
patent: 7782318 (2010-08-01), Shearer
patent: 7830379 (2010-11-01), Peterson et al.
patent: 2004/0249809 (2004-12-01), Ramani et al.
patent: 2005/0264568 (2005-12-01), Keller
patent: 2006/0098009 (2006-05-01), Zuniga
patent: 2006/0139350 (2006-06-01), Reshetov
patent: 2007/0035545 (2007-02-01), Hempel et al.
patent: 2007/0132754 (2007-06-01), Reshetov et al.
patent: 2008/0024489 (2008-01-01), Shearer
patent: 2008/0028154 (2008-01-01), Hoover
patent: 2008/0028403 (2008-01-01), Hoover
patent: 2008/0049017 (2008-02-01), Shearer
patent: 2008/0074420 (2008-03-01), Kuesel
patent: 2008/0074421 (2008-03-01), Hayes
patent: 2008/0088622 (2008-04-01), Shearer
patent: 2008/0122841 (2008-05-01), Brown
patent: 2008/0122845 (2008-05-01), Brown et al.
patent: 2008/0211804 (2008-09-01), Hempel et al.
patent: 2009/0102844 (2009-04-01), Deparis
patent: 2009/0189898 (2009-07-01), Dammertz et al.
patent: 2010/0194751 (2010-08-01), Wald et al.
patent: WO/96/17326 (1996-06-01), None
patent: WO 2008/037599 (2008-04-01), None
Susumu, H., Katahira, M., Nakada, T., Parallel processing of incremental ray tracing on a shared-memory multiprocessor, 1993, The Visual Computer, vol. 9, No. 7, pp. 371-380.
Carsten Benthin, PhD thesis: “Realtime Ray Tracing on Current CPU Architectures,” Saarland University, Saarbrücken, Germany, Jan. 2006. (Available at graphics.cs.uni-sb.de/˜benthin/phd.pdf, last visited on Jan. 7, 2008.).
J.G. Cleary, B.M. Wyvill, G.M. Birtwistle and R. Vatti, “Multiprocessor Ray Tracing,” Computer Graphics Forum, vol. 5, issue 1, pp. 3-12, 1986.
H. Friedrich, J. Günther, A. Dietrich, M. Scherbaum, H-P Seidel and P. Slusallek, “Exploring the Use of Ray Tracing for Future Games,” Proceedings of the 2006 ACM SIGGRAPH symposium on Videogames , Boston, MA, pp. 41-50, 2006.
N. Thrane and L.O. Simonsen, “A Comparison of Acceleration Structures for GPU Assisted Ray Tracing”, Masters thesis, University of Aarhus, Denmark, Aug. 1, 2005. (Available at http://www.larsole.com/files/GPU—BVHthesis.pdf, last visited on Jan. 7, 2008.).
I. Wald, P. Slusallek, C. Benthin and M. Wagner, “Interactive Rendering with Coherent Ray Tracing,” Computer Graphics Forum, Proceedings of Eurographics 2001, vol. 20, No. 3, 2001.
G. Humphreys and C.S. Ananian, “TigerSHARK: A Hardware Accelerated Ray-Tracing Engine,” Technical report, Princeton University, Princeton, NJ, May 14, 1996. (Available at citeseer.ist.psu.edu/article/humphreys96tigershark.html, last visited on Jan. 7, 2008.).
M. Pharr, C. Kolb, R. Gershbein and P. Hanrahan, “Rendering Complex Scenes with Memory-Coherent Ray Tracing,” in Computer Graphics, vol. 31, pp. 101-108, Aug. 1997, ACM Siggraph 1997 Conference Proceedings.
Geoff Wyvill, “Practical Ray Tracing,” Computer Graphics International 1995, Tutorial notes.
I. Wald and P. Slusallek, “State of the Art in Interactive Ray Tracing,” In State of the Art Reports, EUROGRAPHICS 2001, pp. 21-42, 2001.
I. Wald, P. Slusallek and C. Benthin, “Interactive Distributed Ray Tracing of Highly Complex Models,” Rendering Techniques 2001—Proceedings of the 12th EUROGRAPHICS Workshop on Rendering, pp. 274-285, London, England, Jun. 2001.
E. Månsson, J. Munkberg and T. Akenine-Moller, “Deep Coherent Ray Tracing,” RT 07—Symposium on Interactive Ray Tracing 2007, Sep. 10-12, 2007, pp. 79-85. (Available at http://graphics.cs.lth.se/research/papers/2007/deepcoh/deepcoherent.pdf, last visited Jan. 7, 2008.).
W.R. Mark and D. Fussell, “Real-Time Rendering Systems in 2010,” The University of Texas at Austin, Department of Computer Sciences, Technical Report # TR-05-18, May 2, 2005. (Available at http://www-csl.csres.utexas.edu/users/billmark/papers/rendering2010-TR/TR05-18-Rendering2010.pdf, last visited Jan. 7, 2008.).
P.A. Navrátil, D.S. Fussell and C. Lin, “Dynamic Ray Scheduling for Improved System Performance,” The University of Texas at Austin, Department of Computer Sciences, Technology Report #TR-07-19, Apr. 12, 2007. (Available at http://www.cs.utexas.edu/˜pnav/papers/utcs-tr-07-19/utcs-tr-07-19.pdf, last visited Jan. 7, 2008.).
M.L. Anido, N. Tabrizi, H. Du, M. Sanchez-Elez M and N. Bagherzadeh, “Interactive Ray Tracing Using a SIMD Reconfigurable Architecture,” Proceedings of the 14th Symposium on Computer Architecture and High Performance Computing, 2002, pp. 20-28.
A.J. van der Ploeg, “Interactive Ray Tracing, the replacement of rasterization?” B.Sc. thesis, VU University Amsterdam, The Netherlands, Dec. 2006. (Available at http://www.cs.vu.nl/˜kielmann/theses/avdploeg.pdf, last visited on Mar. 31, 2008.).
H. Du, M. Sanchez-Elez, N. Tabrizi, N. Bagherzadeh, M.L. Anido and M. Fernandez, “Interactive Ray Tracing on Reconfigurable SIMD MorphoSys,” Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, 2003, Asia and South Pacific Jan. 21-24, 2003, pp. 471-476.
M. Sanchez-Elez, H. Du, N. Tabrizi, Y. Long, N. Bagherzadeh and M. Fernandez, “Algorithm Optimizations and Mapping Scheme for Interactive Ray Tracing on a Reconfigurable Architecture,” Computers & Graphics 27(5), 2003, pp. 701-713.
Jeffrey A. Mahovsky, “Ray-Tracing with Reduced-Precision Bounding Volume Hierarchies,” PhD thesis, University of Calgary, Alberta, Canada, 2005. (Available at http://pages.cpsc.ucalgary.ca/˜brosz/theses/PhD%20Thesis%20-%202005%20-%20Jeffrey%20Mahovsky%20-%20Ray%20Tracing%20with%20Reduced-Precision%20Bounding%20Volume%20Hierarchies.pdf, last visited on Mar. 31, 2008).
J. Fender and J. Rose, “A High-Speed Ray Tracing Engine Built on a Field-Programmable System,” Proceedings of the 2003 IEEE International Conference on Field-Programmable Technology (FPT), Dec. 15-17, 2003, pp. 188-195.
Wilfrid Lefer “An Efficient Parallel Ray Tracing Scheme for Distributed Memory Parallel Computers,” Oct. 25, 1993, P
McCombe James Alexander
Peterson Luke Tilman
Salsbury Ryan R.
Broome Said
Caustic Graphics, Inc.
Garrabrants Michael S.
Novak Druce & Quigg LLP
LandOfFree
Method, apparatus, and computer readable medium for... 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, apparatus, and computer readable medium for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus, and computer readable medium for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2701166