Processor for the elimination of concealed faces for the synthesis of images in three dimensions

• US 4,812,988 A
• Filed: 08/29/1986
• Issued: 03/14/1989
• Est. Priority Date: 08/30/1985
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Duthuit, Olivier, Martin, Philippe, Bonnet, Thierry
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/902,372
• Time in Patent Office: 928 Days
• Field of Search: 364/518, 364/519, 364/522, 364/523, 364/520, 340/747, 340/723, 340/727
• US Class Current: 345/582
• CPC Class Codes: G06T 15/405 using Z-buffer

Abstract

A processor of images of objects described in three dimensions for determining parameters of pixels on a display screen. The processor possesses inputs for parameters of convex polygons describing the objects in a frame of visualization and determines from the parameters of the polygons the parameters of the pixels of a transformed two-dimensional image of that object. In order to eliminate concealed faces of objects displayed on the screen from a perspective view, the processor selects and stores the parameters of all the elements of the transformed image which are closest to the plane of visualization (the display screen). The image processor is noteworthy in that it serially processes, by pipeline organization, the parameters of a set of segments which constitute the intersections of the set of polygons with each line of visualization of the visual display device, a plurality of segments being processed simultaneously. The parameters of the segments being obtained by previous conversion of the parameters of the polygons. The processor comprises n blocks, each allocated to the serial processing of the pipeline type of the parameters of one of the n pixels of a line of visualization, each block comprising: a decrementor, a validation element and a basic cell which receives and stores parameters of depth and of color and determines new ones, and which then transmits color parameters to a visual display device. According to a further variant, the image processor also includes a circuit for the conversion of the parameters of polygons into parameters of segments.

Claims

1. An image processor for processing a three-dimensional representation of an object to determine two-dimensional representation parameters to permit displaying an image of the represented object on a display screen, said image processor comprising:

means for inputting a plurality of sets of parameters each set corresponding to a single polygon in a plurality of polygons which represent said three-dimensional object at a predetermined angle of observation, each set of parameters defining a set of line segments which constitute the intersection of each polygon with a plurality of planes perpendicular to a plane of visualization through each line of visualization on the display screen, the plane of visualization corresponding to the plane of the display screen and the line of visualization corresponding to a line of visual elements on the display screen; and

means for determining the parameters of a plurality of visual elements in a line of visualization comprising means for simultaneously determining the parameters of a plurality of line segments and means for serially processing each parameter in a set of parameters, said serial processing being of the pipeline type, and for selecting and storing the parameters of line segments closest to the plane of visualization.

2. An image processor according to claim 1, wherein the parameters defining each line segment are supplied to the processor in the form of coordinates of extremities XM₀, XN₀, depth and depth increments coordinates Z₀ and dZ₀, and attribute and attribute increments parameters C₀ and dC₀ relating to each segment, the parameters of segments being introduced bit by bit into the means for serial processing of the pipeline type.

3. An image processor according to claim 1, wherein the parameters defining each line segment are supplied to the processor in the form of coordinates of extremities XM₀, XN₀, depth and depth increments coordinates Z₀ and dZ₀, and attribute and attribute increments parameters C₀ and dC₀ relating to each segment, the parameters of segments being introduced by the groups of bits into the means for serial processing of the pipeline type.

4. An image processor according to claim 1, wherein the parameters of the line segments being supplied to the processor are in the form of coordinates of extremities XM₀, XN₀, depth and depth increments coordiantes Z₀ and dZ₀, and attribute and attribute increments parameters C₀ and dC₀ relating to each segment, and the means for serial processing of the pipeline type comprises n blocks each allocated to the serial processing of the parameters of one of the n visual elements of a line of visualization, the k-th block comprising (with 1≦

k≦

n);

a decrementor receiving the coordinates (XM_k-1, XN_k-1) which it decrements by one binary unit such that;

XM_k =XM_k-1 -1, XN_k =XN_k-1 -1;

a validation element which receives, respectively, the signals (SM_k, SN_k) of the results (XM_k, XN_k) supplied by the decrementor, and determines a validation signal FL_k such that FL_k =SM_k ·

