Mesh Animation + Depsgraph Tweaks:
[blender.git] / source / blender / editors / animation / keyframes_draw.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL 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.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): Joshua Leung (full recode)
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 /* System includes ----------------------------------------------------- */
31
32 #include <math.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <float.h>
36
37 #ifdef HAVE_CONFIG_H
38 #include <config.h>
39 #endif
40
41 #include "MEM_guardedalloc.h"
42
43 #include "BLI_blenlib.h"
44 #include "BLI_math.h"
45 #include "BLI_dlrbTree.h"
46
47 #include "DNA_listBase.h"
48 #include "DNA_anim_types.h"
49 #include "DNA_action_types.h"
50 #include "DNA_armature_types.h"
51 #include "DNA_camera_types.h"
52 #include "DNA_curve_types.h"
53 #include "DNA_object_types.h"
54 #include "DNA_screen_types.h"
55 #include "DNA_scene_types.h"
56 #include "DNA_space_types.h"
57 #include "DNA_key_types.h"
58 #include "DNA_lamp_types.h"
59 #include "DNA_mesh_types.h"
60 #include "DNA_material_types.h"
61 #include "DNA_meta_types.h"
62 #include "DNA_node_types.h"
63 #include "DNA_particle_types.h"
64 #include "DNA_userdef_types.h"
65 #include "DNA_gpencil_types.h"
66 #include "DNA_windowmanager_types.h"
67 #include "DNA_world_types.h"
68 #include "DNA_view2d_types.h"
69
70 #include "BKE_action.h"
71 #include "BKE_depsgraph.h"
72 #include "BKE_fcurve.h"
73 #include "BKE_key.h"
74 #include "BKE_material.h"
75 #include "BKE_object.h"
76 #include "BKE_global.h"         // XXX remove me!
77 #include "BKE_context.h"
78 #include "BKE_utildefines.h"
79
80 #include "BIF_gl.h"
81 #include "BIF_glutil.h"
82
83 #include "UI_interface.h"
84 #include "UI_interface_icons.h"
85 #include "UI_resources.h"
86 #include "UI_view2d.h"
87
88 #include "ED_anim_api.h"
89 #include "ED_keyframing.h"
90 #include "ED_keyframes_draw.h"
91 #include "ED_screen.h"
92 #include "ED_space_api.h"
93
94 /* *************************** Keyframe Processing *************************** */
95
96 /* ActKeyColumns (Keyframe Columns) ------------------------------------------ */
97
98 /* Comparator callback used for ActKeyColumns and cframe float-value pointer */
99 // NOTE: this is exported to other modules that use the ActKeyColumns for finding keyframes
100 short compare_ak_cfraPtr (void *node, void *data)
101 {
102         ActKeyColumn *ak= (ActKeyColumn *)node;
103         float *cframe= data;
104         
105         if (*cframe < ak->cfra)
106                 return -1;
107         else if (*cframe > ak->cfra)
108                 return 1;
109         else
110                 return 0;
111 }
112
113 /* --------------- */
114
115 /* Comparator callback used for ActKeyColumns and BezTriple */
116 static short compare_ak_bezt (void *node, void *data)
117 {
118         ActKeyColumn *ak= (ActKeyColumn *)node;
119         BezTriple *bezt= (BezTriple *)data;
120         
121         if (bezt->vec[1][0] < ak->cfra)
122                 return -1;
123         else if (bezt->vec[1][0] > ak->cfra)
124                 return 1;
125         else
126                 return 0;
127 }
128
129 /* New node callback used for building ActKeyColumns from BezTriples */
130 static DLRBT_Node *nalloc_ak_bezt (void *data)
131 {
132         ActKeyColumn *ak= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn");
133         BezTriple *bezt= (BezTriple *)data;
134         
135         /* store settings based on state of BezTriple */
136         ak->cfra= bezt->vec[1][0];
137         ak->sel= BEZSELECTED(bezt) ? SELECT : 0;
138         ak->key_type= BEZKEYTYPE(bezt); 
139         
140         /* set 'modified', since this is used to identify long keyframes */
141         ak->modified = 1;
142         
143         return (DLRBT_Node *)ak;
144 }
145
146 /* Node updater callback used for building ActKeyColumns from BezTriples */
147 static void nupdate_ak_bezt (void *node, void *data)
148 {
149         ActKeyColumn *ak= (ActKeyColumn *)node;
150         BezTriple *bezt= (BezTriple *)data;
151         
152         /* set selection status and 'touched' status */
153         if (BEZSELECTED(bezt)) ak->sel = SELECT;
154         ak->modified += 1;
155         
156         /* for keyframe type, 'proper' keyframes have priority over breakdowns (and other types for now) */
157         if (BEZKEYTYPE(bezt) == BEZT_KEYTYPE_KEYFRAME)
158                 ak->key_type= BEZT_KEYTYPE_KEYFRAME;
159 }
160
161 /* --------------- */
162
163 /* Add the given BezTriple to the given 'list' of Keyframes */
164 static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTriple *bezt)
165 {
166         if ELEM(NULL, keys, bezt) 
167                 return;
168         else
169                 BLI_dlrbTree_add(keys, compare_ak_bezt, nalloc_ak_bezt, nupdate_ak_bezt, bezt);
170 }
171
172 /* ActBeztColumns (Helpers for Long Keyframes) ------------------------------ */
173
174 /* maximum size of default buffer for BezTriple columns */
175 #define MAX_ABK_BUFSIZE         4
176
177 /* BezTriple Container Node */
178 // NOTE: only used internally while building Long Keyframes for now, but may be useful externally?
179 typedef struct ActBeztColumn {
180         /* Tree Node interface ---------------- */
181                 /* ListBase linkage */
182         struct ActBeztColumn *next, *prev;
183         
184                 /* sorting-tree linkage */
185         struct ActBeztColumn *left, *right;     /* 'children' of this node, less than and greater than it (respectively) */
186         struct ActBeztColumn *parent;           /* parent of this node in the tree */
187         char tree_col;                                          /* DLRB_BLACK or DLRB_RED */
188         char pad;
189         
190         /* BezTriple Store -------------------- */
191         short numBezts;                                         /* number of BezTriples on this frame */
192         float cfra;                                                     /* frame that the BezTriples occur on */
193         
194         BezTriple *bezts[MAX_ABK_BUFSIZE];      /* buffer of pointers to BezTriples on the same frame */
195         //BezTriple **bezts_extra;                      /* secondary buffer of pointers if need be */
196 } ActBeztColumn;
197
198 /* --------------- */
199
200 /* Comparator callback used for ActBeztColumns and BezTriple */
201 static short compare_abk_bezt (void *node, void *data)
202 {
203         ActBeztColumn *abk= (ActBeztColumn *)node;
204         BezTriple *bezt= (BezTriple *)data;
205         
206         if (bezt->vec[1][0] < abk->cfra)
207                 return -1;
208         else if (bezt->vec[1][0] > abk->cfra)
209                 return 1;
210         else
211                 return 0;
212 }
213
214 /* New node callback used for building ActBeztColumns from BezTriples */
215 static DLRBT_Node *nalloc_abk_bezt (void *data)
216 {
217         ActBeztColumn *abk= MEM_callocN(sizeof(ActBeztColumn), "ActKeyColumn");
218         BezTriple *bezt= (BezTriple *)data;
219         
220         /* store the BeztTriple in the buffer, and keep track of its frame number */
221         abk->cfra= bezt->vec[1][0];
222         abk->bezts[abk->numBezts++]= bezt;
223         
224         return (DLRBT_Node *)abk;
225 }
226
227 /* Node updater callback used for building ActBeztColumns from BezTriples */
228 static void nupdate_abk_bezt (void *node, void *data)
229 {
230         ActBeztColumn *abk= (ActBeztColumn *)node;
231         BezTriple *bezt= (BezTriple *)data;
232         
233         /* just add the BezTriple to the buffer if there's space, or allocate a new one */
234         if (abk->numBezts >= MAX_ABK_BUFSIZE) {
235                 // TODO: need to allocate new array to cater...
236                 //bezts_extra= MEM_callocN(...);
237                 if(G.f & G_DEBUG)
238                         printf("FIXME: nupdate_abk_bezt() missing case for too many overlapping BezTriples \n");
239         }
240         else {
241                 /* just store an extra one */
242                 abk->bezts[abk->numBezts++]= bezt;
243         }
244 }
245
246 /* --------------- */
247
248 /* Return the BezTriple in the given ActBeztColumn that matches the requested value */
249 static BezTriple *abk_get_bezt_with_value (ActBeztColumn *abk, float value)
250 {
251         BezTriple *bezt;
252         int i;
253         
254         /* sanity checks */
255         if (abk == NULL)
256                 return NULL;
257         
258         /* look over each BezTriple in this container */
259         for (i = 0; i < abk->numBezts; i++) {           
260                 /* only do exact match for now... */
261                 if (i >= sizeof(abk->bezts)/sizeof(BezTriple)) {
262                         // TODO: this case needs special handling
263                 }
264                 else {
265                         /* just use the default buffer */
266                         bezt= abk->bezts[i];
267                         
268                         if (bezt->vec[1][1] == value)
269                                 return bezt;
270                 }
271         }
272         
273         return NULL;
274 }
275
276 /* ActKeyBlocks (Long Keyframes) ------------------------------------------ */
277
278 /* Create a ActKeyColumn for a pair of BezTriples */
279 static ActKeyBlock *bezts_to_new_actkeyblock(BezTriple *prev, BezTriple *beztn)
280 {
281         ActKeyBlock *ab= MEM_callocN(sizeof(ActKeyBlock), "ActKeyBlock");
282         
283         ab->start= prev->vec[1][0];
284         ab->end= beztn->vec[1][0];
285         ab->val= beztn->vec[1][1];
286         
287         ab->sel= (BEZSELECTED(prev) || BEZSELECTED(beztn)) ? SELECT : 0;
288         ab->modified = 1;
289         
290         return ab;
291 }
292
293 static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, DLRBT_Tree *beztTree, BezTriple *beztn)
294 {
295         ActKeyBlock *new_ab= NULL;
296         ActBeztColumn *abk;
297         BezTriple *prev;
298         
299         /* get the BezTriple immediately before the given one which has the same value */
300                 /* the keyframes immediately before the ones containing the specified keyframe */
301         abk= (ActBeztColumn *)BLI_dlrbTree_search_prev(beztTree, compare_abk_bezt, beztn);
302                 /* if applicable, the BezTriple with the same value */
303         prev= (abk) ? abk_get_bezt_with_value(abk, beztn->vec[1][1]) : NULL;
304
305         /* check if block needed - same value(s)?
306          *      -> firstly, handles must have same central value as each other
307          *      -> secondly, handles which control that section of the curve must be constant
308          */
309         if ((!prev) || (!beztn)) return;
310         if (IS_EQ(beztn->vec[1][1], prev->vec[1][1])==0) return;
311         if (IS_EQ(beztn->vec[1][1], beztn->vec[0][1])==0) return;
312         if (IS_EQ(prev->vec[1][1], prev->vec[2][1])==0) return;
313         
314         
315         /* if there are no blocks already, just add as root */
316         if (blocks->root == NULL) {
317                 /* just add this as the root, then call the tree-balancing functions to validate */
318                 new_ab= bezts_to_new_actkeyblock(prev, beztn);
319                 blocks->root= (DLRBT_Node *)new_ab;
320         }
321         else {
322                 ActKeyBlock *ab, *abp=NULL, *abn=NULL;
323                 
324                 /* try to find a keyblock that starts on the previous beztriple, and add a new one if none start there
325                  * Note: we can't search from end to try to optimise this as it causes errors there's
326                  *              an A ___ B |---| B situation
327                  */
328                 // FIXME: here there is a bug where we are trying to get the summary for the following channels
329                 //              A|--------------|A ______________ B|--------------|B
330                 //              A|------------------------------------------------|A
331                 //              A|----|A|---|A|-----------------------------------|A
332                 for (ab= blocks->root; ab; abp= ab, ab= abn) {
333                         /* check if this is a match, or whether we go left or right */
334                         if (ab->start == prev->vec[1][0]) {
335                                 /* set selection status and 'touched' status */
336                                 if (BEZSELECTED(beztn)) ab->sel = SELECT;
337                                 ab->modified += 1;
338                                 
339                                 /* done... no need to insert */
340                                 return;
341                         }
342                         else {
343                                 ActKeyBlock **abnp= NULL; 
344                                 
345                                 /* check if go left or right, but if not available, add new node */
346                                 if (ab->start < prev->vec[1][0]) 
347                                         abnp= &ab->right;
348                                 else
349                                         abnp= &ab->left;
350                                         
351                                 /* if this does not exist, add a new node, otherwise continue... */
352                                 if (*abnp == NULL) {
353                                         /* add a new node representing this, and attach it to the relevant place */
354                                         new_ab= bezts_to_new_actkeyblock(prev, beztn);
355                                         new_ab->parent= ab;
356                                         *abnp= new_ab;
357                                         break;
358                                 }
359                                 else
360                                         abn= *abnp;
361                         }
362                 }
363         }
364         
365         /* now, balance the tree taking into account this newly added node */
366         BLI_dlrbTree_insert(blocks, (DLRBT_Node *)new_ab);
367 }
368
369 /* --------- */
370
371 /* Handle the 'touched' status of ActKeyColumn tree nodes */
372 static void set_touched_actkeycolumn (ActKeyColumn *ak)
373 {
374         /* sanity check */
375         if (ak == NULL)
376                 return;
377                 
378         /* deal with self first */
379         if (ak->modified) {
380                 ak->modified= 0;
381                 ak->totcurve++;
382         }
383         
384         /* children */
385         set_touched_actkeycolumn(ak->left);
386         set_touched_actkeycolumn(ak->right);
387 }
388
389 /* Handle the 'touched' status of ActKeyBlock tree nodes */
390 static void set_touched_actkeyblock (ActKeyBlock *ab)
391 {
392         /* sanity check */
393         if (ab == NULL)
394                 return;
395                 
396         /* deal with self first */
397         if (ab->modified) {
398                 ab->modified= 0;
399                 ab->totcurve++;
400         }
401         
402         /* children */
403         set_touched_actkeyblock(ab->left);
404         set_touched_actkeyblock(ab->right);
405 }
406
407 /* *************************** Keyframe Drawing *************************** */
408
409 /* coordinates for diamond shape */
410 static const float _unit_diamond_shape[4][2] = {
411         {0.0f, 1.0f},   /* top vert */
412         {1.0f, 0.0f},   /* mid-right */
413         {0.0f, -1.0f},  /* bottom vert */
414         {-1.0f, 0.0f}   /* mid-left */
415 }; 
416
417 /* draw a simple diamond shape with OpenGL */
418 void draw_keyframe_shape (float x, float y, float xscale, float hsize, short sel, short key_type, short mode)
419 {
420         static GLuint displist1=0;
421         static GLuint displist2=0;
422         
423         /* initialise 2 display lists for diamond shape - one empty, one filled */
424         if (displist1 == 0) {
425                 displist1= glGenLists(1);
426                         glNewList(displist1, GL_COMPILE);
427                         
428                         glBegin(GL_LINE_LOOP);
429                                 glVertex2fv(_unit_diamond_shape[0]);
430                                 glVertex2fv(_unit_diamond_shape[1]);
431                                 glVertex2fv(_unit_diamond_shape[2]);
432                                 glVertex2fv(_unit_diamond_shape[3]);
433                         glEnd();
434                 glEndList();
435         }
436         if (displist2 == 0) {
437                 displist2= glGenLists(1);
438                         glNewList(displist2, GL_COMPILE);
439                         
440                         glBegin(GL_QUADS);
441                                 glVertex2fv(_unit_diamond_shape[0]);
442                                 glVertex2fv(_unit_diamond_shape[1]);
443                                 glVertex2fv(_unit_diamond_shape[2]);
444                                 glVertex2fv(_unit_diamond_shape[3]);
445                         glEnd();
446                 glEndList();
447         }
448         
449         /* tweak size of keyframe shape according to type of keyframe 
450          *      - 'proper' keyframes have key_type=0, so get drawn at full size
451          */
452         hsize -= 0.5f*key_type;
453         
454         /* adjust view transform before starting */
455         glTranslatef(x, y, 0.0f);
456         glScalef(1.0f/xscale*hsize, hsize, 1.0f);
457         
458         /* anti-aliased lines for more consistent appearance */
459         glEnable(GL_LINE_SMOOTH);
460         
461         /* draw! */
462         if ELEM(mode, KEYFRAME_SHAPE_INSIDE, KEYFRAME_SHAPE_BOTH) {
463                 /* interior - hardcoded colors (for selected and unselected only) */
464                 switch (key_type) {
465                         case BEZT_KEYTYPE_BREAKDOWN: /* bluish frames for now */
466                         {
467                                 if (sel) glColor3f(0.33f, 0.75f, 0.93f);
468                                 else glColor3f(0.70f, 0.86f, 0.91f);
469                         }
470                                 break;
471                                 
472                         case BEZT_KEYTYPE_EXTREME: /* redish frames for now */
473                         {
474                                 if (sel) glColor3f(95.0f, 0.5f, 0.5f);
475                                 else glColor3f(0.91f, 0.70f, 0.80f);
476                         }
477                                 break;
478                                 
479                         case BEZT_KEYTYPE_KEYFRAME: /* traditional yellowish frames for now */
480                         default:
481                         {
482                                 if (sel) UI_ThemeColorShade(TH_STRIP_SELECT, 50);
483                                 else glColor3f(0.91f, 0.91f, 0.91f);
484                         }
485                                 break;
486                 }
487                 
488                 glCallList(displist2);
489         }
490         
491         if ELEM(mode, KEYFRAME_SHAPE_FRAME, KEYFRAME_SHAPE_BOTH) {
492                 /* exterior - black frame */
493                 glColor3ub(0, 0, 0);
494                 
495                 glCallList(displist1);
496         }
497         
498         glDisable(GL_LINE_SMOOTH);
499         
500         /* restore view transform */
501         glScalef(xscale/hsize, 1.0f/hsize, 1.0);
502         glTranslatef(-x, -y, 0.0f);
503 }
504
505 static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, float ypos)
506 {
507         ActKeyColumn *ak;
508         ActKeyBlock *ab;
509         float xscale;
510         
511         glEnable(GL_BLEND);
512         
513         /* get View2D scaling factor */
514         UI_view2d_getscale(v2d, &xscale, NULL);
515         
516         /* draw keyblocks */
517         if (blocks) {
518                 for (ab= blocks->first; ab; ab= ab->next) {
519                         short startCurves, endCurves, totCurves;
520                         
521                         /* find out how many curves occur at each keyframe */
522                         ak= (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->start);
523                         startCurves = (ak)? ak->totcurve: 0;
524                         
525                         ak= (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->end);
526                         endCurves = (ak)? ak->totcurve: 0;
527                         
528                         /* only draw keyblock if it appears in at all of the keyframes at lowest end */
529                         if (!startCurves && !endCurves) 
530                                 continue;
531                         else
532                                 totCurves = (startCurves>endCurves)? endCurves: startCurves;
533                                 
534                         if (ab->totcurve >= totCurves) {
535                                 /* draw block */
536                                 if (ab->sel)
537                                         UI_ThemeColor4(TH_STRIP_SELECT);
538                                 else
539                                         UI_ThemeColor4(TH_STRIP);
540                                 
541                                 glRectf(ab->start, ypos-5, ab->end, ypos+5);
542                         }
543                 }
544         }
545         
546         /* draw keys */
547         if (keys) {
548                 for (ak= keys->first; ak; ak= ak->next) {
549                         /* optimisation: if keyframe doesn't appear within 5 units (screenspace) in visible area, don't draw 
550                          *      - this might give some improvements, since we current have to flip between view/region matrices
551                          */
552                         if (IN_RANGE_INCL(ak->cfra, v2d->cur.xmin, v2d->cur.xmax) == 0)
553                                 continue;
554                         
555                         /* draw using OpenGL - uglier but faster */
556                         // NOTE1: a previous version of this didn't work nice for some intel cards
557                         // NOTE2: if we wanted to go back to icons, these are  icon = (ak->sel & SELECT) ? ICON_SPACE2 : ICON_SPACE3;
558                         draw_keyframe_shape(ak->cfra, ypos, xscale, 5.0f, (ak->sel & SELECT), ak->key_type, KEYFRAME_SHAPE_BOTH);
559                 }       
560         }
561         
562         glDisable(GL_BLEND);
563 }
564
565 /* *************************** Channel Drawing Funcs *************************** */
566
567 void draw_summary_channel(View2D *v2d, bAnimContext *ac, float ypos)
568 {
569         DLRBT_Tree keys, blocks;
570         
571         BLI_dlrbTree_init(&keys);
572         BLI_dlrbTree_init(&blocks);
573         
574                 summary_to_keylist(ac, &keys, &blocks);
575         
576         BLI_dlrbTree_linkedlist_sync(&keys);
577         BLI_dlrbTree_linkedlist_sync(&blocks);
578         
579                 draw_keylist(v2d, &keys, &blocks, ypos);
580         
581         BLI_dlrbTree_free(&keys);
582         BLI_dlrbTree_free(&blocks);
583 }
584
585 void draw_scene_channel(View2D *v2d, bDopeSheet *ads, Scene *sce, float ypos)
586 {
587         DLRBT_Tree keys, blocks;
588         
589         BLI_dlrbTree_init(&keys);
590         BLI_dlrbTree_init(&blocks);
591         
592                 scene_to_keylist(ads, sce, &keys, &blocks);
593         
594         BLI_dlrbTree_linkedlist_sync(&keys);
595         BLI_dlrbTree_linkedlist_sync(&blocks);
596         
597                 draw_keylist(v2d, &keys, &blocks, ypos);
598         
599         BLI_dlrbTree_free(&keys);
600         BLI_dlrbTree_free(&blocks);
601 }
602
603 void draw_object_channel(View2D *v2d, bDopeSheet *ads, Object *ob, float ypos)
604 {
605         DLRBT_Tree keys, blocks;
606         
607         BLI_dlrbTree_init(&keys);
608         BLI_dlrbTree_init(&blocks);
609         
610                 ob_to_keylist(ads, ob, &keys, &blocks);
611         
612         BLI_dlrbTree_linkedlist_sync(&keys);
613         BLI_dlrbTree_linkedlist_sync(&blocks);
614         
615                 draw_keylist(v2d, &keys, &blocks, ypos);
616         
617         BLI_dlrbTree_free(&keys);
618         BLI_dlrbTree_free(&blocks);
619 }
620
621 void draw_fcurve_channel(View2D *v2d, AnimData *adt, FCurve *fcu, float ypos)
622 {
623         DLRBT_Tree keys, blocks;
624         
625         BLI_dlrbTree_init(&keys);
626         BLI_dlrbTree_init(&blocks);
627         
628                 fcurve_to_keylist(adt, fcu, &keys, &blocks);
629         
630         BLI_dlrbTree_linkedlist_sync(&keys);
631         BLI_dlrbTree_linkedlist_sync(&blocks);
632         
633                 draw_keylist(v2d, &keys, &blocks, ypos);
634         
635         BLI_dlrbTree_free(&keys);
636         BLI_dlrbTree_free(&blocks);
637 }
638
639 void draw_agroup_channel(View2D *v2d, AnimData *adt, bActionGroup *agrp, float ypos)
640 {
641         DLRBT_Tree keys, blocks;
642         
643         BLI_dlrbTree_init(&keys);
644         BLI_dlrbTree_init(&blocks);
645         
646                 agroup_to_keylist(adt, agrp, &keys, &blocks);
647         
648         BLI_dlrbTree_linkedlist_sync(&keys);
649         BLI_dlrbTree_linkedlist_sync(&blocks);
650         
651                 draw_keylist(v2d, &keys, &blocks, ypos);
652         
653         BLI_dlrbTree_free(&keys);
654         BLI_dlrbTree_free(&blocks);
655 }
656
657 void draw_action_channel(View2D *v2d, AnimData *adt, bAction *act, float ypos)
658 {
659         DLRBT_Tree keys, blocks;
660         
661         BLI_dlrbTree_init(&keys);
662         BLI_dlrbTree_init(&blocks);
663         
664                 action_to_keylist(adt, act, &keys, &blocks);
665         
666         BLI_dlrbTree_linkedlist_sync(&keys);
667         BLI_dlrbTree_linkedlist_sync(&blocks);
668         
669                 draw_keylist(v2d, &keys, &blocks, ypos);
670         
671         BLI_dlrbTree_free(&keys);
672         BLI_dlrbTree_free(&blocks);
673 }
674
675 void draw_gpl_channel(View2D *v2d, bDopeSheet *ads, bGPDlayer *gpl, float ypos)
676 {
677         DLRBT_Tree keys;
678         
679         BLI_dlrbTree_init(&keys);
680         
681                 gpl_to_keylist(ads, gpl, &keys, NULL);
682         
683         BLI_dlrbTree_linkedlist_sync(&keys);
684         
685                 draw_keylist(v2d, &keys, NULL, ypos);
686         
687         BLI_dlrbTree_free(&keys);
688 }
689
690 /* *************************** Keyframe List Conversions *************************** */
691
692 void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, DLRBT_Tree *blocks)
693 {
694         if (ac) {
695                 ListBase anim_data = {NULL, NULL};
696                 bAnimListElem *ale;
697                 int filter;
698                 
699                 /* get F-Curves to take keyframes from */
700                 filter= (ANIMFILTER_VISIBLE | ANIMFILTER_CURVESONLY);
701                 ANIM_animdata_filter(ac, &anim_data, filter, ac->data, ac->datatype);
702                 
703                 /* loop through each F-Curve, grabbing the keyframes */
704                 for (ale= anim_data.first; ale; ale= ale->next)
705                         fcurve_to_keylist(ale->adt, ale->data, keys, blocks);
706                 
707                 BLI_freelistN(&anim_data);
708         }
709 }
710
711 void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree *blocks)
712 {
713         if (sce) {
714                 AnimData *adt;
715                 int filterflag;
716                 
717                 /* get filterflag */
718                 if (ads)
719                         filterflag= ads->filterflag;
720                 else
721                         filterflag= 0;
722                         
723                 /* scene animdata */
724                 if ((sce->adt) && !(filterflag & ADS_FILTER_NOSCE)) {
725                         adt= sce->adt;
726                         
727                         if (adt->action) 
728                                 action_to_keylist(adt, adt->action, keys, blocks);
729                 }
730                 
731                 /* world animdata */
732                 if ((sce->world) && (sce->world->adt) && !(filterflag & ADS_FILTER_NOWOR)) {
733                         adt= sce->world->adt;
734                         
735                         if (adt->action) 
736                                 action_to_keylist(adt, adt->action, keys, blocks);
737                 }
738                 
739                 /* nodetree animdata */
740                 if ((sce->nodetree) && (sce->nodetree->adt) && !(filterflag & ADS_FILTER_NONTREE)) {
741                         adt= sce->nodetree->adt;
742                         
743                         if (adt->action) 
744                                 action_to_keylist(adt, adt->action, keys, blocks);
745                 }
746         }
747 }
748
749 void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, DLRBT_Tree *blocks)
750 {
751         Key *key= ob_get_key(ob);
752         int filterflag= (ads)? ads->filterflag : 0;
753         
754         /* sanity check */
755         if (ob == NULL)
756                 return;
757                 
758         /* Add action keyframes */
759         if (ob->adt && ob->adt->action)
760                 action_to_keylist(ob->adt, ob->adt->action, keys, blocks);
761         
762         /* Add shapekey keyframes (only if dopesheet allows, if it is available) */
763         if ((key && key->adt && key->adt->action) && !(filterflag & ADS_FILTER_NOSHAPEKEYS))
764                 action_to_keylist(key->adt, key->adt->action, keys, blocks);
765         
766         /* Add material keyframes */
767         if ((ob->totcol) && !(filterflag & ADS_FILTER_NOMAT)) {
768                 int a;
769                 
770                 for (a=0; a < ob->totcol; a++) {
771                         Material *ma= give_current_material(ob, a);
772                         
773                         /* there might not be a material */
774                         if (ELEM(NULL, ma, ma->adt)) 
775                                 continue;
776                         
777                         /* add material's data */
778                         action_to_keylist(ma->adt, ma->adt->action, keys, blocks);
779                 }
780         }
781         
782         /* Add object data keyframes */
783         switch (ob->type) {
784                 case OB_CAMERA: /* ------- Camera ------------ */
785                 {
786                         Camera *ca= (Camera *)ob->data;
787                         
788                         if ((ca->adt) && !(filterflag & ADS_FILTER_NOCAM)) 
789                                 action_to_keylist(ca->adt, ca->adt->action, keys, blocks);
790                 }
791                         break;
792                 case OB_LAMP: /* ---------- Lamp ----------- */
793                 {
794                         Lamp *la= (Lamp *)ob->data;
795                         
796                         if ((la->adt) && !(filterflag & ADS_FILTER_NOLAM)) 
797                                 action_to_keylist(la->adt, la->adt->action, keys, blocks);
798                 }
799                         break;
800                 case OB_CURVE: /* ------- Curve ---------- */
801                 case OB_SURF: /* ------- Nurbs Surface ---------- */
802                 case OB_FONT: /* ------- Text Curve ---------- */
803                 {
804                         Curve *cu= (Curve *)ob->data;
805                         
806                         if ((cu->adt) && !(filterflag & ADS_FILTER_NOCUR)) 
807                                 action_to_keylist(cu->adt, cu->adt->action, keys, blocks);
808                 }
809                         break;
810                 case OB_MBALL: /* ------- MetaBall ---------- */
811                 {
812                         MetaBall *mb= (MetaBall *)ob->data;
813                         
814                         if ((mb->adt) && !(filterflag & ADS_FILTER_NOMBA)) 
815                                 action_to_keylist(mb->adt, mb->adt->action, keys, blocks);
816                 }
817                         break;
818                 case OB_ARMATURE: /* ------- Armature ---------- */
819                 {
820                         bArmature *arm= (bArmature *)ob->data;
821                         
822                         if ((arm->adt) && !(filterflag & ADS_FILTER_NOARM)) 
823                                 action_to_keylist(arm->adt, arm->adt->action, keys, blocks);
824                 }
825                         break;
826                 case OB_MESH: /* ------- Mesh ---------- */
827                 {
828                         Mesh *me= (Mesh *)ob->data;
829                         
830                         if ((me->adt) && !(filterflag & ADS_FILTER_NOMESH)) 
831                                 action_to_keylist(me->adt, me->adt->action, keys, blocks);
832                 }
833                         break;
834         }
835         
836         /* Add Particle System Keyframes */
837         if ((ob->particlesystem.first) && !(filterflag & ADS_FILTER_NOPART)) {
838                 ParticleSystem *psys = ob->particlesystem.first;
839                 
840                 for(; psys; psys=psys->next) {
841                         if (ELEM(NULL, psys->part, psys->part->adt))
842                                 continue;
843                         else
844                                 action_to_keylist(psys->part->adt, psys->part->adt->action, keys, blocks);
845                 }
846         }
847 }
848
849 void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree *blocks)
850 {
851         DLRBT_Tree *beztTree = NULL;
852         BezTriple *bezt;
853         int v;
854         
855         if (fcu && fcu->totvert && fcu->bezt) {
856                 /* apply NLA-mapping (if applicable) */
857                 if (adt)        
858                         ANIM_nla_mapping_apply_fcurve(adt, fcu, 0, 1);
859                 
860                 /* if getting long keyframes too, grab the BezTriples in a BST for 
861                  * accelerated searching...
862                  */
863                 if (blocks) {
864                         /* init new tree */
865                         beztTree= BLI_dlrbTree_new();
866                         
867                         /* populate tree with the BezTriples */
868                         for (v=0, bezt=fcu->bezt; v < fcu->totvert; v++, bezt++)
869                                 BLI_dlrbTree_add(beztTree, compare_abk_bezt, nalloc_abk_bezt, nupdate_abk_bezt, bezt);
870                         
871                         /* make sure that it is suitable for linked-list searching too */
872                         BLI_dlrbTree_linkedlist_sync(beztTree);
873                 }
874                 
875                 /* loop through beztriples, making ActKeysColumns and ActKeyBlocks */
876                 for (v=0, bezt=fcu->bezt; v < fcu->totvert; v++, bezt++) {
877                         add_bezt_to_keycolumns_list(keys, bezt);
878                         if (blocks) add_bezt_to_keyblocks_list(blocks, beztTree, bezt);
879                 }
880                 
881                 /* update the number of curves that elements have appeared in  */
882                 if (keys)
883                         set_touched_actkeycolumn(keys->root);
884                 if (blocks)
885                         set_touched_actkeyblock(blocks->root);
886                         
887                 /* free temp data for building long keyframes */
888                 if (blocks && beztTree) {
889                         BLI_dlrbTree_free(beztTree);
890                         MEM_freeN(beztTree);
891                 }
892                 
893                 /* unapply NLA-mapping if applicable */
894                 ANIM_nla_mapping_apply_fcurve(adt, fcu, 1, 1);
895         }
896 }
897
898 void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, DLRBT_Tree *keys, DLRBT_Tree *blocks)
899 {
900         FCurve *fcu;
901
902         if (agrp) {
903                 /* loop through F-Curves */
904                 for (fcu= agrp->channels.first; fcu && fcu->grp==agrp; fcu= fcu->next) {
905                         fcurve_to_keylist(adt, fcu, keys, blocks);
906                 }
907         }
908 }
909
910 void action_to_keylist(AnimData *adt, bAction *act, DLRBT_Tree *keys, DLRBT_Tree *blocks)
911 {
912         FCurve *fcu;
913
914         if (act) {
915                 /* loop through F-Curves */
916                 for (fcu= act->curves.first; fcu; fcu= fcu->next) {
917                         fcurve_to_keylist(adt, fcu, keys, blocks);
918                 }
919         }
920 }
921
922
923 void gpl_to_keylist(bDopeSheet *ads, bGPDlayer *gpl, DLRBT_Tree *keys, DLRBT_Tree *blocks)
924 {
925         bGPDframe *gpf;
926         ActKeyColumn *ak;
927         
928         if (gpl && keys) {
929                 /* loop over frames, converting directly to 'keyframes' (should be in order too) */
930                 for (gpf= gpl->frames.first; gpf; gpf= gpf->next) {
931                         ak= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn");
932                         BLI_addtail((ListBase *)keys, ak);
933                         
934                         ak->cfra= (float)gpf->framenum;
935                         ak->modified = 1;
936                         ak->key_type= 0; 
937                         
938                         if (gpf->flag & GP_FRAME_SELECT)
939                                 ak->sel = SELECT;
940                         else
941                                 ak->sel = 0;
942                 }
943         }
944 }
945