ivp_object_polygon_tetra.cxx

hl2 source code. Do not use it illegal.

	    if(edge != edge->other_side()->other_side()){
		error_flag = "error";
		printf("physic_test: edge != edge->other_side()->other_side() in triangle "); edge->print("\n");
	    }
	    if(edge->prev->start_point == edge->opposite->prev->start_point){
		error_flag = "error";
		printf("physic_test: edge->prev->sp == edge->opp->prev->sp in triangle "); edge->print("\n");
	    }
	    if(edge->triangle == edge->opposite->triangle){
		error_flag = "error";
		printf("physic_test: edge->triangle == edge->opposite->triangle in triangle "); edge->print("\n");
	    }
	    if(edge->behind->other_side()->behind != edge->other_side()){
		error_flag = "error";
		printf("physic_test: edge->behind->other_side()->behind = edge->other_side in triangle "); edge->print("\n");
	    }
	    if(edge->triangle != tri){
		error_flag = "error";
		printf("physic_test: edge->triangle != tri in triangle "); edge->print("\n");
	    }
	    if((edge->behind->start_point != edge->start_point) || (edge->behind->next->start_point != edge->next->start_point)){
		error_flag = "error";
		printf("physic_test: (edge->behind->sp != edge->sp) || (edge->behind->next->sp != edge->next->sp) in triangle "); tri->print("\n");
	    }
	}
    }
    
    if(ph->triangles.len != n_triangles_check){
	printf("physik_test: Anzahl der Triangles (%d) != n_triangles (%d)!\n",
	       n_triangles_check, ph->triangles.len);
		error_flag = "error";
    }
    
    return error_flag;
}

void IVP_Object_Polygon_Tetra::free_triangles()
{
    /* Warning: Does not check references to tri edge !! */
    IVP_Triangle *tri;
    for (tri = triangles.first; tri; tri = triangles.first){
	triangles.remove(tri);
	delete tri;
    }
    IVP_Extra_Point *ep,*nep;
    for (ep = extra_points; ep ;ep = nep){
	nep = ep->next;
	delete ep;
    }
    extra_points= 0;
}

void IVP_Object_Polygon_Tetra::calc_concavities()
{
    // check for concav edges, count and calc them

    // calc concavity values
    IVP_Triangle *tri;
    const IVP_DOUBLE uninit = 123456.0f;
    for (tri = this->triangles.first; tri; tri = tri->next){
	IVP_Tri_Edge *edge = &tri->three_edges[0];
	for(int i=2; i>=0; edge=edge->next, i--){
	    edge->concavity = uninit;
	}
    }
	
    for (tri = this->triangles.first; tri; tri = tri->next){
	if(tri->flags.is_hidden) continue;
	int i;
	IVP_Tri_Edge *edge = &tri->three_edges[0];
	for(i=2; i>=0; edge=edge->next, i--){
	    if((edge->concavity == uninit)
	       &&(!edge->triangle->flags.is_hidden)
	       &&(!edge->opposite->triangle->flags.is_hidden)) {
		int flag = this->check_concavity_and_manage(edge, P_CONVEXIFY_STATE_INIT);
		if(flag == -1){
		    printf("Terminal object has identical triangles!!!\n");
		    CORE;
		}
	    }
	}
    }
}

IVP_DOUBLE IVP_Object_Polygon_Tetra::rate_tri_edge(IVP_Tri_Edge *edge){
    IVP_U_Point *p0 = edge->prev->start_point;
    IVP_U_Point *p1 = edge->opposite->prev->start_point;
    return p0->quad_distance_to(p1);
}

void IVP_Object_Polygon_Tetra::move_edge_to_problem_hash(IVP_Tri_Edge *edge){
    IVP_Tri_Edge *opp = edge->opposite;
    this->remove_edge_from_min_list(edge);

    this->tetra_intrude->checkout_edge(edge);
    this->tetra_intrude->checkout_edge(edge->opposite);

    if (opp<edge) edge = opp;
    if (edge->triangle->flags.is_hidden) return;
    this->tetra_intrude->checkin_edge(edge); // intrusion check with visible edges only

    IVP_DOUBLE rating = -edge->start_point->quad_distance_to(edge->next->start_point); // length
    add_edge_to_min_list(edge,P_HASH_CLASS_PROBLEM,rating);
}

