Jump to content

  • Log In with Google      Sign In   
  • Create Account

Irlan Robson

Member Since 08 May 2012
Offline Last Active Yesterday, 05:45 PM

#5254131 Learning GameStates

Posted by Irlan Robson on 26 September 2015 - 07:03 AM

werdy666, what L. Spiro said is correct, I can't think of a more elegant way of managing the game states.


In the case you need help, here follows a simple implementation of a state machine class that allows you to switch between game states at run-time. It was based on L. Spiro articles and I'm still using it today to create demos and testbeds:




Study the CGame, CState, and the CStateFactory classes. Also, make sure you delay the game-state switch in the game. Otherwise you'll be walking on invalid memory lands.

#5253795 WinAPI - Decoupling and abstracting input from window

Posted by Irlan Robson on 24 September 2015 - 05:11 AM

Maybe this is helpfull after you have been familiar with what is on the link that SmkViper posted:



But basically you have input mapping and input re-mapping. The first one maps the raw inputs into the engine inputs and the second maps engine inputs to game inputs.

Hope it helps.

#5253378 Organizing Game Logic

Posted by Irlan Robson on 21 September 2015 - 07:46 PM

If I couldn't porsue a scripiting system I would definately implement the game logic in a game state and switch between game states. In this sense, the game logic data would live inside a specific game state. By the other hand, persistent data would obviously live inside the game class. 


In the most basic form, the engine would manage the graphics, and low level stuff, and the game itself other things such physics, AI, monetization, etc.

#5252536 Bounce Update

Posted by Irlan Robson on 16 September 2015 - 10:55 AM

Good afternoon everyone.

I added spherical, revolute, and mouse joints to Bounce, a physics engine which you can use in your personal projects:


Any kind of advice or contribution is well appreciated! Thanks...

#5247874 Problem Implementing Separating Axis Theorem

Posted by Irlan Robson on 20 August 2015 - 08:01 AM

d07RiV is correct.


I would instead keep a 3x3 rotation matrix inside the transform class and rotate the normals using it. This is much more faster and you don't need to normalize the normals (in both ways).


Test a box-box collision since it is easy to inspect the face and edge normals.

#5247738 Problem Implementing Separating Axis Theorem

Posted by Irlan Robson on 19 August 2015 - 02:33 PM

