incorrect line rendering

Michal Bozon Michal.Bozon at
Sat Oct 13 13:11:27 PDT 2007


I have noticed that arcs and lines in certain angles are rendered ugly in X11. They are not the same as would be the result of the Bresenham's rasterization algorithm.

For example, look at the image at

The first window has drawn the line close to 45deg angle rendered with in Xorg/linux (xorg<-tk<-tkinter<-python). In the second one, there is the same line rendered in MS operating system. The latter looks much nicer, and it is the the correct result of Bresenham's algorithm. I was looking into xorg sources, and there seem to be the same algorithm used (at least when looking to the comments)..

I wonder why the result is as is.. is it a bug or intention ?
Is there a chance the drawing algorithm will be fixed, or eventually, if someone provides the patch, is there a chance it will be accepted ?


PS: I have created a little utility, which helps interactively comparing
the lines rendered by X Windows, and the lines rendered with correct
Bresenham's rasterization algorihm. It's written in Python.


#! /usr/bin/env python
# 2007 Michal Bozon <michal . bozon (a) gmail . com>
# Demonstration of incorrect Xorg line rasterization algorithm

from Tkinter import Tk, Canvas, Label
from UserList import UserList

def pixel(canvas, x, y):
    """simulate a pixel by the line
    (tk canvas cannot do single pixel ?)"""
    return canvas.create_line(x-1, y, x, y)

class Line:
    """Normal line wrapper"""
    def __init__(self, canvas, x0, y0, x1, y1):
        self.canvas = canvas
        self.line = canvas.create_line(x0, y0, x1, y1)
    def delete(self):

class BresenhamLine:
    """Bresenham line algorithm"""
    # taken from
    def __init__(self, canvas, x0, y0, x1, y1):
        self.canvas = canvas
        # simulate pixels by lines
        self.pixels = []
        steep = abs(y1 - y0) > abs(x1 - x0)
        if steep:
            # swap
            x0, y0 = y0, x0
            x1, y1 = y1, x1
        if x0 > x1:
            x0, x1 = x1, x0
            y0, y1 = y1, y0

        dx = x1 - x0
        dy = abs(y1 - y0)
        err = 0
        if y0 < y1:
            ystep = 1
            ystep = -1

        y = y0

        for x in range(x0, x1):
            if steep:
                X = y
                Y = x
                X = x
                Y = y
            self.pixels.append(pixel(canvas, X, Y))
            err += dy
            if (2 * err >= dx):
                y += ystep
                err -= dx

    def delete(self):
        while self.pixels:

class App:
    line_types = {'xorg': Line,
                  'Bresenham': BresenhamLine,

    def line_init(self, event):
        self.currline.x0 = event.x
        self.currline.y0 = event.y

    def line_update(self, event):
        for canv in self.canvases:
            line_class = self.line_types[canv._name.lstrip('canv_')]
            l = line_class(canv,
            canv.line = l
            # canv.update()

    def line_drop(self, event):
        for canv in self.canvases:
            canv.line = None

    def __init__(self, root):
        self.root = root
        self.canvases = []
        self.currline = UserList()
        for i in enumerate(self.line_types):
            canv = Canvas(root,
                          name='canv_' + i[1],
            canv.grid(row=0, column=i[0])
            lbl = Label(root, text=i[1])
            lbl.grid(row=1, column=i[0])

        for canv in self.canvases:
            canv.bind('<1>', self.line_init)
            canv.bind('<B1-Motion>', self.line_update)
            canv.bind('<ButtonRelease-1>', self.line_drop)

    def run(self):

w = Tk()
app = App(w)


More information about the xorg mailing list