[CSDb] - User Forums - Subdivision line drawing method

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Subdivision line drawing method

2022-07-01 17:29

Mixer

Registered: Apr 2008
Posts: 422

Subdivision line drawing method

It is possible to draw lines by calculating mid point between coordinates recursively. It is a known method, but the Bresenham and its variants are more commonly used.

If we consider only the X coordinates of a plotted line, the point coordinates make a slope from X0 to X1 in N steps, where N is the larger of abs(x1-x0) and abs(y1-y0).

Usually these steps are calculated in ascending or descending order. The subdivision method calculates the points in a mid point tree order.

For instance:
x2=(x0+x1)/2
x3=(x0+x2)/2
x4=(x1+x2)/2
x5=(x0+x3)/2
x6=(x1+x3)/2
.
.

The new value is put to memory and used as a new coordinate to calculate midpoint to.

The point order could be:
0......1
....2...
..3.....
......4.
.
.

Here is an example Python code to demonstrate the idea.

from PIL import Image

def mid(x1,x2):
        return (x1+x2)/2

def calc_points(x0,x1,num_points):
        tab=[x0,x1,0]
        tab[2]=mid(tab[0],tab[1])
        i=2
        j=i
        while i< num_points+1:
                tab.append(mid(tab[j],tab[0]))
                tab.append(mid(tab[j],tab[1]))
                i=i+2
                j=j+1
        return tab

def draw_line(start,end,image):
        x0,x1=(start[0],end[0])
        y0,y1=(start[1],end[1])
        # line length calculation
        num_points=max(abs(x1-x0),abs(y1-y0))
        # calculate line points 
        xtab=calc_points(x0,x1,num_points)
        ytab=calc_points(y0,y1,num_points)
        # plot to image
        for i in range(num_points):
               image.putpixel((int(xtab[i]),int(ytab[i])),0)

image=Image.new("1",(320,200),"WHITE")
draw_line((40,0),(100,33),image)
image.show()

Now, one would imagine that it should be easy to implement this code on c-64 for 8 bit coordinates by unrolling something like this:

lda a 
clc
adc b
ror
sta c

Following 64tass macros will produce unrolled code, which generates the code for calculating n midpoints.

mid .macro 
	lda \1+\2
	clc
	adc \1+\3
	ror
	sta \1+\4			
.endm

calcpoints
	
j	.var 2
i	.var 0
.while i<256
	#mid tab,0,j,i
	#mid tab,1,j,i
i	.var i+1
j 	.var j+2
.next

However, this does not quite work, because the repeated subdivision calculation needs decimals, which are truncated away.

So, the challenge, if you're interested is to
a) generate shortest accurate subdivision line routine
b) generate fastest accurate subdivision line routine for c-64

Why? It might be useful or not at all.

Some uses for it are:
a) One can calculate always n points between coordinates.

b) The unrolled subdivision code may be embedded into some raster speed code.

c) If the screen memory is linear (pixel per byte sequence) one can use pixel memory addresses to calculate line points and no other address translation tables are required

d) It can calculate a ramp between any two numbers without the need to calculate slope.

2022-07-04 09:14

Monte Carlos

Registered: Jun 2004
Posts: 351

The point is that Bresenham and Midpoint results both in essentially the same formula. It's just Euler's division algorithm.

2022-07-04 09:42

Krill

Registered: Apr 2002
Posts: 2839

I don't see that this approach would have any advantages over the traditional methods.

Biggest drawback is that you're losing a lot of performance by skipping to different parts of the line all the time, so current state in registers gets overwritten rather than reused. That CLC for every pixel also doesn't bode well.

Bresenham doesn't need a preceding slope calculation either, is also chunkable into same-cycle segments for interleaving into raster code (with a cycle or two of performance loss per pixel), and can also address a linear framebuffer without further lookups.

And this algorithm would not allow for sub-pixel accuracy, and jerky inaccurate routines are one of my many pet peeves on this platform! =)

2022-07-04 11:19

Hoogo

Registered: Jun 2002
Posts: 102

It could be handy for clipping or very flat or steep lines

2022-07-04 11:42

Krill

Registered: Apr 2002
Posts: 2839

Quoting Hoogo

It could be handy for clipping or very flat or steep lines

How? :) (And clipping comes almost for free with Bresenham. Simply stop drawing whenever you go out of bounds.)

2022-07-04 13:11

Mixer

Registered: Apr 2008
Posts: 422

The method may not be practical, but it is possible. The interesting thing to me is that you can achieve that just by taking the average of two numbers repeatedly.

2022-07-04 14:41

Hoogo

Registered: Jun 2002
Posts: 102

I can see some binary search for window ranges or same coordinates there. So for long lines and clipping, this way can be better.

Also, though accuracy of 8bits can be too low for pretty lines, but at least it will hit start and end. Bresenham with 8bits and lines >256 pixels might miss one end. I don't see an application for that feature, but it might be handy sometime.

If a calculated median point and an endpoint share 1 coordinate, then you can draw a straight line. If it is worth to detect this special case in this way is a different topic...

2022-07-05 07:31

Martin Piper

Registered: Nov 2007
Posts: 634

Many years ago, in the time before hardware divides and floating point maths (so we used int/long maths) , a binary chop screen edge clipping algorithm was often considered to be a good accurate way that preserved accuracy.

2022-07-06 07:21

Oswald

Registered: Apr 2002
Posts: 5017

Rescue of Fractalus uses this aproach to draw its "fractal" lines, with a "random" offset thrown in to y.

2022-07-07 01:06

Skate

Registered: Jul 2003
Posts: 490

I remember one graphics editor was using this method on sprite overlay line drawing mode while previewing the line before you set the end point. What caught my attention was when the line got longer, it was skipping more points. Then i noticed it was using same amount of points for any line length. Without examining it any further, i got the middle point algorithm it was using. Of course when you set the end point, it was using a regular line drawing algorithm without skipping any pixels. So, gfx editors are one of the possible usage areas.

Refresh

Subscribe to this thread: