Left: | ||
Right: |
LEFT | RIGHT |
---|---|
1 /* | 1 /* |
2 * ***** BEGIN GPL LICENSE BLOCK ***** | 2 * ***** BEGIN GPL LICENSE BLOCK ***** |
3 * | 3 * |
4 * This program is free software; you can redistribute it and/or | 4 * This program is free software; you can redistribute it and/or |
5 * modify it under the terms of the GNU General Public License | 5 * modify it under the terms of the GNU General Public License |
6 * as published by the Free Software Foundation; either version 2 | 6 * as published by the Free Software Foundation; either version 2 |
7 * of the License, or (at your option) any later version. | 7 * of the License, or (at your option) any later version. |
8 * | 8 * |
9 * This program is distributed in the hope that it will be useful, | 9 * This program is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
(...skipping 11 matching lines...) Expand all Loading... | |
22 * | 22 * |
23 * ***** END GPL LICENSE BLOCK ***** | 23 * ***** END GPL LICENSE BLOCK ***** |
24 */ | 24 */ |
25 | 25 |
26 /** \file blender/blenkernel/intern/depsgraph.c | 26 /** \file blender/blenkernel/intern/depsgraph.c |
27 * \ingroup bke | 27 * \ingroup bke |
28 */ | 28 */ |
29 | 29 |
30 · | 30 · |
31 #include <stdio.h> | 31 #include <stdio.h> |
32 #include <stdlib.h> | |
33 #include <string.h> | 32 #include <string.h> |
34 #include <math.h> | 33 #include <math.h> |
35 | 34 |
36 #include "MEM_guardedalloc.h" | 35 #include "MEM_guardedalloc.h" |
37 | 36 |
38 #ifdef WIN32 | 37 #include "BLI_winstuff.h" |
39 # include "BLI_winstuff.h" | |
40 #endif | |
41 | |
42 #include "BLI_utildefines.h" | 38 #include "BLI_utildefines.h" |
43 #include "BLI_listbase.h" | 39 #include "BLI_listbase.h" |
44 #include "BLI_ghash.h" | 40 #include "BLI_ghash.h" |
45 | 41 |
46 #include "DNA_anim_types.h" | 42 #include "DNA_anim_types.h" |
47 #include "DNA_camera_types.h" | 43 #include "DNA_camera_types.h" |
48 #include "DNA_group_types.h" | 44 #include "DNA_group_types.h" |
49 #include "DNA_lamp_types.h" | |
50 #include "DNA_lattice_types.h" | 45 #include "DNA_lattice_types.h" |
46 #include "DNA_key_types.h" | |
47 #include "DNA_material_types.h" | |
48 #include "DNA_mesh_types.h" | |
49 #include "DNA_node_types.h" | |
51 #include "DNA_scene_types.h" | 50 #include "DNA_scene_types.h" |
52 #include "DNA_screen_types.h" | 51 #include "DNA_screen_types.h" |
53 #include "DNA_windowmanager_types.h" | 52 #include "DNA_windowmanager_types.h" |
53 #include "DNA_movieclip_types.h" | |
54 | 54 |
55 #include "BKE_animsys.h" | 55 #include "BKE_animsys.h" |
56 #include "BKE_action.h" | 56 #include "BKE_action.h" |
57 #include "BKE_effect.h" | |
58 #include "BKE_fcurve.h" | |
59 #include "BKE_global.h" | |
60 #include "BKE_group.h" | |
61 #include "BKE_key.h" | |
62 #include "BKE_library.h" | |
63 #include "BKE_main.h" | |
64 #include "BKE_node.h" | |
65 #include "BKE_mball.h" | |
66 #include "BKE_modifier.h" | |
67 #include "BKE_object.h" | |
68 #include "BKE_particle.h" | |
69 #include "BKE_pointcache.h" | |
70 #include "BKE_scene.h" | |
71 #include "BKE_screen.h" | |
72 #include "BKE_utildefines.h" | |
73 | |
74 #include "depsgraph_private.h" | |
75 · | |
76 /* Queue and stack operations for dag traversal· | |
77 * | |
78 * the queue store a list of freenodes to avoid successives alloc/dealloc | |
79 */ | |
80 | |
81 DagNodeQueue * queue_create (int slots)· | |
82 { | |
83 DagNodeQueue * queue; | |
84 DagNodeQueueElem * elem; | |
85 int i; | |
86 ········ | |
87 queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue"); | |
88 queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue"); | |
89 queue->count = 0; | |
90 queue->maxlevel = 0; | |
91 queue->first = queue->last = NULL; | |
92 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3"); | |
93 elem->node = NULL; | |
94 elem->next = NULL; | |
95 queue->freenodes->first = queue->freenodes->last = elem; | |
96 ········ | |
97 for (i = 1; i <slots;i++) { | |
98 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4"); | |
99 elem->node = NULL; | |
100 elem->next = NULL; | |
101 queue->freenodes->last->next = elem; | |
102 queue->freenodes->last = elem; | |
103 } | |
104 queue->freenodes->count = slots; | |
105 return queue; | |
106 } | |
107 | |
108 void queue_raz(DagNodeQueue *queue) | |
109 { | |
110 DagNodeQueueElem * elem; | |
111 ········ | |
112 elem = queue->first; | |
113 if (queue->freenodes->last) | |
114 queue->freenodes->last->next = elem; | |
115 else | |
116 queue->freenodes->first = queue->freenodes->last = elem; | |
117 ········ | |
118 elem->node = NULL; | |
119 queue->freenodes->count++; | |
120 while (elem->next) { | |
121 elem = elem->next; | |
122 elem->node = NULL; | |
123 queue->freenodes->count++; | |
124 } | |
125 queue->freenodes->last = elem; | |
126 queue->count = 0; | |
127 } | |
128 | |
129 void queue_delete(DagNodeQueue *queue) | |
130 { | |
131 DagNodeQueueElem * elem; | |
132 DagNodeQueueElem * temp; | |
133 ········ | |
134 elem = queue->first; | |
135 while (elem) { | |
136 temp = elem; | |
137 elem = elem->next; | |
138 MEM_freeN(temp); | |
139 } | |
140 ········ | |
141 elem = queue->freenodes->first; | |
142 while (elem) { | |
143 temp = elem; | |
144 elem = elem->next; | |
145 MEM_freeN(temp); | |
146 } | |
147 ········ | |
148 MEM_freeN(queue->freenodes);···················· | |
149 MEM_freeN(queue);······················· | |
150 } | |
151 | |
152 /* insert in queue, remove in front */ | |
153 void push_queue(DagNodeQueue *queue, DagNode *node) | |
154 { | |
155 DagNodeQueueElem * elem; | |
156 int i; | |
157 | |
158 if (node == NULL) { | |
159 fprintf(stderr,"pushing null node \n"); | |
160 return; | |
161 } | |
162 /*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->co unt);*/ | |
163 | |
164 elem = queue->freenodes->first; | |
165 if (elem != NULL) { | |
166 queue->freenodes->first = elem->next; | |
167 if ( queue->freenodes->last == elem) { | |
168 queue->freenodes->last = NULL; | |
169 queue->freenodes->first = NULL; | |
170 } | |
171 queue->freenodes->count--; | |
172 } else { /* alllocating more */········· | |
173 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1"); | |
174 elem->node = NULL; | |
175 elem->next = NULL; | |
176 queue->freenodes->first = queue->freenodes->last = elem; | |
177 | |
178 for (i = 1; i <DAGQUEUEALLOC;i++) { | |
179 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue e lem2"); | |
180 elem->node = NULL; | |
181 elem->next = NULL; | |
182 queue->freenodes->last->next = elem; | |
183 queue->freenodes->last = elem; | |
184 } | |
185 queue->freenodes->count = DAGQUEUEALLOC; | |
186 ························ | |
187 elem = queue->freenodes->first;· | |
188 queue->freenodes->first = elem->next;··· | |
189 } | |
190 elem->next = NULL; | |
191 elem->node = node; | |
192 if (queue->last != NULL) | |
193 queue->last->next = elem; | |
194 queue->last = elem; | |
195 if (queue->first == NULL) { | |
196 queue->first = elem; | |
197 } | |
198 queue->count++; | |
199 } | |
200 | |
201 | |
202 /* insert in front, remove in front */ | |
203 void push_stack(DagNodeQueue *queue, DagNode *node) | |
204 { | |
205 DagNodeQueueElem * elem; | |
206 int i; | |
207 | |
208 elem = queue->freenodes->first;· | |
209 if (elem != NULL) { | |
210 queue->freenodes->first = elem->next; | |
211 if ( queue->freenodes->last == elem) { | |
212 queue->freenodes->last = NULL; | |
213 queue->freenodes->first = NULL; | |
214 } | |
215 queue->freenodes->count--; | |
216 } else { /* alllocating more */ | |
217 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1"); | |
218 elem->node = NULL; | |
219 elem->next = NULL; | |
220 queue->freenodes->first = queue->freenodes->last = elem; | |
221 | |
222 for (i = 1; i <DAGQUEUEALLOC;i++) { | |
223 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue e lem2"); | |
224 elem->node = NULL; | |
225 elem->next = NULL; | |
226 queue->freenodes->last->next = elem; | |
227 queue->freenodes->last = elem; | |
228 } | |
229 queue->freenodes->count = DAGQUEUEALLOC; | |
230 ························ | |
231 elem = queue->freenodes->first;· | |
232 queue->freenodes->first = elem->next;··· | |
233 } | |
234 elem->next = queue->first; | |
235 elem->node = node; | |
236 queue->first = elem; | |
237 if (queue->last == NULL) | |
238 queue->last = elem; | |
239 queue->count++; | |
240 } | |
241 | |
242 | |
243 DagNode * pop_queue(DagNodeQueue *queue) | |
244 { | |
245 DagNodeQueueElem * elem; | |
246 DagNode *node; | |
247 | |
248 elem = queue->first; | |
249 if (elem) { | |
250 queue->first = elem->next; | |
251 if (queue->last == elem) { | |
252 queue->last=NULL; | |
253 queue->first=NULL; | |
254 } | |
255 queue->count--; | |
256 if (queue->freenodes->last) | |
257 queue->freenodes->last->next=elem; | |
258 queue->freenodes->last=elem; | |
259 if (queue->freenodes->first == NULL) | |
260 queue->freenodes->first=elem; | |
261 node = elem->node; | |
262 elem->node = NULL; | |
263 elem->next = NULL; | |
264 queue->freenodes->count++; | |
265 return node; | |
266 } else { | |
267 fprintf(stderr,"return null \n"); | |
268 return NULL; | |
269 } | |
270 } | |
271 | |
272 void *pop_ob_queue(struct DagNodeQueue *queue) { | |
273 return(pop_queue(queue)->ob); | |
274 } | |
275 | |
276 DagNode * get_top_node_queue(DagNodeQueue *queue)· | |
277 { | |
278 return queue->first->node; | |
279 } | |
280 | |
281 int queue_count(struct DagNodeQueue *queue){ | |
282 return queue->count; | |
283 } | |
284 | |
285 | |
286 DagForest *dag_init(void) | |
287 { | |
288 DagForest *forest; | |
289 /* use callocN to init all zero */ | |
290 forest = MEM_callocN(sizeof(DagForest),"DAG root"); | |
291 return forest; | |
292 } | |
293 | |
294 /* isdata = object data... */ | |
295 // XXX this needs to be extended to be more flexible (so that not only objects a re evaluated via depsgraph)... | |
296 static void dag_add_driver_relation(AnimData *adt, DagForest *dag, DagNode *node , int isdata) | |
297 { | |
298 FCurve *fcu; | |
299 DagNode *node1; | |
300 ········ | |
301 for (fcu= adt->drivers.first; fcu; fcu= fcu->next) { | |
302 ChannelDriver *driver= fcu->driver; | |
303 DriverVar *dvar; | |
304 int isdata_fcu = isdata || (fcu->rna_path && strstr(fcu->rna_pat h, "modifiers[")); | |
305 ················ | |
306 /* loop over variables to get the target relationships */ | |
307 for (dvar= driver->variables.first; dvar; dvar= dvar->next) { | |
308 /* only used targets */ | |
309 DRIVER_TARGETS_USED_LOOPER(dvar)· | |
310 { | |
311 if (dtar->id) { | |
312 // FIXME: other data types need to be ad ded here so that they can work! | |
313 if (GS(dtar->id->name)==ID_OB) { | |
314 Object *ob= (Object *)dtar->id; | |
315 ················································ | |
316 /* normal channel-drives-channel */ | |
317 node1 = dag_get_node(dag, dtar-> id); | |
318 ················································ | |
319 /* check if bone... */ | |
320 if ((ob->type==OB_ARMATURE) &&· | |
321 ( ((dtar->rna_path) && s trstr(dtar->rna_path, "pose.bones[")) ||· | |
322 ((dtar->flag & DTAR_FL AG_STRUCT_REF) && (dtar->pchan_name[0])) ))· | |
323 { | |
324 dag_add_relation(dag, no de1, node, isdata_fcu?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver"); | |
325 } | |
326 /* check if ob data */ | |
327 else if (dtar->rna_path && strst r(dtar->rna_path, "data.")) | |
328 dag_add_relation(dag, no de1, node, isdata_fcu?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver"); | |
329 /* normal */ | |
330 else | |
331 dag_add_relation(dag, no de1, node, isdata_fcu?DAG_RL_OB_DATA:DAG_RL_OB_OB, "Driver"); | |
332 } | |
333 } | |
334 } | |
335 DRIVER_TARGETS_LOOPER_END | |
336 } | |
337 } | |
338 } | |
339 | |
340 static void dag_add_collision_field_relation(DagForest *dag, Scene *scene, Objec t *ob, DagNode *node) | |
341 { | |
342 Base *base; | |
343 DagNode *node2; | |
344 | |
345 // would be nice to have a list of colliders here | |
346 // so for now walk all objects in scene check 'same layer rule' | |
347 for(base = scene->base.first; base; base= base->next) { | |
348 if((base->lay & ob->lay) && base->object->pd) { | |
349 Object *ob1= base->object; | |
350 if((ob1->pd->deflect || ob1->pd->forcefield) && (ob1 != ob)) { | |
351 node2 = dag_get_node(dag, ob1);········································ | |
352 dag_add_relation(dag, node2, node, DAG_RL_DATA_D ATA|DAG_RL_OB_DATA, "Field Collision"); | |
353 } | |
354 } | |
355 } | |
356 } | |
357 | |
358 static void build_dag_object(DagForest *dag, DagNode *scenenode, Scene *scene, O bject *ob, int mask) | |
359 { | |
360 bConstraint *con; | |
361 DagNode * node; | |
362 DagNode * node2; | |
363 DagNode * node3; | |
364 Key *key; | |
365 ParticleSystem *psys; | |
366 int addtoroot= 1; | |
367 ········ | |
368 node = dag_get_node(dag, ob); | |
369 ········ | |
370 if ((ob->data) && (mask&DAG_RL_DATA)) { | |
371 node2 = dag_get_node(dag,ob->data); | |
372 dag_add_relation(dag,node,node2,DAG_RL_DATA, "Object-Data Relati on"); | |
373 node2->first_ancestor = ob; | |
374 node2->ancestor_count += 1; | |
375 } | |
376 | |
377 /* also build a custom data mask for dependencies that need certain laye rs */ | |
378 node->customdata_mask= 0; | |
379 ········ | |
380 if (ob->type == OB_ARMATURE) { | |
381 if (ob->pose){ | |
382 bPoseChannel *pchan; | |
383 bConstraint *con; | |
384 ························ | |
385 for (pchan = ob->pose->chanbase.first; pchan; pchan=pcha n->next) { | |
386 for (con = pchan->constraints.first; con; con=co n->next) { | |
387 bConstraintTypeInfo *cti= constraint_get _typeinfo(con); | |
388 ListBase targets = {NULL, NULL}; | |
389 bConstraintTarget *ct; | |
390 ········································ | |
391 if (cti && cti->get_constraint_targets) { | |
392 cti->get_constraint_targets(con, &targets); | |
393 ················································ | |
394 for (ct= targets.first; ct; ct= ct->next) { | |
395 if (ct->tar && ct->tar ! = ob) { | |
396 // fprintf(stder r,"armature %s target :%s \n", ob->id.name, target->id.name); | |
397 node3 = dag_get_ node(dag, ct->tar); | |
398 ································································ | |
399 if (ct->subtarge t[0]) | |
400 dag_add_ relation(dag,node3,node, DAG_RL_OB_DATA|DAG_RL_DATA_DATA, cti->name); | |
401 else if(ELEM3(co n->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO, CONSTRAINT_TYPE_SP LINEIK))········ | |
402 dag_add_ relation(dag,node3,node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, cti->name); | |
403 else | |
404 dag_add_ relation(dag,node3,node, DAG_RL_OB_DATA, cti->name); | |
405 } | |
406 } | |
407 ················································ | |
408 if (cti->flush_constraint_target s) | |
409 cti->flush_constraint_ta rgets(con, &targets, 1); | |
410 } | |
411 ········································ | |
412 } | |
413 } | |
414 } | |
415 } | |
416 ········ | |
417 /* driver dependencies, nla modifiers */ | |
418 #if 0 // XXX old animation system | |
419 if(ob->nlastrips.first) { | |
420 bActionStrip *strip; | |
421 bActionChannel *chan; | |
422 for(strip= ob->nlastrips.first; strip; strip= strip->next) { | |
423 if(strip->modifiers.first) { | |
424 bActionModifier *amod; | |
425 for(amod= strip->modifiers.first; amod; amod= am od->next) { | |
426 if(amod->ob) { | |
427 node2 = dag_get_node(dag, amod-> ob); | |
428 dag_add_relation(dag, node2, nod e, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "NLA Strip Modifier"); | |
429 } | |
430 } | |
431 } | |
432 } | |
433 } | |
434 #endif // XXX old animation system | |
435 if (ob->adt) | |
436 dag_add_driver_relation(ob->adt, dag, node, (ob->type == OB_ARMA TURE)); // XXX isdata arg here doesn't give an accurate picture of situation | |
437 ················ | |
438 key= ob_get_key(ob); | |
439 if (key && key->adt) | |
440 dag_add_driver_relation(key->adt, dag, node, 1); | |
441 | |
442 if (ob->modifiers.first) { | |
443 ModifierData *md; | |
444 ················ | |
445 for(md=ob->modifiers.first; md; md=md->next) { | |
446 ModifierTypeInfo *mti = modifierType_getInfo(md->type); | |
447 ························ | |
448 if (mti->updateDepgraph) mti->updateDepgraph(md, dag, sc ene, ob, node); | |
449 } | |
450 } | |
451 if (ob->parent) { | |
452 node2 = dag_get_node(dag,ob->parent); | |
453 ················ | |
454 switch(ob->partype) { | |
455 case PARSKEL: | |
456 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA |DAG_RL_OB_OB, "Parent"); | |
457 break; | |
458 case PARVERT1: case PARVERT3: | |
459 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|D AG_RL_OB_OB, "Vertex Parent"); | |
460 node2->customdata_mask |= CD_MASK_ORIGINDEX; | |
461 break; | |
462 case PARBONE: | |
463 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|D AG_RL_OB_OB, "Bone Parent"); | |
464 break; | |
465 default: | |
466 if(ob->parent->type==OB_LATTICE)· | |
467 dag_add_relation(dag,node2,node,DAG_RL_D ATA_DATA|DAG_RL_OB_OB, "Lattice Parent"); | |
468 else if(ob->parent->type==OB_CURVE) { | |
469 Curve *cu= ob->parent->data; | |
470 if(cu->flag & CU_PATH)· | |
471 dag_add_relation(dag,node2,node, DAG_RL_DATA_OB|DAG_RL_OB_OB, "Curve Parent"); | |
472 else | |
473 dag_add_relation(dag,node2,node, DAG_RL_OB_OB, "Curve Parent"); | |
474 } | |
475 else | |
476 dag_add_relation(dag,node2,node,DAG_RL_O B_OB, "Parent"); | |
477 } | |
478 /* exception case: parent is duplivert */ | |
479 if(ob->type==OB_MBALL && (ob->parent->transflag & OB_DUPLIVERTS) ) { | |
480 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_ RL_OB_OB, "Duplivert"); | |
481 } | |
482 ················ | |
483 addtoroot = 0; | |
484 } | |
485 if (ob->proxy) { | |
486 node2 = dag_get_node(dag, ob->proxy); | |
487 dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA|DAG_RL_OB_OB , "Proxy"); | |
488 /* inverted relation, so addtoroot shouldn't be set to zero */ | |
489 } | |
490 ········ | |
491 if (ob->transflag & OB_DUPLI) { | |
492 if((ob->transflag & OB_DUPLIGROUP) && ob->dup_group) { | |
493 GroupObject *go; | |
494 for(go= ob->dup_group->gobject.first; go; go= go->next) { | |
495 if(go->ob) { | |
496 node2 = dag_get_node(dag, go->ob); | |
497 /* node2 changes node1, this keeps anima tions updated in groups?? not logical? */ | |
498 dag_add_relation(dag, node2, node, DAG_R L_OB_OB, "Dupligroup"); | |
499 } | |
500 } | |
501 } | |
502 } | |
503 | |
504 /* softbody collision */ | |
505 if ((ob->type==OB_MESH) || (ob->type==OB_CURVE) || (ob->type==OB_LATTICE )) { | |
506 if(modifiers_isSoftbodyEnabled(ob) || modifiers_isClothEnabled(o b) || ob->particlesystem.first) | |
507 dag_add_collision_field_relation(dag, scene, ob, node); /* TODO: use effectorweight->group */ | |
508 } | |
509 ········ | |
510 /* object data drivers */ | |
511 if (ob->data) { | |
512 AnimData *adt= BKE_animdata_from_id((ID *)ob->data); | |
513 if (adt) | |
514 dag_add_driver_relation(adt, dag, node, 1); | |
515 } | |
516 ········ | |
517 /* object type/data relationships */ | |
518 switch (ob->type) { | |
519 case OB_CAMERA: | |
520 { | |
521 Camera *cam = (Camera *)ob->data; | |
522 ························ | |
523 if (cam->dof_ob) { | |
524 node2 = dag_get_node(dag, cam->dof_ob); | |
525 dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "C amera DoF"); | |
526 } | |
527 } | |
528 break; | |
529 case OB_MBALL:· | |
530 { | |
531 Object *mom= find_basis_mball(scene, ob); | |
532 ························ | |
533 if(mom!=ob) { | |
534 node2 = dag_get_node(dag, mom); | |
535 dag_add_relation(dag,node,node2,DAG_RL_DATA_DATA |DAG_RL_OB_DATA, "Metaball"); // mom depends on children! | |
536 } | |
537 } | |
538 break; | |
539 case OB_CURVE: | |
540 { | |
541 Curve *cu= ob->data; | |
542 ························ | |
543 if(cu->bevobj) { | |
544 node2 = dag_get_node(dag, cu->bevobj); | |
545 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA |DAG_RL_OB_DATA, "Curve Bevel"); | |
546 } | |
547 if(cu->taperobj) { | |
548 node2 = dag_get_node(dag, cu->taperobj); | |
549 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA |DAG_RL_OB_DATA, "Curve Taper"); | |
550 } | |
551 } | |
552 break; | |
553 case OB_FONT:· | |
554 { | |
555 Curve *cu= ob->data; | |
556 ························ | |
557 if(cu->textoncurve) { | |
558 node2 = dag_get_node(dag, cu->textoncurve); | |
559 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA |DAG_RL_OB_DATA, "Texture On Curve"); | |
560 } | |
561 } | |
562 break; | |
563 } | |
564 ········ | |
565 /* particles */ | |
566 psys= ob->particlesystem.first; | |
567 if(psys) { | |
568 GroupObject *go; | |
569 | |
570 for(; psys; psys=psys->next) { | |
571 BoidRule *rule = NULL; | |
572 BoidState *state = NULL; | |
573 ParticleSettings *part= psys->part; | |
574 ListBase *effectors = NULL; | |
575 EffectorCache *eff; | |
576 | |
577 dag_add_relation(dag, node, node, DAG_RL_OB_DATA, "Parti cle-Object Relation"); | |
578 | |
579 if(!psys_check_enabled(ob, psys)) | |
580 continue; | |
581 | |
582 if(ELEM(part->phystype,PART_PHYS_KEYED,PART_PHYS_BOIDS)) { | |
583 ParticleTarget *pt = psys->targets.first; | |
584 | |
585 for(; pt; pt=pt->next) { | |
586 if(pt->ob && BLI_findlink(&pt->ob->parti clesystem, pt->psys-1)) { | |
587 node2 = dag_get_node(dag, pt->ob ); | |
588 dag_add_relation(dag, node2, nod e, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Particle Targets"); | |
589 } | |
590 } | |
591 } | |
592 | |
593 if(part->ren_as == PART_DRAW_OB && part->dup_ob) { | |
594 node2 = dag_get_node(dag, part->dup_ob); | |
595 dag_add_relation(dag, node, node2, DAG_RL_OB_OB, "Particle Object Visualisation"); | |
596 if(part->dup_ob->type == OB_MBALL) | |
597 dag_add_relation(dag, node, node2, DAG_R L_DATA_DATA, "Particle Object Visualisation"); | |
598 } | |
599 | |
600 if(part->ren_as == PART_DRAW_GR && part->dup_group) { | |
601 for(go=part->dup_group->gobject.first; go; go=go ->next) { | |
602 node2 = dag_get_node(dag, go->ob); | |
603 dag_add_relation(dag, node2, node, DAG_R L_OB_OB, "Particle Group Visualisation"); | |
604 } | |
605 } | |
606 | |
607 effectors = pdInitEffectors(scene, ob, psys, part->effec tor_weights); | |
608 | |
609 if(effectors) for(eff = effectors->first; eff; eff=eff-> next) { | |
610 if(eff->psys) { | |
611 node2 = dag_get_node(dag, eff->ob); | |
612 dag_add_relation(dag, node2, node, DAG_R L_DATA_DATA|DAG_RL_OB_DATA, "Particle Field"); | |
613 } | |
614 } | |
615 | |
616 pdEndEffectors(&effectors); | |
617 | |
618 if(part->boids) { | |
619 for(state = part->boids->states.first; state; st ate=state->next) { | |
620 for(rule = state->rules.first; rule; rul e=rule->next) { | |
621 Object *ruleob = NULL; | |
622 if(rule->type==eBoidRuleType_Avo id) | |
623 ruleob = ((BoidRuleGoalA void*)rule)->ob; | |
624 else if(rule->type==eBoidRuleTyp e_FollowLeader) | |
625 ruleob = ((BoidRuleFollo wLeader*)rule)->ob; | |
626 | |
627 if(ruleob) { | |
628 node2 = dag_get_node(dag , ruleob); | |
629 dag_add_relation(dag, no de2, node, DAG_RL_OB_DATA, "Boid Rule"); | |
630 } | |
631 } | |
632 } | |
633 } | |
634 } | |
635 } | |
636 ········ | |
637 /* object constraints */ | |
638 for (con = ob->constraints.first; con; con=con->next) { | |
639 bConstraintTypeInfo *cti= constraint_get_typeinfo(con); | |
640 ListBase targets = {NULL, NULL}; | |
641 bConstraintTarget *ct; | |
642 ················ | |
643 if(!cti) | |
644 continue; | |
645 | |
646 /* special case for FollowTrack -- it doesn't use targets to def ine relations */ | |
647 if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_ CAMERASOLVER)) { | |
648 if(cti->type==CONSTRAINT_TYPE_FOLLOWTRACK) { | |
649 bFollowTrackConstraint *data= (bFollowTrackConst raint *)con->data; | |
650 | |
651 if((data->clip || data->flag&FOLLOWTRACK_ACTIVEC LIP) && data->track[0]) { | |
652 if(scene->camera) { | |
653 node2 = dag_get_node(dag, scene- >camera); | |
654 dag_add_relation(dag, node2, nod e, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name); | |
655 } | |
656 } | |
657 } | |
658 | |
659 dag_add_relation(dag,scenenode,node,DAG_RL_SCENE, "Scene Relation"); | |
660 addtoroot = 0; | |
661 } | |
662 else if (cti->get_constraint_targets) { | |
663 cti->get_constraint_targets(con, &targets); | |
664 ························ | |
665 for (ct= targets.first; ct; ct= ct->next) { | |
666 Object *obt; | |
667 ································ | |
668 if (ct->tar) | |
669 obt= ct->tar; | |
670 else | |
671 continue; | |
672 ································ | |
673 node2 = dag_get_node(dag, obt); | |
674 if (ELEM(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO)) | |
675 dag_add_relation(dag, node2, node, DAG_R L_DATA_OB|DAG_RL_OB_OB, cti->name); | |
676 else { | |
677 if (ELEM3(obt->type, OB_ARMATURE, OB_MES H, OB_LATTICE) && (ct->subtarget[0])) { | |
678 dag_add_relation(dag, node2, nod e, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name); | |
679 if (obt->type == OB_MESH) | |
680 node2->customdata_mask | = CD_MASK_MDEFORMVERT; | |
681 } | |
682 else | |
683 dag_add_relation(dag, node2, nod e, DAG_RL_OB_OB, cti->name); | |
684 } | |
685 addtoroot = 0; | |
686 } | |
687 ························ | |
688 if (cti->flush_constraint_targets) | |
689 cti->flush_constraint_targets(con, &targets, 1); | |
690 } | |
691 } | |
692 | |
693 if (addtoroot == 1 ) | |
694 dag_add_relation(dag,scenenode,node,DAG_RL_SCENE, "Scene Relatio n"); | |
695 } | |
696 | |
697 struct DagForest *build_dag(Main *bmain, Scene *sce, short mask)· | |
698 { | |
699 Base *base; | |
700 Object *ob; | |
701 Group *group; | |
702 GroupObject *go; | |
703 DagNode *node; | |
704 DagNode *scenenode; | |
705 DagForest *dag; | |
706 DagAdjList *itA; | |
707 | |
708 dag = sce->theDag; | |
709 sce->dagisvalid=1; | |
710 if ( dag) | |
711 free_forest( dag );· | |
712 else { | |
713 dag = dag_init(); | |
714 sce->theDag = dag; | |
715 } | |
716 ········ | |
717 /* add base node for scene. scene is always the first node in DAG */ | |
718 scenenode = dag_add_node(dag, sce);····· | |
719 ········ | |
720 /* add current scene objects */ | |
721 for(base = sce->base.first; base; base= base->next) { | |
722 ob= base->object; | |
723 ················ | |
724 build_dag_object(dag, scenenode, sce, ob, mask); | |
725 if(ob->proxy) | |
726 build_dag_object(dag, scenenode, sce, ob->proxy, mask); | |
727 ················ | |
728 /* handled in next loop */ | |
729 if(ob->dup_group)· | |
730 ob->dup_group->id.flag |= LIB_DOIT; | |
731 } | |
732 ········ | |
733 /* add groups used in current scene objects */ | |
734 for(group= bmain->group.first; group; group= group->id.next) { | |
735 if(group->id.flag & LIB_DOIT) { | |
736 for(go= group->gobject.first; go; go= go->next) { | |
737 build_dag_object(dag, scenenode, sce, go->ob, ma sk); | |
738 } | |
739 group->id.flag &= ~LIB_DOIT; | |
740 } | |
741 } | |
742 ········ | |
743 /* Now all relations were built, but we need to solve 1 exceptional case ; | |
744 When objects have multiple "parents" (for example parent + constraint working on same object) | |
745 the relation type has to be synced. One of the parents can change, an d should give same event to child */ | |
746 ········ | |
747 /* nodes were callocced, so we can use node->color for temporal storage */ | |
748 for(node = sce->theDag->DagNode.first; node; node= node->next) { | |
749 if(node->type==ID_OB) { | |
750 for(itA = node->child; itA; itA= itA->next) { | |
751 if(itA->node->type==ID_OB) { | |
752 itA->node->color |= itA->type; | |
753 } | |
754 } | |
755 | |
756 /* also flush custom data mask */ | |
757 ((Object*)node->ob)->customdata_mask= node->customdata_m ask; | |
758 } | |
759 } | |
760 /* now set relations equal, so that when only one parent changes, the co rrect recalcs are found */ | |
761 for(node = sce->theDag->DagNode.first; node; node= node->next) { | |
762 if(node->type==ID_OB) { | |
763 for(itA = node->child; itA; itA= itA->next) { | |
764 if(itA->node->type==ID_OB) { | |
765 itA->type |= itA->node->color; | |
766 } | |
767 } | |
768 } | |
769 } | |
770 ········ | |
771 // cycle detection and solving | |
772 // solve_cycles(dag);··· | |
773 ········ | |
774 return dag; | |
775 } | |
776 | |
777 | |
778 void free_forest(DagForest *Dag)· | |
779 { /* remove all nodes and deps */ | |
780 DagNode *tempN; | |
781 DagAdjList *tempA;······ | |
782 DagAdjList *itA; | |
783 DagNode *itN = Dag->DagNode.first; | |
784 ········ | |
785 while (itN) { | |
786 itA = itN->child;······· | |
787 while (itA) { | |
788 tempA = itA; | |
789 itA = itA->next; | |
790 MEM_freeN(tempA);······················· | |
791 } | |
792 ················ | |
793 itA = itN->parent;······ | |
794 while (itA) { | |
795 tempA = itA; | |
796 itA = itA->next; | |
797 MEM_freeN(tempA);······················· | |
798 } | |
799 ················ | |
800 tempN = itN; | |
801 itN = itN->next; | |
802 MEM_freeN(tempN); | |
803 } | |
804 | |
805 BLI_ghash_free(Dag->nodeHash, NULL, NULL); | |
806 Dag->nodeHash= NULL; | |
807 Dag->DagNode.first = NULL; | |
808 Dag->DagNode.last = NULL; | |
809 Dag->numNodes = 0; | |
810 | |
811 } | |
812 | |
813 DagNode * dag_find_node (DagForest *forest,void * fob) | |
814 { | |
815 if(forest->nodeHash) | |
816 return BLI_ghash_lookup(forest->nodeHash, fob); | |
817 | |
818 return NULL; | |
819 } | |
820 | |
821 static int ugly_hack_sorry= 1; // prevent type check | |
822 | |
823 /* no checking of existence, use dag_find_node first or dag_get_node */ | |
824 DagNode * dag_add_node (DagForest *forest, void * fob) | |
825 { | |
826 DagNode *node; | |
827 ················ | |
828 node = MEM_callocN(sizeof(DagNode),"DAG node"); | |
829 if (node) { | |
830 node->ob = fob; | |
831 node->color = DAG_WHITE; | |
832 | |
833 if(ugly_hack_sorry) node->type = GS(((ID *) fob)->name); // sorry, done for pose sorting | |
834 if (forest->numNodes) { | |
835 ((DagNode *) forest->DagNode.last)->next = node; | |
836 forest->DagNode.last = node; | |
837 forest->numNodes++; | |
838 } else { | |
839 forest->DagNode.last = node; | |
840 forest->DagNode.first = node; | |
841 forest->numNodes = 1; | |
842 } | |
843 | |
844 if(!forest->nodeHash) | |
845 forest->nodeHash= BLI_ghash_new(BLI_ghashutil_ptrhash, B LI_ghashutil_ptrcmp, "dag_add_node gh"); | |
846 BLI_ghash_insert(forest->nodeHash, fob, node); | |
847 } | |
848 | |
849 return node; | |
850 } | |
851 | |
852 DagNode * dag_get_node (DagForest *forest,void * fob) | |
853 { | |
854 DagNode *node; | |
855 ········ | |
856 node = dag_find_node (forest, fob);····· | |
857 if (!node)· | |
858 node = dag_add_node(forest, fob); | |
859 return node; | |
860 } | |
861 | |
862 | |
863 | |
864 DagNode * dag_get_sub_node (DagForest *forest,void * fob) | |
865 { | |
866 DagNode *node; | |
867 DagAdjList *mainchild, *prev=NULL; | |
868 ········ | |
869 mainchild = ((DagNode *) forest->DagNode.first)->child; | |
870 /* remove from first node (scene) adj list if present */ | |
871 while (mainchild) { | |
872 if (mainchild->node == fob) { | |
873 if (prev) { | |
874 prev->next = mainchild->next; | |
875 MEM_freeN(mainchild); | |
876 break; | |
877 } else { | |
878 ((DagNode *) forest->DagNode.first)->child = mai nchild->next; | |
879 MEM_freeN(mainchild); | |
880 break; | |
881 } | |
882 } | |
883 prev = mainchild; | |
884 mainchild = mainchild->next; | |
885 } | |
886 node = dag_find_node (forest, fob);····· | |
887 if (!node)· | |
888 node = dag_add_node(forest, fob); | |
889 return node; | |
890 } | |
891 | |
892 static void dag_add_parent_relation(DagForest *UNUSED(forest), DagNode *fob1, Da gNode *fob2, short rel, const char *name)· | |
893 { | |
894 DagAdjList *itA = fob2->parent; | |
895 ········ | |
896 while (itA) { /* search if relation exist already */ | |
897 if (itA->node == fob1) { | |
898 itA->type |= rel; | |
899 itA->count += 1; | |
900 return; | |
901 } | |
902 itA = itA->next; | |
903 } | |
904 /* create new relation and insert at head. MALLOC alert! */ | |
905 itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list"); | |
906 itA->node = fob1; | |
907 itA->type = rel; | |
908 itA->count = 1; | |
909 itA->next = fob2->parent; | |
910 itA->name = name; | |
911 fob2->parent = itA; | |
912 } | |
913 | |
914 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel , const char *name)· | |
915 { | |
916 DagAdjList *itA = fob1->child; | |
917 ········ | |
918 /* parent relation is for cycle checking */ | |
919 dag_add_parent_relation(forest, fob1, fob2, rel, name); | |
920 | |
921 while (itA) { /* search if relation exist already */ | |
922 if (itA->node == fob2) { | |
923 itA->type |= rel; | |
924 itA->count += 1; | |
925 return; | |
926 } | |
927 itA = itA->next; | |
928 } | |
929 /* create new relation and insert at head. MALLOC alert! */ | |
930 itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list"); | |
931 itA->node = fob2; | |
932 itA->type = rel; | |
933 itA->count = 1; | |
934 itA->next = fob1->child; | |
935 itA->name = name; | |
936 fob1->child = itA; | |
937 } | |
938 | |
939 static const char *dag_node_name(DagNode *node) | |
940 { | |
941 if(node->ob == NULL) | |
942 return "null"; | |
943 else if(ugly_hack_sorry) | |
944 return ((ID*)(node->ob))->name+2; | |
945 else | |
946 return ((bPoseChannel*)(node->ob))->name; | |
947 } | |
948 | |
949 #if 0 | |
950 static void dag_node_print_dependencies(DagNode *node) | |
951 { | |
952 DagAdjList *itA; | |
953 | |
954 printf("%s depends on:\n", dag_node_name(node)); | |
955 | |
956 for(itA= node->parent; itA; itA= itA->next) | |
957 printf(" %s through %s\n", dag_node_name(itA->node), itA->name) ; | |
958 printf("\n"); | |
959 } | |
960 #endif | |
961 | |
962 static int dag_node_print_dependency_recurs(DagNode *node, DagNode *endnode) | |
963 { | |
964 DagAdjList *itA; | |
965 | |
966 if(node->color == DAG_BLACK) | |
967 return 0; | |
968 | |
969 node->color= DAG_BLACK; | |
970 | |
971 if(node == endnode) | |
972 return 1; | |
973 | |
974 for(itA= node->parent; itA; itA= itA->next) { | |
975 if(dag_node_print_dependency_recurs(itA->node, endnode)) { | |
976 printf(" %s depends on %s through %s.\n", dag_node_name (node), dag_node_name(itA->node), itA->name); | |
977 return 1; | |
978 } | |
979 } | |
980 | |
981 return 0; | |
982 } | |
983 | |
984 static void dag_node_print_dependency_cycle(DagForest *dag, DagNode *startnode, DagNode *endnode, const char *name) | |
985 { | |
986 DagNode *node; | |
987 | |
988 for(node = dag->DagNode.first; node; node= node->next) | |
989 node->color= DAG_WHITE; | |
990 | |
991 printf(" %s depends on %s through %s.\n", dag_node_name(endnode), dag_n ode_name(startnode), name); | |
992 dag_node_print_dependency_recurs(startnode, endnode); | |
993 printf("\n"); | |
994 } | |
995 | |
996 static int dag_node_recurs_level(DagNode *node, int level) | |
997 { | |
998 DagAdjList *itA; | |
999 int newlevel; | |
1000 | |
1001 node->color= DAG_BLACK; /* done */ | |
1002 newlevel= ++level; | |
1003 ········ | |
1004 for(itA= node->parent; itA; itA= itA->next) { | |
1005 if(itA->node->color==DAG_WHITE) { | |
1006 itA->node->ancestor_count= dag_node_recurs_level(itA->no de, level); | |
1007 newlevel= MAX2(newlevel, level+itA->node->ancestor_count ); | |
1008 } | |
1009 else | |
1010 newlevel= MAX2(newlevel, level+itA->node->ancestor_count ); | |
1011 } | |
1012 ········ | |
1013 return newlevel; | |
1014 } | |
1015 | |
1016 static void dag_check_cycle(DagForest *dag) | |
1017 { | |
1018 DagNode *node; | |
1019 DagAdjList *itA; | |
1020 | |
1021 /* tag nodes unchecked */ | |
1022 for(node = dag->DagNode.first; node; node= node->next) | |
1023 node->color= DAG_WHITE; | |
1024 ········ | |
1025 for(node = dag->DagNode.first; node; node= node->next) { | |
1026 if(node->color==DAG_WHITE) { | |
1027 node->ancestor_count= dag_node_recurs_level(node, 0); | |
1028 } | |
1029 } | |
1030 ········ | |
1031 /* check relations, and print errors */ | |
1032 for(node = dag->DagNode.first; node; node= node->next) { | |
1033 for(itA= node->parent; itA; itA= itA->next) { | |
1034 if(itA->node->ancestor_count > node->ancestor_count) { | |
1035 if(node->ob && itA->node->ob) { | |
1036 printf("Dependency cycle detected:\n"); | |
1037 dag_node_print_dependency_cycle(dag, itA ->node, node, itA->name); | |
1038 } | |
1039 } | |
1040 } | |
1041 } | |
1042 | |
1043 /* parent relations are only needed for cycle checking, so free now */ | |
1044 for(node = dag->DagNode.first; node; node= node->next) { | |
1045 while (node->parent) { | |
1046 itA = node->parent->next; | |
1047 MEM_freeN(node->parent);························ | |
1048 node->parent = itA; | |
1049 } | |
1050 } | |
1051 } | |
1052 | |
1053 /* | |
1054 * MainDAG is the DAG of all objects in current scene | |
1055 * used only for drawing there is one also in each scene | |
1056 */ | |
1057 static DagForest * MainDag = NULL; | |
1058 | |
1059 DagForest *getMainDag(void) | |
1060 { | |
1061 return MainDag; | |
1062 } | |
1063 | |
1064 | |
1065 void setMainDag(DagForest *dag) | |
1066 { | |
1067 MainDag = dag; | |
1068 } | |
1069 | |
1070 | |
1071 /* | |
1072 * note for BFS/DFS | |
1073 * in theory we should sweep the whole array | |
1074 * but in our case the first node is the scene | |
1075 * and is linked to every other object | |
1076 * | |
1077 * for general case we will need to add outer loop | |
1078 */ | |
1079 | |
1080 /* | |
1081 * ToDo : change pos kludge | |
1082 */ | |
1083 | |
1084 /* adjust levels for drawing in oops space */ | |
1085 void graph_bfs(void) | |
1086 { | |
1087 DagNode *node; | |
1088 DagNodeQueue *nqueue; | |
1089 int pos[50]; | |
1090 int i; | |
1091 DagAdjList *itA; | |
1092 int minheight; | |
1093 ········ | |
1094 /* fprintf(stderr,"starting BFS \n ------------\n"); */· | |
1095 nqueue = queue_create(DAGQUEUEALLOC); | |
1096 for ( i=0; i<50; i++) | |
1097 pos[i] = 0; | |
1098 ········ | |
1099 /* Init | |
1100 * dagnode.first is alway the root (scene)· | |
1101 */ | |
1102 node = MainDag->DagNode.first; | |
1103 while(node) { | |
1104 node->color = DAG_WHITE; | |
1105 node->BFS_dist = 9999; | |
1106 node->k = 0; | |
1107 node = node->next; | |
1108 } | |
1109 ········ | |
1110 node = MainDag->DagNode.first; | |
1111 if (node->color == DAG_WHITE) { | |
1112 node->color = DAG_GRAY; | |
1113 node->BFS_dist = 1; | |
1114 push_queue(nqueue,node);·· | |
1115 while(nqueue->count) { | |
1116 node = pop_queue(nqueue); | |
1117 ························ | |
1118 minheight = pos[node->BFS_dist]; | |
1119 itA = node->child; | |
1120 while(itA != NULL) { | |
1121 if(itA->node->color == DAG_WHITE) { | |
1122 itA->node->color = DAG_GRAY; | |
1123 itA->node->BFS_dist = node->BFS_dist + 1 ; | |
1124 itA->node->k = (float) minheight; | |
1125 push_queue(nqueue,itA->node); | |
1126 } | |
1127 ································ | |
1128 else { | |
1129 fprintf(stderr,"bfs not dag tree edge co lor :%i \n",itA->node->color); | |
1130 } | |
1131 | |
1132 ································ | |
1133 itA = itA->next; | |
1134 } | |
1135 if (pos[node->BFS_dist] > node->k ) { | |
1136 pos[node->BFS_dist] += 1;······································ | |
1137 node->k = (float) pos[node->BFS_dist]; | |
1138 } else { | |
1139 pos[node->BFS_dist] = (int) node->k +1; | |
1140 } | |
1141 set_node_xy(node, node->BFS_dist*DEPSX*2, pos[node->BFS_ dist]*DEPSY*2); | |
1142 node->color = DAG_BLACK; | |
1143 /* | |
1144 fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);··· | |
1145 */ | |
1146 } | |
1147 } | |
1148 queue_delete(nqueue); | |
1149 } | |
1150 | |
1151 int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, gra ph_action_func post_func, void **data) { | |
1152 DagNode *node; | |
1153 ········ | |
1154 node = dag->DagNode.first; | |
1155 return pre_and_post_source_BFS(dag, mask, node, pre_func, post_func, data); | |
1156 } | |
1157 | |
1158 | |
1159 int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_a ction_func pre_func, graph_action_func post_func, void **data) | |
1160 { | |
1161 DagNode *node; | |
1162 DagNodeQueue *nqueue; | |
1163 DagAdjList *itA; | |
1164 int retval = 0; | |
1165 /* fprintf(stderr,"starting BFS \n ------------\n"); */· | |
1166 ········ | |
1167 /* Init | |
1168 * dagnode.first is alway the root (scene)· | |
1169 */ | |
1170 node = dag->DagNode.first; | |
1171 nqueue = queue_create(DAGQUEUEALLOC); | |
1172 while(node) { | |
1173 node->color = DAG_WHITE; | |
1174 node->BFS_dist = 9999; | |
1175 node = node->next; | |
1176 } | |
1177 ········ | |
1178 node = source; | |
1179 if (node->color == DAG_WHITE) { | |
1180 node->color = DAG_GRAY; | |
1181 node->BFS_dist = 1; | |
1182 pre_func(node->ob,data); | |
1183 ················ | |
1184 while(nqueue->count) { | |
1185 node = pop_queue(nqueue); | |
1186 ························ | |
1187 itA = node->child; | |
1188 while(itA != NULL) { | |
1189 if((itA->node->color == DAG_WHITE) && (itA->type & mask)) { | |
1190 itA->node->color = DAG_GRAY; | |
1191 itA->node->BFS_dist = node->BFS_dist + 1 ; | |
1192 push_queue(nqueue,itA->node); | |
1193 pre_func(node->ob,data); | |
1194 } | |
1195 ································ | |
1196 else { // back or cross edge | |
1197 retval = 1; | |
1198 } | |
1199 itA = itA->next; | |
1200 } | |
1201 post_func(node->ob,data); | |
1202 node->color = DAG_BLACK; | |
1203 /* | |
1204 fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);··· | |
1205 */ | |
1206 } | |
1207 } | |
1208 queue_delete(nqueue); | |
1209 return retval; | |
1210 } | |
1211 | |
1212 /* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/ | |
1213 DagNodeQueue * graph_dfs(void) | |
1214 { | |
1215 DagNode *node; | |
1216 DagNodeQueue *nqueue; | |
1217 DagNodeQueue *retqueue; | |
1218 int pos[50]; | |
1219 int i; | |
1220 DagAdjList *itA; | |
1221 int time; | |
1222 int skip = 0; | |
1223 int minheight; | |
1224 int maxpos=0; | |
1225 /* int is_cycle = 0; */ /* UNUSED */ | |
1226 /* | |
1227 *fprintf(stderr,"starting DFS \n ------------\n"); | |
1228 */····· | |
1229 nqueue = queue_create(DAGQUEUEALLOC); | |
1230 retqueue = queue_create(MainDag->numNodes); | |
1231 for ( i=0; i<50; i++) | |
1232 pos[i] = 0; | |
1233 ········ | |
1234 /* Init | |
1235 * dagnode.first is alway the root (scene)· | |
1236 */ | |
1237 node = MainDag->DagNode.first; | |
1238 while(node) { | |
1239 node->color = DAG_WHITE; | |
1240 node->DFS_dist = 9999; | |
1241 node->DFS_dvtm = node->DFS_fntm = 9999; | |
1242 node->k = 0; | |
1243 node = node->next; | |
1244 } | |
1245 ········ | |
1246 time = 1; | |
1247 ········ | |
1248 node = MainDag->DagNode.first; | |
1249 | |
1250 do { | |
1251 if (node->color == DAG_WHITE) { | |
1252 node->color = DAG_GRAY; | |
1253 node->DFS_dist = 1; | |
1254 node->DFS_dvtm = time; | |
1255 time++; | |
1256 push_stack(nqueue,node);·· | |
1257 ························ | |
1258 while(nqueue->count) { | |
1259 //graph_print_queue(nqueue); | |
1260 | |
1261 skip = 0; | |
1262 node = get_top_node_queue(nqueue); | |
1263 ························ | |
1264 minheight = pos[node->DFS_dist]; | |
1265 | |
1266 itA = node->child; | |
1267 while(itA != NULL) { | |
1268 if(itA->node->color == DAG_WHITE) { | |
1269 itA->node->DFS_dvtm = time; | |
1270 itA->node->color = DAG_GRAY; | |
1271 | |
1272 time++; | |
1273 itA->node->DFS_dist = node->DFS_dist + 1 ; | |
1274 itA->node->k = (float) minheight; | |
1275 push_stack(nqueue,itA->node); | |
1276 skip = 1; | |
1277 break; | |
1278 } else {· | |
1279 if (itA->node->color == DAG_GRAY) { // b ack edge | |
1280 fprintf(stderr,"dfs back edge :% 15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name); | |
1281 /* is_cycle = 1; */ /* UNUSED */ | |
1282 } else if (itA->node->color == DAG_BLACK ) { | |
1283 ; | |
1284 /* already processed node but we may want later to change distance either to shorter to longer. | |
1285 * DFS_dist is the first encount er·· | |
1286 */ | |
1287 /*if (node->DFS_dist >= itA->nod e->DFS_dist) | |
1288 itA->node->DFS_dist = no de->DFS_dist + 1; | |
1289 | |
1290 fprintf(stderr,"dfs forw ard or cross edge :%15s %i-%i %15s %i-%i \n", | |
1291 ((ID *) node->ob )->name, | |
1292 node->DFS_dvtm,· | |
1293 node->DFS_fntm,· | |
1294 ((ID *) itA->nod e->ob)->name,· | |
1295 itA->node->DFS_d vtm, | |
1296 itA->node->DFS_f ntm); | |
1297 */ | |
1298 } else· | |
1299 fprintf(stderr,"dfs unknown edge \n"); | |
1300 } | |
1301 itA = itA->next; | |
1302 }······················· | |
1303 | |
1304 if (!skip) { | |
1305 node = pop_queue(nqueue); | |
1306 node->color = DAG_BLACK; | |
1307 | |
1308 node->DFS_fntm = time; | |
1309 time++; | |
1310 if (node->DFS_dist > maxpos) | |
1311 maxpos = node->DFS_dist; | |
1312 if (pos[node->DFS_dist] > node->k ) { | |
1313 pos[node->DFS_dist] += 1;······································ | |
1314 node->k = (float) pos[node->DFS_dist]; | |
1315 } else { | |
1316 pos[node->DFS_dist] = (int) node->k +1; | |
1317 } | |
1318 set_node_xy(node, node->DFS_dist*DEPSX*2, pos[no de->DFS_dist]*DEPSY*2); | |
1319 ································ | |
1320 /* | |
1321 fprintf(stderr,"DFS node : %20s %i %i %i %i\n", ((ID *) node->ob)->name,node->BFS_dist, node->DFS_dist, node->DFS_dvtm, node->DF S_fntm );······· | |
1322 */ | |
1323 push_stack(retqueue,node); | |
1324 ································ | |
1325 } | |
1326 } | |
1327 } | |
1328 node = node->next; | |
1329 } while (node); | |
1330 // fprintf(stderr,"i size : %i \n", maxpos); | |
1331 | |
1332 queue_delete(nqueue); | |
1333 return(retqueue); | |
1334 } | |
1335 | |
1336 /* unused */ | |
1337 int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, gra ph_action_func post_func, void **data) { | |
1338 DagNode *node; | |
1339 | |
1340 node = dag->DagNode.first; | |
1341 return pre_and_post_source_DFS(dag, mask, node, pre_func, post_func, data); | |
1342 } | |
1343 | |
1344 int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_a ction_func pre_func, graph_action_func post_func, void **data) | |
1345 { | |
1346 DagNode *node; | |
1347 DagNodeQueue *nqueue; | |
1348 DagAdjList *itA; | |
1349 int time; | |
1350 int skip = 0; | |
1351 int retval = 0; | |
1352 /* | |
1353 *fprintf(stderr,"starting DFS \n ------------\n"); | |
1354 */····· | |
1355 nqueue = queue_create(DAGQUEUEALLOC); | |
1356 ········ | |
1357 /* Init | |
1358 * dagnode.first is alway the root (scene)· | |
1359 */ | |
1360 node = dag->DagNode.first; | |
1361 while(node) { | |
1362 node->color = DAG_WHITE; | |
1363 node->DFS_dist = 9999; | |
1364 node->DFS_dvtm = node->DFS_fntm = 9999; | |
1365 node->k = 0; | |
1366 node = node->next; | |
1367 } | |
1368 ········ | |
1369 time = 1; | |
1370 ········ | |
1371 node = source; | |
1372 do { | |
1373 if (node->color == DAG_WHITE) { | |
1374 node->color = DAG_GRAY; | |
1375 node->DFS_dist = 1; | |
1376 node->DFS_dvtm = time; | |
1377 time++; | |
1378 push_stack(nqueue,node);·· | |
1379 pre_func(node->ob,data); | |
1380 | |
1381 while(nqueue->count) { | |
1382 skip = 0; | |
1383 node = get_top_node_queue(nqueue); | |
1384 ································································ | |
1385 itA = node->child; | |
1386 while(itA != NULL) { | |
1387 if((itA->node->color == DAG_WHITE) && (i tA->type & mask) ) { | |
1388 itA->node->DFS_dvtm = time; | |
1389 itA->node->color = DAG_GRAY; | |
1390 ················································ | |
1391 time++; | |
1392 itA->node->DFS_dist = node->DFS_ dist + 1; | |
1393 push_stack(nqueue,itA->node); | |
1394 pre_func(node->ob,data); | |
1395 | |
1396 skip = 1; | |
1397 break; | |
1398 } else { | |
1399 if (itA->node->color == DAG_GRAY ) {// back edge | |
1400 retval = 1; | |
1401 } | |
1402 // else if (itA->node->color == DAG _BLACK) { // cross or forward | |
1403 // ; | |
1404 } | |
1405 itA = itA->next; | |
1406 }······················· | |
1407 ································ | |
1408 if (!skip) { | |
1409 node = pop_queue(nqueue); | |
1410 node->color = DAG_BLACK; | |
1411 ········································ | |
1412 node->DFS_fntm = time; | |
1413 time++; | |
1414 post_func(node->ob,data); | |
1415 } | |
1416 } | |
1417 } | |
1418 node = node->next; | |
1419 } while (node); | |
1420 queue_delete(nqueue); | |
1421 return(retval); | |
1422 } | |
1423 | |
1424 | |
1425 // used to get the obs owning a datablock | |
1426 struct DagNodeQueue *get_obparents(struct DagForest *dag, void *ob)· | |
1427 { | |
1428 DagNode * node, *node1; | |
1429 DagNodeQueue *nqueue; | |
1430 DagAdjList *itA; | |
1431 | |
1432 node = dag_find_node(dag,ob); | |
1433 if(node==NULL) { | |
1434 return NULL; | |
1435 } | |
1436 else if (node->ancestor_count == 1) { // simple case | |
1437 nqueue = queue_create(1); | |
1438 push_queue(nqueue,node); | |
1439 } else { // need to go over the whole dag for adj list | |
1440 nqueue = queue_create(node->ancestor_count); | |
1441 ················ | |
1442 node1 = dag->DagNode.first; | |
1443 do { | |
1444 if (node1->DFS_fntm > node->DFS_fntm) { // a parent is f inished after child. must check adj list | |
1445 itA = node->child; | |
1446 while(itA != NULL) { | |
1447 if ((itA->node == node) && (itA->type == DAG_RL_DATA)) { | |
1448 push_queue(nqueue,node); | |
1449 } | |
1450 itA = itA->next; | |
1451 } | |
1452 } | |
1453 node1 = node1->next; | |
1454 } while (node1); | |
1455 } | |
1456 return nqueue; | |
1457 } | |
1458 | |
1459 struct DagNodeQueue *get_first_ancestors(struct DagForest *dag, void *ob) | |
1460 { | |
1461 DagNode * node, *node1; | |
1462 DagNodeQueue *nqueue; | |
1463 DagAdjList *itA; | |
1464 ········ | |
1465 node = dag_find_node(dag,ob); | |
1466 ········ | |
1467 // need to go over the whole dag for adj list | |
1468 nqueue = queue_create(node->ancestor_count); | |
1469 ········ | |
1470 node1 = dag->DagNode.first; | |
1471 do { | |
1472 if (node1->DFS_fntm > node->DFS_fntm) {· | |
1473 itA = node->child; | |
1474 while(itA != NULL) { | |
1475 if (itA->node == node) { | |
1476 push_queue(nqueue,node); | |
1477 } | |
1478 itA = itA->next; | |
1479 } | |
1480 } | |
1481 node1 = node1->next; | |
1482 } while (node1); | |
1483 ········ | |
1484 return nqueue;·· | |
1485 } | |
1486 | |
1487 // standard DFS list | |
1488 struct DagNodeQueue *get_all_childs(struct DagForest *dag, void *ob) | |
1489 { | |
1490 DagNode *node; | |
1491 DagNodeQueue *nqueue; | |
1492 DagNodeQueue *retqueue; | |
1493 DagAdjList *itA; | |
1494 int time; | |
1495 int skip = 0; | |
1496 | |
1497 nqueue = queue_create(DAGQUEUEALLOC); | |
1498 retqueue = queue_create(dag->numNodes); // was MainDag... why? (ton) | |
1499 ········ | |
1500 node = dag->DagNode.first; | |
1501 while(node) { | |
1502 node->color = DAG_WHITE; | |
1503 node = node->next; | |
1504 } | |
1505 ········ | |
1506 time = 1; | |
1507 ········ | |
1508 node = dag_find_node(dag, ob); // could be done in loop above (ton) | |
1509 if(node) { // can be null for newly added objects | |
1510 ················ | |
1511 node->color = DAG_GRAY; | |
1512 time++; | |
1513 push_stack(nqueue,node);·· | |
1514 ················ | |
1515 while(nqueue->count) { | |
1516 ························ | |
1517 skip = 0; | |
1518 node = get_top_node_queue(nqueue); | |
1519 ········································ | |
1520 itA = node->child; | |
1521 while(itA != NULL) { | |
1522 if(itA->node->color == DAG_WHITE) { | |
1523 itA->node->DFS_dvtm = time; | |
1524 itA->node->color = DAG_GRAY; | |
1525 ········································ | |
1526 time++; | |
1527 push_stack(nqueue,itA->node); | |
1528 skip = 1; | |
1529 break; | |
1530 }· | |
1531 itA = itA->next; | |
1532 }······················· | |
1533 ························ | |
1534 if (!skip) { | |
1535 node = pop_queue(nqueue); | |
1536 node->color = DAG_BLACK; | |
1537 ································ | |
1538 time++; | |
1539 push_stack(retqueue,node);······················ | |
1540 } | |
1541 } | |
1542 } | |
1543 queue_delete(nqueue); | |
1544 return(retqueue); | |
1545 } | |
1546 | |
1547 /* unused */ | |
1548 short are_obs_related(struct DagForest *dag, void *ob1, void *ob2) { | |
1549 DagNode * node; | |
1550 DagAdjList *itA; | |
1551 ········ | |
1552 node = dag_find_node(dag, ob1); | |
1553 ········ | |
1554 itA = node->child; | |
1555 while(itA != NULL) { | |
1556 if(itA->node->ob == ob2) { | |
1557 return itA->node->type; | |
1558 }· | |
1559 itA = itA->next; | |
1560 } | |
1561 return DAG_NO_RELATION; | |
1562 } | |
1563 | |
1564 int is_acyclic( DagForest *dag) { | |
1565 return dag->is_acyclic; | |
1566 } | |
1567 | |
1568 void set_node_xy(DagNode *node, float x, float y) | |
1569 { | |
1570 node->x = x; | |
1571 node->y = y; | |
1572 } | |
1573 | |
1574 | |
1575 /* debug test functions */ | |
1576 | |
1577 void graph_print_queue(DagNodeQueue *nqueue) | |
1578 {······· | |
1579 DagNodeQueueElem *queueElem; | |
1580 ········ | |
1581 queueElem = nqueue->first; | |
1582 while(queueElem) { | |
1583 fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->n ame,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm); | |
1584 queueElem = queueElem->next;············ | |
1585 } | |
1586 fprintf(stderr,"\n"); | |
1587 } | |
1588 | |
1589 void graph_print_queue_dist(DagNodeQueue *nqueue) | |
1590 {······· | |
1591 DagNodeQueueElem *queueElem; | |
1592 int count; | |
1593 ········ | |
1594 queueElem = nqueue->first; | |
1595 count = 0; | |
1596 while(queueElem) { | |
1597 fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->o b)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm); | |
1598 while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;} | |
1599 fputc('|',stderr);· | |
1600 while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;} | |
1601 fputc('|',stderr); | |
1602 fputc('\n',stderr); | |
1603 count = 0; | |
1604 queueElem = queueElem->next;············ | |
1605 } | |
1606 fprintf(stderr,"\n"); | |
1607 } | |
1608 | |
1609 void graph_print_adj_list(void) | |
1610 { | |
1611 DagNode *node; | |
1612 DagAdjList *itA; | |
1613 ········ | |
1614 node = (getMainDag())->DagNode.first; | |
1615 while(node) { | |
1616 fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node ->color);··············· | |
1617 itA = node->child; | |
1618 while (itA) { | |
1619 fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name); | |
1620 ························ | |
1621 itA = itA->next; | |
1622 } | |
1623 fprintf(stderr,"\n"); | |
1624 node = node->next; | |
1625 } | |
1626 } | |
1627 | |
1628 /* ************************ API *********************** */ | |
1629 | |
1630 /* mechanism to allow editors to be informed of depsgraph updates, | |
1631 to do their own updates based on changes... */ | |
1632 static void (*EditorsUpdateCb)(Main *bmain, ID *id)= NULL; | |
1633 | |
1634 void DAG_editors_update_cb(void (*func)(Main *bmain, ID *id)) | |
1635 { | |
1636 EditorsUpdateCb= func; | |
1637 } | |
1638 | |
1639 static void dag_editors_update(Main *bmain, ID *id) | |
1640 { | |
1641 if(EditorsUpdateCb) | |
1642 EditorsUpdateCb(bmain, id); | |
1643 } | |
1644 | |
1645 /* groups with objects in this scene need to be put in the right order as well * / | |
1646 static void scene_sort_groups(Main *bmain, Scene *sce) | |
1647 { | |
1648 Base *base; | |
1649 Group *group; | |
1650 GroupObject *go; | |
1651 Object *ob; | |
1652 ········ | |
1653 /* test; are group objects all in this scene? */ | |
1654 for(ob= bmain->object.first; ob; ob= ob->id.next) { | |
1655 ob->id.flag &= ~LIB_DOIT; | |
1656 ob->id.newid= NULL; /* newid abuse for GroupObject */ | |
1657 } | |
1658 for(base = sce->base.first; base; base= base->next) | |
1659 base->object->id.flag |= LIB_DOIT; | |
1660 ········ | |
1661 for(group= bmain->group.first; group; group= group->id.next) { | |
1662 for(go= group->gobject.first; go; go= go->next) { | |
1663 if((go->ob->id.flag & LIB_DOIT)==0) | |
1664 break; | |
1665 } | |
1666 /* this group is entirely in this scene */ | |
1667 if(go==NULL) { | |
1668 ListBase listb= {NULL, NULL}; | |
1669 ························ | |
1670 for(go= group->gobject.first; go; go= go->next) | |
1671 go->ob->id.newid= (ID *)go; | |
1672 ························ | |
1673 /* in order of sorted bases we reinsert group objects */ | |
1674 for(base = sce->base.first; base; base= base->next) { | |
1675 ································ | |
1676 if(base->object->id.newid) { | |
1677 go= (GroupObject *)base->object->id.newi d; | |
1678 base->object->id.newid= NULL; | |
1679 BLI_remlink( &group->gobject, go); | |
1680 BLI_addtail( &listb, go); | |
1681 } | |
1682 } | |
1683 /* copy the newly sorted listbase */ | |
1684 group->gobject= listb; | |
1685 } | |
1686 } | |
1687 } | |
1688 | |
1689 /* sort the base list on dependency order */ | |
1690 void DAG_scene_sort(Main *bmain, Scene *sce) | |
1691 { | |
1692 DagNode *node; | |
1693 DagNodeQueue *nqueue; | |
1694 DagAdjList *itA; | |
1695 int time; | |
1696 int skip = 0; | |
1697 ListBase tempbase; | |
1698 Base *base; | |
1699 ········ | |
1700 tempbase.first= tempbase.last= NULL; | |
1701 ········ | |
1702 build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA); | |
1703 ········ | |
1704 dag_check_cycle(sce->theDag); | |
1705 | |
1706 nqueue = queue_create(DAGQUEUEALLOC); | |
1707 ········ | |
1708 for(node = sce->theDag->DagNode.first; node; node= node->next) { | |
1709 node->color = DAG_WHITE; | |
1710 } | |
1711 ········ | |
1712 time = 1; | |
1713 ········ | |
1714 node = sce->theDag->DagNode.first; | |
1715 ········ | |
1716 node->color = DAG_GRAY; | |
1717 time++; | |
1718 push_stack(nqueue,node);·· | |
1719 ········ | |
1720 while(nqueue->count) { | |
1721 ················ | |
1722 skip = 0; | |
1723 node = get_top_node_queue(nqueue); | |
1724 ················ | |
1725 itA = node->child; | |
1726 while(itA != NULL) { | |
1727 if(itA->node->color == DAG_WHITE) { | |
1728 itA->node->DFS_dvtm = time; | |
1729 itA->node->color = DAG_GRAY; | |
1730 ································ | |
1731 time++; | |
1732 push_stack(nqueue,itA->node); | |
1733 skip = 1; | |
1734 break; | |
1735 }· | |
1736 itA = itA->next; | |
1737 }······················· | |
1738 ················ | |
1739 if (!skip) { | |
1740 if (node) { | |
1741 node = pop_queue(nqueue); | |
1742 if (node->ob == sce) // we are done | |
1743 break ; | |
1744 node->color = DAG_BLACK; | |
1745 ································ | |
1746 time++; | |
1747 base = sce->base.first; | |
1748 while (base && base->object != node->ob) | |
1749 base = base->next; | |
1750 if(base) { | |
1751 BLI_remlink(&sce->base,base); | |
1752 BLI_addhead(&tempbase,base); | |
1753 } | |
1754 }······· | |
1755 } | |
1756 } | |
1757 ········ | |
1758 // temporal correction for circular dependancies | |
1759 base = sce->base.first; | |
1760 while (base) { | |
1761 BLI_remlink(&sce->base,base); | |
1762 BLI_addhead(&tempbase,base); | |
1763 //if(G.f & G_DEBUG)· | |
1764 printf("cyclic %s\n", base->object->id.name); | |
1765 base = sce->base.first; | |
1766 } | |
1767 ········ | |
1768 sce->base = tempbase; | |
1769 queue_delete(nqueue); | |
1770 ········ | |
1771 /* all groups with objects in this scene gets resorted too */ | |
1772 scene_sort_groups(bmain, sce); | |
1773 ········ | |
1774 if(G.f & G_DEBUG) { | |
1775 printf("\nordered\n"); | |
1776 for(base = sce->base.first; base; base= base->next) { | |
1777 printf(" %s\n", base->object->id.name); | |
1778 } | |
1779 } | |
1780 /* temporal...? */ | |
1781 sce->recalc |= SCE_PRV_CHANGED; /* test for 3d preview */ | |
1782 } | |
1783 | |
1784 /* node was checked to have lasttime != curtime and is if type ID_OB */ | |
1785 static void flush_update_node(DagNode *node, unsigned int layer, int curtime) | |
1786 { | |
1787 DagAdjList *itA; | |
1788 Object *ob, *obc; | |
1789 int oldflag, changed=0; | |
1790 unsigned int all_layer; | |
1791 ········ | |
1792 node->lasttime= curtime; | |
1793 ········ | |
1794 ob= node->ob; | |
1795 if(ob && (ob->recalc & OB_RECALC_ALL)) { | |
1796 all_layer= node->scelay; | |
1797 | |
1798 /* got an object node that changes, now check relations */ | |
1799 for(itA = node->child; itA; itA= itA->next) { | |
1800 all_layer |= itA->lay; | |
1801 /* the relationship is visible */ | |
1802 if((itA->lay & layer)) { // XXX || (itA->node->ob == obe dit) | |
1803 if(itA->node->type==ID_OB) { | |
1804 obc= itA->node->ob; | |
1805 oldflag= obc->recalc; | |
1806 ········································ | |
1807 /* got a ob->obc relation, now check if flag needs flush */ | |
1808 if(ob->recalc & OB_RECALC_OB) { | |
1809 if(itA->type & DAG_RL_OB_OB) { | |
1810 //printf("ob %s changes ob %s\n", ob->id.name, obc->id.name); | |
1811 obc->recalc |= OB_RECALC _OB; | |
1812 } | |
1813 if(itA->type & DAG_RL_OB_DATA) { | |
1814 //printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name); | |
1815 obc->recalc |= OB_RECALC _DATA; | |
1816 } | |
1817 } | |
1818 if(ob->recalc & OB_RECALC_DATA) { | |
1819 if(itA->type & DAG_RL_DATA_OB) { | |
1820 //printf("obdata %s chan ges ob %s\n", ob->id.name, obc->id.name); | |
1821 obc->recalc |= OB_RECALC _OB; | |
1822 } | |
1823 if(itA->type & DAG_RL_DATA_DATA) { | |
1824 //printf("obdata %s chan ges obdata %s\n", ob->id.name, obc->id.name); | |
1825 obc->recalc |= OB_RECALC _DATA; | |
1826 } | |
1827 } | |
1828 if(oldflag!=obc->recalc) changed= 1; | |
1829 } | |
1830 } | |
1831 } | |
1832 /* even nicer, we can clear recalc flags... */ | |
1833 if((all_layer & layer)==0) { // XXX && (ob != obedit)) { | |
1834 /* but existing displaylists or derivedmesh should be fr eed */ | |
1835 if(ob->recalc & OB_RECALC_DATA) | |
1836 object_free_display(ob); | |
1837 ························ | |
1838 ob->recalc &= ~OB_RECALC_ALL; | |
1839 } | |
1840 } | |
1841 ········ | |
1842 /* check case where child changes and parent forcing obdata to change */ | |
1843 /* should be done regardless if this ob has recalc set */ | |
1844 /* could merge this in with loop above...? (ton) */ | |
1845 for(itA = node->child; itA; itA= itA->next) { | |
1846 /* the relationship is visible */ | |
1847 if((itA->lay & layer)) { // XXX || (itA->node->o b == obedit) | |
1848 if(itA->node->type==ID_OB) { | |
1849 obc= itA->node->ob; | |
1850 /* child moves */ | |
1851 if((obc->recalc & OB_RECALC_ALL)==OB_RECALC_OB) { | |
1852 /* parent has deforming info */ | |
1853 if(itA->type & (DAG_RL_OB_DATA|DAG_RL_DA TA_DATA)) { | |
1854 // printf("parent %s changes ob %s\n", ob->id.name, obc->id.name); | |
1855 obc->recalc |= OB_RECALC_DATA; | |
1856 } | |
1857 } | |
1858 } | |
1859 } | |
1860 } | |
1861 ········ | |
1862 /* we only go deeper if node not checked or something changed */ | |
1863 for(itA = node->child; itA; itA= itA->next) { | |
1864 if(changed || itA->node->lasttime!=curtime)· | |
1865 flush_update_node(itA->node, layer, curtime); | |
1866 } | |
1867 ········ | |
1868 } | |
1869 | |
1870 /* node was checked to have lasttime != curtime , and is of type ID_OB */ | |
1871 static unsigned int flush_layer_node(Scene *sce, DagNode *node, int curtime) | |
1872 { | |
1873 DagAdjList *itA; | |
1874 ········ | |
1875 node->lasttime= curtime; | |
1876 node->lay= node->scelay; | |
1877 ········ | |
1878 for(itA = node->child; itA; itA= itA->next) { | |
1879 if(itA->node->type==ID_OB) { | |
1880 if(itA->node->lasttime!=curtime) { | |
1881 itA->lay= flush_layer_node(sce, itA->node, curti me); // lay is only set once for each relation | |
1882 } | |
1883 else itA->lay= itA->node->lay; | |
1884 ························ | |
1885 node->lay |= itA->lay; | |
1886 } | |
1887 } | |
1888 | |
1889 return node->lay; | |
1890 } | |
1891 | |
1892 /* node was checked to have lasttime != curtime , and is of type ID_OB */ | |
1893 static void flush_pointcache_reset(Scene *scene, DagNode *node, int curtime, int reset) | |
1894 { | |
1895 DagAdjList *itA; | |
1896 Object *ob; | |
1897 ········ | |
1898 node->lasttime= curtime; | |
1899 ········ | |
1900 for(itA = node->child; itA; itA= itA->next) { | |
1901 if(itA->node->type==ID_OB) { | |
1902 if(itA->node->lasttime!=curtime) { | |
1903 ob= (Object*)(itA->node->ob); | |
1904 | |
1905 if(reset || (ob->recalc & OB_RECALC_ALL)) { | |
1906 if(BKE_ptcache_object_reset(scene, ob, P TCACHE_RESET_DEPSGRAPH)) | |
1907 ob->recalc |= OB_RECALC_DATA; | |
1908 | |
1909 flush_pointcache_reset(scene, itA->node, curtime, 1); | |
1910 } | |
1911 else | |
1912 flush_pointcache_reset(scene, itA->node, curtime, 0); | |
1913 } | |
1914 } | |
1915 } | |
1916 } | |
1917 | |
1918 /* flush layer flags to dependencies */ | |
1919 static void dag_scene_flush_layers(Scene *sce, int lay) | |
1920 { | |
1921 DagNode *node, *firstnode; | |
1922 DagAdjList *itA; | |
1923 Base *base; | |
1924 int lasttime; | |
1925 | |
1926 firstnode= sce->theDag->DagNode.first; // always scene node | |
1927 | |
1928 for(itA = firstnode->child; itA; itA= itA->next) | |
1929 itA->lay= 0; | |
1930 | |
1931 sce->theDag->time++; // so we know which nodes were accessed | |
1932 lasttime= sce->theDag->time; | |
1933 | |
1934 /* update layer flags in nodes */ | |
1935 for(base= sce->base.first; base; base= base->next) { | |
1936 node= dag_get_node(sce->theDag, base->object); | |
1937 node->scelay= base->object->lay; | |
1938 } | |
1939 | |
1940 /* ensure cameras are set as if they are on a visible layer, because | |
1941 * they ared still used for rendering or setting the camera view | |
1942 * | |
1943 * XXX, this wont work for local view / unlocked camera's */ | |
1944 if(sce->camera) { | |
1945 node= dag_get_node(sce->theDag, sce->camera); | |
1946 node->scelay |= lay; | |
1947 } | |
1948 | |
1949 #ifdef DURIAN_CAMERA_SWITCH | |
1950 { | |
1951 TimeMarker *m; | |
1952 | |
1953 for(m= sce->markers.first; m; m= m->next) { | |
1954 if(m->camera) { | |
1955 node= dag_get_node(sce->theDag, m->camera); | |
1956 node->scelay |= lay; | |
1957 } | |
1958 } | |
1959 } | |
1960 #endif | |
1961 | |
1962 /* flush layer nodes to dependencies */ | |
1963 for(itA = firstnode->child; itA; itA= itA->next) | |
1964 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)· | |
1965 flush_layer_node(sce, itA->node, lasttime); | |
1966 } | |
1967 | |
1968 static void dag_tag_renderlayers(Scene *sce, unsigned int lay) | |
1969 { | |
1970 if(sce->nodetree) { | |
1971 bNode *node; | |
1972 Base *base; | |
1973 unsigned int lay_changed= 0; | |
1974 ················ | |
1975 for(base= sce->base.first; base; base= base->next) | |
1976 if(base->lay & lay) | |
1977 if(base->object->recalc) | |
1978 lay_changed |= base->lay; | |
1979 ························ | |
1980 for(node= sce->nodetree->nodes.first; node; node= node->next) { | |
1981 if(node->id==(ID *)sce) { | |
1982 SceneRenderLayer *srl= BLI_findlink(&sce->r.laye rs, node->custom1); | |
1983 if(srl && (srl->lay & lay_changed)) | |
1984 nodeUpdate(sce->nodetree, node); | |
1985 } | |
1986 } | |
1987 } | |
1988 } | |
1989 | |
1990 /* flushes all recalc flags in objects down the dependency tree */ | |
1991 void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const sho rt time) | |
1992 { | |
1993 DagNode *firstnode; | |
1994 DagAdjList *itA; | |
1995 Object *ob; | |
1996 int lasttime; | |
1997 ········ | |
1998 if(sce->theDag==NULL) { | |
1999 printf("DAG zero... not allowed to happen!\n"); | |
2000 DAG_scene_sort(bmain, sce); | |
2001 } | |
2002 ········ | |
2003 firstnode= sce->theDag->DagNode.first; // always scene node | |
2004 | |
2005 /* first we flush the layer flags */ | |
2006 dag_scene_flush_layers(sce, lay); | |
2007 | |
2008 /* then we use the relationships + layer info to flush update events */ | |
2009 sce->theDag->time++; // so we know which nodes were accessed | |
2010 lasttime= sce->theDag->time; | |
2011 for(itA = firstnode->child; itA; itA= itA->next) | |
2012 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) | |
2013 flush_update_node(itA->node, lay, lasttime); | |
2014 | |
2015 /* if update is not due to time change, do pointcache clears */ | |
2016 if(!time) { | |
2017 sce->theDag->time++; // so we know which nodes were accessed | |
2018 lasttime= sce->theDag->time; | |
2019 for(itA = firstnode->child; itA; itA= itA->next) { | |
2020 if(itA->node->lasttime!=lasttime && itA->node->type==ID_ OB) { | |
2021 ob= (Object*)(itA->node->ob); | |
2022 | |
2023 if(ob->recalc & OB_RECALC_ALL) { | |
2024 if(BKE_ptcache_object_reset(sce, ob, PTC ACHE_RESET_DEPSGRAPH)) | |
2025 ob->recalc |= OB_RECALC_DATA; | |
2026 | |
2027 flush_pointcache_reset(sce, itA->node, l asttime, 1); | |
2028 } | |
2029 else | |
2030 flush_pointcache_reset(sce, itA->node, l asttime, 0); | |
2031 } | |
2032 } | |
2033 | |
2034 /* also all objects which are parented to tracking data should b e re-calculated */ | |
brechtvl
2011/10/25 16:01:36
This doesn't seem right, looks like it's bypassing
nazgul
2011/10/25 19:04:58
Hrm, yes it looks crappy. Can't remember why this
| |
2035 for(ob=bmain->object.first; ob; ob= ob->id.next){ | |
2036 bConstraint *con; | |
2037 for (con = ob->constraints.first; con; con=con->next) { | |
2038 bConstraintTypeInfo *cti= constraint_get_typeinf o(con); | |
2039 if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER)) { | |
2040 ob->recalc |= OB_RECALC_OB; | |
2041 break; | |
2042 } | |
2043 } | |
2044 } | |
2045 } | |
2046 ········ | |
2047 dag_tag_renderlayers(sce, lay); | |
2048 } | |
2049 | |
2050 static int object_modifiers_use_time(Object *ob) | |
2051 { | |
2052 ModifierData *md; | |
2053 ········ | |
2054 /* check if a modifier in modifier stack needs time input */ | |
2055 for (md=ob->modifiers.first; md; md=md->next) | |
2056 if (modifier_dependsOnTime(md)) | |
2057 return 1; | |
2058 ········ | |
2059 /* check whether any modifiers are animated */ | |
2060 if (ob->adt) { | |
2061 AnimData *adt = ob->adt; | |
2062 FCurve *fcu; | |
2063 ················ | |
2064 /* action - check for F-Curves with paths containing 'modifiers[ ' */ | |
2065 if (adt->action) { | |
2066 for (fcu = adt->action->curves.first; fcu; fcu = fcu->ne xt) { | |
2067 if (fcu->rna_path && strstr(fcu->rna_path, "modi fiers[")) | |
2068 return 1; | |
2069 } | |
2070 } | |
2071 ················ | |
2072 /* This here allows modifier properties to get driven and still update properly | |
2073 * | |
2074 * Workaround to get [#26764] (e.g. subsurf levels not updating when animated/driven) | |
2075 * working, without the updating problems ([#28525] [#28690] [#2 8774] [#28777]) caused | |
2076 * by the RNA updates cache introduced in r.38649 | |
2077 */ | |
2078 for (fcu = adt->drivers.first; fcu; fcu = fcu->next) { | |
2079 if (fcu->rna_path && strstr(fcu->rna_path, "modifiers[") ) | |
2080 return 1; | |
2081 } | |
2082 ················ | |
2083 // XXX: also, should check NLA strips, though for now assume tha t nobody uses | |
2084 // that and we can omit that for performance reasons... | |
2085 } | |
2086 ········ | |
2087 return 0; | |
2088 } | |
2089 | |
2090 static short animdata_use_time(AnimData *adt) | |
2091 { | |
2092 NlaTrack *nlt; | |
2093 ········ | |
2094 if(adt==NULL) return 0; | |
2095 ········ | |
2096 /* check action - only if assigned, and it has anim curves */ | |
2097 if (adt->action && adt->action->curves.first) | |
2098 return 1; | |
2099 ········ | |
2100 /* check NLA tracks + strips */ | |
2101 for (nlt= adt->nla_tracks.first; nlt; nlt= nlt->next) { | |
2102 if (nlt->strips.first) | |
2103 return 1; | |
2104 } | |
2105 ········ | |
2106 /* If we have drivers, more likely than not, on a frame change | |
2107 * they'll need updating because their owner changed | |
2108 *· | |
2109 * This is kindof a hack to get around a whole host of problems | |
2110 * involving drivers using non-object datablock data (which the· | |
2111 * depsgraph currently has no way of representing let alone correctly | |
2112 * dependency sort+tagging). By doing this, at least we ensure that· | |
2113 * some commonly attempted drivers (such as scene -> current frame; | |
2114 * see "Driver updates fail" thread on Bf-committers dated July 2) | |
2115 * will work correctly, and that other non-object datablocks will have | |
2116 * their drivers update at least on frame change. | |
2117 * | |
2118 * -- Aligorith, July 4 2011 | |
2119 */ | |
2120 if (adt->drivers.first) | |
2121 return 1; | |
2122 ········ | |
2123 return 0; | |
2124 } | |
2125 | |
2126 static void dag_object_time_update_flags(Object *ob) | |
2127 { | |
2128 if(ob->constraints.first) { | |
2129 bConstraint *con; | |
2130 for (con = ob->constraints.first; con; con=con->next) { | |
2131 bConstraintTypeInfo *cti= constraint_get_typeinfo(con); | |
2132 ListBase targets = {NULL, NULL}; | |
2133 bConstraintTarget *ct; | |
2134 ························ | |
2135 if (cti) { | |
2136 /* special case for FollowTrack -- it doesn't us e targets to define relations */ | |
2137 if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER)) { | |
2138 ob->recalc |= OB_RECALC_OB; | |
2139 } | |
2140 else if (cti->get_constraint_targets) { | |
2141 cti->get_constraint_targets(con, &target s); | |
2142 ········································ | |
2143 for (ct= targets.first; ct; ct= ct->next ) { | |
2144 if (ct->tar) { | |
2145 ob->recalc |= OB_RECALC_ OB; | |
2146 break; | |
2147 } | |
2148 } | |
2149 ········································ | |
2150 if (cti->flush_constraint_targets) | |
2151 cti->flush_constraint_targets(co n, &targets, 1); | |
2152 } | |
2153 ································ | |
2154 } | |
2155 } | |
2156 } | |
2157 ········ | |
2158 if(ob->parent) { | |
2159 /* motion path or bone child */ | |
2160 if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB; | |
2161 } | |
2162 ········ | |
2163 #if 0 // XXX old animation system | |
2164 if(ob->nlastrips.first) { | |
2165 if(ob->dup_group) { | |
2166 bActionStrip *strip; | |
2167 /* this case is for groups with nla, whilst nla target h as no action or nla */ | |
2168 for(strip= ob->nlastrips.first; strip; strip= strip->nex t) { | |
2169 if(strip->object) | |
2170 strip->object->recalc |= OB_RECALC_ALL; | |
2171 } | |
2172 } | |
2173 } | |
2174 #endif // XXX old animation system | |
2175 ········ | |
2176 if(animdata_use_time(ob->adt)) { | |
2177 ob->recalc |= OB_RECALC_OB; | |
2178 ob->adt->recalc |= ADT_RECALC_ANIM; | |
2179 } | |
2180 ········ | |
2181 if((ob->adt) && (ob->type==OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA; | |
2182 ········ | |
2183 if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA; | |
2184 if((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->rec alc |= OB_RECALC_DATA; | |
2185 ········ | |
2186 { | |
2187 AnimData *adt= BKE_animdata_from_id((ID *)ob->data); | |
2188 Mesh *me; | |
2189 Curve *cu; | |
2190 Lattice *lt; | |
2191 ················ | |
2192 switch(ob->type) { | |
2193 case OB_MESH: | |
2194 me= ob->data; | |
2195 if(me->key) { | |
2196 if(!(ob->shapeflag & OB_SHAPE_LOCK)) { | |
2197 ob->recalc |= OB_RECALC_DATA; | |
2198 } | |
2199 } | |
2200 if(ob->particlesystem.first) | |
2201 ob->recalc |= OB_RECALC_DATA; | |
2202 break; | |
2203 case OB_CURVE: | |
2204 case OB_SURF: | |
2205 cu= ob->data; | |
2206 if(cu->key) { | |
2207 if(!(ob->shapeflag & OB_SHAPE_LOCK)) { | |
2208 ob->recalc |= OB_RECALC_DATA; | |
2209 } | |
2210 } | |
2211 break; | |
2212 case OB_FONT: | |
2213 cu= ob->data; | |
2214 if(cu->nurb.first==NULL && cu->str && cu->vfont) | |
2215 ob->recalc |= OB_RECALC_DATA; | |
2216 break; | |
2217 case OB_LATTICE: | |
2218 lt= ob->data; | |
2219 if(lt->key) { | |
2220 if(!(ob->shapeflag & OB_SHAPE_LOCK)) { | |
2221 ob->recalc |= OB_RECALC_DATA; | |
2222 } | |
2223 } | |
2224 break; | |
2225 case OB_MBALL: | |
2226 if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RE CALC_DATA; | |
2227 break; | |
2228 } | |
2229 ················ | |
2230 if(animdata_use_time(adt)) { | |
2231 ob->recalc |= OB_RECALC_DATA; | |
2232 adt->recalc |= ADT_RECALC_ANIM; | |
2233 } | |
2234 | |
2235 if(ob->particlesystem.first) { | |
2236 ParticleSystem *psys= ob->particlesystem.first; | |
2237 | |
2238 for(; psys; psys=psys->next) { | |
2239 if(psys_check_enabled(ob, psys)) { | |
2240 ob->recalc |= OB_RECALC_DATA; | |
2241 break; | |
2242 } | |
2243 } | |
2244 } | |
2245 }··············· | |
2246 } | |
2247 /* flag all objects that need recalc, for changes in time for example */ | |
2248 /* do_time: make this optional because undo resets objects to their animated loc ations without this */ | |
2249 void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const s hort do_time) | |
2250 { | |
2251 Base *base; | |
2252 Object *ob; | |
2253 Group *group; | |
2254 GroupObject *go; | |
2255 Scene *sce_iter; | |
2256 | |
2257 /* set ob flags where animated systems are */ | |
2258 for(SETLOOPER(scene, sce_iter, base)) { | |
2259 ob= base->object; | |
2260 | |
2261 if(do_time) { | |
2262 /* now if DagNode were part of base, the node->lay could be checked... */ | |
2263 /* we do all now, since the scene_flush checks layers an d clears recalc flags even */ | |
2264 dag_object_time_update_flags(ob); | |
2265 } | |
2266 | |
2267 /* handled in next loop */ | |
2268 if(ob->dup_group) | |
2269 ob->dup_group->id.flag |= LIB_DOIT; | |
2270 } | |
2271 | |
2272 if(do_time) { | |
2273 /* we do groups each once */ | |
2274 for(group= bmain->group.first; group; group= group->id.next) { | |
2275 if(group->id.flag & LIB_DOIT) { | |
2276 for(go= group->gobject.first; go; go= go->next) { | |
2277 dag_object_time_update_flags(go->ob); | |
2278 } | |
2279 } | |
2280 } | |
2281 } | |
2282 | |
2283 for(sce_iter= scene; sce_iter; sce_iter= sce_iter->set) | |
2284 DAG_scene_flush_update(bmain, sce_iter, lay, 1); | |
2285 ········ | |
2286 if(do_time) { | |
2287 /* test: set time flag, to disable baked systems to update */ | |
2288 for(SETLOOPER(scene, sce_iter, base)) { | |
2289 ob= base->object; | |
2290 if(ob->recalc) | |
2291 ob->recalc |= OB_RECALC_TIME; | |
2292 } | |
2293 | |
2294 /* hrmf... an exception to look at once, for invisible camera ob ject we do it over */ | |
2295 if(scene->camera) | |
2296 dag_object_time_update_flags(scene->camera); | |
2297 } | |
2298 | |
2299 /* and store the info in groupobject */ | |
2300 for(group= bmain->group.first; group; group= group->id.next) { | |
2301 if(group->id.flag & LIB_DOIT) { | |
2302 for(go= group->gobject.first; go; go= go->next) { | |
2303 go->recalc= go->ob->recalc; | |
2304 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc); | |
2305 } | |
2306 group->id.flag &= ~LIB_DOIT; | |
2307 } | |
2308 } | |
2309 ········ | |
2310 } | |
2311 | |
2312 static void dag_current_scene_layers(Main *bmain, Scene **sce, unsigned int *lay ) | |
2313 { | |
2314 wmWindowManager *wm; | |
2315 wmWindow *win; | |
2316 | |
2317 /* only one scene supported currently, making more scenes work | |
2318 correctly requires changes beyond just the dependency graph */ | |
2319 | |
2320 *sce= NULL; | |
2321 *lay= 0; | |
2322 | |
2323 if((wm= bmain->wm.first)) { | |
2324 /* if we have a windowmanager, look into windows */ | |
2325 for(win=wm->windows.first; win; win=win->next) { | |
2326 if(win->screen) { | |
2327 if(!*sce) *sce= win->screen->scene; | |
2328 *lay |= BKE_screen_visible_layers(win->screen, w in->screen->scene); | |
2329 } | |
2330 } | |
2331 } | |
2332 else { | |
2333 /* if not, use the first sce */ | |
2334 *sce= bmain->scene.first; | |
2335 if(*sce) *lay= (*sce)->lay; | |
2336 | |
2337 /* XXX for background mode, we should get the scene | |
2338 from somewhere, for the -S option, but it's in | |
2339 the context, how to get it here? */ | |
2340 } | |
2341 } | |
2342 | |
2343 void DAG_ids_flush_update(Main *bmain, int time) | |
2344 { | |
2345 Scene *sce; | |
2346 unsigned int lay; | |
2347 | |
2348 dag_current_scene_layers(bmain, &sce, &lay); | |
2349 | |
2350 if(sce) | |
2351 DAG_scene_flush_update(bmain, sce, lay, time); | |
2352 } | |
2353 | |
2354 void DAG_on_visible_update(Main *bmain, const short do_time) | |
2355 { | |
2356 Scene *scene; | |
2357 Base *base; | |
2358 Object *ob; | |
2359 Group *group; | |
2360 GroupObject *go; | |
2361 DagNode *node; | |
2362 unsigned int lay, oblay; | |
2363 | |
2364 dag_current_scene_layers(bmain, &scene, &lay); | |
2365 | |
2366 if(scene && scene->theDag) { | |
2367 Scene *sce_iter; | |
2368 /* derivedmeshes and displists are not saved to file so need to be | |
2369 remade, tag them so they get remade in the scene update loop, | |
2370 note armature poses or object matrices are preserved and do n ot | |
2371 require updates, so we skip those */ | |
2372 dag_scene_flush_layers(scene, lay); | |
2373 | |
2374 for(SETLOOPER(scene, sce_iter, base)) { | |
2375 ob= base->object; | |
2376 node= (sce_iter->theDag)? dag_get_node(sce_iter->theDag, ob): NULL; | |
2377 oblay= (node)? node->lay: ob->lay; | |
2378 | |
2379 if((oblay & lay) & ~scene->lay_updated) { | |
2380 if(ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, O B_FONT, OB_MBALL, OB_LATTICE)) | |
2381 ob->recalc |= OB_RECALC_DATA; | |
2382 if(ob->dup_group)· | |
2383 ob->dup_group->id.flag |= LIB_DOIT; | |
2384 } | |
2385 } | |
2386 | |
2387 for(group= bmain->group.first; group; group= group->id.next) { | |
2388 if(group->id.flag & LIB_DOIT) { | |
2389 for(go= group->gobject.first; go; go= go->next) { | |
2390 if(ELEM6(go->ob->type, OB_MESH, OB_CURVE , OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE)) | |
2391 go->ob->recalc |= OB_RECALC_DATA ; | |
2392 if(go->ob->proxy_from) | |
2393 go->ob->recalc |= OB_RECALC_OB; | |
2394 } | |
2395 ································ | |
2396 group->id.flag &= ~LIB_DOIT; | |
2397 } | |
2398 } | |
2399 | |
2400 /* now tag update flags, to ensure deformers get calculated on r edraw */ | |
2401 DAG_scene_update_flags(bmain, scene, lay, do_time); | |
2402 scene->lay_updated |= lay; | |
2403 } | |
2404 } | |
2405 | |
2406 static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUS ED(ob), ID **idpoin) | |
2407 { | |
2408 struct { ID *id; int is_dependent; } *data = userData; | |
2409 ········ | |
2410 if(*idpoin && GS((*idpoin)->name)==ID_TE) { | |
2411 if (data->id == (*idpoin)) | |
2412 data->is_dependent = 1; | |
2413 } | |
2414 } | |
2415 | |
2416 static void dag_id_flush_update(Scene *sce, ID *id) | |
2417 { | |
2418 Main *bmain= G.main; | |
2419 Object *obt, *ob= NULL; | |
2420 short idtype; | |
2421 | |
2422 /* here we flush a few things before actual scene wide flush, mostly | |
2423 due to only objects and not other datablocks being in the depsgraph * / | |
2424 | |
2425 /* set flags & pointcache for object */ | |
2426 if(GS(id->name) == ID_OB) { | |
2427 ob= (Object*)id; | |
2428 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH); | |
2429 | |
2430 if(ob->recalc & OB_RECALC_DATA) { | |
2431 /* all users of this ob->data should be checked */ | |
2432 id= ob->data; | |
2433 | |
2434 /* no point in trying in this cases */ | |
2435 if(id && id->us <= 1) { | |
2436 dag_editors_update(bmain, id); | |
2437 id= NULL; | |
2438 } | |
2439 } | |
2440 } | |
2441 | |
2442 /* set flags & pointcache for object data */ | |
2443 if(id) { | |
2444 idtype= GS(id->name); | |
2445 | |
2446 if(ELEM8(idtype, ID_ME, ID_CU, ID_MB, ID_LA, ID_LT, ID_CA, ID_AR , ID_SPK)) { | |
2447 for(obt=bmain->object.first; obt; obt= obt->id.next) { | |
2448 if(!(ob && obt == ob) && obt->data == id) { | |
2449 obt->recalc |= OB_RECALC_DATA; | |
2450 BKE_ptcache_object_reset(sce, obt, PTCAC HE_RESET_DEPSGRAPH); | |
2451 } | |
2452 } | |
2453 } | |
2454 ················ | |
2455 /* set flags based on textures - can influence depgraph via modi fiers */ | |
2456 if(idtype == ID_TE) { | |
2457 for(obt=bmain->object.first; obt; obt= obt->id.next) { | |
2458 struct { ID *id; int is_dependent; } data; | |
2459 data.id= id; | |
2460 data.is_dependent= 0; | |
2461 | |
2462 modifiers_foreachIDLink(obt, dag_id_flush_update __isDependentTexture, &data); | |
2463 if (data.is_dependent) | |
2464 obt->recalc |= OB_RECALC_DATA; | |
2465 | |
2466 /* particle settings can use the texture as well */ | |
2467 if(obt->particlesystem.first) { | |
2468 ParticleSystem *psys = obt->particlesyst em.first; | |
2469 MTex **mtexp, *mtex; | |
2470 int a; | |
2471 for(; psys; psys=psys->next) { | |
2472 mtexp = psys->part->mtex; | |
2473 for(a=0; a<MAX_MTEX; a++, mtexp+ +) { | |
2474 mtex = *mtexp; | |
2475 if(mtex && mtex->tex == (Tex*)id) { | |
2476 obt->recalc |= O B_RECALC_DATA; | |
2477 ································································ | |
2478 if(mtex->mapto & PAMAP_INIT) | |
2479 psys->re calc |= PSYS_RECALC_RESET; | |
2480 if(mtex->mapto & PAMAP_CHILD) | |
2481 psys->re calc |= PSYS_RECALC_CHILD; | |
2482 | |
2483 BKE_ptcache_obje ct_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH); | |
2484 } | |
2485 } | |
2486 } | |
2487 } | |
2488 } | |
2489 } | |
2490 ················ | |
2491 /* set flags based on ShapeKey */ | |
2492 if(idtype == ID_KE) { | |
2493 for(obt=bmain->object.first; obt; obt= obt->id.next) { | |
2494 Key *key= ob_get_key(obt); | |
2495 if(!(ob && obt == ob) && ((ID *)key == id)) { | |
2496 obt->flag |= (OB_RECALC_OB|OB_RECALC_DAT A); | |
2497 BKE_ptcache_object_reset(sce, obt, PTCAC HE_RESET_DEPSGRAPH); | |
2498 } | |
2499 } | |
2500 } | |
2501 ················ | |
2502 /* set flags based on particle settings */ | |
2503 if(idtype == ID_PA) { | |
2504 ParticleSystem *psys; | |
2505 for(obt=bmain->object.first; obt; obt= obt->id.next) | |
2506 for(psys=obt->particlesystem.first; psys; psys=p sys->next) | |
2507 if(&psys->part->id == id) | |
2508 BKE_ptcache_object_reset(sce, ob t, PTCACHE_RESET_DEPSGRAPH); | |
2509 } | |
2510 | |
2511 if(idtype == ID_MC) { | |
2512 for(obt=bmain->object.first; obt; obt= obt->id.next){ | |
2513 bConstraint *con; | |
2514 for (con = obt->constraints.first; con; con=con- >next) { | |
2515 bConstraintTypeInfo *cti= constraint_get _typeinfo(con); | |
2516 if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLO WTRACK, CONSTRAINT_TYPE_CAMERASOLVER)) { | |
2517 obt->recalc |= OB_RECALC_OB; | |
2518 break; | |
2519 } | |
2520 } | |
2521 } | |
2522 | |
2523 if(sce->nodetree) { | |
2524 bNode *node; | |
2525 | |
2526 for(node= sce->nodetree->nodes.first; node; node = node->next) { | |
2527 if(node->id==id) { | |
2528 nodeUpdate(sce->nodetree, node); | |
2529 } | |
2530 } | |
2531 } | |
2532 } | |
2533 | |
2534 /* camera's matrix is used to orient reconstructed stuff, | |
2535 so it should happen tracking-related constraints recalculatio n | |
2536 when camera is changing */ | |
2537 if(sce->camera && &sce->camera->id == id && sce->clip) { | |
2538 dag_id_flush_update(sce, &sce->clip->id); | |
2539 } | |
2540 | |
2541 /* update editors */ | |
2542 dag_editors_update(bmain, id); | |
2543 } | |
2544 } | |
2545 | |
2546 void DAG_ids_flush_tagged(Main *bmain) | |
2547 { | |
2548 ListBase *lbarray[MAX_LIBARRAY]; | |
2549 Scene *sce; | |
2550 unsigned int lay; | |
2551 int a, have_tag = 0; | |
2552 | |
2553 dag_current_scene_layers(bmain, &sce, &lay); | |
2554 | |
2555 if(!sce || !sce->theDag) | |
2556 return; | |
2557 | |
2558 /* loop over all ID types */ | |
2559 a = set_listbasepointers(bmain, lbarray); | |
2560 | |
2561 while(a--) { | |
2562 ListBase *lb = lbarray[a]; | |
2563 ID *id = lb->first; | |
2564 | |
2565 /* we tag based on first ID type character to avoid· | |
2566 looping over all ID's in case there are no tags */ | |
2567 if(id && bmain->id_tag_update[id->name[0]]) { | |
2568 for(; id; id=id->next) { | |
2569 if(id->flag & LIB_ID_RECALC) { | |
2570 dag_id_flush_update(sce, id); | |
2571 id->flag &= ~LIB_ID_RECALC; | |
2572 } | |
2573 } | |
2574 | |
2575 have_tag = 1; | |
2576 } | |
2577 } | |
2578 | |
2579 if(have_tag) { | |
2580 /* clear tags */ | |
2581 memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update)); | |
2582 | |
2583 /* flush changes to other objects */ | |
2584 DAG_scene_flush_update(bmain, sce, lay, 0); | |
2585 } | |
2586 } | |
2587 | |
2588 void DAG_id_tag_update(ID *id, short flag) | |
2589 { | |
2590 Main *bmain= G.main; | |
2591 | |
2592 if(id==NULL) return; | |
2593 ········ | |
2594 /* tag ID for update */ | |
2595 id->flag |= LIB_ID_RECALC; | |
2596 bmain->id_tag_update[id->name[0]] = 1; | |
2597 | |
2598 /* flag is for objects and particle systems */ | |
2599 if(flag) { | |
2600 Object *ob; | |
2601 ParticleSystem *psys; | |
2602 short idtype = GS(id->name); | |
2603 | |
2604 if(idtype == ID_OB) { | |
2605 /* only quick tag */ | |
2606 ob = (Object*)id; | |
2607 ob->recalc |= (flag & OB_RECALC_ALL); | |
2608 } | |
2609 else if(idtype == ID_PA) { | |
2610 /* this is weak still, should be done delayed as well */ | |
2611 for(ob=bmain->object.first; ob; ob=ob->id.next) { | |
2612 for(psys=ob->particlesystem.first; psys; psys=ps ys->next) { | |
2613 if(&psys->part->id == id) { | |
2614 ob->recalc |= (flag & OB_RECALC_ ALL); | |
2615 psys->recalc |= (flag & PSYS_REC ALC); | |
2616 } | |
2617 } | |
2618 } | |
2619 } | |
2620 else { | |
2621 /* disable because this is called on various ID types au tomatically. | |
2622 * where printing warning is not useful. for now just ig nore */ | |
2623 /* BLI_assert(!"invalid flag for this 'idtype'"); */ | |
2624 } | |
2625 } | |
2626 } | |
2627 | |
2628 #if 0 // UNUSED | |
2629 /* recursively descends tree, each node only checked once */ | |
2630 /* node is checked to be of type object */ | |
2631 static int parent_check_node(DagNode *node, int curtime) | |
2632 { | |
2633 DagAdjList *itA; | |
2634 ········ | |
2635 node->lasttime= curtime; | |
2636 ········ | |
2637 if(node->color==DAG_GRAY) | |
2638 return DAG_GRAY; | |
2639 ········ | |
2640 for(itA = node->child; itA; itA= itA->next) { | |
2641 if(itA->node->type==ID_OB) { | |
2642 ························ | |
2643 if(itA->node->color==DAG_GRAY) | |
2644 return DAG_GRAY; | |
2645 | |
2646 /* descend if not done */ | |
2647 if(itA->node->lasttime!=curtime) { | |
2648 itA->node->color= parent_check_node(itA->node, c urtime); | |
2649 ························ | |
2650 if(itA->node->color==DAG_GRAY) | |
2651 return DAG_GRAY; | |
2652 } | |
2653 } | |
2654 } | |
2655 ········ | |
2656 return DAG_WHITE; | |
2657 } | |
2658 #endif | |
2659 | |
2660 /* ******************* DAG FOR ARMATURE POSE ***************** */ | |
2661 | |
2662 /* we assume its an armature with pose */ | |
2663 void DAG_pose_sort(Object *ob) | |
2664 { | |
2665 bPose *pose= ob->pose; | |
2666 bPoseChannel *pchan; | |
2667 bConstraint *con; | |
2668 DagNode *node; | |
2669 DagNode *node2, *node3; | |
2670 DagNode *rootnode; | |
2671 DagForest *dag; | |
2672 DagNodeQueue *nqueue; | |
2673 DagAdjList *itA; | |
2674 ListBase tempbase; | |
2675 int skip = 0; | |
2676 ········ | |
2677 dag = dag_init(); | |
2678 ugly_hack_sorry= 0; // no ID structs | |
2679 | |
2680 rootnode = dag_add_node(dag, NULL); // node->ob becomes NULL | |
2681 ········ | |
2682 /* we add the hierarchy and the constraints */ | |
2683 for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) { | |
2684 int addtoroot = 1; | |
2685 ················ | |
2686 node = dag_get_node(dag, pchan); | |
2687 ················ | |
2688 if(pchan->parent) { | |
2689 node2 = dag_get_node(dag, pchan->parent); | |
2690 dag_add_relation(dag, node2, node, 0, "Parent Relation") ; | |
2691 addtoroot = 0; | |
2692 } | |
2693 for (con = pchan->constraints.first; con; con=con->next) { | |
2694 bConstraintTypeInfo *cti= constraint_get_typeinfo(con); | |
2695 ListBase targets = {NULL, NULL}; | |
2696 bConstraintTarget *ct; | |
2697 ························ | |
2698 if (cti && cti->get_constraint_targets) { | |
2699 cti->get_constraint_targets(con, &targets); | |
2700 ································ | |
2701 for (ct= targets.first; ct; ct= ct->next) { | |
2702 if (ct->tar==ob && ct->subtarget[0]) { | |
2703 bPoseChannel *target= get_pose_c hannel(ob->pose, ct->subtarget); | |
2704 if (target) { | |
2705 node2= dag_get_node(dag, target); | |
2706 dag_add_relation(dag, no de2, node, 0, "Pose Constraint"); | |
2707 ························································ | |
2708 if (con->type==CONSTRAIN T_TYPE_KINEMATIC) { | |
2709 bKinematicConstr aint *data = (bKinematicConstraint *)con->data; | |
2710 bPoseChannel *pa rchan; | |
2711 int segcount= 0; | |
2712 ································································ | |
2713 /* exclude tip f rom chain? */ | |
2714 if(!(data->flag & CONSTRAINT_IK_TIP)) | |
2715 parchan= pchan->parent; | |
2716 else | |
2717 parchan= pchan; | |
2718 ································································ | |
2719 /* Walk to the c hain's root */ | |
2720 while (parchan) { | |
2721 node3= d ag_get_node(dag, parchan); | |
2722 dag_add_ relation(dag, node2, node3, 0, "IK Constraint"); | |
2723 ········································································ | |
2724 segcount ++; | |
2725 if (segc ount==data->rootbone || segcount>255) break; // 255 is weak | |
2726 parchan= parchan->parent; | |
2727 } | |
2728 } | |
2729 } | |
2730 } | |
2731 } | |
2732 ································ | |
2733 if (cti->flush_constraint_targets) | |
2734 cti->flush_constraint_targets(con, &targ ets, 1); | |
2735 } | |
2736 } | |
2737 if (addtoroot == 1 ) { | |
2738 dag_add_relation(dag, rootnode, node, 0, "Root Bone Rela tion"); | |
2739 } | |
2740 } | |
2741 | |
2742 dag_check_cycle(dag); | |
2743 ········ | |
2744 /* now we try to sort... */ | |
2745 tempbase.first= tempbase.last= NULL; | |
2746 | |
2747 nqueue = queue_create(DAGQUEUEALLOC); | |
2748 ········ | |
2749 /* tag nodes unchecked */ | |
2750 for(node = dag->DagNode.first; node; node= node->next)· | |
2751 node->color = DAG_WHITE; | |
2752 ········ | |
2753 node = dag->DagNode.first; | |
2754 ········ | |
2755 node->color = DAG_GRAY; | |
2756 push_stack(nqueue, node);·· | |
2757 ········ | |
2758 while(nqueue->count) { | |
2759 ················ | |
2760 skip = 0; | |
2761 node = get_top_node_queue(nqueue); | |
2762 ················ | |
2763 itA = node->child; | |
2764 while(itA != NULL) { | |
2765 if(itA->node->color == DAG_WHITE) { | |
2766 itA->node->color = DAG_GRAY; | |
2767 push_stack(nqueue,itA->node); | |
2768 skip = 1; | |
2769 break; | |
2770 }· | |
2771 itA = itA->next; | |
2772 }······················· | |
2773 ················ | |
2774 if (!skip) { | |
2775 if (node) { | |
2776 node = pop_queue(nqueue); | |
2777 if (node->ob == NULL) // we are done | |
2778 break ; | |
2779 node->color = DAG_BLACK; | |
2780 ································ | |
2781 /* put node in new list */ | |
2782 BLI_remlink(&pose->chanbase, node->ob); | |
2783 BLI_addhead(&tempbase, node->ob); | |
2784 }······· | |
2785 } | |
2786 } | |
2787 ········ | |
2788 // temporal correction for circular dependancies | |
2789 while(pose->chanbase.first) { | |
2790 pchan= pose->chanbase.first; | |
2791 BLI_remlink(&pose->chanbase, pchan); | |
2792 BLI_addhead(&tempbase, pchan); | |
2793 | |
2794 printf("cyclic %s\n", pchan->name); | |
2795 } | |
2796 ········ | |
2797 pose->chanbase = tempbase; | |
2798 queue_delete(nqueue); | |
2799 ········ | |
2800 // printf("\nordered\n"); | |
2801 // for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) { | |
2802 // printf(" %s\n", pchan->name); | |
2803 // } | |
2804 ········ | |
2805 free_forest( dag ); | |
2806 MEM_freeN( dag ); | |
2807 ········ | |
2808 ugly_hack_sorry= 1; | |
2809 } | |
2810 | |
2811 | |
2812 | |
LEFT | RIGHT |