ivp_object_polygon_tetra.cxx

hl2 source code. Do not use it illegal.

void IVP_Object_Polygon_Tetra::pop_problematic_edge(IVP_Tri_Edge *edge){
    IVP_Tri_Edge *oppo = edge->opposite;
    int is_epsilon_problem = 0;
    int i_got_a_real_problem =0;
    IVP_DOUBLE eps = P_Pop_Eps * 1.1f;
    
    /* **** First check dist of opposing points *********/
    {
	IVP_DOUBLE dist0 = edge->triangle->tmp.gen.hesse.get_dist(oppo->prev->start_point);
	IVP_DOUBLE dist1 = oppo->triangle->tmp.gen.hesse.get_dist(edge->prev->start_point);
	if (edge->tmp.gen.concav_flag == 0) { // convex
	    dist0 = -dist0;
	    dist1 = -dist1;
	}
	
	if (dist1< dist0) dist0 = dist1;
	if (dist0 < P_Pop_Eps * 6.0f){
	    is_epsilon_problem = 1;
	}
#ifdef CONVEX_DEBUG
	printf("***** Problematic %s,pop: edge %i %i, other_p %i %i, dist %f\n",
	       (edge->tmp.gen.concav_flag == 0) ? "convex": "CONCAV",
	       edge->start_point->point_num(),
	       oppo->start_point->point_num(),
	       edge->prev->start_point->point_num(),
	       oppo->prev->start_point->point_num(),
	       dist0);
#endif	

    }
    
    IVP_U_Point mid_of_line;
    mid_of_line.set_multiple(edge->start_point,0.5f);
    mid_of_line.add_multiple(oppo->start_point,0.5f);

    IVP_U_Point new_point;
    
    if (is_epsilon_problem){
	if (edge->tmp.gen.concav_flag == 0) { // convex
	    new_point.add_multiple(&mid_of_line,&edge->triangle->tmp.gen.hesse,eps);
	}else{
	    i_got_a_real_problem = 1;
	}
    }else{
	this->calc_extrusion_point(edge,&new_point);
    }

    if (!i_got_a_real_problem && edge->tmp.gen.concav_flag != 0){ // check flatness of concav edges
	// provide edge variables of already existing triangles
	IVP_Tri_Edge *a0 = edge;     		// pop triangle a
	IVP_Tri_Edge *a1 = a0->next;
	IVP_Tri_Edge *a2 = a1->next;
   
	IVP_Tri_Edge *b0 = a0->opposite; 	// pop triangle b
	IVP_Tri_Edge *b1 = b0->next;
	IVP_Tri_Edge *b2 = b1->next;

	// provide four new triangles
	IVP_Triangle *tri_a = generate_double_triangle(b2->start_point, a2->start_point, a0->start_point);
	IVP_Triangle *tri_b = generate_double_triangle(a2->start_point, b2->start_point, a1->start_point);

    // check wether pop becomes too flat 
	int pop_too_flat_flag = 0;
	pop_too_flat_flag = p_check_for_flat( &tri_a->three_edges[0], &tri_b->three_edges[0], P_Pop_Too_Flat_Eps);
	if(pop_too_flat_flag == 1){
#ifdef CONVEX_DEBUG	
	    printf("problematic pop would be too flat.\n");
#endif
	    p_del_double_triangles(&tri_a, &tri_b);
	    i_got_a_real_problem = 1;
	}
    }
    

    if (!i_got_a_real_problem){

	remove_edge_from_min_list(edge); // in case of convex edges
	// insert new point in extra linked list
	IVP_Extra_Point *extra_point = new IVP_Extra_Point;
	IVP_Tetra_Point *extra_tetra_point = new IVP_Tetra_Point;
	P_MEM_CLEAR(extra_point);
	P_MEM_CLEAR(extra_tetra_point);

	extra_point->tmp.tetra_point = extra_tetra_point;
	extra_tetra_point->opoint = extra_point;
	extra_point->set(&new_point); // koords
	
	extra_point->l_tetras = this;
	extra_tetra_point->init(tetra_intrude);
	
	IVP_Tri_Edge *a0 = edge;     		// pop triangle a
	IVP_Tri_Edge *a1 = a0->next;
	IVP_Tri_Edge *a2 = a1->next;    
	// perform pyramid pop
	IVP_Triangle *tri_pa = generate_double_triangle(a0->next->start_point, a0->start_point, extra_point);
	IVP_Triangle *tri_pb = generate_double_triangle(a1->next->start_point, a1->start_point, extra_point);
	IVP_Triangle *tri_pc = generate_double_triangle(a2->next->start_point, a2->start_point, extra_point);

	// check wether an epsilon problem occurred
	IVP_INTRUSION_CHECK_RESULTS i_flag = this->tetra_intrude->check_intrusion(a0,
										 tri_pa->three_edges[0].prev,
										 tri_pb->three_edges[0].next,
										 tri_pc->three_edges[0].next, extra_points, 3);
	if(i_flag){
#ifdef CONVEX_DEBUG
	    printf("********* Epsilon problem with extra point. P_Pop_Eps: %f\n", P_Pop_Eps);
#endif
	    P_DELETE(extra_point);
	    P_DELETE(extra_tetra_point);
	    p_del_double_triangles(&tri_pa, &tri_pb, &tri_pc);
	    i_got_a_real_problem = 1;
	}else{
	    extra_point->next = this->extra_points;
	    this->extra_points = extra_point;
	    this->n_extra_points++;
	    
	    this->link_triangle_couple(tri_pa, a0, NULL, NULL); 
	    this->link_triangle_couple(tri_pb, a1, tri_pa->three_edges[0].prev, NULL);
	    this->link_triangle_couple(tri_pc, a2, tri_pb->three_edges[0].prev, tri_pa->three_edges[0].next);

	    this->hide_triangle(tri_pa);
	    this->hide_triangle(tri_pb);
	    this->hide_triangle(tri_pc);
	    this->hide_triangle(a0->triangle);
	}
    }
    
    if (i_got_a_real_problem){
#ifdef CONVEX_DEBUG
	printf("********* Epsilon problem moved to epsilon hash: epsilon = %f\n", P_Pop_Eps);
#endif
	this->move_edge_to_epsilon_hash(edge);
    }
}




