modelcollide.cpp

Go to the documentation of this file.

/*
 * Copyright (C) Volition, Inc. 1999.  All rights reserved.
 *
 * All source code herein is the property of Volition, Inc. You may not sell 
 * or otherwise commercially exploit the source or things you created based on the 
 * source.
 *
*/ 




#define MODEL_LIB

#include "cmdline/cmdline.h"
#include "graphics/tmapper.h"
#include "math/fvi.h"
#include "math/vecmat.h"
#include "model/model.h"
#include "model/modelsinc.h"



#define TOL             1E-4
#define DIST_TOL        1.0

// Some global variables that get set by model_collide and are used internally for
// checking a collision rather than passing a bunch of parameters around. These are
// not persistant between calls to model_collide

static mc_info          *Mc;                            // The mc_info passed into model_collide
        
static polymodel        *Mc_pm;                 // The polygon model we're checking
static int                      Mc_submodel;    // The current submodel we're checking

static polymodel_instance *Mc_pmi;

static matrix           Mc_orient;              // A matrix to rotate a world point into the current
                                                                                        // submodel's frame of reference.
static vec3d            Mc_base;                        // A point used along with Mc_orient.

static vec3d            Mc_p0;                  // The ray origin rotated into the current submodel's frame of reference
static vec3d            Mc_p1;                  // The ray end rotated into the current submodel's frame of reference
static float            Mc_mag;                 // The length of the ray
static vec3d            Mc_direction;   // A vector from the ray's origin to its end, in the current submodel's frame of reference

static vec3d            **Mc_point_list = NULL;         // A pointer to the current submodel's vertex list

static float            Mc_edge_time;


void model_collide_free_point_list()
{
        if (Mc_point_list != NULL) {
                vm_free(Mc_point_list);
                Mc_point_list = NULL;
        }
}

// allocate the point list
// NOTE: SHOULD ONLY EVER BE CALLED FROM model_allocate_interp_data()!!!
void model_collide_allocate_point_list(int n_points)
{
        Assert( n_points > 0 );

        if (Mc_point_list != NULL) {
                vm_free(Mc_point_list);
                Mc_point_list = NULL;
        }

        Mc_point_list = (vec3d**) vm_malloc( sizeof(vec3d *) * n_points );

        Verify( Mc_point_list != NULL );
}

// Returns non-zero if vector from p0 to pdir 
// intersects the bounding box.
// hitpos could be NULL, so don't fill it if it is.
int mc_ray_boundingbox( vec3d *min, vec3d *max, vec3d * p0, vec3d *pdir, vec3d *hitpos )
{

        vec3d tmp_hitpos;
        if ( hitpos == NULL )   {
                hitpos = &tmp_hitpos;
        }


        if ( Mc->flags & MC_CHECK_SPHERELINE )  {

                // In the case of a sphere, just increase the size of the box by the radius 
                // of the sphere in all directions.

                vec3d sphere_mod_min, sphere_mod_max;

                sphere_mod_min.xyz.x = min->xyz.x - Mc->radius;
                sphere_mod_max.xyz.x = max->xyz.x + Mc->radius;
                sphere_mod_min.xyz.y = min->xyz.y - Mc->radius;
                sphere_mod_max.xyz.y = max->xyz.y + Mc->radius;
                sphere_mod_min.xyz.z = min->xyz.z - Mc->radius;
                sphere_mod_max.xyz.z = max->xyz.z + Mc->radius;

                return fvi_ray_boundingbox( &sphere_mod_min, &sphere_mod_max, p0, pdir, hitpos );
        } else {
                return fvi_ray_boundingbox( min, max, p0, pdir, hitpos );
        }       
}



// ----- 
// mc_check_face
// nv -- number of vertices
// verts -- actual vertices
// plane_pnt -- A point on the plane.  Could probably use the first vertex.
// plane_norm -- normal of the plane
// uvl_list -- list of uv coords for the poly.
// ntmap -- The tmap index into the model's textures array.
//
// detects whether or not a vector has collided with a polygon.  vector points stored in global
// Mc_p0 and Mc_p1.  Results stored in global mc_info * Mc.

static void mc_check_face(int nv, vec3d **verts, vec3d *plane_pnt, float face_rad, vec3d *plane_norm, uv_pair *uvl_list, int ntmap, ubyte *poly, bsp_collision_leaf* bsp_leaf)
{
        vec3d   hit_point;
        float           dist;
        float           u, v;

        // Check to see if poly is facing away from ray.  If so, don't bother
        // checking it.
        if (vm_vec_dot(&Mc_direction,plane_norm) > 0.0f)        {
                return;
        }

        // Find the intersection of this ray with the plane that the poly
        dist = fvi_ray_plane(NULL, plane_pnt, plane_norm, &Mc_p0, &Mc_direction, 0.0f);

        if ( dist < 0.0f ) return; // If the ray is behind the plane there is no collision
        if ( !(Mc->flags & MC_CHECK_RAY) && (dist > 1.0f) ) return; // The ray isn't long enough to intersect the plane

        // If the ray hits, but a closer intersection has already been found, return
        if ( Mc->num_hits && (dist >= Mc->hit_dist ) ) return;  

        // Find the hit point
        vm_vec_scale_add( &hit_point, &Mc_p0, &Mc_direction, dist );
        
        // Check to see if the point of intersection is on the plane.  If so, this
        // also finds the uv's where the ray hit.
        if ( fvi_point_face(&hit_point, nv, verts, plane_norm, &u,&v, uvl_list ) )      {
                Mc->hit_dist = dist;

                Mc->hit_point = hit_point;
                Mc->hit_submodel = Mc_submodel;

                Mc->hit_normal = *plane_norm;

                if ( uvl_list ) {
                        Mc->hit_u = u;
                        Mc->hit_v = v;
                        if ( ntmap < 0 ) {
                                Mc->hit_bitmap = -1;
                        } else {
                                Mc->hit_bitmap = Mc_pm->maps[ntmap].textures[TM_BASE_TYPE].GetTexture();                        
                        }
                }
                
                if(ntmap >= 0){
                        Mc->t_poly = poly;
                        Mc->f_poly = NULL;
                } else {
                        Mc->t_poly = NULL;
                        Mc->f_poly = poly;
                }

                Mc->bsp_leaf = bsp_leaf;

//              mprintf(( "Bing!\n" ));

                Mc->num_hits++;
        }
}

