Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: FellippeHeitor on March 08, 2020, 12:03:58 pm

Title: Xiaolin Wu's antialiased line algorithm
Post by: FellippeHeitor on March 08, 2020, 12:03:58 pm
SUB lineSmooth (x0, y0, x1, y1, c AS _UNSIGNED LONG), with demo usage below.

Code: QB64: [Select]
  2. SCREEN _NEWIMAGE(800, 600, 32)
  3.  
  4. DIM m$
  7.  
  8.     'bg
  9.     LINE (0, 0)-(_WIDTH, _HEIGHT), _RGB32(166, 83, 72), BF
  10.  
  11.     'normal line
  12.     LINE (0, 0)-(_MOUSEX, _MOUSEY), _RGB32(255)
  13.     m$ = "< QB64's regular LINE"
  14.     _PRINTSTRING (_MOUSEX / 2 + 20, _MOUSEY / 2), m$
  15.  
  16.     'line with antialiasing
  17.     lineSmooth _MOUSEX, _MOUSEY, 800, 600, _RGB32(255)
  18.     m$ = "Xiaolin Wu's antialiased line >"
  19.     _PRINTSTRING ((_MOUSEX + 800) / 2 - _PRINTWIDTH(m$) - 20, (_MOUSEY + 600) / 2), m$
  20.  
  21.     _DISPLAY
  22.     _LIMIT 60
  24.  
  25. SUB lineSmooth (x0, y0, x1, y1, c AS _UNSIGNED LONG)
  26.     'translated from
  27.     'https://en.wikipedia.org/w/index.php?title=Xiaolin_Wu%27s_line_algorithm&oldid=852445548
  28.  
  29.     DIM plX AS INTEGER, plY AS INTEGER, plI
  30.  
  31.     DIM steep AS _BYTE
  32.     steep = ABS(y1 - y0) > ABS(x1 - x0)
  33.  
  34.     IF steep THEN
  35.         SWAP x0, y0
  36.         SWAP x1, y1
  37.     END IF
  38.  
  39.     IF x0 > x1 THEN
  40.         SWAP x0, x1
  41.         SWAP y0, y1
  42.     END IF
  43.  
  44.     DIM dx, dy, gradient
  45.     dx = x1 - x0
  46.     dy = y1 - y0
  47.     gradient = dy / dx
  48.  
  49.     IF dx = 0 THEN
  50.         gradient = 1
  51.     END IF
  52.  
  53.     'handle first endpoint
  54.     DIM xend, yend, xgap, xpxl1, ypxl1
  55.     xend = _ROUND(x0)
  56.     yend = y0 + gradient * (xend - x0)
  57.     xgap = (1 - ((x0 + .5) - INT(x0 + .5)))
  58.     xpxl1 = xend 'this will be used in the main loop
  59.     ypxl1 = INT(yend)
  60.     IF steep THEN
  61.         plX = ypxl1
  62.         plY = xpxl1
  63.         plI = (1 - (yend - INT(yend))) * xgap
  64.         GOSUB plot
  65.  
  66.         plX = ypxl1 + 1
  67.         plY = xpxl1
  68.         plI = (yend - INT(yend)) * xgap
  69.         GOSUB plot
  70.     ELSE
  71.         plX = xpxl1
  72.         plY = ypxl1
  73.         plI = (1 - (yend - INT(yend))) * xgap
  74.         GOSUB plot
  75.  
  76.         plX = xpxl1
  77.         plY = ypxl1 + 1
  78.         plI = (yend - INT(yend)) * xgap
  79.         GOSUB plot
  80.     END IF
  81.  
  82.     DIM intery
  83.     intery = yend + gradient 'first y-intersection for the main loop
  84.  
  85.     'handle second endpoint
  86.     DIM xpxl2, ypxl2
  87.     xend = _ROUND(x1)
  88.     yend = y1 + gradient * (xend - x1)
  89.     xgap = ((x1 + .5) - INT(x1 + .5))
  90.     xpxl2 = xend 'this will be used in the main loop
  91.     ypxl2 = INT(yend)
  92.     IF steep THEN
  93.         plX = ypxl2
  94.         plY = xpxl2
  95.         plI = (1 - (yend - INT(yend))) * xgap
  96.         GOSUB plot
  97.  
  98.         plX = ypxl2 + 1
  99.         plY = xpxl2
  100.         plI = (yend - INT(yend)) * xgap
  101.         GOSUB plot
  102.     ELSE
  103.         plX = xpxl2
  104.         plY = ypxl2
  105.         plI = (1 - (yend - INT(yend))) * xgap
  106.         GOSUB plot
  107.  
  108.         plX = xpxl2
  109.         plY = ypxl2 + 1
  110.         plI = (yend - INT(yend)) * xgap
  111.         GOSUB plot
  112.     END IF
  113.  
  114.     'main loop
  115.     DIM x
  116.     IF steep THEN
  117.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  118.             plX = INT(intery)
  119.             plY = x
  120.             plI = (1 - (intery - INT(intery)))
  121.             GOSUB plot
  122.  
  123.             plX = INT(intery) + 1
  124.             plY = x
  125.             plI = (intery - INT(intery))
  126.             GOSUB plot
  127.  
  128.             intery = intery + gradient
  129.         NEXT
  130.     ELSE
  131.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  132.             plX = x
  133.             plY = INT(intery)
  134.             plI = (1 - (intery - INT(intery)))
  135.             GOSUB plot
  136.  
  137.             plX = x
  138.             plY = INT(intery) + 1
  139.             plI = (intery - INT(intery))
  140.             GOSUB plot
  141.  
  142.             intery = intery + gradient
  143.         NEXT
  144.     END IF
  145.  
  146.     EXIT SUB
  147.  
  148.     plot:
  149.     PSET (plX, plY), _RGB32(_RED32(c), _GREEN32(c), _BLUE32(c), plI * 255)
  150.     RETURN
  152.  
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 12:27:36 pm
Ah that reminds of this:
Code: QB64: [Select]
  1. _TITLE "WuLine test, WuLine is white, QB64 line is yellow. Wu is Smoother!" 'B+ 2019-02-25
  2. SCREEN _NEWIMAGE(700, 700, 32)
  3. _SCREENMOVE 300, 20
  4.  
  5. WHILE _KEYDOWN(27) = 0
  6.     CLS
  7.     WuLine 350, 350, 350 + 340 * COS(a), 350 + 340 * SIN(a), _RGB32(255, 255, 255)
  8.     LINE (350, 350)-(350 - 340 * COS(a), 350 - 340 * SIN(a)), _RGB32(255, 255, 0)
  9.     a = a + _PI(2 / 360)
  10.     _DISPLAY
  11.     _LIMIT 5
  13.  
  14. SUB plot (x, y, c AS _UNSIGNED LONG, opaque) 'c is RGB color a level is opaqueness 0 to 1 transparent to solid
  15.     r = _RED32(c): g = _GREEN32(c): b = _BLUE32(c): o = opaque * 255
  16.     PSET (x, y), _RGBA32(r, g, b, o)
  18.  
  19. '// integer part of x
  20. FUNCTION ipart (x)
  21.     ipart = INT(x)
  23.  
  24. FUNCTION round (x)
  25.     round = ipart(x + 0.5)
  27.  
  28. '// fractional part of x
  29. FUNCTION fpart (x)
  30.     fpart = x - INT(x)
  32.  
  33. FUNCTION rfpart (x)
  34.     rfpart = 1 - fpart(x)
  36.  
  37. SUB WuLine (xx0, yy0, xx1, yy1, c AS _UNSIGNED LONG)
  38.     'make copies since swapping values
  39.  
  40.     x0 = xx0: y0 = yy0: x1 = xx1: y1 = yy1
  41.  
  42.     DIM steep AS INTEGER
  43.     steep = ABS(y1 - y0) > ABS(x1 - x0)
  44.  
  45.     IF steep = -1 THEN
  46.         SWAP x0, y0
  47.         SWAP x1, y1
  48.     END IF
  49.     IF x0 > x1 THEN
  50.         SWAP x0, x1
  51.         SWAP y0, y1
  52.     END IF
  53.  
  54.     dx = x1 - x0
  55.     dy = y1 - y0
  56.     gradient = dy / dx
  57.     IF dx = 0.0 THEN
  58.         gradient = 1.0
  59.     END IF
  60.  
  61.     '// handle first endpoint
  62.     xend = round(x0)
  63.     yend = y0 + gradient * (xend - x0)
  64.     xgap = rfpart(x0 + 0.5)
  65.     xpxl1 = xend '// this will be used in the main loop
  66.     ypxl1 = ipart(yend)
  67.     IF steep THEN
  68.         plot ypxl1, xpxl1, c, rfpart(yend) * xgap
  69.         plot ypxl1 + 1, xpxl1, c, fpart(yend) * xgap
  70.     ELSE
  71.         plot xpxl1, ypxl1, c, rfpart(yend) * xgap
  72.         plot xpxl1, ypxl1 + 1, c, fpart(yend) * xgap
  73.     END IF
  74.     intery = yend + gradient '// first y-intersection for the main loop
  75.  
  76.     '// handle second endpoint
  77.     xend = round(x1)
  78.     yend = y1 + gradient * (xend - x1)
  79.     xgap = fpart(x1 + 0.5)
  80.     xpxl2 = xend '//this will be used in the main loop
  81.     ypxl2 = ipart(yend)
  82.     IF steep THEN
  83.         plot ypxl2, xpxl2, c, rfpart(yend) * xgap
  84.         plot ypxl2 + 1, xpxl2, c, fpart(yend) * xgap
  85.     ELSE
  86.         plot xpxl2, ypxl2, c, rfpart(yend) * xgap
  87.         plot xpxl2, ypxl2 + 1, c, fpart(yend) * xgap
  88.     END IF
  89.  
  90.     '// main loop
  91.     IF steep = -1 THEN
  92.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  93.             plot ipart(intery), x, c, rfpart(intery)
  94.             plot ipart(intery) + 1, x, c, fpart(intery)
  95.             intery = intery + gradient
  96.         NEXT
  97.     ELSE
  98.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  99.             plot x, ipart(intery), c, rfpart(intery)
  100.             plot x, ipart(intery) + 1, c, fpart(intery)
  101.             intery = intery + gradient
  102.         NEXT
  103.     END IF
  105.  
  106.  

