FILL_TO_BORDER 'Problem'

Hi

I have an application which draws simple polygons in white on a black background - in the example below a triangle in which one vertex has a pretty small angle - and then colours the interior of the triangle in a colour (here yellow) using fill_to_border@. Whilst on screen it quite often appears fine (though sometimes you can see uncoloured dots) when one interrogates the actual colours near the 'sharp point' one finds that two or three pixels within the triangle have not in fact been coloured (and in the code below remain black).

I am using the colours to represent results (on a virtual screen) and thus it is essential that all pixels within any triangle are correctly coloured. I could obviously develop my own crude colour routine or do a complete scan of the pixel map to spot and correct any pixels that are not correctly coloured but any other ideas would be appreciated. [In the code below the 'mat' array output has two zero (black ie uncoloured) pixels within the triangle near the point]

Many Thanks

Bill

  program fill_error
  INCLUDE <WINDOWS.INS>
  integer*4 ictrl1,ix,iy,jx,jy,iwhite,iyellow,kol
  character*30 screentitle
  character*1 mat(20,20)
  dimension ix(4),iy(4)

c c set up graphics window c screentitle = 'fill_to_border problem' iwiw = winio@('%ca@&',screentitle) iwiw = winio@('%`gr&',600L,600L,1L) iwiw = winio@('%lw',ictrl1) call select_graphics_object@(1L) call use_rgb_colours@(1L,1L) c c set colours c iwhite = rgb@(255L,255L,255L) iyellow = rgb@(255L,255L,0L) c c colour it white c call draw_filled_rectangle@(1L,1L,600L,600L,0L) call perform_graphics_update@ c c set values for points of triangle and draw it c ix(1) = 15 ix(2) = 156 ix(3) = 15 ix(4) = 15 iy(1) = 240 iy(2) = 428 iy(3) = 146 iy(4) = 240 call draw_polyline@(ix,iy,4L,iwhite) call perform_graphics_update@ c c set values for inner point and fill triangle c jx = 72 jy = 293 call fill_to_border@(jx,jy,iyellow,iwhite)

c c get the colours near the sharp point and represent by c characters in matrix 'mat' c 0 = black, . = white, * = yellow c open(7,file='matrix.txt') do 10 jx = 137,156 do 20 jy= 409,428 i = jx - 136 j = jy - 408 call get_rgb_value@(jx,jy,kol) if(kol .eq. 0L)mat(i,j) = '0' if(kol .eq. iwhite)mat(i,j) = '.' if(kol .eq. iyellow)mat(i,j) = '*' 20 continue write(7,1)(mat(i,j),j=1,20) 1 format(20a1) 10 continue
close(7) end

Bill,

This is a problem of the flood fill algorithm, and probably requires a big fix. As you already drew the triangles, you know the corner coordinates. What is to stop you redrawing the whole triangle as a filled polygon?

I suppose you'll say 'well I know the position of the 'seed' point, but I don't know which triangle it is in'. You can find that using 'area coordinates'. Any point has 3 area coordinates, L1, L2, L3. Assuming the nodes (corners), are numbered N1, N2, N3, then L1 is the area bounded by P, N2, N3 divided by the area of the triangle N1, N2, N3. You are in a given triangle if L1, L2 and L3 are all between 0 and 1. Remember to calculate the area of the main triangle once only, or even store the values. Area coordinates are described in Zienkiewicz's book on finite elements - I'm looking at a very old 2nd edition where it is on p117 - and the requisite formulae are given.

Eddie

ClearWin+ uses the Microsoft ExtFloodFill for fill_to_border@ and fill_surface@ corresponding to FLOODFILLBORDER and FLOODFILLSURFACE.

In this case the point in the image is very sharp with the result that the pixels in question have black pixels at their corners.

Anti aliasing might make a difference. This is available in the latest ClearWin+.

Correction: these routines have not been implemented with anti aliasing.

Thanks Both,

I might have guessed it was a Microsoft problem - they enjoy creating (in particular) O/S problems for me!

The triangle example was just put together as an example - in practice the regions are created as a result of drawing perhaps hundreds of lines to create regions of many forms - and whenever there is a tight corner the problem appears.

There are a number of ways I can get round it on this occasion given the characteristics of the problem and results I am 'plotting'- in particular if a pixel is not coloured the colour on the nearest pixel 'above' will have the correct colour.

Thanks for the quick responses and ideas both..

Bill

Bill,

%ww[no_border] might help with what you are trying to do. See the changes I did. Also, this is a C window so the top left is 0,0, not 1,1.

John

  program fill_error 
    INCLUDE <WINDOWS.INS> 
    integer*4 iwiw, ictrl1,jx,jy,iwhite,iyellow,kol , i,j
    character*30 screentitle 
    character*1 mat(20,20) 
    integer*4 ix(4),iy(4) 
!c 
!c set up graphics window 
!c 
    screentitle = 'fill_to_border problem' 
    iwiw = winio@ ('%ca@&',screentitle) 
    iwiw = winio@ ('%ww[no_border]&')
    iwiw = winio@ ('%`gr&',601L,601L,1L) 
    iwiw = winio@ ('%lw',ictrl1) 
    call select_graphics_object@(1L) 
    call use_rgb_colours@(1L,1L) 
!c 
!c set colours 
!c 
    iwhite  = rgb@(255L,255L,255L) 
    iyellow = rgb@(255L,255L,0L) 
!c 
!c colour it white 
!c 
    call draw_filled_rectangle@(0L,0L,600L,600L,0L) 
    call perform_graphics_update@ 
!c 
!c set values for points of triangle and draw it 
!c 
    ix(1) = 15 
    ix(2) = 156 
    ix(3) = 15 
    ix(4) = 15 
    iy(1) = 240 
    iy(2) = 428 
    iy(3) = 146 
    iy(4) = 240 
    call draw_polyline@ (ix,iy,4L,iwhite) 
    call perform_graphics_update@ 
!c 
!c set values for inner point and fill triangle 
!c 
    jx = 72 
    jy = 293 
    call fill_to_border@ (jx,jy,iyellow,iwhite) 
!c 
!c get the colours near the sharp point and represent by 
!c characters in matrix 'mat' 
!c 0 = black, . = white, * = yellow 
!c 
    open(7,file='matrix.txt') 
    do 10 jx = 137,156 
      do 20 jy= 409,428 
        i = jx - 136 
        j = jy - 408 
        call get_rgb_value@(jx,jy,kol) 
        if(kol .eq. 0L)mat(i,j) = '0' 
        if(kol .eq. iwhite)mat(i,j) = '.' 
        if(kol .eq. iyellow)mat(i,j) = '*' 
 20   continue 
      write(7,1)(mat(i,j),j=1,20) 
  1   format(20a1) 
 10 continue 
    close(7) 
    end

Thanks for your thoughts but this still fails to colour all points.

The routine draw_filled_polygon@ does colour all points (including of course the border) and for some implementations (but not mine) this might be a route forwards with you then re-drawing the borders if you required them to appear in a different colour.

Thanks again ... Bill

I think only OpenGL has no such problems. It is inside the compiler for almost two decades waiting for users to wake up. To simplify the move compiler developers probably have to create the library of elements similar to draw_line@, draw_polygon@, draw_character@ using OpenGL and also combine %gr and %og to use both old and new libraries on the same screen. OpenGL not only survived the war with Microsoft, even more, based on its growing acceptance with other OSes it won.