Perhaps slightly OT... linedrawing with SDL

SDL Development
1

I’m using SDL in a new game I’m creating, and I’m looking to do a LOT of
linedrawings (it’s a vector game) and am finding that even regular
linedraws don’t run as fast as I’d like. I’m wondering if anyone has
advice/pointers on hardware accelerated linedraws using OpenGL or
Direct3D, as I’m not really sure where to start. Thanks in advance!

–>Neil-------------------------------------------------------------------------------
Neil Bradley What are burger lovers saying
Synthcom Systems, Inc. about the new BK Back Porch Griller?
ICQ #29402898 “It tastes like it came off the back porch.” - Me

2

An embedded and charset-unspecified text was scrubbed…
Name: not available
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20021001/6962982d/attachment.txt

3

I think it’s pretty overdoing to use a 3d api to draw lines :wink: Have
you tried Bresenham on a software-surface? I’d advice to keep your
backbuffer in software for faster acces.

That’s precisely what I’m doing, and I’m also writing directly to the in
system memory backbuffer surface. It’s a Bresenham algorithm.

I’ve tried doing dirty tiles, but on faster machines it’s slower than just
doing a single blit of the entire backbuffer to the display surface. I’m
getting roughly 80FPS on a Pentium III 1Ghz, and I have yet to add line
clipping, background tiling, and antialiasing, so obviously I’m looking to
make things really fast. The antialiasing I fear will have a great impact
on performance, so I’m doing as much front optimization as possible. WU
Antialiasing is the approach I’m going to use as it seems to be the
fastest antialiasing algorithm around.

I’m dealing with 400+ vectors PER FRAME, so even the smallest
optimizations are significant.

Check out SDL_Draw, although
i’m not sure what kind of algoritm they use and if they do it smart
(lock, draw all pixelds, unlock) and not calling a dedicated putpixel
function. It’s here:

I took a look at it, and it seems like it’s intelligent. However, I didn’t
see an optimizations for horizontal, vertical, or 45 degree angles, though
I must say I didn’t spend a bunch of time in the code. My code is already
as optimized (if not moreso) than it is, but at least it lets me know I’m
on the right track.

I may just have to make assembly versions of the linedraw routines…

–>Neil-------------------------------------------------------------------------------
Neil Bradley What are burger lovers saying
Synthcom Systems, Inc. about the new BK Back Porch Griller?
ICQ #29402898 “It tastes like it came off the back porch.” - Me

4

If you are using SDL_Flip you will probably find that this is the
function which is taking up all the time so optimizing your line drawing
further will not make any difference. If you are using it on Windows
then SDL_Flip waits for vertical retrace. This means you cannot get any
faster than about 80 FPS even you do no drawing at all. This also means
you will be able to add your other features before the FPS will start to
drop.

Neil Bradley wrote:>>I think it’s pretty overdoing to use a 3d api to draw lines :wink: Have

you tried Bresenham on a software-surface? I’d advice to keep your
backbuffer in software for faster acces.

That’s precisely what I’m doing, and I’m also writing directly to the in
system memory backbuffer surface. It’s a Bresenham algorithm.

I’ve tried doing dirty tiles, but on faster machines it’s slower than just
doing a single blit of the entire backbuffer to the display surface. I’m
getting roughly 80FPS on a Pentium III 1Ghz, and I have yet to add line
clipping, background tiling, and antialiasing, so obviously I’m looking to
make things really fast. The antialiasing I fear will have a great impact
on performance, so I’m doing as much front optimization as possible. WU
Antialiasing is the approach I’m going to use as it seems to be the
fastest antialiasing algorithm around.

I’m dealing with 400+ vectors PER FRAME, so even the smallest
optimizations are significant.

Check out SDL_Draw, although
i’m not sure what kind of algoritm they use and if they do it smart
(lock, draw all pixelds, unlock) and not calling a dedicated putpixel
function. It’s here:

I took a look at it, and it seems like it’s intelligent. However, I didn’t
see an optimizations for horizontal, vertical, or 45 degree angles, though
I must say I didn’t spend a bunch of time in the code. My code is already
as optimized (if not moreso) than it is, but at least it lets me know I’m
on the right track.

