ivp_surbuild_ledge_soup.cxx

hl2 source code. Do not use it illegal.

		}

		this->terminal_spheres.add(sphere);

		n++;
    }

    this->spheres_cluster[n-1].next = 0;
    
    // @@@SF: for speedup of single-convex objects, move this into sphere-clustering!
    if ( ledge_cnt > 1 ) {
		IVP_DOUBLE ext_x = this->extents_max.k[0] - this->extents_min.k[0];
		IVP_DOUBLE ext_y = this->extents_max.k[1] - this->extents_min.k[1];
		IVP_DOUBLE ext_z = this->extents_max.k[2] - this->extents_min.k[2];

		if ( ext_x < ext_y ) {

		    if ( ext_y < ext_z ) 
				this->longest_axis = 2;
			else                 
				this->longest_axis = 1;

		} else {

			if ( ext_x < ext_z ) 
				this->longest_axis = 2;
			else
				this->longest_axis = 0;

		}
    }
    
    return;
}


class IVP_Clustering_Shortrange_Interval_Min_Hash_Entry {
public:    
    IVP_BOOL    start;
    IVV_Sphere *sphere;

    IVP_Clustering_Shortrange_Interval_Min_Hash_Entry(IVP_BOOL start_in, IVV_Sphere *sphere_in) {
	this->start = start_in;
	this->sphere = sphere_in;
	return;
    }
};



/********************************************************************************
 *
 *  DIFFERENT CLUSTERING-METHODS
 *
 *******************************************************************************/


// ------------------------------------------------------------------------------
//   bottom-up
// ------------------------------------------------------------------------------

void IVP_SurfaceBuilder_Ledge_Soup::cluster_spheres_bottomup(IVP_DOUBLE threshold_increase) {

    float fixed_max_radius_for_new_sphere = this->smallest_radius;
	
    // initialize outer (interval) MinHash
    if ( this->number_of_terminal_spheres > 512 ) {
	this->interval_minhash = new IVV_Cluster_Min_Hash(4096*4);
    } else {
	this->interval_minhash = new IVV_Cluster_Min_Hash(256);
    }

    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->number_of_unclustered_spheres = this->number_of_terminal_spheres;
    while ( this->number_of_unclustered_spheres > 1 ) {

	IVV_Cluster_Min_Hash cluster_min_hash(256); //@@@SF: start value still has to be optimized!

	// project all spheres onto the longest axis of ledge soup
	this->generate_interval_minhash(0.5f * fixed_max_radius_for_new_sphere);

	while ( this->interval_minhash->counter > 0 ) {

	    // retrieve smallest value on interval axis
	    IVP_Clustering_Shortrange_Interval_Min_Hash_Entry *entry = (IVP_Clustering_Shortrange_Interval_Min_Hash_Entry *)this->interval_minhash->find_min_elem();
	    this->interval_minhash->remove((void *)entry);

	    // value is left interval border (i.e. the smallest point occupied by sphere)
	    if ( entry->start ) {
		this->overlapping_spheres.add(entry->sphere);
		this->combine_spheres_in_vector(&cluster_min_hash); // calculate all possible combinations of all overlapping spheres
		
		// retrieve smallest mothersphere (if available!)
		IVV_Cluster_Min_Hash_Key key;
		key.key = (int)cluster_min_hash.find_min_elem();
		if ( key.key != (unsigned int)NULL ) { // verify that there were at least 2 spheres in vector and a new minimal sphere could be generated!
		    //IVP_DOUBLE radius = cluster_min_hash->find_min_value(); // radius of minimal sphere
		    int sphere_1_number = key.spheres.s1;
		    int sphere_2_number = key.spheres.s2;
		    
		    // remove all combinations from hash that contain the (soon to be) clustered child spheres...
		    this->remove_all_further_spherecombinations_from_hash(&cluster_min_hash, sphere_1_number);
		    this->remove_all_further_spherecombinations_from_hash(&cluster_min_hash, sphere_2_number);

		    // remove child-spheres of new minimal sphere from vector
		    IVV_Sphere *sphere1 = this->spheres_cluster[sphere_1_number].sphere;
		    IVV_Sphere *sphere2 = this->spheres_cluster[sphere_2_number].sphere;
		    this->overlapping_spheres.remove(sphere1);
		    this->overlapping_spheres.remove(sphere2);

		    // build new mothersphere and store it in separate list
		    IVV_Sphere *new_sphere = this->build_minimal_sphere(sphere1, sphere2);
		    this->built_spheres.add(new_sphere);
		}
	    }
	    // value is right interval border (i.e. the largest point occupied by sphere)
	    else {
		if ( this->overlapping_spheres.index_of(entry->sphere) != -1 ) {
		    this->overlapping_spheres.remove(entry->sphere);
		}
		this->remove_all_further_spherecombinations_from_hash(&cluster_min_hash, entry->sphere->number);
	    }

	    P_DELETE(entry);

	}

	IVP_ASSERT(this->interval_minhash->counter == 0);
	IVP_ASSERT(cluster_min_hash.counter == 0);
	IVP_ASSERT(this->overlapping_spheres.len() == 0);

	// increase threshold/blowup (if necessary)
	if ( this->built_spheres.len() == 0 ) {
	    //printf("No spheres could be combined. Increasing radius threshold from %f to %f.\n", fixed_max_radius_for_new_sphere, fixed_max_radius_for_new_sphere+threshold_increase);
	    fixed_max_radius_for_new_sphere *= threshold_increase;
	}

	// replace old spheres with newly built motherspheres
	this->replace_childspheres_in_spherelist_with_motherspheres();
	IVP_ASSERT(this->built_spheres.len() == 0);
    }

    P_DELETE(this->interval_minhash);

    return;
}


