Author Topic: Xiaolin Wu's antialiased line algorithm  (Read 8002 times)

0 Members and 1 Guest are viewing this topic.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #15 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.
« Last Edit: March 08, 2020, 01:13:35 pm by bplus »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #16 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
« Last Edit: March 08, 2020, 01:17:37 pm by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline STxAxTIC

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

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #18 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.
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #19 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.
« Last Edit: March 08, 2020, 03:54:40 pm by bplus »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #20 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.
« Last Edit: March 08, 2020, 04:01:11 pm by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #21 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
  6. DIM x(nP), y(nP), r(nP), c(nP) AS _UNSIGNED LONG
  7. FOR i = 0 TO nP
  8.     x(i) = .5 * xc: y(i) = yc: r(i) = i * 300 / nP
  9.     c(i) = _RGB32(255 * RND, 255 * RND, 255 * RND)
  10.  
  11. FOR i = 0 TO nP
  12.     CIRCLE (x(i) + xc, y(i)), r(i), c(i)
  13.     FOR a = 0 TO _PI(2.1) STEP .1
  14.         'draw circles with wulines
  15.         x1 = x(i) + r(i) * COS(a)
  16.         y1 = y(i) + r(i) * SIN(a)
  17.         IF a > 0 THEN
  18.             WuLine xlast, ylast, x1, y1, c(i)
  19.         END IF
  20.         xlast = x1: ylast = y1
  21.     NEXT
  22.  
  23. SUB plot (x, y, c AS _UNSIGNED LONG, opaque) 'c is RGB color a level is opaqueness 0 to 1 transparent to solid
  24.     r = _RED32(c): g = _GREEN32(c): b = _BLUE32(c): o = opaque * 255
  25.     PSET (x, y), _RGBA32(r, g, b, o)
  26.  
  27. '// integer part of x
  28. FUNCTION ipart (x)
  29.     ipart = INT(x)
  30.  
  31. FUNCTION round (x)
  32.     round = ipart(x + 0.5)
  33.  
  34. '// fractional part of x
  35. FUNCTION fpart (x)
  36.     fpart = x - INT(x)
  37.  
  38. FUNCTION rfpart (x)
  39.     rfpart = 1 - fpart(x)
  40.  
  41. SUB WuLine (xx0, yy0, xx1, yy1, c AS _UNSIGNED LONG)
  42.     'make copies since swapping values
  43.  
  44.     x0 = xx0: y0 = yy0: x1 = xx1: y1 = yy1
  45.  
  46.     DIM steep AS INTEGER
  47.     steep = ABS(y1 - y0) > ABS(x1 - x0)
  48.  
  49.     IF steep = -1 THEN
  50.         SWAP x0, y0
  51.         SWAP x1, y1
  52.     END IF
  53.     IF x0 > x1 THEN
  54.         SWAP x0, x1
  55.         SWAP y0, y1
  56.     END IF
  57.  
  58.     dx = x1 - x0
  59.     dy = y1 - y0
  60.     gradient = dy / dx
  61.     IF dx = 0.0 THEN
  62.         gradient = 1.0
  63.     END IF
  64.  
  65.     '// handle first endpoint
  66.     xend = round(x0)
  67.     yend = y0 + gradient * (xend - x0)
  68.     xgap = rfpart(x0 + 0.5)
  69.     xpxl1 = xend '// this will be used in the main loop
  70.     ypxl1 = ipart(yend)
  71.     IF steep THEN
  72.         plot ypxl1, xpxl1, c, rfpart(yend) * xgap
  73.         plot ypxl1 + 1, xpxl1, c, fpart(yend) * xgap
  74.     ELSE
  75.         plot xpxl1, ypxl1, c, rfpart(yend) * xgap
  76.         plot xpxl1, ypxl1 + 1, c, fpart(yend) * xgap
  77.     END IF
  78.     intery = yend + gradient '// first y-intersection for the main loop
  79.  
  80.     '// handle second endpoint
  81.     xend = round(x1)
  82.     yend = y1 + gradient * (xend - x1)
  83.     xgap = fpart(x1 + 0.5)
  84.     xpxl2 = xend '//this will be used in the main loop
  85.     ypxl2 = ipart(yend)
  86.     IF steep THEN
  87.         plot ypxl2, xpxl2, c, rfpart(yend) * xgap
  88.         plot ypxl2 + 1, xpxl2, c, fpart(yend) * xgap
  89.     ELSE
  90.         plot xpxl2, ypxl2, c, rfpart(yend) * xgap
  91.         plot xpxl2, ypxl2 + 1, c, fpart(yend) * xgap
  92.     END IF
  93.  
  94.     '// main loop
  95.     IF steep = -1 THEN
  96.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  97.             plot ipart(intery), x, c, rfpart(intery)
  98.             plot ipart(intery) + 1, x, c, fpart(intery)
  99.             intery = intery + gradient
  100.         NEXT
  101.     ELSE
  102.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  103.             plot x, ipart(intery), c, rfpart(intery)
  104.             plot x, ipart(intery) + 1, c, fpart(intery)
  105.             intery = intery + gradient
  106.         NEXT
  107.     END IF
  108.  
  109.  