// ----------------------------------------------------------------------------------------------------------
// check face with spheres
//
//      inputs: nv                              =>              number of vertices
//                              verts                   =>              array of vertices
//                              plane_pnt       =>              center point in plane (about which radius is measured)
//                              face_rad                =>              radius of face 
//                              plane_norm      =>              normal of face
static void mc_check_sphereline_face( int nv, vec3d ** verts, vec3d * plane_pnt, float face_rad, vec3d * plane_norm, uv_pair * uvl_list, int ntmap, ubyte *poly, bsp_collision_leaf *bsp_leaf)
{
        vec3d   hit_point;
        float           u, v;
        float           delta_t;                        // time sphere takes to cross from one side of plane to the other
        float           face_t;                 // time at which face touches plane
                                                                        // NOTE all times are normalized so that t = 1.0 at the end of the frame
        int             check_face = 1;         // assume we'll check the face.
        int             check_edges = 1;                // assume we'll check the edges.
        
        // Check to see if poly is facing away from ray.  If so, don't bother
        // checking it.

        if (vm_vec_dot(&Mc_direction,plane_norm) > 0.0f)        {
                return;
        }

        // Find the intersection of this sphere with the plane of the poly
        if ( !fvi_sphere_plane( &hit_point, &Mc_p0, &Mc_direction, Mc->radius, plane_norm, plane_pnt, &face_t, &delta_t ) ) {
                return;
        }

        // If the ray is behind the plane there is no collision
        if (face_t > 1.0f) {
                check_face = 0;
                check_edges = 0;
        } else if (face_t < 0.0f) {
                check_face = 0;

                // check whether sphere can hit edge in allowed time range
                if ( (face_t + delta_t) < 0.0f)
                        check_edges = 0;
        }

        // If the ray hits, but a closer intersection has already been found, don't check face
        if ( Mc->num_hits && (face_t >= Mc->hit_dist ) ) {
                check_face = 0;         // The ray isn't long enough to intersect the plane
        }


        //vec3d temp_sphere;
        //vec3d temp_dir;
        //float temp_dist;
        // DA 11/5/97  Above is used to test distance between hit_point and sphere_hit_point.
        // This can be as large as 0.003 on a unit sphere.  I suspect that with larger spheres,
        // both the relative and absolute error decrease, but this should still be checked for the
        // case of larger spheres (about 5-10 units).  The error also depends on the geometry of the 
        // object we're colliding against, but I think to a lesser degree.

        if ( check_face )       {
                // Find the time of the sphere surface touches the plane
                // If this is within the collision window, check to see if we hit a face
                if ( fvi_point_face(&hit_point, nv, verts, plane_norm, &u, &v, uvl_list) ) {

                        Mc->hit_dist = face_t;          
                        Mc->hit_point = hit_point;
                        Mc->hit_normal = *plane_norm;
                        Mc->hit_submodel = Mc_submodel;                 
                        Mc->edge_hit = 0;

                        if ( uvl_list ) {
                                Mc->hit_u = u;
                                Mc->hit_v = v;
                                if ( ntmap < 0 ) {
                                        Mc->hit_bitmap = -1;
                                } else {
                                        Mc->hit_bitmap = Mc_pm->maps[ntmap].textures[TM_BASE_TYPE].GetTexture();                        
                                }
                        }

                        if(ntmap >= 0){
                                Mc->t_poly = poly;
                                Mc->f_poly = NULL;
                        } else {
                                Mc->t_poly = NULL;
                                Mc->f_poly = poly;
                        }

                        Mc->bsp_leaf = bsp_leaf;

                        Mc->num_hits++;
                        check_edges = 0;
                        /*
                        vm_vec_scale_add( &temp_sphere, &Mc_p0, &Mc_direction, Mc->hit_dist );
                        temp_dist = vm_vec_dist( &temp_sphere, &hit_point );
                        if ( (temp_dist - DIST_TOL > Mc->radius) || (temp_dist + DIST_TOL < Mc->radius) ) {
                                // get Andsager
                                //mprintf(("Estimated radius error: Estimate %f, actual %f Mc->radius\n", temp_dist, Mc->radius));
                        }
                        vm_vec_sub( &temp_dir, &hit_point, &temp_sphere );
                        // Assert( vm_vec_dot( &temp_dir, &Mc_direction ) > 0 );
                        */
                }
        }


        if ( check_edges ) {
                // Either (face_t) is out of range or we miss the face
                // Check for sphere hitting edge

                // If checking shields, we *still* need to check edges

                // this is where we need another test to cull checking for edges
                // PUT TEST HERE

                // check each edge to see if we hit, find the closest edge
                // Mc->hit_dist stores the best edge time of *all* faces
                float sphere_time;
                if ( fvi_polyedge_sphereline(&hit_point, &Mc_p0, &Mc_direction, Mc->radius, nv, verts, &sphere_time)) {
                        Assert( sphere_time >= 0.0f );
                        /*
                        vm_vec_scale_add( &temp_sphere, &Mc_p0, &Mc_direction, sphere_time );
                        temp_dist = vm_vec_dist( &temp_sphere, &hit_point );
                        if ( (temp_dist - DIST_TOL > Mc->radius) || (temp_dist + DIST_TOL < Mc->radius) ) {
                                // get Andsager
                                //mprintf(("Estimated radius error: Estimate %f, actual %f Mc->radius\n", temp_dist, Mc->radius));
                        }
                        vm_vec_sub( &temp_dir, &hit_point, &temp_sphere );
//                      Assert( vm_vec_dot( &temp_dir, &Mc_direction ) > 0 );
                        */

                        if ( (Mc->num_hits==0) || (sphere_time < Mc->hit_dist) ) {
                                // This is closer than best so far
                                Mc->hit_dist = sphere_time;
                                Mc->hit_point = hit_point;
                                Mc->hit_submodel = Mc_submodel;
                                Mc->edge_hit = 1;
                                if ( ntmap < 0 ) {
                                        Mc->hit_bitmap = -1;
                                } else {
                                        Mc->hit_bitmap = Mc_pm->maps[ntmap].textures[TM_BASE_TYPE].GetTexture();                        
                                }

                                if(ntmap >= 0){
                                        Mc->t_poly = poly;
                                        Mc->f_poly = NULL;
                                } else {
                                        Mc->t_poly = NULL;
                                        Mc->f_poly = poly;
                                }

                                Mc->num_hits++;

                        //      nprintf(("Physics", "edge sphere time: %f, normal: (%f, %f, %f) hit_point: (%f, %f, %f)\n", sphere_time,
                        //              Mc->hit_normal.xyz.x, Mc->hit_normal.xyz.y, Mc->hit_normal.xyz.z,
                        //              hit_point.xyz.x, hit_point.xyz.y, hit_point.xyz.z));
                        } else  {       // Not best so far
                                Assert(Mc->num_hits>0);
                                Mc->num_hits++;
                        }
                }
        }
}


