Method and apparatus for spatial simulation acceleration

• US 5,572,634 A
• Filed: 10/26/1994
• Issued: 11/05/1996
• Est. Priority Date: 10/26/1994
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Silicon Engines Incorporated
• Inventors: Duluk, Jerome F. Jr.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): BUCHEL JR, RUDOLPH JOHN
• Application Number:
  US08/329,226
• Time in Patent Office: 741 Days
• Field of Search: 395/119, 395/120, 395/121
• US Class Current: 345/419
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

Apparatus and method for detecting unconstrained collisions between three-dimensional moving objects are described. The apparatus and method addresses the problems associated with handling objects with substance passing through each other in three-dimensional space. When objects collide in a three-dimensional simulation, it is important to identify such collisions in real-time so that the behavior of the colliding objects may be adjusted appropriately. Native vertices are stored and novel structure is provided so that the stored words containing native vertices work together to form polygons, or other object primitives, that work together. For triangle object primitives, three vertices form the first triangle primitive, but a second triangle primitive is formed by receiving and storing only one additional vertex, the other two vertices needed to form the second triangle primitive being shared with the first triangle primitive. The apparatus and method also provides structure for storing and communicating polygon vertex relationship information between multiple object primitives and objects, and structure and method for comparing the extent of an object primitive with all other previously stored object primitive extents simultaneous with receipt and storage of the object primitive vertex data. The ability to store each coordinate vertex only once and to share the vertex coordinate information among multiple objects radically reduces the vertex storage requirements, simplifies unconstrained object collision determinations, and increases data throughput so that real-time, or near real-time, computations appropriate for simulation are achieved.

Claims

1. A geometric content addressable memory (GCAM) for determining the occurrence of collisions between displayed representations of a stored three-dimensional object and a new three-dimensional object, said representation of said stored object being defined by n stored vertices, said GCAM comprising:

(a) a plurality of bus lines including an x bus, y bus, and z bus, wherein said x, y and z busses respectively supply a new x, y and z coordinate of a new vertex of said new object to every one of said identical memory cells simultaneously;

(b) n identical memory cells, wherein an n^th one of said memory cells includes;

(i.) coordinate storage and arithmetic comparator fields X(n), Y(n) and Z(n) including register means for storing x, y and z coordinates of an n^th one of said stored vertices, and arithmetic comparator means for simultaneously computing comparison results XComp(n), YComp(n) and ZComp(n) indicating whether said new x, y and z coordinate supplied respectively from said x, y and z bus is less than or greater than said x, y and z coordinates stored in said register means of said coordinate fields X(n), Y(n) and Z(n);

(ii.) a plurality of input lines carrying input signals including x-, y-, and z-coordinate vertex miss outputs XVrtxMsOut(n-1), YVrtxMsOut(n-1) and ZVrtxMsOut(n-1) from an n-1^th one of said memory cells;

(iii.) coordinate miss detectors XMsDetect(n), YMsDetect(n) and ZMsDetect(n) that respectively compute vertex miss outputs XVrtxMsOut(n), YVrtxMsOut(n), ZVrtxMsOut(n) and polynomial miss signals XPlyMs(n), YPlyMs(n), ZPlyMs(n) based on said comparison results XComp(n), YComp(n) and ZComp(n), a new status signal, and said vertex miss outputs XVrtxMsOut(n-1), YVrtxMsOut(n-1) and ZVrtxMsOut(n-1) from a n-1^th one of said memory cells, wherein a representative with x vertex miss output XVrtxMsOut(i) indicates whether a said new x coordinate misses (or is not in collision with) corresponding stored x coordinates of vertices 1 through i of said stored object, and a said polynomial miss signal is identical to a said vertex miss output;

(iv.) a polygon miss detector that determines, based on said polynomial miss signals XPlyMs(n), YPlyMs(n), ZPlyMs(n), said new status signal and a standard status signal whether said new vertex misses a polygon defined by said n vertices of said stored object; and

(v.) control means for synchronizing operations of said n^th cell with operations of said n-1^th cell and a simulator display accelerator of which said GCAM is a part.

2. A geometric content addressable memory and collision detection apparatus, said apparatus comprising:

(a) means for storing a plurality of data words, each of said data words including a plurality of data fields including data fields for storing a single coordinate vertex values and a data field for storing a spatial primitive identifier defined by one or more of said words, each of said data fields being divided into a plurality of data bits;

