SCREEN1 = SYSVAR @ JSROM

Anything QL Software or Programming Related.
tcat
Super Gold Card
Posts: 550
Joined: Fri Jan 18, 2013 5:27 pm
Location: Prague, Czech Republic

Re: SCREEN1 = SYSVAR @ JSROM

Postby tcat » Fri Jun 28, 2019 9:54 am

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

poly.png
Filled Polygon


Tomas
Last edited by tcat on Sat Jun 29, 2019 6:45 pm, edited 1 time in total.


User avatar
pjw
Super Gold Card
Posts: 526
Joined: Fri Jul 11, 2014 8:44 am
Location: Norway
Contact:

Re: SCREEN1 = SYSVAR @ JSROM

Postby pjw » Sat Jun 29, 2019 4:24 pm

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?


Per
Be wary of large West-Coast corporations bearing gifts!
- Ancient Trojan proverb
User avatar
pjw
Super Gold Card
Posts: 526
Joined: Fri Jul 11, 2014 8:44 am
Location: Norway
Contact:

Re: SCREEN1 = SYSVAR @ JSROM

Postby pjw » Sat Jun 29, 2019 4:31 pm

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..


Per
Be wary of large West-Coast corporations bearing gifts!
- Ancient Trojan proverb
tcat
Super Gold Card
Posts: 550
Joined: Fri Jan 18, 2013 5:27 pm
Location: Prague, Czech Republic

Re: SCREEN1 = SYSVAR @ JSROM

Postby tcat » Sat Jun 29, 2019 6:04 pm

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.

Code: Select all

pl_scan  ds.l     256               ;Scan lines

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


User avatar
pjw
Super Gold Card
Posts: 526
Joined: Fri Jul 11, 2014 8:44 am
Location: Norway
Contact:

Re: SCREEN1 = SYSVAR @ JSROM

Postby pjw » Sat Jun 29, 2019 11:12 pm

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.


Per
Be wary of large West-Coast corporations bearing gifts!
- Ancient Trojan proverb
stevepoole
Trump Card
Posts: 199
Joined: Mon Nov 24, 2014 2:03 pm

Re: SCREEN1 = SYSVAR @ JSROM

Postby stevepoole » Sun Jun 30, 2019 1:23 am

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.


User avatar
pjw
Super Gold Card
Posts: 526
Joined: Fri Jul 11, 2014 8:44 am
Location: Norway
Contact:

Re: SCREEN1 = SYSVAR @ JSROM

Postby pjw » Sun Jun 30, 2019 11:10 am

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.


Per
Be wary of large West-Coast corporations bearing gifts!
- Ancient Trojan proverb
User avatar
tofro
QL Wafer Drive
Posts: 1585
Joined: Sun Feb 13, 2011 10:53 pm
Location: SW Germany

Re: SCREEN1 = SYSVAR @ JSROM

Postby tofro » Sun Jun 30, 2019 11:18 am

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


ʎɐqǝ ɯoɹɟ ǝq oʇ ƃuᴉoƃ ʇou sᴉ pɹɐoqʎǝʞ ʇxǝu ʎɯ 'ɹɐǝp ɥO
User avatar
pjw
Super Gold Card
Posts: 526
Joined: Fri Jul 11, 2014 8:44 am
Location: Norway
Contact:

Re: SCREEN1 = SYSVAR @ JSROM

Postby pjw » Sun Jun 30, 2019 12:44 pm

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..


Per
Be wary of large West-Coast corporations bearing gifts!
- Ancient Trojan proverb
User avatar
tofro
QL Wafer Drive
Posts: 1585
Joined: Sun Feb 13, 2011 10:53 pm
Location: SW Germany

Re: SCREEN1 = SYSVAR @ JSROM

Postby tofro » Sun Jun 30, 2019 1:12 pm

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


ʎɐqǝ ɯoɹɟ ǝq oʇ ƃuᴉoƃ ʇou sᴉ pɹɐoqʎǝʞ ʇxǝu ʎɯ 'ɹɐǝp ɥO

Who is online

Users browsing this forum: No registered users and 6 guests