void IVP_SurfaceBuilder_Ledge_Soup::generate_interval_minhash(float fixed_max_radius) {

    IVV_Cluster_Min_Hash_Key new_key;
    
    int next_sphere;
    for (next_sphere=this->spheres_cluster[0].next; next_sphere!=0; next_sphere=this->spheres_cluster[next_sphere].next) {

	IVV_Sphere *sphere = this->spheres_cluster[next_sphere].sphere;
	IVP_DOUBLE radius = sphere->radius;
	if ( radius < fixed_max_radius ) {
	    radius = fixed_max_radius;
	}

	// insert interval start into interval MinHash
	IVP_Clustering_Shortrange_Interval_Min_Hash_Entry *new_entry_interval_start = new IVP_Clustering_Shortrange_Interval_Min_Hash_Entry(IVP_TRUE, sphere);
	new_key.key = (int)new_entry_interval_start;
	this->interval_minhash->add((void *)new_key.key, sphere->center.k[this->longest_axis]-radius);

	// insert interval end into interval MinHash
	IVP_Clustering_Shortrange_Interval_Min_Hash_Entry *new_entry_interval_end = new IVP_Clustering_Shortrange_Interval_Min_Hash_Entry(IVP_FALSE, sphere);
	new_key.key = (int)new_entry_interval_end;
	this->interval_minhash->add((void *)new_key.key, sphere->center.k[this->longest_axis]+radius);

    }

    return;
}


