# Palomino Implementation

©1986,2006 Jim E. Brooks http://www.palomino3d.org http://www.jimbrooks.org/sim

See also Palomino Design and Palomino Modules.
This document should be neither too abstract nor too detailed.
vertexs/matrixs [sic] are spelled for searchability.
gfxsys is an abbreviation for the underlying graphics system (OpenGL).
Diagrams were drawn using GNOME dia.

# Contents

- Introduction
- Overview
- Initialization
- Render()
- Draw()
- Visible()
- Animate()
- Timer()
- Object class
- World, Quadrant, Locus classes
- ObjectGroups and Shadow Quadrants
- Engine class
- InputQueue class
- View class
- PolygonList
- Polygon normal vectors
- Collision Detection, Detector object list
- Caches
- Sharing objects
- Zombie list
- Configuration
- Textures
- Importing models (from Blender)
- GFX() wrapper functions
- OpenGL code
- Source code, Compiling, Platforms
- Reminders
- Interface between 3D Engine and Modules

## Introduction

This describes the OpenGL implementation. The source code is written with macros and wrapper functions to provide some abstraction of the underlying graphics library ("gfxsys" henceforth).

## Overview

The essence of the program is to manipulate and render 3D objects. The program constructs instances of the Object class, transforms them in 3D space, and submits them to the gfxsys which renders them. Rendering is driven by a timer and repaint/input events. The program transforms 3D vertexs itself (OpenGL modelview matrix stays identity-mapped).

### Features

- Source code:
  Written in C++ using GNU tool-chain.
- Target platforms:
  Portable to GNU systems supporting OpenGL.
- Modules:
  Low-level graphics functions, 3D engine, game modules.
- Event interface:
  Each module can broadcast events to listeners in other modules. As opposed to direct C function calls, this facilitates substituting modules.
- Run-time optimizer:
  Similar polygons are grouped to avoid GL state changes.
- Subdivided world:
  Objects are placed in quadrants and are dynamically created/destroyed, quadrants around the Eye are rendered and cached (a form of lazy-allocation).
- Caching:
  Object data and transformed vertexs are stored in software caches (reduces memory consumption).
- Efficient collision-detection:
  Different algorithms with different execution times and precision are used to detect when a 3D object has collided into another.
- AI:
  AI is implemented as a frame-driven state-machine that executes virtual instructions.

## Initialization

The program initializes the World object, an initial set of Objects, and the gfxsys. Optionally, saved state (player position/angle) is reloaded.

## Render()

[2006/08]

The render loop is invoked when a redisplay is needed. Sources of redisplays are animation or the gfxsys. Animation, which is driven by a timer tick, posts a redisplay if an object was animated. The gfxsys posts a redisplay in order to repaint the window. The program can quiesce while no redisplays are needed.

The render loop appends all visible Objects to a container, sorts the container by distance from each Object to the Eye, then calls the Draw() method of each Object.

The render loop guarantees:

- Object::Draw() is only called if Object is visible.
  (indirect exception: a visible ObjectGroup calls Object::Visible() for each of its Objects)
- Omni::Draw() is called if Omni is visible and only once per frame. Omnis are linked in a special Quadrant separate from other Objects [2006/11].

    Engine::Render():
        objs = []

        for each Quadrant in Locus that is visible:
            for each Object in this quadrant:
                if not Omni or first visible quadrant:
                    objs.append( object )

        objs.sort()  // sort by distance from Object to Eye

        for obj in objs:
            obj.Draw()

## Draw()

[2006/05]

The Object base class has a virtual Draw() method. Most Objects defer to the generalized PolygonList::Draw(), but some Objects (sky box) define their specialized Draw() methods.

