Xiaolin Wu's antialiased line algorithm

[FellippeHeitor]

SUB lineSmooth (x0, y0, x1, y1, c AS _UNSIGNED LONG), with demo usage below.

Code: QB64: [Select]

1. OPTION _EXPLICIT
2. SCREEN _NEWIMAGE(800, 600, 32)
3.  
4. DIM m$
5. DO
6.     WHILE _MOUSEINPUT: WEND
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
23. LOOP
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
151. END SUB
152.  

[bplus]

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
12. WEND
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)
17. END SUB
18.  
19. '// integer part of x
20. FUNCTION ipart (x)
21.     ipart = INT(x)
22. END FUNCTION
23.  
24. FUNCTION round (x)
25.     round = ipart(x + 0.5)
26. END FUNCTION
27.  
28. '// fractional part of x
29. FUNCTION fpart (x)
30.     fpart = x - INT(x)
31. END FUNCTION
32.  
33. FUNCTION rfpart (x)
34.     rfpart = 1 - fpart(x)
35. END FUNCTION
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
104. END SUB
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

[FellippeHeitor]

Can you spot the differences between our approaches?

[bplus]

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.

[FellippeHeitor]

No :-)

[bplus]

OK

[STxAxTIC]

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?

[FellippeHeitor]

I'm after an antialiased circle algorithm as well, will that do it?

[STxAxTIC]

Oops I edited as you were responding so it may pass by too fast. But for the sake of not skipping a beat:

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

I mean *any* curve...

[FellippeHeitor]

I only mentioned circles *after* you made that edit.

[STxAxTIC]

I guess what I'm after is an anti-aliased DRAW. Hm, now you've got me thinking. God I love the forums...

[bplus]

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.

[bplus]

Hey is this from conversation at Discourse?

[FellippeHeitor]

We are always at Discord. *wink wink*

[STxAxTIC]

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.