Author |
Topic: Translating a line from a fast box blur algorithm (Read 1195 times) |
|
David Williams
Developer
member is offline
meh
Gender: 
Posts: 452
|
 |
Translating a line from a fast box blur algorithm
« Thread started on: Oct 12th, 2011, 1:01pm » |
|
I'm looking at some source code for a "fast box blur" algorithm. I intend first to translate the code to BASIC, and assuming I get it working fine, then to Asm
(which will require taking a very deep breath first!).
There's a demo of it in action here:
http://www.quasimondo.com/BoxBlurForCanvas/FastBlurDemo.html
However this line (and perhaps some others similar to it) in the source code might cause me some problems:
Code:vmin[x] = ( ( p = x + rad1) < wm ? p : wm ) << 2;
Would a correct translation of that line be the following?
Code:p = x + rad1
IF p < wm THEN
vmin(x) = p << 2
ELSE
vmin(x) = wm << 2
ENDIF
Pure guesswork.
I appreciate that this is a BB4W forum, but some someone might be familiar with the syntax.
Source URL: http://www.quasimondo.com/BoxBlurForCanvas/FastBlur.js
Regards,
David.
|
|
|
|
Michael Hutton
Developer
member is offline
Gender:
Posts: 248
|
|
Re: Translating a line from a fast box blur algori
« Reply #1 on: Oct 12th, 2011, 5:17pm » |
|
I'm pretty sure you are right.
btw, I managed to get a HLSL shader gaussian blur going - take a look at:
http://tech.groups.yahoo.com/group/bb4w/files/Graphics/blur%20effect.exe
and I do apologise for the picture... well, I don't really. I think the effect really does say wonders on how I felt that night!
I am pretty sure I could get it into the GFXD3D9LIB.
Come to think of it I don't why a lot of the GFXLIB couldn't be translated to HLSL effects. It would be very, very fast (code, not translation).
Michael
|
|
 Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Translating a line from a fast box blur algori