SN_k (the symbol (.) designating the AND logic operation), with FL_k =1 if the image element analyzed is affected by the coordinates (XM_k, XN_k), and FL_k =0 in the opposite case; and

a basic cell;

which receives the coordinates Z_k-1, dZ_k-1, the parameters C_k-1, dC_k-1, and the signal FL_k ;

which determines, under the control of the signal FL_k =1, the coordinates Z_k, dZ_k, the parameters C_k, dC_k for the following basic cell;

which compares the coordinates Z_k-1 with old stored values Zc_k (old) and stores values Zc_k (new) such that;

Zc_k (new)=Zc_k (old) if Z_k-1 ≧

Zc_k (old) and Zc_k (new)=Z_k-1 <

Zc_k (old);

which stores the attribute paramters C_k-1 associated with the new stored values Zc_k ; and

which transmits the attributes parameters C_k-1 to an external bus.

5. An image processor according to claim 4, wherein the operation of the processor is implemented on a sequence of cycles T each comprising units of time u, generated by a clock H, so that T=a·

u (a being an integer, the length of the word), and in that the n basic cells comprise, for the k-th basic cell with 1≦

k≦

n;

an input flip-flop which validates, on the clock H the signals Z_k-1, dZ_k-1, C_k-1, dC_k-1, and a signal OE_k-1 indicating the end of the exploration of the line of visualization;

an adder which determines the coordinate Z_k such that;

space="preserve" listing-type="equation">Z.sub.k =Z.sub.k-1 +dZ.sub.k if FL.sub.k =1,

space="preserve" listing-type="equation">Z.sub.k =Z.sub.k -1 if FL.sub.k =0;

a temporary register which stores the value Z_k-1 ;

a depth register which stores the new value Zc_k allocated to each image point, such that;

space="preserve" listing-type="equation">Zc.sub.k (new)=Zc.sub.k (old) if Z.sub.k-1 ≧

Zc.sub.k (old),

space="preserve" listing-type="equation">and

space="preserve" listing-type="equation">Zc.sub.k (new)=Z.sub.k-1 if Z.sub.k-1 <

Zc.sub.k (old);

a comparator which compares the value Z_k-1 presented at the input of the adder with the refreshed values Zc_k stored in the depth register, and which supplies a comparison signal UPD_k such that;

space="preserve" listing-type="equation">UPD.sub.k =1 if Z.sub.k-1 new<

Zc.sub.k (refreshed);

a multiplexer which orients, under the control of a signal CN_k, the output of the depth register towards the comparator when CN_k =0, and the output of the temporary register towards the input of the depth register when CN_k =1;

a flip-flop which stores the comparison signal UPD_k ;

a logic AND gate which supplies the signal CN_k =FL_k ·

UPD_k ;

a further adder which determines an attribute parameter C_k such that;

space="preserve" listing-type="equation">C.sub.k =C.sub.k-1 +dC.sub.k-1 if FL.sub.k =1;

an attribute register;

a selector, controlled by the signal CN_k, which orients towards the attribute register the new value C_k-1 if Zc_k (new) is different from Zc_k (old) and causes the old value C_k-1 to circulate if Zc_k (new) is equal to Zc_k (old);

an output circuit which supplies the data C_k-1 to an output bus when all the segments of all the polygons have been examined; and

an output flip-flop which validates, on the clock H which is the inverse of the clock H, the signals Z_k, dZ_k, C_k, dC_k and OE_k supplied for the subsequent basic cell.

6. An image processor for processing a three-dimensional representation of an object to determine two-dimensional representation parameters to permit displaying an image of the represented object on a display screen, said image processor comprising:

means for inputting parameters of each polygon in a set of polygons describing a three-dimensional object;

converting means for converting the parameters of each polygon into parameters of segments which segments constitute the intersection of each polygon with a plurality of planes perpendicular to the plane of visualization through each line of visualization of the visual display device; and

means for simultaneously determining the parameters of a plurality of visual elements in a line of visualization, and serial processing means for serially processing each parameter in a set of parameters, said serial processing being of the pipeline type, and for selecting and storing the parameters of line segments closest to the plane of visualization.

