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