Methods and apparatus for efficiently generating isosurfaces and for displaying isosurfaces and surface contour line image data

Claim 3

A method as set forth in claim 1 wherein said step of identifying is performed utilizing predefined tetrahedron component labeling data stored in said storage means.

Claim 4

A method as set forth in claim 1 wherein said step of generating is performed utilizing a predefined isofacet configuration table stored in said storage means.

Claim 5

A method as set forth in claim 3 wherein said step of identifying is performed utilizing predefined tetrahedron component labeling data, stored in said storage means, to provide an index into said isofacet configuration table.

Claim 6

A method as set forth in claim 4 wherein each isofacet, in the set of isofacets generated utilizing said predefined isofacet configuration table, is expressed in terms of said predefined tetrahedron component labeling data.

Claim 7

A method as set forth in claim 1 further comprising the step of displaying isosurface image data utilizing the set of isofacets generated in step (d) for each value-step in said value-step sequence.

Claim 8

A method as set forth in claim 6 wherein said step of displaying isosurface image data is performed utilizing a selected subsequence of said value-step sequence.

Claim 9

A method as set forth in claim 1 further comprising the step of storing, in said storage means, a representation of the set of isofacets generated in step (d) for each value-step in said value-step sequence.

Claim 10

A method as set forth in claim 8 further comprising the step of displaying isosurface image data utilizing the representation of the set of isofacets stored in said storage means.

Claim 11

A method as set forth in claim 9 wherein said step of displaying isosurface image data further comprises the step of dynamically repositioning said isosurface image data utilizing the representation of said set of isofacets stored in said storage means.

Claim 12

A method as set forth in claim 1 further comprising the step of identifying, for each isofacet in a given set of isofacets, which, if any, edges of the isofacet coincide with the surface of said geometric volume forming a segment of a surface contour line.

Claim 13

A method as set forth in claim 11 further comprising the step of displaying surface contour line image data utilizing the isofacet edges identified as coinciding with the surface of said geometric volume.

Claim 14

A method as set forth in claim 12 wherein said step of displaying surface contour line image data is performed utilizing a selected subsequence of said value-step sequence.

Claim 15

A method as set forth in claim 1 wherein said step of subdividing each volume element into a tetraset is performed utilizing a forest fire algorithm.

Claim 18

A method as set forth in claim 15 further comprising the step of generating the set of isofacets determined in step (b) utilizing a predefined isofacet configuration table.

Claim 19

A method as set forth in claim 15 wherein said step of determining further comprises the step of subdividing each volume element into a tetraset.

Claim 22

A method as set forth in claim 18 further comprising the step of assigning each of a plurality of value-steps identified as being contained within a given member tetrahedral element in a given tetraset, whenever such a plurality of value-steps exists, to separate ones of said plurality of parallel processors to determine the isofacets for each value-step identified in step (c).

Claim 25

Apparatus for generating isosurfaces utilizing a digital computer and associated storage means, wherein (1) a geometric volume represented by volume element data including a set of points in three-dimensional space together with connectivity data defining a set of volume elements which subdivide said geometric volume, and (2) a scalar field associated with said set of points, having a single scalar value within a range associated with each point in said set of points, are stored in said storage means, comprising: (a) means for subdividing, coupled to said storage means and forming a part of said digital computer, each volume element represented by the volume element data stored in said storage means, into a tetraset of linear tetrahedral subelements having triangular faces in such a way that the triangular faces of a ven one of the tetrahedral subelements that are subdivisions of a face of a first volume element align with the faces of a given one of the tetrahedral subelements of a second volume element sharing the face of the first volume element; (b) a value-step sequence generator, coupled to said storage means and forming a part of said digital computer, for determining the range of the scalar values stored in said storage means and for subdividing said range into a predefined number of equally spaced value-steps forming a value-step sequence; (c) means for identifying, forming a part of said digital computer, for each volume element and for each member of the tetraset associated with a given volume element, which, if any, value-steps are contained within each tetraset member; and (d) means for generating, forming a part of said digital computer, a set of isofacets for each value-step identified by said means for identifying.

Claim 26

Apparatus for generating isosurfaces utilizing a digital computer and associated storage means, wherein (1) a geometric volume represented by volume element data including a set of points in three-dimensional space together with connectivity data defining a set of volume elements which subdivide said geometric volume, and (2) a scalar field associated with said set of points, having a single scalar value within a range associated with each point in said set of points, are stored in said storage means, comprising: (a) means for subdividing, coupled to said storage means and forming a part of said digital computer, each volume element represented by the volume element data stored in said storage means, into a tetraset of linear tetrahedral subelements having triangular faces in such a way that the triangular faces of a ven one of the tetrahedral subelements that are subdivisions of a face of a first volume element align with the faces of a given one of the tetrahedral subelements of a second volume element sharing the face of the first volume element; (b) a value-step sequence generator, coupled to said storage means and forming a part of said digital computer, for determining the range of the scalar values stored in said storage means and for subdividing said range into a predefined number of equally spaced value-steps forming a value-step sequence; (c) means for identifying, forming a part of said digital computer, for each volume element and for each member of the tetraset associated with a given volume element, which, if any, value-steps are contained within each tetraset member; and (d) means for generating, forming a part of said digital computer, a set of isofacets for each value-step identified by said means for identifying.