7. An image processor according to claim 6, wherein the parameters of the polygons are supplied to the processor in the form of coordinates and attributes of apices and of parameters of edges of the polygons, and the converting means comprises:

an entry register for receiving the parameters of the polygons;

a circulating store;

a sequencer for controlling the reading of the data from the image store;

an adder which receives at one input the output from the entry register and at another input the output from the circulating store, said circulating store being connected to the output of the adder and having a capacity to store the parameters of the polygons intersected by the line of visualization under consideration;

a test and command circuit for controlling the sequencer and the result emerging from the adder, and for supplying command signals, when the coordinates of the extremities of the edges of the polygons have been reached, to the circulating store, to the entry register and to the sequencer;

the output of the adder supplying data comprising coordinates of extremities XM₀, XN₀, depth and depth increments coordinates Z₀ and dZ₀, attribute and attribute increments parameters C₀ and dC₀ relating to each segment, these data entering the serial processing means which comprises n blocks each allowed to the serial processing of the parameters of one of the n visual elements of a line of visualiation, the k-th block comprising (with 1≦

k≦

n);

a decrementor receiving the coordinates (XM_k-1, XN_k-1) which it decrements by one binary unit such that;

space="preserve" listing-type="equation">XM.sub.k =XM.sub.k-1 -1, XN.sub.k =XN.sub.k-1 -1;

a validation element which receives, respectively, the signs (SM_k, SN_k) of the results (XM_k, XN_k) supplied by the decrementor, and determines a validation signal FL_k such that FL_k =SM_k ·

