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

#### bplus

##### Re: Is this fast enough as general circle fill?
« Reply #15 on: June 25, 2018, 09: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-22CONST xmax = 800CONST ymax = 600SCREEN _NEWIMAGE(xmax, ymax, 32)_SCREENMOVE 100, 20stars& = _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 0DO    CLS    _SOURCE stuff&    _PUTIMAGE    WHILE _MOUSEINPUT: WEND    polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50    _DISPLAY    _LIMIT 30LOOPSUB 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    NEXTEND SUB`
Attached is code with Stars.png for testing with image file.
« Last Edit: June 25, 2018, 09:35:26 AM by bplus »
B = B + ...

#### SMcNeill

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

#### bplus

##### Re: Is this fast enough as general circle fill?
« Reply #17 on: June 25, 2018, 09: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 easilyCONST xmax = 800CONST ymax = 600SCREEN _NEWIMAGE(xmax, ymax, 32)_SCREENMOVE 360, 60start## = TIMER'this is 10 X 10 X 10 runs on circle with different colorsFOR 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    NEXTNEXTCOLOR _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 SUBSUB 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    WENDEND 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 + ...

#### Petr

• I am instructed.
##### Re: Is this fast enough as general circle fill?
« Reply #18 on: June 25, 2018, 10: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 originalREDIM Px(0) AS SINGLE, Py(0) AS SINGLEDemo& = _NEWIMAGE(1366, 768, 256)SCREEN Demo&St! = TIMER(.001)Radius = 1000Cx = RadiusCy = 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 SINGLENEXTFOR s = 0 TO UBOUND(Px)    LINE (Cx - Px(s), Cy - Py(s))-(Cx + Px(s), Cy + Py(s)), 127, BFNEXTF! = TIMER(.001)LOCATE 1, 1PRINT F! - St!;_DELAY 10SCREEN 0_FREEIMAGE Demo&`

#### Petr

• I am instructed.
##### Re: Is this fast enough as general circle fill?
« Reply #19 on: June 25, 2018, 10: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 originalREDIM Px(0) AS SINGLE, Py(0) AS SINGLE, s AS SINGLE, st AS SINGLE, radius AS INTEGER, Cx AS INTEGER, Cy AS INTEGERDemo& = _NEWIMAGE(1366, 768, 256)SCREEN Demo&st! = TIMER(.001)radius = 555Cx = 250 'radiusCy = 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 SINGLENEXTFOR s = 0 TO UBOUND(Px)    LINE (Cx - Px(s), Cy - Py(s))-(Cx + Px(s), Cy + Py(s)), 127, BFNEXTF! = TIMER(.001)LOCATE 1, 1PRINT F! - st!;_DELAY 10SCREEN 0_FREEIMAGE Demo&`
« Last Edit: June 25, 2018, 10:42:21 AM by Petr »

#### Petr

• I am instructed.
##### Re: Is this fast enough as general circle fill?
« Reply #20 on: June 25, 2018, 10: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-22CONST xmax = 800CONST ymax = 600SCREEN _NEWIMAGE(xmax, ymax, 32)_SCREENMOVE 100, 20stars& = _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 0DO    CLS    _SOURCE stuff&    _PUTIMAGE    WHILE _MOUSEINPUT: WEND    polygonImage stars&, _MOUSEX, _MOUSEY, 250, 50    _DISPLAY    _LIMIT 30LOOPSUB 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    NEXTEND 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-22CONST xmax = 800CONST ymax = 600SCREEN _NEWIMAGE(xmax, ymax, 32)_SCREENMOVE 100, 20star& = _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 0DO    '    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 30LOOPSUB 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    NEXTEND SUB`

#### bplus

##### Re: Is this fast enough as general circle fill?
« Reply #21 on: June 25, 2018, 11:16:13 AM »
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, 11:19:34 AM by bplus »
B = B + ...

#### Petr

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

#### SkyCharger001

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

#### bplus

##### Re: Is this fast enough as general circle fill?
« Reply #24 on: June 25, 2018, 04:28:03 PM »
Code: [Select]
`LINE(cx%-px!,cy%-py!)-(cx%+px!,cy%+py!),63,bf`instead of
Code: [Select]
`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.
B = B + ...

#### _vince

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

#### SkyCharger001

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

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

Code: [Select]
`Radius% = 1000Cx% = 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`

#### Ashish

• The joy of coding is endless.
##### Re: Is this fast enough as general circle fill?
« Reply #28 on: June 26, 2018, 09: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
p5.js in QB64 - http://bit.ly/p5jsbas

@KingOfCoders

#### bplus

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