BorlandTalk.com

Jon Lennart Aasenden · Guest

To the borland gfx board

I have some thoughts i would like to share with the community.
Perhaps i am re-inventing the wheel here, but i would apprechiate the input,
both good and bad, from the developers on this board.

Background:

I have been playing around with graphics programming for a few years now,
and have (like most of us do) implemented my own graphics library that i use
in my commerical and personal projects.
Lately however i have started to realize that the brute force of pixel
copying can only get you that far. A fast blitter routine or scaline plotter
is very nice, but the true speed gain is perhaps not how you copy pixels,
but rather what to copy and what to exclude..
A badly written clipping system can (as an example) have a huge impact on
general performance. As can calling out of a filling procedure repeatedly..

Another example of overkill is the old-school platform game (controlling a
figure that can jump around a world of graphic blocks). Most games redraw
everything for each screen redraw - but in reality, they only need to
replace the background of sprites (figures) that have moved. Unless the
entire background has been moves that is. I have seen some lightning fast
win32 games running under GDI that pull off this trick to great success. And
i have seen some sluggish directx games that redraw everything for each
frame. Again, its not how you copy pixels, its what not to copy that
matters.
A bit like life, it not what you do - but your motives that define.. (or was
it the other way around?)

While a lot of optimalization can be done on copying data around, like using
assembler, scanline caching, dividing the surface into segments so you can
move longwords - not much have been done with the actual drawing of
primitives (circles, rectangles, polygons).
Most of us are using code that was created during the age of turbopascal.
Only a handfull of the libraries i have taken a look at implements somthing
unique, my own included.

The idea:

The other day while playing around with my library, i started to think about
how i could optimize my trusty old polygon renderer. I did not write it to
begin with, although i have added to it over the past two years. While
playing around i noticed that at one point in the routine, it sorts all the
points that will affect a scanline into an array, and then draws it into the
surface horizontally. Filling in the polygon from left to right, top to
bottom.
To handle intersections, it organize things into explicit start & stop
points so the scanline fill routine can skip ahead whenever an intersection
is meet.

In pseudo code it would be like:

