Performances GPU vs CPU matrix palette skinning (WAS: Tutorial #2: Part 1: Animated character walking around. Walk cycle and animated clowds)

I planned, for a while, to do another GLES 20 demo for AnimKit with multiple characters on the scene. Found some time yesterday and this is the start (video bellow). Probably I'll cover this in multiple posts; posting the results here when I find some time to progress with it.

Note that the scene is just a work in progress, clouds behind are big panes causing some performance impact but I think a good illustration of what can be done in few hours and I'll use it as input for later performance optimization work on "AnimKit on OpenGL ES 2.0". I'll post code and more text soon, my one year old is about to wake up.


The first work in progress version of code is here: commit 3e7cfe2b27 WIP: Tutorial #2: Part 1: Animated character walking around.


The code could be used as illustration and for benchmarking, I guess if you have a simple scene with less then 4000 matrix skinned vertices it should also be usable, but for this example it is not OK - downloaded SDK for iOS 5.0 and tried it on iPhone 3GS. Got only 7 frames per second (~8000 skinned vertices).
Tried more complex model with 5 animated instances and got 1-2 frames per second (40000 skinned vertices). The model from post Skeleton and pose character animation using AnimKit runs at 14 frames per second.


As assumed in previous posts, CPU matrix skinning (akGeometryDeformer::LBSkinning()) that enumerates through all vertices and normals is the bottleneck - most of the time spent there.

On the other side, tried PoverWR example of GPU matrix skinning POWERVR Insider MBX Chameleon Man Demo and it runs quite smoothly,... but it has only ~1000 skinned vertices in the mesh.


Guess poly-reducing the mesh and moving the calculation to another thread would help, though not  significantly (based on the results above) so I plan to do that (reduce complexity of scene) but also check Chameleon Man source code. Code is available as part of PowerVR Insider SDK and you would just need to register to get it.


Update on March 2nd after implementing GPU skinning: didn't spend time on reducing the scene - just after implemented GPU GLSL matrix skinning the results already look promising (on iPhone 3GS):

Scene	Skinned triangles	FPS with CPU skinning	FPS with GPU skinning
gles2farm - 1 animated character	5620	8	59
AppAnimKitGL - 5 animated characters	33700	1	22

Code is here.


Five animated characters scene looks like this:

In following post, I will try to explain how to implement matrix palette skinning (character skeleton animation using GPU).

CPU skinning is not the best choice for Opengl ES 2.0 devices.

CPU skinning is implemented like this: for every repaint, enumerate through all vertices, calculate and apply bone transformation. In more details, code bellow is an example of CPU skinning in AnimKit's  akGeometryDeformer::LBSkinningUniformScale. Apparently, on iPhone these matrix operations affect performance significantly and are better suited for vertex shader.

const btAlignedObjectArray<akMatrix4>& matrices = *mpalette;

for(unsigned int i=0; i<vtxCount; i++)

{

akMatrix4 mat(matrices[indices[0]] * weights[0]);

if (weights[1]) mat += matrices[indices[1]] * weights[1];

if (weights[2]) mat += matrices[indices[2]] * weights[2];

if (weights[3]) mat += matrices[indices[3]] * weights[3];

// position

*vtxDst = (mat * akVector4(*vtxSrc, 1.f)).getXYZ();

// normal

*normDst = (mat * akVector4(*normSrc, 0.0f)).getXYZ();

*normDst = normalize(*normDst);

akAdvancePointer(normSrc, normSrcStride);

akAdvancePointer(normDst, normDstStride);

akAdvancePointer(weights, weightsStride);

akAdvancePointer(indices, indicesStride);

akAdvancePointer(vtxSrc, vtxSrcStride);

akAdvancePointer(vtxDst, vtxDstStride);

}

Anyway, when bone transformation is applied and mesh vertices and normals updated, repaint is called after updating vertex buffer updating vertex buffer:

akSubMesh* sub = m_mesh->getSubMesh(i);

UTuint32 nv = sub->getVertexCount();

void *codata = sub->getSecondPosNoDataPtr();

UTuint32 datas = sub->getPosNoDataStride();

glBindBuffer(GL_ARRAY_BUFFER_ARB, m_posnoVertexVboIds[i]);

glBufferData(GL_ARRAY_BUFFER_ARB, nv*datas, NULL, GL_STREAM_DRAW);

glBufferSubData(GL_ARRAY_BUFFER_ARB, 0, nv*datas, codata);

This part also would get fixed by GPU skinning, since vertices only needs to be "uploaded" once in init() to vertex buffer, instead on every redraw:

            glBufferData(GL_ARRAY_BUFFER_ARB, nv*posnodatas, posnodata, GL_STATIC_DRAW)

Tutorial #1: Creating animated characters with Blender and rendering them with AnimKit on iOS

So far, I have been writing posts describing how I figured, ported or implemented something. I got a few questions about how to use the code, so I plan to write short tutorials from time to time.

First post is about my findings during creating animated mesh and getting it rendered on iPhone using Opengl ES 2.0 and AppAnimKit. Note that the code should work also on Nokia N9 (Harmattan MeeGo), Ubuntu, Mac OS X.

Here is the result of the steps described in the tutorial:

Here is what I did:

1) downloaded the mesh. 
I have downloaded this one from http://www.3dmodelfree.com/models/22496-4.htm#1. Note that there are many cute models available there, and also note that they are not for commercial use. I would like to credit the author, but the only thing I could find is that the model is uploaded 3 years ago. If someone knows more about the author of or if it is possible to get author name from 3ds file,… appreciate the help.
The columbine.3ds model contains a mesh, no armature and is not not animated. With ~ 100k vertices it was rather too complex to render on N9 and iPhone. I imported it to Blender from 3ds file.
The model I'm using is using vertex paint to render the model. Rendering using vertex groups is not yet implemented in AnimKit. UV texture works - if your model get's displayed white, you should pull the latest version - plan to push fix later this week.