(b) a data bus for providing an input data stream including a plurality of input field matching some of said data word fields including input fields containing coordinate vertex values, and each said input field divided into input bits so as to have a one-to-one bit correspondence to the said data bits in said matching data fields in said words;

(c) query means for simultaneously comparing said plurality of input fields provided by said input data bus to all said stored data words, with simultaneous field comparisons such that each said data word field matching said input field is compared to its corresponding input field, and for generation of query results for at least one said field in said data word and for temporarily storing within said data word; and

(d) collision miss detector means for receiving said query results from a multiplicity of said data word, and for generating a spatial primitive miss signal indicating that the spatial primitive associated with said data word does not intersect with the spatial primitive associated with said input field.

3. A system for querying geometrical data to determine object collisions in three-dimensional space, comprising:

means for receiving a new multi-dimensional coordinate vertex representing a location on a portion of a multi-dimensional object, a predetermined plurality of said vertices received in a predefined order defining an spatial primitive;

means for relating said newly received coordinate vertex with previously received vertices to form vertex associations that define said spatial primitives;

means for simultaneously storing said received vertex and comparing a spatial primitive completed by said received vertex and said associated vertices with all other previously received and stored spatial primitives defined by earlier received vertices to determine if said newly formed spatial primitive has an multi-dimensional coordinate extent that collides (overlaps) with the multi-dimensional coordinate extent of any previously defined and stored spatial primitives;

means for storing an indication of said collision in association with said stored vertex.

4. A method for storing and querying geometrical data to determine geometrical object collisions in three-dimensional space, said method comprising the steps of:

(a) receiving a description of a multiplicity of geometry items as ordered sets of values having a predetermined number of vertex coordinates, said set of vertex coordinates including an x-coordinate, a y-coordinate, and a z-coordinate, at least some of said sets of vertex coordinates being shared between a plurality of said multiplicity of geometrical items;

(b) storing each said received vertex coordinate as it is received in the order received in at most one vertex storage location, each said shared vertex coordinate being stored only once;

(c) establishing a vertex link indicator to each one of said vertices that jointly form a surface with a linking indicator stored with said vertex coordinate identifying the geometry item associated with the vertex stored in the word;

(d) simultaneously comparing the x-, y-, z-coordinate extent of a received geometry item with the respective x-, y-, z-coordinate extents of all earlier received and stored geometry items to determine if said received and stored objects intersect, said simultaneous comparing including comparisons based on a predetermined number of previous collision comparisons;

(e) storing coordinate extent collision information from a predetermined number of said simultaneous comparisons;

(f) using said vertex link indicator in said step of simultaneously comparing to control propagation of coordinate extent collision information from a predetermined number of previous comparisons; and

(g) repeating said steps (a)-(f) for each geometry item received.

5. The apparatus in claim 4, further comprising means for groups of GCAM words to operate cooperatively to store a spatial geometry primitive without vertex storage redundancy;

and means for said spatial geometry primitive to share vertices.

6. A geometrical content addressable memory (GCAM) word structure comprising:

coordinate field storage and logic means for receiving a new coordinate value from a coordinate bus, for storing said new value as a stored value in response to write control signals, for reading said stored value in response to read control signals, and for arithmetically comparing a later arriving new value with said stored value to generate a signal indicating whether said stored value is less than or greater than said later arriving new value;

coordinate tag field storage and logic means for storing the address identifier for the geometry item stored in the particular GCAM word;

coordinate collision miss detector means for receiving a plurality of coordinate query comparison results from comparisons of the coordinate extents of said new polygon with said stored polygons and for generating a coordinate miss signal indicating that the stored polygon is either wholly greater than or wholly less than the extent;

polygon collision miss detector means for receiving a plurality of coordinate miss-detect signals, and for simultaneously comparing said coordinate miss-detect signals to determine if any one of said plurality of coordinate miss-detect signals indicate that the coordinate extent of said stored polygon does not overlap the coordinate extent of said new polygon;

word status flag storage and logic means associated with each said GCAM word for receiving a first plurality of word status control signals, for storing said signals, and for generating a second plurality of word status indicators that define the treatment afforded to the stored coordinate vertex associated with said word status indicators;

word control logic means associated with each GCAM word for controlling the reading and writing of data to and from said word in response to word status indicators, word operation control signals, and word identifier selection signals from said priority resolver means; and

word priority resolver means for identifying the first GCAM word address storing either a collision hit or invalid data indicator.

7. A coordinate field storage and logic structure comprising:

a multiple-bit register for receiving a new coordinate value from a coordinate bus and for storing said received coordinate value as a stored coordinate in response to a clock signal and a word write enable control signal;

