#include "StdAfx.h"
#include "MA_Voxel_Coding.h"
// ----------------------------------------------------------------------------------------
// findLocalMaximumsInCluster
//
// Description: The main function for finding all local maximums within a single SS cluster.
//
// Starting State: -> All MARK_cubes needs to be clear
// -> SS_cube needs to be valid
// -> 'max_list_ptr' allocated but empty
//
// Ending State: -> SS_cube still valid, MARK_cubes still clear
// -> 'max_list' contains all valid local maximums of SS cluster
// ----------------------------------------------------------------------------------------
void MA_VoxelCoding::findLocalMaximumsInCluster( Vect3usi &member_coord, LinkedList<Vect3usi> *max_list_ptr )
{
// Make current list pointer match parameter (needs to be globaly accessible for recursion function)
current_max_list_ptr = max_list_ptr;
// From the starting coordinate, recurse into cluster volume and mark all non-LM
// subclusters in MARK_cubes[NOT_LM].
recurseOnAllNeighbors( member_coord, &MA_VoxelCoding::markAllButLocalMaximumsAndAddNeighbors );
// At this point, we have all of cluster marked as IN_QUEUE, and any maximums have NOT_LM = 0.
// Recurse again into the cluster and add all of those locations to the clusters LM list.
recurseOnAllNeighbors( member_coord, &MA_VoxelCoding::addToListLocalMaximumInCluster );
// Now IN_QUEUE is clear, but NOT_LM is all '1' for cluster. Clear NOT_LM
recurseOnAllNeighbors( member_coord, &MA_VoxelCoding::clearNotLMCubeInCluster );
// Log if no max found
if (current_max_list_ptr->getSize() == 0)
{
write_to_log("MA_VoxelCoding::findLocalMaximumsInCluster - Warning, no max found, using seed %v.", &member_coord);
max_list_ptr->insertAtStart(max_list_ptr->getNewNode());
max_list_ptr->getHeadPtr()->item = member_coord;
}
// Remove some noise max points (hopefully)
reduceClustersLocalMaximumList( current_max_list_ptr );
// Find center of each local max coord (potentially a plane of maximums)
LinkedListNode<Vect3usi> *cur_max_coord = current_max_list_ptr->getHeadPtr();
while ( cur_max_coord )
{
findMidPtOfIntersection( cur_max_coord->item );
cur_max_coord = cur_max_coord->next;
}
}
// ----------------------------------------------------------------------------------------
// markAllButLocalMaximums
//
// Description: A work function called from recurseOnAllNeighbors(), that will mark all
// locations that are NOT local maximums in NOT_LM cube.
//
// Starting State: -> Current Cluster is marked '0' in NOT_LM cube.
// -> IN_QUEUE cube is all '0'
//
// Ending State: -> NOT_LM cube is '0' ONLY at local maximum points
// -> IN_QUEUE cube is all '1'
// ----------------------------------------------------------------------------------------
bool MA_VoxelCoding::markAllButLocalMaximumsAndAddNeighbors( Vect3usi &cur_coord, Vect3usi &nxt_coord )
{
// Make sure it is part of current cluster, and hasn't already been traveled
if ( SS_cube->datac(nxt_coord) == SS_cube->datac(cur_coord) )
{
// If the neighbor has a higher BS code than current spot, mark current spot (and all
// connected equal BS codes in cluster) as NOT local maximum.
if ( (!MARK_cubes[NOT_LM]->get_spot(cur_coord)) &&
(BS_cube->datac(cur_coord) < BS_cube->datac(nxt_coord)) )
{
#if MA_FULL_TRACE_CLUSTER_MAX_PTS
if ( full_trace_enabled )
{
write_to_log( "TRACE (markAllButLocalMaximums) - Marking current subcluster at %v as not LM.", &(cur_coord) );
}
#endif
recurseOnAllNeighbors( cur_coord, &MA_VoxelCoding::markSubClusterAsNotLocalMaximum );
}
// If the neighbor has a smaller BS code than current spot, the neighbor can
// NOT be a local maximum.
else if ( (!MARK_cubes[NOT_LM]->get_spot(nxt_coord)) &&
(BS_cube->datac(cur_coord) > BS_cube->datac(nxt_coord)) )
{
#if MA_FULL_TRACE_CLUSTER_MAX_PTS
if ( full_trace_enabled )
{
write_to_log( "TRACE (markAllButLocalMaximums) - Marking neighbor subcluster at %v as not LM.", &(nxt_coord) );
}
#endif
recurseOnAllNeighbors( nxt_coord, &MA_VoxelCoding::markSubClusterAsNotLocalMaximum );
}
#if MA_FULL_TRACE_CLUSTER_MAX_PTS
if ( full_trace_enabled )
{
write_to_log( "TRACE (markAllButLocalMaximums) - Coordinate %v marked as in queue.", &(nxt_coord) );
}
#endif
// Now add the neighbor for further recursion into cluster, if it has not been added yet.
// Mark spot as being in queue, return TRUE so it really is in queue
if ( !MARK_cubes[IN_QUEUE]->get_spot(nxt_coord) )
{
MARK_cubes[IN_QUEUE]->set_spot_1( nxt_coord );
if ( current_cluster_id > 0 )
{ // Increment clusters size
++ cluster_nodes_array[current_cluster_id-1].size;
}
return true;
}
}
// Add any neighbors to cluster graph, if option is enabled.
else if ( (current_cluster_id > 0) && (!boundary_cube->get_spot(nxt_coord)) )
{
// Check if next spot is ONE smaller SS than current spot,
// if so add to smaller list if not already present.
if ( (SS_cube->datac(nxt_coord)+1) == (SS_cube->datac(cur_coord)) )
{
LinkedListNode<cl_t> *cluster_node_ptr = cluster_nodes_array[current_cluster_id-1].s_list_ptr->getHeadPtr();
cl_t nxt_cluster_id = CL_cube->datac(nxt_coord);
// First item
if ( cluster_node_ptr == NULL )
{
cluster_nodes_array[current_cluster_id-1].s_list_ptr->insertAtEnd( nxt_cluster_id );
return false;
}
while ( cluster_node_ptr )
{
if ( cluster_node_ptr->item == nxt_cluster_id )
{ // Cluster is already in list, break out
break;
}
if ( cluster_node_ptr->next == NULL )
{ // We are at end of list, insert a new smaller neighbor
cluster_nodes_array[ current_cluster_id-1 ].s_list_ptr->insertAtEnd( nxt_cluster_id );
break;
}
cluster_node_ptr = cluster_node_ptr->next;
}
}
// Check if next spot is ONE larger SS than current spot,
// if so add to larger list if not already present.
else if ( (SS_cube->datac(nxt_coord)-1) == (SS_cube->datac(cur_coord)) )
{
LinkedListNode<cl_t> *cluster_node_ptr = cluster_nodes_array[current_cluster_id-1].l_list_ptr->getHeadPtr();
cl_t nxt_cluster_id = CL_cube->datac(nxt_coord);
// First item
if ( cluster_node_ptr == NULL )
{
cluster_nodes_array[ current_cluster_id-1 ].l_list_ptr->insertAtEnd( nxt_cluster_id );
return false;
}
while ( cluster_node_ptr )
{
if ( cluster_node_ptr->item == nxt_cluster_id )
{ // Cluster is already in list, break out
break;
}
if ( cluster_node_ptr->next == NULL )
{ // We are at end of list, insert a new larger neighbor
cluster_nodes_array[ current_cluster_id-1 ].l_list_ptr->insertAtEnd( nxt_cluster_id );
break;
}
cluster_node_ptr = cluster_node_ptr->next;
}
}
}
// Return false, indicating invalid spot
return false;
}
// ----------------------------------------------------------------------------------------
// markSubClusterAsNotLocalMaximum
//
// Description: A work function called from recurseOnAllNeighbors(), that will mark
// all connected spots with same BS and CL codes as '1' in NOT_LM.
//
// Starting State: -> Starting spot is '0' in NOT_LM cube.
//
// Ending State: -> Starting spot and all connected spots that match above
// criteria are '1' in NOT_LM cube.
// ----------------------------------------------------------------------------------------
bool MA_VoxelCoding::markSubClusterAsNotLocalMaximum( Vect3usi &cur_coord, Vect3usi &nxt_coord )
{
if ( (!MARK_cubes[NOT_LM]->get_spot( nxt_coord )) &&
(SS_cube->datac(cur_coord) == SS_cube->datac(nxt_coord)) &&
(BS_cube->datac(cur_coord) == BS_cube->datac(nxt_coord)) )
{
// Mark the spot and return TRUE to indicate add spot to to-do queue
#if MA_FULL_TRACE_CLUSTER_MAX_PTS
if ( full_trace_enabled )
{
write_to_log( "TRACE (markSubClusterAsNotLocalMaximum) - Coordinate %v set as not LM.", &(nxt_coord) );
}
#endif
MARK_cubes[NOT_LM]->set_spot_1( nxt_coord );
return true;
}
else
{
// Return false, indicating invalid spot
return false;
}
}
// ----------------------------------------------------------------------------------------
// clearNotLMCubeInCluster
//
// Description: A work function called from recurseOnAllNeighbors(), that will mark
// all connected spots with same CL codes as '0' in NOT_LM.
//
// Starting State: -> All spots are '1' in NOT_LM cube for cluster.
//
// Ending State: -> All spots are '0' in NOT_LM cube for cluster.
// ----------------------------------------------------------------------------------------
bool MA_VoxelCoding::clearNotLMCubeInCluster( Vect3usi &cur_coord, Vect3usi &nxt_coord )
{
if ( (MARK_cubes[NOT_LM]->get_spot( nxt_coord )) &&
(SS_cube->datac(cur_coord) == SS_cube->datac(nxt_coord)) )
{
// Mark the spot and return TRUE to indicate add spot to to-do queue
#if MA_FULL_TRACE_CLUSTER_MAX_PTS
if ( full_trace_enabled )
{
write_to_log( "TRACE (clearNotLMCubeInCluster) - Coordinate %v cleared in not LM.", &(nxt_coord) );
}
#endif
MARK_cubes[NOT_LM]->set_spot_0( nxt_coord );
return true;
}
else
{
// Return false, indicating invalid spot
return false;
}
}
// ----------------------------------------------------------------------------------------
// addToListLocalMaximumInCluster
//
// Description: A work function called from recurseOnAllNeighbors(), that adds all local
// maximums in current cluster to the 'current_max_list_ptr'.
//
// Starting State: -> Current Cluster is marked '1' in IN_QUEUE cube.
// -> All local maximums are '0' in NOT_LM cube.
//
// Ending State: -> Current Cluster is marked '0' in IN_QUEUE cube.
// -> Current Cluster is marked '1' in NOT_LM cube.
// ----------------------------------------------------------------------------------------
bool MA_VoxelCoding::addToListLocalMaximumInCluster( Vect3usi &cur_coord, Vect3usi &nxt_coord )
{
if ( (MARK_cubes[IN_QUEUE]->get_spot(nxt_coord)) &&
(SS_cube->datac(cur_coord) == SS_cube->datac(nxt_coord)) )
{
// If spot is local max, add to current max list
if ( !MARK_cubes[NOT_LM]->get_spot(nxt_coord) )
{
++ number_of_bs_maximums;
#if MA_FULL_TRACE_CLUSTER_MAX_PTS
if ( full_trace_enabled )
{
write_to_log( "TRACE (addToListLocalMaximumInCluster) - Coordinate %v added as LM.", &(nxt_coord) );
}
#endif
recurseOnAllNeighbors( nxt_coord, &MA_VoxelCoding::markSubClusterAsNotLocalMaximum );
current_max_list_ptr->insertAtStart( current_max_list_ptr->getNewNode() );
current_max_list_ptr->getHeadPtr()->item = nxt_coord;
}
// Clear IN_QUEUE cube spot and return TRUE to indicate add spot to to-do queue
#if MA_FULL_TRACE_CLUSTER_MAX_PTS
if ( full_trace_enabled )
{
write_to_log( "TRACE (addToListLocalMaximumInCluster) - Coordinate %v cleared in queue.", &(nxt_coord) );
}
#endif
MARK_cubes[IN_QUEUE]->set_spot_0( nxt_coord );
return true;
}
else
{
// Return false, indicating invalid spot
return false;
}
}
// ----------------------------------------------------------------------------------------
// reduceClustersLocalMaximumList
//
// Description: Given a list of a CL clusters local maximums, will remove any spots
// that are on a clusters corner unless there is only ONE max point left
// If there are max points close to each other, will keep the one with
// largest BS value.
// ----------------------------------------------------------------------------------------
void MA_VoxelCoding::reduceClustersLocalMaximumList( LinkedList<Vect3usi> *maximum_coord_list_ptr )
{
// If only one maximum coordinate, no need to reduce list
if ( maximum_coord_list_ptr->getSize() == 1 )
{
return;
}
char dx, dy, dz, pvx, pvy, pvz;
char xl, xg, yl, yg, zl, zg;
Vect3usi cur_coord, nei_coord;
LinkedListNode<Vect3usi> *cur_node_ptr = maximum_coord_list_ptr->getHeadPtr();
// Grab current clusters SS code
ss_t SS_code = SS_cube->datac( cur_node_ptr->item );
// Find max BS
bs_t clusters_max_bs = 0;
while ( (cur_node_ptr) && (SS_code == SS_cube->datac(cur_node_ptr->item)) )
{
if ( BS_cube->datac(cur_node_ptr->item) > clusters_max_bs)
{
clusters_max_bs = BS_cube->datac( cur_node_ptr->item );
}
cur_node_ptr = cur_node_ptr->next;
}
// Now go through entire list, doing the following:
// 1) Determine general direction of neighbors to current spot
// 2) If we are not in middle of plain, remove coordinate
cur_node_ptr = maximum_coord_list_ptr->getHeadPtr();
while ( (cur_node_ptr) && (SS_code == SS_cube->datac(cur_node_ptr->item)) )
{
// If there is only one coordinate left, we are done
if ( maximum_coord_list_ptr->getSize() == 1 )
{
return;
}
pvx=0; pvy=0; pvz=0;
cur_coord = cur_node_ptr->item;
// If largest BS code, then we can skip this coordinate
if ( BS_cube->datac(cur_coord) < (clusters_max_bs * 0.95f) )
{
// Bound check
xl=-1, xg=1, yl=-1, yg=1, zl=-1, zg=1;
if (cur_coord.x < 1) xl = 0;
if (cur_coord.y < 1) yl = 0;
if (cur_coord.z < 1) zl = 0;
if (cur_coord.x > boundary_cube->wX-2) xg = 0;
if (cur_coord.y > boundary_cube->wY-2) yg = 0;
if (cur_coord.z > boundary_cube->wZ-2) zg = 0;
// Sum up all directional vectors pointing at neighbors
for (dz = zl; dz <= zg; dz++)
for (dy = yl; dy <= yg; dy++)
for (dx = xl; dx <= xg; dx++)
{
// Make sure neighbor is part of current cluster
nei_coord.from_zyx(cur_coord.z+dz, cur_coord.y+dy, cur_coord.x+dx);
if ( SS_cube->datac(nei_coord) == SS_code )
{
pvx = pvx+dx;
pvy = pvy+dy;
pvz = pvz+dz;
}
}
}
// If we are on a corner, proj vector should have large mag, if plane, should be small or 0
if ( ((int)pvx*pvx + (int)pvy*pvy + (int)pvz*pvz) >= 1 )
{
++number_of_bs_maximums_removed;
if ( cur_node_ptr->next )
{ // Go on to next node, and remove the one we just finished
cur_node_ptr = cur_node_ptr->next;
maximum_coord_list_ptr->removeNode( cur_node_ptr->prev );
}
else
{ // Last spot, remove the node and set pointer to NULL to return
maximum_coord_list_ptr->removeNode( cur_node_ptr );
cur_node_ptr = NULL;
}
}
// We want to keep this max point, go on to next spot
else
{
cur_node_ptr = cur_node_ptr->next;
}
}
// Pass 2, for each coordinate find any close neighbors, and keep largest BS
// NOTE: This turned out to be a bad idea, because if we are approaching a branch
// there can be valid maximum points close to each other.
//LinkedListNode<Vect3usi> *tmp_node_ptr, *nxt_node_ptr;
//bs_t distance;
//cur_node_ptr = maximum_coord_list_ptr->getHeadPtr();
//while ( (cur_node_ptr) && (SS_code == SS_cube->datac(cur_node_ptr->item)) )
//{
// // Normalize and square the bs value
// distance = ( BS_cube->datac(cur_node_ptr->item)*BS_cube->datac(cur_node_ptr->item) )/( BS_Xfrm->getFaceValue()*BS_Xfrm->getFaceValue() );
// // Search for any neighbors within BS distance
// tmp_node_ptr = maximum_coord_list_ptr->getHeadPtr();
// while ( (tmp_node_ptr) && (SS_code == SS_cube->datac(tmp_node_ptr->item)) )
// {
// if ( (tmp_node_ptr != cur_node_ptr) &&
// (tmp_node_ptr->item.get_dist_2_to(cur_node_ptr->item) < distance) )
// {
// // Keep the larger BS coordinate
// if ( BS_cube->datac(cur_node_ptr->item) >= BS_cube->datac(tmp_node_ptr->item) )
// {
// // Only need to remove the temp node
// nxt_node_ptr = tmp_node_ptr->next;
// maximum_coord_list_ptr->removeNode( tmp_node_ptr );
// tmp_node_ptr = nxt_node_ptr;
// }
// else
// {
// // Need to remove current node
// nxt_node_ptr = cur_node_ptr->next;
// maximum_coord_list_ptr->removeNode( cur_node_ptr );
// if ( nxt_node_ptr == NULL )
// {
// // We are done
// return;
// }
// cur_node_ptr = nxt_node_ptr;
// tmp_node_ptr = maximum_coord_list_ptr->getHeadPtr();
// }
// ++ number_of_bs_maximums_removed_s2;
// }
// else
// {
// tmp_node_ptr = tmp_node_ptr->next;
// }
// }
// cur_node_ptr = cur_node_ptr->next;
//}
}