World Eye 
Perspective 2D viewport
©2004,2007 Jim E. Brooks http://www.palomino3d.org
See also Palomino Implementation and Game Mode.
[2007]
Plural endings are misspelled for searchability: vertexs, matrixs [sic].
[2004]
These are the coordinate systems a 3D vertex is transformed thru:
Transformation of a 3D vertex thru coordinate systems:
Local World Eye Perspective 2D viewport
Green indicates transformations done by the engine.
Red indicates transformations done by the gfxsys.
Local:World and World:Eye can be combined by matrix multiplication.
3D objects have their own local coordinate system. Also known as object coordinates.
The world coordinate system contains the simulated world (the scene to be rendered). It is mapped to the eye coordinate system by the Eye Matrix.
Altitude correlates to a positive world Y coordinate. (X,Z) correlates to a 2D position ("ground coordinates") somewhere on the modeled terrain/land.
The eye coordinate system stays mapped to the viewport of the window system. Eye vertexs are the final result of all transformations. They are submitted the gfxsys.
(X,Y) eye coordinates correlate to (X,Y) viewport coordinates. An eye Z coordinate measures the distance from the eye/viewpoint. For an eye vertex, (X,Y) are divided by Z to project the vertex onto the viewport (window). This projection creates the illusion of perspective on a 2D computer display.
Eye coordinates are transformed by the gfxsys into perspective coordinates. The view frustum (which exists in eye space) is mapped to perspective coordinates.
This is the 2D window on the computer's window system.
Every normal vector calculated from a cross product exists in its own coordinate system. Its origin (0,0,0) is mapped to a local vertex of the polygon on which it is perpendicular to. Normals depend on the object's transformation in local space. For example, if the vertexs of an aileron are rotated in local space, all normals on the aileron must be rotated likewise (or recalculated)
[2004]
The result of the cross product of two vectors extending from a shared vertex on a planar polygon is a normal vector.
CrossProduct() uses the first vertex argument as the origin of the normal vector.
The resulting vertex on the normal vector is stored in a distinct NormalVertex type
as it exists in its own coordinate system.
/*****************************************************************************
* Calculate a cross product of two vectors which yields a normal vector
* that is perpendicular to the plane containing the two source vectors.
* Note: The cross product won't be unit length.
* c = a x b
*****************************************************************************/
INLINE NormalVertex
CrossProduct( const Vector3& v1, // origin of normal vector
const Vector3& v2,
const Vector3& v3 )
{
fp a, b, c;
fp d, e, f;
a = v2.x - v1.x;
b = v2.y - v1.y;
c = v2.z - v1.z;
d = v3.x - v1.x;
e = v3.y - v1.y;
f = v3.z - v1.z;
return NormalVertex( b*f - c*e,
c*d - a*f,
a*e - b*d );
}
A dot product is calculated from two vectors extending from a shared vertex. The result is a single value (scalar). If the angle between the two vectors is between 0' and 90', then the dot product will be a positive value. Normal vector, cross products, and dot products are used for culling polygons which aren't facing the viewpoint.
[2004,2007/04]
A compact 4x3 matrix is used:
{ Xx, Xy, Xz, // X axis
Yx, Yy, Yz, // Y axis
Zx, Zy, Zz, // Z axis
Ox, Oy, Oz }; // origin
The 9 axis coefficients and the origin are used for matrix rotation and translation.
OpenGL is based on a 4x4 matrix. OpenGL has a 4th column for homogeneous coordinates. Homogenous coordinates applies to projection and scaling. The engine only rotates and translates non-homogeneous coordinates, and never exchanges matrixs with OpenGL, thus allowing a minimized 4x3 matrix to be used.
A vertex is rotated by:
(one coordinate system is rotated relative to another)
x' = x*Xx + y*Xy + z*Xz y' = x*Yx + y*Yy + z*Yz z' = x*Zx + y*Zy + z*Zz
A vertex is translated by:
(one coordinate system is translated relative to another)
x' = x + Ox y' = y + Oy z' = z + Oz
The eye matrix maps the world coordinate system to the eye coordinate system. A peculiarity of the eye matrix is that its offsets (Ox,Oy,Oz) are all negative.
The Object class has a transform hierarchy which transform vertexs from local space to eye space.
A matrix maps one coordinate system to another. The mapping is directed. The mapping can be reversed by transposing a matrix. This is done by turning each row into a column. Note: a transpose matrix and an inverse matrix are different mathematical concepts.
[ Xx Xy Xz ] [ Xx Yx Zx ] [ Yx Yy Yz ] [ Xy Yy Zy ] [ Zx Zy Zz ] [ Xz Yz Zz ]
An example of using a transpose matrix is the animation of tracer bullets in a first-person view. The eye matrix maps world-to-eye coordinates. The tracer bullets are modeled starting from a local coordinate system. What's needed is a local matrix that maps local-to-world coordinates and it must be aligned with the eye matrix. The transpose of the eye matrix is that local matrix. Although the transposed eye matrix maps eye-to-world coordinates, it can work because the result of the transformation is in world coordinates (on the output side), and by substituting local coordinates instead of eye coordinates on the input side. A copy of the eye matrix used as the local matrix wouldn't work because the two transformations from local-to-world and world-to-eye would nonsensically pass thru the eye matrix (which is meant for the latter transformation only).
[2004,2007/04]
Two different descriptions about rotating a 3D matrix around its axises:
Matrix Rotation [1990]
Matrix Rotation [2004]
[Updated 2007/04. This code evolved into the Matrix class.]
The following notes were written in 2004 as a rewrite of notes from 1990. It distinguishes the two ways to rotate a matrix. Rotation around a fixed coordinate system is for rotating a first-person view (Eye). Rotation around a local coordinate system is for rotating dynamic objects. Both are implemented [2007] as Matrix::RotateFixed() and Matrix::RotateLocal().
This matrix rotation formula is actually rotation around a fixed coordinate system (this fact wasn't originally documented). For example, in the formula for rotation around the X axis...
X Pitch ------- c = cos(radian) s = sin(radian) m[Yx] = m[Yx]*c - m[Zx]*s // Y = Ycos - Zsin m[Yy] = m[Yy]*c - m[Zy]*s m[Yz] = m[Yz]*c - m[Zz]*s m[Zx] = m[Yx]*s + m[Zx]*c // Z = Ysin + Zcos m[Zy] = m[Yy]*s + m[Zy]*c m[Zz] = m[Yx]*s + m[Zz]*c
...notice that the X coordinate doesn't change (X is 1:1). Thus the rotation is around a fixed X axis. The formulas are correct for rotating the viewpoint (first-person perspective) or in other words the eye coordinate system.
But to rotate an object relative to its own local coordinate system, additional math must be done. Recall that a local coordinate system is mapped to the eye coordinate system. After random rotations around all 3 axises of the local coordinate system, eventually, the X coordinate, for instance, should be transformed to a different value.
These are the steps to rotate a coordinate system relative to itself (local rotation):
The trick is transforming the result of the rotation of a fixed coordinate system into the local coordinate system.
/*****************************************************************************
* Rotate a matrix around a fixed axis.
* This function is suited to rotating the viewpoint/eye.
* The word "fixed" should be clear by looking at the math.
* Eg, the value of the X coord won't be changed by a rotation around the X axis.
*****************************************************************************/
void
Matrix::RotateFixed( uint axis, Radian rad )
{
FPM s, c; SinCos( rad, s, c );
Matrix n = *this; // dest = src
switch ( axis )
{
// X : Pitch
case AXIS_X:
n[Yx] = m[Yx]*c - m[Zx]*s; // Y = Ycos - Zsin
n[Yy] = m[Yy]*c - m[Zy]*s;
n[Yz] = m[Yz]*c - m[Zz]*s;
n[Zx] = m[Yx]*s + m[Zx]*c; // Z = Ysin + Zcos
n[Zy] = m[Yy]*s + m[Zy]*c;
n[Zz] = m[Yz]*s + m[Zz]*c;
break;
// Y : Yaw
case AXIS_Y:
n[Xx] = m[Xx]*c - m[Zx]*s; // X = Xcos - Zsin
n[Xy] = m[Xy]*c - m[Zy]*s;
n[Xz] = m[Xz]*c - m[Zz]*s;
n[Zx] = m[Xx]*s + m[Zx]*c; // Z = Xsin + Zcos
n[Zy] = m[Xy]*s + m[Zy]*c;
n[Zz] = m[Xz]*s + m[Zz]*c;
break;
// Z : Roll
case AXIS_Z:
n[Xx] = m[Xx]*c - m[Yx]*s; // X = Xcos - Ysin
n[Xy] = m[Xy]*c - m[Yy]*s;
n[Xz] = m[Xz]*c - m[Yz]*s;
n[Yx] = m[Xx]*s + m[Yx]*c; // Y = Xsin + Ycos
n[Yy] = m[Xy]*s + m[Yy]*c;
n[Yz] = m[Xz]*s + m[Yz]*c;
break;
default: ASSERT(0); return;
}
*this = n; // dest = src
}
/*****************************************************************************
* Rotate matrix around local axis.
* Rotate a local coordinate system around its own axis.
* This function is suited to rotating an independent object.
* The rotation is relative to local coodinate system (not the fixed/eye system).
* The trick is to load an identity-mapped matrix and rotate it, then transform
* it thru the given matrix (which defines the local coordinate system)
* as though it was the coords (1.0, 1.0, 1.0). These coords of course define
* the X,Y,Z axises. The transformation is effectively a local rotation.
*****************************************************************************/
void
Matrix::RotateLocal( uint axis, Radian rad )
{
// Identity (1:1) matrix r.
Matrix r;
// Rotate matrix r.
r.RotateFixed( axis, rad );
// Transform r thru m.
// Ie, thru matrix m, pass r as if it were the rotated coords (1.0, 1.0, 1.0).
Matrix t;
t[Xx] = r.RotateTranslateX( m[Xx], m[Xy], m[Xz] );
t[Xy] = r.RotateTranslateY( m[Xx], m[Xy], m[Xz] );
t[Xz] = r.RotateTranslateZ( m[Xx], m[Xy], m[Xz] );
t[Yx] = r.RotateTranslateX( m[Yx], m[Yy], m[Yz] );
t[Yy] = r.RotateTranslateY( m[Yx], m[Yy], m[Yz] );
t[Yz] = r.RotateTranslateZ( m[Yx], m[Yy], m[Yz] );
t[Zx] = r.RotateTranslateX( m[Zx], m[Zy], m[Zz] );
t[Zy] = r.RotateTranslateY( m[Zx], m[Zy], m[Zz] );
t[Zz] = r.RotateTranslateZ( m[Zx], m[Zy], m[Zz] );
// m = r excluding origin elements.
m[Xx] = t[Xx];
m[Xy] = t[Xy];
m[Xz] = t[Xz];
m[Yx] = t[Yx];
m[Yy] = t[Yy];
m[Yz] = t[Yz];
m[Zx] = t[Zx];
m[Zy] = t[Zy];
m[Zz] = t[Zz];
}
[2007/04]
The engine is based on matrix math (linear algebra). However, the TransformNode class could be implemented as a quaternion.
[2007/04]
The World class keeps its data structs hidden to facilitate future improvements to how the World organizes space and Objects. Clients of World can manipulate Objects in abstract terms (vertexs and volumes in world space) without knowing how/where the World contains Objects.
The simulated world is divided into Quadrants. A Quadrant is a 3D cube with equal sides composed with an axis-aligned BSP tree. The space of a Quadrant is very large (could enclose several mountains). Every Quadrant is given a different random seed which is used to populate it with Objects. Objects are partitioned by their volume using an axis-aligned BSP tree. The BSP tree is used for coarse-level sorting and collision-detection.
The engine renders a "locus" of Quadrants that surround the viewpoint. Quadrants are similar to pages of virtual memory. As the Locus moves over Quadrants, they are populated with Objects. As the Locus leaves Quadrants, they are "shrunk" by deleting reproducible Objects. Background threads could anticipate the viewpoint moving by populating Quadrants adjacent to the Locus. Randomly-generated Objects can be reproduced by using the same seed value that is saved in shrunken Quadrants (pseudo-random functions return the same sequence of numbers when given back the same seed).
[2007/04,2007/06]
Two kinds of BSP trees are axis-aligned and polygon-aligned (AA-BSP and PA-BSP). A BSP node has two child nodes metaphorically named left and right.
"BSP" usually refers to an AA-BSP tree.
Axis-aligned is much simpler and faster to construct than polygon-aligned. Axis-aligned is useful for containing 3D objects in rectangular volumes. Objects can be coarsely (imprecisely) sorted in back-to-front order by traversing an axis-aligned using the distance between a partition vs. viewpoint as the criteria for branching left or right. The granularity of sorting is the rectangular volume of a BSP node. A BSP node may contain multiple Objects, but sorting (by BSP traversal) goes no further (this is why sorting isn't precise). Bypassing finely sorting the Objects of a BSP node is possible if none of the Objects are translucent. Rendering opaque objects out-of-order relies on the hardware Z buffer. Note that the purpose of sorting is to properly alpha-blend translucent Objects.
Polygon-aligned BSP trees are well-suited for precise collision-detection of objects having irregular shapes. Though they have disadvantages such as being complex and slow to construct. Polygons intersecting a plane must be split into two polygons.
The key to understanding a BSP tree is that the traversal path varies according to a branch condition and a stop condition. Unlike a regular binary tree, these conditions are variable. For example, when adding Objects, the branch condition is whether an Object can fit inside a partition. When culling/sorting, the branch condition is determined by distance and orientation of a partition relative to the viewpoint
Culling and sorting objects are done simultaneously by traversing a BSP tree. Traversing is sorting. Reaching a stop condition that evaluates true is culling.
A BSP node and its descendants outside the view frustum are culled since they won't be visible. This culling method is efficient, since a whole subtree of invisible objects are eliminated in one step.
To properly render translucent polygons, furthest-to-nearest order is necessary. During traversal, if two partitions are visible, the partition that is furthest from the viewpoint is selected. A partition's distance and whether inside the frustrum are sub-conditions of the branch condition. The target of the traversal path is to reach the smallest and most distant partition. A terminal partition that contains a translucent Object will require manually sorting Objects (std::sort()).
The branch condition determines which ways to branch:
The stop condition determines when to stop recursing:
if partition is not facing or partition is outside view frustrum.
Ignoring the view frustrum for a moment, possibly all the partitions or none will be visible. For example, if the viewpoint is at the corner of a partition and facing outwards, then none are visible. If the viewpoint is rotated 180', then all become visible.
Adding objects to a AA-BSP is similar to octrees. The tree is recursed until a node (corresponding to an octant) is found that the object doesn't fit or the maximum depth is reached, then the object is attached to its parent node.
There are several cases where an Object can intersect a BSP plane. One case is a Dyna that moves between any two partitions. The worst case is a very large Object that, besides intersecting one or more planes, overlays partitions in multiple BSP trees.
A way to solve intersection is to let multiple BSP nodes reference the same Object in case the Object occupies at least one partition that wasn't culled, but keep a flag (or frame number) to remember that the Object was drawn in a frame in case one or more of its partitions are visible (to avoid redraw).
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.
See Collision-Detection.
[2007/04]
The base Object class defines minimum functionality:
Extended functionality (such as animation) should be defined in a module. Experience has proved that building functionality into Object using composition with factored classes is better than derivation. The old design's use of derivation suffered from a proliferation of Object derivatives, diamond inheritance, functionality unreusable by unrelated derivatives, etc.
[2007/07]
[2007/07]
These diagrams show the important characteristics of this Graph structure. A part of a polygon mesh correlate to a Graph's partition. The atoms of a Graph are Nodes, and its molecules are L patterns of Nodes.
Consider 3 transform nodes that are siblings (non-hierarchical). None should affect any other. This is why a simpler binary tree is unsuitable: the 2nd and 3rd would have to be children of the 1st, but that would form a hierarchy in which the 1st transform affects the 2nd and 3rd.
[2007/07]
These are the requirements of the Graph class. Graph should be well-documented as it is the engine's core.
[2007/05]
The Graph class consists of:
Every Object has a Graph for consistency. An Object can be constructed from 3D model imported into a Graph. Objects can share a graph.
[2007/05]
Properties:
A Graph is highly flexible data structure. But flexibility opens the possibility of constructing a graph that's invalid. For example, a mistake is to attach a vertex node above a transform node (diagram). Such mistakes are caused by not keeping in mind that the purpose of a graph is to control the graphics state-machine.
A Graph is a tree that forms a hierarchy of states. Interior nodes contain graphical states. Leaf nodes contain Polygons. Thus, the tree sorts polygons by state. State-sorting accelerates rendering by minimizing costly state changes.
The effect of a state propagates. What will happen when the same type of state node is visited varies. TransformNodes are relative: a parent transform affects its children. Though, most nodes supercede the same type of nodes visited prior, such as color will be determined by the last visited color node.
[2007/05]
The graph requirements section focused on defining a graph. This section focuses on the uses of a graph.
See also Drawing Graphs.
A Graph is traversed in an unconventional order.
Traversing is done in these steps:
Traversing to a child has higher precedence than traversing to the next sibling.
The decision to branch to either the first child or next sibling corresponds to the decision in a conventional binary tree to branch to the left or right child.
The reason for the stack is to remember to follow the other route when a fork is encountered. In other words, when one node is chosen for traversal, the traversal of the other node is delayed by pushing it on a stack. When the end of traversing the first node is reached, popping from the stack starts the delayed traversal of the other node.
In the diagram below, numbers indicate the order of visited nodes, while lines indicate links to nodes in parent/sibling relationships. Links and traversing are different.
The diagram below is more realistic. Only polygons are siblings. To describe in words:
A special node that can alter the direction of a traversal is LodNode (see LOD). LodNode acts as switch that selects one or more of its children. This special behavior is opaque to the traversal routine (see ObjectLod).
Forking a Graph is similar to forking a UNIX process. Some nodes can be shared while others become private to every Graph.
While forking a Graph, for each node:
A clone node is a node passed to Graph::Clone(Node::Ptr) which turns a shared node into a private node. The clone attribute is sticky.
To understand how a Graph is drawn, first understand that the gfxsys is a state-machine. The Graph has nodes that define various graphical states. During rendering, a Graph is traversed with the purpose of setting states of the gfxsys. Notice in the diagram that interior nodes for materials, textures, and colors are visited before the leaf node of a polygon. Visiting nodes invokes function calls such as:
// Interior (state) nodes. glMaterial(); glBindTexture(); glColor(); // Leaf (polygon) node. glVertex3f(); [..]
To some extent, the engine is a state-machine also. Notice that a TransformNode is above a VertexsNode. When TransformNode is visited, the engine remembers a reference to it. Then, whenever a VertexsNode is visited, the last-visited TransformNode is applied to the local vertexs.
Another description is that a Graph is a form of postfix notation. Operands precede an operator (similar to FORTH).
See Drawing Graphs (impl) and Transforming and Referencing Vertexs.
Modules are free to derive the Node class in order to create special-effects by controlling additional graphical states beyond what the core engine provides.
The Importer class produces a Graph object. Objects can then be composed with a Graph. Graphs can be shared, to a large extent, by forking.
[2007/05]
A transform hierarchy is superimposed on a Graph. That is, TransformNodes can be placed in a Graph. Every Transform affects its descendants. In terms of matrix multiplication, a parent transform multiplies each of its children.
[2007/05]
A transform maps two coordinate systems. A transform is most often used to map local vertexs to eye vertexs. The purpose of TransformNode is to compute eye vertexs while a Graph is traversed to draw an Object. Transforms are also used to recompute polygon normal vectors when part of a mesh is rotated (such as ailerons of an aircraft).
TransformNode contains a mathematical transformation object (matrix or quaternion) and has references to geometry to be transformed.
TransformNode can be implemented as a matrix. But its interface should be designed to allow, in the future, substituting or complementing a matrix with a quaternion. The basis is mathematical: a matrix can be converted to a quaternion, v.v. TransformNode::Update() can insulate clients from reimplementing TransformNode. For example, a client can manipulate a TransformNode in terms of a Matrix. If in the future, TransformNode is reimplemented with a private Quaternion, the Quaternion must stay synced with the client's Matrix. Update() helps a reimplemented TransformNode remain compatible with existing code.
class TransformNode
{
TransformNode( shptr<Matrix> matrix );
//TransformNode( shptr<Quaternion> quaternion );
shptr<Matrix> GetMatrix( void );
//shptr<Quaternion> GetQuaternion( void );
// Client must call Update() after changing the transformation.
void Update( void );
private:
#if ! TRANSFORM_NODE_QUATERNION
Matrix mMatrix;
#else
Quaternion mQuaternion;
#endif
};
[2007/05]
Polygon normals need to be recomputed if the orientation of a polygon changes. These are the situations:
Whether to recompute only the affected normals, or all the normals, is an implementation choice.
[2007/05]
This diagram does omit NamedNode. Graph is flexible enough to be constructed with or without them.
When a Graph is traversed for rendering, one or more pairs of VertexsNodes and TransformNodes will be visited. The current local vertexs (the last visited VertexsNode) will be transformed.
Each Polygon is defined by a set of vertex indexs.
The indexs are relative to the current set of vertexs.
That is, every time Polygon.vix[] = n is encountered,
the index will reference a different vertex,
since the current set of vertexs changes whenever a VertexsNode is visited.
[2007/04]
Culling and sorting are done in tandem in 3 stages:
The first stage sorts Quadrants inside or intersecting the view frustum. Visualize this as a stack of cubes where the furthest is selected first. Quadrants entirely outside the view frustum are culled.
The second stage combines culling and sorting by traversing a BSP tree. A Quadrant has an axis-aligned BSP tree containing Objects. The condition for branching left or right thru the BSP tree is whether viewpoint is facing and distance between partition and viewpoint. Thus, branch follows the facing and most distant partition. Objects are coarsely sorted by traversing in-order the BSP tree. The condition to stop traversing is if a space partition is outside the view frustum. This efficiently culls an entire sub-tree of invisible Objects.
The third stage does fine sorting if necessary. Note that the second stage sorted partitions in the proper order, but within a partition, the Objects are unsorted. That is, the sorting of the second stage had granularity of BSP subspaces, not 3D objects. Since sorting is required only for proper alpha-blending, if a partition has only opaque Objects, the fine sorting can be bypassed. Bypassing fine sorting relies on the hardware Z buffer. Fine sorting could use a standard STL sort algorithm.
For performance, there shall be no sorting at the granularity of graphics primitives. Sorting primitives can be achieved indirectly by encapsulating a primitive in an instance of the Object class. This wouldn't be grossly expensive since Object has a small footprint.
Object derivatives define their GetDistance() return an approximate distance. The sort routine directly uses the value from GetDistance(). This is for flexibility. Objects that can be approximated as a sphere can add radius to their center. But Objects such as Sprites wouldn't factor radius into their distance calculation.
[2007/05]
Polygons which don't face the line-of-sight are culled. The normal vector of every polygon is created by calculating the cross product of two vectors that originate from vertex #0 and extend to vertex #1 and vertex #2. The polygon is culled if the dot product of its normal vector and the line-of-sight vector is negative (the angle is over 90' so the polygon isn't facing the eye or v.v.).
Polygon normals are computed in local space (consistent with a Graph having geometry in local space). The line-of-sight vector is translated from world space into local space in order to compute dot products of line-of-sight and normal vectors in local space.
Most Objects have constant polygon normals. Dynamic Objects require recomputing normals when their Transforms are changed (and by other causes).
[2007/05]
There are two different kinds of LODs: UserLOD and ObjectLOD.
UserLod is defined by discrete enums { DEFAULT,MIN,LOW,MID,HIGH,MAX }. UserLod is a global setting. If UserLod != DEFAULT, then UserLod overrides ObjectLod. For example, if UserLod==MAX, then every Object is rendered with maximum LOD.
ObjectLod is defined as a float range { 0.0:min,..,1.0:max }.
For example:
ObjectLOD=(0.0,1.0) means any LOD (usual)
ObjectLOD=(0.5,1.0) means medium-to-high LOD
ObjectLod is determined by an estimate of an Object's projected 2D area. ObjectLod isn't computed if UserLod != DEFAULT.
Most Objects will be rendered the same way for any LOD. Therefore, the engine can be optimized to only compute ObjectLod on demand by methods such as Graph::Draw() or Object::Draw().
A Graph can be constructed with LodNode which acts a switch to multiple sub-Graphs. See LodNode.
[2007/04]
Collision-detection is done using approximate or precise tests. These tests are based on bounding-box and polygon-aligned BSP trees, resp. See Collision-Detection in implementation and BSP trees.
[2007/01]
A Sprite is a horizontal stack of textured quads facing the viewpoint. It is designed to model amorphous shapes such as clouds. Sprites are a form of volume-rendering. A 3D object is divided into a set of "slices". Each slice is a 2D image, identified by a Z coordinate in range {-0.5,..,0.5}.
For a compromise between image quality and texture resource usage, a Sprite is specified with a slice/texture ratio. For example, a Sprite with 64 slices and a slice/texture ratio of 4 will have every 4 slices blended into one composite texture object, and will be rendered by 16 textured quads.
A Sprite is oriented in two ways.
First, it is oriented with the viewplane.
Second, the sprite's up vector is oriented with the Eye's up vector.
Rolling the sprite in sync with the Eye is sufficient to maintain
the sprite's illusion, even though this has no mathematical basis.
This orientation method is based on these observations:
The Eye object simply adds every degree of roll, 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.
[2007/04]
By design, thread support is limited. Implementing a fully thread-safe engine isn't practical. This follows from the fact that graphics systems aren't thread-safe and are meant for execution by one dedicated thread.
Threaded code must be written in a very disciplined fashion, ensuring that execution cannot reach non-threadable code.
Thread-saftey requirements of the engine:
Thread support consists of:
[2007/04]
Tasks are non-threadable function that are scheduled for mutually-exclusive execution. Tasks are placed into a queue where they will be executed one-at-a-time. If a task is currently executing, the thread trying to enqueue a new task either will be blocked or allowed to continue.
In terms of design patterns, Command objects are enqueued. A Command object can contain whatever state necessary to execute the task. Stored state is important if the enqueuing thread needs to continue before the Command is executed.
Tasks are dequeued and executed only by the main thread.
The idea of task queues comes from Linux kernel programming.
[2007/04]
The engine predefines a task queue for high-level graphics functions. By "graphics functions", this means higher-level functions that use the low-level GFX class (GFX is non-threadable and its limitation is a reason for task queues). The engine enqueues its own main rendering function in this queue.
Modules may need to execute graphics functions in other threads. For example, slow procedural-texture functions may be executed by another thread. This opens the possibility of multiple threads needing to execute graphics functions. The Graphics Task Queue prevents conflict between such threads by serializing execution.
Task queues are dequeued and executed only by the main thread. Executing graphics functions is restricted to the main thread.
[2007/05]
The culling and rendering stages can be pipelined to utilize multi-core CPUs. Both stages can be executed concurrently by two threads. The render thread might sleep if the culling thread is still running.
[2007/05]
The design of this 3D engine is specialized for flight simulation. Consequently, it differs from generalized scene graphs in these aspects:
The counterparts between the basic classes of scene graphs and this engine are:
| Scene graphs: | Engine: |
|---|---|
| Node | private Nodes |
| Transform | private Transform |
| Spatial | shared LocalVolume, private WorldVolume |
| Geometry | LocalVertexs, Graph, Polygon |
| Group | - |
Last modified: Fri Nov 23 11:13:55 EST 2007