Accelerated three-dimensional intersection testing using compressed volumes
US9245383B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | May 20, 2013 |
| Grant date | Jan 26, 2016 |
| Priority date | — |
| Expiry date | Apr 10, 2034 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T17/005
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Aspects of the present disclosure relate to building volumetric data structures for intersection testing. For example, 3D data may be represented by points associated with triangles. The triangles may be rasterized to a 3D grid. Each cell of the grid may contain a set of triangles. The grid may be used to generate a new grid of larger grid cells, where each larger grid cell represents some portion of cells of the original grid. The triangle data from each new cell may then be encoded as a list of integers including the triangle data. The list of values may be run-length-encoded. The result is a single octree cube. This process may be repeated in order to generate additional octree cubes for the volumetric structure. The volumetric structure may then be used to identify triangles that intersect with a given ray.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.