Holiday coding log :)
[blender.git] / source / blender / editors / animation / keyframes_draw.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Joshua Leung (full recode)
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/animation/keyframes_draw.c
29  *  \ingroup edanimation
30  */
31
32
33 /* System includes ----------------------------------------------------- */
34
35 #include <math.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <float.h>
39
40 #include "MEM_guardedalloc.h"
41
42 #include "BLI_blenlib.h"
43 #include "BLI_math.h"
44 #include "BLI_dlrbTree.h"
45 #include "BLI_utildefines.h"
46
47 #include "DNA_anim_types.h"
48 #include "DNA_armature_types.h"
49 #include "DNA_camera_types.h"
50 #include "DNA_object_types.h"
51 #include "DNA_scene_types.h"
52 #include "DNA_key_types.h"
53 #include "DNA_lamp_types.h"
54 #include "DNA_lattice_types.h"
55 #include "DNA_mesh_types.h"
56 #include "DNA_material_types.h"
57 #include "DNA_meta_types.h"
58 #include "DNA_node_types.h"
59 #include "DNA_particle_types.h"
60 #include "DNA_speaker_types.h"
61 #include "DNA_world_types.h"
62 #include "DNA_gpencil_types.h"
63 #include "DNA_mask_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 /* Comparator callback used for ActKeyColumns and GPencil frame */
191 static short compare_ak_masklayshape(void *node, void *data)
192 {
193         ActKeyColumn *ak = (ActKeyColumn *)node;
194         MaskLayerShape *masklay_shape = (MaskLayerShape *)data;
195
196         if (masklay_shape->frame < ak->cfra)
197                 return -1;
198         else if (masklay_shape->frame > ak->cfra)
199                 return 1;
200         else
201                 return 0;
202 }
203
204 /* New node callback used for building ActKeyColumns from GPencil frames */
205 static DLRBT_Node *nalloc_ak_masklayshape(void *data)
206 {
207         ActKeyColumn *ak = MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumnGPF");
208         MaskLayerShape *masklay_shape = (MaskLayerShape *)data;
209
210         /* store settings based on state of BezTriple */
211         ak->cfra = masklay_shape->frame;
212         ak->sel = (masklay_shape->flag & MASK_SHAPE_SELECT) ? SELECT : 0;
213
214         /* set 'modified', since this is used to identify long keyframes */
215         ak->modified = 1;
216
217         return (DLRBT_Node *)ak;
218 }
219
220 /* Node updater callback used for building ActKeyColumns from GPencil frames */
221 static void nupdate_ak_masklayshape(void *node, void *data)
222 {
223         ActKeyColumn *ak = (ActKeyColumn *)node;
224         MaskLayerShape *masklay_shape = (MaskLayerShape *)data;
225
226         /* set selection status and 'touched' status */
227         if (masklay_shape->flag & MASK_SHAPE_SELECT) ak->sel = SELECT;
228         ak->modified += 1;
229 }
230
231
232 /* --------------- */
233
234 /* Add the given BezTriple to the given 'list' of Keyframes */
235 static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTriple *bezt)
236 {
237         if (ELEM(NULL, keys, bezt))
238                 return;
239         else
240                 BLI_dlrbTree_add(keys, compare_ak_bezt, nalloc_ak_bezt, nupdate_ak_bezt, bezt);
241 }
242
243 /* Add the given GPencil Frame to the given 'list' of Keyframes */
244 static void add_gpframe_to_keycolumns_list(DLRBT_Tree *keys, bGPDframe *gpf)
245 {
246         if (ELEM(NULL, keys, gpf))
247                 return;
248         else
249                 BLI_dlrbTree_add(keys, compare_ak_gpframe, nalloc_ak_gpframe, nupdate_ak_gpframe, gpf);
250 }
251
252 /* Add the given MaskLayerShape Frame to the given 'list' of Keyframes */
253 static void add_masklay_to_keycolumns_list(DLRBT_Tree *keys, MaskLayerShape *masklay_shape)
254 {
255         if (ELEM(NULL, keys, masklay_shape))
256                 return;
257         else
258                 BLI_dlrbTree_add(keys, compare_ak_masklayshape, nalloc_ak_masklayshape, nupdate_ak_masklayshape, masklay_shape);
259 }
260
261 /* ActBeztColumns (Helpers for Long Keyframes) ------------------------------ */
262
263 /* maximum size of default buffer for BezTriple columns */
264 #define MAX_ABK_BUFSIZE     4
265
266 /* BezTriple Container Node */
267 // NOTE: only used internally while building Long Keyframes for now, but may be useful externally?
268 typedef struct ActBeztColumn {
269         /* Tree Node interface ---------------- */
270         /* ListBase linkage */
271         struct ActBeztColumn *next, *prev;
272         
273         /* sorting-tree linkage */
274         struct ActBeztColumn *left, *right; /* 'children' of this node, less than and greater than it (respectively) */
275         struct ActBeztColumn *parent;       /* parent of this node in the tree */
276         char tree_col;                      /* DLRB_BLACK or DLRB_RED */
277         char pad;
278         
279         /* BezTriple Store -------------------- */
280         short numBezts;                     /* number of BezTriples on this frame */
281         float cfra;                         /* frame that the BezTriples occur on */
282         
283         BezTriple *bezts[MAX_ABK_BUFSIZE];  /* buffer of pointers to BezTriples on the same frame */
284         //BezTriple **bezts_extra;                      /* secondary buffer of pointers if need be */
285 } ActBeztColumn;
286
287 /* --------------- */
288
289 /* Comparator callback used for ActBeztColumns and BezTriple */
290 static short compare_abk_bezt(void *node, void *data)
291 {
292         ActBeztColumn *abk = (ActBeztColumn *)node;
293         BezTriple *bezt = (BezTriple *)data;
294         
295         if (bezt->vec[1][0] < abk->cfra)
296                 return -1;
297         else if (bezt->vec[1][0] > abk->cfra)
298                 return 1;
299         else
300                 return 0;
301 }
302
303 /* New node callback used for building ActBeztColumns from BezTriples */
304 static DLRBT_Node *nalloc_abk_bezt(void *data)
305 {
306         ActBeztColumn *abk = MEM_callocN(sizeof(ActBeztColumn), "ActKeyColumn");
307         BezTriple *bezt = (BezTriple *)data;
308         
309         /* store the BeztTriple in the buffer, and keep track of its frame number */
310         abk->cfra = bezt->vec[1][0];
311         abk->bezts[abk->numBezts++] = bezt;
312         
313         return (DLRBT_Node *)abk;
314 }
315
316 /* Node updater callback used for building ActBeztColumns from BezTriples */
317 static void nupdate_abk_bezt(void *node, void *data)
318 {
319         ActBeztColumn *abk = (ActBeztColumn *)node;
320         BezTriple *bezt = (BezTriple *)data;
321         
322         /* just add the BezTriple to the buffer if there's space, or allocate a new one */
323         if (abk->numBezts >= MAX_ABK_BUFSIZE) {
324                 // TODO: need to allocate new array to cater...
325                 //bezts_extra = MEM_callocN(...);
326                 if (G.debug & G_DEBUG)
327                         printf("FIXME: nupdate_abk_bezt() missing case for too many overlapping BezTriples\n");
328         }
329         else {
330                 /* just store an extra one */
331                 abk->bezts[abk->numBezts++] = bezt;
332         }
333 }
334
335 /* --------------- */
336
337 /* Return the BezTriple in the given ActBeztColumn that matches the requested value */
338 static BezTriple *abk_get_bezt_with_value(ActBeztColumn *abk, float value)
339 {
340         BezTriple *bezt;
341         int i;
342         
343         /* sanity checks */
344         if (abk == NULL)
345                 return NULL;
346         
347         /* look over each BezTriple in this container */
348         for (i = 0; i < abk->numBezts; i++) {
349                 /* only do exact match for now... */
350                 if (/*i >= MAX_ABK_BUFSIZE*/ 0) {
351                         // TODO: this case needs special handling
352                 }
353                 else {
354                         /* just use the default buffer */
355                         bezt = abk->bezts[i];
356                         
357                         if (bezt->vec[1][1] == value)
358                                 return bezt;
359                 }
360         }
361         
362         return NULL;
363 }
364
365 /* ActKeyBlocks (Long Keyframes) ------------------------------------------ */
366
367 /* Comparator callback used for ActKeyBlock and cframe float-value pointer */
368 /* NOTE: this is exported to other modules that use the ActKeyBlocks for finding long-keyframes */
369 short compare_ab_cfraPtr(void *node, void *data)
370 {
371         ActKeyBlock *ab = (ActKeyBlock *)node;
372         float *cframe = data;
373         
374         if (*cframe < ab->start)
375                 return -1;
376         else if (*cframe > ab->start)
377                 return 1;
378         else
379                 return 0;
380 }
381
382 /* --------------- */
383
384 /* Create a ActKeyColumn for a pair of BezTriples */
385 static ActKeyBlock *bezts_to_new_actkeyblock(BezTriple *prev, BezTriple *beztn)
386 {
387         ActKeyBlock *ab = MEM_callocN(sizeof(ActKeyBlock), "ActKeyBlock");
388         
389         ab->start = prev->vec[1][0];
390         ab->end = beztn->vec[1][0];
391         ab->val = beztn->vec[1][1];
392         
393         ab->sel = (BEZSELECTED(prev) || BEZSELECTED(beztn)) ? SELECT : 0;
394         ab->modified = 1;
395         
396         return ab;
397 }
398
399 static void add_bezt_to_keyblocks_list(DLRBT_Tree *blocks, DLRBT_Tree *beztTree, BezTriple *beztn)
400 {
401         ActKeyBlock *new_ab = NULL;
402         ActBeztColumn *abk;
403         BezTriple *prev;
404         
405         /* get the BezTriple immediately before the given one which has the same value */
406         /* the keyframes immediately before the ones containing the specified keyframe */
407         abk = (ActBeztColumn *)BLI_dlrbTree_search_prev(beztTree, compare_abk_bezt, beztn);
408         /* if applicable, the BezTriple with the same value */
409         prev = (abk) ? abk_get_bezt_with_value(abk, beztn->vec[1][1]) : NULL;
410         
411         /* check if block needed - same value(s)?
412          *      -> firstly, handles must have same central value as each other
413          *      -> secondly, handles which control that section of the curve must be constant
414          */
415         if (prev == NULL) return;
416         if (IS_EQF(beztn->vec[1][1], prev->vec[1][1]) == 0) return;
417         if (IS_EQF(beztn->vec[1][1], beztn->vec[0][1]) == 0) return;
418         if (IS_EQF(prev->vec[1][1], prev->vec[2][1]) == 0) return;
419         
420         
421         /* if there are no blocks already, just add as root */
422         if (blocks->root == NULL) {
423                 /* just add this as the root, then call the tree-balancing functions to validate */
424                 new_ab = bezts_to_new_actkeyblock(prev, beztn);
425                 blocks->root = (DLRBT_Node *)new_ab;
426         }
427         else {
428                 ActKeyBlock *ab, *abn = NULL;
429                 
430                 /* try to find a keyblock that starts on the previous beztriple, and add a new one if none start there
431                  * Note: we can't search from end to try to optimize this as it causes errors there's
432                  *      an A ___ B |---| B situation
433                  */
434                 // FIXME: here there is a bug where we are trying to get the summary for the following channels
435                 //              A|--------------|A ______________ B|--------------|B
436                 //              A|------------------------------------------------|A
437                 //              A|----|A|---|A|-----------------------------------|A
438                 for (ab = blocks->root; ab; ab = abn) {
439                         /* check if this is a match, or whether we go left or right */
440                         if (ab->start == prev->vec[1][0]) {
441                                 /* set selection status and 'touched' status */
442                                 if (BEZSELECTED(beztn)) ab->sel = SELECT;
443                                 ab->modified += 1;
444                                 
445                                 /* done... no need to insert */
446                                 return;
447                         }
448                         else {
449                                 ActKeyBlock **abnp = NULL;
450                                 
451                                 /* check if go left or right, but if not available, add new node */
452                                 if (ab->start < prev->vec[1][0]) 
453                                         abnp = &ab->right;
454                                 else
455                                         abnp = &ab->left;
456                                         
457                                 /* if this does not exist, add a new node, otherwise continue... */
458                                 if (*abnp == NULL) {
459                                         /* add a new node representing this, and attach it to the relevant place */
460                                         new_ab = bezts_to_new_actkeyblock(prev, beztn);
461                                         new_ab->parent = ab;
462                                         *abnp = new_ab;
463                                         break;
464                                 }
465                                 else
466                                         abn = *abnp;
467                         }
468                 }
469         }
470         
471         /* now, balance the tree taking into account this newly added node */
472         BLI_dlrbTree_insert(blocks, (DLRBT_Node *)new_ab);
473 }
474
475 /* --------- */
476
477 /* Handle the 'touched' status of ActKeyColumn tree nodes */
478 static void set_touched_actkeycolumn(ActKeyColumn *ak)
479 {
480         /* sanity check */
481         if (ak == NULL)
482                 return;
483                 
484         /* deal with self first */
485         if (ak->modified) {
486                 ak->modified = 0;
487                 ak->totcurve++;
488         }
489         
490         /* children */
491         set_touched_actkeycolumn(ak->left);
492         set_touched_actkeycolumn(ak->right);
493 }
494
495 /* Handle the 'touched' status of ActKeyBlock tree nodes */
496 static void set_touched_actkeyblock(ActKeyBlock *ab)
497 {
498         /* sanity check */
499         if (ab == NULL)
500                 return;
501                 
502         /* deal with self first */
503         if (ab->modified) {
504                 ab->modified = 0;
505                 ab->totcurve++;
506         }
507         
508         /* children */
509         set_touched_actkeyblock(ab->left);
510         set_touched_actkeyblock(ab->right);
511 }
512
513 /* --------- */
514
515 /* Checks if ActKeyBlock should exist... */
516 short actkeyblock_is_valid(ActKeyBlock *ab, DLRBT_Tree *keys)
517 {
518         ActKeyColumn *ak;
519         short startCurves, endCurves, totCurves;
520         
521         /* check that block is valid */
522         if (ab == NULL)
523                 return 0;
524         
525         /* find out how many curves occur at each keyframe */
526         ak = (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->start);
527         startCurves = (ak) ? ak->totcurve : 0;
528         
529         ak = (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->end);
530         endCurves = (ak) ? ak->totcurve : 0;
531         
532         /* only draw keyblock if it appears in at all of the keyframes at lowest end */
533         if (!startCurves && !endCurves) 
534                 return 0;
535         
536         totCurves = (startCurves > endCurves) ? endCurves : startCurves;
537         return (ab->totcurve >= totCurves);
538 }
539
540 /* *************************** Keyframe Drawing *************************** */
541
542 /* coordinates for diamond shape */
543 static const float _unit_diamond_shape[4][2] = {
544         {0.0f, 1.0f},   /* top vert */
545         {1.0f, 0.0f},   /* mid-right */
546         {0.0f, -1.0f},  /* bottom vert */
547         {-1.0f, 0.0f}   /* mid-left */
548 }; 
549
550 /* draw a simple diamond shape with OpenGL */
551 void draw_keyframe_shape(float x, float y, float xscale, float hsize, short sel, short key_type, short mode, float alpha)
552 {
553         static GLuint displist1 = 0;
554         static GLuint displist2 = 0;
555         
556         /* initialize 2 display lists for diamond shape - one empty, one filled */
557         if (displist1 == 0) {
558                 displist1 = glGenLists(1);
559                 glNewList(displist1, GL_COMPILE);
560                         
561                 glBegin(GL_LINE_LOOP);
562                 glVertex2fv(_unit_diamond_shape[0]);
563                 glVertex2fv(_unit_diamond_shape[1]);
564                 glVertex2fv(_unit_diamond_shape[2]);
565                 glVertex2fv(_unit_diamond_shape[3]);
566                 glEnd();
567
568                 glEndList();
569         }
570         if (displist2 == 0) {
571                 displist2 = glGenLists(1);
572                 glNewList(displist2, GL_COMPILE);
573                         
574                 glBegin(GL_QUADS);
575                 glVertex2fv(_unit_diamond_shape[0]);
576                 glVertex2fv(_unit_diamond_shape[1]);
577                 glVertex2fv(_unit_diamond_shape[2]);
578                 glVertex2fv(_unit_diamond_shape[3]);
579                 glEnd();
580
581                 glEndList();
582         }
583         
584         /* tweak size of keyframe shape according to type of keyframe 
585          * - 'proper' keyframes have key_type = 0, so get drawn at full size
586          */
587         hsize -= 0.5f * key_type;
588         
589         /* adjust view transform before starting */
590         glTranslatef(x, y, 0.0f);
591         glScalef(1.0f / xscale * hsize, hsize, 1.0f);
592         
593         /* anti-aliased lines for more consistent appearance */
594         glEnable(GL_LINE_SMOOTH);
595         
596         /* draw! */
597         if (ELEM(mode, KEYFRAME_SHAPE_INSIDE, KEYFRAME_SHAPE_BOTH)) {
598                 /* interior - hardcoded colors (for selected and unselected only) */
599                 switch (key_type) {
600                         case BEZT_KEYTYPE_BREAKDOWN: /* bluish frames for now */
601                         {
602                                 if (sel) glColor4f(0.33f, 0.75f, 0.93f, alpha);
603                                 else glColor4f(0.70f, 0.86f, 0.91f, alpha);
604                         }
605                         break;
606                                 
607                         case BEZT_KEYTYPE_EXTREME: /* redish frames for now */
608                         {
609                                 if (sel) glColor4f(0.95f, 0.5f, 0.5f, alpha);
610                                 else glColor4f(0.91f, 0.70f, 0.80f, alpha);
611                         }
612                         break;
613                                 
614                         case BEZT_KEYTYPE_JITTER: /* greenish frames for now? */
615                         {
616                                 if (sel) glColor4f(0.38f, 0.75f, 0.26f, alpha);
617                                 else glColor4f(0.58f, 0.90f, 0.46f, alpha);
618                         }
619                         break;
620                                 
621                         case BEZT_KEYTYPE_KEYFRAME: /* traditional yellowish frames for now */
622                         default:
623                         {
624                                 if (sel) UI_ThemeColorShadeAlpha(TH_STRIP_SELECT, 50, -255 * (1.0f - alpha));
625                                 else glColor4f(0.91f, 0.91f, 0.91f, alpha);
626                         }
627                         break;
628                 }
629                 
630                 glCallList(displist2);
631         }
632         
633         if (ELEM(mode, KEYFRAME_SHAPE_FRAME, KEYFRAME_SHAPE_BOTH)) {
634                 /* exterior - black frame */
635                 glColor4f(0.0f, 0.0f, 0.0f, alpha);
636                 
637                 glCallList(displist1);
638         }
639         
640         glDisable(GL_LINE_SMOOTH);
641         
642         /* restore view transform */
643         glScalef(xscale / hsize, 1.0f / hsize, 1.0f);
644         glTranslatef(-x, -y, 0.0f);
645 }
646
647 static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, float ypos, short channelLocked)
648 {
649         ActKeyColumn *ak;
650         ActKeyBlock *ab;
651         float xscale;
652         float iconsize = U.widget_unit / 4.0f;
653         glEnable(GL_BLEND);
654         
655         /* get View2D scaling factor */
656         UI_view2d_getscale(v2d, &xscale, NULL);
657         
658         /* draw keyblocks */
659         if (blocks) {
660                 for (ab = blocks->first; ab; ab = ab->next) {
661                         if (actkeyblock_is_valid(ab, keys)) {
662                                 /* draw block */
663                                 if (ab->sel)
664                                         UI_ThemeColor4(TH_STRIP_SELECT);
665                                 else
666                                         UI_ThemeColor4(TH_STRIP);
667                                 
668                                 glRectf(ab->start, ypos - iconsize, ab->end, ypos + iconsize);
669                         }
670                 }
671         }
672         
673         /* draw keys */
674         if (keys) {
675                 /* locked channels are less strongly shown, as feedback for locked channels in DopeSheet */
676                 /* TODO: allow this opacity factor to be themed? */
677                 float kalpha = (channelLocked) ? 0.25f : 1.0f;
678                 
679                 for (ak = keys->first; ak; ak = ak->next) {
680                         /* optimization: if keyframe doesn't appear within 5 units (screenspace) in visible area, don't draw
681                          *      - this might give some improvements, since we current have to flip between view/region matrices
682                          */
683                         if (IN_RANGE_INCL(ak->cfra, v2d->cur.xmin, v2d->cur.xmax) == 0)
684                                 continue;
685                         
686                         /* draw using OpenGL - uglier but faster */
687                         /* NOTE1: a previous version of this didn't work nice for some intel cards
688                          * NOTE2: if we wanted to go back to icons, these are  icon = (ak->sel & SELECT) ? ICON_SPACE2 : ICON_SPACE3; */
689                         draw_keyframe_shape(ak->cfra, ypos, xscale, iconsize, (ak->sel & SELECT), ak->key_type, KEYFRAME_SHAPE_BOTH, kalpha);
690                 }
691         }
692
693         glDisable(GL_BLEND);
694 }
695
696 /* *************************** Channel Drawing Funcs *************************** */
697
698 void draw_summary_channel(View2D *v2d, bAnimContext *ac, float ypos)
699 {
700         DLRBT_Tree keys, blocks;
701         
702         BLI_dlrbTree_init(&keys);
703         BLI_dlrbTree_init(&blocks);
704         
705         summary_to_keylist(ac, &keys, &blocks);
706         
707         BLI_dlrbTree_linkedlist_sync(&keys);
708         BLI_dlrbTree_linkedlist_sync(&blocks);
709         
710         draw_keylist(v2d, &keys, &blocks, ypos, 0);
711         
712         BLI_dlrbTree_free(&keys);
713         BLI_dlrbTree_free(&blocks);
714 }
715
716 void draw_scene_channel(View2D *v2d, bDopeSheet *ads, Scene *sce, float ypos)
717 {
718         DLRBT_Tree keys, blocks;
719         
720         BLI_dlrbTree_init(&keys);
721         BLI_dlrbTree_init(&blocks);
722         
723         scene_to_keylist(ads, sce, &keys, &blocks);
724         
725         BLI_dlrbTree_linkedlist_sync(&keys);
726         BLI_dlrbTree_linkedlist_sync(&blocks);
727         
728         draw_keylist(v2d, &keys, &blocks, ypos, 0);
729         
730         BLI_dlrbTree_free(&keys);
731         BLI_dlrbTree_free(&blocks);
732 }
733
734 void draw_object_channel(View2D *v2d, bDopeSheet *ads, Object *ob, float ypos)
735 {
736         DLRBT_Tree keys, blocks;
737         
738         BLI_dlrbTree_init(&keys);
739         BLI_dlrbTree_init(&blocks);
740         
741         ob_to_keylist(ads, ob, &keys, &blocks);
742         
743         BLI_dlrbTree_linkedlist_sync(&keys);
744         BLI_dlrbTree_linkedlist_sync(&blocks);
745         
746         draw_keylist(v2d, &keys, &blocks, ypos, 0);
747         
748         BLI_dlrbTree_free(&keys);
749         BLI_dlrbTree_free(&blocks);
750 }
751
752 void draw_fcurve_channel(View2D *v2d, AnimData *adt, FCurve *fcu, float ypos)
753 {
754         DLRBT_Tree keys, blocks;
755         
756         short locked = (fcu->flag & FCURVE_PROTECTED) ||
757                        ((fcu->grp) && (fcu->grp->flag & AGRP_PROTECTED)) ||
758                        ((adt && adt->action) && (adt->action->id.lib));
759         
760         BLI_dlrbTree_init(&keys);
761         BLI_dlrbTree_init(&blocks);
762         
763         fcurve_to_keylist(adt, fcu, &keys, &blocks);
764         
765         BLI_dlrbTree_linkedlist_sync(&keys);
766         BLI_dlrbTree_linkedlist_sync(&blocks);
767         
768         draw_keylist(v2d, &keys, &blocks, ypos, locked);
769         
770         BLI_dlrbTree_free(&keys);
771         BLI_dlrbTree_free(&blocks);
772 }
773
774 void draw_agroup_channel(View2D *v2d, AnimData *adt, bActionGroup *agrp, float ypos)
775 {
776         DLRBT_Tree keys, blocks;
777         
778         short locked = (agrp->flag & AGRP_PROTECTED) ||
779                        ((adt && adt->action) && (adt->action->id.lib));
780         
781         BLI_dlrbTree_init(&keys);
782         BLI_dlrbTree_init(&blocks);
783         
784         agroup_to_keylist(adt, agrp, &keys, &blocks);
785         
786         BLI_dlrbTree_linkedlist_sync(&keys);
787         BLI_dlrbTree_linkedlist_sync(&blocks);
788         
789         draw_keylist(v2d, &keys, &blocks, ypos, locked);
790         
791         BLI_dlrbTree_free(&keys);
792         BLI_dlrbTree_free(&blocks);
793 }
794
795 void draw_action_channel(View2D *v2d, AnimData *adt, bAction *act, float ypos)
796 {
797         DLRBT_Tree keys, blocks;
798         
799         short locked = (act && act->id.lib != 0);
800         
801         BLI_dlrbTree_init(&keys);
802         BLI_dlrbTree_init(&blocks);
803         
804         action_to_keylist(adt, act, &keys, &blocks);
805         
806         BLI_dlrbTree_linkedlist_sync(&keys);
807         BLI_dlrbTree_linkedlist_sync(&blocks);
808         
809         draw_keylist(v2d, &keys, &blocks, ypos, locked);
810         
811         BLI_dlrbTree_free(&keys);
812         BLI_dlrbTree_free(&blocks);
813 }
814
815 void draw_gpl_channel(View2D *v2d, bDopeSheet *ads, bGPDlayer *gpl, float ypos)
816 {
817         DLRBT_Tree keys;
818         
819         BLI_dlrbTree_init(&keys);
820         
821         gpl_to_keylist(ads, gpl, &keys);
822         
823         BLI_dlrbTree_linkedlist_sync(&keys);
824         
825         draw_keylist(v2d, &keys, NULL, ypos, (gpl->flag & GP_LAYER_LOCKED));
826         
827         BLI_dlrbTree_free(&keys);
828 }
829
830 void draw_masklay_channel(View2D *v2d, bDopeSheet *ads, MaskLayer *masklay, float ypos)
831 {
832         DLRBT_Tree keys;
833
834         BLI_dlrbTree_init(&keys);
835
836         mask_to_keylist(ads, masklay, &keys);
837
838         BLI_dlrbTree_linkedlist_sync(&keys);
839
840         draw_keylist(v2d, &keys, NULL, ypos, (masklay->flag & MASK_LAYERFLAG_LOCKED));
841
842         BLI_dlrbTree_free(&keys);
843 }
844
845 /* *************************** Keyframe List Conversions *************************** */
846
847 void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, DLRBT_Tree *blocks)
848 {
849         if (ac) {
850                 ListBase anim_data = {NULL, NULL};
851                 bAnimListElem *ale;
852                 int filter;
853                 
854                 /* get F-Curves to take keyframes from */
855                 filter = ANIMFILTER_DATA_VISIBLE;
856                 ANIM_animdata_filter(ac, &anim_data, filter, ac->data, ac->datatype);
857                 
858                 /* loop through each F-Curve, grabbing the keyframes */
859                 for (ale = anim_data.first; ale; ale = ale->next) {
860
861                         /* Why not use all #eAnim_KeyType here?
862                          * All of the other key types are actually "summaries" themselves, and will just end up duplicating stuff
863                          * that comes up through standard filtering of just F-Curves.
864                          * Given the way that these work, there isn't really any benefit at all from including them. - Aligorith */
865
866                         switch (ale->datatype) {
867                                 case ALE_FCURVE:
868                                         fcurve_to_keylist(ale->adt, ale->data, keys, blocks);
869                                         break;
870                                 case ALE_MASKLAY:
871                                         mask_to_keylist(ac->ads, ale->data, keys);
872                                         break;
873                                 case ALE_GPFRAME:
874                                         gpl_to_keylist(ac->ads, ale->data, keys);
875                                         break;
876                                 default:
877                                         // printf("%s: datatype %d unhandled\n", __func__, ale->datatype);
878                                         break;
879                         }
880                 }
881
882                 BLI_freelistN(&anim_data);
883         }
884 }
885
886 void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree *blocks)
887 {
888         bAnimContext ac = {NULL};
889         ListBase anim_data = {NULL, NULL};
890         bAnimListElem *ale;
891         int filter;
892         
893         bAnimListElem dummychan = {0};
894         
895         if (sce == NULL)
896                 return;
897         
898         /* create a dummy wrapper data to work with */
899         dummychan.type = ANIMTYPE_SCENE;
900         dummychan.data = sce;
901         dummychan.id = &sce->id;
902         dummychan.adt = sce->adt;
903         
904         ac.ads = ads;
905         ac.data = &dummychan;
906         ac.datatype = ANIMCONT_CHANNEL;
907         
908         /* get F-Curves to take keyframes from */
909         filter = ANIMFILTER_DATA_VISIBLE; // curves only
910         ANIM_animdata_filter(&ac, &anim_data, filter, ac.data, ac.datatype);
911         
912         /* loop through each F-Curve, grabbing the keyframes */
913         for (ale = anim_data.first; ale; ale = ale->next)
914                 fcurve_to_keylist(ale->adt, ale->data, keys, blocks);
915         
916         BLI_freelistN(&anim_data);
917 }
918
919 void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, DLRBT_Tree *blocks)
920 {       
921         bAnimContext ac = {NULL};
922         ListBase anim_data = {NULL, NULL};
923         bAnimListElem *ale;
924         int filter;
925         
926         bAnimListElem dummychan = {0};
927         Base dummybase = {0};
928         
929         if (ob == NULL)
930                 return;
931         
932         /* create a dummy wrapper data to work with */
933         dummybase.object = ob;
934         
935         dummychan.type = ANIMTYPE_OBJECT;
936         dummychan.data = &dummybase;
937         dummychan.id = &ob->id;
938         dummychan.adt = ob->adt;
939         
940         ac.ads = ads;
941         ac.data = &dummychan;
942         ac.datatype = ANIMCONT_CHANNEL;
943         
944         /* get F-Curves to take keyframes from */
945         filter = ANIMFILTER_DATA_VISIBLE; // curves only
946         ANIM_animdata_filter(&ac, &anim_data, filter, ac.data, ac.datatype);
947         
948         /* loop through each F-Curve, grabbing the keyframes */
949         for (ale = anim_data.first; ale; ale = ale->next)
950                 fcurve_to_keylist(ale->adt, ale->data, keys, blocks);
951         
952         BLI_freelistN(&anim_data);
953 }
954
955 void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree *blocks)
956 {
957         DLRBT_Tree *beztTree = NULL;
958         BezTriple *bezt;
959         unsigned int v;
960
961         if (fcu && fcu->totvert && fcu->bezt) {
962                 /* apply NLA-mapping (if applicable) */
963                 if (adt)
964                         ANIM_nla_mapping_apply_fcurve(adt, fcu, 0, 0);
965                 
966                 /* if getting long keyframes too, grab the BezTriples in a BST for 
967                  * accelerated searching...
968                  */
969                 if (blocks) {
970                         /* init new tree */
971                         beztTree = BLI_dlrbTree_new();
972                         
973                         /* populate tree with the BezTriples */
974                         for (v = 0, bezt = fcu->bezt; v < fcu->totvert; v++, bezt++)
975                                 BLI_dlrbTree_add(beztTree, compare_abk_bezt, nalloc_abk_bezt, nupdate_abk_bezt, bezt);
976                         
977                         /* make sure that it is suitable for linked-list searching too */
978                         BLI_dlrbTree_linkedlist_sync(beztTree);
979                 }
980                 
981                 /* loop through beztriples, making ActKeysColumns and ActKeyBlocks */
982                 for (v = 0, bezt = fcu->bezt; v < fcu->totvert; v++, bezt++) {
983                         add_bezt_to_keycolumns_list(keys, bezt);
984                         if (blocks) add_bezt_to_keyblocks_list(blocks, beztTree, bezt);
985                 }
986                 
987                 /* update the number of curves that elements have appeared in  */
988                 if (keys)
989                         set_touched_actkeycolumn(keys->root);
990                 if (blocks)
991                         set_touched_actkeyblock(blocks->root);
992                         
993                 /* free temp data for building long keyframes */
994                 if (blocks && beztTree) {
995                         BLI_dlrbTree_free(beztTree);
996                         MEM_freeN(beztTree);
997                 }
998                 
999                 /* unapply NLA-mapping if applicable */
1000                 if (adt)
1001                         ANIM_nla_mapping_apply_fcurve(adt, fcu, 1, 0);
1002         }
1003 }
1004
1005 void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, DLRBT_Tree *keys, DLRBT_Tree *blocks)
1006 {
1007         FCurve *fcu;
1008
1009         if (agrp) {
1010                 /* loop through F-Curves */
1011                 for (fcu = agrp->channels.first; fcu && fcu->grp == agrp; fcu = fcu->next) {
1012                         fcurve_to_keylist(adt, fcu, keys, blocks);
1013                 }
1014         }
1015 }
1016
1017 void action_to_keylist(AnimData *adt, bAction *act, DLRBT_Tree *keys, DLRBT_Tree *blocks)
1018 {
1019         FCurve *fcu;
1020
1021         if (act) {
1022                 /* loop through F-Curves */
1023                 for (fcu = act->curves.first; fcu; fcu = fcu->next) {
1024                         fcurve_to_keylist(adt, fcu, keys, blocks);
1025                 }
1026         }
1027 }
1028
1029
1030 void gpl_to_keylist(bDopeSheet *UNUSED(ads), bGPDlayer *gpl, DLRBT_Tree *keys)
1031 {
1032         bGPDframe *gpf;
1033         
1034         if (gpl && keys) {
1035                 /* although the frames should already be in an ordered list, they are not suitable for displaying yet */
1036                 for (gpf = gpl->frames.first; gpf; gpf = gpf->next)
1037                         add_gpframe_to_keycolumns_list(keys, gpf);
1038         }
1039 }
1040
1041 void mask_to_keylist(bDopeSheet *UNUSED(ads), MaskLayer *masklay, DLRBT_Tree *keys)
1042 {
1043         MaskLayerShape *masklay_shape;
1044
1045         if (masklay && keys) {
1046                 for (masklay_shape = masklay->splines_shapes.first;
1047                      masklay_shape;
1048                      masklay_shape = masklay_shape->next)
1049                 {
1050                         add_masklay_to_keycolumns_list(keys, masklay_shape);
1051                 }
1052         }
1053 }
1054