void IVP_Object_Polygon_Tetra::record_intruding_convex_edges(IVP_Intrusion_Status *status)
{
    IVP_Intrusion_Intersection *is = status->intersections;
    for( ; is; is = is->next){
	IVP_INTRUSION_CHECK_RESULTS typ = is->type;
	if(typ != IVP_INTRUSION_CHECK_LINE) continue;
	IVP_Poly_Point *p1 = is->line_endpoints[0];
	IVP_Poly_Point *p2 = is->line_endpoints[1];
	IVP_Tri_Edge *e=this->get_an_edge_with_points(p1, p2);
	IVP_ASSERT(e);

	// search the matching edge with this points
	IVP_Tri_Edge *e2 = e;
	do {
	    if((e2->tmp.gen.concav_flag==0) && !e2->triangle->flags.is_hidden){
		this->move_edge_to_convex_intrude_hash(e2);
		break; // searching for convex unhidden edges only
	    }
	    e2 = e2->behind;
	}while( e2 != e);
    }
}

void IVP_Object_Polygon_Tetra::link_existing_pop_edge(IVP_Tri_Edge *pop_edge)
{
	IVP_Tri_Edge *e = pop_edge->opposite->next;
	IVP_Tri_Edge *end_edge = pop_edge;
	//IVP_Poly_Point *p_sp = pop_edge->start_point;
	IVP_Poly_Point *p_ep = pop_edge->next->start_point;
	while(1){
	    if(e==end_edge) break; // all neighbours visited
	    //IVP_Poly_Point *n_sp = e->start_point;
	    IVP_Poly_Point *n_ep = e->next->start_point;
	    //IVP_ASSERT (p_sp==n_sp);
	    if(p_ep==n_ep){
		// encountered a pop edge -> link it
		this->p_link_edge(e, pop_edge->opposite);
#ifdef CONVEX_DEBUG	
		printf("\n**********************************************pop edge already existed in neighbour region -> linked it.\n");
		e->print("e");
		pop_edge->print("e0");
		printf("\n");
#endif
		break;
	    }
	    e = e->opposite->next;
	}
}

