bvh interface and high perf gate

[carveJwlIkooP6JGAAIwe30JlM.git] / player.h

#ifndef PLAYER_H
#define PLAYER_H

#include "common.h"
#include "character.h"

static int freecam = 0;
static float k_walkspeed = 2.0f; 
static int walk_grid_iterations = 1;

static struct gplayer
{
   /* Physics */
   v3f co, v, a, v_last, m, bob, vl;
   v4f rot;
   float vswitch, slip, slip_last,
         reverse;

   float iY;   /* Yaw inertia */
   int in_air, is_dead, on_board;

   /* Input */
   v2f joy_l;

   v2f board_xy;
   float grab;
   float pitch;

   v3f land_target;
   v3f land_target_log[22];
   u32 land_target_colours[22];
   int land_log_count;
   m3x3f vr;

   m4x3f to_world, to_local;
   
   struct character mdl;

   v3f handl_target, handr_target,
       handl, handr;
   
   /* Camera */
   float air_blend;
   
   v3f camera_pos, smooth_localcam;
   v2f angles;
   m4x3f camera, camera_inverse;
}
player = 
{
   .on_board = 1
};

static void player_transform_update(void)
{
   q_normalize( player.rot );
   q_m3x3( player.rot, player.to_world );
   v3_copy( player.co, player.to_world[3] );

   m4x3_invert_affine( player.to_world, player.to_local );
}

static int reset_player( int argc, char const *argv[] )
{
   v3_copy( (v3f){ 0.0f, -2.0f, 0.0f }, player.co );

   if( argc == 1 )
   {
      if( !strcmp( argv[0], "tutorial" ))
         v3_copy( world.tutorial, player.co );
   }

   v3_copy( (v3f){ 0.0f, 0.0f, -0.2f }, player.v );
   q_identity( player.rot );
   player.vswitch = 1.0f;
   player.slip_last = 0.0f;
   player.is_dead = 0;
   player.in_air = 1;
   m3x3_identity( player.vr );

   player.mdl.shoes[0] = 1;
   player.mdl.shoes[1] = 1;

   player_transform_update();
   return 0;
}

static void player_mouseview(void)
{
   static v2f mouse_last,
              view_vel = { 0.0f, 0.0f };

   if( vg_get_button_down( "primary" ) )
      v2_copy( vg_mouse, mouse_last );
   else if( vg_get_button( "primary" ) )
   {
      v2f delta;
      v2_sub( vg_mouse, mouse_last, delta );
      v2_copy( vg_mouse, mouse_last );

      v2_muladds( view_vel, delta, 0.005f, view_vel );
   }
   
   v2_muls( view_vel, 0.7f, view_vel );
   v2_add( view_vel, player.angles, player.angles );
   player.angles[1] = vg_clampf( player.angles[1], -VG_PIf*0.5f, VG_PIf*0.5f );

}

static void player_freecam(void)
{
   player_mouseview();

   float movespeed = 25.0f;
   v3f lookdir = { 0.0f, 0.0f, -1.0f },
       sidedir = { 1.0f, 0.0f,  0.0f };
   
   m3x3_mulv( player.camera, lookdir, lookdir );
   m3x3_mulv( player.camera, sidedir, sidedir );
   
   static v3f move_vel = { 0.0f, 0.0f, 0.0f };
   if( vg_get_button( "forward" ) )
      v3_muladds( move_vel, lookdir, ktimestep * movespeed, move_vel );
   if( vg_get_button( "back" ) )
      v3_muladds( move_vel, lookdir, ktimestep *-movespeed, move_vel );
   if( vg_get_button( "left" ) )
      v3_muladds( move_vel, sidedir, ktimestep *-movespeed, move_vel );
   if( vg_get_button( "right" ) )
      v3_muladds( move_vel, sidedir, ktimestep * movespeed, move_vel );

   v3_muls( move_vel, 0.7f, move_vel );
   v3_add( move_vel, player.camera_pos, player.camera_pos );
}

static void apply_gravity( v3f vel, float const timestep )
{
   v3f gravity = { 0.0f, -9.6f, 0.0f };
   v3_muladds( vel, gravity, timestep, vel );
}

/*
 * TODO: The angle bias should become greater when launching from a steeper 
 *       angle and skewed towords more 'downwards' angles when launching from
 *       shallower trajectories
 */
static void player_start_air(void)
{
   player.in_air = 1;

   float pstep = ktimestep*10.0f;

   float best_velocity_mod = 0.0f,
         best_velocity_delta = -9999.9f;

   float k_bias = 0.97f;

   v3f axis, vup;
   m3x3_mulv( player.to_world, (v3f){0.0f,1.0f,0.0f}, vup );
   v3_cross( vup, player.v, axis );
   v3_normalize( axis );
   player.land_log_count = 0;
   
   m3x3_identity( player.vr );

   for( int m=-3;m<=12; m++ )
   {
      float vmod = ((float)m / 15.0f)*0.09f;

      v3f pco, pco1, pv;
      v3_copy( player.co, pco );
      v3_muls( player.v, k_bias, pv );

      /* 
       * Try different 'rotations' of the velocity to find the best possible
       * landing normal. This conserves magnitude at the expense of slightly
       * unrealistic results
       */

      m3x3f vr;
      v4f vr_q;

      q_axis_angle( vr_q, axis, vmod );
      q_m3x3( vr_q, vr );

      m3x3_mulv( vr, pv, pv );
      v3_muladds( pco, pv, pstep, pco );

      for( int i=0; i<50; i++ )
      {
         v3_copy( pco, pco1 );
         apply_gravity( pv, pstep );

         m3x3_mulv( vr, pv, pv );
         v3_muladds( pco, pv, pstep, pco );
         
         ray_hit contact;
         v3f vdir;

         v3_sub( pco, pco1, vdir );
         contact.dist = v3_length( vdir );
         v3_divs( vdir, contact.dist, vdir);

         if( ray_world( pco1, vdir, &contact ))
         {
            float land_delta = v3_dot( pv, contact.normal );
            u32 scolour = (u8)(vg_minf(-land_delta * 2.0f, 255.0f));

            /* Bias prediction towords ramps */
            if( ray_hit_is_ramp( &contact ) )
            {
               land_delta *= 0.1f;
               scolour |= 0x0000a000;
            }

            if( (land_delta < 0.0f) && (land_delta > best_velocity_delta) )
            {
               best_velocity_delta = land_delta;
               best_velocity_mod = vmod;

               v3_copy( contact.pos, player.land_target );

               q_axis_angle( vr_q, axis, vmod*0.1f );
               q_m3x3( vr_q, player.vr );
            }

            v3_copy( contact.pos, 
                  player.land_target_log[player.land_log_count] );
            player.land_target_colours[player.land_log_count] = 
               0xff000000 | scolour;

            player.land_log_count ++;

            break;
         }
      }
   }

   //v3_rotate( player.v, best_velocity_mod, axis, player.v );
   
   return;
   v3_muls( player.v, best_velocity_mod, player.v );
}

