I am implementing a multi-phase collision detection system whose final collision check is checking the triangles of one shape against those of another. As the number of triangle-triangle comparisons can get high I have implemented the spatial hash described at Optimized Spatial Hashing For Collision Detection of Deformable Objects.
At the moment I iterate through each shape, check if its bounding sphere intersects with any other bounding spheres, then hash all the triangles from all shapes that potentially collide. I then check all the buckets in my hash table that have more than one entry and, for each entry in those bucket, make sure that triangle and the next triangle are not from the same shape (class Asset
). If they are not from the same shape I run triangle-triangle collision checks on them.
The problem I have run into is that I am eating up enormous amounts of time just checking the Asset each triangle belongs to, so much so that it can take me 30 seconds to go through one round of this testing, with only 2000 triangles in total between my shapes. Am I doing something wrong?
Here is my code for collision detection:
GLboolean checkForCollisions()
{
std::vector<Asset*> potentialCollisions;
getPotentialCollisions(potentialCollisions);
if (potentialCollisions.size() > 0)
for (Asset* asset : potentialCollisions)
{
updateVertices(asset);
for (Triangle* triangle : asset->triangles)
hash.add(triangle, currentTime);
}
std::vector<HashElement*> bucketsWithMultipleTriangles = hash.getAllBucketsWithMultipleTriangles(currentTime);
for (HashElement* element : bucketsWithMultipleTriangles)
{
HashElement* firstElement = element;
HashElement* currentElement = element;
HashElement* nextElement;
while (currentElement->nextElement != nullptr)
{
nextElement = currentElement->nextElement;
if (currentElement->_triangle->_asset != nextElement->_triangle->_asset)
{
if (collisionDetector.checkForCollision(currentElement->_triangle, nextElement->_triangle))
{
currentElement->_triangle->_asset->velocity = glm::vec3(0, 0, 0);
nextElement->_triangle->_asset->velocity = glm::vec3(0, 0, 0);
}
}
}
}
return false;
void updateVertices(Asset* asset)
{
asset->triangles.clear();
for (Triangle* triangle : asset->originalTriangles)
{
glm::vec4 transformedVector0 = glm::translate(glm::mat4(1.0f), asset->position) *
glm::vec4(triangle->_vertex0.x, triangle->_vertex0.y, triangle->_vertex0.z, 1);
glm::vec4 transformedVector1 = glm::translate(glm::mat4(1.0f), asset->position) *
glm::vec4(triangle->_vertex1.x, triangle->_vertex1.y, triangle->_vertex1.z, 1);
glm::vec4 transformedVector2 = glm::translate(glm::mat4(1.0f), asset->position) *
glm::vec4(triangle->_vertex2.x, triangle->_vertex2.y, triangle->_vertex2.z, 1);
asset->triangles.push_back(new Triangle(transformedVector0, transformedVector1, transformedVector2, asset));
}
}
GLboolean vectorContainsAsset(std::vector<Asset*> assets, Asset* asset)
{
for (Asset* _asset : assets)
{
if (_asset == asset)
return true;
}
}
void getPotentialCollisions(std::vector<Asset*> &potentialCollisions)
{
int assetsSize = assets.size();
for (int i = 0; i < assetsSize; i++)
{
for (int j = i + 1; j < assetsSize; j++)
{
if (assets.at(j)->collisionAdditionTime != currentTime)
{
if (assets.at(i)->boundingSphere.checkForCollision(assets.at(j)->boundingSphere))
{
if (assets.at(i)->collisionAdditionTime != currentTime)
{
assets.at(i)->collisionAdditionTime = currentTime;
potentialCollisions.push_back(assets.at(i));
}
assets.at(j)->collisionAdditionTime = currentTime;
potentialCollisions.push_back(assets.at(j));
}
}
}
}
}
my Asset class is defined as:
#ifndef ASSET_H
#define ASSET_H
#include "BoundingSphere.h"
class Triangle;
class Asset
{
public:
Asset::Asset(std::string assetOBJFile);
GLuint vertexArrayID;
GLuint programID;
GLuint vertexbuffer;
GLint verticesSize;
std::vector<GLuint> faces;
std::vector<glm::vec3> vertices;
std::vector<Triangle*> originalTriangles;
std::vector<Triangle*> triangles;
BoundingSphere boundingSphere;
glm::vec3 velocity;
glm::vec3 position;
double collisionAdditionTime = -1;
private:
void loadOBJ(const char* path);
};
#endif
and my Triangle class as:
#ifndef TRIANGLE_H
#define TRIANGLE_H
#include <glm\glm.hpp>
class Asset;
class Triangle
{
public:
glm::vec3 _vertex0, _vertex1, _vertex2;
Asset* _asset;
Triangle(glm::vec3 vertex0, glm::vec3 vertex1, glm::vec3 vertex2, Asset* asset);
Triangle(glm::vec3 vertex0, glm::vec3 vertex1, glm::vec3 vertex2);
Triangle(glm::vec4 vertex0, glm::vec4 vertex1, glm::vec4 vertex2, Asset* asset);
private:
};
#endif
Note that I load all of the triangles for an asset into the originalTriangles
vector. Then, if my bounding sphere-bounding sphere intersection test returns true I update the vertices of each triangle in my updateVertices
function. (I think there is a better way to do that which doesn't involve clearing and rebuilding my triangles vector, but for right now that's not where the bottleneck is.
I have done unit testing on my BoundingSphere
and TriangleTriangleDetection
classes, and know that they work as intended.
Finally, the code for my SpatialHash
is as follows:
#ifndef SPATIAL_HASH_H
#define SPATIAL_HASH_H
#include <vector>
#include "Triangle.h"
#define P1 73856093
#define P2 19349663
#define P3 83492791
#define TABLE_SIZE 2887
struct HashElement
{
Triangle* _triangle;
HashElement* nextElement;
double timeAdded;
HashElement()
{
_triangle = nullptr;
nextElement = nullptr;
}
HashElement(Triangle* triangle, double currentTime)
{
_triangle = triangle;
nextElement = nullptr;
timeAdded = currentTime;
}
};
class SpatialHash
{
public:
SpatialHash();
void add(Triangle* triangle, double currentTime);
std::vector<HashElement*> find(Triangle* triangle);
std::vector<HashElement*> getAllBucketsWithMultipleTriangles(double currentTime);
private:
HashElement* hashTable[TABLE_SIZE];
void destroy(HashElement** element);
int hash(int x, int y, int z);
HashElement* lastElementInChain(HashElement* element);
glm::vec3 getMax(Triangle* triangle);
glm::vec3 getMin(Triangle* triangle);
};
#endif
Implementation:
#include <GL\glew.h>
#include <GLFW\glfw3.h>
#include <glm\gtc\matrix_transform.hpp>
#include "SpatialHash.h"
#include "TriangleTriangleCollision.h"
#include "Triangle.h"
#include "Asset.h"
#include <vector>
#include <iostream>
class Triangle;
class Asset;
glm::mat4 projection;
glm::mat4 view = glm::lookAt(glm::vec3(0, 5, 30),
glm::vec3(0, 1, 0),
glm::vec3(0, 1, 0));
glm::mat4 camera;
GLFWwindow* window;
GLint _windowWidth, _windowHeight;
TriangleTriangleCollision collisionDetector;
SpatialHash hash;
std::vector<Asset*> assets;
double lastTime, currentTime;
void setupAndInitializeWindow(GLint windowWidth, GLint windowHeight, std::string windowTitle)
{
_windowWidth = windowWidth;
_windowHeight = windowHeight;
if (!glfwInit())
{
fprintf(stderr, "Failed to initialize GLFW\n");
std::cin.get(); exit(-1);
}
glfwWindowHint(GLFW_SAMPLES, 4);
glfwWindowHint(GLFW_CONTEXT_VERSION_MAJOR, 3);
glfwWindowHint(GLFW_CONTEXT_VERSION_MINOR, 3);
glfwWindowHint(GLFW_OPENGL_PROFILE, GLFW_OPENGL_CORE_PROFILE);
window = glfwCreateWindow(_windowWidth, _windowHeight, windowTitle.c_str(), NULL, NULL);
if (window == NULL){
fprintf(stderr, "Failed to open GLFW window. If you have an Intel GPU, they are not 3.3 compatible. Try the 2.1 version of the tutorials.\n");
glfwTerminate();
std::cin.get(); exit(-1);
}
glfwMakeContextCurrent(window);
glewExperimental = true;
if (glewInit() != GLEW_OK) {
fprintf(stderr, "Failed to initialize GLEW\n");
std::cin.get(); exit(-1);
}
glfwSetInputMode(window, GLFW_STICKY_KEYS, GL_TRUE);
glfwSetCursorPos(window, _windowWidth / 2, _windowHeight / 2);
glClearColor(1.0f, 1.0f, 1.0f, 1.0f);
glEnable(GL_DEPTH_TEST);
glDepthFunc(GL_LESS);
glEnable(GL_CULL_FACE);
projection = glm::perspective(45.0f, (float) _windowWidth / _windowHeight, 0.1f, 100.0f);
camera = projection * view;
}
void renderAsset(Asset* asset)
{
glUseProgram(asset->programID);
GLuint cameraID = glGetUniformLocation(asset->programID, "camera");
glUniformMatrix4fv(cameraID, 1, GL_FALSE, &camera[0][0]);
GLuint positionID = glGetUniformLocation(asset->programID, "position");
glUniformMatrix4fv(positionID, 1, GL_FALSE, &glm::translate(glm::mat4(), asset->position)[0][0]);
glEnableVertexAttribArray(0);
glBindBuffer(GL_ARRAY_BUFFER, asset->vertexbuffer);
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 0, (void*)0);
glDrawArrays(GL_TRIANGLES, 0, asset->verticesSize);
glDisableVertexAttribArray(0);
}
void cleanupAsset(Asset asset)
{
glDeleteBuffers(1, &asset.vertexbuffer);
glDeleteProgram(asset.programID);
glDeleteVertexArrays(1, &asset.vertexArrayID);
}
glm::mat4 translate(glm::vec3 position)
{
return glm::translate(glm::mat4(), position);
}
void moveAsset(Asset* asset)
{
asset->position.x += (asset->velocity.x * (currentTime - lastTime));
asset->position.y += (asset->velocity.y * (currentTime - lastTime));
asset->position.z += (asset->velocity.z * (currentTime - lastTime));
}
void updateVertices(Asset* asset)
{
asset->triangles.clear();
for (Triangle* triangle : asset->originalTriangles)
{
glm::vec4 transformedVector0 = glm::translate(glm::mat4(1.0f), asset->position) *
glm::vec4(triangle->_vertex0.x, triangle->_vertex0.y, triangle->_vertex0.z, 1);
glm::vec4 transformedVector1 = glm::translate(glm::mat4(1.0f), asset->position) *
glm::vec4(triangle->_vertex1.x, triangle->_vertex1.y, triangle->_vertex1.z, 1);
glm::vec4 transformedVector2 = glm::translate(glm::mat4(1.0f), asset->position) *
glm::vec4(triangle->_vertex2.x, triangle->_vertex2.y, triangle->_vertex2.z, 1);
asset->triangles.push_back(new Triangle(transformedVector0, transformedVector1, transformedVector2, asset));
}
}
GLboolean vectorContainsAsset(std::vector<Asset*> assets, Asset* asset)
{
for (Asset* _asset : assets)
{
if (_asset == asset)
return true;
}
}
void getPotentialCollisions(std::vector<Asset*> &potentialCollisions)
{
int assetsSize = assets.size();
for (int i = 0; i < assetsSize; i++)
{
for (int j = i + 1; j < assetsSize; j++)
{
if (assets.at(j)->collisionAdditionTime != currentTime)
{
if (assets.at(i)->boundingSphere.checkForCollision(assets.at(j)->boundingSphere))
{
if (assets.at(i)->collisionAdditionTime != currentTime)
{
assets.at(i)->collisionAdditionTime = currentTime;
potentialCollisions.push_back(assets.at(i));
}
assets.at(j)->collisionAdditionTime = currentTime;
potentialCollisions.push_back(assets.at(j));
}
}
}
}
}
GLboolean checkForCollisions()
{
std::vector<Asset*> potentialCollisions;
getPotentialCollisions(potentialCollisions);
if (potentialCollisions.size() > 0)
for (Asset* asset : potentialCollisions)
{
updateVertices(asset);
for (Triangle* triangle : asset->triangles)
hash.add(triangle, currentTime);
}
std::vector<HashElement*> bucketsWithMultipleTriangles = hash.getAllBucketsWithMultipleTriangles(currentTime);
for (HashElement* element : bucketsWithMultipleTriangles)
{
HashElement* firstElement = element;
HashElement* currentElement = element;
HashElement* nextElement;
while (currentElement->nextElement != nullptr)
{
nextElement = currentElement->nextElement;
if (currentElement->_triangle->_asset != nextElement->_triangle->_asset)
{
if (collisionDetector.checkForCollision(currentElement->_triangle, nextElement->_triangle))
{
currentElement->_triangle->_asset->velocity = glm::vec3(0, 0, 0);
nextElement->_triangle->_asset->velocity = glm::vec3(0, 0, 0);
}
}
}
}
return false;
}
void loadScene()
{
assets.push_back(new Asset("cube.obj"));
assets.back()->position = glm::vec3(2, 0, 0);
assets.back()->velocity = glm::vec3(-2, 0, 0);
assets.push_back(new Asset("donut.obj"));
assets.back()->position = glm::vec3(2, 2, 0);
assets.back()->velocity = glm::vec3(0, -2, 0);
assets.push_back(new Asset("donut.obj"));
assets.back()->position = glm::vec3(-2, 0, 0);
assets.back()->velocity = glm::vec3(2, 0, 0);
/*
Asset* cube = new Asset("cube.obj");
currentTime = 0.5;
lastTime = 0.0;
updateVertices(cube);
for (Triangle* triangle : cube->triangles)
hash.add(triangle, currentTime);
cube->position = glm::vec3(0.0, 2.0, 0.0);
updateVertices(cube);
currentTime = 1.0;
for (Triangle* triangle : cube->triangles)
hash.add(triangle, currentTime);*/
}
int main()
{
setupAndInitializeWindow(760, 480, "Final Project");
loadScene();
lastTime = currentTime = glfwGetTime();
do{
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
//move assets
for (Asset* &asset : assets)
{
moveAsset(asset);
}
//softUpdate their bounding volumes
for (Asset* &asset : assets)
{
asset->boundingSphere.softUpdate(asset->position);
}
//checkForCollisions
checkForCollisions();
//renderAsset
for (Asset* asset : assets)
{
renderAsset(asset);
}
lastTime = currentTime;
currentTime = glfwGetTime();
glfwSwapBuffers(window);
glfwPollEvents();
} while (glfwGetKey(window, GLFW_KEY_ESCAPE) != GLFW_PRESS &&
glfwWindowShouldClose(window) == 0);
glfwTerminate();
return 0;
}