void IVP_Object_Polygon_Tetra::move_edge_to_convex_intrude_hash(IVP_Tri_Edge *edge){
    IVP_Tri_Edge *opp = edge->opposite;
    this->remove_edge_from_min_list(edge);

    if (opp<edge) edge = opp;

    IVP_DOUBLE rating = -edge->start_point->quad_distance_to(edge->next->start_point); // length
    add_edge_to_min_list(edge, P_HASH_CLASS_CONVEX_INTRUDE, rating);
}

void IVP_Object_Polygon_Tetra::move_edge_to_epsilon_hash(IVP_Tri_Edge *edge){
    IVP_Tri_Edge *opp = edge->opposite;
    this->remove_edge_from_min_list(edge);

    this->tetra_intrude->checkout_edge(edge);
    this->tetra_intrude->checkout_edge(edge->opposite);

    if (opp<edge) edge = opp;
    if (edge->triangle->flags.is_hidden) return;
    this->tetra_intrude->checkin_edge(edge); // intrusion check with convex edges only

    IVP_DOUBLE rating = this->rate_tri_edge(edge);
    add_edge_to_min_list(edge,P_HASH_CLASS_EPSILON,rating);
}

void IVP_Object_Polygon_Tetra::move_edge_to_normal_hash(IVP_Tri_Edge *edge){
    this->remove_edge_from_min_list(edge);
    this->tetra_intrude->checkout_edge(edge);
    this->tetra_intrude->checkout_edge(edge->opposite);

    IVP_ASSERT(edge->tmp.gen.concav_flag != -2);
    IVP_Tri_Edge *opp = edge->opposite;
    if (opp<edge) edge = opp;
    if (edge->triangle->flags.is_hidden) return;
    this->tetra_intrude->checkin_edge(edge);
    if (edge->tmp.gen.concav_flag == 0)	return;
    
    IVP_DOUBLE rating = this->rate_tri_edge(edge);
    add_edge_to_min_list(edge,P_HASH_CLASS_NORMAL,rating);
}

void IVP_Object_Polygon_Tetra::add_edge_to_min_list(IVP_Tri_Edge *edge,P_HASH_CLASS hash_class, IVP_DOUBLE rating){
    IVP_ASSERT(edge->tmp.gen.hash_class == P_HASH_CLASS_NONE);
    IVP_Tri_Edge *opp = edge->opposite;
    if (opp<edge) edge = opp;
    IVP_ASSERT(edge->tmp.gen.hash_class == P_HASH_CLASS_NONE);
    min_hash[hash_class]->add((void *)edge,rating);
    edge->tmp.gen.hash_class = hash_class;
}

void IVP_Object_Polygon_Tetra::remove_edge_from_min_list(IVP_Tri_Edge *edge){
    if (edge->tmp.gen.hash_class){
	this->min_hash[edge->tmp.gen.hash_class]->remove((void *)edge);	
	edge->tmp.gen.hash_class = P_HASH_CLASS_NONE;
    }
    edge = edge->opposite;
    if (edge->tmp.gen.hash_class){
	this->min_hash[edge->tmp.gen.hash_class]->remove((void *)edge);	
	edge->tmp.gen.hash_class = P_HASH_CLASS_NONE;
    }
}


void IVP_Object_Polygon_Tetra::hide_triangle(IVP_Triangle *tri)
{
    // prepos: links are perfect
    if (1 || !tri->flags.is_hidden){
	IVP_Tri_Edge *edge = &tri->three_edges[0];
	for (int i=2;i>=0;i--,edge = edge->next){
	    this->remove_edge_from_min_list(edge);
	    this->tetra_intrude->checkout_edge(edge);
	    this->tetra_intrude->checkout_edge(edge->opposite);
	}
    }
    tri->flags.is_hidden = 1;
}