with scanline do
Begin
forward(10); fill(25);
forward(76); fill(9 Cool

;
end;
The forward() simply increment a pByte pointer by X number of Bytes Per
Pixel.

While none of the above is either new or revolutionary, this old school
procedure is one of the fastest procedures in my library, and one of the
fastest polygon renderers i have used. And the way it works gave me an
interesting idea on how to fill pixels. I have been thinking about this for
a while now.

My silly idea - put plainly:
Would it not be possible to create a small bytecode system to limit the
number of operations and time required to produce a visual graphic result?

I remember learning logo at school on commodore 64. It was slow, sluggish
and fairly useless for anything other than long-term statistics (long term
because it took forever to draw anything), but the concept of an economic
rasterization language is probably the only thing i have not seen in the
delphi camp.
I know freetype1 uses such a system to draw fonts fast to handle hinting of
polybeziers and drawing of font glyphs.

While thinking about this, i have started to notice the concept in existing
software, software that we use and even try to mimic. Some commercial
libraries explicitly require you to call some variant of beginUpdate() and
endUpdate(). No doubt mapping the regions of a surface that is affected by a
series of graphics operations. GDI itself is one of the fastest graphics
systems out there (think about it before flaming me, it handles thousands of
graphics objects without even making a blip in the cpu monitor, only pixel
operations stored in chipset memory is dead slow). Again it uses
BeginPaint() and EndPaint() in the message loop.
I also seem to remember that SDL has a "updaterects" functions to finalize
the changes for offscreen surfaces.
Its veird to suddenly start noticing somthing on your own, then start seeing
it everywhere..

So...before i start experimenting with this, i would like some feedback on
the subject.
Have anyone on this board any experience with this?
Have it been done and failed, or perhaps been a success?
What would the immediate benefits be? What would the burdens be?

From my point of view, the hard nut would be the code that excludes various
regions as a result of overlapping graphics operations. Like drawing two
intersecting primitives, resulting in a polygon rather than a traight
forward scanline filled rectangle.

Kind regards

Jon Lennart Aasenden

Anders Isaksson · Guest

Jon Lennart Aasenden wrote:

Nils Haeck · Guest

Hi Jon,

In my existing DtpDocuments component I use a clipping rectangle that is
made up of all the changed areas (the unified rectangle of them). This
indeed speeds up things quite a bit. If a user e.g. moves a shape, the
previous bounding box unified with the new bounding box gets redrawn, which
is usually much smaller than the total screen.

Furthermore, it *caches* shapes, so they usually do not require another
scanline conversion. It's just a matter of blitting the cache in the new
position to the final backdrop.

In my new Pyro library, I use the same system.. and in addition, there's a
cover class that stores "spans". spans are scanline parts that were painted
by the last scanline conversion. A span can be a AA (antialiased) span, or a
solid span. The list of spans are then later analysed to generate a fill. A
fill can be anything from a solid color, gradient, texture, etc.

For some great ideas, make sure to read the information on the Antigrain
website. It is a C project, but has some great principles at its basis. Lots
of these ideas have also gone into Pyro.

Kind regards,

Nils

"Jon Lennart Aasenden" <post_nospam_nojunk (AT) jurasoft (DOT) no> schreef in bericht
news:435b4bcd (AT) newsgroups (DOT) borland.com...

Jens Gruschel · Guest

It's hard to reply to this with only one sentence. And this is not ment
to be a complete answer.

First of all, yes, the GDI is very optimized and lightning fast. One
reason for this it that it is supported directly by all graphic cards we
have today. Try a card from 1995 or so, and you'll be disappointed,
because it's very likely that it has no hardware bltter and doesn't
support filling large regions directly. What makes such operations
really fast is that pixel data is only copied inside of the graphic
card. The CPU, the bus, and the main memory isn't involved.

Libraries like Graphics32 support operations GDI doesn't support (for
example operations with antialiasing and alpha blending), so you cannot
make use of hardware accelleration (at least not "traditional hardware
accelleration"). To implement routines with antialiasing / alpha
blending, you have to read each pixel e.g. in a CPU register (reading
from the graphic card tends to be slow), and write the modified data
back (what's normally faster). That's why such routines normally use
bitmaps stored in the main memory, and when all drawings have been done
the complete result is copied to video memory (using a more or less fast
blt operation).

People realized that the GDI is too limited, and software rendering,
while being most flexible, is too slow. So they made graphic cards more
powerful, e.g. by supporting alpha blending, antialising, textured
polygon rendering etc. directly. The interface to use this power is
DirectX (or openGL). As much as possible is directly performed by the
graphic card. Of course you are still limited to the functions
supported, but limits are much higher (and with pixel shaders you can
even make your own pixel filters done by the graphic card).

Yes, DirectX is often used for games or 3D applications, but it's not
limited to these. But for 2D (and in some cases maybe even 3D)
applications software renderers still make sense. Nice looking business
charts often don't need to be lightning fast. And software rendering has
one advantage: you know what exactly the result will look like, what you
don't when using hardware rendering (yes, more or less you know, too,
but consider rounding, which can be done differently).

You are right, intelligent optimization is a good thing and should be
done (and it is done by some renderers), but sometimes brute force has
its benefits, too. Let's use your example, a 2D game like a jump'n'run.
When there is no scrolling (and not too much sprites), you can safe much
CPU power by only updating regions which have to be updated. But often
more or less the complete visible area has to be updated, for example
when scrolling has to be performed. Yes, you can use the GDI / hardware
accelleration to perform scrolling fast, and then update smaller parts
(regions with moving sprites), but you probably are faced with a
flickering problem, and if you want paralax scrolling (several layers
scrolling with different speed), there is no other way than brute force.
Of course you could use different techniques when scrolling has to be
done, and when no scrolling has to be done. But then you have a game
that's sometimes fast and sometimes slow (in fact some games use this
approach, but IMO it's only a pseudo solution).

I don't want to say that your ideas are bad. But it really depends on
what you want to accomplish. Sometimes the most intelligent algorithmn
is beat by brute force, when brute force is supported by your hardware.

Jens

--
Jens Gruschel
http://www.pegtop.net

Rudy Velthuis [TeamB] · Guest

At 13:11:33, 23.10.2005, Nils Haeck wrote:

Jens Gruschel · Guest

Jens Gruschel · Guest

HB · Guest

Before looking for a solution, one has to separate two different goals:
1) Fast re-draw of a scene that contains only a small change.
(e.g. during editing or animation)
2) Fast re-draw of the whole ! scene
(e.g. after panning or zoom).

(1) has some solution in graphics32 (with microtiling),
But many graphic apps don't need a solution here because they
don't draw in real-time, but preview changes (e.g.dragging
curves) with the classical gdi-xor.

