diff options
Diffstat (limited to 'source/blender/blenkernel/intern/depsgraph.c')
| -rw-r--r-- | source/blender/blenkernel/intern/depsgraph.c | 802 |
1 files changed, 582 insertions, 220 deletions
diff --git a/source/blender/blenkernel/intern/depsgraph.c b/source/blender/blenkernel/intern/depsgraph.c index 668b18c0913..9f0501d54fc 100644 --- a/source/blender/blenkernel/intern/depsgraph.c +++ b/source/blender/blenkernel/intern/depsgraph.c @@ -41,17 +41,25 @@ #include "BLI_blenlib.h" #include "BLI_arithb.h" +#include "DNA_action_types.h" +#include "DNA_armature_types.h" +#include "DNA_curve_types.h" #include "DNA_ID.h" +#include "DNA_effect_types.h" +#include "DNA_lattice_types.h" +#include "DNA_mesh_types.h" #include "DNA_object_types.h" +#include "DNA_object_force.h" #include "DNA_oops_types.h" #include "DNA_scene_types.h" -#include "DNA_action_types.h" #include "DNA_screen_types.h" #include "DNA_space_types.h" #include "DNA_view2d_types.h" -#include "BKE_utildefines.h" +#include "BKE_action.h" #include "BKE_global.h" +#include "BKE_mball.h" +#include "BKE_utildefines.h" #include "MEM_guardedalloc.h" #include "blendef.h" @@ -272,18 +280,16 @@ int queue_count(struct DagNodeQueue *queue){ DagForest * dag_init() { DagForest *forest; - - forest = MEM_mallocN(sizeof(DagForest),"DAG root"); - forest->DagNode.first = NULL; - forest->DagNode.last = NULL; - forest->numNodes = 0; + /* use callocN to init all zero */ + forest = MEM_callocN(sizeof(DagForest),"DAG root"); return forest; } -struct DagForest *build_dag(struct Scene *sce, short mask) +struct DagForest *build_dag(struct Scene *sce, short mask) { Base *base; Object *ob; + bConstraint *con; DagNode * node; DagNode * node2; DagNode * node3; @@ -299,130 +305,126 @@ struct DagForest *build_dag(struct Scene *sce, short mask) sce->theDag = dag; } - // add base node for scene. scene is always the first node in DAG + /* add base node for scene. scene is always the first node in DAG */ scenenode = dag_add_node(dag, sce); - /* targets in object struct yet to be added. should even they ? - struct Ipo *ipo; - ListBase nlastrips; - ListBase hooks; - */ - - - base = sce->base.first; - while(base) { // add all objects in any case + for(base = sce->base.first; base; base= base->next) { int addtoroot = 1; ob= (Object *) base->object; node = dag_get_node(dag,ob); - if ((ob->data) && (mask&DAG_RL_DATA_MASK)) { + if ((ob->data) && (mask&DAG_RL_DATA)) { node2 = dag_get_node(dag,ob->data); dag_add_relation(dag,node,node2,DAG_RL_DATA); node2->first_ancestor = ob; node2->ancestor_count += 1; - if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) { // add armature constraints to datas - if (ob->pose){ - bPoseChannel *pchan; - bConstraint *con; - Object * target; - - for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){ - for (con = pchan->constraints.first; con; con=con->next){ - if (constraint_has_target(con)) { - target = get_constraint_target(con); - if (strcmp(target->id.name, ob->id.name) != 0) { - //fprintf(stderr,"armature target :%s \n", target->id.name); - node3 = dag_get_node(dag,target); - dag_add_relation(dag,node3,node2,DAG_RL_CONSTRAINT); - } - } - } - } - } - } - if ((ob->hooks.first) && (mask&DAG_RL_HOOK)) { - ObHook *hook; + } + if (ob->type == OB_ARMATURE) { + if (ob->pose){ + bPoseChannel *pchan; + bConstraint *con; + Object * target; + char *subtarget; - for(hook= ob->hooks.first; hook; hook= hook->next) { - if(hook->parent) { - node3 = dag_get_node(dag,hook->parent); - dag_add_relation(dag,node3,node2,DAG_RL_HOOK); - } - } - } - } else { // add armature constraints to object itself - if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) { - if (ob->pose){ - bPoseChannel *pchan; - bConstraint *con; - Object * target; - - for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){ - for (con = pchan->constraints.first; con; con=con->next){ - if (constraint_has_target(con)) { - target = get_constraint_target(con); - if (strcmp(target->id.name, ob->id.name) != 0) { - //fprintf(stderr,"armature target :%s \n", target->id.name); - node3 = dag_get_node(dag,target); - dag_add_relation(dag,node3,node,DAG_RL_CONSTRAINT); - } + for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){ + for (con = pchan->constraints.first; con; con=con->next){ + if (constraint_has_target(con)) { + target = get_constraint_target(con, &subtarget); + if (target!=ob) { + // fprintf(stderr,"armature %s target :%s \n", ob->id.name, target->id.name); + node3 = dag_get_node(dag, target); + + dag_add_relation(dag,node3,node,DAG_RL_OB_DATA); + } } } } } - if ((ob->hooks.first) && (mask&DAG_RL_HOOK)) { - ObHook *hook; - - for(hook= ob->hooks.first; hook; hook= hook->next) { - if(hook->parent) { - node3 = dag_get_node(dag,hook->parent); - dag_add_relation(dag,node3,node,DAG_RL_HOOK); - } + } + if (ob->hooks.first) { + ObHook *hook; + + for(hook= ob->hooks.first; hook; hook= hook->next) { + if(hook->parent) { + node3 = dag_get_node(dag,hook->parent); + dag_add_relation(dag,node3,node,DAG_RL_OB_DATA); } - } + } } - - if ((ob->parent) && (mask&DAG_RL_PARENT_MASK)){ + if (ob->parent) { node2 = dag_get_node(dag,ob->parent); - dag_add_relation(dag,node2,node,DAG_RL_PARENT); + + switch(ob->partype) { + case PARSKEL: + dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB); + break; + case PARVERT1: case PARVERT3: case PARBONE: + dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB); + break; + default: + if(ob->parent->type==OB_LATTICE) + dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB); + else if(ob->parent->type==OB_CURVE) { + Curve *cu= ob->parent->data; + if(cu->flag & CU_PATH) + dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB); + else + dag_add_relation(dag,node2,node,DAG_RL_OB_OB); + } + else + dag_add_relation(dag,node2,node,DAG_RL_OB_OB); + } addtoroot = 0; } - if ((ob->track) && (mask&DAG_RL_TRACK_MASK)){ + if (ob->track) { node2 = dag_get_node(dag,ob->track); - dag_add_relation(dag,node2,node,DAG_RL_TRACK); + dag_add_relation(dag,node2,node,DAG_RL_OB_OB); addtoroot = 0; - } - if ((ob->path) && (mask&DAG_RL_PATH_MASK)){ - node2 = dag_get_node(dag,ob->track); - dag_add_relation(dag,node2,node,DAG_RL_PATH); - addtoroot = 0; - + if (ob->type==OB_MBALL) { + Object *mom= find_basis_mball(ob); + if(mom!=ob) { + node2 = dag_get_node(dag, mom); + dag_add_relation(dag,node,node2,DAG_RL_DATA_DATA|DAG_RL_OB_DATA); // mom depends on children! + } } - - /* Count constraints */ - if (mask & DAG_RL_CONSTRAINT_MASK) { - bConstraint *con; - for (con = ob->constraints.first; con; con=con->next){ - if (constraint_has_target(con)) { - node2 = dag_get_node(dag,get_constraint_target(con)); - dag_add_relation(dag,node2,node,DAG_RL_CONSTRAINT); - addtoroot = 0; - - } + else if (ob->type==OB_CURVE) { + Curve *cu= ob->data; + if(cu->bevobj) { + node2 = dag_get_node(dag, cu->bevobj); + dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA); } - } + if(cu->taperobj) { + node2 = dag_get_node(dag, cu->taperobj); + dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA); + } + } + else if(ob->type==OB_FONT) { + Curve *cu= ob->data; + if(cu->textoncurve) { + node2 = dag_get_node(dag, cu->textoncurve); + dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA); + } + } + for (con = ob->constraints.first; con; con=con->next){ + if (constraint_has_target(con)) { + char *str; + node2 = dag_get_node(dag, get_constraint_target(con, &str)); + if(con->type==CONSTRAINT_TYPE_FOLLOWPATH) + dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB); + else + dag_add_relation(dag, node2, node, DAG_RL_OB_OB); + addtoroot = 0; + } + } if (addtoroot == 1 ) dag_add_relation(dag,scenenode,node,DAG_RL_SCENE); - - addtoroot = 1; - base= base->next; } // cycle detection and solving @@ -458,18 +460,20 @@ void free_forest(DagForest *Dag) DagNode * dag_find_node (DagForest *forest,void * fob) { - DagNode *node = forest->DagNode.first; - - while (node) { - if (node->ob == fob) - return node; - node = node->next; - } - return NULL; + DagNode *node = forest->DagNode.first; + + while (node) { + if (node->ob == fob) + return node; + node = node->next; + } + return NULL; } +static int ugly_hack_sorry= 1; // prevent type check + /* no checking of existance, use dag_find_node first or dag_get_node */ -DagNode * dag_add_node (DagForest *forest,void * fob) +DagNode * dag_add_node (DagForest *forest, void * fob) { DagNode *node; @@ -486,7 +490,7 @@ DagNode * dag_add_node (DagForest *forest,void * fob) node->first_ancestor = NULL; node->ancestor_count = 0; - node->type = GS(((ID *) fob)->name); + if(ugly_hack_sorry) node->type = GS(((ID *) fob)->name); // sorry, done for pose sorting if (forest->numNodes) { ((DagNode *) forest->DagNode.last)->next = node; forest->DagNode.last = node; @@ -540,7 +544,7 @@ DagNode * dag_get_sub_node (DagForest *forest,void * fob) return node; } -void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, dag_rel_type rel) +void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel) { DagAdjList *itA = fob1->child; @@ -846,6 +850,7 @@ DagNodeQueue * graph_dfs(void) return(retqueue); } +/* unused */ int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) { DagNode *node; @@ -933,84 +938,6 @@ int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_a return(retval); } -// sort the base list on place -void topo_sort_baselist(struct Scene *sce){ - DagNode *node; - DagNodeQueue *nqueue; - DagAdjList *itA; - int time; - int skip = 0; - ListBase tempbase; - Base *base; - - tempbase.first= tempbase.last= 0; - - build_dag(sce,DAG_RL_ALL_BUT_DATA_MASK); - - nqueue = queue_create(DAGQUEUEALLOC); - - node = sce->theDag->DagNode.first; - while(node) { - node->color = DAG_WHITE; - node = node->next; - } - - time = 1; - - node = sce->theDag->DagNode.first; - - node->color = DAG_GRAY; - time++; - push_stack(nqueue,node); - - while(nqueue->count) { - - skip = 0; - node = get_top_node_queue(nqueue); - - itA = node->child; - while(itA != NULL) { - if((itA->node->color == DAG_WHITE) ) { - itA->node->DFS_dvtm = time; - itA->node->color = DAG_GRAY; - - time++; - push_stack(nqueue,itA->node); - skip = 1; - break; - } - itA = itA->next; - } - - if (!skip) { - if (node) { - node = pop_queue(nqueue); - if (node->ob == sce) // we are done - break ; - node->color = DAG_BLACK; - - time++; - base = sce->base.first; - while (base->object != node->ob) - base = base->next; - BLI_remlink(&sce->base,base); - BLI_addhead(&tempbase,base); - } - } - } - - // temporal correction for circular dependancies - base = sce->base.first; - while (base) { - BLI_remlink(&sce->base,base); - BLI_addhead(&tempbase,base); - base = sce->base.first; - } - - sce->base = tempbase; - queue_delete(nqueue); -} - // used to get the obs owning a datablock struct DagNodeQueue *get_obparents(struct DagForest *dag, void *ob) @@ -1020,7 +947,10 @@ struct DagNodeQueue *get_obparents(struct DagForest *dag, void *ob) DagAdjList *itA; node = dag_find_node(dag,ob); - if (node->ancestor_count == 1) { // simple case + if(node==NULL) { + return NULL; + } + else if (node->ancestor_count == 1) { // simple case nqueue = queue_create(1); push_queue(nqueue,node); } else { // need to go over the whole dag for adj list @@ -1082,7 +1012,7 @@ struct DagNodeQueue *get_all_childs(struct DagForest *dag, void *ob) int skip = 0; nqueue = queue_create(DAGQUEUEALLOC); - retqueue = queue_create(MainDag->numNodes); + retqueue = queue_create(dag->numNodes); // was MainDag... why? (ton) node = dag->DagNode.first; while(node) { @@ -1092,45 +1022,47 @@ struct DagNodeQueue *get_all_childs(struct DagForest *dag, void *ob) time = 1; - node = dag_find_node(dag,ob); - - node->color = DAG_GRAY; - time++; - push_stack(nqueue,node); - - while(nqueue->count) { + node = dag_find_node(dag,ob); // could be done in loop above (ton) + if(node) { // can be null for newly added objects - skip = 0; - node = get_top_node_queue(nqueue); - - itA = node->child; - while(itA != NULL) { - if((itA->node->color == DAG_WHITE) ) { - itA->node->DFS_dvtm = time; - itA->node->color = DAG_GRAY; - - time++; - push_stack(nqueue,itA->node); - skip = 1; - break; - } - itA = itA->next; - } + node->color = DAG_GRAY; + time++; + push_stack(nqueue,node); - if (!skip) { - node = pop_queue(nqueue); - node->color = DAG_BLACK; + while(nqueue->count) { - time++; - push_stack(retqueue,node); + skip = 0; + node = get_top_node_queue(nqueue); + + itA = node->child; + while(itA != NULL) { + if((itA->node->color == DAG_WHITE) ) { + itA->node->DFS_dvtm = time; + itA->node->color = DAG_GRAY; + + time++; + push_stack(nqueue,itA->node); + skip = 1; + break; + } + itA = itA->next; + } + + if (!skip) { + node = pop_queue(nqueue); + node->color = DAG_BLACK; + + time++; + push_stack(retqueue,node); + } } } - queue_delete(nqueue); return(retqueue); } -dag_rel_type are_obs_related(struct DagForest *dag, void *ob1, void *ob2) { +/* unused */ +short are_obs_related(struct DagForest *dag, void *ob1, void *ob2) { DagNode * node; DagAdjList *itA; @@ -1211,4 +1143,434 @@ void graph_print_adj_list(void) } } +/* ************************ API *********************** */ + +/* sort the base list on dependency order */ +void DAG_scene_sort(struct Scene *sce) +{ + DagNode *node; + DagNodeQueue *nqueue; + DagAdjList *itA; + int time; + int skip = 0; + ListBase tempbase; + Base *base; + + tempbase.first= tempbase.last= NULL; + + build_dag(sce, DAG_RL_ALL_BUT_DATA); + + nqueue = queue_create(DAGQUEUEALLOC); + + node = sce->theDag->DagNode.first; + while(node) { + node->color = DAG_WHITE; + node = node->next; + } + + time = 1; + + node = sce->theDag->DagNode.first; + + node->color = DAG_GRAY; + time++; + push_stack(nqueue,node); + + while(nqueue->count) { + + skip = 0; + node = get_top_node_queue(nqueue); + + itA = node->child; + while(itA != NULL) { + if((itA->node->color == DAG_WHITE) ) { + itA->node->DFS_dvtm = time; + itA->node->color = DAG_GRAY; + + time++; + push_stack(nqueue,itA->node); + skip = 1; + break; + } + itA = itA->next; + } + + if (!skip) { + if (node) { + node = pop_queue(nqueue); + if (node->ob == sce) // we are done + break ; + node->color = DAG_BLACK; + + time++; + base = sce->base.first; + while (base->object != node->ob) + base = base->next; + BLI_remlink(&sce->base,base); + BLI_addhead(&tempbase,base); + } + } + } + + // temporal correction for circular dependancies + base = sce->base.first; + while (base) { + BLI_remlink(&sce->base,base); + BLI_addhead(&tempbase,base); + //if(G.f & G_DEBUG) + printf("cyclic %s\n", base->object->id.name); + base = sce->base.first; + } + + sce->base = tempbase; + queue_delete(nqueue); + + if(G.f & G_DEBUG) { + printf("\nordered\n"); + for(base = sce->base.first; base; base= base->next) { + printf(" %s\n", base->object->id.name); + } + } +} + +/* node was checked to have lasttime != curtime and is if type ID_OB */ +static void flush_update_node(DagNode *node, unsigned int layer, int curtime) +{ + DagAdjList *itA; + Object *ob, *obc; + int oldflag, changed=0; + unsigned int all_layer; + + node->lasttime= curtime; + + ob= node->ob; + if(ob->recalc & OB_RECALC) { + all_layer= ob->lay; + /* got an object node that changes, now check relations */ + for(itA = node->child; itA; itA= itA->next) { + all_layer |= itA->lay; + /* the relationship is visible */ + if(itA->lay & layer) { + if(itA->node->type==ID_OB) { + obc= itA->node->ob; + oldflag= obc->recalc; + + /* got a ob->obc relation, now check if flag needs flush */ + if(ob->recalc & OB_RECALC_OB) { + if(itA->type & DAG_RL_OB_OB) { + //printf("ob %s changes ob %s\n", ob->id.name, obc->id.name); + obc->recalc |= OB_RECALC_OB; + } + if(itA->type & DAG_RL_OB_DATA) { + //printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name); + obc->recalc |= OB_RECALC_DATA; + } + } + if(ob->recalc & OB_RECALC_DATA) { + if(itA->type & DAG_RL_DATA_OB) { + //printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name); + obc->recalc |= OB_RECALC_OB; + } + if(itA->type & DAG_RL_DATA_DATA) { + //printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name); + obc->recalc |= OB_RECALC_DATA; + } + } + if(oldflag!=obc->recalc) changed= 1; + } + } + } + /* even nicer, we can clear recalc flags... but we don't for armatures, these can have poses that need pointer checks (read old file issue) */ + if(ob->type!=OB_ARMATURE) + if((all_layer & layer)==0) + ob->recalc &= ~OB_RECALC; + } + else{ + /* Object has not RECALC flag */ + /* check case where child changes and parent forcing obdata to change */ + /* could merge this in with loop above... (ton) */ + for(itA = node->child; itA; itA= itA->next) { + /* the relationship is visible */ + if(itA->lay & layer) { + if(itA->node->type==ID_OB) { + obc= itA->node->ob; + /* child moves */ + if((obc->recalc & OB_RECALC)==OB_RECALC_OB) { + /* parent has deforming info */ + if(itA->type & (DAG_RL_OB_DATA|DAG_RL_DATA_DATA)) { + // printf("parent %s changes ob %s\n", ob->id.name, obc->id.name); + obc->recalc |= OB_RECALC_DATA; + } + } + } + } + } + } + /* we only go deeper if node not checked or something changed */ + for(itA = node->child; itA; itA= itA->next) { + if(changed || itA->node->lasttime!=curtime) + flush_update_node(itA->node, layer, curtime); + } +} + +/* node was checked to have lasttime != curtime , and is of type ID_OB */ +static unsigned int flush_layer_node(DagNode *node, int curtime) +{ + DagAdjList *itA; + + node->lasttime= curtime; + node->lay= ((Object *)node->ob)->lay; + + for(itA = node->child; itA; itA= itA->next) { + if(itA->node->type==ID_OB) { + if(itA->node->lasttime!=curtime) { + itA->lay= flush_layer_node(itA->node, curtime); // lay is only set once for each relation + //printf("layer %d for relation %s to %s\n", itA->lay, ((Object *)node->ob)->id.name, ((Object *)itA->node->ob)->id.name); + } + else itA->lay= itA->node->lay; + + node->lay |= itA->lay; + } + } + + return node->lay; +} + +/* flushes all recalc flags in objects down the dependency tree */ +void DAG_scene_flush_update(Scene *sce) +{ + DagNode *firstnode; + DagAdjList *itA; + int lasttime; + + firstnode= sce->theDag->DagNode.first; // always scene node + + /* first we flush the layer flags */ + sce->theDag->time++; // so we know which nodes were accessed + lasttime= sce->theDag->time; + for(itA = firstnode->child; itA; itA= itA->next) { + if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) + flush_layer_node(itA->node, lasttime); + } + + /* then we use the relationships + layer info to flush update events */ + sce->theDag->time++; // so we know which nodes were accessed + lasttime= sce->theDag->time; + for(itA = firstnode->child; itA; itA= itA->next) { + if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) + flush_update_node(itA->node, sce->lay, lasttime); + } +} + +/* flag all objects that need recalc, for changes in time for example */ +void DAG_scene_update_flags(Scene *sce, unsigned int lay) +{ + Base *base; + Object *ob; + + /* set ob flags where animated systems are */ + for(base= sce->base.first; base; base= base->next) { + + /* now if DagNode were part of base, the node->lay could be checked... */ + /* we do all now, since the scene_flush checks layers */ + //if((base->lay & lay)) { + ob= base->object; + + if(ob->ipo) ob->recalc |= OB_RECALC_OB; + else if(ob->constraints.first) ob->recalc |= OB_RECALC_OB; + else if(ob->scriptlink.totscript) ob->recalc |= OB_RECALC_OB; + else if(ob->parent) { + if(ob->parent->type==OB_CURVE) ob->recalc |= OB_RECALC_OB; + } + + if(ob->action) ob->recalc |= OB_RECALC_DATA; + else if(ob->nlastrips.first) ob->recalc |= OB_RECALC_DATA; + else if(ob->softflag & OB_SB_ENABLE) ob->recalc |= OB_RECALC_DATA; + else { + Mesh *me; + Curve *cu; + Lattice *lt; + + switch(ob->type) { + case OB_MESH: + me= ob->data; + if(me->key) ob->recalc |= OB_RECALC_DATA; + else if(ob->effect.first) { + Effect *eff= ob->effect.first; + if(eff->type==EFF_WAVE) ob->recalc |= OB_RECALC_DATA; + } + break; + case OB_CURVE: + case OB_SURF: + cu= ob->data; + if(cu->key) ob->recalc |= OB_RECALC_DATA; + break; + case OB_LATTICE: + lt= ob->data; + if(lt->key) ob->recalc |= OB_RECALC_DATA; + break; + } + } + //} + } + DAG_scene_flush_update(sce); +} + +/* flag this object and all its relations to recalc */ +/* if you need to do more objects, tag object yourself and + use DAG_scene_flush_update() in end */ +void DAG_object_flush_update(Scene *sce, Object *ob, short flag) +{ + Base *base; + + if(ob==NULL) return; + ob->recalc |= flag; + + /* all users of this ob->data should be checked */ + if(flag & OB_RECALC_DATA) { + ID *id= ob->data; + if(id && id->us>1) { + for (base= sce->base.first; base; base= base->next) { + if (ob->data==base->object->data) { + base->object->recalc |= OB_RECALC_DATA; + } + } + } + } + + DAG_scene_flush_update(sce); +} + +/* ******************* DAG FOR ARMATURE POSE ***************** */ + +/* we assume its an armature with pose */ +void DAG_pose_sort(Object *ob) +{ + bPose *pose= ob->pose; + bPoseChannel *pchan; + bConstraint *con; + DagNode *node; + DagNode *node2, *node3; + DagNode *rootnode; + DagForest *dag; + DagNodeQueue *nqueue; + DagAdjList *itA; + ListBase tempbase; + int skip = 0; + + dag = dag_init(); + ugly_hack_sorry= 0; // no ID structs + + rootnode = dag_add_node(dag, NULL); // node->ob becomes NULL + + /* we add the hierarchy and the constraints */ + for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) { + int addtoroot = 1; + + node = dag_get_node(dag, pchan); + + if(pchan->parent) { + node2 = dag_get_node(dag, pchan->parent); + dag_add_relation(dag, node2, node, 0); + addtoroot = 0; + } + for (con = pchan->constraints.first; con; con=con->next){ + if (constraint_has_target(con)) { + char *subtarget; + Object *target = get_constraint_target(con, &subtarget); + + if (target==ob && subtarget) { + bPoseChannel *target= get_pose_channel(ob->pose, subtarget); + if(target) { + node2= dag_get_node(dag, target); + dag_add_relation(dag, node2, node, 0); + + if(con->type==CONSTRAINT_TYPE_KINEMATIC) { + bPoseChannel *par= pchan->parent; + + while(par) { + node3= dag_get_node(dag, par); + dag_add_relation(dag, node2, node3, 0); + + if(par->bone->flag & BONE_IK_TOPARENT) + par= par->parent; + else break; + } + } + } + } + } + } + if (addtoroot == 1 ) + dag_add_relation(dag, rootnode, node, 0); + } + + /* now we try to sort... */ + tempbase.first= tempbase.last= NULL; + + nqueue = queue_create(DAGQUEUEALLOC); + + /* tag nodes unchecked */ + for(node = dag->DagNode.first; node; node= node->next) + node->color = DAG_WHITE; + + node = dag->DagNode.first; + + node->color = DAG_GRAY; + push_stack(nqueue, node); + + while(nqueue->count) { + + skip = 0; + node = get_top_node_queue(nqueue); + + itA = node->child; + while(itA != NULL) { + if((itA->node->color == DAG_WHITE) ) { + itA->node->color = DAG_GRAY; + push_stack(nqueue,itA->node); + skip = 1; + break; + } + itA = itA->next; + } + + if (!skip) { + if (node) { + node = pop_queue(nqueue); + if (node->ob == NULL) // we are done + break ; + node->color = DAG_BLACK; + + /* put node in new list */ + BLI_remlink(&pose->chanbase, node->ob); + BLI_addhead(&tempbase, node->ob); + } + } + } + + // temporal correction for circular dependancies + while(pose->chanbase.first) { + pchan= pose->chanbase.first; + BLI_remlink(&pose->chanbase, pchan); + BLI_addhead(&tempbase, pchan); + + printf("cyclic %s\n", pchan->name); + } + + pose->chanbase = tempbase; + queue_delete(nqueue); + +// printf("\nordered\n"); +// for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) { +// printf(" %s\n", pchan->name); +// } + + free_forest( dag ); + MEM_freeN( dag ); + + ugly_hack_sorry= 1; +} + + |