Open yuripourre opened 4 years ago
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
Better Intersection algorithm: Based on real time algorithms book. https://gist.github.com/zvonicek/fe73ba9903f49d57314cf7e8e0f05dcf
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