EP0160848A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Computer systems for curve-solid classification and solid modeling
Assignee: University of Rochester
•
Filing: 1985-04-04
•
Granted: —
•
Expires: 2005-04-04
Abstract
Abstract A computer system is introduced for curve-solid classification (raycasting) of objects in constructive solid geometry (CSG) modeling to produce image representations of two-and three- dimensional objects. The system carries out curve-solid classifications in parallel and at much higher speed than a general purpose computer. It uses primitive classification processors which compute all of the (curve-line or ray) primitive (basic solid bodies: block, cylinder, etc) intersections in parallel, combine processors which are connected into a binary tree that duplicates the binary tree defining the CSG solid and computes the set operations (union, intersection and difference), and a host computer.
Inventors
- 👤 Gershon Kedem
- 👤 John L. Ellis
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-30 22:09
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/10
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
97 words
A system for the characterization of plural dimensional objects, including representing images of such objects from the intersections of curves with primitive solids from which said object can be constructed which comprises primitive classification means for computing the intersections of a plurality of curves with said primitive solids, means for computing classification combinations arranged with said primitive classification means in a binary tree which defines the object by constructive solid geometry, said classification combination computing means each corresponding to a different node of said tree and having means for computing a set operation for its corresponding node.
Claim 2
Independent Claim
97 words
A system for the characterization of plural dimensional objects, including representing images of such objects from the intersections of curves with primitive solids from which said object can be constructed which comprises primitive classification means for computing the intersections of a plurality of curves with said primitive solids, means for computing classification combinations arranged with said primitive classification means in a binary tree which defines the object by constructive solid geometry, said classification combination computing means each corresponding to a different node of said tree and having means for computing a set operation for its corresponding node.
Claim 3
Dependent Claim
14 words
The system according to Claim 1 wherein said tree is a right-heavy binary tree.
Claim 4
Dependent Claim
27 words
The system according to Claim 1 wherein said primitive classification means and said classification combination computing means are arranged in a (log 2 (N)+1) X N array.
Claim 5
Dependent Claim
29 words
The system according to Claim 3 wherein said tree is a right-heavy binary tree the primitive classification and classification combination computing means of which are imbedded in said array.
Claim 6
Dependent Claim
57 words
The system according to Claim 4 wherein the leaves of said tree are the primitive classification means and are disposed in rows at the bottom of said array, said classification combination computing means are disposed in rows above said bottom row and the root of said array is in the upper left comer of the uppermost row.
Claim 7
Dependent Claim
36 words
The system according to Claim 1 further comprising host computer means for communicating instructions from said primitive classification means and receiving outputs from one of said classification combination computing means at the root of said tree.
Claim 8
Dependent Claim
37 words
The system according to Claim 6 further comprising means included in said primitive classification means and said classification combining means for propagating instructions from said host computer through said primitive classification means and said classification combination means.
Claim 9
Dependent Claim
52 words
The system according to Claim 1 further comprising host comptuer means for operating said primitive classification means and said classification combination means to classify a plurality of rays one at a time in each of said primitive classification means and the results of each plurality of rays in said classification combiner means.
Claim 10
Dependent Claim
65 words
The system according to Claim 1 wherein said primitive solids are constructed from linear and quadratic half spaces and said primitive classification means includes means for incrementally classifying said intersections with a family of straight lines which constitute said curves, said lines being defined by the following equation: and said classification means being operative by solving the equation for each of said lines, as follows:
Claim 11
Dependent Claim
53 words
The system according to Claim 9 wherein each primitive classification means comprises means for incrementally computing the intersection of said lines with said half spaces, means for controlling said incremental computing means, and output means connecting said incremental computing means with the one of said classification combination means above it in said tree.
Claim 12
Dependent Claim
73 words
The system according to Claim 10 wherein said incremental computing means comprises means for computing B/2A + SQRT ((B/2A)' -C/A) where A(h,s) is obtained by collecting all the terms that multiply t2 in equation (3) (of Claim 9) above. B(h,s) are all the terms in equation (3) (of Claim 9) that multiply t. C(h,s) is obtained by collecting all the terms in equation (3) (of Claim 9) that has no t in them.
Claim 13
Dependent Claim
64 words
The system according to Claim 1 wherein said classification combination computing means is provided by a log 2 (N) X N array of identical combiner processors each comprising means combining signals corresponding to sequences of leading and trailing ends of interval segments defined by the intersections of said curves and said solids and means for controlling the set operation performed by said combining means.
Claim 14
Dependent Claim
34 words
The system according to Claim 12 wherein said combining means comprises a min-max compare network, and said controlling means comprises programmable logic array means and host computer means, for programming said logic array means.
Claim 15
Dependent Claim
41 words
The system according to Claim 13 further comprising input and output multiplexers for inputting digital signals representing said leading and trailing ends of said interval segments and deriving outputs representing leading and trailing ends of said segments from said min-max network.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.