ivp_gridbuild_array.cxx

hl2 source code. Do not use it illegal.

	    int p;
	    // check for at least three consequtive parallel triangles
	    for ( p = ep; p< ep+3 && p < strip_size-1 ; p++){
		IVP_DOUBLE diff = height_field [ strip_field_offset[p+0] ] + height_field [ strip_field_offset[p-1] ] -
				      height_field [ strip_field_offset[p-2] ] - height_field [ strip_field_offset[p+1] ];
		if (diff < 0.0f || diff > 1e-3f){
		    p = -1;
		    break;
		}
	    }
	    if (p == -1)	break; // no three flat triangles found
	}
	// now ep is the first point needed
	dest_stripe[dest_index++] = strip_field_offset[ep];	// finalize triangle

	if ( ep < strip_size-1 ){	// check the next triangle for convex piece
	    IVP_DOUBLE diff = height_field [ strip_field_offset[ep+0] ] + height_field [ strip_field_offset[ep-1] ] -
				      height_field [ strip_field_offset[ep-2] ] - height_field [ strip_field_offset[ep+1] ];
	    if (diff >= 0.0f){		// convex edge
		start_pos = ep+1;
		goto check_flat_triangles;
	    }
	}
	end_pos = ep;	// includes ep
	IVP_Compact_Ledge *cl;

	while(1){
	    if ( dest_index == 3){
		cl=convert_convex_triangle_to_compact_ledge( &dest_stripe[0]);
		break;
	    }
	    IVP_BOOL is_right_starter;
	    if ((strip_field_offset[first_point] < strip_field_offset[first_point+1]) ^ (is_left_handed == IVP_TRUE)){
		is_right_starter = IVP_FALSE;
	    }else{
		is_right_starter = IVP_TRUE;
	    }
	    
	    if (dest_index == 4){
		cl = convert_convex_square_to_compact_ledge( &dest_stripe[0], is_right_starter);
		break;
	    }
	    { //else
		IVP_U_Float_Point ref_points[2];
		{ // search for minimum value
		    int p0a_index = dest_stripe[0];
		    int p1a_index = dest_stripe[1];
		    int p0b_index = dest_stripe[(dest_index-1)& ~1];
		    int p1b_index = dest_stripe[((dest_index-2)& ~1) +1];

		    IVP_U_Float_Point *p0a = &height_points[p0a_index];
		    IVP_U_Float_Point *p0b = &height_points[p0b_index];
		    IVP_U_Float_Point *p1a = &height_points[p1a_index];
		    IVP_U_Float_Point *p1b = &height_points[p1b_index];

		    ref_points[0].set(p0a);
		    ref_points[1].set(p1a);
		    IVP_FLOAT col_pos = 0.5f * (p0a->k[ templ->column_info.maps_to ] + p0b->k[ templ->column_info.maps_to ]);
		    ref_points[0].k[ templ->column_info.maps_to ] = col_pos;
		    ref_points[1].k[ templ->column_info.maps_to ] = col_pos;

		    IVP_FLOAT dz = (templ->height_invert_axis)? -1.0f: 1.0f;
		    // search min value of z axis
		    IVP_FLOAT minz, z;
		    minz = p0a->k[ templ->height_maps_to ] * dz;
		       z = p0b->k[ templ->height_maps_to ] * dz; if (z < minz) minz=z;
		       z = p1a->k[ templ->height_maps_to ] * dz; if (z < minz) minz=z;
		       z = p1b->k[ templ->height_maps_to ] * dz; if (z < minz) minz=z;
		    minz -= templ->grid_field_size;
		    minz *= dz;
		    ref_points[0].k[ templ->height_maps_to ] = minz;
		    ref_points[1].k[ templ->height_maps_to ] = minz;
		}

		if(is_right_starter){
		    IVP_U_Point hp;
		    hp.set(&ref_points[0]);
		    ref_points[0].set(&ref_points[1]);
		    ref_points[1].set(&hp);
		}

		cl=convert_convex_stripe_to_compact_ledge_fast( &dest_stripe[0], dest_index, ref_points, is_right_starter );
#ifdef DEBUG
		IVP_Compact_Ledge_Solver::check_ledge(cl);
#endif
		break;
	    }
	    break;
	}
	int ledge_index = ledges->len();
	ledges->add(cl);
	// fill in the reference indizes
	for ( int p = first_point; p < ep-1 /* == end_pos-1*/; p++){
	    int a_offset = strip_field_offset[p];
	    int b_offset = strip_field_offset[p+1];
	    if (a_offset < b_offset) {	// forward strip
		ledge_reference_field[a_offset].compact_ledge_index[0] = ledge_index;
	    }else{			// backward
		ledge_reference_field[b_offset-1].compact_ledge_index[1] = ledge_index;
	    }
	}
    }
}


