ivp_ray_solver.cxx

hl2 source code. Do not use it illegal.

// Copyright (C) Ipion Software GmbH 1999-2000. All rights reserved.


#include <ivp_physics.hxx>

#include <ivu_min_hash.hxx>

#include <ivp_compact_ledge.hxx>
#include <ivp_compact_ledge_solver.hxx>

#include <ivp_clustering_longrange.hxx>
#include <ivp_compact_surface.hxx>

#ifndef WIN32
#	pragma implementation "ivp_ray_solver.hxx"
#endif

#include <ivp_ray_solver.hxx>

    // ATT: must be the same than in class definition!

#define IVP_LEFT 1
#define IVP_RIGHT 2
#define IVP_ABOVE 4
#define IVP_BELOW 8
#define IVP_FRONT 16
#define IVP_BEHIND 32

IVP_Ray_Solver::IVP_Ray_Solver(const IVP_Ray_Solver_Template *templ) 
{
    // ray dir must be normized.
    IVP_ASSERT( (templ->ray_normized_direction.real_length() > (1.0f - 1e-4f) ) &&
	      (templ->ray_normized_direction.real_length() < (1.0f + 1e-4f) ) );
    
    this->ray_direction.set(&templ->ray_normized_direction);
    this->ray_start_point.set(&templ->ray_start_point);
    
    this->ray_length = templ->ray_length;
    this->ray_flags  = templ->ray_flags;
    
    // calc end point of ray
    this->ray_center_point.set(&this->ray_start_point);
    this->ray_center_point.add_multiple( &this->ray_direction, this->ray_length * 0.5f);
    
    this->ray_end_point.add_multiple(&ray_start_point, &ray_direction, ray_length);
}


void IVP_Ray_Solver_Min_Hash::add_hit_object(IVP_Real_Object *object, const IVP_Compact_Ledge *compact_ledge, const IVP_Compact_Triangle *compact_triangle, IVP_DOUBLE hit_dist,
				    IVP_U_Point *hit_sur_vec_os)
{
    // Insert object into class member 'output_min_hash'
    // when ray flags allow for it.
    
    if(this->output_min_hash.counter >= IVP_MAX_NUM_RAY_HITS){
	IVP_IF(1){
	    printf("IVP_Ray_Solver::add_hit_object - max ray hits exceeded -> hit list truncated.\n");
	}
	// todo: if hit_dist < current hash minimum: replace any min hash entry with this hit
	// ...
	return;
    }

    IVP_Ray_Hit *ray_hit = &this->hit_info[this->output_min_hash.counter];
    ray_hit->hit_real_object = object;
    ray_hit->hit_compact_ledge = compact_ledge;
    ray_hit->hit_compact_triangle = compact_triangle;
    IVP_IF(0){
	printf("object inserted: %s, dist %g\n", object->get_name(), hit_dist);
    }
    ray_hit->hit_surface_direction_os.set(hit_sur_vec_os);
    ray_hit->hit_distance = hit_dist;

    this->output_min_hash.add((void *)ray_hit, hit_dist);
}


IVP_BOOL IVP_Ray_Solver::check_ray_against_sphere(const IVP_U_Float_Point *sphere_center_ws,	  IVP_FLOAT sphere_radius){
    // returns IVP_FALSE if sphere is not hit by ray
    IVP_U_Float_Point delta_vec;
    IVP_DOUBLE rad_sum = ray_length * 0.5f + sphere_radius;
    delta_vec.subtract(sphere_center_ws, &ray_center_point);

    if (delta_vec.quad_length() >= rad_sum * rad_sum){
	return IVP_FALSE;
    }
    
    IVP_U_Float_Point h;
    h.inline_calc_cross_product(&ray_direction, &delta_vec);
    
    IVP_FLOAT quad_dist = (IVP_FLOAT)h.quad_length();
    
    IVP_FLOAT coll_dist = sphere_radius;
    
    if(quad_dist < coll_dist*coll_dist) return IVP_TRUE;
    
    return IVP_FALSE;
}

IVP_BOOL IVP_Ray_Solver_Group::check_ray_group_against_sphere(const IVP_U_Float_Point *sphere_center_ws,	  IVP_FLOAT sphere_radius){
    // returns IVP_FALSE if sphere is not hit by ray
    IVP_U_Float_Point delta_vec;
    IVP_DOUBLE rad_sum = radius + sphere_radius;
    delta_vec.subtract(sphere_center_ws, &center_ws);

    if (delta_vec.quad_length() >= rad_sum * rad_sum){
	return IVP_FALSE;
    }
    return IVP_TRUE;
}

