Add Binary Partition structure

[yuripourre]

Octree structure where you can insert, remove and check collision between meshes.

E.g.: Moving Sphere/Capsule:
bsp.check(Vector3 oldPosition, Vector3 newPosition, radius);

Dynamic size is a must. If a triangle point or a particule is outside the root node (AABB) we need a bigger node. Recreate the tree.

Code can be found at propan-storage

• Insert Vector3
• Find Vector3
• Add a dynamic size tree
• Use gdx Bounding Box
  BB.intersect(bb) could be slower (don't use it).
• Create a triangle class
• Add Triangle to libgdx
• Calculate normal in constructor
• Port the intersection algorithm
• Update Intersector?
• Test it

[yuripourre]

One MVP idea would be having an octree and triangle insertion.

So you could have something like:

bsp.add(Triangle t);

For each node that triangle collides, you should perform insertion of the triangle.

Collision:
https://stackoverflow.com/a/17503268

bool IsIntersecting(IAABox box, ITriangle triangle)
{
    double triangleMin, triangleMax;
    double boxMin, boxMax;

    // Test the box normals (x-, y- and z-axes)
    var boxNormals = new IVector[] {
        new Vector(1,0,0),
        new Vector(0,1,0),
        new Vector(0,0,1)
    };
    for (int i = 0; i < 3; i++)
    {
        IVector n = boxNormals[i];
        Project(triangle.Vertices, boxNormals[i], out triangleMin, out triangleMax);
        if (triangleMax < box.Start.Coords[i] || triangleMin > box.End.Coords[i])
            return false; // No intersection possible.
    }

    // Test the triangle normal
    double triangleOffset = triangle.Normal.Dot(triangle.A);
    Project(box.Vertices, triangle.Normal, out boxMin, out boxMax);
    if (boxMax < triangleOffset || boxMin > triangleOffset)
        return false; // No intersection possible.

    // Test the nine edge cross-products
    IVector[] triangleEdges = new IVector[] {
        triangle.A.Minus(triangle.B),
        triangle.B.Minus(triangle.C),
        triangle.C.Minus(triangle.A)
    };
    for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
    {
        // The box normals are the same as it's edge tangents
        IVector axis = triangleEdges[i].Cross(boxNormals[j]);
        Project(box.Vertices, axis, out boxMin, out boxMax);
        Project(triangle.Vertices, axis, out triangleMin, out triangleMax);
        if (boxMax <= triangleMin || boxMin >= triangleMax)
            return false; // No intersection possible
    }

    // No separating axis found.
    return true;
}

void Project(IEnumerable<IVector> points, IVector axis,
        out double min, out double max)
{
    double min = double.PositiveInfinity;
    double max = double.NegativeInfinity;
    foreach (var p in points)
    {
        double val = axis.Dot(p);
        if (val < min) min = val;
        if (val > max) max = val;
    }
}

Reference (C++):
https://computergraphicsguide.blogspot.com/2015/09/speed-up-ray-casting-with-octrees.html?m=1

[yuripourre]

Implementation in details:
https://www.geeksforgeeks.org/octree-insertion-and-searching/

https://www.gamedev.net/tutorials/programming/general-and-gameplay-programming/introduction-to-octrees-r3529/

[yuripourre]

Better Intersection algorithm:
Based on real time algorithms book.
https://gist.github.com/zvonicek/fe73ba9903f49d57314cf7e8e0f05dcf