Weeding out triangles for triangle-triangle collision detection using a spatial hash

Question

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;
}

Answer 1

If it's taking 15 msec to to identify which asset a triangle belongs to, then wouldn't it make sense to store an asset pointer in each triangle, or keep a hash map on the side?

Here's a coding style remark. In checkForCollisions you do:

if (potentialCollisions.size() > 0)

for (Asset* asset : potentialCollisions)
{

Standard advice is to always use {} curly braces on if, even for a single statement as we have here, in order to avoid maintenance issues down the road. But even stronger advice is to at least indent the statement, yikes! And, do we even need the if? Did you bench this and obtain compelling timing results? Why does checking size twice, once in your if and once in the for, go faster than checking it once? I recommend trimming the if.