![]() |
SSG: A Simple Scene Graph APIfor OpenGLby Steve Baker |
SSG is a part of PLIB.
This document assumes a certain degree of knowledge of OpenGL.
SSG includes a subsidiary library of simple matix and vector math with support for some intersection testing, field-of-view culling and such like. This is called 'Simple Geometry' (SG). SG is used extensively by SSG - but is also useful as a standalone library.
A Scene Graph is essentially just a tree-structured database containing a hierarchy of branches - and a bunch of leaf nodes. Each leaf node does some OpenGL rendering - the branch nodes are intended to manage things like: field of view (FOV) culling, level of detail (LOD) management, transformations, and animation.
In addition, each leaf node has a structure tacked on to it to encapsulate OpenGL state information - and that in turn may optionally have a texture applied to it.
Hence, all SSG symbols for classes and functions start with ssg
and all #define
tokens start with SSG
. Functions and symbols
that belong to the SG library similarly start with sg
or SG
.
Words within a class or function name are Capitalised and NOT
separated with underscores. Words within #define
tokens may
be separated with underscores to make them readable.
class ssgBase | |__ class ssgEntity | | | |__ class ssgLeaf | | |__ class ssgVTable | | | |__ class ssgBranch | |__ class ssgRoot | |__ class ssgInvisible | |__ class ssgSelector | | |__ class ssgAnimation | | |__ class ssgLevelOfDetail | | | |__ class ssgBaseTransform | | |__ class ssgTransform | | |__ class ssgTexTrans | | | |__ class ssgCutout | |___ class ssgState | |__ class ssgSimpleState | |___ class ssgTextureThe general idea is that, all geometry is contained in ssgLeaf classes, all data heirarchy is in a ssgBranch classes and all OpenGL state information is in ssgStates.
You may not declare instances of ssgBase, ssgEntity, ssgBaseTransform, ssgLeaf or ssgState since they are all abstract classes.
It is presumed that applications will add new kinds of leaves, branches, states and textures to customise SSG to their needs.
class ssgBase
- The Universal Abstract Base Class.class ssgBase { void ref () ; void deRef () ; int getRef () ; int isA ( int ty ) ; int isAKindOf ( int ty ) ; int getType (void) ; virtual char *getTypeName(void) ; virtual void print ( FILE *fd = stderr ) ; virtual void save ( FILE *fd = stderr ) ; } ;
Sometimes, you need a node to stay in memory even though it may be
be disconnected from the scene graph. You can achieve that by
calling ssgBase::ref()
to increment the reference count. If you later find
you don't need that node anymore then you may ssgBase::deRef()
it. If you
ssgBase::deRef()
a node to zero, SSG won't automatically delete it - you
still need to use delete
to do that. The only time SSG will
automatically delete a node when the ref count is zero is when
that node is removed from the scene graph - or when a parent
node is deleted and its children are no longer referenced.
You can read the current ref count for a node using ssgBase::getRef()
.
int ssgTypeBase () ; int ssgTypeEntity () ; int ssgTypeLeaf () ; int ssgTypeVTable () ; int ssgTypeDisplayList() ; int ssgTypeBranch () ; int ssgTypeBaseTransform(); int ssgTypeTransform () ; int ssgTypeTexTrans () ; int ssgTypeSelector () ; int ssgTypeAnimation () ; int ssgTypeRoot () ; int ssgTypeCutout () ;Now, you can use the
ssgBase::isA(type)
or ssgBase::isAKindOf
to test the type of the node. For example, if you want to test
whether a node is a Leaf node or a Branch node, you can do this:
if ( mynode -> isAKindOf ( ssgTypeLeaf ) ) printf ( "Leaf node\n" ) ; else if ( mynode -> isAKindOf ( ssgTypeBranch ) ) printf ( "Branch node\n" ) ; else printf ( "Something else\n" ) ;Notice that if you ran that code on (say) an ssgSelector, then it'll print "Branch node" since the Selector class is derived from the Branch class. If you wanted to tell if a node was *exactly* a Branch node - and not from a derived class, then you could use:
if ( mynode -> isA ( ssgTypeBranch ) ) printf ( "Branch node\n" ) ;Finally, you can actually read the type of a node - either as a token (using
ssgBase::getType()
) or as an ASCII string
(using ssgBase::getTypeName()
). The latter is very useful
for debug routines:
printf ( "ERROR - something wrong with my '%s' node.\n", mynode -> getTypeName () ) ;
ssgBase::print(fd,indent)
does that for you - it prints out the node itself - and anything
connected beneath it in the scene graph. fd
is the
file descriptor to print to (defaults to stderr) and
indent
is a string that will prefix all output lines
- and is used internally within SSG to make printout of tree
structures more legible by indenting them. It would be unwise
to attempt to parse the output of ssgBase::print
into another
program since it is only intended for human consumption and the
format may change dramatically between revisions of SSG.
class ssgEntity
- A Node in the Tree.clas ssgEntity : public ssgBase { public: ssgEntity (void) ; virtual ~ssgEntity (void) ; int getTraversalMask () ; void setTraversalMask ( int t ) ; void setTraversalMaskBits ( int t ) ; void clrTraversalMaskBits ( int t ) ; char *getUserData () ; void setUserData ( char *s ) ; virtual void recalcBSphere (void) ; int isDirtyBSphere (void) ; void dirtyBSphere () ; sgSphere *getBSphere () ; void setName ( char *nm ) { name = nm ; } virtual int getNumKids (void) ; int getNumParents () ; ssgBranch *getParent ( int p ) ; ssgBranch *getNextParent () ; virtual void cull ( sgFrustum *f, sgMat4 m, int test_needed ) ; virtual void isect ( sgSphere *s, sgMat4 m, int test_needed ) ; virtual void hot ( sgVec3 s, sgMat4 m, int test_needed ) ; } ;
The structure of the scene graph permits the same node to be inserted into the graph in multiple locations. This is useful for saving space when the same object is needed many times in the scene. Hence, any given node may have more than one parent node.
You can traverse the list of parent nodes
using ssgEntity::getNumParents()
to find out the number
of parents this node has and
ssgEntity::getParent(n)
to locate the n'th parent.
Alternatively, after calling getParent, you can call getNextParent to get the N+1'th parent node - it returns NULL when no more parents are available.
As a convenience for general tree-walking routines, there is a
ssgEntity::getNumKids()
call - which will always
return zero on leaf nodes. You cannot actually get kid nodes unless
the node is some kind of ssgBranch.
ssgEntity::setName(s)
sets the name,
ssgEntity::getName()
returns it.
It's quite useful to be able to limit the traversal so that certain nodes do not get tested. This can save time - or prevent undesirable side-effects.
Each entity has a 'traveral mask' - which is a simple integer with one bit per kind of traversal. At present, there are three kinds of traversal:
SSGTRAV_CULL -- Culling to the field of view. SSGTRAV_ISECT -- General intersection testing. SSGTRAV_HOT -- Height-over-terrain testing.You can directly set or get the traversal mask with
ssgEntity::setTraversalMask(m)
ssgEntity::getTraversalMask()
. You can set an individual traversal bit using
ssgEntity::setTraversalMaskBits(m)
or clear one using
ssgEntity::clrTraversalMaskBits(m)
.
ssgEntity::getUserData()
and ssgEntity::setUserData(data)
. Note that
it is your responsability to track when that data should be deleted since
SSG's reference counting mechanism does not extend to user data.
Clearly one does not want to recompute the bounding sphere every frame - just some objects do change their size over time. Hence, the bounding sphere is lazily evaluated.
Whenever you do something to change the size or shape of an entity,
you should call ssgEntity::dirtyBSphere()
. This will
mark this entity's sphere as invalid ("dirty") and also, walk
backwards up the scene graph tree making all the nodes above
this one dirty too. The next time SSG needs to know the bounding
sphere size, it'll recompute it.
If you'd prefer for the bounding sphere recalculation to be
done immediately, then you can call ssgEntity::recalcBSphere()
and it will be done immediately. Branch nodes like ssgTransforms will
automatically dirty their bounding spheres when necessary. Leaf nodes
generally do not.
When anyone needs to know the bounding sphere size for a node,
they'll call ssgEntity::getBSphere()
- which will
recaclulate the Bsphere if it needs to.
ssgEntity::cull()
- calling
this on the root node in the scene graph causes the entire
scene to be rendered in an efficient manner.
class ssgLeaf
- Leaf nodes.class ssgLeaf : public ssgEntity { public: int getExternalPropertyIndex () int isTranslucent () int hasState () ssgState *getState () void setState ( ssgState *st ) virtual float *getVertex ( int i ) virtual float *getNormal ( int i ) virtual float *getColour ( int i ) virtual float *getTexCoord ( int i ) virtual int getNumTriangles() ; virtual void getTriangle ( int n, short *v1, short *v2, short *v3 ) virtual void transform ( sgMat4 m ) void setCullFace ( int cf ) int getCullFace () void makeDList () ; void deleteDList () ; GLuint getDListIndex () ; } ;
ssgLeaf::makeDList()
. If you want to
make changes to the Leaf, you'll have to call makeDList again
since OpenGL does not support the editing of display lists.
You can call ssgLeaf::deleteDList()
to stop
this leaf from being display listed from now on and to
free up the display list memory.
ssgLeaf::getDListIndex()
returns the OpenGL
display list handle - or zero if no display list exists
for this leaf.
If you change a leaf node's geometry when it has an active display list without calling either deleteDList or makeDList again, then any subsequent operation involving rendering this node could fail.
ssgLeaf::setCullFace(cf)
where cf
is TRUE to enable backface culling,
FALSE to disable it. You can test the state of face culling
using ssgLeaf::getCullFace()
.
Nodes may also be stateless - but that isn't useful for any of the existing SSG leaf node types.
You can set the state for a node using ssgLeaf::setState(state)
and query it using ssgLeaf::getState()
. You can ask if
a node has state information attached using ssgLeaf::hasState()
.
Since OpenGL does not render translucent object well when Z-buffering
is enabled, it's often useful to know if an object is translucent.
ssgLeaf::isTranslucent()
handles that test.
It is often useful to tag ssgState's with external properties - and
you can retrieve the property of a leaf's state using
ssgLeaf::getExternalPropertyIndex()
.
Although classes derived from ssgLeaf are entitled to store their geometry in any form, all of them are required to respond to queries about basic triangle primitives.
Firstly, you can get a count of the number of triangles in this
leaf using ssgLeaf::getNumTriangles()
. Each triangle
has an index number for each vertex which can be queried using
ssgLeaf::getTriangle(n,&v1,&v2,&v3)
which copies
the 'short' indices for the n'th triangle's three vertices into
v1, v2 and v3.
Once you know the indices of a triangle's vertices, you can ask for
more information about that vertex using
ssgLeaf::getVertex(i)
,
ssgLeaf::getNormal(i)
,
ssgLeaf::getColour(i)
, and
ssgLeaf::getTexCoord(i)
. These calls allow you to
retrieve the i'th vertex, normal, colour or texture coordinate as
a short floating point array. (3 elements for Vertex and Normal,
4 elements for Colour (RGBA) and two elements for a texture coordinate.
You can transform all the vertices of a leaf each frame by placing
an ssgTransform node above the leaf in the scene graph - but for
transformations that never change, it's more efficient to pre-transform
the vertices in the leaf node.
ssgLeaf::transform(matrix)
permenantly transforms all
the vertices and normals of this leaf by multiplying them by the
matrix. (In the case of the normals, the translation part of the
matrix is ignored).
It's inadvisable to repeatedly transform a leaf using transform
since roundoff error will be accumulated with bad consequences (eventually).
In those cases, use an ssgTransform node.
class ssgBranch
- A basic branch node.There are a rich set of functions for adding, deleting and replacing child nodes:
class ssgBranch : public ssgEntity { int getNumKids (void) ; ssgEntity *getKid ( int n ) ; ssgEntity *getNextKid (void) ; int searchForKid ( ssgEntity *entity ) ; void addKid ( ssgEntity *entity ) ; void removeKid ( int n ) ; void removeKid ( ssgEntity *entity ) ; void removeAllKids (void) ; } ;Most of these are pretty self-explanatory.
ssgBranch::getNumKids()
returns the number of child nodes
beneath this branch.
ssgBranch::getKid(n)
returns the address of the n'th child ssgEntity.
ssgBranch::getNextKid()
returns the address of the child entity following
the last one returned by getKid or getNextKid - returning NULL when all child nodes
have been exhausted.
ssgBranch::searchForKid(entity)
searches for the specified entity
in the list of child nodes and returns it's index (ie the inverse of getKid).
ssgBranch::addKid(entity)
adds the specified entity to the list of
child nodes - the new node is added at the end of the list and will therefore
have the highest numbered index.
ssgBranch::removeKid(n)
removes the n'th child node and renumbers
any higher numbered children so there are never any gaps in the number range.
ssgBranch::removeKid(entity)
same as removeKid(searchKid(entity)).
ssgBranch::removeAllKids()
remove ALL child entities.
If the entity removed by any of these commands has a ref count of
zero, it will be deleted.
class ssgInvisible
- Invisible parts of a Scene Graph.class ssgRoot
- The Root of the Scene Graph,class ssgRoot : public ssgBranch { } ;
class ssgSelector
- A switch point,A selector contains up to 32 daughter objects and a 32 bit unsigned integer mask. Where there is a one bit in the mask, that child object will be drawn, where there is a zero, it will not.
ssgSelector::select(mask)
sets the mask,
ssgSelector::getSelect()
returns the current
state of the mask, ssgSelector::selectStep(n)
sets the n'th mask bit and zeroes out all the others - effectively
causing only the n'th child object to be displayed.
It is quite common to have an ssgSelector with just one child object that can be enabled with select(1) and disabled with select(0).
class ssgBaseTransform
- Nodes with transformations.class ssgBaseTransform : ssgBranch { void getTransform ( sgMat4 xform ) ; virtual void setTransform ( sgVec3 xyz ) ; virtual void setTransform ( sgCoord *xform ) ; virtual void setTransform ( sgCoord *xform, float sx, float sy, float sz ) ; virtual void setTransform ( sgMat4 xform ) ; } ;You can set up the transformation matrix using
ssgBaseTransform::setTransform()
which has versions that allow you to pass either a full-blown
4x4 matrix, a simple translation, an 'sgCoord' (which is an xyz translation
and a hpr rotation) or an sgCoord and scale factors in each of X, Y and Z
directions.
ssgBaseTransform::getTransform(matrix)
copies the current
transform into the matrix that you provide.
class ssgTransform
- Nodes with spatial transformations.class ssgTexTrans
- Nodes with moving textureclass ssgCutout
- turn-to-face-the-viewer nodes.There are actually two distinct forms of ssgCutout - depending on what value is passed as a parameter to the constructor function. ssgCutout(TRUE) produces an object that rotates around it's origin such as to keep the X/Z plane parallel to the screen and ssgCutout(FALSE) produces one that tries to stay parallel to the screen - but which is only allowed to rotate about the Z axis. The latter form is useful for objects with cylindrical symmetry and the former for those with spherical symmetry.
class ssgState
- OpenGL state representation.There can (in principal) be a number of different ways to represent OpenGL state - but all must be derived from an ssgState:
class ssgState : public ssgBase { int getExternalPropertyIndex () ; void setExternalPropertyIndex ( int i ) ; virtual void force () ; virtual void apply () ; } ;
ssgState::setExternalPropertyIndex(i)
or queried using ssgState::getExternalPropertyIndex()
.
External properties are of use to certain sorts of applications programs,
for example, a game might want to encode the set of OpenGL state information
that represents Lava as something that is hot and Ice as something that
is cold by encoding the temperature of the material in the External
property field. Most applications will probably use this field as an
index into a table of material properties inside the application itself.
In such cases, it is important to bear in mind that SSG changes the OpenGL state as little as possible - in order to save time. Hence, when a leaf node has just been drawn with one set of state information, and another leaf node is about to be drawn using another, SSG carefully compares the two states to see how they differ and arranges to make only the fewest possible OpenGL state change calls. If the application goes in "behind SSG's back" and changes state then SSG will be confused.
There are two ways to achive this. One is to use SSG state classes to
change the state by calling ssgState::apply()
. That call
will ensure that OpenGL's state matches the desired state using the
minimum of calls. However, if your application absolutely MUST make
it's own state calls then you should call ssgState::force()
to force all aspects of a specified state to be set in OpenGL so that
SSG can be certain about how things are set up.
class ssgSimpleState
- Simple State class.class ssgSimpleState : ssgState { void disable ( GLenum mode ) ; void enable ( GLenum mode ) ; void set ( GLenum mode, int val ) { val ? enable(mode) : disable(mode) ; } void setTexture ( char *fname, int wrapu = TRUE, int wrapv = TRUE ) void setTexture ( ssgTexture *tex ) void setTexture ( GLuint tex ) void setColourMaterial ( GLenum which ) void setMaterial ( GLenum which, float r, float g, float b, float a = 1.0f ) void setMaterial ( GLenum which, sgVec4 rgba ) void setShininess ( float sh ) void setShadeModel ( GLenum model ) void setAlphaClamp ( float clamp ) } ;These calls mostly correspond to similarly named OpenGL functions.
ssgSimpleState:: disable ( mode )
,
ssgSimpleState:: enable ( mode )
and
ssgSimpleState:: set ( mode, val )
provide
the same services as glEnable and glDisable ('set' is a convenience function
that is a 'disable' if 'val' is FALSE, 'enable' otherwise). The 'mode'
parameter uses tokens that are similarly named to those in OpenGL:
SSG_GL_TEXTURE_EN SSG_GL_CULL_FACE_EN SSG_GL_COLOR_MATERIAL_EN SSG_GL_BLEND_EN SSG_GL_ALPHA_TEST_EN SSG_GL_LIGHTING_EN
ssgSimpleState::setTexture ( fname, wrapu, wrapv )
,
ssgSimpleState::setTexture ( ssgtexture )
, and
ssgSimpleState::setTexture ( texture_handle )
.
In the form that takes a filename, U-axis wrap and V-axis wrap flags, the
texture is loaded from a texture file on disk (see ssgTexture
below for details on how this is done). The map will be MIPmapped and set with
a texture environment that is GL_LINEAR_MIPMAP_LINEAR and GL_MODULATE.
If you need something fancier, then declare an 'ssgTexture' class and pass that to the setTexture function. You can also load your own texture and pass the OpenGL glBindTexture handle to setTexture.
ssgSimpleState::setColourMaterial(which)
ssgSimpleState::setMaterial(which,r,g,b,a)
ssgSimpleState::setMaterial(which,rgba)
ssgSimpleState::setShininess(sh)
ssgSimpleState::setShadeModel(model)
ssgSimpleState::setAlphaClamp(clamp)
class ssgTexture
- Storing texture maps.
The ssgTexture constructor function
ssgTexture::ssgTexture( char *fname,
int wrapu = TRUE, int wrapv = TRUE )
does all the work,
presuming that you require GL_LINEAR_MIPMAP_LINEAR filtering and a
GL_MODULATE texture environment.
You can obtain the OpenGL glBindTexture handle for the texture
using ssgTexture::getHandle()
.
When ssgTexture loads a map from disk, it uses the filename extension to determine which image format the file is in.
Currently, only SGI format and uncompressed 8 or 24 bit BMP images are supported - but more formats are planned for the future. Filenames ending with '.rgb', '.rgba', '.int', '.inta', '.bw' are assumed to be SGI formatted files, '.bmp' are in Microsoft's BMP format and '.png' are in Portable Network Graphics format.
If for any reason ssgTexture cannot load the requested file, it creates a 2x2 texel red and white chequerboard map to enable the program to continue running. This is often very useful for debugging and to enable program development to continue when texture maps are not yet painted.
void ssgSetFOV ( float w, float h ) ; void ssgSetNearFar ( float n, float f ) ; void ssgSetCamera ( sgCoord *coord ) ;The ssgSetFOV call sets up the vertical and horizontal fields of view (in degrees), ssgSetNearFar sets the near and far clip planes (in whatever units your model is built in). Finally, you can position the virtual camera relative to the database origin using ssgSetCamera.
void ssgCullAndDraw ( ssgRoot *root ) ;This call deals with the entire process of rendering the database. Your application need only call ssgInit(), build a database, position the camera and call ssgCullAndDraw using the root node of that database.
int ssgIsect ( ssgRoot *root, sgSphere *s, sgMat4 m, ssgHit **results ) ; int ssgHOT ( ssgRoot *root, sgVec3 s, sgMat4 m, ssgHit **results ) ; int ssgLOS ( ssgRoot *root, sgVec3 s, sgMat4 m, ssgHit **results ) ;These three calls implement various ways to test the database for collisions, weapon impacts and such like. In each case, the search for a collision starts at 'root', and the database is transformed by the matrix 'm' before the test is evaluated - hence, 'm' is ususally the inverse of the matrix describing the test object's location.
ie: ssgHit *results ; int num_hits = ssgIsect ( root, &sphere, mat, &results ) ; for ( int i = 0 ; i < num_hits ; i++ ) { ssgHit *h = &(results [ i ]) ; /* Do something with 'h' */ }Remember, you must finish using the results array before you do another ssgIsect/ssgHOT/ssgLOS because all three functions share the same results array.
An ssgHit looks like this:
class ssgHit { ssgLeaf *leaf ; int triangle ; sgVec4 plane ; sgMat4 matrix ; ssgHit () int getNumPathEntries () ; ssgEntity *getPathEntry ( int i ) ; } ;The 'leaf' member points at the leaf node that impacted the sphere. The 'triangle' member tells you which triangle within the leaf did the impacting. The 'plane' member contains the plane equation of the impacting triangle and the 'matrix' element tells you the net result of concatenating all the transform nodes from the root to the leaf to the matrix you provided in the ssgIsect call.
It's possible for there to be multiple paths through the scene graph to the leaf node. Sometimes you'll need to look back up the tree to see nodes above the one that we actually impacted with. Hence, you can read all the ssgEntities that were traversed on the path from the root down to the leaf. Calling the 'getNumPathEntries' function to find the number of nodes along the path - and then 'getPathEntry(n)' to get the n'th entry in the path. The 'root' node will always be the zeroth entry in the path - and the leaf node will always be the last.
ssgLight *ssgGetLight ( int i ) ;...to get the i'th light should you need to manipulate it.
class ssgLight { int isOn () ; void on () ; void off () ; void setPosition ( sgVec3 pos ) ; void setHeadlight ( int head ) ; int isHeadlight () ; } ;Each light can be turned on or off - or tested to see if it's on or off.
Lights are positioned with 'setPosition()' - which can be relative to the origin of the world - or relative to the SSG camera (in 'headlight' mode).
int ssgGetNumTexelsLoaded () ;(Bear in mind that a texel could be 16 or 32 bits depending on the hardware - and with MIPmapping enabled, 25% of the texels will be in the MIPmaps - so ssgGetNumTexelsLoaded will return a larger number than the total of the sizes of the input images might suggest.
During testing, you sometimes need to disable texture rendering:
void ssgOverrideTexture ( int on_off ) ;
typedef ssgBranch *(*ssgHookFunc)(char *) ; ssgEntity *ssgLoadAC ( char *fname, ssgHookFunc hookfunc = NULL ) ;Minimally, all you need to do is to call ssgLoadAC with the name of the file to load. However, most file formats (AC3D's included) lack many desirable features, and it is also often necessary to store application-specific information in the file.
SSG's loaders will decode the comment fields found in the nodes of many common file formats and pass these onto the application via 'hookfunc'. This function should decode the string and construct whatever kind of SSG node it considers appropriate.
Similarly, the application may wish to embellish the ssgState of a loaded node - and since state information rarely has a comment field in most file formats, we pass the texture filename instead and expect the application to construct the entire ssgState:
void ssgSetAppStateCallback ( ssgState *(*cb)(char *) ) ;One common problem with file loaders is that it's often possible to refer to a second file from inside the first - but the path to that file is often not adequately defined by the original file. Hence, the application can specify a file path to be prepended to all model or texture file names.
void ssgModelPath ( char *path ) ; void ssgTexturePath ( char *path ) ;Most file formats contain considerable numbers of redundant nodes (because of the way people build using these tools). This function walks a database sub-tree multiplying out any ssgTransform nodes and replacing them with ssgBranch'ed - unless they have userdata associated with them. Any branch nodes with zero kids are deleted - any with just one kid are eliminated and the child node pushed up one level.
void ssgFlatten ( ssgEntity *ent ) ;It's important for 3D performance to optimise triangles into triangle strips or fans. Since most file formats don't record strip/fan information, it's useful to call:
void ssgStripify ( ssgEntity *ent ) ;