Source: http://www.google.com/patents/US8115763?dq=7,441,219
Timestamp: 2017-04-30 18:15:26
Document Index: 418578663

Matched Legal Cases: ['§119', 'Application No. 10', '§365', 'Application No. 03790730', 'Application No. 2006', 'Application No. 2006']

Patent US8115763 - Device for the photorealistic representation of dynamic, complex, three ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsThe invention relates to a device for the photorealistic representation of dynamic, complex, three-dimensional scenes by means of ray-tracing. Said device comprises at least one programmable ray-tracing processor in which are implemented: special traversing instructions and/or vector arithmetic instructions...http://www.google.com/patents/US8115763?utm_source=gb-gplus-sharePatent US8115763 - Device for the photorealistic representation of dynamic, complex, three-dimensional scenes by means of ray tracingAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS8115763 B2Publication typeGrantApplication numberUS 10/589,794PCT numberPCT/DE2005/000266Publication dateFeb 14, 2012Filing dateFeb 16, 2005Priority dateFeb 17, 2004Fee statusPaidAlso published asDE102004007835A1, EP1716543A1, US20070182732, WO2005078665A1Publication number10589794, 589794, PCT/2005/266, PCT/DE/2005/000266, PCT/DE/2005/00266, PCT/DE/5/000266, PCT/DE/5/00266, PCT/DE2005/000266, PCT/DE2005/00266, PCT/DE2005000266, PCT/DE200500266, PCT/DE5/000266, PCT/DE5/00266, PCT/DE5000266, PCT/DE500266, US 8115763 B2, US 8115763B2, US-B2-8115763, US8115763 B2, US8115763B2InventorsSven Woop, Philip Slussallek, Jörg SchmittlerOriginal AssigneeJordaan Consulting Ltd. V, LlcExport CitationBiBTeX, EndNote, RefManPatent Citations (32), Non-Patent Citations (37), Referenced by (18), Classifications (13), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetDevice for the photorealistic representation of dynamic, complex, three-dimensional scenes by means of ray tracing
US 8115763 B2Abstract
The invention relates to a device for the photorealistic representation of dynamic, complex, three-dimensional scenes by means of ray-tracing. Said device comprises at least one programmable ray-tracing processor in which are implemented:
1. A method for rendering three-dimensional scenes, the method comprising:
Applicants claim priority under 35 U.S.C. §119 of German Application No. 10 2004 007 835.1 filed Feb. 17, 2004. Applicants also claim priority under 35 U.S.C. §365 of PCT/DE2005/000266 filed Feb. 16, 2005. The international application under PCT article 21 (2) was not published in English.
The prior art relating to the representation of three-dimensional scenes currently falls under two main categories, namely rasterization and ray-tracing (see Computer Graphics/Addison-Wesley ISBN 0201848406).
Aside from the described shadow computation, this method also allows computation of specular reflections and of light refractions by means of computing reflection rays and refracted secondary rays. An added advantage is that scenes of almost arbitrary size can be handled and represented. The reason for this is that an acceleration structure is used. This is a special process with an appropriate data structure that makes it possible to “shoot” and traverse the virtual ray rapidly through the scene. A number of objects that are potential hit candidates are selected on the way, as a result of which the point of impact is quickly found. Theoretical studies have shown that on average, the complexity of the ray tracing process grows logarithmically with the size of the scene. That means that squaring the number of scene objects only doubles the computational overhead.
In contrast to the rasterization process, there is currently no pure hardware solution that implements the ray-tracing process, but only software-based systems that need a relatively large amount of computational power and computing time. To illustrate the extent of time required for the computations it may be remarked that with PC hardware conforming to the current prior art, a computation time of several seconds to several hours—the exact time will depend on the complexity of the image—is needed to create a single still image using this method. The computation of moving images requires a correspondingly large amount of time and/or the availability of special mainframes.
The paper “SaarCOR—A Hardware Architecture for Ray-Tracing” by the Department of Computer Graphics at the University of Saarland describes a hardware architecture for ray tracing, but it is again limited to static scenes.
The paper “A Simple and Practical Method for Interactive Ray-Tracing of Dynamic Scenes” by the Department of Computer Graphics at the University of Saarland describes a software approach to supporting dynamic scenes in a ray tracer. However, the software process described uses only one object level, i.e. it cannot handle multi-level nesting.
By contrast, the object of this invention is to propose a device with which ray tracing in dynamic, complex, three-dimensional scenes can be performed faster—preferably also in real time—in such manner that a photorealistic representation is obtained.
For the realization of arbitrary, disordered dynamics in a scene, the acceleration structure has to be computed anew for each image of the image sequence. This means that large scenes involve a huge computational overhead, since the entire geometry of the scene has to be “handled”. In such cases, the advantage of the logarithmic complexity is swallowed up by the size of the scene.
A solution—described in the paper “A Simple and Practical Method for Interactive Ray-Tracing”—to this problem is to subdivide the scene into objects and to allow the movement of these objects exclusively in their entirety. This necessitates two acceleration structures.
The uses of computer-animated, photorealistic, real-time, three-dimensional moving scenes and images range from the representation of three-dimensional CAD data and of medical and technical-analytical data, through film animation and use in flight simulators and driving simulators, to so-called “home” applications in computer games with complex real-time graphics.
The same processes may additionally be used—without further modifications to the functional configuration—for non-photorealistic image generation (e.g. line drawings or the representation of comic stills). It is likewise possible, again without the need for any technical modifications, to perform computations that are not generally associated directly with image computation. Examples here include collision detection for geometric objects and the discrete solving of numerical problems. None of the applications described are restricted to the interactive sector and all can also be used offline—for example for cinema-film computations or very complex physical simulations—without any modifications to the process or the device.
These objects must now be tested for a possible intersection. If there is no valid intersection, traversing must be continued. The list unit sends the potential hit objects that have not yet been processed to the matrix-loading unit one after the other. The matrix-loading unit loads the affine transformation belonging to the object. This affine transformation can be represented by a 4×3 matrix. The matrices may be object-space transformation matrices or matrices that transform into the normalized space of a primitive object. After the matrix-loading unit has stored the matrix in the transformation unit, the ray-casting unit sends the rays through the transformation unit.
Photon mapping is a standard technique in which virtual photons are shot from the light sources into the scene and are collected on the surfaces of the scene. The light distribution of the scene can thus be simulated. This applies above all to caustics. If photons are shot, an acceleration structure—a kD tree, for example—is built up over the photons. Now, an image of this computed photon light distribution can be effected by visualizing the scene with standard ray-tracing techniques and incorporating the incident light intensity at every point of impact into the color computation in such manner that the energies of all the photons striking in the vicinity of this point are added up. This entails searching for all the neighboring photons in the photon acceleration structure. The traversal unit can help with this task by traversing a volume instead of traversing along a ray. All the neighboring photons can be processed in this way, for example by adding up their energies.
A second exemplary embodiment of the invention is based on the configuration and use of freely programmable ray-tracing CPUs or ray-tracing processors, which are program-controlled to carry out the special ray-tracing functions and processes described in the invention. Thanks to appropriate logic parallelism and function parallelism, only a few—preferably one or two—CPU tact cycles are needed here to process the individual functions.
Ray-tracing processors are fully programmable computing units which are engineered to carry out vector arithmetic instructions and special ray-tracing instructions, such as “traversing” and “establishment of acceleration structures”. The configuration may incorporate additional functional units or else make use of already available functional units plus a few additional logic devices if required. For example, traversing may be effected by means of special functional units or by expanding the available arithmetic functional units by a few logical functional units.
FIG. 1 illustrates how a tree can be built up from several object levels. To start with, a leaf is modeled as a level 1 object 101. This leaf 101 is now instantiated repeatedly and applied to a branch 102, thus creating another object, this time a level 2 object. These small branches 102 can now be instantiated repeatedly again to form a tree 103 as a level 3 object.
501: Load instruction 502: Instruction memory 503: RISC core 504: Cache 505: Traversal core 506: Node cache 507: Vector arithmetic core 508: Vector cache FIG. 6 illustrates an example of simplified geometry in the octree nodes. The reference numeral 601 denotes the ray cone, and the reference numeral 602 an instance of “simplified geometry”.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5305430Dec 26, 1990Apr 19, 1994Xerox CorporationObject-local sampling histories for efficient path tracingUS5442733 *Mar 20, 1992Aug 15, 1995The Research Foundation Of State University Of New YorkMethod and apparatus for generating realistic images using a discrete representationUS5594844Jan 25, 1994Jan 14, 1997Hitachi, Ltd.Three dimensional view using ray tracing through voxels subdivided numerically using object based parametersUS5933146 *Nov 30, 1995Aug 3, 1999Advanced Rendering Technology LimitedMethod of and apparatus for constructing an image of a notional scene by a process of ray tracingUS6088035Aug 12, 1997Jul 11, 2000Virtue, Ltd.Method for displaying a graphic modelUS6111582Jul 23, 1997Aug 29, 2000Jenkins; Barry L.System and method of image generation and encoding using primitive reprojectionUS6302541Nov 6, 1998Oct 16, 2001Christoph GrossmannMethod and device for autostereoscopyUS6556200Sep 1, 1999Apr 29, 2003Mitsubishi Electric Research Laboratories, Inc.Temporal and spatial coherent ray tracing for rendering scenes with sampled and geometry dataUS6587110Feb 3, 2000Jul 1, 2003Kabushiki Kaisha ToshibaImage processing unit, image processing system using the same, and image processing methodUS6597359 *May 17, 2000Jul 22, 2003Raychip, Inc.Hierarchical space subdivision hardware for ray tracingUS6664961Dec 20, 2000Dec 16, 2003Rutgers, The State University Of NjResample and composite engine for real-time volume renderingUS6868420Jul 31, 2002Mar 15, 2005Mitsubishi Electric Research Laboratories, Inc.Method for traversing quadtrees, octrees, and N-dimensional bi-treesUS7012604Sep 12, 2002Mar 14, 2006Advanced Micro Devices, Inc.System architecture for high speed ray tracingUS7164420 *Jul 22, 2004Jan 16, 2007Autodesk, Inc.Ray tracing hierarchyUS7483024 *Dec 31, 2003Jan 27, 2009Autodesk, Inc.Accelerated ray-object intersectionUS7495664 *Apr 19, 2007Feb 24, 2009Mental Images GmbhInstant ray tracingUS20020140703Aug 24, 2001Oct 3, 2002Baker Nicholas R.Applying multiple texture maps to objects in three-dimensional imaging processesUS20030001842 *Jun 27, 2001Jan 2, 2003Munshi Aaftab A.Object visibility control for ray tracingUS20030160788 *Feb 28, 2002Aug 28, 2003Buehler David B.Pixel pruning and rendering apparatus and methodUS20030165254Feb 15, 2002Sep 4, 2003International Business Machines CorporationAdapting point geometry for storing address densityUS20030227457 *Jun 6, 2002Dec 11, 2003Pharr Matthew MiltonSystem and method of using multiple representations per object in computer graphicsUS20040233222 *Dec 1, 2003Nov 25, 2004Lee Jerome ChanMethod and system for scaling control in 3D displays ("zoom slider")US20050041024 *Aug 20, 2003Feb 24, 2005Green Robin J.Method and apparatus for real-time global illumination incorporating stream processor based hybrid ray tracingUS20060066607 *Aug 20, 2003Mar 30, 2006Jorg SchmittlerMethod and device for creating a two-dimensional representation of a three-dimensional structureUS20080043018Apr 19, 2007Feb 21, 2008Alexander KellerInstant ray tracingDE4331715A1Sep 17, 1993Mar 23, 1995Zeiss Carl FaShutter spectacles (shutter goggles)DE4417664C1May 20, 1994Dec 15, 1994Zeiss Carl FaDevice having at least two display screen monitors which are set up adjacently and have different display modes, and method for operating the sameDE19737449A1Aug 22, 1997Feb 25, 1999Hertz Inst HeinrichViewer-tracking autostereoscopic flat screen displayDE19753040A1Nov 19, 1997May 27, 1999Fraunhofer Ges ForschungMethod of generating 3D images for visual 3D perception based on virtual or real images for 3D vision in 3D video, 3D TV or 3D multimediaDE19827590A1Jun 20, 1998Dec 23, 1999Christoph GrosmannAuto stereoscopic representation of images on display screenJP2000293709A Title not availableJP2001092985A Title not available* Cited by examinerNon-Patent CitationsReference1Appel, Arthur, "Some Techniques for shading machine rendering of solids," Proceedings of "AFIPS 1968 Spring Joint Computer Conference," Apr. 30-May 2, vol. 32, pp. 37-45, Atlantic City, New Jersey.2Arnaldi et al: A new space subdivision method for ray tracing CSG modelled scenes; Aug. 1987; Springer Berlin: The Visual Computer, vol. 3, No. 2; pp. 98-108.3Aruga et al., "A Space Sampling Method for Improving Realism of 3-Dimensional Computer Graphics," PFU Technical Review, PFU, Aug. 1, 1995, vol. 6, No. 2, pp. 83-92.4Briere et al., "Hierarchical View-dependent Structures for Interactive Scene Manipulation," SIGGRAPH 96, New Orleans, Louisiana, Aug. 1996.5Clark J H: "Hierarchical Geometric Models for Visible Surface Algorithms" Communications of the Association for Computing Machinery, Association for Computing Machinery. New York, US, vol. 19, No. 10, Oct. 1, 1976, pp. 547-554, XP00646877 ISSN: 0001-0782 p. 551.6Department of Computer Graphics at the University of Saarland, "A Simple and Practical Method for Interactive Ray-Tracing of Dynamic Scenes" (2002).7EP Office Action issued Mar. 17, 2010 from EP Application No. 03790730.0.8Fender et al., "A High-Speed Ray Tracing Engine Built on a Field-Programmable System," Deutsches Patent Und Markenamt, IEEE Xplore, pp. 188-195 (Dec. 15-17, 2003).9Final Office Action issued Feb. 23, 2011 from Japanese Application No. 2006-552460.10Foley J D et al: "Computer Graphics Principles and Practice" Computer Graphics. Principles and Practice, Reading, Addison Wesley, US 1996, pp. 649-720, XP002082444 p. 701-p. 711.11Foley J D et al: "Computer Graphics Principles and Practice: 16.12 Recursive Ray Tracing" Computer Graphics, Principles and Practice, Reading, Addison Wesley, US 1006, pp. 7760792, XP002328211 p. 786-p. 787.12Glassner (Editor), "An Introduction to Ray Tracing," Academic Press, ISBN 0-12-286160-4 (Feb. 11, 1989).13Goldsmith et al., "Automatic Creation of Object Hierarchies for Ray Tracing," IEEE CG&A, Deutsches Patent Und Markenamt, pp. 14-20, California Institute of Technology Synchrotron Laboratory 206-49, Pasadena, California, 1987.14Hirata et al, "An Elementary Processor Architecture with Parallel Instruction Issuing from Multiple Threads," Transactions of Information Processing Society of Japan, Japan, Information Processing Society of Japan, Apr. 15, 1993, vol. 34, No. 4, pp. 595-605.15Hook, David G., "Algorithms For Accelerating Ray Tracing," May 29, 1995, http://72.14.209.104/search?q=cache:asx-13iRcaoJ:bund.com.au/~dgh/HookMAppScThesis.ps.gz+algorithm+for+accelerating+ray+tracing&hl=en&ct=clnk&cd=5&gl=us.16Hook, David G., "Algorithms For Accelerating Ray Tracing," May 29, 1995, http://72.14.209.104/search?q=cache:asx—13iRcaoJ:bund.com.au/˜dgh/HookMAppScThesis.ps.gz+algorithm+for+accelerating+ray+tracing&hl=en&ct=clnk&cd=5&gl=us.17ISR mailed Jun. 21, 2005 from WO2005/078665 A1.18ISR mailed Mar. 2, 2004 from WO2004/021274 A2.19Japanese Decision to Grant issued May 24, 2011 from Japanese Application No. 2006-552460, mailed May 26, 2011.20Kanazawa et al., "A CG Model of Illuminated Volume By Spotlight," IEICE Technical Report, Japan, IEICE, Mar. 12, 1998, vol. 97, No. 597, pp. 7-13.21Kurachi, "Graphics Hardware Performing A Ray Tracing With a Hardware," CG World, Japan, Works Corporation, Dec. 1, 2002, vol. 52, p. 116-119.22Lext et al., "Towards Rapid Reconstruction for Animated Ray Tracing," Department of Computer Engineering, Chalmers University of Technology, Sweden, The Eurographics Association 2001, Short Presentations, pp. 311-318.23Macdonald et al.; Heuristics for ray tracing using space subdivision; Jun. 1990; Springer-Verlag New York; The Visual Computer, Volumbe 6, No. 3; pp. 153-166.24Notice of Allowance mailed Jun. 29, 2007 from U.S. Appl. No. 10/526,055.25Office Action mailed Nov. 22, 2006 from U.S. Appl. No. 10/526,055.26Office Action mailed Sep. 7, 2011 from U.S. Appl. No. 12/608,864.27Onoue et al., "A Rendering Method on Desert Scenes of Dunes with Wind-Ripples," Transaction of IEICE, Japan IEICE, Feb. 1, 2003, vol. J86-D-II, No. 2, pp. 282-289.28Reinhard et al., "Dynamic Acceleration Structures for Interactive Ray Tracing," University of Utah, Rendering Techniques 2000, Proceedings of the Eurographics Workshop, Brno, Czech Republic, Jun. 26-28, 2000, pp. 299-306, XP002269803.29Rubin S. Witted T: "A 3-Dimensional Representation for Fast Rendering of Complex Scenes" Siggraph 1980 Conference Proceedings. Seventh Annual Conference on Computer Graphics and Interactive Techniques Jul. 14-18, 1080 Seattle WA, USA, vol. 14, No. 3, 1980, pp. 110-116, XP002328212, Computer Graphics USA ISSN: 0097-8930, p. 110-p. 112.30Schmittler J. et al: "A virtual memory architecture for real-time ray tracing hardware," Computers and Graphics, Pergamon Press Ltd., Oxford, GB, vol. 27, No. 5, Oct. 2003, pp. 693-699, XP004465051 ISSN: 0097-8493, p. 693-p. 695.31Schmittler J., Wald I, Slusallek P: "SaarCOR-A Hardware for Ray Tracing" Proceedings of Eurographics Graphics Hardware 2002, Sep. 1, 2002, pp. 27-36, XP002328209 Saarbrücken, Germany.32Schmittler J., Wald I, Slusallek P: "SaarCOR—A Hardware for Ray Tracing" Proceedings of Eurographics Graphics Hardware 2002, Sep. 1, 2002, pp. 27-36, XP002328209 Saarbrücken, Germany.33Wald et al., "A Simple and Practical Method for Interactive Ray Tracing of Dynamic Scenes," Saarland University, Technical Report Apr. 2002, submitted for publication, http://graphics.cs.uni-sb.de/Publications/TR/2002/Dyn/DynamicRayTracing.pdf.34Wald et al., "Interactive Rendering with Coherent Ray Tracing," Computer Graphics Group, Saarland University, vol. 20 (2001), No. 3, The Eurographics Association and Blackwell Publishers 2001 (Guest Editors), Oxford, MA, USA.35Wald et al., "State of the Art In Interactive Ray Tracing," Qluelle:www.openrt.de/Publications.36Wald I et al: "Distributed interactive ray tracing of dynamic scenes" Parallel and Large-Data Visualization and Graphics, 2003. PVG 2003. IEEE Symposium on Oct. 20-21, 2003, Piscataway, NJ, USA, IEEE, Oct. 20, 2003, pp. 77-85, XP010670788 ISBN: 0-7803-8122-X, p. 78-p. 80.37Watt, A., "3D Computer Graphics," 2000, Addison-Wesley, Harlow, England XP002269804, Kapitel 12, pp. 358 and 365.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8281281 *Sep 14, 2006Oct 2, 2012PixarSetting level of detail transition pointsUS8441482 *Sep 21, 2009May 14, 2013Caustic Graphics, Inc.Systems and methods for self-intersection avoidance in ray tracingUS8711145 *Feb 7, 2008Apr 29, 2014The University Of Utah Research FoundationRepresenting polarized light in computer modelsUS8817026Feb 13, 2014Aug 26, 2014Raycast Systems, Inc.Computer hardware architecture and data structures for a ray traversal unit to support incoherent ray traversalUS8842117Feb 13, 2014Sep 23, 2014Raycast Systems, Inc.Computer hardware architecture and data structures for lookahead flags to support incoherent ray traversalUS8928675Feb 13, 2014Jan 6, 2015Raycast Systems, Inc.Computer hardware architecture and data structures for encoders to support incoherent ray traversalUS8947447Feb 13, 2014Feb 3, 2015Raycast Systems, Inc.Computer hardware architecture and data structures for ray binning to support incoherent ray traversalUS8952961 *Jun 29, 2010Feb 10, 2015Imagination Technologies, LimitedSystems and methods for photon map queryingUS8952963Feb 13, 2014Feb 10, 2015Raycast Systems, Inc.Computer hardware architecture and data structures for a grid traversal unit to support incoherent ray traversalUS9035946Feb 13, 2014May 19, 2015Raycast Systems, Inc.Computer hardware architecture and data structures for triangle binning to support incoherent ray traversalUS9058691Jun 24, 2014Jun 16, 2015Raycast Systems, Inc.Computer hardware architecture and data structures for a ray traversal unit to support incoherent ray traversalUS9087394Feb 13, 2014Jul 21, 2015Raycast Systems, Inc.Computer hardware architecture and data structures for packet binning to support incoherent ray traversalUS9330501 *Aug 20, 2012May 3, 2016Autodesk, Inc.Systems and methods for augmenting panoramic image data with performance related data for a buildingUS9424685Jul 30, 2013Aug 23, 2016Imagination Technologies LimitedUnified rasterization and ray tracing rendering environmentsUS20100332523 *Jun 29, 2010Dec 30, 2010Caustic Graphics, Inc.Systems and methods for photon map queryingUS20110043516 *Feb 7, 2008Feb 24, 2011University Of Utah Research FoundationRepresenting Polarized Light in Computer ModelsUS20110069067 *Sep 21, 2009Mar 24, 2011Caustic Graphics, Inc.Systems and methods for self-intersection avoidance in ray tracingUS20140049537 *Aug 20, 2012Feb 20, 2014Keshaba Chandra SahooSystems and methods for augmenting panoramic image data with performance related data for a building* Cited by examinerClassifications U.S. Classification345/420, 345/619, 345/426International ClassificationG06T17/00, G06T15/06, G06T15/50, G06T15/00Cooperative ClassificationG06T15/005, G06T15/50, G06T15/06European ClassificationG06T15/06, G06T15/00A, G06T15/50Legal EventsDateCodeEventDescriptionSep 18, 2006ASAssignmentOwner name: UNIVERSITAT DES SAARLANDES, GERMANYFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:WOOP, SVEN;SLUSSALLEK, PHILIP;SCHMITTLER, JORG;REEL/FRAME:018311/0344;SIGNING DATES FROM 20060813 TO 20060821Owner name: UNIVERSITAT DES SAARLANDES, GERMANYFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:WOOP, SVEN;SLUSSALLEK, PHILIP;SCHMITTLER, JORG;SIGNING DATES FROM 20060813 TO 20060821;REEL/FRAME:018311/0344Oct 6, 2008ASAssignmentOwner name: JORDAAN CONSULTING LTD. V, LLC, DELAWAREFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:UNIVERSITAT DES SAARLANDES;REEL/FRAME:021637/0126Effective date: 20080626Mar 19, 2013CCCertificate of correctionJul 28, 2015FPAYFee paymentYear of fee payment: 4Dec 22, 2015ASAssignmentOwner name: OL SECURITY LIMITED LIABILITY COMPANY, DELAWAREFree format text: MERGER;ASSIGNOR:JORDAAN CONSULTING LTD. V, LLC;REEL/FRAME:037346/0708Effective date: 20150826RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services