ivp_gridbuild_array.cxx

hl2 source code. Do not use it illegal.

// -1 , -2 are reference points
IVP_Compact_Poly_Point *IVP_GridBuilder_Array::get_point_at_strip_pos(int pos){
    int point_index = c_point_to_point_index[pos+2];
    return &c_points[point_index];
}



IVP_Compact_Ledge *IVP_GridBuilder_Array::convert_convex_stripe_to_compact_ledge_fast(
						int strip_points[],		int n_points,
						IVP_U_Float_Point ref_point[2],
						IVP_BOOL is_right_starter)
{
    ///// Convert a convex strip into a compact ledge
    IVP_ASSERT(n_points >=4);


    //// INITS
    //// INITS
    int num_triangles = 4 + 2*(n_points-2);
    this->triangle_count = 0;


    // get memory for Ledge Header, Triangles and Points
    int mem_size = 	sizeof(IVP_Compact_Ledge) +	num_triangles * sizeof(IVP_Compact_Triangle);

    this->c_ledge = (IVP_Compact_Ledge *)mm->get_memc( mem_size);
    IVP_ASSERT ( (int(c_ledge) & 15) == 0);



    { // set point arrays
	// search the minimum point index and install points
	int min = c_point_to_point_index[0] = install_point(&ref_point[0]);
	int max = c_point_to_point_index[1] = install_point(&ref_point[1]);
	if (min > max){ int h = max; max = min; min = h; }; // exchange points
	for (int i=n_points-1;i>=0;i--){
	    int index = install_grid_point(strip_points[i]);
	    if (index < min) min = index;
	    if (index > max) max = index;
	    c_point_to_point_index[i+2] = index;
	}
	// shift start so min gets zero
	for (int j = n_points +1; j>=0; j--){
	    c_point_to_point_index[j] -= min;
	}
	IVP_ASSERT(max - min + 1 < n_cols * 4 + 1);
	this->c_points = &compact_poly_point_buffer[min];
	c_ledge->set_offset_ledge_points( (uchar *)c_points - (uchar *)c_ledge ); // byte offset from 'this' to (ledge) point array
    }
    
    c_ledge->set_is_compact( IVP_FALSE);
    c_ledge->set_size(mem_size);		// if size < 0 than compact_edge is not compact and shares point arrays
    c_ledge->n_triangles = num_triangles;
    c_ledge->has_chilren_flag = IVP_FALSE;


    int cp = 2; // init current point index counter
    int end_point_idx = n_points-1; // used to determine completion
    int last_opp = 0; // used to link last with first triangle
    int left_off, mid_off, right_off; // used to override the upper edge opposite indices

    //// START TRIANGLES
    //// START TRIANGLES
    {
	IVP_U_Hesse hesse;
	hesse.calc_hesse(	get_point_at_strip_pos(-1), get_point_at_strip_pos(-2), get_point_at_strip_pos(0));
	IVP_DOUBLE dist = hesse.get_dist( get_point_at_strip_pos(1) );

	if(is_right_starter){
	    /// right starter

	    // figure out the convex way to connect start edge with ref points
	    if(dist>0.0f){	// sign.
		// make triangles
		this->add_triangle(3, 2, 0,		8, 5, 19);
		this->add_triangle(2, 1, 0,		10, -1000, -5); // -1000 is replaced later
		left_off = -19;
		mid_off  = -8;
		right_off= -10;
	    }else{
		// make triangles
		this->add_triangle(3, 2, 1,		8, 13, 2);
		this->add_triangle(3, 1, 0,		-2, -1000, 15); // -1000 is replaced later
		left_off = -15;
		mid_off  = -8;
		right_off= -13;
	    }

	    // skip to regular lower right proc
	    goto lower_right;
	}else{
	    /// left starter
	    // figure out the convex way to connect start edge with ref points
	    if(dist<0.0f){	// sign.
		// make triangles p1,r0,p0 and p1,r1,r0
		this->add_triangle(3, 0, 2,   6, 12, 6);
		this->add_triangle(3, 1, 0,   18, -1000,-6); // -1000 is replaced later
		left_off = -12;
		mid_off  = -6;
		right_off= -18;
	    }else{
		// make triangles p0,p1,r1 and p0,r1,r0
		this->add_triangle(2, 3, 1,    8, 21, 2);
		this->add_triangle(2, 1, 0,    -2, -1000, 7); // -1000 is replaced later
		left_off = -7;
		mid_off  = -8;
		right_off= -21;
	    }
	    // continue with regular upper left proc
	}
    }
    //// REGULAR LOOP
    //// REGULAR LOOP
    while(1){
	    /// upper left plus left neighbor
	    if(cp<end_point_idx){
		    // regular
		    this->add_triangle(cp+1, cp, cp+2, 	   mid_off, 3, 6);
		    mid_off = -6;
		    this->add_triangle(cp+2, cp, 0, 	   -3, left_off, 15);
		    left_off = -15;
		    cp++;
	    }else{
		    /// last one

		    // figure out the convex way to connect last edge with ref points
		    IVP_U_Hesse hesse;
		    hesse.calc_hesse(get_point_at_strip_pos(-2), get_point_at_strip_pos(-1), get_point_at_strip_pos(cp+1-2));
		    IVP_DOUBLE dist = hesse.get_dist(get_point_at_strip_pos(cp /*+2-2*/) );
		    if(dist<0.0f){ // sign.
			    const IVP_Compact_Triangle *tri = &c_ledge->get_first_triangle()[this->triangle_count-1];
			    const IVP_Compact_Edge *edge = tri->get_edge(1);
			    insert_opposite_index(edge,13);

			    this->add_triangle(cp+1, cp,   cp+2,   mid_off, 3, 6);
			    this->add_triangle(cp+2, cp,   0, 	   -3, left_off, 7);
			    this->add_triangle(cp+1, cp+2, 1, 	   -6, 3, -13);

			    last_opp = -1-(num_triangles-2)*4;
			    this->add_triangle(1,    cp+2, 0,      -3, -7, last_opp);
		    }else{
			    const IVP_Compact_Triangle *tri = &c_ledge->get_first_triangle()[this->triangle_count-1];
			    const IVP_Compact_Edge *edge = tri->get_edge(1);
			    insert_opposite_index(edge,17);

			    this->add_triangle(cp+1, cp, cp+2,   mid_off, 3, 6);
			    this->add_triangle(cp+2, cp,   0, 	   -3, left_off, 3);
			    this->add_triangle(cp+1, cp+2, 0, 	   -6, -3, 2);

			    last_opp = -(num_triangles-2)*4;
			    this->add_triangle(cp+1, 0,	   1, 	   -2, last_opp, -17);
		    }
		    break;
	    }
lower_right:
		/// lower right plus right neighbor
		if(cp<end_point_idx){
			// regular
			this->add_triangle(cp, cp+1, cp+2, 	   mid_off, 7, 2);
			mid_off = -7;
			this->add_triangle(cp, cp+2, 1, 	   -2, 17, right_off);
			right_off = -17;
			cp++;
		}else{
			/// last one
			// figure out the convex way to connect last edge with ref points
			IVP_U_Hesse hesse;
			hesse.calc_hesse(get_point_at_strip_pos(-2), get_point_at_strip_pos(-1), get_point_at_strip_pos(cp+1-2));
			IVP_DOUBLE dist = hesse.get_dist(get_point_at_strip_pos(cp /*+2-2*/ ));
			if(dist>0.0f){ // sign.
				const IVP_Compact_Triangle *tri = &c_ledge->get_first_triangle()[this->triangle_count-1];
				const IVP_Compact_Edge *edge = tri->get_edge(2);
				insert_opposite_index(edge, 15);

				this->add_triangle(cp,   cp+1, cp+2,	mid_off, 7, 2);
				this->add_triangle(cp,   cp+2, 1,		-2, 5, right_off);
				this->add_triangle(cp+2, cp+1, 1,		-7, 3, -5);

				last_opp = -1-(num_triangles-2)*4;
				this->add_triangle(1,    cp+1, 0,		-3, -15, last_opp);
			}else{
				IVP_Compact_Triangle *tri = &c_ledge->get_first_triangle()[this->triangle_count-1];
				const IVP_Compact_Edge *edge = tri->get_edge(2);
				insert_opposite_index(edge, 11);

				this->add_triangle(cp,   cp+1, cp+2,	mid_off, 7, 2);
				this->add_triangle(cp,   cp+2, 1,		-2, 9, right_off);
				this->add_triangle(cp+2, cp+1, 0,		-7, -11, 2);

				last_opp = -(num_triangles-2)*4;
				this->add_triangle(cp+2, 0,    1,		-2, last_opp, -9);
			}
			break;
		}
	} // loop

	// link last with first triangle
	{
		IVP_ASSERT(last_opp);
		const IVP_Compact_Triangle *tri = &this->c_ledge->get_first_triangle()[1];
		IVP_ASSERT(tri->get_tri_index() == 1);
		const IVP_Compact_Edge *link_edge = tri->get_edge(1);
		insert_opposite_index(link_edge, -last_opp);
	}

	//// INSERT PIERCING INFO
	//// INSERT PIERCING INFO
	{
		// simple, square worst case (unlikely)
		int found_cnt = 0;
		IVP_DOUBLE take_it_eps = 0.01f;

		const IVP_Compact_Triangle *tri = this->c_ledge->get_first_triangle();
		for(int t=num_triangles-1; t>=0; t--, tri = tri->get_next_tri()){
			IVP_U_Point norm_vec;
			norm_vec.inline_set_vert_to_area_defined_by_three_points(
				tri->get_edge(0)->get_start_point(c_ledge),
				tri->get_edge(1)->get_start_point(c_ledge),
				tri->get_edge(2)->get_start_point(c_ledge) );

			IVP_DOUBLE max_h = -1.0f;
			int	max_tri_num = -1;
			const IVP_Compact_Triangle *tri2 = this->c_ledge->get_first_triangle();
			for(int u=num_triangles-1; u>=0; u--, tri2 = tri2->get_next_tri()){
				if(t==u) continue;
				IVP_U_Point norm_vec2;
				norm_vec2.inline_set_vert_to_area_defined_by_three_points(
					tri2->get_edge(0)->get_start_point(c_ledge),
					tri2->get_edge(1)->get_start_point(c_ledge),
					tri2->get_edge(2)->get_start_point(c_ledge) );

				// check if the normal are looking in different directions 
				IVP_DOUBLE h = norm_vec.dot_product(&norm_vec2);
				if(h > take_it_eps){
					// found
					((IVP_Compact_Triangle *)tri)->set_pierce_index(u);
					found_cnt++;
					goto found_a_tri; // sorry for gotos, want to avoid extra if's
				}else{
					if(h>max_h){
						max_h = h;
						max_tri_num = u;
					}
				}
			} // for u
			IVP_ASSERT(max_tri_num >= 0);
			((IVP_Compact_Triangle *)tri)->set_pierce_index(max_tri_num);
			found_cnt++;				
found_a_tri:
			;
		} // for t
		IVP_ASSERT(found_cnt == num_triangles);
	}

#ifdef DEBUG
	IVP_Compact_Ledge_Solver::check_ledge(c_ledge);
#endif

	return this->c_ledge;
}

