System and method for fast polyhedral cell sorting
US6356262B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 15, 1999 |
| Grant date | Mar 12, 2002 |
| Priority date | — |
| Expiry date | Apr 15, 2019 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T17/20
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The visibility ordering of polyhedral cells is efficiently determined by building an ordering graph, comprising oriented edges between two cells. Each edge (A,B) corresponds to the fact that cell A has to be projected, or rendered, before B. A set of ordering relations and rules that can be shown to generate, if one exists, a global ordering of the polyhedral cell complex. Three different types of edges are used to accomplish this: MPVO, BSP and PPC edges. MPVO edges exist between two cells that share a face. To define the BSP edges, a BSP-tree of the boundary faces of the cell complex is constructed. During this construction, some of the boundary faces of the cells will be ‘cut’ by the BSP-tree ‘extended’ faces, into multiple pieces. If C is the boundary cell, and c′, c″, and so on, are the pieces of its boundary faces, the BSP_edge (c′, C) is defined to mean that cell C can only be projected after c′ has been projected by the BSP. A cell C is in the PPC if one of the pieces that compose it, say c′, has been projected by the BSP, but there exist other pieces of cell C that have not been projected. In this case, additional check…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.