|
TICT TUTORIAL SERIES 2 - Part I
| (c) TI-Chess Team 2001 |
|
Texturing Vertical Strips
|
Focus Of This Series
As promised a long time ago I have started now a second Tutorial Series about
advanced TIGCC Programming Topics. The new Series aims to intermediate and
advanced TIGCCC programmers. If you have just started coding in C or if you are
not comfortable with the TIGCC Environment, I suggest that you start first
reading the first Tutorial Series which can be downloaded at
http://www.ticalc.org/archives/files/authors/32/3274.html. The second
Series is definitely NOT for beginners.
If you don't understand something in this Series please use the TIGCC Programming Forum at
http://pub26.ezboard.com/btichessteamhq
to ask your questions. and don't mail to me directly. Every day I get more than
a dozen mails and it cost me too much time to answer all of them (nevertheless
bug reports or positive feedback is very welcome in any form).
Software used to produce this Series:
Focus Of This Tutorial
I know "Texturing Vertical Strips" is a very weird title for a tutorial.
Now what is this? I think a picture says more than thousand words.
Suppose you have a grayscale texture of size 64 x 64 pixels and want to stretch
and pinch it that it will fit into the red outlined figure. To perform this you need
an algorithm which can scale a random column of the texture by a random factor. There are
many different names for this mechanism. I have choosen to call it "Texturing Vertical Strips".
"Scaling Vertical Texture Spans" would be also a suitable name.
|
 |
If you ever have played Wolfenstein3D, DOOM or any similar 3D game, then it should be obviously
to you for what this "texture scaling" mechanism may be used.
This tutorial will show you how to perform the scaling of a single column really fast by using
a pre-calculated lookup table. The given demo implementation should be seen only as "proof of
concept". It's written in plain C and contains everything (data and code) in one file.
For a real implementation the data of the lookup table as well as the data for the texture
should be stored in compressed form in an external variable. Using a little bit inline assembler
"magic" for the inner loop would als speed up the whole stuff. But as stated above: its just a
"proof of concept" and in its form no "production code".
The demo code is capable of scaling strips of height 64 to a heights between 1 and 64, but it
should be easy to modify the code to use other values.
Screenshot of the "Proof of Concept" Program (scaler.89z/scaler.9xz).
Note that this program
produces just a "still" image, but if you improve it further you may use it for some kind
of "weak" realtime 3D, too. For real good and fast 3D additionally algorithms are necessary like a
raycasting algorithm.
|
 |
used Texture |
 |