2) polyreduce (and triangulate)
I find that Blender 2.49b polyreducer script works better then to apply Decimate modifier - which is the approach if using Blender 2.57. So, open mesh in Blender 2.49b, select it, go to Edit mode, select all vertices or only area you want to polyreduce, right mouse button to open menu, from Scripts submenu select Polyreducer. If using per vertex coloring (like I do in this case) disable "Interpolate vertex colors" as result would look fuzzy. I have applied the script several times and video above presents mesh with ~3000 vertices.

3) Smooth normals
While in Blender 2.49b select to Smooth normals. I'm typing this while commuting and don't know out of my head in which button area the toggle is. I could not find this option in Blender 2.57 and, if not set, AnimKit loader would spend noticeable amount of time on startup computing (smoothening) normals.

4) Create armature
Adding armature to mesh start by placing cursor to a dot inside or under the mesh where you want your topmost bone to appear. For this I returned to Blender 2.57. I use term topmost with the meaning "the parent of all other bones". Press space and select Armature. then extrude bones - there are multiple tutorials available about it. To extrude legs and arms use mirror extruding (Shift+E). With Blender 2.57 this option is hidden in Tools toolbar - go to Armature edit mode, open Tools toolbar (Ctrl+T) and check X Axis Mirror Editing. This enables Shift+E - otherwise Shift+E behaves like standard extruding (when pressing E).

5) Prepare bone influence before parenting armature to mesh
Show bones as envelopes and try to scale envelopes (bone effect area) to cover parts of mesh you wish them to affect. With current version of Animkit it is good not to leave mesh areas that are not under bone influence. I plan to open an issue/push patch about this once I get time to debug it. If later you see parts of the mesh stretched to the mesh centre, it is a sign you need to come back to this step.

6) parent the mesh to the armature. Select automatic weights. 

7) Start creating animation (create action)
Go to pose mode. Open one DopeSheet view and switch to Action Editor. Add an action. Make sure timeline cursor is on frame 1.

8) Add key 
rotate and translate tail bone to extreme position on the left. Press I to insert key.


9) Add one more key
move the time slider and position the tail as in initial position. Press I to add another key.


10) Add one more key
add symmetrical position to position in step 8). It is an extreme position with tail on right.


11) Finish animation editing (more keys)
copy 9) and 8) keys to get full cycle of tail going 8(left) -> 9(down) -> 10(right) -> (down) -> (left). After this I opened timeline view, set animation length to length of the cycle in 11) and could see animation rendered in Blender.

