+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;
+#if 0
+ 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 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 )