Direct display of CSG expression by use of depth buffers

Apparatus for generating displayable information that is expressive of a three dimensional solid, comprising:

• means for expressing the solid in a Constructive Solid Geometry representation thereof so as to be comprised of one or more primitive objects;
• and
• means for repetitively evaluating a sequence of one or more primitive objects to determine a correct image of a product of the primitive objects;
• wherein
• the evaluating means includes means for projecting from points on a face of the primitive object to a reference plane, the reference plane being partitioned into a plurality of pixels, the evaluating means further including means, responsive to the operation of the projecting means, for determining a location of a pixel or pixels covered by the projection of the face and for selecting only those pixels having a consistent point, independent of an inclination of the face with respect to the reference plane, that lie within the projection from the points on the face of the primitive object, the evaluating means further including means for determining a reference depth to an initially evaluated pixel that is covered by the projection of the face, the reference depth being determined from the consistent point of the initially evaluated pixel to a point on the face that projects onto the initially evaluated pixel, and wherein the reference depth is subsequently employed by the evaluating means in determining a depth to points on the face that project onto other pixels.

Apparatus for generating displayable information that is expressive of a three dimensional solid, comprising:

• means for expressing the solid in a Constructive Solid Geometry representation thereof so as to be comprised of one or more primitive objects;
• and
• means for evaluating the one or more primitive objects to determine displayable faces thereof;
• wherein
• the evaluating means includes means for comparing a depth, relative to a reference plane, of a point on a face of the primitive object being evaluated to a depth of a first point stored within a first depth buffer means and also to a depth of a second point stored within a second depth buffer means, and wherein the comparing means makes the depth comparison using a predetermined depth tolerance value, the predetermined depth tolerance value being selected to compensate for computation-induced round-off errors that occur at least during the determination of the displayable faces and to compensate for a resolution of the first and the second depth buffer means, said predetermined depth tolerance value enabling a correct interpretation, consistent with a definition of a solid, that eliminates dangling faces and edges.

Apparatus for generating displayable information that is expressive of a three dimensional solid, comprising:

• means for expressing the solid in a Constructive Solid Geometry representation thereof so as to be comprised of one or more primitive objects;
• and
• means for evaluating the one or more primitive objects to determine displayable faces thereof;
• wherein
• the evaluating means includes first means for repetitively comparing depths of points, that lie on faces of primitive objects being evaluated, to previously determined depths and for storing depths, within a depth buffer means (Z1), of each point determined to lie on displayable faces of the primitive objects, the depth being relative to a reference plane, wherein
• the evaluating means includes second means, responsive to a termination of operation of the first means, for comparing points on front-facing faces of the primitive objects and for storing within an intensity buffer means (I1) intensities of points on the front-facing surfaces that have a depth determined to be equal to a corresponding depth stored within Z1;
• and wherein,
• the first and the second comparing means each make depth comparisons using a predetermined depth tolerance value, the predetermined depth tolerance value being selected to compensate for computation-induced round-off errors that occur at least during the determination of the displayable faces and to enable a correct interpretation, consistent with a definition of a solid, that eliminates dangling faces and edges.

A method for generating displayable information that is expressive of a three dimensional solid, comprising the steps of:

• expressing the solid in a Constructive Solid Geometry representation thereof so as to be comprised of one or more primitive objects, the one or more primitive objects each being comprised of a plurality of faces;
• repetitively evaluating a sequence of one or more primitive objects to determine a correct image of a product of the primitive objects;
• for each repetitive evaluation, incrementing a count;
• detecting a condition wherein the count indicates that a plurality of consecutive evaluations occur without causing a change in a tentative image of the product;
• and
• generating a signal for causing the step of repetitively evaluating to terminate when a number of consecutive evaluations occur that result in no change in the tentative image of the product, wherein the number is sufficient to construct the correct image of the product and is less than the square of the number of primitive objects in the product.

A method for generating displayable information that is expressive of a three dimensional solid, comprising the steps of:

