Author Topic: Is this fast enough as general circle fill?  (Read 1161 times)

Re: Is this fast enough as general circle fill?
« Reply #15 on: June 25, 2018, 10:30:55 AM »
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: [Select]
'Poly Image Demo 2
'by bplus started 2018-06-22

CONST xmax = 800
CONST ymax = 600
SCREEN _NEWIMAGE(xmax, ymax, 32)
_SCREENMOVE 100, 20

stars& = _LOADIMAGE("stars.png")
stuff& = _NEWIMAGE(xmax, ymax, 32)
_DEST stuff&
FOR i = 1 TO 100
    CIRCLE (RND * xmax, RND * ymax), RND * 100, _RGB32(RND * 255, RND * 255, RND * 255)
NEXT
_DEST 0
DO
    CLS
    _SOURCE stuff&
    _PUTIMAGE
    WHILE _MOUSEINPUT: WEND
    polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50
    _DISPLAY
    _LIMIT 30
LOOP


SUB polygonImage (ImageHandle&, xOrigin, yOrigin, radius, nVertex)
    polyAngle = _PI(2) / nVertex
    x1 = xOrigin + radius * COS(polyAngle)
    y1 = yOrigin + radius * SIN(polyAngle)
    FOR i = 2 TO nVertex + 1
        x2 = xOrigin + radius * COS(i * polyAngle)
        y2 = yOrigin + radius * SIN(i * polyAngle)
        _MAPTRIANGLE (xOrigin, yOrigin)-(x1, y1)-(x2, y2), ImageHandle& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
        x1 = x2: y1 = y2
    NEXT
END SUB

Attached is code with Stars.png for testing with image file.
« Last Edit: June 25, 2018, 10:35:26 AM by bplus »
B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00

Offline SMcNeill

  • QB64 Developer
Re: Is this fast enough as general circle fill?
« Reply #16 on: June 25, 2018, 10:43:40 AM »
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. 

Re: Is this fast enough as general circle fill?
« Reply #17 on: June 25, 2018, 10:47:54 AM »
Here is my test code comparing the 2 Methods with just one color. Over 2 times slower but not 10 or 1000 times...

Code: [Select]
_TITLE "Circle fill: Steve's method versus MapTriangle by bplus started 2018-06-22"
'QB64 version 2017 1106/82 (the day before they switched to version 1.2)

'steve's method wins easily

CONST xmax = 800
CONST ymax = 600
SCREEN _NEWIMAGE(xmax, ymax, 32)
_SCREENMOVE 360, 60
start## = TIMER
'this is 10 X 10 X 10 runs on circle with different colors
FOR r = 246 TO 255
    FOR g = 246 TO 255
        FOR b = 1 TO 10
            'fpcir xmax / 2, ymax / 2, 300, _RGB32(r, g, b)
            fcirc xmax / 2, ymax / 2, 300, _RGB32(r, g, b)
        NEXT
    NEXT
NEXT
COLOR _RGB32(255, 255, 255)
PRINT TIMER - start##

SUB fpcir (xOrigin AS LONG, yOrigin AS LONG, radius AS LONG, K AS _UNSIGNED LONG)
    a& = _NEWIMAGE(1, 1, 32)
    _DEST a&
    PSET (0, 0), K
    _DEST 0
    DIM x1 AS LONG, y1 AS LONG, x2 AS LONG, y2 AS LONG, i AS INTEGER
    DIM polyAngle AS SINGLE
    polyAngle = _PI(2) / 60
    x1 = xOrigin + radius * COS(polyAngle)
    y1 = yOrigin + radius * SIN(polyAngle)
    FOR i = 2 TO 61
        x2 = xOrigin + radius * COS(i * polyAngle)
        y2 = yOrigin + radius * SIN(i * polyAngle)
        _MAPTRIANGLE (0, 0)-(0, 0)-(0, 0), a& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
        x1 = x2: y1 = y2
    NEXT
    _FREEIMAGE a& '<<< this is important!
END SUB

SUB fcirc (CX AS LONG, CY AS LONG, R AS LONG, K AS _UNSIGNED LONG)
    DIM subRadius AS LONG, RadiusError AS LONG
    DIM X AS LONG, Y AS LONG

    subRadius = ABS(R)
    RadiusError = -subRadius
    X = subRadius
    Y = 0

    IF subRadius = 0 THEN PSET (CX, CY): EXIT SUB

    ' Draw the middle span here so we don't draw it twice in the main loop,
    ' which would be a problem with blending turned on.
    LINE (CX - X, CY)-(CX + X, CY), K, BF

    WHILE X > Y
        RadiusError = RadiusError + Y * 2 + 1
        IF RadiusError >= 0 THEN
            IF X <> Y + 1 THEN
                LINE (CX - Y, CY - X)-(CX + Y, CY - X), K, BF
                LINE (CX - Y, CY + X)-(CX + Y, CY + X), K, BF
            END IF
            X = X - 1
            RadiusError = RadiusError - X * 2
        END IF
        Y = Y + 1
        LINE (CX - X, CY - Y)-(CX + X, CY - Y), K, BF
        LINE (CX - X, CY + Y)-(CX + X, CY + Y), K, BF
    WEND
