ivp_object_polygon_tetra.cxx

hl2 source code. Do not use it illegal.

	    P_Sur_2D_Triangle *triang = new P_Sur_2D_Triangle(point_a->point_num,
							      point_c->point_num,
							      point_b->point_num);
	    this->triangles.insert(triang);
#ifdef SUR_DEBUG	    
	    printf("Triangle %d: %d, %d, %d\n",triangle_count,
		   point_a->point_num, point_c->point_num, point_b->point_num);
#endif
	    triangle_count++;
	    
	    // delete used lines      , maybe faster with hash
	    this->lines.remove(td_base_line);
	    
#ifdef SUR_DEBUG
	    printf("    line removed: %d, %d\n", td_base_line->start_point->point_num,
		   td_base_line->end_point->point_num);
#endif		    
	    P_Sur_2D_Line *td_ident_line;
	    P_Sur_2D_Line *td_ident_line_next;
	    int ca_removed = 0; // flags
	    int bc_removed = 0;
	    P_DELETE(td_base_line);
	    
	    for(td_ident_line=this->lines.first; td_ident_line; td_ident_line=td_ident_line_next){
		td_ident_line_next = td_ident_line->next;
		// if( td_ident_line->has_points(point_c, point_a) && td_ident_line->has_points(point_c, point_b) ){
		//    printf("scheibenkleister!\n");
		// }
		if( td_ident_line->has_points(point_c, point_a) ){
		    this->lines.remove(td_ident_line);
#ifdef SUR_DEBUG
		    printf("    line removed: %d, %d\n", td_ident_line->start_point->point_num,
			   td_ident_line->end_point->point_num);
#endif		    
		    ca_removed = 1;
		    P_DELETE(td_ident_line);
		}
		if( td_ident_line && td_ident_line->has_points(point_c, point_b) ){
		    this->lines.remove(td_ident_line);
#ifdef SUR_DEBUG
		    printf("    line removed: %d, %d\n", td_ident_line->start_point->point_num,
			   td_ident_line->end_point->point_num);
#endif		    
		    bc_removed = 1;
		    P_DELETE(td_ident_line);
		}
	    }

	    // insert remaining triangle as new lines
	    if(!ca_removed){
		P_Sur_2D_Line *td_new_line = new P_Sur_2D_Line(point_a, point_c);
		this->lines.insert(td_new_line); // append is better
	    }
	    if(!bc_removed){
		P_Sur_2D_Line *td_new_line = new P_Sur_2D_Line(point_c, point_b);
		this->lines.insert(td_new_line); // append is better
	    }

	    // proceed to next base line for next triangle
	    break;
	} // end for all points
    } // end for all base_lines

    // clean up
    P_DELETE(td_ca_line);
    P_DELETE(td_bc_line);

    // lines and points are no longer needed
    int i;
    for(i=this->orig_surface->n_lines-1; i>=0; --i){
//	delete this->line_array[i];
	delete this->point_array[i];
    }
    
    if(wrong_flag){
	return "something went wrong in calc_triangle_representation! break...\n";
    }
    return IVP_NO_ERROR;
}

void ivp_check_for_opposite(IVP_Hash *hash, IVP_Poly_Point *p0, IVP_Poly_Point *p1, IVP_Tri_Edge *edge)
{
    IVP_Poly_Point *hashval[2];
    if(p0<p1){
	hashval[0] = p0;
	hashval[1] = p1;
    }else{
	hashval[0] = p1;
	hashval[1] = p0;
    }
    IVP_Tri_Edge *edge2;
    edge2 = (IVP_Tri_Edge *)hash->find((char *)(&hashval[0]));
    if(!edge2){
	// add
	hash->add((char *)(&hashval[0]), (void *)edge);	
    }else{
	// opposites now known -> add
	edge->opposite = edge2;
	edge2->opposite = edge;	
    }
}

