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