static int sample_if_resistant( v3f pos )
{
   v3f ground;
   v3_copy( pos, ground );
   ground[1] += 4.0f;
   
   ray_hit hit;
   hit.dist = INFINITY;

   if( ray_world( ground, (v3f){0.0f,-1.0f,0.0f}, &hit ))
   {
      v3f angle;
      v3_copy( player.v, angle );
      v3_normalize( angle );
      float resistance = v3_dot( hit.normal, angle );

      if( resistance < 0.25f )
      {
         v3_copy( hit.pos, pos );
         return 1;
      }
   }

   return 0;
}

static float stable_force( float current, float diff )
{
   float new = current + diff;

   if( new * current < 0.0f )
      return 0.0f;

   return new;
}

static void player_physics_ground(void)
{
   /* 
    * Getting surface collision points,
    * the contact manifold is a triangle for simplicity.
    */
   v3f contact_front, contact_back, contact_norm, vup, vside,
       axis;
   
   float klength = 0.65f;
   m4x3_mulv( player.to_world, (v3f){ 0.15f,0.0f,-klength}, contact_norm );
   m4x3_mulv( player.to_world, (v3f){-0.15f,0.0f,-klength}, contact_front );
   m4x3_mulv( player.to_world, (v3f){ 0.00f,0.0f, klength}, contact_back );
   m3x3_mulv( player.to_world, (v3f){ 0.0f, 1.0f, 0.0f}, vup );
   m3x3_mulv( player.to_world, (v3f){ 1.0f, 0.0f, 0.0f}, vside );

   v3f cn0, cn1, cn2;
   
   int contact_count = 
      sample_if_resistant( contact_front ) +
      sample_if_resistant( contact_back ) +
      sample_if_resistant( contact_norm );
   
   if( contact_count < 3 )
   {
      player_start_air();
      return;
   }

   v3f norm;
   v3f v0, v1;
   v3_sub( contact_norm, contact_front, v0 );
   v3_sub( contact_back, contact_front, v1 );
   v3_cross( v1, v0, norm );
   v3_normalize( norm );

   vg_line( contact_norm, contact_front, 0xff00ff00 );
   vg_line( contact_back, contact_front, 0xff0000ff );

   /* Surface alignment */
   float angle = v3_dot( vup, norm );
   v3_cross( vup, norm, axis );

   if( angle < 0.999f )
   {
      v4f correction;
      q_axis_angle( correction, axis, acosf(angle) );
      q_mul( correction, player.rot, player.rot );
   }

   float resistance = v3_dot( norm, player.v );
   if( resistance >= 0.0f )
   {
      player_start_air();
      return;
   }
   else
   {
      v3_muladds( player.v, norm, -resistance, player.v );
   }
   
   /* This is where velocity integration used to be */

   float slip = 0.0f;

   player.co[1] = (contact_front[1]+contact_back[1])*0.5f;

   v3f vel;
   m3x3_mulv( player.to_local, player.v, vel );

   /* Calculate local forces */
   
   if( fabsf(vel[2]) > 0.01f )
      slip = fabsf(-vel[0] / vel[2]) * vg_signf(vel[0]);

   if( fabsf( slip ) > 1.2f )
      slip = vg_signf( slip ) * 1.2f;
   player.slip = slip;
   player.reverse = -vg_signf(vel[2]);

   float substep = ktimestep * 0.2f;
   float fwd_resistance = (vg_get_button( "break" )? 5.0f: 0.02f) * -substep;

   for( int i=0; i<5; i++ )
   {
      vel[2] = stable_force( vel[2], vg_signf( vel[2] ) * fwd_resistance );
      vel[0] = stable_force( vel[0], vg_signf( vel[0] ) * -7.0f *substep );
   }
   
   static double start_push = 0.0;
   if( vg_get_button_down( "push" ) )
      start_push = vg_time;

   if( !vg_get_button("break") && vg_get_button( "push" ) )
   {
      float const k_maxpush = 16.0f,
                  k_pushaccel = 5.0f;

      float cycle_time = vg_time-start_push,
            amt = k_pushaccel * (sinf( cycle_time * 8.0f )*0.5f+0.5f)*ktimestep,
            current = v3_length( vel ),
            new_vel = vg_minf( current + amt, k_maxpush );
      new_vel -= vg_minf(current, k_maxpush);
      vel[2] -= new_vel * player.reverse;
   }
   
   m3x3_mulv( player.to_world, vel, player.v );

   if( vg_get_button( "yawl" ) )
      player.iY +=  3.6f * ktimestep;
   if( vg_get_button( "yawr" ) )
      player.iY -=  3.6f * ktimestep;
   
   float steer = vg_get_axis( "horizontal" );
   player.iY -= vg_signf(steer)*powf(steer,2.0f) * 1.5f * ktimestep;
   
   /* Too much lean and it starts to look like a snowboard here */
   v2_lerp( player.board_xy, (v2f){ slip*0.25f, 0.0f }, 
         ktimestep*5.0f, player.board_xy);
}

