ivp_surbuild_ledge_soup.cxx

hl2 source code. Do not use it illegal.

	if ( child_sphere_2->number == this->spheres_cluster[0].next ) {
	    this->spheres_cluster[0].next = this->spheres_cluster[child_sphere_2->number].next;
	}
	this->spheres_cluster[child_sphere_2->number].sphere = NULL;
	this->spheres_cluster[this->spheres_cluster[child_sphere_2->number].previous].next = this->spheres_cluster[child_sphere_2->number].next;
	this->spheres_cluster[this->spheres_cluster[child_sphere_2->number].next].previous = this->spheres_cluster[child_sphere_2->number].previous;

	this->number_of_nodes++; // [# of nodes] = [# of term.nodes] + [# of internal nodes]
    
	// decrease number of unclustered spheres by one...
	this->number_of_unclustered_spheres--;

    }
    this->built_spheres.clear();

    return;

}


// ------------------------------------------------------------------------------
//   top-down
// ------------------------------------------------------------------------------

void IVP_SurfaceBuilder_Ledge_Soup::cluster_spheres_topdown_mediancut(IVP_DOUBLE /*threshold_increase*/) {

    IVP_U_Vector<IVV_Sphere> terminals;
    
    for(int next_sphere=this->spheres_cluster[0].next; next_sphere != 0; next_sphere = this->spheres_cluster[next_sphere].next) {
		terminals.add(this->spheres_cluster[next_sphere].sphere);
    }

    this->number_of_nodes = this->number_of_terminal_spheres; // [# of nodes] = [# of term.nodes] + [# of internal nodes]; needed for calculation of compact_surface size!
    
    this->spheres_cluster[this->spheres_cluster[0].next].sphere = this->cluster_spheres_topdown_mediancut_recursively(&terminals);
    
    return;
}


void IVP_SurfaceBuilder_Ledge_Soup::calculate_boundingbox(IVP_U_Vector<IVV_Sphere> *terminals, IVP_U_Float_Point *ext_min, IVP_U_Float_Point *ext_max) {

    static IVP_DOUBLE dimension_steps = IVP_COMPACT_BOUNDINGBOX_STEP_SIZE;
    
    ext_min->set( 1000000.0f,  1000000.0f,  1000000.0f);
    ext_max->set(-1000000.0f, -1000000.0f, -1000000.0f);
    
    for(int x = 0; x<terminals->len(); x++) {
	
		IVV_Sphere *sphere = terminals->element_at(x);

		IVP_DOUBLE work = dimension_steps * sphere->radius;

		IVP_DOUBLE min[3], max[3];
		min[0] = sphere->center.k[0] - ( sphere->box_sizes[0] * work );
		min[1] = sphere->center.k[1] - ( sphere->box_sizes[1] * work );
		min[2] = sphere->center.k[2] - ( sphere->box_sizes[2] * work );
		max[0] = sphere->center.k[0] + ( sphere->box_sizes[0] * work );
		max[1] = sphere->center.k[1] + ( sphere->box_sizes[1] * work );
		max[2] = sphere->center.k[2] + ( sphere->box_sizes[2] * work );

		if ( min[0] < ext_min->k[0] ) ext_min->k[0] = min[0];
		if ( max[0] > ext_max->k[0] ) ext_max->k[0] = max[0];
		if ( min[1] < ext_min->k[1] ) ext_min->k[1] = min[1];
		if ( max[1] > ext_max->k[1] ) ext_max->k[1] = max[1];
		if ( min[2] < ext_min->k[2] ) ext_min->k[2] = min[2];
		if ( max[2] > ext_max->k[2] ) ext_max->k[2] = max[2];

    }

    return;
}