/* scan each strip for convex parts, skip flat areas */
void IVP_GridBuilder_Array::convert_strip_to_compact_ledges(int row, IVP_U_Vector<IVP_Compact_Ledge> *ledges){

    int strip_field_offset[IVP_GRID_MAX_COLUMNS * 2];		// jumps alternately between the two rows of points defining row
    int dest_stripe[IVP_GRID_MAX_COLUMNS * 2];		// the compacted strip to be later translated into compact ledge

    {	// build the stripe
	int low = row * n_cols;
	int high = low + n_cols;
	int d = 0;
	for (int c = 0; c < n_cols; c++){
	    strip_field_offset[d] = low++;
	    strip_field_offset[d+1] = high++;
	    d+=2;
	}
    }	

    int strip_size = n_cols + n_cols;

    int start_pos; // start of stripe
    int end_pos; // end of convex stripe
    int dest_index;
	

    for (start_pos = 0; start_pos< strip_size-2; start_pos = end_pos-1){
	dest_index = 0;
	int first_point = start_pos;
	dest_stripe[dest_index] = strip_field_offset[start_pos];	// insert first line
	dest_stripe[dest_index+1] = strip_field_offset[start_pos+1];
	dest_index+=2;
	start_pos+=2;
	// search end pos

	int ep;		// will be the first point (behind start_pos) which will be needed
	check_flat_triangles:
	for ( ep = start_pos; ep < strip_size-3; ep+=2){