static void draw_cross(v3f pos,u32 colour, float scale)
{
   v3f p0, p1;
   v3_add( (v3f){ scale,0.0f,0.0f}, pos, p0 );
   v3_add( (v3f){-scale,0.0f,0.0f}, pos, p1 );
   vg_line( p0, p1, colour );
   v3_add( (v3f){0.0f, scale,0.0f}, pos, p0 );
   v3_add( (v3f){0.0f,-scale,0.0f}, pos, p1 );
   vg_line( p0, p1, colour );
   v3_add( (v3f){0.0f,0.0f, scale}, pos, p0 );
   v3_add( (v3f){0.0f,0.0f,-scale}, pos, p1 );
   vg_line( p0, p1, colour );
}

static void player_physics_air(void)
{
   m3x3_mulv( player.vr, player.v, player.v );
   draw_cross( player.land_target, 0xff0000ff, 1 );

   v3f ground_pos;
   v3_copy( player.co, ground_pos );
   ground_pos[1] += 4.0f;
   
   ray_hit hit;
   hit.dist = INFINITY;
   if( ray_world( ground_pos, (v3f){0.0f,-1.0f,0.0f}, &hit ))
   {
      if( hit.pos[1] > player.co[1] )
      {
         player.in_air = 0;
         
         if( !ray_hit_is_ramp( &hit ) )
         {
            player.is_dead = 1;
            character_ragdoll_copypose( &player.mdl, player.v );
         }

         return;
      }
   }
   
   /* Prediction 
    */
   float pstep = ktimestep*10.0f;

   v3f pco, pco1, pv;
   v3_copy( player.co, pco );
   v3_copy( player.v, pv );
   
   float time_to_impact = 0.0f;
   float limiter = 1.0f;

   for( int i=0; i<50; i++ )
   {
      v3_copy( pco, pco1 );
      apply_gravity( pv, pstep );
      v3_muladds( pco, pv, pstep, pco );

      //vg_line( pco, pco1, i&0x1?0xff000000:0xffffffff );
      
      ray_hit contact;
      v3f vdir;

      v3_sub( pco, pco1, vdir );
      contact.dist = v3_length( vdir );
      v3_divs( vdir, contact.dist, vdir);
      
      float orig_dist = contact.dist;
      if( ray_world( pco1, vdir, &contact ))
      {
         v3f localup;
         m3x3_mulv( player.to_world, (v3f){0.0f,1.0f,0.0f}, localup );

         float angle = v3_dot( localup, contact.normal );
         v3f axis; 
         v3_cross( localup, contact.normal, axis );

         time_to_impact += (contact.dist/orig_dist)*pstep;
         limiter = vg_minf( 5.0f, time_to_impact )/5.0f;
         limiter = 1.0f-limiter;
         limiter *= limiter;
         limiter = 1.0f-limiter;

         if( angle < 0.99f )
         {
            v4f correction;
            q_axis_angle( correction, axis, acosf(angle)*0.05f*(1.0f-limiter) );
            q_mul( correction, player.rot, player.rot );
         }

         draw_cross( contact.pos, 0xffff0000, 1 );
         break;
      }
      time_to_impact += pstep;
   }

   player.iY -= vg_get_axis( "horizontal" ) * 3.6f * ktimestep;
   {

      float iX = vg_get_axis( "vertical" ) * 3.6f * limiter * ktimestep;
      static float siX = 0.0f;
      siX = vg_lerpf( siX, iX, 0.3f );
      
      v4f rotate;
      v3f vside;
      
      m3x3_mulv( player.to_world, (v3f){1.0f,0.0f,0.0f}, vside );

      q_axis_angle( rotate, vside, siX );
      q_mul( rotate, player.rot, player.rot );
   }
   
   v2f target = {0.0f,0.0f};
   v2_muladds( target, (v2f){ vg_get_axis("h1"), vg_get_axis("v1") },
               player.grab, target );
   v2_lerp( player.board_xy, target, ktimestep*3.0f, player.board_xy );
}

static void player_do_motion(void)
{
   float horizontal = vg_get_axis("horizontal"),
         vertical = vg_get_axis("vertical");

   player.joy_l[0] = vg_signf(horizontal) * powf( horizontal, 2.0f );
   player.joy_l[1] = vg_signf(vertical) * powf( vertical, 2.0f );

   if( player.in_air )
      player_physics_air();

   if( !player.in_air )
      player_physics_ground();
   
   /* Integrate velocity */
   v3f prevco;
   v3_copy( player.co, prevco );
   
   apply_gravity( player.v, ktimestep );
   v3_muladds( player.co, player.v, ktimestep, player.co );

   /* Integrate inertia */
   v4f rotate; v3f vup = {0.0f,1.0f,0.0f};
   m3x3_mulv( player.to_world, vup, vup );

   static float siY = 0.0f;

   float lerpq = player.in_air? 0.04f: 0.3f;
   siY = vg_lerpf( siY, player.iY, lerpq );

   q_axis_angle( rotate, vup, siY );
   q_mul( rotate, player.rot, player.rot );

   player.iY = 0.0f; /* temp */

   /* GATE COLLISION */

   for( int i=0; i<world.gate_count; i++ )
   {
      teleport_gate *gate = &world.gates[i];

      if( gate_intersect( gate, player.co, prevco ) )
      {
         m4x3_mulv( gate->transport, player.co, player.co );
         m3x3_mulv( gate->transport, player.v, player.v );
         m3x3_mulv( gate->transport, player.vl, player.vl );
         m3x3_mulv( gate->transport, player.v_last, player.v_last );
         m3x3_mulv( gate->transport, player.m, player.m );
         m3x3_mulv( gate->transport, player.bob, player.bob );

         v4f transport_rotation;
         m3x3_q( gate->transport, transport_rotation );
         q_mul( transport_rotation, player.rot, player.rot );

         break;
      }
   }

   /* Camera and character */
   player_transform_update();
   
   v3_lerp( player.vl, player.v, 0.05f, player.vl );

   player.angles[0] = atan2f(  player.vl[0], -player.vl[2] );
   player.angles[1] = atan2f( -player.vl[1], sqrtf(player.vl[0]*player.vl[0]+
                                            player.vl[2]*player.vl[2]) ) * 0.3f;
}

