49 results about "Bounding volume hierarchy" patented technology

Different rendering techniques are selected for portions of a scene based on statistical estimates of the portions' rendering costs. A scene is partitioned into a bounding volume hierarchy. Each bounding volume includes a statistical model of the spatial distribution of geometric primitives within the bounding volume. An image to be rendered is partitioned into screen regions and each screen region is associated with one or more bounding volumes and their statistical models. The associated statistical models of a screen region are evaluated to estimate the rendering cost, such as the probable number of geometric primitives per pixel, for the screen region. Based on the rendering cost, the screen region is assigned to a dense geometry renderer, such as a ray tracing renderer, or a sparse geometry renderer, such as a rasterization renderer. Rendered screen regions are combined to form a rendered image.

Methods, systems, devices, and computer program code (software) products enable acceleration of ray tracing by using acceleration data structures with high arity to enable processing of nodes using streaming SIMD (Single Instruction, Multiple Data) instructions with reduced memory requirements.

The invention relates to a balanced binary tree-based method for detecting collisions in a large-scale virtual environment. According to the characteristics of large object quantity and complex object types in a large-scale visual environment, the method adopts an expanded balanced binary tree to improve a bounding volume hierarchy tree, accelerates the detection of object collisions and reduces time complexity, caused by environmental changes, of tree reconstruction for overcoming the drawbacks of the conventional bounding volume hierarchy method in the real-time detection of collisions in a dynamic environment. The method adopts different bounding volumes according to hierarchy, combines the simplicity and compactibility of the bounding volumes, and improves a collision method as well as the accuracy of collision detection. Concrete processing flow is described in drawings in the abstract.

Provided are an apparatus and method for detecting ray-triangle collision for ray-tracing. The apparatus includes a ray bundle memory for storing ray bundle, a geometry data memory for storing geometry triangle data, a hierarchy structure memory for storing space subdivision and bounding volume hierarchy structure information, a virtual pager for receiving the geometry triangle data, the space subdivision and bounding volume hierarchy structure information, and the bounding hierarchical structure information by rearranging geometry triangle data by final end nodes, a virtual paged memory for receiving the rearranged data, forming page memories, and storing triangle data by pages, a virtual page cache for processing the page data in a pipe line manner, and previously storing a page memory for collision detection, a ray-triangle collision detection pipe for detecting a ray-triangle collision based on the page memory and the ray bundle, and an output memory for storing the ray-triangle collision detection result.

The invention discloses a self collision detection method based on a triangle mesh deformation body, comprising the steps of (1), constructing a data structure based on a hierarchical hounding volume (BVH); constructing an xBVH (expanded bounding volume hierarchy); constructing an SCTT (self-collision test tree)); optimizing star-shaped outline; (2), pre-processing self-collision detection based on the star-shaped outline; (3), performing self-collision test based on the star-shaped outline in real time. The method can detect the self-collision phenomenon during the deformation of the triangle mesh deformation body effectively in real time, accurately locates collision generation point and updates the collision information in real time.

Different rendering techniques are selected for portions of a scene based on statistical estimates of the portions' rendering costs. A scene is partitioned into a bounding volume hierarchy. Each bounding volume includes a statistical model of the spatial distribution of geometric primitives within the bounding volume. An image to be rendered is partitioned into screen regions and each screen region is associated with one or more bounding volumes and their statistical models. The associated statistical models of a screen region are evaluated to estimate the rendering cost, such as the probable number of geometric primitives per pixel, for the screen region. Based on the rendering cost, the screen region is assigned to a dense geometry renderer, such as a ray tracing renderer, or a sparse geometry renderer, such as a rasterization renderer. Rendered screen regions are combined to form a rendered image.

Apparatus and method for compressing an acceleration data structure such as a bounding volume hierarchy (BVH). For example, one embodiment of a graphics processing apparatus comprises: one or more cores to execute graphics instructions including instructions to perform ray tracing operations; and compression circuitry to compress lowest level nodes of a hierarchical acceleration data structure comprising a plurality of hierarchically arranged nodes, each of the lowest level nodes comprising pointers to leaf data; the compression circuitry to quantize the lowest level nodes to generate quantized lowest level nodes and to store each quantized lowest level node and associated leaf data without the pointers to the leaf data.

