ivp_object_polygon_tetra.cxx

hl2 source code. Do not use it illegal.

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


#include <ivp_physics.hxx>
#include <string.h>
#include <ivu_float.hxx>

#include <ivu_list.hxx>
#include <ivu_hash.hxx>
#include <ivu_geometry.hxx>

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

#include "ivp_triangle_gen.hxx"
#include <ivp_object_polygon_tetra.hxx>
#include <ivp_templates_intern.hxx>
#include <ivu_min_hash.hxx>
#include <ivp_tetra_intrude.hxx>

/* for debugging stop after some pops */
int	   n_physical_pops = -1;

/*** DEFINES ***/

//#define SUR_DEBUG
//#define CONVEX_DEBUG

#define P_POP_SURFACE_CONVEX_BLUR (0.1f * P_OBJECT_BLUR)		
#define P_POP_EPS_INIT 0.001f
#define P_POP_EPS_REDUCE_FACTOR 0.125f
#define P_POP_TOO_FLAT_EPS_FACTOR 2.1f // factor of P_Pop_Eps
#define P_POP_SCAL_EPS_INIT 0.01f
                        // [m] safety distance for collisions
#define P_CROSS_EPS 0.0001f
#define P_CROSS_EPS_QUAD (P_CROSS_EPS*P_CROSS_EPS)


/*** GLOBALS ***/
IVP_DOUBLE P_Pop_Eps;
IVP_DOUBLE P_Pop_Scal_Eps;
IVP_DOUBLE P_Pop_Too_Flat_Eps;

/*** METHODS AND SUBS ***/
int IVP_Poly_Point::point_num()
{
    if (!l_tetras) return -1;
    return this - this->l_tetras->points;
}

void IVP_Poly_Point::print(const char *text){
    printf("num %i: ",this->point_num());
    IVP_U_Point::print(text);
}

int IVP_Poly_Point::p(){
    this->print();
    return 0;
}

void p_del_double_triangles(IVP_Triangle **tri_a, IVP_Triangle **tri_b=NULL, IVP_Triangle **tri_c=NULL);
void p_del_double_triangles(IVP_Triangle **tri_a, IVP_Triangle **tri_b, IVP_Triangle **tri_c)
{
    if(tri_a) P_DELETE((*tri_a)->other_side);
    if(tri_b) P_DELETE((*tri_b)->other_side);
    if(tri_c) P_DELETE((*tri_c)->other_side);
    if(tri_a) P_DELETE((*tri_a));
    if(tri_b) P_DELETE((*tri_b));
    if(tri_c) P_DELETE((*tri_c));
}

int p_check_for_flat(IVP_Tri_Edge *a0, IVP_Tri_Edge *b0, IVP_DOUBLE eps)
{
	IVP_DOUBLE dist1 = -a0->triangle->tmp.gen.hesse.get_dist(b0->prev->start_point);
	IVP_DOUBLE dist2 = -b0->triangle->tmp.gen.hesse.get_dist(a0->prev->start_point);
	if( (dist1<eps) || (dist2<eps)){
	    //printf("%f %f\n",dist1,dist2);
	    return 1;
	}
	return 0;
}

void IVP_Triangle::calc_hesse()
{
    IVP_U_Point *p0, *p1, *p2;

    p0 = this->three_edges[0].start_point;
    p1 = this->three_edges[0].next->start_point;
    p2 = this->three_edges[0].prev->start_point;

    this->tmp.gen.hesse.calc_hesse(p0, p2, p1);
    this->tmp.gen.hesse.normize();
}

IVP_DOUBLE IVP_Triangle::calc_areasize()
{
    IVP_U_Hesse norm;
    IVP_U_Point *p0, *p1, *p2;

    p0 = this->three_edges[0].start_point;
    p1 = this->three_edges[0].next->start_point;
    p2 = this->three_edges[0].prev->start_point;

    norm.calc_hesse(p0, p2, p1);
    return norm.real_length() * 0.5f;
}

int IVP_Triangle::print(const char *comment)
{
    // OG problems with sun
    return 0;
    
    const char *obj_name = "unknown name";
    printf("%s '%s' T(%d %d %d) \n",
	   (comment)?comment:"",
	   (obj_name)?obj_name:"",
	   this->three_edges[0].start_point->point_num(), 
	   this->three_edges[0].next->start_point->point_num(),
	   this->three_edges[0].prev->start_point->point_num()
	);
    return 0;
}

IVP_Tri_Edge *IVP_Tri_Edge::other_side()
{
    int i;
    if(!this->triangle->other_side) return NULL;
    IVP_Tri_Edge *e = &this->triangle->other_side->three_edges[0];
    for(i=2; i>=0; i--){
	if(e->next->start_point == this->start_point) return e;
	e++;
    }
    return NULL;
}


void IVP_Tri_Edge::print(const char *text){
    if (!text) text = "";
    const char *name = start_point->get_real_object2()->get_name();
    if (!name) name = "noname";
    printf("%s '%s'	start_%lX: %i	",text,name, 0xff & ( ( (long)this->start_point->l_tetras  ) >>8), this->start_point->point_num());
    this->triangle->print("\n");
}

