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