Method and apparatus for sorting line segments for display and manipulation by a computer system

Claim 2

A sorting circuit for a graphics output system comprising means for presenting information regarding the position of a pixel of a first line segment on a particular scan line, means for presenting information regarding the position of a pixel of a second line segment on the same particular scan line, means for selecting from a scan line one pixel from each of the first and second line segments, means for comparing the positions of selected pixels to determine which pixel is further to one extreme on the scan line than the other, and means for comparing a pixel found to have an extreme position with a pixel found in an earlier comparison to have an extreme position to determine which pixel has the more extreme position.

Claim 3

A sorting circuit for a graphics output system as claimed in claim 1 further comprising means for disabling a comparison of pixels until a pixel lies within a selected window.

Claim 4

A sorting circuit for a graphics output system as claimed in claim 1 further comprising means for substituting a clip window value for a pixel from a line segment.

Claim 5

A sorting circuit for a graphics output system as claimed in claim 1 further comprising means for selecting the order in which pixels are selected from scan lines.

Claim 6

A sorting circuit for a graphics output system as claimed in claim 4 in which the order depends on the slope of each of the line segments.

Claim 7

A sorting circuit for a graphics output system as claimed in claim 4 in which the means for selecting the order in which pixels are selected from scan lines further comprises means for determining when pixels from a next scan line are to be compared.

Claim 8

A sorting circuit for a graphics output system as claimed in claim 1 further comprising means for selecting the order in which pixels are selected from any individual scan line.

Claim 9

A sorting circuit for a graphics output system as claimed in claim 7 in which the order depends on the slope of each of the line segments.

Claim 10

In a computer graphics system in which information defining graphic images to be presented on an output display is available on a scan line basis for a pair of line segments subtending a portion of an image to be presented, the information including the slope of each line segment and the X positions of both line segments on each scan line, each scan line having a first end and a second end, a circuit comprising: two comparator subportions, each of the comparator subportions adapted to process information regarding one of said line segments subtending a portion of the image to be presented; means for receiving first signals representing first X positions of both said line segments to be processed for one scan line; means for comparing said first signals to determine the relative positions to each other of said first X positions on the scan line; means for selecting the X positions of the first end of the scan line based on the determination of said relative positions of said first X positions and the slope of each line segment; means for receiving second signals representing second X positions of both line segments to be processed for the same scan line; means for comparing said second signals to determine the relative positions to each other of said second X positions on the scan line; means for selecting the X position of the second end of the scan line based on the determination of said relative positions of said second X positions and the slope of each line segment; means for receiving signals indicative of the X positions of a clip window in which the portion of the image is to appear; and means for comparing said signals indicative of the X positions of a clip window to said first signals and said second signals.

Claim 11

In a computer graphics system in which information defining graphic images to be presented on an output display is available on a scan line basis for a pair of line segments subtending a portion of an image to be presented, the information including the slope of each line segment and the X positions of both line segments on each scan line, each scan line having a first end and a second end, a circuit comprising: two comparator subportions, each of the comparator subportions adapted to process information regarding one of said line segments subtending a portion of the image to be presented; means for receiving first signals representing first X positions of both said line segments to be processed for one scan line; means for comparing said first signals to determine the relative positions to each other of said first X positions on the scan line; means for selecting the X positions of the first end of the scan line based on the determination of said relative positions of said first X positions and the slope of each line segment; means for receiving second signals representing second X positions of both line segments to be processed for the same scan line; means for comparing said second signals to determine the relative positions to each other of said second X positions on the scan line; means for selecting the X position of the second end of the scan line based on the determination of said relative positions of said second X positions and the slope of each line segment; means for receiving signals indicative of the X positions of a clip window in which the portion of the image is to appear; and means for comparing said signals indicative of the X positions of a clip window to said first signals and said second signals.

Claim 12

In a computer graphics system as claimed in claim 9, the means for receiving said first signals and said second signals comprising multiplexor circuitry.

Claim 13

In a computer graphics system as claimed in claim 9, the means for receiving said first signals and said second signals further comprising means for receiving signals representing clip window edges.

Claim 14

In a computer graphics system as claimed in claim 11, the means for receiving said first signals and said second signals comprising multiplexor circuitry.

Claim 15