IVV_Sphere *IVP_SurfaceBuilder_Ledge_Soup::cluster_spheres_topdown_mediancut_recursively(IVP_U_Vector<IVV_Sphere> *terminals) {

    // Proceedings:
    // 1. calculate bounding box (and smallest enclosing sphere) for set of terminals
    // 2. find longest axis
    // 3. calculate median
    // 4. assign terminals to left- and righthand vectors according to their centers' positions
    // 5. recursively process left- and righthand vectors

    IVP_ASSERT(terminals->len() > 0);

    if ( terminals->len() == 1 ) return( terminals->element_at(0) ); // only one terminal left: return it

    // calculate the bounding box for the supplied set of terminals
    this->calculate_boundingbox(terminals, &this->extents_min, &this->extents_max);
    
    static IVP_DOUBLE dimension_steps = IVP_COMPACT_BOUNDINGBOX_STEP_SIZE;
    IVP_U_Point rad;
    IVP_U_Point new_center;
    IVP_DOUBLE new_radius;
    new_center.set_interpolate(&this->extents_max, &this->extents_min, 0.5f); // use center of bounding box as center of sphere
    rad.subtract(&this->extents_max, &new_center);
    new_radius = rad.real_length(); // calculate radius of box-enclosing sphere
    IVP_DOUBLE work = new_radius * dimension_steps;

    // initialize new mothersphere
    IVV_Sphere *new_sphere = new IVV_Sphere();
    this->all_spheres.add(new_sphere);
    new_sphere->number = 0;
    new_sphere->radius = new_radius;
    new_sphere->center = new_center;
    new_sphere->compact_ledge = NULL;
    new_sphere->box_sizes[0] = int((this->extents_max.k[0]-new_center.k[0])/work)+1;
    new_sphere->box_sizes[1] = int((this->extents_max.k[1]-new_center.k[1])/work)+1;
    new_sphere->box_sizes[2] = int((this->extents_max.k[2]-new_center.k[2])/work)+1;

    // special case: "two spheres left in branch"
    // independent of the spheres' position we simply assign one of them to the left branch and one to the right branch.
    if ( terminals->len() == 2 ) {
	
		// recursively process subsets
		IVP_U_Vector<IVV_Sphere> lefthand_terminals, righthand_terminals;
		lefthand_terminals.add(terminals->element_at(0));
		righthand_terminals.add(terminals->element_at(1));
		new_sphere->child_1 = this->cluster_spheres_topdown_mediancut_recursively(&lefthand_terminals);
		new_sphere->child_2 = this->cluster_spheres_topdown_mediancut_recursively(&righthand_terminals);
    
		IVP_ASSERT(new_sphere->child_1 != 0);
		IVP_ASSERT(new_sphere->child_2 != 0);
		
		this->number_of_nodes++; // [# of nodes] = [# of term.nodes] + [# of internal nodes]
		
		return(new_sphere);

    }
    
    // set order of axes
    IVP_DOUBLE exts[3];
    exts[0] = this->extents_max.k[0] - this->extents_min.k[0];
    exts[1] = this->extents_max.k[1] - this->extents_min.k[1];
    exts[2] = this->extents_max.k[2] - this->extents_min.k[2];

#ifndef IVP_CLUSTER_SHORTRANGE_BALANCED
    int axes_order[3];

    if ( exts[0] < exts[1] ) {

		if ( exts[1] < exts[2] ) { 
			axes_order[0]=2;  
			axes_order[1]=1;  
			axes_order[2]=0; 
		} else if ( exts[0] < exts[2] ) { 
			axes_order[0]=1;  
			axes_order[1]=2;  
			axes_order[2]=0; 
		} else { 
			axes_order[0]=1;  
			axes_order[1]=0;  
			axes_order[2]=2; 
		}

    } else {

		if ( exts[0] < exts[2] ) { 
			axes_order[0]=2;  
			axes_order[1]=0;  
			axes_order[2]=1; 
		} else if ( exts[1] < exts[2] ) { 
			axes_order[0]=0;  
			axes_order[1]=2;  
			axes_order[2]=1; 
		} else { 
			axes_order[0]=0;  
			axes_order[1]=1;  
			axes_order[2]=2; 
		}

    }
#endif    

    //IVP_U_Vector<IVV_Sphere> lefthand_terminals[3], righthand_terminals[3];
    IVP_U_Vector<IVV_Sphere> *lefthand_terminals[3], *righthand_terminals[3];
    lefthand_terminals[0] = new IVP_U_Vector<IVV_Sphere>(terminals->len());
    lefthand_terminals[1] = new IVP_U_Vector<IVV_Sphere>(terminals->len());
    lefthand_terminals[2] = new IVP_U_Vector<IVV_Sphere>(terminals->len());
    righthand_terminals[0] = new IVP_U_Vector<IVV_Sphere>(terminals->len());
    righthand_terminals[1] = new IVP_U_Vector<IVV_Sphere>(terminals->len());
    righthand_terminals[2] = new IVP_U_Vector<IVV_Sphere>(terminals->len());
    
    IVP_FLOAT difference_in_boundingbox_volumes[3];

#ifdef IVP_CLUSTER_SHORTRANGE_BALANCED
    for(int axis = 0; axis<3; axis++) // we are balancing over three axes
#else
	int axis = axes_order[0]; // we just balance over the first
#endif
	{    
		// calculate median on chosen axis
		IVP_DOUBLE median = 0.0f;

		for(int median_average = 0; median_average < terminals->len(); median_average++) {
			median += terminals->element_at(median_average)->center.k[axis];
		}

		median /= terminals->len();

		IVP_IF(0) {
//		    ivp_message("Median on axis %d: %f\n", axis, median);
		}

		// assign terminals to either side of splitting plane
		// (this is a bit tricky as we have to carefully handle terminals lying on the median itself;
		//  to avoid ending up with an empty subbox by assigning a median-terminal randomly to the
		//  same side as the non-median-terminal, we examine the non-median-terminal and choose the
		//  opposite side; in case of more than one median-terminal we alternate between left and
		//  right side)
		IVP_BOOL toggle = IVP_TRUE;

		for(int x = 0; x < terminals->len(); x++) {
			IVV_Sphere* terminal_sphere = terminals->element_at(x);

			if ( terminal_sphere->center.k[axis] < (median-P_FLOAT_RES) ) {

				lefthand_terminals[axis]->add(terminal_sphere); // sphere center left of the median

			} else if ( terminal_sphere->center.k[axis] > (median+P_FLOAT_RES) ) {

				righthand_terminals[axis]->add(terminal_sphere); // sphere center right of the median

			} else { // current sphere center on median

				IVV_Sphere* reference_sphere;

				if ( x == terminals->len() - 1 ) {
					reference_sphere = terminals->element_at(x - 1);
				} else {
					reference_sphere = terminals->element_at(x + 1);
				}

				if ( reference_sphere->center.k[axis] < (median-P_FLOAT_RES) ) {
					righthand_terminals[axis]->add(terminal_sphere);
					continue;
				}

				if ( reference_sphere->center.k[axis] > (median+P_FLOAT_RES) ) {
					lefthand_terminals[axis]->add(terminal_sphere);
					continue;
				}

				{ // reference sphere also had center on median!!
    				if ( lefthand_terminals[axis]->len() == 0 ) {
						lefthand_terminals[axis]->add(terminal_sphere);
						continue;
					}

    				if ( righthand_terminals[axis]->len() == 0 ) {
						righthand_terminals[axis]->add(terminal_sphere);
						continue;
					}

					if ( toggle ) {
						lefthand_terminals[axis]->add(terminal_sphere);
						toggle = IVP_FALSE;
					} else {
						righthand_terminals[axis]->add(terminal_sphere);
						toggle = IVP_TRUE;
					}
				}
			}
		}

		// calculate children's boundingboxes for all three possible splits and choose the split with
		// optimal balanced boundingbox volume/surface
		IVP_U_Float_Point min[2], max[2];
		this->calculate_boundingbox(lefthand_terminals[axis], &min[0], &max[0]);
		this->calculate_boundingbox(righthand_terminals[axis], &min[1], &max[1]);

#ifdef IVP_CLUSTER_SHORTRANGE_BALANCE_VOLUME	
		IVP_U_Float_Point dim1(IVP_Inline_Math::fabsd(max[0].k[0]-min[0].k[0]),
			IVP_Inline_Math::fabsd(max[0].k[1]-min[0].k[1]),
			IVP_Inline_Math::fabsd(max[0].k[2]-min[0].k[2])); // slower!
		IVP_U_Float_Point dim2(IVP_Inline_Math::fabsd(max[1].k[0]-min[1].k[0]),
			IVP_Inline_Math::fabsd(max[1].k[1]-min[1].k[1]),
			IVP_Inline_Math::fabsd(max[1].k[2]-min[1].k[2])); // slower!
		IVP_FLOAT volume1 = dim1.k[0] * dim1.k[1] * dim1.k[2];
		IVP_FLOAT volume2 = dim2.k[0] * dim2.k[1] * dim2.k[2];
		//IVP_FLOAT volume1 = fabs(max[0].k[0]-min[0].k[0]) * fabs(max[0].k[1]-min[0].k[1]) * fabs(max[0].k[2]-min[0].k[2]); // faster!
		//IVP_FLOAT volume2 = fabs(max[1].k[0]-min[1].k[0]) * fabs(max[1].k[1]-min[1].k[1]) * fabs(max[1].k[2]-min[1].k[2]); // faster!
		difference_in_boundingbox_volumes[axis] = IVP_Inline_Math::fabsd(volume2-volume1);
#else

		//difference_in_boundingbox_volumes[axis] = max[left].k[axis] - min[right].k[axis];
		IVP_U_Float_Point dim1(IVP_Inline_Math::fabsd(max[0].k[0]-min[0].k[0]), IVP_Inline_Math::fabsd(max[0].k[1]-min[0].k[1]), IVP_Inline_Math::fabsd(max[0].k[2]-min[0].k[2])); // slower!
		IVP_U_Float_Point dim2(IVP_Inline_Math::fabsd(max[1].k[0]-min[1].k[0]), IVP_Inline_Math::fabsd(max[1].k[1]-min[1].k[1]), IVP_Inline_Math::fabsd(max[1].k[2]-min[1].k[2])); // slower!
		IVP_FLOAT volume1 = dim1.k[0] * dim1.k[1] * dim1.k[2];
		IVP_FLOAT volume2 = dim2.k[0] * dim2.k[1] * dim2.k[2];
		//IVP_FLOAT volume1 = fabs(max[0].k[0]-min[0].k[0]) * fabs(max[0].k[1]-min[0].k[1]) * fabs(max[0].k[2]-min[0].k[2]); // faster!
		//IVP_FLOAT volume2 = fabs(max[1].k[0]-min[1].k[0]) * fabs(max[1].k[1]-min[1].k[1]) * fabs(max[1].k[2]-min[1].k[2]); // faster!
		difference_in_boundingbox_volumes[axis] = volume2+volume1;
#endif	
    }

#ifdef IVP_CLUSTER_SHORTRANGE_BALANCED    
    int chosen_axis = 0;
    { // find optimum axis
		IVP_DOUBLE max_diff = P_DOUBLE_MAX;

		for (int i = 0; i< 3; i++) {
			if ( difference_in_boundingbox_volumes[i] < max_diff ) {
				if ( (lefthand_terminals[i]->len() != 0) && (righthand_terminals[i]->len() != 0) )
					chosen_axis = i;

				max_diff = difference_in_boundingbox_volumes[i];
		    }
		}
    }
#else
    int chosen_axis = axes_order[0];
#endif    

    //printf("Chosen axis: %d\n", chosen_axis);
    
    IVP_ASSERT(lefthand_terminals[chosen_axis]->len() != 0);
    IVP_ASSERT(righthand_terminals[chosen_axis]->len() != 0);

    // recursively process subsets
    new_sphere->child_1 = this->cluster_spheres_topdown_mediancut_recursively(lefthand_terminals[chosen_axis]);
    new_sphere->child_2 = this->cluster_spheres_topdown_mediancut_recursively(righthand_terminals[chosen_axis]);

    P_DELETE(lefthand_terminals[0]);
    P_DELETE(lefthand_terminals[1]);
    P_DELETE(lefthand_terminals[2]);
    P_DELETE(righthand_terminals[0]);
    P_DELETE(righthand_terminals[1]);
    P_DELETE(righthand_terminals[2]);
    
    IVP_ASSERT(new_sphere->child_1 != 0);
    IVP_ASSERT(new_sphere->child_2 != 0);
    
    this->number_of_nodes++; // [# of nodes] = [# of term.nodes] + [# of internal nodes]
    
    return(new_sphere);
}