I would be interested in (2)..
As Nils pointed out, caching of objects would be a solution
(at least for panning ). But I think there should also be a solution
like in 3D-drawing (with Z-buffering or such thing), or maybe
the microTiling-thing can be used here too ( don't know,
unfortunately I don't have time to investigate it)

Jon Lennart Aasenden · Guest

I used to code games on my Amiga & Atari, so yes Smile

I remember the good old
days.

But my focus with my post was more on the RLE/Bytecode system.

Kind regards

Jon Lennart Aasenden

"Jens Gruschel" <nospam (AT) thisurldoesnotexist (DOT) com> wrote

Jon Lennart Aasenden · Guest

First, thanks for all you comments!
Its great to see that so many people are working on more or less the same
thing.

Now, the focus of my post was not the "blitter" functionality directly.
There are only so many ways you can move X number of pixels from one memory
location to another, so brute force is probably the best way here. I make
full use of loop reduction in my blitter engine, moving 8 pixels at a time -
and it work very well. As for the RLE based transparency, i have been
thinking about that, but only done some mild experiments.

My focus was on painting primitives, such as lines, ellipses, polygons and
the all the fundamentals that everything else depend on. For example, take
the Line() method (perhaps not the best example, but valid non the less):

Every time you draw a line, each pixel has to be calculated and plotted.
Depending on your library, you may call out of the line procedure to plot
the pixel.
Before this is done, parameters have to be checked, pixel buffers verified,
brush objects located and coordinates clipped etc. etc. So drawing 1000
lines is not just drawing for start to stop, it's also testing parameters
1000 times for each pixel, as well as fetching pointers and clipping. Not in
that order ofcourse.

So - how can we reduce the amount of testing involved?
Well, if you are anything like me - you optimize for more code, writing the
pixels directly from the line drawing method.
Performing blending on the spot, and dont get me started on bitmap brushes..
having to fetch and decode pixels from other bitmaps who might even use a
different pixelformat. Surely there must be a better, cleaner and more
flexible way?

The idea i have swirling around my head at the moment, is to take the
resulting array to TPoints a line method produce, and then reduce the
operations required to render that into a memory buffer. For example, if two
pixels are side-by-side, on the same scanline - it is faster to draw both in
one operation, than plotting them seperatly. Consider a line line so:

(start)
**
***
***
***(stop)

In this pseudo line, there are 4 segments of pixels, and a total of 11 plot
operations.
All these segments could be reduced to 8 plot operations.

HPlot(2);NL;
HPLOT(3);NL;
HPLOT(3);NL;
HPLOT(3);NL;

NL= Next Scanline.

= 8 operations.

The speed gain is ofcourse that there will be no calling out of the
executing loop that fetches and translates the opcodes:

While FIndex<FMaxOpcode do
Begin
Case FOpcodes[FIndex].ro_opcode of
CMD_HPLOT:
Begin
while FOpCodes[FIndex].ro_span>0 do
begin
PBGR24(Addr)^:=FPenColor; // draw 24 bit pixel
inc(PBGR24(FAddr)); // update addr to next
horizontal pixel
dec(FOpCodes[FIndex].ro_span);
end;
end;
CMD_NL: inc(FAddr,FPitch);
...
...
end;
inc(FIndex);
end;

(* type holding one opcode & one parameter *)
Type TRasterOpcode = Record
ro_opcode: word; //perhaps split into two bytes, the last byte
holding the direction of the operation (right,left,top,bottom)
ro_value: word;
End;

Inside the line method, we would have to do some plot reduction before
converting to opcodes...

example:
Type TPixelOperation = Record
x,y: Integer;
VSpan: integer;
End;

(* is the current point in the line on the same scanline as the previous
*)
if FPixels[index-1].y=y then
Begin
(* is it right beside us? *)
if Diff(x,FPixels[index-1].x)=1 then //diff should be replaced by
inline code.
Begin
(* update span to cover this pixel as well *)
inc(FPixels[index-1].span);

(* drop current pixel plot, and continue with the next *)
Continue;
end;
end;
(* we are to far away from any pixels, so we need to plot this one, save
to stack *)
FCurrent:=PixelOP(x,y,1);
AddPixelToStack(FCurrent);

Now what
========

The main benefit of this approach is that all drawing operations are painted
very fast. If we take for granted that operations are executed from top-left
to right-bottom in an linear framebuffer (or dib, as long as pixel[0,0] is
at a lower adresse than pixel[right,bottom]), it would greatly reduce the
workload needed to draw the pixels involved. Also, pixels that overlap would
be non-existant since they would have been deleted by opcode reduction.

The weight of the problem now resides on math and plot reduction techniques
rather than brute force.

Well, just an idea... :)

Jon Lennart Aasenden

Nils Haeck · Guest

Hi Jon,

This is more or less exactly what I'm doing with pyro.

The cover object stores a number of spans (the horizontal start and stop
locations on each scanline). Spans consist of *byte* values, that represent
a cover. E.g. 0=totally uncovered, and $FF=totally covered.

There is a slight, but crucial difference between cover and alpha, and the
only source up till now addressing this issue more or less correctly is the
PDF specification, so I suggest anyone wanting to learn about this to read
the salient parts of that spec first.

The cover object doesn't really care itself on *how* the underlying pixels
are painted, that's the task of another object in Pyro.

Solid colors are easy.. just loop through the spans and merge all underlying
pixels under partial with the solid color, or completely replace them with
the solid color if cover = 255 and the solid color has alpha=255.

The fun part starts when filling the covers with specific "paint", like a
gradient or texture. At that moment it requires to calculate the inverse
transform for each pixel location back into the texture or gradient. To
avoid a lot of float calculations to get the inverse, I have optimized this
too.. For *linear* transformations (e.g. affine transforms) one just has to
calculate the start point and end point, and then intermediate positions can
be interpolated.

Btw, I've profiled my code extensively and found that the scanline
conversion is the biggest bottleneck, not the blending or blitting, at
least, when doing 256 AA levels. So it is important to focus on how to make
scanline conversion (going from polygon to raster cover) can be made as fast
as possible. I'm looking into caching cover objects now.

Nils

"Jon Lennart Aasenden" <post_nospam_nojunk (AT) jurasoft (DOT) no> schreef in bericht
news:435bed67 (AT) newsgroups (DOT) borland.com...