Process for eliminating hidden faces for synthesis of a three-dimensional wire image

• US 5,125,074 A
• Filed: 08/10/1989
• Issued: 06/23/1992
• Est. Priority Date: 08/10/1988
• Status: Expired due to Fees

• Current Assignee: Thomson-CSF (Thales SA)
• Original Assignee: Thomson-CSF (Thales SA)
• Inventors: Pierre, Eric, Labeaute, Philippe
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Bayerl, Raymond J.
• Application Number:
  US07/391,960
• Time in Patent Office: 1,048 Days
• Field of Search: 364/522, 364/521, 340/729, 340/739, 340/723, 340/747, 395/121, 395/127, 395/143, 395/134
• US Class Current: 345/421
• CPC Class Codes: G06T 15/405 using Z-buffer

Abstract

A process for eliminating hidden faces for synthesis of a three-dimensional wire image from the set of edges of a wire image, the edges being provided with priority parameters making it possible to restore the appearances of a third-dimension. The process consists of:

cutting the set of ordinate values into intervals [Y(i),Y(i+1)] as a function of the ordinates of the edge ends;

determining, in each interval [Y(i),Y(i+1)], the coordinates of intersection points (I1 . . . I4) of the edges;

making, for each edge (AB), an arranged list of points of intersection of this edge with more priority edges;

determining, for each intersection point (I1 . . . I4), the value of an indicator indicating whether the facet of the most priority edge masks the least priority edge, starting from the intersection point considered, or masks it before the intersection point considered or else masks it before and after the intersection point;

determining, for first end (A) of each edge, the number of facets that mask this first end;

determining the segments of this edge that are visible and those that are hidden, by determining the number of facets that mask each segment, from the number of facets that mask first end (A) of the edge, and from the values of the indicators for intersection points (I1 . . . I4) of this edge (AB) with more priority edges.

Claims

1. A process for eliminating hidden faces for synthesis of a three-dimensional wire image wherein said wire image consists of facets, each facet consisting of edges each represented by the coordinates of its ends and by the value of its slope, in a Cartesian system of coordinates of two axes of coordinates, each point of an edge being provided with a priority parameter making it possible to restore the appearance of a third dimension, on a two-dimension display, said process comprising the steps of:

extracting data from a data base to determine the facets which will represent an object in wire form;

performing a geometric transformation on each of said facets to place it in a Cartesian system of coordinates which is the coordinates of the observer of the synthesis image and no longer the coordinates corresponding to the calculations made in order to provide the data base;

performing a cutting to eliminate the facets which will be outside the observer'"'"'s field of vision wherein said field of vision has the shape of a pyramid whose vertex is the observers eye;

providing a projection of said facets on a display plane by a homothetic transformation whose ratio is a function of the distance between the observer and the point to be projected on the screen and also a function of the distance between the observer and the screen;

determining intersection points of all edges by;

cutting a set of ordinate values into intervals so that each bound is the ordinate value of an edge end and so that no ordinate of an edge end is in said intervals;

determining, for each interval, the coordinates of intersection points of edges whose ordinates are in said intervals;

constituting, for each edge, a list of the intersection points of said each edge with other of said edges of higher priority wherein said list is arranged according to the position of points of intersection between a first and second edge end;

determining, for each intersection point the value of an indicator indicating if the facet of the higher priority edge masks the least priority edge, from the intersection point considered;

or masks it before the intersection point considered;

or else masks it before and after the intersection point;

each edge being scanned from a first to a second end;

determining, for a first end of each image, a number of facts which mask said first end;

determining, for each edge, the segments of said each edge which are visible and those that are hidden, by determining a number of facets that mask each segment, based on said number of facets which mask said first end of the edge, and based on the values of the indicators for said points of intersection of said each edge with most priority edges whereby the hidden parts of said facets are able to be eliminated; and

displaying on a display device the image obtained by calculating the actuating signals corresponding to each edge segment that is to be lit up on the screen.