I used it in a clock and the Search engine here is not linking me to the place I just saw it.

Ah here it is:
https://www.qb64.org/forum/index.php?topic=1083.msg102983#msg102983
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: FellippeHeitor on March 08, 2020, 12:33:23 pm
Can you spot the differences between our approaches?
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 12:36:47 pm
Quote from: FellippeHeitor on March 08, 2020, 12:33:23 pm
Can you spot the differences between our approaches?

My translation is shorter ;-)) Can you just summarize I've been all over the place with library work and my brain is scattered to 4 winds.
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: FellippeHeitor on March 08, 2020, 12:37:21 pm
No :-)
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 12:37:51 pm
OK
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 12:38:45 pm
Interesting. Seems like a lot of work though to just make a line by PSET with transparency.

Code: QB64: [Select]
  1.   PSET (plX, plY), _RGB32(_RED32(c), _GREEN32(c), _BLUE32(c), plI * 255)

I might try to make something shorter and name it after myself instead. Until then, let's glorify Xiaolin Wu.

.... I'll only do it if I can generalize it to curves, how's that?
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: FellippeHeitor on March 08, 2020, 12:45:45 pm
I'm after an antialiased circle algorithm as well, will that do it?
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 12:46:42 pm
Oops I edited as you were responding so it may pass by too fast. But for the sake of not skipping a beat:

Quote
.... I'll only do it if I can generalize it to curves, how's that?

I mean *any* curve...
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: FellippeHeitor on March 08, 2020, 12:47:43 pm
I only mentioned circles *after* you made that edit.
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 12:48:53 pm
I guess what I'm after is an anti-aliased DRAW. Hm, now you've got me thinking. God I love the forums...
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 12:50:51 pm
OK in two minutes of compare I see Fell's WuLine all in one sub 126 lines, convenient!

My version has 5 supplemental subs that might be used in other places, 90 lines total.


Antialias circle great goal! I hope you have better luck than I.
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 12:53:30 pm
Hey is this from conversation at Discourse?
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: FellippeHeitor on March 08, 2020, 12:58:56 pm
We are always at Discord. *wink wink*
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 01:05:36 pm
Maybe bplus was wondering if somehow Discord was channeling its output here because we were exchanging so fast?

Not the case. Just two ninjas at work.
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 01:11:18 pm
I just had a vision how it might be done:
Forget about single "line" of points and think topological map coloring.

EDIT: It being anti-alias of circles and other curves.
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 01:16:32 pm
I may or may no work on it but here's what I told Fellippe in Discord:

Quote
should i explain it or should i just try it?
if i fail you'll never hear about it again
so this may be the only chance to explain my attempt. i have two:

attempt 1) borrow the constructions from my curve smoother, which got refined in Collisions 9, because it calculates the perpendicular vector a curve. then, along that vector, plot points with fading alpha, barely a pixel deep in each direction

attempt 2) surround the curve by a very thin membrane, mathematically speaking, and then blur everything in that membrane