// Point list
// +0      int         id
// +4      int         size
// +8      int         n_verts
// +12     int         n_norms
// +16     int         offset from start of chunk to vertex data
// +20     n_verts*char    norm_counts
// +offset             vertex data. Each vertex n is a point followed by norm_counts[n] normals.     
void model_collide_defpoints(ubyte * p)
{
        int n;
        int nverts = w(p+8);    
        int offset = w(p+16);   

        ubyte * normcount = p+20;
        vec3d *src = vp(p+offset);
        
        Assert( Mc_point_list != NULL );

        for (n=0; n<nverts; n++ ) {
                Mc_point_list[n] = src;

                src += normcount[n]+1;
        } 
}

int model_collide_parse_bsp_defpoints(ubyte * p)
{
        int n;
        int nverts = w(p+8);    
        int offset = w(p+16);   

        ubyte * normcount = p+20;
        vec3d *src = vp(p+offset);

        model_collide_allocate_point_list(nverts);

        Assert( Mc_point_list != NULL );

        for (n=0; n<nverts; n++ ) {
                Mc_point_list[n] = src;

                src += normcount[n]+1;
        } 

        return nverts;
}

// Flat Poly
// +0      int         id
// +4      int         size 
// +8      vec3d      normal
// +20     vec3d      center
// +32     float       radius
// +36     int         nverts
// +40     byte        red
// +41     byte        green
// +42     byte        blue
// +43     byte        pad
// +44     nverts*int  vertlist
void model_collide_flatpoly(ubyte * p)
{
        int i;
        int nv;
        vec3d *points[TMAP_MAX_VERTS];
        short *verts;

        nv = w(p+36);

        if ( nv <= 0 )
                return;

        if ( nv > TMAP_MAX_VERTS ) {
                Int3();
                return;
        }

        verts = (short *)(p+44);

        for (i=0;i<nv;i++)      {
                points[i] = Mc_point_list[verts[i*2]];
        }

        if ( Mc->flags & MC_CHECK_SPHERELINE )  {
                mc_check_sphereline_face(nv, points, vp(p+20), fl(p+32), vp(p+8), NULL, -1, p, NULL);
        } else {
                mc_check_face(nv, points, vp(p+20), fl(p+32), vp(p+8), NULL, -1, p, NULL);
        }
}


// Textured Poly
// +0      int         id
// +4      int         size 
// +8      vec3d      normal
// +20     vec3d      normal_point
// +32     int         tmp = 0
// +36     int         nverts
// +40     int         tmap_num
// +44     nverts*(model_tmap_vert) vertlist (n,u,v)
void model_collide_tmappoly(ubyte * p)
{
        int i;
        int nv;
        uv_pair uvlist[TMAP_MAX_VERTS];
        vec3d *points[TMAP_MAX_VERTS];
        model_tmap_vert *verts;

        nv = w(p+36);

        if ( nv <= 0 )
                return;

        if ( nv > TMAP_MAX_VERTS ) {
                Int3();
                return;
        }

        int tmap_num = w(p+40);
        Assert(tmap_num >= 0 && tmap_num < MAX_MODEL_TEXTURES); // Goober5000

        if ( (!(Mc->flags & MC_CHECK_INVISIBLE_FACES)) && (Mc_pm->maps[tmap_num].textures[TM_BASE_TYPE].GetTexture() < 0) )     {
                // Don't check invisible polygons.
                //SUSHI: Unless $collide_invisible is set.
                if (!(Mc_pm->submodel[Mc_submodel].collide_invisible))
                        return;
        }

        verts = (model_tmap_vert *)(p+44);

        for (i=0;i<nv;i++)      {
                points[i] = Mc_point_list[verts[i].vertnum];
                uvlist[i].u = verts[i].u;
                uvlist[i].v = verts[i].v;
        }

        if ( Mc->flags & MC_CHECK_SPHERELINE )  {
                mc_check_sphereline_face(nv, points, vp(p+20), fl(p+32), vp(p+8), uvlist, tmap_num, p, NULL);
        } else {
                mc_check_face(nv, points, vp(p+20), fl(p+32), vp(p+8), uvlist, tmap_num, p, NULL);
        }
}


// Sortnorms
// +0      int         id
// +4      int         size 
// +8      vec3d      normal
// +20     vec3d      center
// +32     float       radius
// 36     int     front offset
// 40     int     back offset
// 44     int     prelist offset
// 48     int     postlist offset
// 52     int     online offset

int model_collide_sub( void *model_ptr );

void model_collide_sortnorm(ubyte * p)
{
        int frontlist = w(p+36);
        int backlist = w(p+40);
        int prelist = w(p+44);
        int postlist = w(p+48);
        int onlist = w(p+52);
        vec3d hitpos;

        if ( Mc_pm->version >= 2000 )   {
                if ( mc_ray_boundingbox( vp(p+56), vp(p+68), &Mc_p0, &Mc_direction, &hitpos) )  {
                        if ( !(Mc->flags & MC_CHECK_RAY) && (vm_vec_dist(&hitpos, &Mc_p0) > Mc_mag) ) {
                                return;
                        }
                } else {
                        return;
                }
        }

        if (prelist) model_collide_sub(p+prelist);
        if (backlist) model_collide_sub(p+backlist);
        if (onlist) model_collide_sub(p+onlist);
        if (frontlist) model_collide_sub(p+frontlist);
        if (postlist) model_collide_sub(p+postlist);
}

