Category Archives: Collision Detection

Spatial Partitioning

Implementing Polygon level collision detection was fun and quite useful. I have implemented the system for static objects, dynamic objects, skinned characters and terrain. So even though collision detection is done it’s not ready for full game scene having 1 million polygons or more. The main reason is the performance if we use this system as it as for big levels without any High level optimizations we can’t get playable frame rates because CPU’s are still not powerful enough to do that and will never be. Because as the CPU or GPU horsepower increases people would demand larger and more realistic  looking worlds that means more polygons means more horsepower required to manage that. So we have to implement high level optimizations and we should try to rule out insignificant calculations as early as possible. Because check your character against all 1 million polygons or so every frame doesn’t make sense.

So next that’s where Spatial Partitioning comes into use. As name describes itself Spatial Partitioning algorithms divides the game level spatially into different areas or chunks depending on particular algorithm being used.  So every frame we can only test our character against objects / polygons in that particular area.

Not only collision detection same spatial partitioning algorithms can be used for speeding up rendering also. We have already divided space into smaller chunks / areas so sometimes we can get away only rendering that particular area. For example a scene consisting of 100 rooms and we are in room 50 then we just have to render that particular room and objects in it ignoring  all other rooms and objects in them. So that saves a lot of GPU power send in rendering other 99 rooms which user can’t even see (ignoring things like windows etc to make example simpler).

So this was an extreme example I gave but in many cases the amount of boost we get rendering and collision detection is comparable to example above.

Also I just gave you once example in the area of rendering deciding visibility or object but this can help in many other areas like LOD, Animation LOD and much more.

Hierarchical Partitioning

So by spatial partitioning we mean diving scene in cells (rows and columns etc) so we can just reject whole area / chunk of level at once from rendering or collision detection instead of going to each game object or polygon and checking if its visible or colliding.

Well this process can still be speeded up further much more by making the spatial partitioning hierarchical. So for example we can sometimes reject the 50% of the scene in single bounding volume check which is a major speed boost.

So here are some popular Hierarchical partitioning algorithms –

  • Quad Tree : A Quad Tree is a tree data structure in which each internal node has exactly four children. Quad Trees are most often used to partition a 2D / 3D space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. But for games shapes are mostly square or sometimes rectangle. At each parent node 2 planes are chosen which mostly divides the node into 4 equal children.
    QuadTreeImage
  • Oct Tree : An Oct Treeis mostly same as Quad Tree with a difference that  each internal node has 8 children. Oct Trees are used in 3D environments. At each parent node 3 planes are chosen which mostly divides the node into 8 equal children. But there are other techniques also like Loose Oct Trees in which 8 children may/mayn’t be of equal size.
  • Axis Aligned BSP Trees or KD Trees : A k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key. Even Quad Tree and Oct Tree can be thought of as k-d tree with 4 &  8 dimensions.  But in-game development k-d tree mostly means a special case of BSP or Binary Space partitioning Tree in which each internal node has only 2 children and plane used to split at any internal node is aligned to one of the Axes (X,Y or Z).
  • Polygon Aligned BSP Solid  Leaf Trees : Binary space partitioning is a generic process of recursively dividing a scene into two until the partitioning satisfies one or more requirements. At any internal node a plane aligned to one of the polygon is chosen to split other polygons at this level into back child and front child. At leaf Nodes polygons will only be present in front node and back nodes are mostly empty to represent what is called Solid Space or space where player can’t enter.  So we can easily render polygons in back to front or vice versa. Also there many occlusion culling techniques made possible by the BSP trees like Portals and PVS. All of this combined together is still the fastest way to render indoor scenes.

Another factor comes into play is whether we should clip objects / polygons or not along the boundaries of a Node. If we actually clip then polygon count will increase but 2 objects created as a result of clip along any plane will be owned by unique Nodes/ Leafs. But if we decide we don’t want to clip we either have to expand boundaries of Nodes (e.g. loose Oct Trees) or we have to include polygons in both children nodes in which case we have to implement something to avoid rendering same object more than once.

So at the time of writing this Quad Tree , Oct Tree and KD Tree were working and some foundation code for BSP is there but I most probably will be dropping it because right now I want to focus mostly on techniques that can be used in real-time and BSP takes a huge amount of pre processing time in construction of BSP Trees etc, also BSP are mostly much more useful for indoor environments or some outdoor environments with different sections that can be realized like indoor environments or areas (e.g. counterstrike or even half life2 itself).

So here are some screenshots and some statistics of what I achieved –

(Notice the number of triangles rendered in the 1st screenshot is only 8, which is made possible by spatial partitioning and hierarchical frustum culling)

Spatial partitioning is not the end but the beginning of algorithms or techniques that are used to manage / optimize the rendering /collision detection of large scenes. For example one next step is Hierarchical Frustum Culling and then occlusion culling etc.

For people who are interested to investigate it further here are some very good books on the subject –

RealTime Rendering

3D Game Engine Design

Realtime Collision Detection

Advertisements

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.

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.