IVP_BOOL IVP_Object_Polygon_Tetra::p_link_edge(IVP_Tri_Edge *edge, IVP_Tri_Edge *neighb)
{
    // prepos: - perfect linked obj
    //         - other_side of edge

    IVP_Tri_Edge *orig_edge_oppo = edge->opposite;
    IVP_Tri_Edge *edge_oth = edge->other_side();
    
    if(!neighb){
	// triangle is open at this side, only linked with
	// triangle->other_side
	edge->opposite = edge_oth;
	edge_oth->opposite = edge;
	edge->behind = edge;
	edge_oth->behind = edge_oth;
	edge->concavity = 12345.6f; // most important: convex
	edge_oth->concavity = edge->concavity;
	return IVP_FALSE;
    }
    
    IVP_Tri_Edge *neighb_opp = neighb->opposite;
    IVP_Tri_Edge *neighb_oth = neighb->other_side();
    IVP_ASSERT(neighb_opp != edge); // questionable; maybe just do a return?
    {
	IVP_ASSERT(neighb_opp != edge); // questionable; maybe just do a return?
	IVP_Tri_Edge *test_edge;
	for (test_edge = edge->next; test_edge != edge;test_edge = test_edge->next){
	    IVP_ASSERT(test_edge != neighb_opp);
	}
    }

    IVP_Tri_Edge *edge_opp = edge->opposite;

    neighb->opposite = edge; 
    neighb_opp->opposite = edge_opp;

    edge->opposite = neighb;
    edge_oth->behind = neighb;
    edge_opp->other_side()->behind = neighb_opp;
    edge_opp->opposite = neighb_opp;

    neighb->opposite = edge;
    neighb_oth->behind = edge;
    neighb_opp->other_side()->behind = edge_opp;
    neighb_opp->opposite = edge_opp;


    // set/recalc concavity infos
    IVP_BOOL retval = IVP_FALSE;
    int flag = this->check_concavity_and_manage(edge, P_CONVEXIFY_STATE_LINK);
    //if (flag <0) retval = IVP_TRUE;
    flag = this->check_concavity_and_manage(orig_edge_oppo, P_CONVEXIFY_STATE_LINK);
    //if (flag <0) retval = IVP_TRUE;
    return retval;
}

int IVP_Object_Polygon_Tetra::link_triangle_couple(
    IVP_Triangle *triangle,
    IVP_Tri_Edge *neighbor_0,
    IVP_Tri_Edge *neighbor_1,
    IVP_Tri_Edge *neighbor_2)
{
    // prepos: triangle internal links,
    // 	        triangle->other_side == another new triangle to be inserted
    //	 	  object has perfect links.
    
    // inserts triangle triangle and its other_side triangle
    // into object. perfect links with neighbours.

    // neighbor_0 will be opposited with triangle->edge etc.
    ivp_u_bool flag;
    flag = p_link_edge(&triangle->three_edges[0], neighbor_0);
    IVP_ASSERT(!flag);
    flag = p_link_edge(triangle->three_edges[0].next, neighbor_1);
    IVP_ASSERT(!flag);
    flag = p_link_edge(triangle->three_edges[0].prev, neighbor_2);
    IVP_ASSERT(!flag);
    this->triangles.insert(triangle);
    this->triangles.insert(triangle->other_side);
    this->make_double_triangle_permanent(triangle);
    return IVP_OK;
}

void p_link_triangle_self(IVP_Triangle *tri){
/* prepos: set other_side */
    int i;
    for (i=0;i<3;i++){
	tri->three_edges[i].triangle = tri;
	tri->three_edges[i].behind = &tri->three_edges[i];
	tri->three_edges[i].opposite = tri->three_edges[i].other_side();
    }
}

IVP_Tri_Edge *IVP_Object_Polygon_Tetra::get_an_edge_with_points(IVP_Poly_Point *p1, IVP_Poly_Point *p2)
{
    IVP_Poly_Point *p[2];
    int i=0;
    if(p1 > p2) i = 1;
    p[i] = p1;
    p[1-i] = p2;

    IVP_Tri_Edge *found_edge = (IVP_Tri_Edge *)this->points_to_edge_hash->find((char *)&p[0]);
    return found_edge;
}


void IVP_Object_Polygon_Tetra::add_edge_into_point_to_edge_hash(IVP_Tri_Edge *edge)
{
    IVP_Poly_Point *p[2], *hp;

    p[0] = edge->start_point;
    p[1] = edge->next->start_point;

    if(p[0]>p[1]){ // swap
	hp = p[0]; p[0] = p[1]; p[1] = hp;
    }
    if (this->points_to_edge_hash->find((char *)&p[0]) != 0) {
	return;			// already in hash
    }
    this->points_to_edge_hash->add((char *)&p[0], (void *)edge);
}


IVP_Triangle::IVP_Triangle()
{
    next = prev = other_side = NULL;
    pierced_triangle = NULL;
    flags.is_terminal = 0;
    flags.is_hidden = 0;
    ivp_surface = NULL;
    memset((char*)(&three_edges[0]), 0, 3 * sizeof(IVP_Tri_Edge));
}

IVP_Triangle::~IVP_Triangle()
{
}