Disclosed herein is a parallel collision detection method using load balancing in order to detect collision between two objects of a polygon soup. The parallel collision detection method is processed in parallel using a plurality of threads. The parallel collision detection method includes traversing a Bounding Volume Traversal Tree (BVTT) using Bounding Volume Hierarchies (BVHs) related to the polygon soup in a depth first search manner or a width first search manner; recursively traversing the children node of an internal node (a parent node) when a currently traversed node is the internal node and two Boundary Volumes (BVs) in the corresponding node overlap, and stopping to traverse the node when the currently traversed node is the internal node and two Boundary Volumes (BVs) do not overlap; and storing collision primitives in a leaf node when the currently traversed node is the leaf node and collision primitives in the leaf node overlap.

A system, method, and computer program product are provided for modifying a hierarchical tree data structure. An initial hierarchical tree data structure is received and treelets of node neighborhoods in the initial hierarchical tree data structure are formed. Each treelet includes n leaf nodes and n−1 internal nodes. The treelets are restructured, by a processor, to produce an optimized hierarchical tree data structure.

Methods, systems, devices, and computer program code (software) products enable acceleration of ray tracing by using acceleration data structures with high arity to enable processing of nodes using streaming SIMD (Single Instruction, Multiple Data) instructions with reduced memory requirements.

The invention discloses a surface area heuristic construction KD (K-dimension) tree parallel method on a graphics processing unit. A traditional serial method on a CPU (central processing unit) can not well play the powerful parallel computing capability of a GPU (graphics processing unit) streaming architecture. The surface area heuristic construction KD tree parallel method disclosed by the invention comprises the following steps of: inputting data description of a 3D (three-dimensional) scene; designing a data structure of a KD-Tree space partition structure; performing SAH (surface area heuristic) optimization function parallel computing; and performing parallel triangle mesh cutting and sequencing. According to the method disclosed by the invention, the high-quality KD-Tree space partition structure can be constructed for an input 3D model on the GPU streaming architecture in a high-efficient and parallel manner, and the efficiency of the method disclosed by the invention is higher than that of the traditional serial and parallel methods on the CPU; furthermore, in the aspect of acceleration ratio of interaction with rays, the method disclosed by the invention is much higher than a BVH (bounding volume hierarchy)-Tree acceleration method which is currently relatively popular on the GPU.

Some aspects of the disclosure include systems and methods for grouping rays into sets according to their directions. In some cases, the rays of the directional sets may then be organized into a hierarchy according to their origins and bounding cones are generated for the hierarchy nodes. The resulting bounding cone hierarchy may be intersected with a bounding volume hierarchy or other scene hierarchy.

An apparatus and method are described for using tessellation hardware to generate bounding volume hierarchies (BVHs) and perform other ray tracing operations. For example, one embodiment of an apparatus comprises: a shader to output a plurality of tessellation factors and one or more input surfaces; and a tessellation circuit comprising first circuitry and / or logic to tesselate each input surface to generate a new set of primitives and second circuitry and / or logic to concurrently generate a bounding volume hierarchy (BVH) 1521 based on the new set of primitives.

A method and apparatus to construct a bounding volume hierarchy (BVH) tree includes: generating 2-dimensional (2D) tiles including primitives; converting the 2D tiles into 3-dimensional (3D) tiles; and constructing the BVH tree based on the 3D tiles.

An apparatus and method for performing BVH compression and decompression concurrently with stores and loads, respectively. For example, one embodiment comprises: bounding volume hierarchy (BVH) construction circuitry to build a BVH based on a set of input primitives, the BVH comprising a plurality of uncompressed coordinates; traversal / intersection circuitry to traverse one or more rays through the BVH and determine intersections with the set of input primitives using the uncompressed coordinates; store with compression circuitry to compress the BVH including the plurality of uncompressed coordinates to generate a compressed BVH with compressed coordinates and to store the compressed BVH to a memory subsystem; and load with decompression circuitry to decompress the BVH including the compressed coordinates to generate a decompressed BVH with the uncompressed coordinates and to load the decompressed BVH with uncompressed coordinates to a cache and / or a set of registers accessible by the traversal / intersection circuitry.

