 |
|
|
|
|
|
 Title: |
US6356262:
System and method for fast polyhedral cell sorting
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Klosowski, James Thomas; Rye, NY
Silva, Claudio T.; Mahwah, NJ
Taubin, Gabriel; Hartsdale, NY
Williams, Peter Lawrence; Livermore, CA
Mitchell, Joseph Shannon Baird; Port Jefferson, NY
Comba, Joao Luiz Dihl; Stanford, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
2002-03-12
/ 1999-04-15
|
| Application Number: |
US1999000292704
|
| IPC Code: |
Advanced:
G06T 15/40;
G06T 17/00;
G06T 17/20;
Core:
G06T 15/10;
more...
IPC-7:
G06T 15/40;
|
| ECLA Code: |
G06T15/00D; G06T15/40; G06T17/00K; G06T17/20;
|
| U.S. Class: |
345/421;
345/619;
|
| Field of Search: |
345/421,433,440,423,619
|
| Priority Number: |
| 1999-04-15 |
US1999000292704 |
| 1998-04-16 |
US1998000082009P |
|
| 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 checks are done to ensure cells are not being projected out of order. This is accomplished by performing "ray shooting'.
|
| Attorney, Agent or Firm: |
Percello, Louis J.Ohlandt, Greeley, Ruggiero & Perle, LLP ;
|
| Primary / Asst. Examiners: |
Zimmerman, Mark; Cao, Huedung X.
|
| INPADOC Legal Status: |
Show legal status actions
|
| Parent Case: |
This application claim benefit to provisional 60/082,009 filed Apr. 16, 1998.
|
| Family: |
None
|
First Claim:
Show all 8 claims |
We claim:
1. A computer implemented method for rendering a polyhedral complex of a plurality of polyhedral cells by means of computing a visibility ordering relation, and projecting said polyhedral cells in either back-to-front or front-to-back order, comprising the steps of:
- building a visibility ordering graph that includes internal edge data for each of said polyhedral cells that has a shared face with any other of said polyhedral cells and external edge data for each of said polyhedral cells that has a boundary face that is not shared with any other of said polyhedral cells;
- sorting said internal edge data and said external edge data of said visibility ordering graph to provide a set of edge data topologically ordering said polyhedral cells in said back-to-front or front-to-back order; and
- rendering said polyhedral cells by using said set of edge data of said visibility graph.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 3 U.S. patent(s) that reference this one
|
|
