BBC BASIC for Windows
Programming >> Graphics and Games >> GFXLIB2: PlotSubPixel
http://bb4w.conforums.com/index.cgi?board=graphics&action=display&num=1318695123
GFXLIB2: PlotSubPixel
Post by David Williams on Oct 15th, 2011, 4:12pm

Alright, this thread title is a bit misleading because my attempt at subpixel plotting hasn't yet been translated to Asm, but visually I like the results it can achieve.

Three example progs:

PlotSubPixel_BASIC - Draw's three concentric circles using the 'normal' GFXLIB_PlotPixel function. Press Space Bar to display the circles using subpixel plotting (you'll have to wait a second or two - it's in BASIC remember!).

PlotSubPixel2_BASIC - Draws a spiral pattern, again first using GFXLIB_PlotPixel then after Space Bar is pressed, with subpixel plotting.

PlotSubPixel3_BASIC - Line drawing using subpixel plotting. The yellow reflected line is drawn with pixels using GFXLIB_PlotPixel. The (pseudo-?)antialiased line looks a lot better.

All files (EXE's) in this one zip archive:

http://www.bb4wgames.com/misc/plotsubpixel_basic.zip

The next step, of course, is to get a fast Asm version going.

Source for PlotSubPixel_BASIC.EXE below for the curious (although bear in mind the messy code is largely due to the fact that I had Asm translation in mind while writing it!).

EDIT: Here's an almost perfect-looking set of concentric circles:

http://www.bb4wgames.com/misc/plotsubpixel4_basic.zip


Regards,

David.

=====================================

Code:
      *FLOAT 64
      
      MODE 8
      OFF
      
      INSTALL @lib$ + "GFXLIB2"
      PROCInitGFXLIB
      
      *REFRESH OFF
      
      SYS GFXLIB_Clr%, dispVars{}, FNrgb( 40, 70, 160 )
      FOR r = 1 TO 3
        FOR theta = 0.0 TO 2.0*PI STEP 0.005
          T% = TIME
          x = 320 + 75*r*SIN(theta)
          y = 256 + 75*r*COS(theta)
          SYS GFXLIB_PlotPixel%, dispVars{}, x, y, &FFFFFF
        NEXT theta
      NEXT r
      PROCdisplay
      
      REPEAT UNTIL INKEY-99 OR INKEY(1)=0
      
      SOUND 1, -10, 230, 1
      
      REM. Now draw the three circles using subpixel plotting
      
      SYS GFXLIB_Clr%, dispVars{}, FNrgb( 40, 70, 160 )
      FOR r = 1 TO 3
        FOR theta = 0.0 TO 2.0*PI STEP 0.005
          T% = TIME
          x = 320 + 75*r*SIN(theta)
          y = 256 + 75*r*COS(theta)
          PROC_PlotSubPixel( dispVars.bmBuffAddr%, 640, 512, x, y, &FFFFFF )
        NEXT theta
      NEXT r
      PROCdisplay
      
      OSCLI "REFRESH ON" : ON : REPEAT UNTIL INKEY(1)=0
      END
      :
      :
      :
      :
      DEF PROC_PlotSubPixel( pBuffer%, bW%, bH%, x, y, colour% )
      
      LOCAL x%, y%, i
      
      x% = INTx
      y% = INTy
      
      IF (x - x%) = 0 AND (y - y%) = 0 THEN
        PROC_putBlendedPixel( pBuffer%, bW%, bH%, x%, y%, colour%, 1.0*&10000 )
        ENDPROC
      ENDIF
      
      REM. 2x2 square
      
      REM. bottom-left square
      i = (x%+1 - x)*(y%+1 - y)
      IF i > 0 THEN
        PROC_putBlendedPixel( pBuffer%, bW%, bH%, x%, y%, colour%, i*&10000 )
      ENDIF
      
      REM. bottom-right square
      i = ((x+1) - (x%+1))*(y%+1 - y)
      IF i > 0 THEN
        PROC_putBlendedPixel( pBuffer%, bW%, bH%, x%+1, y%, colour%, i*&10000 )
      ENDIF
      
      REM. top-left square
      i = (x%+1 - x)*((y+1) - (y%+1))
      IF i > 0 THEN
        PROC_putBlendedPixel( pBuffer%, bW%, bH%, x%, y%+1, colour%, i*&10000 )
      ENDIF
      
      REM. top-right square
      i = ((x+1) - (x%+1))*((y+1) - (y%+1))
      IF i > 0 THEN
        PROC_putBlendedPixel( pBuffer%, bW%, bH%, x%+1, y%+1, colour%, i*&10000 )
      ENDIF
      
      ENDPROC
      :
      :
      :
      :
      DEF PROC_putBlendedPixel( pBuffer%, bW%, bH%, x%, y%, colour%, i% )
      LOCAL p%
      IF x% < 0 OR x% >= bW% THEN ENDPROC
      IF y% < 0 OR y% >= bH% THEN ENDPROC
      p% = pBuffer% + 4*(bW%*y% + x%)
      !p% = FN_blendPixel( !p%, colour%, i% )
      ENDPROC
      :
      :
      :
      :
      DEF FN_blendPixel( bg%, fg%, i% )
      LOCAL pFg%, pBg%, r_fg%, g_fg%, b_fg%, r_bg%, g_bg%, b_bg%, r%, g%, b%
      
      pFg% = ^fg%
      pBg% = ^bg%
      
      r_fg% = pFg%?2
      r_bg% = pBg%?2
      r% = r_bg% + (i%*(r_fg% - r_bg%) >> 16)
      
      g_fg% = pFg%?1
      g_bg% = pBg%?1
      g% = g_bg% + (i%*(g_fg% - g_bg%) >> 16)
      
      b_fg% = ?pFg%
      b_bg% = ?pBg%
      b% = b_bg% + (i%*(b_fg% - b_bg%) >> 16)
      
      = r%*&10000 + g%*&100 + b%


Re: GFXLIB2: PlotSubPixel
Post by admin on Oct 15th, 2011, 5:52pm

on Oct 15th, 2011, 4:12pm, David Williams wrote:
Alright, this thread title is a bit misleading

Arguably there is a terminological inexactitude! By 'sub-pixel plotting' do you mean 'anti-aliased plotting'? Are you trying to produce a GFXLIB equivalent of GDI Plus?

Edit: Looking at your source code do I take it you're using a 2x2-kernel bi-linear filter? That, of course, is the simplest possible filter (and therefore the easiest/fastest to implement) but it would be nice to support some higher-order anti-aliasing if possible.

Richard.
Re: GFXLIB2: PlotSubPixel
Post by David Williams on Oct 15th, 2011, 6:24pm

on Oct 15th, 2011, 5:52pm, Richard Russell wrote:
Arguably there is a terminological inexactitude! By 'sub-pixel plotting' do you mean 'anti-aliased plotting'? Are you trying to produce a GFXLIB equivalent of GDI Plus?


A Google search for "subpixel plotting" returned 140,000 results!


on Oct 15th, 2011, 5:52pm, Richard Russell wrote:
Edit: Looking at your source code do I take it you're using a 2x2-kernel bi-linear filter? That, of course, is the simplest possible filter (and therefore the easiest/fastest to implement) but it would be nice to support some higher-order anti-aliasing if possible.


I know it would be nice, but first thing's first!

The Asm version (which I'm working on right now) will be a lot more efficient than the BASIC 'prototype' might have suggested.


David.
Re: GFXLIB2: PlotSubPixel
Post by David Williams on Oct 15th, 2011, 8:42pm

Right, here's an early assembler version:


http://www.bb4wgames.com/misc/plotsubpixel_asm.zip (EXE)


(Yes, I noticed the extraneous pixel on the left edge of the window, and the one missing from the centre - lol).




Re: GFXLIB2: PlotSubPixel
Post by admin on Oct 15th, 2011, 8:44pm

on Oct 15th, 2011, 6:24pm, David Williams wrote:
A Google search for "subpixel plotting" returned 140,000 results!

And the first hit is for the phrase "Antialiasing and subpixel plotting"!

Personally I don't like the term 'sub-pixel' because there ain't no such animal - by definition a pixel is the smallest element of a picture so what is a sub-pixel?

It's back to my old pet hate, I'm afraid: thinking about things in the spatial domain when they ought to be thought about in the frequency domain:

http://www.rtrussell.co.uk/filters/fdscale.html

I should emphasise that there's nothing whatever wrong with what you are doing now - it's exactly the same technique that I used when implementing the BBC's Test Cards J and W - it's just that it results in a sin(x)/x (box-car) frequency response which isn't ideal.

Richard.
Re: GFXLIB2: PlotSubPixel
Post by David Williams on Oct 15th, 2011, 9:38pm

Antialiased lines (rotating spokes):

www.bb4wgames.com/misc/spokes.zip

(Press Space Bar to toggle between aliased and antialiased lines).

Bear in mind that the position of every point in the antialiased lines is calculated in BASIC.

Code:
      DEF PROC_line( x1#, y1#, x2#, y2#, C% )
      LOCAL dx#, dy#, len#, step#, r#
      dx# = x2# - x1#
      dy# = y2# - y1#
      len# = SQR( dx#^2 + dy#^2 )
      step# = 1.0 / len#
      FOR r# = 0.0 TO 1.0 STEP step#
        table{(N%)}.x# = x1# + r#*dx#
        table{(N%)}.y# = y1# + r#*dy#
        table{(N%)}.col% = C%
        N%+=1
      NEXT
      ENDPROC



David.
Re: GFXLIB2: PlotSubPixel
Post by admin on Oct 15th, 2011, 10:04pm

on Oct 15th, 2011, 9:38pm, David Williams wrote:
Antialiased lines (rotating spokes):
www.bb4wgames.com/misc/spokes.zip

That's a jolly tough test, and you can quite easily see the residual aliasing as the lines pass through horizontal. To eliminate that you'd need a more sophisticated filter, not that I think it would be worth it for most applications.

Richard.
Re: GFXLIB2: PlotSubPixel
Post by admin on Oct 16th, 2011, 2:02pm

on Oct 15th, 2011, 8:44pm, Richard Russell wrote:
It's back to my old pet hate, I'm afraid: thinking about things in the spatial domain when they ought to be thought about in the frequency domain

Perhaps I might be allowed to expand on this (feel free to ignore any or all of what follows as desired!).

Having done a little bit of Googling on the subject of antialiased line drawing (as I expect you've done as well) it's notable how many, apparently learned, articles attack the problem in the following way. They visualise a grid of squares (corresponding to 'pixels') and then they overlay on this grid the line, curve or whatever they want to draw. Then for each 'square' they look at the proportion of its area that is overlapped by the line (etc.) and take this as the required amplitude of the pixel.

It almost seems to be 'taken as read' that the amplitude calculated this way is correct, but it's not! To see why we need to use a bit of sampling theory. The first thing to note is that the process is precisely equivalent to sampling a 'continuous image' in two dimensions. The image is the set of lines, curves etc. that you want to draw and the pixels are the sampling points. Indeed it's pretty obvious that what you are trying to create is the same set of samples that would be generated by pointing a 'perfect' digital camera at the image.

Once this equivalence has been appreciated two things immediately follow. First, in order to avoid aliasing, the original image must be low-pass filtered in order to remove any frequency components in excess of half the sampling frequency (the Nyquist limit). Second, the sampling must take place at a point (not averaged over the area of the pixel), or an equivalent aperture correction performed.

I wouldn't want to begin to demonstrate this mathematically, but hopefully it's pretty obvious that the net effect of filtering off the out-of-band components, followed by sampling at an infinitesimally small point, will not result in exactly the same pixel amplitudes as the naive 'area proportion' approach produces.

For example a line which is 'one pixel' wide can only ever 'overlap' two of the squares (at any point along its length), so the naive approach can only result in two pixels having non-zero amplitudes. But the 'accurate' approach will result in more than two pixels being 'illuminated' (because the low-pass filter spreads the line out, theoretically to an infinite extent).

It would take some experimentation to quantify just how significant the disparity is, and under what circumstances it might be desirable to use a more complex algorithm, but there should at least be a recognition that the naive approach isn't accurate. I see precious little of that in what I have read.

Richard.
Re: GFXLIB2: PlotSubPixel
Post by David Williams on Oct 17th, 2011, 03:10am

on Oct 16th, 2011, 2:02pm, Richard Russell wrote:
Perhaps I might be allowed to expand on this (feel free to ignore any or all of what follows as desired!).

Having done a little bit of Googling on the subject of antialiased line drawing (as I expect you've done as well)


Indeed I have.



on Oct 16th, 2011, 2:02pm, Richard Russell wrote:
it's notable how many, apparently learned, articles attack the problem in the following way. They visualise a grid of squares (corresponding to 'pixels') and then they overlay on this grid the line, curve or whatever they want to draw. Then for each 'square' they look at the proportion of its area that is overlapped by the line (etc.) and take this as the required amplitude of the pixel.


Yes, I think that's how the antialiasing on "Wu lines" is achieved. I was just yesterday thinking of translating the algorithm to BBC BASIC, then to Asm.


on Oct 16th, 2011, 2:02pm, Richard Russell wrote:
It almost seems to be 'taken as read' that the amplitude calculated this way is correct, but it's not!


In the context of what I'm interested in, and I think you know what that is, it's correct enough for my purposes!

I'm not an image processing professional, nor is my sprawling graphics library a broadcast-quality image processing library, needless to say! I need the rendering to be as quick as possible, therefore compromises (quality vs. speed) have to be made, and so that 2x2 filter thing I've concocted is probably just about as good as I'm going to get for practical reasons. I mean, as I've mentioned, just drawing 2x2 filtered points (if that's the right term!) is computationally expensive enough as it is, as I've discovered. And in the real-time context of 2D, bitmap-based games, higher order filters or better quality filtering (in software) is probably out of the question.

So that's my concern at the moment: How fast can I get this very simple method of achieving antialised edges. For the purpose of 2D bitmap-based game creation (GFXLIB's raison d'etre - can't find the circumflex 'e'), the antialising effect it produces looks just about adequate.


on Oct 16th, 2011, 2:02pm, Richard Russell wrote:
To see why we need to use a bit of sampling theory. The first thing to note is that the process is precisely equivalent to sampling a 'continuous image' in two dimensions. The image is the set of lines, curves etc. that you want to draw and the pixels are the sampling points. Indeed it's pretty obvious that what you are trying to create is the same set of samples that would be generated by pointing a 'perfect' digital camera at the image.


Understood.


on Oct 16th, 2011, 2:02pm, Richard Russell wrote:
Once this equivalence has been appreciated two things immediately follow. First, in order to avoid aliasing, the original image must be low-pass filtered in order to remove any frequency components in excess of half the sampling frequency (the Nyquist limit). Second, the sampling must take place at a point (not averaged over the area of the pixel), or an equivalent aperture correction performed.


Mostly understood. smiley


on Oct 16th, 2011, 2:02pm, Richard Russell wrote:
I wouldn't want to begin to demonstrate this mathematically, but hopefully it's pretty obvious that the net effect of filtering off the out-of-band components, followed by sampling at an infinitesimally small point, will not result in exactly the same pixel amplitudes as the naive 'area proportion' approach produces.


Despite its simplicity and drawbacks (sin(x)/x frequency response - will have to look this up on Wikipedia!), and I'm of course effectively using this "area proportion approach" myself, whilst not technically correct for the reasons you've outlined, it's darn sight more visually pleasing than totally unfiltered, truncated integer, nearest-neighbour pixel plotting.

I noticed that with my 2x2 filter as it's currently implemented, when the point to be plotted precisely overlaps a single pixel (fractional parts of X,Y coordinates zero), the pixel's plotted at its full intensity while the others are not even processed, and it looks a bit naff.


on Oct 16th, 2011, 2:02pm, Richard Russell wrote:
For example a line which is 'one pixel' wide can only ever 'overlap' two of the squares (at any point along its length), so the naive approach can only result in two pixels having non-zero amplitudes. But the 'accurate' approach will result in more than two pixels being 'illuminated' (because the low-pass filter spreads the line out, theoretically to an infinite extent).

It would take some experimentation to quantify just how significant the disparity is, and under what circumstances it might be desirable to use a more complex algorithm, but there should at least be a recognition that the naive approach isn't accurate. I see precious little of that in what I have read.


Okay, I do follow.

I wouldn't want you to feel you've wasted your time, but bilinear filtering is about as sophisticated as I can get if I want my GFXLIB-based programs to run at the highest possible frame rate (not exceeding the screen's refresh rate, of course).


David.

Re: GFXLIB2: PlotSubPixel
Post by admin on Oct 17th, 2011, 08:42am

on Oct 17th, 2011, 03:10am, David Williams wrote:
Yes, I think that's how the antialiasing on "Wu lines" is achieved. I was just yesterday thinking of translating the algorithm to BBC BASIC, then to Asm.

I'm not sure I'd bother. Some of the examples I've seen of the 'Wu' antialiasing have been awful, far worse than yours (I have no idea why).

Quote:
that 2x2 filter thing I've concocted is probably just about as good as I'm going to get for practical reasons.

I'm not entirely convinced. I can understand that going above a 2x2 kernel would be computationally expensive, but even within that constraint there are alternatives to the 'area proportional ' approach that might give better results without being significantly slower. For example if one could use a look-up-table to determine the relationship between 'proximity to edge' and 'amplitude' it would give the opportunity to use, say, a sin-squared law rather than the linear law which you have now.

Just a thought.

Richard.