Is this fast enough as general circle fill?

[bplus]

Slower than Steve's but this fills a regular polygon that approaches a circle as increase the number of sides. It fills the circle with an image and the image is based according to location of mouse (or where ever you want a circular part of image).

This is a circle fill method based on _MAPTRIANGLE, I think it is fast enough to impress!

Code: QB64: [Select]

1. 'Poly Image Demo 2
2. 'by bplus started 2018-06-22
3.  
4. CONST xmax = 800
5. CONST ymax = 600
6. SCREEN _NEWIMAGE(xmax, ymax, 32)
7. _SCREENMOVE 100, 20
8.  
9. stars& = _LOADIMAGE("stars.png")
10. stuff& = _NEWIMAGE(xmax, ymax, 32)
11. _DEST stuff&
12. FOR i = 1 TO 100
13.     CIRCLE (RND * xmax, RND * ymax), RND * 100, _RGB32(RND * 255, RND * 255, RND * 255)
14. NEXT
15. _DEST 0
16. DO
17.     CLS
18.     _SOURCE stuff&
19.     _PUTIMAGE
20.     WHILE _MOUSEINPUT: WEND
21.     polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50
22.     _DISPLAY
23.     _LIMIT 30
24. LOOP
25.  
26.  
27. SUB polygonImage (ImageHandle&, xOrigin, yOrigin, radius, nVertex)
28.     polyAngle = _PI(2) / nVertex
29.     x1 = xOrigin + radius * COS(polyAngle)
30.     y1 = yOrigin + radius * SIN(polyAngle)
31.     FOR i = 2 TO nVertex + 1
32.         x2 = xOrigin + radius * COS(i * polyAngle)
33.         y2 = yOrigin + radius * SIN(i * polyAngle)
34.         _MAPTRIANGLE (xOrigin, yOrigin)-(x1, y1)-(x2, y2), ImageHandle& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
35.         x1 = x2: y1 = y2
36.     NEXT
37. END SUB
38.  

Attached is code with Stars.png for testing with image file.

[SMcNeill]

For the absolute FASTEST filled circle routine, what one could do is simply pre-calculate the start and end points for each line of a circle of X size, and then save that data into an array.  Then, instead of the program having to do any math, it'd just lookup the plot points directly from memory, and insta-draw the circle.

Take all the math out ahead of time, utilize a lookup table, and it'd be much quicker than anything anybody has shared previously.  Only drawback would be the memory required to store the lookup table, which, in regards to modern OS memory limits, really shouldn't be that big an issue at all, honestly. 

[bplus]

Here is my test code comparing the 2 Methods with just one color. Over 2 times slower but not 10 or 1000 times...

Code: QB64: [Select]

