Efficient stroking of vectors with arbitrary endpoints

Abstract

An improved device, of the type utilizing a display having pixels identified by a two-axis coordinate system, displays line segments referenced to the same coordinate system under control of a digital computer. The coordinate system, for example, having standard rectangular X and Y Cartesian coordinates, is configured so that each pixel lies at the intersection of a coordinate line from each of the axes. The improvement has an arrangement for determining as a major axis the axis of the coordinate system with respect to which the line moves most, and for defining the other one of the axes as the minor axis. For each major axis coordinate line crossing of the line segment, a pixel selection arrangement selects for display a pixel that both lies on the major axis coordinate line and has a minor axis coordinate that is closest to the line segment. In a further embodiment, the pixel selection arrangement includes a tie breaker for selecting for display, in accordance with a uniform rule, between two minor axis coordinates equidistant to the line segment. In a further embodiment, a second uniform rule determines whether to select a pixel for display when an end of the line segment lies exactly on the major coordinate line of a pixel. The second uniform rule selects for display one of the first and last pixels of a line segment unless the line segment is isolated and unless the line segment lies at a specified end of a series of connected segments.