wuLine Circles.PNG
* wuLine Circles.PNG (Filesize: 170.39 KB, Dimensions: 1206x716, Views: 296)
« Last Edit: March 08, 2020, 04:40:54 pm by bplus »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #22 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
You're not done when it works, you're done when it's right.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #23 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?
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #24 on: March 08, 2020, 05:30:14 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.  

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #25 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)
  5. _DELAY .25 '< after load before move .1 not always working
  6.  
  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 - 1
  10.     c(i) = _RGBA32(255 * RND, 255 * RND, 255 * RND, 255) ' << opaque OK but transparent NOT
  11.  
  12. FOR i = nP TO 0 STEP -1
  13.     fcirc x(i) + xc, y(i), r(i), c(i)
  14.     'FOR a = 0 TO _PI(2.0) STEP .5 / r(i)
  15.     '    'draw circles with wulines
  16.     '    x1 = x(i) + r(i) * COS(a)
  17.     '    y1 = y(i) + r(i) * SIN(a)
  18.     '    IF a > 0 THEN
  19.     '        WuLine xlast, ylast, x1, y1, c(i)
  20.     '    END IF
  21.     '    xlast = x1: ylast = y1
  22.     'NEXT
  23.     fcircSmooth x(i), y(i), r(i), c(i) 'fill on to of wuLine
  24.  
  25. SUB plot (x, y, c AS _UNSIGNED LONG, opaque) 'c is RGB color a level is opaqueness 0 to 1 transparent to solid
  26.     r = _RED32(c): g = _GREEN32(c): b = _BLUE32(c): o = opaque * 255
  27.     PSET (x, y), _RGBA32(r, g, b, o)
  28.  
  29. '// integer part of x
  30. FUNCTION ipart (x)
  31.     ipart = INT(x)
  32.  
  33. FUNCTION round (x)
  34.     round = ipart(x + 0.5)
  35.  
  36. '// fractional part of x
  37. FUNCTION fpart (x)
  38.     fpart = x - INT(x)
  39.  
  40. FUNCTION rfpart (x)
  41.     rfpart = 1 - fpart(x)
  42.  
  43. SUB WuLine (xx0, yy0, xx1, yy1, c AS _UNSIGNED LONG)
  44.     'make copies since swapping values
  45.  
  46.     x0 = xx0: y0 = yy0: x1 = xx1: y1 = yy1
  47.  
  48.     DIM steep AS INTEGER
  49.     steep = ABS(y1 - y0) > ABS(x1 - x0)
  50.  
  51.     IF steep = -1 THEN
  52.         SWAP x0, y0
  53.         SWAP x1, y1
  54.     END IF
  55.     IF x0 > x1 THEN
  56.         SWAP x0, x1
  57.         SWAP y0, y1
  58.     END IF
  59.  
  60.     dx = x1 - x0
  61.     dy = y1 - y0
  62.     IF dx = 0.0 THEN
  63.         gradient = 1.0
  64.     ELSE
  65.         gradient = dy / dx
  66.     END IF
  67.  
  68.     '// handle first endpoint
  69.     xend = round(x0)
  70.     yend = y0 + gradient * (xend - x0)
  71.     xgap = rfpart(x0 + 0.5)
  72.     xpxl1 = xend '// this will be used in the main loop
  73.     ypxl1 = ipart(yend)
  74.     IF steep THEN
  75.         plot ypxl1, xpxl1, c, rfpart(yend) * xgap
  76.         plot ypxl1 + 1, xpxl1, c, fpart(yend) * xgap
  77.     ELSE
  78.         plot xpxl1, ypxl1, c, rfpart(yend) * xgap
  79.         plot xpxl1, ypxl1 + 1, c, fpart(yend) * xgap
  80.     END IF
  81.     intery = yend + gradient '// first y-intersection for the main loop
  82.  
  83.     '// handle second endpoint
  84.     xend = round(x1)
  85.     yend = y1 + gradient * (xend - x1)
  86.     xgap = fpart(x1 + 0.5)
  87.     xpxl2 = xend '//this will be used in the main loop
  88.     ypxl2 = ipart(yend)
  89.     IF steep THEN
  90.         plot ypxl2, xpxl2, c, rfpart(yend) * xgap
  91.         plot ypxl2 + 1, xpxl2, c, fpart(yend) * xgap
  92.     ELSE
  93.         plot xpxl2, ypxl2, c, rfpart(yend) * xgap
  94.         plot xpxl2, ypxl2 + 1, c, fpart(yend) * xgap
  95.     END IF
  96.  
  97.     '// main loop
  98.     IF steep = -1 THEN
  99.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  100.             plot ipart(intery), x, c, rfpart(intery)
  101.             plot ipart(intery) + 1, x, c, fpart(intery)
  102.             intery = intery + gradient
  103.         NEXT
  104.     ELSE
  105.         FOR x = xpxl1 + 1 TO xpxl2 - 1
  106.             plot x, ipart(intery), c, rfpart(intery)
  107.             plot x, ipart(intery) + 1, c, fpart(intery)
  108.             intery = intery + gradient
  109.         NEXT
  110.     END IF
  111.  
  112. SUB fcircSmooth (CX AS INTEGER, CY AS INTEGER, R AS INTEGER, C AS _UNSIGNED LONG)
  113.     DIM Radius AS INTEGER, RadiusError AS INTEGER, X AS SINGLE, Y AS SINGLE, xlast AS SINGLE, ylast AS SINGLE
  114.     DIM a AS SINGLE
  115.     FOR a = 0 TO _PI(2.0) + .5 / R STEP .5 / R
  116.         'draw circles with wulines
  117.         X = CX + R * COS(a)
  118.         Y = CY + R * SIN(a)
  119.         IF a > 0 THEN
  120.             WuLine xlast, ylast, X, Y, C
  121.         END IF
  122.         xlast = X: ylast = Y
  123.     NEXT
  124.  
  125.     Radius = ABS(R): RadiusError = -Radius: X = Radius: Y = 0
  126.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  127.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  128.     WHILE X > Y
  129.         RadiusError = RadiusError + Y * 2 + 1
  130.         IF RadiusError >= 0 THEN
  131.             IF X <> Y + 1 THEN
  132.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  133.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  134.             END IF
  135.             X = X - 1
  136.             RadiusError = RadiusError - X * 2
  137.         END IF
  138.         Y = Y + 1
  139.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  140.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  141.     WEND
  142.  
  143. 'from Steve Gold standard
  144. SUB fcirc (CX AS INTEGER, CY AS INTEGER, R AS INTEGER, C AS _UNSIGNED LONG)
  145.     DIM Radius AS INTEGER, RadiusError AS INTEGER
  146.     DIM X AS INTEGER, Y AS INTEGER
  147.     Radius = ABS(R): RadiusError = -Radius: X = Radius: Y = 0
  148.     IF Radius = 0 THEN PSET (CX, CY), C: EXIT SUB
  149.     LINE (CX - X, CY)-(CX + X, CY), C, BF
  150.     WHILE X > Y
  151.         RadiusError = RadiusError + Y * 2 + 1
  152.         IF RadiusError >= 0 THEN
  153.             IF X <> Y + 1 THEN
  154.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), C, BF
  155.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), C, BF
  156.             END IF
  157.             X = X - 1
  158.             RadiusError = RadiusError - X * 2
  159.         END IF
  160.         Y = Y + 1
  161.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), C, BF
  162.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), C, BF
  163.     WEND
  164.  
  165.  
Fill Circle Smooth Transparent.PNG
* Fill Circle Smooth Transparent.PNG (Filesize: 200.16 KB, Dimensions: 1204x734, Views: 304)
« Last Edit: March 08, 2020, 06:26:14 pm by bplus »

Offline STxAxTIC

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

FellippeHeitor

  • Guest
Re: Xiaolin Wu's antialiased line algorithm
« Reply #27 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.

Offline Ashish

  • Forum Resident
  • Posts: 630
  • Never Give Up!
    • View Profile
Re: Xiaolin Wu's antialiased line algorithm
« Reply #28 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..
if (Me.success) {Me.improve()} else {Me.tryAgain()}


My Projects - https://github.com/AshishKingdom?tab=repositories
OpenGL tutorials - https://ashishkingdom.github.io/OpenGL-Tutorials