void IVP_SurfaceBuilder_Ledge_Soup::combine_spheres_in_vector(IVV_Cluster_Min_Hash *cluster_min_hash) {

    IVV_Cluster_Min_Hash_Key newkey;
    
    int x;
    for (x=0; x<this->overlapping_spheres.len(); x++) {

	IVV_Sphere *sphere_1 = this->overlapping_spheres.element_at(x);

	int y;
	for (y=0; y<this->overlapping_spheres.len(); y++) {
	    if ( x == y ) continue;
	    IVV_Sphere *sphere_2 = this->overlapping_spheres.element_at(y);

#if 0	    
	    IVP_DOUBLE qdistance = sphere_1->center.quad_distance_to(&sphere_2->center);
	    IVP_DOUBLE qdiff_radius = sphere_1->radius - sphere_2->radius;
	    qdiff_radius *= qdiff_radius;

	    // sort spheres: larger sphere is always left (i.e. position 1 :)
	    if ( sphere_1->radius < sphere_2->radius ) {
		IVV_Sphere *sphere_buf = sphere_1;
		sphere_1 = sphere_2;
		sphere_2 = sphere_buf;
	    }
	    
	    IVP_DOUBLE radius;
	    if ( qdistance <= qdiff_radius ) { // sphere 2 completely within sphere 1
		radius = sphere_1->radius;
	    }else {
		IVP_DOUBLE distance_2 = sqrt(qdistance) * 0.5f;
		IVP_DOUBLE r1r2_2 = IVP_Inline_Math::fabsd(sphere_1->radius - sphere_2->radius) * 0.5f;
		radius = distance_2 + sphere_1->radius - r1r2_2;
	    }
#else
 	    IVP_DOUBLE work1 = IVP_COMPACT_BOUNDINGBOX_STEP_SIZE * sphere_1->radius;
	    IVP_DOUBLE work2 = IVP_COMPACT_BOUNDINGBOX_STEP_SIZE * sphere_2->radius;
	
	    IVP_DOUBLE max1_x = sphere_1->center.k[0] + ( sphere_1->box_sizes[0] * work1 );
	    IVP_DOUBLE max1_y = sphere_1->center.k[1] + ( sphere_1->box_sizes[1] * work1 );
	    IVP_DOUBLE max1_z = sphere_1->center.k[2] + ( sphere_1->box_sizes[2] * work1 );
	    IVP_DOUBLE min1_x = sphere_1->center.k[0] - ( sphere_1->box_sizes[0] * work1 );
	    IVP_DOUBLE min1_y = sphere_1->center.k[1] - ( sphere_1->box_sizes[1] * work1 );
	    IVP_DOUBLE min1_z = sphere_1->center.k[2] - ( sphere_1->box_sizes[2] * work1 );

	    IVP_DOUBLE max2_x = sphere_2->center.k[0] + ( sphere_2->box_sizes[0] * work2 );
	    IVP_DOUBLE max2_y = sphere_2->center.k[1] + ( sphere_2->box_sizes[1] * work2 );
	    IVP_DOUBLE max2_z = sphere_2->center.k[2] + ( sphere_2->box_sizes[2] * work2 );
	    IVP_DOUBLE min2_x = sphere_2->center.k[0] - ( sphere_2->box_sizes[0] * work2 );
	    IVP_DOUBLE min2_y = sphere_2->center.k[1] - ( sphere_2->box_sizes[1] * work2 );
	    IVP_DOUBLE min2_z = sphere_2->center.k[2] - ( sphere_2->box_sizes[2] * work2 );

	    IVP_U_Point min, max, center, rad;
	    if ( min1_x < min2_x ) min.k[0] = min1_x; else min.k[0] = min2_x;
	    if ( min1_y < min2_y ) min.k[1] = min1_y; else min.k[1] = min2_y;
	    if ( min1_z < min2_z ) min.k[2] = min1_z; else min.k[2] = min2_z;
	    if ( max1_x > max2_x ) max.k[0] = max1_x; else max.k[0] = max2_x;
	    if ( max1_y > max2_y ) max.k[1] = max1_y; else max.k[1] = max2_y;
	    if ( max1_z > max2_z ) max.k[2] = max1_z; else max.k[2] = max2_z;

	    center.set_interpolate(&max, &min, 0.5f); // use center of bounding box as center of sphere
	    rad.subtract(&max, &center);
	    IVP_DOUBLE radius = rad.real_length(); // calculate radius of box-enclosing sphere
#endif	    

	    newkey.spheres.s1 = sphere_1->number;
	    newkey.spheres.s2 = sphere_2->number;
	    if ( !cluster_min_hash->is_elem((void *)newkey.key) ) {
		cluster_min_hash->add((void *)newkey.key, radius);
	    }

	}

    }
    
    return;
}


void IVP_SurfaceBuilder_Ledge_Soup::remove_all_further_spherecombinations_from_hash(IVV_Cluster_Min_Hash *cluster_min_hash, int spherenumber)
{

    // ----------------------------------------------------------------------
    // remove all possible combinations (even if not present in hash) of the
    // supplied sphere from hashtable
    // ----------------------------------------------------------------------
    
    IVV_Cluster_Min_Hash_Key remove_key;

    int x;
    for (x=0; x<this->overlapping_spheres.len(); x++) {

	IVV_Sphere *partner_sphere = this->overlapping_spheres.element_at(x);
	if ( partner_sphere->number == spherenumber ) continue;
	
	remove_key.spheres.s1 = spherenumber;
	remove_key.spheres.s2 = partner_sphere->number;
	cluster_min_hash->remove((void *)remove_key.key);

	remove_key.spheres.s1 = partner_sphere->number;
	remove_key.spheres.s2 = spherenumber;
	cluster_min_hash->remove((void *)remove_key.key);

    }

    return;
}


