US5086495A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Solid modelling system with logic to discard redundant primitives
Assignee: International Business Machines Corp
•
Filing: 1988-12-16
•
Granted: 1992-02-04
•
Expires: 2008-12-16
Abstract
Abstract A solid modelling system for generating a spatial representation of an object defined by a structure having a plurality of linked nodes representing the object in terms of solid geometric primitives combined by a logical expression, which is adapted to recognize redundant primitives automatically. Bitmap generation logic (BGL) is provided for traversing at least certain of the nodes in the structure for generating a bitmap representing the part of the logical expression defined in the traversed nodes and redundant primitive logic (RPL) is provided for testing the bitmap for logical redundancies indicative of redundant geometric primitives. Each bit in the bitmap is representative of a respective one of the constituents of the primitives, a constituent being the volume formed by the intersection of primitives or their complements, and, in order to test for the redundancy of a primitive u, the RPL tests for equivalence of the corresponding utrue and ufalse constituents in the bitmap. The BGL additinally generates a table of pointers to the primitives encountered during the traversal and the RPL deletes from the table a pointer to a primitive which is found to be redundant. Node generation logic (NGL) is provided for replacing the nodes traversed by the first logic by a single truth table node which comprises the modified bitmap produced by the RPL and pointers to nodes defining the remaining primitives. Logic may also be provided for processing a relevance map indicative of geometric information in combination with the bitmap.
Inventors
- 👤 Michael A. Gray
- 👤 Alan R. Halbert
- 👤 Stephen J. Todd
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 02:47
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
101 words
A solid modelling system for generating a spatial representation of an object defined in terms of solid geometric primitives combined by a logical expression including one or more combinatorial logical operators, comprising: object definition means including a structure comprising a plurality of linked nodes for said primitives and for said operators; first logic means for traversing at least certain of the nodes generating a table comprising a bitmap representing the logical expression or the part thereof defined at the operator nodes encountered during the traversal; and second logic means for testing the bitmap for logical redundancies indicative of redundant geometric primitives.
Claim 2
Dependent Claim
101 words
A solid modelling system for generating a spatial representation of an object defined in terms of solid geometric primitives combined by a logical expression including one or more combinatorial logical operators, comprising: object definition means including a structure comprising a plurality of linked nodes for said primitives and for said operators; first logic means for traversing at least certain of the nodes generating a table comprising a bitmap representing the logical expression or the part thereof defined at the operator nodes encountered during the traversal; and second logic means for testing the bitmap for logical redundancies indicative of redundant geometric primitives.
Claim 3
Dependent Claim
57 words
A solid modelling system as claimed in claim 1 wherein each bit in the bitmap is representative of a respective one of the constituents of said primitives and wherein said second logic means, in order to test for the redundancy of a primitive u, tests for the equivalence of corresponding utrue and ufalse constituent in the bitmap.
Claim 4
Dependent Claim
47 words
A solid modelling system as claimed in claim 1 wherein said first logic means additionally generates a set of pointers to the primitives encountered during the traversal and wherein the second logic deletes from the set a pointer to a primitive which is found to be redundant.
Claim 5
Dependent Claim
51 words
A solid modelling system as claimed in claim 3 additionally comprising third logic means for replacing the nodes traversed by said first logic means by a single truth table node which comprises the bitmap produced by said first logic means and the set of pointers to nodes defining the remaining primitives.
Claim 6
Dependent Claim
130 words
A solid modelling system as claimed in claim 4 which additionally comprises: world space definition means for defining a voxel in which the object exists; spatial subdivision logic means for subdividing world space into progressively smaller voxels until voxels are created for which the spatial representation can be rendered; object simplification logic means for simplifying the structure defining the object within a voxel generated by the spatial subdivision means by combining or eliminating primitives entirely inside or outside said voxel; counting logic means for counting the number of primitives remaining in the, or a part of a simplified structure as generated by the object simplification means and, if there are less than a predetermined number of primitives, to cause the first and second logic means to process said simplified structure.
Claim 7
Dependent Claim
44 words
A solid modelling system as claimed in claim 5 in which the object simplification logic means comprises: logic which, within a voxel generated by said spatial subdivision logic means simplifies the truth table node previously inserted in the structure by the third logic means.
Claim 8
Dependent Claim
42 words
A solid modelling system as claimed in claim 5, additionally comprising logic for processing a relevance map representative of geometric information for indicating when bits of the bitmap are determined to be irrelevant to the definition of the object within that voxel.
Claim 9
Dependent Claim
30 words
A solid modelling system as claimed in claim 7, wherein said second logic means deletes from the set of pointers a pointer to a primitive by modifying the relevance map.
Claim 10
Dependent Claim
130 words
A solid modelling system as claimed in claim 1 which additionally comprises: world space definition means for defining a voxel in which the object exists; spatial subdivision logic means for subdividing world space into progressively smaller voxels until voxels are created for which the spatial representation can be rendered; object simplification logic means for simplifying the structure defining the object within a voxel generated by the spatial subdivision means by combining or eliminating primitives entirely inside or outside said voxel; counting logic means for counting the number of primitives remaining in the, or a part of a simplified structure as generated by the object simplification means and, if there are less than a predetermined number of primitives, to cause the first and second logic means to process said simplified structure.
Claim 11
Dependent Claim
42 words
A solid modelling system as claimed in claim 9 additionally comprising logic for processing a relevance map representative of geometric information for indicating when bits of the bitmap are determined to be irrelevant to the definition of the object within that voxel.
References Cited (Backward Citations)
US4694404A
Cited
US4649498A
Cited
US4845651A
Cited
US4809201A
Cited
US4862392A
Cited
US4858149A
Cited
US4816999A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-02-03 | 1995-08-05 | 1996-02-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-02-03 | 1999-08-05 | 2000-02-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-02-03 | 2003-08-05 | 2004-02-04 | $7700.00 | Window Closed / Lapsed |