IVP_Object_Polygon_Tetra::IVP_Object_Polygon_Tetra(IVP_Template_Polygon *i_temp_pop)
{
    P_MEM_CLEAR(this);
    this->template_polygon = i_temp_pop;

    this->n_points = i_temp_pop->n_points;
    this->points = (IVP_Poly_Point *)p_calloc(sizeof(IVP_Poly_Point), this->n_points);
    int i;
    for (i=0;i<this->n_points;i++){
	IVP_U_Point *p = &i_temp_pop->points[i];
	this->points[i].set( p );
	this->points[i].l_tetras = this;
    }


    this->n_surfaces = i_temp_pop->n_surfaces;
    this->surfaces = (IVP_Poly_Surface *)p_calloc(sizeof(IVP_Poly_Surface), this->n_surfaces);
    for (i=0;i<this->n_surfaces;i++){
	this->surfaces[i].set( &i_temp_pop->surfaces[i], this );
    }
    
    template_polygon = NULL;
}

void IVP_Poly_Surface::set(IVP_Template_Surface *templ_sur,
			  IVP_Object_Polygon_Tetra *i_tetras)
{
    this->tetras = i_tetras;
    IVP_USE(templ_sur);
}

int IVP_Poly_Surface::get_surface_index(){
    return this - tetras->surfaces;
}


IVP_Object_Polygon_Tetra::~IVP_Object_Polygon_Tetra()
{
    this->free_triangles();
    P_FREE(this->surfaces);
    P_FREE(this->points);
}


IVP_ERROR_STRING IVP_Object_Polygon_Tetra::make_triangles()
{
    int n_edges;
    IVP_Template_Surface *sur;
    IVP_Poly_Point *po, *po2, *po3;
    IVP_Triangle *tri;
    IVP_Hash *hash;
    IVP_Template_Polygon *templ = template_polygon;
    int num_of_edges;
    
    n_edges = 0;
    num_of_edges = 6 * (templ->n_points-2); // accurately calculated
    hash = new IVP_Hash(num_of_edges/*size*/, 8 /*keylen*/, 0/*notfound*/);
    {
	int i;    
	IVP_Tri_Edge *edge;
	for(i=templ->n_surfaces-1, sur=&templ->surfaces[0]; i>=0; i--, sur++){
	    // split plane into triangles and insert them
	    P_Sur_2D *td_sur = new P_Sur_2D(this,sur);
	    IVP_ERROR_STRING error = td_sur->calc_line_representation();
	    if(error){
		printf("make_triangles:calc_line_representation: %s\n", error);
		return "No 2d representation";
	    }
	    error = td_sur->calc_triangle_representation();
	    if(error){
		printf("make_triangles:calc_triangle_representation: %s\n", error);
		return "no 3d representation";
	    }
	    
	    P_Sur_2D_Triangle *td_tri;
	    
	    for(td_tri=td_sur->triangles.first; td_tri; td_tri=td_tri->next){
		po = &this->points[td_tri->point_nums[2]];
		po2 = &this->points[td_tri->point_nums[1]];
		po3 = &this->points[td_tri->point_nums[0]];

		// clockwise ?
		{
		    IVP_U_Point *hesse = &sur->normal;
		    IVP_U_Point v0, v1;
		    v0.subtract(po2, po);
		    v1.subtract(po3, po);
		    IVP_U_Point cross;
		    cross.calc_cross_product(&v0, &v1);
		    IVP_DOUBLE scal = cross.dot_product(hesse);
		    if(scal<0.0f){
			IVP_Poly_Point *h=po3;
			po3 = po2;
			po2 = h;
			//printf("Points swapped for clockwise.\n");		    
		    }
		}
		
		// make physical triangle
		tri = new IVP_Triangle();
		this->triangles.insert(tri);
		tri->flags.is_terminal = 1; // might be changed later on
		int sur_index = sur->get_surface_index();
		tri->ivp_surface = &surfaces[sur_index];
		tri->flags.is_hidden = 0;
		
		// 3 edges in uzs
		edge = &tri->three_edges[0];
		n_edges += 3;
		
		// 1. edge
//		tri->edge = edge;
		edge->start_point = po;
		edge->triangle = tri;
		edge->next = edge+1;
		edge->prev = edge+2;
		edge->behind = NULL; // terminal!
		ivp_check_for_opposite(hash, po, po2, edge);
		
		// 2. edge
		edge++;
		edge->start_point = po2;
		edge->triangle = tri;
		edge->next = edge+1;
		edge->prev = edge-1;
		edge->behind = NULL; // terminal!
		ivp_check_for_opposite(hash, po2, po3, edge);
		
		// 3. edge
		edge++;
		edge->start_point = po3;
		edge->triangle = tri;
		edge->next = edge-2;
		edge->prev = edge-1;
		edge->behind = NULL; // terminal!
		ivp_check_for_opposite(hash, po3, po, edge);
	    }
	    P_DELETE(td_sur);
	}
	P_DELETE(hash);
    }
//	this->check_konsistency_of_triangles();

	IVP_Triangle *otri;
	for(otri=this->triangles.first; otri; otri=otri->next){
	    // make physical triangle - backside
	    tri = new IVP_Triangle();
	    this->triangles.insert(tri);
	    tri->flags.is_terminal = 1;
	    tri->ivp_surface = NULL;
	    tri->flags.is_hidden = 1;
	    tri->other_side = otri;
	    otri->other_side = tri;

	    n_edges += 3;

	    int i;
	    for(i=2; i>=0; i--){
		IVP_Tri_Edge *edge = &tri->three_edges[i];
		edge->start_point = otri->three_edges[i].next->start_point;
		edge->triangle = tri;
		edge->next = &tri->three_edges[(i+2)%3];
		edge->prev = &tri->three_edges[(i+1)%3];
		edge->behind = otri->three_edges[i].opposite;
		IVP_Tri_Edge *opp = edge->other_side()->opposite->other_side();
		if(opp){
		    edge->opposite = opp;
		    opp->opposite = edge;
		}
		otri->three_edges[i].opposite->behind = &tri->three_edges[i];
	    }
	    for(i=2; i>=0; i--){
		IVP_Tri_Edge *edge = &tri->three_edges[i];
		this->add_edge_into_point_to_edge_hash(edge);
	    }
	}
	return NULL;
	// this->check_konsistency_of_triangles();
}


