ivp_object_polygon_tetra.cxx

hl2 source code. Do not use it illegal.

    // it doesn't count as a crossing, if lines have a
    // common end/start point.

   
    P_Sur_2D_Line *line_u = this;
#ifdef SUR_DEBUG
    printf("    crossing (%d, %d) with (%d, %d): ", line_u->start_point->point_num,
	   line_u->end_point->point_num, line_v->start_point->point_num,
	   line_v->end_point->point_num);
#endif

    // delta values for quickness and readability
#define u_dx (line_u->delta_x)
#define u_dy (line_u->delta_y)
#define v_dx (line_v->delta_x)
#define v_dy (line_v->delta_y)
#define DET_EPS 0.000000001f



    // calc determinante of (inhomogene) linear system
    IVP_DOUBLE D = v_dx * u_dy - u_dx * v_dy;
    if(IVP_Inline_Math::fabsd(D) < DET_EPS){
#ifdef SUR_DEBUG
	printf("det < det_eps: ");
#endif	
	// linear dependency: on the line or just parallel?
	if(IVP_Inline_Math::fabsd(line_u->dist_to_point(line_v->start_point)) < P_CROSS_EPS_QUAD){
#ifdef SUR_DEBUG
	    printf("on the line: ");
#endif
	    if( line_u->overlaps_with_line(line_v) ){
#ifdef SUR_DEBUG
		printf("overlapping (crossing)!\n");
#endif
		return 1; // lines are overlapping
	    }else{
#ifdef SUR_DEBUG
		printf("not overlapping (no crossing)!\n");
#endif		    
		return 0;
	    }
	}else{
#ifdef SUR_DEBUG
	    printf("really parallel.\n");
#endif	
	    return 0; // really parallel
	}
    }   
 
    // check whether lines have common end/start points
    if( (line_u->start_point == line_v->end_point)   ||
        (line_u->start_point == line_v->start_point) ||
        (line_u->end_point   == line_v->start_point) ||
        (line_u->end_point   == line_v->end_point) ){
#ifdef SUR_DEBUG
	printf("common end/start point -> no crossing\n");
#endif
	return 0; // shall not count as crossing
    }

    // calc delta of start_points ('origins')
    IVP_DOUBLE o_dx = line_v->start_point->k[0] - line_u->start_point->k[0];
    IVP_DOUBLE o_dy = line_v->start_point->k[1] - line_u->start_point->k[1];
    
    IVP_DOUBLE left_border, right_border;
    if(D>0.0f){
	left_border = 0.0f;
	right_border = D;
    }else{
	left_border = D;
	right_border = 0.0f;	
    }
 
    // check crossing on line_u
    IVP_DOUBLE u_t = v_dx*o_dy - v_dy*o_dx; // u_sp + u_t*D*(u_ep-u_sp) = crossing
#ifdef SUR_DEBUG
	printf("u_t %g: ", u_t/D);
#endif	
    if(u_t < left_border || u_t > right_border){
#ifdef SUR_DEBUG
	printf("no crossing.\n");
#endif	
	return 0; // crosses beyond line interval
    }
    // check crossing on line_v
    IVP_DOUBLE v_t = u_dx*o_dy - o_dx*u_dy; // v_sp + v_t*D*(v_ep-v_sp) = crossing
#ifdef SUR_DEBUG
	printf("v_t %g: ", v_t/D);
#endif	
    if(v_t < left_border || v_t > right_border){
#ifdef SUR_DEBUG
	printf("no crossing.\n");
#endif	
	return 0; // crosses beyond line interval
    }
    // real crossing
#ifdef SUR_DEBUG
    printf("CROSSING.\n");
#endif	
    return 1;
    
#undef u_dx  
#undef u_dy  
#undef v_dx  
#undef v_dy  
#undef DET_EPS    
}

P_Sur_2D::P_Sur_2D(IVP_Object_Polygon_Tetra *tetras_, IVP_Template_Surface *sur)
{
    P_MEM_CLEAR(this);
    orig_tetras = tetras_;
    orig_surface = sur;
}