SN_k, (the symbol (.0 designating the AND logic operation), with FL_k =1 if the image element analyzed is affected by the coordinates (XM_k, XN_k) and FL_k =0 in the opposite case; and

a basic cell;

which receives the coordinates Z_k-1, dZ_k-1, the parameters C_k-1, dC_k-1, and the signal FL_k ;

which determines, under the control of the signal FL_k =1, the coordinates Z_k, C_k, and the parameters dZ_k, dC_k for the following basic cell;

which compares the coordinates Z_k-1 with old stored values Zc_k (old) and stores values Zc_k (new) such that;

space="preserve" listing-type="equation">Zc.sub.k (new)=Zc.sub.k (old) if Z.sub.k-1 ≧

Zc.sub.k (old),

space="preserve" listing-type="equation">and

space="preserve" listing-type="equation">Zc.sub.k (new)=Z.sub.k-1 if Z.sub.k-1 <

Zc.sub.k (old);

which stores the attributes parameters C_k-1 associated with the new stored values Zc_k ; and

which transmits the attributes parameters C_k-1 to an external bus.

8. An image processor according to claim 7, wherein the sequencer comprises:

an address register containing the addresses for addressing to the image store the polygons in the course of processing, said address register being controlled by the test and command circuit;

an entry stack controlled by the test and command circuit for storing the addresses of the parameters of the polygons to be input;

an adder incrementing the address supplied by the output of the address register and supplying incremented addresses to address the image store, these incremented addresses being reintroduced at the input of a multiplexer which selects these incremented addresses or new addresses contained in the entry stack, under the control of the test and command circuit, in order to replace by a new polygon a polygon which has ceased to be intersected by the perpendicular plane through the line of visualization under consideration.

9. An image processor according to claim 8, wherein the operation of the processor is implemented on a sequence of cycles T each comprising units of time u, generated by a clock H, so that T=a·

u (a being an integer, the length of the word), and in that the n basic cells comprise, for the k-th basic cell with 1≦

k≦

n;

an input flip-flop which validates, on the clock H the signals Z_k-1, dZ_k-1, C_k-1, dC_k-1, and a signal OE_k-1 indicating the end of the exploration of the line of visualization;

an adder which determines the coordinate Z_k such that;

space="preserve" listing-type="equation">Z.sub.k =Z.sub.k-1 +dZ.sub.k if FL.sub.k =1,

space="preserve" listing-type="equation">Z.sub.k =k-1 if FL.sub.k =0;

a temporary register which stores the value Z_k-1;

a depth register which stores the new value Zc_k allocated to each image point, such that Zc_k (new)=Zc_k (old) if Z_k-1 ≧

Zc_k (old) and Zc_k (new)=Z_k-1 if Z_k-1 <

Zc_k (old);

a comparator which compares the value Z_k-1 presented at the input of the adder with the refreshed values Zc_k stored in the depth register, and which supplies a comparison signal UPD_k such that;

space="preserve" listing-type="equation">UPD.sub.k =1 if Z.sub.k-1 new<

Zc.sub.k (refreshed);

a multiplexer unter the control of a signal CN_k which directs the output of the depth register to the comparator when CN_k =0, and the output of the temporary register to the input of the depth register when CN_k =1;

a flip-flop which stores the comparison signal UPD_k ;

a logic AND gate which supplies the signal CN_k =FL_k ·

UPD_k ;

a further adder which determines an attribute parameter C_k such that;

space="preserve" listing-type="equation">C.sub.k =C.sub.k-1 +dC.sub.k-1 if FL.sub.k =1;

an attribute register;

a selector, controlled by the signal CN_k, which directs to the attribute register the new value C_k-1 if Zc_k (new) is different from Zc_k (old) and causes the old value C_k-1 to circulate if Zc_k (new) is equal to Zc_k (old);

an output circuit which supplies the data C_k-1, to an output bus when all the segments of all the polygons have been examined; and

an output flip-flop which validates, on the clock H which is the inverse of the clock H, the signals Z_k, dZ_k, C_k, dC_k and OE_k supplied for the subsequent basic cell.

10. An image processor according to claim 7, wherein the operation of the processor is implemented on a sequence of cycles T each comprising units of time u, generated by a clock H, so that T=a·

u (a being an integer, the length of the word), and in that the n basic cells comprise, for the k-th basic cell with 1≦

k≦

n;

an input flip-flop which validates, on the clock H the signals Z_k-1, dZ_k-1, C_k-1, dC_k-1, and a signal OE_k-1 indicating the end of the exploration of the line of visualization;

an adder which determines the coordinate Z_k such that;

space="preserve" listing-type="equation">Z.sub.k =Z.sub.k-1 +dZ.sub.k if FL.sub.k =1,

space="preserve" listing-type="equation">Z.sub.k =Z.sub.k-1 if FL.sub.k =0;

a temporary register which stores the value Z_k-1

a depth register which stores the new value Zc_k allocated to each image point, such that Zc_k (new)=Zc_k (old) if Z_k-1 ≧

Zc_k (old) and Zc_k (new)=Z_k-1 if Z_k-1 <

Zc_k (old);

a comparator which compares the value Z_k-1 presented at the input of the adder with the refreshed values Zc_k stored in the depth register, and which supplies a comparison signal UPD_k such that;

space="preserve" listing-type="equation">UPD.sub.k =1 if Z.sub.k-1 (new)<

Zc.sub.k (refreshed);

a multiplexer under the control of a signal CN_k which directs the output of the depth register to the comparator when CN_k =0, and the output of the temporary register to the input of the depth register when CN_k =1;

a flip-flop- which stores the comparison signal UPD_k ;

a logic AND gate which supplies the signal CN_k =FL_k ·

UPD_k ;

a further adder which determines an attribute parameter C_k such that;

space="preserve" listing-type="equation">C.sub.k =C.sub.k-1 +dC.sub.k-1 if FL.sub.k =1;

an attribute register;

a selector, controlled by the signal CN_k, which directs to the attribute register the new value C_k-1 if Zc_k (new) is different from Zc_k (old) and causes the old value C_k-1 to circulate if Zc_k (new) is equal to Zc_k (old);

an output circuit which supplies the data C_k-1 to an output bus when all the segments of all the polygons have been examined; and

an output flip-flop which validates, on the clock H which is the inverse of the clock H, the signals Z_k, dZ_k, c_k, dC_k and OE_k supplied for the subsequent basic cell.

11. A circuit for the conversion of parameters of polygons into parameters of segments for a processor of images of objects described in three dimensions, the conversion circuit comprising:

an entry register for receiving the parameter of m polygons Pm supplied to the image processor in the form of coordinates and attributes of apices and of parameters of edges of the polygons;

a circulating store for storing the parameters of the polygons intersected by a plane perpendicular to a plane of visualization through the line of visualization under consideration;

a first adder for receiving at one input the output from the entry register and at another input the output from the circulating store, the circulating store having its input connected to the output of the adder; and

a sequencer for controlling the reading of the parameters of the m polygons Pm from the image store, comprising;

an address register containing the addresses for addressing the polygons into the image store during the course of processing;

an entry stack storing the addresses of the parameters of the polygons to be input;

a second adder for incrementing the address supplied by the output of the address register and supplying incremented addresses, some of which serve for addressing the image store;

a multiplexer having an input for receiving said incremented addresses and which selects these imcremented addresses or new addresses contained in the entry stack in order to replace by a new polygon a polygon which has ceased to be intersected by the perpendicular plane through the line of visualization under consideration; and

a test and command circuit for controlling the sequencer and the result emanating from the adder, and for supplying command signals, when the coordinates of the extremities of the edges have been reached, to the circulating store, to the entry register and to the sequencer.

12. A method for determining the parameters of visual elements on a display screen for a transformed image of an object, comprising:

supplying the parameters of a set of polygons representing an object;

converting the parameters of the polygons into a set of segments constituted by the intersections of the set of polygons with a pluraity of planes perpendicular to the plane of visualization of the display device each through a line of visualization of the display device;

supplying the segments to a serial processing means for serial processing of a plurality of segments, the serial processing means having n blocks corresponding to n visual elements of a line of visualization of a display device and being of the pipeline type, the segments being supplied to the serial processing means in the form of coordinates of extremities XM₀, XN₀, depth and depth increments coordinates Z₀ and dZ₀, and attribute and attribute increments parameters C₀ and dC₀ relating to each segment;

operating the serial processing means on a sequence of periods of base T, each comprising units of time u, generated by a clock, such that T=a·

u (where a is an integer, the length of the word);

for each block k (with 1≦

k≦

n) of said n blocks of said serial processing means;

initializing the content of two stores MT and MP with the maximum values ZT and Zc_k which they can contain;

inputting successively the coordinates XM_k-1, XN_k-1 of the extremities of a set of segments in series into a decrementor which subtracts from each unit of time u a binary unit at the coordinate XM_k-1 and at the coordinate XN_k-1 of each segment;

storing the signs of the results SM_k, SN_k of the coordinates XM_k, XN_k obtained after these decrementations are stored;

determining a signal FL_k =SM_k ·

SN_k ;

when the signal FL_k =1, inputting the depth coordinate and increment Z_k-1 and dZ_k-1 and the attribute parameter and increment C_k-1 and dC_k-1 into a basic cell of the block which determines a value Z_k and a value C_k such that;

##EQU10## loading into the store MT the value Z_k-1 in order that ZT=Z_k-1 ;

commencing with the least significant bit, for each unit of time u, comparing each binary element of the value Z_k-1 with each binary element of the value Zc_k contained in the store MP, and generating a comparison signals UPD_k such that UPD_k =1 if Z_k-1 <

Zc_k, and determining a signal CN_k =FL_k ·

UPD_k ;

when CN_k =1, replacing the value Zc_k by the value ZT=Z_k-1 in the courese of the period T, and inputting the value C_k-1 into an attribute register,

when CN_k =0, circulating the data Zc_k from the output of the store MP to the input of the same store during a cycle of duration T;

simultaneously carrying out these same steps for the n successive blocks in such a manner that a given block k receives its data from the preceding block (k-1) and transmits them to the subsequent block (k+1), each block effecting at a given instant, according to a pipeline procedure;

the determination of the values XM₀, XN₀ during cycle T_r ;

the determination and storage of the data Z relating to previous cycle T_r-1 ;

the determination and the storage of the data C relating to preceding cycle T_r-2 ; and

updating of the Z value refreshed; and

when all the segments have been completely explored, applying all the data Ck emerging from the k blocks to an output bus over a certain number of cycles T determined by the number of segments included in the line of visualization under consideration.