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