2. A process according to claim 1, wherein determining, for each interval, the coordinates of the intersection points comprises the steps of:

determining a first list, consisting of edges, called nonhorizontal, having a single point, called a passage point, on a first ordinate line, and consisting of the first and second ends of edges, called horizontal, whose points are all located on the first ordinate line, this list being arranged as a function of the abscissas of the passage points of nonhorizontal edges, and secondarily as a function of their slope, and being arranged as a function of the ends of the horizontal edges;

deducing from this first list the existence of intersection points located on said first ordinate line;

determining the abscissas of the passage points of the nonhorizontal edges of the first list on a second ordinate line;

determining a second list consisting of all the nonhorizontal edges of the first list, and arranged as a function of the abscissas of their passage points on said second ordinate line;

comparing the order of said first list and that of said second list (L-pas(Y(i+1)), and deducing from this the existence of intersection points located between said first and second ordinate lines;

calculating the coordinates of an intersection point for each pair of edges for which an intersection has been detected.

3. A process according to claim 2, wherein deducing from said first list the existence of points of intersection between nonhorizontal edges and horizontal edges comprises the steps of:

reading said first list entirely by updating a third list which is blank at the beginning of the reading of the first list, and in which each horizontal edge is entered when a first end of this edge is read in the first list, and in which this horizontal edge is erased when a second end is read in the first list;

concluding that there is an intersection, each time that a nonhorizontal edge is read in said first list when a horizontal edge is present on the third list.

4. A process according to claim 2, wherein determining said first list of edges, for each interval comprises the steps of:

making a list of all the edges of the image, by arranging the nonhorizontal edges according to decreasing values of the ordinates of their first ends, the first end being defined as the one having the greatest ordinate, and secondarily according to their slope, when several nonhorizontal edges have first ends having the same ordinate, and by arranging the horizontal edges according to their ordinates, and secondarily according to the absicissas of their first ends, when several horizontal edges have the same ordinate;

determining said first list successively for each interval by considering the intervals in the order of decreasing first ordinates, starting from said second list determined for the interval considered just before said each interval by adding to this second list the edges which have a first ordinate end equal to said first ordinate line, and removing from it the horizontal edges and edges that have a second end having an ordinate equal to said first ordinate line.

5. A process according to claim 2, wherein the value of said indicator for each intersection point is determined as a function of:

the order of two edges having an intersection in said first list corresponding to the interval where the intersection point considered is found;

and the position of the most priority facet relative to an edge which is part of this facet and which has the intersection point considered.

6. A process according to claim 2, wherein determining the number of facets that mask the first end of each edge, successively in each interval, taken in the order of decreasing ordinates, comprises the steps of:

successively reading the edges and the ends of edges contained in said first list constituted for the current line corresponding to this interval;

updating a fourth list containing the facets able to mask an edge of the first list, the fourth list being blank at the beginning of reading of the first list, a facet being entered in the fourth list when a first nonhorizontal edge belonging to this facet is read in the first list or else when a first end of a horizontal edge belonging to this facet is read in the first list; and

this same facet then being removed from the fourth list when a second nonhorizontal edge belonging to this facet is read in the first list, or else when second end of a horizontal edge belonging to this facet is read in the first list;

comparing the priority of each edge having its first end on the current line with the priority of each facet contained in the fourth list in its state corresponding to the edge considered, and then counting the number of facets present on the fourth list and having a priority greater than that of the edge considered.

7. A process according to claim 1, wherein arranging the list of points of intersection between the first and second edge end comprises the steps of:

calculating, for each intersection point, the value of a parameter, which is proportional to the distance between the intersection point and the second end of the edge, as a function of the coordinates of the two ends of the edges having an interseciton, and as a function of their slopes;

determining the order of intersections by comparing the value of this parameter for all the intersection points of the edge; and

calculating the ordinate and abscissa of each intersection point from the value of said parameter calculated for this intersection.