technically in the infinite limit those are the same
and what i hope is it generalizes what i've seen you guys do for straight lines
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 02:04:00 pm
Try this one out. Press space to begin drawing the smoothest damn curves I've seen in QB64. Thanks Fellippe. A perfect perfect piece to add.

Code: QB64: [Select]
  1. ' Display
  2. SCREEN _NEWIMAGE(800, 600, 32)
  3. _SCREENMOVE (_DESKTOPWIDTH \ 2 - _WIDTH \ 2) - 3, (_DESKTOPHEIGHT \ 2 - _HEIGHT \ 2) - 29
  4. _TITLE "If these curves were smoother they'd steal your wife."
  6.  
  7. ' Meta
  8. start:
  12.  
  13. ' Data structures
  14. TYPE Vector
  15.     x AS DOUBLE
  16.     y AS DOUBLE
  18.  
  19. DIM SHARED vtemp AS Vector
  20.  
  21. ' Object type
  22. TYPE Object
  23.     Elements AS INTEGER
  24.     Shade AS _UNSIGNED LONG
  26.  
  27. ' Object storage
  28. DIM SHARED Shape(300) AS Object
  29. DIM SHARED PointChain(300, 500) AS Vector
  30. DIM SHARED TempChain(300, 500) AS Vector
  31. DIM SHARED ShapeCount AS INTEGER
  32. DIM SHARED SelectedShape AS INTEGER
  33.  
  34. ' Initialize
  35. ShapeCount = 0
  36.  
  37. ' Main loop
  39.     IF (UserInput = -1) THEN GOTO start
  40.     CALL Graphics
  41.     _LIMIT 120
  43.  
  45.  
  46. FUNCTION UserInput
  47.     TheReturn = 0
  48.     ' Keyboard input
  49.     kk = _KEYHIT
  50.     SELECT CASE kk
  51.         CASE 32
  52.             DO: LOOP UNTIL _KEYHIT
  53.             WHILE _MOUSEINPUT: WEND
  54.             _KEYCLEAR
  55.             CALL NewMouseShape(7.5, 150, 15)
  56.             CLS
  57.     END SELECT
  58.     IF (kk) THEN
  59.         _KEYCLEAR
  60.     END IF
  61.     UserInput = TheReturn
  63.  
  64.  
  65. SUB Graphics
  66.     LINE (0, 0)-(_WIDTH, _HEIGHT), _RGBA(0, 0, 0, 200), BF
  67.     CALL cprintstring(16 * 17, "PRESS SPACE and then drag MOUSE 1 to draw a new shape.")
  68.     FOR ShapeIndex = 1 TO ShapeCount
  69.         FOR i = 1 TO Shape(ShapeIndex).Elements - 1
  70.             CALL lineSmooth(PointChain(ShapeIndex, i).x, PointChain(ShapeIndex, i).y, PointChain(ShapeIndex, i + 1).x, PointChain(ShapeIndex, i + 1).y, Shape(ShapeIndex).Shade)
  71.         NEXT
  72.         CALL lineSmooth(PointChain(ShapeIndex, 1).x, PointChain(ShapeIndex, 1).y, PointChain(ShapeIndex, Shape(ShapeIndex).Elements).x, PointChain(ShapeIndex, Shape(ShapeIndex).Elements).y, Shape(ShapeIndex).Shade)
  73.     NEXT
  74.     _DISPLAY
  76.  
  77. SUB NewMouseShape (rawresolution AS DOUBLE, targetpoints AS INTEGER, smoothiterations AS INTEGER)
  78.     ShapeCount = ShapeCount + 1
  79.     numpoints = 0
  80.     xold = 999 ^ 999
  81.     yold = 999 ^ 999
  82.     DO
  83.         DO WHILE _MOUSEINPUT
  84.             x = _MOUSEX
  85.             y = _MOUSEY
  86.             IF (x > 0) AND (x < _WIDTH) AND (y > 0) AND (y < _HEIGHT) THEN
  87.                 IF _MOUSEBUTTON(1) THEN
  88.                     x = x - (_WIDTH / 2)
  89.                     y = -y + (_HEIGHT / 2)
  90.                     delta = SQR((x - xold) ^ 2 + (y - yold) ^ 2)
  91.                     IF (delta > rawresolution) AND (numpoints < targetpoints - 1) THEN
  92.                         numpoints = numpoints + 1
  93.                         PointChain(ShapeCount, numpoints).x = x
  94.                         PointChain(ShapeCount, numpoints).y = y
  95.                         CALL cpset(x, y, _RGB(0, 255, 255))
  96.                         xold = x
  97.                         yold = y
  98.                     END IF
  99.                 END IF
  100.             END IF
  101.         LOOP
  102.         _DISPLAY
  103.     LOOP UNTIL NOT _MOUSEBUTTON(1) AND (numpoints > 1)
  104.  
  105.     DO WHILE (numpoints < targetpoints)
  106.         rad2max = -1
  107.         kmax = -1
  108.         FOR k = 1 TO numpoints - 1
  109.             xfac = PointChain(ShapeCount, k).x - PointChain(ShapeCount, k + 1).x
  110.             yfac = PointChain(ShapeCount, k).y - PointChain(ShapeCount, k + 1).y
  111.             rad2 = xfac ^ 2 + yfac ^ 2
  112.             IF rad2 > rad2max THEN
  113.                 kmax = k
  114.                 rad2max = rad2
  115.             END IF
  116.         NEXT
  117.         edgecase = 0
  118.         xfac = PointChain(ShapeCount, numpoints).x - PointChain(ShapeCount, 1).x
  119.         yfac = PointChain(ShapeCount, numpoints).y - PointChain(ShapeCount, 1).y
  120.         rad2 = xfac ^ 2 + yfac ^ 2
  121.         IF (rad2 > rad2max) THEN
  122.             kmax = numpoints
  123.             rad2max = rad2
  124.             edgecase = 1
  125.         END IF
  126.         IF (edgecase = 0) THEN
  127.             numpoints = numpoints + 1
  128.             FOR j = numpoints TO kmax + 1 STEP -1
  129.                 PointChain(ShapeCount, j).x = PointChain(ShapeCount, j - 1).x
  130.                 PointChain(ShapeCount, j).y = PointChain(ShapeCount, j - 1).y
  131.             NEXT
  132.             PointChain(ShapeCount, kmax + 1).x = (1 / 2) * (PointChain(ShapeCount, kmax).x + PointChain(ShapeCount, kmax + 2).x)
  133.             PointChain(ShapeCount, kmax + 1).y = (1 / 2) * (PointChain(ShapeCount, kmax).y + PointChain(ShapeCount, kmax + 2).y)
  134.         ELSE
  135.             numpoints = numpoints + 1
  136.             xx = PointChain(ShapeCount, numpoints - 1).x
  137.             yy = PointChain(ShapeCount, numpoints - 1).y
  138.             PointChain(ShapeCount, numpoints).x = (1 / 2) * (PointChain(ShapeCount, 1).x + xx)
  139.             PointChain(ShapeCount, numpoints).y = (1 / 2) * (PointChain(ShapeCount, 1).y + yy)
  140.         END IF
  141.     LOOP
  142.  
  143.     FOR j = 1 TO smoothiterations
  144.         FOR k = 2 TO numpoints - 1
  145.             TempChain(ShapeCount, k).x = (1 / 2) * (PointChain(ShapeCount, k - 1).x + PointChain(ShapeCount, k + 1).x)
  146.             TempChain(ShapeCount, k).y = (1 / 2) * (PointChain(ShapeCount, k - 1).y + PointChain(ShapeCount, k + 1).y)
  147.         NEXT
  148.         FOR k = 2 TO numpoints - 1
  149.             PointChain(ShapeCount, k).x = TempChain(ShapeCount, k).x
  150.             PointChain(ShapeCount, k).y = TempChain(ShapeCount, k).y
  151.         NEXT
  152.     NEXT
  153.  
  154.     Shape(ShapeCount).Elements = numpoints
  155.     Shape(ShapeCount).Shade = _RGB(100 + INT(RND * 155), 100 + INT(RND * 155), 100 + INT(RND * 155))
  156.     SelectedShape = ShapeCount
  158.  
  159. SUB cpset (x1, y1, col AS _UNSIGNED LONG)
  160.     PSET (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col
  162.  
  163. SUB cprintstring (y, a AS STRING)
  164.     _PRINTSTRING (_WIDTH / 2 - (LEN(a) * 8) / 2, -y + _HEIGHT / 2), a
  166.  
  167. SUB lineSmooth (x0, y0, x1, y1, c AS _UNSIGNED LONG)
  168.     'translated from
  169.     'https://en.wikipedia.org/w/index.php?title=Xiaolin_Wu%27s_line_algorithm&oldid=852445548
  170.  
  171.     DIM plX AS INTEGER, plY AS INTEGER, plI
  172.  
  173.     DIM steep AS _BYTE
  174.     steep = ABS(y1 - y0) > ABS(x1 - x0)
  175.  
  176.     IF steep THEN
  177.         SWAP x0, y0
  178.         SWAP x1, y1
  179.     END IF
  180.  
  181.     IF x0 > x1 THEN
  182.         SWAP x0, x1
  183.         SWAP y0, y1
  184.     END IF
  185.  
  186.     DIM dx, dy, gradient
  187.     dx = x1 - x0
  188.     dy = y1 - y0
  189.     gradient = dy / dx
  190.  
  191.     IF dx = 0 THEN
  192.         gradient = 1
  193.     END IF
  194.  
  195.     'handle first endpoint
  196.     DIM xend, yend, xgap, xpxl1, ypxl1
  197.     xend = _ROUND(x0)
  198.     yend = y0 + gradient * (xend - x0)
  199.     xgap = (1 - ((x0 + .5) - INT(x0 + .5)))
  200.     xpxl1 = xend 'this will be used in the main loop
  201.     ypxl1 = INT(yend)
  202.     IF steep THEN
  203.         plX = ypxl1
  204.         plY = xpxl1
  205.         plI = (1 - (yend - INT(yend))) * xgap
  206.         GOSUB plot
  207.  
  208.         plX = ypxl1 + 1
  209.         plY = xpxl1
  210.         plI = (yend - INT(yend)) * xgap
  211.         GOSUB plot
  212.     ELSE
  213.         plX = xpxl1
  214.         plY = ypxl1
  215.         plI = (1 - (yend - INT(yend))) * xgap
  216.         GOSUB plot
  217.  
  218.         plX = xpxl1
  219.         plY = ypxl1 + 1
  220.         plI = (yend - INT(yend)) * xgap
  221.         GOSUB plot
  222.     END IF
  223.  
  224.     DIM intery
  225.     intery = yend + gradient 'first y-intersection for the main loop
  226.  
  227.     'handle second endpoint
  228.     DIM xpxl2, ypxl2
  229.     xend = _ROUND(x1)
  230.     yend = y1 + gradient * (xend - x1)
  231.     xgap = ((x1 + .5) - INT(x1 + .5))
  232.     xpxl2 = xend 'this will be used in the main loop
  233.     ypxl2 = INT(yend)
  234.     IF steep THEN
  235.         plX = ypxl2
  236.         plY = xpxl2
  237.         plI = (1 - (yend - INT(yend))) * xgap
  238.         GOSUB plot
  239.  
  240.         plX = ypxl2 + 1
  241.         plY = xpxl2
  242.         plI = (yend - INT(yend)) * xgap
  243.         GOSUB plot
  244.     ELSE
  245.         plX = xpxl2
  246.         plY = ypxl2
  247.         plI = (1 - (yend - INT(yend))) * xgap
  248.         GOSUB plot
  249.  
  250.         plX = xpxl2
  251.         plY = ypxl2 + 1
  252.         plI = (yend - INT(yend)) * xgap
  253.         GOSUB plot
  254.     END IF
  255.  
  256.     'main loop
  257.     DIM x
  258.     IF steep THEN
  259.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  260.             plX = INT(intery)
  261.             plY = x
  262.             plI = (1 - (intery - INT(intery)))
  263.             GOSUB plot
  264.  
  265.             plX = INT(intery) + 1
  266.             plY = x
  267.             plI = (intery - INT(intery))
  268.             GOSUB plot
  269.  
  270.             intery = intery + gradient
  271.         NEXT
  272.     ELSE
  273.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  274.             plX = x
  275.             plY = INT(intery)
  276.             plI = (1 - (intery - INT(intery)))
  277.             GOSUB plot
  278.  
  279.             plX = x
  280.             plY = INT(intery) + 1
  281.             plI = (intery - INT(intery))
  282.             GOSUB plot
  283.  
  284.             intery = intery + gradient
  285.         NEXT
  286.     END IF
  287.  
  288.     EXIT SUB
  289.  
  290.     plot:
  291.     CALL cpset(plX, plY, _RGB32(_RED32(c), _GREEN32(c), _BLUE32(c), plI * 255))
  292.     RETURN
  294.  
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 03:03:10 pm
Unless anyone finds and bugs with this ^, I'll soon swap this code in for the "curve smoother" demo we have up in Samples, adding Fellippe as a contributor.
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 03:51:06 pm
Hi STxAxTIC,

What would a circle drawing routine sub look like maybe with fill option?

Circles are often so ragged! would be nice if we could have smooth ones, how many lines of code would that cost?

Oh, come to think, PAINTing is quite a challenge with different colored edges. That might be where I got stuck.
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 03:57:49 pm
No problem bplus - so filled shapes and antialiasing have to be done in the proper order. Fill first, alias last. Otherwise, the PAINT function is seeking a gradient for a border, not a hard edge. That said though, you only need to alias the outside of the circle.

Dirty trick: Draw a filled circle just inside an aliased ring. Nope, alpha will break. Gotta just anti-alias one side of the curve.

Maybe I'll adapt the code above to handle common perfect shapes in addition to mouse shapes.
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 04:32:31 pm
 STxAxTIC, I just fugired out what you were doing with Curve smoother... Now applied directly for circles, Not bad! and far less code.
Code: QB64: [Select]
  1. CONST xmax = 1200, ymax = 700, xc = 600, yc = 350, nP = 20
  2.  
  3. _TITLE "WuLine Circles on Left, Normal circles on right, hmm.... not bad" 'B+ 2020-03-08
  4. SCREEN _NEWIMAGE(xmax, ymax, 32)
  5. _DELAY .25
  7. DIM x(nP), y(nP), r(nP), c(nP) AS _UNSIGNED LONG
  8. FOR i = 0 TO nP
  9.     x(i) = .5 * xc: y(i) = yc: r(i) = i * 300 / nP
  10.     c(i) = _RGB32(255 * RND, 255 * RND, 255 * RND)
  12.  
  13. FOR i = 0 TO nP
  14.     CIRCLE (x(i) + xc, y(i)), r(i), c(i)
  15.     FOR a = 0 TO _PI(2.1) STEP .1
  16.         'draw circles with wulines
  17.         x1 = x(i) + r(i) * COS(a)
  18.         y1 = y(i) + r(i) * SIN(a)
  19.         IF a > 0 THEN
  20.             WuLine xlast, ylast, x1, y1, c(i)
  21.         END IF
  22.         xlast = x1: ylast = y1
  23.     NEXT
  25.  
  26. SUB plot (x, y, c AS _UNSIGNED LONG, opaque) 'c is RGB color a level is opaqueness 0 to 1 transparent to solid
  27.     r = _RED32(c): g = _GREEN32(c): b = _BLUE32(c): o = opaque * 255
  28.     PSET (x, y), _RGBA32(r, g, b, o)
  30.  
  31. '// integer part of x
  32. FUNCTION ipart (x)
  33.     ipart = INT(x)
  35.  
  36. FUNCTION round (x)
  37.     round = ipart(x + 0.5)
  39.  
  40. '// fractional part of x
  41. FUNCTION fpart (x)
  42.     fpart = x - INT(x)
  44.  
  45. FUNCTION rfpart (x)
  46.     rfpart = 1 - fpart(x)
  48.  
  49. SUB WuLine (xx0, yy0, xx1, yy1, c AS _UNSIGNED LONG)
  50.     'make copies since swapping values
  51.  
  52.     x0 = xx0: y0 = yy0: x1 = xx1: y1 = yy1
  53.  
  54.     DIM steep AS INTEGER
  55.     steep = ABS(y1 - y0) > ABS(x1 - x0)
  56.  
  57.     IF steep = -1 THEN
  58.         SWAP x0, y0
  59.         SWAP x1, y1
  60.     END IF
  61.     IF x0 > x1 THEN
  62.         SWAP x0, x1
  63.         SWAP y0, y1
  64.     END IF
  65.  
  66.     dx = x1 - x0
  67.     dy = y1 - y0
  68.     gradient = dy / dx
  69.     IF dx = 0.0 THEN
  70.         gradient = 1.0
  71.     END IF
  72.  
  73.     '// handle first endpoint
  74.     xend = round(x0)
  75.     yend = y0 + gradient * (xend - x0)
  76.     xgap = rfpart(x0 + 0.5)
  77.     xpxl1 = xend '// this will be used in the main loop
  78.     ypxl1 = ipart(yend)
  79.     IF steep THEN
  80.         plot ypxl1, xpxl1, c, rfpart(yend) * xgap
  81.         plot ypxl1 + 1, xpxl1, c, fpart(yend) * xgap
  82.     ELSE
  83.         plot xpxl1, ypxl1, c, rfpart(yend) * xgap
  84.         plot xpxl1, ypxl1 + 1, c, fpart(yend) * xgap
  85.     END IF
  86.     intery = yend + gradient '// first y-intersection for the main loop
  87.  
  88.     '// handle second endpoint
  89.     xend = round(x1)
  90.     yend = y1 + gradient * (xend - x1)
  91.     xgap = fpart(x1 + 0.5)
  92.     xpxl2 = xend '//this will be used in the main loop
  93.     ypxl2 = ipart(yend)
  94.     IF steep THEN
  95.         plot ypxl2, xpxl2, c, rfpart(yend) * xgap
  96.         plot ypxl2 + 1, xpxl2, c, fpart(yend) * xgap
  97.     ELSE
  98.         plot xpxl2, ypxl2, c, rfpart(yend) * xgap
  99.         plot xpxl2, ypxl2 + 1, c, fpart(yend) * xgap
  100.     END IF
  101.  
  102.     '// main loop
  103.     IF steep = -1 THEN
  104.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  105.             plot ipart(intery), x, c, rfpart(intery)
  106.             plot ipart(intery) + 1, x, c, fpart(intery)
  107.             intery = intery + gradient
  108.         NEXT
  109.     ELSE
  110.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  111.             plot x, ipart(intery), c, rfpart(intery)
  112.             plot x, ipart(intery) + 1, c, fpart(intery)
  113.             intery = intery + gradient
  114.         NEXT
  115.     END IF
  117.  
  118.  

Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 05:15:28 pm
Note bad m8!

Careful - you risk division by zero here:

Code: QB64: [Select]
  1.     dx = x1 - x0
  2.     dy = y1 - y0
  3.     gradient = dy / dx
  4.     IF dx = 0.0 THEN
  5.         gradient = 1.0
  6.     END IF
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 05:18:16 pm
We should definitely stand back and figure out a good way to package this anti-aliasing stuff once the small demos stop pouring in. I'm already hating the crudeness of my graphics after looking at anti-aliased curves earlier today.

Luckily the demo I posted was just my gutted Collisions engine, so it's already a solved issue thanks to Fellippe.

Maybe work on filled circles and ellipses next?
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 05:30:14 pm
Quote from: STxAxTIC on March 08, 2020, 05:15:28 pm
Note bad m8!

Careful - you risk division by zero here:

Code: QB64: [Select]
  1.     dx = x1 - x0
  2.     dy = y1 - y0
  3.     gradient = dy / dx
  4.     IF dx = 0.0 THEN
  5.         gradient = 1.0
  6.     END IF

Nice catch!
Code: QB64: [Select]
  1.     dx = x1 - x0
  2.     dy = y1 - y0
  3.     IF dx = 0.0 THEN
  4.         gradient = 1.0
  5.     ELSE
  6.         gradient = dy / dx
  7.     END IF
  8.  
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: bplus on March 08, 2020, 06:23:55 pm
Opaque fills OK with filled circle on top but not transparent:

Code: QB64: [Select]
  1. CONST xmax = 1200, ymax = 700, xc = 600, yc = 350, nP = 20
  2.  
  3. _TITLE "WuLine Circles on Left, Normal circles on right, hmm.... not bad" 'B+ 2020-03-08
  4. SCREEN _NEWIMAGE(xmax, ymax, 32)
  6. _DELAY .25 '< after load before move .1 not always working
  8.  
  9. DIM x(nP), y(nP), r(nP), c(nP) AS _UNSIGNED LONG
  10. FOR i = 0 TO nP
  11.     x(i) = .5 * xc: y(i) = yc: r(i) = i * 300 / nP - 1
  12.     c(i) = _RGBA32(255 * RND, 255 * RND, 255 * RND, 255) ' << opaque OK but transparent NOT
  14.  
  15. FOR i = nP TO 0 STEP -1
  16.     fcirc x(i) + xc, y(i), r(i), c(i)
  17.     'FOR a = 0 TO _PI(2.0) STEP .5 / r(i)
  18.     '    'draw circles with wulines
  19.     '    x1 = x(i) + r(i) * COS(a)
  20.     '    y1 = y(i) + r(i) * SIN(a)
  21.     '    IF a > 0 THEN
  22.     '        WuLine xlast, ylast, x1, y1, c(i)
  23.     '    END IF
  24.     '    xlast = x1: ylast = y1
  25.     'NEXT
  26.     fcircSmooth x(i), y(i), r(i), c(i) 'fill on to of wuLine
  28.  
  29. SUB plot (x, y, c AS _UNSIGNED LONG, opaque) 'c is RGB color a level is opaqueness 0 to 1 transparent to solid
  30.     r = _RED32(c): g = _GREEN32(c): b = _BLUE32(c): o = opaque * 255
  31.     PSET (x, y), _RGBA32(r, g, b, o)
  33.  
  34. '// integer part of x
  35. FUNCTION ipart (x)
  36.     ipart = INT(x)
  38.  
  39. FUNCTION round (x)
  40.     round = ipart(x + 0.5)
  42.  
  43. '// fractional part of x
  44. FUNCTION fpart (x)
  45.     fpart = x - INT(x)
  47.  
  48. FUNCTION rfpart (x)
  49.     rfpart = 1 - fpart(x)
  51.  
  52. SUB WuLine (xx0, yy0, xx1, yy1, c AS _UNSIGNED LONG)
  53.     'make copies since swapping values
  54.  
  55.     x0 = xx0: y0 = yy0: x1 = xx1: y1 = yy1
  56.  
  57.     DIM steep AS INTEGER
  58.     steep = ABS(y1 - y0) > ABS(x1 - x0)
  59.  
  60.     IF steep = -1 THEN
  61.         SWAP x0, y0
  62.         SWAP x1, y1
  63.     END IF
  64.     IF x0 > x1 THEN
  65.         SWAP x0, x1
  66.         SWAP y0, y1
  67.     END IF
  68.  
  69.     dx = x1 - x0
  70.     dy = y1 - y0
  71.     IF dx = 0.0 THEN
  72.         gradient = 1.0
  73.     ELSE
  74.         gradient = dy / dx
  75.     END IF
  76.  
  77.     '// handle first endpoint
  78.     xend = round(x0)
  79.     yend = y0 + gradient * (xend - x0)
  80.     xgap = rfpart(x0 + 0.5)
  81.     xpxl1 = xend '// this will be used in the main loop
  82.     ypxl1 = ipart(yend)
  83.     IF steep THEN
  84.         plot ypxl1, xpxl1, c, rfpart(yend) * xgap
  85.         plot ypxl1 + 1, xpxl1, c, fpart(yend) * xgap
  86.     ELSE
  87.         plot xpxl1, ypxl1, c, rfpart(yend) * xgap
  88.         plot xpxl1, ypxl1 + 1, c, fpart(yend) * xgap
  89.     END IF
  90.     intery = yend + gradient '// first y-intersection for the main loop
  91.  
  92.     '// handle second endpoint
  93.     xend = round(x1)
  94.     yend = y1 + gradient * (xend - x1)
  95.     xgap = fpart(x1 + 0.5)
  96.     xpxl2 = xend '//this will be used in the main loop
  97.     ypxl2 = ipart(yend)
  98.     IF steep THEN
  99.         plot ypxl2, xpxl2, c, rfpart(yend) * xgap
  100.         plot ypxl2 + 1, xpxl2, c, fpart(yend) * xgap
  101.     ELSE
  102.         plot xpxl2, ypxl2, c, rfpart(yend) * xgap
  103.         plot xpxl2, ypxl2 + 1, c, fpart(yend) * xgap
  104.     END IF
  105.  
  106.     '// main loop
  107.     IF steep = -1 THEN
  108.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  109.             plot ipart(intery), x, c, rfpart(intery)
  110.             plot ipart(intery) + 1, x, c, fpart(intery)
  111.             intery = intery + gradient
  112.         NEXT
  113.     ELSE
  114.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  115.             plot x, ipart(intery), c, rfpart(intery)
  116.             plot x, ipart(intery) + 1, c, fpart(intery)
  117.             intery = intery + gradient
  118.         NEXT
  119.     END IF
  121.  
  122. SUB fcircSmooth (CX AS INTEGER, CY AS INTEGER, R AS INTEGER, C AS _UNSIGNED LONG)
  123.     DIM Radius AS INTEGER, RadiusError AS INTEGER, X AS SINGLE, Y AS SINGLE, xlast AS SINGLE, ylast AS SINGLE
  124.     DIM a AS SINGLE
  125.     FOR a = 0 TO _PI(2.0) + .5 / R STEP .5 / R
  126.         'draw circles with wulines
  127.         X = CX + R * COS(a)
  128.         Y = CY + R * SIN(a)
  129.         IF a > 0 THEN
  130.             WuLine xlast, ylast, X, Y, C
  131.         END IF
  132.         xlast = X: ylast = Y
  133.     NEXT
  134.  
  135.     Radius = ABS(R): RadiusError = -Radius: X = Radius: Y = 0
  136.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  137.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  138.     WHILE X > Y
  139.         RadiusError = RadiusError + Y * 2 + 1
  140.         IF RadiusError >= 0 THEN
  141.             IF X <> Y + 1 THEN
  142.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  143.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  144.             END IF
  145.             X = X - 1
  146.             RadiusError = RadiusError - X * 2
  147.         END IF
  148.         Y = Y + 1
  149.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  150.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  151.     WEND
  153.  
  154. 'from Steve Gold standard
  155. SUB fcirc (CX AS INTEGER, CY AS INTEGER, R AS INTEGER, C AS _UNSIGNED LONG)
  156.     DIM Radius AS INTEGER, RadiusError AS INTEGER
  157.     DIM X AS INTEGER, Y AS INTEGER
  158.     Radius = ABS(R): RadiusError = -Radius: X = Radius: Y = 0
  159.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  160.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  161.     WHILE X > Y
  162.         RadiusError = RadiusError + Y * 2 + 1
  163.         IF RadiusError >= 0 THEN
  164.             IF X <> Y + 1 THEN
  165.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  166.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  167.             END IF
  168.             X = X - 1
  169.             RadiusError = RadiusError - X * 2
  170.         END IF
  171.         Y = Y + 1
  172.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  173.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  174.     WEND
  176.  
  177.  
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: STxAxTIC on March 08, 2020, 06:38:10 pm
Here is a version of my submission above that does not insist on closed shapes. Press space to enter draw mode, and then single click to draw a straight line, hold mouse1 to make a curve.

Code: QB64: [Select]
  1. ' Display
  2. SCREEN _NEWIMAGE(800, 600, 32)
  3. _SCREENMOVE (_DESKTOPWIDTH \ 2 - _WIDTH \ 2) - 3, (_DESKTOPHEIGHT \ 2 - _HEIGHT \ 2) - 29
  4. _TITLE "If these curves were smoother they'd steal your wife."
  6.  
  7. ' Meta
  8. start:
  12.  
  13. ' Data structures
  14. TYPE Vector
  15.     x AS DOUBLE
  16.     y AS DOUBLE
  18.  
  19. DIM SHARED vtemp AS Vector
  20.  
  21. ' Object type
  22. TYPE Object
  23.     Elements AS INTEGER
  24.     Shade AS _UNSIGNED LONG
  26.  
  27. ' Object storage
  28. DIM SHARED Shape(300) AS Object
  29. DIM SHARED PointChain(300, 500) AS Vector
  30. DIM SHARED TempChain(300, 500) AS Vector
  31. DIM SHARED ShapeCount AS INTEGER
  32. DIM SHARED SelectedShape AS INTEGER
  33.  
  34. ' Initialize
  35. ShapeCount = 0
  36.  
  37. ' Main loop
  39.     IF (UserInput = -1) THEN GOTO start
  40.     CALL Graphics
  41.     _LIMIT 120
  43.  
  45.  
  46. FUNCTION UserInput
  47.     TheReturn = 0
  48.     ' Keyboard input
  49.     kk = _KEYHIT
  50.     SELECT CASE kk
  51.         CASE 32
  52.             DO: LOOP UNTIL _KEYHIT
  53.             WHILE _MOUSEINPUT: WEND
  54.             _KEYCLEAR
  55.             CALL NewMouseShape(7.5, 150, 15)
  56.             CLS
  57.     END SELECT
  58.     IF (kk) THEN
  59.         _KEYCLEAR
  60.     END IF
  61.     UserInput = TheReturn
  63.  
  64.  
  65. SUB Graphics
  66.     LINE (0, 0)-(_WIDTH, _HEIGHT), _RGBA(0, 0, 0, 200), BF
  67.     CALL cprintstring(16 * 17, "PRESS SPACE and then drag MOUSE 1 to draw a new shape.")
  68.     FOR ShapeIndex = 1 TO ShapeCount
  69.         FOR i = 1 TO Shape(ShapeIndex).Elements - 1
  70.             CALL lineSmooth(PointChain(ShapeIndex, i).x, PointChain(ShapeIndex, i).y, PointChain(ShapeIndex, i + 1).x, PointChain(ShapeIndex, i + 1).y, Shape(ShapeIndex).Shade)
  71.         NEXT
  72.     NEXT
  73.     _DISPLAY
  75.  
  76. SUB NewMouseShape (rawresolution AS DOUBLE, targetpoints AS INTEGER, smoothiterations AS INTEGER)
  77.     ShapeCount = ShapeCount + 1
  78.     numpoints = 0
  79.     xold = 999 ^ 999
  80.     yold = 999 ^ 999
  81.     DO
  82.         DO WHILE _MOUSEINPUT
  83.             x = _MOUSEX
  84.             y = _MOUSEY
  85.             IF (x > 0) AND (x < _WIDTH) AND (y > 0) AND (y < _HEIGHT) THEN
  86.                 IF _MOUSEBUTTON(1) THEN
  87.                     x = x - (_WIDTH / 2)
  88.                     y = -y + (_HEIGHT / 2)
  89.                     delta = SQR((x - xold) ^ 2 + (y - yold) ^ 2)
  90.                     IF (delta > rawresolution) AND (numpoints < targetpoints - 1) THEN
  91.                         numpoints = numpoints + 1
  92.                         PointChain(ShapeCount, numpoints).x = x
  93.                         PointChain(ShapeCount, numpoints).y = y
  94.                         CALL cpset(x, y, _RGB(0, 255, 255))
  95.                         xold = x
  96.                         yold = y
  97.                     END IF
  98.                 END IF
  99.             END IF
  100.         LOOP
  101.         _DISPLAY
  102.     LOOP UNTIL NOT _MOUSEBUTTON(1) AND (numpoints > 1)
  103.  
  104.     DO WHILE (numpoints < targetpoints)
  105.         rad2max = -1
  106.         kmax = -1
  107.         FOR k = 1 TO numpoints - 1
  108.             xfac = PointChain(ShapeCount, k).x - PointChain(ShapeCount, k + 1).x
  109.             yfac = PointChain(ShapeCount, k).y - PointChain(ShapeCount, k + 1).y
  110.             rad2 = xfac ^ 2 + yfac ^ 2
  111.             IF rad2 > rad2max THEN
  112.                 kmax = k
  113.                 rad2max = rad2
  114.             END IF
  115.         NEXT
  116.         FOR j = numpoints TO kmax + 1 STEP -1
  117.             PointChain(ShapeCount, j + 1).x = PointChain(ShapeCount, j).x
  118.             PointChain(ShapeCount, j + 1).y = PointChain(ShapeCount, j).y
  119.         NEXT
  120.         PointChain(ShapeCount, kmax + 1).x = (1 / 2) * (PointChain(ShapeCount, kmax).x + PointChain(ShapeCount, kmax + 2).x)
  121.         PointChain(ShapeCount, kmax + 1).y = (1 / 2) * (PointChain(ShapeCount, kmax).y + PointChain(ShapeCount, kmax + 2).y)
  122.         numpoints = numpoints + 1
  123.     LOOP
  124.  
  125.     FOR j = 1 TO smoothiterations
  126.         FOR k = 2 TO numpoints - 1
  127.             TempChain(ShapeCount, k).x = (1 / 2) * (PointChain(ShapeCount, k - 1).x + PointChain(ShapeCount, k + 1).x)
  128.             TempChain(ShapeCount, k).y = (1 / 2) * (PointChain(ShapeCount, k - 1).y + PointChain(ShapeCount, k + 1).y)
  129.         NEXT
  130.         FOR k = 2 TO numpoints - 1
  131.             PointChain(ShapeCount, k).x = TempChain(ShapeCount, k).x
  132.             PointChain(ShapeCount, k).y = TempChain(ShapeCount, k).y
  133.         NEXT
  134.     NEXT
  135.  
  136.     Shape(ShapeCount).Elements = numpoints
  137.     Shape(ShapeCount).Shade = _RGB(100 + INT(RND * 155), 100 + INT(RND * 155), 100 + INT(RND * 155))
  138.     SelectedShape = ShapeCount
  140.  
  141. SUB cpset (x1, y1, col AS _UNSIGNED LONG)
  142.     PSET (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col
  144.  
  145. SUB cprintstring (y, a AS STRING)
  146.     _PRINTSTRING (_WIDTH / 2 - (LEN(a) * 8) / 2, -y + _HEIGHT / 2), a
  148.  
  149. SUB lineSmooth (x0, y0, x1, y1, c AS _UNSIGNED LONG)
  150.     'translated from
  151.     'https://en.wikipedia.org/w/index.php?title=Xiaolin_Wu%27s_line_algorithm&oldid=852445548
  152.  
  153.     DIM plX AS INTEGER, plY AS INTEGER, plI
  154.  
  155.     DIM steep AS _BYTE
  156.     steep = ABS(y1 - y0) > ABS(x1 - x0)
  157.  
  158.     IF steep THEN
  159.         SWAP x0, y0
  160.         SWAP x1, y1
  161.     END IF
  162.  
  163.     IF x0 > x1 THEN
  164.         SWAP x0, x1
  165.         SWAP y0, y1
  166.     END IF
  167.  
  168.     DIM dx, dy, gradient
  169.     dx = x1 - x0
  170.     dy = y1 - y0
  171.     gradient = dy / dx
  172.  
  173.     IF dx = 0 THEN
  174.         gradient = 1
  175.     END IF
  176.  
  177.     'handle first endpoint
  178.     DIM xend, yend, xgap, xpxl1, ypxl1
  179.     xend = _ROUND(x0)
  180.     yend = y0 + gradient * (xend - x0)
  181.     xgap = (1 - ((x0 + .5) - INT(x0 + .5)))
  182.     xpxl1 = xend 'this will be used in the main loop
  183.     ypxl1 = INT(yend)
  184.     IF steep THEN
  185.         plX = ypxl1
  186.         plY = xpxl1
  187.         plI = (1 - (yend - INT(yend))) * xgap
  188.         GOSUB plot
  189.  
  190.         plX = ypxl1 + 1
  191.         plY = xpxl1
  192.         plI = (yend - INT(yend)) * xgap
  193.         GOSUB plot
  194.     ELSE
  195.         plX = xpxl1
  196.         plY = ypxl1
  197.         plI = (1 - (yend - INT(yend))) * xgap
  198.         GOSUB plot
  199.  
  200.         plX = xpxl1
  201.         plY = ypxl1 + 1
  202.         plI = (yend - INT(yend)) * xgap
  203.         GOSUB plot
  204.     END IF
  205.  
  206.     DIM intery
  207.     intery = yend + gradient 'first y-intersection for the main loop
  208.  
  209.     'handle second endpoint
  210.     DIM xpxl2, ypxl2
  211.     xend = _ROUND(x1)
  212.     yend = y1 + gradient * (xend - x1)
  213.     xgap = ((x1 + .5) - INT(x1 + .5))
  214.     xpxl2 = xend 'this will be used in the main loop
  215.     ypxl2 = INT(yend)
  216.     IF steep THEN
  217.         plX = ypxl2
  218.         plY = xpxl2
  219.         plI = (1 - (yend - INT(yend))) * xgap
  220.         GOSUB plot
  221.  
  222.         plX = ypxl2 + 1
  223.         plY = xpxl2
  224.         plI = (yend - INT(yend)) * xgap
  225.         GOSUB plot
  226.     ELSE
  227.         plX = xpxl2
  228.         plY = ypxl2
  229.         plI = (1 - (yend - INT(yend))) * xgap
  230.         GOSUB plot
  231.  
  232.         plX = xpxl2
  233.         plY = ypxl2 + 1
  234.         plI = (yend - INT(yend)) * xgap
  235.         GOSUB plot
  236.     END IF
  237.  
  238.     'main loop
  239.     DIM x
  240.     IF steep THEN
  241.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  242.             plX = INT(intery)
  243.             plY = x
  244.             plI = (1 - (intery - INT(intery)))
  245.             GOSUB plot
  246.  
  247.             plX = INT(intery) + 1
  248.             plY = x
  249.             plI = (intery - INT(intery))
  250.             GOSUB plot
  251.  
  252.             intery = intery + gradient
  253.         NEXT
  254.     ELSE
  255.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  256.             plX = x
  257.             plY = INT(intery)
  258.             plI = (1 - (intery - INT(intery)))
  259.             GOSUB plot
  260.  
  261.             plX = x
  262.             plY = INT(intery) + 1
  263.             plI = (intery - INT(intery))
  264.             GOSUB plot
  265.  
  266.             intery = intery + gradient
  267.         NEXT
  268.     END IF
  269.  
  270.     EXIT SUB
  271.  
  272.     plot:
  273.     CALL cpset(plX, plY, _RGB32(_RED32(c), _GREEN32(c), _BLUE32(c), plI * 255))
  274.     RETURN
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: FellippeHeitor on March 08, 2020, 07:49:13 pm
"If these curves were smoother they'd steal your wife." <- That's gold man <3

You guys took it and revamped it! This is great to see.
Title: Re: Xiaolin Wu's antialiased line algorithm
Post by: Ashish on March 09, 2020, 12:41:59 am
Wow..! I like it! It matches very closely to MSAA. Can be extended for smoothing images as well..
Text Only | Text with Attachments