

                  TAGL Threedee Advanced Graphic Library
                  --------------------------------------

Author
------

Bruno Levy
levyb@loria.fr

1. Introduction
---------------

TAGL is a library that provides a subset of SGI-GL functionalities. Its main purpose is to
be portable and extensible. 
It has been developped under Linux, but it can compile under whatever Unix system with X. 
On other systems, it requires a little bit of work, but not much. The SVGAGraphicPort 
(for Linux SVGALib) has been written within an hour. 

Some of its features are (o) or will be (-):

o portable framebuffer class
o virtual constructors
o (convex)polygon clipping
o polygon shading
o dithering
o RGB emulation in 8bpp mode (dithering)
- Alpha (for translucent objects)
o ZBuffer
- Texture mapping 
o built in sine and cosine tables
- 99 per cent of integer math 
- 3D transform matrices
- Blitting and bitmap scaling
- Text output 
- mpeg decoding ...

2. System design
----------------

You can skip this section if you don't want to know how this works ...

The design of the library is based on the architecture of a real computer graphics 
pipeline. A graphic system is composed of a framebuffer, a colormap, input devices,
and several graphic processors. All of these are called "graphic components". All
graphic components are linked by two busses, a command bus and a data bus. There is
also an entity called "bus switch" that allows data to be switched between host 
adapter bus and graphic busses. 

2.1. Conceptual design
----------------------

Here is a part of TAGL inheritance tree:


                    GraphicComponent
                      /        \
               GraphicPort    GraphicProcessor
              /    |            |         \     \
           XGP  SVGAGP ...  PolygonEngine Blitter  FontGenerator  
                             /   |    \      
                            PE8 PE555 PE24

The graphic bus is represented here by static fields of the GraphicComponent class. They
are shared between all GraphicComponent instances, so that they can exchange information
quickly and easily. These fields are :

_graph_mem      = the adress of the frame buffer
_colormap       = a translation table that converts colorindexes to system colorindexes 
_width,_height  = framebuffer size
_bytes_per_line = can be different from _width * _bytes_per_pixel if there is padding
_z_mem          = zbuffer
_clip           = clipping rectangle 
_bits_per_pixel
_bytes_per_pixel
_R_mask   |
_G_mask   | "graphic endianness" 
_B_mask   |       

2.2. Structural design
----------------------

The graphic pipeline looks like this:

	vertex
          |
          |   transform
          v
	vertex
          |
          |   project
          v
	vertex
	polygon
          |
          |   clip
          v
        polygon
	  |
          |   tesselate
          v
	polygon
          |
          |   fillpoly
          v
        pixels

A vertice is transformed by two matrices. The resulting polygon is clipped, and it 
generates another polygon. The latter polygon is transferred to the screen.

2.2.1. Transforming
-------------------

It uses (will use) integer math only. Numbers are represented by two classes, a Coord
is a coordinate of a vector, and a Coeff is a coefficient of a matrix. They work the
same way, internal representation of numbers are multiplied by a power of two
(left shift). A VertexCache identifies vertices that already have passed through this
stage, and avoid to compute several time the same vertice. This can occur, if a vertice
of a mesh is common to several polygons. This is implemented in the geometry engine class.
For the moment, Coeff and Coords are doubles, but they are embedded in classes, so that
it won't be much difficult to replace it with longs.

The other operations are handled by the polygon engine class.

2.2.2. Clipping
---------------

The clipping code is an implementation of Sutherland-Hogdman's algorithm. The library
handles polygon as an array of pointers to vertices. This level of indirection allows
insertions and tesselations without increasing the data flow. When new vertex are
generated, attributes are interpolated. Current attribute mode describe wich attributes
are to be handled.

2.2.3. Tesselation
------------------

TAGL filling routine is not able to fill concave polygons. This operations subdivides
a concave polygon into several convex polygons, without generating new vertices.
Whatsmore, it's necessary to subdivide large polygons when doing texture mapping in
perspective projection mode. It reduces interpolation errors.
(not implemented yet)

2.2.4. Polygon filling
----------------------

The algorithm has two passes. In the first pass, the boundary of the polygon is put into
an auxiliary structure. This structure countains for each scanline the information about
its leftmost vertex and its rightmost pixel. The second pass draws each scanline of the
polygon. There are many different routines, one per possible combination of the
attributes.

2.3. Coding
-----------

I have chosen C++ for the project. It reduces the spectrum of potential users since
its not available everywhere, but it's  possible to distribute compiled libraries and 
call it from a C interface for people that do not have C++. Anyway, C++ is more and
more spreaded, ask your local sysadm to install a gnu c++ distribution if you don't have
one availabe. 
C++ allows strong type checking, operators overloading, and high level object oriented
abstractions. And what I consider really important is that it allows to have a great
control of what kind of code will be generated. This is necessary for a real time
graphic engine.

For instance, a member function can be

     o inline   -> just like C macros, with type checking before expansion.
                   It costs just as much as a macro.
     o static   -> no instance pointer is passed, the cost is exactly the same
                   as for a C function.
     o "normal" -> Default case. Pass a pointer to the current instance.
                   It also costs as much as a C function.
     o virtual  -> The address of the function is retreived in the virtual table
                   of the instance, it costs a little more than a call to a C
                   function.