Claim 27

Apparatus as set forth in claim 21 wherein said means for identifying is coupled to said storage means and utilizes predefined tetrahedron component labeling data stored in a first data set resident in said storage means.

Claim 28

A method as set forth in claim 22 wherein said means for generating is coupled to said storage means and utilizes a predefined isofacet configuration table stored in a second data set resident in said storage means.

Claim 29

Apparatus as set forth in claim 23 wherein said means for identifying further comprises means for indexing into said second data set utilizing the data stored in said first data set.

Claim 30

Apparatus as set forth in claim 24 wherein said means for generating expresses each isofacet, in the set of isofacets generated utilizing said predefined isofacet configuration table, in terms of the data stored in said first data set.

Claim 31

Apparatus as set forth in claim 21 further comprising means for displaying isosurface image data, coupled to said means for generating, utilizing the set of isofacets generated by said means for generating.

Claim 32

Apparatus as set forth in claim 26 wherein said means for displaying isosurface image data further comprises means for dynamically repositioning said isosurface image data.

Claim 33

Apparatus as set forth in claim 21 wherein said means for identifying is operative to identify, for each isofacet in a given set of isofacets, which, if any, edges of a given isofacet are colocated with the surface of said geometric volume forming a segment of a surface contour line.

Claim 34

Apparatus as said forth in claim 28 further comprising means for displaying surface contour line image data, coupled to said means for identifying, utilizing the isofacet edges identified as being colocated with the surface of said geometric volume by said means for identifying.

Claim 35

Apparatus for generating isosurfaces utilizing a digital computer and associated storage means, wherein (1) a geometric volume represented by volume element data including a set of points in three-dimensional space together with connectivity data defining a set of volume elements which subdivide said geometric volume, and (2) a scalar field associated with said set of points, wherein a single scalar value within a range is associated with each point in said set of points, are stored in said storage means, comprising: (a) a value-step sequence generator, coupled to said storage means and forming a part of said digital computer, for determining the range of the scalar values stored in said storage means and for subdividing said range into a predefined number of equally spaced value-steps forming a value-step sequence; and (b) means for determining, forming a part of said digital computer, the isofacets contained within each volume element as a function of a predefined number of equally spaced value-steps, forming a value-step sequence, into which the range of said scalar field is divided.

Claim 36

Apparatus for generating isosurfaces utilizing a digital computer and associated storage means, wherein (1) a geometric volume represented by volume element data including a set of points in three-dimensional space together with connectivity data defining a set of volume elements which subdivide said geometric volume, and (2) a scalar field associated with said set of points, wherein a single scalar value within a range is associated with each point in said set of points, are stored in said storage means, comprising: (a) a value-step sequence generator, coupled to said storage means and forming a part of said digital computer, for determining the range of the scalar values stored in said storage means and for subdividing said range into a predefined number of equally spaced value-steps forming a value-step sequence; and (b) means for determining, forming a part of said digital computer, the isofacets contained within each volume element as a function of a predefined number of equally spaced value-steps, forming a value-step sequence, into which the range of said scalar field is divided.

Claim 37

Apparatus as set forth in claim 30 wherein said means for determining further comprises means for generating the set of isofacets determined by said means for determining utilizing a predefined isofacet configuration table.

Claim 38

Apparatus as set forth in claim 31 wherein said means for determining is operative to subdivide each volume element into a tetraset.

Claim 39

Apparatus for generating isosurfaces utilizing a plurality of parallel processors and storage means associated with said parallel processors, wherein (1) a geometric volume represented by volume element data including a set of points in three-dimensional space together with connectivity data defining a set of volume elements which subdivide said geometric volume, and (2) a scalar field associated with said set of points, wherein a single scalar value within a range is associated with each point in said set of points, are stored in said storage means, comprising: (a) means for subdividing, coupled to said storage means, each volume element represented by the volume element data stored in said storage means, into a tetraset of linear tetrahedral subelements having triangular faces in such a way that the triangular faces of a given one of the tetrahedral subelements that are subdivisions of a face of a first volume element align with the faces of a given one of the tetrahedral subelements of a second volume element sharing the face of the first volume element; (b) a value-step sequence generator, coupled to said storage means, for determining the range of the scalar values stored in said storage means and for subdividing said range into a predefined number of equally spaced value-steps forming a value-step sequence; (c) means for identifying, including said plurality of parallel processors, for each volume element and for each member of the tetraset associated with a given volume element, which, if any, value-steps are contained within each tetraset member; and (d) means for assigning each member tetrahedral element from a given tetraset, whenever a plurality of such member tetrahedral elements exists, to separate ones of said plurality of parallel processors to determine the isofacets for each value-step identified by said means for identifying.