Typical actions of a Draw() method:

    Object::Draw():
        if Dyna:
            transform local vertexs into world vertexs
            transform local normals into world normals
        transform world vertexs into eye vertexs
        for each polygon:
            if PolygonFacing():
                for each vertex index (vix):
                    submit vertexEye[vix]
                    if texture:
                       submit 2D texture (x,y)

    PolygonFacing( worldVertexs, normalsWorld, polygon.vix[0] )
        calculate dot product of polygon's first vertex and eye origin (world space)
        return dot product >= 0    # true if facing

## Visible()

See Visibility Testing and Level-of-detail.

    Object::Visible():
        distance test:
            calculate distance between center world vertex and eye
            return false if too distant
        facing test:
            transform center vertex
            add radius to center eye Z
            return false if Z < 0    # if object is not facing (behind viewpoint)
        viewport test:
            transform object's position from world space to eye space
            make a 2D square (NW,SE) in eye space by adding (radius,radius,0) and (-radius,-radius,0)
            project 2D square
            return if 2D square lies outside 2D viewport:
        return true    # visible

## Animate()

Animate() is called by Timer(). Dyna objects (eg aircraft) are translated and rotated. If any Dyna objects were animated (changed), the routines post a repaint message to the gfxsys (which indirectly causes the render routine to be invoked).

The Game object maintains lists of animatable Dyna objects (Craft, Tracer). Animate() iterates thru these lists, calling Dyna::Animate().

## Timer()

This drives the render routine and the animation of 3D objects. A timer is used to achieve smooth rendering (assuming the system is fast enough).

## Object class

This is the base class of all 3D objects. See Objects in Design.

The Object class exploits the C++ feature of redefining virtual methods in derived classes. For example, Object::Draw() draws a object using its PolygonList. But Special objects such as the sky box do not have a PolygonList, so Object::Draw() is redefined.

A set of Get*() methods are used to abstract the source of data. For example, Object::GetNormals() will initially calculate the normal vectors on each polygon and insert them into a cache. When called again, Object::GetNormals() return the cached calculations. The Dyna class overrides GetNormals(), see Polygon normal vectors.

## World, Quadrant, Locus classes

These define the simulated 3D world. They're documented in Design.

## ObjectGroups and Shadow Quadrants

[2006/05]

An ObjectGroup is an optimization that reduces visibility calculations. It contains (both geometrically and programmatically) a set of Objects.

Geometrically, an ObjectGroup is a bounding cube that encloses its Objects. When an ObjectGroup is not visible, then none of its Objects are visible. But an ObjectGroup that is visible doesn't necessarily mean each of its Objects are. For example, if the right part of the cube is visible, then Objects in the left part aren't visible. This is the reason why, as a special case, the Draw() methods of grouped Objects still need to call Object::Visible().

Grouped objects are excluded (hidden) from the render loop. This is an optimization implemented by "shadow quadrants". The render loop is based on iterating thru normal quadrants in the locus. Grouped objects are linked into separate shadow quadrants which occupy the same location in world space. Shadow quadrants are necessary (and better than Object::mQuadrant = NULL) since the Object class and much of the engine code assume an Object is linked with a Quadrant.

## Engine class

The Engine class of course represents the 3D engine. The 3D engine does actions such as initializes the gfxsys, render objects, test visibility of objects, loads textures from files, updates the Locus, etc. To interface with modules, it broadcasts events to listener functions. See Palomino Modules.

## InputQueue class

This is a low-level class that handles keyboard and joystick events from the underlying gfxsys. It enqueues input events, and provides an interface to poll and dequeue them.

Regardless of "queue" being in the name, InputQueue doesn't queue joystick events. Rather, InputQueue effectively returns the last joystick event, discarding prior events. The reason is that a noticable delay and jerky response would result if multiple joystick events are queued while rendering a frame, then processed suddenly at the frame's end. On Windows, the InputQueue class does no special action as the Windows joystick driver just samples the joystick's latest state. But the Linux joystick driver queues events, so the InputQueue class has Linux-specific code to discard prior events.

## View class

