Monthly Archives: April 2012

Collision Detection Progress – 2

Am Currently still in phase 1 of implementing Collision Detection in my game engine – JustAnotherGameEngine.

Things marked have been done –

  • Design Collision Manager that will be handling all collision related stuff.
  • CD (Collision Detection) of AABB with Polygons (triangles making up objects in current scene , yes there are no simple primitives).
  • Sphere & Ellipsoid with Polygons.
  • Registration & CD of Static Objects
  • Registration & CD of Dynamic Objects (Moving objects like bullet etc)
  • Registration & CD of Height map Terrains (avoiding registration of whole terrain mesh if possible because that’s going to take allot of memory and unnecessary CPU time )
  • Update Player FPS Controller and Implement Response phase.
  • Registration of Static Hierarchal meshes loaded from 3ds Max as Static Objects.
  • Registration & CD of Models with animation loaded from 3ds Max (e.g. Walking character , etc).
  • Map Editor with collision detection support for making simple levels.
  • Or Implement the support for Loading Levels from 3ds Max and register it with Collision detection System and also make a provision to place some simple entities in 3ds Max and recognize it in engine while loading.
  • Make the whole Collision Detection System and Response phase of Player \ Character Independent of Default Co-ordinate Axes. (I will explain it later but it’s like using OABB instead of AABB. But thing am trying to do is beyond that and I can’t explain it without screenshots etc)

So i have completed the system for making Collision Detection and Response of Character Controller Independent of Default Coordinate Axes.

First let me explain what i actually mean in above line. Normally when we implement a Character Controller (Whether FPS, TPS ,etc) we choose direction of gravity mostly along one of the principal axes (-Y in my engine) and assume that it won’t change. Which in turn also fixes the Player’s UP axis (+Y in this case). This assumption greatly simplifies the process of writing the character controller. For let’s make one more assumption that length of character model is equal to its length (width = length) so its a circle on XZ plane. So that rotation of player about Y axis doesn’t matter. So we now can represent player as an AABB which will later easily converted to ellipsoid in detection phase.

Using above assumptions and using an ellipsoid for player’s collision detection, ellipsoid can easily be calculated once at loading time by determining length, width and height of Character Model. So our problem becomes the problem of collision detection of moving Ellipsoid and it’s response.

There are plenty of examples on the internet how to use ellipsoids for collision detection e.g. –

So using this method to make a character controller walking on a terrain here are the steps (its just a brief idea of how things work not a in depth description) for Collision Detection & Response –

  • Calculate Ellipsoid once from AABB at loading setup.
  • Send Ellipsoid and its current position in Collision Detection Phase. (Refer to links mentioned above on how to implement this phase)
  • Retrieve the final position & velocity of Ellipsoid and list of contact points as returned by the Detection Phase.
  • Compare the Y value of contact point if its smaller than a threshold value character / ellipsoid can slide over it else it’s velocity will be reflected to new direction as returned by response phase.
  • Also Camera system can be easily implemented.

This process is good enough for almost all games we make nowadays whether a First Person shooter, Third Person, Plat former, etc.

But i had an idea in my mind what if we can change the direction of gravity in real-time ? Also i wanted to overcome the drawbacks of above method (or eliminate all those assumptions mentioned above) –

  • Gravity can be along any arbitrary direction (e.g. (3,8,10), (5,7,1), etc instead of (0,-1,0))
  • We should be able to change direction of gravity at runtime.
  • Character can have different values for length, width or height.
  • Response phase should also be independent of principal axes and player should be able to walk over terrain at any orientation (given if gravity is normal to terrain).

So all the goals add a whole new level of complexity in Collision Detection and Response and some problems too. Here’s an idea of added complexity and extra work involved in steps discussed earlier –

  • We have to use OABB instead of AABB which will be calculated every frame. As a result ellipsoid have to be calculated every frame.
  • We can no longer use tricks to simplify calculations which assumed UP axis is always Y axis, increasing complexity and computing power required.
  • In detection phase we can no longer squeeze the world with ellipsoid to make it a sphere to make calculations easier. This is because ellipsoid is no longer aligned to principal axes.
  • In response phase we can no longer just compare Y values on contact points to determine if we can slide over object or not. We either have to
  • Increased complexity.
  • Increased compute power required for Collision Detection & Response.

Also not to mention there will be considerable changes in Camera System also –

  • We can’t use principle axis as X,Y,Z for Camera.
  • There’s no Fixed Up or +Y axis to normalize right and look vector.
  • I had to re – implement all types of cameras – First Person, Third person, Over the Shoulder, Free Look, etc in way that it’s no longer depends of principal axis instead depends on Character’s orientation.

(Note – I will try to post camera system in detail in a different blog post in future.)

So Is it worth it to do this extra effort and to make something that’s not only more complex but slower also ?

For me it was a good exercise for 3D Math and as a preparation step for some game play idea clicked to my mind .

Well I know these things can be explained better by a demo video but i don’t want post a video with boxes, wireframe, etc. So I am planning to make a tech demo later on after completing phase 1 of my collision system with some decent graphics and models. Some sort of a mini game or a game concept video. But for that am also working on a new model loading and animation system, loading scenes from 3Ds Max and bunch of other things.

So till then here are some screenshots –

1) Gravity along -Y Axes

2) Edit Mode – Changing Terrain Orientation and setting gravity direction as normal to terrain plane so its no longer -Y Axes

3) Resuming Game after Making changes to terrain and gravity.

Advertisements

Collision Detection Progress