12) use file from C++ code.
I saved the file and changed the demo code from Blu.blend to use my mesh. Don't forget to add the file to build target (has to be in the bundle).

13) Contributing patch upstream (gamekit)
There were few minor issues as initially I could not see animation running. It was a nice experience to start collaboration with Ervin and Xavier from gamekit project - getting a minor fix for animation not playing in AnimKit upstream code: just opened an issue and attached the patch. Fix got in AnimKit soon after that. Few other related patches I plan to "pull" to https://github.com/astojilj/astojilj_animkit/tree/ios later this week, but the code there should already be OK.

Skeleton and pose character animation using AnimKit

Objective: How to implement pose and skeleton character animation in OpenGL ES 2.0?

I don't want to use gamekit with OGRE 1.8 rendering engine - need something lighter. Don't see this as "reinventing the wheel" - though there is nothing wrong with "reinventing the wheel" when it is fun, when you enjoy doing it. Hunter S. Thomson typed copies of Hemingway's books - he enjoyed doing it and he knew why he was doing it. I believe he wasn't having a feeling he would live for 1000 years - so, why not waste a bit of time... IMHO, doing this is the best/fastest way for me to learn and it is fun. Guess one could say that I could also type copy of Hunter S. Thomson articles, before continuing, to make this blog more fun to read.

Anyway, I think this is just what I need - gamekit's AnimKit. Briefly checked the code and run it on my desktop: it supports vertex (pose and morph) and skeleton animations, animation blending... inverse kinematics in the roadmap. Grepped for MATRIX_PALETTE - seems to have software (on CPU) animation implemented only. There is nice demo application AppAnimKitGL which looks quite promising. It is dependent on libGLU, libGLEW and libGLUT, and with fixed rendering pipeline. So, there is some effort needed to port it to iPhone and N9 - but I did this work in previous posts/examples so it should go faster now. Let's see. Plan to first focus on opengles 2.0.
...
Continuing:
Had some time during the weekend to check this. Here is how it looks on Nokia N9 running next to the AnimKit demo on Ubuntu:

Note that I did not port all of the demo helper features (bones, normal rendering, etc). Difference in texture color on N9 comes from using loaded BGR texture as RGB - if you plan to use the same code, you'll probably use different Blender model and different texture loader.
Code is available here: https://github.com/astojilj/astojilj_animkit/commit/df571339ab55d74681badf8c88cc468cedb3d372
To run it on Nokia N9, open Samples/AnimKitGL/AppAnimKitGl.pro with QtCreator and just build&deploy. If you intend to run original demo on desktop, note that you'll need to have Blu.blend in current directory.

Next thing I plan to do is add (copy from previous project) iPhone/iPad project support files.

...

iPhone version

Note that the fragment shader is different from N9 version - uncommented the code that is darkening the borders and doing the phong (giving the cartoon shading look).

