placing white holes, and changed to n-body gravitational pull instead of
[ld42_outofspace] / src / gamescr.cc
index 032b3b9..4bac184 100644 (file)
@@ -6,11 +6,14 @@
 #include "opengl.h"
 #include "texture.h"
 #include "sdr.h"
+#include "mesh.h"
+#include "meshgen.h"
+#include "goatkit/goatkit.h"
 
 /* NOTES:
  * - whistle hhgg music
- * - colliding particles merge
  * - select objects and center camera on them
+ * - we need to rely on actual collisions instead of grid occupancy
  */
 
 struct Particle {
@@ -18,6 +21,10 @@ struct Particle {
        float mass;
        Vec2 pos;
        Vec2 vel;
+
+       float vis_height;
+
+       Particle *next, *prev;
 };
 
 struct Emitter {
@@ -25,6 +32,8 @@ struct Emitter {
        float mass;
        float rate, chunk;
        float angle, spread;
+
+       float spawn_pending;
 };
 
 struct Rect {
@@ -45,7 +54,7 @@ struct QuadMesh {
 #define SIM_DT         0.016
 
 #define GRID_SIZE      2048
-#define GRID_BITS      12
+#define GRID_BITS      11
 #define GRID_X(idx)    (((idx) >> GRID_BITS) & (GRID_SIZE - 1))
 #define GRID_Y(idx)    ((idx) & (GRID_SIZE - 1))
 #define GRID_DELTA     ((float)FIELD_SIZE / (float)GRID_SIZE)
@@ -54,40 +63,83 @@ struct QuadMesh {
 #define MIN_CAM_DIST   1.0f
 #define MAX_CAM_DIST   350.0f
 
-#define MASS_TO_RAD(m) log((m) + 1.0)
+#define MASS_TO_RADIUS(m)      log((m) + 1.0)
 
 #define CONTRIB_THRES  0.005
 #define CONTRIB_RANGE(m) sqrt((m) / CONTRIB_THRES)
 
+/* gravitational strength */
+#define GRAV_STR       16.0f
+
+#define INIT_MASS_BUDGET       600.0f
+#define EM_MASS_DEFAULT                100.0f
+
+static int pos_to_grid_x_noclamp(float x);
+static int pos_to_grid_y_noclamp(float y);
 static int pos_to_grid(float x, float y);
 static Vec2 grid_to_pos(int gx, int gy);
 
+static void calc_contrib_bounds(const Vec2 &pos, float mass, Rect *rect);
+static void add_influence(const Vec2 &pos, float mass, float radius, const Rect &cbox);
+
+static Vec2 calc_field_grad(int gidx);
+
 static void destroy_quadmesh(QuadMesh *m);
 static void draw_quadmesh(const QuadMesh *m, unsigned int prim = GL_QUADS);
 static void gen_quad_plane(QuadMesh *mesh, float width, float height, int usub, int vsub);
 
+static void spawn_particle(const Vec2 &pos, const Vec2 &vel, float mass);
+static void add_particle(Particle *p);
+static void remove_particle(Particle *p);
+static Particle *alloc_particle();
+void free_particle(Particle *p);
+
+static bool pause;
+
 static float grid[GRID_SIZE * GRID_SIZE];
-static Particle grid_part[GRID_SIZE * GRID_SIZE];
+static Particle *grid_part[GRID_SIZE * GRID_SIZE];
 static Texture *grid_tex;
 
+static Particle *plist;
+
 static std::vector<Emitter*> emitters;
 
 static Texture *gvis_tex;      // texture tile for visualizing a grid
 static unsigned int field_sdr;
-static int tess_level = 32;
+static int tess_level = 64;
 static float field_scale = 16.0f;
 
 static QuadMesh field_mesh;
 
+static Mesh *pmesh;
+static unsigned int particle_sdr;
+
+static Vec2 cam_pos;
 static float cam_theta;
 static float cam_dist = 100.0f;
-static Vec2 *targ_pos;
+static Vec2 *targ_pos = &cam_pos;
 static Mat4 view_matrix, proj_matrix;
 
+static bool wireframe;
+static int mouse_x, mouse_y;
+
 // emitter placement data (filled by event handlers, completed in update)
 static bool emit_place_pending;
 static Vec2 emit_place_pos;
 
+static bool placing_emitter;
+
+static float mass_left;
+
+// UI
+static void ui_handler(goatkit::Widget *w, const goatkit::Event &ev, void *cls);
+static int ui_virt_width = 800;
+static int ui_virt_height = 600;
+static goatkit::Screen *ui;
+static goatkit::Button *bn_emitter;
+static goatkit::Slider *slider_mass;
+static bool mouse_over_ui;
+
 
 bool GameScreen::init()
 {
@@ -121,9 +173,35 @@ bool GameScreen::init()
 
        gen_quad_plane(&field_mesh, FIELD_SIZE, FIELD_SIZE, 32, 32);
 
-       // XXX DBG
-       emit_place_pos = Vec2(0, 0);
-       emit_place_pending = true;
+       pmesh = new Mesh;
+       gen_geosphere(pmesh, 1.0, 2);
+
+       if(!(particle_sdr = create_program_load("sdr/sph.v.glsl", "sdr/sph.p.glsl"))) {
+               return false;
+       }
+
+       mass_left = INIT_MASS_BUDGET;
+
+       ui = new goatkit::Screen;
+       ui->hide();
+
+       bn_emitter = new goatkit::Button;
+       bn_emitter->set_position(5, 5);
+       bn_emitter->set_size(250, 30);
+       bn_emitter->set_text("new white hole");
+       bn_emitter->set_callback(goatkit::EV_CLICK, ui_handler);
+       ui->add_widget(bn_emitter);
+
+       slider_mass = new goatkit::Slider;
+       slider_mass->set_position(300, 5);
+       slider_mass->set_size(400, 30);
+       slider_mass->set_continuous_change(false);
+       slider_mass->set_range(0, mass_left);
+       slider_mass->set_value(EM_MASS_DEFAULT);
+       slider_mass->set_callback(goatkit::EV_CHANGE, ui_handler);
+       ui->add_widget(slider_mass);
+
+       ui->set_visibility_transition(300);
 
        assert(glGetError() == GL_NO_ERROR);
        return true;
@@ -135,66 +213,162 @@ void GameScreen::destroy()
        delete gvis_tex;
        delete grid_tex;
        destroy_quadmesh(&field_mesh);
+       delete pmesh;
+
+       delete bn_emitter;
 }
 
-static void calc_contrib_bounds(const Emitter *em, Rect *rect)
+void GameScreen::start()
 {
-       int gidx = pos_to_grid(em->pos.x, em->pos.y);
-       int gx = GRID_X(gidx);
-       int gy = GRID_Y(gidx);
-       int maxrange = (int)ceil(CONTRIB_RANGE(em->mass));
-
-       int sx = gx - maxrange;
-       int sy = gy - maxrange;
-       int ex = gx + maxrange;
-       int ey = gy + maxrange;
-
-       if(ex > GRID_SIZE) ex = GRID_SIZE;
-       if(ey > GRID_SIZE) ey = GRID_SIZE;
+       ui->show();
+       slider_mass->hide();
+}
 
-       rect->x = sx < 0 ? 0 : sx;
-       rect->y = sy < 0 ? 0 : sy;
-       rect->width = ex - sx;
-       rect->height = ey - sy;
+void GameScreen::stop()
+{
 }
 
 static void simstep()
 {
-       // calculate gravitational field - assume field within radius constant: m / r^2
+       if(pause) return;
+
+       // distribute forces
+       Particle *p = plist;
+       while(p) {
+               int num_emitters = emitters.size();
+               for(int i=0; i<num_emitters; i++) {
+                       Emitter *em = emitters[i];
+                       Vec2 dir = p->pos - em->pos;
+                       p->vel += dir * em->mass * GRAV_STR * 0.01 / dot(dir, dir) * SIM_DT;
+               }
 
-       // first clear the field, and then add contributions
-       memset(grid, 0, sizeof grid);
+               Particle *q = plist;
+               while(q) {
+                       if(p != q) {
+                               Vec2 dir = q->pos - p->pos;
+                               float accel = GRAV_STR * q->mass / dot(dir, dir);
+                               p->vel += dir * accel * SIM_DT;
+                       }
+                       q = q->next;
+               }
+               p = p->next;
+       }
 
-       // contribution of emitters
+       // move existing particles
+       p = plist;
+       while(p) {
+               // calculate the field gradient at the particle position
+               int gidx = pos_to_grid(p->pos.x, p->pos.y);
+               //Vec2 grad = calc_field_grad(gidx) * GRAV_STR;
+
+               //p->vel += grad * SIM_DT;
+               p->pos += p->vel * SIM_DT;
+
+               // if it moved outside of the simulation field, remove it
+               int gx = pos_to_grid_x_noclamp(p->pos.x);
+               int gy = pos_to_grid_y_noclamp(p->pos.y);
+               if(gx < 0 || gx >= GRID_SIZE || gy < 0 || gy >= GRID_SIZE) {
+                       Particle *next = p->next;
+                       grid_part[gidx] = 0;
+                       remove_particle(p);
+                       free_particle(p);
+                       p = next;
+                       continue;
+               }
+
+               // find the grid cell it's moving to
+               int gidx_next = pos_to_grid(p->pos.x, p->pos.y);
+               p->vis_height = 0.0f;//-grid[gidx_next] * field_scale;
+
+               if(gidx_next == gidx) {
+                       p = p->next;
+                       continue;
+               }
+
+               Particle *destp = grid_part[gidx_next];
+               if(destp) {
+                       assert(destp != p);
+                       // another particle at the destination, merge them
+                       destp->vel += p->vel;
+                       destp->mass += p->mass;
+                       destp->radius = MASS_TO_RADIUS(destp->mass);
+
+                       // ... and remove it
+                       grid_part[gidx] = 0;
+                       Particle *next = p->next;
+                       remove_particle(p);
+                       free_particle(p);
+                       p = next;
+               } else {
+                       // destination is empty, go there
+                       if(gidx != gidx_next) {
+                               grid_part[gidx] = 0;
+                               grid_part[gidx_next] = p;
+                       }
+
+                       p = p->next;
+               }
+       }
+
+       // TODO destroy particles which left the simulation field
+
+       // spawn particles
        int num_emitters = emitters.size();
        for(int i=0; i<num_emitters; i++) {
                Emitter *em = emitters[i];
-               Rect cbox;
-               calc_contrib_bounds(em, &cbox);
-               float emradius = MASS_TO_RAD(em->mass);
+               em->spawn_pending += em->rate * SIM_DT;
+               while(em->spawn_pending >= 1.0f && em->mass > 0.0f) {
+                       Vec2 pvel;      // XXX calc eject velocity
 
-               float *gptr = grid + cbox.y * GRID_SIZE + cbox.x;
-               Vec2 startpos = grid_to_pos(cbox.x, cbox.y);
+                       float angle = (float)rand() / (float)RAND_MAX * (M_PI * 2.0);
+                       float emradius = MASS_TO_RADIUS(em->mass);
+                       Vec2 ppos = em->pos + Vec2(cos(angle), sin(angle)) * emradius * 1.00001;
 
-               for(int y=0; y<cbox.height; y++) {
-                       for(int x=0; x<cbox.width; x++) {
-                               Vec2 cellpos = Vec2(startpos.x + (float)x * GRID_DELTA, startpos.y);
+                       float pmass = em->chunk > em->mass ? em->mass : em->chunk;
+                       spawn_particle(ppos, pvel, pmass);
+                       em->mass -= pmass;
 
-                               Vec2 dir = cellpos - em->pos;
-                               float dsq = dot(dir, dir);
-                               float radsq = emradius * emradius;
-                               if(dsq < radsq) {
-                                       dsq = radsq;
-                               }
-
-                               gptr[x] -= em->mass / dsq;
-                       }
+                       em->spawn_pending -= 1.0f;
+               }
+       }
 
-                       startpos.y += GRID_DELTA;
-                       gptr += GRID_SIZE;
+       // remove dead emitters
+       std::vector<Emitter*>::iterator it = emitters.begin();
+       while(it != emitters.end()) {
+               Emitter *em = *it;
+
+               if(em->mass <= 0.0f) {
+                       printf("emitter depleted\n");
+                       it = emitters.erase(it);
+                       delete em;
+               } else {
+                       it++;
                }
        }
 
+       // calculate gravitational field - assume field within radius constant: m / r^2
+       // first clear the field, and then add contributions
+       memset(grid, 0, sizeof grid);
+
+       // contribution of emitters
+       for(int i=0; i<num_emitters; i++) {
+               Emitter *em = emitters[i];
+               Rect cbox;
+               calc_contrib_bounds(em->pos, em->mass, &cbox);
+               float emradius = MASS_TO_RADIUS(em->mass);
+
+               add_influence(em->pos, -em->mass, emradius, cbox);
+       }
+
+       // contribution of particles
+       p = plist;
+       while(p) {
+               Rect cbox;
+               calc_contrib_bounds(p->pos, p->mass, &cbox);
+               add_influence(p->pos, p->mass, p->radius, cbox);
+               p = p->next;
+       }
+
        // update texture
        assert(glGetError() == GL_NO_ERROR);
        grid_tex->bind();
@@ -205,19 +379,43 @@ static void simstep()
 
 static void update()
 {
+       if(placing_emitter) {
+               float x = (float)mouse_x / (float)win_width;
+               float y = 1.0f - (float)mouse_y / (float)win_height;
+               Ray pick_ray = mouse_pick_ray(x, y, view_matrix, proj_matrix);
+
+               float ndotdir = pick_ray.dir.y;
+               if(fabs(ndotdir) > 1e-6f) {
+                       float ndotpdir = -pick_ray.origin.y;
+                       float t = ndotpdir / ndotdir;
+
+                       x = pick_ray.origin.x + pick_ray.dir.x * t;
+                       y = pick_ray.origin.z + pick_ray.dir.z * t;
+
+                       if(x >= -FIELD_SIZE / 2 && x < FIELD_SIZE / 2 &&
+                                       y >= -FIELD_SIZE / 2 && y < FIELD_SIZE / 2) {
+                               emit_place_pos = Vec2(x, y);
+                       }
+               }
+       }
+
        if(emit_place_pending) {
                emit_place_pending = false;
                Emitter *em = new Emitter;
                em->pos = emit_place_pos;
-               em->mass = 100;
-               em->rate = 1;
-               em->chunk = 0.05;
+               em->mass = slider_mass->get_value();
+               em->rate = 10;
+               em->chunk = 0.001 * em->mass;
                em->angle = -1;
                em->spread = 0;
+               em->spawn_pending = 0;
                emitters.push_back(em);
 
+               mass_left -= em->mass;
+               if(mass_left < 0.0f) mass_left = 0.0f;
+
                Rect cbox;
-               calc_contrib_bounds(em, &cbox);
+               calc_contrib_bounds(em->pos, em->mass, &cbox);
                printf("bounds: %d,%d %dx%d\n", cbox.x, cbox.y, cbox.width, cbox.height);
        }
 
@@ -259,29 +457,88 @@ void GameScreen::draw()
        glMatrixMode(GL_MODELVIEW);
        glLoadMatrixf(view_matrix[0]);
 
-       glPushAttrib(GL_ENABLE_BIT);
-       glDisable(GL_LIGHTING);
-       glDisable(GL_CULL_FACE);
+       // draw gravitational field
+       if(wireframe) {
+               glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
+
+               float amb[] = {0.5, 0.5, 0.5, 1.0};
+               glLightModelfv(GL_LIGHT_MODEL_AMBIENT, amb);
+       } else {
+               float amb[] = {0.01, 0.01, 0.01, 1.0};
+               glLightModelfv(GL_LIGHT_MODEL_AMBIENT, amb);
+       }
 
-       glEnable(GL_TEXTURE_2D);
        bind_texture(gvis_tex, 0);
        bind_texture(grid_tex, 1);
 
        glUseProgram(field_sdr);
-       assert(glGetError() == GL_NO_ERROR);
-
        glPatchParameteri(GL_PATCH_VERTICES, 4);
        draw_quadmesh(&field_mesh, GL_PATCHES);
 
+       if(wireframe) {
+               glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
+       }
+
+       // draw particles
+       glUseProgram(particle_sdr);
+
+       Particle *p = plist;
+       while(p) {
+               int gidx = pos_to_grid(p->pos.x, p->pos.y);
+
+               glPushMatrix();
+               glTranslatef(p->pos.x, p->vis_height, p->pos.y);
+               glScalef(p->radius, p->radius, p->radius);
+
+               pmesh->draw();
+
+               glPopMatrix();
+               p = p->next;
+       }
+
        glUseProgram(0);
 
-       glPopAttrib();
+       // draw emitter placement marker if we are in placement mode
+       if(placing_emitter && !mouse_over_ui) {
+               glPushMatrix();
+               glTranslatef(emit_place_pos.x, 0, emit_place_pos.y);
+
+               glBegin(GL_LINES);
+               glColor3f(0, 1, 0);
+               glVertex3f(0, -1000, 0);
+               glVertex3f(0, 1000, 0);
+               glEnd();
+
+               float s = MASS_TO_RADIUS(slider_mass->get_value());
+               if(s < 0.1) s = 0.1;
+               glScalef(s, s, s);
+
+               glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
+               pmesh->draw();
+               glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
+
+               glPopMatrix();
+       }
+
+       // draw the UI
+       glMatrixMode(GL_PROJECTION);
+       glLoadIdentity();
+       glOrtho(0, ui_virt_width, ui_virt_height, 0, -1, 1);
+
+       glMatrixMode(GL_MODELVIEW);
+       glLoadIdentity();
+
+       ui->draw();
+
 
        assert(glGetError() == GL_NO_ERROR);
 }
 
 void GameScreen::reshape(int x, int y)
 {
+       ui_virt_width = x;
+       ui_virt_height = y;
+       ui->set_size(ui_virt_width, ui_virt_height);
 }
 
 
@@ -327,26 +584,59 @@ void GameScreen::keyboard(int key, bool pressed)
                        set_uniform_float(field_sdr, "field_scale", field_scale);
                        break;
 
+               case 'w':
+                       wireframe = !wireframe;
+                       break;
+
+               case ' ':
+                       pause = !pause;
+                       break;
+
                default:
                        break;
                }
        }
 }
 
-static int prev_x, prev_y;
+#define UI_HEIGHT      50
 
 void GameScreen::mbutton(int bn, bool pressed, int x, int y)
 {
-       prev_x = x;
-       prev_y = y;
+       mouse_x = x;
+       mouse_y = y;
+
+       mouse_over_ui = y < UI_HEIGHT;
+
+       ui->sysev_mouse_button(bn, pressed, x * ui_virt_width / win_width,
+                       y * ui_virt_height / win_height);
+
+       if(placing_emitter && bn == 0 && pressed && !mouse_over_ui) {
+               emit_place_pending = true;
+               placing_emitter = false;
+               slider_mass->hide();
+       }
 }
 
 void GameScreen::mmotion(int x, int y)
 {
-       int dx = x - prev_x;
-       int dy = y - prev_y;
-       prev_x = x;
-       prev_y = y;
+       int dx = x - mouse_x;
+       int dy = y - mouse_y;
+       mouse_x = x;
+       mouse_y = y;
+
+       mouse_over_ui = y < UI_HEIGHT;
+
+       ui->sysev_mouse_motion(x * ui_virt_width / win_width, y * ui_virt_height / win_height);
+       if(ui->get_mouse_grab()) {
+               return;
+       }
+
+       if(game_bnstate(0)) {
+               float pan_speed = pow(cam_dist, 1.5) * 0.00035; // magic
+               Vec2 dir = rotate(Vec2(dx, dy) * pan_speed, deg_to_rad(cam_theta));
+               cam_pos.x -= dir.x;
+               cam_pos.y -= dir.y;
+       }
 
        if(game_bnstate(2)) {
                cam_theta += dx * 0.5;
@@ -360,11 +650,42 @@ void GameScreen::mwheel(int dir, int x, int y)
        if(cam_dist > MAX_CAM_DIST) cam_dist = MAX_CAM_DIST;
 }
 
+static void ui_handler(goatkit::Widget *w, const goatkit::Event &ev, void *cls)
+{
+       if(w == bn_emitter) {
+               if(placing_emitter) {
+                       placing_emitter = false;
+                       slider_mass->hide();
+               } else {
+                       if(mass_left > 0.0f) {
+                               placing_emitter = true;
+                               slider_mass->set_range(0, mass_left);
+                               slider_mass->set_value(mass_left >= EM_MASS_DEFAULT ? EM_MASS_DEFAULT : mass_left);
+                               slider_mass->show();
+                       }
+               }
+               return;
+       }
+
+       if(w == slider_mass) {
+               printf("foo: %f\n", slider_mass->get_value());
+       }
+}
+
+static int pos_to_grid_x_noclamp(float x)
+{
+       return ((x / (float)FIELD_SIZE) + 0.5f) * (float)GRID_SIZE;
+}
+
+static int pos_to_grid_y_noclamp(float y)
+{
+       return ((y / (float)FIELD_SIZE) + 0.5f) * (float)GRID_SIZE;
+}
 
 static int pos_to_grid(float x, float y)
 {
-       int gx = ((x / (float)FIELD_SIZE) + 0.5f) * (float)GRID_SIZE;
-       int gy = ((y / (float)FIELD_SIZE) + 0.5f) * (float)GRID_SIZE;
+       int gx = pos_to_grid_x_noclamp(x);
+       int gy = pos_to_grid_y_noclamp(y);
 
        if(gx < 0) gx = 0;
        if(gx >= GRID_SIZE) gx = GRID_SIZE - 1;
@@ -382,6 +703,70 @@ static Vec2 grid_to_pos(int gx, int gy)
        return Vec2(x, y);
 }
 
+static void calc_contrib_bounds(const Vec2 &pos, float mass, Rect *rect)
+{
+       int gidx = pos_to_grid(pos.x, pos.y);
+       int gx = GRID_X(gidx);
+       int gy = GRID_Y(gidx);
+       int maxrange = (int)ceil(CONTRIB_RANGE(mass));
+
+       int sx = gx - maxrange;
+       int sy = gy - maxrange;
+       int ex = gx + maxrange;
+       int ey = gy + maxrange;
+
+       if(ex > GRID_SIZE) ex = GRID_SIZE;
+       if(ey > GRID_SIZE) ey = GRID_SIZE;
+
+       rect->x = sx < 0 ? 0 : sx;
+       rect->y = sy < 0 ? 0 : sy;
+       rect->width = ex - sx;
+       rect->height = ey - sy;
+}
+
+static void add_influence(const Vec2 &pos, float mass, float radius, const Rect &cbox)
+{
+       float *gptr = grid + cbox.y * GRID_SIZE + cbox.x;
+       Vec2 startpos = grid_to_pos(cbox.x, cbox.y);
+
+       for(int y=0; y<cbox.height; y++) {
+               for(int x=0; x<cbox.width; x++) {
+                       Vec2 cellpos = Vec2(startpos.x + (float)x * GRID_DELTA, startpos.y);
+
+                       Vec2 dir = cellpos - pos;
+                       float dsq = dot(dir, dir);
+                       float radsq = radius * radius;
+                       if(dsq < radsq) {
+                               dsq = radsq;
+                       }
+
+                       gptr[x] += mass / dsq;
+               }
+
+               startpos.y += GRID_DELTA;
+               gptr += GRID_SIZE;
+       }
+}
+
+static Vec2 calc_field_grad(int gidx)
+{
+       int gx = GRID_X(gidx);
+       int gy = GRID_Y(gidx);
+
+       int nidx = ((gx + 1 >= GRID_SIZE ? gx : gx + 1) << GRID_BITS) | gy;
+       int pidx = ((gx > 0 ? gx - 1 : gx) << GRID_BITS) | gy;
+       float dfdx = grid[nidx] - grid[pidx];
+
+       nidx = (gx << GRID_BITS) | (gy + 1 >= GRID_SIZE ? gy : gy + 1);
+       pidx = (gx << GRID_BITS) | (gy > 0 ? gy - 1 : gy);
+       float dfdy = grid[nidx] - grid[pidx];
+
+       return Vec2(dfdx, dfdy);
+}
+
+
+// ---- quad mesh operations ----
+
 static void destroy_quadmesh(QuadMesh *m)
 {
        glDeleteBuffers(1, &m->vbo_v);
@@ -450,9 +835,9 @@ static void gen_quad_plane(QuadMesh *m, float width, float height, int usub, int
                                int idx = i * vverts + j;
 
                                *iptr++ = idx;
-                               *iptr++ = idx + vverts;
-                               *iptr++ = idx + vverts + 1;
                                *iptr++ = idx + 1;
+                               *iptr++ = idx + vverts + 1;
+                               *iptr++ = idx + vverts;
                        }
 
                        v += dv;
@@ -475,3 +860,81 @@ static void gen_quad_plane(QuadMesh *m, float width, float height, int usub, int
        glBindBuffer(GL_ARRAY_BUFFER, 0);
        glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
 }
+
+static void spawn_particle(const Vec2 &pos, const Vec2 &vel, float mass)
+{
+       int gidx = pos_to_grid(pos.x, pos.y);
+
+       if(grid_part[gidx]) {
+               // merge with existing
+               Particle *p = grid_part[gidx];
+               p->vel += vel;
+               p->mass += mass;
+               p->radius = MASS_TO_RADIUS(p->mass);
+
+       } else {
+               Particle *p = alloc_particle();
+               p->pos = pos;
+               p->vel = vel;
+               p->mass = mass;
+               p->radius = MASS_TO_RADIUS(mass);
+               grid_part[gidx] = p;
+
+               add_particle(p);
+       }
+}
+
+static void add_particle(Particle *p)
+{
+       if(plist) plist->prev = p;
+
+       p->next = plist;
+       p->prev = 0;
+       plist = p;
+}
+
+static void remove_particle(Particle *p)
+{
+       assert(plist->prev == 0);
+
+       if(plist == p) {
+               assert(p->prev == 0);
+               plist = p->next;
+       }
+       if(p->prev) {
+               p->prev->next = p->next;
+       }
+       if(p->next) {
+               p->next->prev = p->prev;
+       }
+       p->prev = p->next = 0;
+}
+
+// particle allocator
+#define MAX_PFREE_SIZE 256
+static Particle *pfree_list;
+static int pfree_size;
+
+static Particle *alloc_particle()
+{
+       if(pfree_list) {
+               Particle *p = pfree_list;
+               pfree_list = pfree_list->next;
+               pfree_size--;
+               return p;
+       }
+
+       return new Particle;
+}
+
+void free_particle(Particle *p)
+{
+       if(pfree_size < MAX_PFREE_SIZE) {
+               p->next = pfree_list;
+               p->prev = 0;
+               pfree_list = p;
+               pfree_size++;
+       } else {
+               delete p;
+       }
+}