The Art of Demomaking - Issue 10 - Roto-Zooming by (25 October 1999) | Return to The Archives

Introduction

Welcome back for another week's worth of free knowledge :) Hope you appreciate it. This time I will tell you about roto-zooming, and the various different ways of doing it. You will also learn about basic 2D geometry, and also about profiling and visual performance testing.

The Theory Behind Roto-Zooming

Just like all the previous effects, roto zooming is really easy once you understand how it works. The basic idea is that you select an area in texture space that you will have to map onto the screen. The area you choose in texture space can have any shape, but things are much easier if you select a 4 sided polygon. Another possible simplification is to perform orthonormal roto-zooming, which means you map your texture from a rectangular area.
Orthonormal roto-zooming is the easiest to code, and arbitrary roto-zooming looks better. But it all depends what you want your effect to look like. Orthonormal rotozooming preserves the aspect of the texture, so it's probably best to use this method if your texture contains some text that needs to be read. Arbitrary roto-zooming makes the texture look wobbly, not very realistic, but somewhat cooler. We'll use orthonormal rotozooming. We only need the coordinates of 3 points in texture space: A, B and C.

      // compute deltas
         int dxdx = (Bx-Ax)/320,
             dydx = (By-Ay)/320,
             dxdy = (Cx-Ax)/200,
             dydy = (Cy-Ay)/200;
         long offs = 0;
      // loop for all lines
         for (int j=0; j<200; j++)
         {
              Cx = Ax;
              Cy = Ay;
           // for each pixel
              for (int i=0; i&kt;320; i++)
              {
               // get texel and store pixel
                  page_draw[offs] = texture[((Cy>>8)&0xff00)+((Cx>>16)&0xff)];
               // interpolate to get next texel in texture space
                  Cx += dxdx;
                  Cy += dydx;
                  offs++;
              }
           // interpolate to get start of next line in texture space
              Ax += dxdy;
              Ay += dydy;
         }

The only difference with arbitrary roto-zooming is a extra interpolation. And we need the coordinates of 4 points in texture space: A, B, C and D.

      // compute deltas for interpolation along Y
         int dx1dy = (Cx-Ax)/200,
             dy1dy = (Cy-Ay)/200,
             dx2dy = (Dx-Bx)/200,
             dy2dy = (Dy-By)/200;
         long offs = 0;
      // loop for all lines
         for (int j=0; j<200; j++)
         {
           // compute deltas for interpolation along X
              int dxdx = (Bx-Ax)/320;
              int dydx = (By-Ay)/320;
           // set starting position
              Cx = Ax;
              Cy = Ay;
           // for each pixel
              for (int i=0; i<320; i++)
              {
               // get texel and store pixel
                  page_draw[offs] = texture[((Cy>>8)&0xff00)+((Cx>>16)&0xff)];
               // interpolate to get next texel in texture space
                  Cx += dxdx;
                  Cy += dydx;
                  offs++;
              }
           // interpolate to get coordinates of next line in texture space
              Ax += dx1dy;
              Ay += dy1dy;
              Bx += dx2dy;
              By += dy2dy;
         }

All we need to do now is select the area of texture space we wish to map.

2D Rotation

Since we want to rotate and zoom our rectangular area of texture space, we need to know a bit about rotating 2D points. As I said in a previous tutorial, we use the sine function to do this. Given a radius, and a rotation angle, we can find the coordinates of our rotated point given the following equation:

            x = radius * cos( angle )
            y = radius * sin( angle )

This is all we need for our roto-zoomer, but you may also want to know how to rotate and arbitrary point around the origin. This is done with the following equation:

            x' = x * cos( angle ) - y * sin( angle )
            y' = y * cos( angle ) + x * sin( angle )

If you wish to rotate point A around another point B, simply translate both points so that B is at the origin. Then rotate A and translate it back by the same amount.

Dynamic Texture Mapping

This week's effect is a form of dynamic texture mapping. This means that we recompute our (u,v) coordinates at each pixel every frame. In the case of a roto-zoomer this is quite quick, since there is not much computation to perform. You could drastically boost the visual quality of this effect by implementing simple bilinear filtering and mip-maping. There's nothing new there, it's just a question of sitting down and doing it.
Another thing I should point out is the implementation of block rendering. Indeed as i mentioned in the tutorial about cache performance, this technique makes sure the effect runs at a constant frame rate, independent of the rotation angle. I've coded this for you, just because a roto-zoomer without block rendering is not worthy ;)