static int player_walkgrid_tri_walkable( u32 tri[3] )
{
   return tri[0] < world.sm_road.vertex_count;
}

#define WALKGRID_SIZE 16
struct walkgrid
{
   struct grid_sample
   {
      enum sample_type
      {
         k_sample_type_air,      /* Nothing was hit. */
         k_sample_type_invalid,  /* The point is invalid, but there is a sample
                                    underneath that can be used */
         k_sample_type_valid,    /* This point is good */
      }
      type;

      v3f clip[2];
      v3f pos;

      enum traverse_state
      {
         k_traverse_none = 0x00,
         k_traverse_h    = 0x01,
         k_traverse_v    = 0x02
      }
      state;
   }
   samples[WALKGRID_SIZE][WALKGRID_SIZE];

#if 0
   u32 geo[256];
#endif

   boxf region;

   float move; /* Current amount of movement we have left to apply */
   v2f dir;    /* The movement delta */
   v2i cell_id;/* Current cell */
   v2f pos;    /* Local position (in cell) */
   float h;
};

/*
 * Get a sample at this pole location, will return 1 if the sample is valid,
 * and pos will be updated to be the intersection location.
 */
static void player_walkgrid_samplepole( struct grid_sample *s )
{
   boxf region = {{ s->pos[0] -0.01f, s->pos[1] - 4.0f, s->pos[2] -0.01f},
                  { s->pos[0] +0.01f, s->pos[1] + 4.0f, s->pos[2] +0.01f}};

#if 0
   vg_line( region[0],region[1], 0x20ffffff );
#endif

   u32 geo[256];
   v3f tri[3];
   int len = bvh_select_triangles( &world.geo, region, geo, 256 );
   
   const float k_minworld_y = -2000.0f;

   float walk_height = k_minworld_y,
         block_height = k_minworld_y;

   s->type = k_sample_type_air;

   for( int i=0; i<len; i++ )
   {
      u32 *ptri = &world.geo.indices[ geo[i] ];

      for( int j=0; j<3; j++ )
         v3_copy( world.geo.verts[ptri[j]].co, tri[j] );
      
      v3f vdown = {0.0f,-1.0f,0.0f};
      v3f sample_from;
      v3_copy( s->pos, sample_from );
      sample_from[1] = region[1][1];
      
      float dist;
      if( ray_tri( tri, sample_from, vdown, &dist ))
      {
         v3f p0;
         v3_muladds( sample_from, vdown, dist, p0 );

         if( player_walkgrid_tri_walkable(ptri) )
         {
            if( p0[1] > walk_height )
            {
               walk_height = p0[1];
            }

#if 0
            draw_cross( p0, 0xffffffff, 0.05f );
#endif
         }
         else
         {
            if( p0[1] > block_height )
               block_height = p0[1];
#if 0
            draw_cross( p0, 0xff0000ff, 0.05f );
#endif
         }
      }
   }

   s->pos[1] = walk_height;

   if( walk_height > k_minworld_y )
      if( block_height > walk_height )
         s->type = k_sample_type_invalid;
      else
         s->type = k_sample_type_valid;
   else
      s->type = k_sample_type_air;
   
#if 0
   if( s->type == k_sample_type_valid )
   {
      vg_line_pt3( s->pos, 0.01f, 0xff00ff00 );
   }
#endif

#if 0
   int count = 0;

   ray_hit hit;
   hit.dist = 10.0f;
   count = bvh_raycast( &world.geo, sample_pos, vdir, &hit );

   if( count )
   {
      v3_copy( hit.pos, s->pos );

      if( !player_walkgrid_tri_walkable( hit.tri ) )
      {
         draw_cross( pos, 0xff0000ff, 0.05f );
         return 0;
      }
      else
      {
         draw_cross( pos, 0xff00ff00, 0.05f );
         return count;
      }
   }
   else
      return 0;
#endif
}

float const k_gridscale = 0.5f;

enum eclipdir
{
   k_eclipdir_h = 0,
   k_eclipdir_v = 1
};

static void player_walkgrid_clip_blocker( struct grid_sample *sa,
                                          struct grid_sample *sb,
                                          struct grid_sample *st,
                                          enum eclipdir dir )
{
   v3f clipdir, pos;
   int valid_a = sa->type == k_sample_type_valid,
       valid_b = sb->type == k_sample_type_valid;
   struct grid_sample *target = valid_a? sa: sb,
                      *other  = valid_a? sb: sa;
   v3_copy( target->pos, pos );
   v3_sub( other->pos, target->pos, clipdir );

   boxf cell_region;
   v3_muladds( pos, (v3f){1.0f,1.0f,1.0f}, -k_gridscale*2.1f, cell_region[0]);
   v3_muladds( pos, (v3f){1.0f,1.0f,1.0f},  k_gridscale*2.1f, cell_region[1]);

   u32 geo[256];
   v3f tri[3];
   int len = bvh_select_triangles( &world.geo, cell_region, geo, 256 );
   
   
   float start_time = v3_length( clipdir ),
         min_time = start_time;
   v3_normalize( clipdir );
   v3_muls( clipdir, 0.0001f, st->clip[dir] );

   for( int i=0; i<len; i++ )
   {
      u32 *ptri = &world.geo.indices[ geo[i] ];
      for( int j=0; j<3; j++ )
         v3_copy( world.geo.verts[ptri[j]].co, tri[j] );

      if( player_walkgrid_tri_walkable(ptri) )
         continue;

      float dist;
      if(ray_tri( tri, pos, clipdir, &dist ))
      {
         if( dist > 0.0f && dist < min_time )
         {
            min_time = dist;
            sb->type = k_sample_type_air;
         }
      }
   }

   if( !(min_time < start_time) )
      min_time = 0.5f * k_gridscale;

   min_time = vg_clampf( min_time/k_gridscale, 0.01f, 0.99f );

   v3_muls( clipdir, min_time, st->clip[dir] );

   v3f p0;
   v3_muladds( target->pos, st->clip[dir], k_gridscale, p0 );
}

