#134834 - gazsp - Tue Jul 17, 2007 1:46 pm
Hi all,
I've just begun my first game for the GBA, and I'd like to know if anyone has implemented a fast pixel plotting routine (it will hopefully be a vector graphics type games, if I can get the speed out the GBA)
I'm thinking of doing the plotting in ASM, and putting the routine in IWRAM for extra speed.
Has anybody attempted this before? Or does anyone have any suggestions from past experience that may help me?
Cheers,
Gaz.
#134836 - keldon - Tue Jul 17, 2007 2:24 pm
Well bearing in mind the amount of 3d games on the GBA, vector games isn't going to be a problem ^_^
#134837 - kusma - Tue Jul 17, 2007 2:24 pm
The first trick to fast pixel plotting is to not have a routine at all. Try to plot many pixels at once, preferably in horizontal spans. This way you can burst out multiple pixels at once, without having to re-calculate addresses. On straight pixel-plotting, assembly does not gain you much. Also note that the VRAM of the GBA does not support 8bit writes, so you can't draw single pixels without read-modify-write in mode 4.
A simple and fast way of drawing polygons in mode4 is to scan-convert, and do read-modify-write on the pixels at the end of the spans.
#134873 - gazsp - Tue Jul 17, 2007 9:42 pm
Cool, thanks for that.
Do you know where I can find some example code for a generic scanline converter?
Cheers,
Gaz.
#134875 - tepples - Tue Jul 17, 2007 10:06 pm
It's called Bresenham's line algorithm.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#134876 - DekuTree64 - Tue Jul 17, 2007 10:10 pm
| gazsp wrote: |
| Do you know where I can find some example code for a generic scanline converter? |
The second trick to fast pixel plotting: Don't try to make things overly generic. Figure out what you need, and write it straight out.
There are some triangle fillers in my old demo here that could be useful. The textured triangle .s file is the main one that's used. I basically wrote the inner loop for it, and then worked my way out to make sure I had everything I needed in registers with as little swapping around as possible.
Also, this site has some very good articles on scan converting.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#134919 - gazsp - Wed Jul 18, 2007 10:08 am
At the moment, all of the shapes in the game are just held as a list of points, then are drawn with Bresenham's line algorithm (which I already knew about, but thanks tepples :-) ).
Do I need to convert all the shapes to triangles for a scanline converter to work? Or is there an implementation that will work for any polygon shape?
Sorry for all the questions, but this is my first GBA game. I'm actually an embedded software engineer, but most of my work is done in C on set top boxes :-)
#134921 - DekuTree64 - Wed Jul 18, 2007 10:29 am
Hmm, if all your graphics are just single pixel lines, then you're probably not going to get much faster than bresenham plotting one pixel at a time. Scan converting is more for filling solid shapes.
But still, there are some tricks that can be used depending on the exact style you're going for. How many colors do you plan to use? Any solid shapes, flat color or not? And is the background just a solid color?
A mockup screenshot would be helpful.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#134922 - gazsp - Wed Jul 18, 2007 10:57 am
The background is going to be black, all the graphics will be line-drawn vector objects, with each line being a solid colour (with each shape using only one colour).
It'll kind of look like a multicoloured Asteroids type game when finished (but it won't play like Asteroids).
They'll probably only be about 8 colours on screen at once. Maybe more for explosions :-)
After coding my plot routine in assembly, the 'game' now runs much faster. Now thinking about recoding the line-drawing routine in assembler and moving the whole lot to IWRAM.
Cheers,
Gaz.
#134929 - tepples - Wed Jul 18, 2007 1:45 pm
| gazsp wrote: |
The background is going to be black, all the graphics will be line-drawn vector objects, with each line being a solid colour (with each shape using only one colour).
It'll kind of look like a multicoloured Asteroids type game when finished (but it won't play like Asteroids). |
More like Tempest?
| Quote: |
| After coding my plot routine in assembly, the 'game' now runs much faster. Now thinking about recoding the line-drawing routine in assembler and moving the whole lot to IWRAM. |
What you gain in speed by rewriting something in assembly language you may lose in maintainability. Make sure to profile the end result to make sure that the gain outweighs the loss.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#134932 - gazsp - Wed Jul 18, 2007 2:25 pm
| Quote: |
| More like Tempest? |
Mmmm, not really. It's hard to explain. It's going to be a (up to) four player game, all on one screen. Kind of like Asteroids, but with little aliens that multiply and connect together, and without the rocks. That's about the best description I can give :-)
There's no background as such (maybe just some stars or something).
I'm thinking basically there are two routines that will be used the most, PlotPixelMode4 (already in assembler), which is called DrawLine (Bresenham's line algorithm in C at the moment). These are called from a function DrawVectorObject which draws all the game objects.
I'd say that DrawLine is another good candidate for moving to assembler. I've seen the assembler that is produced by GCC (with -O3) and I think I may be able to optimize it a bit.
I'm also wondering, would it be faster to use a different mode and implement the buffer swapping myself?
Cheers,
Gaz.
#134957 - Miked0801 - Wed Jul 18, 2007 9:54 pm
Depending on how fast you need FAST to be, there are a number of ways to make line drawing go faster. My guess is though, your collision detection routines will probably be a bigger hit than your rasterizer once you get a Bres algorithm up and running. Remember, premature optimization is the root of all evil in programming :)
#134958 - gazsp - Wed Jul 18, 2007 9:57 pm
| Quote: |
| Depending on how fast you need FAST to be, there are a number of ways to make line drawing go faster. My guess is though, your collision detection routines will probably be a bigger hit than your rasterizer once you get a Bres algorithm up and running. Remember, premature optimization is the root of all evil in programming :) |
Ok, fair point :-) The engine so far is running at a pretty decent pace anyway.
Just out of interest though, what are you thoughts on making the line drawing faster?
#134959 - keldon - Wed Jul 18, 2007 10:04 pm
Think of it this way, you can spend 5 hours optimizing your line drawing routine and get 0 gain, or you can 5 hours optimizing your line drawing routine and find you can do something you couldn't before. If it is not a problem than you probably will achieve only the former and not the latter!
#134960 - kusma - Wed Jul 18, 2007 10:04 pm
Don't have a plot-pixel routine you call, you'll end up wasting more performance on function-call overhead than you'll gain on anything else.
And don't think about assembly optimizing before you're sure you have the optimal algorithm in C/C++ first.
Last edited by kusma on Wed Jul 18, 2007 10:07 pm; edited 1 time in total
#134961 - Miked0801 - Wed Jul 18, 2007 10:05 pm
Hand tuned asm of course :)
There are also ways of calling multiple line drawing routines depending on the angle of the line to speed up the horizontal drawing portion of the code. I can't remember exactly what the technique is called, but we used WAY back when on the 286/386 in college when doing 3D rendering in 320/200 mode. Funny how such old stuff is still useful today.
#134963 - kusma - Wed Jul 18, 2007 10:11 pm
| Miked0801 wrote: |
| Hand tuned asm of course :) |
Oh come on, that's such a 1994 mind-set. You gain MUCH more on high-level optimizations, and by keeping the code in high-level languages you lower the effort for trying new stuff. Sure, once you are certain you have all the theory in place, you could assembly-optimize your code, but you'll most likely end up getting your code 10% faster at best, and, well, 10% isn't much when it comes to perceived frame-rate.
#134965 - keldon - Wed Jul 18, 2007 10:19 pm
Thought: with the size of games and programs rapidly growing larger, the 10% where you code is spending 90% of its time is much larger than it was 10 years ago!
#134966 - Miked0801 - Wed Jul 18, 2007 10:23 pm
Hence my original advice of get the other stuff done first, then and only then, optimize in places where the profiler says you should.
And yes, high level, algorithm optimization do usually yield the best 'big' speed increases. But, a fine tuned asm routine in the right location will yield a very nice result. Even hand-tuned C code will get you most of what a asm routine will, but that requires an excellent handle on what the compiler can, can't, and won't do with certain code.
Most compilers that I've worked with on our little embedded systems are laughable in terms of how tight they make there code. Asm is one of many tools that I have to make things work better. In every (recent) case where I've deemed asm was needed due to a speed bottleneck, I've gotten dramatic, game enhancing results with my changes.
Asm is for:
* low level code
* Called many, many times per gameloop
* Is a top 5 contributor to overall game slowdown.
* Is a very small, self contained module that I am not afraid to support for the remainder of the platform's life. As soon as something goes asm, you are tied to it forever. :)
A pixel rasterizer fits the first 2 catagories, but is unknown in the other 2 until the rest of the game is most of the way complete.
#134969 - gazsp - Wed Jul 18, 2007 10:37 pm
Well, thanks for all the replies so fay guys.
The engine does seem to slow down as I add objects to the screen. Is there anyway I can keep the speed (close to) constant?
I don't want it speeding up and slowing down as objects are removed / added :-)
#134973 - Miked0801 - Wed Jul 18, 2007 10:56 pm
Fix your framerate at 30hz to start. That will keep the game at a predictable level and give you some cycles to work with.
Profile your code to determine where the slowdown is taking place per object.
#135010 - gazsp - Thu Jul 19, 2007 10:33 am
As it's off topic, I've posted a new question about profiling here: http://forum.gbadev.org/viewtopic.php?p=135009.
Thanks for all your help so far everyone :-)
Cheers,
Gaz.