Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenkernel/intern/depsgraph.c
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenkernel/intern/depsgraph.c')
-rw-r--r--source/blender/blenkernel/intern/depsgraph.c548
1 files changed, 2 insertions, 546 deletions
diff --git a/source/blender/blenkernel/intern/depsgraph.c b/source/blender/blenkernel/intern/depsgraph.c
index 8c55ad02dc6..68bdf8a8100 100644
--- a/source/blender/blenkernel/intern/depsgraph.c
+++ b/source/blender/blenkernel/intern/depsgraph.c
@@ -278,22 +278,11 @@ DagNode *pop_queue(DagNodeQueue *queue)
}
}
-void *pop_ob_queue(struct DagNodeQueue *queue)
-{
- return(pop_queue(queue)->ob);
-}
-
DagNode *get_top_node_queue(DagNodeQueue *queue)
{
return queue->first->node;
}
-int queue_count(struct DagNodeQueue *queue)
-{
- return queue->count;
-}
-
-
DagForest *dag_init(void)
{
DagForest *forest;
@@ -1190,539 +1179,6 @@ static void dag_check_cycle(DagForest *dag)
}
}
-/*
- * MainDAG is the DAG of all objects in current scene
- * used only for drawing there is one also in each scene
- */
-static DagForest *MainDag = NULL;
-
-DagForest *getMainDag(void)
-{
- return MainDag;
-}
-
-
-void setMainDag(DagForest *dag)
-{
- MainDag = dag;
-}
-
-
-/*
- * note for BFS/DFS
- * in theory we should sweep the whole array
- * but in our case the first node is the scene
- * and is linked to every other object
- *
- * for general case we will need to add outer loop
- */
-
-/*
- * ToDo : change pos kludge
- */
-
-/* adjust levels for drawing in oops space */
-void graph_bfs(void)
-{
- DagNode *node;
- DagNodeQueue *nqueue;
- int pos[50];
- int i;
- DagAdjList *itA;
- int minheight;
-
- /* fprintf(stderr, "starting BFS\n ------------\n"); */
- nqueue = queue_create(DAGQUEUEALLOC);
- for (i = 0; i < 50; i++)
- pos[i] = 0;
-
- /* Init
- * dagnode.first is always the root (scene)
- */
- node = MainDag->DagNode.first;
- while (node) {
- node->color = DAG_WHITE;
- node->BFS_dist = 9999;
- node->k = 0;
- node = node->next;
- }
-
- node = MainDag->DagNode.first;
- if (node->color == DAG_WHITE) {
- node->color = DAG_GRAY;
- node->BFS_dist = 1;
- push_queue(nqueue, node);
- while (nqueue->count) {
- node = pop_queue(nqueue);
-
- minheight = pos[node->BFS_dist];
- itA = node->child;
- while (itA != NULL) {
- if (itA->node->color == DAG_WHITE) {
- itA->node->color = DAG_GRAY;
- itA->node->BFS_dist = node->BFS_dist + 1;
- itA->node->k = (float) minheight;
- push_queue(nqueue, itA->node);
- }
-
- else {
- fprintf(stderr, "bfs not dag tree edge color :%i\n", itA->node->color);
- }
-
-
- itA = itA->next;
- }
- if (pos[node->BFS_dist] > node->k) {
- pos[node->BFS_dist] += 1;
- node->k = (float) pos[node->BFS_dist];
- }
- else {
- pos[node->BFS_dist] = (int) node->k + 1;
- }
- set_node_xy(node, node->BFS_dist * DEPSX * 2, pos[node->BFS_dist] * DEPSY * 2);
- node->color = DAG_BLACK;
-
- // fprintf(stderr, "BFS node : %20s %i %5.0f %5.0f\n", ((ID *) node->ob)->name, node->BFS_dist, node->x, node->y);
- }
- }
- queue_delete(nqueue);
-}
-
-int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data)
-{
- DagNode *node;
-
- node = dag->DagNode.first;
- return pre_and_post_source_BFS(dag, mask, node, pre_func, post_func, data);
-}
-
-
-int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
-{
- DagNode *node;
- DagNodeQueue *nqueue;
- DagAdjList *itA;
- int retval = 0;
- /* fprintf(stderr, "starting BFS\n ------------\n"); */
-
- /* Init
- * dagnode.first is always the root (scene)
- */
- node = dag->DagNode.first;
- nqueue = queue_create(DAGQUEUEALLOC);
- while (node) {
- node->color = DAG_WHITE;
- node->BFS_dist = 9999;
- node = node->next;
- }
-
- node = source;
- if (node->color == DAG_WHITE) {
- node->color = DAG_GRAY;
- node->BFS_dist = 1;
- pre_func(node->ob, data);
-
- while (nqueue->count) {
- node = pop_queue(nqueue);
-
- itA = node->child;
- while (itA != NULL) {
- if ((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
- itA->node->color = DAG_GRAY;
- itA->node->BFS_dist = node->BFS_dist + 1;
- push_queue(nqueue, itA->node);
- pre_func(node->ob, data);
- }
-
- else { /* back or cross edge */
- retval = 1;
- }
- itA = itA->next;
- }
- post_func(node->ob, data);
- node->color = DAG_BLACK;
-
- // fprintf(stderr, "BFS node : %20s %i %5.0f %5.0f\n", ((ID *) node->ob)->name, node->BFS_dist, node->x, node->y);
- }
- }
- queue_delete(nqueue);
- return retval;
-}
-
-/* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
-DagNodeQueue *graph_dfs(void)
-{
- DagNode *node;
- DagNodeQueue *nqueue;
- DagNodeQueue *retqueue;
- int pos[50];
- int i;
- DagAdjList *itA;
- int time;
- int skip = 0;
- int minheight;
- int maxpos = 0;
- /* int is_cycle = 0; */ /* UNUSED */
- /*
- *fprintf(stderr, "starting DFS\n ------------\n");
- */
- nqueue = queue_create(DAGQUEUEALLOC);
- retqueue = queue_create(MainDag->numNodes);
- for (i = 0; i < 50; i++)
- pos[i] = 0;
-
- /* Init
- * dagnode.first is always the root (scene)
- */
- node = MainDag->DagNode.first;
- while (node) {
- node->color = DAG_WHITE;
- node->DFS_dist = 9999;
- node->DFS_dvtm = node->DFS_fntm = 9999;
- node->k = 0;
- node = node->next;
- }
-
- time = 1;
-
- node = MainDag->DagNode.first;
-
- do {
- if (node->color == DAG_WHITE) {
- node->color = DAG_GRAY;
- node->DFS_dist = 1;
- node->DFS_dvtm = time;
- time++;
- push_stack(nqueue, node);
-
- while (nqueue->count) {
- //graph_print_queue(nqueue);
-
- skip = 0;
- node = get_top_node_queue(nqueue);
-
- minheight = pos[node->DFS_dist];
-
- itA = node->child;
- while (itA != NULL) {
- if (itA->node->color == DAG_WHITE) {
- itA->node->DFS_dvtm = time;
- itA->node->color = DAG_GRAY;
-
- time++;
- itA->node->DFS_dist = node->DFS_dist + 1;
- itA->node->k = (float) minheight;
- push_stack(nqueue, itA->node);
- skip = 1;
- break;
- }
- else {
- if (itA->node->color == DAG_GRAY) { /* back edge */
- fprintf(stderr, "dfs back edge :%15s %15s\n", ((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
- /* is_cycle = 1; */ /* UNUSED */
- }
- else if (itA->node->color == DAG_BLACK) {
- /* already processed node but we may want later to change distance either to shorter to longer.
- * DFS_dist is the first encounter
- */
-#if 0
- if (node->DFS_dist >= itA->node->DFS_dist)
- itA->node->DFS_dist = node->DFS_dist + 1;
-
- fprintf(stderr, "dfs forward or cross edge :%15s %i-%i %15s %i-%i\n",
- ((ID *) node->ob)->name,
- node->DFS_dvtm,
- node->DFS_fntm,
- ((ID *) itA->node->ob)->name,
- itA->node->DFS_dvtm,
- itA->node->DFS_fntm);
-#endif
- }
- else
- fprintf(stderr, "dfs unknown edge\n");
- }
- itA = itA->next;
- }
-
- if (!skip) {
- node = pop_queue(nqueue);
- node->color = DAG_BLACK;
-
- node->DFS_fntm = time;
- time++;
- if (node->DFS_dist > maxpos)
- maxpos = node->DFS_dist;
- if (pos[node->DFS_dist] > node->k) {
- pos[node->DFS_dist] += 1;
- node->k = (float) pos[node->DFS_dist];
- }
- else {
- pos[node->DFS_dist] = (int) node->k + 1;
- }
- set_node_xy(node, node->DFS_dist * DEPSX * 2, pos[node->DFS_dist] * DEPSY * 2);
-
- // fprintf(stderr, "DFS node : %20s %i %i %i %i\n", ((ID *) node->ob)->name, node->BFS_dist, node->DFS_dist, node->DFS_dvtm, node->DFS_fntm );
-
- push_stack(retqueue, node);
-
- }
- }
- }
- node = node->next;
- } while (node);
-// fprintf(stderr, "i size : %i\n", maxpos);
-
- queue_delete(nqueue);
- 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;
-
- node = dag->DagNode.first;
- return pre_and_post_source_DFS(dag, mask, node, pre_func, post_func, data);
-}
-
-int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
-{
- DagNode *node;
- DagNodeQueue *nqueue;
- DagAdjList *itA;
- int time;
- int skip = 0;
- int retval = 0;
- /*
- * fprintf(stderr, "starting DFS\n ------------\n");
- */
- nqueue = queue_create(DAGQUEUEALLOC);
-
- /* Init
- * dagnode.first is always the root (scene)
- */
- node = dag->DagNode.first;
- while (node) {
- node->color = DAG_WHITE;
- node->DFS_dist = 9999;
- node->DFS_dvtm = node->DFS_fntm = 9999;
- node->k = 0;
- node = node->next;
- }
-
- time = 1;
-
- node = source;
- do {
- if (node->color == DAG_WHITE) {
- node->color = DAG_GRAY;
- node->DFS_dist = 1;
- node->DFS_dvtm = time;
- time++;
- push_stack(nqueue, node);
- pre_func(node->ob, data);
-
- while (nqueue->count) {
- skip = 0;
- node = get_top_node_queue(nqueue);
-
- itA = node->child;
- while (itA != NULL) {
- if ((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
- itA->node->DFS_dvtm = time;
- itA->node->color = DAG_GRAY;
-
- time++;
- itA->node->DFS_dist = node->DFS_dist + 1;
- push_stack(nqueue, itA->node);
- pre_func(node->ob, data);
-
- skip = 1;
- break;
- }
- else {
- if (itA->node->color == DAG_GRAY) { // back edge
- retval = 1;
- }
-// else if (itA->node->color == DAG_BLACK) { // cross or forward
-//
-// }
- }
- itA = itA->next;
- }
-
- if (!skip) {
- node = pop_queue(nqueue);
- node->color = DAG_BLACK;
-
- node->DFS_fntm = time;
- time++;
- post_func(node->ob, data);
- }
- }
- }
- node = node->next;
- } while (node);
- queue_delete(nqueue);
- return(retval);
-}
-
-
-/* used to get the obs owning a datablock */
-DagNodeQueue *get_obparents(struct DagForest *dag, void *ob)
-{
- DagNode *node, *node1;
- DagNodeQueue *nqueue;
- DagAdjList *itA;
-
- node = dag_find_node(dag, ob);
- 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 */
- nqueue = queue_create(node->ancestor_count);
-
- node1 = dag->DagNode.first;
- do {
- if (node1->DFS_fntm > node->DFS_fntm) { /* a parent is finished after child. must check adj list */
- itA = node->child;
- while (itA != NULL) {
- if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
- push_queue(nqueue, node);
- }
- itA = itA->next;
- }
- }
- node1 = node1->next;
- } while (node1);
- }
- return nqueue;
-}
-
-DagNodeQueue *get_first_ancestors(struct DagForest *dag, void *ob)
-{
- DagNode *node, *node1;
- DagNodeQueue *nqueue;
- DagAdjList *itA;
-
- node = dag_find_node(dag, ob);
-
- /* need to go over the whole dag for adj list */
- nqueue = queue_create(node->ancestor_count);
-
- node1 = dag->DagNode.first;
- do {
- if (node1->DFS_fntm > node->DFS_fntm) {
- itA = node->child;
- while (itA != NULL) {
- if (itA->node == node) {
- push_queue(nqueue, node);
- }
- itA = itA->next;
- }
- }
- node1 = node1->next;
- } while (node1);
-
- return nqueue;
-}
-
-/* standard DFS list */
-DagNodeQueue *get_all_childs(struct DagForest *dag, void *ob)
-{
- DagNode *node;
- DagNodeQueue *nqueue;
- DagNodeQueue *retqueue;
- DagAdjList *itA;
- int time;
- int skip = 0;
-
- nqueue = queue_create(DAGQUEUEALLOC);
- retqueue = queue_create(dag->numNodes); /* was MainDag... why? (ton) */
-
- node = dag->DagNode.first;
- while (node) {
- node->color = DAG_WHITE;
- node = node->next;
- }
-
- time = 1;
-
- node = dag_find_node(dag, ob); /* could be done in loop above (ton) */
- if (node) { /* can be null for newly added objects */
-
- 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) {
- node = pop_queue(nqueue);
- node->color = DAG_BLACK;
-
- time++;
- push_stack(retqueue, node);
- }
- }
- }
- queue_delete(nqueue);
- return(retqueue);
-}
-
-/* unused */
-#if 0
-short are_obs_related(struct DagForest *dag, void *ob1, void *ob2)
-{
- DagNode *node;
- DagAdjList *itA;
-
- node = dag_find_node(dag, ob1);
-
- itA = node->child;
- while (itA != NULL) {
- if (itA->node->ob == ob2) {
- return itA->node->type;
- }
- itA = itA->next;
- }
- return DAG_NO_RELATION;
-}
-#endif
-
-int is_acyclic(DagForest *dag)
-{
- return dag->is_acyclic;
-}
-
-void set_node_xy(DagNode *node, float x, float y)
-{
- node->x = x;
- node->y = y;
-}
-
-
/* debug test functions */
void graph_print_queue(DagNodeQueue *nqueue)
@@ -1757,12 +1213,12 @@ void graph_print_queue_dist(DagNodeQueue *nqueue)
fprintf(stderr, "\n");
}
-void graph_print_adj_list(void)
+void graph_print_adj_list(DagForest *dag)
{
DagNode *node;
DagAdjList *itA;
- node = (getMainDag())->DagNode.first;
+ node = dag->DagNode.first;
while (node) {
fprintf(stderr, "node : %s col: %i", ((ID *) node->ob)->name, node->color);
itA = node->child;
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-05 10:55:42 +0300