In a computer graphics system as claimed in claim 9, each of the comparator subportions further comprising means for substituting said signals indicative of the X positions of a clip window for said first signals and said second signals.

Claim 16

In a computer graphics system as claimed in claim 9, each of the comparator subportions further comprising means for selecting the order in which said first signals and said second signals are selected from scan lines.

Claim 17

In a computer graphics system as claimed in claim 14, the order selected by the means for selecting the order in which said first signals and said second signals are selected from scan lines depends on the slope of each of the line segments.

Claim 18

In a computer graphics system as claimed in claim 14 the means for selecting the order in which said first signals and said second signals are selected from scan lines further comprises means for determining when first signals and second signals from a next scan line are to be compared.

Claim 19

In a computer graphics system in which information defining graphic images to be presented on an output display is available on a scan line basis for a pair of line segments subtending a portion of an image to be presented, the information including the slope of each line segment and the X positions of both line segments on each scan line, each scan line having a first end and a second end, a circuit comprising: two comparator subportions, each of the comparator subportions adapted to process information regarding one of said line segments subtending a portion of the image to be presented; means for receiving first signals representing first X positions of both of said line segments to be processed for one scan line; means for comparing said first signals to determine the relative positions to each other of said first X positions on the scan line; first storage means for storing each of said first signals based on said relative positions of said first X positions and the slope of each line segment; means for receiving second signals representing second X positions of both of the line segments to be processed for the same scan line; means for comparing said second signals to determine the relative positions to each other of said second X positions on the scan line; second storage means for storing each of said second signals based on the determination of said relative positions of said second X positions and the slope of each line segment; means for comparing said second signals and the stored one of said first signals to select an X position for said first end of said scan line; means for comparing said first signals and the stored one of said second signals to select an X position for said second end of said scan line; means for receiving signals indicative of the X positions of a clip window in which the portion of the image is to appear; and means for comparing said signals indicative of the X positions of a clip window to said first signals and said second signals.

Claim 20

In a computer graphics system in which information defining graphic images to be presented on an output display is available on a scan line basis for a pair of line segments subtending a portion of an image to be presented, the information including the slope of each line segment and the X positions of both line segments on each scan line, each scan line having a first end and a second end, a circuit comprising: two comparator subportions, each of the comparator subportions adapted to process information regarding one of said line segments subtending a portion of the image to be presented; means for receiving first signals representing first X positions of both of said line segments to be processed for one scan line; means for comparing said first signals to determine the relative positions to each other of said first X positions on the scan line; first storage means for storing each of said first signals based on said relative positions of said first X positions and the slope of each line segment; means for receiving second signals representing second X positions of both of the line segments to be processed for the same scan line; means for comparing said second signals to determine the relative positions to each other of said second X positions on the scan line; second storage means for storing each of said second signals based on the determination of said relative positions of said second X positions and the slope of each line segment; means for comparing said second signals and the stored one of said first signals to select an X position for said first end of said scan line; means for comparing said first signals and the stored one of said second signals to select an X position for said second end of said scan line; means for receiving signals indicative of the X positions of a clip window in which the portion of the image is to appear; and means for comparing said signals indicative of the X positions of a clip window to said first signals and said second signals.

Claim 21

In a computer graphics system as claimed in claim 17, the means for receiving said first signals and said second signals comprising multiplexor circuitry.

Claim 22

In a computer graphics system as claimed in claim 17, the means for receiving said first signals and said second signals further comprising means for receiving signals representing clip window edges.

Claim 23

In a computer graphics system as claimed in claim 19, the means for receiving said first signals and said second signals comprising multiplexor circuitry.

Claim 24

In a computer graphics system as claimed in claim 17, each of the comparator subportions further comprising means for substituting said signals indicative of the X positions of a clip window for said first signals and said second signals.

Claim 25

In a computer graphics system as claimed in claim 17, each of the comparator subportions further comprising means for selecting the order in which said first signals and said second signals are selected from scan lines.

Claim 26

In a computer graphics system as claimed in claim 22, the order selected by the means for selecting the order in which said first signals and said second signals are selected from scan lines depends on the slope of each of the line segments.

Claim 27

In a computer graphics system as claimed in claim 22, the means for selecting the order in which said first signals and said second signals are selected from scan lines further comprises means for determining when first signals and second signals from a next scan line are to be compared.