/* split the array into strips */
void IVP_GridBuilder_Array::convert_array_to_compact_ledges( const IVP_Template_Compact_Grid *gp, IVP_U_Vector<IVP_Compact_Ledge> *ledges){

    IVP_U_Matrix m_object_f_grid;
    {
	IVP_U_Point col_axle; col_axle.set_to_zero();
	IVP_U_Point row_axle; row_axle.set_to_zero();
	IVP_U_Point h_axle;   h_axle.set_to_zero();

	IVP_DOUBLE dx = (gp->row_info.invert_axis) ? -gp->grid_field_size:gp->grid_field_size;
	IVP_DOUBLE dy = (gp->column_info.invert_axis) ? -gp->grid_field_size:gp->grid_field_size;
	IVP_DOUBLE dz = (gp->height_invert_axis) ? -1.0f:1.0f;

	row_axle.k[ gp->row_info.maps_to]    = dx;
	col_axle.k[ gp->column_info.maps_to] = dy;
	h_axle.k[gp->height_maps_to]         = dz;

	m_object_f_grid.get_position()->set(&gp->position_origin_os);
	m_object_f_grid.init_columns3(&row_axle, &col_axle, &h_axle);

	IVP_DOUBLE det = m_object_f_grid.get_determinante();
	if (det > 0.0f){
	    is_left_handed = IVP_TRUE;
	}else{
	    is_left_handed = IVP_FALSE;
	}
    }

    for (int r=0;r< n_rows-1;r++){
	convert_strip_to_compact_ledges(r, ledges);
    }
}