Profiling

A very important aspect of coding effects is getting them to run quickly. So obviously optimisation is needed. Now usually with a bit of experience you can tell, or at least guess where your program spends most of it's time and optimise the algorithm and code for that specific part. For those of you with less experience, finding the bottleneck of the code can be difficult. And that's where profiling comes in to the rescue.
Profiling is the process of running the program and timing each and every procedure in the program. So the output of the profiled program is a table that contains the number of times each procedure was called, and much time was spent in each one.
To enable profiling with DJGPP, simply compile with the -pg switch. Also remember not to use the -s switch. So type this at the command line:

           gcc *.cpp -o roto.exe -O2 -lstdcxx -lpng -lz -pg

Then simply run the program. Let it run a few seconds so the program can be profiled. Then simply type:

           gprof roto.exe > list.txt

This creates a file called list.txt that contains all the profiled information. The first few lines look like this:

        Each sample counts as 0.055556 seconds.
          %   cumulative   self              self     total
          time   seconds   seconds    calls  ms/call  ms/call  name
          61.54      0.89     0.89      185     4.80     4.80  VGA::Update
          38.46      1.44     0.56      185     3.00     3.00  BlockTextureScreen
          0.00       1.44     0.00      256     0.00     0.00  VGA::SetColour
          0.00       1.44     0.00      187     0.00     0.00  TIMER::getCount

Right, now we know this program is wasting most of it's time waiting for the vertical retrace. We also know the only procedure worth optimising (writing in assembler maybe) is the BlockTextureScreen one, and all the others are not worth bothering with.
Profiling is especially useful when your main loop calls more than one procedure. It seems a bit stupid to profile this specific program, since you all could have told me which procedure to optimise without even profiling ;)

Visual Performance Testing

Another simple technique to test the performance in real time involves a tricky hack with the palette. Basically we set the background colour to white while we are drawing, and change it back when we've finished. You will then see that the top part of the border is white, and the rest is black. The bigger the white portion, the slower the main loop is running. So you will notice drops in the FPS when the white part of the border gets much bigger. This happens for example without the block renderer, when the angle is approximately 90 degrees.
Another thing I just noticed with this method were the random jerks in the FPS. The white area sometimes covers the entire screen under Win98. This is extremely frustrating since it doesn't happen in good old DOS. I should have known that windows would make the program randomly miss vertical retraces. The answer would be to use Direct Draw, or run the program in DOS.

Final words

Roto-zooming can be pretty boring on it's own, but is very often at the base of the best looking effects. This particular implementation is quick, but has a lot of room for visual improvement. As for profiling, it can be very helpful in complex programs to help you determine what your program is doing and how long for. It's also useful for finding unexpected bad performance in some procedures.
Well, this time I've absolutely no idea what's going to happen next week. The only thing I know is that there will be at least one or two more issues of this column.
You can download this week's demo and source code package right here (128k)
Happy Coding,
Alex

Article Series:

> - The Art of Demomaking - Issue 01 - Prologue
> - The Art of Demomaking - Issue 02 - Introduction To Computer Graphics
> - The Art of Demomaking - Issue 03 - Timer Related Issues
> - The Art of Demomaking - Issue 04 - Per Pixel Control
> - The Art of Demomaking - Issue 05 - Filters
> - The Art of Demomaking - Issue 06 - Bitmap Distortion
> - The Art of Demomaking - Issue 07 - Bump Mapping
> - The Art of Demomaking - Issue 08 - Fractal Zooming
> - The Art of Demomaking - Issue 09 - Static Texture Mapping
> - The Art of Demomaking - Issue 10 - Roto-Zooming
> - The Art of Demomaking - Issue 11 - Particle Systems
> - The Art of Demomaking - Issue 12 - Span Based Rendering
> - The Art of Demomaking - Issue 13 - Polygon Engines
> - The Art of Demomaking - Issue 14 - Perspective Correct Texture Mapping
> - The Art of Demomaking - Issue 15 - Music And Synchronization
> - The Art of Demomaking - Issue 16 - The Final Product

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.