diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | balls.cpp | 72 | ||||
| -rw-r--r-- | balls.h | 49 | ||||
| -rw-r--r-- | layers.cpp | 67 | ||||
| -rw-r--r-- | vec.cpp | 2 |
5 files changed, 155 insertions, 37 deletions
@@ -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 @@ -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); } @@ -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; +} @@ -1,5 +1,3 @@ -#include <math.h> - #include "balls.h" Vector |