IVV_Sphere *IVP_SurfaceBuilder_Ledge_Soup::build_minimal_sphere(IVV_Sphere *sphere_1, IVV_Sphere *sphere_2) {

    static IVP_DOUBLE dimension_steps = IVP_COMPACT_BOUNDINGBOX_STEP_SIZE;
    IVP_DOUBLE new_radius;
    IVP_U_Point new_center;
    
    IVV_Sphere *new_sphere = new IVV_Sphere();

#if 0    
    IVP_U_Point dist_vec;
    IVP_DOUBLE distance, distance_2;
    IVP_DOUBLE r1r2_2;
    IVP_DOUBLE interpolation_factor;
    
    // calculate the new mothersphere
    dist_vec.subtract(&sphere_1->center, &sphere_2->center);
    distance = dist_vec.fast_real_length();

    if ( distance + sphere_2->radius <= sphere_1->radius ) {
	new_radius = sphere_1->radius;
	new_center = sphere_1->center;
    }
    else {
	distance_2 = distance * 0.5f;
	r1r2_2 = IVP_Inline_Math::fabsd(sphere_1->radius - sphere_2->radius) * 0.5f;
	new_radius = distance_2 + sphere_1->radius - r1r2_2;
	
	interpolation_factor = ( distance_2 - r1r2_2 ) / distance;
	new_center.set_interpolate(&sphere_1->center, &sphere_2->center, interpolation_factor);
    }
#else
    IVP_DOUBLE work1 = IVP_COMPACT_BOUNDINGBOX_STEP_SIZE * sphere_1->radius;
    IVP_DOUBLE work2 = IVP_COMPACT_BOUNDINGBOX_STEP_SIZE * sphere_2->radius;
	
    IVP_DOUBLE max1_x = sphere_1->center.k[0] + ( sphere_1->box_sizes[0] * work1 );
    IVP_DOUBLE max1_y = sphere_1->center.k[1] + ( sphere_1->box_sizes[1] * work1 );
    IVP_DOUBLE max1_z = sphere_1->center.k[2] + ( sphere_1->box_sizes[2] * work1 );
    IVP_DOUBLE min1_x = sphere_1->center.k[0] - ( sphere_1->box_sizes[0] * work1 );
    IVP_DOUBLE min1_y = sphere_1->center.k[1] - ( sphere_1->box_sizes[1] * work1 );
    IVP_DOUBLE min1_z = sphere_1->center.k[2] - ( sphere_1->box_sizes[2] * work1 );

    IVP_DOUBLE max2_x = sphere_2->center.k[0] + ( sphere_2->box_sizes[0] * work2 );
    IVP_DOUBLE max2_y = sphere_2->center.k[1] + ( sphere_2->box_sizes[1] * work2 );
    IVP_DOUBLE max2_z = sphere_2->center.k[2] + ( sphere_2->box_sizes[2] * work2 );
    IVP_DOUBLE min2_x = sphere_2->center.k[0] - ( sphere_2->box_sizes[0] * work2 );
    IVP_DOUBLE min2_y = sphere_2->center.k[1] - ( sphere_2->box_sizes[1] * work2 );
    IVP_DOUBLE min2_z = sphere_2->center.k[2] - ( sphere_2->box_sizes[2] * work2 );

    IVP_U_Point min, max, rad;
    if ( min1_x < min2_x ) min.k[0] = min1_x; else min.k[0] = min2_x;
    if ( min1_y < min2_y ) min.k[1] = min1_y; else min.k[1] = min2_y;
    if ( min1_z < min2_z ) min.k[2] = min1_z; else min.k[2] = min2_z;
    if ( max1_x > max2_x ) max.k[0] = max1_x; else max.k[0] = max2_x;
    if ( max1_y > max2_y ) max.k[1] = max1_y; else max.k[1] = max2_y;
    if ( max1_z > max2_z ) max.k[2] = max1_z; else max.k[2] = max2_z;

    new_center.set_interpolate(&max, &min, 0.5f); // use center of bounding box as center of sphere
    rad.subtract(&max, &new_center);
    new_radius = rad.real_length(); // calculate radius of box-enclosing sphere
    
    IVP_DOUBLE work = new_radius * dimension_steps;
    new_sphere->box_sizes[0] = int((max.k[0]-new_center.k[0])/work)+1;
    new_sphere->box_sizes[1] = int((max.k[1]-new_center.k[1])/work)+1;
    new_sphere->box_sizes[2] = int((max.k[2]-new_center.k[2])/work)+1;
#endif    
    
    // initialize new mothersphere
    new_sphere->number = sphere_1->number; // replace sphere_1 (left sphere) with mothersphere
    new_sphere->radius = new_radius;
    new_sphere->center = new_center;
    new_sphere->compact_ledge = NULL;
    //    new_sphere->parent = NULL;
    new_sphere->child_1 = sphere_1;
    new_sphere->child_2 = sphere_2;

    return(new_sphere);
}


void IVP_SurfaceBuilder_Ledge_Soup::replace_childspheres_in_spherelist_with_motherspheres() {

    int x;
    for (x=0; x<this->built_spheres.len(); x++) {

	IVV_Sphere *mothersphere   = this->built_spheres.element_at(x);
	IVV_Sphere *child_sphere_1 = mothersphere->child_1;
	IVV_Sphere *child_sphere_2 = mothersphere->child_2;
	
	//	child_sphere_1->parent = mothersphere;
	//	child_sphere_2->parent = mothersphere;
	
	// replace old left sphere with new mothersphere, remove old right sphere completely...
	this->spheres_cluster[child_sphere_1->number].sphere = mothersphere;