//calls the object interpreter to render an object.  The object renderer
//is really a seperate pipeline. returns true if drew
int model_collide_sub(void *model_ptr )
{
        ubyte *p = (ubyte *)model_ptr;
        int chunk_type, chunk_size;
        vec3d hitpos;

        chunk_type = w(p);
        chunk_size = w(p+4);

        while (chunk_type != OP_EOF)    {

//              mprintf(( "Processing chunk type %d, len=%d\n", chunk_type, chunk_size ));

                switch (chunk_type) {
                case OP_DEFPOINTS:      model_collide_defpoints(p); break;
                case OP_FLATPOLY:               model_collide_flatpoly(p); break;
                case OP_TMAPPOLY:               model_collide_tmappoly(p); break;
                case OP_SORTNORM:               model_collide_sortnorm(p); break;
                case OP_BOUNDBOX:       
                        if ( mc_ray_boundingbox( vp(p+8), vp(p+20), &Mc_p0, &Mc_direction, &hitpos ) )  {
                                if ( !(Mc->flags & MC_CHECK_RAY) && (vm_vec_dist(&hitpos, &Mc_p0) > Mc_mag) ) {
                                        // The ray isn't long enough to intersect the bounding box
                                        return 1;
                                }
                        } else {
                                return 1;
                        }
                        break;
                default:
                        mprintf(( "Bad chunk type %d, len=%d in model_collide_sub\n", chunk_type, chunk_size ));
                        Int3();         // Bad chunk type!
                        return 0;
                }
                p += chunk_size;
                chunk_type = w(p);
                chunk_size = w(p+4);
        }
        return 1;
}

void model_collide_bsp_poly(bsp_collision_tree *tree, int leaf_index)
{
        int i;
        int tested_leaf = leaf_index;
        uv_pair uvlist[TMAP_MAX_VERTS];
        vec3d *points[TMAP_MAX_VERTS];

        while ( tested_leaf >= 0 ) {
                bsp_collision_leaf *leaf = &tree->leaf_list[tested_leaf];

                bool flat_poly = false;
                int vert_start = leaf->vert_start;
                int nv = leaf->num_verts;

                if ( leaf->tmap_num < MAX_MODEL_TEXTURES ) {
                        if ( (!(Mc->flags & MC_CHECK_INVISIBLE_FACES)) && (Mc_pm->maps[leaf->tmap_num].textures[TM_BASE_TYPE].GetTexture() < 0) )       {
                                // Don't check invisible polygons.
                                //SUSHI: Unless $collide_invisible is set.
                                if (!(Mc_pm->submodel[Mc_submodel].collide_invisible))
                                        return;
                        }
                } else {
                        flat_poly = true;
                }

                int vert_num;
                for ( i = 0; i < nv; ++i ) {
                        vert_num = tree->vert_list[vert_start+i].vertnum;
                        points[i] = &tree->point_list[vert_num];

                        uvlist[i].u = tree->vert_list[vert_start+i].u;
                        uvlist[i].v = tree->vert_list[vert_start+i].v;
                }

                if ( flat_poly ) {
                        if ( Mc->flags & MC_CHECK_SPHERELINE ) {
                                mc_check_sphereline_face(nv, points, &leaf->plane_pnt, leaf->face_rad, &leaf->plane_norm, NULL, -1, NULL, leaf);
                        } else {
                                mc_check_face(nv, points, &leaf->plane_pnt, leaf->face_rad, &leaf->plane_norm, NULL, -1, NULL, leaf);
                        }
                } else {
                        if ( Mc->flags & MC_CHECK_SPHERELINE ) {
                                mc_check_sphereline_face(nv, points, &leaf->plane_pnt, leaf->face_rad, &leaf->plane_norm, uvlist, leaf->tmap_num, NULL, leaf);
                        } else {
                                mc_check_face(nv, points, &leaf->plane_pnt, leaf->face_rad, &leaf->plane_norm, uvlist, leaf->tmap_num, NULL, leaf);
                        }
                }

                tested_leaf = leaf->next;
        }
}

void model_collide_bsp(bsp_collision_tree *tree, int node_index)
{
        if ( tree->node_list == NULL || tree->n_verts <= 0) {
                return;
        }

        bsp_collision_node *node = &tree->node_list[node_index];
        vec3d hitpos;

        // check the bounding box of this node. if it passes, check left and right children
        if ( mc_ray_boundingbox( &node->min, &node->max, &Mc_p0, &Mc_direction, &hitpos ) ) {
                if ( !(Mc->flags & MC_CHECK_RAY) && (vm_vec_dist(&hitpos, &Mc_p0) > Mc_mag) ) {
                        // The ray isn't long enough to intersect the bounding box
                        return;
                }

                if ( node->leaf >= 0 ) {
                        model_collide_bsp_poly(tree, node->leaf);
                } else {
                        if ( node->back >= 0 ) model_collide_bsp(tree, node->back);
                        if ( node->front >= 0 ) model_collide_bsp(tree, node->front);
                }
        }
}

void model_collide_parse_bsp_tmappoly(bsp_collision_leaf *leaf, SCP_vector<model_tmap_vert> *vert_buffer, void *model_ptr)
{
        ubyte *p = (ubyte *)model_ptr;

        int i;
        int nv;
        model_tmap_vert *verts;

        nv = w(p+36);

        if ( nv < 0 ) return;

        if ( nv > TMAP_MAX_VERTS ) {
                Int3();
                return;
        }

        int tmap_num = w(p+40);

        Assert(tmap_num >= 0 && tmap_num < MAX_MODEL_TEXTURES);

        verts = (model_tmap_vert *)(p+44);

        leaf->tmap_num = (ubyte)tmap_num;
        leaf->num_verts = (ubyte)nv;
        leaf->vert_start = vert_buffer->size();

        vec3d *plane_pnt = vp(p+20);
        float face_rad = fl(p+32);
        vec3d *plane_norm = vp(p+8);

        leaf->plane_pnt = *plane_pnt;
        leaf->face_rad = face_rad;
        leaf->plane_norm = *plane_norm;

        for ( i = 0; i < nv; ++i ) {
                vert_buffer->push_back(verts[i]);
        }
}