static void player_walkgrid_clip_edge( struct grid_sample *sa,
                                       struct grid_sample *sb,
                                       struct grid_sample *st, /* data store */
                                       enum eclipdir dir )
{
   v3f clipdir = { 0.0f, 0.0f, 0.0f }, pos;
   int valid_a = sa->type == k_sample_type_valid,
       valid_b = sb->type == k_sample_type_valid;

   struct grid_sample *target = valid_a? sa: sb,
                      *other  = valid_a? sb: sa;
   
   v3_sub( other->pos, target->pos, clipdir );
   clipdir[1] = 0.0f;

   v3_copy( target->pos, pos );

   boxf cell_region;
   v3_muladds( pos, (v3f){1.0f,1.0f,1.0f}, -k_gridscale*1.1f, cell_region[0]);
   v3_muladds( pos, (v3f){1.0f,1.0f,1.0f},  k_gridscale*1.1f, cell_region[1]);

   u32 geo[256];
   int len = bvh_select_triangles( &world.geo, cell_region, geo, 256 );

   float max_dist = 0.0f;
   v3f tri[3];
   v3f perp;
   v3_cross( clipdir,(v3f){0.0f,1.0f,0.0f},perp );
   v3_muls( clipdir, 0.001f, st->clip[dir] );

   for( int i=0; i<len; i++ )
   {
      u32 *ptri = &world.geo.indices[ geo[i] ];
      for( int j=0; j<3; j++ )
         v3_copy( world.geo.verts[ptri[j]].co, tri[j] );
      
      if( !player_walkgrid_tri_walkable(ptri) )
         continue;

      for( int k=0; k<3; k++ )
      {
         int ia = k,
             ib = (k+1)%3;
         
         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 void player_walkgrid_clip( struct grid_sample *sa,
                                  struct grid_sample *sb,
                                  enum eclipdir dir )
{
   int mintype = VG_MIN( sa->type, sb->type ),
       maxtype = VG_MAX( sa->type, sb->type );

   if( maxtype == k_sample_type_valid )
   {
      if( mintype == k_sample_type_air || mintype == k_sample_type_invalid )
      {
         player_walkgrid_clip_edge( sa, sb, sa, dir );
      }

#if 0
      else if( mintype == k_sample_type_invalid )
      {
         player_walkgrid_clip_blocker( sa, sb, dir );
      }
#endif
   }
}

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
    */

#if 0
   if( wg->cell_id[0] < 0 || wg->cell_id[0] >= WALKGRID_SIZE-1 ||
       wg->cell_id[1] < 0 || wg->cell_id[1] >= WALKGRID_SIZE-1 )
   {
      /*
       * This condition should never be reached if the grid size is big 
       * enough
       */
      wg->move = -1.0f;
      return;
   }
#endif

   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
   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.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.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.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 );
   }

   /* 
    * 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.co[0] - wg.region[0][0]) * (1.0f/k_gridscale),
      (player.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];


#if 0
   /* Get surface samples
    *
    * TODO: Replace this with a spiral starting from the player position
    */
   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->pos[1] = cell[1];
         player_walkgrid_samplepole( s );
      }
   }
   
   /* 
    * Calculate h+v clipping distances.
    * Distances are stored in A always, so you know that if the sample is
    * invalid, this signifies the start of the manifold as opposed to the
    * extent or bounds of it.
    */
   for( int i=0; i<2; i++ )
   {
      for( int x=0; x<WALKGRID_SIZE; x++ )
      {
         for( int z=0; z<WALKGRID_SIZE-1; z++ )
         {
            struct grid_sample *sa, *sb;
            if( i == 1 )
            {
               sa = &wg.samples[z][x];
               sb = &wg.samples[z+1][x];
            }
            else
            {
               sa = &wg.samples[x][z];
               sb = &wg.samples[x][z+1];
            }
            
            player_walkgrid_clip( sa, sb, i );

            if( sa->type == k_sample_type_valid && 
                sb->type == k_sample_type_valid )
               vg_line( sa->pos, sb->pos, 0xffffffff );
#if 0
            if( sa->valid != sb->valid )
            {
               clipdir[i*2] = (float)(sa->valid - sb->valid) * k_gridscale;

               player_walkgrid_clip( sa->valid? sa->pos: sb->pos,
                                     clipdir, sa->clip[i] );
            }
            else
            {
               if( sa->valid )
               {
                  vg_line( sa->pos, sb->pos, 0xffffffff );
               }
            }
#endif
         }
      }
   }
#endif
   
   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 )
         break;
   }

#if 0
   player.co[0] += wg.dir[0];
   player.co[2] += wg.dir[1];
#endif



   /* Draw connections */
   struct grid_sample *corners[4];
   for( int x=0; x<WALKGRID_SIZE-1; x++ )
   {
      for( int z=0; z<WALKGRID_SIZE-1; z++ )
      {
         const struct conf *conf = 
            player_walkgrid_conf( &wg, (v2i){x,z}, corners );

         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 );

            vg_line( p0, p1, 0xff0000ff );
         }
      }
   }

   /*
    * Commit player movement into the grid 
    */
   
   if( v3_length2(delta) <= 0.00001f )
      return;
   
   int i=0;
   for(; i<8 && wg.move > 0.001f; i++ )
      player_walkgrid_iter( &wg, i );

   player_walkgrid_stand_cell( &wg );
}

static void player_walkgrid(void)
{
   player_walkgrid_getsurface();
   
   m4x3_mulv( player.to_world, (v3f){0.0f,1.8f,0.0f}, player.camera_pos );
   player_mouseview();
   player_transform_update();
}

