Separating axis theorem implementation

4 files changed, 103 insertions, 0 deletions

diff --git a/frontend/2d/_collisions/rectangle_rectangle.html b/frontend/2d/_collisions/rectangle_rectangle.html
index 03829ce..8b10ab6 100644
--- a/frontend/2d/_collisions/rectangle_rectangle.html
+++ b/frontend/2d/_collisions/rectangle_rectangle.html
@@ -119,6 +119,7 @@ Vector2 getNormalToLineSegment(LineSegment* segment) {
     <footer id="references">
       <h2>References</h2>
       <ul>
+		<li><a href="https://dyn4j.org/2010/01/sat/">Great SAT Explanation</a></li>
       </ul>
     </footer>
   </section>
diff --git a/frontend/2d/_collisions/rectangle_rectangle.html.content b/frontend/2d/_collisions/rectangle_rectangle.html.content
index 30e34d8..b994f45 100644
--- a/frontend/2d/_collisions/rectangle_rectangle.html.content
+++ b/frontend/2d/_collisions/rectangle_rectangle.html.content
@@ -69,6 +69,7 @@ Vector2 getNormalToLineSegment(LineSegment* segment) {
     <footer id="references">
       <h2>References</h2>
       <ul>
+		<li><a href="https://dyn4j.org/2010/01/sat/">Great SAT Explanation</a></li>
       </ul>
     </footer>
   </section>
diff --git a/frontend/2d/_collisions/rectangle_rectangle/dist/output.wasm b/frontend/2d/_collisions/rectangle_rectangle/dist/output.wasm
index 951a3b6..9038de5 100755
--- a/frontend/2d/_collisions/rectangle_rectangle/dist/output.wasm
+++ b/frontend/2d/_collisions/rectangle_rectangle/dist/output.wasm
diff --git a/frontend/2d/_collisions/rectangle_rectangle/main.cpp b/frontend/2d/_collisions/rectangle_rectangle/main.cpp
index eda76d4..b4e307e 100644
--- a/frontend/2d/_collisions/rectangle_rectangle/main.cpp
+++ b/frontend/2d/_collisions/rectangle_rectangle/main.cpp
@@ -103,6 +103,41 @@ struct Rectangle {
 	void unload() {
 		shape.unload();
 	}
+
+	// Note that these getters are needlessly verbose for demonstration's sake
+	void getPoints(Vector2* pointList) {
+		Vector2 botLeft = shape.model * Vector2 { -width / 2.f, -height / 2.f };
+		Vector2 topLeft = shape.model * Vector2 { -width / 2.f, height / 2.f };
+		Vector2 topRight = shape.model * Vector2 { width / 2.f, height / 2.f };
+		Vector2 botRight = shape.model * Vector2 { width / 2.f, -height / 2.f };
+
+		pointList[0] = botLeft;
+		pointList[1] = topLeft;
+		pointList[2] = topRight;
+		pointList[3] = botRight;
+	}
+
+    void getEdges(Vector2* edgeList) {
+		Vector2 pointsList[4];
+		getPoints(pointsList);
+
+		for (int i = 0; i < 4; i++) {
+			if (i + 1 == 4) {
+				edgeList[i] =  pointsList[i] - pointsList[0];
+			} else {
+				edgeList[i] =  pointsList[i] - pointsList[i + 1];
+			}
+		}
+	}
+
+	void getNormals(Vector2* normalList) {
+		Vector2 edgeList[4];
+		getEdges(edgeList);
+
+		for (int i = 0; i < 4; i++) {
+			normalList[i] = edgeList[i].getPerp().normalize();
+		}
+	}
 };
 
 
@@ -149,11 +184,67 @@ void load() {
     mainLoop.run(update);
 }
 
+Vector2 getProjection(Vector2* vertices, Vector2 axis) {
+	float32 min = axis.dot(vertices[0]);
+	float32 max = min;
+
+	for (int v = 1; v < 4; v++) {
+		float32 d = axis.dot(vertices[v]);
+
+		if (d < min) {
+			min = d;
+		} else if (d > max) {
+			max = d;
+		}
+	}
+
+	return Vector2 { min, max };
+}
+
+bool projectionsOverlap(Vector2 first, Vector2 second) {
+	return first.x <= second.y && second.x <= first.y;
+}
 
 const float32 EPSILON = 1.f;
 IntersectionResult getIntersection(Rectangle* first, Rectangle* second) {
 	IntersectionResult ir;
 
+	// For two rectangles to overlap, it means that at least one of the corners of one is inside of the other
+	Vector2 firstNormals[4];
+	first->getNormals(firstNormals);
+	Vector2 firstPoints[4];
+	first->getPoints(firstPoints);
+
+	Vector2 secondNormals[4];
+	second->getNormals(secondNormals);
+	Vector2 secondPoints[4];
+    second->getPoints(secondPoints);
+
+	for (int i = 0; i < 4; i++) {
+		Vector2 normal = firstNormals[i];
+
+	    Vector2 firstProj = getProjection(firstPoints, normal);
+		Vector2 secondProj = getProjection(secondPoints, normal);
+
+		if (!projectionsOverlap(firstProj, secondProj)) {
+			return ir;
+		}
+	}
+
+	for (int i = 0; i < 4; i++) {
+		Vector2 normal = secondNormals[i];
+
+	    Vector2 firstProj = getProjection(firstPoints, normal);
+		Vector2 secondProj = getProjection(secondPoints, normal);
+
+		if (!projectionsOverlap(firstProj, secondProj)) {
+			return ir;
+		}
+	}
+
+	printf("We are overlapping\n");
+	
+
 	return ir;
 }
 
@@ -183,6 +274,16 @@ void update(float32 deltaTimeSeconds, void* userData) {
 		rectangleList[r].update(deltaTimeSeconds);
 	}
 
+	// Check collisions
+	for (int i = 0; i < 4; i++) {
+		Rectangle* first = &rectangleList[i];
+		for (int j = i + 1; j < 4; j++) {
+			Rectangle* second = &rectangleList[j];
+			
+			IntersectionResult ir = getIntersection(first, second);
+		}
+	}
+
 	/*for (int32 segmentIndex = 0; segmentIndex < 4; segmentIndex++) {
 		IntersectionResult ir = getIntersection(&rectangle, &segmentList[segmentIndex]);
 		if (!ir.intersect) {