Just managed to re-use my male character model to create a female. It's still work in progress, but it was enough to inspired me to put together this quick concept cover art.
Wednesday, 20 January 2010
Monday, 18 January 2010
Octrees - Code and walkthrough
Octrees are a data structure to represent spartially dividing up a scene. The way they work is to divide up a scene into eight leafs, with each leaf further dividing up if they contained more objects than the set threashold.
You could then use this divided up scene for optimisations. Such as to only process rendering for the objects in the visible octrees, or to only process collisions for the objects in the same octree as the current object.
Here's a video of the octrees in action, notice how when a leaf becomes dense, it breaks down into a further eight leafs.
So let's start.
First we create our octree structure. With each octree will containing a pointer to it's parent tree, it's eight leafs, a set of objects and it's world position.
We can then create the octree with.
Now we'd need to handle adding an object to the tree, this is done by use of recursive function calls, that drill down into the leaf nodes to add the object to all the leafs it resides in. Once it's found a leaf if we have space for the object we add it into it's object list, if we don't have space we'll need to split the tree down to a further eight leafs and re-attempt adding the object.
To check if the object resides in a leaf's space we simply use our min max vectors which we're set in OctreeNew.
Now comes the fun part, splitting our octree into a further eight octrees.
To do so, we first create the eight leaf nodes from our parent's min max vectors and hSize variables.
We then parse through the current leaf's objects, remove them from the object list and re-add them into the appropriate new leafs we've just created.
Now for removing an object from the tree, we simply check through all the leafs the object resides in and one by one remove the object from the trees list. We then set a call to prune the tree, so that if the leafs are no longer needed they'll be deleted.
Above I set a timer to 1.0f which would count down elsewhere to call the prune tree function. With the prune tree function recursively calling itself on all it's leafs, and if the set of leafs have no objects in them they get deleted.
Again delete leafs works by recursively calling itself to free all the leafs inside.
That's it! Simply add in all your static objects, then whenever you move an object, just re-add it to the root tree, so it can put itself into the appropriate leafs.
You could then use this divided up scene for optimisations. Such as to only process rendering for the objects in the visible octrees, or to only process collisions for the objects in the same octree as the current object.
Here's a video of the octrees in action, notice how when a leaf becomes dense, it breaks down into a further eight leafs.
So let's start.
First we create our octree structure. With each octree will containing a pointer to it's parent tree, it's eight leafs, a set of objects and it's world position.
enum OctreeLeafs
{
leaf_bottom_front_left,
leaf_bottom_front_right,
leaf_bottom_back_left,
leaf_bottom_back_right,
leaf_top_front_left,
leaf_top_front_right,
leaf_top_back_left,
leaf_top_back_right,
};
struct Octree
{
Octree *parent;
Octree **leafs;
ObjectCollideable *objects[MAX_TREE_OBJECTS];
uint numberOfObjects;
float hSize;
Vector3 min, max;
};
We can then create the octree with.
void OctreeNew(Octree **tree, Octree *parent, const Vector3 position, const float size)
{
*tree = malloc( sizeof( Octree ) );
(*tree)->parent = parent;
(*tree)->leafs = nil;
(*tree)->numberOfObjects = 0;
(*tree)->hSize = size * 0.5f;
(*tree)->min = position;
(*tree)->max = position;
Vector3AddFloat( &(*tree)->min, -(*tree)->hSize );
Vector3AddFloat( &(*tree)->max, (*tree)->hSize );
}
Now we'd need to handle adding an object to the tree, this is done by use of recursive function calls, that drill down into the leaf nodes to add the object to all the leafs it resides in. Once it's found a leaf if we have space for the object we add it into it's object list, if we don't have space we'll need to split the tree down to a further eight leafs and re-attempt adding the object.
void OctreeAddObject(Octree *tree, ObjectCollideable *collideable)
{
// Ensure the object is within the octree's limits
if( tree->parent == nil )
{
UpdateCollisions( collideable );
Vector3 *objectMin = &collideable->min;
Vector3 *objectMax = &collideable->max;
if( objectMax->x < tree->min.x ||
objectMax->y < tree->min.y ||
objectMax->z < tree->min.z ||
objectMin->x > tree->max.x ||
objectMin->y > tree->max.y ||
objectMin->z > tree->max.z )
{
return;
}
}
// Insert in an approperate leaf node
if( tree->leafs != nil )
{
UpdateCollisions( collideable );
for( uint i=0; i<8; ++i )
{
Octree *leaf = tree->leafs[i];
if( OctreeIsInLeaf( leaf, &collideable->min, &collideable->max ) )
{
OctreeAddObject( leaf, collideable );
}
}
}
// Unless we don't have any
else if( tree->numberOfObjects < MAX_TREE_OBJECTS )
{
tree->objects[tree->numberOfObjects++] = collideable;
assert( collideable->numberOfOctrees < MAX_OBJECT_TREES );
collideable->octrees[collideable->numberOfOctrees++] = tree;
}
// If we have too many objects split the octree
else
{
OctreeSplit( tree );
// Try again
OctreeAddObject( tree, collideable );
}
}
To check if the object resides in a leaf's space we simply use our min max vectors which we're set in OctreeNew.
BOOL OctreeIsInLeaf(Octree *leaf, Vector3 *targetMin, Vector3 *targetMax)
{
Vector3 *sourceMin = &leaf->min;
Vector3 *sourceMax = &leaf->max;
if( sourceMax->y > targetMin->y && sourceMin->y < targetMax->y )
{
if( sourceMax->x > targetMin->x && sourceMin->x < targetMax->x )
{
if( sourceMax->z > targetMin->z && sourceMin->z < targetMax->z )
{
return YES;
}
}
}
return NO;
}
Now comes the fun part, splitting our octree into a further eight octrees.
To do so, we first create the eight leaf nodes from our parent's min max vectors and hSize variables.
void OctreeSplitTopLeafs(Octree *tree, const uint index, Vector3 position)
{
position.y += tree->hSize;
Octree **leaf = &( tree->leafs[index+4] );
OctreeNew( leaf, tree, position, tree->hSize );
}
void OctreeSplit(Octree *tree)
{
assert( tree->leafs == nil );
tree->leafs = malloc( sizeof( Octree ) * 8 );
// Create our leaf nodes
uint index = leaf_bottom_front_left;
Vector3 position = tree->min;
Vector3AddFloat( &position, tree->hSize * 0.5f );
Octree **leaf = &( tree->leafs[index] );
OctreeNew( leaf, tree, position, tree->hSize );
OctreeSplitTopLeafs( tree, index, position );
index = leaf_bottom_front_right;
position.x += tree->hSize;
leaf = &( tree->leafs[index] );
OctreeNew( leaf, tree, position, tree->hSize );
OctreeSplitTopLeafs( tree, index, position );
index = leaf_bottom_back_right;
position.z += tree->hSize;
leaf = &( tree->leafs[index] );
OctreeNew( leaf, tree, position, tree->hSize );
OctreeSplitTopLeafs( tree, index, position );
index = leaf_bottom_back_left;
position.x -= tree->hSize;
leaf = &( tree->leafs[index] );
OctreeNew( leaf, tree, position, tree->hSize );
OctreeSplitTopLeafs( tree, index, position );
...
We then parse through the current leaf's objects, remove them from the object list and re-add them into the appropriate new leafs we've just created.
// Now we need to sort our objects into our new leafs
while( tree->numberOfObjects > 0 )
{
ObjectCollideable *collideable = tree->objects[0];
removeFromList( collideable, (void**)tree->objects, &tree->numberOfObjects );
removeFromList( tree, (void**)collideable->octrees, &collideable->numberOfOctrees );
UpdateCollisions( collideable );
for( uint i=0; i<8; ++i )
{
Octree *leaf = tree->leafs[i];
if( OctreeIsInLeaf( leaf, &collideable->min, &collideable->max ) )
{
// Place this object in this leaf
leaf->objects[leaf->numberOfObjects++] = collideable;
assert( leaf->numberOfObjects <= MAX_TREE_OBJECTS );
collideable->octrees[collideable->numberOfOctrees++] = leaf;
assert( collideable->numberOfOctrees < MAX_OBJECT_TREES );
}
}
}
}
Now for removing an object from the tree, we simply check through all the leafs the object resides in and one by one remove the object from the trees list. We then set a call to prune the tree, so that if the leafs are no longer needed they'll be deleted.
void OctreeRemoveObject(ObjectCollideable *collideable)
{
while( collideable->numberOfOctrees > 0 )
{
Octree *tree = collideable->octrees[0];
removeFromList( collideable, (void**)tree->objects, &tree->numberOfObjects );
removeFromList( tree, (void**)collideable->octrees, &collideable->numberOfOctrees );
if( tree->numberOfObjects == 0 )
{
if( gEngine->collideables->pruneTrees <= 0.0f )
{
gEngine->collideables->pruneTrees = 1.0f;
}
}
}
}
Above I set a timer to 1.0f which would count down elsewhere to call the prune tree function. With the prune tree function recursively calling itself on all it's leafs, and if the set of leafs have no objects in them they get deleted.
void OctreePruneTree(Octree *tree)
{
if( tree->leafs != nil )
{
BOOL hasObjects = OctreeHasObjects( tree );
if( hasObjects == NO )
{
OctreeDeleteLeafs( tree );
}
else
{
for( uint i=0; i<8; ++i )
{
OctreePruneTree( tree->leafs[i] );
}
}
}
}
BOOL OctreeHasObjects(Octree *tree)
{
BOOL hasObjects = tree->numberOfObjects > 0;
if( tree->leafs != nil )
{
for( uint i=0; i<8 && hasObjects == NO; ++i )
{
hasObjects |= OctreeHasObjects( tree->leafs[i] );
}
}
return hasObjects;
}
Again delete leafs works by recursively calling itself to free all the leafs inside.
void OctreeDeleteLeafs(Octree *tree)
{
// Ensure all our leafs are deleted
if( tree->leafs != nil )
{
for( uint i=0; i<8; ++i )
{
if( tree->leafs[i] != nil )
{
Octree *leaf = tree->leafs[i];
OctreeDeleteLeafs( leaf );
}
}
free( tree->leafs );
tree->leafs = nil;
}
}
That's it! Simply add in all your static objects, then whenever you move an object, just re-add it to the root tree, so it can put itself into the appropriate leafs.
Friday, 8 January 2010
Widgets and function pointers
I'm currently working through the setting screens, so I needed to make a few widget classes. Basically I have a bunch of widgets which contain their position, size and some functions to determine how input is handled. Now comes the fun bit, re-using the class for different options. I wanted one widget to handle starting a new game, one for toggling collision boxes, etc.
To get this done, I used function pointers. I'd let the scene handle the interactions with the widgets and when one was invoked, it's set callback was fired.
So in the header file, I have two members, the first being the function to call, and second being the parameter to pass into the function.
When the widget is invoked, it then went ahead and fired it's function pointer.
So in the case of toggling a bool on or off, in the main scene I'd create a widget and pass in the function pointer for toggling bools with the variable active.
Finally, the function of toggleBool would simply toggle the bool.
So now we have a classes which encapsulate the drawing and user interaction, but provide differing responses.
To get this done, I used function pointers. I'd let the scene handle the interactions with the widgets and when one was invoked, it's set callback was fired.
So in the header file, I have two members, the first being the function to call, and second being the parameter to pass into the function.
@interface WidgetButton : WidgetBase
{
@public
void (*callback_routine)(void *data);
void *callback_data;
}
When the widget is invoked, it then went ahead and fired it's function pointer.
-(BOOL)handleControls:(ScreenTouches*)screenTouch
{
if( [super handleControls:screenTouch] )
{
if( callback_routine )
{
callback_routine( callback_data );
}
return YES;
}
return NO;
}
So in the case of toggling a bool on or off, in the main scene I'd create a widget and pass in the function pointer for toggling bools with the variable active.
activateWidget = [[WidgetButton alloc] init];
((WidgetButton*)activateWidget)->callback_routine = &toggleBool;
((WidgetButton*)activateWidget)->callback_data = &active;
Finally, the function of toggleBool would simply toggle the bool.
void toggleBool(void *data)
{
BOOL *toggle = (BOOL*)data;
*toggle = !(*toggle);
}
So now we have a classes which encapsulate the drawing and user interaction, but provide differing responses.
Friday, 1 January 2010
iPhone - Unproject a 2D point
Alright, just added in support for selecting 3d objects using 2d coordinates. So you can select an object in a 3d scene using your finger. The idea to do this is to unproject the 2d coordinates passed in at 0 and 1 range to get the direction of the ray, then simply use that ray to find which objects collide.
Step one was to find the source for glu unProject function. There's loads of sources online for OpenGL, so all you need to do is port it over to OpenGL ES (just replace GLdouble with GLfloat).
Here's some source code ported from http://code.google.com/p/iphone-glu
static void __gluMultMatrixVecd(const GLfloat matrix[16], const GLfloat in[4],
GLfloat out[4])
{
int i;
for( i=0; i<4; ++i )
{
out[i] =
in[0] * matrix[0*4+i] +
in[1] * matrix[1*4+i] +
in[2] * matrix[2*4+i] +
in[3] * matrix[3*4+i];
}
}
/*
** Invert 4x4 matrix.
** Contributed by David Moore (See Mesa bug #6748)
*/
static int __gluInvertMatrixd(const GLfloat m[16], GLfloat invOut[16])
{
GLfloat inv[16];
inv[0] = m[5]*m[10]*m[15] - m[5]*m[11]*m[14] - m[9]*m[6]*m[15]
+ m[9]*m[7]*m[14] + m[13]*m[6]*m[11] - m[13]*m[7]*m[10];
inv[4] = - m[4]*m[10]*m[15] + m[4]*m[11]*m[14] + m[8]*m[6]*m[15]
- m[8]*m[7]*m[14] - m[12]*m[6]*m[11] + m[12]*m[7]*m[10];
inv[8] = m[4]*m[9]*m[15] - m[4]*m[11]*m[13] - m[8]*m[5]*m[15]
+ m[8]*m[7]*m[13] + m[12]*m[5]*m[11] - m[12]*m[7]*m[9];
inv[12] = - m[4]*m[9]*m[14] + m[4]*m[10]*m[13] + m[8]*m[5]*m[14]
- m[8]*m[6]*m[13] - m[12]*m[5]*m[10] + m[12]*m[6]*m[9];
inv[1] = - m[1]*m[10]*m[15] + m[1]*m[11]*m[14] + m[9]*m[2]*m[15]
- m[9]*m[3]*m[14] - m[13]*m[2]*m[11] + m[13]*m[3]*m[10];
inv[5] = m[0]*m[10]*m[15] - m[0]*m[11]*m[14] - m[8]*m[2]*m[15]
+ m[8]*m[3]*m[14] + m[12]*m[2]*m[11] - m[12]*m[3]*m[10];
inv[9] = - m[0]*m[9]*m[15] + m[0]*m[11]*m[13] + m[8]*m[1]*m[15]
- m[8]*m[3]*m[13] - m[12]*m[1]*m[11] + m[12]*m[3]*m[9];
inv[13] = m[0]*m[9]*m[14] - m[0]*m[10]*m[13] - m[8]*m[1]*m[14]
+ m[8]*m[2]*m[13] + m[12]*m[1]*m[10] - m[12]*m[2]*m[9];
inv[2] = m[1]*m[6]*m[15] - m[1]*m[7]*m[14] - m[5]*m[2]*m[15]
+ m[5]*m[3]*m[14] + m[13]*m[2]*m[7] - m[13]*m[3]*m[6];
inv[6] = - m[0]*m[6]*m[15] + m[0]*m[7]*m[14] + m[4]*m[2]*m[15]
- m[4]*m[3]*m[14] - m[12]*m[2]*m[7] + m[12]*m[3]*m[6];
inv[10] = m[0]*m[5]*m[15] - m[0]*m[7]*m[13] - m[4]*m[1]*m[15]
+ m[4]*m[3]*m[13] + m[12]*m[1]*m[7] - m[12]*m[3]*m[5];
inv[14] = - m[0]*m[5]*m[14] + m[0]*m[6]*m[13] + m[4]*m[1]*m[14]
- m[4]*m[2]*m[13] - m[12]*m[1]*m[6] + m[12]*m[2]*m[5];
inv[3] = - m[1]*m[6]*m[11] + m[1]*m[7]*m[10] + m[5]*m[2]*m[11]
- m[5]*m[3]*m[10] - m[9]*m[2]*m[7] + m[9]*m[3]*m[6];
inv[7] = m[0]*m[6]*m[11] - m[0]*m[7]*m[10] - m[4]*m[2]*m[11]
+ m[4]*m[3]*m[10] + m[8]*m[2]*m[7] - m[8]*m[3]*m[6];
inv[11] = - m[0]*m[5]*m[11] + m[0]*m[7]*m[9] + m[4]*m[1]*m[11]
- m[4]*m[3]*m[9] - m[8]*m[1]*m[7] + m[8]*m[3]*m[5];
inv[15] = m[0]*m[5]*m[10] - m[0]*m[6]*m[9] - m[4]*m[1]*m[10]
+ m[4]*m[2]*m[9] + m[8]*m[1]*m[6] - m[8]*m[2]*m[5];
GLfloat det = m[0]*inv[0] + m[1]*inv[4] + m[2]*inv[8] + m[3]*inv[12];
if( det == 0 )
{
return GL_FALSE;
}
det = 1.0 / det;
for( int i=0; i<16; ++i )
{
invOut[i] = inv[i] * det;
}
return GL_TRUE;
}
static void __gluMultMatricesd(const GLfloat a[16], const GLfloat b[16],
GLfloat r[16])
{
int i, j;
for( i=0; i<4; ++i )
{
for( j=0; j<4; ++j )
{
r[i*4+j] =
a[i*4+0]*b[0*4+j] +
a[i*4+1]*b[1*4+j] +
a[i*4+2]*b[2*4+j] +
a[i*4+3]*b[3*4+j];
}
}
}
BOOL gluUnProject(GLfloat winx, GLfloat winy, GLfloat winz,
const GLfloat modelMatrix[16],
const GLfloat projMatrix[16],
const GLint viewport[4],
GLfloat *objx, GLfloat *objy, GLfloat *objz)
{
GLfloat finalMatrix[16];
GLfloat in[4];
GLfloat out[4];
__gluMultMatricesd( modelMatrix, projMatrix, finalMatrix );
if( !__gluInvertMatrixd( finalMatrix, finalMatrix ) )
{
return NO;
}
in[0] = winx;
in[1] = winy;
in[2] = winz;
in[3] = 1.0;
/* Map x and y from window coordinates */
in[0] = ( in[0] - viewport[0] ) / viewport[2];
in[1] = ( in[1] - viewport[1] ) / viewport[3];
/* Map to range -1 to 1 */
in[0] = in[0] * 2 - 1;
in[1] = in[1] * 2 - 1;
in[2] = in[2] * 2 - 1;
__gluMultMatrixVecd(finalMatrix, in, out);
if( out[3] == 0.0 )
{
return NO;
}
out[0] /= out[3];
out[1] /= out[3];
out[2] /= out[3];
*objx = out[0];
*objy = out[1];
*objz = out[2];
return YES;
}
Step two take in a 2d coordinate and feed it into the collision detection system. My collision system scans through all base objects of ObjectCollideable and returns the one which is closest to the start of the ray. The viewport and projection matrices are calculated on OpenGL initialisation with the following calls.
ObjectCollideable* Projection2DScan(CGPoint point)
{
GLfloat modelViewMatrix[16];
glGetFloatv( GL_MODELVIEW_MATRIX, modelViewMatrix );
point.y = 1.0f - point.x;
point.x *= gView->viewport[2];
point.y *= gView->viewport[3];
Vector3 nearPlane, farPlane;
gluUnProject( point.x, point.y, 0.0f, modelViewMatrix, gView->projectionMatrix, gView->viewport, &nearPlane.x, &nearPlane.y, &nearPlane.z );
gluUnProject( point.x, point.y, 1.0f, modelViewMatrix, gView->projectionMatrix, gView->viewport, &farPlane.x, &farPlane.y, &farPlane.z );
// Figure out our ray's direction
Vector3 direction = farPlane;
Vector3Sub( &direction, &nearPlane );
Vector3Normalize( &direction );
// Cast the ray from our near plane
Vector3 farPoint = Vector3MulResult( &direction, 500.0f );
Vector3Add( &farPoint, &nearPlane );
Vector3 hitLocation;
ObjectCollideable *hitObject = BasicLineCollisionCheck( &nearPlane, &farPoint, &hitLocation, gEngine->collideables );
return hitObject;
}
Subscribe to:
Posts (Atom)