In TAGL, a class is represented by three files :

	xxxxx.h   -> class definition, constants, typedefs.
	xxxxx_i.h -> inline functions.
	xxxxx.C   -> code, static members declaration.

Having a separate header for inline functions ensure the mobility of these functions. 
If they become too big to be inline, they can be moved to the ".C" file, without modifying
the ".h". Whatsmore, it makes the ".h" more readable.

2.3.1 Generic filling routine
-----------------------------

The generic filling routine is a '.h' file. 
Several macros will be defined before including it. They define what code will be generated,
and which attributes will be interpolated. Some code can be inserted.
The macro GENFILL_DO_PIXEL defines what the function will do for each pixel.
If GENFILL_SCAN is defined, it will be done for each scanline, and pixel level code won't
be generated. GENFILL_NAME is the name of the generated function.
This file may be included several time in the same file. This trick makes it easy to write
a new polyeng_XXX class. And the use of the virtual constructor avoids modification of
the other parts of the library (see below). 
If somebody wants to write polyeng_664, polyeng_565 and polyeng_655, go ahead !!!
(It should take an afternoon for each).

Have a look at polyeng_XXX.C and genfill.h for more details.
I can also give more details via e-mail ...

2.3.2 Multitechnology support and virtual constructors
------------------------------------------------------

With TAGL,
the same program can run under SVGAlib and X11. Whatsmore, support for a new device 
can be added to the library without recompiling it. Multitech is supported through
a high level primitive called a VC (Virtual Constructor). C++ doesn't have
support for real virtual constructors, so it is implemented as a class in the
library. A VC has a table of function ptrs, returning either a pointer to the
allocated object, either NULL if construction wasn't sucessfull. A new technology
support may register to the virtual constructor in order to be taken into account
at object creation time. This is performed via a "Stub" classes, that will have it
constructor called before the begining of main().

Here is the code for registration of a PolygonEngine
MakePolygonEngine checks graphic endianness, and returns a valid PolygonEngine_555 if
its correct. The stub registers this function to PolygonEngine_VC (Virtual Constructor).
A client may call MakePolygonEngine(), which is the client interface to the virtual
constructor. 

PolygonEngine *MakePolygonEngine_555(GraphicPort *GP, int verb)
{
  PolygonEngine *PE = new PolygonEngine_555(GP,verb);

  if(PE->BitsPerPixel() != 15 ||
     PE->RedMask()      != (31 << 10) ||
     PE->GreenMask()    != (31 << 5)  ||
     PE->BlueMask()     != 31          )
    {
      delete PE;
      return NULL;
    }
  return PE;
}

class PolygonEngine_555Stub
{
public:
  PolygonEngine_555Stub(void) 
    { 
      PolygonEngine_VC.Register(MakePolygonEngine_555); 
    } 
};

static PolygonEngine_555Stub Dummy;


The drivers are not included in the library for several reasons.
First, it is possible to add new drivers, and there is no reason to make a difference between 
standard drivers and user defined ones.
Second, when the linker merges a ".a" archie file, it checks for each ".o" countained by
the ".a" if it's referred. Drivers are not externaly referred, since they have been designed
so that client code does not need to be modified when a new driver is added. The only external
reference will be the call to the constructor of "Dummy", that will register the function 
"MakeXXX". The linker does not detect that, because it is not an explicit reference, so the
drivers could not be linked if they were in the ".a". 
That's why the driver are in a separate directory. It should be possible to link dynamically
a ".o" to a running program (it works for simple functions that don't have global data)

3. Tagl classes
---------------

Most classes of tagl are derived from a top class : GraphicComponent. A GraphicComponent
is plugged to the graphic port (static members _graph_mem, _colormap ...), and has a
stack of operating modes, called attributes. A virtual member function modifies or
restore the current operating mode.
A GraphicProcessor is a GraphicComponent plugged on top of a GraphicPort.

3.1. GraphicPorts
-----------------

In order to be portable, the library uses a machine abstraction layer. All the system
dependant stuff is embedded in an entity called a GraphicPort. A GraphicPort handles
framebuffer initialisation, colormaps, input (kbd and mouse), ZBuffer allocation and
double buffering. There is a GraphicPort for X11, and one for Linux-SVGAlib. It should
not be difficult to write a GraphicPort for other systems (even if XGraphicPort gave me
an headache :-) ).

3.2. PolygonEngines
-------------------

This class performs polygon filling, attributes interpolating and Z-Buffer. It handles 2D
coordinates, attributes, and depth. There is one polygon engine per possible graphic depth
and endianness. There is a filling routine for each possible mode combination, written with
the help of the generic filling routines, so that each function takes at most 10 lines,
5 minutes to write ( and 10 minutes to debug ;-} ). PolygonEngines also handle line drawing
and SetPixel().



3.3. GeometryEngines
--------------------

It is the high level interface to PolygonEngine. It performs 3D transformations and vertex
attributes handling. It offers an API similar to GL functions for polygons.
(Not implemented yet, will be in TAGL next release).