1. _TITLE "Circle fill: Steve's method versus MapTriangle by bplus started 2018-06-22"
2. 'QB64 version 2017 1106/82 (the day before they switched to version 1.2)
3.  
4. 'steve's method wins easily
5.  
6. CONST xmax = 800
7. CONST ymax = 600
8. SCREEN _NEWIMAGE(xmax, ymax, 32)
9. _SCREENMOVE 360, 60
10. start## = TIMER
11. 'this is 10 X 10 X 10 runs on circle with different colors
12. FOR r = 246 TO 255
13.     FOR g = 246 TO 255
14.         FOR b = 1 TO 10
15.             'fpcir xmax / 2, ymax / 2, 300, _RGB32(r, g, b)
16.             fcirc xmax / 2, ymax / 2, 300, _RGB32(r, g, b)
17.         NEXT
18.     NEXT
19. NEXT
20. COLOR _RGB32(255, 255, 255)
21. PRINT TIMER - start##
22.  
23. SUB fpcir (xOrigin AS LONG, yOrigin AS LONG, radius AS LONG, K AS _UNSIGNED LONG)
24.     a& = _NEWIMAGE(1, 1, 32)
25.     _DEST a&
26.     PSET (0, 0), K
27.     _DEST 0
28.     DIM x1 AS LONG, y1 AS LONG, x2 AS LONG, y2 AS LONG, i AS INTEGER
29.     DIM polyAngle AS SINGLE
30.     polyAngle = _PI(2) / 60
31.     x1 = xOrigin + radius * COS(polyAngle)
32.     y1 = yOrigin + radius * SIN(polyAngle)
33.     FOR i = 2 TO 61
34.         x2 = xOrigin + radius * COS(i * polyAngle)
35.         y2 = yOrigin + radius * SIN(i * polyAngle)
36.         _MAPTRIANGLE (0, 0)-(0, 0)-(0, 0), a& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
37.         x1 = x2: y1 = y2
38.     NEXT
39.     _FREEIMAGE a& '<<< this is important!
40. END SUB
41.  
42. SUB fcirc (CX AS LONG, CY AS LONG, R AS LONG, K AS _UNSIGNED LONG)
43.     DIM subRadius AS LONG, RadiusError AS LONG
44.     DIM X AS LONG, Y AS LONG
45.  
46.     subRadius = ABS(R)
47.     RadiusError = -subRadius
48.     X = subRadius
49.     Y = 0
50.  
51.     IF subRadius = 0 THEN PSET (CX, CY): EXIT SUB
52.  
53.     ' Draw the middle span here so we don't draw it twice in the main loop,
54.     ' which would be a problem with blending turned on.
55.     LINE (CX - X, CY)-(CX + X, CY), K, BF
56.  
57.     WHILE X > Y
58.         RadiusError = RadiusError + Y * 2 + 1
59.         IF RadiusError >= 0 THEN
60.             IF X <> Y + 1 THEN
61.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), K, BF
62.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), K, BF
63.             END IF
64.             X = X - 1
65.             RadiusError = RadiusError - X * 2
66.         END IF
67.         Y = Y + 1
68.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), K, BF
69.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), K, BF
70.     WEND
71. END SUB
72.  
73.  

Might use codeguy's "mini step" to adjust number of triangles to take according to size of (near) circle. Here I just tested a large "circle" polygon with 60 sides for speed.

[Petr]

Hi Codeguy. I was watching your program, there are two brakes. The first big brake is Minstep !, it's really low for large diameters and that's why it's so slow. Another - but smaller brake is the call of the sinus and cosine functions during rendering. It is far more advantageous to save these values in a field and then to use them directly for drawing. I made some attempts, the LINE command with the parameter, BF is 50 percent faster than without it, and 40 percent slower with the B parameter than without it. Your turn-around solution with only a quarter rotation is very nice, it saves a lot of extra time.

Code: QB64: [Select]

1.  
2. '0.105 original
3. REDIM Px(0) AS SINGLE, Py(0) AS SINGLE
4. Demo& = _NEWIMAGE(1366, 768, 256)
5. SCREEN Demo&
6. St! = TIMER(.001)
7. Radius = 1000
8. Cx = Radius
9. Cy = Radius
10.  
11. ' Minstep: When someone rewrite it to function, I would leave this as an optional parameter, letting everyone decide by themselves how much smooth circle wants ...
12. 'Minstep! = 1 / (2 * _PI * Radius) 'why so? For circle R = 250: 1 / (6.28 * 250) = 0.0006. This is very small step...
13. Minstep! = 1 / _PI / (Radius / 10) ' for Circle R = 250: 1 / 3.14 / 25 = 0.01, it is enought...or not?
14.  
15. FOR s = 0 TO _PI / 2 STEP Minstep!
16.     Px(i) = Radius * COS(s!)
17.     Py(i) = Radius * SIN(s!)
18.     i = i + 1
19.     REDIM _PRESERVE Px(i) AS SINGLE
20.     REDIM _PRESERVE Py(i) AS SINGLE
21. NEXT
22.  
23.  
24. FOR s = 0 TO UBOUND(Px)
25.     LINE (Cx - Px(s), Cy - Py(s))-(Cx + Px(s), Cy + Py(s)), 127, BF
26. NEXT
27.  
28. F! = TIMER(.001)
29. LOCATE 1, 1
30. PRINT F! - St!;
31. _DELAY 10
32. SCREEN 0
33. _FREEIMAGE Demo&
34.  
35.  

[Petr]

For some reason, I can not edit the previous post, so here is the Minstep! fixed so that it also works on small radius.

Code: QB64: [Select]