This is an old  brute-force SAT:

                float fMin;
                float fMax;
                bool Overlap(const PROJECTION& _pOther) const {
                        return !(fMax < _pOther.fMin || _pOther.fMax < fMin);
bool CSat::TestFaces(const CShapeInstance* _psiShape0, const CShapeInstance* _psiShape1) const {
        const CConvexPolyhedron* pcpConvex0 = static_cast<const CConvexPolyhedron*>(_psiShape0->m_psShape);
        const CConvexPolyhedron* pcpConvex1 = static_cast<const CConvexPolyhedron*>(_psiShape1->m_psShape);
        for (unsigned int I = 0; I < pcpConvex0->m_ui32TotalFaces; ++I) {
                CVector3 vAxis = _psiShape0->m_mTransform.Rotation() * pcpConvex0->m_pvFaces[I];
                PROJECTION pProj0;
                PROJECTION pProj1;
                Project(pcpConvex0, _psiShape0->m_mTransform, vAxis, pProj0);
                Project(pcpConvex1, _psiShape1->m_mTransform, vAxis, pProj1);
                if (!pProj0.Overlap(pProj1)) {
                        return false;
        return true;
void CSat::Project(const CConvexPolyhedron* _pcpHull, const CMatrix4x4& _mTransform, const CVector3& _vAxis, PROJECTION& _pProj) const {
        _pProj.fMin = _pProj.fMax = _vAxis.Dot(_mTransform * _pcpHull->m_pvVerts[0]);
        for (unsigned int I = 1; I < _pcpHull->m_ui32TotalVerts; ++I) {
                float fProj = _vAxis.Dot(_mTransform * _pcpHull->m_pvVerts[I]);
                if (fProj < _pProj.fMin) {
                        _pProj.fMin = fProj;
                if (fProj > _pProj.fMax) {
                        _pProj.fMax = fProj;
bool CSat::TestEdges(const CShapeInstance* _psiShape0, const CShapeInstance* _psiShape1) const {
        const CConvexPolyhedron* pcpConvex0 = static_cast<const CConvexPolyhedron*>(_psiShape0->m_psShape);
        const CConvexPolyhedron* pcpConvex1 = static_cast<const CConvexPolyhedron*>(_psiShape1->m_psShape);
        for (unsigned int I = 0; I < pcpConvex0->m_ui32TotalEdges; ++I) {
                CVector3 vAxis0 = _psiShape0->m_mTransform.Rotation() * pcpConvex0->m_pvEdges[I].vNormal;
                for (unsigned int J = 0; J < pcpConvex1->m_ui32TotalEdges; ++J) {
                        CVector3 vAxis1 = _psiShape1->m_mTransform.Rotation() * pcpConvex1->m_pvEdges[J].vNormal;
                        CVector3 vAxis = vAxis0.Cross(vAxis1);
                        PROJECTION pProj0;
                        PROJECTION pProj1;
                        Project(pcpConvex0, _psiShape0->m_mTransform, vAxis, pProj0);
                        Project(pcpConvex1, _psiShape1->m_mTransform, vAxis, pProj1);
                        if (!pProj0.Overlap(pProj1)) {
                                return false;
        return true;
bool CSat::Intersect(const CShapeInstance* _psiShape0, const CShapeInstance* _psiShape1) {
       if ( !TestFaces(_psiShape0, _psiShape1) ) {
                return false;
        if ( !TestFaces( _psiShape1, _psiShape0 ) ) {
                return false;
        if ( !TestEdges( _psiShape0, _psiShape1 ) ) {
                return false;
        return true;

This thread discusses different issues with SAT as well optimizations in order to put in production:



#5244957 Box stacking

Posted by Irlan Robson on 07 August 2015 - 09:44 AM

If you're talking about convergence then the boxes shoudn't fall. 

#5244804 Box stacking

Posted by Irlan Robson on 06 August 2015 - 06:40 AM

Each contact point holds the normal and tangential impulses;
Before a manifold generation, make a copy of the old manifold;
If there is a match between the manifold contact points then copy the normal impulse and project the old manifold tangential impulses on the new tangential directions;
Apply the old impulses one time (that is, warm-start the solver);
Apply new impulses for how many iterations you want updating the accumulated impulses during the iterations;

Basically, thats all needed.

Test your colllision detection routine separately for a box pair drawing the contact points and normal persistently.

#5242722 collision detection in games and physics engine 3d

Posted by Irlan Robson on 25 July 2015 - 09:42 PM


This depends of the game requirements. Some games has very specifics collision detection routines; some are made of OBBs, other of a sphere and a box, e etc. In this case these problems can be solved by only using a OBB-OBB test or a simply capsule-capsule for instance. Using this loss of generality you have the positive side that is fast intersection routines. Read Christer Ericsons orange book.

Recent games needs to support basically any kind of shape, and like you said, convex polyhedras are being used in recent game physics simulations.

The most commom algorithms are the SAT and the GJK.

The image you showed is a convex version of a concave mesh. It is generally transformed in convex using the QuickHull algorithm.

SAT is slightly slower but (in my experience) is numerically stable. This is because when using GJK you usually need to use EPA to get the minimum separation distance between the objects, which leads to numerical errors.

See this thread


Dirk has described the SAT algorithm in details.

#5242459 Bounce v1.0 Release

Posted by Irlan Robson on 24 July 2015 - 12:51 PM

Good afternoon everyone.

I'm happy to distribute Bounce, a lightweight and portable 3D physics engine for games. 

Bounc3 is available at GitHub. 


Some of the physics engine features can be seen at the basic (.pdf) documentation, living inside the repository. Additionaly, a demo application lives inside the repository as well.



Irlan R.

#5240338 3D SAT Problem

Posted by Irlan Robson on 14 July 2015 - 03:54 PM

I'll share here my solution based on the previous recommendations.
Let's see the image below. Let the reference polygon be the box 1 and the incident the box 2. The incident polygon is CW (from the normal POV), and CCW from the current view (as in the figure).
All edges of the reference face side planes are the half-edge IDs. Then, this is how the vertices should be filled in on the Sutherland-Hodgman clipping:
'1' is the reference face and '2' is the incident face (as the image).
// Build faces (keep plane IDs...
// Build incident polygon:
// The incoming edge of each polygon point is the current half-edge id, and the outcoming is the next half-edge of the current one.
if ( v1 is behind and v2 is in front ) {
//intersection point ip
ip.inEdge1 = null;
ip.inEdge2 = v1.outEdge2;
ip.outEdge1 = planeEdge;
ip.outEdge2 = null;
else if ( v2 is behind and v1 is in front ) {
//intersection point ip and v2
ip.inEdge1 = planeEdge;
ip.inEdge2 = null;
ip.outEdge1 = null;
ip.outEdge2 = v2.outEdge2;
// Flip if needed
I've looped through all contact IDs and they're unique and they're matching. A stack of 10 boxes with density 0.2km^3 (2x2x2m) bounces a little bit initially but stabilizes after ~6s, using 10 iterations and warm-starting. Is this a common behaviour? Do you guys have a video or a description of a simple cenario so I can compare with mine?

#5239341 Collision detection and response

Posted by Irlan Robson on 09 July 2015 - 03:00 PM

I don't know what are "subdivided convex hulls", but do you mean that your physics objects are always approximations?


smaller convex sets -> better mesh approximation -> better collision culling -> less instructions

#5239216 Collision detection and response

Posted by Irlan Robson on 09 July 2015 - 07:59 AM

Sorry if I misunderstood your question, but are you asking what is the standard way of running collision detection on objects in a game?


Are you talking about collision detection in physics simulations or general computer graphics applications?



Generally, the polygons you render aren't the polygons that are used to represent solid objects (rigid bodies). In a game, a triangle soup is generally represented by a convex polyhedras (AKA convex hulls/sets) due to the bad performance that mesh-mesh intersection tests have. However, hull-hull intersection tests do still a little bit slower. For instance, running a sphere-sphere test is 90% faster than a hull-hull test. Therefore, objects with well-know simmetry such cubes, spheres, cylinders, etc. has its own intersection routines to increase the performance of the collision detection system.


My question is if that's a legit approach, and if that issue has ever been brought up for discussion.
Particularly, for a rigid body physics simulation in a game, this is the legit approach. However, it is definately not the standard approach for more serious applications such CAD, medical training, 3D modelling, etc.

Now the obvious approach I thought of for dealing with physics is to store the vertices and indices of every entity (and perhaps normals too, to reduces some calculations), and then feed the Physics::calc_collision_with_triangle() routine with the each entity's triangles, based on the indices.
...or you can abstract everything and separate physics from graphics. 

#5234622 stable constraint solver with no warmstarting

Posted by Irlan Robson on 13 June 2015 - 11:48 AM

Hi people!

Short story, I was trying to understand how physics engine work, and proceeded to code a simple 3d physics engine based on a very nice presentation from erin catto. I took a peek inside box2d-lite source code and implemented my 3d version. It works, I got boxes colliding and stacking nicely (wiggle a bit at start, but converge into a stable configuration quickly).
Now as I understand it, box2d-lite used iterative solver. This kind of solver gives a quite-close-to-correct solution in every iteration, based on the answer of previous iteration. That makes the "warmstarting" very essential. In fact, without it, the solver would be "wrong". The thing is, keeping a list of arbiters for every pair of touching bodies is quite a lot of work. Are there any other physics engine schemes that don't need "warmstarting" but very stable and simple enough to implement? I don't want to have to do the housekeeping of records of touching bodies. I simply want to do it the "sweep, prune, solve and forget" kind of style.
Do you know any tutorial/articles that might be useful? Or maybe a source code to take a look at? Thank you!


Box2D uses Projected-Gauss-Seidel (PGS) to satisfy velocity constraints subject to mixed complementarity conditions (MLCP) (a general complementarity problem for collision and contact, and the mixed part for friction (motor joint) ). The Gauss-Seidel part is for solving a simple generalized linear equation, and the Projected essentially is just a clamping procedure on the impulse magnitudes.


Generally you find the PGS algorithm for a generalized system, so it is not completely explicit by the sequential impulses technique at first. Iterative solutions (iterative numerical methods and solvers) algorithms are used in interactive applications. Global solutions such Baraff's techniques are generally used in real-time ones or even discarded.


If you want to understand how really this works I recommend all Baraff papers (89-2000), and Kenny Erleben thesis (2004), as well Florian and Potra papers.


The sequential impulses is a specialization of the PGS algorithm. It will search for corrective impulses that will satisfy the constraints. In the sense of being an iterative solver the PGS algorithm uses an initial guess for the lambdas. So, for contacts, you need a way of matching contact points between frames. This depends of the discrete collision detection scheme that you have. Iterative algorithms (GJK, MPR) generally are distance algorithms, so you get only two points in every geometry (and you also need to adjust to work for penetrating cases). This way you need to match new and old points using some criteria such the contact area projected on the gravity direction and the points distances. However, this is not 100% correct. Using SAT you can use contact point IDs (as mentioned), then, it is definately a better solution. 


The sweep-prune-solve and forget requires a lot of tunning. Specifically with the discrete collision detection scheme.


At the end, you should have something like this for a simple physics engine:


Dynamic AABB Tree;


Semi-implicit Euler for integration;

Contact/Joint Graph;


For the SAT, read http://www.gamedev.net/topic/667499-3d-sat-problem/. Dirk answered a lot of questions excellently (all credits to him).

#5227609 Physics engine for a simracing game. Where to begin?

Posted by Irlan Robson on 06 May 2015 - 06:14 PM

I've been reading the "Game Physics Engine Development by Ian Millington" book as I've been recommended to (not ended yet) but still quite lost about how to start with the development, don't really know where to begin...


This book is a good introduction, but is outdated. Forget about it.


I recommend all Erin Catto GDC slides, here: https://code.google.com/p/box2d/downloads/list. All slides on this website are pure gold, so do the references.


Take a look into sequential impulses LCP solver.


The most basic dynamics simulation should have rigid bodies and ball-socket joints.


You will also need collision detection, which increases exponentially the time needed to create an physics engine.


Creating a physics engine from scratch without a solid math background such vector calculus is hard. Especifically, to learn about constrained dynamics, which naturally comes from the robotics/mechanics literature. But is not impossible. Is actually a very good experience, IMHO.