/********************************************************************************
 *	Name:	     	allocate_compact_surface
 *	Description:	allocates memory for compact surface and initializes
 *			some basic values
 ********************************************************************************/
IVP_Compact_Surface *IVP_SurfaceBuilder_Ledge_Soup::allocate_compact_surface()
{
        
    // allocate memory for "Compact Surface"
    int cs_header_size     = sizeof(IVP_Compact_Surface);

    int cs_estimated_ledglelist_size = 0;
    int number_of_triangles_compiled = 0;
    int number_of_ledges_compiled = 0;

    if (parameters->link_to_input_compact_ledges == IVP_FALSE){
	for (int i=0; i<this->terminal_spheres.len(); i++) {
       	    IVV_Sphere *sphere = this->terminal_spheres.element_at(i);
	    IVP_Compact_Ledge *source = sphere->compact_ledge;	    
	    int ledge_size = source->get_size(); // 'IVP_Compact_Ledge's have to be 16bytes-aligned!
    	    cs_estimated_ledglelist_size += ledge_size;
	    number_of_triangles_compiled += source->get_n_triangles();
	    number_of_ledges_compiled ++;
	}
    }

    for (int j=0; j<this->rec_spheres.len(); j++) {
       	IVV_Sphere *sphere = this->rec_spheres.element_at(j);
	IVP_Compact_Ledge *source = sphere->compact_ledge;
        int ledge_size = source->get_size(); // 'IVP_Compact_Ledge's have to be 16bytes-aligned!
        cs_estimated_ledglelist_size += ledge_size;
        number_of_triangles_compiled += source->get_n_triangles();
	number_of_ledges_compiled++;
    }

    int cs_ledgetree_size = this->number_of_nodes * sizeof(IVP_Compact_Ledgetree_Node);
    // complete size of compact surface
    int cs_size = cs_header_size + cs_estimated_ledglelist_size + cs_ledgetree_size;

    cs_size = (cs_size + 15) & ~0xf;