1.  
2.  
3.  
4. '0.105 original
5. REDIM Px(0) AS SINGLE, Py(0) AS SINGLE, s AS SINGLE, st AS SINGLE, radius AS INTEGER, Cx AS INTEGER, Cy AS INTEGER
6. Demo& = _NEWIMAGE(1366, 768, 256)
7. SCREEN Demo&
8. st! = TIMER(.001)
9. radius = 555
10. Cx = 250 'radius
11. Cy = 400 'radius
12.  
13. ' Minstep: When someone rewrite it to function, I would leave this as an optional parameter, letting everyone decide by themselves how much smooth circle wants ...
14. 'Minstep! = 1 / (2 * _PI * Radius) 'why so? For circle R = 250: 1 / (6.28 * 250) = 0.0006. This is very small step...
15. Minstep! = 1 / (_PI / 2 * radius)
16.  
17. FOR s = 0 TO _PI / 2 STEP Minstep!
18.     Px(i) = radius * COS(s!)
19.     Py(i) = radius * SIN(s!)
20.     i = i + 1
21.     REDIM _PRESERVE Px(i) AS SINGLE
22.     REDIM _PRESERVE Py(i) AS SINGLE
23. NEXT
24.  
25.  
26. FOR s = 0 TO UBOUND(Px)
27.     LINE (Cx - Px(s), Cy - Py(s))-(Cx + Px(s), Cy + Py(s)), 127, BF
28. NEXT
29.  
30. F! = TIMER(.001)
31. LOCATE 1, 1
32. PRINT F! - st!;
33. _DELAY 10
34. SCREEN 0
35. _FREEIMAGE Demo&
36.  
37.  

[Petr]

Slower than Steve's but this fills a regular polygon that approaches a circle as increase the number of sides. It fills the circle with an image and the image is based according to location of mouse (or where ever you want a circular part of image).

This is a circle fill method based on _MAPTRIANGLE, I think it is fast enough to impress!

Code: QB64: [Select]

1. 'Poly Image Demo 2
2. 'by bplus started 2018-06-22
3.  
4. CONST xmax = 800
5. CONST ymax = 600
6. SCREEN _NEWIMAGE(xmax, ymax, 32)
7. _SCREENMOVE 100, 20
8.  
9. stars& = _LOADIMAGE("stars.png")
10. stuff& = _NEWIMAGE(xmax, ymax, 32)
11. _DEST stuff&
12. FOR i = 1 TO 100
13.     CIRCLE (RND * xmax, RND * ymax), RND * 100, _RGB32(RND * 255, RND * 255, RND * 255)
14. NEXT
15. _DEST 0
16. DO
17.     CLS
18.     _SOURCE stuff&
19.     _PUTIMAGE
20.     WHILE _MOUSEINPUT: WEND
21.     polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50
22.     _DISPLAY
23.     _LIMIT 30
24. LOOP
25.  
26.  
27. SUB polygonImage (ImageHandle&, xOrigin, yOrigin, radius, nVertex)
28.     polyAngle = _PI(2) / nVertex
29.     x1 = xOrigin + radius * COS(polyAngle)
30.     y1 = yOrigin + radius * SIN(polyAngle)
31.     FOR i = 2 TO nVertex + 1
32.         x2 = xOrigin + radius * COS(i * polyAngle)
33.         y2 = yOrigin + radius * SIN(i * polyAngle)
34.         _MAPTRIANGLE (xOrigin, yOrigin)-(x1, y1)-(x2, y2), ImageHandle& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
35.         x1 = x2: y1 = y2
36.     NEXT
37. END SUB
38.  

Attached is code with Stars.png for testing with image file.

Hi Bplus, You can use hardware images for really fast output:

Code: QB64: [Select]

