Graphics / Reference / The digital line problem
The digital line problem
The digital line problem is the conversion of an ideal continuous line into a discrete set of pixels. The mathematical description alone does not uniquely determine which pixels a raster display should activate.
A mathematical line is an ideal continuous geometric object with length but no breadth. A raster graphics line is represented by a finite set of pixels on a discrete grid.
The line-drawing problem is: given a mathematical line, which pixels should be turned on to represent it?
The continuous line may pass through pixel interiors, between pixel centres, or along pixel boundaries, so the line equation by itself does not identify one unique pixel set. A separate rasterisation rule is required.
This problem underlies the conversion of geometric descriptions into raster images. Wireframe views make the role of line drawing explicit because model edges appear directly as rasterised line segments, while filled rendered scenes depend on later rasterisation stages as well.
The standard diagram for this concept shows a continuous line crossing a pixel grid before any pixels have been selected.
Builds on
Read
- Read the chapter: The digital line problem