static void player_animate(void)
{
   /* Camera position */
   v3_sub( player.v, player.v_last, player.a );
   v3_copy( player.v, player.v_last );

   v3_add( player.m, player.a, player.m );
   v3_lerp( player.m, (v3f){0.0f,0.0f,0.0f}, 0.1f, player.m );
   v3f target;
   
   player.m[0] = vg_clampf( player.m[0], -2.0f, 2.0f );
   player.m[1] = vg_clampf( player.m[1], -0.2f, 5.0f );
   player.m[2] = vg_clampf( player.m[2], -2.0f, 2.0f );
   v3_copy( player.m, target );
   v3_lerp( player.bob, target, 0.2f, player.bob );

   /* Head */
   float lslip = fabsf(player.slip); //vg_minf( 0.4f, slip );
                              
   float grabt = vg_get_axis( "grabr" )*0.5f+0.5f;
   player.grab = vg_lerpf( player.grab, grabt, 0.04f );

   float kheight = 2.0f,
         kleg = 0.6f;

   v3f head;
   head[0] = 0.0f;
   head[1] = (0.3f+cosf(lslip)*0.5f*(1.0f-player.grab*0.7f)) * kheight;
   head[2] = 0.0f;

   v3f offset;
   m3x3_mulv( player.to_local, player.bob, offset );

   offset[0] *= 0.3333f;
   offset[1] *= -0.25f;
   offset[2] *= 0.7f;
   v3_muladds( head, offset, 0.7f, head );
   head[1] = vg_clampf( head[1], 0.3f, kheight );

#if 0
   if( !freecam )
   {
      v3_copy( head, player.view );
      v3f camoffs = {-0.2f,-0.6f,0.00f};
      v3_add( player.view, camoffs, player.view );
   }
#endif

   /* 
    * Animation blending
    * ===========================================
    */

   static float fslide = 0.0f;
   static float fdirz = 0.0f;
   static float fdirx = 0.0f;
   static float fstand = 0.0f;
   static float ffly = 0.0f;

   float speed = v3_length( player.v );
   
   fstand = vg_lerpf(fstand, 1.0f-vg_clampf(speed*0.03f,0.0f,1.0f),0.1f);
   fslide = vg_lerpf(fslide, vg_clampf(lslip+fabsf(offset[0])*0.2f,
            0.0f,1.0f), 0.04f);
   fdirz = vg_lerpf(fdirz, player.reverse > 0.0f? 1.0f: 0.0f, 0.04f );
   fdirx = vg_lerpf(fdirx, player.slip < 0.0f?    1.0f: 0.0f, 0.04f );
   ffly = vg_lerpf(ffly, player.in_air?           1.0f: 0.0f, 0.04f );

   character_pose_reset( &player.mdl );

   float amt_air = ffly*ffly,
         amt_ground = 1.0f-amt_air,
         amt_std = (1.0f-fslide) * amt_ground,
         amt_stand = amt_std * fstand,
         amt_aero = amt_std * (1.0f-fstand),
         amt_slide = amt_ground * fslide;

   character_final_pose( &player.mdl, offset, &pose_stand, amt_stand*fdirz );
   character_final_pose( &player.mdl, offset, 
         &pose_stand_reverse, amt_stand * (1.0f-fdirz) );

   character_final_pose( &player.mdl, offset, &pose_aero, amt_aero*fdirz );
   character_final_pose( &player.mdl, offset, 
         &pose_aero_reverse, amt_aero * (1.0f-fdirz) );

   character_final_pose( &player.mdl, offset, &pose_slide, amt_slide*fdirx );
   character_final_pose( &player.mdl, offset, 
         &pose_slide1, amt_slide*(1.0f-fdirx) );

   character_final_pose( &player.mdl, (v3f){0.0f,0.0f,0.0f}, 
         &pose_fly, amt_air );

   /* Camera position */
   v3_lerp( player.smooth_localcam, player.mdl.cam_pos, 0.08f, 
            player.smooth_localcam );
   v3_muladds( player.smooth_localcam, offset, 0.7f, player.camera_pos );
   player.camera_pos[1] = vg_clampf( player.camera_pos[1], 0.3f, kheight );
   m4x3_mulv( player.to_world, player.camera_pos, player.camera_pos );

   player.air_blend = vg_lerpf( player.air_blend, player.in_air, 0.04f );
   v3_muladds( player.camera_pos, player.v, -0.05f*player.air_blend, 
         player.camera_pos );

   /* 
    * Additive effects
    * ==========================
    */
   struct ik_basic *arm_l = &player.mdl.ik_arm_l,
                   *arm_r = &player.mdl.ik_arm_r;

   v3f localv;
   m3x3_mulv( player.to_local, player.v, localv );
   v3_muladds( arm_l->end, localv, -0.01f, arm_l->end );
   v3_muladds( arm_r->end, localv, -0.01f, arm_r->end );

   /* New board transformation */
   v4f board_rotation; v3f board_location;

   v4f rz, rx;
   q_axis_angle( rz, (v3f){ 0.0f, 0.0f, 1.0f }, player.board_xy[0] );
   q_axis_angle( rx, (v3f){ 1.0f, 0.0f, 0.0f }, player.board_xy[1] );
   q_mul( rx, rz, board_rotation );
   
   v3f *mboard = player.mdl.matrices[k_chpart_board];// player.mboard;
   q_m3x3( board_rotation, mboard );
   m3x3_mulv( mboard, (v3f){ 0.0f, -0.5f, 0.0f }, board_location );
   v3_add( (v3f){0.0f,0.5f,0.0f}, board_location, board_location );
   v3_copy( board_location, mboard[3] );


   float wheel_r = offset[0]*-0.4f;
   v4f qwheel;
   q_axis_angle( qwheel, (v3f){0.0f,1.0f,0.0f}, wheel_r );
   
   q_m3x3( qwheel, player.mdl.matrices[k_chpart_wb] );

   m3x3_transpose( player.mdl.matrices[k_chpart_wb],
                   player.mdl.matrices[k_chpart_wf] );
   v3_copy( player.mdl.offsets[k_chpart_wb], 
         player.mdl.matrices[k_chpart_wb][3] );
   v3_copy( player.mdl.offsets[k_chpart_wf], 
         player.mdl.matrices[k_chpart_wf][3] );
   
   m4x3_mul( mboard, player.mdl.matrices[k_chpart_wb],
                     player.mdl.matrices[k_chpart_wb] );
   m4x3_mul( mboard, player.mdl.matrices[k_chpart_wf],
                     player.mdl.matrices[k_chpart_wf] );

   m4x3_mulv( mboard, player.mdl.ik_leg_l.end, player.mdl.ik_leg_l.end );
   m4x3_mulv( mboard, player.mdl.ik_leg_r.end, player.mdl.ik_leg_r.end );


   v3_copy( player.mdl.ik_arm_l.end, player.handl_target );
   v3_copy( player.mdl.ik_arm_r.end, player.handr_target );

   if( 1||player.in_air )
   {
      float tuck = player.board_xy[1],
            tuck_amt = fabsf( tuck ) * (1.0f-fabsf(player.board_xy[0]));
      
      float crouch = player.grab*0.3f;
      v3_muladds( player.mdl.ik_body.base, (v3f){0.0f,-1.0f,0.0f}, 
            crouch, player.mdl.ik_body.base );
      v3_muladds( player.mdl.ik_body.end, (v3f){0.0f,-1.0f,0.0f}, 
            crouch*1.2f, player.mdl.ik_body.end );

      if( tuck < 0.0f )
      {
         //foot_l *= 1.0f-tuck_amt*1.5f;

         if( player.grab > 0.1f )
         {
            m4x3_mulv( mboard, (v3f){0.1f,0.14f,0.6f}, 
                  player.handl_target );
         }
      }
      else
      {
         //foot_r *= 1.0f-tuck_amt*1.4f;

         if( player.grab > 0.1f )
         {
            m4x3_mulv( mboard, (v3f){0.1f,0.14f,-0.6f}, 
                  player.handr_target );
         }
      }
   }

   v3_lerp( player.handl, player.handl_target, 0.1f, player.handl );
   v3_lerp( player.handr, player.handr_target, 0.1f, player.handr );

   v3_copy( player.handl, player.mdl.ik_arm_l.end );
   v3_copy( player.handr, player.mdl.ik_arm_r.end );

   /* Head rotation */

   static float rhead = 0.0f;
   rhead = vg_lerpf( rhead,
         vg_clampf(atan2f( localv[2], -localv[0] ),-1.0f,1.0f), 0.04f );
   player.mdl.rhead = rhead;
}