void IVP_Object_Polygon_Tetra::pop_concav_edge(IVP_Tri_Edge *edge)
{
    // assert edge is real concave 
#ifdef CONVEX_DEBUG
    printf("Try pop: edge %d %d with %d & %d. concavity %g)",
	   edge->start_point->point_num(),
	   edge->next->start_point->point_num(),
	   edge->prev->start_point->point_num(),
	   edge->opposite->prev->start_point->point_num(),
	   edge->concavity );
#endif

    // provide edge variables of already existing triangles
    IVP_Tri_Edge *a0 = edge;     		// pop triangle a
    IVP_Tri_Edge *a1 = a0->next;
    IVP_Tri_Edge *a2 = a1->next;
   
    IVP_Tri_Edge *b0 = a0->opposite; 	// pop triangle b
    IVP_Tri_Edge *b1 = b0->next;
    IVP_Tri_Edge *b2 = b1->next;
       
    // provide four new triangles
    IVP_Triangle *tri_a = generate_double_triangle(b2->start_point, a2->start_point, a0->start_point);
    IVP_Triangle *tri_b = generate_double_triangle(a2->start_point, b2->start_point, a1->start_point);

    IVP_Tri_Edge *e0 = &tri_a->three_edges[0];
    IVP_Tri_Edge *f0 = &tri_b->three_edges[0];
    
    /* Check wether pop is allowed */
    // calculate a required pop flag (for a single neighbour triangle)
    ivp_u_bool tetra_close_flag = IVP_FALSE;
    IVP_Triangle *tri_first = tri_a;
    IVP_Triangle *tri_second = tri_b;
    int n_new_triangles = 2;
    if(a0->next->opposite->triangle == b0->prev->opposite->triangle){
	n_new_triangles--;
	tetra_close_flag = IVP_TRUE;
    }
    if(a0->prev->opposite->triangle == b0->next->opposite->triangle){
	tetra_close_flag = IVP_TRUE;
	n_new_triangles--;
	// swap: calc_intrusion_status wants existing tris first
	tri_first = tri_b;
	tri_second = tri_a;
    }

    this->remove_edge_from_min_list(edge);

    // check wether pop becomes too flat 
    int pop_too_flat_flag = 0;
    if(!tetra_close_flag){
	pop_too_flat_flag = p_check_for_flat(e0, f0, P_Pop_Too_Flat_Eps);
	if(pop_too_flat_flag == 1){
	    this->move_edge_to_epsilon_hash(edge);
#ifdef CONVEX_DEBUG	
	    printf("\n            too flat -> edge moved to epsilon problem hash!\n");
#endif
	    p_del_double_triangles(&tri_a, &tri_b);
	    return;
	}
    }
    
    IVP_INTRUSION_CHECK_RESULTS intrusion_val;
    {
	IVP_Tri_Edge *otherside0 = tri_first->three_edges[0].other_side();
	IVP_Tri_Edge *otherside1 = tri_second->three_edges[0].other_side();
	intrusion_val = this->tetra_intrude->check_intrusion(a0, b0,otherside0, otherside1,
				 this->extra_points, n_new_triangles );
    }
    
    if((intrusion_val!=IVP_INTRUSION_CHECK_NONE)){
	// alas, must abort pop
	if(intrusion_val!=IVP_INTRUSION_CHECK_EPSILON){
	    this->move_edge_to_problem_hash(edge);
	    IVP_Intrusion_Status *status =
		this->tetra_intrude->calc_intrusion_status(a0, b0,
							   tri_first->three_edges[0].other_side(),
							   tri_second->three_edges[0].other_side(),
							   this->extra_points, n_new_triangles );
	    this->record_intruding_convex_edges(status);
#ifdef CONVEX_DEBUG	
	    printf("\n            intrusion: edge added to problem_min_hash.\n");
	    status->print("test status");
#endif
	    delete status;
	}else{
#ifdef CONVEX_DEBUG	
	    printf("\n            epsilon violation. smaller epsilon will work. shifted to eps hash.\n");
#endif
	    this->move_edge_to_epsilon_hash(edge);
	}
	p_del_double_triangles(&tri_a, &tri_b);
	return;
    }

    /*** insert new triangles ***/
    IVP_Tri_Edge *p0 = b1->opposite;
    IVP_Tri_Edge *q0 = b2->opposite;
    IVP_Tri_Edge *n0 = a2->opposite;
    IVP_Tri_Edge *o0 = a1->opposite;
    
    IVP_Tri_Edge *link_to_tri_a_edge = NULL;
    IVP_Tri_Edge *link_to_tri_b_edge = NULL;
    
    if(p0->triangle == n0->triangle){
	link_to_tri_a_edge = n0->next->opposite;
	P_DELETE(tri_a);
    }else{
	make_double_triangle_permanent(tri_a);
    }
    if(q0->triangle == o0->triangle){
	link_to_tri_b_edge = o0->prev->opposite;
	P_DELETE(tri_b);
    }else{
	make_double_triangle_permanent(tri_b);
    }
    
    if (tri_a){
	if (tri_b){
	    this->link_triangle_couple(tri_a, NULL, n0, p0);
	    this->link_triangle_couple(tri_b, e0, q0, o0);
	}else{
	    this->link_triangle_couple(tri_a, link_to_tri_b_edge, n0, p0);
	}
    }else{
	if (tri_b){
	    this->link_triangle_couple(tri_b, link_to_tri_a_edge, q0, o0);
	}else{
	    printf("* NULL pop");
	    // anything else?
	}
    }
	    
    // set hiding flags. algorithm wants to know what he may access
    this->hide_triangle(a0->triangle); // popped triangles are hidden now
    this->hide_triangle(b0->triangle);

    this->hide_triangle(a1->opposite->triangle);
    this->hide_triangle(b1->opposite->triangle);

    // if pop edge already exists in neighborhood -> link it
    if(!tetra_close_flag){
	this->link_existing_pop_edge(f0);
	//this->link_existing_pop_edge(e0);
    } 

#ifdef CONVEX_DEBUG	
    printf(" *\n");
#endif

}
    
