86b438846c93d144d7aaa1bfcba33a4c4419c9ec
[blender.git] / source / blender / editors / animation / keyframes_draw.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup edanimation
22  */
23
24 /* System includes ----------------------------------------------------- */
25
26 #include <math.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <float.h>
30
31 #include "MEM_guardedalloc.h"
32
33 #include "BLI_dlrbTree.h"
34 #include "BLI_math.h"
35 #include "BLI_utildefines.h"
36 #include "BLI_rect.h"
37
38 #include "DNA_anim_types.h"
39 #include "DNA_cachefile_types.h"
40 #include "DNA_object_types.h"
41 #include "DNA_scene_types.h"
42 #include "DNA_gpencil_types.h"
43 #include "DNA_brush_types.h"
44 #include "DNA_mask_types.h"
45
46 #include "BKE_fcurve.h"
47
48 #include "GPU_draw.h"
49 #include "GPU_immediate.h"
50 #include "GPU_state.h"
51
52 #include "UI_resources.h"
53 #include "UI_view2d.h"
54
55 #include "ED_anim_api.h"
56 #include "ED_keyframes_draw.h"
57
58 /* *************************** Keyframe Processing *************************** */
59
60 /* ActKeyColumns (Keyframe Columns) ------------------------------------------ */
61
62 BLI_INLINE bool is_cfra_eq(float a, float b)
63 {
64   return IS_EQT(a, b, BEZT_BINARYSEARCH_THRESH);
65 }
66
67 BLI_INLINE bool is_cfra_lt(float a, float b)
68 {
69   return (b - a) > BEZT_BINARYSEARCH_THRESH;
70 }
71
72 /* Comparator callback used for ActKeyColumns and cframe float-value pointer */
73 /* NOTE: this is exported to other modules that use the ActKeyColumns for finding keyframes */
74 short compare_ak_cfraPtr(void *node, void *data)
75 {
76   ActKeyColumn *ak = (ActKeyColumn *)node;
77   const float *cframe = data;
78   float val = *cframe;
79
80   if (is_cfra_eq(val, ak->cfra))
81     return 0;
82
83   if (val < ak->cfra)
84     return -1;
85   else
86     return 1;
87 }
88
89 /* --------------- */
90
91 /* Set of references to three logically adjacent keys. */
92 typedef struct BezTripleChain {
93   /* Current keyframe. */
94   BezTriple *cur;
95
96   /* Logical neighbors. May be NULL. */
97   BezTriple *prev, *next;
98 } BezTripleChain;
99
100 /* Categorize the interpolation & handle type of the keyframe. */
101 static eKeyframeHandleDrawOpts bezt_handle_type(BezTriple *bezt)
102 {
103   if (bezt->h1 == HD_AUTO_ANIM && bezt->h2 == HD_AUTO_ANIM) {
104     return KEYFRAME_HANDLE_AUTO_CLAMP;
105   }
106   else if (ELEM(bezt->h1, HD_AUTO_ANIM, HD_AUTO) && ELEM(bezt->h2, HD_AUTO_ANIM, HD_AUTO)) {
107     return KEYFRAME_HANDLE_AUTO;
108   }
109   else if (bezt->h1 == HD_VECT && bezt->h2 == HD_VECT) {
110     return KEYFRAME_HANDLE_VECTOR;
111   }
112   else if (ELEM(HD_FREE, bezt->h1, bezt->h2)) {
113     return KEYFRAME_HANDLE_FREE;
114   }
115   else {
116     return KEYFRAME_HANDLE_ALIGNED;
117   }
118 }
119
120 /* Determine if the keyframe is an extreme by comparing with neighbors.
121  * Ends of fixed-value sections and of the whole curve are also marked.
122  */
123 static eKeyframeExtremeDrawOpts bezt_extreme_type(BezTripleChain *chain)
124 {
125   if (chain->prev == NULL && chain->next == NULL) {
126     return KEYFRAME_EXTREME_NONE;
127   }
128
129   /* Keyframe values for the current one and neighbors. */
130   float cur_y = chain->cur->vec[1][1];
131   float prev_y = cur_y, next_y = cur_y;
132
133   if (chain->prev && !IS_EQF(cur_y, chain->prev->vec[1][1])) {
134     prev_y = chain->prev->vec[1][1];
135   }
136   if (chain->next && !IS_EQF(cur_y, chain->next->vec[1][1])) {
137     next_y = chain->next->vec[1][1];
138   }
139
140   /* Static hold. */
141   if (prev_y == cur_y && next_y == cur_y) {
142     return KEYFRAME_EXTREME_FLAT;
143   }
144
145   /* Middle of an incline. */
146   if ((prev_y < cur_y && next_y > cur_y) || (prev_y > cur_y && next_y < cur_y)) {
147     return KEYFRAME_EXTREME_NONE;
148   }
149
150   /* Bezier handle values for the overshoot check. */
151   bool l_bezier = chain->prev && chain->prev->ipo == BEZT_IPO_BEZ;
152   bool r_bezier = chain->next && chain->cur->ipo == BEZT_IPO_BEZ;
153   float handle_l = l_bezier ? chain->cur->vec[0][1] : cur_y;
154   float handle_r = r_bezier ? chain->cur->vec[2][1] : cur_y;
155
156   /* Detect extremes. One of the neighbors is allowed to be equal to current. */
157   if (prev_y < cur_y || next_y < cur_y) {
158     bool is_overshoot = (handle_l > cur_y || handle_r > cur_y);
159
160     return KEYFRAME_EXTREME_MAX | (is_overshoot ? KEYFRAME_EXTREME_MIXED : 0);
161   }
162
163   if (prev_y > cur_y || next_y > cur_y) {
164     bool is_overshoot = (handle_l < cur_y || handle_r < cur_y);
165
166     return KEYFRAME_EXTREME_MIN | (is_overshoot ? KEYFRAME_EXTREME_MIXED : 0);
167   }
168
169   return KEYFRAME_EXTREME_NONE;
170 }
171
172 /* Comparator callback used for ActKeyColumns and BezTripleChain */
173 static short compare_ak_bezt(void *node, void *data)
174 {
175   BezTripleChain *chain = data;
176
177   return compare_ak_cfraPtr(node, &chain->cur->vec[1][0]);
178 }
179
180 /* New node callback used for building ActKeyColumns from BezTripleChain */
181 static DLRBT_Node *nalloc_ak_bezt(void *data)
182 {
183   ActKeyColumn *ak = MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn");
184   BezTripleChain *chain = data;
185   BezTriple *bezt = chain->cur;
186
187   /* store settings based on state of BezTriple */
188   ak->cfra = bezt->vec[1][0];
189   ak->sel = BEZT_ISSEL_ANY(bezt) ? SELECT : 0;
190   ak->key_type = BEZKEYTYPE(bezt);
191   ak->handle_type = bezt_handle_type(bezt);
192   ak->extreme_type = bezt_extreme_type(chain);
193
194   /* count keyframes in this column */
195   ak->totkey = 1;
196
197   return (DLRBT_Node *)ak;
198 }
199
200 /* Node updater callback used for building ActKeyColumns from BezTripleChain */
201 static void nupdate_ak_bezt(void *node, void *data)
202 {
203   ActKeyColumn *ak = node;
204   BezTripleChain *chain = data;
205   BezTriple *bezt = chain->cur;
206
207   /* set selection status and 'touched' status */
208   if (BEZT_ISSEL_ANY(bezt))
209     ak->sel = SELECT;
210
211   /* count keyframes in this column */
212   ak->totkey++;
213
214   /* For keyframe type, 'proper' keyframes have priority over breakdowns
215    * (and other types for now). */
216   if (BEZKEYTYPE(bezt) == BEZT_KEYTYPE_KEYFRAME)
217     ak->key_type = BEZT_KEYTYPE_KEYFRAME;
218
219   /* For interpolation type, select the highest value (enum is sorted). */
220   ak->handle_type = MAX2(ak->handle_type, bezt_handle_type(bezt));
221
222   /* For extremes, detect when combining different states. */
223   char new_extreme = bezt_extreme_type(chain);
224
225   if (new_extreme != ak->extreme_type) {
226     /* Replace the flat status without adding mixed. */
227     if (ak->extreme_type == KEYFRAME_EXTREME_FLAT) {
228       ak->extreme_type = new_extreme;
229     }
230     else if (new_extreme != KEYFRAME_EXTREME_FLAT) {
231       ak->extreme_type |= (new_extreme | KEYFRAME_EXTREME_MIXED);
232     }
233   }
234 }
235
236 /* ......... */
237
238 /* Comparator callback used for ActKeyColumns and GPencil frame */
239 static short compare_ak_gpframe(void *node, void *data)
240 {
241   bGPDframe *gpf = (bGPDframe *)data;
242
243   float frame = gpf->framenum;
244   return compare_ak_cfraPtr(node, &frame);
245 }
246
247 /* New node callback used for building ActKeyColumns from GPencil frames */
248 static DLRBT_Node *nalloc_ak_gpframe(void *data)
249 {
250   ActKeyColumn *ak = MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumnGPF");
251   bGPDframe *gpf = (bGPDframe *)data;
252
253   /* store settings based on state of BezTriple */
254   ak->cfra = gpf->framenum;
255   ak->sel = (gpf->flag & GP_FRAME_SELECT) ? SELECT : 0;
256   ak->key_type = gpf->key_type;
257
258   /* count keyframes in this column */
259   ak->totkey = 1;
260
261   return (DLRBT_Node *)ak;
262 }
263
264 /* Node updater callback used for building ActKeyColumns from GPencil frames */
265 static void nupdate_ak_gpframe(void *node, void *data)
266 {
267   ActKeyColumn *ak = (ActKeyColumn *)node;
268   bGPDframe *gpf = (bGPDframe *)data;
269
270   /* set selection status and 'touched' status */
271   if (gpf->flag & GP_FRAME_SELECT)
272     ak->sel = SELECT;
273
274   /* count keyframes in this column */
275   ak->totkey++;
276
277   /* for keyframe type, 'proper' keyframes have priority over breakdowns
278    * (and other types for now). */
279   if (gpf->key_type == BEZT_KEYTYPE_KEYFRAME)
280     ak->key_type = BEZT_KEYTYPE_KEYFRAME;
281 }
282
283 /* ......... */
284
285 /* Comparator callback used for ActKeyColumns and GPencil frame */
286 static short compare_ak_masklayshape(void *node, void *data)
287 {
288   MaskLayerShape *masklay_shape = (MaskLayerShape *)data;
289
290   float frame = masklay_shape->frame;
291   return compare_ak_cfraPtr(node, &frame);
292 }
293
294 /* New node callback used for building ActKeyColumns from GPencil frames */
295 static DLRBT_Node *nalloc_ak_masklayshape(void *data)
296 {
297   ActKeyColumn *ak = MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumnGPF");
298   MaskLayerShape *masklay_shape = (MaskLayerShape *)data;
299
300   /* store settings based on state of BezTriple */
301   ak->cfra = masklay_shape->frame;
302   ak->sel = (masklay_shape->flag & MASK_SHAPE_SELECT) ? SELECT : 0;
303
304   /* count keyframes in this column */
305   ak->totkey = 1;
306
307   return (DLRBT_Node *)ak;
308 }
309
310 /* Node updater callback used for building ActKeyColumns from GPencil frames */
311 static void nupdate_ak_masklayshape(void *node, void *data)
312 {
313   ActKeyColumn *ak = (ActKeyColumn *)node;
314   MaskLayerShape *masklay_shape = (MaskLayerShape *)data;
315
316   /* set selection status and 'touched' status */
317   if (masklay_shape->flag & MASK_SHAPE_SELECT)
318     ak->sel = SELECT;
319
320   /* count keyframes in this column */
321   ak->totkey++;
322 }
323
324 /* --------------- */
325
326 /* Add the given BezTriple to the given 'list' of Keyframes */
327 static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTripleChain *bezt)
328 {
329   if (ELEM(NULL, keys, bezt))
330     return;
331   else
332     BLI_dlrbTree_add(keys, compare_ak_bezt, nalloc_ak_bezt, nupdate_ak_bezt, bezt);
333 }
334
335 /* Add the given GPencil Frame to the given 'list' of Keyframes */
336 static void add_gpframe_to_keycolumns_list(DLRBT_Tree *keys, bGPDframe *gpf)
337 {
338   if (ELEM(NULL, keys, gpf))
339     return;
340   else
341     BLI_dlrbTree_add(keys, compare_ak_gpframe, nalloc_ak_gpframe, nupdate_ak_gpframe, gpf);
342 }
343
344 /* Add the given MaskLayerShape Frame to the given 'list' of Keyframes */
345 static void add_masklay_to_keycolumns_list(DLRBT_Tree *keys, MaskLayerShape *masklay_shape)
346 {
347   if (ELEM(NULL, keys, masklay_shape))
348     return;
349   else
350     BLI_dlrbTree_add(keys,
351                      compare_ak_masklayshape,
352                      nalloc_ak_masklayshape,
353                      nupdate_ak_masklayshape,
354                      masklay_shape);
355 }
356
357 /* ActKeyBlocks (Long Keyframes) ------------------------------------------ */
358
359 static const ActKeyBlockInfo dummy_keyblock = {0};
360
361 static void compute_keyblock_data(ActKeyBlockInfo *info, BezTriple *prev, BezTriple *beztn)
362 {
363   memset(info, 0, sizeof(ActKeyBlockInfo));
364
365   if (BEZKEYTYPE(beztn) == BEZT_KEYTYPE_MOVEHOLD) {
366     /* Animator tagged a "moving hold"
367      *   - Previous key must also be tagged as a moving hold, otherwise
368      *     we're just dealing with the first of a pair, and we don't
369      *     want to be creating any phantom holds...
370      */
371     if (BEZKEYTYPE(prev) == BEZT_KEYTYPE_MOVEHOLD) {
372       info->flag |= ACTKEYBLOCK_FLAG_MOVING_HOLD | ACTKEYBLOCK_FLAG_ANY_HOLD;
373     }
374   }
375
376   /* Check for same values...
377    *  - Handles must have same central value as each other
378    *  - Handles which control that section of the curve must be constant
379    */
380   if (IS_EQF(beztn->vec[1][1], prev->vec[1][1])) {
381     bool hold;
382
383     /* Only check handles in case of actual bezier interpolation. */
384     if (prev->ipo == BEZT_IPO_BEZ) {
385       hold = IS_EQF(beztn->vec[1][1], beztn->vec[0][1]) &&
386              IS_EQF(prev->vec[1][1], prev->vec[2][1]);
387     }
388     /* This interpolation type induces movement even between identical keys. */
389     else {
390       hold = !ELEM(prev->ipo, BEZT_IPO_ELASTIC);
391     }
392
393     if (hold) {
394       info->flag |= ACTKEYBLOCK_FLAG_STATIC_HOLD | ACTKEYBLOCK_FLAG_ANY_HOLD;
395     }
396   }
397
398   /* Remember non-bezier interpolation info. */
399   if (prev->ipo != BEZT_IPO_BEZ) {
400     info->flag |= ACTKEYBLOCK_FLAG_NON_BEZIER;
401   }
402
403   info->sel = BEZT_ISSEL_ANY(prev) || BEZT_ISSEL_ANY(beztn);
404 }
405
406 static void add_keyblock_info(ActKeyColumn *col, const ActKeyBlockInfo *block)
407 {
408   /* New curve and block. */
409   if (col->totcurve <= 1 && col->totblock == 0) {
410     memcpy(&col->block, block, sizeof(ActKeyBlockInfo));
411   }
412   /* Existing curve. */
413   else {
414     col->block.conflict |= (col->block.flag ^ block->flag);
415     col->block.flag |= block->flag;
416     col->block.sel |= block->sel;
417   }
418
419   if (block->flag) {
420     col->totblock++;
421   }
422 }
423
424 static void add_bezt_to_keyblocks_list(DLRBT_Tree *keys, BezTriple *bezt, int bezt_len)
425 {
426   ActKeyColumn *col = keys->first;
427
428   if (bezt && bezt_len >= 2) {
429     ActKeyBlockInfo block;
430
431     /* Find the first key column while inserting dummy blocks. */
432     for (; col != NULL && is_cfra_lt(col->cfra, bezt[0].vec[1][0]); col = col->next) {
433       add_keyblock_info(col, &dummy_keyblock);
434     }
435
436     BLI_assert(col != NULL);
437
438     /* Insert real blocks. */
439     for (int v = 1; col != NULL && v < bezt_len; v++, bezt++) {
440       /* Wrong order of bezier keys: resync position. */
441       if (is_cfra_lt(bezt[1].vec[1][0], bezt[0].vec[1][0])) {
442         /* Backtrack to find the right location. */
443         if (is_cfra_lt(bezt[1].vec[1][0], col->cfra)) {
444           ActKeyColumn *newcol = (ActKeyColumn *)BLI_dlrbTree_search_exact(
445               keys, compare_ak_cfraPtr, &bezt[1].vec[1][0]);
446
447           if (newcol != NULL) {
448             col = newcol;
449
450             /* The previous keyblock is garbage too. */
451             if (col->prev != NULL) {
452               add_keyblock_info(col->prev, &dummy_keyblock);
453             }
454           }
455           else {
456             BLI_assert(false);
457           }
458         }
459
460         continue;
461       }
462
463       /* Normal sequence */
464       BLI_assert(is_cfra_eq(col->cfra, bezt[0].vec[1][0]));
465
466       compute_keyblock_data(&block, bezt, bezt + 1);
467
468       for (; col != NULL && is_cfra_lt(col->cfra, bezt[1].vec[1][0]); col = col->next) {
469         add_keyblock_info(col, &block);
470       }
471
472       BLI_assert(col != NULL);
473     }
474   }
475
476   /* Insert dummy blocks at the end. */
477   for (; col != NULL; col = col->next) {
478     add_keyblock_info(col, &dummy_keyblock);
479   }
480 }
481
482 /* Walk through columns and propagate blocks and totcurve.
483  *
484  * This must be called even by animation sources that don't generate
485  * keyblocks to keep the data structure consistent after adding columns.
486  */
487 static void update_keyblocks(DLRBT_Tree *keys, BezTriple *bezt, int bezt_len)
488 {
489   /* Recompute the prev/next linked list. */
490   BLI_dlrbTree_linkedlist_sync(keys);
491
492   /* Find the curve count */
493   int max_curve = 0;
494
495   for (ActKeyColumn *col = keys->first; col; col = col->next) {
496     max_curve = MAX2(max_curve, col->totcurve);
497   }
498
499   /* Propagate blocks to inserted keys */
500   ActKeyColumn *prev_ready = NULL;
501
502   for (ActKeyColumn *col = keys->first; col; col = col->next) {
503     /* Pre-existing column. */
504     if (col->totcurve > 0) {
505       prev_ready = col;
506     }
507     /* Newly inserted column, so copy block data from previous. */
508     else if (prev_ready != NULL) {
509       col->totblock = prev_ready->totblock;
510       memcpy(&col->block, &prev_ready->block, sizeof(ActKeyBlockInfo));
511     }
512
513     col->totcurve = max_curve + 1;
514   }
515
516   /* Add blocks on top */
517   add_bezt_to_keyblocks_list(keys, bezt, bezt_len);
518 }
519
520 /* --------- */
521
522 bool actkeyblock_is_valid(ActKeyColumn *ac)
523 {
524   return ac != NULL && ac->next != NULL && ac->totblock > 0;
525 }
526
527 /* Checks if ActKeyBlock should exist... */
528 int actkeyblock_get_valid_hold(ActKeyColumn *ac)
529 {
530   /* check that block is valid */
531   if (!actkeyblock_is_valid(ac))
532     return 0;
533
534   const int hold_mask = (ACTKEYBLOCK_FLAG_ANY_HOLD | ACTKEYBLOCK_FLAG_STATIC_HOLD |
535                          ACTKEYBLOCK_FLAG_ANY_HOLD);
536   return (ac->block.flag & ~ac->block.conflict) & hold_mask;
537 }
538
539 /* *************************** Keyframe Drawing *************************** */
540
541 void draw_keyframe_shape(float x,
542                          float y,
543                          float size,
544                          bool sel,
545                          short key_type,
546                          short mode,
547                          float alpha,
548                          unsigned int pos_id,
549                          unsigned int size_id,
550                          unsigned int color_id,
551                          unsigned int outline_color_id,
552                          unsigned int flags_id,
553                          short handle_type,
554                          short extreme_type)
555 {
556   bool draw_fill = ELEM(mode, KEYFRAME_SHAPE_INSIDE, KEYFRAME_SHAPE_BOTH);
557   bool draw_outline = ELEM(mode, KEYFRAME_SHAPE_FRAME, KEYFRAME_SHAPE_BOTH);
558
559   BLI_assert(draw_fill || draw_outline);
560
561   /* tweak size of keyframe shape according to type of keyframe
562    * - 'proper' keyframes have key_type = 0, so get drawn at full size
563    */
564   switch (key_type) {
565     case BEZT_KEYTYPE_KEYFRAME: /* must be full size */
566       break;
567
568     case BEZT_KEYTYPE_BREAKDOWN: /* slightly smaller than normal keyframe */
569       size *= 0.85f;
570       break;
571
572     case BEZT_KEYTYPE_MOVEHOLD: /* Slightly smaller than normal keyframes
573                                  * (but by less than for breakdowns). */
574       size *= 0.925f;
575       break;
576
577     case BEZT_KEYTYPE_EXTREME: /* slightly larger */
578       size *= 1.2f;
579       break;
580
581     default:
582       size -= 0.8f * key_type;
583   }
584
585   unsigned char fill_col[4];
586   unsigned char outline_col[4];
587   unsigned int flags = 0;
588
589   /* draw! */
590   if (draw_fill) {
591     /* get interior colors from theme (for selected and unselected only) */
592     switch (key_type) {
593       case BEZT_KEYTYPE_BREAKDOWN: /* bluish frames (default theme) */
594         UI_GetThemeColor4ubv(sel ? TH_KEYTYPE_BREAKDOWN_SELECT : TH_KEYTYPE_BREAKDOWN, fill_col);
595         break;
596       case BEZT_KEYTYPE_EXTREME: /* reddish frames (default theme) */
597         UI_GetThemeColor4ubv(sel ? TH_KEYTYPE_EXTREME_SELECT : TH_KEYTYPE_EXTREME, fill_col);
598         break;
599       case BEZT_KEYTYPE_JITTER: /* greenish frames (default theme) */
600         UI_GetThemeColor4ubv(sel ? TH_KEYTYPE_JITTER_SELECT : TH_KEYTYPE_JITTER, fill_col);
601         break;
602       case BEZT_KEYTYPE_MOVEHOLD: /* similar to traditional keyframes, but different... */
603         UI_GetThemeColor4ubv(sel ? TH_KEYTYPE_MOVEHOLD_SELECT : TH_KEYTYPE_MOVEHOLD, fill_col);
604         break;
605       case BEZT_KEYTYPE_KEYFRAME: /* traditional yellowish frames (default theme) */
606       default:
607         UI_GetThemeColor4ubv(sel ? TH_KEYTYPE_KEYFRAME_SELECT : TH_KEYTYPE_KEYFRAME, fill_col);
608     }
609
610     /* NOTE: we don't use the straight alpha from the theme, or else effects such as
611      * graying out protected/muted channels doesn't work correctly!
612      */
613     fill_col[3] *= alpha;
614
615     if (!draw_outline) {
616       /* force outline color to match */
617       outline_col[0] = fill_col[0];
618       outline_col[1] = fill_col[1];
619       outline_col[2] = fill_col[2];
620       outline_col[3] = fill_col[3];
621     }
622   }
623
624   if (draw_outline) {
625     /* exterior - black frame */
626     UI_GetThemeColor4ubv(sel ? TH_KEYBORDER_SELECT : TH_KEYBORDER, outline_col);
627     outline_col[3] *= alpha;
628
629     if (!draw_fill) {
630       /* fill color needs to be (outline.rgb, 0) */
631       fill_col[0] = outline_col[0];
632       fill_col[1] = outline_col[1];
633       fill_col[2] = outline_col[2];
634       fill_col[3] = 0;
635     }
636
637     /* Handle type to outline shape. */
638     switch (handle_type) {
639       case KEYFRAME_HANDLE_AUTO_CLAMP:
640         flags = 0x2;
641         break; /* circle */
642       case KEYFRAME_HANDLE_AUTO:
643         flags = 0x12;
644         break; /* circle with dot */
645       case KEYFRAME_HANDLE_VECTOR:
646         flags = 0xC;
647         break; /* square */
648       case KEYFRAME_HANDLE_ALIGNED:
649         flags = 0x5;
650         break; /* clipped diamond */
651
652       case KEYFRAME_HANDLE_FREE:
653       default:
654         flags = 1; /* diamond */
655     }
656
657     /* Extreme type to arrow-like shading. */
658     if (extreme_type & KEYFRAME_EXTREME_MAX) {
659       flags |= 0x100;
660     }
661     if (extreme_type & KEYFRAME_EXTREME_MIN) {
662       flags |= 0x200;
663     }
664     if (extreme_type & KEYFRAME_EXTREME_MIXED) {
665       flags |= 0x400;
666     }
667   }
668
669   immAttr1f(size_id, size);
670   immAttr4ubv(color_id, fill_col);
671   immAttr4ubv(outline_color_id, outline_col);
672   immAttr1u(flags_id, flags);
673   immVertex2f(pos_id, x, y);
674 }
675
676 static void draw_keylist(View2D *v2d,
677                          DLRBT_Tree *keys,
678                          float ypos,
679                          float yscale_fac,
680                          bool channelLocked,
681                          int saction_flag)
682 {
683   const float icon_sz = U.widget_unit * 0.5f * yscale_fac;
684   const float half_icon_sz = 0.5f * icon_sz;
685   const float smaller_sz = 0.35f * icon_sz;
686   const float ipo_sz = 0.1f * icon_sz;
687
688   GPU_blend(true);
689
690   /* locked channels are less strongly shown, as feedback for locked channels in DopeSheet */
691   /* TODO: allow this opacity factor to be themed? */
692   float alpha = channelLocked ? 0.25f : 1.0f;
693
694   /* Show interpolation and handle type? */
695   bool show_ipo = (saction_flag & SACTION_SHOW_INTERPOLATION) != 0;
696
697   /* draw keyblocks */
698   if (keys) {
699     float sel_color[4], unsel_color[4];
700     float sel_mhcol[4], unsel_mhcol[4];
701     float ipo_color[4], ipo_color_mix[4];
702
703     /* cache colours first */
704     UI_GetThemeColor4fv(TH_STRIP_SELECT, sel_color);
705     UI_GetThemeColor4fv(TH_STRIP, unsel_color);
706     UI_GetThemeColor4fv(TH_DOPESHEET_IPOLINE, ipo_color);
707
708     sel_color[3] *= alpha;
709     unsel_color[3] *= alpha;
710     ipo_color[3] *= alpha;
711
712     copy_v4_v4(sel_mhcol, sel_color);
713     sel_mhcol[3] *= 0.8f;
714     copy_v4_v4(unsel_mhcol, unsel_color);
715     unsel_mhcol[3] *= 0.8f;
716     copy_v4_v4(ipo_color_mix, ipo_color);
717     ipo_color_mix[3] *= 0.5f;
718
719     uint block_len = 0;
720     for (ActKeyColumn *ab = keys->first; ab; ab = ab->next) {
721       if (actkeyblock_get_valid_hold(ab)) {
722         block_len++;
723       }
724       if (show_ipo && actkeyblock_is_valid(ab) && (ab->block.flag & ACTKEYBLOCK_FLAG_NON_BEZIER)) {
725         block_len++;
726       }
727     }
728
729     if (block_len > 0) {
730       GPUVertFormat *format = immVertexFormat();
731       uint pos_id = GPU_vertformat_attr_add(format, "pos", GPU_COMP_F32, 2, GPU_FETCH_FLOAT);
732       uint color_id = GPU_vertformat_attr_add(format, "color", GPU_COMP_F32, 4, GPU_FETCH_FLOAT);
733       immBindBuiltinProgram(GPU_SHADER_2D_FLAT_COLOR);
734
735       immBegin(GPU_PRIM_TRIS, 6 * block_len);
736       for (ActKeyColumn *ab = keys->first; ab; ab = ab->next) {
737         int valid_hold = actkeyblock_get_valid_hold(ab);
738         if (valid_hold != 0) {
739           if ((valid_hold & ACTKEYBLOCK_FLAG_STATIC_HOLD) == 0) {
740             /* draw "moving hold" long-keyframe block - slightly smaller */
741             immRectf_fast_with_color(pos_id,
742                                      color_id,
743                                      ab->cfra,
744                                      ypos - smaller_sz,
745                                      ab->next->cfra,
746                                      ypos + smaller_sz,
747                                      (ab->block.sel) ? sel_mhcol : unsel_mhcol);
748           }
749           else {
750             /* draw standard long-keyframe block */
751             immRectf_fast_with_color(pos_id,
752                                      color_id,
753                                      ab->cfra,
754                                      ypos - half_icon_sz,
755                                      ab->next->cfra,
756                                      ypos + half_icon_sz,
757                                      (ab->block.sel) ? sel_color : unsel_color);
758           }
759         }
760         if (show_ipo && actkeyblock_is_valid(ab) &&
761             (ab->block.flag & ACTKEYBLOCK_FLAG_NON_BEZIER)) {
762           /* draw an interpolation line */
763           immRectf_fast_with_color(
764               pos_id,
765               color_id,
766               ab->cfra,
767               ypos - ipo_sz,
768               ab->next->cfra,
769               ypos + ipo_sz,
770               (ab->block.conflict & ACTKEYBLOCK_FLAG_NON_BEZIER) ? ipo_color_mix : ipo_color);
771         }
772       }
773       immEnd();
774       immUnbindProgram();
775     }
776   }
777
778   if (keys) {
779     /* count keys */
780     uint key_len = 0;
781     for (ActKeyColumn *ak = keys->first; ak; ak = ak->next) {
782       /* Optimization: if keyframe doesn't appear within 5 units (screenspace)
783        * in visible area, don't draw.
784        * This might give some improvements,
785        * since we current have to flip between view/region matrices.
786        */
787       if (IN_RANGE_INCL(ak->cfra, v2d->cur.xmin, v2d->cur.xmax))
788         key_len++;
789     }
790
791     if (key_len > 0) {
792       /* draw keys */
793       GPUVertFormat *format = immVertexFormat();
794       uint pos_id = GPU_vertformat_attr_add(format, "pos", GPU_COMP_F32, 2, GPU_FETCH_FLOAT);
795       uint size_id = GPU_vertformat_attr_add(format, "size", GPU_COMP_F32, 1, GPU_FETCH_FLOAT);
796       uint color_id = GPU_vertformat_attr_add(
797           format, "color", GPU_COMP_U8, 4, GPU_FETCH_INT_TO_FLOAT_UNIT);
798       uint outline_color_id = GPU_vertformat_attr_add(
799           format, "outlineColor", GPU_COMP_U8, 4, GPU_FETCH_INT_TO_FLOAT_UNIT);
800       uint flags_id = GPU_vertformat_attr_add(format, "flags", GPU_COMP_U32, 1, GPU_FETCH_INT);
801       immBindBuiltinProgram(GPU_SHADER_KEYFRAME_DIAMOND);
802       GPU_enable_program_point_size();
803       immUniform2f(
804           "ViewportSize", BLI_rcti_size_x(&v2d->mask) + 1, BLI_rcti_size_y(&v2d->mask) + 1);
805       immBegin(GPU_PRIM_POINTS, key_len);
806
807       short handle_type = KEYFRAME_HANDLE_NONE, extreme_type = KEYFRAME_EXTREME_NONE;
808
809       for (ActKeyColumn *ak = keys->first; ak; ak = ak->next) {
810         if (IN_RANGE_INCL(ak->cfra, v2d->cur.xmin, v2d->cur.xmax)) {
811           if (show_ipo) {
812             handle_type = ak->handle_type;
813           }
814           if (saction_flag & SACTION_SHOW_EXTREMES) {
815             extreme_type = ak->extreme_type;
816           }
817
818           draw_keyframe_shape(ak->cfra,
819                               ypos,
820                               icon_sz,
821                               (ak->sel & SELECT),
822                               ak->key_type,
823                               KEYFRAME_SHAPE_BOTH,
824                               alpha,
825                               pos_id,
826                               size_id,
827                               color_id,
828                               outline_color_id,
829                               flags_id,
830                               handle_type,
831                               extreme_type);
832         }
833       }
834
835       immEnd();
836       GPU_disable_program_point_size();
837       immUnbindProgram();
838     }
839   }
840
841   GPU_blend(false);
842 }
843
844 /* *************************** Channel Drawing Funcs *************************** */
845
846 void draw_summary_channel(
847     View2D *v2d, bAnimContext *ac, float ypos, float yscale_fac, int saction_flag)
848 {
849   DLRBT_Tree keys;
850
851   saction_flag &= ~SACTION_SHOW_EXTREMES;
852
853   BLI_dlrbTree_init(&keys);
854
855   summary_to_keylist(ac, &keys, saction_flag);
856
857   draw_keylist(v2d, &keys, ypos, yscale_fac, false, saction_flag);
858
859   BLI_dlrbTree_free(&keys);
860 }
861
862 void draw_scene_channel(
863     View2D *v2d, bDopeSheet *ads, Scene *sce, float ypos, float yscale_fac, int saction_flag)
864 {
865   DLRBT_Tree keys;
866
867   saction_flag &= ~SACTION_SHOW_EXTREMES;
868
869   BLI_dlrbTree_init(&keys);
870
871   scene_to_keylist(ads, sce, &keys, saction_flag);
872
873   draw_keylist(v2d, &keys, ypos, yscale_fac, false, saction_flag);
874
875   BLI_dlrbTree_free(&keys);
876 }
877
878 void draw_object_channel(
879     View2D *v2d, bDopeSheet *ads, Object *ob, float ypos, float yscale_fac, int saction_flag)
880 {
881   DLRBT_Tree keys;
882
883   saction_flag &= ~SACTION_SHOW_EXTREMES;
884
885   BLI_dlrbTree_init(&keys);
886
887   ob_to_keylist(ads, ob, &keys, saction_flag);
888
889   draw_keylist(v2d, &keys, ypos, yscale_fac, false, saction_flag);
890
891   BLI_dlrbTree_free(&keys);
892 }
893
894 void draw_fcurve_channel(
895     View2D *v2d, AnimData *adt, FCurve *fcu, float ypos, float yscale_fac, int saction_flag)
896 {
897   DLRBT_Tree keys;
898
899   bool locked = (fcu->flag & FCURVE_PROTECTED) ||
900                 ((fcu->grp) && (fcu->grp->flag & AGRP_PROTECTED)) ||
901                 ((adt && adt->action) && ID_IS_LINKED(adt->action));
902
903   BLI_dlrbTree_init(&keys);
904
905   fcurve_to_keylist(adt, fcu, &keys, saction_flag);
906
907   draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
908
909   BLI_dlrbTree_free(&keys);
910 }
911
912 void draw_agroup_channel(
913     View2D *v2d, AnimData *adt, bActionGroup *agrp, float ypos, float yscale_fac, int saction_flag)
914 {
915   DLRBT_Tree keys;
916
917   bool locked = (agrp->flag & AGRP_PROTECTED) ||
918                 ((adt && adt->action) && ID_IS_LINKED(adt->action));
919
920   BLI_dlrbTree_init(&keys);
921
922   agroup_to_keylist(adt, agrp, &keys, saction_flag);
923
924   draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
925
926   BLI_dlrbTree_free(&keys);
927 }
928
929 void draw_action_channel(
930     View2D *v2d, AnimData *adt, bAction *act, float ypos, float yscale_fac, int saction_flag)
931 {
932   DLRBT_Tree keys;
933
934   bool locked = (act && ID_IS_LINKED(act));
935
936   saction_flag &= ~SACTION_SHOW_EXTREMES;
937
938   BLI_dlrbTree_init(&keys);
939
940   action_to_keylist(adt, act, &keys, saction_flag);
941
942   draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
943
944   BLI_dlrbTree_free(&keys);
945 }
946
947 void draw_gpencil_channel(
948     View2D *v2d, bDopeSheet *ads, bGPdata *gpd, float ypos, float yscale_fac, int saction_flag)
949 {
950   DLRBT_Tree keys;
951
952   saction_flag &= ~SACTION_SHOW_EXTREMES;
953
954   BLI_dlrbTree_init(&keys);
955
956   gpencil_to_keylist(ads, gpd, &keys, false);
957
958   draw_keylist(v2d, &keys, ypos, yscale_fac, false, saction_flag);
959
960   BLI_dlrbTree_free(&keys);
961 }
962
963 void draw_gpl_channel(
964     View2D *v2d, bDopeSheet *ads, bGPDlayer *gpl, float ypos, float yscale_fac, int saction_flag)
965 {
966   DLRBT_Tree keys;
967
968   bool locked = (gpl->flag & GP_LAYER_LOCKED) != 0;
969
970   BLI_dlrbTree_init(&keys);
971
972   gpl_to_keylist(ads, gpl, &keys);
973
974   draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
975
976   BLI_dlrbTree_free(&keys);
977 }
978
979 void draw_masklay_channel(View2D *v2d,
980                           bDopeSheet *ads,
981                           MaskLayer *masklay,
982                           float ypos,
983                           float yscale_fac,
984                           int saction_flag)
985 {
986   DLRBT_Tree keys;
987
988   bool locked = (masklay->flag & MASK_LAYERFLAG_LOCKED) != 0;
989
990   BLI_dlrbTree_init(&keys);
991
992   mask_to_keylist(ads, masklay, &keys);
993
994   draw_keylist(v2d, &keys, ypos, yscale_fac, locked, saction_flag);
995
996   BLI_dlrbTree_free(&keys);
997 }
998
999 /* *************************** Keyframe List Conversions *************************** */
1000
1001 void summary_to_keylist(bAnimContext *ac, DLRBT_Tree *keys, int saction_flag)
1002 {
1003   if (ac) {
1004     ListBase anim_data = {NULL, NULL};
1005     bAnimListElem *ale;
1006     int filter;
1007
1008     /* get F-Curves to take keyframes from */
1009     filter = ANIMFILTER_DATA_VISIBLE;
1010     ANIM_animdata_filter(ac, &anim_data, filter, ac->data, ac->datatype);
1011
1012     /* loop through each F-Curve, grabbing the keyframes */
1013     for (ale = anim_data.first; ale; ale = ale->next) {
1014       /* Why not use all #eAnim_KeyType here?
1015        * All of the other key types are actually "summaries" themselves,
1016        * and will just end up duplicating stuff that comes up through
1017        * standard filtering of just F-Curves. Given the way that these work,
1018        * there isn't really any benefit at all from including them. - Aligorith */
1019
1020       switch (ale->datatype) {
1021         case ALE_FCURVE:
1022           fcurve_to_keylist(ale->adt, ale->data, keys, saction_flag);
1023           break;
1024         case ALE_MASKLAY:
1025           mask_to_keylist(ac->ads, ale->data, keys);
1026           break;
1027         case ALE_GPFRAME:
1028           gpl_to_keylist(ac->ads, ale->data, keys);
1029           break;
1030         default:
1031           // printf("%s: datatype %d unhandled\n", __func__, ale->datatype);
1032           break;
1033       }
1034     }
1035
1036     ANIM_animdata_freelist(&anim_data);
1037   }
1038 }
1039
1040 void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, int saction_flag)
1041 {
1042   bAnimContext ac = {NULL};
1043   ListBase anim_data = {NULL, NULL};
1044   bAnimListElem *ale;
1045   int filter;
1046
1047   bAnimListElem dummychan = {NULL};
1048
1049   if (sce == NULL)
1050     return;
1051
1052   /* create a dummy wrapper data to work with */
1053   dummychan.type = ANIMTYPE_SCENE;
1054   dummychan.data = sce;
1055   dummychan.id = &sce->id;
1056   dummychan.adt = sce->adt;
1057
1058   ac.ads = ads;
1059   ac.data = &dummychan;
1060   ac.datatype = ANIMCONT_CHANNEL;
1061
1062   /* get F-Curves to take keyframes from */
1063   filter = ANIMFILTER_DATA_VISIBLE;  // curves only
1064   ANIM_animdata_filter(&ac, &anim_data, filter, ac.data, ac.datatype);
1065
1066   /* loop through each F-Curve, grabbing the keyframes */
1067   for (ale = anim_data.first; ale; ale = ale->next)
1068     fcurve_to_keylist(ale->adt, ale->data, keys, saction_flag);
1069
1070   ANIM_animdata_freelist(&anim_data);
1071 }
1072
1073 void ob_to_keylist(bDopeSheet *ads, Object *ob, DLRBT_Tree *keys, int saction_flag)
1074 {
1075   bAnimContext ac = {NULL};
1076   ListBase anim_data = {NULL, NULL};
1077   bAnimListElem *ale;
1078   int filter;
1079
1080   bAnimListElem dummychan = {NULL};
1081   Base dummybase = {NULL};
1082
1083   if (ob == NULL)
1084     return;
1085
1086   /* create a dummy wrapper data to work with */
1087   dummybase.object = ob;
1088
1089   dummychan.type = ANIMTYPE_OBJECT;
1090   dummychan.data = &dummybase;
1091   dummychan.id = &ob->id;
1092   dummychan.adt = ob->adt;
1093
1094   ac.ads = ads;
1095   ac.data = &dummychan;
1096   ac.datatype = ANIMCONT_CHANNEL;
1097
1098   /* get F-Curves to take keyframes from */
1099   filter = ANIMFILTER_DATA_VISIBLE;  // curves only
1100   ANIM_animdata_filter(&ac, &anim_data, filter, ac.data, ac.datatype);
1101
1102   /* loop through each F-Curve, grabbing the keyframes */
1103   for (ale = anim_data.first; ale; ale = ale->next)
1104     fcurve_to_keylist(ale->adt, ale->data, keys, saction_flag);
1105
1106   ANIM_animdata_freelist(&anim_data);
1107 }
1108
1109 void cachefile_to_keylist(bDopeSheet *ads,
1110                           CacheFile *cache_file,
1111                           DLRBT_Tree *keys,
1112                           int saction_flag)
1113 {
1114   if (cache_file == NULL) {
1115     return;
1116   }
1117
1118   /* create a dummy wrapper data to work with */
1119   bAnimListElem dummychan = {NULL};
1120   dummychan.type = ANIMTYPE_DSCACHEFILE;
1121   dummychan.data = cache_file;
1122   dummychan.id = &cache_file->id;
1123   dummychan.adt = cache_file->adt;
1124
1125   bAnimContext ac = {NULL};
1126   ac.ads = ads;
1127   ac.data = &dummychan;
1128   ac.datatype = ANIMCONT_CHANNEL;
1129
1130   /* get F-Curves to take keyframes from */
1131   ListBase anim_data = {NULL, NULL};
1132   int filter = ANIMFILTER_DATA_VISIBLE;  // curves only
1133   ANIM_animdata_filter(&ac, &anim_data, filter, ac.data, ac.datatype);
1134
1135   /* loop through each F-Curve, grabbing the keyframes */
1136   for (bAnimListElem *ale = anim_data.first; ale; ale = ale->next) {
1137     fcurve_to_keylist(ale->adt, ale->data, keys, saction_flag);
1138   }
1139
1140   ANIM_animdata_freelist(&anim_data);
1141 }
1142
1143 void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, int saction_flag)
1144 {
1145   if (fcu && fcu->totvert && fcu->bezt) {
1146     /* apply NLA-mapping (if applicable) */
1147     if (adt)
1148       ANIM_nla_mapping_apply_fcurve(adt, fcu, 0, 0);
1149
1150     /* Check if the curve is cyclic. */
1151     bool is_cyclic = BKE_fcurve_is_cyclic(fcu) && (fcu->totvert >= 2);
1152     bool do_extremes = (saction_flag & SACTION_SHOW_EXTREMES) != 0;
1153
1154     /* loop through beztriples, making ActKeysColumns */
1155     BezTripleChain chain = {0};
1156
1157     for (int v = 0; v < fcu->totvert; v++) {
1158       chain.cur = &fcu->bezt[v];
1159
1160       /* Neighbor keys, accounting for being cyclic. */
1161       if (do_extremes) {
1162         chain.prev = (v > 0) ? &fcu->bezt[v - 1] : is_cyclic ? &fcu->bezt[fcu->totvert - 2] : NULL;
1163         chain.next = (v + 1 < fcu->totvert) ? &fcu->bezt[v + 1] : is_cyclic ? &fcu->bezt[1] : NULL;
1164       }
1165
1166       add_bezt_to_keycolumns_list(keys, &chain);
1167     }
1168
1169     /* Update keyblocks. */
1170     update_keyblocks(keys, fcu->bezt, fcu->totvert);
1171
1172     /* unapply NLA-mapping if applicable */
1173     if (adt)
1174       ANIM_nla_mapping_apply_fcurve(adt, fcu, 1, 0);
1175   }
1176 }
1177
1178 void agroup_to_keylist(AnimData *adt, bActionGroup *agrp, DLRBT_Tree *keys, int saction_flag)
1179 {
1180   FCurve *fcu;
1181
1182   if (agrp) {
1183     /* loop through F-Curves */
1184     for (fcu = agrp->channels.first; fcu && fcu->grp == agrp; fcu = fcu->next) {
1185       fcurve_to_keylist(adt, fcu, keys, saction_flag);
1186     }
1187   }
1188 }
1189
1190 void action_to_keylist(AnimData *adt, bAction *act, DLRBT_Tree *keys, int saction_flag)
1191 {
1192   FCurve *fcu;
1193
1194   if (act) {
1195     /* loop through F-Curves */
1196     for (fcu = act->curves.first; fcu; fcu = fcu->next) {
1197       fcurve_to_keylist(adt, fcu, keys, saction_flag);
1198     }
1199   }
1200 }
1201
1202 void gpencil_to_keylist(bDopeSheet *ads, bGPdata *gpd, DLRBT_Tree *keys, const bool active)
1203 {
1204   bGPDlayer *gpl;
1205
1206   if (gpd && keys) {
1207     /* for now, just aggregate out all the frames, but only for visible layers */
1208     for (gpl = gpd->layers.last; gpl; gpl = gpl->prev) {
1209       if ((gpl->flag & GP_LAYER_HIDE) == 0) {
1210         if ((!active) || ((active) && (gpl->flag & GP_LAYER_SELECT))) {
1211           gpl_to_keylist(ads, gpl, keys);
1212         }
1213       }
1214     }
1215   }
1216 }
1217
1218 void gpl_to_keylist(bDopeSheet *UNUSED(ads), bGPDlayer *gpl, DLRBT_Tree *keys)
1219 {
1220   bGPDframe *gpf;
1221
1222   if (gpl && keys) {
1223     /* Although the frames should already be in an ordered list,
1224      * they are not suitable for displaying yet. */
1225     for (gpf = gpl->frames.first; gpf; gpf = gpf->next)
1226       add_gpframe_to_keycolumns_list(keys, gpf);
1227
1228     update_keyblocks(keys, NULL, 0);
1229   }
1230 }
1231
1232 void mask_to_keylist(bDopeSheet *UNUSED(ads), MaskLayer *masklay, DLRBT_Tree *keys)
1233 {
1234   MaskLayerShape *masklay_shape;
1235
1236   if (masklay && keys) {
1237     for (masklay_shape = masklay->splines_shapes.first; masklay_shape;
1238          masklay_shape = masklay_shape->next) {
1239       add_masklay_to_keycolumns_list(keys, masklay_shape);
1240     }
1241
1242     update_keyblocks(keys, NULL, 0);
1243   }
1244 }