IVP_ERROR_STRING IVP_Object_Polygon_Tetra::final_convexify_check()
{
    // checks wether the concavity of edges is correctly defined
    IVP_ERROR_STRING error_flag = 0;
    
    IVP_Object_Polygon_Tetra *ph = this;
    IVP_Triangle *tri;
    int i;
    int n_triangles_check = 0;
    for(tri=ph->triangles.first; tri; tri=tri->next){
	n_triangles_check++;

        // check triangle features
	// ...
	
	// check edges
	IVP_Tri_Edge *e = &tri->three_edges[0];
	for(i=0; i<3; i++, e=e->next){
	    int conc_flag = e->check_concavity(e->opposite);
	    if(conc_flag == -2){
		error_flag = "error";
		printf("convex_test: tri->edge: tmp.gen.concav_flag == -2 (partly overlapping)"); tri->print("\n");	    		
	    }
	    if(conc_flag == -1){
		error_flag = "error";
		printf("convex_test: tri->edge: tmp.gen.concav_flag == -1 (identic)"); tri->print("\n");	    		
	    }
	    if(conc_flag == 0){
		// convex: are neighbour and myself unhidden?
		if(!tri->flags.is_terminal && (e->opposite->triangle->flags.is_hidden ||
		   e->triangle->flags.is_hidden)){
		    printf("convex_test:  warning edge is convex, but neighbours are hidden."); tri->print("\n");
		}		
	    }
	    if(conc_flag == 1){
		// concav: are neighbour and myself hidden?
		if(!e->opposite->triangle->flags.is_hidden ||
		   !e->triangle->flags.is_hidden){
		    if (e->concavity < - P_POP_SURFACE_CONVEX_BLUR){
			printf("convex_test:  edge is concav %f, but neighbours are unhidden.",e->concavity); tri->print("\n");
			error_flag = "error";
		    }
		}		
	    }
	}
    }
    if(!error_flag){
	//printf("final_convexify_check: OK: %i triangles, %i extrapoints.\n", n_triangles_check, n_extra_points);
    }else{
	printf("final_convexify_check: ERRORS: %i triangles, %i extrapoints.\n", n_triangles_check, n_extra_points);
    }
    return error_flag;
}


