Discrete Cartesian Geometry Primitives

Whether using a retained mode or an immediate mode graphics API, the programmer must specify the geometry that the API eventually draws onto a pixel buffer. A pixel buffer is a two-dimensional array of pixels. Those pixels are most naturally referenced by integer indices.

How do you represent geometry in a graphics API? Do you use DiscreteCartesianGeometryPrimitives or ContinuousCartesianGeometryPrimitives?

One or more of these applies:

The renderer will run on machines with no graphics hardware accelerator. Graphics are drawn by direct access to the pixel buffer by the CPU.
The machine has quite slow processors (e.g. PDAs, mobile phones, embedded systems, etc.) with no FPU, so integer calculations are much faster than floating point calculations. Therefore avoiding floating point calculations will reduce the amount of processing time used to render graphics.
Most geometry will not be transformed by arbitrary affine transformations.
The renderer will not antialias geometry primitives.

Simple frame-buffer graphics hardware is often used in PDAs, mobile phones, and embedded systems. Such machines usually have quite slow processors so processing power is a scarce resource. They also usually have no FPU so integer calculations are much faster than floating point calculations. Avoiding floating point calculations will therefore reduce the amount of processing time used to render graphics.

Therefore:

Represent geometry using integer values.

However, with DiscreteCartesianGeometryPrimitives, it is impossible to use sub-pixel positioning, which takes advantage of antialiasing and the display manager's SingleTransform. Therefore, DiscreteCartesianGeometryPrimitives are only really useful in a StructuredGraphics framework, but do not work well in a SceneGraph.

Applications that want to apply transformations to rendered geometry must implement the transformations themselves and then map transformed coordinates to the integer coordinates used by the API.

The pixel buffer is a 2d-array of rectangles, not a 2d-array of points. Thinking of pixels as points is a common cause of OffByOne errors. Integer coordinates actually refer to the top-left corners of the pixels in the buffer.

Original Version and Discussion

Since graphic displays are merely two-dimensional arrays of pixels, each pixel is discrete point in a Cartesian plane. Since the term "graphics" implies geometry, it's useful to have geometric primitives like Point and Rectangle.

This primitizes are commonly defined in a graphic framework. Typically, their values are integral (thus, discrete). When they are not, they are eventually transformed to a discrete geometric object.

One common problem with discrete geometry is OffByOne pixel errors everywhere. The most common example: is the rectangle (0,0,0,0) one pixel wide and high or zero pixels wide and high? Either answer is acceptable (see caveat below), but you have to choose which convention you want and stick to it.

Caveat: Actually, defining it as one pixel wide and high leads to cleaner algebra later on.

Thinking of pixels as a 2d-array of squares (as opposed to a 2d-array of points) is an insight that has proven out well over 2 decades of graphics and image processing programming. Time and time again I have seen otherwise competent electrical engineers defeated by their OffByOne errors they view as unavoidable given their point-sample view of imaging.

What about FixedPointCartesianGeometryPrimitives?

I commonly think of (integer) coordinates as referring to the mid-point of the pixel. Are there any problems (e.g. OffByOne) with that view ? -- StefanLjungstrand

Yes, you end up with the confusions that led to the original comments on this page. In a system with DiscreteCartesianGeometryPrimitives, coordinates refer to pixels, which are rectangles with width and height of unit length. Every such system (as far as the author knows) expects that a pixel coordinate refers to the top-left corner of the pixel it identifies. If you assume differently, line and shape drawing functions no longer have a clean model of execution.

Systems with ContinuousCartesianGeometryPrimitives, such as OpenGl, usually act the same. However, this causes unexpected effects when antialiasing is enabled: antialiasing causes pixels around the line to be affected. The usual solution is to set the SingleTransform to translate drawing operations so that integer coordinates are mapped to the center of a pixel.

Also see GraphicsPatterns, CandyStripeSyndrome

CategoryGraphicsPattern CategoryPattern