END SUB


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.
B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00

Offline Petr

  • I am instructed.
Re: Is this fast enough as general circle fill?
« Reply #18 on: June 25, 2018, 11:23:13 AM »
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: [Select]

'0.105 original
REDIM Px(0) AS SINGLE, Py(0) AS SINGLE
Demo& = _NEWIMAGE(1366, 768, 256)
SCREEN Demo&
St! = TIMER(.001)
Radius = 1000
Cx = Radius
Cy = Radius

' 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 ...
'Minstep! = 1 / (2 * _PI * Radius) 'why so? For circle R = 250: 1 / (6.28 * 250) = 0.0006. This is very small step...
Minstep! = 1 / _PI / (Radius / 10) ' for Circle R = 250: 1 / 3.14 / 25 = 0.01, it is enought...or not?

FOR s = 0 TO _PI / 2 STEP Minstep!
    Px(i) = Radius * COS(s!)
    Py(i) = Radius * SIN(s!)
    i = i + 1
    REDIM _PRESERVE Px(i) AS SINGLE
    REDIM _PRESERVE Py(i) AS SINGLE
NEXT


FOR s = 0 TO UBOUND(Px)
    LINE (Cx - Px(s), Cy - Py(s))-(Cx + Px(s), Cy + Py(s)), 127, BF
NEXT

F! = TIMER(.001)
LOCATE 1, 1
PRINT F! - St!;
_DELAY 10
SCREEN 0
_FREEIMAGE Demo&


Offline Petr

  • I am instructed.
Re: Is this fast enough as general circle fill?
« Reply #19 on: June 25, 2018, 11:41:16 AM »
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: [Select]



'0.105 original
REDIM Px(0) AS SINGLE, Py(0) AS SINGLE, s AS SINGLE, st AS SINGLE, radius AS INTEGER, Cx AS INTEGER, Cy AS INTEGER
Demo& = _NEWIMAGE(1366, 768, 256)
SCREEN Demo&
st! = TIMER(.001)
radius = 555
Cx = 250 'radius
Cy = 400 'radius

' 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 ...
'Minstep! = 1 / (2 * _PI * Radius) 'why so? For circle R = 250: 1 / (6.28 * 250) = 0.0006. This is very small step...
Minstep! = 1 / (_PI / 2 * radius)

FOR s = 0 TO _PI / 2 STEP Minstep!
    Px(i) = radius * COS(s!)
    Py(i) = radius * SIN(s!)
    i = i + 1
    REDIM _PRESERVE Px(i) AS SINGLE
    REDIM _PRESERVE Py(i) AS SINGLE
NEXT


FOR s = 0 TO UBOUND(Px)
    LINE (Cx - Px(s), Cy - Py(s))-(Cx + Px(s), Cy + Py(s)), 127, BF
NEXT

F! = TIMER(.001)
LOCATE 1, 1
PRINT F! - st!;
_DELAY 10
SCREEN 0
_FREEIMAGE Demo&

« Last Edit: June 25, 2018, 11:42:21 AM by Petr »

Offline Petr

  • I am instructed.
Re: Is this fast enough as general circle fill?
« Reply #20 on: June 25, 2018, 11:55:32 AM »
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: [Select]
'Poly Image Demo 2
'by bplus started 2018-06-22

CONST xmax = 800
CONST ymax = 600
SCREEN _NEWIMAGE(xmax, ymax, 32)
_SCREENMOVE 100, 20

stars& = _LOADIMAGE("stars.png")
stuff& = _NEWIMAGE(xmax, ymax, 32)
_DEST stuff&
FOR i = 1 TO 100
    CIRCLE (RND * xmax, RND * ymax), RND * 100, _RGB32(RND * 255, RND * 255, RND * 255)
NEXT
_DEST 0
DO
    CLS
    _SOURCE stuff&
    _PUTIMAGE
    WHILE _MOUSEINPUT: WEND
    polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50
    _DISPLAY
    _LIMIT 30
LOOP


