Applications of interval arithmetic for reduction of number of computations in ray tracing problems

Patent 7348975 Issued on March 25, 2008. Estimated Expiration Date:

December 28, 2024. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Method for traversing a binary space partition or octree and image processor for implementing the method
Patent #: 6429864
Issued on: 08/06/2002
Inventor: Schwarzer

Size conditioned visibility search system and method
Patent #: 6750859
Issued on: 06/15/2004
Inventor: Sowizral, et al.

Method for converting explicitly represented geometric surfaces into accurate level sets Patent #: 7098907
Issued on: 08/29/2006
Inventor: Houston, et al.

Inventors

Assignee

Intel Corporation

Application

No. 11024527 filed on 12/28/2004

US Classes:

345/421, Hidden line/surface determining345/419, Three-dimension345/418COMPUTER GRAPHICS PROCESSING

Examiners

Primary: Nguyen, Phu K.

Attorney, Agent or Firm

McCall; Molly A.

International Class

G06T 15/00

Abstract

Embodiments provide for ray tracing traversal that relies on selected geometrical properties of the application to reduce the number of operations required during each traversal step. The traversal algorithm does not depend on the number of rays in the group. As a result, multi-level traversal schemes may be implemented, starting with a large number of rays in a group and then reducing it as needed to maintain group coherency. Multi-level traversal schemes may be created by splitting large groups of rays while traversing acceleration structures.

Other References

Hanan Samet, et al., “Hierarchical Data Structures and Algorithms for Computer Graphics”, Part II: Applications, IEEE Computer Graphics and Applications, IEEE Service Center, NY USA (Jul. 1988), XP001098905, ISSN: 0272-1716 (pp. 59-75).
Hanan Samet, et al., “Hierarchical Data Structures and Algorithms for Computer Graphics”—Part 1: Fundamentals, IEEE Computer Graphics and Applications, IEEE Service Center, NY, USA, vol. 8, No. 3 (May 1988), XP000006955, ISSN: 0272-1716 (pp. 48-68).
Gerd Marmitt, et al., “Fast and Accurate Ray-Voxel Intersction Techniques for Iso-Surface Ray Tracing”, Vision, Modeling, and Visualization 2004 (VMV 2004), Stanford, USA, Nov. 16-18, 2004, XP002378437 (pp. 429-435).
J. F. Sanhuan-Estrada, et al., “Reliable Algorithms for Ray Intersection in Computer Graphics Based on Interval Arithmetic”, Computer Graphics and Image Processing (2003), XVI Brazilian Symposium on Oct. 12-15, 2003, Piscataway, NJ, USA, IEEE Oct. 12, 2003, XP010664266, ISBN: 0-7695-2032-4 (p. 1-8).
Adrian Bowyer, et al., “Interval Methods in Geometric Modeling”, Geometric Modeling and Processing 2000, Theory and Applications, Proceedings Hong Kong, China Apr. 10-12, 2000, Los Alamitos, CA, USA, IEEE Comput. Soc., US, Apr. 10, 2000 (XP 010377961, ISBN: 0-7695-0562-7 (pp. 321-327).
Wilhelm Barth, et al., “Ray Tracing General Parametric Surfaces Using Interval Arithmetic”, The Visual Computer International Journal of Computer Graphics, Springer International, Berlin, DE, vol. 10, No. 7 (1994), XP008030167, ISSN: 0178-2789 (pp. 363-371).
PCT International Search Report (dated May 18, 2006), International Application No. PCT/US2005/047701-13 International Filing Date Dec. 29, 2005, [File No P19888PCT], (13 pages).