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