I may just have to make assembly versions of the linedraw routines…

–>Neil

Neil Bradley What are burger lovers saying
Synthcom Systems, Inc. about the new BK Back Porch Griller?
ICQ #29402898 “It tastes like it came off the back porch.” - Me

5

If you are using SDL_Flip you will probably find that this is the
function which is taking up all the time so optimizing your line drawing
further will not make any difference. If you are using it on Windows
then SDL_Flip waits for vertical retrace. This means you cannot get any
faster than about 80 FPS even you do no drawing at all. This also means
you will be able to add your other features before the FPS will start to
drop.

Thanks for the advice, but I’m not using SDL_Flip - I’m just using
SDL_BlitSurface(), so vertical retrace shouldn’t enter in to the picture.

–>Neil-------------------------------------------------------------------------------
Neil Bradley What are burger lovers saying
Synthcom Systems, Inc. about the new BK Back Porch Griller?
ICQ #29402898 “It tastes like it came off the back porch.” - Me

6

I’m using SDL in a new game I’m creating, and I’m looking to do a LOT
of linedrawings (it’s a vector game) and am finding that even regular
linedraws don’t run as fast as I’d like.

Why? Are you doing the rendering into VRAM, or into a s/w shadow buffer?
(You should do the latter, unless you’re only covering a small fraction
of the screen area with lines.)

I’m wondering if anyone has
advice/pointers on hardware accelerated linedraws using OpenGL or
Direct3D, as I’m not really sure where to start. Thanks in advance!

Well, for one thing, don’t count on lines (AA or not) being accelerated
on 3D cards sold as gaming cards. As an example, GeForce 2 an IIRC even
GeForce 3 cards had accelerated line drawing entirely disabled in the
mainstream drivers, despite it being supported in the hardware. (In that
particular case, the fix is just a matter of tweaking the registry
settings, but I think there are quite a few gaming cards that can’t
accelerate lines at all.)

So, you probably need a safe fallback. Basically, just draw the lines as
polygons (quads) using a white texture and vertex color modulation to set
colors.

If you want AA, you’ll need an RGBA texture (possibly a 1D texture) that
spans the width of the widest line you want to be able to draw, and then
just scale it down to the width you want for each line. (Scaling up is a
bad idea, as that will cause the texture filtering to generate very
blurry edges.)

//David Olofson - Programmer, Composer, Open Source Advocate

.- Coming soon from VaporWare Inc…------------------------.
| The Return of Audiality! Real, working software. Really! |
| Real time and off-line synthesis, scripting, MIDI, LGPL…|
-----------------------------------> (Public Release RSN) -' .- M A I A -------------------------------------------------. | The Multimedia Application Integration Architecture |----------------------------> http://www.linuxdj.com/maia -’
— http://olofson.net — http://www.reologica.se —On Wednesday 02 October 2002 01:38, Neil Bradley wrote:

7

I think it’s pretty overdoing to use a 3d api to draw lines :wink: Have
you tried Bresenham on a software-surface? I’d advice to keep your
backbuffer in software for faster acces.

That’s precisely what I’m doing, and I’m also writing directly to the
in system memory backbuffer surface. It’s a Bresenham algorithm.

I’ve tried doing dirty tiles, but on faster machines it’s slower than
just doing a single blit of the entire backbuffer to the display
surface. I’m getting roughly 80FPS on a Pentium III 1Ghz, and I have
yet to add line clipping, background tiling, and antialiasing, so
obviously I’m looking to make things really fast. The antialiasing I
fear will have a great impact on performance, so I’m doing as much
front optimization as possible. WU Antialiasing is the approach I’m
going to use as it seems to be the fastest antialiasing algorithm
around.

I think you’re looking for the performance issues in the wrong place. If
you profile your application, I’m about 90% sure that you’ll find that
most of the time is spent in SDL_FlipSurface(), or whatever you use to
blit the back buffer to the screen.

I’m dealing with 400+ vectors PER FRAME, so even the smallest
optimizations are significant.