read means for reading said stored coordinate value from said register and for outputting said stored coordinate value to said coordinate bus as a new coordinate in response to a word read enable control signal;

first arithmetic comparator means for receiving said stored coordinate value from said register and said new coordinate value from said coordinate bus, and for comparing said stored and new values in response to a compare enable control signal and generating a first stored-less-than-new coordinate query result signal when said stored value is less than said new value; and

second arithmetic comparator means for receiving said stored coordinate value from said register and said new coordinate value from said coordinate bus, and for comparing said stored and new values in response to a compare enable control signal and generating a second stored-greater-than-new coordinate query result signal when said stored value is greater than said new value;

said first and second arithmetic comparator means making said comparisons and generating said first and second coordinate query result signals simultaneously with receipt of said new coordinate value from said coordinate bus.

8. A coordinate collision miss detector structure comprising:

means for receiving a new (m^th) coordinate query comparison result signal;

means for storing a middle (m-1^th) coordinate query comparison result signal, said middle coordinate query comparison result signal corresponding to the new coordinate query comparison result signal from the previous clock cycle;

means for storing an oldest (m-2^th) coordinate query comparison result signal, said oldest coordinate query comparison result signal corresponding to the middle coordinate query comparison result signal from the previous clock cycle;

first means for generating a comparison conjunction result for a coordinate by logically ANDing together a plurality of signals derived from said coordinate query comparison result signals and generating a coordinate miss due-to-less-than signal when the extent of the stored polygon is determined by said comparison to be wholly less than the extent of the new polygon;

second means for generating a comparison conjunction result for a coordinate by logically ANDing together a plurality of signals derived from said coordinate query comparison result signals and generating a coordinate miss due-to-greater-than signal when the extent of the stored polygon is determined by said comparison to be wholly greater than the extent of the new polygon; and

means for generating a coordinate polygon miss signal indicating that said stored polygon does not overlap in said coordinate extent with said new polygon when either of said coordinate miss due-to-less-than signal or said coordinate miss due-to-greater-than signal are asserted.

9. The coordinate collision miss detector structure in claim 8, wherein said plurality of signals derived from said coordinate query comparison result signals include the new, middle, and oldest signals derived from said coordinate query comparison result.

10. A polygon collision miss detector structure comprising:

means for receiving from said plurality of coordinate miss-detect means a plurality of coordinate polygon miss detect signals; and

means simultaneously computing the disjunctive logical OR of said plurality of coordinate polygon miss detect signals and generating a polygon box mis-detect signal when any one of said plurality of coordinate miss-detect signals indicate that the coordinate extent of said stored polygon does not overlap the coordinate extent of said new polygon.

11. The polygon collision miss detector of claim 10, further comprising:

means for receiving a stored polygon is invalid signal to indicate that the coordinate vertex stored in the particular word does not correspond to a valid polygon;

means for receiving a new polygon is invalid signal to indicate that the new coordinate vertex received does not correspond to a valid polygon; and

wherein said means for simultaneously computing the disjunctive logical OR further computes the disjunctive logical OR of said new polygon invalid signal and said stored polygon is invalid signal.

12. A word status flag storage and logic structure comprising:

first register means for storing an invalid data status indicator which when asserted indicates that the data stored in the word is invalid and can be overwritten;

second register means for storing a considered stored indicator which when asserted indicates that the vertex stored in the word correspond to a valid stored polygon;

third register means for storing a vertex completes polygon indicator which when asserted indicates that the vertex stored in the word completes a valid polygon;

logic means for generating a stored polygon invalid indicator which when asserted indicates that the vertex stored in the word does not correspond to a valid polygon when either said considered stored indicator and said vertex completes polygon are asserted;

fourth register means for storing a replace oldest vertex indicator which when asserted indicates that the vertex stored in the word has replaced the oldest vertex of the previous polygon;

fifth register means for storing a disable oldest polygon indicator which when asserted indicates that the polygon completed by the coordinate stored in the word does not use the oldest vertex of the previous polygon; and

logic means for setting and resetting said register means in response to predetermined status control signals.

13. A word control logic structure comprising:

register means for storing a value derived from said polygon box miss signal output from said polygon miss-detect means of a particular word in response to a store hits/misses control signal generated during a clock cycle when a spatial query is performed, a value being stored in each said GCAM word simultaneously;

means responsive to said priority resolver means for selecting a single word for writing to and enabling writing of data to predetermined fields (coordinate and tag) of said selected word; and

