Some options used for "expert" x264 setup were removed from FFmpeg 0.11
[blender.git] / source / blender / blenkernel / intern / sketch.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  * Contributor(s): none yet.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/blenkernel/intern/sketch.c
24  *  \ingroup bke
25  */
26
27
28 #include <string.h>
29 #include <math.h>
30 #include <float.h>
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_blenlib.h"
35 #include "BLI_math.h"
36 #include "BLI_utildefines.h"
37
38 #include "BKE_sketch.h"
39
40
41 #include "DNA_userdef_types.h"
42
43 void freeSketch(SK_Sketch *sketch)
44 {
45         SK_Stroke *stk, *next;
46
47         for (stk = sketch->strokes.first; stk; stk = next) {
48                 next = stk->next;
49
50                 sk_freeStroke(stk);
51         }
52
53         BLI_freelistN(&sketch->depth_peels);
54
55         MEM_freeN(sketch);
56 }
57
58 SK_Sketch *createSketch(void)
59 {
60         SK_Sketch *sketch;
61
62         sketch = MEM_callocN(sizeof(SK_Sketch), "SK_Sketch");
63
64         sketch->active_stroke = NULL;
65         sketch->gesture = NULL;
66
67         sketch->strokes.first = NULL;
68         sketch->strokes.last = NULL;
69
70         return sketch;
71 }
72
73 void sk_initPoint(SK_Point *pt, SK_DrawData *dd, const float no[3])
74 {
75         if (no) {
76                 normalize_v3_v3(pt->no, no);
77         }
78         else {
79                 pt->no[0] = 0.0f;
80                 pt->no[1] = 0.0f;
81                 pt->no[2] = 1.0f;
82         }
83         pt->p2d[0] = dd->mval[0];
84         pt->p2d[1] = dd->mval[1];
85         /* more init code here */
86 }
87
88 void sk_copyPoint(SK_Point *dst, SK_Point *src)
89 {
90         memcpy(dst, src, sizeof(SK_Point));
91 }
92
93 void sk_allocStrokeBuffer(SK_Stroke *stk)
94 {
95         stk->points = MEM_callocN(sizeof(SK_Point) * stk->buf_size, "SK_Point buffer");
96 }
97
98 void sk_freeStroke(SK_Stroke *stk)
99 {
100         MEM_freeN(stk->points);
101         MEM_freeN(stk);
102 }
103
104 SK_Stroke *sk_createStroke(void)
105 {
106         SK_Stroke *stk;
107
108         stk = MEM_callocN(sizeof(SK_Stroke), "SK_Stroke");
109
110         stk->selected = 0;
111         stk->nb_points = 0;
112         stk->buf_size = SK_Stroke_BUFFER_INIT_SIZE;
113
114         sk_allocStrokeBuffer(stk);
115
116         return stk;
117 }
118
119 void sk_shrinkStrokeBuffer(SK_Stroke *stk)
120 {
121         if (stk->nb_points < stk->buf_size) {
122                 SK_Point *old_points = stk->points;
123
124                 stk->buf_size = stk->nb_points;
125
126                 sk_allocStrokeBuffer(stk);
127
128                 memcpy(stk->points, old_points, sizeof(SK_Point) * stk->nb_points);
129
130                 MEM_freeN(old_points);
131         }
132 }
133
134 void sk_growStrokeBuffer(SK_Stroke *stk)
135 {
136         if (stk->nb_points == stk->buf_size) {
137                 SK_Point *old_points = stk->points;
138
139                 stk->buf_size *= 2;
140
141                 sk_allocStrokeBuffer(stk);
142
143                 memcpy(stk->points, old_points, sizeof(SK_Point) * stk->nb_points);
144
145                 MEM_freeN(old_points);
146         }
147 }
148
149 void sk_growStrokeBufferN(SK_Stroke *stk, int n)
150 {
151         if (stk->nb_points + n > stk->buf_size) {
152                 SK_Point *old_points = stk->points;
153
154                 while (stk->nb_points + n > stk->buf_size) {
155                         stk->buf_size *= 2;
156                 }
157
158                 sk_allocStrokeBuffer(stk);
159
160                 memcpy(stk->points, old_points, sizeof(SK_Point) * stk->nb_points);
161
162                 MEM_freeN(old_points);
163         }
164 }
165
166
167 void sk_replaceStrokePoint(SK_Stroke *stk, SK_Point *pt, int n)
168 {
169         memcpy(stk->points + n, pt, sizeof(SK_Point));
170 }
171
172 void sk_insertStrokePoint(SK_Stroke *stk, SK_Point *pt, int n)
173 {
174         int size = stk->nb_points - n;
175
176         sk_growStrokeBuffer(stk);
177
178         memmove(stk->points + n + 1, stk->points + n, size * sizeof(SK_Point));
179
180         memcpy(stk->points + n, pt, sizeof(SK_Point));
181
182         stk->nb_points++;
183 }
184
185 void sk_appendStrokePoint(SK_Stroke *stk, SK_Point *pt)
186 {
187         sk_growStrokeBuffer(stk);
188
189         memcpy(stk->points + stk->nb_points, pt, sizeof(SK_Point));
190
191         stk->nb_points++;
192 }
193
194 void sk_insertStrokePoints(SK_Stroke *stk, SK_Point *pts, int len, int start, int end)
195 {
196         int size = end - start + 1;
197
198         sk_growStrokeBufferN(stk, len - size);
199
200         if (len != size) {
201                 int tail_size = stk->nb_points - end + 1;
202
203                 memmove(stk->points + start + len, stk->points + end + 1, tail_size * sizeof(SK_Point));
204         }
205
206         memcpy(stk->points + start, pts, len * sizeof(SK_Point));
207
208         stk->nb_points += len - size;
209 }
210
211 void sk_trimStroke(SK_Stroke *stk, int start, int end)
212 {
213         int size = end - start + 1;
214
215         if (start > 0) {
216                 memmove(stk->points, stk->points + start, size * sizeof(SK_Point));
217         }
218
219         stk->nb_points = size;
220 }
221
222 void sk_straightenStroke(SK_Stroke *stk, int start, int end, float p_start[3], float p_end[3])
223 {
224         SK_Point pt1, pt2;
225         SK_Point *prev, *next;
226         float delta_p[3];
227         int i, total;
228
229         total = end - start;
230
231         sub_v3_v3v3(delta_p, p_end, p_start);
232
233         prev = stk->points + start;
234         next = stk->points + end;
235
236         copy_v3_v3(pt1.p, p_start);
237         copy_v3_v3(pt1.no, prev->no);
238         pt1.mode = prev->mode;
239         pt1.type = prev->type;
240
241         copy_v3_v3(pt2.p, p_end);
242         copy_v3_v3(pt2.no, next->no);
243         pt2.mode = next->mode;
244         pt2.type = next->type;
245
246         sk_insertStrokePoint(stk, &pt1, start + 1); /* insert after start */
247         sk_insertStrokePoint(stk, &pt2, end + 1); /* insert before end (since end was pushed back already) */
248
249         for (i = 1; i < total; i++) {
250                 float delta = (float)i / (float)total;
251                 float *p = stk->points[start + 1 + i].p;
252
253                 mul_v3_v3fl(p, delta_p, delta);
254                 add_v3_v3(p, p_start);
255         }
256 }
257
258 void sk_polygonizeStroke(SK_Stroke *stk, int start, int end)
259 {
260         int offset;
261         int i;
262
263         /* find first exact points outside of range */
264         for (; start > 0; start--) {
265                 if (stk->points[start].type == PT_EXACT) {
266                         break;
267                 }
268         }
269
270         for (; end < stk->nb_points - 1; end++) {
271                 if (stk->points[end].type == PT_EXACT) {
272                         break;
273                 }
274         }
275
276         offset = start + 1;
277
278         for (i = start + 1; i < end; i++) {
279                 if (stk->points[i].type == PT_EXACT) {
280                         if (offset != i) {
281                                 memcpy(stk->points + offset, stk->points + i, sizeof(SK_Point));
282                         }
283
284                         offset++;
285                 }
286         }
287
288         /* some points were removes, move end of array */
289         if (offset < end) {
290                 int size = stk->nb_points - end;
291                 memmove(stk->points + offset, stk->points + end, size * sizeof(SK_Point));
292                 stk->nb_points = offset + size;
293         }
294 }
295
296 void sk_flattenStroke(SK_Stroke *stk, int start, int end)
297 {
298         float normal[3], distance[3];
299         float limit;
300         int i, total;
301
302         total = end - start + 1;
303
304         copy_v3_v3(normal, stk->points[start].no);
305
306         sub_v3_v3v3(distance, stk->points[end].p, stk->points[start].p);
307         project_v3_v3v3(normal, distance, normal);
308         limit = normalize_v3(normal);
309
310         for (i = 1; i < total - 1; i++) {
311                 float d = limit * i / total;
312                 float offset[3];
313                 float *p = stk->points[start + i].p;
314
315                 sub_v3_v3v3(distance, p, stk->points[start].p);
316                 project_v3_v3v3(distance, distance, normal);
317
318                 copy_v3_v3(offset, normal);
319                 mul_v3_fl(offset, d);
320
321                 sub_v3_v3(p, distance);
322                 add_v3_v3(p, offset);
323         }
324 }
325
326 void sk_removeStroke(SK_Sketch *sketch, SK_Stroke *stk)
327 {
328         if (sketch->active_stroke == stk) {
329                 sketch->active_stroke = NULL;
330         }
331
332         BLI_remlink(&sketch->strokes, stk);
333         sk_freeStroke(stk);
334 }
335
336 void sk_reverseStroke(SK_Stroke *stk)
337 {
338         SK_Point *old_points = stk->points;
339         int i = 0;
340
341         sk_allocStrokeBuffer(stk);
342
343         for (i = 0; i < stk->nb_points; i++) {
344                 sk_copyPoint(stk->points + i, old_points + stk->nb_points - 1 - i);
345         }
346
347         MEM_freeN(old_points);
348 }
349
350
351 /* Ramer-Douglas-Peucker algorithm for line simplification */
352 void sk_filterStroke(SK_Stroke *stk, int start, int end)
353 {
354         SK_Point *old_points = stk->points;
355         int nb_points = stk->nb_points;
356         char *marked = NULL;
357         char work;
358         int i;
359
360         if (start == -1) {
361                 start = 0;
362                 end = stk->nb_points - 1;
363         }
364
365         sk_allocStrokeBuffer(stk);
366         stk->nb_points = 0;
367
368         /* adding points before range */
369         for (i = 0; i < start; i++) {
370                 sk_appendStrokePoint(stk, old_points + i);
371         }
372
373         marked = MEM_callocN(nb_points, "marked array");
374         marked[start] = 1;
375         marked[end] = 1;
376         
377         work = 1;
378         
379         /* while still reducing */
380         while (work) {
381                 int ls, le;
382                 work = 0;
383                 
384                 ls = start;
385                 le = start + 1;
386                 
387                 /* while not over interval */
388                 while (ls < end) {
389                         int max_i = 0;
390                         short v1[2];
391                         float max_dist = 16; /* more than 4 pixels */
392                         
393                         /* find the next marked point */
394                         while (marked[le] == 0) {
395                                 le++;
396                         }
397                         
398                         /* perpendicular vector to ls-le */
399                         v1[1] = old_points[le].p2d[0] - old_points[ls].p2d[0]; 
400                         v1[0] = old_points[ls].p2d[1] - old_points[le].p2d[1]; 
401                         
402
403                         for (i = ls + 1; i < le; i++) {
404                                 float mul;
405                                 float dist;
406                                 short v2[2];
407                                 
408                                 v2[0] = old_points[i].p2d[0] - old_points[ls].p2d[0]; 
409                                 v2[1] = old_points[i].p2d[1] - old_points[ls].p2d[1];
410                                 
411                                 if (v2[0] == 0 && v2[1] == 0) {
412                                         continue;
413                                 }
414
415                                 mul = (float)(v1[0] * v2[0] + v1[1] * v2[1]) / (float)(v2[0] * v2[0] + v2[1] * v2[1]);
416                                 
417                                 dist = mul * mul * (v2[0] * v2[0] + v2[1] * v2[1]);
418                                 
419                                 if (dist > max_dist) {
420                                         max_dist = dist;
421                                         max_i = i;
422                                 }
423                         }
424                         
425                         if (max_i != 0) {
426                                 work = 1;
427                                 marked[max_i] = 1;
428                         }
429                         
430                         ls = le;
431                         le = ls + 1;
432                 }
433         }
434         
435
436         /* adding points after range */
437         for (i = start; i <= end; i++) {
438                 if (marked[i]) {
439                         sk_appendStrokePoint(stk, old_points + i);
440                 }
441         }
442
443         MEM_freeN(marked);
444
445         /* adding points after range */
446         for (i = end + 1; i < nb_points; i++) {
447                 sk_appendStrokePoint(stk, old_points + i);
448         }
449
450         MEM_freeN(old_points);
451
452         sk_shrinkStrokeBuffer(stk);
453 }
454
455
456 void sk_filterLastContinuousStroke(SK_Stroke *stk)
457 {
458         int start, end;
459
460         end = stk->nb_points - 1;
461
462         for (start = end - 1; start > 0 && stk->points[start].type == PT_CONTINUOUS; start--) {
463                 /* nothing to do here*/
464         }
465
466         if (end - start > 1) {
467                 sk_filterStroke(stk, start, end);
468         }
469 }
470
471 SK_Point *sk_lastStrokePoint(SK_Stroke *stk)
472 {
473         SK_Point *pt = NULL;
474
475         if (stk->nb_points > 0) {
476                 pt = stk->points + (stk->nb_points - 1);
477         }
478
479         return pt;
480 }
481
482 void sk_endContinuousStroke(SK_Stroke *stk)
483 {
484         stk->points[stk->nb_points - 1].type = PT_EXACT;
485 }
486
487 void sk_updateNextPoint(SK_Sketch *sketch, SK_Stroke *stk)
488 {
489         if (stk) {
490                 memcpy(&sketch->next_point, stk->points[stk->nb_points - 1].p, sizeof(SK_Point));
491         }
492 }
493
494 int sk_stroke_filtermval(SK_DrawData *dd)
495 {
496         int retval = 0;
497         if (ABS(dd->mval[0] - dd->previous_mval[0]) + ABS(dd->mval[1] - dd->previous_mval[1]) > U.gp_manhattendist) {
498                 retval = 1;
499         }
500
501         return retval;
502 }
503
504 void sk_initDrawData(SK_DrawData *dd, const int mval[2])
505 {
506         dd->mval[0] = mval[0];
507         dd->mval[1] = mval[1];
508         dd->previous_mval[0] = -1;
509         dd->previous_mval[1] = -1;
510         dd->type = PT_EXACT;
511 }
512
513
514 void sk_deleteSelectedStrokes(SK_Sketch *sketch)
515 {
516         SK_Stroke *stk, *next;
517
518         for (stk = sketch->strokes.first; stk; stk = next) {
519                 next = stk->next;
520
521                 if (stk->selected == 1) {
522                         sk_removeStroke(sketch, stk);
523                 }
524         }
525 }
526
527 void sk_selectAllSketch(SK_Sketch *sketch, int mode)
528 {
529         SK_Stroke *stk = NULL;
530
531         if (mode == -1) {
532                 for (stk = sketch->strokes.first; stk; stk = stk->next) {
533                         stk->selected = 0;
534                 }
535         }
536         else if (mode == 0) {
537                 for (stk = sketch->strokes.first; stk; stk = stk->next) {
538                         stk->selected = 1;
539                 }
540         }
541         else if (mode == 1) {
542                 int selected = 1;
543
544                 for (stk = sketch->strokes.first; stk; stk = stk->next) {
545                         selected &= stk->selected;
546                 }
547
548                 selected ^= 1;
549
550                 for (stk = sketch->strokes.first; stk; stk = stk->next) {
551                         stk->selected = selected;
552                 }
553         }
554 }