P_Sur_2D::~P_Sur_2D()
{
    P_FREE(line_array);
    P_FREE(point_array);
    while(lines.first){
	P_Sur_2D_Line *l = lines.first;
	P_DELETE(l->start_point);
	P_DELETE(l->end_point);
	lines.remove(l);
	P_DELETE(l);
    }
    P_Sur_2D_Triangle *tri;
    while((tri = triangles.first)){
	triangles.remove(tri);
	P_DELETE(tri);
    }
}

IVP_ERROR_STRING P_Sur_2D::calc_line_representation()
{
    IVP_Template_Surface *sur = this->orig_surface;
    if(!sur){
	return "calc_line_representation: no orig_surface specified!\n";
    }
    

    IVP_Object_Polygon_Tetra *pop = orig_tetras;
    
#ifdef SUR_DEBUG    
    printf("\n\n\n***********************\n"
	   "POP: %d, SURFACE_NUM %d with %d points\n\n", (int)pop, sur->get_surface_index(),
	   sur->n_lines);
#endif    
    // 3d->2d trafo: skip koord with greatest ohesse extent
    IVP_U_Point *hesse = &sur->normal;
    int max_koord = 0;
    IVP_DOUBLE max_koord_val = IVP_Inline_Math::fabsd(hesse->k[0]);
    if(IVP_Inline_Math::fabsd(hesse->k[1]) > max_koord_val){
	max_koord_val = IVP_Inline_Math::fabsd(hesse->k[1]);
	max_koord = 1;
    }
    if(IVP_Inline_Math::fabsd(hesse->k[2]) > max_koord_val){
	max_koord_val = IVP_Inline_Math::fabsd(hesse->k[2]);
	max_koord = 2;
    }

    
    int td_k0, td_k1;
    switch(max_koord){
    case 0:
	td_k0 = 1; td_k1 = 2;
	break;
    case 1:
	td_k0 = 0; td_k1 = 2;
	break;
    case 2:
	td_k0 = 0; td_k1 = 1;
	break;
    default:
	td_k0 = td_k1 = 0; // compiler lullaby
	CORE;
    }
    
    // is trafo mirrored ?
    int trafo_is_mirrored = 0;
    if(hesse->k[max_koord] < 0.0f) trafo_is_mirrored = 1;

#ifdef SUR_DEBUG
    printf("hesse: %g %g %g; max_koord: %d; take koords %d %d; mirrored: %d\n",
	   hesse->k[0], hesse->k[1], hesse->k[2], max_koord, td_k0, td_k1, trafo_is_mirrored);
#endif
    if(max_koord==1) trafo_is_mirrored = 1-trafo_is_mirrored;

    // transfer line and point info
    P_Sur_2D_Point **point_hash_array = (P_Sur_2D_Point**)p_calloc(pop->n_points,
							    sizeof(P_Sur_2D_Point*));
    P_FREE(this->line_array);
    this->line_array = (P_Sur_2D_Line **)p_calloc(sur->n_lines,
							    sizeof(P_Sur_2D_Line*));
    P_FREE(this->point_array);
    this->point_array = (P_Sur_2D_Point **)p_calloc(sur->n_lines,
							    sizeof(P_Sur_2D_Point*));
    int point_count = 0;
    int i;
    for(i=sur->n_lines-1; i>=0; --i){

	// read line info
	int line_num = sur->lines[i];
	IVP_Template_Line *line = &pop->template_polygon->lines[line_num];

	int revert = sur->revert_line[i];
	if(trafo_is_mirrored) revert = 1 - revert;
	int start_point_num = line->p[revert];
	int end_point_num = line->p[1-revert];

	// gen 2D line and points
	P_Sur_2D_Point *start_point = point_hash_array[start_point_num];
	if(!start_point){
	    start_point = new P_Sur_2D_Point(start_point_num);
	    point_hash_array[start_point_num] = start_point;
	    point_array[point_count++] = start_point;
	}
	start_point->set(pop->points[start_point_num].k[td_k0],
		       pop->points[start_point_num].k[td_k1], 0.0f);
	
	P_Sur_2D_Point *end_point = point_hash_array[end_point_num];
	if(!end_point){
	    end_point = new P_Sur_2D_Point(end_point_num);
	    point_hash_array[end_point_num] = end_point;
	    point_array[point_count++] = end_point;
	}
	end_point->set(pop->points[end_point_num].k[td_k0],
		       pop->points[end_point_num].k[td_k1], 0.0f);
	
	P_Sur_2D_Line *td_line = new P_Sur_2D_Line(start_point, end_point);
	start_point->line_ref = td_line;
	IVP_ASSERT(td_line);
	this->lines.insert(td_line);
	this->line_array[i] = td_line;// bookmark for posterior deletion
    }

    IVP_ASSERT(point_count == sur->n_lines);
    
    // clean up
    P_FREE(point_hash_array);
    
    return IVP_NO_ERROR;
}