Am Currently in phase 1 of implementing Collision Detection in my game engine – JustAnotherGameEngine.

Things marked have been done –

  • Design Collision Manager that will be handling all collision related stuff.
  • CD (Collision Detection) of AABB with Polygons (triangles making up objects in current scene , yes there are no simple primitives).
  • Sphere & Ellipsoid with Polygons.
  • Registration & CD of Static Objects
  • Registration & CD of Dynamic Objects (Moving objects like bullet etc)
  • Registration & CD of Height map Terrains (avoiding registration of whole terrain mesh if possible because that’s going to take allot of memory and unnecessary CPU time )
  • Update Player FPS Controller and Implement Response phase.
  • Registration of Static Hierarchal meshes loaded from 3ds Max as Static Objects.
  • Registration & CD of Models with animation loaded from 3ds Max (e.g. Walking character , etc).
  • Map Editor with collision detection support for making simple levels.
  • Or Implement the support for Loading Levels from 3ds Max and register it with Collision detection System and also make a provision to place some simple entities in 3ds Max and recognize it in engine while loading.
  • Make the whole Collision Detection System and Response phase of Player Independent of Default Co-ordinate Axes. (I will explain it later but it’s like using OABB instead of AABB. But thing am trying to do is beyond that and I can’t explain it without screenshots etc)

Here’s the way things work now, During Scene Initialization all the objects are registered with Collision Detection as static or dynamic objects passing the mesh data to build polygons in Collision Manager Database. Later on when we need to move a dynamic object say the player object it will call just one function passing in its current position and new position, Collision Manager then uses its Triangle database created at loading time to check player object against all the objects / triangles in the scene (remember there’s no high level optimization technique planned in phase 1).

For Terrains there’s separate system to register and check collision detection. If we use the same system like static Objects and pass terrain meshes to Collision Manager then allot of memory will be wasted and also number of triangles to be processed will increase. To avoid this we will only generate terrain mesh around player position and check collision against it. This mesh will be generated every frame using height map.

Here’s a screen shot of player object with terrain (having > 2 Million polygons). As you can see am getting 108 fps. If i have registered this terrain as static mesh to the collision system it would have processed all 2M triangles which would have taken ages and obviously not practical for any purpose. Instead what am doing here is am generating a part of terrain mesh surrounding the players position inside the collision system every frame with the help of height map data. Blur Colored Triangles are the ones generated inside collision system for detection in this frame. And player object collides with the triangle shown red.

(Terrain size 1025 x 1025)

(Note –¬†terrain is being rendered without any optimization technique e.g. ¬†frustum culling, occlusion culling etc. So all vertices and triangles are being passed to draw call)

(Same terrain with Frustum Culling on. Notice the Number of Vertices and Triangles being passed to Draw Call)

 

 

 

Collision Detection System

In last post I have already talked about why i wanted to make proper collision detection system and also said I will be posting progress and what things i want to implement so here it is –

Basically I want to implement the whole collision detecting system involving primitives, mesh colliders etc together with broad phase optimization techniques. So i don’t have to worry about collision detection ever again. Also i want to utilize knowledge gained in the process and apply it to the rendering and finally implement the things i wanted from a long time like Scene Graph, Occlusion Culling, Portals systems, etc.

I have divided the things into 2 phases –

Phase 1

In this phase player or object in consideration will either be a AABB, Cube, Sphere or Ellipsoid. And we will be using polygons/ triangles making up the objects for collision also and not simple primitive objects. Goals for this phase –

  • Design Collision Manager that will be handling all collision related stuff.
  • CD (Collision Detection) of AABB with Polygons (triangles making up objects in current scene , yes there are no simple primitives).
  • Sphere & Ellipsoid with Polygons.
  • Registration & CD of Static Objects
  • Registration & CD of Dynamic Objects (Moving objects like bullet etc)
  • Registration & CD of Height map Terrains (avoiding registration of whole terrain mesh if possible because that’s going to take allot of memory and unnecessary CPU time )
  • Registration of Static Hierarchal meshes loaded from 3ds Max as Static Objects.
  • Registration & CD of Models with animation loaded from 3ds Max (e.g. Walking character , etc).
  • Update Player FPS Controller and Implement Response phase.
  • Map Editor with collision detection support for making simple levels.
  • Or Implement the support for Loading Levels from 3ds Max and register it with Collision detection System and also make a provision to place some simple entities in 3ds Max and recognize it in engine while loading.
  • Make the whole Collision Detection System and Response phase of Player Independent of Default Co-ordinate Axes. (I will explain it later but it’s like using OABB instead of AABB. But thing am trying to do is beyond that and I can’t explain it without screenshots etc)

Phase 2

  • Implement primitives (Cylinders) to speed up Collision Detection allowing us to avoid Mesh Collider implemented in Phase 1 whenever we can. (Mesh collider can be used easily with every object but it’s quite heavy on the processing side. Also arguably its the most involved one.)
  • Implement High Level or Broad Phase Optimization techniques like KD Trees, Oct Trees, BSP, etc
  • Use the tools and knowledge gathered in Collision Detection and Apply it to Rendering also.

Phase 3

  • Convex Hulls
  • Collision Detection on GPU (using general techniques and maybe using CUDA also).

Phase 3 is not really planned but am looking forward to do it. But I think it will not be soon because I would like to implement other things first like Physics. There’s no point of fancy Collision Detection System without a good Physics System with rigid body physics at least. There are other things I would like to do before that like a more robust Scene Manager with Portals, Occlusion Culling etc. All these techniques are related with Collision Detection.