Fill Algorithms On The Amiga ============================ By Dave Edwards =============== This article was prompted by my experiences in writing code to display three- dimensional objects on screen, in a manner similar to the game 'Elite' and a number of flight simulator programs available for the Amiga. Preamble -------- Those familiar with Amiga hardware will know that the blitter posses- ses a fill mode, and may be puzzled about the rationale behind this article. Well, it is simply this. The blitter fill mode is, in my opinion, useless. I shall justify this alarming statement below. The blitter's fill mode is simple to say the least. It is a raster- line fill, which relies upon testing for a single set pixel within a memory word to determine the start and the end of the boundary of the shape to be filled. So, in the example below, the '.' characters represent cleared pixels and the '*~ characters represent filled pixels. Given a raster line of the form: .....*...................*...... Fig. 1 the blitter will test for the set pixel in each case, and begin the fill from that point onwards until the next set pixel is found, and then stop filling: .....*********************...... Fig. 2 The fill is achieved using three bits in the BLTCON1 register, the FCI (Fill Carry In) bit, and the EFE/IFE bits (Inclusive Fill Enable and Exclusive Fill Enable respectively). Basically, the blitter copies the initial value of the FCI bit into all cleared pixels until a set pixel is hit. If the IFE mode is set, then the blitter inverts the FCI bit first, then copies the newly inver- ted FCI bit into the pixel position. If the EFE mode is set, the FCI bit is copied into the pixel position first, then the FCI bit is inverted. For example, if our memory area contains an outline for a polygon (in this case a simple one) drawn using the blitter's SING line mode (this mode exists for just this purpose), such as: .........*.......*.............. ........*..........*............ .......*.............*.......... Fig. 3 ......*................*........ .....*...................*...... then the blitter will fill the polygon: .........*********.............. ........************............ .......***************.......... Fig. 4 ......******************........ .....*********************...... which is what was desired. So far, so good. Why did I describe this fill mode as useless? Well, in order to work, this fill mode requires that for each horizontal line of the resulting filled polygon, there should be an even number of set pixels. If, for example, we had a polygon drawn as: .........*..................... ........*...*.................. .......*........*.............. Fig. 5 ......*.............*.......... .....*..................*...... which appears to be a perfectly respectable triangle, the result of filling this would be: *********..................... ........*****................. .......**********............. Fig. 6 ......***************......... .....*******************...... because there is only one set pixel on the top raster line. No problem, in theory at least. Just ensure that all of the coordinates defining the end- points of each component line don't coincide. All well and fine, but if the coordinates have been obtained from transforming a 3D object into a 2D per- spective projection, for example (which is the application I was seeking to use this fill for) then two problems arise. First, once the 3D coordinates are transformed, the resulting 2D coordinates for plotting might just have the very values that produce a polygon such as the one in Fig. 5. Two, if a fix is applied to try and stop this, it produces unacceptable distortion in small objects (squares are no longer square, for example, after applying the fix). Right. That is the principal objection to the blitter fill mode. It manifests itself in several situations, the worst case being that of concave polygons. I shall define convex and concave polygons by example. Fig 7 below is a convex polygon: .........*..................... ........*...*.................. .......*........*.............. Fig. 7 ......*.............*.......... .....*..................*...... and Fig. 8 below is a concave polygon: .........*...................... ........*...*................... .......*........*............... ......*.............*........... .....*...........*......*....... Fig. 8 ......*........*...*.....*...... .......*.....*.......*...*...... ........*..*...........*.*...... .........*...............*...... Concave polygons, for want of a better term, have indentations cut into them. Concave polygons tend to have 'sharp corners', such as those in Fig. 9 below: ......*...... .....**...... ....*.*...... ...*..*...... Fig. 9 ..*...*...... .*....*...... *.....*...... which are formed when two lines inclined at more than 45 degrees to the vert- ical meet at a point. The horizontal analogue of this is shown in Fig. 10: ......*...................... ...........*................. ................*............ .....................*...*... Fig. 10 .....................*....... ................*............ ...........*................. Here, the problem is caused by the blitter drawing a line sloping at an angle of less than 45 degrees to the vertical, from upper left to lower right, then plotting a second line (from right to left, again downwards) at the point of intersection of the two lines. If the lines were drawn solidly, and not using SING mode, then the lines would look respectable, as in Fig. 11: ......*****.................. ...........*****............. ................*****........ .....................*****... Fig. 11 .................*****....... ............*****............ .......*****................. But because SING mode is being used (to allow blitter filling), an extra un- wanted pixel crops up. The appearance of these corners, and the need for com- plex algorithms to sort out the mess, makes the blitter fill inadequate in my view. Doing It The Hard Way --------------------- So, if the blitter can't be used, the only alternative is to write a routine to allow the 68000 to fill the area. This poses two problems. First, how to fill an area, and second, how fast is the code that does it? Before offering my own solution, let me discuss the various possible methods. 1) Raster line fill. Basically doing what the blitter does, or a better ver- sion of it. The method I tried at first, and which works well on convex poly- gons. Concave polygons are a different problem. Deciding whether a single set pixel is an edge boundary or a vertex for a 'sharp corner' as in Figs 9-10 is fraught with problems. 2) Vertical column fill. This involves filling from top to bottom in strips of one byte or one word. Again, this method runs into trouble when used upon concave polygons, especially at horizontal 'sharp corners' such as Fig. 10, when the single pixel at the corner lies in bit 15 or bit 0 of the word (or bit 0 or bit 7 of the byte if doing a byte-wide fill). 3) Contour fill. This involves finding the boundary of the object, and per- forming a fill upon all words containing boundary pixels, then filling all of the internal zero words afterwards using something like: moveq #-1,d2 ;fill value loop ... ;loop start move.w d2,(a0)+ ;a0 points to nonzero ;fill word ... ;other code Again, the problem lies in testing for 'sharp corners'. 4) Internal flood fill. This method guarantees that the shape will be proper- ly filled, but only if the boundary is drawn using the normal line mode in- stead of the SING mode. Also, it is more complex. A choice has to be made to perform the fill either horizontally first, then vertically, or vice versa. Flood-fills are normally performed at the pixel (bit) level, which results in slower execution, and a number of flood-fill routines are written recursively to allow for correct handling of concave polygons. An excellent example of a flood-fill is the AmigaBASIC PAINT command, or the fill activated using the fill tool of the DPaint program. Flood-fills also fail in a small number of cases, involving polygons that are very thin and inclined at an angle, for example: .......*.......................... .......**......................... .......*.*........................ ........*.*....................... .........*.*...................... ..........*.*..................... Fig. 12 ...........*.*.................... ............*.*................... .............*.*.................. ..............*.*................. ...............*.................. Unless the fill has the ability to test across diagonals (and do so in such a way as to prevent leakage from 'sharp corners' into the surrounding memory), the above shape will not be correctly filled using a flood-fill. A Possible Solution ------------------- Because I wanted a fill algorithm that was fast as well as correct, I decided to ignore concave polygons. This is a fairly safe procedure to adopt, as it is always possible to construct concave polygons by linking together a group of 2 or more convex polygons. The concave polygon of Fig. 8 above can be redrawn as: .........*........... ............... ........*...*........ ............... .......*........*.... ............... ......*............*. ...*........... .....*...........*... and ..*....*....... Fig. 13 ......*........*..... ..*.....*...... .......*.....*....... ....*...*...... ........*..*......... ......*.*...... .........*........... ........*...... the two convex polygons then being drawn alongside each other. There exists, for adventurous readers, a mathematical proof that any concave polygon can be drawn as 2 or more convex polygons (in fact, any polygon desired can always be drawn as a collection of triangles!) but for those not wishing to concern themselves with this, I shall move on. To implement the solution I adopted requires a small amount of later- al thinking. Because a raster-line based fill offered the best prospects for execution speed, I decided to implement two fill algorithms. First, finding the leftmost pixel in a shape, and filling from left to right until the last word in the raster line is found. Second, finding the rightmost pixel in a shape, then filling from right to left until the 1st word of the raster line is met. I then implemented these by drawing the polygon twice in two separate memory areas, and performing a different fill upon each copy. For example, I would take the polygon: .........*..................... ........*...*.................. .......*........*.............. Fig. 14 ......*.............*.......... .....*..................*...... and draw it in one memory area. Then, simply copy this memory area using the blitter to a second memory area. Then, take the two memory areas, and perform the different fills upon each: .........********************** ........*********************** .......************************ ......************************* .....************************** Fig. 15 **********..................... *************.................. *****************.............. *********************.......... *************************...... Now, simply AND the two memory areas together with the blitter, and Voila! A correctly filled polygon, as in Fig. 16 below! .........*..................... ........*****.................. .......**********.............. Fig. 16 ......***************.......... .....********************...... Now, the code. The code below is for the raster fill algorithms, and consists of four routines. The first two perform the fill upon one raster line, & the second two perform the fill upon the entire memory area. All parameters and associated data are given. These routines should be reasonably fast. Needless to say, there is still room for improvement upon these, one obvious one being the use of a binary search to find the pixel rather than a linear search, but the complications involved in a case where a word contains two pixels (as in the approach to a 'sharp corner') would slow such a search up badly, which is why I stuck to the simple left-to-right (or vice versa) search for the pixel in the routines below. To speed things up, I use a table to determine the fill words. Table accesses are always fast, so they are useful for ensuring that the fill rou- tines run quickly. See the comments below for how it's done. * FillFromLeft(a0,d0) * a0 = ptr to 1st word to fill * d0 = no of words in this raster line * Finds leftmost possible pixel in shape then * fills from that point onwards, to allow the * creation of a filled polygon in two halves * which are ANDed together to prevent extraneous * horizontal lines appearing. * d1-d5/a0-a1 corrupt FillFromLeft move.w d0,d1 ;copy word count FFL_1 move.w (a0),d2 ;get fill word bne.s FFL_2 ;nonzero so make fill mask for it addq.l #2,a0 ;else next word subq.w #1,d1 ;and subtract count bne.s FFL_1 ;back for more if any left FFL_5 rts ;else done FFL_2 moveq #15,d4 ;bit number of leftmost pixel moveq #1,d5 ror.w #1,d5 ;leftmost pixel set FFL_3 move.w d2,d3 and.w d5,d3 ;this pixel set? bne.s FFL_4 ;skip if set lsr.w #1,d5 ;else next leftmost pixel subq.w #1,d4 ;and bit position bra.s FFL_3 FFL_4 add.w d4,d4 ;make index into table lea FLTable(pc),a1 ;get table ptr move.w 0(a1,d4.w),d2 ;get fill word move.w d2,(a0)+ ;and write into area subq.w #1,d1 ;done them all? beq.s FFL_5 ;exit if so moveq #-1,d2 ;fill word for all subsequent ;area words FFL_6 move.w d2,(a0)+ ;fill subq.w #1,d1 ;done them all? bne.s FFL_6 ;back for more if not rts ;else done * FillFromRight(a0,d0) * a0 = ptr to start of raster line * d0 = no of words to fill on this raster line * Finds rightmost possible pixel in shape then * fills from that point backwards, to allow the * creation of a filled polygon in two halves * which are ANDed together to prevent extraneous * horizontal lines appearing. * d1-d5/a0-a1 corrupt FillFromRight move.w d0,d1 ;copy word count add.w d0,a0 add.w d0,a0 ;point to end of raster line FFR_1 move.w -(a0),d2 ;get fill word bne.s FFR_2 ;nonzero so make fill mask subq.w #1,d1 ;done all of them? bne.s FFR_1 ;back for more if not FFR_5 rts ;else done FFR_2 moveq #0,d4 ;bit position moveq #1,d5 ;rightmost pixel set FFR_3 move.w d2,d3 ;copy word and.w d5,d3 ;this pixel set? bne.s FFR_4 ;skip if so add.w d5,d5 ;else next rightmost pixel addq.w #1,d4 ;and bit position bra.s FFR_3 FFR_4 add.w d4,d4 ;make index into table lea FRTable(pc),a1 ;get ptr to fill table move.w 0(a1,d4.w),d2 ;get fill word move.w d2,(a0) ;and insert into area subq.w #1,d1 ;done them all? beq.s FFR_5 ;exit if so moveq #-1,d2 ;fill word for remainder FFR_6 move.w d2,-(a0) ;fill area subq.w #1,d1 ;done all words? bne.s FFR_6 ;back for more if not rts ;else done. * Fill Mask Tables for above routines FLTable dc.w $0001,$0003,$0007,$000F dc.w $001F,$003F,$007F,$00FF dc.w $01FF,$03FF,$07FF,$0FFF dc.w $1FFF,$3FFF,$7FFF,$FFFF FRTable dc.w $FFFF,$FFFE,$FFFC,$FFF8 dc.w $FFF0,$FFE0,$FFC0,$FF80 dc.w $FF00,$FE00,$FC00,$F800 dc.w $F000,$E000,$C000,$8000 * FillLeftHalf(a0,d0,d7) * a0 = ptr to 1st word of memory area to fill * d0 = no of words per raster line * d7 = no of raster lines * Perform a left-to-right fill for the object. * d1-d5/d7/a0-a1 corrupt FillLeftHalf bsr FillFromLeft subq.w #1,d7 bne.s FillLeftHalf rts * FillRightHalf(a0,d0,d7) * a0 = ptr to 1st word of memory area to fill * d0 = no of words per raster line * d7 = no of raster lines * Perform a right-to-left fill for the object. * d1-d5/d7/a0-a1 corrupt FillRightHalf bsr FillFromRight add.w d0,a0 add.w d0,a0 subq.w #1,d7 bne.s FillRightHalf rts One may wonder why I didn't combine the two approaches in a single fill. Well problems arise when creating the fill word for those memory words that have both a leftmost and a rightmost pixel, and there are two memory pointers to keep track of at any one time. In any case, the routine is quick enough for the momemt. Where You Come In ----------------- And now the spot where ACC members can add to the repository of know- ledge! Given the above information, some time, and a desire to write the fas- test fill in the known universe, can any of you do better? Since I don't have a lot of money, I can't offer any prizes, just the prospect of fame as an in- ducement. But it would be interesting to see if anyone has any ideas that run faster than the above, especially if they are radically different and new. So come on, guys, get cracking! Or, once again, Live fast, code hard & die in a beautiful way, Dave Edwards.