- v3f v0, v1;
- v3_sub( tri[ia], pos, v0 );
- v3_sub( tri[ib], pos, v1 );
-
- if( (clipdir[2]*v0[0] - clipdir[0]*v0[2]) *
- (clipdir[2]*v1[0] - clipdir[0]*v1[2]) < 0.0f )
- {
- float da = v3_dot(v0,perp),
- db = v3_dot(v1,perp),
- d = da-db,
- qa = da/d;
-
- v3f p0;
- v3_muls( v1, qa, p0 );
- v3_muladds( p0, v0, 1.0f-qa, p0 );
-
- float h = v3_dot(p0,clipdir)/v3_dot(clipdir,clipdir);
-
- if( h >= max_dist && h <= 1.0f )
- {
- max_dist = h;
- float l = 1.0f/v3_length(clipdir);
- v3_muls( p0, l, st->clip[dir] );
- }
- }
- }
- }
-}
-
-static const struct conf
-{
- struct confedge
- {
- /* i: sample index
- * d: data index
- * a: axis index
- * o: the 'other' point to do a A/B test with
- * if its -1, all AB is done.
- */
- int i0, i1,
- d0, d1,
- a0, a1,
- o0, o1;
- }
- edges[2];
- int edge_count;
-}
-k_walkgrid_configs[16] = {
- {{},0},
- {{{ 3,3, 3,0, 1,0, -1,-1 }}, 1},
- {{{ 2,2, 1,3, 0,1, -1,-1 }}, 1},
- {{{ 2,3, 1,0, 0,0, 3,-1 }}, 1},
-
- {{{ 1,1, 0,1, 1,0, -1,-1 }}, 1},
- {{{ 3,3, 3,0, 1,0, -1,-1 },
- { 1,1, 0,1, 1,0, -1,-1 }}, 2},
- {{{ 1,2, 0,3, 1,1, 2,-1 }}, 1},
- {{{ 1,3, 0,0, 1,0, 2, 2 }}, 1},
-
- {{{ 0,0, 0,0, 0,1, -1,-1 }}, 1},
- {{{ 3,0, 3,0, 1,1, 0,-1 }}, 1},
- {{{ 2,2, 1,3, 0,1, -1,-1 },
- { 0,0, 0,0, 0,1, -1,-1 }}, 2},
- {{{ 2,0, 1,0, 0,1, 3, 3 }}, 1},
-
- {{{ 0,1, 0,1, 0,0, 1,-1 }}, 1},
- {{{ 3,1, 3,1, 1,0, 0, 0 }}, 1},
- {{{ 0,2, 0,3, 0,1, 1, 1 }}, 1},
- {{},0},
-};
-
-/*
- * Get a buffer of edges from cell location
- */
-static const struct conf *player_walkgrid_conf( struct walkgrid *wg,
- v2i cell,
- struct grid_sample *corners[4] )
-{
- corners[0] = &wg->samples[cell[1] ][cell[0] ];
- corners[1] = &wg->samples[cell[1]+1][cell[0] ];
- corners[2] = &wg->samples[cell[1]+1][cell[0]+1];
- corners[3] = &wg->samples[cell[1] ][cell[0]+1];
-
- u32 vd0 = corners[0]->type == k_sample_type_valid,
- vd1 = corners[1]->type == k_sample_type_valid,
- vd2 = corners[2]->type == k_sample_type_valid,
- vd3 = corners[3]->type == k_sample_type_valid,
- config = (vd0<<3) | (vd1<<2) | (vd2<<1) | vd3;
-
- return &k_walkgrid_configs[ config ];
-}
-
-static void player_walkgrid_floor(v3f pos)
-{
- v3_muls( pos, 1.0f/k_gridscale, pos );
- v3_floor( pos, pos );
- v3_muls( pos, k_gridscale, pos );
-}
-
-/*
- * Computes the barycentric coordinate of location on a triangle (vertical),
- * then sets the Y position to the interpolation of the three points
- */
-static void player_walkgrid_stand_tri( v3f a, v3f b, v3f c, v3f pos )
-{
- v3f v0,v1,v2;
- v3_sub( b, a, v0 );
- v3_sub( c, a, v1 );
- v3_sub( pos, a, v2 );
-
- float d = v0[0]*v1[2] - v1[0]*v0[2],
- v = (v2[0]*v1[2] - v1[0]*v2[2]) / d,
- w = (v0[0]*v2[2] - v2[0]*v0[2]) / d,
- u = 1.0f - v - w;
-
- vg_line( pos, a, 0xffff0000 );
- vg_line( pos, b, 0xff00ff00 );
- vg_line( pos, c, 0xff0000ff );
- pos[1] = u*a[1] + v*b[1] + w*c[1];
-}
-
-/*
- * Get the minimum time value of pos+dir until a cell edge
- *
- * t[0] -> t[3] are the individual time values
- * t[5] & t[6] are the maximum axis values
- * t[6] is the minimum value
- *
- */
-static void player_walkgrid_min_cell( float t[7], v2f pos, v2f dir )
-{
- v2f frac = { 1.0f/dir[0], 1.0f/dir[1] };
-
- t[0] = 999.9f;
- t[1] = 999.9f;
- t[2] = 999.9f;
- t[3] = 999.9f;
-
- if( fabsf(dir[0]) > 0.0001f )
- {
- t[0] = (0.0f-pos[0]) * frac[0];
- t[1] = (1.0f-pos[0]) * frac[0];
- }
- if( fabsf(dir[1]) > 0.0001f )
- {
- t[2] = (0.0f-pos[1]) * frac[1];
- t[3] = (1.0f-pos[1]) * frac[1];
- }
-
- t[4] = vg_maxf(t[0],t[1]);
- t[5] = vg_maxf(t[2],t[3]);
- t[6] = vg_minf(t[4],t[5]);
-}
-
-static void player_walkgrid_iter(struct walkgrid *wg, int iter)
-{
-
- /*
- * For each walkgrid iteration we are stepping through cells and determining
- * the intersections with the grid, and any edges that are present
- */
-
- u32 icolours[] = { 0xffff00ff, 0xff00ffff, 0xffffff00 };
-
- v3f pa, pb, pc, pd, pl0, pl1;
- pa[0] = wg->region[0][0] + (float)wg->cell_id[0] *k_gridscale;
- pa[1] = (wg->region[0][1] + wg->region[1][1]) * 0.5f + k_gridscale;
- pa[2] = wg->region[0][2] + (float)wg->cell_id[1] *k_gridscale;
- pb[0] = pa[0];
- pb[1] = pa[1];
- pb[2] = pa[2] + k_gridscale;
- pc[0] = pa[0] + k_gridscale;
- pc[1] = pa[1];
- pc[2] = pa[2] + k_gridscale;
- pd[0] = pa[0] + k_gridscale;
- pd[1] = pa[1];
- pd[2] = pa[2];
-#if 0
- /* if you want to draw the current cell */
- vg_line( pa, pb, 0xff00ffff );
- vg_line( pb, pc, 0xff00ffff );
- vg_line( pc, pd, 0xff00ffff );
- vg_line( pd, pa, 0xff00ffff );
-#endif
- pl0[0] = pa[0] + wg->pos[0]*k_gridscale;
- pl0[1] = pa[1];
- pl0[2] = pa[2] + wg->pos[1]*k_gridscale;
-
- /*
- * If there are edges present, we need to create a 'substep' event, where
- * we find the intersection point, find the fully resolved position,
- * then the new pos dir is the intersection->resolution
- *
- * the resolution is applied in non-discretized space in order to create a
- * suitable vector for finding outflow, we want it to leave the cell so it
- * can be used by the quad
- */
-
- v2f pos, dir;
- v2_copy( wg->pos, pos );
- v2_muls( wg->dir, wg->move, dir );
-
- struct grid_sample *corners[4];
- v2f corners2d[4] = {{0.0f,0.0f},{0.0f,1.0f},{1.0f,1.0f},{1.0f,0.0f}};
- const struct conf *conf = player_walkgrid_conf( wg, wg->cell_id, corners );
-
- float t[7];
- player_walkgrid_min_cell( t, pos, dir );
-
- for( int i=0; i<conf->edge_count; i++ )
- {
- const struct confedge *edge = &conf->edges[i];
-
- v2f e0, e1, n, r, target, res, tangent;
- e0[0] = corners2d[edge->i0][0] + corners[edge->d0]->clip[edge->a0][0];
- e0[1] = corners2d[edge->i0][1] + corners[edge->d0]->clip[edge->a0][2];
- e1[0] = corners2d[edge->i1][0] + corners[edge->d1]->clip[edge->a1][0];
- e1[1] = corners2d[edge->i1][1] + corners[edge->d1]->clip[edge->a1][2];
-
- v3f pe0 = { pa[0] + e0[0]*k_gridscale,
- pa[1],
- pa[2] + e0[1]*k_gridscale };
- v3f pe1 = { pa[0] + e1[0]*k_gridscale,
- pa[1],
- pa[2] + e1[1]*k_gridscale };
-
- v2_sub( e1, e0, tangent );
- n[0] = -tangent[1];
- n[1] = tangent[0];
- v2_normalize( n );
-
- /*
- * If we find ourselfs already penetrating the edge, move back out a
- * little
- */
- v2_sub( e0, pos, r );
- float p1 = v2_dot(r,n);
-
- if( -p1 < 0.0001f )
- {
- v2_muladds( pos, n, p1+0.0001f, pos );
- v2_copy( pos, wg->pos );
- v3f p_new = { pa[0] + pos[0]*k_gridscale,
- pa[1],
- pa[2] + pos[1]*k_gridscale };
- v3_copy( p_new, pl0 );
- }
-
- v2_add( pos, dir, target );
-
- v2f v1, v2, v3;
- v2_sub( e0, pos, v1 );
- v2_sub( target, pos, v2 );
-
- v2_copy( n, v3 );
-
- v2_sub( e0, target, r );
- float p = v2_dot(r,n),
- t1 = v2_dot(v1,v3)/v2_dot(v2,v3);
-
- if( t1 < t[6] && t1 > 0.0f && -p < 0.001f )
- {
- v2_muladds( target, n, p+0.0001f, res );
-
- v2f intersect;
- v2_muladds( pos, dir, t1, intersect );
- v2_copy( intersect, pos );
- v2_sub( res, intersect, dir );
-
- v3f p_res = { pa[0] + res[0]*k_gridscale,
- pa[1],
- pa[2] + res[1]*k_gridscale };
- v3f p_int = { pa[0] + intersect[0]*k_gridscale,
- pa[1],
- pa[2] + intersect[1]*k_gridscale };
-
- vg_line( pl0, p_int, icolours[iter%3] );
- v3_copy( p_int, pl0 );
- v2_copy( pos, wg->pos );
-
- player_walkgrid_min_cell( t, pos, dir );
- }
- }
-
- /*
- * Compute intersection with grid cell moving outwards
- */
- t[6] = vg_minf( t[6], 1.0f );
-
- pl1[0] = pl0[0] + dir[0]*k_gridscale*t[6];
- pl1[1] = pl0[1];
- pl1[2] = pl0[2] + dir[1]*k_gridscale*t[6];
- vg_line( pl0, pl1, icolours[iter%3] );
-
- if( t[6] < 1.0f )
- {
- /*
- * To figure out what t value created the clip so we know which edge
- * to wrap around
- */
-
- if( t[4] < t[5] )
- {
- wg->pos[1] = pos[1] + dir[1]*t[6];
-
- if( t[0] > t[1] ) /* left edge */
- {
- wg->pos[0] = 0.9999f;
- wg->cell_id[0] --;
-
- if( wg->cell_id[0] == 0 )
- wg->move = -1.0f;
- }
- else /* Right edge */
- {
- wg->pos[0] = 0.0001f;
- wg->cell_id[0] ++;
-
- if( wg->cell_id[0] == WALKGRID_SIZE-2 )
- wg->move = -1.0f;
- }
- }
- else
- {
- wg->pos[0] = pos[0] + dir[0]*t[6];
-
- if( t[2] > t[3] ) /* bottom edge */
- {
- wg->pos[1] = 0.9999f;
- wg->cell_id[1] --;
-
- if( wg->cell_id[1] == 0 )
- wg->move = -1.0f;
- }
- else /* top edge */
- {
- wg->pos[1] = 0.0001f;
- wg->cell_id[1] ++;
-
- if( wg->cell_id[1] == WALKGRID_SIZE-2 )
- wg->move = -1.0f;
- }
- }
-
- wg->move -= t[6];
- }
- else
- {
- v2_muladds( wg->pos, dir, wg->move, wg->pos );
- wg->move = 0.0f;
- }
-}
-
-static void player_walkgrid_stand_cell(struct walkgrid *wg)
-{
- /*
- * NOTE: as opposed to the other function which is done in discretized space
- * this use a combination of both.
- */
-
- v3f world;
- world[0] = wg->region[0][0]+((float)wg->cell_id[0]+wg->pos[0])*k_gridscale;
- world[1] = player.rb.co[1];
- world[2] = wg->region[0][2]+((float)wg->cell_id[1]+wg->pos[1])*k_gridscale;
-
- struct grid_sample *corners[4];
- const struct conf *conf = player_walkgrid_conf( wg, wg->cell_id, corners );
-
- if( conf != k_walkgrid_configs )
- {
- if( conf->edge_count == 0 )
- {
- v3f v0;
-
- /* Split the basic quad along the shortest diagonal */
- if( fabsf(corners[2]->pos[1] - corners[0]->pos[1]) <
- fabsf(corners[3]->pos[1] - corners[1]->pos[1]) )
- {
- vg_line( corners[2]->pos, corners[0]->pos, 0xffaaaaaa );
-
- if( wg->pos[0] > wg->pos[1] )
- player_walkgrid_stand_tri( corners[0]->pos,
- corners[3]->pos,
- corners[2]->pos, world );
- else
- player_walkgrid_stand_tri( corners[0]->pos,
- corners[2]->pos,
- corners[1]->pos, world );
- }
- else
- {
- vg_line( corners[3]->pos, corners[1]->pos, 0xffaaaaaa );
-
- if( wg->pos[0] < 1.0f-wg->pos[1] )
- player_walkgrid_stand_tri( corners[0]->pos,
- corners[3]->pos,
- corners[1]->pos, world );
- else
- player_walkgrid_stand_tri( corners[3]->pos,
- corners[2]->pos,
- corners[1]->pos, world );
- }
- }
- else
- {
- for( int i=0; i<conf->edge_count; i++ )
- {
- const struct confedge *edge = &conf->edges[i];
-
- v3f p0, p1;
- v3_muladds( corners[edge->i0]->pos,
- corners[edge->d0]->clip[edge->a0], k_gridscale, p0 );
- v3_muladds( corners[edge->i1]->pos,
- corners[edge->d1]->clip[edge->a1], k_gridscale, p1 );
-
- /*
- * Find penetration distance between player position and the edge
- */
-
- v2f normal = { -(p1[2]-p0[2]), p1[0]-p0[0] },
- rel = { world[0]-p0[0], world[2]-p0[2] };
-
- if( edge->o0 == -1 )
- {
- /* No subregions (default case), just use triangle created by
- * i0, e0, e1 */
- player_walkgrid_stand_tri( corners[edge->i0]->pos,
- p0,
- p1, world );
- }
- else
- {
- /*
- * Test if we are in the first region, which is
- * edge.i0, edge.e0, edge.o0,
- */
- v3f v0, ref;
- v3_sub( p0, corners[edge->o0]->pos, ref );
- v3_sub( world, corners[edge->o0]->pos, v0 );
-
- vg_line( corners[edge->o0]->pos, p0, 0xffffff00 );
- vg_line( corners[edge->o0]->pos, world, 0xff000000 );
-
- if( ref[0]*v0[2] - ref[2]*v0[0] < 0.0f )
- {
- player_walkgrid_stand_tri( corners[edge->i0]->pos,
- p0,
- corners[edge->o0]->pos, world );
- }
- else
- {
- if( edge->o1 == -1 )
- {
- /*
- * No other edges mean we just need to use the opposite
- *
- * e0, e1, o0 (in our case, also i1)
- */
- player_walkgrid_stand_tri( p0,
- p1,
- corners[edge->o0]->pos, world );
- }
- else
- {
- /*
- * Note: this v0 calculation can be ommited with the
- * current tileset.
- *
- * the last two triangles we have are:
- * e0, e1, o1
- * and
- * e1, i1, o1
- */
- v3_sub( p1, corners[edge->o1]->pos, ref );
- v3_sub( world, corners[edge->o1]->pos, v0 );
- vg_line( corners[edge->o1]->pos, p1, 0xff00ffff );
-
- if( ref[0]*v0[2] - ref[2]*v0[0] < 0.0f )
- {
- player_walkgrid_stand_tri( p0,
- p1,
- corners[edge->o1]->pos,
- world );
- }
- else
- {
- player_walkgrid_stand_tri( p1,
- corners[edge->i1]->pos,
- corners[edge->o1]->pos,
- world );
- }
- }
- }
- }
- }
- }
- }
-
- v3_copy( world, player.rb.co );
-}
-
-static void player_walkgrid_getsurface(void)
-{
- float const k_stepheight = 0.5f;
- float const k_miny = 0.6f;
- float const k_height = 1.78f;
- float const k_region_size = (float)WALKGRID_SIZE/2.0f * k_gridscale;
-
- static struct walkgrid wg;
-
- v3f cell;
- v3_copy( player.rb.co, cell );
- player_walkgrid_floor( cell );
-
- v3_muladds( cell, (v3f){-1.0f,-1.0f,-1.0f}, k_region_size, wg.region[0] );
- v3_muladds( cell, (v3f){ 1.0f, 1.0f, 1.0f}, k_region_size, wg.region[1] );
-
-
- /*
- * Create player input vector
- */
- v3f delta = {0.0f,0.0f,0.0f};
- v3f fwd = { -sinf(-player.angles[0]), 0.0f, -cosf(-player.angles[0]) },
- side = { -fwd[2], 0.0f, fwd[0] };
-
- /* Temp */
- if( !vg_console_enabled() )
- {
- if( glfwGetKey( vg_window, GLFW_KEY_W ) )
- v3_muladds( delta, fwd, ktimestep*k_walkspeed, delta );
- if( glfwGetKey( vg_window, GLFW_KEY_S ) )
- v3_muladds( delta, fwd, -ktimestep*k_walkspeed, delta );
-
- if( glfwGetKey( vg_window, GLFW_KEY_A ) )
- v3_muladds( delta, side, -ktimestep*k_walkspeed, delta );
- if( glfwGetKey( vg_window, GLFW_KEY_D ) )
- v3_muladds( delta, side, ktimestep*k_walkspeed, delta );
-
- v3_muladds( delta, fwd,
- vg_get_axis("vertical")*-ktimestep*k_walkspeed, delta );
- v3_muladds( delta, side,
- vg_get_axis("horizontal")*ktimestep*k_walkspeed, delta );
- }
-
- /*
- * Create our move in grid space
- */
- wg.dir[0] = delta[0] * (1.0f/k_gridscale);
- wg.dir[1] = delta[2] * (1.0f/k_gridscale);
- wg.move = 1.0f;
-
- v2f region_pos =
- {
- (player.rb.co[0] - wg.region[0][0]) * (1.0f/k_gridscale),
- (player.rb.co[2] - wg.region[0][2]) * (1.0f/k_gridscale)
- };
- v2f region_cell_pos;
- v2_floor( region_pos, region_cell_pos );
- v2_sub( region_pos, region_cell_pos, wg.pos );
-
- wg.cell_id[0] = region_cell_pos[0];
- wg.cell_id[1] = region_cell_pos[1];
-
- for(int y=0; y<WALKGRID_SIZE; y++ )
- {
- for(int x=0; x<WALKGRID_SIZE; x++ )
- {
- struct grid_sample *s = &wg.samples[y][x];
- v3_muladds( wg.region[0], (v3f){ x, 0, y }, k_gridscale, s->pos );
- s->state = k_traverse_none;
- s->type = k_sample_type_air;
- v3_zero( s->clip[0] );
- v3_zero( s->clip[1] );
- }
- }
-
- v2i border[WALKGRID_SIZE*WALKGRID_SIZE];
- v2i *cborder = border;
- u32 border_length = 1;
-
- struct grid_sample *base = NULL;
-
- v2i starters[] = {{0,0},{1,1},{0,1},{1,0}};
-
- for( int i=0;i<4;i++ )
- {
- v2i test;
- v2i_add( wg.cell_id, starters[i], test );
- v2i_copy( test, border[0] );
- base = &wg.samples[test[1]][test[0]];
-
- base->pos[1] = cell[1];
- player_walkgrid_samplepole( base );
-
- if( base->type == k_sample_type_valid )
- break;
- else
- base->type = k_sample_type_air;
- }
-
- vg_line_pt3( base->pos, 0.1f, 0xffffffff );
-
- int iter = 0;
-
- while( border_length )
- {
- v2i directions[] = {{1,0},{0,1},{-1,0},{0,-1}};
-
- v2i *old_border = cborder;
- int len = border_length;
-
- border_length = 0;
- cborder = old_border+len;
-
- for( int i=0; i<len; i++ )
- {
- v2i co;
- v2i_copy( old_border[i], co );
- struct grid_sample *sa = &wg.samples[co[1]][co[0]];
-
- for( int j=0; j<4; j++ )
- {
- v2i newp;
- v2i_add( co, directions[j], newp );
-
- if( newp[0] < 0 || newp[1] < 0 ||
- newp[0] == WALKGRID_SIZE || newp[1] == WALKGRID_SIZE )
- continue;
-
- struct grid_sample *sb = &wg.samples[newp[1]][newp[0]];
- enum traverse_state thismove = j%2==0? 1: 2;
-
- if( (sb->state & thismove) == 0x00 ||
- sb->type == k_sample_type_air )
- {
- sb->pos[1] = sa->pos[1];
-
- player_walkgrid_samplepole( sb );
-
- if( sb->type != k_sample_type_air )
- {
- /*
- * Need to do a blocker pass
- */
-
- struct grid_sample *store = (j>>1 == 0)? sa: sb;
- player_walkgrid_clip_blocker( sa, sb, store, j%2 );
-
-
- if( sb->type != k_sample_type_air )
- {
- vg_line( sa->pos, sb->pos, 0xffffffff );
-
- if( sb->state == k_traverse_none )
- v2i_copy( newp, cborder[ border_length ++ ] );
- }
- else
- {
- v3f p1;
- v3_muladds( sa->pos, store->clip[j%2], k_gridscale, p1 );
- vg_line( sa->pos, p1, 0xffffffff );
- }
- }
- else
- {
- /*
- * A clipping pass is now done on the edge of the walkable
- * surface
- */
-
- struct grid_sample *store = (j>>1 == 0)? sa: sb;
- player_walkgrid_clip_edge( sa, sb, store, j%2 );
-
- v3f p1;
- v3_muladds( sa->pos, store->clip[j%2], k_gridscale, p1 );
- vg_line( sa->pos, p1, 0xffffffff );
- }
-
- sb->state |= thismove;
- }
- }
-
- sa->state = k_traverse_h|k_traverse_v;
- }
-
- iter ++;
- if( iter == walk_grid_iterations )