• expressing the solid in a Constructive Solid Geometry representation thereof so as to be comprised of one or more primitive objects;
• and
• evaluating a sequence of one or more primitive objects to determine a correct image of a product of the primitive objects;
• wherein
• the step of evaluating includes a step of projecting from points on a face of the primitive object to a reference plane, the reference plane being partitioned into a plurality of pixels, to determine which pixel or pixels are covered by the face, the step of projecting including a step of determining that a given pixel is covered only if a consistent point of the pixel lies within the projection from the points on the face of the primitive object, the consistent point being independent of an inclination of the face with respect to the reference plane, wherein the step of evaluating includes an initial step of determining a reference depth to an initially evaluated pixel that is covered by the projection of the face, the reference depth being determined from the consistent point of the initially evaluated pixel to a point on the face that projects onto the initially evaluated pixel, and wherein the reference depth is subsequently employed in determining a depth to points on the face that project onto other pixels.

A method for generating displayable information that is expressive of a three dimensional solid, comprising the steps of:

• expressing the solid in a Constructive Solid Geometry representation thereof so as to be comprised of one or more primitive objects;
• and
• evaluating the one or more primitive objects to determine displayable faces thereof;
• wherein
• the step of evaluating includes a step of comparing a depth, relative to a reference plane, of a point on a face of the primitive object being evaluated to a depth of a first point stored within a first depth buffer means and also to a depth of a second point stored within a second depth buffer means, and wherein the step of comparing compares the depths to using a predetermined depth tolerance value, the predetermined depth tolerance value being selected to compensate for computation-induced round-off errors that occur at least during the determination of the displayable faces and to enable a correct interpretation, consistent with a definition of a solid, that eliminates dangling faces and edges.

A method for generating displayable information that is expressive of a three dimensional solid, comprising the steps of:

• expressing the solid in a Constructive Solid Geometry representation thereof so as to be comprised of one or more primitive objects;
• and
• evaluating the one or more primitive objects to determine displayable faces thereof;
• wherein
• the step of evaluating includes the steps of
• repetitively comparing depths of points on faces of primitive objects being evaluated to previously determined depths;
• storing depths, within a depth buffer means (Z1), of each point determined to lie on displayable faces of the primitive objects, the depth being relative to a reference plane;
• comparing a depth of points on front-facing faces of the primitive objects to a corresponding depth stored within Z1;
• and
• storing within an intensity buffer means (I1) intensities of points on the front-facing surfaces having a depth determined to be equal to the corresponding depth stored within Z1;
• wherein the step of repetitively comparing and the step of comparing each compare the depths using a predetermined depth tolerance value, the predetermined depth tolerance value being selected to compensate for computation-induced round-off errors that occur at least during the determination of the displayable faces and to enable a correct interpretation, consistent with a definition of a solid, that eliminates dangling faces and edges.

A method for generating displayable information for representing a solid that is expressed in a Constructive Solid Geometry representation that includes one or more primitives, the one or more primitives each being comprised of a plurality of faces, comprising the steps of:

• repetitively evaluating a sequence of one or more primitives to determine a correct image of a product of the primitives, the step of repetitively evaluating including a step of determining depths to faces of the primitives, referenced to a pixel plane, using a predetermined depth tolerance value, the predetermined depth tolerance value being selected to compensate for computation-induced round-off errors and to reduce a probability of an occurrence of a singularity in the displayable information;
• for each repetitive evaluation, incrementing a count;
• detecting a condition wherein the count indicates that a plurality of consecutive evaluations occur without causing a change in a tentative image of the product;
• and
• generating a signal for causing the step of repetitively evaluating to terminate when a number of consecutive evaluations occur that are sufficient to construct the correct image of the product, wherein the number is less than the square of the number of primitives in the product.

Apparatus for generating displayable information for representing a solid that is expressed in a Constructive Solid Geometry representation that includes one or more primitives, the one or more primitives each being comprised of a plurality of faces, comprising:

• means for repetitively evaluating a sequence of one or more primitives to determine a correct image of a product of the primitives, said means for repetitively evaluating including means for determining depths to faces of the primitives, referenced to a pixel plane, using a predetermined depth tolerance value, the predetermined depth tolerance value being selected to compensate for computation-induced round-off errors and to reduce a probability of an occurrence of a singularity in the displayable information;
• means, responsive to each repetitive evaluation, for incrementing a counter means;
• means for detecting a condition wherein said counter means indicates that a plurality of consecutive evaluations occur without causing a change in a tentative image of the product;
• and
• means for generating a signal for causing the operation of said evaluating means to terminate when a number of consecutive evaluations occur that are sufficient to construct the correct image of the product, wherein the number is less than the square of the number of primitives in the product.