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