US5488692A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for representing and manipulating three-dimensional objects on massively parallel architectures
Assignee: International Business Machines Corp
•
Filing: 1994-08-11
•
Granted: 1996-01-30
•
Expires: 2014-08-11
Abstract
Abstract A parallel computing system is described that comprises a plurality of uniquely labeled, parallel processors, each processor capable of modelling a three-dimensional object that includes a plurality of vertices, faces and edges. The system comprises a front-end processor for issuing a modelling command to the parallel processors, relating to a three-dimensional object. Each parallel processor, in response to the command and through the use of its own unique label, creates a directed-edge (d-edge) data structure that uniquely relates an edge of the three-dimensional object to one face of the object. Each d-edge data structure at least includes vertex descriptions of the edge and a description of the one face. As a result, each processor, in response to the modelling command, operates upon a small component of the model and generates results, in parallel with all other processors, without the need for processor-to-processor intercommunication.
Inventors
- 👤 Michael S. Karasick
- 👤 David R. Strip
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:02
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/10; G06T19/00; G06T19/20; G06T2210/00; G06T2210/52; G06T2219/00; G06T2219/20; G06T2219/2021
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
247 words
A method for modelling a three-dimensional object that includes vertices, faces and edges, said method implemented on a parallel computing system which includes a front and processor for issuing modelling instructions and plural modelling processors responsive to said modelling instructions, each modelling processor having an assigned unique label, said method comprising the steps of: storing directed-edge (d-edge) data structures in a plurality of said modelling processors, each d-edge having a label equal to the unique label of the modelling processor in which it is stored, a plurality of d-edges defining a face of said three-dimensional object, said plurality of d-edges sequentially valued, said face having a label equal to one of a sequentially valued d-edge, said data structure defining a d-edge with at least vertex descriptions of an associated edge of said face and a description of said face; issuing an instruction to said modelling processors to model at least a face of said three-dimensional object, said instruction including a designation of said face; enabling each said modelling processor to determine if a d-edge data structure having a label equal to the label of said face that is to be modeled, is stored therein; and operating each said modelling processor which includes a d-edge data description equal to the label of said face, to execute, simultaneously with all other modelling processors including a d-edge data description equal to the label of said face, a modelling instruction with respect to each said stored d-edge data description stored therein.
Claim 2
Independent Claim
247 words
A method for modelling a three-dimensional object that includes vertices, faces and edges, said method implemented on a parallel computing system which includes a front and processor for issuing modelling instructions and plural modelling processors responsive to said modelling instructions, each modelling processor having an assigned unique label, said method comprising the steps of: storing directed-edge (d-edge) data structures in a plurality of said modelling processors, each d-edge having a label equal to the unique label of the modelling processor in which it is stored, a plurality of d-edges defining a face of said three-dimensional object, said plurality of d-edges sequentially valued, said face having a label equal to one of a sequentially valued d-edge, said data structure defining a d-edge with at least vertex descriptions of an associated edge of said face and a description of said face; issuing an instruction to said modelling processors to model at least a face of said three-dimensional object, said instruction including a designation of said face; enabling each said modelling processor to determine if a d-edge data structure having a label equal to the label of said face that is to be modeled, is stored therein; and operating each said modelling processor which includes a d-edge data description equal to the label of said face, to execute, simultaneously with all other modelling processors including a d-edge data description equal to the label of said face, a modelling instruction with respect to each said stored d-edge data description stored therein.
Claim 3
Dependent Claim
79 words
The method as recited in claim 1 wherein each said edge of a three-dimensional model is defined by a plurality of intersecting faces, each intersecting face including a d-edge that is associated with an edge of said face, each said d-edge that is associated with an edge being ordered in a predetermined direction about said edge, said predetermined direction determined in relation to a vector direction of said edge as determined by initial and terminal vertices of said edge.
Claim 4
Dependent Claim
22 words
The method as recited in claim 2 wherein d-edges present in a face are ordered in a predetermined direction about said face.
Claim 5
Dependent Claim
57 words
The method as recited in claim 1 comprising the further step of: after said operating step, causing each said modelling processor to issue, in parallel with all other modelling processors, instructions to display an edge that is derivable from a d-edge data structure that has been modified in a modelling processor in accordance with said modelling instruction.
Claim 6
Independent Claim
210 words
A method for modelling a three-dimensional object that includes vertices, faces and edges, said method implemented on a parallel computing system which includes a front and processor for issuing modelling instructions and plural modelling processors responsive to said modelling instructions, each modelling processor having an assigned unique label, said method comprising the steps of: storing directed-edge (d-edge) data structures in a plurality of said modelling processors, each d-edge having a label equal to the unique label of the modelling processor in which it is stored, a plurality of d-edges defining a face of said three-dimensional object, said plurality of d-edges sequentially valued, said face having a label equal to one of a sequentially valued d-edge, said data structure defining a d-edge with at least vertex descriptions of an associated edge of said face and a description of said face; finding points of intersection between edges of at least a pair of intersecting faces of said three-dimensional object by employing stored d-edge data structures in said plurality of modelling processors; ordering said points of intersection; and distributing said ordered points of intersection into a contiguous sequence of said plural modelling processors for further processing that involves said ordered points of intersection, whereby interprocessor communication links are minimized when such processing occurs.
Claim 7
Independent Claim
210 words
A method for modelling a three-dimensional object that includes vertices, faces and edges, said method implemented on a parallel computing system which includes a front and processor for issuing modelling instructions and plural modelling processors responsive to said modelling instructions, each modelling processor having an assigned unique label, said method comprising the steps of: storing directed-edge (d-edge) data structures in a plurality of said modelling processors, each d-edge having a label equal to the unique label of the modelling processor in which it is stored, a plurality of d-edges defining a face of said three-dimensional object, said plurality of d-edges sequentially valued, said face having a label equal to one of a sequentially valued d-edge, said data structure defining a d-edge with at least vertex descriptions of an associated edge of said face and a description of said face; finding points of intersection between edges of at least a pair of intersecting faces of said three-dimensional object by employing stored d-edge data structures in said plurality of modelling processors; ordering said points of intersection; and distributing said ordered points of intersection into a contiguous sequence of said plural modelling processors for further processing that involves said ordered points of intersection, whereby interprocessor communication links are minimized when such processing occurs.
Claim 8
Independent Claim
243 words
A method for modelling a three-dimensional object that includes vertices, faces and edges, said method implemented on a parallel computing system which includes a front and processor for issuing modelling instructions and plural modelling processors responsive to said modelling instructions, each modelling processor having an assigned unique label, said method comprising the steps of: storing directed-edge (d-edge) data structures in a plurality of said modelling processors, each d-edge having a labels equal to the unique label of the modelling processor in which it is stored, a plurality of d-edges defining a face of said three-dimensional object, said plurality of d-edges sequentially valued, said face having a label equal to one of a sequentially valued d-edge, said data structure defining a d-edge with at least vertex descriptions of an associated edge of said face and a description of said face, said data structure further including a value for said d-edge which provides said d-edge with an order value in relation to other d-edges that share a common vertex; determining an orthogonal vector to an edge having a vertex equal to said common vertex; finding angles between said orthogonal vector and each of a plurality of d-edges that are ordered about said common vertex, said angles measured in a predetermined direction about said common vertex; and distributing said d-edges in order of their found angles into a sequence of contiguous modelling processors to enable minimization of inter-processor communication lengths for further processing involving said d-edges.
Claim 9
Independent Claim
243 words
A method for modelling a three-dimensional object that includes vertices, faces and edges, said method implemented on a parallel computing system which includes a front and processor for issuing modelling instructions and plural modelling processors responsive to said modelling instructions, each modelling processor having an assigned unique label, said method comprising the steps of: storing directed-edge (d-edge) data structures in a plurality of said modelling processors, each d-edge having a labels equal to the unique label of the modelling processor in which it is stored, a plurality of d-edges defining a face of said three-dimensional object, said plurality of d-edges sequentially valued, said face having a label equal to one of a sequentially valued d-edge, said data structure defining a d-edge with at least vertex descriptions of an associated edge of said face and a description of said face, said data structure further including a value for said d-edge which provides said d-edge with an order value in relation to other d-edges that share a common vertex; determining an orthogonal vector to an edge having a vertex equal to said common vertex; finding angles between said orthogonal vector and each of a plurality of d-edges that are ordered about said common vertex, said angles measured in a predetermined direction about said common vertex; and distributing said d-edges in order of their found angles into a sequence of contiguous modelling processors to enable minimization of inter-processor communication lengths for further processing involving said d-edges.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-29 | 1999-07-31 | 2000-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-29 | 2003-07-31 | 2004-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-29 | 2007-07-31 | 2008-01-30 | $7700.00 | Window Closed / Lapsed |