Page 6 of 10
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Fri Jun 28, 2019 9:54 am
by tcat
Hi,
EDIT
My attempt with scan filled poly, closely follows the above `pseudo code'. I use copy of display control, to toggle bit0 to mark fill 0/1 (on-off) state.
Code: Select all
dctl dc.b %00000000 ;Display control copy
;bit7=$20000/$28000
;bit3=mode4/8
;bit1=blank
;bit0=fill0/1
- Filled Polygon
Tomas
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Sat Jun 29, 2019 4:24 pm
by pjw
tcat wrote:I am further thinking about fill. I do scan line fill for circle, and ellipse using BLOCK, that I now have optimised. Filled rectangle really is BLOCK on its own...
Funnily enough, Ive also been thinking about FILL recently, not least because the built-in fill doesnt work for larger screen resolutions. Anything above 1280x768 (Im sure someone can come up with the exact figure) just crashes the system. I havent got as far as thinking about algorithms, so just for the hell of it I decided to try out the one you posted here:
Code: Select all
100 COLOUR_NATIVE
110 ch = 1: CLS#ch
120 paper% = RPIX%(#ch; 1, 1)
130 CIRCLE#ch; 50, 50, 20
140 Fills#ch; paper%, 999, 100, 100
150 :
160 DEFine PROCedure Fills(chn, tgc%, rpc%, x%, y%)
170 REMark tgc%, rpc% - target, replacement colour
180 :
190 REMark PAUSE 1: rem Un-Remark to see the action
200 IF tgc% = RPIX%(#chn; x%, y%) THEN
210 REMark RPIX% = pick colour at x,y coord
220 BLOCK#chn; 1, 1, x%, y%, rpc% : REMark no clip
230 Fills#chn; tgc%, rpc%, x%, y% - 1 : REMark south
240 Fills#chn; tgc%, rpc%, x%, y% + 1 : REMark north
250 Fills#chn; tgc%, rpc%, x% - 1, y% : REMark west
260 Fills#chn; tgc%, rpc%, x% + 1, y% : REMark east
270 END IF
280 END DEFine Fills
290 :
300 :
310 REMark PROCEDURE Fill*(tgc, rpc, x, y: INTEGER);
320 REMark VAR c: INTEGER; (*tgc, rpc - target, replacement colour*)
330 REMark BEGIN
340 REMark (*c = pick colour at x,y coord *)
350 REMark IF c = tgc THEN
360 REMark Display.Dot(rpc, x, y, Display.replace); (*no clip*)
370 REMark Fill(tgc, rpc, x, y-1); (*south*)
380 REMark Fill(tgc, rpc, x, y+1); (*north*)
390 REMark Fill(tgc, rpc, x-1, y); (*west*)
400 REMark Fill(tgc, rpc, x+1, y); (*east*)
410 REMark END
420 REMark END Fill;
430 :
(This version is for GD2 systems only, and needs my Knoware/toolkits/RPIX% command.)
Sadly, it doesnt do very well, as it eats up stack space, and spends half its time back tracking. It wont do shapes much larger than the circle demonstrated here before crashing out. What else is there?
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Sat Jun 29, 2019 4:31 pm
by pjw
tofro wrote:Tomas,
the QL's native FILL works with a simple scanline algorithm that simply remembers a start and an endpoint per scanline while FILL is active...
Sorry, Tobias. I did read your piece some days ago and just forgot. I'll read the Wikipedia link you posted and shut up until I can improve on silence..
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Sat Jun 29, 2019 6:04 pm
by tcat
Hi Per,
Sadly, it doesnt do very well, as it eats up stack space
Yes, that is the drawback of flood filling, for larger areas it can soon exhaust stack space, the experience you have. Although it goes by 4 pixels at a time, is not very fast. One advantage, it can fill any shape.
As oposed to scan line fill, much faster especially when using BLOCK, and it can work with fixed size buffer. All good, except it may struggle with concave shapes.
On the genuine QL, I set aside 256 longs as static buffer for it.
Improved version of flood fill, may control stack usage, and revisit unflooded parts.
EDIT, Hi Per,
Knoware/toolkits/RPIX% does colour picking?
Very useful!
Tom
Tomas
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Sat Jun 29, 2019 11:12 pm
by pjw
tcat wrote:.. EDIT, Hi Per,
Knoware/toolkits/RPIX% does colour picking?
Very useful!
Tom
Yes. Its not as clever as the original RPIXL from Qptr, but it will read a pixel relative to a given window, or relative to the screen, and return the colour in native or RGB mode.
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Sun Jun 30, 2019 1:23 am
by stevepoole
Hi,
In early QL days, TALENT sold a microdrive cartridge called GraphiQL, which had an incredible FloodFill.
You would press keys FA to find an area, then FC to fill with Colour or FT to fill with texture.
I used the routines to literally flood a cave system, first drawing the cave network, then flooding it progressively....
I am pretty sure that the routines used a second screen memory area to define the floodable pixels, as the cave sytstem occupied a whole screen.
Starting from a point, the routine would search left & right, then move up & down along 'tree-branches', one row at a time. It was quite fast on small shapes !
Sadly, my cartridge is unreadable, and as far as I know, Talent never released their code as public domain. I have always regretted that !
In a QL magazine review, the routines were described as remarkably simple, but I was not able to emulate them ! (Pixel handling is not straightforward).
Regards,
Steve Poole.
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Sun Jun 30, 2019 11:10 am
by pjw
If you can define a shape as a blob, theres an inbuilt routine to fill it with any colour or texture, in any mode. I dont know what limitations the routine has re size, memory or efficiency, but it might be worth investigating.
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Sun Jun 30, 2019 11:18 am
by tofro
Per,
Fiddled a bit just for the fun of it....
here's an implementation of a flood fill algorithm that is a bit faster (and also quite less stack heavy than the simple recursive approach). It can fill concave shapes (as in the example) and can also fill a whole scanline at once if you optimize it a bit.
It uses a local stack (which needs to be adjusted to the complexity of the shape to be filled) which is not the least bit boundary-checked atm. (I was playing with the HISTORY device to act as a stack, but couldn't get that working properly)
There's obviously a lot of potential to optimize (like optimizing the BLOCK to draw longer lines instead of single pixels as of now) but should get you going.
Tobias
Code: Select all
100 COLOUR_NATIVE
110 ch=1 : CLS #ch
120 paper% = RPIX%(#ch;1, 1)
130 CIRCLE #ch; 50, 50, 20
135 CIRCLE #ch; 50, 50, 10
140 FloodFill #ch; paper%, 7, 100, 100
145 :
150 REMark The scanline floodfill algorithm using a stack
160 DEFine PROCedure FloodFill (channel, oldColor, newColor, x, y)
170 LOCal x1, spanAbove, spanBelow, stack(2048), stackCtr
180 IF oldColor = newColor THEN
190 REMark Nothing to do
200 RETurn
210 END IF
235 stackCtr =0
240 stack(stackCtr) = x : stackCtr = stackCtr + 1 : stack(stackCtr) = y : stackCtr = stackCtr + 1
242 REMark PRINT#0,"Push:", x, y, stackCtr
245 PAUSE #0,-1
250 REMark Loop until stack empty
260 REPeat stackLoop
275 IF stackCtr <= 0 THEN
277 EXIT stackLoop
278 END IF
279 stackCtr = stackCtr - 1 : y = stack (stackCtr) : stackCtr = stackCtr - 1 : x = stack (stackCtr)
290 REMark PRINT #0; "Pop:", x, y, stackCtr
295 REMark PAUSE #0, -1
330 x1 = x
340 REMark search left boundary
350 REPeat leftLoop
360 IF x1 < 0 : EXIT leftLoop
370 IF RPIX% (#channel; x1, y) <> oldColor THEN
380 EXIT leftLoop
390 ELSE
400 x1 = x1 - 1
410 END IF
420 END REPeat leftLoop
430 x1 = x1 + 1
440 spanAbove = 0
450 spanBelow = 0
460 REMark search right boundary
470 REPeat rightLoop
480 IF x1 >= SCR_XLIM : EXIT rightLoop
490 IF RPIX% (#channel; x1, y) <> oldColor THEN
500 EXIT rightLoop
510 END IF
520 BLOCK #channel, 1, 1, x1, y, newColor
522 REMark look into scanline above
525 IF (y > 0) THEN
530 IF (spanAbove = 0) THEN
550 IF RPIX% (#channel; x1, y - 1) = oldColor THEN
555 stack (stackCtr) = x1 :stackCtr = stackCtr + 1 : stack(stackCtr) = y - 1 : stackCtr = stackCtr + 1
565 REMark PRINT#0,"Push:", x1, y - 1, stackCtr
570 spanAbove = 1
580 END IF
590 ELSE
630 IF RPIX%(#channel; x1, y - 1) <> oldColor THEN
640 spanAbove = 0
650 END IF
660 END IF
670 END IF
675 IF y < (SCR_YLIM - 1) THEN
680 IF spanBelow = 0 THEN
700 IF RPIX%(#channel; x1, y + 1) = oldColor THEN
705 stack (stackCtr) = x1 :stackCtr = stackCtr + 1 : stack(stackCtr) = y + 1 : stackCtr = stackCtr + 1
715 REMark PRINT #0, "Push: ", x1, y + 1, stackCtr
720 spanBelow = 1
730 END IF
740 ELSE
770 IF RPIX% (#channel; x1, y + 1) <> oldColor THEN
780 spanBelow = 0
790 END IF
795 END IF
797 END IF
810 x1 = x1 + 1
820 END REPeat rightLoop
830 END REPeat stackLoop
850 END DEFine
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Sun Jun 30, 2019 12:44 pm
by pjw
tofro wrote:Fiddled a bit just for the fun of it....
Very nice!
Something to work with.
Theres also something called
QuickFill which by all accounts seems to be one of the more efficient and versatile algorithms around. Unfortunately, I dont know enough C++ to understand in detail how it works or to translate it into SBASIC or assembler. These algorithms are tricky, so details are important. It is often said about C++ that although all you asked for was a banana, what you get is a gorilla and half the jungle to boot. So it may not be just a simple matter of translation either..
Re: SCREEN1 = SYSVAR @ JSROM
Posted: Sun Jun 30, 2019 1:12 pm
by tofro
Per,
the above algorithm is (from a pure FILL perspective) actually one of the most efficient ones - It guarantees that every pixel to be filled is only visited exactly once. The
drawing could be made faster, though.
(And the whole thing reminds me a bit of playing "The Hobbit" on the ZX Spectrum as a kid. I believe they used a very similar way of filling areas
)
What you're linking to seems to be more complicated because it wants to support a pattern fill.
Tobias