1. 'Poly Image Demo 2
2. 'by bplus started 2018-06-22
3.  
4. CONST xmax = 800
5. CONST ymax = 600
6. SCREEN _NEWIMAGE(xmax, ymax, 32)
7. _SCREENMOVE 100, 20
8.  
9. star& = _LOADIMAGE("stars.png")
10. stars& = _COPYIMAGE(star&, 33)
11. _FREEIMAGE star&
12. stuff& = _NEWIMAGE(xmax, ymax, 32)
13. _DEST stuff&
14. FOR i = 1 TO 100
15.     CIRCLE (RND * xmax, RND * ymax), RND * 100, _RGB32(RND * 255, RND * 255, RND * 255)
16. NEXT
17. _DEST 0
18. DO
19.     '    CLS not need for hardware images and in this case also not, _PUTIMAGE in this case rewrite screen.
20.     _SOURCE stuff&
21.     _PUTIMAGE
22.     WHILE _MOUSEINPUT: WEND
23.     polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50
24.     _DISPLAY
25.     _LIMIT 30
26. LOOP
27.  
28.  
29. SUB polygonImage (ImageHandle&, xOrigin, yOrigin, radius, nVertex) 'Where I just saw it.... :-D
30.     polyAngle = _PI(2) / nVertex
31.     x1 = xOrigin + radius * COS(polyAngle)
32.     y1 = yOrigin + radius * SIN(polyAngle)
33.     FOR i = 2 TO nVertex + 1
34.         x2 = xOrigin + radius * COS(i * polyAngle)
35.         y2 = yOrigin + radius * SIN(i * polyAngle)
36.         _MAPTRIANGLE (xOrigin, yOrigin)-(x1, y1)-(x2, y2), ImageHandle& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
37.         x1 = x2: y1 = y2
38.     NEXT
39. END SUB
40.  
41.  

[bplus]

Code: QB64: [Select]

1. stars& = _COPYIMAGE(star&, 33)

Petr, Using this line is causing a line of distortion on y axis right down the 270 to 90 degree line from center??? for my system when I move the mouse around. Using the image as I had directly was better (for my system anyway).

Does anyone else see it? It's seems about 2-4 (maybe more) pixels wide.



PS Petr: Right! CLS was not needed, leftover from before drawing "stuff".

[Petr]

Petr, Using this line is causing a line of distortion on y axis right down the 270 to 90 degree line from center??? for my system when I move the mouse around. Using the image as I had directly was better (for my system anyway).

Does anyone else see it? It's seems about 2-4 (maybe more) pixels wide.

Yes, right under the mouse. It is interesting. It is best see in bright places. And it does with a hardware image only. So I have it not seen this yet.

[SkyCharger001]

about the LINE BF,

Code: QB64: [Select]

1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bf

instead of

Code: QB64: [Select]

1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bf

should save you half of the LINE calls

[bplus]

about the LINE BF,

Code: QB64: [Select]

1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bf

instead of

Code: QB64: [Select]

1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bf

should save you half of the LINE calls

Yes, but if you are using alpha coloring, the overlapping boxes might NOT give you an even shade.

[_vince]

These claims I strongly refuse to believe that anything's faster than that by Steve.

[SkyCharger001]

about the LINE BF,

Code: QB64: [Select]

1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bf

instead of

Code: QB64: [Select]

1. LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bf

should save you half of the LINE calls

Yes, but if you are using alpha coloring, the overlapping boxes might NOT give you an even shade.

Ah, didn't think about that.
one solution (that might ruin the speed-gain) would be to draw the filled circle on a temporary indexed image with color 0 set to RGBA(0,0,0,0) for masking and color 1 set to whatever RGBA color you want, and _PUTIMAGEing it onto the target image.

[zigzag]

Hasn't anyone considered using this method?

Code: QB64: [Select]

1. Radius% = 1000
2. Cx% = Radius%
3. Cy% = Radius%
4.  
5. FOR X% = 0 TO Radius%
6.   Y% = SQR(Radius% * Radius% - X% * X%)
7.   LINE (Cx% + X%, Cy% - Y%)-(Cx% + X%, Cy% + Y%)
8.   LINE (Cx% - X%, Cy% - Y%)-(Cx% - X%, Cy% + Y%)
9. NEXT

[Ashish]

+Zigzag
I guess you are using circle equation (x^2+y^2=r^2) inside the loop and it works. Good to see this code as I've only use these equation on paper graphs.

[bplus]

Hi zigzag,

Yes! First thing I ever tried. Apparently the SQR function takes allot of time!

Also, it has been recently discussed, counter to our intuition that a line is faster with BF than without.



I think Steve's "Gold Standard" method comes from here:
https://en.wikipedia.org/wiki/Midpoint_circle_algorithm