void IVP_Object_Polygon_Tetra::convexify()
{
    // ATT! not idempotent
    
#ifdef CONVEX_DEBUG
    printf("\n\nCONVEXIFY\n==============\n");
#endif

    
    // init global epsilons
    P_Pop_Eps = P_POP_EPS_INIT;
    P_Pop_Scal_Eps = P_POP_SCAL_EPS_INIT;
    P_Pop_Too_Flat_Eps = P_POP_TOO_FLAT_EPS_FACTOR * P_Pop_Eps;
    
    // set random seed for random breakup
    // p_srand(123);

    // set tetra points in polygon
    int point_anz = this->n_points;
    int n_malloced_points = point_anz;
    IVP_Tetra_Point *t4_points = (IVP_Tetra_Point *)p_calloc(sizeof(IVP_Tetra_Point),n_malloced_points);
    int i;
    for(i=point_anz-1; i>=0; i--){
	t4_points[i].opoint = &this->points[i];
	this->points[i].tmp.tetra_point = &t4_points[i];
    }
   
    this->tetra_intrude = new IVP_Tetra_Intrude(t4_points, this->n_points);
    tetra_intrude->n_tetra_points_malloced = n_tetra_points_malloced;

    IVP_Triangle *tri;
    for (tri = triangles.first; tri; tri = tri->next){
        for(i=0; i<=2; i++){
	    IVP_Tri_Edge *e = &tri->three_edges[i];
	    e->tmp.gen.tetra_point = e->start_point->tmp.tetra_point;
	}
	tri->calc_hesse();
    }
    {
	for (i= P_HASH_CLASS_NORMAL; i< P_HASH_CLASS_MAX;i++){
	    this->min_hash[i] = new IVP_U_Min_Hash(512);
	}
    }

    this->calc_concavities();
#ifdef CONVEX_DEBUG
    int num_of_loops = 0;
#endif
    
    /*** pop concav edges till everything is pretty convex ***/
    while(1){
#ifdef CONVEX_DEBUG	
	this->check_konsistency_of_triangles();
	    
	printf("%i:",num_of_loops);
	for (i=P_HASH_CLASS_NORMAL; i<P_HASH_CLASS_MAX;i++){
	    printf(" %i",min_hash[i]->counter);
	}
	printf(":   ");
	num_of_loops++;
	if(num_of_loops == n_physical_pops -1){
	    printf("Nearly Last Loop!\n");
	}

	if(num_of_loops == n_physical_pops ){
	    printf("P_CONVEX_LOOPS reached!\n");
	    break;
	}
#endif
	
	// ******** take an existing normal concav edge and pop it
	IVP_Tri_Edge *edge = (IVP_Tri_Edge *)min_hash[P_HASH_CLASS_NORMAL]->find_min_elem();
	if (edge){
	    this->pop_concav_edge(edge);
	    continue;
	}
	
	// ******** tak