void model_collide_parse_bsp_flatpoly(bsp_collision_leaf *leaf, SCP_vector<model_tmap_vert> *vert_buffer, void *model_ptr)
{
        ubyte *p = (ubyte *)model_ptr;

        int i;
        int nv;
        short *verts;

        nv = w(p+36);

        if ( nv < 0 ) return;

        if ( nv > TMAP_MAX_VERTS ) {
                Int3();
                return;
        }

        verts = (short *)(p+44);

        leaf->tmap_num = 255;
        leaf->num_verts = (ubyte)nv;
        leaf->vert_start = vert_buffer->size();

        vec3d *plane_pnt = vp(p+20);
        float face_rad = fl(p+32);
        vec3d *plane_norm = vp(p+8);

        leaf->plane_pnt = *plane_pnt;
        leaf->face_rad = face_rad;
        leaf->plane_norm = *plane_norm;

        model_tmap_vert vert;

        for ( i = 0; i < nv; ++i ) {
                vert.vertnum = verts[i*2];
                vert.normnum = 0;
                vert.u = 0.0f;
                vert.v = 0.0f;

                vert_buffer->push_back(vert);
        }
}

void model_collide_parse_bsp(bsp_collision_tree *tree, void *model_ptr, int version)
{
        ubyte *p = (ubyte *)model_ptr;
        ubyte *next_p;

        int chunk_type = w(p);
        int chunk_size = w(p+4);

        int next_chunk_type;
        int next_chunk_size;

        Assert(chunk_type == OP_DEFPOINTS);

        int n_verts = model_collide_parse_bsp_defpoints(p);

        if ( n_verts <= 0) {
                tree->point_list = NULL;
                tree->n_verts = 0;

                tree->n_nodes = 0;
                tree->node_list = NULL;

                tree->n_leaves = 0;
                tree->leaf_list = NULL;

                // finally copy the vert list.
                tree->vert_list = NULL;

                return;
        }

        p += chunk_size;

        bsp_collision_node new_node;
        bsp_collision_leaf new_leaf;

        SCP_vector<bsp_collision_node> node_buffer;
        SCP_vector<bsp_collision_leaf> leaf_buffer;
        SCP_vector<model_tmap_vert> vert_buffer;

        SCP_map<size_t, ubyte*> bsp_datap;

        node_buffer.push_back(new_node);

        size_t i = 0;
        vec3d *min;
        vec3d *max;

        bsp_datap[i] = p;

        while ( i < node_buffer.size() ) {
                p = bsp_datap[i];

                chunk_type = w(p);
                chunk_size = w(p+4);

                switch ( chunk_type ) {
                case OP_SORTNORM:
                        if ( version >= 2000 ) {
                                min = vp(p+56);
                                max = vp(p+68);

                                node_buffer[i].min = *min;
                                node_buffer[i].max = *max;
                        }

                        node_buffer[i].leaf = -1;
                        node_buffer[i].front = -1;
                        node_buffer[i].back = -1;

                        if ( w(p+36) ) {
                                next_chunk_type = w(p+w(p+36));

                                if ( next_chunk_type != OP_EOF ) {
                                        node_buffer.push_back(new_node);
                                        node_buffer[i].front = (node_buffer.size() - 1);
                                        bsp_datap[node_buffer[i].front] = p+w(p+36);
                                }
                        }

                        if ( w(p+40) ) {
                                next_chunk_type = w(p+w(p+40));
                                
                                if ( next_chunk_type != OP_EOF ) {
                                        node_buffer.push_back(new_node);
                                        node_buffer[i].back = (node_buffer.size() - 1);
                                        bsp_datap[node_buffer[i].back] = p+w(p+40);
                                }
                        }

                        next_p = p + chunk_size;
                        next_chunk_type = w(next_p);

                        Assert( next_chunk_type == OP_EOF );

                        ++i;
                        break;
                case OP_BOUNDBOX:
                        min = vp(p+8);
                        max = vp(p+20);

                        node_buffer[i].min = *min;
                        node_buffer[i].max = *max;

                        node_buffer[i].front = -1;
                        node_buffer[i].back = -1;
                        node_buffer[i].leaf = -1;

                        next_p = p + chunk_size;
                        next_chunk_type = w(next_p);
                        next_chunk_size = w(next_p+4);

                        if ( next_chunk_type != OP_EOF && (next_chunk_type == OP_TMAPPOLY || next_chunk_type == OP_FLATPOLY ) ) {
                                new_leaf.next = -1;

                                node_buffer[i].leaf = leaf_buffer.size();       // get index of where our poly list starts in the leaf buffer

                                while ( next_chunk_type != OP_EOF ) {
                                        if ( next_chunk_type == OP_TMAPPOLY ) {

                                                model_collide_parse_bsp_tmappoly(&new_leaf, &vert_buffer, next_p);

                                                leaf_buffer.push_back(new_leaf);

                                                leaf_buffer.back().next = leaf_buffer.size();
                                        } else if ( next_chunk_type == OP_FLATPOLY ) {
                                                model_collide_parse_bsp_flatpoly(&new_leaf, &vert_buffer, next_p);

                                                leaf_buffer.push_back(new_leaf);

                                                leaf_buffer.back().next = leaf_buffer.size();
                                        } else {
                                                Int3();
                                        }

                                        next_p += next_chunk_size;
                                        next_chunk_type = w(next_p);
                                        next_chunk_size = w(next_p+4);
                                }

                                leaf_buffer.back().next = -1;
                        }

                        Assert(next_chunk_type == OP_EOF);

                        ++i;
                        break;
                }
        }

        // copy point list
        Assert(n_verts != -1);

        tree->point_list = (vec3d*)vm_malloc(sizeof(vec3d) * n_verts);

        for ( i = 0; i < (size_t)n_verts; ++i ) {
                tree->point_list[i] = *Mc_point_list[i];
        }

        tree->n_verts = n_verts;

        // copy node info. this might be a good time to organize the nodes into a cache efficient tree layout.
        tree->n_nodes = node_buffer.size();
        tree->node_list = (bsp_collision_node*)vm_malloc(sizeof(bsp_collision_node) * node_buffer.size());
        memcpy(tree->node_list, &node_buffer[0], sizeof(bsp_collision_node) * node_buffer.size());
        node_buffer.clear();

        // copy leaves.
        tree->n_leaves = leaf_buffer.size();
        tree->leaf_list = (bsp_collision_leaf*)vm_malloc(sizeof(bsp_collision_leaf) * leaf_buffer.size());
        memcpy(tree->leaf_list, &leaf_buffer[0], sizeof(bsp_collision_leaf) * leaf_buffer.size());
        leaf_buffer.clear();

        // finally copy the vert list.
        tree->vert_list = (model_tmap_vert*)vm_malloc(sizeof(model_tmap_vert) * vert_buffer.size());
        memcpy(tree->vert_list, &vert_buffer[0], sizeof(model_tmap_vert) * vert_buffer.size());
        vert_buffer.clear();
}

