Blitter defill - is it possible?

[Ozzyboshi]

Sorry for the noob question.
I have some 2D filled polygon on a bitplane.
I want to "defill" them, I mean i want to set to zero all the bits INSIDE the polygon.
All the bits that form the silhouette must be set.
At the end i want only to see the edges of the polygon and the polygon must be empty inside.
I know that blitter is is capable of filling bits between horizontal lines, but is there some trick to use it for the inverse operation?
The only option that came to my mind is to write a custom (probably complex?) iteration for the 68K.

[roondar]

There is no Blitter 'de-fill mode'. I thought about abusing the Blitter fill mode, but since it requires a single dot set per edge, I don't think this is possible in a single step

You may be able to 'trick' something using two buffers, though:

1) draw the lines for the polygon in buffer 1.
2) use buffer one as source for the fill (A), but buffer 2 as the destination (D) and set Blitter to use inclusive mode fill.

If I'm right, that should get you both a filled and unfilled polygon (in two buffers). The obvious drawback here being you now have two buffers to deal with and clear.

Note: I've not actually tried this, but I think it should work. Generally, the Blitter doesn't care where the D channel points so I'm hoping the same goes for fill mode. Also note: I'm not too sure this'll work properly under all circumstances as the Blitter wants one dot per edge for filling and not all lines generate that.

[Ozzyboshi]

I dont think it would work because the exlusive fill deletes only one side of the edge, not both.
Furthermore what about the top or the bottom edge of a square?
It seems this operation is impossible with the blitter.
What about using the shift register?
I would make 4 other buffers of the size of the bitplane.
The first buffer would have the right shifted image of 1 px, at this point whenever in the source image there is a 1 and in the first buffer there is a 0, this would be the left edge.
The same process could be done with the right edge (left shifting)
For the top and bottom i could add or subtract the blitter addresses by one line.
Maybe it works....

Originally Posted by roondar

There is no Blitter 'de-fill mode'. I thought about abusing the Blitter fill mode, but since it requires a single dot set per edge, I don't think this is possible in a single step

You may be able to 'trick' something using two buffers, though:

1) draw the lines for the polygon in buffer 1.
2) use buffer one as source for the fill (A), but buffer 2 as the destination (D) and set Blitter to use inclusive mode fill.

If I'm right, that should get you both a filled and unfilled polygon (in two buffers). The obvious drawback here being you now have two buffers to deal with and clear.

Note: I've not actually tried this, but I think it should work. Generally, the Blitter doesn't care where the D channel points so I'm hoping the same goes for fill mode. Also note: I'm not too sure this'll work properly under all circumstances as the Blitter wants one dot per edge for filling and not all lines generate that.

[Kalms]

Originally Posted by Ozzyboshi

I dont think it would work because the exlusive fill deletes only one side of the edge, not both.
Furthermore what about the top or the bottom edge of a square?
It seems this operation is impossible with the blitter.
What about using the shift register?
I would make 4 other buffers of the size of the bitplane.
The first buffer would have the right shifted image of 1 px, at this point whenever in the source image there is a 1 and in the first buffer there is a 0, this would be the left edge.
The same process could be done with the right edge (left shifting)
For the top and bottom i could add or subtract the blitter addresses by one line.
Maybe it works....

That ought to work.

If it is OK to have one of the sides' edge-line lie 1 pixel outside of the filled polygon, then left+right can be handled in a single pass. Similarly, up+down can be handled in a single pass. Use (buffer XOR (buffer shifted by 1 pixel)) to generate, one pass horizontally, then another pass vertically, with blits like this:

Blit 1:
A, B = input image
D = output buffer
D = (A ^ (B shifted left by 1 pixel))

Blit 2:
A = input image
B = input image + 1 line
C, D = output buffer
D = C | (A ^ B))

If it is required to always have the edge-line inside of the filled polygon, then 4 passes will be needed. Use (buffer & ~(buffer shifted by 1 pixel)) to generate edge pixels. One pass each for left/right/up/down.