IVP_ERROR_STRING IVP_Object_Polygon_Tetra::check_konsistency_of_triangles()
{
    // tests consistency of object's physical elements

    IVP_ERROR_STRING error_flag = 0;
    
    IVP_Object_Polygon_Tetra *ph = this;
    IVP_Triangle *tri;
    IVP_Tri_Edge *edge;
    int i;
    int n_triangles_check = 0;
    for(tri=ph->triangles.first; tri; tri=tri->next){
	n_triangles_check++;

	if(tri != tri->other_side->other_side){
		error_flag = "error";
		printf("physic_test: tri != tri->other_side->other_side in triangle "); tri->print("\n");	    
	}
	if( (tri->three_edges[0].next != &tri->three_edges[1] ||
	     tri->three_edges[1].next != &tri->three_edges[2] ||
	     tri->three_edges[2].next != &tri->three_edges[0] ) &&

	    (tri->three_edges[0].prev != &tri->three_edges[1] ||
	     tri->three_edges[1].prev != &tri->three_edges[2] ||
	     tri->three_edges[2].prev != &tri->three_edges[0] )
	    ){
		error_flag = "error";
		printf("physic_test: edges do not properly form a ring in triangle "); tri->print("\n");
	}
	if(tri->calc_areasize() < 1E-6f){
		error_flag = "error";
		printf("pysic_test: tri->calc_areasize() < 1E-6f in triangle: %g", tri->calc_areasize()); tri->print("\n");	    	    
	}

	// check tetraeder, if hidden and
	// check consistency of hidden flag in a tetraeder
	// (tetraeder -> all hidden, no tetraeder -> all unhidden)
	IVP_Tri_Edge *e = &tri->three_edges[0];
	if(tri->flags.is_hidden){
	    // check wether the neighbors do form a tetraeder
	    if( !tri->flags.is_terminal && ( (e->opposite->prev->start_point != e->next->opposite->prev->start_point)||
		(e->opposite->prev->start_point != e->prev->opposite->prev->start_point))   )
	    {
		error_flag = "error";
		printf("physic_test:  triangle is hidden, but neighbours don't form a tetraeder."); tri->print("\n");		
	    }
		// are all triangles inside this tetraeder hidden?
	    if(!(e->opposite->triangle->flags.is_hidden &&
	       e->next->opposite->triangle->flags.is_hidden &&
	       e->prev->opposite->triangle->flags.is_hidden)){
		error_flag = "error";
		printf("physic_test:  triangle is hidden, but not all neighbours are hidden."); tri->print("\n");
	    }
	}else{
	    if( e->opposite->triangle->flags.is_hidden ||
	        e->next->opposite->triangle->flags.is_hidden ||
		e->prev->opposite->triangle->flags.is_hidden){
		error_flag = "error";
		printf("physic_test:  triangle is not hidden, but a neighbour is hidden."); tri->print("\n");
	    }
	}

	
	// check edges
	edge = &tri->three_edges[0];
	for(i=0; i<3; i++, edge=edge->next){

	    // check if any hidden edge is in any hash
	    if(tri->flags.is_hidden && edge->tmp.gen.hash_class){
		error_flag = "error";
		printf("physic_test: tri->is_hidden && in hash"); tri->print("\n");
	    }
	    
	    if(edge->opposite->opposite != edge){
		error_flag = "error";
		printf("physic_test: edge->opposite->opposite != edge in triangle "); edge->print("\n");
	    }
	    if(edge->start_point != edge->opposite->next->start_point){
		error_flag = "error";
		printf("physic_test: edge->start_point != edge->opposite->next->startpoint in triangle "); edge->print("\n");
	    }