I started using MOC (http://www.ogre3d.org/tikiwiki/Minimal+Ogre+Collision) but I noticed the FPS drop significantly when there is more than one query per frame. so in my use-case, where there are ~100 NPCs running around and colliding stuff, it wasn't doing the trick
also, I noticed there is no static geometry support.
So I decided to re-write the utility and I think some of you might benefit from it.
for real physics I still recommend using a proper lib, but for experimenting or for games with very simple collision (like a top-down RPG), this utility might do the trick.
NOTE: It's not heavily tested yet! so I take no responsibility for bugs
Features:
* polygon based collision, i.e. accurate collision that is not based on bounding box (like in MOC)
* collision detection type for different entities (bounding box, sphere, or accurate). for example, if you have a simple entity like a box or a sphere you can just use bounding box check for this specific entity instead of using accurate collision.
* static geometry
* don't query all entities - query only entities you register to the collision tools. still support ogre's query flags.
* ignore-entity pointer, so entities won't check collision with themselves.
* first-hit optimization, that stop checking once a positive check is found instead of returning the nearest collision
Performance:
did some tests with ~825 static entities with accurate collision type (200 walls & trees, 625 ground tiles) and some NPCs running around randomly (every NPC running is another ray query per frame). always rendered the scene from the same camera and level, and with const number of rendered NPCs - what changes was which NPCs are moving and which are standing still (only moving are casting queries). all the geometry was static.
without any NPCs moving the FPS was 274.
with 50 NPCs running - still 274
with 100 NPCs running - 188
with 200 NPCs running - 102
Caveat:
* don't support terrains (didn't need so excluded that), unless are converted to an entity with mesh
* ignore ogre query flag types (note: types means billboard, terrain, entity... query flags are supported, types are not.) personally I find this an advantage. but that's just my opinion I guess.
* no skeleton-based animation supported (but node movement / rotation / scaling is supported)
How this works:
1. you create a collision tools instance
2. you register every entity you want to be collideable to the collision tools (you choose collision type and register as static or dynamic entity)
3. for accurate collisions, the tools will hold a cache of the vertices and indices. entities are removed from cache once there are no more references to them.
4. there are two functions for query checks you can use - with starting point and ending point, or with just a ray.
Usage examples:
ray query (note - providing this->m_Entity so it won't collide with itself):
Code: Select all
Collision::SCheckCollisionAnswer ret = collision_tools.check_ray_collision(FromPos, ToPos, 0.3f, 0.5f,
(QUERY_OBJECT_ENTITY | QUERY_TERRAIN_ENTITY), this->m_Entity, true);
if (ret.collided)
....
Code: Select all
collision_tools.register_static_entity(lEntity, Position, quat, Size, Collision::COLLISION_BOX);
collision_tools.register_entity(lEntity, Collision::COLLISION_ACCURATE);
header file:
Code: Select all
/**
* Ness Collision Detection - rewritten simple Ogre collision detection based on MOC idea.
* Feel free to use this!
*
* Author: Ronen Ness
* Since: 22/04/14
*/
#pragma once
#include <Ogre.h>
#include <vector>
#include <utility>
#include <unordered_map>
namespace Collision {
// return struct for the function check_ray_collision (all the data about collision)
// collided - weather or not there was a collision and the data in the struct is valid (if false ignore other fields).
// position - will contain the collision position
// entity - the collided entity
// closest_distance - will contain the closest distance we collided with
struct SCheckCollisionAnswer
{
bool collided;
Ogre::Vector3 position;
Ogre::Entity* entity;
float closest_distance;
};
// different collision types
enum ECollisionType
{
COLLISION_ACCURATE, // will check accurate intersection with all verticles of the entity (for complex shapes that need accurate collision)
COLLISION_BOX, // will only check intersection with the bounding box (good for walls and crates-like objects)
COLLISION_SPHERE, // will only check interection with the object sphere (good for characters)
};
// holds vertices data of a mesh
struct SMeshData
{
unsigned int ref_count; // how many entities we have with that mesh registered to the collision tools (when 0, this data is deleted)
size_t vertex_count; // vertices count
Ogre::Vector3* vertices; // vertices
size_t index_count; // indices count
Ogre::uint32* indices; // indices
SMeshData() : ref_count(0), vertex_count(0), vertices(nullptr), index_count(0), indices(nullptr)
{
}
// delete the inner data
void delete_data()
{
delete[] vertices;
delete[] indices;
}
};
// data about an entity registered to the collision tools
struct SCollidableEntity
{
Ogre::Entity* Entity; // the entity to check
ECollisionType CollisionType; // the prefered collision type for this entity
bool IsStatic; // is this entity part of a static geometry
// Data used only for static entities
struct SStaticData
{
Ogre::Sphere Sphere; // used only for static objects with sphere collision
Ogre::AxisAlignedBox Box; // used only for static objects with box or accurate collision
Ogre::Matrix4 Mat; // transformation matrix
} *StaticData;
// delete the static data if have it
void remove_static_data()
{
if (StaticData)
delete StaticData;
StaticData = nullptr;
}
};
// collision detection manager for a specific scene
class CollisionTools {
private:
std::vector<SCollidableEntity> m_Entities; // the entities that are registered for collision checks
std::unordered_map<const Ogre::Mesh*, SMeshData> m_MeshesData; // data about meshes we need for accurate collision
public:
CollisionTools();
~CollisionTools();
// register a dynamic entity for collision detection
void register_entity(Ogre::Entity* Entity, ECollisionType CollisionType = COLLISION_ACCURATE);
// register a static entity for collision detection
void register_static_entity(Ogre::Entity* Entity, const Ogre::Vector3& position, const Ogre::Quaternion orientation, const Ogre::Vector3 scale, ECollisionType CollisionType = COLLISION_ACCURATE);
// unregister an entity from collision detection (make sure to call this when the entity is deleted!)
void remove_entity(Ogre::Entity* Entity);
// check ray collision. check out "SCheckCollisionAnswer" for info about return values.
// ray - collision ray to check
// queryMask - ogre's query mask (you can set for every entity
// ignore - will ignore the entity who has the address of 'ignore'. use this if you want to prevent a character from colliding with itself..
// maxDistance - beyond this distance we'll ignore entities
// stopOnFirstPositive - if true, will stop on first positive collision (instead of nearest)
SCheckCollisionAnswer check_ray_collision(const Ogre::Ray &ray, const Ogre::uint32 queryMask = 0xFFFFFFFF, void* ignore = nullptr, Ogre::Real maxDistance = 0xffff, bool stopOnFirstPositive = false);
// check ray collision. check out "SCheckCollisionAnswer" for info about return values.
// fromPoint - ray starting point
// toPoint - ray ending point
// collisionRadius - ray 'radius'
// rayHeightLevel - will add this factor to the yof the ray.
// queryMask - ogre's query mask (you can set for every entity
// ignore - will ignore the entity who has the address of 'ignore'. use this if you want to prevent a character from colliding with itself..
// stopOnFirstPositive - if true, will stop on first positive collision (instead of nearest)
SCheckCollisionAnswer check_ray_collision(const Ogre::Vector3& fromPoint, const Ogre::Vector3& toPoint, const float collisionRadius = 1.0f,
const float rayHeightLevel = 0.0f, const Ogre::uint32 queryMask = 0xFFFFFFFF, void* ignore = nullptr, bool stopOnFirstPositive = false);
private:
// do a simple ray query and return a list of results sorted by distance
// NOTE!!! this function only do simple query! it does not do accurate checks or anything, either box collision or sphere collision.
// all the accurate checks and range limit is done in one of the 'check_ray_collision' functions
// stopOnFirstPositive - if true, will stop on first positive bounding box or sphere collision (not relevant for accurate collisions)
typedef std::pair<const SCollidableEntity*, Ogre::Real> RayQueryEntry;
std::list<RayQueryEntry> get_basic_ray_query_entities_list(const Ogre::Ray &ray, const Ogre::uint32 queryMask = 0xFFFFFFFF,
void* ignore = nullptr, Ogre::Real maxDistance = 0xffff, bool stopOnFirstPositive = false);
// comparing function to arranage the result list of get_basic_ray_query_entities_list
friend bool compare_query_distance (const CollisionTools::RayQueryEntry& first, const CollisionTools::RayQueryEntry& second);
// add mesh data reference to m_MeshesData map.
// if first mesh of this type, create all its data, if already exist just increase the reference
void add_mesh_data(const Ogre::Mesh* mesh);
// remove reference from mesh data. if ref count is 0, data is released
void remove_mesh_data(const Ogre::Mesh* mesh);
// get all the needed information of a mesh
// we use this function to create the mesh data hash table for accurate collision
void get_mesh_info(const Ogre::Mesh* mesh,
size_t &vertex_count,
Ogre::Vector3* &vertices,
size_t &index_count,
Ogre::uint32* &indices);
};
};
Code: Select all
#include "NessCollisionDetection.h"
namespace Collision {
CollisionTools::CollisionTools()
{
}
CollisionTools::~CollisionTools()
{
// remove all entities and static data
while (!m_Entities.empty())
{
m_Entities.back().remove_static_data();
m_Entities.pop_back();
}
// remove all meshes data
for (auto mesh_data = m_MeshesData.begin(); mesh_data != m_MeshesData.end(); ++ mesh_data)
{
mesh_data->second.delete_data();
}
}
// unregister an entity from collision detection (make sure to call this when the entity is deleted!)
void CollisionTools::remove_entity(Ogre::Entity* Entity)
{
// find the entity in the entities list
for (auto data = m_Entities.begin(); data != m_Entities.end(); ++data)
{
if (data->Entity == Entity)
{
// remove static data and mesh data (if exist)
data->remove_static_data();
if (data->CollisionType == COLLISION_ACCURATE)
remove_mesh_data(data->Entity->getMesh().get());
// erase this entity from the list
m_Entities.erase(data);
return;
}
}
assert(false);
}
SCheckCollisionAnswer CollisionTools::check_ray_collision(const Ogre::Vector3& fromPoint, const Ogre::Vector3& toPoint, const float collisionRadius,
const float rayHeightLevel, const Ogre::uint32 queryMask, void* ignore, bool stopOnFirstPositive)
{
// convert points to a collision ray
Ogre::Vector3 fromPointAdj(fromPoint.x, fromPoint.y + rayHeightLevel, fromPoint.z);
Ogre::Vector3 toPointAdj(toPoint.x, toPoint.y + rayHeightLevel, toPoint.z);
Ogre::Vector3 normal = toPointAdj - fromPointAdj;
float distToDest = normal.normalise();
static Ogre::Ray ray;
ray.setOrigin(fromPointAdj);
ray.setDirection(normal);
// do the query
SCheckCollisionAnswer ret = check_ray_collision(ray, queryMask, ignore, collisionRadius, stopOnFirstPositive);
// make sure its within radius range
if (ret.collided)
{
float distToColl = ret.closest_distance;
distToColl -= collisionRadius;
ret.collided = (distToColl <= distToDest);
}
return ret;
}
SCheckCollisionAnswer CollisionTools::check_ray_collision(const Ogre::Ray &ray, const Ogre::uint32 queryMask, void* ignore,
Ogre::Real maxDistance, bool stopOnFirstPositive)
{
// create return structure
SCheckCollisionAnswer ret;
memset(&ret, 0, sizeof(ret));
// first do a simple ray query on all the entities we registered
std::list<CollisionTools::RayQueryEntry> results = get_basic_ray_query_entities_list(ray, queryMask, ignore, maxDistance, stopOnFirstPositive);
// no results? stop here
if (results.size() <= 0)
{
return ret;
}
// at this point we have raycast to a series of different objects bounding boxes.
// we need to test these different objects to see which is the first polygon hit.
// there are some minor optimizations (distance based) that mean we wont have to
// check all of the objects most of the time, but the worst case scenario is that
// we need to test every triangle of every object.
//Ogre::Ogre::Real closest_distance = -1.0f;
ret.closest_distance = -1.0f;
for (auto query_result = results.begin(); query_result != results.end(); ++query_result)
{
// since its sorted by distance, once we hit an entity that only collides with bounding box or sphere,
// we stop immediatly and return it. there's no point checking the rest of the entities.
if (query_result->first->CollisionType != COLLISION_ACCURATE)
{
ret.closest_distance = abs(query_result->second);
ret.collided = true;
ret.entity = query_result->first->Entity;
ret.position = ray.getPoint(ret.closest_distance);
return ret;
}
// stop checking if we have found a raycast hit that is closer
// than all remaining entities
if (((ret.closest_distance >= 0.0f) && (maxDistance < maxDistance)) &&
(ret.closest_distance < query_result->second || stopOnFirstPositive))
{
break;
}
// only check this result if its a hit against an entity
{
// get the entity to check
Ogre::MovableObject *pentity = static_cast<Ogre::MovableObject*>(query_result->first->Entity);
// get mesh data from cache
const SMeshData& data = m_MeshesData[query_result->first->Entity->getMesh().get()];
assert(data.ref_count);
// test for hitting individual triangles on the mesh
bool new_closest_found = false;
for (size_t i = 0; i < data.index_count; i += 3)
{
// get transformation matrix
const Ogre::Matrix4* mat;
if (query_result->first->IsStatic)
{
mat = &query_result->first->StaticData->Mat;
}
else
{
mat = &query_result->first->Entity->getParentNode()->_getFullTransform();
}
// get corrent triangle and transform it
Ogre::Vector3 v1, v2, v3;
v1 = (*mat) * data.vertices[data.indices[i]];
v2 = (*mat) * data.vertices[data.indices[i+1]];
v3 = (*mat) * data.vertices[data.indices[i+2]];
// check for a hit against this triangle
std::pair<bool, Ogre::Real> hit = Ogre::Math::intersects(ray, v1, v2, v3, true, false);
// if it was a hit check if its the closest
if (hit.first && hit.second < maxDistance)
{
if ((ret.closest_distance < 0.0f) ||
(hit.second < ret.closest_distance))
{
// this is the closest so far, save it off
ret.closest_distance = hit.second;
new_closest_found = true;
}
}
}
// if we found a new closest raycast for this object, update the
// closest_result before moving on to the next object.
if (new_closest_found)
{
ret.entity = (Ogre::Entity*)pentity;
ret.position = ray.getPoint(ret.closest_distance);
}
}
}
// return the result
ret.collided = (ret.closest_distance >= 0.0f);
return ret;
}
// Get the mesh information for the given mesh.
// Code found on this forum link: http://www.ogre3d.org/wiki/index.php/RetrieveVertexData
// TAKEN FROM MOC
void CollisionTools::get_mesh_info(const Ogre::Mesh* mesh,
size_t &vertex_count,
Ogre::Vector3* &vertices,
size_t &index_count,
Ogre::uint32* &indices)
{
bool added_shared = false;
size_t current_offset = 0;
size_t shared_offset = 0;
size_t next_offset = 0;
size_t index_offset = 0;
vertex_count = index_count = 0;
// Calculate how many vertices and indices we're going to need
for (unsigned short i = 0; i < mesh->getNumSubMeshes(); ++i)
{
Ogre::SubMesh* submesh = mesh->getSubMesh( i );
// We only need to add the shared vertices once
if(submesh->useSharedVertices)
{
if( !added_shared )
{
vertex_count += mesh->sharedVertexData->vertexCount;
added_shared = true;
}
}
else
{
vertex_count += submesh->vertexData->vertexCount;
}
// Add the indices
index_count += submesh->indexData->indexCount;
}
// Allocate space for the vertices and indices
vertices = new Ogre::Vector3[vertex_count];
indices = new Ogre::uint32[index_count];
added_shared = false;
// Run through the submeshes again, adding the data into the arrays
for ( unsigned short i = 0; i < mesh->getNumSubMeshes(); ++i)
{
Ogre::SubMesh* submesh = mesh->getSubMesh(i);
Ogre::VertexData* vertex_data = submesh->useSharedVertices ? mesh->sharedVertexData : submesh->vertexData;
if((!submesh->useSharedVertices)||(submesh->useSharedVertices && !added_shared))
{
if(submesh->useSharedVertices)
{
added_shared = true;
shared_offset = current_offset;
}
const Ogre::VertexElement* posElem =
vertex_data->vertexDeclaration->findElementBySemantic(Ogre::VES_POSITION);
Ogre::HardwareVertexBufferSharedPtr vbuf =
vertex_data->vertexBufferBinding->getBuffer(posElem->getSource());
unsigned char* vertex =
static_cast<unsigned char*>(vbuf->lock(Ogre::HardwareBuffer::HBL_READ_ONLY));
// There is _no_ baseVertexPointerToElement() which takes an Ogre::Ogre::Real or a double
// as second argument. So make it float, to avoid trouble when Ogre::Ogre::Real will
// be comiled/typedefed as double:
// Ogre::Ogre::Real* pOgre::Real;
float* pReal;
for( size_t j = 0; j < vertex_data->vertexCount; ++j, vertex += vbuf->getVertexSize())
{
posElem->baseVertexPointerToElement(vertex, &pReal);
Ogre::Vector3 pt(pReal[0], pReal[1], pReal[2]);
vertices[current_offset + j] = pt;
}
vbuf->unlock();
next_offset += vertex_data->vertexCount;
}
Ogre::IndexData* index_data = submesh->indexData;
size_t numTris = index_data->indexCount / 3;
Ogre::HardwareIndexBufferSharedPtr ibuf = index_data->indexBuffer;
bool use32bitindexes = (ibuf->getType() == Ogre::HardwareIndexBuffer::IT_32BIT);
Ogre::uint32* pLong = static_cast<Ogre::uint32*>(ibuf->lock(Ogre::HardwareBuffer::HBL_READ_ONLY));
unsigned short* pShort = reinterpret_cast<unsigned short*>(pLong);
size_t offset = (submesh->useSharedVertices)? shared_offset : current_offset;
if ( use32bitindexes )
{
for ( size_t k = 0; k < numTris*3; ++k)
{
indices[index_offset++] = pLong[k] + static_cast<Ogre::uint32>(offset);
}
}
else
{
for ( size_t k = 0; k < numTris*3; ++k)
{
indices[index_offset++] = static_cast<Ogre::uint32>(pShort[k]) +
static_cast<Ogre::uint32>(offset);
}
}
ibuf->unlock();
current_offset = next_offset;
}
}
// register a dynamic entity for collision detection
void CollisionTools::register_entity(Ogre::Entity* Entity, ECollisionType CollisionType)
{
// create the new data struct
SCollidableEntity New;
New.Entity = Entity;
New.CollisionType = CollisionType;
New.IsStatic = false;
New.StaticData = nullptr;
// if need accurate collision, create the data for it
if (CollisionType == COLLISION_ACCURATE)
add_mesh_data(Entity->getMesh().get());
// add it to the list of collideables
m_Entities.push_back(New);
}
// register a static entity for collision detection
void CollisionTools::register_static_entity(Ogre::Entity* Entity, const Ogre::Vector3& position, const Ogre::Quaternion orientation, const Ogre::Vector3 scale, ECollisionType CollisionType)
{
// create the new data struct
SCollidableEntity New;
New.Entity = Entity;
New.CollisionType = CollisionType;
New.IsStatic = true;
New.StaticData = new SCollidableEntity::SStaticData();
New.StaticData->Mat.makeTransform(position, scale, orientation);
New.StaticData->Sphere.setRadius(Entity->getBoundingRadius() * scale.length());
New.StaticData->Sphere.setCenter(position);
New.StaticData->Box = Entity->getBoundingBox();
Ogre::Matrix4 mat;
mat.makeTransform(position, scale, orientation);
New.StaticData->Box.transform(mat);
// if need accurate collision, create the data for it
if (CollisionType == COLLISION_ACCURATE)
add_mesh_data(Entity->getMesh().get());
// add it to the list of collideables
m_Entities.push_back(New);
}
// add a reference to a mesh data
void CollisionTools::add_mesh_data(const Ogre::Mesh* mesh)
{
// if already exist, just increase the reference count
SMeshData& data = m_MeshesData[mesh];
if (data.ref_count > 0)
{
data.ref_count++;
return;
}
// if not exist, create it
data.ref_count = 1;
get_mesh_info(mesh, data.vertex_count, data.vertices, data.index_count, data.indices);
}
// remove reference from mesh data. if ref count is 0, data is released
void CollisionTools::remove_mesh_data(const Ogre::Mesh* mesh)
{
SMeshData& data = m_MeshesData[mesh];
data.ref_count--;
if (data.ref_count == 0)
{
data.delete_data();
m_MeshesData.erase(mesh);
}
}
// to sort the return list from 'get_basic_ray_query_entities_list()'
bool compare_query_distance (const CollisionTools::RayQueryEntry& first, const CollisionTools::RayQueryEntry& second)
{
// if first collision function is more simple than second, always put it first
if (first.first->CollisionType != COLLISION_ACCURATE && second.first->CollisionType == COLLISION_ACCURATE)
return true;
// if second collision function is more simple than second, always put it first
if (second.first->CollisionType != COLLISION_ACCURATE && first.first->CollisionType == COLLISION_ACCURATE)
return false;
// else, sort by distance
return first.second < second.second;
}
// do a simple ray query and return a list of results sorted by distance
std::list<CollisionTools::RayQueryEntry> CollisionTools::get_basic_ray_query_entities_list(const Ogre::Ray &ray, const Ogre::uint32 queryMask, void* ignore,
Ogre::Real maxDistance, bool stopOnFirstPositive)
{
// return vector
std::list<CollisionTools::RayQueryEntry> ret;
// loop over all the registered entities and check simple sphere/box intersection. arrange by distance.
bool Stop = false;
for (auto data = m_Entities.begin(); (data != m_Entities.end() && !Stop); ++data)
{
// skip the ignored entity
if (data->Entity == ignore)
continue;
// skip if query mask don't fit
if ((data->Entity->getQueryFlags() & queryMask) == 0)
continue;
// if its static, first perform simple distance check
if (data->IsStatic &&
ray.getOrigin().distance(data->StaticData->Sphere.getCenter()) - data->StaticData->Sphere.getRadius() > maxDistance)
continue;
// if invisible skip it
if (!data->Entity->isVisible())
continue;
// check basic intersection
switch (data->CollisionType)
{
// check box intersection
case COLLISION_ACCURATE:
case COLLISION_BOX:
{
// get the bounding box to use
const Ogre::AxisAlignedBox* bb = (data->IsStatic) ? &data->StaticData->Box : &data->Entity->getWorldBoundingBox(true);
// check if intersects and if so insert to return list (sorting comes in the end)
std::pair<bool, Ogre::Real> inter = ray.intersects(*bb);
assert(maxDistance >= 0);
if (inter.first && inter.second < maxDistance)
{
ret.push_back(CollisionTools::RayQueryEntry(data._Ptr, inter.second));
if (stopOnFirstPositive && data->CollisionType == COLLISION_BOX)
Stop = true;
}
break;
}
// check sphere collision
case COLLISION_SPHERE:
{
// get the sphere to use
const Ogre::Sphere* sp;
if (data->IsStatic)
{
sp = &data->StaticData->Sphere;
}
else
{
Ogre::Sphere sphere = data->Entity->getWorldBoundingSphere(true);
sp = &sphere;
}
// check if intersects and if so insert to return list (sorting comes in the end)
std::pair<bool, Ogre::Real> inter = ray.intersects(*sp);
inter.second = abs(inter.second);
if (inter.first && inter.second < maxDistance)
{
ret.push_back(CollisionTools::RayQueryEntry(data._Ptr, inter.second));
if (stopOnFirstPositive)
Stop = true;
}
break;
}
// should never get here.
default:
assert(false);
}
}
// now sort the list!
ret.sort(compare_query_distance);
// return the list
return ret;
}
};
[youtube]eWitZPEyfCw[/youtube]
Enjoy
and thanks to everyone 