[Ozzyboshi]

Maybe I have a solution that involves 2 steps
First, move down-right exposing top-left border
Second, move up-left exposing bottom-right border and OR with previous screen.
ASM translation assuming that the bitplanes are 40 bytes for 256 lines (320X256 res):

COPY_SCREEN_RIGHT_SHIFT MACRO
        btst    #6,$dff002   
\@.waitblit
        btst    #6,$dff002
        bne.s   \@.waitblit
        move.w  #$1D0C,$dff040  ; BLTCON0 => SHIFT:1, CHANNEL A,B AND D ENABLED,MINTERMS 2-3 ENABLED (COPY FROM B TO D MASKING WITH A)
        move.w  #$0000,$dff042  ; BLTCON1
        move.w  #$ffff,$dff044   ; BLTAFWM
        move.w  #$ffff,$dff046   ; BLTALWM
        lea \1,a0
        suba.l #40,a0
        move.l  a0,$dff050     ; BLTAPT
        move.l  #\1,$dff04c     ; BLTBPT
        move.l  #\2,$dff054     ; BLTDPT
        move.w  #0,$dff064      ; BLTAMOD
        move.w  #0,$dff062      ; BLTBMOD
        move.w  #0,$dff066      ; BLTDMOD
        move.w  #$4014,$dff058  ; BLTSIZE 
        ENDM

COPY_SCREEN_LEFT_SHIFT MACRO
        btst    #6,$dff002  
\@.waitblit
        btst    #6,$dff002
        bne.s   \@.waitblit 
        move.w  #$FFAE,$dff040   ; BLTCON0 => SHIFT:15, ALL CHANNELS ON, MINTERMS 1-2-3-5-7 ENABLED (COPY FROM B TO D MASKING WITH A, THE RESULT IS ADDED TO C)
        move.w  #$0000,$dff042  ; BLTCON1
        move.w  #$ffff,$dff044   ; BLTAFWM
        move.w  #$ffff,$dff046   ; BLTALWM
        lea \1,a0
        adda.l #42,a0
        move.l  a0,$dff050     ; BLTAPT
        move.l  #\1,$dff04c     ; BLTBPT
        move.l  #\2,$dff048     ; BLTCPT
        move.l  #\3,$dff054     ; BLTDPT
        move.w  #0,$dff064      ; BLTAMOD
        move.w  #0,$dff062      ; BLTBMOD
        move.w  #0,$dff060      ; BLTCMOD
        move.w  #0,$dff066      ; BLTDMOD
        move.w  #$4014,$dff058  ; BLTSIZE 
        ENDM

Now, the polygon we want to defill is on LAST_MASK_SHAPE, we allocate 2 more areas in chip ram like this

LAST_MASK_PRE_RSHIFT
        dcb.b 40,$00   
LAST_MASK_RSHIFT
        ds.b    40*256 
LAST_MASK_POST_RSHIFT
        dcb.b 40,$00  
LAST_MASK_PRE_LSHIFT
        dcb.b 40,$00  
LAST_MASK_LSHIFT
        ds.b    40*256
LAST_MASK_POST_LSHIFT
        dcb.b 40,$00

To defill just use the macros

COPY_SCREEN_RIGHT_SHIFT LAST_MASK_SHAPE,LAST_MASK_RSHIFT ; Get a 1 pixel right shifted screen to figure out the left and top edges
COPY_SCREEN_LEFT_SHIFT LAST_MASK_SHAPE,LAST_MASK_RSHIFT,LAST_MASK_LSHIFT ; Get a 1 pixel left shifted screen to figure out the right and bottom edges

Now, in the LAST_MASK_LSHIFT area there is the defilled image.

In conclusion, the whole process takes 2 blitter operations and a few more instructions, probably there are better ways to accomplish that but this is the best solution I found.
If someone has better ideas please let me know.