The invention discloses a single instruction multiple data (SIMD)-based k-discrete oriented polytope (k-DOP) bounding volume collision detection method, which comprises the following steps of: (1) constructing a bounding volume hierarchy (BVH) by using an SIMD instruction; (2) constructing a bounding volume testing tree (BVTT), and performing a bounding volume overlap test on the BVTT by using the SIMD instruction; and (3) performing accurate collision detection on a bounding volume. The instruction-level parallel processing capability of SIMD is utilized, so that the number of instructions in the collision detection operation process is reduced, the process of constructing or reconstructing the bounding volume and constructing or updating the BVH and the bounding volume overlap test process are accelerated, and collision detection time is shortened; and compared with the conventional collision detection method, the method has the advantages that: the speed can be improved by about 4 times, and the method is high in compatibility and is effectively complementary with task-level parallel processing, so that the whole parallel speed-up ratio is improved, and the method is particularly suitable for the technical fields of robot motion path planning, physical simulation, video games and the like.

An apparatus and method are described for using tessellation hardware to generate bounding volume hierarchies (BVHs) and perform other ray tracing operations. For example, one embodiment of an apparatus comprises: a shader to output a plurality of tessellation factors and one or more input surfaces; and a tessellation circuit comprising first circuitry and / or logic to tesselate each input surface to generate a new set of primitives and second circuitry and / or logic to concurrently generate a bounding volume hierarchy (BVH) based on the new set of primitives.

A boundary handling for particle-based simulation is disclosed. Boundary handling is performed in particle-based simulation. Slab cut ball processing defines the boundary volumes for interaction with particles in particle-based simulation. The slab cut balls are used for collision detection of a solid object with particles. The solid object may be divided into a plurality of independent slab cut balls for efficient collision detection without a bounding volume hierarchy. The division of the solid object may be handled in repeating binary division operations. Processing speed may be further increased by determining the orientation of each slab cut ball based on the enclosed parts of the boundary rather than testing multiple possible orientations.

Apparatus and method for a compressed stack representation for a BVH. For example, one embodiment of an apparatus comprises: a ray generator to generate a plurality of rays in a first graphics scene; a bounding volume hierarchy (BVH) generator to construct a BVH comprising a plurality of hierarchically arranged nodes, wherein the BVH comprises a specified number of child nodes at a current BVH level beneath a parent node in the hierarchy; traversal / intersection circuitry to traverse one or more of the rays through the hierarchically arranged nodes of the BVH and intersect the one or more rays with primitives contained within the nodes; a short traversal stack of a fixed size comprising a specified number of entries fewer than the number of child nodes beneath the parent node, each entry associated with a child node at the current BVH level, the entries ordered from top to bottom within the short traversal stack based on a sorted distance of each respective child node, wherein each entry includes a field to indicate whether that entry is associated with a final child in the current BVH level; wherein the traversal / intersection circuitry is to process entries from the top of the traversal stack, removing entries as they are processed, the traversal / intersection circuitry to determine that a current entry is associated with the final child node at the current BVH level by reading a first value in the field.

Apparatus and method for box-box testing. For example, one embodiment of a processor comprises: a bounding volume hierarchy (BVH) generator to construct a BVH comprising a plurality of hierarchically arranged BVH nodes; traversal circuitry to traverse query boxes through the BVH, the traversal circuitry to read a BVH node from a top of a BVH node stack and to read a query box from a local storage or memory, the traversal circuitry further comprising: box-box testing circuitry and / or logic to compare maximum and minimum X, Y, and Z coordinates of the BVH node and the query box and to generate an overlap indication if overlap is detected for each of the X, Y, and Z dimensions; distance determination circuitry and / or logic to generate a distance value representing an extent of overlap between the BVH node and the query box; and sorting circuitry and / or logic to sort the BVH node within a set of one or more additional BVH nodes based on the distance value.