A View object represents a viewport where the gfxsys renders into and stores rendering state. A viewport is a subdivision of the main window. For example, the main view and radar are defined by separate View objects. ViewMain manages and contains View objects (in addition to managing its viewport). Some ViewMain methods/data can still be accessed regardless of the current view. ViewMain can be rendered and is the main viewport (usually thru front cockpit).

## PolygonList

A PolygonList is composed of segregated lists of Polygon objects. A Polygon object is composed of a PolygonAttribs, RGBA, and Texture objects.

One reason for the decomposition is to maximize sharing of objects. Every Polygon in a PolygonList may share the same PolygonAttribs object. The same RGBA value could be shared by Polygons even in different PolygonLists.

A PolygonList is effectively shared by calling its copy constructor. This does a shallow copy and uses a reference count to share resources. See Sharing objects.

A PolygonList is built by successively calling PolygonList::NewPolygon(), then finally calling PolygonList::Optimize(). The idea of Optimize() is to group polygons to minimize OpenGL state changes. Optimize() will segregate the polygons into separate lists which can be more efficently rendered using corresponding specialized Draw*() methods. For example, textured polygons are sent to DrawTextured(), but untextured (opaque) polygons are sent to the faster DrawOpaque().

## Polygon normal vectors

In this implementation, normal vectors on polygons are calculated from world vertexs using a PolygonList object. Normals vectors are used to cull polygons that aren't facing the viewpoint/eye. The base Object::GetNormals() method will initially calculate the normal vectors and store them in a cache to bypass re-calculations. The Dyna class, since its world vertexs/normals are dynamic, redefines Object::GetNormals() to always calculate the normals without caching them.

## Collision Detection, Detector object list

See also Collision Detection in Design.

Collisions are detected by a Detector object. An Object which is "collidable" creates its own Detector object. Detector::Collided() returns true if the passed Dyna object has collided into the Object's Detector.

An example is during animation of Tracer objects (gunfire). A loop passes all Dyna objects (craft) to the individual Tracer's Detector::Collided() method to test if the Tracer has hit any Craft (Craft is derived from Dyna).

Every Quadrant maintains a list of Detector objects. This speeds collision detection into Fixed (stationary) objects. For example, when a Dyna object is translated (moved), a collision detection test is done to determine if it has crashed into anything else [Dyna::CollisionDetection()]. Iterating thru all of the objects in a Quadrant (which was implemented) was slow, and unnecessary since most objects aren't considered collidable (eg small trees).

Collision-detection is started by Craft::Translate() when a craft is translated. It calls Dyna::CollisionDetection() whichs iterates thru the list of Detector objects in the same quadrant as the Craft. Objects such as protruding terrain (hills), buildings, and other Craft have Detector objects.

## Caches

See Caches in Design.

A software cache is used for two purposes: to avoid recomputing an object, and/or to save memory by freeing objects which haven't been used recently. Caches are constructed using the C++ class template "Cache" gfx_cache.hh

## Sharing objects

C++ objects can be shared in different ways.

### Sharing objects using ShareVal or SharedPtr template classes

Objects (data structs), which exist in multitude with the same repeated values, such as RGBA values, polygons, polygon attributes, are shared to save memory. The C++ template class SharedVal in gfx_shared_val.hh is based on a STL map containing pointers to shared copies of objects and their reference counts. When SharedVal::Share() is passed an object, it looks thru the map for an object with the same value, and if found, returns it and increments its reference count, otherwise, it inserts the object. SharedVal::Unshare() decrements the reference count, and deletes the object when the count becomes zero.

Copies of objects are shared, rather than the originals, to avoid the complication that would arise when the shared object's reference count hits zero, but what if the original object is static (delete can't be used) or if it's in the heap (delete should be used). Testing object equality is done by their values, not their addresses, as two separate objects could have the same value.

