Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2006-11-21
2010-10-05
Chauhan, Ulka (Department: 2628)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000, C345S421000, C345S426000, C345S428000, C345S544000, C345S555000
Reexamination Certificate
active
07808500
ABSTRACT:
Embodiments of the invention provide methods and apparatus to improve the efficiency of a ray tracing image processing system. According to one embodiment of the invention, when building a spatial index the position of a splitting plane used to create a bounding volume may be jittered or moved along an axis to determine if a more efficient location for the splitting plane exists. After jittering the splitting plane a number of primitives intersected by the splitting plane may be calculated. The number of primitives intersected by the splitting plane for each location may be compared, and the location with the fewest intersected primitives may be chosen for the final position of the splitting plane. By choosing the location with the fewest intersected primitives the number of ray-primitive intersection tests necessary when performing ray tracing may be reduced. Consequently, the efficiency of the image processing system may be improved.
REFERENCES:
patent: 5666474 (1997-09-01), Otto
patent: 6580426 (2003-06-01), Small et al.
patent: 7002571 (2006-02-01), Lake et al.
patent: 7495664 (2009-02-01), Keller et al.
patent: 2004/0095343 (2004-05-01), Forest et al.
patent: 2006/0098009 (2006-05-01), Zuniga
patent: 2008/0024489 (2008-01-01), Shearer
patent: 2008/0074416 (2008-03-01), Brown et al.
patent: 2008/0074417 (2008-03-01), Mejdrich et al.
patent: 2008/0088619 (2008-04-01), Shearer et al.
patent: 2008/0088622 (2008-04-01), Shearer
patent: 2008/0170071 (2008-07-01), Shearer
patent: 2009/0189898 (2009-07-01), Dammertz et al.
Samanta et al., “Load balancing for multiprojector rendering systems”, Eurographics/SIGGRAPH workshop on Graphics hardware, Los Angeles, CA, Aug. 1999, ACM Press, pp. 107-116.
Harter, et al., “Soft Shadow Volumes for Ray Tracing with Frustum Shooting”, Masters Thesis, Chalmers University of Technology, 9 pages, Feb. 2006, http://www.cse.chalmers.se/˜uffe/.
Elhassan, Ikrima. “An Analysis Of GPU-based Interactive Raytracing”. The University of Texas at Austin, Department of Computer Sciences. Report# HN-06-12 (honors). May 2006. 8 pages.
Foley, T. and Sugerman, J., “KD-tree acceleration structures for a GPU raytracer”, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware, Los Angeles, California, Jul. 30-31, 2005, HWWS '05, ACM, New York, NY, pp. 15-22.
Glazer, Brendon C., “Interactive Ray Tracing of VRML Scenes in Java”, Master of Engineering Thesis, Massachusetts Institute of Technology, Feb. 1999, 70 pages.
V. Havran et al., “On fast construction of spatial hierarchies for ray tracing”, Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing, Sep. 2006.
Mayer, A. J., “Dynamic Occlusion Culling”, Courses, Seminar, WS2006, Institute of Computer Graphics and Algorithms, Vienna University of Technology, 2006, http://www.cg.tuwien.ac.at/courses/Seminar/WS2006/dynamicvisibility.pdf.
Shade et al., “Hierarchical image caching for accelerated walkthroughs of complex environments”, Proceedings of the 23rd Annual Conference on Computer Graphics and interactive Techniques SIGGRAPH '96. ACM, New York, NY, Jul. 1996, pp. 75-82.
Shagam J., “Dynamic spatial partitioning for real-time visibility determination”, Informatique, New Mexico State University, Department of computer science, Technical Report NMSU-CS-2003-004, Apr. 7, 2003, pp. 1-9.
Stefan Popov, et al., “Experiences with Streaming Construction of SAH KDTrees”, Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing, pp. 89-94, Sep. 18-20, 2006.
Szirmay-Kalos, et al., “On the efficiency of ray-shooting acceleration schemes”, Proceedings of the 18th Spring Conference on Computer Graphics, Budmerice, Slovakia, Apr. 24-27, 2002, SCCG '02, ACM, New York, NY, pp. 97-106.
Wald et al., “Distributed Interactive Ray Tracing of Dynamic Scenes”, Proceedings of the 2003 IEEE Symposium on Parallel and Large-Data Visualization and Graphics, Oct. 20-21, 2003, Parallel and large-data visualization and graphics, IEEE Computer Society, Washington, DC, pp. 77-85.
Woop et al., “B-KD trees for hardware accelerated ray tracing of dynamic scenes”, Proceedings of the 21st ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware, Vienna, Austria, Sep. 3-4, 2006, GH '06, ACM, New York, NY, pp. 67-77.
Gummerus, S., “Conservative from Point Visibility”, Master's Thesis, University of Tampere, Dec. 2003, 77 pages, p. 22.
Lext, J., Assarsson, U., and Moeller, T. 2000. “BART: A Benchmark for Animated Ray Tracing”, Technical report, Department of Computer Engineering, Chalmers University of Technology, Goeteborg, Sweden, May 2000, pp. 22-31, Available at http://www.ce.chalmers.se/BART/.
Chauhan Ulka
International Business Machines - Corporation
Patterson & Sheridan LLP
Prendergast Roberta
LandOfFree
Method for improving spatial index efficiency by jittering... 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 improving spatial index efficiency by jittering..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for improving spatial index efficiency by jittering... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4208602