#include "StdAfx.h" #include "MA_Voxel_Coding.h" // ---------------------------------------------------------------------------------------- // generateClusterGraph // // Description - // ---------------------------------------------------------------------------------------- void MA_VoxelCoding::generateClusterGraph( ) { Vect3usi cur_coord; cl_t i; // In case caching is used, reset buffers to normal size (from here on all cubes are used) CL_cube->resizeCacheBuffer( memory_limit_cl_bytes ); BS_cube->resizeCacheBuffer( memory_limit_bs_bytes ); SS_cube->resizeCacheBuffer( memory_limit_ss_bytes ); // Allocate memory for each cluster node cluster_nodes_array = new ClusterGraphNode[number_of_clusters]; progress_win_ptr->SetWindowText("Generating cluster graph and finding max points..." ); write_to_log("MA_VoxelCoding::generateClusterGraph - Finding BS max points and neighbors for %d clusters.", number_of_clusters); float step_size = (float)number_of_clusters/100; progress_bar_ptr->SetRange(0, 100); progress_bar_ptr->SetPos(0); // Initialize each node with it's ID and max BS coordinates current_cluster_id = 1; // Need to initialize all ID's first (for finding neighbors) for ( i = 1; i <= number_of_clusters; i++ ) { cluster_nodes_array[i-1].ID = i; cluster_nodes_array[i-1].volume_indx = 0xFFFF; } // Determine which volume each cluster belongs to MARK_cubes[NOT_LM]->clear(); MARK_cubes[TRAVELED]->clear(); determineClustersVolumes(); MARK_cubes[TRAVELED]->clear(); // This is a list of lists for storing all shortest paths and later medial axis paths for each volume medial_path_volumes = new MedialPathVolumeInfo[number_of_volumes]; // Fill out all clusters graph nodes for ( cur_coord.z = 0 ; cur_coord.z < boundary_cube->wZ; cur_coord.z++) { for ( cur_coord.y = 0 ; cur_coord.y < boundary_cube->wY; cur_coord.y++) { for (cur_coord.x = 0 ; cur_coord.x < boundary_cube->wX; cur_coord.x++) { // Check if this is next cluster if ( CL_cube->datac(cur_coord) == current_cluster_id ) { // Fill in cluster info cluster_nodes_array[current_cluster_id-1].SS_code = SS_cube->datac( cur_coord ); cluster_nodes_array[current_cluster_id-1].cluster_type &= ~CLUSTER_TYPE_NULL; // Find all local BS maximum points within the cluster and store in the group list, // also finds neighboring clusters and adds them to appropriate lists (uses current_cluster_id) findLocalMaximumsInCluster( cur_coord, cluster_nodes_array[current_cluster_id-1].max_coord_list_ptr ); // Purge the cluster nodes lists since they are now final size cluster_nodes_array[current_cluster_id-1].max_coord_list_ptr->purgeFreeList(); cluster_nodes_array[current_cluster_id-1].s_list_ptr->purgeFreeList(); cluster_nodes_array[current_cluster_id-1].l_list_ptr->purgeFreeList(); // Go on to the next cluster ++ current_cluster_id; progress_bar_ptr->SetPos( (int)( (float)current_cluster_id/step_size ) ); } } } } // Need to reset to 0, to prevent future Link calls messing with cluster graph current_cluster_id = 0; // ------------------------------------------------------------------------------------ // Now that cluster graph is created, we can fill in clusters 'type' info for each node progress_win_ptr->SetWindowText("Generating cluster graph (determining types)..."); write_to_log("MA_VoxelCoding::generateClusterGraph - Determining type for each cluster."); for ( i = 0; i < number_of_clusters; i++ ) { // If cluster doesn't have any larger neighbors, must be a LOCAL MAX cluster if ( cluster_nodes_array[i].l_list_ptr->getSize() == 0 ) { cluster_nodes_array[i].cluster_type |= CLUSTER_TYPE_LOCAL_MAX; ++number_of_local_max_clusters; LinkedListNode<Vect3usi> *coord_node_ptr = cluster_nodes_array[i].max_coord_list_ptr->getHeadPtr(); // Pick largest BS code if multiple LM if ( cluster_nodes_array[i].max_coord_list_ptr->getSize() > 1 ) { write_to_log("MA_VoxelCoding::generateClusterGraph - more than one max coord detected in LM clust."); LinkedListNode<Vect3usi> *temp_node_ptr = cluster_nodes_array[i].max_coord_list_ptr->getHeadPtr()->next; while ( temp_node_ptr ) { if ( BS_cube->datac(temp_node_ptr->item) > BS_cube->datac(coord_node_ptr->item) ) { coord_node_ptr = temp_node_ptr; } temp_node_ptr = temp_node_ptr->next; } } // Insert coordinate into LM list (decreasing SS code order) insertStartingPointIntoShortestPaths( coord_node_ptr->item, cluster_nodes_array[i].volume_indx ); } // At least two +1 greater clusters connected, might be a dividing cluster // (IF ANY +1s have BS of '3', IT IS A NOISE BRANCH THAT WILL BE REMOVED) else if ( 1 < countInListSameSS(cluster_nodes_array[i].l_list_ptr, cluster_nodes_array[i].SS_code + 1, cluster_nodes_array[i].volume_indx) ) { cluster_nodes_array[i].cluster_type |= CLUSTER_TYPE_DIVIDING; ++number_of_dividing_clusters; } // If no smaller neighboring clusters, must be an RP if ( cluster_nodes_array[i].s_list_ptr->getSize() == 0 ) { cluster_nodes_array[i].cluster_type |= CLUSTER_TYPE_RP; ++number_of_rp_clusters; } // At least two -1 smaller clusters connected, must be a merging cluster else if ( 1 < countInListSameSS(cluster_nodes_array[i].s_list_ptr, cluster_nodes_array[i].SS_code - 1, cluster_nodes_array[i].volume_indx) ) { cluster_nodes_array[i].cluster_type |= CLUSTER_TYPE_MERGING; ++number_of_merging_clusters; } // If no flags are set at this point, it is just a normal cluster. } } // ---------------------------------------------------------------------------------------- // countInListSameSS // // Description - // ---------------------------------------------------------------------------------------- int MA_VoxelCoding::countInListSameSS( LinkedList<cl_t> *node_list, ss_t ssid, v_id volume ) { LinkedListNode<cl_t> *cur_node_ptr = node_list->getHeadPtr(); int count = 0; while ( cur_node_ptr ) { if ( (cluster_nodes_array[cur_node_ptr->item-1].SS_code == ssid) && (cluster_nodes_array[cur_node_ptr->item-1].volume_indx == volume)) { ++ count; } cur_node_ptr = cur_node_ptr->next; } return count; } // ---------------------------------------------------------------------------------------- // createClustersNeighborLists // // Description - Inserts a cluster node into a list in decreasing SS_code order. // ---------------------------------------------------------------------------------------- void MA_VoxelCoding::insertStartingPointIntoShortestPaths( Vect3usi &coord, v_id volume_id ) { // If it is the very first item, simply insert it and return if ( medial_path_volumes[volume_id].medial_paths_list->getSize() == 0 ) { medial_path_volumes[volume_id].medial_paths_list->insertAtStart( medial_path_volumes[volume_id].medial_paths_list->getNewNode() ); medial_path_volumes[volume_id].medial_paths_list->getHeadPtr()->item = new LinkedList<PathNode>( 0 ); medial_path_volumes[volume_id].medial_paths_list->getHeadPtr()->item->insertAtStart( medial_path_volumes[volume_id].medial_paths_list->getHeadPtr()->item->getNewNode() ); medial_path_volumes[volume_id].medial_paths_list->getHeadPtr()->item->getHeadPtr()->item.coordinate = coord; return; } LinkedListNode<LinkedList<PathNode>*> *cur_node_ptr = medial_path_volumes[volume_id].medial_paths_list->getHeadPtr(); // Travel down list until in list coordinate has smaller SS code than current while ( cur_node_ptr ) { if ( SS_cube->datac((cur_node_ptr->item->getHeadPtr())->item.coordinate) < SS_cube->datac(coord) ) { break; } cur_node_ptr = cur_node_ptr->next; } // We have either reached end of list, or spot with smaller SS code if ( cur_node_ptr ) { // Insert new coordinate list before list we stopped at. medial_path_volumes[volume_id].medial_paths_list->insertBefore( cur_node_ptr, medial_path_volumes[volume_id].medial_paths_list->getNewNode() ); cur_node_ptr->prev->item = new LinkedList<PathNode>( 0 ); cur_node_ptr->prev->item->insertAtStart( cur_node_ptr->prev->item->getNewNode() ); cur_node_ptr->prev->item->getHeadPtr()->item.coordinate = coord; } else { // Insert new coordinate list at end medial_path_volumes[volume_id].medial_paths_list->insertAtEnd( medial_path_volumes[volume_id].medial_paths_list->getNewNode() ); medial_path_volumes[volume_id].medial_paths_list->getTailPtr()->item = new LinkedList<PathNode>( 0 ); medial_path_volumes[volume_id].medial_paths_list->getTailPtr()->item->insertAtStart( medial_path_volumes[volume_id].medial_paths_list->getTailPtr()->item->getNewNode() ); medial_path_volumes[volume_id].medial_paths_list->getTailPtr()->item->getHeadPtr()->item.coordinate = coord; } } // ---------------------------------------------------------------------------------------- // removeFromMergingCluster // // Description - // ---------------------------------------------------------------------------------------- void MA_VoxelCoding::removeFromMergingCluster( cl_t remove_cluster_id ) { LinkedListNode<cl_t> *cur_clt_node_ptr = cluster_nodes_array[remove_cluster_id-1].l_list_ptr->getHeadPtr(); LinkedListNode<cl_t> *tmp_clt_node_ptr; while ( cur_clt_node_ptr ) { tmp_clt_node_ptr = cluster_nodes_array[cur_clt_node_ptr->item-1].s_list_ptr->getHeadPtr(); while ( tmp_clt_node_ptr ) { if ( tmp_clt_node_ptr->item == remove_cluster_id ) { if ( tmp_clt_node_ptr->next ) { tmp_clt_node_ptr = tmp_clt_node_ptr->next; cluster_nodes_array[cur_clt_node_ptr->item-1].s_list_ptr->removeNode(tmp_clt_node_ptr->prev); } else { cluster_nodes_array[cur_clt_node_ptr->item-1].s_list_ptr->removeNode(tmp_clt_node_ptr); tmp_clt_node_ptr = NULL; } } else { tmp_clt_node_ptr = tmp_clt_node_ptr->next; } } // Make sure cluster remains merging type if ( 1 >= countInListSameSS(cluster_nodes_array[cur_clt_node_ptr->item-1].s_list_ptr, cluster_nodes_array[cur_clt_node_ptr->item-1].SS_code - 1, cluster_nodes_array[cur_clt_node_ptr->item-1].volume_indx) ) { cluster_nodes_array[cur_clt_node_ptr->item-1].cluster_type &= ~CLUSTER_TYPE_MERGING; ++ number_of_merging_clusters_removed; } // Remove from list cluster_nodes_array[remove_cluster_id-1].l_list_ptr->removeHeadNode(); cur_clt_node_ptr = cluster_nodes_array[remove_cluster_id-1].l_list_ptr->getHeadPtr(); } // If this cluster was dividing, make sure it still is if ( 1 >= countInListSameSS(cluster_nodes_array[remove_cluster_id-1].l_list_ptr, cluster_nodes_array[remove_cluster_id-1].SS_code + 1, cluster_nodes_array[remove_cluster_id-1].volume_indx) ) { cluster_nodes_array[remove_cluster_id-1].cluster_type &= ~CLUSTER_TYPE_DIVIDING; ++ number_of_dividing_clusters_removed; } } // ---------------------------------------------------------------------------------------- // removeFromDividingCluster // // Description - // ---------------------------------------------------------------------------------------- void MA_VoxelCoding::removeFromDividingCluster( cl_t remove_cluster_id ) { LinkedListNode<cl_t> *cur_clt_node_ptr = cluster_nodes_array[remove_cluster_id-1].s_list_ptr->getHeadPtr(); LinkedListNode<cl_t> *tmp_clt_node_ptr; while ( cur_clt_node_ptr ) { tmp_clt_node_ptr = cluster_nodes_array[cur_clt_node_ptr->item-1].l_list_ptr->getHeadPtr(); while ( tmp_clt_node_ptr ) { // Remove connection from larger list if ( tmp_clt_node_ptr->item == remove_cluster_id ) { if ( tmp_clt_node_ptr->next ) { tmp_clt_node_ptr = tmp_clt_node_ptr->next; cluster_nodes_array[cur_clt_node_ptr->item-1].l_list_ptr->removeNode(tmp_clt_node_ptr->prev); } else { cluster_nodes_array[cur_clt_node_ptr->item-1].l_list_ptr->removeNode(tmp_clt_node_ptr); tmp_clt_node_ptr = NULL; } } else { tmp_clt_node_ptr = tmp_clt_node_ptr->next; } } // Make sure cluster remains dividing type if ( 1 >= countInListSameSS(cluster_nodes_array[cur_clt_node_ptr->item-1].l_list_ptr, cluster_nodes_array[cur_clt_node_ptr->item-1].SS_code + 1, cluster_nodes_array[cur_clt_node_ptr->item-1].volume_indx) ) { cluster_nodes_array[cur_clt_node_ptr->item-1].cluster_type &= ~CLUSTER_TYPE_DIVIDING; ++ number_of_dividing_clusters_removed; } // Remove from list cluster_nodes_array[remove_cluster_id-1].s_list_ptr->removeHeadNode(); cur_clt_node_ptr = cluster_nodes_array[remove_cluster_id-1].s_list_ptr->getHeadPtr(); } // If this cluster was merging, make sure it still is if ( 1 >= countInListSameSS(cluster_nodes_array[remove_cluster_id-1].s_list_ptr, cluster_nodes_array[remove_cluster_id-1].SS_code - 1, cluster_nodes_array[remove_cluster_id-1].volume_indx) ) { cluster_nodes_array[remove_cluster_id-1].cluster_type &= ~CLUSTER_TYPE_MERGING; ++ number_of_merging_clusters_removed; } }