An object that is identified by a pointer can be shared using the SharedPtr class. SharedPtr is better suited than SharedVal when a specific object needs to be shared versus sharing the value of an object.

### Sharing an object's resources rather than the object itself

If writing a copy constructor that does a "deep copy" is impractical (which the SharedVal template class requires), an alternative is to share an object's resources, rather than the object itself. This applies to objects with a small foot-print and whose resources are pointed to. A copy constructor could be safely written to copy pointers to resources by using an "untied" reference count (a reference count allocated on the heap). Sharing an object is effectively done by the copy constructor. The destructor only deletes the resources when the last object is deleted (when the reference count becomes zero).

An example of this is how PolygonList objects are shared (eng_polygon.cc). The way of sharing was chosen because of the impracticality of writing a Dlist copy constructor that SharedVal requires.

## Zombie list

The zombie list (marked-for-deletion list) is a list of Objects that have decided to delete themselves. A C++ object cannot directly delete itself. Instead, an Object appends itself to the zombie list [Object::Discard()]. For example, a Tracer that hits an object will stop/delete itself by calling Object::Discard in lieue of delete. The zombie list is purged after rendering every frame.

## Configuration

The ConfigFile class is used to store various state (player's matrix, joystick calibration, LOD, fog density, etc). The configuration is a set of key/value pairs. A value can be 1 of 3 types: int, float, string. The configuration file consists of lines of human-readable plain-text. Each line defines a key/value pair. The file terminates at a line containing "END". For example:

    # palomino configuration (gfx::ConfigFile v2)
    int collisions 1
    int joystick 0
    int joystick_axis3 1
    int response_chase 0
    int response_eye 0
    double fog_density 0.50000000000000000000
    double gui_zoom 1.00000000000000000000
    string lod 3 MID
    END

## Textures

### Constructing and loading textures

The simulated world is constructed before the gfxsys is initialized. But the constructors of some Objects (C++ objects) construct Texture objects (C++ objects). Therefore, the Texture class was designed to accept texture data and settings at any time, but defers creating (binding) the actual graphics texture until the gfxsys is ready.

### Texture class

The Texture class is given ready-to-use texture images from clients. Thus, the class is insulated from the source of the texture (graphics file, dynamically-generated texture, etc).

Features of the Texture class:

- instances can be constructed at any time, even before gfxsys is initialized
- clients obtain the texture image from arbitrary source and give it to the class
- clients can change texture properties by public methods
- texture image data can be specified as static or mutable (static for sharing texture images)
- texture settings can be extracted into an opaque struct then switched by client

### Texture settings

Texture settings are controlled by various setter methods. All the settings can be extracted out of the Texture class into an opaque struct. The opaque struct can be passed back into the Texture object. This facilitates switching texture settings by the client.

### Static/mutable texture images

The Texture class is designed to manage the host buffer that holds the texture image. Some textures are given texture data which nevers changes. But the ability to dynamically modify texture data is needed.

StaticTexture class supports only a static texture image. MutableTexture class allows dynamically altering its texture image. The reason is to conserve memory: StaticTexture can release the host buffer after the texture image is sent to the gfxsys (as an OpenGL "texture object"), but MutableTexture must keep the host buffer allocated to allow the client to modify it. This limitation stems from OpenGL not providing a way to read back a texture into host memory.

The adjectives static and mutable refer only to the texture image (host-side buffer in particular). Both classes allow the client to modify texture settings at any time.

    class Texture
    {
    public:
        Texture( uint width, uint height, uint depth=1 );

        uint8*   GetBuffer( void );
        uint     GetBufferLen( void );
    };

    class StaticTexture : public Texture
    {
    public:
        void     CommitBuffer( void );  // GetBuffer*() will fail after this is called
    };

    class MutableTexture : public Texture
    {
    public:
        uint8*   BufferWasModified( void );  // notifies the class of buffer modification
    };

StaticTexture lets the client write to the buffer. The client must call CommitBuffer() for the graphics object to be affected. CommitBuffer() will push the texture image to the gfxsys, then free the host-side buffer. Thus, the client cannot write to it again!

MutableTexture also lets the client write to the buffer. The client must call ModifiedBuffer() for the graphics object to be affected. Unlike StaticTexture, the client can repeatedly modify the buffer and call ModifiedBuffer().

## Importing models (from Blender)

[2006/08]

The Blender Python script `export-palomino.py` can export a Blender model into a data format (.pal) that Palomino can understand.
Here's a picture of Blender with the Palomino export script. Since the .pal format is difficult to read, the script can optionally output verbose XML (toggle Format button).

### Data format for importing models

(Exact details subject-to-change but the basic structure should remain the same)

The .pal data format is an extremely simplified markup format. The format has tags analogous to XML but it isn't true XML. It is a compromise between efficient parsing by C++ stream code vs. being barely human-readable for debugging.

Sections are always marked by a start tag. An end tag is present unless the start tag has the finalizing slash char: "<tag/>" as opposed to "<tag>". Every item in a section must be on its own line. If a section has variable amount of items, they items are prefixed a count (so a C++ container can be allocated for the items without needing to scan forward to an end tag). The count can be omitted in sections with a predetermined amount of items (eg RGBA always has 4 items). These restrictions simplify and speed parsing by C++ stream code.

To minimize the format, the XML "empty" tag syntax (where a '/' follows the tag name) is used in cases where the amount of lines that follow is known at the point where that tag was encountered. Otherwise, a separate end tag is used (where a '/' precedes the tag name). Eg, <v/> is used rather than (<v>,</v>) since the amount of lines that follow is given by the next line which contains a vertex count. By contrast, (<p>,</p>) is necessary for polygons since one may or may not contain a texture tag (how many lines follow <p> isn't yet known at that point).

For grouping and context, a naming convention for sub-sections is to append their names as suffixes to the section that encloses them. Eg, <pr/> means an RGBA value of a polygon: 'r' is appended to 'p'.

The .pal format's structure and order is:

1. <info ... />
Example:
<info ver='1.0' type='Palomino 3D model' name='tankAbrams' author='Homer' modelProg='Blender' modelProgVer='235'/>
All of this info is on one line so that the parser can quickly jump over it
(currently, none of this info is really used but is provided in case).
`ver` is the version of this data format (and of the Python export script).
`type` is just to tell a human what this file is for.
`name` name given to this 3D model.
`modelPrg,modelerPrgVer` identify the modeling program that produced the 3D model.
2. <ex> tags for storing data used by the Blender export script
3. <v/> vertex array
4. <n/> normal vector array
5. <p> polygon(s)

1. <pr/> RGBA
2. <pt/> texture name (or encoded data?)
3. <pv/> array of vertex indexs (into preceding vertex array)

6. </p> polygon end

For example:

    <info ver='1.0' type='Palomino 3D model' name='tankAbrams' modeler='Blender' modelerVer='235'/>
    <ex rot='90.0,180.0,0.0'/>     pre-rotates model (Blender export script)
    <ex scale='2.0'/>     pre-scales model (Blender export script)
    <v/>
    15                 count: 15 vertexs follow
    -8.48319530487     vertex[0].x
    3.13391828537      vertex[0].y
    0.0                vertex[0].z  [...]
    5.99767303467
    3.13391828537
    [...]              there is no </v> end tag because of <v/>
    <p>                beginning of polygon[0]
    <pr/>              RGBA value
    0.5                RGBA.r
    0.5                RGBA.g
    0.5                RGBA.b
    1.0                RGBA.a
    <pv/>              beginning of array of vertex indexs
    4                  count: 4 vertex indexs follow
    11
    14
    13
    12
    </p>
    <p>                beginning of polygon[1]  [...]
    <pv/>
    4
    7
    10
    9
    8

## GFX() wrapper functions

A set of GFX() wrapper functions and macros provides a large degree of independence of the underlying gfxsys. GFX() parallel the OpenGL API and are implemented for OpenGL .

## OpenGL code

Aspects of the OpenGL and GLUT code in Palomino:

- GLUT creates the window and handles window resize events.
- GLUT sends keyboard and mouse (but not joystick) events to application.
- GUI is rendered using OpenGL alpha-blending for transparency.
- GUI buttons are rendered in OpenGL 2D mode.
- GUI text rendered using OpenGL textures.

Matrix calculations are done by the program itself using matrix formulas I invented, rather than using OpenGL matrix functions. Thus, the OpenGL modelview matrix stays identity-mapped (1:1). Doing matrix calculations by program code might be slower: newer graphics cards could be capable of doing matrix calculations (concurrently with program execution).

## Source Code, Compiling, Platforms

Source code is written in C++ and developed primarily on Linux using the GNU toolchain.

Layout of source tree:

    gfx/src               gfxsys library
    input/src             input device (joystick)
    palomino/engine/src   engine core

For independence from graphic systems/drivers, a set of GFX_* macros are used to code the "OpenGL way" without writing actual OpenGL code. In theory, the GFX_* macros could be redefined to compile code for DirectX or another graphics system.

For posterity, was originally developed on these PC systems:
gemini: dual Pentium II/400Mhz, 3dfx Voodoo 3, Mandrake 8.1 Linux, BeOS 5 (gcc-2.9-beos-991026)
lion: Pentium III/533Mhz (Katmai), ATI Rage128, Redhat 8, FreeBSD 4.6.2
shannara: AMD K6-2/350Mhz, Windows 98, Nvidia TNT2, Debian 3.0 (woody)

### Source code style

Naming convention:

- camel-back: craftMatrix
- functions/methods begin with capital letter
- class members begin with "m"
  (writing "p"/"r" for pointers/references is too pedantic: compiler will catch misuse).
- global vars begin with "g"
- static vars begin with "s"
  whether static members begin with "s" depends on whether the fact it's shared should be exposed or concealed
- "cnt" for a count or anything that is incremented
  (rather than the ambiguous "s" suffix: eg does "polygons" mean an array or a count?)
- Get(), Set() methods for interface to private members or to abtract data,
  Get() should return a const whenever possible

The code is written in C++. It follows the conventional OOP doctrines: source code organized as classes, well-documented public interfaces, hiding internal methods/data, etc.

C++ RTTI and exceptions are avoided utterly. Casting is avoided as much as possible, esp. the dreaded reinterpret_cast(). One technique used to avoid them is the placement of dummy classes in base classes for whom only some of its descendants actually implement those classes. For example, only the Craft class has need for a ChasePlane class, not the Eye class. But since code manipulates Craft and Eye objects as the base Dyna objects, the Dyna class is given a ChasePlaneDummy class to avoid the mess of casting or special-case coding.

To catch memory corruption, type-signature checking is compiled in DEBUG builds.

### Summary of source directories:

- gfx/src/
  Library that provides independence of graphics system and OS.
- gfx/tests/
  Tests for gfx library code.
- input/
  Library for input devices.
- palomino/engine
  Palomino 3D engine code.
- palomino/game/base
  Palomino game base module (base classes, common code).
- palomino/game/pony
  Palomino "pony" game module.

## Reminders

### Do

- Occasionally compile with DEBUG=2.
- Do write world coord constants inside the WORLD() macro in case the world coord system needs to be scaled in the future.
- Do NULLify a pointer to a deleted object. This protects against multiple deletions in case a member pointer is static (delete NULL is a NOP).
- A bug results if a loop that iterates a list calls a function that alters it.

### Don't

- Don't save state across multiple frames (in an Object) unless the state is per-view (since multiple views are possible).

Last modified: Fri Nov 10 13:30:58 EST 2006