Patent ID: 6993461

Claim:
A method for use in calculation of a swept volume of a computer generated model of a real-world object, the method comprising: generating a three dimensional polyhedral representation of the model of the real-world object, the representation comprising a plurality of triangles joined at their edges, said triangles forming a tessellated representation of the modeled real-world object; representing three dimensional motion of the modeled object by a series of sequential positions of the modeled object in three dimensional space; and for each position in the series of sequential positions of the modeled object, (i) determining a subset of the edges such that each edge in said subset has a trajectory through a corresponding first zone in which motion of the corresponding edge comprises motion on the boundary of the modeled swept volume during motion of the modeled object from a current position to a next position, where each such edge's corresponding first zone comprising a region external to the material of the modeled object and bounded by a planar extension of the triangles that join at said edge; (ii) determining a subset of the triangles such that each triangle in said subset has a trajectory through a corresponding second zone during motion of the modeled object from a preceding position to a current position and from the current position to a next position; and where: each such triangle's second zone comprises a zone represented by a half sphere, said half sphere comprising a flat face that is planar with said triangle, and said half sphere extending interior to the modeled object, and said second zone representing a space that had been occupied by at least a portion of the modeled object when the modeled object was positioned at said preceding position; (iii) generating a trace of the motion of said subset of edges between said current and said next positions; and constructing a representation of the swept volume from the generated traces of the motion of said subset of edges wherein constructing a representation of the swept volume further comprises bounding the swept volume at each of said current positions in said series by said subset of triangles associated with each such current position.