IVP_BOOL IVP_Ray_Solver_Os::check_ray_against_sphere_os(const IVP_U_Float_Point *sphere_center_os,  IVP_FLOAT sphere_radius){
    // returns IVP_FALSE if sphere is not hit by ray
    IVP_U_Float_Point delta_vec; // quick check for ends of ray
    IVP_DOUBLE qrad_sum = ray_length * 0.5f + sphere_radius;
    IVP_DOUBLE qsphere_rad = sphere_radius * sphere_radius;
    qrad_sum *= qrad_sum;
    delta_vec.subtract(sphere_center_os, &ray_center_point);
    IVP_DOUBLE quad_center_dist = delta_vec.quad_length();
    if ( quad_center_dist >= qrad_sum ){
	return IVP_FALSE;
    }
    if ( quad_center_dist < qsphere_rad ){
	return IVP_TRUE;
    }
    
    IVP_U_Float_Point h;
    h.inline_calc_cross_product(&ray_direction, &delta_vec);
    
    IVP_FLOAT quad_dist = (IVP_FLOAT)h.quad_length();
    
    IVP_FLOAT coll_dist = sphere_radius;
    
    if((coll_dist*coll_dist - quad_dist) >= -0.01f){ //@@CB
	return IVP_TRUE;
    }
    
    return IVP_FALSE;
}


IVP_BOOL IVP_Ray_Solver::check_ray_against_square(IVP_FLOAT pos_dist,
						  IVP_FLOAT pos_axis_len,
						  const IVP_U_Float_Point *min_coords,
						  const IVP_U_Float_Point *max_coords,
						  int coord_0, int coord_1)
{

    // returns IVP_FALSE if square is not hit by ray
    
    // better than 'if' in the loop!? -OG
    short coord_index[2];
    coord_index[0] = coord_0;
    coord_index[1] = coord_1;
    
    // each axis
    int i;
    for(i=1; i>=0; --i){
	// check against one limiting plane
	int coord=coord_index[i];
	IVP_FLOAT comp_val = pos_dist * ray_length * ray_direction.k[coord];
	if( (comp_val < (min_coords->k[coord] - ray_start_point.k[coord]) * pos_axis_len ) ||
	    (comp_val > (max_coords->k[coord] - ray_start_point.k[coord]) * pos_axis_len ) ){
	    // miss
	    return IVP_FALSE;
	}
    }
    
    // ray hits for both coords
    return IVP_TRUE;
}