IVP_Triangle *IVP_Object_Polygon_Tetra::generate_double_triangle(IVP_Poly_Point *p1, IVP_Poly_Point *p2, IVP_Poly_Point *p3)
{
    IVP_Triangle *tri_a = new IVP_Triangle();
    IVP_Triangle *i_tri_a = new IVP_Triangle();

    // provide new edges
    IVP_Tri_Edge *e0 = &tri_a->three_edges[0];
    IVP_Tri_Edge *e1 = &tri_a->three_edges[1];
    IVP_Tri_Edge *e2 = &tri_a->three_edges[2];

    IVP_Tri_Edge *i_e0 = &i_tri_a->three_edges[0];
    IVP_Tri_Edge *i_e1 = &i_tri_a->three_edges[1];
    IVP_Tri_Edge *i_e2 = &i_tri_a->three_edges[2];

    // provide some links in new elements
    e0->next = e1; e0->prev = e2; e0->start_point = p1; e0->triangle = tri_a;
    e1->next = e2; e1->prev = e0; e1->start_point = p2; e1->triangle = tri_a;
    e2->next = e0; e2->prev = e1; e2->start_point = p3; e2->triangle = tri_a;

    i_e0->next = i_e2; i_e0->prev = i_e1; i_e0->start_point = p2; i_e0->triangle = i_tri_a;
    i_e1->next = i_e0; i_e1->prev = i_e2; i_e1->start_point = p3; i_e1->triangle = i_tri_a;
    i_e2->next = i_e1; i_e2->prev = i_e0; i_e2->start_point = p1; i_e2->triangle = i_tri_a;

    tri_a->other_side = i_tri_a; i_tri_a->other_side = tri_a;
    
    p_link_triangle_self(tri_a); p_link_triangle_self(i_tri_a);        

    tri_a->calc_hesse();
    i_tri_a->calc_hesse();
    int i;
    IVP_Tri_Edge *e;

    for (i=0,e=e0;i<3;e=e->next,i++){
	e->tmp.gen.tetra_point = e->start_point->tmp.tetra_point;
    }    
    for (i=0,e=i_e0;i<3;e=e->next,i++){
	e->tmp.gen.tetra_point = e->start_point->tmp.tetra_point;
    }
    return tri_a;
}

void IVP_Object_Polygon_Tetra::make_double_triangle_permanent(IVP_Triangle *triangle)
{
    int i;
    IVP_Tri_Edge *e;
    for (i=0,e= &triangle->three_edges[0];i<3;e=e->next,i++){
	this->add_edge_into_point_to_edge_hash(e);
    }
    
}

IVP_DOUBLE p_calc_min_intrude_dist(IVP_Triangle *tri, IVP_Intrusion_Status *stat,
			       IVP_DOUBLE start_min)
{
    IVP_Intrusion_Included_Points *i_point;
    IVP_DOUBLE min = start_min;
    for(i_point=stat->intruded_points; i_point; i_point=i_point->next){
	IVP_DOUBLE dist = tri->tmp.gen.hesse.get_dist(i_point->tetra_point->opoint);
	if(dist<min) min=dist;
    }
    IVP_Intrusion_Intersection *intersect;
    for(intersect=stat->intersections; intersect; intersect=intersect->next){
	if (intersect->type != IVP_INTRUSION_CHECK_OVERLAP){
	    IVP_DOUBLE dist = tri->tmp.gen.hesse.get_dist(&intersect->intersect_point);
	    if(dist<min) min=dist;
	}
    }
    return min;
}

void IVP_Object_Polygon_Tetra::calc_extrusion_point(const IVP_Tri_Edge *edge, IVP_U_Point *point_out){
    // assert IVP_Inline_Math::fabsd(concavity) > 8 * P_Pop_Eps

    IVP_U_Point mid_of_line;
    IVP_DOUBLE eps = P_Pop_Eps * 1.1f;
    IVP_Tri_Edge *oppo = edge->opposite; // 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 mpo;		// mid point of tri_a, P_Pop_Eps dist to tria
    mpo.add_multiple(&mid_of_line, &edge->triangle->tmp.gen.hesse, eps);

    IVP_U_Plain *oppo_ebene;
    {
	IVP_U_Point p0,p1;
	p0.add_multiple(oppo->start_point, &oppo->triangle->tmp.gen.hesse,eps);
	p1.add_multiple(oppo->next->start_point, &oppo->triangle->tmp.gen.hesse,eps);
	oppo_ebene = new IVP_U_Plain(&p0,&p1,oppo->next->next->start_point);
    }
    IVP_U_Straight straight;
    IVP_U_Point svec;
    svec.subtract(&mpo, edge->prev->start_point);
	
    straight.set(edge->prev->start_point, &svec);
    ((IVP_U_Hesse *)oppo_ebene)->calc_intersect_with(&straight,point_out);
    delete oppo_ebene;
}