bool mc_shield_check_common(shield_tri  *tri)
{
        vec3d * points[3];
        vec3d hitpoint;
         
        float dist;
        float sphere_check_closest_shield_dist = FLT_MAX;

        // Check to see if Mc_pmly is facing away from ray.  If so, don't bother
        // checking it.
        if (vm_vec_dot(&Mc_direction,&tri->norm) > 0.0f)        {
                return false;
        }
        // get the vertices in the form the next function wants them
        for (int j = 0; j < 3; j++ )
                points[j] = &Mc_pm->shield.verts[tri->verts[j]].pos;

        if (!(Mc->flags & MC_CHECK_SPHERELINE) ) {      // Don't do this test for sphere colliding against shields
                // Find the intersection of this ray with the plane that the Mc_pmly
                // lies in
                dist = fvi_ray_plane(NULL, points[0],&tri->norm,&Mc_p0,&Mc_direction,0.0f);

                if ( dist < 0.0f ) return false; // If the ray is behind the plane there is no collision
                if ( !(Mc->flags & MC_CHECK_RAY) && (dist > 1.0f) ) return false; // The ray isn't long enough to intersect the plane

                // Find the hit Mc_pmint
                vm_vec_scale_add( &hitpoint, &Mc_p0, &Mc_direction, dist );
        
                // Check to see if the Mc_pmint of intersection is on the plane.  If so, this
                // also finds the uv's where the ray hit.
                if ( fvi_point_face(&hitpoint, 3, points, &tri->norm, NULL,NULL,NULL ) )        {
                        Mc->hit_dist = dist;
                        Mc->shield_hit_tri = tri - Mc_pm->shield.tris;
                        Mc->hit_point = hitpoint;
                        Mc->hit_normal = tri->norm;
                        Mc->hit_submodel = -1;
                        Mc->num_hits++;
                        return true;            // We hit, so we're done
                }
        } else {                // Sphere check against shield
                                        // This needs to look at *all* shield tris and not just return after the first hit

                // HACK HACK!! The 10000.0 is the face radius, I didn't know this,
                // so I'm assume 10000 would be as big as ever.
                mc_check_sphereline_face(3, points, points[0], 10000.0f, &tri->norm, NULL, 0, NULL, NULL);
                if (Mc->num_hits && Mc->hit_dist < sphere_check_closest_shield_dist) {

                        // same behavior whether face or edge
                        // normal, edge_hit, hit_point all updated thru sphereline_face
                        sphere_check_closest_shield_dist = Mc->hit_dist;
                        Mc->shield_hit_tri = tri - Mc_pm->shield.tris;
                        Mc->hit_submodel = -1;
                        Mc->num_hits++;
                        return true;            // We hit, so we're done
                }
        } // Mc->flags & MC_CHECK_SPHERELINE else

        return false;
}

bool mc_check_sldc(int offset)
{
        if (offset > Mc_pm->sldc_size-5) //no way is this big enough
                return false;
        char *type_p = (char *)(Mc_pm->shield_collision_tree+offset);
        
        // not used
        //int *size_p = (int *)(Mc_pm->shield_collision_tree+offset+1);
        // split and polygons
        vec3d *minbox_p = (vec3d*)(Mc_pm->shield_collision_tree+offset+5);
        vec3d *maxbox_p = (vec3d*)(Mc_pm->shield_collision_tree+offset+17);

        // split
        unsigned int *front_offset_p = (unsigned int*)(Mc_pm->shield_collision_tree+offset+29);
        unsigned int *back_offset_p = (unsigned int*)(Mc_pm->shield_collision_tree+offset+33);

        // polygons
        unsigned int *num_polygons_p = (unsigned int*)(Mc_pm->shield_collision_tree+offset+29);

        unsigned int *shld_polys = (unsigned int*)(Mc_pm->shield_collision_tree+offset+33);



        // see if it fits inside our bbox
        if (!mc_ray_boundingbox( minbox_p, maxbox_p, &Mc_p0, &Mc_direction, NULL ))     {
                return false;
        }

        if (*type_p == 0) // SPLIT
        {
                        return mc_check_sldc(offset+*front_offset_p) || mc_check_sldc(offset+*back_offset_p);
        }
        else
        {
                // poly list
                shield_tri      * tri;
                for (unsigned int i = 0; i < *num_polygons_p; i++)
                {
                        tri = &Mc_pm->shield.tris[shld_polys[i]];
                                                
                        mc_shield_check_common(tri);

                } // for (unsigned int i = 0; i < leaf->num_polygons; i++)
        }

        // shouldn't be reached
        return false;
}

// checks a vector collision against a ships shield (if it has shield points defined).
void mc_check_shield()
{
        int i;


        if ( Mc_pm->shield.ntris < 1 )
                return;
        if (Mc_pm->shield_collision_tree)
        {
                mc_check_sldc(0); // see if we hit the SLDC
        }
        else
        {
                int o;
                for (o=0; o<8; o++ )    {
                        model_octant * poct1 = &Mc_pm->octants[o];

                        if (!mc_ray_boundingbox( &poct1->min, &poct1->max, &Mc_p0, &Mc_direction, NULL ))       {
                                continue;
                        }
                        
                        for (i = 0; i < poct1->nshield_tris; i++) {
                                shield_tri      * tri = poct1->shield_tris[i];
                                mc_shield_check_common(tri);
                        }
                }
        }//model has shield_collsion_tree
}


