Line Drawing algorithm (implimented but odd error)

Discussion of Common Lisp
Post Reply
Pixel_Outlaw
Posts: 43
Joined: Mon Aug 26, 2013 9:24 pm

Line Drawing algorithm (implimented but odd error)

Post by Pixel_Outlaw » Thu Nov 07, 2013 11:33 pm

I've implimented Bresenham line drawing in lisp and added an optional feature for dashed lines.
The dashed line option is used when an array of t and nil values are provided.
You must provide your own plot function, making this highly portable as it separates the algorithm from the graphics lib.

Here is the algorithm I'll post the error below:

Code: Select all

(defun draw-line-dashed(x y x2 y2 plot-function &optional pattern)
  (let* ((dx (abs (- x2 x)))
	 (dy (abs (- y2 y)))
	 (sx (if (< x x2) 1 -1))
	 (sy (if (< y y2) 1 -1))
	 (err (- dx dy))
	 (e2 nil)
	 (p-len (length pattern))
	 (p-iter 0))
    (loop

       (if (= p-iter p-len)
	   (setf p-iter 0))
       (if (> p-len 0)
	   (if (aref pattern p-iter)
	       (funcall plot-function x y))
	   (funcall plot-function x y))
       (incf p-iter)
       (and (= x x2) (= y y2) (return-from draw-line-dashed))
       (setf e2 (* 2 err))
       (when (> e2 (* -1 dy))
	 (setf err (- err dy))
	 (setf x (+ x sx)))
       (when (and (= x x2) (= y y2))
	 (if (> p-len 0)
	     (if (aref pattern p-iter)
		 (funcall plot-function x y))
	     (funcall plot-function x y))
	 (return-from draw-line-dashed))
       (when (< e2 dx) 
	 (setf err (+ err dx)) 
	 (setf y (+ y sy))))))
The problem comes when using expressions such as (random number) for both x2 and y2 at the same time along with a dash pattern.
If just the pattern is provided with x2 and y2 being both numeric constants and a dash pattern it works.

On the other hand, you can seem to be able to use (random number) on x2 and y2 without a dash pattern and it works....

For example this line will fail:
Assume *pixel-buffer* is a 2d array of 0's or 1's.

Code: Select all


(defparameter *pixel-buffer* (make-array '(480 480) :initial-element 0))

(defun plot(x y)
  (setf (aref *pixel-buffer* x y) 1))

(defparameter *dash* (make-array 4 :initial-contents '(t t nil nil)))

(dotimes (i 100)
  (draw-line-dashed 240 240 
	     (round (+ 240 (* (cos (* i .0628)) 230)))
	     (round (+ 240 (* (sin (* i .0628)) 230)))
	     #'plot *dash*))
Any help is appreciated. It is really very strange...

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Line Drawing algorithm (implimented but odd error)

Post by edgar-rft » Fri Nov 08, 2013 1:38 am

Here is what happens:

Code: Select all

(loop
  (if (= p-iter p-len)                <--- check p-iter overflow
      (setf p-iter 0))
  (if (> p-len 0)
      (if (aref pattern p-iter)       <--- no array index overflow
          (funcall plot-function x y))
      (funcall plot-function x y))
  (incf p-iter)                       <--- increment p-iter
  (and (= x x2) (= y y2) (return-from draw-line-dashed))
  (setf e2 (* 2 err))
  (when (> e2 (* -1 dy))
    (setf err (- err dy))
    (setf x (+ x sx)))
  (when (and (= x x2) (= y y2))
    (if (> p-len 0)
        (if (aref pattern p-iter)     <--- error: array index out of bounds
            (funcall plot-function x y))
            (funcall plot-function x y))
    (return-from draw-line-dashed))
  (when (< e2 dx)
    (setf err (+ err dx))
    (setf y (+ y sy))))
Here is an (incf p-iter) replacement that avoids overflow automatically:

Code: Select all

(setf p-iter (mod (1+ p-iter) p-len))
- edgar

Pixel_Outlaw
Posts: 43
Joined: Mon Aug 26, 2013 9:24 pm

Re: Line Drawing algorithm (implimented but odd error)

Post by Pixel_Outlaw » Fri Nov 08, 2013 1:09 pm

Once again you come to the rescue!
Thanks for the help Edgar it is working now.
It was a silly mistake. This is actually for the graphics viewer we were working on. It might be cool if the forum had a code snippit section since this function is not bound to any library and could be extended by the user.
I might also add an option for filled arrow ends. I didn't use your mod method because it is a costly operation compared to a second if check.

I'm now considering adding a few more functions like polygons (with stipple patterns defined by 2d arrays of t and nil values) Then you could combine the polygon function and the line function to get an arrow function (line with polygon arrow tips) I also have a spline drawing function for bezier curves which could also be paired with a polygon function to get curvy leader arrows like you see in drafting blueprints.

All in all, this working function opens up some doors.
Thank you very much for finding and spotting my error.
This was sent from my 80x24 command terminal hopefully the formatting is OK.

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Line Drawing algorithm (implimented but odd error)

Post by edgar-rft » Fri Nov 08, 2013 10:07 pm

Question: What exactly is the difference between your pattern code above and the Tk canvas dash and stipple options? Wouldn't it make sense to write a function that converts e.g. a CL bit-vector into a X bitmap string and then use the XBM pattern to draw stippled lines? Of course I don't want to stop you to explore Bresenham's graphics algorithms but why re-inventing the wheel if dashed and stippled lines are already part of the Tk canvas?

- edgar

Post Reply