#pragma once
#include "afxwin.h"
#include "MedialAxisDefines.h"
#include "DistanceTransform.h"
#include "DS_1b_cube.h"
#include "vect3usi.h"
#include "LinkedList.h"
#include "NetworkGraph.h"
#include "useful_inlined_functions.h"
using namespace std;
// See MedialAxisDefines.h for type definitions
// ========================================================================================
// Support structures for Medial Axis
// ----------------------------------------------------------------------------------------
// Bits to indicate type of cluster
typedef char cl_flags;
#define CLUSTER_TYPE_NULL 0x01
#define CLUSTER_TYPE_LOCAL_MAX 0x02
#define CLUSTER_TYPE_MERGING 0x04
#define CLUSTER_TYPE_DIVIDING 0x08
#define CLUSTER_TYPE_RP 0x10
#define CLUSTER_TYPE_BRANCHING ( CLUSTER_TYPE_MERGING | CLUSTER_TYPE_DIVIDING )
class ClusterGraphNode
{
public:
// Constructor and destructor
ClusterGraphNode( )
{
ID = 0;
size = 0;
cluster_type = CLUSTER_TYPE_NULL;
max_coord_list_ptr = new LinkedList<Vect3usi>( 0 );
s_list_ptr = new LinkedList<cl_t>( 0 );
l_list_ptr = new LinkedList<cl_t>( 0 );
};
~ClusterGraphNode( )
{
delete max_coord_list_ptr;
delete s_list_ptr;
delete l_list_ptr;
};
// Cluster nodes ID, initially 0
cl_t ID;
// SS code of this cluster
ss_t SS_code;
// Cluster type (initially CLUSTER_TYPE_NULL)
cl_flags cluster_type;
// Size of cluster (in voxels)
unsigned int size;
// Volume cluster belongs to
v_id volume_indx;
// A list of coordinates that are local maximum within the cluster
LinkedList<Vect3usi> *max_coord_list_ptr;
// Cluser ID lists of smaller SS and larger SS neighbors of this cluster
LinkedList<cl_t> *s_list_ptr;
LinkedList<cl_t> *l_list_ptr;
};
// ----------------------------------------------------------------------------------------
typedef enum path_node_type
{
COORD_NODE = 0,
LINK_NODE,
} path_node_type;
class PathNode
{
public:
PathNode() { type = COORD_NODE; };
~PathNode() { };
Vect3usi coordinate;
cl_t from_branch_cluster_id;
path_node_type type;
};
// ----------------------------------------------------------------------------------------
class MedialPathVolumeInfo
{
public:
MedialPathVolumeInfo()
{
medial_paths_list = new LinkedList<LinkedList<PathNode>*>( MA_PREALLOC_MA_GROUPS );
medial_paths_array = NULL;
walls_to_destroy_at_start_array = NULL;
wall_off_start_array = NULL;
wall_off_between_array = NULL;
wall_off_end_array = NULL;
};
~MedialPathVolumeInfo()
{
if ( medial_paths_list )
delete medial_paths_list;
if ( medial_paths_array )
{
for ( unsigned int i = 0; i < number_of_medial_paths; i++ )
{
delete medial_paths_array[i];
}
delete[] medial_paths_array;
}
if ( walls_to_destroy_at_start_array )
delete[] walls_to_destroy_at_start_array;
if ( wall_off_start_array )
delete[] wall_off_start_array;
if ( wall_off_between_array )
delete[] wall_off_between_array;
if ( wall_off_end_array )
delete[] wall_off_end_array;
};
unsigned int number_of_medial_paths;
LinkedList<LinkedList<PathNode>*> *medial_paths_list;
LinkedList<PathNode> **medial_paths_array;
LinkedList<Vect3usi> *walls_to_destroy_at_start_array;
LinkedList<Vect3usi> *wall_off_start_array;
LinkedList<Vect3usi> *wall_off_between_array;
LinkedList<Vect3usi> *wall_off_end_array;
};
// ----------------------------------------------------------------------------------------
// ========================================================================================
// ========================================================================================
// ---------------------------------------------------------------
// Options available to Medial Axis generation
typedef unsigned int ma_options;
#define MA_OPTIONS_NONE 0
#define MA_BOUNDARY_IS_SOLID 0x00000001 // Cube boundary is a wall rather than internal mirror
#define MA_USE_MAX_BS_FOR_RP 0x00000002 // Default is to generate SS field and use furthest point for RP
// Output options (cubes)
#define MA_SAVE_SS_GRAY 0x00000010 // SS (single seed) distance transform cube
#define MA_SAVE_SS_RGB 0x00000020
#define MA_SAVE_BS_GRAY 0x00000040 // BS (boarder seed) distance transform cube
#define MA_SAVE_BS_RGB 0x00000080
#define MA_SAVE_CL_GRAY 0x00000100 // Cluster cube
#define MA_SAVE_CL_RGB 0x00000200
#define MA_SAVE_CL_MARKED 0x00000400 // Detailed cluster cube, highlights cluster types and max pts (Saved in "Cluster cube" formats)
#define MA_SAVE_SP_CUBE 0x00000800 // Shortest paths cube
#define MA_SAVE_MA_CUBE 0x00001000 // 1-bit cube with medial axis marked
#define MA_SAVE_MA_DETAILED 0x00002000 // ss_t medial axis cube with fibers marked, and each axis marked with it's path id
#define MA_SAVE_MA_GRAPH 0x00004000 // 1-bit cube with final medial axis graph marked (graph is used for results)
#define MA_SAVE_NETWORK_TXT 0x00008000 // Dumps network graph in text form to file
// Log detail options
#define MA_LOG_DELETED_PATHS 0x10000000
#define MA_LOG_FORCED_LINKS 0x20000000
// ---------------------------------------------------------------
// Possible return status
typedef enum ma_status
{
MA_NO_ERRORS = 0,
MA_FILE_OPEN_ERROR,
MA_NO_MEDIAL_AXIS_FOUND,
MA_UNKNOWN_ERROR
} ma_status;
class MA_VoxelCoding
{
// ---------------------------------------------------------------
// Typedefs internal to medial axis object
typedef unsigned int ma_settings;
#define BS_IS_PRELOADED 0x01
#define SS_IS_PRELOADED 0x02
#define CL_IS_PRELOADED 0x04
#define MA_IS_PRELOADED 0x08
typedef enum ma_direction
{
LEFT = 0,
RIGHT,
SOUTH,
NORTH,
DOWN,
UP
} ma_direction;
typedef enum ma_wall_action
{
CREATE = 0,
DESTROY
} ma_wall_action;
typedef enum ma_link_type
{
NORMAL = 0,
TO_PATH,
FROM_PATH,
REVERSE
} ma_link_type;
typedef bool(MA_VoxelCoding::*InnerOpPtr)( Vect3usi &cur_coord, Vect3usi &nxt_coord );
// ---------------------------------------------------------------
// Public access functions
public:
MA_VoxelCoding(DS_1b_cube *ds_cube_ptr, CEdit *prog_text, CProgressCtrl *prog_bar);
~MA_VoxelCoding(void);
// Functions for changing settings
ma_status preloadBSCube( char *file_name );
ma_status preloadSSCube( char *file_name );
ma_status preloadCLCube( char *file_name );
ma_status preloadMACube( char *file_name );
void enableCachingFromDisc( unsigned int memory_limit_in_mb );
void changeNodeDistributionCubeSize( float size_in_um );
void changePixelSize( float size_in_um );
// Function to start analysis using current settings
ma_status runMedialAxis( ma_options run_options, char *output_prefix );
// ---------------------------------------------------------------
// Private functions
private:
void prepareForRun( );
void cleanUpAfterRun( );
bool findNextStartingPt( Vect3usi &begin_scan_pt, Vect3usi &ret_start_pt );
void generateFullSS( );
void generateClusterCube( );
void findLocalMaximumsInCluster( Vect3usi &member_coord, LinkedList<Vect3usi> *max_list_ptr );
void reduceClustersLocalMaximumList( LinkedList<Vect3usi> *maximum_coord_list_ptr );
void findMidPtOfIntersection( Vect3usi &start_coord );
void travelDesiredOffsetInIntersection( int lr_off, int sn_off, int du_off, Vect3usi &cur_coord, Vect3usi &ret_end_coord );
int findDepthOfCone( ma_direction direction, Vect3usi &cur_coord );
int recurseInConeIfValid( ma_direction direction, Vect3usi &cur_coord, Vect3usi &nxt_coord );
void generateClusterGraph( );
void insertStartingPointIntoShortestPaths( Vect3usi &coord, v_id volume_id );
int countInListSameSS( LinkedList<cl_t> *node_list, ss_t ssid, v_id volume );
void determineClustersVolumes();
void removeFromMergingCluster( cl_t remove_cluster_id );
void removeFromDividingCluster( cl_t remove_cluster_id );
void traceShortestPaths( );
int findNearestCoordinateInList( Vect3usi &coord_near_to, LinkedList<Vect3usi> *max_list_ptr, Vect3usi &max_nearest );
int findMaxBSCoordinateInList( LinkedList<Vect3usi> *max_list_ptr, Vect3usi &max_bs_coord);
void editSSClusterWall( LinkedList<Vect3usi> *cluster_coordinates, ma_wall_action action );
void centerPathInReverse( LinkedList<PathNode> *path_ptr,
LinkedListNode<PathNode> *path_end_ptr,
LinkedListNode<PathNode> *path_start_ptr );
void traceMedialAxis( );
LinkedListNode<PathNode>* findNextMedialCoordinate( LinkedList<PathNode> *path_ptr,
LinkedListNode<PathNode> *first_node_ptr,
ma_link_type &returned_link_type,
LinkedListNode<PathNode> *reverse_tie_breaker_node_ptr );
bool attemptDirectLinearLink( LinkedList<PathNode> *path_ptr, LinkedListNode<PathNode> *start_node_ptr );
void linkUsingShortestPathToNextPathNode(LinkedList<PathNode> *path_ptr, LinkedListNode<PathNode> *start_node_ptr);
bool linkDirectlyWithNextPathNode( LinkedList<PathNode> *path_ptr, LinkedListNode<PathNode> *start_node_ptr );
LinkedListNode<PathNode>* linkPointToPoint( LinkedList<PathNode> *path_ptr,
LinkedListNode<PathNode> *start_node_ptr,
ma_link_type link_type=NORMAL );
LinkedListNode<PathNode>* linkPointToPath( LinkedList<PathNode> *path_ptr,
LinkedListNode<PathNode> *start_node_ptr,
bool link_with_previous );
void doSingleShortestPath( LinkedList<PathNode> *path_ptr, LinkedListNode<PathNode> *start_node_ptr, bool do_in_reverse );
void findMaxBSInMedialPath( Vect3usi &path_coord );
void convertPathTo26Linked( LinkedList<PathNode> *path_ptr );
// Analysis functions
ma_status performAnalysis( char *output_prefix );
void generateNetworkGraph( );
void findGraphNodesNeighbors( LinkedList<NetworkGraphNode*> *Q, NetworkGraph *G, NetworkGraphNode *N );
void mergeAllTwoDegreeNodes( );
// Utility functions
void recurseOnAllNeighbors( Vect3usi &start_coord, InnerOpPtr functionToDoPtr );
void recurseOnFaceNeighbors( Vect3usi &start_coord, InnerOpPtr functionToDoPtr );
bool hasMedialAxisNeighbors( Vect3usi &around_this_coord, Vect3usi &nearest_to );
void markPathInCube( LinkedList<PathNode> *path_ptr, DS_1b_cube *cube_to_mark_in, bool mark_val );
void markPathInSSCube( LinkedList<PathNode> *path_ptr, ss_t mark_value );
void removeCoordinateFromList( LinkedList<Vect3usi> *list_ptr, Vect3usi &coordinate );
void moveOffOfMedialAxis( Vect3usi &coordinate );
// Inner work functions for recurseOnAllNeighbors() and recurseOnFaceNeighbors() wrappers
bool markSingleClusterInCL( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool findMaxBSInVolume( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool determineClustersInVolume( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool markAllButLocalMaximumsAndAddNeighbors( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool markSubClusterAsNotLocalMaximum( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool clearNotLMCubeInCluster( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool addToListLocalMaximumInCluster( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool markSingleClusterInMarkCube( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool markSSClusterWall( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool clearSmoothCube( Vect3usi &cur_coord, Vect3usi &nxt_coord );
bool markTraveledAndAddCoordinateToGraphNode( Vect3usi &cur_coord, Vect3usi &nxt_coord );
// Output functions
void writeToFileBS( char *output_prefix, ma_options save_options );
void writeToFileSS( char *output_prefix, ma_options save_options );
void writeToFileCL( char *output_prefix, ma_options save_options );
void writeToFileShortestPaths( char *output_prefix, ma_options save_options );
void writeToFileMedialPaths( char *output_prefix, ma_options save_options );
void doFullDump( bool is_fatal );
// ---------------------------------------------------------------
// Variables used during algorithm execution
// External pointers, should not be modified
DS_1b_cube *boundary_cube;
// Progress bar and text
CEdit *progress_win_ptr;
CProgressCtrl *progress_bar_ptr;
// Current user specified options
ma_options run_options;
char *result_file_prefix;
ma_settings run_settings;
unsigned int delete_sp_below_size;
float merge_nodes_bs_multiplier;
float pixel_size_in_um;
float node_distribution_cube_size_in_um;
// Memory info
UINT64 memory_limit_total_bytes;
UINT64 memory_limit_bs_bytes;
UINT64 memory_limit_ss_bytes;
UINT64 memory_limit_cl_bytes;
// All cubes that will be allocated and used
DSt_cube<bs_t> *BS_cube;
DSt_cube<ss_t> *SS_cube;
DSt_cube<cl_t> *CL_cube;
#define TOTAL_MARK_CUBES 2
DS_1b_cube *MARK_cubes[ TOTAL_MARK_CUBES ];
#define NOT_LM 0 // For finding clusters max points
#define FINAL_MA 0 // For analysis graph generation
#define IN_QUEUE 1 // For finding clusters max points
#define SMOOTHING 1 // For converting a path to 26-linked
#define TRAVELED 1 // For analysis graph generation
// We will use different transforms for BS and SS fields, because SS can get much higher values.
// So we might want to have an 8-bit/16-bit combo.
DistanceXfrm<bs_t> *BS_Xfrm;
DistanceXfrm<ss_t> *SS_Xfrm;
// Used for converting a medial path from face connected to fully connected.
DistanceXfrm<ss_t> *SS_Xfrm_Smooth;
// Used for generating final medial axis graph.
DistanceXfrm<ss_t> *SS_Xfrm_Axis;
ss_t ss_infinity;
ss_t ss_medial_path; // One less than infinity, used to mark MA in SS cube
int current_recursion;
// ---------------------------------------------------------------
// Allocated items for various use
// Group of available preallocated coordinate queues for recursion use.
GroupedLists<int, Vect3usi> *recursion_queue;
LinkedList<Vect3usi> *coordinate_queue;
LinkedList<Vect3usi> *max_points_list;
LinkedList<LinkedList<Vect3usi>> *clusters_max_points_lists;
LinkedList<NetworkGraphNode*> *graph_node_queue;
// All cluster nodes for cluster graph
ClusterGraphNode *cluster_nodes_array;
// Data type properties
FindUsefulTypeProperties<cl_t> CL_type_properties;
FindUsefulTypeProperties<ss_t> SS_type_properties;
FindUsefulTypeProperties<bs_t> BS_type_properties;
MedialPathVolumeInfo *medial_path_volumes;
NetworkGraph *medial_axis_graphs_array;
// ---------------------------------------------------------------
// Statistics Variables, some of these are used in functions
unsigned int number_of_volumes; // This indicates the number of disconnected medial axis groups, i.e. pores
unsigned int number_of_graphs; // This indicates the final number of disconnected medial axis graphs
unsigned int number_of_bs_maximums;
unsigned int number_of_bs_maximums_removed;
unsigned int number_of_bs_maximums_removed_s2;
cl_t number_of_clusters; // Indicates total number of clusters
cl_t number_of_local_max_clusters;
cl_t number_of_merging_clusters;
cl_t number_of_merging_clusters_removed;
cl_t number_of_dividing_clusters;
cl_t number_of_dividing_clusters_removed;
cl_t number_of_rp_clusters;
cl_t number_of_failed_ma_links;
cl_t number_of_failed_ma_path_links;
unsigned int number_of_medial_paths_total;
// ---------------------------------------------------------------
// Method/Function specific variables
cl_t current_mark_value; // markSingleClusterInMarkCube(), markSingleClusterInCL()
DSt_cube<unsigned char> *out_marked_cube; // markSingleClusterInMarkCube() - Only resides temporarily
v_id current_volume_number; // determineClustersVolumes()
Vect3usi current_max_bs_coord; // findNextStartingPt(), findMaxBSInVolume()
bs_t current_max_bs_value; // findNextStartingPt(), findMaxBSInVolume()
cl_t current_cluster_id; // generateClusterGraph()
LinkedList<Vect3usi> *current_max_list_ptr; // findLocalMaximumsInCluster()
bool creating_ss_wall; // editSSClusterWall()
NetworkGraphNode *current_graph_node; // markTraveledAndAddCoordinateToGraphNode()
unsigned int current_medial_path_num;
unsigned int current_volume_num;
Vect3usi queue_mark_coord;
#if MA_DO_FULL_TRACE
// This can be used to enable/disable full trace on the fly during debugging
bool full_trace_enabled;
char trace_text_buffer[MAX_LOG_ENTRY_LENGTH];
#endif
};