Faster version of Bresenham's line drawing alg?
Blitz3D Forums/Blitz3D Programming/Faster version of Bresenham's line drawing alg?
| ||
| I found another old classic book while sorting out the loft, this time "Graphics Gems". While flicking through it i saw the Bresenham's line drawing code but in the following chapter was an "Enhanced" version said to be 3-4 times quicker than the original. I have scanned & OCR'ed the chapter and have pasted it into this post. The problem i have is that i know zero about 'C' code and while i can figure out parts of it my attempts to turn it into a Blitz3d function have failed miserably. If anyone could convert it that would be great as if it is indeed faster a lot of people might find it useful, myself included :) 1st the chapter scan Line Drawing Drawing straight lines on a raster device, such as an incremental graph plotter or frame store is an old problem. Jack Bresenham (1965) produced a simple and efficient algorithm that lent itself to hardware implementation. Bresenham’s algorithm works by keeping track of the error between the actual line and the nearest pixel. This value is called a discriminator. The method has to find the next pixel closest to the true line. Once the direction of the line is determined, all the algorithm has to do is decide between two alternative pixels at each step. To do this the discriminator is tested to find the next pixel and then (and this is the clever bit) incremented by a constant amount ready for the next test. This basic algorithm was not greatly improved in over twenty years. Many researchers became interested in line drawing, particularly the hardware manufacturers, who relied on producing faster line drawing for comparison with their competitors. Today Bresenham’s algorithm is at the heart of several fast line drawing chips. Double Speed Bresenham’s A few years ago one of my students, Xialon Wu, approached me with an exciting new line drawing algorithm. At the time his English was bad, his claims outrageous, and I was busy. Eventually Wu developed his double step algorithm with Prof. Jon Rokne and I realized what a good idea he had had (see Wu and Rokne, 1987). Like all good ideas it is very simple: instead of using a discriminator to choose the next pixel, Wu chooses the next pattern of two pixels (see Fig. 1). Since there are four distinct patterns, how does the algorithm reduce to a simple binary decision? Let us for the moment call patterns 2 and 3 one pattern, 2(3). This could be the case on a multilevel display since both patterns could be shown as one with the center pixels at half intensity to achieve a degree of anti-aliasing. It can be shown that for lines whose slope is less than 1/2 that pattern 4 does not occur; the choice is then between pattern 1 and 2(3). Similarly, for lines with slope greater than or equal to 1/2, the choice is between pattern 2(3) and pattern 4 (pattern 1 cannot occur). Simply by testing the slope outside the plotting loop the algorithm reduces to a single discriminator. To distinguish between patterns 2 and 3 also turns out to be easy, requiring one more test but using the same discriminator. In this way the algorithm does only slightly more work to produce two pixels instead of one per step, virtually doubling the speed of Bresenham’s original. (A similar, but much more complex algorithm also exists for quadruple step patterns (Bao and Rokne, 1990). Using Symmetry So impressed was I with this breakthrough that I coded the algorithm and added a small change of my own. Since lines are symmetric about the center, it makes sense to use this symmetry to plot from both ends simultaneously using half the number of steps. Wu was not pleased to see that I had doubled the speed of his algorithm overnight! It turns out that using the symmetry was not a new idea; probably Bresenham himself thought of it originally. The symmetric double step algorithm is between three and four times faster than the original Bresenham’s (see Rokne et al., 1990). The hardware manufacturers were not particularly interested in Wu’s idea. The bottleneck (currently) in line drawing is not choosing the pixels, but getting the information to the display, the pixel write operations. Wu went on to develop a similar idea for drawing conics and Jon Rokne and Paul Bao continued with the pattern idea to produce a quadruple step version of the line algorithm. Pseudo code for lines with slopes from 0 to 1/2 is set out in Fig. 2. C code for lines of any slope is given in the appendix. Figure 1. Double step pixel patterns (Wu, 1987). ooo ooo Pattern 1 xxx ooo oox Pattern 2 xxo ooo oxx Pattern 3 xoo oox oxo Pattern 4 xoo Figure 2. Pseudo-code for symmetrical double step line algorithm symwuline(a1, b1, a2, b2) int a1, b1, a2, b2; drawline from a1, b1 to a2, b2 The algorithm is described for slopes between 0 and 1/2 The C version given later is generalized to all quadrants begin dx <-- a2–a1; This may be generalized to dy <-- b2–b1; axis of greatest movement xend <-- (dx–1) / 4; pixelsLeft <-- (dx–1) mod 4; incr2 <-- 4*dy–2*dx; plot first two points setpixel(a1, b1); setpixel(a2, b2); c <-- 2*dy; incrl <-- 2*c; D <-- incrl–dx; plotting loop for i:int <-- 0, i < xend, i <-- i + 1 do a1 <-- a1 + 1; a2 <-- a2–1; if (D < 0) then begin drawPattern1Forwards; drawPattern1Backwards; D = D + incr1; end; else begin if (D < c) then begin pattern2Forwards; pattern2Backwards; end; else begin pattern3Forwards; pattern3Backwards; end; D = D + incr2; end; endloop; if pixelsLeft > 0 then begin drawTwoForwardPixels; drawTwoBackwardPixels; end; end; now the C code
/*
Symmetric Double Step Line Algorithm
by Brian Wyvill
from "Graphics Gems", Academic Press, 1990
user provides "setpixel()" function for output.
*/
#define swap(a,b) {a^=b; b^=a; a^=b;}
#define absolute(i,j,k) ( (i-j)*(k = ( (i-j)<0 ? -1 : 1)))
int
symwuline(a1, b1, a2, b2) int a1, b1, a2, b2;
{
int dx, dy, incr1, incr2, D, x, y, xend, c, pixels_left;
int x1, y1;
int sign_x, sign_y, step, reverse, i;
dx = absolute(a2, a1, sign_x);
dy = absolute(b2, b1, sign_y);
/* decide increment sign by the slope sign */
if (sign_x == sign_y)
step = 1;
else
step = -1;
if (dy > dx) { /* chooses axis of greatest movement (make dx) */
swap(a1, b1);
swap(a2, b2);
swap(dx, dy);
reverse = 1;
} else
reverse = 0;
/* note error check for dx==0 should be included here */
if (a1 > a2) { /* start from the smaller coordinate */
x = a2;
y = b2;
x1 = a1;
y1 = b1;
} else {
x = a1;
y = b1;
x1 = a2;
y1 = b2;
}
/* Note dx=n implies 0 - n or (dx+1) pixels to be set */
/* Go round loop dx/4 times then plot last 0,1,2 or 3 pixels */
/* In fact (dx-1)/4 as 2 pixels are already plotted */
xend = (dx - 1) / 4;
pixels_left = (dx - 1) % 4; /* number of pixels left over at the end */
plot(x, y, reverse);
if ( pixels_left < 0 ) return ; /* plot only one pixel for zero length vectors */
plot(x1, y1, reverse); /* plot first two points */
incr2 = 4 * dy - 2 * dx;
if (incr2 < 0) { /* slope less than 1/2 */
c = 2 * dy;
incr1 = 2 * c;
D = incr1 - dx;
for (i = 0; i < xend; i++) { /* plotting loop */
++x;
--x1;
if (D < 0) {
/* pattern 1 forwards */
plot(x, y, reverse);
plot(++x, y, reverse);
/* pattern 1 backwards */
plot(x1, y1, reverse);
plot(--x1, y1, reverse);
D += incr1;
} else {
if (D < c) {
/* pattern 2 forwards */
plot(x, y, reverse);
plot(++x, y += step, reverse);
/* pattern 2 backwards */
plot(x1, y1, reverse);
plot(--x1, y1 -= step, reverse);
} else {
/* pattern 3 forwards */
plot(x, y += step, reverse);
plot(++x, y, reverse);
/* pattern 3 backwards */
plot(x1, y1 -= step, reverse);
plot(--x1, y1, reverse);
}
D += incr2;
}
} /* end for */
/* plot last pattern */
if (pixels_left) {
if (D < 0) {
plot(++x, y, reverse); /* pattern 1 */
if (pixels_left > 1)
plot(++x, y, reverse);
if (pixels_left > 2)
plot(--x1, y1, reverse);
} else {
if (D < c) {
plot(++x, y, reverse); /* pattern 2 */
if (pixels_left > 1)
plot(++x, y += step, reverse);
if (pixels_left > 2)
plot(--x1, y1, reverse);
} else {
/* pattern 3 */
plot(++x, y += step, reverse);
if (pixels_left > 1)
plot(++x, y, reverse);
if (pixels_left > 2)
plot(--x1, y1 -= step, reverse);
}
}
} /* end if pixels_left */
}
/* end slope < 1/2 */
else { /* slope greater than 1/2 */
c = 2 * (dy - dx);
incr1 = 2 * c;
D = incr1 + dx;
for (i = 0; i < xend; i++) {
++x;
--x1;
if (D > 0) {
/* pattern 4 forwards */
plot(x, y += step, reverse);
plot(++x, y += step, reverse);
/* pattern 4 backwards */
plot(x1, y1 -= step, reverse);
plot(--x1, y1 -= step, reverse);
D += incr1;
} else {
if (D < c) {
/* pattern 2 forwards */
plot(x, y, reverse);
plot(++x, y += step, reverse);
/* pattern 2 backwards */
plot(x1, y1, reverse);
plot(--x1, y1 -= step, reverse);
} else {
/* pattern 3 forwards */
plot(x, y += step, reverse);
plot(++x, y, reverse);
/* pattern 3 backwards */
plot(x1, y1 -= step, reverse);
plot(--x1, y1, reverse);
}
D += incr2;
}
} /* end for */
/* plot last pattern */
if (pixels_left) {
if (D > 0) {
plot(++x, y += step, reverse); /* pattern 4 */
if (pixels_left > 1)
plot(++x, y += step, reverse);
if (pixels_left > 2)
plot(--x1, y1 -= step, reverse);
} else {
if (D < c) {
plot(++x, y, reverse); /* pattern 2 */
if (pixels_left > 1)
plot(++x, y += step, reverse);
if (pixels_left > 2)
plot(--x1, y1, reverse);
} else {
/* pattern 3 */
plot(++x, y += step, reverse);
if (pixels_left > 1)
plot(++x, y, reverse);
if (pixels_left > 2) {
if (D > c) /* step 3 */
plot(--x1, y1 -= step, reverse);
else /* step 2 */
plot(--x1, y1, reverse);
}
}
}
}
}
}
/* non-zero flag indicates the pixels needing swap back. */
plot(x, y, flag) int x, y, flag;
{
if (flag)
setpixel(y, x);
else
setpixel(x, y);
}
Last edited 2011 Last edited 2011 |
| ||
| Do you believe that Blitz2D-3D relies on the old algorithm and therefore this would be faster? What makes you think so? Or is this just for curiosity's sake? |
| ||
| Do you believe that Blitz2D-3D relies on the old algorithm and therefore this would be faster? What makes you think so? Or is this just for curiosity's sake? Mainly for curiosity's sake as there is a normal Bresenham's line drawing routine in the code arcs that when modified from Plot to a WritePixelFast on a locked buffer has very little speed difference to the standard inbuilt Blitz3d one. http://www.blitzbasic.com/codearcs/codearcs.php?code=2287 Last edited 2011 |
| ||
| Basically i am messing about with 2d wireframes at the moment and would like the objects to wrap round the screen, e.g imagine asteroids & the middle of the asteroid is at 300,0. I would like the top half to be drawn at the bottom of the screen with the bottom half at the top so it wraps round smoothly. So basically i have 2 choices as far as i can see, draw the lines using points which makes it easier to check/draw if the object is wrapping, or use normal Blitz lines & write some kind of routine that checks if the object is wrapping & if so split the line & continue drawing from where it left off on the other side. The 1st choice i know how to do & that is what i have done, the second choice i have no idea. So the faster i can draw the line with pixels the better. If there is another option that i am missing please let me know & i will look into it. |
| ||
| OK, after a lot of web searching to find out what +=,?, --, ++, etc do, how For....Next loops as well as If..Else worked & downloading a C compiler my crash course in C has allowed me to convert the above code into a Blitz Function. I must warn you now that the result is not pretty as it is a pure literal translation of the C code & i am in the process of seeing how it can be optimised for Blitz. How much the calls to the pplot function slow it down i am unsure but i can't see them helping the speed much. The following code includes the way i compared the speed to the Blitz line function as well the code from the archive. My results where as follows, Blitz Line = 13239ms, symline = 10006ms & bresenham line=8323ms. Considering the size of the function, all the nested IF's as well as the calls to the pplot function it amazed me that it did actually beat the Blitz Line command. BTW do not run the code with Debug Enabled as you will have a very long wait thanks to the size of the function :) Graphics 800,600,32,2 SetBuffer BackBuffer() Cls ; 1st do blitz line Delay 5000 starttime = MilliSecs() SeedRnd 1 For loop = 0 To 99 Cls For c = 0 To 10000 x1 = Rand (0,799) y1 = Rand (0,599) x2 = Rand (0,799) y2 = Rand (0,599) Line x1,y1,x2,y2 Next Flip Next Cls totaltime = MilliSecs()-starttime Text 0,0,totaltime Flip WaitKey() ; 2nd do symline Delay 5000 starttime = MilliSecs() SeedRnd 1 For loop = 0 To 99 Cls For c = 0 To 10000 x1 = Rand (0,799) y1 = Rand (0,599) x2 = Rand (0,799) y2 = Rand (0,599) symline x1,y1,x2,y2 Next Flip Next Cls totaltime = MilliSecs()-starttime Text 0,0,totaltime Flip WaitKey() ; lastly do bessenham line from code arc's Delay 5000 starttime = MilliSecs() SeedRnd 1 For loop = 0 To 99 Cls For c = 0 To 10000 x1 = Rand (0,799) y1 = Rand (0,599) x2 = Rand (0,799) y2 = Rand (0,599) bLine x1,y1,x2,y2 Next Flip Next Cls totaltime = MilliSecs()-starttime Text 0,0,totaltime Flip WaitKey() Function symline(a1%,b1%,a2%,b2%) Local dx%, dy%, incr1%, incr2%, D%, x%, y%, xend%, c%, pixels_left% Local x1%, y1% Local sign_x%, sign_y%, pstep%, reverse%, i% temp = a2-a1 ; my version of the absolute part If temp < 0 Then ; in the original c code. val1 = -1 ; it works but unsure if there Else ; is a better/easier way of doing it val1 = 1 End If val2 = temp * val1 dx=val2 sign_x = val1 temp = b2-b1 If temp < 0 Then val1 = -1 Else val1 = 1 End If val2 = temp * val1 dy=val2 sign_y = val1 If sign_x = sign_y Then pstep = 1 Else pstep = -1 End If If dy > dx Then temp = a1 : a1 = b1 : b1 = temp temp = a2 : a2 = b2 : b2 = temp temp = dx : dx = dy : dy = temp reverse = 1 Else reverse = 0 End If If a1 > a2 Then x = a2 y = b2 x1 = a1 y1 = b1 Else x = a1 y = b1 x1 = a2 y1 = b2 End If xend = (dx - 1) / 4 pixels_left = (dx - 1) Mod 4 pplot (x,y,reverse) If pixels_left < 0 Then Return pplot (x1,y1,reverse) incr2 = 4 * dy - 2 * dx If incr2 < 0 Then c = 2 * dy incr1 = 2 * c D = incr1 - dx For i = 0 To xend-1 x = x + 1 x1 = x1 - 1 If D < 0 ; pattern 1 forwards pplot (x,y,reverse) x=x+1 pplot (x,y,reverse) ; pattern 1 backwards pplot (x1,y1,reverse) x1=x1-1 pplot (x1,y1,reverse) D = D + incr1 Else If D < c Then ; pattern 2 forwards pplot (x,y,reverse) y=y+pstep x=x+1 pplot (x,y,reverse) ;to check ; pattern 2 bacwards pplot (x1,y1,reverse) y1=y1-pstep x1=x1-1 pplot (x1,y1,reverse) ; to check Else ; pattern 3 forwards y=y+pstep pplot (x,y,reverse) x=x+1 pplot (x,y,reverse) ; pattern 3 backwards y1=y1-pstep pplot (x1,y1,reverse) x1=x1-1 pplot (x1,y1,reverse) End If D = D + incr2 End If Next ; plot last pattern If pixels_left <> 0 Then If D < 0 ; pattern 1 x=x+1 pplot (x,y,reverse) If pixels_left > 1 Then x=x+1 pplot (x,y,reverse) End If If pixels_left > 2 Then x1=x1-1 pplot (x1,y1,reverse) End If Else If D < c Then ; pattern 2 x=x+1 pplot (x,y,reverse) If pixels_left > 1 Then x=x+1 y=y+pstep pplot (x,y,reverse) End If If pixels_left > 2 Then x1=x1-1 pplot (x1,y1,reverse) End If Else ; pattern 3 y=y+pstep x=x+1 pplot (x,y,reverse) If pixels_left > 1 Then x=x+1 pplot(x,y,reverse) End If If pixels_left > 2 Then y1=y1-pstep x1=x1-1 pplot (x1,y1,reverse) End If End If End If End If ; end slope < 1/2 Else ; slope > 1/2 c = 2 * (dy - dx) incr1 = 2 * c D = incr1 + dx For i = 0 To xend-1 x = x + 1 x1 = x1 - 1 If D > 0 ; pattern 4 forwards y=y+pstep pplot (x,y,reverse) y=y+pstep x=x+1 pplot (x,y,reverse) ; pattern 4 backwards y1=y1-pstep pplot (x1,y1,reverse) y1=y1-pstep x1=x1-1 pplot (x1,y1,reverse) D = D + incr1 Else If D < c Then ; pattern 2 forwards pplot (x,y,reverse) y=y+pstep x=x+1 pplot (x,y,reverse) ; pattern 2 backwards pplot (x1,y1,reverse) y1=y1-pstep x1=x1-1 pplot (x1,y1,reverse) Else ; pattern 3 forwards y=y+pstep pplot (x,y,reverse) x=x+1 pplot (x,y,reverse) ; pattern 3 backwards y1=y1-pstep pplot (x1,y1,reverse) x1=x1-1 pplot (x1,y1,reverse) End If D = D + incr2 End If Next ; plot last pattern If pixels_left <> 0 Then If D > 0 Then ; pattern 4 y=y+pstep x=x+1 pplot(x,y,reverse) If pixels_left > 1 Then y=y+pstep x=x+1 pplot (x,y,reverse) End If If pixels_left > 2 Then y1=y1-pstep x1=x1-1 pplot (x1,y1,reverse) End If Else If D < c Then ; pattern 2 x=x+1 pplot (x,y,reverse) If pixels_left > 1 Then y=y+pstep x=x+1 pplot (x,y,reverse) End If If pixels_left > 2 Then x1=x1-1 pplot(x1,y1,reverse) End If Else ; pattern 3 y=y+pstep x=x+1 pplot (x,y,reverse) If pixels_left > 1 Then x=x+1 pplot (x,y,reverse) End If If pixels_left > 2 Then If D > c Then ; step 3 y1=y1-pstep x1=x1-1 pplot (x1,y1,reverse) Else ; step 2 x1=x1-1 pplot (x1,y1,reverse) End If End If End If End If End If End If End Function Function pplot (x,y,flag) If flag = 1 Then WritePixelFast y,x,-1 Else WritePixelFast x,y,-1 End If End Function Function bLine(X1,Y1,X2,Y2) ; Code taken from the code archives ;Draws a Line of individual pixels from X1,Y1 To X2,Y2 at any angle Local Steep=Abs(Y2-Y1) > Abs(X2-X1) ;Boolean If Steep Local Temp=X1: X1=Y1: Y1=Temp ;Swap X1,Y1 Temp=X2: X2=Y2: Y2=Temp ;Swap X2,Y2 EndIf Local DeltaX=Abs(X2-X1) ;X Difference Local DeltaY=Abs(Y2-Y1) ;Y Difference Local Error=0 ;Overflow counter Local DeltaError=DeltaY ;Counter adder Local X=X1 ;Start at X1,Y1 Local Y=Y1 Local XStep Local YStep If X1<X2 Then XStep=1 Else XStep=-1 ;Direction If Y1<Y2 Then YStep=1 Else YStep=-1 ;Direction If Steep Then WritePixelFast Y,X,-1 Else WritePixelFast X,Y,-1 ;Draw While X<>X2 X=X+XStep ;Move in X Error=Error+DeltaError ;Add To counter If (Error Shl 1)>DeltaX ;Would it overflow? Y=Y+YStep ;Move in Y Error=Error-DeltaX ;Overflow/wrap the counter EndIf If Steep Then WritePixelFast Y,X,-1 Else WritePixelFast X,Y,-1 ;Draw Wend End Function |
| ||
| An excellent & informative post furbrain :) |
| ||
| An excellent & informative post furbrain :) Thank you MCP :) After a bit of tweaking (and making the source twice as large lol) i have managed to shave over 3.5 seconds off my previous symline code post by :- 1, Very slight changes to the code before it calls the drawing routines. 2, Splitting the draw routines into two functions, if 'reverse' = 1 then call that function otherwise call the other. This has allowed the WritePixelFast to be in the functions rather than having to call another function just to plot a pixel. 3, A slight change to the "Plot last pattern" part in that rather than check if >1 or >2 points left it checks if =3 then plot that pattern as well as the >1 pattern, if =2 then just plot the >1 pattern. Seeing as the only values passed to that part are either 2 or 3 (condition 1 is plotted before that test & the rest of the routine plots the 4 pixel parts). Hardly a noticable improvement in that part but no loss so it stays :) If i knew more 'C' and how to create a userlib from the code (especially how to write to a buffer from a userlib) i could see that routine being pretty swift. How much swifter (if at all) i don't know. Thats my lot, time for bed before my head hits the keyboard. Amended code follows, only the functions, not the testing code posted earlier. Function symline(a1%,b1%,a2%,b2%) Local dx%, dy%, incr1%, incr2%, D%, x%, y%, xend%, c%, pixels_left% Local x1%, y1% Local sign_x%, sign_y%, pstep%, reverse% temp = a2-a1 val1 = 1 If temp < 0 Then val1 = -1 dx=temp*val1 sign_x = val1 temp = b2-b1 val = 1 If temp < 0 Then val1 = -1 dy=temp * val1 sign_y = val1 pstep = -1 If sign_x = sign_y Then pstep = 1 reverse = 0 If dy > dx Then temp = a1 : a1 = b1 : b1 = temp temp = a2 : a2 = b2 : b2 = temp temp = dx : dx = dy : dy = temp reverse = 1 End If x = a1 y = b1 x1 = a2 y1 = b2 If a1 > a2 Then x = a2 y = b2 x1 = a1 y1 = b1 End If xend = (dx - 1) / 4 pixels_left = (dx - 1) Mod 4 If reverse = 1 Then WritePixelFast y,x,-1 Else WritePixelFast x,y,-1 End If If pixels_left < 0 Then Return incr2 = 4 * dy - 2 * dx If reverse = 1 Then WritePixelFast y1,x1,-1 plotreverse(x%,y%,x1%,y1%,dx%,dy%,xend%,pixels_left%,incr2%,pstep%) Else WritePixelFast x1,y1,-1 plotnormal(x%,y%,x1%,y1%,dx%,dy%,xend%,pixels_left%,incr2%,pstep%) End If End Function Function plotreverse(x%,y%,x1%,y1%,dx%,dy%,xend%,pixels_left%,incr2%,pstep%) If incr2 < 0 Then ; slope < 1/2 c% = 2 * dy incr1% = 2 * c D% = incr1 - dx For i% = 0 To xend-1 x = x + 1 x1 = x1 - 1 If D < 0 ; pattern 1 forwards WritePixelFast y,x,-1 x=x+1 WritePixelFast y,x,-1 ; pattern 1 backwards WritePixelFast y1,x1,-1 x1=x1-1 WritePixelFast y1,x1,-1 D = D + incr1 Else If D < c Then ; pattern 2 forwards WritePixelFast y,x,-1 y=y+pstep x=x+1 WritePixelFast y,x,-1 ;to check ; pattern 2 bacwards WritePixelFast y1,x1,-1 y1=y1-pstep x1=x1-1 WritePixelFast y1,x1,-1 ; to check Else ; pattern 3 forwards y=y+pstep WritePixelFast y,x,-1 x=x+1 WritePixelFast y,x,-1 ; pattern 3 backwards y1=y1-pstep WritePixelFast y1,x1,-1 x1=x1-1 WritePixelFast y1,x1,-1 End If D = D + incr2 End If Next ; plot last pattern If pixels_left <> 0 Then If D < 0 ; pattern 1 x=x+1 WritePixelFast y,x,-1 If pixels_left > 1 Then x=x+1 WritePixelFast y,x,-1 End If If pixels_left > 2 Then x1=x1-1 WritePixelFast y1,x1,-1 End If Else If D < c Then ; pattern 2 x=x+1 WritePixelFast y,x,-1 If pixels_left > 1 Then x=x+1 y=y+pstep WritePixelFast y,x,-1 End If If pixels_left > 2 Then x1=x1-1 WritePixelFast y1,x1,-1 End If Else ; pattern 3 y=y+pstep x=x+1 WritePixelFast y,x,-1 If pixels_left > 1 Then x=x+1 WritePixelFast y,x,-1 End If If pixels_left > 2 Then y1=y1-pstep x1=x1-1 WritePixelFast y1,x1,-1 End If End If End If End If ; end slope < 1/2 Else ; slope > 1/2 c% = 2 * (dy - dx) incr1% = 2 * c D% = incr1 + dx For i% = 0 To xend-1 x = x + 1 x1 = x1 - 1 If D > 0 ; pattern 4 forwards y=y+pstep WritePixelFast y,x,-1 y=y+pstep x=x+1 WritePixelFast y,x,-1 ; pattern 4 backwards y1=y1-pstep WritePixelFast y1,x1,-1 y1=y1-pstep x1=x1-1 WritePixelFast y1,x1,-1 D = D + incr1 Else If D < c Then ; pattern 2 forwards WritePixelFast y,x,-1 y=y+pstep x=x+1 WritePixelFast y,x,-1 ; pattern 2 backwards WritePixelFast y1,x1,-1 y1=y1-pstep x1=x1-1 WritePixelFast y1,x1,-1 Else ; pattern 3 forwards y=y+pstep WritePixelFast y,x,-1 x=x+1 WritePixelFast y,x,-1 ; pattern 3 backwards y1=y1-pstep WritePixelFast y1,x1,-1 x1=x1-1 WritePixelFast y1,x1,-1 End If D = D + incr2 End If Next ; plot last pattern If pixels_left <> 0 Then If D > 0 Then ; pattern 4 y=y+pstep x=x+1 WritePixelFast y,x,-1 If pixels_left = 3 Then y=y+pstep x=x+1 WritePixelFast y,x,-1 y1=y1-pstep x1=x1-1 WritePixelFast y1,x1,-1 End If If pixels_left = 2 Then y=y+pstep x=x+1 WritePixelFast y,x,-1 End If Else If D < c Then ; pattern 2 x=x+1 WritePixelFast y,x,-1 If pixels_left = 3 Then y=y+pstep x=x+1 WritePixelFast y,x,-1 x1=x1-1 WritePixelFast y1,x1,-1 End If If pixels_left = 2 Then y=y+pstep x=x+1 WritePixelFast y,x,-1 End If Else ; pattern 3 y=y+pstep x=x+1 WritePixelFast y,x,-1 If pixels_left = 3 Then x=x+1 WritePixelFast y,x,-1 If D > c Then ; step 3 y1=y1-pstep x1=x1-1 WritePixelFast y1,x1,-1 Else ; step 2 x1=x1-1 WritePixelFast y1,x1,-1 End If End If If pixels_left = 2 Then x=x+1 WritePixelFast y,x,-1 End If End If End If End If End If End Function Function plotnormal(x%,y%,x1%,y1%,dx%,dy%,xend%,pixels_left%,incr2%,pstep%) If incr2 < 0 Then c% = 2 * dy incr1% = 2 * c D% = incr1 - dx For i% = 0 To xend-1 x = x + 1 x1 = x1 - 1 If D < 0 ; pattern 1 forwards WritePixelFast x,y,-1 x=x+1 WritePixelFast x,y,-1 ; pattern 1 backwards WritePixelFast x1,y1,-1 x1=x1-1 WritePixelFast x1,y1,-1 D = D + incr1 Else If D < c Then ; pattern 2 forwards WritePixelFast x,y,-1 y=y+pstep x=x+1 WritePixelFast x,y,-1 ;to check ; pattern 2 bacwards WritePixelFast x1,y1,-1 y1=y1-pstep x1=x1-1 WritePixelFast x1,y1,-1 ; to check Else ; pattern 3 forwards y=y+pstep WritePixelFast x,y,-1 x=x+1 WritePixelFast x,y,-1 ; pattern 3 backwards y1=y1-pstep WritePixelFast x1,y1,-1 x1=x1-1 WritePixelFast x1,y1,-1 End If D = D + incr2 End If Next ; plot last pattern If pixels_left <> 0 Then If D < 0 ; pattern 1 x=x+1 WritePixelFast x,y,-1 If pixels_left = 3 Then x=x+1 WritePixelFast x,y,-1 x1=x1-1 WritePixelFast x1,y1,-1 End If If pixels_left = 2 Then x=x+1 WritePixelFast x,y,-1 End If Else If D < c Then ; pattern 2 x=x+1 WritePixelFast x,y,-1 If pixels_left = 3 Then x=x+1 y=y+pstep WritePixelFast x,y,-1 x1=x1-1 WritePixelFast x1,y1,-1 End If If pixels_left = 2 Then x=x+1 y=y+pstep WritePixelFast x,y,-1 End If Else ; pattern 3 y=y+pstep x=x+1 WritePixelFast x,y,-1 If pixels_left = 3 Then x=x+1 WritePixelFast x,y,-1 y1=y1-pstep x1=x1-1 WritePixelFast x1,y1,-1 End If If pixels_left = 2 Then x=x+1 WritePixelFast x,y,-1 End If End If End If End If ; end slope < 1/2 Else ; slope > 1/2 c% = 2 * (dy - dx) incr1% = 2 * c D% = incr1 + dx For i% = 0 To xend-1 x = x + 1 x1 = x1 - 1 If D > 0 ; pattern 4 forwards y=y+pstep WritePixelFast x,y,-1 y=y+pstep x=x+1 WritePixelFast x,y,-1 ; pattern 4 backwards y1=y1-pstep WritePixelFast x1,y1,-1 y1=y1-pstep x1=x1-1 WritePixelFast x1,y1,-1 D = D + incr1 Else If D < c Then ; pattern 2 forwards WritePixelFast x,y,-1 y=y+pstep x=x+1 WritePixelFast x,y,-1 ; pattern 2 backwards WritePixelFast x1,y1,-1 y1=y1-pstep x1=x1-1 WritePixelFast x1,y1,-1 Else ; pattern 3 forwards y=y+pstep WritePixelFast x,y,-1 x=x+1 WritePixelFast x,y,-1 ; pattern 3 backwards y1=y1-pstep WritePixelFast x1,y1,-1 x1=x1-1 WritePixelFast x1,y1,-1 End If D = D + incr2 End If Next ; plot last pattern If pixels_left <> 0 Then If D > 0 Then ; pattern 4 y=y+pstep x=x+1 WritePixelFast x,y,-1 If pixels_left = 3 Then y=y+pstep x=x+1 WritePixelFast x,y,-1 y1=y1-pstep x1=x1-1 WritePixelFast x1,y1,-1 End If If pixels_left = 2 Then y=y+pstep x=x+1 WritePixelFast x,y,-1 End If Else If D < c Then ; pattern 2 x=x+1 WritePixelFast x,y,-1 If pixels_left = 3 Then y=y+pstep x=x+1 WritePixelFast x,y,-1 x1=x1-1 WritePixelFast x1,y1,-1 End If If pixels_left = 2 Then y=y+pstep x=x+1 WritePixelFast x,y,-1 End If Else ; pattern 3 y=y+pstep x=x+1 WritePixelFast x,y,-1 If pixels_left = 3 Then x=x+1 WritePixelFast x,y,-1 If D > c Then ; step 3 y1=y1-pstep x1=x1-1 WritePixelFast x1,y1,-1 Else ; step 2 x1=x1-1 WritePixelFast x1,y1,-1 End If If pixels_left = 2 Then x=x+1 WritePixelFast x,y,-1 End If End If End If End If End If End If End Function |
| ||
| You don't by chance want to make a minecraft version of this do you? :P |
   |