means responsive to said priority resolver means and a vertex read select control signal for selecting a single word for reading from and enabling reading of data from predetermined fields of said selected single word.

14. A word address priority resolver structure comprising:

means for receiving a word select request signal; and

means for generating a priority out signal wherein if said word select signal for said particular word is not asserted then said priority out signal is a daisy chain output of the priority out signal from the previous GCAM word, and if said word select signal for said particular word is asserted and said priority out signal for said previous GCAM word is asserted then asserting a word select signal indicating that the particular word is selected for reading and writing.

15. The word address priority resolver structure in claim 14, wherein said priority resolver is configured as a hierarchical tree structure.

16. The priority resolver structure in claim 14, wherein said priority resolver structure includes precharged domino logic devices so that the output is efficiently indicating its own completion.

17. A tag field storage and logic structure comprising:

means for storing an address identifier for a geometry item stored in the particular GCAM word; and

logic means for queuing the contents of said stored address identifier.

18. The tag field storage and logic structure in claim 17, wherein for a polygon type geometry item, said address identifier is for identifying the address of the polygon completed by the vertex stored in the particular GCAM word.

19. A geometrical content addressable memory (GCAM) logic circuit comprising:

a plurality of word logic means for storing vertex coordinate values related to a geometry item and for computing geometry item coordinate collision results;

control means for controlling movement of data values into said word logic means and for controlling output of object collision result data from said GCAM; and

means for receiving x-, y-, and z-coordinate values for each geometry item from an external coordinate source;

each said word logic means including;

x-coordinate field storage and comparison logic means including register means for storing an x-coordinate and arithmetic comparison means for arithmetically comparing a new x-coordinate value present on an x-coordinate bus with said x-coordinate value stored in said register means and to determine if said stored value is greater-than or less-than said bus x-coordinate, and for generating an x-coordinate comparison result based on said comparison;

y-coordinate field storage and comparison logic means including register means for storing a y-coordinate and arithmetic comparison means for arithmetically comparing a new y-coordinate value present on a y-coordinate bus with said y-coordinate value stored in said register means and to determine if said stored value is greater-than or less-than said bus y-coordinate, and for generating a y-coordinate comparison result based on said comparison;

z-coordinate field storage and comparison logic means including register means for storing a z-coordinate and arithmetic comparison means for arithmetically comparing a new z-coordinate value present on a z-coordinate bus with said z-coordinate value stored in said register means and to determine if said stored value is greater-than or less-than said bus z-coordinate, and for generating a z-coordinate comparison result based on said comparison;

an x-coordinate collision miss detect field logic means associated with said x-coordinate field storage and comparison logic means for receiving said x-coordinate comparison result, a word status flag, and a status control signal and determining whether the x-extent of the stored polygon is wholly less-than the x-extent of the new polygon or wholly greater-than the x-extent of the new polygon, and generating an x-coordinate vertex miss output signal(n) indicating that said x-extent of said stored polygon is wholly greater-than or less-than the x-extent of said new polygon;

a y-coordinate collision miss detect field logic means associated with said y-coordinate field storage and comparison logic means for receiving said y-coordinate comparison result, a word status flag, and a status control signal and determining whether the y-extent of the stored polygon is wholly less-than the y-extent of the new polygon or wholly greater-than the y-extent of the new polygon, and generating an y-coordinate vertex miss output signal(n) indicating that said y-extent of said stored polygon is wholly greater-than or less-than the y-extent of said new polygon;

a z-coordinate collision miss detect field logic means associated with said z-coordinate field storage and comparison logic means for receiving said z-coordinate comparison result, a word status flag, and a status control signal and determining whether the z-extent of the stored polygon is wholly less-than the z-extent of the new polygon or wholly greater-than the z-extent of the new polygon, and generating an z-coordinate vertex miss output signal(n) indicating that said z-extent of said stored polygon is wholly greater-than or less-than the z-extent of said new polygon;

a polygon collision miss detect field logic means for receiving said x-coordinate vertex miss output signal(n), said y-coordinate vertex miss output signal(n), and said z-coordinate vertex miss output signal(n) and generating a polygon box miss detect signal when any of said x-, y-, or z-coordinate vertex miss output signals indicates that said coordinate vertex misses;

word status flag field storage and logic means for storing word status indicators and for controlling use of said word based on said status indicators, including controlling use of said word as a stored or as a new vertex;

word control field logic means for controlling reading and writing of said word; and