« Reply #2 on: Oct 12th, 2011, 5:31pm » |
|
on Oct 12th, 2011, 1:01pm, David Williams wrote:
I can't make that work. Nothing seems to happen when I move the sliders.
Quote:
I seriously doubt that! The translation looks correct to me.
I'm not familiar with the term 'box blur'. Any kind of blur is a 2D spatial filter, so I presume the 'box' bit refers to the particular shape of the aperture. Is it perhaps a filter with a rectangular aperture in both X and Y directions?
The way I'd probably do it is to use a general purpose filter routine (MMX of course!) and simply feed in the appropriate coefficients. It might not be the fastest way, but means you can use different apertures with no extra effort or performance penalty.
As with any 2D filtering, if the aperture can be decomposed into separate horizontal and vertical components then the fastest approach will probably be to run two 1D filters, one after the other. However, such a blurring filter is not very convincing (a point gets blurred into a rectangle, not a circle) and a proper 2D aperture is desirable.
Edit: When I did 'blurring' at the BBC, it was done with hardware. See Synthetic defocussing here: http://www.bbceng.info/Designs/designs_reminiscences/richard_russell_part2/rtrbbc.html
Richard.
|
| « Last Edit: Oct 12th, 2011, 5:42pm by admin » |
Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Translating a line from a fast box blur algori
« Reply #3 on: Oct 12th, 2011, 5:36pm » |
|
on Oct 12th, 2011, 5:17pm, Michael Hutton wrote:| http://tech.groups.yahoo.com/group/bb4w/files/Graphics/blur%20effect.exe |
|
All I get here is the error message 'Failed to create dummy texture' (Windows XP, integrated graphics, DirectX 9.0c, DirectDraw and Direct3D acceleration enabled).
Richard.
|
|
Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Translating a line from a fast box blur algori
« Reply #5 on: Oct 12th, 2011, 5:51pm » |
|
on Oct 12th, 2011, 5:38pm, Michael Hutton wrote:
That confirms what I suspected: it's an aperture which is rectangular in both X and Y directions. It gives a very unconvincing effect, as I mentioned before, although obviously it's computationally convenient, being decomposable into separate horizontal and vertical operations.
Richard.
|
|
Logged
|
|
|
|
Michael Hutton
Developer
member is offline
Gender:
Posts: 248
|
|
Re: Translating a line from a fast box blur algori
« Reply #6 on: Oct 12th, 2011, 5:57pm » |
|
on Oct 12th, 2011, 5:36pm, Richard Russell wrote:All I get here is the error message 'Failed to create dummy texture' (Windows XP, integrated graphics, DirectX 9.0c, DirectDraw and Direct3D acceleration enabled).
Richard.
|
|
Dammit, sorry, I am trying to fix the problem asap. I don't know why it does this - works fine this end then fails. I am sure I tested the exe...
Ho hum.
Will try to fix.
Michael
|
|
Logged
|
|
|
|
David Williams
Developer
member is offline
meh
Gender:
Posts: 452
|
|
Re: Translating a line from a fast box blur algori
« Reply #7 on: Oct 12th, 2011, 11:22pm » |
|
[OT]
GFXLIB finally a gets a circle plotter - or at least a filled circle plotter.
Quick demo of GFXLIB_DrawFilledCircle:
http://www.bb4wgames.com/misc/drawfilledcircle.zip (EXE; 66 Kb)
On my laptop, it appears to be about twice as fast as BB4W's native CIRCLE FILL command (which relies on the GDI, IIRC).
The fact that GFXLIB_DrawFilledCircle is 'only' twice as fast (on my laptop) suggests to me that filled circles drawn
with CIRCLE FILL use hardware accelerated rendering, so there's a lengthy pipeline of bloat or abstraction between
CIRCLE FILL and the GPU.
David.
|
|
Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Translating a line from a fast box blur algori
« Reply #8 on: Oct 13th, 2011, 08:32am » |
|
on Oct 12th, 2011, 11:22pm, David Williams wrote:The fact that GFXLIB_DrawFilledCircle is 'only' twice as fast (on my laptop) suggests to me that filled circles drawn
with CIRCLE FILL use hardware accelerated rendering. |
|
I don't see the argument. If CIRCLE FILL used non-accelerated (CPU) rendering then you would expect it to be somewhat - but not a lot - slower than your GFXLIB version, and a factor-of-two difference doesn't seem unreasonable to me. If it were 'hardware-accelerated' I would expect it to be faster than your version, at least for largish circles, not slower.
If you were expecting your version to be a lot faster than the GDI32 version, why? The code they use is probably quite similar, and it's running on the same CPU. The extra overheads and complications of the GDI32 version (principally things like having to support a range of different bit depths) aren't that great.
Richard.
|
|
Logged
|
|
|
|
David Williams
Developer
member is offline
meh
Gender:
Posts: 452
|
|
Re: Translating a line from a fast box blur algori
« Reply #9 on: Oct 13th, 2011, 10:45am » |
|
on Oct 13th, 2011, 08:32am, Richard Russell wrote:| If you were expecting your version to be a lot faster than the GDI32 version, why? The code they use is probably quite similar, and it's running on the same CPU. The extra overheads and complications of the GDI32 version (principally things like having to support a range of different bit depths) aren't that great. |
|
My expectation for GFXLIB_DrawFilledCircle to be more than just twice as fast as the GDI32 circle plotter (which I think produces rubbish-looking circles at small radii - but that's a different story, although you'll probably take issue with it!), stems in part from the following observation (which I've shared with you before, possibly only privately though):
My game "Bugs" (a port of the Flash-based game "Ladybug Sumo"), featured my first attempt at an x86 Asm bitmap rotation routine (IIRC). And what a dire piece of code it is! The inner loop has 30 instructions per non-black (zero-valued) source bitmap pixel (including five IMUL instructions!); a code sequence that probably produces several CPU stalls per pixel, absolutely no attempt at pipelining / instruction pairing. It actually writes two pixels for each non-black pixel in the source bitmap as a frightful means of dealing with the problem of holes appearing in the rotated bitmap. In addition, no use of the stack to store local variables; they're globals read from (and in one case written to) main memory (although the reads are probably cached on most user's systems). So a pretty bad bit of code, all-round.
Yet it can draw a rotated bitmap at least as fast (if not faster) than the GDI's DrawIcon can simply draw a non-rotated bitmap.
I couldn't believe how slow DrawIcon was when I first had to use it in one of my early BB4W programs. It only had to render a few bytes of data! I remember thinking to myself, "Crikey! I've got a 733 MHz processor here, yet I've seen faster bitmap drawing on a BBC Micro". Which was probably a bit of an exaggeration, although that's how it seemed at the time.
DrawIcon was doubtlessly coded by highly paid, skilled software engineers who knew exactly what they were doing, and compiled their source code with a compiler that generated efficient code, yet I don't think I could write a bitmap plotter as slow as DrawIcon if I tried. I would literally have to put in a deliberate delay after each PutPixel()!
Of course, I realise that DrawIcon has to deal with a variety of colour depths - but so what? It would just need to call a different PutPixel subroutine depending on the colour depth, using perhaps a jump table or a short switch-case structure.
This is why I had expected GFXLIB_DrawFilledCircle to be significantly faster than the GDI's circle plotter (assumption being that the GDI filled circle drawer isn't using hardware acceleration).
EDIT: I admit that GFXLIB_DrawFilledCircle isn't exactly a shining example of efficient code either; for each horizontal line drawn, an external horizontal line drawer (GFXLIB_DrawHLine) is called, which in turn calls GFXLIB_ClipHLine. The circle edges are computed using x=((radius^2 - (y0-y)^2))^0.5, so one FPU fsqrt instruction per line drawn, plus a fild and a fistp. An integer SQRT routine would probably be faster, although precision might suffer.
David.
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Translating a line from a fast box blur algori
« Reply #10 on: Oct 13th, 2011, 4:21pm » |
|
on Oct 13th, 2011, 10:45am, David Williams wrote:| Of course, I realise that DrawIcon has to deal with a variety of colour depths - but so what? It would just need to call a different PutPixel subroutine depending on the colour depth |
|
Maybe, but that only deals with colour depth. There are other format variations such as the different ways of representing the 'mask' - encoded in each pixel as ARGB or as a separate monochrome bitmap - and encodings - e.g. PNG. One could in principle have an entirely separate DrawIcon routine for each different format, but perhaps Microsoft didn't think the overhead of that was justified.
DrawIcon also has to contend with issues such as clipping to the current Clip Region, and adapting to the current Mapping Mode. Again, it could have multiple routines - fast(er) ones that are called when there's no clipping or mapping, and slower ones when there is - but maybe it doesn't work that way.
Bear in mind that icons are not sprites! DrawIcon is not intended for displaying moving objects of the kind you might use in a game, it's intended for displaying a static icon in the corner of the window, or in the taskbar etc. So there's little incentive for Microsoft to put effort into making it efficient, when it's irrelevant for its main purpose.
When it comes to graphics primitives like circle drawing, it's probable that Microsoft will have put much more effort into optimising them, since they are indeed quite likely to be used in some speed-critical, dynamic display.
Richard.
|
| « Last Edit: Oct 13th, 2011, 5:27pm by admin » |
Logged
|
|
|
|
|