Claim 40

Apparatus for generating isosurfaces utilizing a plurality of parallel processors and storage means associated with said parallel processors, wherein (1) a geometric volume represented by volume element data including a set of points in three-dimensional space together with connectivity data defining a set of volume elements which subdivide said geometric volume, and (2) a scalar field associated with said set of points, wherein a single scalar value within a range is associated with each point in said set of points, are stored in said storage means, comprising: (a) means for subdividing, coupled to said storage means, each volume element represented by the volume element data stored in said storage means, into a tetraset of linear tetrahedral subelements having triangular faces in such a way that the triangular faces of a given one of the tetrahedral subelements that are subdivisions of a face of a first volume element align with the faces of a given one of the tetrahedral subelements of a second volume element sharing the face of the first volume element; (b) a value-step sequence generator, coupled to said storage means, for determining the range of the scalar values stored in said storage means and for subdividing said range into a predefined number of equally spaced value-steps forming a value-step sequence; (c) means for identifying, including said plurality of parallel processors, for each volume element and for each member of the tetraset associated with a given volume element, which, if any, value-steps are contained within each tetraset member; and (d) means for assigning each member tetrahedral element from a given tetraset, whenever a plurality of such member tetrahedral elements exists, to separate ones of said plurality of parallel processors to determine the isofacets for each value-step identified by said means for identifying.

Claim 41

Apparatus as set forth in claim 33 further comprising means for assigning each of a plurality of value-steps identified as being contained within a given member tetrahedral element in a given tetraset, whenever such a plurality of value-steps exists, to separate ones of said plurality of parallel processors to determine the isofacets for each value-step identified by said means for identifying.

Claim 42

Apparatus for generating isosurfaces utilizing a plurality of parallel processors and storage means associated with said parallel processors, wherein (1) a geometric volume represented by volume element data including a set of points in three-dimensional space together with connectivity data defining a set of volume elements which subdivide said geometric volume, and (2) a scalar field associated with said set of points, wherein a single scalar value within a range is associated with each point in said set of points, are stored in said storage means, comprising: (a) means for subdividing, coupled to said storage means, each volume element represented by the volume element data stored in said storage means, into a tetraset of linear tetrahedral subelements having triangular faces in such a way that the triangular faces of a given one of the tetrahedral subelements that are subdivisions of a face of a first volume element align with the faces of a given one of the tetrahedral subelements of a second volume element sharing the face of the first volume element; (b) a value-step sequence generator, coupled to said storage means, for determining the range of the scalar values stored in said storage means and for subdividing said range into a predefined number of equally spaced value-steps forming a value-step sequence; (c) means for identifying, including said plurality of parallel processors, for each volume element and for each member of the tetraset associated with a given volume element, which, if any, value-steps are contained within each tetraset member; and (d) means for assigning each of a plurality of value steps identified as being contained within a given member tetrahedral element in a given tetraset, whenever such a plurality of value-steps exists, to separate ones of said plurality of parallel processors to determine the isofacets for each value-step identified by said means for identifying.

Claim 43

Apparatus for generating isosurfaces utilizing a plurality of parallel processors and storage means associated with said parallel processors, wherein (1) a geometric volume represented by volume element data including a set of points in three-dimensional space together with connectivity data defining a set of volume elements which subdivide said geometric volume, and (2) a scalar field associated with said set of points, wherein a single scalar value within a range is associated with each point in said set of points, are stored in said storage means, comprising: (a) means for subdividing, coupled to said storage means, each volume element represented by the volume element data stored in said storage means, into a tetraset of linear tetrahedral subelements having triangular faces in such a way that the triangular faces of a given one of the tetrahedral subelements that are subdivisions of a face of a first volume element align with the faces of a given one of the tetrahedral subelements of a second volume element sharing the face of the first volume element; (b) a value-step sequence generator, coupled to said storage means, for determining the range of the scalar values stored in said storage means and for subdividing said range into a predefined number of equally spaced value-steps forming a value-step sequence; (c) means for identifying, including said plurality of parallel processors, for each volume element and for each member of the tetraset associated with a given volume element, which, if any, value-steps are contained within each tetraset member; and (d) means for assigning each of a plurality of value steps identified as being contained within a given member tetrahedral element in a given tetraset, whenever such a plurality of value-steps exists, to separate ones of said plurality of parallel processors to determine the isofacets for each value-step identified by said means for identifying.