1
\$\begingroup\$

I am implementing the spatial hashing algorithm described in Optimized Spatial Hashing for Collision Detection of Deformable Objects with a few adjustments, the largest one being that each bucket in the hash table stores an array of pointers to a linked list of Triangles. Each of the elements in the array has a pointer to an Asset class. This way I don't have to check the triangles from the same asset against each other.

At the moment everything seems to be working fine, but does anyone see any glaring problems, or areas that could be optimized, before I continue?

SpatialHash.h

#ifndef SPATIAL_HASH_H
#define SPATIAL_HASH_H

#include <glm\glm.hpp>

#include "Triangle.h"
#include "Asset.h"

#define P1 73856093
#define P2 19349663
#define P3 83492791
#define TABLE_SIZE 20

#define MAX_ASSETS 10

struct TriangleElement
{
    Triangle* _triangle;
    TriangleElement* _nextElement;

    TriangleElement(Triangle* triangle)
    {
        _triangle = triangle;
        _nextElement = nullptr;
    }
};

struct AssetData
{
    Asset* _asset;
    TriangleElement* _firstTriangle;

    AssetData(Triangle* triangle)
    {
        _asset = triangle->_asset;
        _firstTriangle = new TriangleElement(triangle);
    }
};

struct HashElement
{
    AssetData* _assets[MAX_ASSETS];
    double _timeInserted;

    HashElement(double timeInserted)
    {
        for (AssetData* &asset : _assets)
        {
            asset = nullptr;
        }

        _timeInserted = timeInserted;
    }
};

class SpatialHash
{
public:
    SpatialHash();
    void insert(Triangle* triangle, double currentTime);
private:
    HashElement* hashTable[TABLE_SIZE];
    glm::vec3 getMax(Triangle* triangle);
    glm::vec3 getMin(Triangle* triangle);
    int hash(int x, int y, int z);
    void destroy(HashElement* element);
    void insertIntoList(Triangle* triangle, TriangleElement* firstElement);
};

#endif

and my implementation:

#include "SpatialHash.h"

SpatialHash::SpatialHash()
{
    for (HashElement* &element : hashTable)
    {
        element = nullptr;
    }
}

void SpatialHash::insert(Triangle* triangle, double currentTime)
{
    glm::vec3 max = getMax(triangle);
    glm::vec3 min = getMin(triangle);

    for (int i = min.x; i <= max.x; i++)
    {
        for (int j = min.y; j <= max.y; j++)
        {
            for (int k = min.z; k <= max.z; k++)
            {
                int index = hash(i, j, k);
                if (hashTable[index] == nullptr)
                {
                    hashTable[index] = new HashElement(currentTime);
                }
                if (hashTable[index]->_timeInserted == currentTime)
                {
                    for (int i = 0; i < MAX_ASSETS; i++)
                    {
                        bool inserted = false;
                        if (hashTable[index]->_assets[i] == nullptr)
                        {
                            hashTable[index]->_assets[i] = new AssetData(triangle);
                            inserted = true;
                        }
                        else if (hashTable[index]->_assets[i]->_asset == triangle->_asset)
                        {
                            if (hashTable[index]->_assets[i]->_firstTriangle == nullptr)
                                hashTable[index]->_assets[i]->_firstTriangle = new TriangleElement(triangle);
                            else insertIntoList(triangle, hashTable[index]->_assets[i]->_firstTriangle);
                            inserted = true;
                        }
                        if (inserted) break;
                    }
                }
                else
                {
                    destroy(hashTable[index]);
                    hashTable[index]->_timeInserted = currentTime;
                    hashTable[index]->_assets[0] = new AssetData(triangle);
                }
            }
        }
    }
}

void SpatialHash::insertIntoList(Triangle* triangle, TriangleElement* element)
{
    if (element->_triangle == triangle) return;
    if (element->_nextElement == nullptr)
        element->_nextElement = new TriangleElement(triangle);
    else(insertIntoList(triangle, element->_nextElement));
}