SUB polygonImage (ImageHandle&, xOrigin, yOrigin, radius, nVertex)
    polyAngle = _PI(2) / nVertex
    x1 = xOrigin + radius * COS(polyAngle)
    y1 = yOrigin + radius * SIN(polyAngle)
    FOR i = 2 TO nVertex + 1
        x2 = xOrigin + radius * COS(i * polyAngle)
        y2 = yOrigin + radius * SIN(i * polyAngle)
        _MAPTRIANGLE (xOrigin, yOrigin)-(x1, y1)-(x2, y2), ImageHandle& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
        x1 = x2: y1 = y2
    NEXT
END SUB

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


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

Code: [Select]
'Poly Image Demo 2
'by bplus started 2018-06-22

CONST xmax = 800
CONST ymax = 600
SCREEN _NEWIMAGE(xmax, ymax, 32)
_SCREENMOVE 100, 20

star& = _LOADIMAGE("stars.png")
stars& = _COPYIMAGE(star&, 33)
_FREEIMAGE star&
stuff& = _NEWIMAGE(xmax, ymax, 32)
_DEST stuff&
FOR i = 1 TO 100
    CIRCLE (RND * xmax, RND * ymax), RND * 100, _RGB32(RND * 255, RND * 255, RND * 255)
NEXT
_DEST 0
DO
    '    CLS not need for hardware images and in this case also not, _PUTIMAGE in this case rewrite screen.
    _SOURCE stuff&
    _PUTIMAGE
    WHILE _MOUSEINPUT: WEND
    polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50
    _DISPLAY
    _LIMIT 30
LOOP


SUB polygonImage (ImageHandle&, xOrigin, yOrigin, radius, nVertex) 'Where I just saw it.... :-D
    polyAngle = _PI(2) / nVertex
    x1 = xOrigin + radius * COS(polyAngle)
    y1 = yOrigin + radius * SIN(polyAngle)
    FOR i = 2 TO nVertex + 1
        x2 = xOrigin + radius * COS(i * polyAngle)
        y2 = yOrigin + radius * SIN(i * polyAngle)
        _MAPTRIANGLE (xOrigin, yOrigin)-(x1, y1)-(x2, y2), ImageHandle& TO(xOrigin, yOrigin)-(x1, y1)-(x2, y2), 0
        x1 = x2: y1 = y2
    NEXT
END SUB


Re: Is this fast enough as general circle fill?
« Reply #21 on: June 25, 2018, 12:16:13 PM »
Code: [Select]
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".
« Last Edit: June 25, 2018, 12:19:34 PM by bplus »
B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00

Offline Petr

  • I am instructed.
Re: Is this fast enough as general circle fill?
« Reply #22 on: June 25, 2018, 01:44:00 PM »
Quote
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.

Re: Is this fast enough as general circle fill?
« Reply #23 on: June 25, 2018, 03:55:44 PM »
about the LINE BF,
Code: [Select]
LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bfinstead of
Code: [Select]
LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bfshould save you half of the LINE calls

Re: Is this fast enough as general circle fill?
« Reply #24 on: June 25, 2018, 05:28:03 PM »
about the LINE BF,
Code: [Select]
LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bfinstead of
Code: [Select]
LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bfshould 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.
B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00

Re: Is this fast enough as general circle fill?
« Reply #25 on: June 25, 2018, 07:45:58 PM »
These claims I strongly refuse to believe that anything's faster than that by Steve.

Re: Is this fast enough as general circle fill?
« Reply #26 on: June 26, 2018, 05:44:11 AM »
about the LINE BF,
Code: [Select]
LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bfinstead of
Code: [Select]
LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%-py!),63,bfshould 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.

Re: Is this fast enough as general circle fill?
« Reply #27 on: June 26, 2018, 08:01:16 AM »
Hasn't anyone considered using this method?

Code: [Select]
Radius% = 1000
Cx% = Radius%
Cy% = Radius%

FOR X% = 0 TO Radius%
  Y% = SQR(Radius% * Radius% - X% * X%)
  LINE (Cx% + X%, Cy% - Y%)-(Cx% + X%, Cy% + Y%)
  LINE (Cx% - X%, Cy% - Y%)-(Cx% - X%, Cy% + Y%)
NEXT

Offline Ashish

  • The joy of coding is endless.
Re: Is this fast enough as general circle fill?
« Reply #28 on: June 26, 2018, 10:06:53 AM »
+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.
if (Me.success) {Me.improve()} else {Me.tryAgain()}


aKFrameWork - http://bit.ly/aKFrameWork
Menu System - http://bit.ly/guiMenuBar
p5.js in QB64 - http://bit.ly/p5jsbas

@KingOfCoders

Re: Is this fast enough as general circle fill?
« Reply #29 on: June 26, 2018, 10:09:36 AM »
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

B = B + ...
QB64 x 64 v1.2 2018 0228/86 git b30af92
QB64 v1.2 20180228/86 git 6fde149
QB64 v1.2 [dev build]_d84bb00