static int giftwrapXZ( v3f *points, int *output, int len )
{
   int l, p, q, count;

   if( len < 3 )
      return 0;

   l = 0;
   for( int i=1; i<len; i++ )
      if( points[i][0] < points[l][0] )
         l = i;

   p = l;
   count = 0;
   do
   {
      if( count >= len )
      {
         vg_error ("MANIFOLD ERR (%d)\n", count );
         return 0;
      }
      output[ count ++ ] = p;

      q = (p+1)%len;

      for( int i=0; i<len; i++ )
      {
         float orient = 
             (points[i][2]-points[p][2])*(points[q][0]-points[i][0]) -
             (points[i][0]-points[p][0])*(points[q][2]-points[i][2]);

         if( orient > 0.0001f )
         {
            q = i;
         }
      }
      p = q;
   }
   while( p != l );
   
   return count;
}
 
static void player_do_collision( rigidbody *rb )
{
   /*
    * If point is inside box
    *   find normal (theres 8 simple pyramid regions for this, x>y/dim .. etc)
    *   find distance (same sorta thing)
    *
    * apply normal impulse to rotation
    * correct position based on new penetration amount if needed
    * apply normal impulse to velocity
    */

   v3f pfront, pback;
   m4x3_mulv( player.to_world, (v3f){ 0.0f,0.0f,-1.0f }, pfront );
   m4x3_mulv( player.to_world, (v3f){ 0.0f,0.0f, 1.0f }, pback );

   float const kheight = 2.0f;
   
   v3f verts[8];

   v3f a, b;
   v3_copy( rb->bbx[0], a );
   v3_copy( rb->bbx[1], b );

   m4x3f compound;
   m4x3_mul( player.to_local, rb->to_world, compound );
   
        m4x3_mulv( compound, (v3f){ a[0], a[1], a[2] }, verts[0] );
        m4x3_mulv( compound, (v3f){ a[0], b[1], a[2] }, verts[1] );
        m4x3_mulv( compound, (v3f){ b[0], b[1], a[2] }, verts[2] );
        m4x3_mulv( compound, (v3f){ b[0], a[1], a[2] }, verts[3] );
        m4x3_mulv( compound, (v3f){ a[0], a[1], b[2] }, verts[4] );
        m4x3_mulv( compound, (v3f){ a[0], b[1], b[2] }, verts[5] );
        m4x3_mulv( compound, (v3f){ b[0], b[1], b[2] }, verts[6] );
        m4x3_mulv( compound, (v3f){ b[0], a[1], b[2] }, verts[7] );

   int const indices[12][2] = {
      {0,1},{1,2},{2,3},{3,0},{4,5},{5,6},{6,7},{7,4},
      {0,4},{1,5},{2,6},{3,7}
   };
   
   v3f hull[12*2 + 8];
   int hull_indices[12*2 + 8];
   int hull_len = 0;

   for( int i=0; i<8; i++ )
   {
      int ia = indices[i][0];
      float ya = verts[ia][1];

      if( ya > 0.2f && ya < kheight )
      {
         int add_point = 1;
         for( int j=0; j<hull_len; j++ )
         {
            v2f delta = { verts[ia][0]-hull[j][0], verts[ia][2]-hull[j][2] };
            if( v2_length2( delta ) < 0.0004f )
            {
               add_point = 0;
               break;
            }
         }

         if( add_point )
            v3_copy( verts[ia], hull[hull_len] );

         hull[hull_len ++][1] = 0.2f;
      }
   }

   for( int i=0; i<vg_list_size(indices); i++ )
   {
      int ia = indices[i][0],
          ib = indices[i][1];

      v3f p0, p1;

      float ya = verts[ia][1],
            yb = verts[ib][1],
            d = 1.0f/(yb-ya),
            qa;

      float planes[] = { 0.2f, kheight };
      
      for( int k=0; k<vg_list_size(planes); k++ )
      {
         float clip = planes[k];

         if( (ya-clip) * (yb-clip) < 0.0f )
         {
            v3_muls( verts[ia], (yb-clip)*d, p0 );
            v3_muladds( p0, verts[ib], -(ya-clip)*d, p0 );
            
            int add_point = 1;
            for( int j=0; j<hull_len; j++ )
            {
               v2f delta = { p0[0]-hull[j][0], p0[2]-hull[j][2] };
               if( v2_length2( delta ) < 0.0004f )
               {
                  add_point = 0;
                  break;
               }
            }

            if( add_point )
               v3_copy( p0, hull[hull_len ++] );

            m4x3_mulv( player.to_world, p0, p0 );
            vg_line_pt3( p0, 0.1f, 0xffffff00 );
         }
      }
   }

   if( hull_len < 3 ) 
      return;

   int len = giftwrapXZ( hull, hull_indices, hull_len );
   for( int i=0; i<len; i++ )
   {
      v3f p0, p1, p2, p3;
      v3_copy( hull[hull_indices[i]], p0 );
      v3_copy( hull[hull_indices[(i+1)%len]], p1 );
      p0[1] = 0.2f;
      p1[1] = 0.2f;
      v3_add( p0, (v3f){0,kheight-0.2f,0}, p2 );
      v3_add( p1, (v3f){0,kheight-0.2f,0}, p3 );
         
      m4x3_mulv( player.to_world, p0, p0 );
      m4x3_mulv( player.to_world, p1, p1 );
      m4x3_mulv( player.to_world, p2, p2 );
      m4x3_mulv( player.to_world, p3, p3 );

      vg_line2( p0, p1, 0xff00ffff, 0xff000000 );
      vg_line( p2, p3, 0xff00ffff );
      vg_line( p0, p2, 0xff00ffa0 );
   }

   v2f endpoints[] = {{ 0.0f, -1.0f },{ 0.0f, 1.0f }};
   
   for( int j=0; j<vg_list_size(endpoints); j++ )
   {
      v2f point;
      v2_copy( endpoints[j], point );

      int collide = 1;
      float min_dist = 99999.9f;
      v2f normal;
      for( int i=0; i<len; i++ )
      {
         v2f p0, p1;
         p0[0] = hull[hull_indices[i]][0];
         p0[1] = hull[hull_indices[i]][2];
         p1[0] = hull[hull_indices[(i+1)%len]][0];
         p1[1] = hull[hull_indices[(i+1)%len]][2];
         
         v2f t,n, rel;
         v2_sub( p1, p0, t );
         n[0] = -t[1];
         n[1] =  t[0];
         v2_normalize(n);
         
         v2_sub( point, p0, rel );
         float d = -v2_dot( n, rel ) + 0.5f;

         if( d < 0.0f )
         {
            collide = 0;
            break;
         }

         if( d < min_dist )
         {
            min_dist = d;
            v2_copy( n, normal );
         }
      }

      if( collide )
      {
         v3f p0, p1;
         p0[0] =  0.0f;
         p0[1] =  0.2f;
         p0[2] = -1.0f;

         p1[0] = p0[0] + normal[0]*min_dist;
         p1[1] = p0[1];
         p1[2] = p0[2] + normal[1]*min_dist;
         
         m4x3_mulv( player.to_world, p0, p0 );
         m4x3_mulv( player.to_world, p1, p1 );

         vg_line( p0, p1, 0xffffffff );
         
         v3f vel;
         m3x3_mulv( player.to_local, player.v, vel );
         vel[1] = vel[2];

         float vn = vg_maxf( -v2_dot( vel, normal ), 0.0f );
         vn += -0.2f * (1.0f/k_rb_delta) * vg_minf( 0.0f, -min_dist+0.04f );
         
         v2f impulse;
         if( vn > 14.0f )
         {
            player.is_dead = 1;
            character_ragdoll_copypose( &player.mdl, player.v );
            return;
         }

         if( vn > 0.0f )
         {
            v2_muls( normal, min_dist, impulse );
            float rotation = v2_cross( point, impulse )*0.08f;
            v4f rot;
            v3f up = {0.0f,1.0f,0.0f};
            m3x3_mulv( player.to_world, up, up );
            q_axis_angle( rot, up, -rotation );
            q_mul( rot, player.rot, player.rot );
         }

         v2_muls( normal, vn*0.03f, impulse );
         v3f impulse_world = { impulse[0], 0.0f, impulse[1] };

         m3x3_mulv( player.to_world, impulse_world, impulse_world );
         v3_add( impulse_world, player.v, player.v );
      }
   }
}

