BLI_graph.h

Go to the documentation of this file.

#ifndef BLI_GRAPH_H_
#define BLI_GRAPH_H_

#include "DNA_listBase.h"

struct BGraph;
struct BNode;
struct BArc;

struct RadialArc;

typedef void (*FreeArc)(struct BArc*);
typedef void (*FreeNode)(struct BNode*);
typedef void (*RadialSymmetry)(struct BNode* root_node, struct RadialArc* ring, int total);
typedef void (*AxialSymmetry)(struct BNode* root_node, struct BNode* node1, struct BNode* node2, struct BArc* arc1, struct BArc* arc2);

/* IF YOU MODIFY THOSE TYPES, YOU NEED TO UPDATE ALL THOSE THAT "INHERIT" FROM THEM
 * 
 * RigGraph, ReebGraph
 * 
 * */

typedef struct BGraph {
        ListBase        arcs;
        ListBase        nodes;
        
        float length;
        
        /* function pointer to deal with custom fonctionnality */
        FreeArc                 free_arc;
        FreeNode                free_node;
        RadialSymmetry  radial_symmetry;
        AxialSymmetry   axial_symmetry;
} BGraph;

typedef struct BNode {
        void *next, *prev;
        float p[3];
        int flag;

        int degree;
        struct BArc **arcs;
        
        int subgraph_index;

        int symmetry_level;
        int symmetry_flag;
        float symmetry_axis[3];
} BNode;

typedef struct BArc {
        void *next, *prev;
        struct BNode *head, *tail;
        int flag;

        float length;

        int symmetry_level;
        int symmetry_group;
        int symmetry_flag;
} BArc;

struct BArcIterator;

void* IT_head(void* iter);
void* IT_tail(void* iter);
void* IT_peek(void* iter, int n);
void* IT_next(void* iter);
void* IT_nextN(void* iter, int n);
void* IT_previous(void* iter);
int   IT_stopped(void* iter);

typedef void* (*HeadFct)(void* iter);
typedef void* (*TailFct)(void* iter);
typedef void* (*PeekFct)(void* iter, int n);
typedef void* (*NextFct)(void* iter);
typedef void* (*NextNFct)(void* iter, int n);
typedef void* (*PreviousFct)(void* iter);
typedef int   (*StoppedFct)(void* iter);

typedef struct BArcIterator {
        HeadFct         head;
        TailFct         tail;
        PeekFct         peek;
        NextFct         next;
        NextNFct        nextN;
        PreviousFct     previous;
        StoppedFct      stopped;
        
        float *p, *no;
        float size;
        
        int length;
        int index;
} BArcIterator;

/* Helper structure for radial symmetry */
typedef struct RadialArc
{
        struct BArc *arc; 
        float n[3]; /* normalized vector joining the nodes of the arc */
} RadialArc;

BNode *BLI_otherNode(BArc *arc, BNode *node);

void BLI_freeNode(BGraph *graph, BNode *node);
void BLI_removeNode(BGraph *graph, BNode *node);

void BLI_removeArc(BGraph *graph, BArc *arc);

void BLI_flagNodes(BGraph *graph, int flag);
void BLI_flagArcs(BGraph *graph, int flag);

int BLI_hasAdjacencyList(BGraph *rg);
void BLI_buildAdjacencyList(BGraph *rg);
void BLI_rebuildAdjacencyList(BGraph* rg);
void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node);
void BLI_freeAdjacencyList(BGraph *rg);

int BLI_FlagSubgraphs(BGraph *graph);
void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph);

#define SHAPE_RADIX 10 /* each shape level is encoded this base */

int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root);
float BLI_subtreeLength(BNode *node);
void BLI_calcGraphLength(BGraph *graph);

void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced);
void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced);
void BLI_removeDoubleNodes(BGraph *graph, float limit);
BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit);

BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v);

int     BLI_isGraphCyclic(BGraph *graph);

/*------------ Symmetry handling ------------*/
void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit);

void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]);

/* BNode symmetry flags */
#define SYM_TOPOLOGICAL 1
#define SYM_PHYSICAL    2

/* the following two are exclusive */
#define SYM_AXIAL               4
#define SYM_RADIAL              8

/* BArc symmetry flags
 * 
 * axial symetry sides */
#define SYM_SIDE_POSITIVE               1
#define SYM_SIDE_NEGATIVE               2
/* Anything higher is the order in radial symmetry */
#define SYM_SIDE_RADIAL                 3

#endif /*BLI_GRAPH_H_*/