partition collisions

5 files changed, 155 insertions, 37 deletions

diff --git a/Makefile b/Makefile
index aac8508..7a26099 100644
--- a/Makefile
+++ b/Makefile
@@ -2,7 +2,7 @@ CC = g++
 CFLAGS = -Wall -pedantic
 LDFLAGS = -ltbb -lglut -lGLU -lGL
 
-balls: balls.o collision.o point.o vec.o
+balls: balls.o collision.o point.o vec.o layers.o
 	${CC} -o $@ $^ ${LDFLAGS}
 	@echo done
 
diff --git a/balls.cpp b/balls.cpp
index 22b9f0d..9743478 100644
--- a/balls.cpp
+++ b/balls.cpp
@@ -1,13 +1,5 @@
-#include <stdlib.h>
-#include <iostream>
-#include <GL/glut.h>
-#include <oneapi/tbb.h>
-
 #include "balls.h"
 
-using namespace std;
-using namespace oneapi::tbb;
-
 #define VMAX_INIT 0.05
 	/* max initial velocity [m/frame] */
 #define RMIN 0.05
@@ -38,7 +30,7 @@ void display(void);
 void drawBackground(void);
 void drawCircle(double radius, Point p, Color color);
 void reshape(int w, int h);
-vector<Ball> makeBalls(unsigned int n);
+vector<Ball *> makeBalls(int n);
 vector<Point> noOverlapCircles(unsigned int n);
 double mass(double radius);
 double volume(double radius);
@@ -47,7 +39,8 @@ Color randColor(void);
 
 const static Rectangle bounds = {{-1.5, -1.0}, {1.5, 1.0}};
 