IVP_BOOL IVP_Ray_Solver::check_ray_against_cube(const IVP_U_Float_Point *luf_point,
						const IVP_U_Float_Point *rlb_point)
{
    // Checks wether the specified cube is hit by the specified ray.
    // Returns IVP_TRUE in case of a hit.
    // Returns IVP_FALSE if cube is not hit by the ray.
    
    // calc clip flags for start point.
    
    // todo: use ray radius, but beware of the corner roundings!
    
    short start_point_flags = 0;
    short end_point_flags   = 0;
    
    if(ray_start_point.k[0]<luf_point->k[0]) start_point_flags = IVP_LEFT;
    else if(ray_start_point.k[0]>rlb_point->k[0]) start_point_flags = IVP_RIGHT;
    
    if(ray_start_point.k[1]<luf_point->k[1]) start_point_flags |= IVP_ABOVE;
    else if(ray_start_point.k[1]>rlb_point->k[1]) start_point_flags |= IVP_BELOW;
    
    if(ray_start_point.k[2]<luf_point->k[2]) start_point_flags |= IVP_FRONT;
    else if(ray_start_point.k[2]>rlb_point->k[2]) start_point_flags |= IVP_BEHIND;
    
    // if startpoint is inside the cube, ray hits.
    if(start_point_flags==0) return IVP_TRUE;
    
    // calc clip flags for end point.
    
    if(ray_end_point.k[0]<luf_point->k[0]) end_point_flags = IVP_LEFT;
    else if(ray_end_point.k[0]>rlb_point->k[0]) end_point_flags = IVP_RIGHT;
    
    if(ray_end_point.k[1]<luf_point->k[1]) end_point_flags |= IVP_ABOVE;
    else if(ray_end_point.k[1]>rlb_point->k[1]) end_point_flags |= IVP_BELOW;
    
    if(ray_end_point.k[2]<luf_point->k[2]) end_point_flags |= IVP_FRONT;
    else if(ray_end_point.k[2]>rlb_point->k[2]) end_point_flags |= IVP_BEHIND;
    
    // if endpoint is inside the cube, ray hits.
    if(end_point_flags==0) return IVP_TRUE;
    
    // if points are both outside for any coordinate, ray doesn't hit.
    if(start_point_flags & end_point_flags){
	return IVP_FALSE;
    }
    
    // now we need a more thorough check...
    
    // facet 0 (front)
    if((start_point_flags&IVP_FRONT) && !(end_point_flags&IVP_FRONT)){
	IVP_FLOAT pos_dist = luf_point->k[2] - ray_start_point.k[2];
	IVP_FLOAT pos_axis_len = ray_end_point.k[2] - ray_start_point.k[2];
	IVP_ASSERT(pos_dist >= 0.0f);
	IVP_ASSERT(pos_axis_len >= 0.0f);
	IVP_U_Float_Point max_coords(rlb_point->k[0], rlb_point->k[1], luf_point->k[2]);
	IVP_BOOL res = check_ray_against_square(pos_dist, pos_axis_len, luf_point, &max_coords, 0, 1);
	if(res) return IVP_TRUE;
    }
    // facet 1 (right)
    if((start_point_flags&IVP_RIGHT) && !(end_point_flags&IVP_RIGHT)){
	IVP_FLOAT pos_dist = ray_start_point.k[0] - rlb_point->k[0];
	IVP_FLOAT pos_axis_len = ray_start_point.k[0] - ray_end_point.k[0];
	IVP_ASSERT(pos_dist >= 0.0f);
	IVP_ASSERT(pos_axis_len >= 0.0f);
	IVP_U_Float_Point min_coords(rlb_point->k[0], luf_point->k[1], luf_point->k[2]);
	IVP_BOOL res = check_ray_against_square(pos_dist, pos_axis_len, &min_coords, rlb_point, 1, 2);
	if(res) return IVP_TRUE;
    }
    // facet 2 (back)
    if((start_point_flags&IVP_BEHIND) && !(end_point_flags&IVP_BEHIND)){
	IVP_FLOAT pos_dist = ray_start_point.k[2] - rlb_point->k[2];
	IVP_FLOAT pos_axis_len =  ray_start_point.k[2] - ray_end_point.k[2];
	IVP_ASSERT(pos_dist >= 0.0f);
	IVP_ASSERT(pos_axis_len >= 0.0f);
	IVP_U_Float_Point min_coords(luf_point->k[0], luf_point->k[1], rlb_point->k[2]);
	IVP_BOOL res = check_ray_against_square(pos_dist, pos_axis_len, &min_coords, rlb_point, 0, 1);
	if(res) return IVP_TRUE;
    }
    // facet 3 (left)
    if((start_point_flags&IVP_LEFT) && !(end_point_flags&IVP_LEFT)){
	IVP_FLOAT pos_dist =  luf_point->k[0] - ray_start_point.k[0];
	IVP_FLOAT pos_axis_len = ray_end_point.k[0] - ray_start_point.k[0];
	IVP_ASSERT(pos_dist >= 0.0f);
	IVP_ASSERT(pos_axis_len >= 0.0f);
	IVP_U_Float_Point max_coords(luf_point->k[0], rlb_point->k[1], rlb_point->k[2]);
	IVP_BOOL res = check_ray_against_square(pos_dist, pos_axis_len, luf_point, &max_coords, 1, 2);
	if(res) return IVP_TRUE;
    }
    // facet 4 (top)
    if((start_point_flags&IVP_ABOVE) && !(end_point_flags&IVP_ABOVE)){
	IVP_FLOAT pos_dist = luf_point->k[1] - ray_start_point.k[1];
	IVP_FLOAT pos_axis_len =  ray_end_point.k[1] - ray_start_point.k[1];
	IVP_ASSERT(pos_dist >= 0.0f);
	IVP_ASSERT(pos_axis_len >= 0.0f);
	IVP_U_Float_Point max_coords(rlb_point->k[0], luf_point->k[1], rlb_point->k[2]);
	IVP_BOOL res = check_ray_against_square(pos_dist, pos_axis_len, luf_point, &max_coords, 0, 2);
	if(res) return IVP_TRUE;
    }
    // facet 5 (down)
    if((start_point_flags&IVP_BELOW) && !(end_point_flags&IVP_BELOW)){
	IVP_FLOAT pos_dist = ray_start_point.k[1] - rlb_point->k[1];
	IVP_FLOAT pos_axis_len =  ray_start_point.k[1] - ray_end_point.k[1];
	IVP_ASSERT(pos_dist >= 0.0f);
	IVP_ASSERT(pos_axis_len >= 0.0f);
	IVP_U_Float_Point min_coords(luf_point->k[0], rlb_point->k[1], luf_point->k[2]);
	IVP_BOOL res = check_ray_against_square(pos_dist, pos_axis_len, &min_coords, rlb_point, 0, 2);
	if(res) return IVP_TRUE;
    }
    
    return IVP_FALSE;
}