I don’t think so. Your CPU has about 31250 cycles to render each line.
Depending on your application and screen resolution, that’s probably in
the range of 50-500 cycles per pixel of each line.

You think there is a problem!? :slight_smile:

Well, there is: Getting the result into VRAM…

Check out SDL_Draw, although
i’m not sure what kind of algoritm they use and if they do it smart
(lock, draw all pixelds, unlock) and not calling a dedicated putpixel
function. It’s here:

I took a look at it, and it seems like it’s intelligent. However, I
didn’t see an optimizations for horizontal, vertical, or 45 degree
angles, though I must say I didn’t spend a bunch of time in the code.

It might be because there isn’t much point in such optimizations (unless
possibly for the horizontal case), when the algo is totally memory bound
on any but the slowest still working PCs you can find today.

My code is already as optimized (if not moreso) than it is, but at
least it lets me know I’m on the right track.

I may just have to make assembly versions of the linedraw routines…

Don’t bother. You’ll need to spend serious time on it to beat the
compiler, and you’re still memory bound.

//David Olofson - Programmer, Composer, Open Source Advocate

.- Coming soon from VaporWare Inc…------------------------.
| The Return of Audiality! Real, working software. Really! |
| Real time and off-line synthesis, scripting, MIDI, LGPL…|
-----------------------------------> (Public Release RSN) -' .- M A I A -------------------------------------------------. | The Multimedia Application Integration Architecture |----------------------------> http://www.linuxdj.com/maia -’
— http://olofson.net — http://www.reologica.se —On Wednesday 02 October 2002 09:15, Neil Bradley wrote:

8

Well, vertical retrace sync isn’t an issue anyway (unless you fail to
notice it’s used when benchmarking), but the back->front blit is.

And if you were drawing directly into VRAM when possible, you’d be hit by
VRAM read-modify-write issues, unless you figure out a way to always
perform aligned 64 bit writes…

That’s less of an issue if you’re only filling a fraction of the screen
with lines, of course - but then you’d have to be equally smart about
removing those lines, or you might as well stick with the s/w back
buffer approach.

//David Olofson - Programmer, Composer, Open Source Advocate

.- Coming soon from VaporWare Inc…------------------------.
| The Return of Audiality! Real, working software. Really! |
| Real time and off-line synthesis, scripting, MIDI, LGPL…|
-----------------------------------> (Public Release RSN) -' .- M A I A -------------------------------------------------. | The Multimedia Application Integration Architecture |----------------------------> http://www.linuxdj.com/maia -’
— http://olofson.net — http://www.reologica.se —On Wednesday 02 October 2002 09:43, Neil Bradley wrote:

If you are using SDL_Flip you will probably find that this is the
function which is taking up all the time so optimizing your line
drawing further will not make any difference. If you are using it on
Windows then SDL_Flip waits for vertical retrace. This means you
cannot get any faster than about 80 FPS even you do no drawing at
all. This also means you will be able to add your other features
before the FPS will start to drop.

Thanks for the advice, but I’m not using SDL_Flip - I’m just using
SDL_BlitSurface(), so vertical retrace shouldn’t enter in to the
picture.

9

I’m using SDL in a new game I’m creating, and I’m looking to do a LOT
of linedrawings (it’s a vector game) and am finding that even regular
linedraws don’t run as fast as I’d like.
Why? Are you doing the rendering into VRAM, or into a s/w shadow buffer?
(You should do the latter, unless you’re only covering a small fraction
of the screen area with lines.)

As I’ve stated in my followup emails, I am rendering to a software
backbuffer.