word priority resolver means for identifying the first GCAM word address storing either a collision hit or invalid data indicator.

20. A method for detecting spatial volume collisions in a graphics simulator between multi-dimensional objects, each said object represented as at least one mesh of interconnected object primitives, each said object primitive defined by a plurality of vertex data, and each said vertex data including an object identifier, a vertex identifier, and a vertex coordinate, each vertex that is shared by multiple object primitives being represented only a single time in said object representation, the vertex coordinates of all vertices making up said object primitive defining a coordinate extent of said object primitive and the vertex coordinates of all said object primitives making up said object defining the coordinate extent of said object, said method comprising:

receiving an input data item for an object primitive from an external object data source;

simultaneously comparing, as each said object primitive is received, the coordinate extent of said newly received object primitive with the coordinate extent of all other of said previously received and stored object primitives to determine intersections (collisions) between said newly received object primitive and said previously stored object primitives, said comparing being performed on a coordinate axis by coordinate axis basis;

labeling each said determined object primitive intersection but selectively ignoring intersections between object primitives belonging to the same object based on predetermined rules; and

identifying each object having an intersection with another object based on said intersecting object primitives.

21. The method in claim 20, wherein said multi-dimensional coordinate comprises an x-coordinate, a y-coordinate, and a z-coordinate.

22. The method in claim 21, wherein said multi-dimensional coordinate further comprises a time coordinate (t-coordinate).

23. The method in claim 21, wherein said predetermined rules include ignoring intersections of object primitives within a fixed portion of said object, but not ignoring intersections of object primitives for the same object when said object includes object components that may change location relative to other same object components.

24. A method of detecting collisions between a plurality of three dimensional objects, comprising the steps of:

(A) representing each said three-dimensional object as one or more mesh, each said mesh including one or more spatial primitives, each said spatial primitive being represented by a plurality of connected spatial vertices, at least one of said spatial primitives having a unique vertex not shared by any other one of said spatial primitives within the same mesh, and at least one of said spatial primitives within said same mesh having a common vertex that is at the same spatial location as a vertex of at least one other different spatial primitive within said same mesh;

(B) for each mesh in a selected object;

(1) identifying unique vertices and common vertices within said selected mesh, wherein said unique vertices are vertices not included in more than one spatial primitive within said selected mesh, and wherein said common vertices are vertices included in at least two spatial primitive within said selected mesh;

(2) receiving each vertex sequentially from an external spatial primitive source and performing the following steps;

(a) storing each received reflex, including each common vertex, only once in a memory as said vertex is received, and storing indicators associated with each said stored vertex in said memory that identify all of the spatial primitives to which said stored vertex is relevant;

(b) generating at least one vertex comparison result by comparing coordinate values of each said received vertex with the corresponding coordinate values of all other previously stored vertices belonging to other than said same object as said received vertex, if any, to indicate on a coordinate axis-by-axis basis either that said received vertex coordinate values are greater-than, less-than, or equal-to, the corresponding coordinate values of all of said previously stored vertices, and temporarily storing said at least one vertex comparison result in said memory; and

(c) determining if said received vertex completes formation of a spatial primitive, and if said determination indicates that said received vertex completes formation of a spatial primitive, then examining each said temporarily stored vertex comparison result generated for a vertex belonging to said completed spatial primitive to generate an overlap result indicating whether any coordinate for said completed spatial primitive is wholly greater-than or wholly less-than the corresponding coordinates of all previously stored spatial primitives such that no overlap exists, or that any coordinate for said completed spatial primitive is not wholly greater-than and not wholly less-than the corresponding coordinates of all previously stored spatial primitives such that overlap exits; and

(C) repeating step (B) for another selected object.

25. The method in claim 24, wherein said spatial primitives are selected from the group consisting of bounding box, parallelepiped bounding volume, objects represented by a constellation of vertices, points, lines, triangles, polygons, polyhedra, polygon meshes, polyhedron meshes, CSG primitives, and combinations thereof.

26. The method of claim 24, wherein said step of generating at least one vertex comparison result is performed in parallel for each said received vertex.

27. The method of claim 24, wherein an entire three-dimensional object is approximated by a single spatial primitive, and wherein said spatial primitive is a multiplicity of spatial vertices and the convex hull around said vertices encloses said entire object.

28. The method of claim 24, wherein said steps of (a) storing, (b) generating, and (c) determining are performed simultaneously.

29. The method of claim 24, wherein said steps of (a) storing, (b) generating, and (c) determining are performed in parallel.