int SpatialHash::hash(int x, int y, int z)
{
    int result = (((x * P1) ^ (y * P2) ^ (z * P3)) % TABLE_SIZE);
    if (result < 0)
        result += TABLE_SIZE;
    return result;
}

glm::vec3 SpatialHash::getMax(Triangle* triangle)
{
    glm::vec3 max;

    max.x = glm::floor(glm::max(glm::max(triangle->_vertex0.x, triangle->_vertex1.x), triangle->_vertex2.x));
    max.y = glm::floor(glm::max(glm::max(triangle->_vertex0.y, triangle->_vertex1.y), triangle->_vertex2.y));
    max.z = glm::floor(glm::max(glm::max(triangle->_vertex0.z, triangle->_vertex1.z), triangle->_vertex2.z));

    return max;
}

glm::vec3 SpatialHash::getMin(Triangle* triangle)
{
    glm::vec3 min;

    min.x = glm::floor(glm::min(glm::min(triangle->_vertex0.x, triangle->_vertex1.x), triangle->_vertex2.x));
    min.y = glm::floor(glm::min(glm::min(triangle->_vertex0.y, triangle->_vertex1.y), triangle->_vertex2.y));
    min.z = glm::floor(glm::min(glm::min(triangle->_vertex0.z, triangle->_vertex1.z), triangle->_vertex2.z));

    return min;
}

void SpatialHash::destroy(HashElement* element)
{
    for (AssetData* &asset : element->_assets)
    {
        if (asset == nullptr) break;
        asset->_asset = nullptr;
        TriangleElement* currentElement = asset->_firstTriangle;
        TriangleElement* nextElement = currentElement->_nextElement;
        while (nextElement != nullptr)
        {
            currentElement->_nextElement = nullptr;
            currentElement->_triangle = nullptr;
            delete currentElement;
            currentElement = nextElement;
            nextElement = currentElement->_nextElement;
        }
        asset = nullptr;
    }
}

also, my Triangle and Asset header files:

#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

Asset.h

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

    double lastTime;
    glm::vec3 position;
private:
    void loadOBJ(const char* path);
};

#endif
\$\endgroup\$
1
\$\begingroup\$

I would like to make some suggestions on code improvements in general, if I may:

  • Prefer const or constexpr for compile time constants. The problems with macro constants are that they don't respect scope and can also be silently redefined, not to mention that they are very weakly typed.

  • Names starting with an underscore, while not wrong for a member variable of a class or struct, are reserved in some cases. I would advise agains their use because it is easy to slip such a name into the global namespace if you are accustomed with writing them in other places.

  • Make more use of const. Const is good for code self-documentation and can also help preventing programmer errors. I recommend that you read more about Const Correctness.

  • currentTime and timeInserted: These variables are referring to an amount of time, that is obvious enough, but how is someone supposed to know which time unit is being used? Without a comment or an indicative in the name, one can only guess... Seconds, milliseconds, microseconds? A comment would sure help, but also, when dealing with different units and scales, it is a very good idea to encode that information in the name. So lets assume you are using milliseconds, the variables could be renamed to currentTimeMs and timeInsertedMs, I've used the Ms suffix in this example, but you could very well use a full Milliseconds to make it cristal clear.

  • Still about the times though, you could also switch to the new <chrono> library and use the strongly typed time measurement objects instead.

  • Your code is relying too heavily on raw pointers. Just from looking at it, as an outsider to the project, it is very hard to tell which objects own which. I wouldn't be surprised if you have memory leaks going on over there. The use of standard smart pointers and standard containers would make your code a lot memory safer and easier to comprehend.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Awesome, thanks for the advice. I just learned about smart pointers the other day and haven't had a chance to really look into them. But once the semester is over that's on the list of things to learn. \$\endgroup\$ – ThomYorkkke Dec 2 '14 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.