0
\$\begingroup\$

I am attempting to make split axis theorem for 2d collision physics. It does works, but is inaccurate. It is based off of: https://www.gamedev.net/tutorials/programming/math-and-physics/a-verlet-based-approach-for-2d-game-physics-r2714/

A video for reference: https://www.youtube.com/watch?v=edSN3_Xkkls

Here is the physics class:

class Physics {
int pointCount = 0;
Point* vertices[MAX_VERTICES];
int edgeCount = 0;
Edge* edges[MAX_EDGES];
PhysicsBody* PhysicsBodies[MAX_BODIES];
int bodyCount = 0;

float timestep = 1.0;
// The 'Depth' is the length of the vector, the 'Normal' is the direction of the vector discussed above. 
struct {
    float Depth;
    sf::Vector2f Normal;

    Edge* E;
    Point* V;
} CollisionInfo;
public:

void Update();
void UpdateForces();
void updateVerlet();
void updateEdges();
void ProcessCollision();
void IterateCollisions();
void renderPoints(sf::RenderWindow& window);
void MakeShape(std::vector<sf::Vector2f> points, bool anchored);
bool DetectCollision(PhysicsBody* B1, PhysicsBody* B2);
float IntervalDistance(float MinA, float MaxA, float MinB, float MaxB);
};

Here is the point class:

struct Point {
sf::Vector2f Position;
sf::Vector2f OldPosition;
sf::Vector2f Acceleration;
};

Here is the edge class:

struct Edge {
Point* v1;
Point* v2;

float OriginalLength; // The length of the edge when it was created

PhysicsBody* Parent; // The physics body that it belongs to
};

Here is the detect collision function:

bool Physics::DetectCollision(PhysicsBody* B1, PhysicsBody* B2) {

float MinDistance = 10000.0f;
// Iterates through all edges of both bodies at once
for (int i = 0; i < B1->EdgeCount + B2->EdgeCount; i++) {
    Edge* E;
    if (i < B1->EdgeCount) {
        E = B1->edges[i];
        E->v1 = B1->edges[i]->v1;
        E->v2 = B1->edges[i]->v2;
    }
    else {
        E = B2->edges[i - B1->EdgeCount];
    }

    // Calculate the axis perpendicular to this edge and normalize
    //printPosition(E->v1->Position.x, E->v1->Position.y);
    //printPosition(E->v2->Position.x, E->v2->Position.y);
    sf::Vector2f Axis(E->v1->Position.y - E->v2->Position.y, E->v2->Position.x - E->v1->Position.y);
    float AxisN = Normalize(Axis);
    
    float MinA, MinB, MaxA, MaxB;
    B1->ProjectToAxis(Axis, MinA, MaxA);
    B2->ProjectToAxis(Axis, MinB, MaxB);

    float Distance = IntervalDistance(MinA, MaxA, MinB, MaxB);

    if (Distance > 0.0f) {
        return false; //If the intervals don't overlap, return false, since there is no collision
    }
    // If the intervals overlap, check, whether the vector length on this
    //edge is smaller than the smallest length that has been reported so far
    else if (abs(Distance) < MinDistance) {
        MinDistance = abs(Distance);

        CollisionInfo.Normal = Axis; //Save collision information for later
        CollisionInfo.E = E; //Store the edge, as it is the collision edge
    }
}

CollisionInfo.Depth = MinDistance;

// Ensure that the body containing the collision edge lies in
//B2 and the one containing the collision vertex in B1
// doesn't have an edge set to it 
if (CollisionInfo.E->Parent != B2) {
    PhysicsBody* Temp = B2;
    B2 = B1;
    B1 = Temp;
}

//This is needed to make sure that the collision normal is pointing at B1
int Sign = SGN(CollisionInfo.Normal.x * (B1->Center.x - B2->Center.x));

//Remember that the line equation is N*( R - R0 ). We choose B2->Center
//as R0; the normal N is given by the collision normal

if (Sign != 1)
    CollisionInfo.Normal = -CollisionInfo.Normal; //Revert the collision normal if it points away from B1


float SmallestD = 100000.0f; //Initialize the smallest distance to a high value
for (int I = 0; I < B1->VertexCount; I++) {
    //Measure the distance of the vertex from the line using the line equation
    float Distance = distanceBetweenPoints(CollisionInfo.Normal, (B1->vertices[I]->Position - B2->Center));
    //If the measured distance is smaller than the smallest distance reported
    //so far, set the smallest distance and the collision vertex
    if (Distance < SmallestD) {
        SmallestD = Distance;
        CollisionInfo.V = B1->vertices[I];
    }
}

return true; //There is no separating axis. Report a collision!
}

I tried changing the Min = std::min(DotP, Min); & Min = std::min(DotP, Min); to Min = FLT_MAX, Max = FLT_MIN; but this only made the problem worse.

Here is the project to axis function:

void PhysicsBody::ProjectToAxis(sf::Vector2f& Axis, float& Min, float& Max) {

float DotP = dotProduct(Axis, vertices[0]->Position);
// set min and max to the project of the first vertex
Min = Max = DotP;

for (int i = 1; i < VertexCount; i++) {
    // Project the rest of the vertices onto the axis and extend
    // The interval to left and right if necessary
    float DotP = dotProduct(Axis, vertices[1]->Position);

    //Min = FLT_MAX, Max = FLT_MIN;

    Min = std::min(DotP, Min);
    Max = std::max(DotP, Max);
}
/*
As you can see, projection in 2D is simply a dot product of the projection axis and the point we want to project.
*/
}

Here is the SGN function:

inline bool SGN(float x) {
if (x > 0) return 1;
if (x < 0) return -1;
return 0;
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ SAT is for convex shapes. In the second run, when the top shape square shape twists into an hour glass, it is no longer convex. \$\endgroup\$
    – Pikalek
    Nov 24, 2023 at 15:35

1 Answer 1

0
\$\begingroup\$

The following code provides a convex shape to the algorithm by re-ordering the vertices per major axis prior to implementation.

    // Calculate the axis perpendicular to this edge and normalize
    sf::Vector2f Axis(Max(E->v1->Position.y, E->v2->Position.y) - 
                      Min(E->v1->Position.y, E->v2->Position.y),
                      Max(E->v1->Position.x, E->v2->Position.x) - 
                      Min(E->v1->Position.x, E->v2->Position.x));
    float AxisN = Normalize(Axis);
\$\endgroup\$
2
  • 1
    \$\begingroup\$ What does min & max do? Isn't it supposed to take 2 arguments, not one? \$\endgroup\$ Dec 10, 2023 at 22:36
  • \$\begingroup\$ @NoStepOnSnek Corrected. \$\endgroup\$
    – agone
    Dec 12, 2023 at 20:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .