polyadvent

A game engine from scratch in C
git clone git://jb55.com/polyadvent
Log | Files | Refs | README

terrain.c (12325B)


      1 
      2 
      3 #include "terrain.h"
      4 #include "util.h"
      5 #include "delaunay.h"
      6 #include "debug.h"
      7 #include "vec3.h"
      8 #include "perlin.h"
      9 #include "poisson.h"
     10 
     11 static const float plane_verts[] = {
     12   -1,-1,0,  -1,1,0,  1,1,0,  1,-1,0
     13 };
     14 
     15 static const float plane_normals[] = {
     16   0,0,1,  0,0,1,  0,0,1,  0,0,1
     17 };
     18 
     19 static const u32 plane_indices[] = {
     20   2,1,0,  2,0,3
     21 };
     22 
     23 
     24 double old_noisy_boi(struct terrain *t, double x, double y) {
     25   /* return cos(x/10.0) * sin(y/10.0) * 20.0; */
     26   struct perlin_settings *s = &t->settings;
     27   /* x *= s->scale; */
     28   /* y *= s->scale; */
     29   double e =  perlin2d(t->settings.seed, x, y, s->freq, s->depth)
     30       + s->o1s * perlin2d(t->settings.seed, s->o1 * x, s->o1 * y, s->freq, s->depth)
     31       + s->o2s * perlin2d(t->settings.seed, s->o2 * x, s->o2 * y, s->freq, s->depth);
     32   return pow(e, s->exp) * s->amplitude;
     33 }
     34 
     35 typedef double (*noisefn)(void*,double,double);
     36 
     37 void deriv(noisefn fn, void* data, double x, double y, double z1, double *dx, double *dy)
     38 {
     39   static const double h = 0.01;
     40   double zx = fn(data, x + h, y);
     41   double zy = fn(data, x, y - h);
     42   *dx = (zx - z1)/h;
     43   *dy = (zy - z1)/h;
     44 }
     45 
     46 void reset_terrain(struct terrain *terrain, float size) {
     47     terrain->samples = NULL;
     48     terrain->n_samples = 0;
     49     terrain->fn = 0;
     50     terrain->size = size;
     51 
     52     struct entity *ent = get_entity(&terrain->entity_id);
     53     assert(ent);
     54 }
     55 
     56 void init_terrain(struct terrain *terrain, float size) {
     57     init_id(&terrain->entity_id);
     58 
     59     struct entity *ent  = new_entity(&terrain->entity_id);
     60     struct node *node   = get_node(&ent->node_id);
     61     struct model *model = new_model(&ent->model_id, "terrain"); assert(model);
     62     /* struct model *model = init_model(&ent->model_id); assert(model); */
     63 
     64     model->shader = 1;
     65     node_set_label(node, "terrain");
     66     ent->flags &= ~ENT_CASTS_SHADOWS;
     67 
     68     // this is scale for some reason!?
     69     /* node->pos[2] = 20.0; */
     70 
     71     reset_terrain(terrain, size);
     72 }
     73 
     74 double offset_fn(struct terrain* terrain, double x, double y) {
     75     struct perlin_settings *perlin = &terrain->settings;
     76     double ox = perlin->ox;
     77     double oy = perlin->oy;
     78     return old_noisy_boi(terrain, ox+x, oy+y);
     79 }
     80 
     81 void gen_terrain_samples(struct terrain *terrain, float scale, const double pdist) {
     82 
     83     debug("generating terrain samples\n");
     84     if (terrain->samples)
     85         free(terrain->samples);
     86 
     87     int n_samples =
     88         (terrain->size * terrain->size) / (scale * scale);
     89 
     90     /* struct point *samples = */
     91     /*   uniform_samples(n_samples, game->terrain.size); */
     92 
     93     struct point *samples =
     94         poisson_disk_samples(pdist, terrain->size, 30, &n_samples);
     95 
     96     /* remap_samples(samples, n_samples, game->terrain.size); */
     97 
     98     /* draw_samples(samples, pdist, n_samples, game->terrain.size); */
     99 
    100     terrain->samples = samples;
    101     terrain->n_samples = n_samples;
    102 
    103 }
    104 
    105 static inline struct terrain_cell *index_terrain_cell(struct terrain *terrain, int x, int y)
    106 {
    107     if (x < 0 || y < 0 || x >= terrain->n_cells || y >= terrain->n_cells) {
    108         assert(!"terrain oob");
    109         return NULL;
    110     }
    111 
    112     return &terrain->grid[y * terrain->n_cells + x];
    113 }
    114 
    115 static inline struct terrain_cell *query_terrain_cell(struct terrain *terrain,
    116                                                       float x, float y,
    117                                                       int *grid_x, int *grid_y)
    118 { 
    119     assert(x >= 0);
    120     assert(y >= 0);
    121     assert(x < terrain->size);
    122     assert(y < terrain->size);
    123     *grid_x = grid_index(terrain, x);
    124     *grid_y = grid_index(terrain, y);
    125 
    126     return index_terrain_cell(terrain, *grid_x, *grid_y);
    127 }
    128 
    129 void query_terrain_grid(struct terrain *terrain, float x, float y,
    130                         struct terrain_cell *cells[9])
    131 {
    132     int grid_x, grid_y;
    133 
    134     // middle
    135     cells[4] = query_terrain_cell(terrain, x, y, &grid_x, &grid_y);
    136 
    137     // top row
    138     cells[0] = index_terrain_cell(terrain, grid_x - 1, grid_y - 1);
    139     cells[1] = index_terrain_cell(terrain, grid_x,     grid_y - 1);
    140     cells[2] = index_terrain_cell(terrain, grid_x + 1, grid_y - 1);
    141 
    142     // left, right
    143     cells[3] = index_terrain_cell(terrain, grid_x - 1, grid_y);
    144     cells[5] = index_terrain_cell(terrain, grid_x + 1, grid_y);
    145 
    146     // bottom row
    147     cells[6] = index_terrain_cell(terrain, grid_x - 1, grid_y + 1);
    148     cells[7] = index_terrain_cell(terrain, grid_x    , grid_y + 1);
    149     cells[8] = index_terrain_cell(terrain, grid_x + 1, grid_y + 1);
    150 }
    151 
    152 static void insert_grid_vertex(struct terrain_cell *cell, int ind)
    153 {
    154     assert(cell->vert_count + 1 <= MAX_CELL_VERTS);
    155     cell->verts_index[cell->vert_count++] = ind;
    156 }
    157 
    158 #ifdef DEBUG
    159 static int terrain_cell_debug(struct terrain *terrain, struct terrain_cell *cell, int ind, vec3 *pos)
    160 {
    161     int ok = 0;
    162     struct entity_id *ent_id = &cell->debug_ent[ind];
    163 
    164     if (is_null_id(ent_id)) {
    165         assert(cell->verts_index[ind] < terrain->n_verts);
    166         float *vert = &terrain->verts[cell->verts_index[ind]];
    167         int gx = grid_index(terrain, pos[0]);
    168         int gy = grid_index(terrain, pos[1]);
    169         int vgx = grid_index(terrain, vert[0]);
    170         int vgy = grid_index(terrain, vert[1]);
    171         debug("creating new grid_debug entity at %f %f %f, cell (%d, %d) vert_cell(%d, %d)\n",
    172                 vert[0], vert[1], vert[2],
    173                 gx, gy, vgx, vgy);
    174         new_debug_entity(ent_id, vert);
    175         ok |= 1;
    176     }
    177 
    178     return ok;
    179 }
    180 #endif /* DEBUG */
    181 
    182 
    183 #ifdef DEBUG
    184 static int collide_terrain_debug(struct terrain *terrain, struct terrain_cell *cell, int ind, vec3 *pos)
    185 {
    186     int ok = 0;
    187     for (int j = 0; j < cell->vert_count; j++) {
    188         ok |= terrain_cell_debug(terrain, cell, ind, pos);
    189     }
    190 
    191     return ok;
    192 }
    193 #endif /* DEBUG */
    194 
    195 static double distance_to_closest_edge(double size, double x, double y) {
    196     double top    = y;
    197     double left   = x;
    198     double right  = size - x;
    199     double bottom = size - y;
    200     return min(top, min(left, min(right, bottom)));
    201 }
    202 
    203 void create_terrain(struct terrain *terrain, float scale, int seed) {
    204     u32 i;
    205     const double size = terrain->size;
    206 
    207     static const double pdist = 24.0;
    208     terrain->settings.seed = seed;
    209 
    210     float tmp1[3], tmp2[3];
    211     if (!terrain->n_samples) {
    212         gen_terrain_samples(terrain, scale, pdist);
    213         /* save_samples(terrain->samples, seed, terrain->n_samples); */
    214     }
    215     assert(terrain->n_samples > 0);
    216 
    217     del_point2d_t *points = calloc(terrain->n_samples, sizeof(*points));
    218     float *verts = calloc(terrain->n_samples * 3, sizeof(*verts));
    219     terrain->cell_size = pdist;
    220     terrain->n_cells = round(size / terrain->cell_size) + 1;
    221     debug("n_cells %d\n", terrain->n_cells);
    222 
    223     struct terrain_cell *grid =
    224         calloc(terrain->n_cells * terrain->n_cells, sizeof(struct terrain_cell));
    225 
    226     terrain->grid = grid;
    227 
    228     /* float *normals = calloc(terrain->n_samples * 3, sizeof(*verts)); */
    229 
    230     terrain->fn = offset_fn;
    231 
    232     // n random samples from our noise function
    233     for (i = 0; i < (u32)terrain->n_samples; i++) {
    234         int n = i*3;
    235         double x, y;
    236         /* double dx, dy; */
    237 
    238         x = terrain->samples[i].x;
    239         y = terrain->samples[i].y;
    240 
    241         double z = terrain->fn(terrain, x, y);
    242 
    243         points[i].x = x;
    244         points[i].y = y;
    245 
    246         verts[n] = (float)x;
    247         verts[n+1] = (float)y;
    248 
    249         int grid_x = verts[n] / terrain->cell_size;
    250         int grid_y = verts[n+1] / terrain->cell_size;
    251 
    252         // clamp height at edge
    253 
    254         double d = distance_to_closest_edge(size, x, y);
    255         z *= (d / (size/2.0)) * 2.0;
    256 
    257         struct terrain_cell *cell =
    258             index_terrain_cell(terrain, grid_x, grid_y);
    259 
    260         assert(cell);
    261 
    262         insert_grid_vertex(cell, n);
    263 
    264         static const double limit = 1.4;
    265         if (x < limit || x > size-limit || y < limit || y > size-limit)
    266         verts[n+2] = 0;
    267         else
    268         verts[n+2] = (float)z;
    269     }
    270 
    271     delaunay2d_t *del = delaunay2d_from(points, terrain->n_samples);
    272     tri_delaunay2d_t *tri = tri_delaunay2d_from(del);
    273 
    274     int num_verts = tri->num_triangles * 3;
    275     float *del_verts = malloc(num_verts * 3 * sizeof(*del_verts));
    276     float *del_norms = malloc(num_verts * 3 * sizeof(*del_norms));
    277     u32   *del_indices = malloc(num_verts * sizeof(*del_indices));
    278     struct vert_tris *vert_tris = calloc(num_verts, sizeof(struct vert_tris));
    279     terrain->vtris = vert_tris;
    280 
    281     /// XXX (perf): we should be able to do this directly from del instead of
    282     /// triangulating with tri
    283     debug("terrain n_tris %d\n", tri->num_triangles);
    284     for (i = 0; i < tri->num_triangles; ++i) {
    285         int nv = i * 3;
    286         int ndv = i * 9;
    287 
    288         int p[3] = {
    289             tri->tris[nv + 0]*3,
    290             tri->tris[nv + 1]*3,
    291             tri->tris[nv + 2]*3,
    292         };
    293 
    294         float *v[3] = {
    295             &verts[p[0]],
    296             &verts[p[1]],
    297             &verts[p[2]]
    298         };
    299 
    300         for (int j = 0; j < 3; j++) {
    301             struct vert_tris *vtris = &vert_tris[p[j]/3];
    302             assert(vtris->tri_count + 1 < MAX_VERT_TRIS);
    303             struct tri *t = &vtris->tris[vtris->tri_count++];
    304             assert(sizeof(p) == sizeof(t->vert_indices));
    305             memcpy(t->vert_indices, p, sizeof(p));
    306 
    307             int ind = ndv + j*3;
    308             del_verts[ind+0] = v[j][0];
    309             del_verts[ind+1] = v[j][1];
    310             del_verts[ind+2] = v[j][2];
    311         }
    312 
    313         // normals
    314         vec3_subtract(v[1], v[0], tmp1);
    315         vec3_subtract(v[2], v[0], tmp2);
    316 
    317         vec3_cross(tmp1, tmp2, tmp2);
    318         vec3_normalize(tmp2, tmp2);
    319 
    320         for (int j = 0; j < 9; ++j) {
    321             del_norms[ndv+j] = tmp2[j%3];
    322         }
    323 
    324         del_indices[nv+0] = nv+0;
    325         del_indices[nv+1] = nv+1;
    326         del_indices[nv+2] = nv+2;
    327     }
    328 
    329     /* printf("faces %d tris %d points %d\n", */
    330     /*        del->num_faces, tri->num_triangles, tri->num_points); */
    331 
    332     struct entity *ent = get_entity(&terrain->entity_id);
    333     assert(ent);
    334 
    335     struct make_geometry mkgeom;
    336     init_make_geometry(&mkgeom);
    337 
    338     mkgeom.num_verts = num_verts;
    339     mkgeom.vertices = (float*)del_verts;
    340     mkgeom.normals = (float*)del_norms;
    341     mkgeom.indices = (u32*)del_indices;
    342     mkgeom.num_indices = num_verts;
    343 
    344     struct model *model = get_model(&ent->model_id); assert(model);
    345     struct geometry *geom = get_geometry(&model->geom_id); assert(geom);
    346 
    347     assert(mkgeom.joint_weights == 0);
    348     make_buffer_geometry(&mkgeom, geom);
    349 
    350     delaunay2d_release(del);
    351     tri_delaunay2d_release(tri);
    352 
    353     assert(del_verts);
    354 
    355     free(points);
    356     // needed for collision
    357     /* free(verts); */
    358     free(del_verts);
    359 
    360     terrain->verts = verts;
    361     terrain->n_verts = num_verts;
    362 
    363     // we might need norms in memory eventually as well ?
    364     free(del_norms);
    365     free(del_indices);
    366 
    367 }
    368 
    369 
    370 void destroy_terrain(struct terrain *terrain) {
    371     struct entity *ent = get_entity(&terrain->entity_id); assert(ent);
    372     struct model *model = get_model(&ent->model_id); assert(model);
    373     destroy_buffer_geometry(&model->geom_id);
    374 }
    375 
    376 
    377 void update_terrain(struct terrain *terrain, const double pdist) {
    378     static int first = 1;
    379     static float last_scale = -1.0;
    380 
    381     struct entity *ent = get_entity(&terrain->entity_id);
    382     assert(ent);
    383     struct perlin_settings *ts = &terrain->settings;
    384     struct node *tnode = get_node(&ent->node_id);
    385     assert(tnode);
    386 
    387     debug("updating terrain\n");
    388 
    389     if (first) {
    390         reset_terrain(terrain, terrain->size);
    391         /* tnode->pos[0] = rand_0to1() * terrain->size; */
    392         /* tnode->pos[1] = rand_0to1() * terrain->size; */
    393         first = 0;
    394     }
    395 
    396     ts->ox = tnode->pos[0];
    397     ts->oy = tnode->pos[1];
    398 
    399     double scale = tnode->pos[2] * 0.0015;
    400     if (scale == 0) scale = 1.0;
    401 
    402     printf("terrain %f %f %f\n", tnode->pos[0], tnode->pos[1], tnode->pos[2]);
    403 
    404     /* ts.o1s = fabs(sin(1/n) * 0.25); */
    405     /* ts.o1 = fabs(cos(n*0.2) * 0.5); */
    406     /* ts.o2s = fabs(cos(n+2) * 0.5); */
    407     /* ts.o2 = fabs(sin(n*0.02) * 2); */
    408     ts->freq = scale * 0.08;
    409     ts->amplitude = 70.0;
    410 
    411     /* if (terrain->fn) */
    412     /*     destroy_terrain(terrain); */
    413 
    414     /* const double pdist = min(5.0, max(1.1, 1.0/scale*1.4)); */
    415 
    416     /* printf("pdist %f\n", pdist); */
    417 
    418     if (last_scale == -1.0 || fabs(scale - last_scale) > 0.00001) {
    419         gen_terrain_samples(terrain, scale, pdist);
    420     }
    421 
    422     last_scale = scale;
    423     create_terrain(terrain, scale, 0);
    424 }