int IVP_Tri_Edge::p(){
    this->print();
    return 0;
}


int IVP_Object_Polygon_Tetra::check_concavity_and_manage(IVP_Tri_Edge *edge, P_CONVEXIFY_STATE )
{
    // prepo perfect links and perfect hidden flags
    // uses/sets opposite edge

    int flag = edge->check_concavity(edge->opposite);
    edge->opposite->concavity = edge->concavity;
    edge->tmp.gen.concav_flag = (char)flag;
    edge->opposite->tmp.gen.concav_flag = (char)flag;

    if((flag==-2)){
	move_edge_to_epsilon_hash(edge);
    }else{
	move_edge_to_normal_hash(edge);
    }
    return flag;
}

		       
int IVP_Tri_Edge::check_concavity(IVP_Tri_Edge *other_edge)
{
    // calcs concavity and test if edge could be popped
    // sets ggf. concavity and unsolvable of this
    // values for other_edge have to be copied manually afterwards

    // -2: partly overlapping
    // -1: identical
    // 0: convex
    // 1: concav
    
    if(!this){
	printf("NULL edge in check_concavity.\n");
    }

    
    // set concavity as measure for concavity volume (+ -> convex)
    IVP_DOUBLE concav = -this->triangle->tmp.gen.hesse.get_dist(other_edge->prev->start_point);
    {
	IVP_DOUBLE concav2 = -other_edge->triangle->tmp.gen.hesse.get_dist(this->prev->start_point);
	if (concav2 > concav){
	    concav = concav2;
	}
    }
    
    IVP_DOUBLE scal = this->triangle->tmp.gen.hesse.dot_product(&other_edge->triangle->tmp.gen.hesse);


    if(scal > 0.0f){
	// angle greater than 90 degrees or greater 270
	
	if( scal<1.0f-P_Pop_Scal_Eps || IVP_Inline_Math::fabsd(concav) >= P_POP_SURFACE_CONVEX_BLUR){
	    // different planes -> everything normal
	    
	    this->concavity = concav;

	    if(concav < 0){
		return 1; // real concav
	    }else{
		return 0; // real convex
	    }
	}else{
	    // same plane
	    concavity = 0.0f; // is convex (flat)
	    return 0;	
	}
    }else{
	// angle is less than 90 degrees
	this->concavity = concav;
	if (concav > 0){
		return 0; // real convex
	}
	// are triangles in the same plane ?
	if(concav < -P_Pop_Eps){
	    // different planes -> everything normal
		return 1; // real concav
	}else{
	    if(this->prev->start_point == other_edge->prev->start_point){
		CORE;
		return -1; // identical points
	    }
	    return -2;		// windschief
	}
    }
    CORE; // should not have happened
    return -12345; // dummy
}

P_Sur_2D_Triangle::P_Sur_2D_Triangle(int pn0, int pn1, int pn2)
{
    P_MEM_CLEAR(this);
    point_nums[0] = pn0;
    point_nums[1] = pn1;
    point_nums[2] = pn2;

#ifdef SUR_DEBUG
    printf("TRIANGLE GENERATED: %d, %d, %d\n",pn0, pn1, pn2);
#endif
}

P_Sur_2D_Point::P_Sur_2D_Point(int i_point_num)
{
    P_MEM_CLEAR(this);
    point_num = i_point_num;
}

P_Sur_2D_Point::~P_Sur_2D_Point()
{
    ;
}

P_Sur_2D_Line::P_Sur_2D_Line(P_Sur_2D_Point *sp, P_Sur_2D_Point *ep)
{
    P_MEM_CLEAR(this);
    start_point = sp;
    end_point = ep;

    if(sp && ep){
	this->delta_x = ep->k[0] - sp->k[0];
	this->delta_y = ep->k[1] - sp->k[1];
    }
#ifdef SUR_DEBUG
    printf("    Line generated: %d, %d\n", sp->point_num, ep->point_num);
#endif
}

P_Sur_2D_Line::~P_Sur_2D_Line()
{
    ; // end/start_points remain!
}

int P_Sur_2D_Line::point_lies_to_the_left(IVP_U_Point *i_point)
{
    IVP_DOUBLE hesse_dist = this->hesse_dist_to_point(i_point);
    if(hesse_dist <= P_DOUBLE_EPS) return 0; // on the other side
    if(hesse_dist <= P_Pop_Too_Flat_Eps) return 2; // not enough distance for triangle
    return 1;
}

int P_Sur_2D_Line::has_points(P_Sur_2D_Point *point_a, P_Sur_2D_Point *point_b)
{
    if(!point_b){
	if( (start_point==point_a) || (end_point==point_a) ) return 1;
	return 0;
    }
    
    if( (start_point==point_a)&&(end_point==point_b) ) return 1;
    if( (end_point==point_a)&&(start_point==point_b) ) return 1;
    return 0;
}

