incorrect line rendering

[Michal Bozon]

Hi,

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 http://tinyurl.com/2u2ru6

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 ?

Thanks,
  -m.

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.

--cut--

#! /usr/bin/env python
# bresenhamlines.py
# 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):
        self.canvas.delete(self.line)

class BresenhamLine:
    """Bresenham line algorithm"""
    # taken from
    # http://tide4javascript.com/?s=Bresenham
    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
        else:
            ystep = -1

        y = y0

        for x in range(x0, x1):
            if steep:
                X = y
                Y = x
            else:
                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:
            self.canvas.delete(self.pixels.pop())

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:
            try:
                canv.line.delete()
            except:
                pass
            line_class = self.line_types[canv._name.lstrip('canv_')]
            l = line_class(canv,
                           self.currline.x0,
                           self.currline.y0,
                           event.x,
                           event.y
                           )
            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],
                          width=150,
                          height=150,
                          bg="#aaaaaa")
            canv.grid(row=0, column=i[0])
            self.canvases.append(canv)
            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):
        self.root.mainloop()

w = Tk()
app = App(w)
app.run()

--cut--