I’m wondering if anyone has
advice/pointers on hardware accelerated linedraws using OpenGL or
Direct3D, as I’m not really sure where to start. Thanks in advance!
Well, for one thing, don’t count on lines (AA or not) being accelerated
on 3D cards sold as gaming cards. As an example, GeForce 2 an IIRC even
GeForce 3 cards had accelerated line drawing entirely disabled in the
mainstream drivers, despite it being supported in the hardware. (In that

That’s PRECISELY the answer I was looking for - thank you! In short,
“Don’t rely on hardware linedraws because they most likely are not there”.

And your other emails:

I think you’re looking for the performance issues in the wrong place. If
you profile your application, I’m about 90% sure that you’ll find that
most of the time is spent in SDL_FlipSurface(), or whatever you use to
blit the back buffer to the screen.

Nope - I’ve already profiled it - the blitting is sitting around 30% of
the overall CPU utilization.

I’m dealing with 400+ vectors PER FRAME, so even the smallest
optimizations are significant.

I don’t think so. Your CPU has about 31250 cycles to render each line.
Depending on your application and screen resolution, that’s probably in
the range of 50-500 cycles per pixel of each line.

Regardless of what you say above, if I remove the lines of code that write
to the dirty tile map (but still blit the entire screen), I see a jump of
about 15FPS on my PII 1Ghz. As I stated above, even the smallest
optimizations are significant. I didn’t just make that up. :wink:

It might be because there isn’t much point in such optimizations (unless
possibly for the horizontal case), when the algo is totally memory bound
on any but the slowest still working PCs you can find today.

It does make a difference when the game draws primarily horizontal and
veritcal lines.

Don’t bother. You’ll need to spend serious time on it to beat the
compiler, and you’re still memory bound.

That migh be true on RISC CPUs, but I know from my own experience I can
beat any compiler’s output, and I’ve done so on many occasions (I do a
LOT of assembly language), when doing graphcis and processor emulation.
CPU Emulation increased by a factor of 5 when I went to assembly (and the
C version was no slouch, either).

Things in VERY tight loops are prime candidates for optimization, and this
is no exception. But of course I’ll keep the C version around for
comparison/portability. :wink:

One other possibilty I haven’t considered is that I’m doing 16bpp access,
which means that the CPU is taking a pipeline stall for a 16 bit
instruction. I’m starting to wonder if going to 32 bit will be faster…

–>Neil-------------------------------------------------------------------------------
Neil Bradley What are burger lovers saying
Synthcom Systems, Inc. about the new BK Back Porch Griller?
ICQ #29402898 “It tastes like it came off the back porch.” - Me

10

Why are you trying to beat 80 FPS… what vid-mode/monitor are you
dealing with that can beat that? If you don’t sync to the v-refresh,
you will get all sorts of ugly tearing… are you sure this is what you
want? I’m not saying that you shouldn’t get the frame-rate as high as
possible, but most video-modes only go between 60Hz and 120Hz…

-LorenOn Wed, 2002-10-02 at 10:39, Neil Bradley wrote:

I’m dealing with 400+ vectors PER FRAME, so even the smallest
optimizations are significant.

I don’t think so. Your CPU has about 31250 cycles to render each line.
Depending on your application and screen resolution, that’s probably in
the range of 50-500 cycles per pixel of each line.

Regardless of what you say above, if I remove the lines of code that write
to the dirty tile map (but still blit the entire screen), I see a jump of
about 15FPS on my PII 1Ghz. As I stated above, even the smallest
optimizations are significant. I didn’t just make that up. :wink:

11

Regardless of what you say above, if I remove the lines of code that write
to the dirty tile map (but still blit the entire screen), I see a jump of
about 15FPS on my PII 1Ghz. As I stated above, even the smallest
optimizations are significant. I didn’t just make that up. :wink:
Why are you trying to beat 80 FPS… what vid-mode/monitor are you
dealing with that can beat that? If you don’t sync to the v-refresh,
you will get all sorts of ugly tearing… are you sure this is what you
want? I’m not saying that you shouldn’t get the frame-rate as high as
possible, but most video-modes only go between 60Hz and 120Hz…

Because I want it to run on much lower end machines, and I’m still not
done adding in things like a background image, character movement, audio,
etc… I’m only looking for a target frame rate of about 30FPS but I want
it to run on as low end of machine as possible.

–>Neil-------------------------------------------------------------------------------
Neil Bradley What are burger lovers saying
Synthcom Systems, Inc. about the new BK Back Porch Griller?
ICQ #29402898 “It tastes like it came off the back porch.” - Me

12

Hi,

I on the other hand believe that massive linedrawing can be accelerated
with 3D since there are clever algorithms
for drawing wireframe 3D models. If this can be accelerated with
hardware I’m not sure about. But with pixel-
or vertex- shaders it could be possible

/Pontus>Hi,

I think it’s pretty overdoing to use a 3d api to draw lines :wink: Have you tried Bresenham on a
software-surface? I’d advice to keep your backbuffer in software for faster acces. Check out
SDL_Draw, although i’m not sure what kind of algoritm they use and if they do it smart (lock,
draw all pixelds, unlock) and not calling a dedicated putpixel function. It’s here:

http://sdl-draw.sourceforge.net

Patrick.

Neil Bradley nb at synthcom.com schreef:

I’m using SDL in a new game I’m creating, and I’m looking to do a LOT of
linedrawings (it’s a vector game) and am finding that even regular
linedraws don’t run as fast as I’d like. I’m wondering if anyone has
advice/pointers on hardware accelerated linedraws using OpenGL or
Direct3D, as I’m not really sure where to start. Thanks in advance!

–>Neil

Neil Bradley What are burger lovers saying
Synthcom Systems, Inc. about the new BK Back Porch Griller?
ICQ #29402898 “It tastes like it came off the back porch.” - Me

SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

13

That’s precisely what I’m doing, and I’m also writing directly to the in
system memory backbuffer surface. It’s a Bresenham algorithm.

Have you read the Graphics Gems books? There are a few better
algortihms out there. It’s been a while, but I remember that one of
them involved a method of calculating three pixels at once… i.e., for
any slope, a group of three pixels will be one of the four following
(flipped around x = y, perhaps).

… .-- …- .-'On Wed, 2002-10-02 at 00:15, Neil Bradley wrote:

–
…
: Benjamin Keil VEGAN Publications :
: Webmaster and A Professional Website for :
: Strategy / Linux Editor Video Game Reviewing and Reporting :
:… http://www.veganpub.com/ …:

14

Hi,

I on the other hand believe that massive linedrawing can be accelerated
with 3D since there are clever algorithms
for drawing wireframe 3D models.

Well, OpenGL has had lines for ages.

If this can be accelerated with hardware I’m not sure about.

Well, even today, you generally need a professional 3D card to get them
accelerated. (Sure, most modern 3D accelerators support lines, but have
them disabled on gaming cards in various ways, to force “serious” 3D
users to buy the much more expensive pro cards, even though they have
effectively the same chips.)

But with pixel-
or vertex- shaders it could be possible

What difference would pixel and vertex shaders do for basic (including
AA) lines? I don’t think they’ll give you anything you don’t have with
good old polygons and a white texture, optionally with an alpha channel
for AA.

Of course, you could fake highpoly wireframe using wireframe RGBA skins
for your models. Might be faster than one poly per line, at least as long
as it’s the vertex count rather than the fillrate that limits the
framerate. (Don’t count on fully transparent alpha pixels rendering any
faster than the ones that are actually blended…)

//David Olofson - Programmer, Composer, Open Source Advocate

.- Coming soon from VaporWare Inc…------------------------.
| The Return of Audiality! Real, working software. Really! |
| Real time and off-line synthesis, scripting, MIDI, LGPL…|
-----------------------------------> (Public Release RSN) -' .- M A I A -------------------------------------------------. | The Multimedia Application Integration Architecture |----------------------------> http://www.linuxdj.com/maia -’
— http://olofson.net — http://www.reologica.se —On Wednesday 02 October 2002 08:35, Pontus Pihlgren wrote:

15

Hi!

I thought of something cool, If you are drawing long lines that have
less than 45 degrees incline you get this
kind of stairstepping:

__—^^^

with long horisontal line for each step i the y-direction. If you use an
RLE-accelerated surface you could
RLE-compress those horisontal lines, at least if they are homogenous in
color. Don’t know if it’s worth
the effort or how it actually is done, but it is a novelty, I’ve never
heard anyone try.

Cheers, Pontus.>Have you read the Graphics Gems books? There are a few better

algortihms out there. It’s been a while, but I remember that one of
them involved a method of calculating three pixels at once… i.e., for
any slope, a group of three pixels will be one of the four following
(flipped around x = y, perhaps).

… .-- …- .-’