Adding undo push and redraw for convert calls.
[blender.git] / source / blender / src / editarmature_sketch.c
1 /**
2  * $Id: $
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 #include <string.h>
24 #include <math.h>
25
26 #include "MEM_guardedalloc.h"
27
28 #include "DNA_listBase.h"
29 #include "DNA_scene_types.h"
30 #include "DNA_view3d_types.h"
31 #include "DNA_meshdata_types.h"
32 #include "DNA_object_types.h"
33 #include "DNA_armature_types.h"
34
35 #include "BLI_blenlib.h"
36 #include "BLI_arithb.h"
37
38 #include "BKE_utildefines.h"
39 #include "BKE_global.h"
40 #include "BKE_DerivedMesh.h"
41 #include "BKE_object.h"
42 #include "BKE_anim.h"
43
44 #include "BSE_view.h"
45
46 #include "BIF_gl.h"
47 #include "BIF_resources.h"
48 #include "BIF_screen.h"
49 #include "BIF_space.h"
50 #include "BIF_mywindow.h"
51 #include "BIF_editarmature.h"
52 #include "BIF_sketch.h"
53
54 #include "blendef.h"
55 #include "mydevice.h"
56
57 typedef enum SK_PType
58 {
59         PT_CONTINUOUS,
60         PT_EXACT,
61 } SK_PType;
62
63 typedef enum SK_PMode
64 {
65         PT_EMBED,
66         PT_SNAP,
67         PT_PROJECT,
68 } SK_PMode;
69
70 typedef struct SK_Point
71 {
72         float p[3];
73         SK_PType type;
74         SK_PMode mode;
75 } SK_Point;
76
77 typedef struct SK_Stroke
78 {
79         struct SK_Stroke *next, *prev;
80
81         SK_Point *points;
82         int nb_points;
83         int buf_size;
84         int selected;
85 } SK_Stroke;
86
87 #define SK_Stroke_BUFFER_INIT_SIZE 20
88
89 typedef struct SK_DrawData
90 {
91         short mval[2];
92         short previous_mval[2];
93         SK_PType type;
94 } SK_DrawData;
95
96 typedef struct SK_Intersection
97 {
98         struct SK_Intersection *next, *prev;
99         SK_Stroke *stroke;
100         int                     start;
101         int                     end;
102         float           p[3];
103 } SK_Intersection;
104
105 typedef struct SK_Sketch
106 {
107         ListBase        strokes;
108         SK_Stroke       *active_stroke;
109         SK_Stroke       *gesture;
110         SK_Point        next_point;
111 } SK_Sketch;
112
113 SK_Sketch *GLOBAL_sketch = NULL;
114 SK_Point boneSnap;
115
116 #define SNAP_MIN_DISTANCE 12
117
118 /******************** PROTOTYPES ******************************/
119
120 void sk_freeStroke(SK_Stroke *stk);
121 void sk_freeSketch(SK_Sketch *sketch);
122
123 /******************** PEELING *********************************/
124
125 typedef struct SK_DepthPeel
126 {
127         struct SK_DepthPeel *next, *prev;
128         
129         float depth;
130         float p[3];
131         float no[3];
132         Object *ob;
133         int flag;
134 } SK_DepthPeel;
135
136 int cmpPeel(void *arg1, void *arg2)
137 {
138         SK_DepthPeel *p1 = arg1;
139         SK_DepthPeel *p2 = arg2;
140         int val = 0;
141         
142         if (p1->depth < p2->depth)
143         {
144                 val = -1;
145         }
146         else if (p1->depth > p2->depth)
147         {
148                 val = 1;
149         }
150         
151         return val;
152 }
153
154 void addDepthPeel(ListBase *depth_peels, float depth, float p[3], float no[3], Object *ob)
155 {
156         SK_DepthPeel *peel = MEM_callocN(sizeof(SK_DepthPeel), "DepthPeel");
157         
158         peel->depth = depth;
159         peel->ob = ob;
160         VECCOPY(peel->p, p);
161         VECCOPY(peel->no, no);
162         
163         BLI_addtail(depth_peels, peel);
164         
165         peel->flag = 0;
166 }
167
168 int peelDerivedMesh(Object *ob, DerivedMesh *dm, float obmat[][4], float ray_start[3], float ray_normal[3], short mval[2], ListBase *depth_peels)
169 {
170         int retval = 0;
171         int totvert = dm->getNumVerts(dm);
172         int totface = dm->getNumFaces(dm);
173         
174         if (totvert > 0) {
175                 float imat[4][4];
176                 float timat[3][3]; /* transpose inverse matrix for normals */
177                 float ray_start_local[3], ray_normal_local[3];
178                 int test = 1;
179
180                 Mat4Invert(imat, obmat);
181
182                 Mat3CpyMat4(timat, imat);
183                 Mat3Transp(timat);
184                 
185                 VECCOPY(ray_start_local, ray_start);
186                 VECCOPY(ray_normal_local, ray_normal);
187                 
188                 Mat4MulVecfl(imat, ray_start_local);
189                 Mat4Mul3Vecfl(imat, ray_normal_local);
190                 
191                 
192                 /* If number of vert is more than an arbitrary limit, 
193                  * test against boundbox first
194                  * */
195                 if (totface > 16) {
196                         struct BoundBox *bb = object_get_boundbox(ob);
197                         test = ray_hit_boundbox(bb, ray_start_local, ray_normal_local);
198                 }
199                 
200                 if (test == 1) {
201                         MVert *verts = dm->getVertArray(dm);
202                         MFace *faces = dm->getFaceArray(dm);
203                         int i;
204                         
205                         for( i = 0; i < totface; i++) {
206                                 MFace *f = faces + i;
207                                 float lambda;
208                                 int result;
209                                 
210                                 
211                                 result = RayIntersectsTriangle(ray_start_local, ray_normal_local, verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, &lambda, NULL);
212                                 
213                                 if (result) {
214                                         float location[3], normal[3];
215                                         float intersect[3];
216                                         float new_depth;
217                                         
218                                         VECCOPY(intersect, ray_normal_local);
219                                         VecMulf(intersect, lambda);
220                                         VecAddf(intersect, intersect, ray_start_local);
221                                         
222                                         VECCOPY(location, intersect);
223                                         
224                                         if (f->v4)
225                                                 CalcNormFloat4(verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, verts[f->v4].co, normal);
226                                         else
227                                                 CalcNormFloat(verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, normal);
228
229                                         Mat4MulVecfl(obmat, location);
230                                         
231                                         new_depth = VecLenf(location, ray_start);                                       
232                                         
233                                         Mat3MulVecfl(timat, normal);
234                                         Normalize(normal);
235
236                                         addDepthPeel(depth_peels, new_depth, location, normal, ob);
237                                 }
238                 
239                                 if (f->v4 && result == 0)
240                                 {
241                                         result = RayIntersectsTriangle(ray_start_local, ray_normal_local, verts[f->v3].co, verts[f->v4].co, verts[f->v1].co, &lambda, NULL);
242                                         
243                                         if (result) {
244                                                 float location[3], normal[3];
245                                                 float intersect[3];
246                                                 float new_depth;
247                                                 
248                                                 VECCOPY(intersect, ray_normal_local);
249                                                 VecMulf(intersect, lambda);
250                                                 VecAddf(intersect, intersect, ray_start_local);
251                                                 
252                                                 VECCOPY(location, intersect);
253                                                 
254                                                 if (f->v4)
255                                                         CalcNormFloat4(verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, verts[f->v4].co, normal);
256                                                 else
257                                                         CalcNormFloat(verts[f->v1].co, verts[f->v2].co, verts[f->v3].co, normal);
258
259                                                 Mat4MulVecfl(obmat, location);
260                                                 
261                                                 new_depth = VecLenf(location, ray_start);                                       
262                                                 
263                                                 Mat3MulVecfl(timat, normal);
264                                                 Normalize(normal);
265         
266                                                 addDepthPeel(depth_peels, new_depth, location, normal, ob);
267                                         } 
268                                 }
269                         }
270                 }
271         }
272
273         return retval;
274
275
276 int peelObjects(ListBase *depth_peels, short mval[2])
277 {
278         Base *base;
279         int retval = 0;
280         float ray_start[3], ray_normal[3];
281         
282         viewray(mval, ray_start, ray_normal);
283
284         base= FIRSTBASE;
285         for ( base = FIRSTBASE; base != NULL; base = base->next ) {
286                 if ( BASE_SELECTABLE(base) ) {
287                         Object *ob = base->object;
288                         
289                         if (ob->transflag & OB_DUPLI)
290                         {
291                                 DupliObject *dupli_ob;
292                                 ListBase *lb = object_duplilist(G.scene, ob);
293                                 
294                                 for(dupli_ob = lb->first; dupli_ob; dupli_ob = dupli_ob->next)
295                                 {
296                                         Object *ob = dupli_ob->ob;
297                                         
298                                         if (ob->type == OB_MESH) {
299                                                 DerivedMesh *dm = mesh_get_derived_final(ob, CD_MASK_BAREMESH);
300                                                 int val;
301                                                 
302                                                 val = peelDerivedMesh(ob, dm, dupli_ob->mat, ray_start, ray_normal, mval, depth_peels);
303         
304                                                 retval = retval || val;
305         
306                                                 dm->release(dm);
307                                         }
308                                 }
309                                 
310                                 free_object_duplilist(lb);
311                         }
312                         
313                         if (ob->type == OB_MESH) {
314                                 DerivedMesh *dm = NULL;
315                                 int val;
316
317                                 if (ob != G.obedit)
318                                 {
319                                         dm = mesh_get_derived_final(ob, CD_MASK_BAREMESH);
320                                         
321                                         val = peelDerivedMesh(ob, dm, ob->obmat, ray_start, ray_normal, mval, depth_peels);
322                                 }
323                                 else
324                                 {
325                                         dm = editmesh_get_derived_cage(CD_MASK_BAREMESH);
326                                         
327                                         val = peelDerivedMesh(ob, dm, ob->obmat, ray_start, ray_normal, mval, depth_peels);
328                                 }
329                                         
330                                 retval = retval || val;
331                                 
332                                 dm->release(dm);
333                         }
334                 }
335         }
336         
337         BLI_sortlist(depth_peels, cmpPeel);
338         
339         return retval;
340 }
341
342 /**************************************************************/
343
344 void sk_freeSketch(SK_Sketch *sketch)
345 {
346         SK_Stroke *stk, *next;
347         
348         for (stk = sketch->strokes.first; stk; stk = next)
349         {
350                 next = stk->next;
351                 
352                 sk_freeStroke(stk);
353         }
354         
355         MEM_freeN(sketch);
356 }
357
358 SK_Sketch* sk_createSketch()
359 {
360         SK_Sketch *sketch;
361         
362         sketch = MEM_callocN(sizeof(SK_Sketch), "SK_Sketch");
363         
364         sketch->active_stroke = NULL;
365         sketch->gesture = NULL;
366
367         sketch->strokes.first = NULL;
368         sketch->strokes.last = NULL;
369         
370         return sketch;
371 }
372
373 void sk_allocStrokeBuffer(SK_Stroke *stk)
374 {
375         stk->points = MEM_callocN(sizeof(SK_Point) * stk->buf_size, "SK_Point buffer");
376 }
377
378 void sk_freeStroke(SK_Stroke *stk)
379 {
380         MEM_freeN(stk->points);
381         MEM_freeN(stk);
382 }
383
384 SK_Stroke* sk_createStroke()
385 {
386         SK_Stroke *stk;
387         
388         stk = MEM_callocN(sizeof(SK_Stroke), "SK_Stroke");
389         
390         stk->selected = 0;
391         stk->nb_points = 0;
392         stk->buf_size = SK_Stroke_BUFFER_INIT_SIZE;
393         
394         sk_allocStrokeBuffer(stk);
395         
396         return stk;
397 }
398
399 void sk_shrinkStrokeBuffer(SK_Stroke *stk)
400 {
401         if (stk->nb_points < stk->buf_size)
402         {
403                 SK_Point *old_points = stk->points;
404                 
405                 stk->buf_size = stk->nb_points;
406
407                 sk_allocStrokeBuffer(stk);              
408                 
409                 memcpy(stk->points, old_points, sizeof(SK_Point) * stk->nb_points);
410                 
411                 MEM_freeN(old_points);
412         }
413 }
414
415 void sk_growStrokeBuffer(SK_Stroke *stk)
416 {
417         if (stk->nb_points == stk->buf_size)
418         {
419                 SK_Point *old_points = stk->points;
420                 
421                 stk->buf_size *= 2;
422                 
423                 sk_allocStrokeBuffer(stk);
424                 
425                 memcpy(stk->points, old_points, sizeof(SK_Point) * stk->nb_points);
426                 
427                 MEM_freeN(old_points);
428         }
429 }
430
431 void sk_replaceStrokePoint(SK_Stroke *stk, SK_Point *pt, int n)
432 {
433         memcpy(stk->points + n, pt, sizeof(SK_Point));
434 }
435
436 void sk_insertStrokePoint(SK_Stroke *stk, SK_Point *pt, int n)
437 {
438         int size = stk->nb_points - n;
439         
440         sk_growStrokeBuffer(stk);
441         
442         memmove(stk->points + n + 1, stk->points + n, size * sizeof(SK_Point));
443         
444         memcpy(stk->points + n, pt, sizeof(SK_Point));
445         
446         stk->nb_points++;
447 }
448
449 void sk_appendStrokePoint(SK_Stroke *stk, SK_Point *pt)
450 {
451         sk_growStrokeBuffer(stk);
452         
453         memcpy(stk->points + stk->nb_points, pt, sizeof(SK_Point));
454         
455         stk->nb_points++;
456 }
457
458 void sk_trimStroke(SK_Stroke *stk, int start, int end)
459 {
460         int size = end - start + 1;
461         
462         if (start > 0)
463         {
464                 memmove(stk->points, stk->points + start, size * sizeof(SK_Point));
465         }
466         
467         stk->nb_points = size;
468 }
469
470 /* Apply reverse Chaikin filter to simplify the polyline
471  * */
472 void sk_filterStroke(SK_Stroke *stk, int start, int end)
473 {
474         SK_Point *old_points = stk->points;
475         int nb_points = stk->nb_points;
476         int i, j;
477         
478         if (start == -1)
479         {
480                 start = 0;
481                 end = stk->nb_points - 1;
482         }
483
484         sk_allocStrokeBuffer(stk);
485         stk->nb_points = 0;
486         
487         /* adding points before range */
488         for (i = 0; i < start; i++)
489         {
490                 sk_appendStrokePoint(stk, old_points + i);
491         }
492         
493         for (i = start, j = start; i <= end; i++)
494         {
495                 if (i - j == 3)
496                 {
497                         SK_Point pt;
498                         float vec[3];
499                         
500                         pt.type = PT_CONTINUOUS;
501                         pt.p[0] = 0;
502                         pt.p[1] = 0;
503                         pt.p[2] = 0;
504                         
505                         VECCOPY(vec, old_points[j].p);
506                         VecMulf(vec, -0.25);
507                         VecAddf(pt.p, pt.p, vec);
508                         
509                         VECCOPY(vec, old_points[j+1].p);
510                         VecMulf(vec,  0.75);
511                         VecAddf(pt.p, pt.p, vec);
512
513                         VECCOPY(vec, old_points[j+2].p);
514                         VecMulf(vec,  0.75);
515                         VecAddf(pt.p, pt.p, vec);
516
517                         VECCOPY(vec, old_points[j+3].p);
518                         VecMulf(vec, -0.25);
519                         VecAddf(pt.p, pt.p, vec);
520                         
521                         sk_appendStrokePoint(stk, &pt);
522
523                         j += 2;
524                 }
525                 
526                 /* this might be uneeded when filtering last continuous stroke */
527                 if (old_points[i].type == PT_EXACT)
528                 {
529                         sk_appendStrokePoint(stk, old_points + i);
530                         j = i;
531                 }
532         } 
533         
534         /* adding points after range */
535         for (i = end + 1; i < nb_points; i++)
536         {
537                 sk_appendStrokePoint(stk, old_points + i);
538         }
539
540         MEM_freeN(old_points);
541
542         sk_shrinkStrokeBuffer(stk);
543 }
544
545 void sk_filterLastContinuousStroke(SK_Stroke *stk)
546 {
547         int start, end;
548         
549         end = stk->nb_points -1;
550         
551         for (start = end - 1; start > 0 && stk->points[start].type == PT_CONTINUOUS; start--)
552         {
553                 /* nothing to do here*/
554         }
555         
556         if (end - start > 1)
557         {
558                 sk_filterStroke(stk, start, end);
559         }
560 }
561
562 SK_Point *sk_lastStrokePoint(SK_Stroke *stk)
563 {
564         SK_Point *pt = NULL;
565         
566         if (stk->nb_points > 0)
567         {
568                 pt = stk->points + (stk->nb_points - 1);
569         }
570         
571         return pt;
572 }
573
574 void sk_drawStroke(SK_Stroke *stk, int id, float color[3])
575 {
576         float rgb[3];
577         int i;
578         
579         if (id != -1)
580         {
581                 glLoadName(id);
582                 
583                 glBegin(GL_LINE_STRIP);
584                 
585                 for (i = 0; i < stk->nb_points; i++)
586                 {
587                         glVertex3fv(stk->points[i].p);
588                 }
589                 
590                 glEnd();
591                 
592         }
593         else
594         {
595                 float d_rgb[3] = {1, 1, 1};
596                 
597                 VECCOPY(rgb, color);
598                 VecSubf(d_rgb, d_rgb, rgb);
599                 VecMulf(d_rgb, 1.0f / (float)stk->nb_points);
600                 
601                 glBegin(GL_LINE_STRIP);
602
603                 for (i = 0; i < stk->nb_points; i++)
604                 {
605                         glColor3fv(rgb);
606                         glVertex3fv(stk->points[i].p);
607                         VecAddf(rgb, rgb, d_rgb);
608                 }
609                 
610                 glEnd();
611         
612                 glColor3f(0, 0, 0);
613                 glBegin(GL_POINTS);
614         
615                 for (i = 0; i < stk->nb_points; i++)
616                 {
617                         if (stk->points[i].type == PT_EXACT)
618                         {
619                                 glVertex3fv(stk->points[i].p);
620                         }
621                 }
622                 
623                 glEnd();
624         }
625
626 //      glColor3f(1, 1, 1);
627 //      glBegin(GL_POINTS);
628 //
629 //      for (i = 0; i < stk->nb_points; i++)
630 //      {
631 //              if (stk->points[i].type == PT_CONTINUOUS)
632 //              {
633 //                      glVertex3fv(stk->points[i].p);
634 //              }
635 //      }
636 //
637 //      glEnd();
638 }
639
640 SK_Point *sk_snapPointStroke(SK_Stroke *stk, short mval[2], int *dist)
641 {
642         SK_Point *pt = NULL;
643         int i;
644         
645         for (i = 0; i < stk->nb_points; i++)
646         {
647                 if (stk->points[i].type == PT_EXACT)
648                 {
649                         short pval[2];
650                         int pdist;
651                         
652                         project_short_noclip(stk->points[i].p, pval);
653                         
654                         pdist = ABS(pval[0] - mval[0]) + ABS(pval[1] - mval[1]);
655                         
656                         if (pdist < *dist)
657                         {
658                                 *dist = pdist;
659                                 pt = stk->points + i;
660                         }
661                 }
662         }
663         
664         return pt;
665 }
666
667 SK_Point *sk_snapPointArmature(ListBase *ebones, short mval[2], int *dist)
668 {
669         SK_Point *pt = NULL;
670         EditBone *bone;
671         
672         for (bone = ebones->first; bone; bone = bone->next)
673         {
674                 short pval[2];
675                 int pdist;
676                 
677                 if ((bone->flag & BONE_CONNECTED) == 0)
678                 {
679                         project_short_noclip(bone->head, pval);
680                         
681                         pdist = ABS(pval[0] - mval[0]) + ABS(pval[1] - mval[1]);
682                         
683                         if (pdist < *dist)
684                         {
685                                 *dist = pdist;
686                                 pt = &boneSnap;
687                                 VECCOPY(pt->p, bone->head);
688                                 pt->type = PT_EXACT;
689                         }
690                 }
691                 
692                 
693                 project_short_noclip(bone->tail, pval);
694                 
695                 pdist = ABS(pval[0] - mval[0]) + ABS(pval[1] - mval[1]);
696                 
697                 if (pdist < *dist)
698                 {
699                         *dist = pdist;
700                         pt = &boneSnap;
701                         VECCOPY(pt->p, bone->tail);
702                         pt->type = PT_EXACT;
703                 }
704         }
705         
706         return pt;
707 }
708
709 void sk_startStroke(SK_Sketch *sketch)
710 {
711         SK_Stroke *stk = sk_createStroke();
712         
713         BLI_addtail(&sketch->strokes, stk);
714         sketch->active_stroke = stk;
715 }
716
717 void sk_endStroke(SK_Sketch *sketch)
718 {
719         sk_shrinkStrokeBuffer(sketch->active_stroke);
720         sketch->active_stroke = NULL;
721 }
722
723 void sk_updateDrawData(SK_DrawData *dd)
724 {
725         dd->type = PT_CONTINUOUS;
726         
727         dd->previous_mval[0] = dd->mval[0];
728         dd->previous_mval[1] = dd->mval[1];
729 }
730
731 float sk_distanceDepth(float p1[3], float p2[3])
732 {
733         float vec[3];
734         float distance;
735         
736         VecSubf(vec, p1, p2);
737         
738         Projf(vec, vec, G.vd->viewinv[2]);
739         
740         distance = VecLength(vec);
741         
742         if (Inpf(G.vd->viewinv[2], vec) > 0)
743         {
744                 distance *= -1;
745         }
746         
747         return distance; 
748 }
749
750 void sk_interpolateDepth(SK_Stroke *stk, int start, int end, float length, float distance)
751 {
752         float progress = 0;
753         int i;
754         
755         progress = VecLenf(stk->points[start].p, stk->points[start - 1].p);
756         
757         for (i = start; i <= end; i++)
758         {
759                 float ray_start[3], ray_normal[3];
760                 float delta = VecLenf(stk->points[i].p, stk->points[i + 1].p);
761                 short pval[2];
762                 
763                 project_short_noclip(stk->points[i].p, pval);
764                 viewray(pval, ray_start, ray_normal);
765                 
766                 VecMulf(ray_normal, distance * progress / length);
767                 VecAddf(stk->points[i].p, stk->points[i].p, ray_normal);
768
769                 progress += delta ;
770         }
771 }
772
773 void sk_projectDrawPoint(float vec[3], SK_Stroke *stk, SK_DrawData *dd)
774 {
775         /* copied from grease pencil, need fixing */    
776         SK_Point *last = sk_lastStrokePoint(stk);
777         short cval[2];
778         //float *fp = give_cursor();
779         float fp[3] = {0, 0, 0};
780         float dvec[3];
781         
782         if (last != NULL)
783         {
784                 VECCOPY(fp, last->p);
785         }
786         
787         initgrabz(fp[0], fp[1], fp[2]);
788         
789         /* method taken from editview.c - mouse_cursor() */
790         project_short_noclip(fp, cval);
791         window_to_3d(dvec, cval[0] - dd->mval[0], cval[1] - dd->mval[1]);
792         VecSubf(vec, fp, dvec);
793 }
794
795 int sk_getStrokeDrawPoint(SK_Point *pt, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
796 {
797         pt->type = dd->type;
798         pt->mode = PT_PROJECT;
799         sk_projectDrawPoint(pt->p, stk, dd);
800         
801         return 1;
802 }
803
804 int sk_addStrokeDrawPoint(SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
805 {
806         SK_Point pt;
807         
808         sk_getStrokeDrawPoint(&pt, sketch, stk, dd);
809
810         sk_appendStrokePoint(stk, &pt);
811         
812         return 1;
813 }
814
815
816 int sk_getStrokeSnapPoint(SK_Point *pt, SK_Sketch *sketch, SK_Stroke *source_stk, SK_DrawData *dd)
817 {
818         SK_Stroke *stk;
819         int dist = SNAP_MIN_DISTANCE;
820         int point_added = 0;
821         
822         for (stk = sketch->strokes.first; stk; stk = stk->next)
823         {
824                 SK_Point *spt = sk_snapPointStroke(stk, dd->mval, &dist);
825                 
826                 if (spt != NULL)
827                 {
828                         VECCOPY(pt->p, spt->p);
829                         point_added = 1;
830                 }
831         }
832         
833         /* check on bones */
834         {
835                 SK_Point *spt = sk_snapPointArmature(&G.edbo, dd->mval, &dist);
836                 
837                 if (spt != NULL)
838                 {
839                         VECCOPY(pt->p, spt->p);
840                         point_added = 1;
841                 }
842         }
843         
844         if (point_added)
845         {
846                 pt->type = PT_EXACT;
847                 pt->mode = PT_SNAP;
848         }
849         
850         return point_added;
851 }
852
853 int sk_addStrokeSnapPoint(SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
854 {
855         SK_Point pt;
856         int point_added = 0;
857         
858         point_added = sk_getStrokeSnapPoint(&pt, sketch, stk, dd);
859
860         if (point_added)
861         {
862                 float final_p[3];
863                 float distance;
864                 float length;
865                 int i, total;
866                 
867                 VECCOPY(final_p, pt.p);
868
869                 sk_projectDrawPoint(pt.p, stk, dd);
870                 sk_appendStrokePoint(stk, &pt);
871                 
872                 /* update all previous point to give smooth Z progresion */
873                 total = 0;
874                 length = 0;
875                 for (i = stk->nb_points - 2; i > 0; i--)
876                 {
877                         length += VecLenf(stk->points[i].p, stk->points[i + 1].p);
878                         total++;
879                         if (stk->points[i].type == PT_EXACT)
880                         {
881                                 break;
882                         }
883                 }
884                 
885                 if (total > 1)
886                 {
887                         distance = sk_distanceDepth(final_p, stk->points[i].p);
888                         
889                         sk_interpolateDepth(stk, i + 1, stk->nb_points - 2, length, distance);
890                 }
891         
892                 VECCOPY(stk->points[stk->nb_points - 1].p, final_p);
893         }
894         
895         return point_added;
896 }
897
898 int sk_getStrokeEmbedPoint(SK_Point *pt, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
899 {
900         ListBase depth_peels;
901         SK_DepthPeel *p1, *p2;
902         SK_Point *last_pt = NULL;
903         float dist = FLT_MAX;
904         float p[3];
905         int point_added = 0;
906         
907         depth_peels.first = depth_peels.last = NULL;
908         
909         peelObjects(&depth_peels, dd->mval);
910         
911         if (stk->nb_points > 0 && stk->points[stk->nb_points - 1].type == PT_CONTINUOUS)
912         {
913                 last_pt = stk->points + (stk->nb_points - 1);
914         }
915         
916         
917         for (p1 = depth_peels.first; p1; p1 = p1->next)
918         {
919                 if (p1->flag == 0)
920                 {
921                         float vec[3];
922                         float new_dist;
923                         
924                         p1->flag = 0;
925                         
926                         for (p2 = p1->next; p2 && p2->ob != p1->ob; p2 = p2->next)
927                         {
928                                 /* nothing to do here */
929                         }
930                         
931                         
932                         if (p2)
933                         {
934                                 p2->flag = 1;
935                                 
936                                 VecAddf(vec, p1->p, p2->p);
937                                 VecMulf(vec, 0.5f);
938                         }
939                         else
940                         {
941                                 VECCOPY(vec, p1->p);
942                         }
943                         
944                         if (last_pt == NULL)
945                         {
946                                 VECCOPY(p, vec);
947                                 dist = 0;
948                                 break;
949                         }
950                         
951                         new_dist = VecLenf(last_pt->p, vec);
952                         
953                         if (new_dist < dist)
954                         {
955                                 VECCOPY(p, vec);
956                                 dist = new_dist;
957                         }
958                 }
959         }
960         
961         if (dist != FLT_MAX)
962         {
963                 pt->type = dd->type;
964                 pt->mode = PT_EMBED;
965                 VECCOPY(pt->p, p);
966                 
967                 point_added = 1;
968         }
969         
970         BLI_freelistN(&depth_peels);
971         
972         return point_added;
973 }
974
975 int sk_addStrokeEmbedPoint(SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
976 {
977         SK_Point pt;
978         int point_added;
979         
980         point_added = sk_getStrokeEmbedPoint(&pt, sketch, stk, dd);
981         
982         if (point_added)
983         {
984                 float final_p[3];
985                 float length, distance;
986                 int total;
987                 int i;
988                 
989                 VECCOPY(final_p, pt.p);
990                 
991                 sk_projectDrawPoint(pt.p, stk, dd);
992                 sk_appendStrokePoint(stk, &pt);
993                 
994                 /* update all previous point to give smooth Z progresion */
995                 total = 0;
996                 length = 0;
997                 for (i = stk->nb_points - 2; i > 0; i--)
998                 {
999                         length += VecLenf(stk->points[i].p, stk->points[i + 1].p);
1000                         total++;
1001                         if (stk->points[i].mode == PT_EMBED || stk->points[i].type == PT_EXACT)
1002                         {
1003                                 break;
1004                         }
1005                 }
1006                 
1007                 if (total > 1)
1008                 {
1009                         distance = sk_distanceDepth(final_p, stk->points[i].p);
1010                         
1011                         sk_interpolateDepth(stk, i + 1, stk->nb_points - 2, length, distance);
1012                 }
1013                 
1014                 VECCOPY(stk->points[stk->nb_points - 1].p, final_p);
1015                 
1016                 point_added = 1;
1017         }
1018         
1019         return point_added;
1020 }
1021
1022 void sk_addStrokePoint(SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd, short qual)
1023 {
1024         int point_added = 0;
1025         
1026         if (qual & LR_CTRLKEY)
1027         {
1028                 point_added = sk_addStrokeSnapPoint(sketch, stk, dd);
1029         }
1030         
1031         if (point_added == 0 && qual & LR_SHIFTKEY)
1032         {
1033                 point_added = sk_addStrokeEmbedPoint(sketch, stk, dd);
1034         }
1035         
1036         if (point_added == 0)
1037         {
1038                 point_added = sk_addStrokeDrawPoint(sketch, stk, dd);
1039         }       
1040 }
1041
1042 void sk_getStrokePoint(SK_Point *pt, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd, short qual)
1043 {
1044         int point_added = 0;
1045         
1046         if (qual & LR_CTRLKEY)
1047         {
1048                 point_added = sk_getStrokeSnapPoint(pt, sketch, stk, dd);
1049         }
1050         
1051         if (point_added == 0 && qual & LR_SHIFTKEY)
1052         {
1053                 point_added = sk_getStrokeEmbedPoint(pt, sketch, stk, dd);
1054         }
1055         
1056         if (point_added == 0)
1057         {
1058                 point_added = sk_getStrokeDrawPoint(pt, sketch, stk, dd);
1059         }       
1060 }
1061
1062 void sk_endContinuousStroke(SK_Stroke *stk)
1063 {
1064         stk->points[stk->nb_points - 1].type = PT_EXACT;
1065 }
1066
1067 void sk_updateNextPoint(SK_Sketch *sketch)
1068 {
1069         if (sketch->active_stroke)
1070         {
1071                 SK_Stroke *stk = sketch->active_stroke;
1072                 memcpy(&sketch->next_point, stk->points[stk->nb_points - 1].p, sizeof(SK_Point));
1073         }
1074 }
1075
1076 int sk_stroke_filtermval(SK_DrawData *dd)
1077 {
1078         int retval = 0;
1079         if (dd->mval[0] != dd->previous_mval[0] || dd->mval[1] != dd->previous_mval[1])
1080         {
1081                 retval = 1;
1082         }
1083         
1084         return retval;
1085 }
1086
1087 void sk_initDrawData(SK_DrawData *dd)
1088 {
1089         getmouseco_areawin(dd->mval);
1090         dd->previous_mval[0] = -1;
1091         dd->previous_mval[1] = -1;
1092         dd->type = PT_EXACT;
1093 }
1094 /********************************************/
1095
1096 float calcStrokeCorrelation(SK_Stroke *stk, int start, int end, float v0[3], float n[3])
1097 {
1098         int len = 2 + abs(end - start);
1099         
1100         if (len > 2)
1101         {
1102                 float avg_t = 0.0f;
1103                 float s_t = 0.0f;
1104                 float s_xyz = 0.0f;
1105                 int i;
1106                 
1107                 /* First pass, calculate average */
1108                 for (i = start; i <= end; i++)
1109                 {
1110                         float v[3];
1111                         
1112                         VecSubf(v, stk->points[i].p, v0);
1113                         avg_t += Inpf(v, n);
1114                 }
1115                 
1116                 avg_t /= Inpf(n, n);
1117                 avg_t += 1.0f; /* adding start (0) and end (1) values */
1118                 avg_t /= len;
1119                 
1120                 /* Second pass, calculate s_xyz and s_t */
1121                 for (i = start; i <= end; i++)
1122                 {
1123                         float v[3], d[3];
1124                         float dt;
1125                         
1126                         VecSubf(v, stk->points[i].p, v0);
1127                         Projf(d, v, n);
1128                         VecSubf(v, v, d);
1129                         
1130                         dt = VecLength(d) - avg_t;
1131                         
1132                         s_t += dt * dt;
1133                         s_xyz += Inpf(v, v);
1134                 }
1135                 
1136                 /* adding start(0) and end(1) values to s_t */
1137                 s_t += (avg_t * avg_t) + (1 - avg_t) * (1 - avg_t);
1138                 
1139                 return 1.0f - s_xyz / s_t; 
1140         }
1141         else
1142         {
1143                 return 1.0f;
1144         }
1145 }
1146
1147 EditBone * subdivideStrokeByCorrelation(SK_Stroke *stk, int start, int end, float invmat[][4])
1148 {
1149         bArmature *arm= G.obedit->data;
1150         EditBone *lastBone = NULL;
1151         float n[3];
1152         float CORRELATION_THRESHOLD = G.scene->toolsettings->skgen_correlation_limit;
1153         
1154         if (G.scene->toolsettings->skgen_options & SKGEN_CUT_CORRELATION)
1155         {
1156                 EditBone *child = NULL;
1157                 EditBone *parent = NULL;
1158                 int boneStart = start;
1159                 int i;
1160
1161                 parent = addEditBone("Bone", &G.edbo, arm);
1162                 VECCOPY(parent->head, stk->points[start].p);
1163                 Mat4MulVecfl(invmat, parent->head);
1164                 
1165                 for (i = start + 1; i < end; i++)
1166                 {
1167                         /* Calculate normal */
1168                         VecSubf(n, stk->points[i].p, parent->head);
1169
1170                         if (calcStrokeCorrelation(stk, boneStart, i, parent->head, n) < CORRELATION_THRESHOLD)
1171                         {
1172                                 VECCOPY(parent->tail, stk->points[i - 1].p);
1173                                 Mat4MulVecfl(invmat, parent->tail);
1174
1175                                 child = addEditBone("Bone", &G.edbo, arm);
1176                                 VECCOPY(child->head, parent->tail);
1177                                 child->parent = parent;
1178                                 child->flag |= BONE_CONNECTED;
1179                                 
1180                                 parent = child; // new child is next parent
1181                                 boneStart = i; // start next bone from current index
1182                         }
1183                 }
1184
1185                 VECCOPY(parent->tail, stk->points[end].p);
1186                 Mat4MulVecfl(invmat, parent->tail);
1187                 lastBone = parent;
1188         }
1189         
1190         return lastBone;
1191 }
1192
1193 EditBone * subdivideStrokeByLength(SK_Stroke *stk, int start, int end, float invmat[][4])
1194 {
1195         bArmature *arm= G.obedit->data;
1196         EditBone *lastBone = NULL;
1197         
1198         if (G.scene->toolsettings->skgen_options & SKGEN_CUT_LENGTH)
1199         {
1200                 EditBone *child = NULL;
1201                 EditBone *parent = NULL;
1202                 float lengthLimit = G.scene->toolsettings->skgen_length_limit;
1203                 int i;
1204                 int same = 0;
1205                 
1206                 parent = addEditBone("Bone", &G.edbo, arm);
1207                 VECCOPY(parent->head, stk->points[start].p);
1208
1209                 i = start + 1;
1210                 while (i < end)
1211                 {
1212                         float *vec0 = stk->points[i - 1].p;
1213                         float *vec1 = stk->points[i].p;
1214
1215                         /* If lengthLimit hits the current segment */
1216                         if (VecLenf(vec1, parent->head) > lengthLimit)
1217                         {
1218                                 if (same == 0)
1219                                 {
1220                                         float dv[3], off[3];
1221                                         float a, b, c, f;
1222                                         
1223                                         /* Solve quadratic distance equation */
1224                                         VecSubf(dv, vec1, vec0);
1225                                         a = Inpf(dv, dv);
1226                                         
1227                                         VecSubf(off, vec0, parent->head);
1228                                         b = 2 * Inpf(dv, off);
1229                                         
1230                                         c = Inpf(off, off) - (lengthLimit * lengthLimit);
1231                                         
1232                                         f = (-b + (float)sqrt(b * b - 4 * a * c)) / (2 * a);
1233                                         
1234                                         //printf("a %f, b %f, c %f, f %f\n", a, b, c, f);
1235                                         
1236                                         if (isnan(f) == 0 && f < 1.0f)
1237                                         {
1238                                                 VECCOPY(parent->tail, dv);
1239                                                 VecMulf(parent->tail, f);
1240                                                 VecAddf(parent->tail, parent->tail, vec0);
1241                                         }
1242                                         else
1243                                         {
1244                                                 VECCOPY(parent->tail, vec1);
1245                                         }
1246                                 }
1247                                 else
1248                                 {
1249                                         float dv[3];
1250                                         
1251                                         VecSubf(dv, vec1, vec0);
1252                                         Normalize(dv);
1253                                          
1254                                         VECCOPY(parent->tail, dv);
1255                                         VecMulf(parent->tail, lengthLimit);
1256                                         VecAddf(parent->tail, parent->tail, parent->head);
1257                                 }
1258                                 
1259                                 /* put head in correct space */
1260                                 Mat4MulVecfl(invmat, parent->head);
1261                                 
1262                                 child = addEditBone("Bone", &G.edbo, arm);
1263                                 VECCOPY(child->head, parent->tail);
1264                                 child->parent = parent;
1265                                 child->flag |= BONE_CONNECTED;
1266                                 
1267                                 parent = child; // new child is next parent
1268                                 
1269                                 same = 1; // mark as same
1270                         }
1271                         else
1272                         {
1273                                 i++;
1274                                 same = 0; // Reset same
1275                         }
1276                 }
1277                 VECCOPY(parent->tail, stk->points[end].p);
1278                 Mat4MulVecfl(invmat, parent->tail);
1279                 lastBone = parent;
1280         }
1281         
1282         return lastBone;
1283 }
1284
1285 void sk_convertStroke(SK_Stroke *stk)
1286 {
1287         bArmature *arm= G.obedit->data;
1288         SK_Point *head;
1289         EditBone *parent = NULL;
1290         float invmat[4][4]; /* move in caller function */
1291         int head_index = 0;
1292         int i;
1293         
1294         head = NULL;
1295         
1296         Mat4Invert(invmat, G.obedit->obmat);
1297         
1298         for (i = 0; i < stk->nb_points; i++)
1299         {
1300                 SK_Point *pt = stk->points + i;
1301                 
1302                 if (pt->type == PT_EXACT)
1303                 {
1304                         if (head == NULL)
1305                         {
1306                                 head_index = i;
1307                                 head = pt;
1308                         }
1309                         else
1310                         {
1311                                 EditBone *bone = NULL;
1312                                 EditBone *new_parent;
1313                                 
1314                                 if (i - head_index > 1)
1315                                 {
1316                                         bone = subdivideStrokeByCorrelation(stk, head_index, i, invmat);
1317                                         
1318                                         if (bone == NULL)
1319                                         {
1320                                                 bone = subdivideStrokeByLength(stk, head_index, i, invmat);
1321                                         }
1322                                 }
1323                                 
1324                                 if (bone == NULL)
1325                                 {
1326                                         bone = addEditBone("Bone", &G.edbo, arm);
1327                                         
1328                                         VECCOPY(bone->head, head->p);
1329                                         VECCOPY(bone->tail, pt->p);
1330                                         
1331                                         Mat4MulVecfl(invmat, bone->head);
1332                                         Mat4MulVecfl(invmat, bone->tail);
1333                                 }
1334                                 
1335                                 new_parent = bone;
1336                                 bone->flag |= BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
1337                                 
1338                                 /* move to end of chain */
1339                                 while (bone->parent != NULL)
1340                                 {
1341                                         bone = bone->parent;
1342                                         bone->flag |= BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
1343                                 }
1344
1345                                 if (parent != NULL)
1346                                 {
1347                                         bone->parent = parent;
1348                                         bone->flag |= BONE_CONNECTED;                                   
1349                                 }
1350                                 
1351                                 parent = new_parent;
1352                                 head_index = i;
1353                                 head = pt;
1354                         }
1355                 }
1356         }
1357 }
1358
1359 void sk_convert(SK_Sketch *sketch)
1360 {
1361         SK_Stroke *stk;
1362         
1363         for (stk = sketch->strokes.first; stk; stk = stk->next)
1364         {
1365                 if (stk->selected == 1)
1366                 {
1367                         sk_convertStroke(stk);
1368                 }
1369         }
1370 }
1371 /******************* GESTURE *************************/
1372
1373
1374 /* returns the number of self intersections */
1375 int sk_getSelfIntersections(ListBase *list, SK_Stroke *gesture)
1376 {
1377         int added = 0;
1378         int s_i;
1379
1380         for (s_i = 0; s_i < gesture->nb_points - 1; s_i++)
1381         {
1382                 float s_p1[3] = {0, 0, 0};
1383                 float s_p2[3] = {0, 0, 0};
1384                 int g_i;
1385                 
1386                 project_float(gesture->points[s_i].p, s_p1);
1387                 project_float(gesture->points[s_i + 1].p, s_p2);
1388
1389                 /* start checking from second next, because two consecutive cannot intersect */
1390                 for (g_i = s_i + 2; g_i < gesture->nb_points - 1; g_i++)
1391                 {
1392                         float g_p1[3] = {0, 0, 0};
1393                         float g_p2[3] = {0, 0, 0};
1394                         float vi[3];
1395                         float lambda;
1396                         
1397                         project_float(gesture->points[g_i].p, g_p1);
1398                         project_float(gesture->points[g_i + 1].p, g_p2);
1399                         
1400                         if (LineIntersectLineStrict(s_p1, s_p2, g_p1, g_p2, vi, &lambda))
1401                         {
1402                                 SK_Intersection *isect = MEM_callocN(sizeof(SK_Intersection), "Intersection");
1403                                 
1404                                 isect->start = s_i;
1405                                 isect->end = g_i + 1;
1406                                 isect->stroke = gesture;
1407                                 
1408                                 VecSubf(isect->p, gesture->points[s_i + 1].p, gesture->points[s_i].p);
1409                                 VecMulf(isect->p, lambda);
1410                                 VecAddf(isect->p, isect->p, gesture->points[s_i].p);
1411                                 
1412                                 BLI_addtail(list, isect);
1413
1414                                 added++;
1415                         }
1416                 }
1417         }
1418         
1419         return added;
1420 }
1421
1422
1423 /* returns the maximum number of intersections per stroke */
1424 int sk_getIntersections(ListBase *list, SK_Sketch *sketch, SK_Stroke *gesture)
1425 {
1426         SK_Stroke *stk;
1427         int added = 0;
1428
1429         for (stk = sketch->strokes.first; stk; stk = stk->next)
1430         {
1431                 int s_added = 0;
1432                 int s_i;
1433                 
1434                 for (s_i = 0; s_i < stk->nb_points - 1; s_i++)
1435                 {
1436                         float s_p1[3] = {0, 0, 0};
1437                         float s_p2[3] = {0, 0, 0};
1438                         int g_i;
1439                         
1440                         project_float(stk->points[s_i].p, s_p1);
1441                         project_float(stk->points[s_i + 1].p, s_p2);
1442
1443                         for (g_i = 0; g_i < gesture->nb_points - 1; g_i++)
1444                         {
1445                                 float g_p1[3] = {0, 0, 0};
1446                                 float g_p2[3] = {0, 0, 0};
1447                                 float vi[3];
1448                                 float lambda;
1449                                 
1450                                 project_float(gesture->points[g_i].p, g_p1);
1451                                 project_float(gesture->points[g_i + 1].p, g_p2);
1452                                 
1453                                 if (LineIntersectLineStrict(s_p1, s_p2, g_p1, g_p2, vi, &lambda))
1454                                 {
1455                                         SK_Intersection *isect = MEM_callocN(sizeof(SK_Intersection), "Intersection");
1456                                         float ray_start[3], ray_end[3];
1457                                         short mval[2];
1458                                         
1459                                         isect->start = s_i;
1460                                         isect->end = s_i + 1;
1461                                         isect->stroke = stk;
1462                                         
1463                                         mval[0] = (short)(vi[0]);
1464                                         mval[1] = (short)(vi[1]);
1465                                         viewline(mval, ray_start, ray_end);
1466                                         
1467                                         LineIntersectLine(      stk->points[s_i].p,
1468                                                                                 stk->points[s_i + 1].p,
1469                                                                                 ray_start,
1470                                                                                 ray_end,
1471                                                                                 isect->p,
1472                                                                                 vi);
1473                                         
1474                                         BLI_addtail(list, isect);
1475
1476                                         s_added++;
1477                                 }
1478                         }
1479                 }
1480                 
1481                 added = MAX2(s_added, added);
1482         }
1483         
1484         
1485         return added;
1486 }
1487
1488 int sk_getSegments(SK_Stroke *segments, SK_Stroke *gesture)
1489 {
1490         float CORRELATION_THRESHOLD = 0.995f;
1491         float *vec;
1492         int i, j;
1493         
1494         sk_appendStrokePoint(segments, &gesture->points[0]);
1495         vec = segments->points[segments->nb_points - 1].p;
1496
1497         for (i = 1, j = 0; i < gesture->nb_points; i++)
1498         { 
1499                 float n[3];
1500                 
1501                 /* Calculate normal */
1502                 VecSubf(n, gesture->points[i].p, vec);
1503                 
1504                 if (calcStrokeCorrelation(gesture, j, i, vec, n) < CORRELATION_THRESHOLD)
1505                 {
1506                         j = i - 1;
1507                         sk_appendStrokePoint(segments, &gesture->points[j]);
1508                         vec = segments->points[segments->nb_points - 1].p;
1509                         segments->points[segments->nb_points - 1].type = PT_EXACT;
1510                 }
1511         }
1512
1513         sk_appendStrokePoint(segments, &gesture->points[gesture->nb_points - 1]);
1514         
1515         return segments->nb_points - 1;
1516 }
1517
1518 void sk_applyCutGesture(SK_Sketch *sketch, SK_Stroke *gesture, ListBase *list, SK_Stroke *segments)
1519 {
1520         SK_Intersection *isect;
1521         
1522         for (isect = list->first; isect; isect = isect->next)
1523         {
1524                 SK_Point pt;
1525                 
1526                 pt.type = PT_EXACT;
1527                 pt.mode = PT_PROJECT; /* take mode from neighbouring points */
1528                 VECCOPY(pt.p, isect->p);
1529                 
1530                 sk_insertStrokePoint(isect->stroke, &pt, isect->end);
1531         }
1532 }
1533
1534 int sk_detectTrimGesture(SK_Sketch *sketch, SK_Stroke *gesture, ListBase *list, SK_Stroke *segments)
1535 {
1536         float s1[3], s2[3];
1537         float angle;
1538         
1539         VecSubf(s1, segments->points[1].p, segments->points[0].p);
1540         VecSubf(s2, segments->points[2].p, segments->points[1].p);
1541         
1542         angle = VecAngle2(s1, s2);
1543         
1544         if (angle > 60 && angle < 120)
1545         {
1546                 return 1;
1547         }
1548         else
1549         {
1550                 return 0;
1551         }
1552 }
1553
1554 void sk_applyTrimGesture(SK_Sketch *sketch, SK_Stroke *gesture, ListBase *list, SK_Stroke *segments)
1555 {
1556         SK_Intersection *isect;
1557         float trim_dir[3];
1558         
1559         VecSubf(trim_dir, segments->points[2].p, segments->points[1].p);
1560         
1561         for (isect = list->first; isect; isect = isect->next)
1562         {
1563                 SK_Point pt;
1564                 float stroke_dir[3];
1565                 
1566                 pt.type = PT_EXACT;
1567                 pt.mode = PT_PROJECT; /* take mode from neighbouring points */
1568                 VECCOPY(pt.p, isect->p);
1569                 
1570                 VecSubf(stroke_dir, isect->stroke->points[isect->end].p, isect->stroke->points[isect->start].p);
1571                 
1572                 /* same direction, trim end */
1573                 if (Inpf(stroke_dir, trim_dir) > 0)
1574                 {
1575                         sk_replaceStrokePoint(isect->stroke, &pt, isect->end);
1576                         sk_trimStroke(isect->stroke, 0, isect->end);
1577                 }
1578                 /* else, trim start */
1579                 else
1580                 {
1581                         sk_replaceStrokePoint(isect->stroke, &pt, isect->start);
1582                         sk_trimStroke(isect->stroke, isect->start, isect->stroke->nb_points - 1);
1583                 }
1584         
1585         }
1586 }
1587
1588 int sk_detectDeleteGesture(SK_Sketch *sketch, SK_Stroke *gesture, ListBase *list, SK_Stroke *segments)
1589 {
1590         float s1[3], s2[3];
1591         float angle;
1592         
1593         VecSubf(s1, segments->points[1].p, segments->points[0].p);
1594         VecSubf(s2, segments->points[2].p, segments->points[1].p);
1595         
1596         angle = VecAngle2(s1, s2);
1597         
1598         if (angle > 120)
1599         {
1600                 return 1;
1601         }
1602         else
1603         {
1604                 return 0;
1605         }
1606 }
1607
1608 void sk_applyDeleteGesture(SK_Sketch *sketch, SK_Stroke *gesture, ListBase *list, SK_Stroke *segments)
1609 {
1610         SK_Intersection *isect;
1611         
1612         for (isect = list->first; isect; isect = isect->next)
1613         {
1614                 /* only delete strokes that are crossed twice */
1615                 if (isect->next && isect->next->stroke == isect->stroke)
1616                 {
1617                         isect = isect->next;
1618                         
1619                         BLI_remlink(&sketch->strokes, isect->stroke);
1620                         sk_freeStroke(isect->stroke);
1621                 }
1622         }
1623 }
1624
1625 int sk_detectMergeGesture(SK_Sketch *sketch, SK_Stroke *gesture, ListBase *list, SK_Stroke *segments)
1626 {
1627         short start_val[2], end_val[2];
1628         short dist;
1629         
1630         project_short_noclip(gesture->points[0].p, start_val);
1631         project_short_noclip(gesture->points[gesture->nb_points - 1].p, end_val);
1632         
1633         dist = MAX2(ABS(start_val[0] - end_val[0]), ABS(start_val[1] - end_val[1]));
1634         
1635         /* if gesture is a circle */
1636         if ( dist <= 20 )
1637         {
1638                 SK_Intersection *isect;
1639                 
1640                 /* check if it circled around an exact point */
1641                 for (isect = list->first; isect; isect = isect->next)
1642                 {
1643                         /* only delete strokes that are crossed twice */
1644                         if (isect->next && isect->next->stroke == isect->stroke)
1645                         {
1646                                 int start_index, end_index;
1647                                 int i;
1648                                 
1649                                 start_index = MIN2(isect->end, isect->next->end);
1650                                 end_index = MAX2(isect->start, isect->next->start);
1651
1652                                 for (i = start_index; i <= end_index; i++)
1653                                 {
1654                                         if (isect->stroke->points[i].type == PT_EXACT)
1655                                         {
1656                                                 return 1; /* at least one exact point found, stop detect here */
1657                                         }
1658                                 }
1659
1660                                 /* skip next */                         
1661                                 isect = isect->next;
1662                         }
1663                 }
1664                         
1665                 return 0;
1666         }
1667         else
1668         {
1669                 return 0;
1670         }
1671 }
1672
1673 void sk_applyMergeGesture(SK_Sketch *sketch, SK_Stroke *gesture, ListBase *list, SK_Stroke *segments)
1674 {
1675         SK_Intersection *isect;
1676         
1677         /* check if it circled around an exact point */
1678         for (isect = list->first; isect; isect = isect->next)
1679         {
1680                 /* only delete strokes that are crossed twice */
1681                 if (isect->next && isect->next->stroke == isect->stroke)
1682                 {
1683                         int start_index, end_index;
1684                         int i;
1685                         
1686                         start_index = MIN2(isect->end, isect->next->end);
1687                         end_index = MAX2(isect->start, isect->next->start);
1688
1689                         for (i = start_index; i <= end_index; i++)
1690                         {
1691                                 /* if exact, switch to continuous */
1692                                 if (isect->stroke->points[i].type == PT_EXACT)
1693                                 {
1694                                         isect->stroke->points[i].type = PT_CONTINUOUS;
1695                                 }
1696                         }
1697
1698                         /* skip next */                         
1699                         isect = isect->next;
1700                 }
1701         }
1702 }
1703
1704 void sk_applyGesture(SK_Sketch *sketch)
1705 {
1706         ListBase intersections;
1707         ListBase self_intersections;
1708         SK_Stroke *segments = sk_createStroke();
1709         int nb_self_intersections, nb_intersections, nb_segments;
1710         
1711         intersections.first = intersections.last = NULL;
1712         self_intersections.first = self_intersections.last = NULL;
1713         
1714         nb_self_intersections = sk_getSelfIntersections(&self_intersections, sketch->gesture);
1715         nb_intersections = sk_getIntersections(&intersections, sketch, sketch->gesture);
1716         nb_segments = sk_getSegments(segments, sketch->gesture);
1717         
1718         /* detect and apply */
1719         if (nb_segments == 1 && nb_intersections == 1)
1720         {
1721                 sk_applyCutGesture(sketch, sketch->gesture, &intersections, segments);
1722         }
1723         else if (nb_segments == 2 && nb_intersections == 1 && sk_detectTrimGesture(sketch, sketch->gesture, &intersections, segments))
1724         {
1725                 sk_applyTrimGesture(sketch, sketch->gesture, &intersections, segments);
1726         }
1727         else if (nb_segments == 2 && nb_intersections == 2 && sk_detectDeleteGesture(sketch, sketch->gesture, &intersections, segments))
1728         {
1729                 sk_applyDeleteGesture(sketch, sketch->gesture, &intersections, segments);
1730         }
1731         else if (nb_segments > 2 && nb_intersections == 2 && sk_detectMergeGesture(sketch, sketch->gesture, &intersections, segments))
1732         {
1733                 sk_applyMergeGesture(sketch, sketch->gesture, &intersections, segments);
1734         }
1735         else if (nb_segments > 2 && nb_self_intersections == 1)
1736         {
1737                 sk_convert(sketch);
1738                 BIF_undo_push("Convert Sketch");
1739                 allqueue(REDRAWBUTSEDIT, 0);
1740         }
1741         
1742         sk_freeStroke(segments);
1743         BLI_freelistN(&intersections);
1744         BLI_freelistN(&self_intersections);
1745 }
1746
1747 /********************************************/
1748
1749 void sk_deleteStrokes(SK_Sketch *sketch)
1750 {
1751         SK_Stroke *stk, *next;
1752         
1753         for (stk = sketch->strokes.first; stk; stk = next)
1754         {
1755                 next = stk->next;
1756                 
1757                 if (stk->selected == 1)
1758                 {
1759                         BLI_remlink(&sketch->strokes, stk);
1760                         sk_freeStroke(stk);
1761                 }
1762         }
1763 }
1764
1765 void sk_selectAllSketch(SK_Sketch *sketch, int mode)
1766 {
1767         SK_Stroke *stk = NULL;
1768         
1769         if (mode == -1)
1770         {
1771                 for (stk = sketch->strokes.first; stk; stk = stk->next)
1772                 {
1773                         stk->selected = 0;
1774                 }
1775         }
1776         else if (mode == 0)
1777         {
1778                 for (stk = sketch->strokes.first; stk; stk = stk->next)
1779                 {
1780                         stk->selected = 1;
1781                 }
1782         }
1783         else if (mode == 1)
1784         {
1785                 int selected = 1;
1786                 
1787                 for (stk = sketch->strokes.first; stk; stk = stk->next)
1788                 {
1789                         selected &= stk->selected;
1790                 }
1791                 
1792                 selected ^= 1;
1793
1794                 for (stk = sketch->strokes.first; stk; stk = stk->next)
1795                 {
1796                         stk->selected = selected;
1797                 }
1798         }
1799 }
1800
1801 void sk_selectStroke(SK_Sketch *sketch)
1802 {
1803         unsigned int buffer[MAXPICKBUF];
1804         short hits, mval[2];
1805
1806         persp(PERSP_VIEW);
1807
1808         getmouseco_areawin(mval);
1809         hits = view3d_opengl_select(buffer, MAXPICKBUF, mval[0]-5, mval[1]-5, mval[0]+5, mval[1]+5);
1810         if(hits==0)
1811                 hits = view3d_opengl_select(buffer, MAXPICKBUF, mval[0]-12, mval[1]-12, mval[0]+12, mval[1]+12);
1812                 
1813         if (hits>0)
1814         {
1815                 int besthitresult = -1;
1816                         
1817                 if(hits == 1) {
1818                         besthitresult = buffer[3];
1819                 }
1820                 else {
1821                         besthitresult = buffer[3];
1822                         /* loop and get best hit */
1823                 }
1824                 
1825                 if (besthitresult > 0)
1826                 {
1827                         SK_Stroke *selected_stk = BLI_findlink(&sketch->strokes, besthitresult - 1);
1828                         
1829                         if ((G.qual & LR_SHIFTKEY) == 0)
1830                         {
1831                                 sk_selectAllSketch(sketch, -1);
1832                                 
1833                                 selected_stk->selected = 1;
1834                         }
1835                         else
1836                         {
1837                                 selected_stk->selected ^= 1;
1838                         }
1839                         
1840                         
1841                 }
1842         }
1843 }
1844
1845 void sk_queueRedrawSketch(SK_Sketch *sketch)
1846 {
1847         if (sketch->active_stroke != NULL)
1848         {
1849                 SK_Point *last = sk_lastStrokePoint(sketch->active_stroke);
1850                 
1851                 if (last != NULL)
1852                 {
1853                         allqueue(REDRAWVIEW3D, 0);
1854                 }
1855         }
1856 }
1857
1858 void sk_drawSketch(SK_Sketch *sketch, int with_names)
1859 {
1860         SK_Stroke *stk;
1861         
1862         glDisable(GL_DEPTH_TEST);
1863
1864         glLineWidth(BIF_GetThemeValuef(TH_VERTEX_SIZE));
1865         glPointSize(BIF_GetThemeValuef(TH_VERTEX_SIZE));
1866         
1867         if (with_names)
1868         {
1869                 int id;
1870                 for (id = 1, stk = sketch->strokes.first; stk; id++, stk = stk->next)
1871                 {
1872                         sk_drawStroke(stk, id, NULL);
1873                 }
1874                 
1875                 glLoadName(-1);
1876         }
1877         else
1878         {
1879                 float selected_rgb[3] = {1, 0, 0};
1880                 float unselected_rgb[3] = {1, 0.5, 0};
1881                 
1882                 for (stk = sketch->strokes.first; stk; stk = stk->next)
1883                 {
1884                         sk_drawStroke(stk, -1, (stk->selected==1?selected_rgb:unselected_rgb));
1885                 }
1886         
1887                 /* only draw gesture in active area */
1888                 if (sketch->gesture != NULL && area_is_active_area(G.vd->area))
1889                 {
1890                         float gesture_rgb[3] = {0, 0.5, 1};
1891                         sk_drawStroke(sketch->gesture, -1, gesture_rgb);
1892                 }
1893                 
1894                 if (sketch->active_stroke != NULL)
1895                 {
1896                         SK_Point *last = sk_lastStrokePoint(sketch->active_stroke);
1897                         
1898                         if (last != NULL)
1899                         {
1900                                 /* update point if in active area */
1901                                 if (area_is_active_area(G.vd->area))
1902                                 {
1903                                         SK_DrawData dd;
1904                                         
1905                                         sk_initDrawData(&dd);
1906                                         sk_getStrokePoint(&sketch->next_point, sketch, sketch->active_stroke, &dd, G.qual);
1907                                 }
1908                                 
1909                                 glEnable(GL_LINE_STIPPLE);
1910                                 glColor3f(1, 0.5, 0);
1911                                 glBegin(GL_LINE_STRIP);
1912                                 
1913                                         glVertex3fv(last->p);
1914                                         glVertex3fv(sketch->next_point.p);
1915                                 
1916                                 glEnd();
1917                                 
1918                                 glDisable(GL_LINE_STIPPLE);
1919         
1920                                 switch (sketch->next_point.mode)
1921                                 {
1922                                         case PT_SNAP:
1923                                                 glColor3f(0, 0.5, 1);
1924                                                 break;
1925                                         case PT_EMBED:
1926                                                 glColor3f(0, 1, 0);
1927                                                 break;
1928                                         case PT_PROJECT:
1929                                                 glColor3f(0, 0, 0);
1930                                                 break;
1931                                 }
1932                                 
1933                                 glBegin(GL_POINTS);
1934                                 
1935                                         glVertex3fv(sketch->next_point.p);
1936                                 
1937                                 glEnd();
1938                         }
1939                 }
1940         }
1941         
1942         glLineWidth(1.0);
1943         glPointSize(1.0);
1944
1945         glEnable(GL_DEPTH_TEST);
1946 }
1947
1948 int sk_paint(SK_Sketch *sketch, short mbut)
1949 {
1950         int retval = 1;
1951         
1952         if (mbut == LEFTMOUSE)
1953         {
1954                 SK_DrawData dd;
1955                 if (sketch->active_stroke == NULL)
1956                 {
1957                         sk_startStroke(sketch);
1958                 }
1959
1960                 sk_initDrawData(&dd);
1961                 
1962                 /* paint loop */
1963                 do {
1964                         /* get current user input */
1965                         getmouseco_areawin(dd.mval);
1966                         
1967                         /* only add current point to buffer if mouse moved (otherwise wait until it does) */
1968                         if (sk_stroke_filtermval(&dd)) {
1969
1970                                 sk_addStrokePoint(sketch, sketch->active_stroke, &dd, G.qual);
1971                                 sk_updateDrawData(&dd);
1972                                 force_draw(0);
1973                         }
1974                         else
1975                         {
1976                                 BIF_wait_for_statechange();
1977                         }
1978                         
1979                         while( qtest() ) {
1980                                 short event, val;
1981                                 event = extern_qread(&val);
1982                         }
1983                         
1984                         /* do mouse checking at the end, so don't check twice, and potentially
1985                          * miss a short tap 
1986                          */
1987                 } while (get_mbut() & L_MOUSE);
1988                 
1989                 sk_endContinuousStroke(sketch->active_stroke);
1990                 sk_filterLastContinuousStroke(sketch->active_stroke);
1991                 sk_updateNextPoint(sketch);
1992         }
1993         else if (mbut == RIGHTMOUSE)
1994         {
1995                 if (sketch->active_stroke != NULL)
1996                 {
1997                         sk_endStroke(sketch);
1998                         allqueue(REDRAWVIEW3D, 0);
1999                 }
2000                 else
2001                 {
2002                         SK_DrawData dd;
2003                         sketch->gesture = sk_createStroke();
2004         
2005                         sk_initDrawData(&dd);
2006                         
2007                         /* paint loop */
2008                         do {
2009                                 /* get current user input */
2010                                 getmouseco_areawin(dd.mval);
2011                                 
2012                                 /* only add current point to buffer if mouse moved (otherwise wait until it does) */
2013                                 if (sk_stroke_filtermval(&dd)) {
2014
2015                                         sk_addStrokeDrawPoint(sketch, sketch->gesture, &dd);
2016                                         sk_updateDrawData(&dd);
2017                                         
2018                                         /* draw only if mouse has moved */
2019                                         if (sketch->gesture->nb_points > 1)
2020                                         {
2021                                                 force_draw(0);
2022                                         }
2023                                 }
2024                                 else
2025                                 {
2026                                         BIF_wait_for_statechange();
2027                                 }
2028                                 
2029                                 while( qtest() ) {
2030                                         short event, val;
2031                                         event = extern_qread(&val);
2032                                 }
2033                                 
2034                                 /* do mouse checking at the end, so don't check twice, and potentially
2035                                  * miss a short tap 
2036                                  */
2037                         } while (get_mbut() & R_MOUSE);
2038                         
2039                         sk_endContinuousStroke(sketch->gesture);
2040                         sk_filterLastContinuousStroke(sketch->gesture);
2041                         sk_filterLastContinuousStroke(sketch->gesture);
2042                         sk_filterLastContinuousStroke(sketch->gesture);
2043         
2044                         if (sketch->gesture->nb_points == 1)            
2045                         {
2046                                 sk_selectStroke(sketch);
2047                         }
2048                         else
2049                         {
2050                                 /* apply gesture here */
2051                                 sk_applyGesture(sketch);
2052                         }
2053         
2054                         sk_freeStroke(sketch->gesture);
2055                         sketch->gesture = NULL;
2056                         
2057                         allqueue(REDRAWVIEW3D, 0);
2058                 }
2059         }
2060         
2061         return retval;
2062 }
2063
2064 void BDR_drawSketchNames()
2065 {
2066         if (BIF_validSketchMode())
2067         {
2068                 if (GLOBAL_sketch != NULL)
2069                 {
2070                         sk_drawSketch(GLOBAL_sketch, 1);
2071                 }
2072         }
2073 }
2074
2075 void BDR_drawSketch()
2076 {
2077         if (BIF_validSketchMode())
2078         {
2079                 if (GLOBAL_sketch != NULL)
2080                 {
2081                         sk_drawSketch(GLOBAL_sketch, 0);
2082                 }
2083         }
2084 }
2085
2086 void BIF_endStrokeSketch()
2087 {
2088         if (BIF_validSketchMode())
2089         {
2090                 if (GLOBAL_sketch != NULL)
2091                 {
2092                         sk_endStroke(GLOBAL_sketch);
2093                         allqueue(REDRAWVIEW3D, 0);
2094                 }
2095         }
2096 }
2097
2098 void BIF_deleteSketch()
2099 {
2100         if (BIF_validSketchMode())
2101         {
2102                 if (GLOBAL_sketch != NULL)
2103                 {
2104                         sk_deleteStrokes(GLOBAL_sketch);
2105                         allqueue(REDRAWVIEW3D, 0);
2106                 }
2107         }
2108 }
2109
2110 void BIF_convertSketch()
2111 {
2112         if (BIF_validSketchMode())
2113         {
2114                 if (GLOBAL_sketch != NULL)
2115                 {
2116                         sk_convert(GLOBAL_sketch);
2117                         BIF_undo_push("Convert Sketch");
2118                         allqueue(REDRAWVIEW3D, 0);
2119                         allqueue(REDRAWBUTSEDIT, 0);
2120                 }
2121         }
2122 }
2123
2124 int BIF_paintSketch(short mbut)
2125 {
2126         if (BIF_validSketchMode())
2127         {
2128                 if (GLOBAL_sketch == NULL)
2129                 {
2130                         GLOBAL_sketch = sk_createSketch();
2131                 }
2132                 
2133                 return sk_paint(GLOBAL_sketch, mbut);
2134         }
2135         else
2136         {
2137                 return 0;
2138         }
2139 }
2140         
2141
2142 void BDR_queueDrawSketch()
2143 {
2144         if (BIF_validSketchMode())
2145         {
2146                 if (GLOBAL_sketch != NULL)
2147                 {
2148                         sk_queueRedrawSketch(GLOBAL_sketch);
2149                 }
2150         }
2151 }
2152
2153 void BIF_selectAllSketch(int mode)
2154 {
2155         if (BIF_validSketchMode())
2156         {
2157                 if (GLOBAL_sketch != NULL)
2158                 {
2159                         sk_selectAllSketch(GLOBAL_sketch, mode);
2160                         allqueue(REDRAWVIEW3D, 0);
2161                 }
2162         }
2163 }
2164
2165 int BIF_validSketchMode()
2166 {
2167         if (G.obedit && 
2168                 G.obedit->type == OB_ARMATURE && 
2169                 G.scene->toolsettings->bone_sketching & BONE_SKETCHING)
2170         {
2171                 return 1;
2172         }
2173         else
2174         {
2175                 return 0;
2176         }
2177 }