/* merge everything into the final compact grid thing */
IVP_Compact_Grid *IVP_GridBuilder_Array::compile_ledges_into_compact_grid(const IVP_Template_Compact_Grid *gp,IVP_U_Vector<IVP_Compact_Ledge> *ledges){
	IVP_Compact_Grid *cg = NULL;
	int buffer_size = (char *)&cg->offset_compact_ledge_array[0] - (char *)cg;	// size for base compact ledge

	buffer_size += ledges->len() * sizeof(int); // add buffersize for ledge index array
	buffer_size += (n_rows-1) * (n_cols-1) * sizeof(IVP_Compact_Grid_Element);	 //the grid referencing ledge index array
	buffer_size += n_compact_poly_points_used * sizeof(IVP_Compact_Poly_Point);
	buffer_size = (buffer_size + 15) & ~15;	// align compact ledges

	for ( int i = ledges->len()-1; i>=0;i--){	// add buffersize for ledges
		IVP_Compact_Ledge *cl = ledges->element_at(i);
		int l_size = cl->get_size();
		IVP_ASSERT( ((l_size) & 0xf) == 0);
		buffer_size += l_size;
	}

	cg = (IVP_Compact_Grid *)ivp_malloc_aligned(buffer_size+4,16);
	cg->byte_size = buffer_size;

	cg->n_rows = n_rows-1;
	cg->n_columns = n_cols-1;
	cg->n_compact_ledges= ledges->len();

	IVP_U_Matrix m_object_f_grid;
	{
	    IVP_U_Point col_axle; col_axle.set_to_zero();
	    IVP_U_Point row_axle; row_axle.set_to_zero();
	    IVP_U_Point h_axle;   h_axle.set_to_zero();

	    IVP_DOUBLE dx = (gp->row_info.invert_axis) ? -gp->grid_field_size:gp->grid_field_size;
	    IVP_DOUBLE dy = (gp->column_info.invert_axis) ? -gp->grid_field_size:gp->grid_field_size;
	    IVP_DOUBLE dz = (gp->height_invert_axis) ? -1.0f:1.0f;

	    row_axle.k[ gp->row_info.maps_to]    = dx;
	    col_axle.k[ gp->column_info.maps_to] = dy;
	    h_axle.k[gp->height_maps_to]         = dz;

	    m_object_f_grid.get_position()->set(&gp->position_origin_os);
	    m_object_f_grid.init_columns3(&row_axle, &col_axle, &h_axle);

	    cg->m_grid_f_object.real_invert(&m_object_f_grid);
	}
	{
	    IVP_DOUBLE det = m_object_f_grid.get_determinante();
	    if (det > 0.0f){
		is_left_handed = IVP_TRUE;
	    }else{
		is_left_handed = IVP_FALSE;
	    }
	}
	IVP_DOUBLE max_delta_height_os;
	{ // find center, use bounding box
	    IVP_FLOAT max, min;
	    max = min = height_field[0];
	    for (int x= n_cols * n_rows -1;x>=0; x--){
		if (height_field[x] > max) max = height_field[x];
		if (height_field[x] < min) min = height_field[x];
	    }
	    IVP_U_Float_Point center_gs;
	    center_gs.set( (n_rows-1) * 0.5f, (n_cols-1) * 0.5f, (max + min) * 0.5f );

	    m_object_f_grid.vmult4( &center_gs, &cg->center );
	    max_delta_height_os = (max - min ) * 0.5f;
	}

	IVP_U_Point center; center.set(&cg->center);
	{ // find radius, loop through all used 
	    IVP_DOUBLE qrad;
	    qrad = center.quad_distance_to(&compact_poly_point_buffer[0]);

	    for ( int i = n_compact_poly_points_used-1; i>0; i--){
		IVP_DOUBLE 	qr = center.quad_distance_to( & compact_poly_point_buffer[i]);
		if (qr > qrad) qrad = qr;
	    }
	    cg->radius = (IVP_FLOAT)IVP_Inline_Math::sqrtd(qrad);
	}
	cg->inv_grid_size = 1.0f / gp->grid_field_size;

	// reserve space for the grid elements
	cg->offset_grid_elements = ((char *)(&cg->offset_compact_ledge_array[0])) - ((char *)cg) + sizeof(int) * ledges->len(); // skip the ledge offsets
	
	// TL: align offset to next 16 Byte Alignment (I didn't write the GridBuilder, so I have no idea wether the memory will be enough, lets hope ... - the SUN-Debugger will find it)
	int aligned_offset=cg->offset_grid_elements+15;
	aligned_offset=aligned_offset & 0xfffffff0;
    cg->offset_grid_elements=aligned_offset;

	{ // fill in the compact ledges

		char *dest = ((char *)cg) + cg->offset_grid_elements + (n_rows-1) * (n_cols-1) * sizeof(IVP_Compact_Grid_Element);


		char *compact_points = dest;
		{ // all points
			int size_of_points = sizeof(IVP_Compact_Poly_Point) * n_compact_poly_points_used;
			memcpy(compact_points, (char *)compact_poly_point_buffer, size_of_points);
			dest += size_of_points;
		}

		// and the ledges
		dest = (char *)((long(dest)+0xf) & ~0xf);     	// align destination
		for (int ledge_index = 0; ledge_index < ledges->len(); ledge_index++){
			IVP_Compact_Ledge *cl;
			cl = ledges->element_at(ledge_index);
			int l_size = cl->get_size();
			memcpy(dest, (char *)cl, l_size);

			IVP_Compact_Ledge *cl_dest = (IVP_Compact_Ledge *)dest;
			cl_dest->set_offset_ledge_points( (char *)cl->get_point_array() - (char *)compact_poly_point_buffer + compact_points - (char *)cl_dest );

			IVP_ASSERT( cl_dest->get_point_array()->quad_distance_to(cl->get_point_array()) == 0.0f);

			cg->offset_compact_ledge_array[ ledge_index ] = dest - (char *)cg;
			dest += l_size;
		}
		ledges->remove_all();
		IVP_ASSERT( (char *)dest - (char *)cg == cg->byte_size );
	}


	{ // fill in the grid referencing offset_compact_ledge_array
	    IVP_Compact_Grid_Element *ge = (IVP_Compact_Grid_Element *)cg->get_grid_elements();	// discard const
		IVP_Compact_Grid_Element *source = &ledge_reference_field[0];

		for (int r = 1; r < n_rows; r++){
			for (int c=1; c < n_cols; c++){
				*ge = *source;
				ge++;
				source++;
			}
			source++;	// skip extra unused row
		}
	}



	return cg;
}
 

IVP_Compact_Grid  *IVP_GridBuilder_Array::convert_array_to_compact_grid(IVP_Environment *env, const IVP_Template_Compact_Grid *gp, IVP_FLOAT *height_field){
	
    IVP_U_Memory	*mm = env->get_memory_manager();
	mm->start_memory_transaction();

	IVP_GridBuilder_Array builder(mm, gp, height_field);


	IVP_U_Vector<IVP_Compact_Ledge> ledges(1024);
	
	builder.convert_array_to_compact_ledges(gp, &ledges);

	IVP_Compact_Grid *cg = builder.compile_ledges_into_compact_grid(gp, &ledges);

	mm->end_memory_transaction();
	return cg;

}