Apparatus and method for a compressed stack representation for a BVH. For example, one embodiment of an apparatus comprises: a ray generator to generate a plurality of rays in a first graphics scene; a bounding volume hierarchy (BVH) generator to construct a BVH comprising a plurality of hierarchically arranged nodes, wherein the BVH comprises a specified number of child nodes at a current BVH level beneath a parent node in the hierarchy; traversal / intersection circuitry to traverse one or more of the rays through the hierarchically arranged nodes of the BVH and intersect the one or more rays with primitives contained within the nodes; a short traversal stack of a fixed size comprising a specified number of entries fewer than the number of child nodes beneath the parent node, each entry associated with a child node at the current BVH level, the entries ordered from top to bottom within the short traversal stack based on a sorted distance of each respective child node, wherein each entry includes a field to indicate whether that entry is associated with a final child in the current BVH level; wherein the traversal / intersection circuitry is to process entries from the top of the traversal stack, removing entries as they are processed, the traversal / intersection circuitry to determine that a current entry is associated with the final child node at the current BVH level by reading a first value in the field.

Apparatus and method for double-precision traversal and intersection. For example, one embodiment of an apparatus comprises: a bounding volume hierarchy (BVH) generator to construct a BVH comprising a plurality of hierarchically arranged BVH nodes; a ray storage to store rays to be traversed through one or more of the BVH nodes; ray traversal circuitry comprising a first plurality of 64-bit arithmetic logic units (ALUs) which natively support double-precision floating point operations, the ray traversal circuitry to use at least a first ALU of the one or more ALUs to traverse a first ray through a first BVH node at a double-precision floating point precision to generate double-precision floating point traversal results; a plurality of execution units (EUs) coupled to the ray traversal circuitry, at least one of the plurality of EUs comprising a second plurality of 64-bit ALUs capable of natively performing double-precision floating point operations, the at least one of the plurality of EUs to execute one or more intersection shaders to perform ray-primitive intersection testing at double-precision floating point precision based on the double-precision floating point traversal results.

The invention discloses a polluted water environment three-dimensional rapid display method and a system. The method comprises: sensing information of each water area by a corresponding sensor, and transmitting data back at regular time, storing information sensed by sensors to a database; establishing a case library in accordance with five types of the national water quality standard; dividing a water environment three-dimensional scene, and establishing a scene tree based on a BSP tree structure with a water area target knot as an organization unit; conducting view frustum culling based on a bounding volume hierarchy of the scene tree; determining the grade of water quality based on the data sensed by sensors; looking for corresponding cases in the library based on the determination result, and displaying water quality graphics; and looking for water quality information by clicking. The method and the system of the invention obviate the need for experts to observe water quality on site, realize rapid display of polluted water environment three-dimensional graphics, can conduct automatic selection of corresponding water quality graphics, and enable experts to roam in the water environment three-dimensional scene and observe, look for real-time information of current water area, and facilitate experts' research on polluted water environment.

The invention discloses a loudspeaker array-based virtual acoustic environment auralization implementation method and system. The method comprises the steps that 1, a bounding volume hierarchy structure tree of a geometric model of a target environment is constructed; 2, sound field distribution of a sound source is calculated by means of the bounding volume hierarchy structure tree and the location of a given sound source; 3, room impulse responses from the sound source to target locations in the target environment are calculated according to the sound field distribution of the sound source;4, the room impulse responses obtained through calculation are converted into HOA coefficient vectors; 5, the HOA coefficient vectors are decoded according to the actual placing locations of loudspeakers in a replaying environment to obtain gains of the various loudspeakers, and the gains are called as multi-channel room impulse responses; and 6, the multi-channel room impulse responses obtained through decoding are convolved with any sound source signal to serve as signals of the loudspeakers to reconstruct a sound field of the sound signal at the target location. According to the method, replaying of a virtual acoustic environment in a non-standard playing environment is achieved.