int p_count_reachable(P_Sur_2D_Point *i_point)
{
    // counts (and marks) all points not yet reached
    int reached_counter = 0;

    P_Sur_2D_Point *point;
    for(point=i_point; point && !point->was_reached; point=point->line_ref->end_point){
	point->was_reached = 1;
	reached_counter++;
    }
    return reached_counter;
}

IVP_DOUBLE p_ab_quad_length(P_Sur_2D_Point *pa, P_Sur_2D_Point *pb, P_Sur_2D_Point *pc)
{
    // return added lengths of both triangle sides
    return pc->quad_distance_to(pa) + pc->quad_distance_to(pb);
}

IVP_ERROR_STRING P_Sur_2D::calc_triangle_representation()
{
    // opt: check whether there are any islands in the surface
    int having_islands = 0;
    int triangle_count = 0;
    int n_lines = this->orig_surface->n_lines;
    int reached_points_counter = p_count_reachable(this->lines.first->start_point);

    IVP_U_Min_Hash ab_min_hash(16);
    P_Sur_2D_Line *td_base_line;
   
    if(reached_points_counter < n_lines){
	having_islands = 1;
    }
#ifdef SUR_DEBUG
    printf("   Having islands would be: %d\n", having_islands);
#endif
    having_islands = 1; // forced

    P_Sur_2D_Line *td_ca_line = NULL;
    P_Sur_2D_Line *td_bc_line = NULL;
    
    // for all lines
    int wrong_flag = 0;
    int loop_counter = 0;
    while((td_base_line=this->lines.first)){
#ifdef SUR_DEBUG
	printf("TAKE BASE LINE: (%d %d)\n", td_base_line->start_point->point_num,
	       td_base_line->end_point->point_num);
#endif
	if (loop_counter++ > 100){ //@@@@SF: changed from 100000 to 100 [05.03.2000]
	    //printf("Degenerated polygon found:\n");
//	    P_Sur_2D_Point *point_a = td_base_line->start_point; // a b c form a triangle
//	    P_Sur_2D_Point *point_b = td_base_line->end_point;
//	    printf("  %f %f %f\n", point_a->k[0], point_a->k[1], point_a->k[2]);
//	    printf("  %f %f %f\n", point_b->k[0], point_b->k[1], point_b->k[2]);
	    P_Sur_2D_Line *td_point_line;
 	    for(td_point_line=this->lines.first; td_point_line; td_point_line=td_point_line->next){
		P_Sur_2D_Point *point_c = td_point_line->start_point;
		printf("  %f %f %f\n", point_c->k[0], point_c->k[1], point_c->k[2]);
	    }
	    return "Cannot convert";
	}
	// put points into min_hash
	while (ab_min_hash.find_min_elem()){
	    ab_min_hash.remove_min();
	}
	P_Sur_2D_Point *point_a = td_base_line->start_point; // a b c form a triangle
	P_Sur_2D_Point *point_b = td_base_line->end_point;
	P_Sur_2D_Line *td_point_line;
 	for(td_point_line=this->lines.first; td_point_line; td_point_line=td_point_line->next){
	    P_Sur_2D_Point *point_c = td_point_line->start_point;
	    ab_min_hash.add((void *)td_point_line,p_ab_quad_length(point_a, point_b, point_c));    
	}

	// now try triangles in ascending side length order
	for(td_point_line=(P_Sur_2D_Line *)ab_min_hash.find_min_elem();
	    td_point_line;
	    ab_min_hash.remove_min(), td_point_line=(P_Sur_2D_Line *)ab_min_hash.find_min_elem()){
	    if(td_point_line == td_base_line) continue;	    
	    if(td_point_line->start_point == td_base_line->end_point) continue;
#ifdef SUR_DEBUG
	    printf("  Trying point %d: ", td_point_line->start_point->point_num);
#endif		

	    // set koords
	    // point_a and point_b are already set
	    P_Sur_2D_Point *point_c = td_point_line->start_point;
	    
	    // check side: point_c must be on the left!!
	    int dist_flag;
	    if(! (dist_flag=td_base_line->point_lies_to_the_left(point_c)) ){
#ifdef SUR_DEBUG
		if(dist_flag==2){
		    printf("lies to near for triangle!");
		}else{
		    printf("lies on wrong side.\n");			    
		}
#endif		
		continue;
	    }
#ifdef SUR_DEBUG
	    printf("side OK.\n");
#endif		

	    int skip_this_point = 0;

	    // provide the two other triangle sides as lines (bc & ca)
#ifdef SUR_DEBUG
		printf("    check sides of triangle:\n");
#endif		
	    delete td_ca_line;
	    td_ca_line = new P_Sur_2D_Line(point_c, point_a);	    
	    delete td_bc_line;
	    td_bc_line = new P_Sur_2D_Line(point_b, point_c);

            // for all lines: check crossing
	    P_Sur_2D_Line *td_cross_line;
	    for(td_cross_line=this->lines.first; td_cross_line; td_cross_line=td_cross_line->next){
		// crosses ca ?
		if(!td_cross_line->has_points(point_c, point_a)){ // !'identical'
		    if(td_cross_line->is_crossing_line(td_ca_line)){
			skip_this_point = 1;
			break;
		    }
		}
		
		// crosses bc ?
		if(!td_cross_line->has_points(point_b, point_c)){ // !'identical'
		    if(td_cross_line->is_crossing_line(td_bc_line)){
			skip_this_point = 1;
			break;
		    }
		}
	    }
	    if(skip_this_point){
		if(!ab_min_hash.find_min_elem()){
		    printf("Couldn't find a matching point to baseline!\n");
		    CORE;
		}
#ifdef SUR_DEBUG
		printf("    ...giving up point %d because of crossing. next one!\n",
		       td_point_line->start_point->point_num);
#endif		
		continue;
	    }

	    // something inside?
	    if(having_islands){
		P_Sur_2D_Line *td_inside_line;
		for(td_inside_line=this->lines.first; td_inside_line; td_inside_line=td_inside_line->next){
		    // start_point inside triangle?
		    P_Sur_2D_Point *sp = td_inside_line->start_point;
		    if( td_base_line->point_lies_to_the_left(sp) &&
			td_bc_line->point_lies_to_the_left(sp)   &&
			td_ca_line->point_lies_to_the_left(sp)){
			// alas, triangle not empty...
			skip_this_point = 1;
			break;
		    }
		}
	    }
	    if(skip_this_point){
		if(!td_point_line->next){
		    printf("Couldn't find a matching point to baseline!\n");
		    CORE;
		}
#ifdef SUR_DEBUG
		printf("    ...giving up point because of point(s) inside. next one!\n");
#endif		
		continue;
	    }

	    // take triangle