IVP_BOOL IVP_Ray_Solver_Group::check_ray_group_against_cube(const IVP_U_Float_Point *cube_center_ws, IVP_FLOAT cube_size){
    IVP_U_Float_Point dist;
    dist.subtract( cube_center_ws, &center_ws);
    dist.set( IVP_Inline_Math::fabsd(dist.k[0]),
	IVP_Inline_Math::fabsd(dist.k[1]),
	IVP_Inline_Math::fabsd(dist.k[2]));
    cube_size = 0.5f * cube_size + this->radius;
    if ( dist.k[0] > cube_size ) return IVP_FALSE;
    if ( dist.k[1] > cube_size ) return IVP_FALSE;
    if ( dist.k[2] > cube_size ) return IVP_FALSE;
    if ( dist.quad_length() >= cube_size * cube_size * 3 ) return IVP_FALSE;
    
    return IVP_TRUE;
}

IVP_BOOL IVP_Ray_Solver_Os::check_ray_against_compact_ledge_os(const IVP_Compact_Ledge *ledge_to_compare){
    // Checks wether the specified ledge is hit by the specified ray.
    // Adds the corresponding object to the min hash in case of a hit.
    // Get hold of a surface that is pointing into the opposite of the ray direction.
    int n_triangles = ledge_to_compare->get_n_triangles();

    if (n_triangles == 2){ // super fast version for triangle ledges
	const IVP_Compact_Triangle *tri = ledge_to_compare->get_first_triangle();
	const IVP_Compact_Edge *edge = tri->get_first_edge();
	
	IVP_U_Point hesse_vec_os; // prefer normized ?
	IVP_CLS.calc_hesse_vec_object_not_normized(edge, ledge_to_compare, &hesse_vec_os);

	const IVP_U_Float_Point *p0 = IVP_CLS.give_object_coords(edge, ledge_to_compare);

	IVP_DOUBLE z = hesse_vec_os.dot_product(p0);
	IVP_DOUBLE a = ray_start_point.dot_product( &hesse_vec_os ) - z;
	IVP_DOUBLE b = ray_end_point.dot_product( &hesse_vec_os ) - z;

	if (a*b >=0){
	    return IVP_FALSE; // does not hit
	}

	IVP_DOUBLE hit_dist = a/(a-b);
	IVP_U_Point intersect_point; intersect_point.set_interpolate( &ray_start_point, &ray_end_point, hit_dist);

	IVP_Unscaled_QR_Result qr;
	IVP_CLS.calc_unscaled_qr_vals_F_space(ledge_to_compare, edge, &intersect_point,&qr);

	if (qr.is_outside()){
	    return IVP_FALSE;
	}
	
	if (a<0) hesse_vec_os.mult(-1);
	hesse_vec_os.IVP_U_Point::normize();
	hit_listener->add_hit_object(object, ledge_to_compare, tri, hit_dist * ray_length, &hesse_vec_os);
	return IVP_TRUE;
    }
    
    IVP_U_Float_Point ray_start_os;
    IVP_U_Float_Point ray_dir_os;
    
    ray_start_os.set(&ray_start_point);
    ray_dir_os.set(&ray_direction);
    
    const IVP_Compact_Triangle *tri = ledge_to_compare->get_first_triangle();
    const IVP_Compact_Edge *take_edge = 0;
    int i;
    for(i=0; i<n_triangles; i++, tri=tri->get_next_tri()){
	// check triangle
	const IVP_Compact_Edge *edge = tri->get_first_edge();
	IVP_U_Point hesse_vec_os; // prefer normized ?
	IVP_CLS.calc_hesse_vec_object_not_normized(edge, ledge_to_compare, &hesse_vec_os);
	
	// check direction
	IVP_DOUBLE dot_prod = hesse_vec_os.dot_product(&ray_dir_os);	

	if(dot_prod > -P_DOUBLE_RES){ // @@@ select correct side
	    continue;
	}

	// now check first point whether it sees the area
        const IVP_U_Float_Point *p0 = IVP_CLS.give_object_coords(edge, ledge_to_compare);
	IVP_DOUBLE z = hesse_vec_os.dot_product(p0);
	IVP_DOUBLE a = ray_start_point.dot_product( &hesse_vec_os ) - z;
	if ( a > 0 ){
	    // quick check second object 
	    IVP_DOUBLE b = ray_end_point.dot_product( &hesse_vec_os ) - z;
	    if (b > 0) return IVP_FALSE;	// no way to get a hit
	    take_edge = edge;
	    break;
	}

    } // for triangles
    
    if(!take_edge){
	IVP_IF(0){
	    printf("IVP_Ray_Solver::check_ray_against_compact_ledge - no correct face found.\n");
	}
	return IVP_FALSE;
    }
    
    {
	// navigate to potential hit position.
	const IVP_Compact_Edge *edge = take_edge;