-static vector<Ball> balls;
+vector<Ball *> balls;
+vector<vector<Collision>> collisions;
 
 int
 main(int argc, char *argv[]) {
@@ -71,6 +64,7 @@ main(int argc, char *argv[]) {
 	}
 
 	balls = makeBalls(nballs);
+	collisions = partitionCollisions(balls);
 
 	glutTimerFunc(FRAME_TIME_MS, animate, 0);
 
@@ -90,8 +84,8 @@ display(void) {
 	glClearColor(0, 0, 0, 1);
 	glClear(GL_COLOR_BUFFER_BIT);
 	drawBackground();
-	for (Ball b : balls)
-		drawCircle(b.r, b.p, b.color);
+	for (const Ball *b : balls)
+		drawCircle(b->r, b->p, b->color);
 
 	glutSwapBuffers();
 }
@@ -139,21 +133,30 @@ reshape(int w, int h) {
 	glMatrixMode(GL_MODELVIEW);
 }
 
-/* return n-length vector of Balls with random attributes */
-vector<Ball>
-makeBalls(unsigned int n) {
-	vector<Ball> balls(n);
+
+vector<Ball *>
+makeBalls(int n) {
+	size_t i;
+
 	vector<Point> positions = noOverlapCircles(n);
 	
-	parallel_for(size_t(0), balls.size(), [&balls, positions] (size_t i) {
+	vector<Ball *> balls(n);
+	for(i = 0; i < balls.size(); i++) {
 		cout << "Creating ball " << i << "\n";
-		balls[i].p = positions[i];
-		balls[i].v.x = randDouble(-VMAX_INIT, VMAX_INIT);
-		balls[i].v.y = randDouble(-VMAX_INIT, VMAX_INIT);
-		balls[i].r = randDouble(RMIN, RMAX);
-		balls[i].m = mass(balls[i].r);
-		balls[i].color = randColor();
-	});
+		if ((balls[i] = (Ball *) malloc(sizeof(Ball))) == NULL) {
+			cerr << "failed to allocate ball\n";
+			while (i-- > 0)
+				free(balls[i]);
+			exit(1);
+		}
+		
+		balls[i]->p = positions[i];
+		balls[i]->v.x = randDouble(-VMAX_INIT, VMAX_INIT);
+		balls[i]->v.y = randDouble(-VMAX_INIT, VMAX_INIT);
+		balls[i]->r = randDouble(RMIN, RMAX);
+		balls[i]->m = mass(balls[i]->r);
+		balls[i]->color = randColor();
+	};
 	return balls;
 }
 
@@ -193,21 +196,22 @@ volume(double radius) {
 
 void
 animate(int v) {
-	size_t i, j;
-
 	/* TODO: parallel */
-	for (Ball &ball : balls) {
-		ball.v.y -=G;
-		ball.p = ptAddVec(ball.p, ball.v);
+	for (Ball *ball : balls) {
+		ball->v.y -=G;
+		ball->p = ptAddVec(ball->p, ball->v);
 	}
 
-	/* TODO: parallel */
-	for (i = 0; i < balls.size(); i++) {
-		for (j = i+1; j < balls.size(); j++)
-			collideBall(&balls[i], &balls[j]);
-		collideWall(&balls[i], bounds);
+	for (vector<Collision> layer : collisions) {
+		/* TODO: parallelize */
+		for (Collision c : layer) {
+			collideBall(c.b1, c.b2);
+		}
 	}
 
+	for (Ball *ball : balls)
+		collideWall(ball, bounds);
+
 	display();
 	glutTimerFunc(FRAME_TIME_MS, animate, 0);
 }
diff --git a/balls.h b/balls.h
index 3d0202c..b908183 100644
--- a/balls.h
+++ b/balls.h
@@ -1,3 +1,14 @@
+#include <stdlib.h>
+#include <iostream>
+#include <math.h>
+#include <GL/glut.h>
+#include <oneapi/tbb.h>
+#include <oneapi/tbb/flow_graph.h>
+
+using namespace std;
+using namespace oneapi::tbb;
+using namespace oneapi::tbb::flow;
+
 typedef struct {
 	double x, y;
 } Point;
@@ -22,6 +33,44 @@ typedef struct {
 	Color color;
 } Ball;
 
+typedef continue_node<continue_msg> node_t;
+typedef const continue_msg & msg_t;
+
+class Collision {
+public:
+	Ball *b1, *b2;
+
+	Collision(Ball *_b1, Ball *_b2) {
+		b1 = _b1;
+		b2 = _b2;
+	}
+
+	friend bool operator<(const Collision& a, const Collision& b) {
+		return a.b1 < b.b1 || a.b2 < b.b2;
+	}
+
+	friend bool operator==(const Collision& a, const Collision& b) {
+		return a.b1 == b.b1 && a.b2 == b.b2;
+	}
+
+	friend ostream &operator<<(ostream& os, Collision const & c) {
+		return os << "(" << c.b1 << ", " << c.b2 << ")";
+	}
+};
+
+class CollisionGraph {
+private:
+	graph g;
+	node_t root;
+	vector<vector<reference_wrapper<node_t>>> layers;
+
+public:
+	CollisionGraph(void);
+	void run();
+};
+
+vector<vector<Collision>> partitionCollisions(vector<Ball *> balls);
+
 Point addPt(Point p, Point q);
 Point subPt(Point p, Point q);
 Point ptAddVec(Point p, Vector v);
diff --git a/layers.cpp b/layers.cpp
new file mode 100644
index 0000000..f8b3afd
--- /dev/null
+++ b/layers.cpp
@@ -0,0 +1,67 @@
+#include "balls.h"
+
+static vector<Collision> completeGraph(vector<Ball *> balls);
+static vector<Collision> matching(vector<Collision> edges);
+static vector<Collision> diff(vector<Collision> a, vector<Collision> b);
+
+vector<vector<Collision>>
+partitionCollisions(vector<Ball *> balls) {
+	vector<vector<Collision>> layers;
+
+	vector<Collision> collisions = completeGraph(balls);
+	while (!collisions.empty()) {
+		cout << "\nadd layer\n";
+		cout << "layers.size(): " << layers.size() << "\n";
+
+		vector<Collision> layerCollisions = matching(collisions);
+		cout << "layer collisions: ";
+		for (Collision c : layerCollisions)
+			cout << c << " ";
+		cout << "\n";
+		collisions = diff(collisions, layerCollisions);
+
+		vector<Collision> thisLayer;
+		for (Collision c : layerCollisions) {
+			cout << "create node with " << c << "\n";
+			thisLayer.push_back(c);
+		}
+		cout << "thisLayer.size(): " << thisLayer.size() << "\n";
+		layers.push_back(thisLayer);
+	}
+	return layers;
+}
+
+static vector<Collision>
+completeGraph(vector<Ball *> balls) {
+	vector<Collision> edges;
+	size_t i, j;
+
+	for (i = 0; i < balls.size(); i++)
+		for (j = i+1; j < balls.size(); j++)
+			edges.push_back(Collision(balls.at(i), balls.at(j)));
+	return edges;
+}
+
+static vector<Collision>
+matching(vector<Collision> edges) {
+	vector<Collision> matching;
+	size_t i;
+
+	for (Collision e : edges) {
+		for (i = 0; i < matching.size(); i++)
+			if (e.b1 == matching[i].b1 || e.b1 == matching[i].b2 || e.b2 == matching[i].b1 || e.b2 == matching[i].b2)
+				break;
+		if (i == matching.size()) /* no shared vertices */
+			matching.push_back(e);
+	}
+	return matching;
+}
+
+static vector<Collision>
+diff(vector<Collision> a, vector<Collision> b) {
+	vector<Collision> diff;
+	set_difference(a.begin(), a.end(),
+		b.begin(), b.end(),
+		inserter(diff, diff.begin()));
+	return diff;
+}
diff --git a/vec.cpp b/vec.cpp
index a9b78e9..a0b50e3 100644
--- a/vec.cpp
+++ b/vec.cpp
@@ -1,5 +1,3 @@
-#include <math.h>
-
 #include "balls.h"
 
 Vector