A system, method, and computer program product are provided for modifying a hierarchical tree data structure. An initial hierarchical tree data structure is received and treelets of node neighborhoods in the initial hierarchical tree data structure are formed. Each treelet includes n leaf nodes and n−1 internal nodes. The treelets are restructured, by a processor, to produce an optimized hierarchical tree data structure.

Apparatus and method for a hierarchical beam tracer. For example, one embodiment of an apparatus comprises: a beam generator to generate beam data associated with a beam projected into a graphics scene; a bounding volume hierarchy (BVH) generator to generate BVH data comprising a plurality of hierarchically arranged BVH nodes; a hierarchical beam-based traversal unit to determine whether the beam intersects a current BVH node and, if so, to responsively subdivide the beam into N child beams to test against the current BVH node and / or to traverse further down the BVH hierarchy to select a new BVH node, wherein the hierarchical beam-based traversal unit is to iteratively subdivide successive intersecting child beams and / or to continue to traverse down the BVH hierarchy until a leaf node is reached with which at least one final child beam is determined to intersect; the hierarchical beam-based traversal unit to generate a plurality of rays within the final child beam; and intersection hardware logic to perform intersection testing for any rays intersecting the leaf node, the intersection testing to determine intersections between the rays intersecting the leaf node and primitives bounded by the leaf node.

The invention discloses a bounding volume hierarchy design method targeted at motion blur. The method includes two parts: a construction period and a traversal period. In the construction period, the method includes the following steps: in a node of a BVH structure, finding out all surface patches with irregular motion behaviors; collecting all surface patches with the above mentioned characteristics and placing the surface patches at a special node: MB node and recording a time point when the surface patches cross a dividing plane at the same time; and after the MB node is generated, setting a threshold, when surface patches which move into the MB node cover more than 50% of all the surface patches, according to an SAH cost model, recalculating the potion of a division point on the basis of remaining surface patches in the node so as to generate new left and right sub-nodes. In the traversal period, the method includes the following steps: instructing the irregular surface patches in the MB node to be redistributed; re-dividing all the surface patches in the MB node into corresponding left and right sub-nodes; and then re-calculating corresponding node bounding volume hierarchies and adjusting downward bounding volume hierarchies of sub-nodes and carrying out recursion on the process until the whole updating work is completed.

The invention provides a cloth real-time simulation method for virtual fitting, which belongs to the technical field of virtual fitting. The problem solved by the invention is that a cloth fast simulation method based on a GPU is proposed for the problem that the simulation speed of the existing 3D virtual fitting is slow. The core part of a main algorithm of the cloth real-time simulation methodis to rapidly construct and update a bounding volume hierarchy (BVH) by maximally utilizing the parallelism of the GPU, and a collision detection and processing method for corresponding large step integration is proposed. According to the cloth real-time simulation method, an entire cloth simulation system is arranged on the GPU, and a corresponding stream processing algorithm is proposed. Compared with some existing methods at present, the cloth real-time simulation method provided by the invention can realize cloth simulation more rapidly on the basis of ensuring high realness degree of cloth simulation, realizes the real-time simulation of clothing in a virtual fitting application, and is suitable for other cloth simulation fields.

An apparatus and method for performing BVH compression and decompression concurrently with stores and loads, respectively. For example, one embodiment comprises: bounding volume hierarchy (BVH) construction circuitry to build a BVH based on a set of input primitives, the BVH comprising a plurality of uncompressed coordinates; traversal / intersection circuitry to traverse one or more rays through the BVH and determine intersections with the set of input primitives using the uncompressed coordinates; store with compression circuitry to compress the BVH including the plurality of uncompressed coordinates to generate a compressed BVH with compressed coordinates and to store the compressed BVH to a memory subsystem; and load with decompression circuitry to decompress the BVH including the compressed coordinates to generate a decompressed BVH with the uncompressed coordinates and to load the decompressed BVH with uncompressed coordinates to a cache and / or a set of registers accessible by the traversal / intersection circuitry.