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_*/