static void player_update(void)
{
   for( int i=0; i<player.land_log_count; i++ )
      draw_cross( player.land_target_log[i], player.land_target_colours[i], 1);

   if( vg_get_axis("grabl")>0.0f)
      reset_player(0,NULL);

   if( freecam )
   {
      player_freecam();
   }
   else
   {
      if( player.is_dead )
      {
         character_ragdoll_iter( &player.mdl );
         character_debug_ragdoll( &player.mdl );
      }
      else
      {
         if( player.on_board )
         {
            bh_debug_node(&world.bhcubes, 0, 
                  player.camera_pos, 0xff80ff00 );

            u32 colliders[16];
            boxf wbox = {{ -2.0f, -2.0f, -2.0f },
                         {  2.0f,  2.0f,  2.0f }};
            m4x3_transform_aabb( player.to_world, wbox );
            int len = bh_select( &world.bhcubes, wbox, colliders, 32 );

            for( int i=0; i<len; i++ )
               player_do_collision( &world.temp_rbs[colliders[i]] );

            player_do_motion();
            player_animate();
         }
         else
         {
            player_walkgrid();
         }
      }
   }

   /* Update camera matrices */
   m4x3_identity( player.camera );
   m4x3_rotate_y( player.camera, -player.angles[0] );
   m4x3_rotate_x( player.camera, -0.33f -player.angles[1] );
   v3_copy( player.camera_pos, player.camera[3] );
   m4x3_invert_affine( player.camera, player.camera_inverse );
}

static void draw_player(void)
{
   /* Draw */
   m4x3_copy( player.to_world, player.mdl.mroot );

   if( player.is_dead )
      character_mimic_ragdoll( &player.mdl );
   else
      character_eval( &player.mdl );

   character_draw( &player.mdl, (player.is_dead|player.in_air)? 0.0f: 1.0f );
}

#endif /* PLAYER_H */