// This function recursively checks a submodel and its children
// for a collision with a vector.
void mc_check_subobj( int mn )
{
        vec3d tempv;
        vec3d hitpt;            // used in bounding box check
        bsp_info * sm;
        int i;

        Assert( mn >= 0 );
        Assert( mn < Mc_pm->n_models );
        if ( (mn < 0) || (mn>=Mc_pm->n_models) ) return;
        
        sm = &Mc_pm->submodel[mn];
        if (sm->no_collisions) return; // don't do collisions
        if (sm->nocollide_this_only) goto NoHit; // Don't collide for this model, but keep checking others

        // Rotate the world check points into the current subobject's 
        // frame of reference.
        // After this block, Mc_p0, Mc_p1, Mc_direction, and Mc_mag are correct
        // and relative to this subobjects' frame of reference.
        vm_vec_sub(&tempv, Mc->p0, &Mc_base);
        vm_vec_rotate(&Mc_p0, &tempv, &Mc_orient);

        vm_vec_sub(&tempv, Mc->p1, &Mc_base);
        vm_vec_rotate(&Mc_p1, &tempv, &Mc_orient);
        vm_vec_sub(&Mc_direction, &Mc_p1, &Mc_p0);

        // bail early if no ray exists
        if ( IS_VEC_NULL(&Mc_direction) ) {
                return;
        }

        if (Mc_pm->detail[0] == mn)     {
                // Quickly bail if we aren't inside the full model bbox
                if (!mc_ray_boundingbox( &Mc_pm->mins, &Mc_pm->maxs, &Mc_p0, &Mc_direction, NULL))      {
                        return;
                }

                // If we are checking the root submodel, then we might want to check    
                // the shield at this point
                if ((Mc->flags & MC_CHECK_SHIELD) && (Mc_pm->shield.ntris > 0 )) {
                        mc_check_shield();
                        return;
                }
        }

        if (!(Mc->flags & MC_CHECK_MODEL)) {
                return;
        }
        
        Mc_submodel = mn;

        // Check if the ray intersects this subobject's bounding box
        if ( mc_ray_boundingbox(&sm->min, &sm->max, &Mc_p0, &Mc_direction, &hitpt) ) {
                if (Mc->flags & MC_ONLY_BOUND_BOX) {
                        float dist = vm_vec_dist( &Mc_p0, &hitpt );

                        // If the ray is behind the plane there is no collision
                        if (dist < 0.0f) {
                                goto NoHit;
                        }

                        // The ray isn't long enough to intersect the plane
                        if ( !(Mc->flags & MC_CHECK_RAY) && (dist > Mc_mag) ) {
                                goto NoHit;
                        }

                        // If the ray hits, but a closer intersection has already been found, return
                        if ( Mc->num_hits && (dist >= Mc->hit_dist) ) {
                                goto NoHit;
                        }

                        Mc->hit_dist = dist;
                        Mc->hit_point = hitpt;
                        Mc->hit_submodel = Mc_submodel;
                        Mc->hit_bitmap = -1;
                        Mc->num_hits++;
                } else {
                        // The ray intersects this bounding box, so we have to check all the
                        // polygons in this submodel.
                        if ( Cmdline_old_collision_sys ) {
                                model_collide_sub(sm->bsp_data);
                        } else {
                                if (Mc->lod > 0 && sm->num_details > 0) {
                                        bsp_info *lod_sm = sm;

                                        for (i = Mc->lod - 1; i >= 0; i--) {
                                                if (sm->details[i] != -1) {
                                                        lod_sm = &Mc_pm->submodel[sm->details[i]];

                                                        //mprintf(("Checking %s collision for %s using %s instead\n", Mc_pm->filename, sm->name, lod_sm->name));
                                                        break;
                                                }
                                        }

                                        model_collide_bsp(model_get_bsp_collision_tree(lod_sm->collision_tree_index), 0);
                                } else {
                                        model_collide_bsp(model_get_bsp_collision_tree(sm->collision_tree_index), 0);
                                }
                        }
                }
        }

NoHit:

        // If we're only checking one submodel, return
        if (Mc->flags & MC_SUBMODEL)    {
                return;
        }

        
        // If this subobject doesn't have any children, we're done checking it.
        if ( sm->num_children < 1 ) return;
        
        // Save instance (Mc_orient, Mc_base, Mc_point_base)
        matrix saved_orient = Mc_orient;
        vec3d saved_base = Mc_base;
        
        // Check all of this subobject's children
        i = sm->first_child;
        while ( i >= 0 )        {
                angles angs;
                bool blown_off;
                bool collision_checked;
                bsp_info * csm = &Mc_pm->submodel[i];
                
                if ( Mc_pmi ) {
                        angs = Mc_pmi->submodel[i].angs;
                        blown_off = Mc_pmi->submodel[i].blown_off;
                        collision_checked = Mc_pmi->submodel[i].collision_checked;
                } else {
                        angs = csm->angs;
                        blown_off = csm->blown_off ? true : false;
                        collision_checked = false;
                }

                // Don't check it or its children if it is destroyed
                // or if it's set to no collision
                if ( !blown_off && !collision_checked && !csm->no_collisions )  {
                        if ( Mc_pmi ) {
                                Mc_orient = Mc_pmi->submodel[i].mc_orient;
                                Mc_base = Mc_pmi->submodel[i].mc_base;
                                vm_vec_add2(&Mc_base, Mc->pos);
                        } else {
                                //instance for this subobject
                                matrix tm = IDENTITY_MATRIX;

                                vm_vec_unrotate(&Mc_base, &csm->offset, &saved_orient );
                                vm_vec_add2(&Mc_base, &saved_base );

                                if( vm_matrix_same(&tm, &csm->orientation)) {
                                        // if submodel orientation matrix is identity matrix then don't bother with matrix ops
                                        vm_angles_2_matrix(&tm, &angs);
                                } else {
                                        matrix rotation_matrix = csm->orientation;
                                        vm_rotate_matrix_by_angles(&rotation_matrix, &angs);

                                        matrix inv_orientation;
                                        vm_copy_transpose(&inv_orientation, &csm->orientation);

                                        vm_matrix_x_matrix(&tm, &rotation_matrix, &inv_orientation);
                                }

                                vm_matrix_x_matrix(&Mc_orient, &saved_orient, &tm);
                        }

                        mc_check_subobj( i );
                }

                i = csm->next_sibling;
        }

}

MONITOR(NumFVI)