IVP_DOUBLE P_Sur_2D_Line::dist_to_point(IVP_U_Point *i_point)
{
    // att: maybe negative!
    
    IVP_DOUBLE norm = delta_y*delta_y + delta_x*delta_x;
    if(norm < P_DOUBLE_EPS){
	// line is just a point
	IVP_DOUBLE dx = this->start_point->k[0] - i_point->k[0];
	IVP_DOUBLE dy = this->start_point->k[1] - i_point->k[1];
	return dx*dx + dy*dy;
    }
    
    IVP_DOUBLE hesse_dist = delta_y * (start_point->k[0] - i_point->k[0]) +
	delta_x * (i_point->k[1] - start_point->k[1]); // not normized!

    return hesse_dist / IVP_Inline_Math::sqrtd(norm);
}

IVP_DOUBLE P_Sur_2D_Line::hesse_dist_to_point(IVP_U_Point *i_point)
{
    // att: maybe negative!
    
    IVP_DOUBLE hesse_dist = delta_y * (start_point->k[0] - i_point->k[0]) +
	delta_x * (i_point->k[1] - start_point->k[1]); // not normized!

    return hesse_dist;
}

int P_Sur_2D_Line::point_lies_in_interval(IVP_U_Point *i_point)
{
    // ATT: vorr: point lies on the extension of the line

    // try delta_x
    IVP_DOUBLE line_abs_delta = IVP_Inline_Math::fabsd(delta_x);
    if(line_abs_delta > P_DOUBLE_EPS){
	int dx = (delta_x > 0)? 1: -1;
	IVP_DOUBLE point_delta = (i_point->k[0] - start_point->k[0]) * dx;
	if(point_delta>P_CROSS_EPS && point_delta<line_abs_delta-P_CROSS_EPS){
	    return 1; // definitely inside
	}
	return 0; // outside or exactly on start/end point!!
    }

    // try delta_y
    line_abs_delta = IVP_Inline_Math::fabsd(delta_y);
    if(line_abs_delta > P_DOUBLE_EPS){
	int dy = (delta_y > 0)? 1: -1;
	IVP_DOUBLE point_delta = (i_point->k[1] - start_point->k[1]) * dy;
	if(point_delta>P_CROSS_EPS && point_delta<line_abs_delta-P_CROSS_EPS){
	    return 1; // definitely inside
	}
	return 0; // outside or exactly on start/end point!!
    }

    // line actually is a point
    return 0; // not inside
}

int P_Sur_2D_Line::overlaps_with_line(P_Sur_2D_Line *line_v)
{
#define P_OVERLAP_EPS 1E-8f   
    // ATT: vorr: lines are in a common line
    P_Sur_2D_Line *line_u = this;
    
    // try delta_x
    IVP_DOUBLE line_abs_delta = IVP_Inline_Math::fabsd(delta_x);
    if(line_abs_delta > P_OVERLAP_EPS){
	IVP_DOUBLE u_lower, u_higher;
	if(delta_x > 0.0f){
	    u_lower = line_u->start_point->k[0];
	    u_higher = line_u->end_point->k[0];
	}else{
	    u_lower = line_u->end_point->k[0];
	    u_higher = line_u->start_point->k[0];	    
	}
	u_lower += P_OVERLAP_EPS;
	u_higher -= P_OVERLAP_EPS;
	IVP_DOUBLE v_start = line_v->start_point->k[0];
	IVP_DOUBLE v_end = line_v->end_point->k[0];

	if( ((v_start<=u_lower) && (v_end<=u_lower)) ||
	    ((v_start>=u_higher) && (v_end>=u_higher)) ){
	    return 0; // no overlapping (but maybe 1 common point!)
	}
	return 1; // definitely overlapping
    }

    // try delta_y
    line_abs_delta = IVP_Inline_Math::fabsd(delta_y);
    if(line_abs_delta > P_OVERLAP_EPS){
	IVP_DOUBLE u_lower, u_higher;
	if(delta_y > 0.0f){
	    u_lower = line_u->start_point->k[1];
	    u_higher = line_u->end_point->k[1];
	}else{
	    u_lower = line_u->end_point->k[1];
	    u_higher = line_u->start_point->k[1];	    
	}
	u_lower += P_OVERLAP_EPS;
	u_higher -= P_OVERLAP_EPS;
	IVP_DOUBLE v_start = line_v->start_point->k[1];
	IVP_DOUBLE v_end = line_v->end_point->k[1];

	if( ((v_start<=u_lower) && (v_end<=u_lower)) ||
	    ((v_start>=u_higher) && (v_end>=u_higher)) ){
	    return 0; // no overlapping (but maybe 1 common point!)
	}
	return 1; // definitely overlapping
    }

    // line_u actually is a point
    return line_v->point_lies_in_interval(line_u->start_point);
#undef P_OVERLAP_EPS    
}

int P_Sur_2D_Line::is_crossing_line(P_Sur_2D_Line *line_v)
{
    // returns 1 if line_u (=this) crosses line_v, otherwise 0.