From 30b579c8ce41c105392c436880612a0e9057880f Mon Sep 17 00:00:00 2001 From: Sam Anthony Date: Wed, 9 Oct 2024 09:26:26 -0400 Subject: partition collisions --- Makefile | 2 +- balls.cpp | 72 +++++++++++++++++++++++++++++++++----------------------------- balls.h | 49 ++++++++++++++++++++++++++++++++++++++++++ layers.cpp | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ vec.cpp | 2 -- 5 files changed, 155 insertions(+), 37 deletions(-) create mode 100644 layers.cpp 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 -#include -#include -#include - #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 makeBalls(unsigned int n); +vector makeBalls(int n); vector 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 balls; +vector balls; +vector> 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 -makeBalls(unsigned int n) { - vector balls(n); + +vector +makeBalls(int n) { + size_t i; + vector positions = noOverlapCircles(n); - parallel_for(size_t(0), balls.size(), [&balls, positions] (size_t i) { + vector 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 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 +#include +#include +#include +#include +#include + +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 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>> layers; + +public: + CollisionGraph(void); + void run(); +}; + +vector> partitionCollisions(vector 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 completeGraph(vector balls); +static vector matching(vector edges); +static vector diff(vector a, vector b); + +vector> +partitionCollisions(vector balls) { + vector> layers; + + vector collisions = completeGraph(balls); + while (!collisions.empty()) { + cout << "\nadd layer\n"; + cout << "layers.size(): " << layers.size() << "\n"; + + vector layerCollisions = matching(collisions); + cout << "layer collisions: "; + for (Collision c : layerCollisions) + cout << c << " "; + cout << "\n"; + collisions = diff(collisions, layerCollisions); + + vector 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 +completeGraph(vector balls) { + vector 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 +matching(vector edges) { + vector 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 +diff(vector a, vector b) { + vector 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 - #include "balls.h" Vector -- cgit v1.2.3