©2004,2007 Jim E. Brooks http://www.palomino3d.org
See also Palomino Design and Game Mode.
[2007/05]
The primary function of a 3D engine is to render 3D objects. The engine contains, culls, sorts, transforms, and renders Objects. Each Object consists of a Graph. Objects are constructed and controlled by application-level modules.
[2007/04]
[2007/04]
[2004/06]
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
[2007/08]
Parameters of the simulated World are defined by
the configuration file world.conf.
Parameters are described at world_conf.txt.
[2007/07]
The Engine has support for loading and setting Texture objects. Modules tell the Engine where directories are that contain texture files.
In each texture dir, a file named texture.conf contains texture parameters. Its format consists of these lines (correlates to OpenGL textures):
# comment
def_min_filter nearest|...
def_mag_filter linear|...
def_wrap repeat|...
def_func modulate|...
textureName { setting1 ... }
textureName // settings block omitted, default parameters implied
def_* specify default parameters (optional).
A texture is referenced by its filename (minus any suffix),
and its parameters are placed between braces.
Example:
# Palomino texture configuration version 1.0.
def_min_filter linear_mipmap_nearest
def_mag_filter linear
f14_pirate_64 { decal clamp }
[2007/06]
Globals are either defined as members of a Global class in each library, or as Singletons. Both have advantages and disadvantages.
As members of a Global class, globals become obvious and are easy to search. They're accessed by writing "global.mMember". The order of construction is the order they're declared in the class. And, they auto-destruct in inverse order at program exit. A disadvantage is that this order is limited to the scope of the class.
Singletons solve the problem of globals (or static objects) depending on other globals. Disadvantages are that Singletons don't auto-destruct as Global members do, and Singletons are difficult to find when searching for globals (for the purpose of implementing threading).
global::mWorld.GetEdge(); // obvious global World::GetEdge(); // hidden global
[2007/08]
Each partition of a graph has its own matrix. A parent partition transforms its child partitions. As each TransformNode of a Partition is visitied, matrixs are combined directly using matrix multiplication:
mMatrixLocal maps
VisitorDraw::Visit( TransformNode& node )
{
mMatrix = node.GetMatrix() * mMatrix;
}
This formula combines local:world and world:eye transformations using matrix multiplication.
It is based on the two steps needed to transform a local vertex to eye space:
transform local --> world : rotation, translation transform world --> eye : translation, rotation
Local vertexs are first rotated around their origin, then translated to world space. World vertexs, conversely, are first translated to eye space, then rotated around the eye's origin.
[ x ] * [ Xx Xy Xz Tx ] = [ x2 ] * [ 1 0 0 Tx ] = [ x3 ] * [ Xx Xy Xz 0 ]
[ y ] [ Yx Yy Yz Ty ] [ y2 ] [ 0 1 0 Ty ] [ y3 ] [ Yx Yy Yz 0 ]
[ z ] [ Zx Zy Zz Tz ] [ z2 ] [ 0 0 1 Tz ] [ z3 ] [ Zx Zy Zz 0 ]
[ 1 ] [ 0 0 0 1 ] [ 1 ] [ 0 0 0 1 ] [ 1 ] [ 0 0 0 1 ]
t1 t3
The eye matrix relates to the multiplied matrix from every Partition this way:
VisitorDraw::Visit( TransformNode& node )
{
mMatrix = node.GetMatrix() * mMatrix;
ComputeEyeMatrix(); // implicit arg is mMatrix
}
void
VisitorDraw::ComputeEyeMatrix( void )
{
Matrix t1;
t1[Ox] = mMatrixView[Ox];
t1[Oy] = mMatrixView[Oy];
t1[Oz] = mMatrixView[Oz];
Matrix t2 = mMatrix * t1;
Matrix t3 = mMatrixView;
t3[Ox] = t3[Oy] = t3[Oz] = 0.0;
mMatrixEye = t2 * t3;
}
[2007/04]
World class has a public interface for containing Objects. The base World class, being a generic part of the Engine, doesn't know specifically how to populate Objects. Therefore, a module is required to extend World [World::Populate(Box&)].
See World Organization.
In V1, all possible Quadrants were allocated since its World::mQuadrants[] was small. V2 has a huge mQuadrants[], therefore, Quadrants are lazy-allocated to save memory.
The World and its related class are multithreaded. The reason is that terrain generation is a slow process. The division of World into Quadrants facilitates distributing terrain generation across threads.
When the Eye causes the Locus to move to another set of Quadrants, the main threads builds N work-queues, then spawns N threads. A work-queue contains a list of Quadrants that a thread shall populate. The main thread can continue rendering while distant Quadrants are being populated.
The converse is shrinking/destroying Quadrants. Destroying Quadrants also is a slow process (~BSP has to recursively free Objects). For the sake of constraining complexity, instead of using threads, destroyable Quadrants are inserted in a zombie list. A timer-tick function periodically deletes a limited amount of zombie Quadrants to avoid stalling the engie. A fail-safe of destroying all possible zombies is activated in case too many zombies accumulate. Quadrants turn into zombies if a thread was still busy populating it, or it was containing an unreproducible Object (a Dyna should eventually transit to another Quadrant).
[2007/06]
The base Volume class is abstract and space-neutral.
[2007/06]
These different derivatives of Volume are required:
[2007/06]
Although Volume is space-neutral, which space can be inferred from the context or an accessor method's name. Implementing distinct types, such as LocalVolume and WorldVolume, isn't practical (that would require duplicating the Volume class hierarchy).
[2007/06]
Volumes in local space can be shared by the same kinds of Objects. But Volumes in world spare are unique (despite GetWorldVolume() returning SharedPtr).
class Object
{
shptr<Volume> GetLocalVolume( void ) const;
shptr<Volume> GetWorldVolume( void ) const;
};
[2007/06]
See also Collision-Detection.
When a Dyna moves, collision-detection is necessary. The Quadrant's BSP is traversed, stopping at the partition where the Dyna moved into. The partition may contain zero or more other Objects. For each Object, the Dyna's Volume is passed to Volume::IfInside(Volume&). That method will be, in fact, either SphereVolume::IfInside(Volume&) or BSPVolume::IfInside(Volume&) for regular and irregular Objects, resp. But the Volume arg is abstract, not concrete. Noting that both methods operate with a SphereVolume as an arg, therefore, the abstract Volume class has this abstract method to produce a concrete Volume:
class SphereVolume;
class Volume : public Shared
{
virtual SphereVolume ToSphereVolume( void ) const = 0;
virtual BoxVolume ToBoxVolume( void ) const = 0;
};
class SphereVolume : public Volume
{
bool IfInside( const Volume& abstractVolume ) const
{
SphereVolume sphereVolume = abstractVolume.ToSphereVolume();
[..radius formula..]
}
};
[2007/07]
Prototype code
See also Objects in design.
////////////////////////////////////////////////////////////////////////////////
/// @brief Base class for 3D objects.
///
class Object : public Shared
{
// Construction, identity:
protected: Object( shptr<Graph> graph, const WorldVertex& position );
public: virtual ~Object();
public: virtual PostConstruct( void );
protected: void SelfDestruct( void );
public: virtual bool Reproducible( void ) = 0;
public: virtual const string GetName( void ) = 0;
// Drawing:
public: virtual void Draw( void );
// Spatial:
public: void SetPosition( const WorldVertex& position );
public: WorldVertex GetPosition( void );
public: shptr<WorldVolume> GetWorldVolume( void );
// Geometry:
public: shptr<Graph> GetGraph( void );
// Transformation:
public: shptr<const Matrix> GetMatrix( void );
public: void SetMatrix( shptr<Matrix> );
// Collidable/indestructible:
public: void SetCollidable( bool collidable );
};
Object::SetPosition() forwards to World::SetPosition(). World is responsible for migrating Object across its private spatial structs (Quadrants and BSP trees).
Object::SetCollidable() forwards to World::SetCollidable(). World maintains a list of collidable Objects in partitions of BSP trees. An Object is made collidable or indestructible by linking in or out of the list of collidables.
Object::PostConstruct() allows base classes to do post-construction actions on fully-constructed Object. World automatically calls Object::PostConstruct() after a new Object is created.
Object LOD and drawing:
Most Objects are expected to have one mesh/LOD.
Objects with multiple LODs should call Engine::GetLod(Object) when their
Object::Draw() method is called. This method provides flexibility
in the Engine's implementation (cull stage may have computed/saved LOD from
projection-based visibility test or Engine may compute LOD only when demanded).
[2007/07]
This diagram illustrates the relationships of Nodes in the chosen implementation of the Graph.
Children/siblings nodes are contained in a SortedNodes object. This is a Flyweight container that sorts nodes according to priority. For example, an opaque ModesNode has more priority than an translucent one, so the opaque one will precede (be visited first).
class Node
{
protected:
SharedPtr<Node> mParent;
SortedNodes; mChildren; // sorted by priority
Node::Idx mSiblingIdx; // index into mChildren of this node's parent
};
[2007/07]
Graph is a rigidly ordered container of Nodes.
Each Graph has one and only one LodNode. A Graph can have one or more partitions which is a subtree that defines a whole or part of a mesh. Each Node has a two-order priority. The first-order priority is heterogeneous order relative to other types of Nodes which determines which level in the partition tree it must be placed. The second-order priority is homogeneous order relative the the same types of Nodes. When comparing priorities, if the first-order differs, then comparison stops since the second-order is N/A. Among equal Nodes, there is a chronological order. The newest equal node is placed after older equal nodes. The implementation depends on chronological order for efficiency (specifically, Node::AttachChild() has to reindex siblings which is usually fast since only the newest/last node needs reindexing).
This reason for this rule is to minimize traversing. An obvious example is that a polygon node depends on a color node. The appropriate color will be already submitted to the gfxsys before the polygon node is visited.
An exception to this rule is NormalsNode. Normal vectors depends on local vertexs and polygons. A NormalsNode does follow this rule WRT to vertexs: a NormalsNode is attached below a VertexsNode. But polygon nodes must be leaf nodes. Therefore, NormalsNodes must be above them and violate this rule. To resolve its dependency on polygons, as punishment, NormalsNode incurs the inefficiency of creating another Visitor to visit all polygons below it. This inefficiency of a visitor-within-a-visitor causing a second traversal is the reason for following this rule if possible.
An attempt is made to keep knowledge of the correct and optimal order of nodes private to the Graph and friend classes. GraphMaker acts a Facade between the Graph class and clients that make Graph (see Constructing Graphs).
A general rule is that children nodes should be homogeneous. This rule exists to catch misplaced Nodes that would result in aberrant rendering (the fundamental Graph structure itself doesn't impose this rule).
These are the exceptions:
[2007/07]
[2007/07]
GraphMaker is a Facade between a Graph and a client that makes a Graph. It allows a client to be ignorant, to some degree, of the exact structure of a Graph. An analogy is one person choosing decorations for a tree, while another person chooses where to place them on the tree. GraphMaker knows how to arrange nodes in optimal order (by priority).
A client specifies a set of predecessor nodes. Predecessors chart a path in a tree from the root node to an incoming node. A client isn't required to fully-specify every predecessor on every level. GraphMaker can tolerate a client specifying incomplete predecessors and predecessors out-of-order. GraphMaker will fill-in-the-gaps as necessary to place a node. GraphMaker is responsible for searching for existing nodes to avoid duplicates and creating predecessors that don't exist yet.
GraphMaker has the notion of a current partition. A mesh can be divided into logical parts, hence the name partition. A partition can be the whole Graph or a subtree of a Graph. The root node of a partition is a PartitionNode object.
[2007/07]
Graph imposes a rigid order of nodes. Graph's concealment of its structure and GraphMaker's mediation helps to enforce that. But to self-check Graph and also privileged clients allowed to circumvent GraphMaker (none currently exist), VisitorCheck was introduced to try to catch invalid Graphs. For DEBUG, GraphMaker automatically calls VisitorCheck. It looks for errors such as mismatched nodes, out-of-order nodes, duplication of unique nodes, interior nodes attached as leaf nodes, etc.
[2007/05]
A linked set of Nodes is attached to a Graph. Graph::~Graph() destroys them simply by unlinking them from each other. That's because Nodes are linked by reference-counted smart pointers (SharedPtr). Unlinking decrements their reference-counts.
[2007/05]
A Visitor is passed to Graph::Traverse(), which in turn, passes the Visitor to every Node. Optionally, the Visitor object can stop the Traversal by becoming false (virtual Visitor::operator bool()). This is useful when the purpose of a Visitor is to find a particular Node.
The Visitor design pattern doesn't necessarily require tediously defining a Visitor::Visit() method for every Node class. In the following example, only TransformNode is of interest.
class VisitorFindFirstTransformNode : public Visitor
{
public:
void Visit( Node& node ) { } // don't care about other Node classes
void Visit( TransformNode& node )
{
// Found the first TransformNode, stop traversing.
mStop = true;
mTransformNode = &transformNode;
}
};
[2007/07]
Graph::Traversal() uses a stack of Nodes. The state of a traversal (node stack) is encapsulated in a GraphTraversal object, which is passed to Visitor::Begin() at the beginning of a traversal.
Some kinds of Nodes require a departure action, which is the counterpart to the visit action. An example is visiting a TextureNode which enables texturing. But after TextureNode (and all of its children) are visited, texturing should revert to being disabled.
The traversal stack can be used to divert to a departure node. A SpecialNode can be pushed at the point where a node is visited. Visitor::Visit() can call GraphTraversal::Push(Node&) to push a SpecialNode derivative. Graph::Traverse() will pop it from the stack, and thru the Visitor dispatch mechanism, will invoke the departure action.
[2007/05]
Node clones are nodes private to a Graph. Graph links shared nodes together, but keeps clones are separate (unlinked). Traversal follows links to every shared node in the graph structure. If a shared node has a clone, the clone is passed to the Visitor instead. Thus, clones have precedence over the shared (original) counterpart.
When a graph is forked, VisitorCloner visits every node in the parent, makes a new clone, for the child, of every clone the parent has. This is why the clone attribute is sticky: forking re-clones every clone.
Clone indexing is almost as a fast as an array indexing. The class that contains Clones is optimized for space too, according to the expectation that most Graphs only need one clone of a TransformNode. To save memory, extra storage for more clones is lazy-allocated.
[2007/07]
SpecialNode is sort of like an ESC character. In some sense, SpecialNode derivatives create an orthogonal hierarchy of Visit() methods. This simplifies the base Visitor class: it only needs to declare Visit(SpecialNode&) (not all the possible SpecialNode derivatives).
SpecialNodes can be pushed on the traversal stack.
class Visitor // base class
{
// Regular nodes:
virtual void Visit( LodNode& node ) { }
virtual void Visit( TransformNode& node ) { }
[..]
// Visit special nodes (not linked to Graph):
virtual void Visit( SpecialNode& node ) { }
};
For example, VisitorDraw defines its own SpecialNodes, yet adding more specific Visit() methods to the base Visitor isn't necessary. Visitor::Visit(SpecialNode&) will be bound at run-time to the corresponding SpecialNode derivative.
class VisitorDraw : public Visitor
{
// Regular nodes:
[..]
// Visit special nodes (not linked to Graph):
virtual void Visit( PopMatrixNode& node );
private:
class PopMatrixNode : public SpecialNode
{
[..]
};
};
[2007/08]
Normal vectors used to be retransformed, but was eliminated by the dot product formula for polygon culling which transforms normal vectors instead into into eye space. References to retransforming normals in normal space were striked, not removed, in case that becomes useful again.
A Graph contains a NormalsNode which contains two different arrays of normal vectors. To cull polygons, normal vectors on polygons are needed: polygon normals. To properly light a model with smooth shading, normal vectors on vertexs are needed: vertex normals. Vertex normals are the average of all the normals on the polygons on which a vertex resides.
There's a distinction between computing vs. transforming normals.
Normal vectors are initially computed from cross products.
Afterwards, they can be subsequently transformed (rotated) thru a matrix.
Computing normals is much slower than transforming (explained later).
Normal vectors are pre-computed. Although GraphMaker does pre-computing for a Graph, functions to pre-compute normal vectors must be in Graph. The reason is that, after a Graph is made, its polygons could be dynamically modified (deformed) which requires re-computing normals.
To compute normal vectors, a Visitor is used to visit all the polygon and vertex nodes.
Both kinds of normals, polygon normals and vertex normals,
are computed and stored as arrays in a NormalsNode.
This is why transforming normals is much faster than computing normals:
transforming can index an array, while computing has to traverse a graph.
Every subtree in a Graph has one NormalsNode.
Normals need to be lazy-computed and lazy-transformed.
Immediately recomputing them would be inefficient:
consider that GraphMaker repeatedly attaches polygons.
Changes to polygons or vertex nodes causes Graph
to set recompute normals and retransform normals flags.
Rotating a matrix affects just the retransform normals flag.
Computing can be postponed until an Object needs to be drawn.
NormalsNode provides storage for normal vectors and flags.
Graph (VisitorDraw) is responsible for computing/transforming them.
A mathematical property of vectors (OpenGL red book) is that adding vectors
then normalizing the sum results in a normalized average.
This is an alternative to averaging by dividing by the number of values.
Normalize( v1 + v2 + v3 ) = Normalize( (v1 + v2 + v3) / 3.0 )
VisitorComputeNormals uses this property since it doesn't know how many vectors there will be (divisor unknown).
[2007/08]
A few special-case Objects have "constant normals". A reason is that they lack enough polygons for averaging normals and therefore specially pre-computed before rendering, and never re-computed.
[2007/08]
There is more than one formula to cull polygons based on computing a dot product. This formula is specific to the Graph implementation and available input. The key idea is to transform a normal vector (stored in a Graph and referenced by a visited polygon) from Normal Space to Eye Space, since by the time the dot product will be computed, a Graph's local vertexs has been transformed to Eye Space, esp. the first vertex of the polygon.
/*****************************************************************************
* Polygon using dot product.
*
* The origin of the normal vector, which is the first vertex of the polygon,
* has been transformed into Eye Space. Therefore, the polygon's normal vector
* is translated from Normal Space to Local Space, then it is transformed into Eye Space.
*****************************************************************************/
bool
CullPolygon()
{
// Translate normal vector from Normal Space to Local Space.
LocalVertex localNormal( (*mLocalVertexs)[vixs[0]].x + (*mPolygonNormals)[nix].x,
(*mLocalVertexs)[vixs[0]].y + (*mPolygonNormals)[nix].y,
(*mLocalVertexs)[vixs[0]].z + (*mPolygonNormals)[nix].z );
// Transform normal vector from Local Space to Eye Space.
EyeVertex eyeNormal = mMatrixEye.RotateTranslate<EyeVertex,LocalVertex>( localNormal );
// Translate normal vector so that the first vertex of polygon is the origin.
EyeVertex eyeNormal2( eyeNormal.x - mEyeVertexs[vixs[0]].x,
eyeNormal.y - mEyeVertexs[vixs[0]].y,
eyeNormal.z - mEyeVertexs[vixs[0]].z );
// Likewise, translate Eye so that the first vertex of polygon is the origin.
EyeVertex eye( -mEyeVertexs[vixs[0]].x,
-mEyeVertexs[vixs[0]].y,
-mEyeVertexs[vixs[0]].z );
// Compute dot product of transformed normal vector and Eye
// relative to the first vertex (origin of normal vector).
return DotProduct3( eyeNormal2, eye ) < 0 );
}
[2004/11]
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.
[2007/04]
The Engine class represents the interface to the 3D engine. Much of the Engine is implemented as separate classes in the eng/ directory.
Engine methods:
[2004]
The zombie list (marked-for-deletion) 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.
[2007/04]
The static GFX class provides a large degree of independence of the underlying gfxsys. GFX methods parallel the OpenGL API.
[2007/04]
Aspects of the OpenGL and GLUT code in Palomino:
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).
[2007/04]
[2007/08]
During program startup, populators will construct Objects having textures. The engine starts the gfxsys before populators are called to guarantee that texture resources are available.
Texture code is implemented across the gfx/ and engine/ src directories.
[2007/08]
[2007/08]
The Targa code (written in C) always produces a full 32-bit RGBA image. Note that trying to optimize it to produce a smaller image (if Alpha is absent) would be difficult (it's old C code), and another obstacle is that the clients of Targa, Font and Texture classes, depend on Targa producing full RGBA.
[2007/07]
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).
(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 similar 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:
<info ver='2.0' type='Palomino 3D model' name='f-14tomcat.pal' author='Grianne Ohmsford' modelProg='Blender' modelProgVer='244' />All of this info is on one line so that the parser can quickly jump over it
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.
For example:
<info ver='2.0' type='Palomino 3D model' name='f-14tomcat.pal' author='Grianne Ohmsford' modelProg='Blender' modelProgVer='244' /> <ex rot='90.0,180.0,0.0'/> pre-rotates model (Blender export script) <ex scale='2.0'/> pre-scales model (Blender export script) <part> <name/> root name of Partition <pivot/> origin of Partition (optional) 0.0 0.0 0.0 <part> child partition ... </part> <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 </part>
[2007/10]
See Commodore 64 programmer's manual for register definitions.
A Sprite is a set of quads that are oriented perpedicular to the viewplane. After orienting, effectively, Sprites become 2D. For an illusion, as the viewpoint is rolled, Sprites are counter-rolled. The Sprite's up vector stays synchronized with the Eye's up vector (in World Space).
Sprite are oriented in two ways:
The Eye object accumulates changes to the degree of roll (simple addition), regardless of the state of its matrix. For example, if the Eye is looking at a Sprite, does a 360' roll, orbits some, does another 360' roll, the Sprite's roll will be the same both times. The Eye accumulated {0..360} and {360..720} degrees but for rotation both range of degrees are the same.
eye eye eye
+Y +Y +Y
+---------+ +---------+ +---------+
| | | | | |
| +-+ |eye | /\ | | +-+ | eye
| | | |+X | / / | | | | | +X
| +-+ | | \/ | | +-+ |
| | | |eye | |
+---------+ +---------++X +---------+
Sprite Sprite vertical orbit
inside rolls as over Sprite
viewport eye rolls (geometry stays constant)
[2007/10]
ParticleSystem class is a container of Particles. ParticleSystem registers a timer-tick functor, then ages and animates every particle. New Particles can be dynamically added (expanding smoke trail, explosions). ParticleSystem will destroy Particles past their lifetime.
Particle is derived from the Sprite class. Particle::Animate() is a virtual method, called by ParticleSystem, for doing optional animation such as altering color, alpha, etc.
[2004]
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).
Each view produces a unique range of frame numbers. This allows detecting a change in frames when a different view is rendered.
[2007/05]
Rendering frames is driven by an OpenGL GLUT timer or by posting a redisplay event (in response to joystick/keyboard input). The engine should quiesce while no redisplay is necessary. The engine renders Objects inside the view frustum. Depending on LOD, distant Objects that would have a small projected 2D area may be culled.
The render loop guarantees that Object::Draw() is only called if the Object is visible.
Engine::Draw():
construct AA BSP containing Quadrants inside view frustum
traverse this BSP in back-to-front order:
from furthest to nearest Quadrant (relative to viewpoint):
traverse this Quadrant's BSP tree in back-to-front order:
from furthest to nearest Object:
cull Object if outside view frustum, continue
cull Object if entirely behing viewpoint, continue
call Object::Draw()
[2007/04]
The base class Object has a virtual Draw() method which defaults to calling Graph::Draw(). See Drawing Graphs (design) and Drawing Graphs (impl)
Specialized rendering without using a Graph is possible by overriding Object::Draw().
[2007/06]
Drawing a Graph is implemented using the Visitor pattern (SGI invented this technique). The Graph::DrawVisitor class has a set of Visit() methods. Most of the Visit() methods accumulate graphic states (colors, textures). The Visit() methods that correlate to polygons (which are leaf nodes) trigger the actual rendering of a polygon (submitting of vertexs to gfxsys).
[2007/05]
See UserLod in design.
See ObjectLod in design.
[2007/07]
LodNode maintains a private struct that defines the ObjectLOD of its children which are PartitionNodes. ObjectLOD is a float range, eg, (0.0,1.0) means any LOD. LodNode acts as a switch to one (or more) of its children. A reason for the ability to switch to multiple children (rather than only one-at-time) is usual case of Graph having sibling Partitions that are drawn at any LOD.
[2007/08]
When an Object is constructed, VisitorComputeVolume computes the Object's radius, and also the center of polygon mesh (local center). When the Object is going to be drawn, VisitorDraw transforms the Object's center in local space to eye space and passes the eye vertex and radius, forming a sphere, to GFX::IfVisibleSphere(). This function tests if the sphere is inside the view frustum. The view frustum was pre-computed at program startup suited to culling (the view frustum doesn't require updating since the engine transforms vertexs itself, and leaves the OpenGL modelview matrix identity-mapped).
[2007/04]
See also Collision-Detection Using Volumes.
The interface to set an Object as collidable or not is Object::SetCollidable(bool).
Internal to the World's organization, whether an Object is collidable is determined by whether the Object is linked in a BSP node's list of collidable Objects. A BSP node also has a total list of Objects (regardless of collidable). Object::SetCollidable(bool) forwards to World::SetCollidable(Object&,bool) to modify the BSP node's lists appropriately.
To speed collision-detection, for every BSP node, the World maintains a list of collidable Objects. In the best case, collision-detection can be bypassed if a collider is in a BSP node with an empty list of collidables.
Two methods for collision-detection are implemented: approximate and precise.
Approximate detection of a collision is acceptable for a small Object or an Objects having a regular shape. A fast but approximate way to test is to define the collidable's volume as bounding sphere or box. The implementation reuses the existing Volume object of the Object class. The Volume class is abstract, but in fact, would be implemented either as a bounding box or sphere, which provides a fast way to test intersections.
Precise detection of a collision into a large Object or an Object having an irregular complex shape is necessary. Precise intersection can be done by defining the collidable's volume as a polygon-aligned BSP tree. Disadvantanges are that these are slower to construct and to test intersections. Detection for such Objects may be faster by first testing with the approximate method, then proceeding to the precise method if the approximate one indicated a probable collision.
Testing if a 3D vertex is inside a PA-BSP is done by traversing. If the vertex is inside, then the vertex will be behind every polygon encountered during traversal. Eventually, traversal will stop at a leaf node, which means a collision was detected.
[2007/06]
RushLock is the fastest lock.
It is implemented as a NON-RECURSIVE spinlock.
Appropriate for short self-contained routines
that NEVER call other routines guarded by the same lock.
WARNING: RushLock will dead-lock if the same thread hits it twice!
FastLock is a recursive spinlock. Not quite as fast as RushLock, but is much safer.
Despite its name, in certain situations, SlowLock can boost net speed by allowing the CPU to execute another thread instead of spinning uselessly as RushLock or FastLock would do. SlowLock is a slower lock meant for slower functions that take a long time to execute and often stay locked.
SlowLock is implemented as a recursive pthreads mutex. A blocked thread will be put to sleep thus freeing a CPU to run another thread.
[2007/04]
"lock" and "mutex" are synonyms in this doc. "lock" is preferred.
#define PERSISTENT static #define INLINE static inline #define CLASS_CONST static const #define CLASS_VAR static #define CLASS_METHOD static
Locking is necessary in code that can be run by multiple threads and
a two threads could concurrently access the same resource.
One and only one thread must lock that resource during access.
Examples of resources that require locking:
[2007/04]
These are empty classes that serve as indicators of the level of threadability of a class. By using these, doxygen can show threadable or non-threadable classes.
A Threadable object meets these requirements:
NonThreadable is an object that cannot be executed concurrently. Any Threadable user must lock an NonThreadable.
SemiThreadable indicates a class with a limited degree of thread-safety. The decision to use further locking is deferred to its users.
For example, imagine a List class with a locked Prepend() method. Two producer threads can concurrently call Prepend(). Used in this limited way, List is fully thread-safe.
But if a consumer thread is started, it would call methods IfEmpty() and Unlink() as a non-atomic sequence. Even though both particular methods are separately thread-safe, they can be used to form a thread-unsafe operation outside a class by its users. Therefore, in this case, the producer and consumer threads (the users) have the responsibility of locking the whole list.
[2007/04]
doxygen can show the classes derived from Threadable et al. This documents the important classes.
Thread implementation follows the design goal of minimal/limited thread support. Only classes that need to be thread-safe are thread-safe.
These basic classes are ubiquitous, therefore, they must be thread-safe.
Supports multiple threads populating subdivisions of the World as Objects can be made randomly.
Accessing read-only methods is necessary to support threading populators. But methods such as SetPosition() are intrinsically serial.
Locking individual graphics function isn't practical. Therefore, multiple threads must not try to render. Rendering should be restricted to the main thread. See Graphics Task Queue.
[2007/04]
See Task Queues and the Graphics Task Queue in design.
[2007/04]
See Graphics Task Queue in design.
[2007/04]
Timer-ticks (and redisplay events) drive rendering. Modules can register timer callbacks as event listeners using the class eng::Timer. eng::Timer requires being driven by the underlying system's timer-tick (GLUT timer).
[2007/08]
When compiled with make DEBUG=1 or DEBUG=2, debug modes are available via the GUI. BSP nodes and Object's bounding boxes can themselves be drawn.
[2006,2007/06]
C++ objects can be shared in different ways (objects in the general sense).
SharedPtr is a smart pointer that maintains a reference-count. A requirement is that objects to share must be derived from Shared. Shared provides storage for the reference-count, intrusively in an object itself, since Shared is its base class.
Besides sharing, SharedPtr simplifies object ownership. SharedPtr auto-deletes the object when it is no longer referenced, eliminating needing to explicitly delete an object.
NOTE: For speed, regular SharedPtr does not support NULL. The slower variant SharedPtrNull does.
A particular Shared object is interchangable with different kinds of SharedPtrs. SharedPtr::PTR() can extract the Shared object which can be used to create another SharedPtr variable of the same or different type.
An idiom is using a SharedPtr for its auto-deletion ability, even though the object really isn't shared.
Constructors with the potential to produce multitudes of objects with duplicate values can be constrained using UniquePtr. When given an object, the UniquePtr ctor may substitute the object with a shared one in a private STL set and delete the given duplicate object. UniquePtr shares copies that it owns rather than originals (which it doesn't own).
[2007/04]
Source code is written in C++ and developed primarily on Linux using the GNU toolchain. For some degree of independence from graphic systems, graphics code is based on the GFX class (Facade).
The code is written in C++ in accordance with OOP doctrines. Source code is organized as classes, documented easy-to-use public interfaces, hiding internal methods/data, etc.
C++ exceptions should be limited to assertions and very rare cases. C++ RTTI shall never be used. Strive to limit use of casting, raw pointers, and NULL. To catch memory corruption, type-signature checking is compiled in DEBUG builds.
[2004,2007/06]
Naming convention:
Restricted globals are typically independent variables with a narrow scope. namespace is spelled "restrict" as "restricted" is a C99 keyword.
[2004]
SafePtr prevents deleting the pointed-to object.
class Object
{
Shape* GetShape( void );
SafePtr<Shape> GetShape( void );
};
Object A passes a pointer to its member to object B. But A could be destroyed before B uses the pointer. Or B could delete the passed object, then A tries to use it. SharedPtr can prevent these problems.
Last modified: Fri Nov 23 11:15:36 EST 2007