Straightforward Implementation (lame)
Suppose we are not limited by the hardware and we want to scale a source strip of height 64
to a destination strip of height of dest_height. The straightforward implementation
(pseudo code) may looks like this:
//------------------------------------------------------------------------------
// (dest_x,dest_y) ... position in screen memory where the strip should be drawn
// texture_x ... column number of texture which should be used as input
// dest_height ... destination height (1..64) NOTE: 0 is an invalid height
//------------------------------------------------------------------------------
void RenderStrip(short dest_height,short dest_x,short dest_y,short texture_x) {
double delta_y = 64.0/dest_height;
double texture_y = 0.0;
COLOR color;
short actheight;
for (actheight=0; actheight < dest_height; actheight++) {
color = GetTexturePixel(texture_x,(short)texture_y);
texture_y += delta_y;
SetDestinationPixel(dest_x,dest_y+actheight,color);
}
}
If you try to implement such an algorithm you will notice that its slower than a
snail on your calculator. This slowness is caused by the floating point operations.
In the above approach one floating point addition and one conversion of a floating point
number into a short (the cast) is necessary for each drawn point and this makes the whole processing
crawl.
Implementation using a Lookup Table (fast)
The speedup idea is simple: don't use any floating point calculation! Nice idea, but how to
perform this?
Suppose we have an array which consists of 64 other arrays (one for each destination height value).
Suppose further that these arrays hold the texture_y values which where used in the above straightforward
implementation. Then during rendering floating point operations are not necessary anymore and can
be replaced by a simple lookup of the value in the lookup table.
The optimized routine will look like this:
//------------------------------------------------------------------------------
// (dest_x,dest_y) ... position in screen memory where the strip should be drawn
// texture_x ... column number of texture which should be used as input
// dest_height ... destination height (1..64) NOTE: 0 is an invalid height
//------------------------------------------------------------------------------
void RenderStrip(short dest_height,short dest_x,short dest_y,short texture_x) {
short* table_for_height = lookup_table[dest_height-1];
COLOR color;
short actheight;
for (actheight=0; actheight < dest_height; actheight++) {
color = GetTexturePixel(texture_x,table_for_height[actheight]);
SetDestinationPixel(dest_x,dest_y+actheight,color);
}
}
Filling the Lookup Table
In a first approach I implemented the filling of the lookup table
within the program itself (performed during startup). But even this "one-time"
calculation of the values took "years" and the program started with a delay of
many seconds which wasn't acceptable (at least for me). Therefore I have implemented a
tiny tool called genlookup which calculates the values in form of a static array on the PC.
If you ever have wondered (BTW: I have ;-) how to define a static array which
holds arrays of different sizes, here are the first lines of the lookup table:
unsigned short** lookup_table = (unsigned short *[64]){
(unsigned short [1]){0},
(unsigned short [2]){0,256},
(unsigned short [3]){0,168,176},
(unsigned short [4]){0,128,128,128},
(unsigned short [5]){0,104,104,96,104},
(unsigned short [6]){0,88,80,88,88,80},
(unsigned short [7]){0,72,72,72,80,72,72},
// .... and so on ....
I took me quite a while to figure it out (BTW: the numbers in the square brackets are not necessary).
Conclusion and Outlook
The "Alpha-And-Omega" of Speed Optimization is to know the following facts:
- which values have to be really re-calculated
- how often are values re-calculated
- how long takes the re-calculation
Operations that are performed for each pixels should be executed fast and should be
reduced to a minimum, because there are thousands of pixels being processed.
Using lookup tables instead of re-calculations is one of the major techniques to make
a program fast. In this case you will treat memory for speed. But there are also other
techniques like fixpoint arithmetic where floating point calculations are performed by
using integer operations.
Each of these techniques may be worth a tutorial, but if I find the time for this is
very questionable. Actually I'm working on a kind of raycasting engine. This first
tutorial of the second series is a kind of side effect of this project.
Another reason of this tutorial is that I want to see more 3D games for the TI89/92p.
The processor is fast enough and there is plenty of RAM available in the calculator.
When I think back on the time when I have first played Wolfenstein3D and I can remember
that it was on a machine which a processor comparable to the one used in our calcs.
But the game was rendered with 320x200 pixels which is 4 times more than available
on the LCD of the TI-89. This games are possible on the calc and they can be implemented
using C. Maybe with some help of inline Assembler for the last Speedup, but for concept
proofs this is not necessary.
So what are you waiting for? Examine the sourcecode attached to this tutorial,
research the Net for some more informations and start coding ....
... And The Credits go to:
Copyleft
This program may be distributed by any other website for non-commercial use only.
DISTRIBUTIONS ON ANY OTHER MEDIUM (Disc,CD-ROM,DVD etc.) are PROHIBITED without separate allowance of the author.
The author makes no representations or warranties about the suitability of the software and/or the data files, either express or implied.
The author shall not be liable for any damages suffered as a result of using or distributing this software and/or data files.
You are free to re-use any part of the sourcecode in your products as long as
you give credits including a reference to the TICT-HQ (http://tict.ticalc.org/).
Contact TI-Chess Team Members
Check the TICT HQ Website at http://tict.ticalc.org for more
tutorials and software.
More useful tips, tricks and hints can be found at our Messageboard at:
http://pub26.ezboard.com/btichessteamhq.
Suggestions, bug reports and similar are VERY welcome (use our Messageboard for this!!).
How to Thanx the Author?
Like Xavier from the Doors Team I like it to get postcards from all over the world.
If you want to thank me, just send me an postcard with greetings on it. Thats enough.
UPDATE: since the last half year of working I just got 3 postcards. It looks like
that almost nobody find these tutorials worth a card, so why should I waste time
any longer writing them? :-(
My address is:
Thomas Nussbaumer
Heinrichstrasse 112a
A-8010 Graz
Austria
... and please: no mail bombs if one of my programs had crashed your calculator!
Thomas Nussbaumer Graz,Austria 21/02/2001 - TiCT's First Anniversary