Dependency graph patch, provided by Jean-Luc Peuriere.
[blender.git] / source / blender / src / drawdeps.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2004 Blender Foundation.
24  * All rights reserved.
25  *
26  * Contributor(s): none yet.
27  *
28  * ***** END GPL/BL DUAL LICENSE BLOCK *****
29  */
30
31 #include <stdio.h>
32 #include <string.h>
33 #include <math.h>
34
35 #ifdef _WIN32
36 #include "BLI_winstuff.h"
37 #endif
38
39 #include "BMF_Api.h"
40
41 #include "BLI_blenlib.h"
42 #include "BLI_arithb.h"
43
44 #include "DNA_ID.h"
45 #include "DNA_object_types.h"
46 #include "DNA_oops_types.h"
47 #include "DNA_scene_types.h"
48 #include "DNA_screen_types.h"
49 #include "DNA_space_types.h"
50 #include "DNA_view2d_types.h"
51 #include "DNA_action_types.h"
52
53 #include "BKE_utildefines.h"
54 #include "BKE_global.h"
55
56 #include "BIF_interface.h"
57 #include "BIF_gl.h"
58 #include "BIF_glutil.h"
59 #include "BIF_mywindow.h"
60 #include "BIF_resources.h"
61 #include "BIF_screen.h"
62
63 #include "BIF_oops.h"
64
65 #include "BSE_drawipo.h"
66 #include "BSE_drawoops.h"
67 #include "MEM_guardedalloc.h"
68 #include "blendef.h"
69
70
71 #include "depsgraph_private.h"
72
73 #include <sys/time.h>
74
75
76
77 void boundbox_deps()
78 {
79         DagNode *node;
80         float min[2], max[2];
81         
82         if(G.soops==0) return;
83         
84         min[0]= 1000.0;
85         max[0]= -10000.0;
86         min[1]= 1000.0;
87         max[1]= -1000.0;
88         
89         node = getMainDag()->DagNode.first;
90         while(node) {
91                 min[0]= MIN2(min[0], node->x);
92                 max[0]= MAX2(max[0], node->x+OOPSX);
93                 min[1]= MIN2(min[1], node->y);
94                 max[1]= MAX2(max[1], node->y+OOPSY);
95                 
96                 node= node->next;
97         }
98                 
99         G.v2d->tot.xmin= min[0];
100         G.v2d->tot.xmax= max[0];
101         G.v2d->tot.ymin= min[1];
102         G.v2d->tot.ymax= max[1];
103 }
104
105 static unsigned int get_line_color(DagAdjList *child)
106 {
107         switch  (child->type) {
108                 case DAG_RL_SCENE :
109                         return 0x00000;
110                 case DAG_RL_DATA :
111                         return 0xFF0000;
112                 case DAG_RL_PARENT :
113                         return 0x00FF00;
114                 case DAG_RL_TRACK :
115                         return 0xFFFF00;
116                 case DAG_RL_PATH :
117                         return 0x000000;
118                 case DAG_RL_CONSTRAINT :
119                         return 0x0000FF;
120                 case DAG_RL_HOOK :
121                         return 0x00FFFF;
122                 case DAG_RL_DATA_CONSTRAINT :
123                         return 0x0000FF;
124                 default :
125                         return 0x0000FF;
126         }
127         //return 0x00000;
128 }
129
130
131 static void draw_deps(DagNode *node)
132 {
133         float v1[2], x1, y1, x2, y2;
134         unsigned int body, border;
135         short line= 0;
136         char str[32];
137         DagAdjList *itA = node->child;
138
139         x1= node->x; 
140         x2= node->x+DEPSX;
141         y1= node->y; 
142         y2= node->y+DEPSY;
143
144         if(x2 < G.v2d->cur.xmin || x1 > G.v2d->cur.xmax) return;
145         if(y2 < G.v2d->cur.ymin || y1 > G.v2d->cur.ymax) return;
146
147         body =  give_oops_color(node->type, 0, &border);
148
149         line= 0;
150 //      border= 00;
151         cpack(body);
152
153         glRectf(x1,  y1,  x2,  y2);
154         
155         v1[0]= x1; 
156         v1[1]= (y1+y2)/2 -0.3;
157         sprintf(str, "     %s", ((ID *) node->ob)->name+2);
158         
159         calc_oopstext(str, v1);
160         
161                 /* ICON */
162 //      if(str[1] && oopscalex>1.1) {
163         draw_icon_oops(v1, node->type);
164 //      }
165
166         
167         cpack(0x0);
168         glRasterPos3f(v1[0],  v1[1], 0.0);
169         BMF_DrawString(G.fonts, str);
170
171         
172         if(line) setlinestyle(2);
173         cpack(border);
174
175         glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
176         glRectf(x1,  y1,  x2,  y2);
177         glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
178         if(line) setlinestyle(0);
179
180         while (itA) { /* draw connection lines */
181                 cpack(get_line_color(itA));
182                 glBegin(GL_LINE_STRIP);
183                         glVertex2f(node->x+DEPSX, node->y+ 0.5*DEPSY);
184                         glVertex2f(itA->node->x, itA->node->y+ 0.5*DEPSY);                      
185                 glEnd();
186                 itA = itA->next;
187         }
188                         /* Draw the little rounded connection point */
189                 glColor3ub(0, 0, 0);
190                 glPushMatrix();
191
192                 glTranslatef(node->x , node->y+ 0.5*DEPSY, 0.0);
193                 glutil_draw_filled_arc(-M_PI/2, M_PI, 0.07*DEPSX, 7);
194
195                 glPopMatrix();
196
197 }
198
199 void    draw_all_deps(void)
200 {
201         DagNode *node;
202         DagForest *dag;
203         
204         dag = getMainDag();
205          node = dag->DagNode.first;
206         //node = node->next;
207         while(node) {
208                 draw_deps(node);
209                 node = node->next;
210         }
211         free_forest(dag);
212         MEM_freeN(dag);
213         setMainDag(NULL);
214 }
215
216
217
218
219 int build_deps(short mask)
220 {
221         Base *base;
222         Object *ob = NULL;
223         DagNode * node = NULL; 
224         DagNode * node2 = NULL ;
225         DagNode * node3 = NULL;
226 DagNode * scenenode;
227         DagForest *dag;
228
229 #ifdef DEPS_DEBUG
230         //timers
231         struct timeval tp1, tp2, tp3, tp4;
232         
233         gettimeofday(&tp1,NULL);
234 #endif
235         
236         DagNodeQueue *retqueue;
237         
238 //      float y = 0;
239 //      int maxlev = 0;
240
241         if(G.soops==0) return -1;
242         
243         
244         // rebuilt each time for now
245         dag = getMainDag();
246         if ( dag)
247                 free_forest( dag ); 
248         else {
249                 dag = dag_init();
250                 setMainDag(dag);
251                 }
252                 
253         // add base node for scene. scene is always the first node in DAG
254         scenenode = dag_add_node(dag, G.scene);
255         set_node_xy(scenenode,0.0, 0.0);        
256                 /* blocks from this scene */
257                 
258                 
259                 /* targets in object struct yet to be added. should even they ?
260                                 struct Ipo *ipo;
261                         ListBase nlastrips;
262                         ListBase hooks;
263                 */
264                 
265                 
266         base= FIRSTBASE;
267         while(base) { // add all objects in any case
268                 int addtoroot = 1;
269                 
270 //                               graph_print_adj_list();
271 ob= (Object *) base->object;
272
273                 node = dag_get_node(dag,ob);
274         
275                 if ((ob->data) && (mask&DAG_RL_DATA_MASK)) {
276                         node2 = dag_get_node(dag,ob->data);
277                         dag_add_relation(dag,node,node2,DAG_RL_DATA);
278                         node2->first_ancestor = ob;
279                         node2->ancestor_count += 1;
280                         
281                         if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) { // add armature constraints to datas
282                                 if (ob->pose){
283                                         bPoseChannel *pchan;
284                                         bConstraint *con;
285                                         Object * target;
286                                         
287                                         for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
288                                                 for (con = pchan->constraints.first; con; con=con->next){
289                                                         if (constraint_has_target(con)) {
290                                                                 target = get_constraint_target(con);
291                                                                 if (strcmp(target->id.name, ob->id.name) != 0) {
292                                                                         //fprintf(stderr,"armature target :%s \n", target->id.name);
293                                                                         node3 = dag_get_node(dag,target);
294                                                                         dag_add_relation(dag,node3,node2,DAG_RL_CONSTRAINT);
295                                                                 }
296                                                         }
297                                                 }
298                                         }
299                                 }
300                         }
301                         
302                         if (ob->hooks.first) {
303                                 ObHook *hook;
304                                 
305                                 for(hook= ob->hooks.first; hook; hook= hook->next) {
306                                         if(hook->parent) {
307                                                 node3 = dag_get_node(dag,hook->parent);
308                                                 dag_add_relation(dag,node3,node2,DAG_RL_HOOK);
309                                         }
310                                 }
311                         }
312                 } else { // add armature constraints to object itself
313                         if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) {
314                                 if (ob->pose){
315                                         bPoseChannel *pchan;
316                                         bConstraint *con;
317                                         Object * target;
318                                         
319                                         for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
320                                                 for (con = pchan->constraints.first; con; con=con->next){
321                                                         if (constraint_has_target(con)) {
322                                                                 target = get_constraint_target(con);
323                                                                 if (strcmp(target->id.name, ob->id.name) != 0) {
324                                                                         //fprintf(stderr,"armature target :%s \n", target->id.name);
325                                                                         node3 = dag_get_node(dag,target);
326                                                                         dag_add_relation(dag,node3,node,DAG_RL_CONSTRAINT);
327                                                                 }
328                                                         }
329                                                 }
330                                         }
331                                 }
332                         }
333                         if (ob->hooks.first) {
334                                 ObHook *hook;
335                                 
336                                 for(hook= ob->hooks.first; hook; hook= hook->next) {
337                                         if(hook->parent) {
338                                                 node3 = dag_get_node(dag,hook->parent);
339                                                 dag_add_relation(dag,node3,node,DAG_RL_HOOK);
340                                         }
341                                 }
342                         }                       
343                 }
344
345                 if ((ob->parent) && (mask&DAG_RL_PARENT_MASK)){
346                         node2 = dag_get_node(dag,ob->parent);
347                         dag_add_relation(dag,node2,node,DAG_RL_PARENT);
348                         addtoroot = 0;
349                 }
350                 if ((ob->track) && (mask&DAG_RL_TRACK_MASK)){
351                         node2 = dag_get_node(dag,ob->track);
352                         dag_add_relation(dag,node2,node,DAG_RL_TRACK);
353                         addtoroot = 0;
354
355                 }
356                 if ((ob->path) && (mask&DAG_RL_PATH_MASK)){
357                         node2 = dag_get_node(dag,ob->track);
358                         dag_add_relation(dag,node2,node,DAG_RL_PATH);
359                         addtoroot = 0;
360
361                 }
362
363                 /* Count constraints */
364                 if (mask & DAG_RL_CONSTRAINT_MASK) {
365                         bConstraint *con;
366                         for (con = ob->constraints.first; con; con=con->next){
367                                 if (constraint_has_target(con)) {
368                                         node2 = dag_get_node(dag,get_constraint_target(con));
369                                         dag_add_relation(dag,node2,node,DAG_RL_CONSTRAINT);
370                                         addtoroot = 0;
371                                         
372                                 }
373                         }
374                 }       
375                 
376                 
377                 if (addtoroot == 1 )
378                         dag_add_relation(dag,scenenode,node,DAG_RL_SCENE);
379
380                 addtoroot = 1;
381                 base= base->next;
382         }
383
384 //graph_print_adj_list();
385 //fprintf(stderr,"building deps\n");
386 #ifdef DEPS_DEBUG
387         gettimeofday(&tp2,NULL);
388 #endif
389
390 //graph_bfs(); //set levels
391
392 #ifdef DEPS_DEBUG
393 gettimeofday(&tp3,NULL);
394 #endif
395
396
397 retqueue = graph_dfs(); //set levels
398 #ifdef DEPS_DEBUG
399 gettimeofday(&tp4,NULL);
400 fprintf(stderr,"************************************\n");
401 graph_print_queue_dist(retqueue);
402 //graph_print_queue(retqueue);
403
404 fprintf(stderr,"TIME BUILD %d %d BFS %d %d DFS  %d %d\n",tp2.tv_sec-tp1.tv_sec ,tp2.tv_usec-tp1.tv_usec
405                                                                                                                 , tp3.tv_sec-tp2.tv_sec ,tp3.tv_usec-tp2.tv_usec
406                                                                                                                 , tp4.tv_sec-tp3.tv_sec ,tp4.tv_usec-tp3.tv_usec);
407 #endif
408
409 queue_delete(retqueue);
410
411 //graph_print_adj_list();
412 return 0;
413 }