Started from XCode, File->New Project->OpenGL ES Application (iPhone). After this, added all the sources to the project, replaced all "in project" project includes using <> with "" (e.g. #include "Mathematics.h") and added OPENGL_ES_2_0 to Preprocessor Macros item in Target Info dialog. Added also code to printout frames per second info.

This made the things compile, but when run I couldn't see anything rendered. Both use the same memory layout (little endian) so that wasn't a problem. Turned out that with 15000+ indices using glDrawElements with GL_UNSIGNED_INT indices doesn't work. GL_UNSIGNED_SHORT does.
Put a quick fix in the code with following comment:

// in iOS 4.1 simulator, glDrawElements(GL_TRIANGLES, cnt, GL_UNSIGNED_INT did not work - did not show anything on screen

// while GL_UNSIGNED_SHORT works. Using this as temporary workaround until trying with new sdk or anyway, change types

// in animkit code (no reason to use unsigned int anyway).

This got the scene rendered, and only thing left to do was to add depth buffer support (as default XCode SDK skeleton code doesn't have it on).

Code for the example running on iPhone (note that I was using iOS SDK 4.1 - yep, plan to update soon...) https://github.com/astojilj/astojilj_animkit/commit/5c11f660281bb8c8a6b5e3bba93938f703b6307c.  Few fixes added later here: https://github.com/astojilj/astojilj_animkit/commit/03545c7d1ea753c078aab4d441d4f12d91d462b8
Plan to merge it to master after verifying changes don't break anything on N9.

Next thing to try is scene with multiple actors with animated skeleton (I think I'll do cartoon animals) hardware (on GPU) matrix palette skeleton animation.

Collision detection for character - hit character falls down as rag-doll

Objective: how to implement collision detection for animated character? Character has bone system and it's position and movement is controlled by pose and animations but once it gets hit it needs to fall down like a rag-doll.

Get character model to ReadBlend: There is no code change needed for this part - if you have existing model with character, open project's blend file (PhysicsAnimationBakingDemo.blend) and use Blender's File->Append or Link command. Once you select blender file to "append" character model, select Objects and then selects meshes, armatures or constraints to import. I tried with this file and it worked - got the static character displayed in the demo. However, with ~300 triangles per each piece it was needed to reduce number of vertices not to let it affect frames per second count. If you hit an error "Error Not A Library" in Blender when appending, usually it is related to incompatible versions - open biped-rig blend file, save it (overwrite) and then try append from it again.  

Once I got biped_rig's character displayed next to the tree, it just didn't look nice. Decided to do my own made from boxes; it didn't take long to make head, spine, pelvis, upper and lower legs and arms, feet (and hands) from boxes used in the scene. When model is created, assuming all body pieces are marked as default "Static" (and not as "Rigid body") in Blender, character made of boxes gets displayed in the demo in standing position, not affected by gravity but with ball bouncing against it. If body parts would be marked as "Dynamic", ball would push them. So, for the character body parts, controlled by animation proper mode is Dynamic. Once the contact with bullet is detected, we will just "switch" them to be affected by gravity and they'll fall down.

Modeling joint constraints in Blender: to get "more realistic" rag-doll joint constraints, I need btConeTwistConstraint and btHingeConstraint and to set limits. Check the details for joint constraints example from Bulletphysics Ragdoll example code. I didn't set the limits in Blender 2.49, which you can tell from the demo bellow. When needed, constraints could be tweaked in C++ code (BulletBlendReaderNew::convertConstraints()). Anyway, just put joint constraints between body parts (this tutorial might help) to Blender file and they work also on phone.

Turn on the gravity for character body parts - when character is hit, it needs to fall down like a rag-doll: just after stepSimulation(), call processContactData() to check collision between ball and character:

void BulletBlendReaderNew::processContactData()
{
    //Assume world->stepSimulation or world->performDiscreteCollisionDetection has been called
    int numManifolds = m_destinationWorld->getDispatcher()->getNumManifolds();
    for (int i=0;i<numManifolds;i++)
    {
        btPersistentManifold* contactManifold =  m_destinationWorld->getDispatcher()->getManifoldByIndexInternal(i);
        btCollisionObject* obA = static_cast<btCollisionObject*>(contactManifold->getBody0());
        btCollisionObject* obB = static_cast<btCollisionObject*>(contactManifold->getBody1());


        int numContacts = contactManifold->getNumContacts();
        if (!numContacts)
            continue;


// check if one of colliding shapes is ball
        if (obA != ball && obB != ball)
            continue;


// this is simplified check if another collision shape is part of character's armature
        if (obA->getCollisionShape()->getUserPointer() == &(this->armature)
                || obB->getCollisionShape()->getUserPointer() == &(this->armature))
        {
            // convert armature -> ragdoll in case ball hits character
            turnToRagdoll(&(this->armature));
        }
    }
}


void BulletBlendReaderNew::turnToRagdoll(ArmNode *nodeList)
{
    ArmNode *next = nodeList;
    while(next) {
        if (next->piece)
            ((btRigidBody*)next->piece)->setAngularFactor(1.f);
        next = next->nextSibling;
    }
}

Note that all the body parts' meshes are marked as "Dynamic" in Blender's Logic panel (F4). Dynamic bodies have setAngularFactor set in ReadBlend set to 0.f initially in BulletBlendReaderNew::createBulletObject().

In case of complex sophisticated character meshes, it makes sense to use the same technique, and not only on constrained systems (like iPhone and N9) - don't add complete mesh to physics world for collision and gravity simulation, but create "shadow" model out of boxes only for physics and collision. Then, when rendering rigged mesh, use motionState to get location (transformation) of each box (bone in simplified armature in physics simulation world) and then apply transformation to complex rigged character's bones when rendering it. Simple physics model would not be rendered, it would just exist in physics world.

Tree collision demo - getting the texture and color to N9

I didn't use textures from demo http://opengles20study.blogspot.com/2011/01/cel-shading-toon-shading-silhouette-how.html after porting to N9: http://opengles20study.blogspot.com/2011/08/meego.html
To get the textures work if using jpeg library (if not using iPhone SDK to generate images - code under #ifdef USE_IPHONE_SDK_JPEGLIB) it is needed to change m_pixelColorComponents from GL_RGBA to GL_RGB here.
It seemed like a good idea not to texture the tree, but to supply color via uniform value when rendering the  tree per instance. I plan to check how the tree looks with very few leaves and for that ngPlant leaves group probably would be better to use textures (billboards). For example about how to use uniform color value in shader, just grep the code for u_Color - there are several available.
This is how it looks on N9 - sorry for the poor video quality.

Tree branches collision detection

I showed the example from previous post to cousin Miša and explained how I plan to add physics and collision detection for each branch and leaf of the tree; he noticed that the tree looks quite complex (several thousands vertices) and asked how much CPU that could consume, and how much it could affect performance and lower frames per second count...
In short, this is what the post, code examples and demo is about. There is another thing that could be interesting, animating camera position from behind the ball to the position orthogonal to ball direction while the ball is moving - not stopping or slowing down the simulation like in previous posts.

Have to apologize for the not so good quality of videos I made; I'll try to compensate it with detailed explanation and code examples about how to use related ngPlant and bulletphysics API.

The video above shows a heavy ball rolling down the hill to hit the tree, bounce back and hit low hanging tree branch.
Another video shows a rather heavy ball rolling down the hill, hitting the tree,... after it rolls away from the tree btRigidBody::applyCentralImpulse() is "applied" throwing the ball back to the tree. After it bounces back several times and get thrown again, eventually ball gets stuck between the branches of the tree.

This is simplified version of the code throwing the ball from the ground to the tree - impulse with angle of 45 degrees (500 horizontally and  500 vertically):

Vec3 vToTree;
MatrixVec3Normalize(vToTree, vTarget - vFrom); // vTarget is tree,
// vFrom is current ball position
((btRigidBody*)ball)->applyCentralImpulse(btVector3(0.,0.,500.) + 500. * btVector3(vToTree.x, vToTree.y, vToTree.z));


Camera animation while simulation is running - from behind the ball to orthogonal to ball rolling direction

For this, I'm using TransformInterpolator class designed in previous post about camera movement animation - start point in transform interpolation is defined as camera behind the ball:


MATRIX mTransformStart;
// take vFrom as previous position and vTarget as current, or in this case it is tree position
modelTransformWithCameraBehindTheBall(mTransformStart, vFrom, vTarget);
cameraAnimation = new TransformInterpolator(mTransformStart, mTransform, 75);


End point in camera animation (mTransform) is camera transformation to look at ball orthogonal to direction of ball movement, calculated as in this example:


Vec3 vBallDirection = vTarget - vBall;
Vec3 vViewDirection, vDirection;
// camera position on vector vViewDirection from the ball:
// it needs to be orthogonal to both ball movement direction (vBallDirection) and "up" vector z
// as in example coordinate system z means up.
MatrixVec3CrossProduct(vViewDirection, vBallDirection, Vec3(0,0,1));

MatrixVec3Normalize(vDirection, vViewDirection);
// center of the view would be between ball and the tree
Vec3 vTo = vBall + vBallDirection/ 2;

// we take some distance from "center of the view" - a point that lies on vector vViewDirection
// looking at vTo is then nice landscape view, orthogonal to "up" and ball direction.
MatrixLookAtRH(mTransform, vTo + 3.f * CameraDistanceFromBall * vDirection, vTo, Vec3(0,0,1));


It is important to update cameraAnimation endPoing after each dynamicsWorld->stepSimulation(); as the ball advances to the tree camera needs to follow - after animation is finished, camera will just follow the ball movement. Since the target is the tree, this would give a nice side view of ball hitting and bouncing of the tree, as on both videos above.

Physics (collision) for tree and all tree branches

ngPlant and bulletphysics btIndexedMesh and btTriangleMesh APIs fit together; I'm using:


void P3DHLIPlantInstance::FillVAttrBuffersI( const P3DHLIVAttrBuffers *VAttrBuffers, unsigned int GroupIndex) const

to load vertices, used to render the tree and for physics btIndexedMesh::m_vertexBase.


void P3DHLIPlantTemplate::FillIndexBuffer
(void *IndexBuffer,
unsigned int GroupIndex,
unsigned int PrimitiveType,
unsigned int ElementType,
unsigned int IndexBase) const

to load index of vertices in triangles, used to render the tree and for physics btIndexedMesh::m_triangleIndexBase

This is a code used to add mesh for a tree to btDynamicsWorld.


btVector3 scale(object->size.x,object->size.y,object->size.z);
btTransform worldTrans;
worldTrans.setIdentity();
worldTrans.setOrigin(btVector3(object->loc.x,object->loc.y,object->loc.z));
worldTrans.getBasis().setEulerZYX(object->rot.x,object->rot.y,object->rot.z);


btTriangleMesh* meshInterface = new btTriangleMesh();
// for now, modeling this way trees in blender - a mash with name OBplant_
if (!strncmp(object->id.name, "OBplant_", 6)) {

// get the plant data
PlantGraphicsObject *plant = (PlantGraphicsObject *)createGraphicsObject(object, 0);

// fill the mesh bullet interface with plant branch layer data
for (int i = 0; i < plant->plantData().branchLevels.size(); i++) { 
    btIndexedMesh mesh; 
    const PlantObjectData::BranchLevel &levelData(plant->plantData().branchLevels.at(i));
    mesh.m_numTriangles = levelData.IndexCount / 3;
    mesh.m_triangleIndexBase = (const unsigned char *)levelData.IndexBuffer;
    mesh.m_triangleIndexStride = 3 * sizeof(unsigned int);
    mesh.m_numVertices = levelData.vertexCount;
    mesh.m_vertexBase = (const unsigned char *)levelData.PosBuffer;
    mesh.m_vertexStride = sizeof(float) * 3;
    meshInterface->addIndexedMesh(mesh);
}

// create convex collision object based on mesh bullet interface
btCollisionShape* colShape = 0;
btBvhTriangleMeshShape* childShape = new btBvhTriangleMeshShape(meshInterface, true);

if (scale[0]!=1. || scale[1]!=1. || scale[2]!=1.) {
// I have scaled down the mesh in blender as it was too big
    colShape = new btScaledBvhTriangleMeshShape(childShape,scale);
} else {     
    colShape = childShape;
}

btVector3 inertia(0,0,0);
btRigidBody* colObj = new btRigidBody(0.f,0,colShape,inertia);
colObj->setWorldTransform(worldTrans);

// references ...
colObj->setCollisionShape(colShape);
plant->setCollisionObject(colObj);
colObj->setUserPointer(plant);

// add the physics object to the world
m_destinationWorld->addRigidBody(colObj);


N9

I'm very proud I was part of N9 team for last three years. The device is out. It is beautiful piece of hardware with amazing screen.

I'll start using it as development device for this thing I'm learning here. Here is the demo from the last post, with 2 ngPlant trees, running on N9.

Next thing I'm planning to do is to add collision for all of the branches in ngPlant tree to PlayBlends' btDiscreteDynamicsWorld - let's say simulating a ball hitting a branch, then bouncing from one to another until it fells down to ground ... or micro airplane flying through treetop ... anyway, just would like to see how it performs and what are the constraints. Rendering ngPlant tree seems quite OK - uploading vertex and index data to GPU buffers for rendering:

        glBindBuffer(GL_ARRAY_BUFFER,...);
        glBufferData(GL_ARRAY_BUFFER, ... GL_STATIC_DRAW);

....

        Piper::instance()->glDrawElements(GL_TRIANGLES....

Note that ngPlant doesn't yet support exporting mash data as triangle strips. The documentation states it is planned for next versions.
For tree branches collision detection, I'll start by reading Real Time Collision Detection and check btBvhTriangleMeshShape.