polyadvent

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

terrain.c (12424B)


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