// See model.h for usage.   I don't want to put the
// usage here because you need to see the #defines and structures
// this uses while reading the help.   
int model_collide(mc_info *mc_info_obj)
{
        Mc = mc_info_obj;

        MONITOR_INC(NumFVI,1);

        Mc->num_hits = 0;                               // How many collisions were found
        Mc->shield_hit_tri = -1;        // Assume we won't hit any shield polygons
        Mc->hit_bitmap = -1;
        Mc->edge_hit = 0;

        if ( (Mc->flags & MC_CHECK_SHIELD) && (Mc->flags & MC_CHECK_MODEL) )    {
                Error( LOCATION, "Checking both shield and model!\n" );
                return 0;
        }

        //Fill in some global variables that all the model collide routines need internally.
        Mc_pm = model_get(Mc->model_num);
        Mc_orient = *Mc->orient;
        Mc_base = *Mc->pos;
        Mc_mag = vm_vec_dist( Mc->p0, Mc->p1 );
        Mc_edge_time = FLT_MAX;

        if ( Mc->model_instance_num >= 0 ) {
                Mc_pmi = model_get_instance(Mc->model_instance_num);
        } else {
                Mc_pmi = NULL;
        }

        // DA 11/19/98 - disable this check for rotating submodels
        // Don't do check if for very small movement
//      if (Mc_mag < 0.01f) {
//              return 0;
//      }

        float model_radius;             // How big is the model we're checking against
        int first_submodel;             // Which submodel gets returned as hit if MC_ONLY_SPHERE specified

        if ( (Mc->flags & MC_SUBMODEL) || (Mc->flags & MC_SUBMODEL_INSTANCE) )  {
                first_submodel = Mc->submodel_num;
                model_radius = Mc_pm->submodel[first_submodel].rad;
        } else {
                first_submodel = Mc_pm->detail[0];
                model_radius = Mc_pm->rad;
        }

        if ( Mc->flags & MC_CHECK_SPHERELINE ) {
                if ( Mc->radius <= 0.0f ) {
                        Warning(LOCATION, "Attempting to collide with a sphere, but the sphere's radius is <= 0.0f!\n\n(model file is %s; submodel is %d, mc_flags are %d)", Mc_pm->filename, first_submodel, Mc->flags);
                        return 0;
                }

                // Do a quick check on the Bounding Sphere
                if (fvi_segment_sphere(&Mc->hit_point_world, Mc->p0, Mc->p1, Mc->pos, model_radius+Mc->radius) )        {
                        if ( Mc->flags & MC_ONLY_SPHERE )       {
                                Mc->hit_point = Mc->hit_point_world;
                                Mc->hit_submodel = first_submodel;
                                Mc->num_hits++;
                                return (Mc->num_hits > 0);
                        }
                        // continue checking polygons.
                } else {
                        return 0;
                }
        } else {
                int r;

                // Do a quick check on the Bounding Sphere
                if ( Mc->flags & MC_CHECK_RAY ) {
                        r = fvi_ray_sphere(&Mc->hit_point_world, Mc->p0, Mc->p1, Mc->pos, model_radius);
                } else {
                        r = fvi_segment_sphere(&Mc->hit_point_world, Mc->p0, Mc->p1, Mc->pos, model_radius);
                }
                if (r) {
                        if ( Mc->flags & MC_ONLY_SPHERE ) {
                                Mc->hit_point = Mc->hit_point_world;
                                Mc->hit_submodel = first_submodel;
                                Mc->num_hits++;
                                return (Mc->num_hits > 0);
                        }
                        // continue checking polygons.
                } else {
                        return 0;
                }

        }

        if ( Mc->flags & MC_SUBMODEL )  {
                // Check only one subobject
                mc_check_subobj( Mc->submodel_num );
                // Check submodel and any children
        } else if (Mc->flags & MC_SUBMODEL_INSTANCE) {
                mc_check_subobj(Mc->submodel_num);
        } else {
                // Check all the the highest detail model polygons and subobjects for intersections

                // Don't check it or its children if it is destroyed
                if (!Mc_pm->submodel[Mc_pm->detail[0]].blown_off)       {       
                        mc_check_subobj( Mc_pm->detail[0] );
                }
        }


        //If we found a hit, then rotate it into world coordinates      
        if ( Mc->num_hits )     {
                if ( Mc->flags & MC_SUBMODEL )  {
                        // If we're just checking one submodel, don't use normal instancing to find world points
                        vm_vec_unrotate(&Mc->hit_point_world, &Mc->hit_point, Mc->orient);
                        vm_vec_add2(&Mc->hit_point_world, Mc->pos);
                } else {
                        if ( Mc_pmi ) {
                                model_instance_find_world_point(&Mc->hit_point_world, &Mc->hit_point, Mc->model_instance_num, Mc->hit_submodel, Mc->orient, Mc->pos);
                        } else {
                                model_find_world_point(&Mc->hit_point_world, &Mc->hit_point, Mc->model_num, Mc->hit_submodel, Mc->orient, Mc->pos);
                        }
                }
        }


        return Mc->num_hits;

}

void model_collide_preprocess_subobj(vec3d *pos, matrix *orient, polymodel *pm,  polymodel_instance *pmi, int subobj_num)
{
        submodel_instance *smi = &pmi->submodel[subobj_num];

        smi->mc_base = *pos;
        smi->mc_orient = *orient;

        int i = pm->submodel[subobj_num].first_child;

        while ( i >= 0 ) {
                angles angs = pmi->submodel[i].angs;
                bsp_info * csm = &pm->submodel[i];

                matrix tm = IDENTITY_MATRIX;

                vm_vec_unrotate(pos, &csm->offset, &smi->mc_orient );
                vm_vec_add2(pos, &smi->mc_base);

                if( vm_matrix_same(&tm, &csm->orientation)) {
                        // if submodel orientation matrix is identity matrix then don't bother with matrix ops
                        vm_angles_2_matrix(&tm, &angs);
                } else {
                        matrix rotation_matrix = csm->orientation;
                        vm_rotate_matrix_by_angles(&rotation_matrix, &angs);

                        matrix inv_orientation;
                        vm_copy_transpose(&inv_orientation, &csm->orientation);

                        vm_matrix_x_matrix(&tm, &rotation_matrix, &inv_orientation);
                }

                vm_matrix_x_matrix(orient, &smi->mc_orient, &tm);

                model_collide_preprocess_subobj(pos, orient, pm, pmi, i);

                i = csm->next_sibling;
        }
}

void model_collide_preprocess(matrix *orient, int model_instance_num, int detail_num)
{
        polymodel_instance      *pmi;
        polymodel *pm;

        pmi = model_get_instance(model_instance_num);
        pm = model_get(pmi->model_num);

        matrix current_orient;
        vec3d current_pos;

        current_orient = *orient;

        vm_vec_zero(&current_pos);

        model_collide_preprocess_subobj(&current_pos, &current_orient, pm, pmi, pm->detail[detail_num]);
}