Final merge of HEAD (bf-blender) into the orange branch.
[blender.git] / source / blender / src / unwrapper.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL/BL DUAL 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. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  */
32
33 #include <string.h>
34 #include <stdlib.h>
35 #include <math.h>
36
37 #ifdef HAVE_CONFIG_H
38 #include <config.h>
39 #endif
40
41 #include "MEM_guardedalloc.h"
42
43 #include "DNA_mesh_types.h"
44 #include "DNA_meshdata_types.h"
45 #include "DNA_scene_types.h"
46 #include "DNA_screen_types.h"
47 #include "DNA_space_types.h"
48
49 #include "BKE_global.h"
50 #include "BKE_mesh.h"
51 #include "BKE_utildefines.h"
52
53 #include "BLI_arithb.h"
54 #include "BLI_edgehash.h"
55
56 #include "BIF_editsima.h"
57 #include "BIF_space.h"
58 #include "BIF_screen.h"
59
60 #include "blendef.h"
61 #include "mydevice.h"
62
63 #include "ONL_opennl.h"
64 #include "BDR_unwrapper.h"
65
66 #include "PIL_time.h"
67
68 #include "parametrizer.h"
69
70 short CurrentUnwrapper = 0;
71
72 /* Implementation Least Squares Conformal Maps parameterization, based on
73  * chapter 2 of:
74  * Bruno Levy, Sylvain Petitjean, Nicolas Ray, Jerome Maillot. Least Squares
75  * Conformal Maps for Automatic Texture Atlas Generation. In Siggraph 2002,
76  * July 2002.
77  */
78  
79 /* Data structure defines */
80 #define LSCM_SEAM1   1
81 #define LSCM_SEAM2   2
82 #define LSCM_INDEXED 4
83 #define LSCM_PINNED  8
84
85 /* LscmVert = One UV */
86 typedef struct LscmVert {
87         int v, v1, v2;            /* vertex indices */
88         int index;                /* index in solver */
89         short tf_index;           /* index in tface (0, 1, 2 or 3) */
90         short flag;               /* see above LSCM constants */
91         TFace *tf;                /* original tface */
92 } LscmVert;
93
94 /* QuickSort helper function, sort by vertex id */
95 static int comp_lscmvert(const void *u1, const void *u2)
96 {
97         LscmVert *v1, *v2;
98         
99         v1= *((LscmVert**)u1);
100         v2= *((LscmVert**)u2);
101
102         if (v1->v > v2->v) return 1;
103         else if (v1->v < v2->v) return -1;
104         return 0;
105 }
106
107 /* Hashed edge table utility */
108
109 static void hash_add_face(EdgeHash *ehash, MFace *mf)
110 {
111         BLI_edgehash_insert(ehash, mf->v1, mf->v2, NULL);
112         BLI_edgehash_insert(ehash, mf->v2, mf->v3, NULL);
113         if(mf->v4) {
114                 BLI_edgehash_insert(ehash, mf->v3, mf->v4, NULL);
115                 BLI_edgehash_insert(ehash, mf->v4, mf->v1, NULL);
116         }
117         else
118                 BLI_edgehash_insert(ehash, mf->v3, mf->v1, NULL);
119 }
120
121 /* divide selected faces in groups, based on seams. note that group numbering
122    starts at 1 */
123 static int make_seam_groups(Mesh *me, int **seamgroups)
124 {
125         int a, b, gid;
126         TFace *tf, *tface;
127         MFace *mf, *mface;
128         int *gf, *gface, *groups;
129         EdgeHash *ehash;
130         int doit, mark;
131
132         if(!me || !me->tface) return 0;
133
134         groups= (int*)MEM_callocN(sizeof(int)*me->totface, "SeamGroups");
135
136         ehash= BLI_edgehash_new();
137
138         mface= (MFace*)me->mface;
139         tface= (TFace*)me->tface;
140         gface= groups;
141         gid= 0;
142         for(b=me->totface; b>0; b--, mface++, tface++, gface++) {
143                 if(!(tface->flag & TF_SELECT) || *gface!=0) continue;
144
145                 if(gid != 0)
146                         BLI_edgehash_clear(ehash, NULL);
147
148                 gid++;
149                 *gface= gid;
150                 mark= 0;
151                 doit= 1;
152
153
154                 while(doit) {
155                         doit= 0;
156                 
157                         /* select connected: fill array */
158                         tf= tface;
159                         mf= mface;
160                         gf= gface;
161                         a= b;
162                         while(a--) {
163                                 if(tf->flag & TF_HIDE);
164                                 else if(tf->flag & TF_SELECT && *gf==gid) {
165                                         hash_add_face(ehash, mf);
166                                 }
167                                 tf++; mf++; gf++;
168                         }
169                 
170                         /* select the faces using array
171                          * consider faces connected when they share one non-seam edge */
172                         tf= tface;
173                         mf= mface;
174                         gf= gface;
175                         a= b;
176                         while(a--) {
177                                 if(tf->flag & TF_HIDE);
178                                 else if(tf->flag & TF_SELECT && *gf==0) {
179                                         mark= 0;
180         
181                                         if(!(tf->unwrap & TF_SEAM1))
182                                                 if(BLI_edgehash_haskey(ehash, mf->v1, mf->v2))
183                                                         mark= 1;
184                                         if(!(tf->unwrap & TF_SEAM2))
185                                                 if(BLI_edgehash_haskey(ehash, mf->v2, mf->v3))
186                                                         mark= 1;
187                                         if(!(tf->unwrap & TF_SEAM3)) {
188                                                 if(mf->v4) {
189                                                         if(BLI_edgehash_haskey(ehash, mf->v3, mf->v4))
190                                                                 mark= 1;
191                                                 }
192                                                 else if(BLI_edgehash_haskey(ehash, mf->v3, mf->v1))
193                                                         mark= 1;
194                                         }
195                                         if(mf->v4 && !(tf->unwrap & TF_SEAM4))
196                                                 if(BLI_edgehash_haskey(ehash, mf->v4, mf->v1))
197                                                         mark= 1;
198         
199                                         if(mark) {
200                                                 *gf= gid;
201                                                 doit= 1;
202                                         }
203                                 }
204                                 tf++; mf++; gf++;
205                         }
206                 }
207         }
208
209         BLI_edgehash_free(ehash, NULL);
210         *seamgroups= groups;
211
212         return gid;
213 }
214
215 static void lscm_rotate_vert(int a, LscmVert **sortvert, int v2, int index)
216 {
217         LscmVert **sv, *v;
218         int found, b;
219
220         /* starting from edge sortvert->v,v2, rotate around vertex and set
221          * index until a seam or an already marked tri is encountered */
222         found = 1;
223
224         while(found) {
225                 found= 0;
226                 sv=sortvert;
227
228                 for(b=a; b>0 && ((*sv)->v == (*sortvert)->v) && !found; b--, sv++) {
229                         v= *sv;
230
231                         if(v->flag & LSCM_INDEXED);
232                         else if(v->v1 == v2) {
233                                 v2= v->v2;
234
235                                 if(v->flag & LSCM_SEAM1) break;
236
237                                 v->index= index;
238                                 v->flag |= LSCM_INDEXED;
239                                 found= 1;
240                                 break;
241                         }
242                         else if(v->v2==v2) {
243                                 v2= v->v1;
244
245                                 if(v->flag & LSCM_SEAM2) break;
246
247                                 v->index= index;
248                                 v->flag |= LSCM_INDEXED;
249                                 found= 1;
250                                 break;
251                         }
252                 }
253         }
254 }
255
256 static int lscm_vertex_set_index(int a, LscmVert **sortvert, int totindex)
257 {
258         LscmVert **sv, *v;
259         int index, b;
260
261         /* rotate over 'wheel' of faces around vertex, incrementing the index
262            everytime we meet a seam, or no next connected face is found.
263            repeat this until we have and id for all verts.
264            if mesh is non-manifold, non-manifold edges will be cut randomly */
265
266         index= totindex;
267         sv= sortvert;
268
269         for(b=a; b>0 && ((*sv)->v == (*sortvert)->v); b--, sv++) {
270                 v= *sv;
271
272                 if(v->flag & LSCM_INDEXED) continue;
273
274                 v->index= index;
275                 v->flag |= LSCM_INDEXED;
276
277                 lscm_rotate_vert(b, sv, v->v1, index);
278                 lscm_rotate_vert(b, sv, v->v2, index);
279
280                 index++;
281         }
282
283         return index;
284 }
285
286 static int lscm_set_indices(LscmVert **sortvert, int totvert)
287 {
288         LscmVert *v, **sv;
289         int a, lastvert, totindex;
290
291         totindex= 0;
292         lastvert= -1;
293         sv= sortvert;
294
295         for(a=totvert; a>0; a--, sv++) {
296                 v= *sv;
297                 if(v->v != lastvert) {
298                         totindex= lscm_vertex_set_index(a, sv, totindex);
299                         lastvert= v->v;
300                 }
301         }
302
303         return totindex;
304 }
305
306 static void lscm_normalize(float *co, float *center, float radius)
307 {
308         /* normalize relative to complete surface */
309         VecSubf(co, co, center);
310         VecMulf(co, (float)1.0/radius);
311 }
312
313 static void lscm_add_triangle(float *v1, float *v2, float *v3, int vid1, int vid2, int vid3, float *center, float radius)
314 {
315         float x[3], y[3], z[3], sub[3], z1[2], z2[2];
316         int id0[2], id1[2], id2[2];
317
318         /* project 3d triangle
319          * edge length is lost, as this algorithm is angle based */
320         lscm_normalize(v1, center, radius);
321         lscm_normalize(v2, center, radius);
322         lscm_normalize(v3, center, radius);
323
324         VecSubf(x, v2, v1);
325         Normalise(x);
326
327         VecSubf(sub, v3, v1);
328         Crossf(z, x, sub);
329         Normalise(z);
330
331         Crossf(y, z, x);
332
333         /* reduce to two 2d vectors */
334         VecSubf(sub, v2, v1);
335         z1[0]= Normalise(sub);
336         z1[1]= 0;
337
338         VecSubf(sub, v3, v1);
339         z2[0]= Inpf(sub, x);
340         z2[1]= Inpf(sub, y);
341
342         /* split id's up for u and v
343            id = u, id + 1 = v */
344         id0[0]= 2*vid1;
345         id0[1]= 2*vid1 + 1;
346         id1[0]= 2*vid2;
347         id1[1]= 2*vid2 + 1;
348         id2[0]= 2*vid3;
349         id2[1]= 2*vid3 + 1;
350
351         /* The LSCM Equation:
352          * ------------------
353          * (u,v) are the uv coords we are looking for -> complex number u + i*v
354          * (x,y) are the above calculated local coords -> complex number x + i*y
355          * Uk = uk + i*vk
356          * Zk = xk + i*yk (= zk[0] + i*zk[1] in the code)
357          * 
358          * That makes the equation:
359          * (Z1 - Z0)(U2 - U0) = (Z2 - Z0)(U1 - U0)
360          *
361          * x0, y0 and y1 were made zero by projecting the triangle:
362          * (x1 + i*y1)(u2 + i*v2 - u0 - i*v0) = (x2 + i*y2)(u1 + i*v1 - u0 - i*v0)
363          *
364          * this gives the following coefficients:
365          * u0 * ((-x1 + x2) + i*(y2))
366          * v0 * ((-y2) + i*(-x1 + x2))
367          * u1 * ((-x2) + i*(-y2))
368          * v1 * ((y2) + i*(-x2))
369          * u2 * (x1)
370          * v2 * (i*(x1))
371          */
372
373         /* real part */
374         nlBegin(NL_ROW);
375         nlCoefficient(id0[0], -z1[0] + z2[0]);
376         nlCoefficient(id0[1], -z2[1]        );
377         nlCoefficient(id1[0], -z2[0]        );
378         nlCoefficient(id1[1],  z2[1]        );
379         nlCoefficient(id2[0],  z1[0]        );
380         nlEnd(NL_ROW);
381
382         /* imaginary  part */
383         nlBegin(NL_ROW);
384         nlCoefficient(id0[0],  z2[1]        );
385         nlCoefficient(id0[1], -z1[0] + z2[0]);
386         nlCoefficient(id1[0], -z2[1]        );
387         nlCoefficient(id1[1], -z2[0]        );
388         nlCoefficient(id2[1],  z1[0]        );
389         nlEnd(NL_ROW);
390 }
391
392 static float lscm_angle_cos(float *v1, float *v2, float *v3)
393 {
394     float vec1[3], vec2[3];
395
396         VecSubf(vec1, v2, v1);
397         VecSubf(vec2, v3, v1);
398         Normalise(vec1);
399         Normalise(vec2);
400
401         return vec1[0]*vec2[0] + vec1[1]*vec2[1] + vec1[2]*vec2[2];
402 }
403
404 static int lscm_build_vertex_data(Mesh *me, int *groups, int gid, LscmVert **lscm_vertices, LscmVert ***sort_vertices)
405 {
406         MVert *mv;
407         MFace *mf;
408         TFace *tf;
409         int *gf, totvert, a;
410         LscmVert *lscmvert, **sortvert;
411         LscmVert *v1, *v2, *v3, **sv1, **sv2, **sv3;
412         float a1, a2;
413
414         /* determine size for malloc */
415         totvert= 0;
416         mv = me->mvert;
417         mf= me->mface;
418         tf= me->tface;
419         gf= groups;
420         a1 = a2 = 0;
421
422         for(a=me->totface; a>0; a--) {
423                 if(*gf==gid) {
424
425                         totvert += 3;
426                         if(mf->v4) totvert +=3; 
427                 }
428                 tf++; mf++; gf++;
429         }
430
431         /* a list per face vertices */
432         lscmvert= (LscmVert*)MEM_mallocN(sizeof(LscmVert)*totvert,"LscmVerts");
433         /* the above list sorted by vertex id */
434         sortvert= (LscmVert**)MEM_mallocN(sizeof(LscmVert*)*totvert, "LscmVSort");
435
436         /* actually build the list (including virtual triangulation) */
437         mf= me->mface;
438         tf= me->tface;
439         gf= groups;
440
441         v1= lscmvert;
442         v2= lscmvert + 1;
443         v3= lscmvert + 2;
444
445         sv1= sortvert;
446         sv2= sortvert + 1;
447         sv3= sortvert + 2;
448
449         /* warning: ugly code :) */
450         for(a=me->totface; a>0; a--) {
451                 if(*gf==gid) {
452                         /* determine triangulation direction, to avoid degenerate
453                            triangles (small cos = degenerate). */
454                         if(mf->v4) {
455                                 a1 = lscm_angle_cos((mv+mf->v1)->co, (mv+mf->v2)->co, (mv+mf->v3)->co);
456                                 a1 += lscm_angle_cos((mv+mf->v2)->co, (mv+mf->v1)->co, (mv+mf->v3)->co);
457                                 a1 += lscm_angle_cos((mv+mf->v3)->co, (mv+mf->v1)->co, (mv+mf->v2)->co);
458
459                                 a2 = lscm_angle_cos((mv+mf->v1)->co, (mv+mf->v2)->co, (mv+mf->v4)->co);
460                                 a2 += lscm_angle_cos((mv+mf->v2)->co, (mv+mf->v1)->co, (mv+mf->v4)->co);
461                                 a2 += lscm_angle_cos((mv+mf->v4)->co, (mv+mf->v1)->co, (mv+mf->v2)->co);
462                         }
463
464                         a1 = 0.0; a2 = 1.0;
465
466                         if(!mf->v4 || a1 > a2) {
467                                 v1->v= mf->v1;
468                                 v2->v= mf->v2;
469                                 v3->v= mf->v3;
470
471                                 v1->tf_index= 0;
472                                 v2->tf_index= 1;
473                                 v3->tf_index= 2;
474
475                                 v1->flag= v2->flag= v3->flag= 0;
476
477                                 v1->v1= v2->v;
478                                 v1->v2= v3->v;
479
480                                 v2->v1= v1->v;
481                                 v2->v2= v3->v;
482
483                                 v3->v1= v1->v;
484                                 v3->v2= v2->v;
485
486                                 v1->tf= v2->tf= v3->tf= tf;
487
488                                 *sv1= v1;
489                                 *sv2= v2;
490                                 *sv3= v3;
491
492                                 if(tf->unwrap & TF_SEAM1) {
493                                         v1->flag |= LSCM_SEAM1;
494                                         v2->flag |= LSCM_SEAM1;
495                                 }
496         
497                                 if(tf->unwrap & TF_SEAM2) {
498                                         v2->flag |= LSCM_SEAM2;
499                                         v3->flag |= LSCM_SEAM2;
500                                 }
501
502                                 if(!mf->v4 && tf->unwrap & TF_SEAM3) {
503                                         v1->flag |= LSCM_SEAM2;
504                                         v3->flag |= LSCM_SEAM1;
505                                 }
506
507                                 v1 += 3; v2 += 3; v3 += 3;
508                                 sv1 += 3; sv2 += 3; sv3 += 3;
509                         }
510
511                         if(mf->v4 && a1 > a2) {
512                                 v1->v= mf->v1;
513                                 v2->v= mf->v3;
514                                 v3->v= mf->v4;
515
516                                 v1->tf_index= 0;
517                                 v2->tf_index= 2;
518                                 v3->tf_index= 3;
519
520                                 v1->flag= v2->flag= v3->flag= 0;
521
522                                 v1->v1= v2->v;
523                                 v1->v2= v3->v;
524
525                                 v2->v1= v3->v;
526                                 v2->v2= v1->v;
527         
528                                 v3->v1= v1->v;
529                                 v3->v2= v2->v;
530
531                                 v1->tf= v2->tf= v3->tf= tf;
532
533                                 *sv1= v1;
534                                 *sv2= v2;
535                                 *sv3= v3;
536
537                                 if(tf->unwrap & TF_SEAM3) {
538                                         v2->flag |= LSCM_SEAM1;
539                                         v3->flag |= LSCM_SEAM2;
540                                 }
541         
542                                 if(tf->unwrap & TF_SEAM4) {
543                                         v1->flag |= LSCM_SEAM2;
544                                         v3->flag |= LSCM_SEAM1;
545                                 }
546
547                                 v1 += 3; v2 += 3; v3 += 3;
548                                 sv1 += 3; sv2 += 3; sv3 += 3;
549                         }
550
551                         if(mf->v4 && a1 <= a2) {
552                                 v1->v= mf->v1;
553                                 v2->v= mf->v2;
554                                 v3->v= mf->v4;
555
556                                 v1->tf_index= 0;
557                                 v2->tf_index= 1;
558                                 v3->tf_index= 3;
559
560                                 v1->flag= v2->flag= v3->flag= 0;
561
562                                 v1->v1= v2->v;
563                                 v1->v2= v3->v;
564
565                                 v2->v1= v1->v;
566                                 v2->v2= v3->v;
567
568                                 v3->v1= v1->v;
569                                 v3->v2= v2->v;
570
571                                 v1->tf= v2->tf= v3->tf= tf;
572
573                                 *sv1= v1;
574                                 *sv2= v2;
575                                 *sv3= v3;
576
577                                 if(tf->unwrap & TF_SEAM1) {
578                                         v1->flag |= LSCM_SEAM1;
579                                         v2->flag |= LSCM_SEAM1;
580                                 }
581         
582                                 if(tf->unwrap & TF_SEAM4) {
583                                         v1->flag |= LSCM_SEAM2;
584                                         v3->flag |= LSCM_SEAM1;
585                                 }
586
587                                 v1 += 3; v2 += 3; v3 += 3;
588                                 sv1 += 3; sv2 += 3; sv3 += 3;
589
590                                 /* -- */
591
592                                 v1->v= mf->v2;
593                                 v2->v= mf->v3;
594                                 v3->v= mf->v4;
595
596                                 v1->tf_index= 1;
597                                 v2->tf_index= 2;
598                                 v3->tf_index= 3;
599
600                                 v1->flag= v2->flag= v3->flag= 0;
601
602                                 v1->v1= v2->v;
603                                 v1->v2= v3->v;
604
605                                 v2->v1= v1->v;
606                                 v2->v2= v3->v;
607         
608                                 v3->v1= v1->v;
609                                 v3->v2= v2->v;
610
611                                 v1->tf= v2->tf= v3->tf= tf;
612
613                                 *sv1= v1;
614                                 *sv2= v2;
615                                 *sv3= v3;
616
617                                 if(tf->unwrap & TF_SEAM2) {
618                                         v1->flag |= LSCM_SEAM1;
619                                         v2->flag |= LSCM_SEAM1;
620                                 }
621         
622                                 if(tf->unwrap & TF_SEAM3) {
623                                         v2->flag |= LSCM_SEAM2;
624                                         v3->flag |= LSCM_SEAM2;
625                                 }
626
627                                 v1 += 3; v2 += 3; v3 += 3;
628                                 sv1 += 3; sv2 += 3; sv3 += 3;
629                         }
630
631                 }
632                 tf++; mf++; gf++;
633         }
634
635         /* sort by vertex id */
636         qsort(sortvert, totvert, sizeof(LscmVert*), comp_lscmvert);
637         
638         *lscm_vertices= lscmvert;
639         *sort_vertices= sortvert;
640         return totvert;
641 }
642
643 static void lscm_min_max_cent_rad(Mesh *me, LscmVert **sortvert, int totvert, float *min, float *max, float *center, float *radius)
644 {
645         MVert *mv= me->mvert;
646         LscmVert *v, **sv;
647         int a, lastvert, vertcount;
648         float *co, sub[3];
649         
650         /* find min, max and center */
651         center[0]= center[1]= center[2]= 0.0;
652         INIT_MINMAX(min, max);
653
654         vertcount= 0;
655         lastvert= -1;
656         sv= sortvert;
657
658         for(a=totvert; a>0; a--, sv++) {
659                 v= *sv;
660                 if(v->v != lastvert) {
661                         co= (mv+v->v)->co;
662
663                         VecAddf(center, center, (mv+v->v)->co);
664                         DO_MINMAX(co, min, max);
665
666                         vertcount++;
667                         lastvert= v->v;
668                 }
669         }
670
671         VecMulf(center, (float)1.0/(float)vertcount);
672
673         /* find radius */
674         VecSubf(sub, center, max);
675         *radius= Normalise(sub);
676
677         if(*radius < 1e-20)
678                 *radius= 1.0;
679 }
680
681 static void lscm_projection_axes(float *min, float *max, float *p1, float *p2)
682 {
683         float dx, dy, dz;
684
685         dx= max[0] - min[0];
686         dy= max[1] - min[1];
687         dz= max[2] - min[2];
688
689         p1[0]= p1[1]= p1[2]= 0.0;
690         p2[0]= p2[1]= p2[2]= 0.0;
691
692         if(dx < dy && dx < dz) {
693                 if(dy > dz) p1[1]= p2[2]= 1.0;   /* y, z */
694                 else p1[2]= p2[1]= 1.0;          /* z, y */
695         }
696         else if(dy < dx && dy < dz) {
697                 if(dx > dz) p1[0]= p2[2]= 1.0;   /* x, z */
698                 else p1[2]= p2[0]= 1.0;          /* z, x */
699         }
700         else {
701                 if(dx > dy) p1[0]= p2[1]= 1.0;   /* x, y */
702                 else p1[1]= p2[0]= 1.0;          /* y, x */
703         }
704 }
705
706 static void lscm_set_initial_solution(Mesh *me, LscmVert **sortvert, int totvert, float *p1, float *p2, int *vertex_min, int *vertex_max)
707 {
708         float umin, umax, *uv, *co;
709         int vmin, vmax, a;
710         LscmVert **sv, *v;
711         MVert *mv= me->mvert;
712
713         umin= 1.0e30;
714         umax= -1.0e30;
715
716         vmin= 0;
717         vmax= 2;
718
719         sv= sortvert;
720
721         for(a=totvert; a>0; a--, sv++) {
722                 v= *sv;
723                 co= (mv+v->v)->co;
724                 uv= v->tf->uv[v->tf_index];
725
726                 uv[0]= Inpf(co, p1);
727                 uv[1]= Inpf(co, p2);
728                 
729                 if(uv[0] < umin) {
730                         vmin= v->index;
731                         umin= uv[0];
732                 }
733                 if(uv[0] > umax) {
734                         vmax= v->index;
735                         umax= uv[0];
736                 }
737
738                 nlSetVariable(2*v->index, uv[0]);
739                 nlSetVariable(2*v->index + 1, uv[1]);
740         }
741
742         *vertex_min= vmin;
743         *vertex_max= vmax;
744 }
745
746 static void lscm_set_pinned_solution(Mesh *me, LscmVert **sortvert, int totvert, int *pinned)
747 {
748         float min[2], max[2], *uv, *co;
749         int a, pin;
750         LscmVert **sv, *v;
751         MVert *mv= me->mvert;
752
753         INIT_MINMAX2(min, max);
754         *pinned= 0;
755
756         sv= sortvert;
757
758         for(a=totvert; a>0; a--, sv++) {
759                 v= *sv;
760                 co= (mv+v->v)->co;
761                 uv= v->tf->uv[v->tf_index];
762
763                 pin = ((v->tf->unwrap & TF_PIN1) && (v->tf_index == 0)) ||
764                       ((v->tf->unwrap & TF_PIN2) && (v->tf_index == 1)) ||
765                       ((v->tf->unwrap & TF_PIN3) && (v->tf_index == 2)) ||
766                       ((v->tf->unwrap & TF_PIN4) && (v->tf_index == 3)); 
767
768                 nlSetVariable(2*v->index, uv[0]);
769                 nlSetVariable(2*v->index + 1, uv[1]);
770
771         if(pin){
772                         DO_MINMAX2(uv, min, max);
773
774                         *pinned += 1;
775
776                         nlLockVariable(2*v->index);
777                         nlLockVariable(2*v->index + 1);
778                 }
779         }
780
781         if (*pinned){
782                 /* abuse umax vmax for caculating euclidian distance */
783                 max[0] -= min[0];
784                 max[1] -= min[1];
785
786                 /* check for degenerated pinning box */
787                 if (((max[0]*max[0])+(max[1]*max[1])) < 1e-10)
788                         *pinned = -1;
789         }
790 }
791
792
793 static void lscm_build_matrix(Mesh *me, LscmVert *lscmvert, int *groups, int gid, float *center, float radius)
794 {
795         MVert *mv= me->mvert;
796         MFace *mf;
797         TFace *tf;
798         int *gf, a, id1, id2, id3;
799         LscmVert *v;
800         float co1[3], co2[3], co3[3];
801
802         nlBegin(NL_MATRIX);
803
804         mf= me->mface;
805         tf= me->tface;
806         gf= groups;
807         v= lscmvert;
808
809         for(a=me->totface; a>0; a--) {
810                 if(*gf==gid) {
811                         VecCopyf(co1, (mv+v->v)->co);
812                         id1= v->index; v++;
813                         VecCopyf(co2, (mv+v->v)->co);
814                         id2= v->index; v++;
815                         VecCopyf(co3, (mv+v->v)->co);
816                         id3= v->index; v++;
817                         lscm_add_triangle(co1, co2, co3, id1, id2, id3, center, radius);
818
819                         if(mf->v4) {
820                                 VecCopyf(co1, (mv+v->v)->co);
821                                 id1= v->index; v++;
822                                 VecCopyf(co2, (mv+v->v)->co);
823                                 id2= v->index; v++;
824                                 VecCopyf(co3, (mv+v->v)->co);
825                                 id3= v->index; v++;
826                                 lscm_add_triangle(co1, co2, co3, id1, id2, id3, center, radius);
827                         } 
828                 }
829                 tf++; mf++; gf++;
830         }
831
832         nlEnd(NL_MATRIX);
833 }
834
835 static void lscm_load_solution(Mesh *me, LscmVert *lscmvert, int *groups, int gid)
836 {
837         MFace *mf;
838         TFace *tf;
839         int *gf, a, b;
840         LscmVert *v;
841         float *uv;
842
843         mf= me->mface;
844         tf= me->tface;
845         gf= groups;
846         v= lscmvert;
847
848         for(a=me->totface; a>0; a--) {
849                 if(*gf==gid) {
850
851                         if(mf->v4) b= 6;
852                         else b=3;
853
854                         /* index= u, index + 1= v */
855                         while(b > 0) {
856                                 uv= v->tf->uv[v->tf_index];
857
858                                 uv[0]= nlGetVariable(2*v->index);
859                                 uv[1]= nlGetVariable(2*v->index + 1);
860
861                                 v++;
862                                 b--;
863                         }
864                 }
865                 tf++; mf++; gf++;
866         }
867 }
868
869 static int unwrap_lscm_face_group(Mesh *me, int *groups, int gid)
870 {
871         LscmVert *lscmvert, **sortvert;
872         int totindex, totvert, vmin, vmax,pinned;
873         float min[3], max[3], center[3], radius, p1[3], p2[3];
874
875         /* build the data structures */
876         totvert= lscm_build_vertex_data(me, groups, gid, &lscmvert, &sortvert);
877
878         /* calculate min, max, center and radius */
879         lscm_min_max_cent_rad(me, sortvert, totvert, min, max, center, &radius);
880
881         /* index distinct vertices */
882         totindex= lscm_set_indices(sortvert, totvert);
883
884         /* create solver */
885         nlNewContext();
886         nlSolverParameteri(NL_NB_VARIABLES, 2*totindex);
887         nlSolverParameteri(NL_LEAST_SQUARES, NL_TRUE);
888
889         nlBegin(NL_SYSTEM);
890
891         /* find axes for projecting initial solutions on */
892         lscm_projection_axes(min, max, p1, p2);
893     /* see if pinned data is avail and set on fly */
894         lscm_set_pinned_solution(me, sortvert, totvert, &pinned);
895
896     if(pinned < 0); /* really small pinned uv's: won't see difference anyway */
897         else { 
898                 /* auto pinning */
899                 if(pinned < 2) 
900                 {
901                         /* set initial solution and locate two extrema vertices to pin */
902                         lscm_set_initial_solution(me,sortvert,totvert,p1,p2,&vmin,&vmax);
903
904                         /* pin 2 uv's */
905                         nlLockVariable(2*vmin);
906                         nlLockVariable(2*vmin + 1);
907                         nlLockVariable(2*vmax);
908                         nlLockVariable(2*vmax + 1);
909                 }
910
911                 /* add triangles to the solver */
912                 lscm_build_matrix(me, lscmvert, groups, gid, center, radius);
913                 
914                 nlEnd(NL_SYSTEM);
915
916                 /* LSCM solver magic! */
917                 nlSolve(NULL, NL_FALSE);
918                 
919                 /* load new uv's: will be projected uv's if solving failed  */
920                 lscm_load_solution(me, lscmvert, groups, gid);
921     }
922
923         nlDeleteContext(nlGetCurrent());
924         MEM_freeN(lscmvert);
925         MEM_freeN(sortvert);
926         return (pinned);
927 }
928
929 static void seam_group_bbox(Mesh *me, int *groups, int gid, float *min, float *max)
930 {
931         MFace *mf;
932         TFace *tf;
933         int *gf, a;
934
935         INIT_MINMAX2(min, max);
936
937         mf= me->mface;
938         tf= me->tface;
939         gf= groups;
940
941         for(a=me->totface; a>0; a--) {
942                 if((gid!=0 && *gf==gid) || (gid==0 && *gf)) {
943                         
944                         DO_MINMAX2(tf->uv[0], min, max)
945                         DO_MINMAX2(tf->uv[1], min, max)
946                         DO_MINMAX2(tf->uv[2], min, max)
947
948                         if(mf->v4) { 
949                                 DO_MINMAX2(tf->uv[3], min, max)
950                         }
951                 }
952                 tf++; mf++; gf++;
953         }
954 }
955
956 static void seam_group_scale(Mesh *me, int *groups, int gid, float scale)
957 {
958         MFace *mf;
959         TFace *tf;
960         int *gf, a;
961
962         mf= me->mface;
963         tf= me->tface;
964         gf= groups;
965
966         for(a=me->totface; a>0; a--) {
967                 if((gid!=0 && *gf==gid) || (gid==0 && *gf)) {
968                         
969                         Vec2Mulf(tf->uv[0], scale);
970                         Vec2Mulf(tf->uv[1], scale);
971                         Vec2Mulf(tf->uv[2], scale);
972                         if(mf->v4) Vec2Mulf(tf->uv[3], scale);
973                 }
974                 tf++; mf++; gf++;
975         }
976 }
977
978 static void seam_group_move(Mesh *me, int *groups, int gid, float add[2])
979 {
980         MFace *mf;
981         TFace *tf;
982         int *gf, a;
983
984         mf= me->mface;
985         tf= me->tface;
986         gf= groups;
987
988         for(a=me->totface; a>0; a--) {
989                 if((gid!=0 && *gf==gid) || (gid==0 && *gf)) {
990                         
991                         Vec2Addf(tf->uv[0], tf->uv[0], add);
992                         Vec2Addf(tf->uv[1], tf->uv[1], add);
993                         Vec2Addf(tf->uv[2], tf->uv[2], add);
994                         if(mf->v4) Vec2Addf(tf->uv[3], tf->uv[3], add);
995                 }
996                 tf++; mf++; gf++;
997         }
998 }
999
1000 /* put group withing (0,0)->(1,1) boundbox */
1001 static void seam_group_normalize(Mesh *me, int *groups, int gid)
1002 {
1003         float min[2], max[2], sx, sy, scale, add[2];
1004
1005         seam_group_bbox(me, groups, gid, min, max);
1006
1007         sx= (max[0]-min[0]);
1008         sy= (max[1]-min[1]);
1009
1010         scale= MAX2(sx, sy);
1011         scale= (1.0/scale);
1012
1013         add[0]= -min[0];
1014         add[1]= -min[1];
1015
1016         seam_group_move(me, groups, gid, add);
1017         seam_group_scale(me, groups, gid, scale);
1018 }
1019
1020 /* get scale relative to mesh */
1021 static float seam_group_relative_scale(Mesh *me, int *groups, int gid)
1022 {
1023         MVert *mv= me->mvert;
1024         MFace *mf;
1025         TFace *tf;
1026         int *gf, a;
1027         float len_xyz, len_uv;
1028
1029         len_xyz= 0.0;
1030         len_uv= 0.0;
1031         mf= me->mface;
1032         tf= me->tface;
1033         gf= groups;
1034
1035         for(a=me->totface; a>0; a--) {
1036                 if(*gf==gid) {
1037                         
1038                         len_uv += Vec2Lenf(tf->uv[0], tf->uv[1]);
1039                         len_xyz += VecLenf((mv+mf->v1)->co, (mv+mf->v2)->co);
1040
1041                         len_uv += Vec2Lenf(tf->uv[1], tf->uv[2]);
1042                         len_xyz += VecLenf((mv+mf->v2)->co, (mv+mf->v3)->co);
1043
1044                         if(mf->v4) { 
1045
1046                                 len_uv += Vec2Lenf(tf->uv[2], tf->uv[3]);
1047                                 len_xyz += VecLenf((mv+mf->v3)->co, (mv+mf->v4)->co);
1048                                 
1049                                 len_uv += Vec2Lenf(tf->uv[3], tf->uv[0]);
1050                                 len_xyz += VecLenf((mv+mf->v4)->co, (mv+mf->v1)->co);
1051                         }
1052                         else {
1053                                 len_uv += Vec2Lenf(tf->uv[2], tf->uv[0]);
1054                                 len_xyz += VecLenf((mv+mf->v3)->co, (mv+mf->v1)->co);
1055                         }
1056                 }
1057                 tf++; mf++; gf++;
1058         }
1059
1060         return (len_uv/len_xyz);
1061 }
1062
1063 /* very primitive packing */
1064 static void pack_seam_groups(Mesh *me, int *groups, int totgroup)
1065 {
1066         float *groupscale, minscale, scale, add[2], groupw;
1067         float dx, dy, packx, packy, min[2], max[2], rowh;
1068         int a;
1069
1070         groupscale = (float*)MEM_mallocN(sizeof(float)*totgroup, "SeamGroupScale");
1071
1072         minscale= 1e30;
1073
1074         for(a=0; a<totgroup; a++) {
1075                 groupscale[a]= seam_group_relative_scale(me, groups, a+1);
1076                 minscale= MIN2(groupscale[a], minscale);
1077         }
1078
1079         packx= packy= 0.0;
1080         rowh= 0.0;
1081         groupw= 1.0/sqrt(totgroup);
1082
1083         for(a=0; a<totgroup; a++) {
1084
1085                 /* scale so all groups have the same size relative to the mesh */
1086                 scale = minscale/groupscale[a];
1087                 scale *= groupw;
1088
1089                 seam_group_bbox(me, groups, a+1, min, max);
1090                 dx= (max[0]-min[0])*scale;
1091                 dy= (max[1]-min[1])*scale;
1092
1093                 /* for padding */
1094                 dx += 0.01;
1095                 dy += 0.01;
1096
1097                 add[0]= add[1]= 0.0;
1098
1099                 if(dx > 1.0) {
1100                         add[0]= 0.0;
1101                         add[1]= packy;
1102
1103                         packy += dy;
1104                         packx= 0.0;
1105                         rowh= 0.0;
1106                 }
1107                 else if(dx <= (1.0-packx)) {
1108                         add[0]= packx;
1109                         add[1]= packy;
1110
1111                         packx += dx;
1112                         rowh= MAX2(rowh, dy);
1113                 }
1114                 else {
1115                         packy += rowh;
1116                         packx= dx;
1117                         rowh= dy;
1118
1119                         add[0]= 0.0;
1120                         add[1]= packy;
1121                 }
1122
1123                 /* for padding */
1124                 add[0] += 0.005;
1125                 add[1] += 0.005;
1126
1127                 seam_group_scale(me, groups, a+1, scale);
1128                 seam_group_move(me, groups, a+1, add);
1129         }
1130
1131         MEM_freeN(groupscale);
1132
1133         seam_group_normalize(me, groups, 0);
1134         seam_group_scale(me, groups, 0, 0.98);
1135         add[0]= add[1]= 0.01;
1136         seam_group_move(me, groups, 0, add);
1137 }
1138
1139 void unwrap_lscm(void)
1140 {
1141     int dopack = 1;
1142         int res;
1143         Mesh *me;
1144         int totgroup, *groups=NULL, a;
1145
1146         if (CurrentUnwrapper == 1) {
1147                 unwrap_lscm_new();
1148                 return;
1149         }
1150         
1151         me= get_mesh(OBACT);
1152         if(me==0 || me->tface==0) return;
1153         
1154         totgroup= make_seam_groups(me, &groups);
1155         
1156         if(totgroup==0) return;
1157         
1158         for(a=totgroup; a>0; a--) {
1159                 res= unwrap_lscm_face_group(me, groups, a);
1160                 if((res < 3) && (res > -1)) {
1161                         seam_group_normalize(me, groups, a);
1162                 }
1163                 else {
1164                         dopack = 0;
1165                 }
1166                 
1167         }
1168         
1169         if(dopack) pack_seam_groups(me, groups, totgroup);
1170         
1171         MEM_freeN(groups);
1172
1173         BIF_undo_push("UV lscm unwrap");
1174
1175         object_uvs_changed(OBACT);
1176
1177         allqueue(REDRAWVIEW3D, 0);
1178         allqueue(REDRAWIMAGE, 0);
1179 }
1180
1181 /* note; to make it quick work, brecht/jens: you can make it nice later! (ton) */
1182 void unwrap_lscm_live(void)
1183 {
1184     int dopack = 1;
1185         int res;
1186         Mesh *me;
1187         int totgroup, *groups=NULL, a;
1188         
1189         me= get_mesh(OBACT);
1190         if(me==0 || me->tface==0) return;
1191         
1192         totgroup= make_seam_groups(me, &groups);
1193         
1194         if(totgroup==0) return;
1195         
1196         for(a=totgroup; a>0; a--) {
1197                 res= unwrap_lscm_face_group(me, groups, a);
1198                 if((res < 3) && (res > -1)) {
1199                         seam_group_normalize(me, groups, a);
1200                 }
1201                 else {
1202                         dopack = 0;
1203                 }
1204                 
1205         }
1206         
1207         if(dopack) pack_seam_groups(me, groups, totgroup);
1208         
1209         MEM_freeN(groups);
1210
1211 }
1212
1213 /* Set tface seams based on edge data, uses hash table to find seam edges. */
1214
1215 void set_seamtface()
1216 {
1217         Mesh *me;
1218         EdgeHash *ehash;
1219         int a;
1220         MFace *mf;
1221         TFace *tf;
1222         MEdge *medge;
1223
1224         me= get_mesh(OBACT);
1225         if(!me || !me->tface || !(G.f & G_FACESELECT)) return;
1226         
1227         ehash= BLI_edgehash_new();
1228
1229         for(medge=me->medge, a=me->totedge; a>0; a--, medge++)
1230                 if(medge->flag & ME_SEAM)
1231                         BLI_edgehash_insert(ehash, medge->v1, medge->v2, NULL);
1232
1233         mf= me->mface;
1234         tf= me->tface;
1235         for(a=me->totface; a>0; a--, mf++, tf++) {
1236                 tf->unwrap &= ~(TF_SEAM1|TF_SEAM2|TF_SEAM3|TF_SEAM4);
1237
1238                 if(!ehash) continue;
1239
1240                 if(BLI_edgehash_haskey(ehash, mf->v1, mf->v2)) tf->unwrap |= TF_SEAM1;
1241                 if(BLI_edgehash_haskey(ehash, mf->v2, mf->v3)) tf->unwrap |= TF_SEAM2;
1242
1243                 if(mf->v4) {
1244                         if(BLI_edgehash_haskey(ehash, mf->v3, mf->v4)) tf->unwrap |= TF_SEAM3;
1245                         if(BLI_edgehash_haskey(ehash, mf->v4, mf->v1)) tf->unwrap |= TF_SEAM4;
1246                 }
1247                 else if(BLI_edgehash_haskey(ehash, mf->v3, mf->v1)) tf->unwrap |= TF_SEAM3;
1248         }
1249
1250         BLI_edgehash_free(ehash, NULL);
1251 }
1252
1253 void select_linked_tfaces_with_seams(int mode, Mesh *me, unsigned int index)
1254 {
1255         TFace *tf;
1256         MFace *mf;
1257         int a, doit=1, mark=0;
1258         char *linkflag;
1259         EdgeHash *ehash;
1260
1261         ehash= BLI_edgehash_new();
1262         linkflag= MEM_callocN(sizeof(char)*me->totface, "linkflaguv");
1263
1264         if (mode==0 || mode==1) {
1265                 /* only put face under cursor in array */
1266                 mf= ((MFace*)me->mface) + index;
1267                 hash_add_face(ehash, mf);
1268                 linkflag[index]= 1;
1269         }
1270         else {
1271                 /* fill array by selection */
1272                 tf= me->tface;
1273                 mf= me->mface;
1274                 for(a=0; a<me->totface; a++, tf++, mf++) {
1275                         if(tf->flag & TF_HIDE);
1276                         else if(tf->flag & TF_SELECT) {
1277                                 hash_add_face(ehash, mf);
1278                                 linkflag[a]= 1;
1279                         }
1280                 }
1281         }
1282         
1283         while(doit) {
1284                 doit= 0;
1285                 
1286                 /* expand selection */
1287                 tf= me->tface;
1288                 mf= me->mface;
1289                 for(a=0; a<me->totface; a++, tf++, mf++) {
1290                         if(tf->flag & TF_HIDE);
1291                         else if(!linkflag[a]) {
1292                                 mark= 0;
1293
1294                                 if(!(tf->unwrap & TF_SEAM1))
1295                                         if(BLI_edgehash_haskey(ehash, mf->v1, mf->v2))
1296                                                 mark= 1;
1297                                 if(!(tf->unwrap & TF_SEAM2))
1298                                         if(BLI_edgehash_haskey(ehash, mf->v2, mf->v3))
1299                                                 mark= 1;
1300                                 if(!(tf->unwrap & TF_SEAM3)) {
1301                                         if(mf->v4) {
1302                                                 if(BLI_edgehash_haskey(ehash, mf->v3, mf->v4))
1303                                                         mark= 1;
1304                                         }
1305                                         else if(BLI_edgehash_haskey(ehash, mf->v3, mf->v1))
1306                                                 mark= 1;
1307                                 }
1308                                 if(mf->v4 && !(tf->unwrap & TF_SEAM4))
1309                                         if(BLI_edgehash_haskey(ehash, mf->v4, mf->v1))
1310                                                 mark= 1;
1311
1312                                 if(mark) {
1313                                         linkflag[a]= 1;
1314                                         hash_add_face(ehash, mf);
1315                                         doit= 1;
1316                                 }
1317                         }
1318                 }
1319                 
1320         }
1321
1322         if(mode==0 || mode==2) {
1323                 for(a=0, tf=me->tface; a<me->totface; a++, tf++)
1324                         if(linkflag[a])
1325                                 tf->flag |= TF_SELECT;
1326                         else
1327                                 tf->flag &= ~TF_SELECT;
1328         }
1329         else if(mode==1) {
1330                 for(a=0, tf=me->tface; a<me->totface; a++, tf++)
1331                         if(linkflag[a] && (tf->flag & TF_SELECT))
1332                                 break;
1333
1334                 if (a<me->totface) {
1335                         for(a=0, tf=me->tface; a<me->totface; a++, tf++)
1336                                 if(linkflag[a])
1337                                         tf->flag &= ~TF_SELECT;
1338                 }
1339                 else {
1340                         for(a=0, tf=me->tface; a<me->totface; a++, tf++)
1341                                 if(linkflag[a])
1342                                         tf->flag |= TF_SELECT;
1343                 }
1344         }
1345         
1346         BLI_edgehash_free(ehash, NULL);
1347         MEM_freeN(linkflag);
1348         
1349         BIF_undo_push("Select linked UV face");
1350         object_tface_flags_changed(OBACT, 0);
1351 }
1352
1353 /* Parametrizer */
1354
1355 ParamHandle *construct_param_handle(Mesh *me, short implicit, short fill)
1356 {
1357         int a;
1358         TFace *tf;
1359         MFace *mf;
1360         MVert *mv;
1361         MEdge *medge;
1362         ParamHandle *handle;
1363         
1364         handle = param_construct_begin();
1365         
1366         mv= me->mvert;
1367         mf= me->mface;
1368         tf= me->tface;
1369         for (a=0; a<me->totface; a++, mf++, tf++) {
1370                 ParamKey key, vkeys[4];
1371                 ParamBool pin[4], select[4];
1372                 float *co[4];
1373                 float *uv[4];
1374                 int nverts;
1375
1376                 if ((tf->flag & TF_HIDE) || !(tf->flag & TF_SELECT))
1377                         continue;
1378
1379                 if (implicit && !(tf->flag & (TF_SEL1|TF_SEL2|TF_SEL3|TF_SEL4)))
1380                         continue;
1381
1382                 key = (ParamKey)mf;
1383                 vkeys[0] = (ParamKey)mf->v1;
1384                 vkeys[1] = (ParamKey)mf->v2;
1385                 vkeys[2] = (ParamKey)mf->v3;
1386
1387                 co[0] = (mv+mf->v1)->co;
1388                 co[1] = (mv+mf->v2)->co;
1389                 co[2] = (mv+mf->v3)->co;
1390
1391                 uv[0] = tf->uv[0];
1392                 uv[1] = tf->uv[1];
1393                 uv[2] = tf->uv[2];
1394
1395                 pin[0] = ((tf->unwrap & TF_PIN1) != 0);
1396                 pin[1] = ((tf->unwrap & TF_PIN2) != 0);
1397                 pin[2] = ((tf->unwrap & TF_PIN3) != 0);
1398
1399                 select[0] = ((tf->flag & TF_SEL1) != 0);
1400                 select[1] = ((tf->flag & TF_SEL2) != 0);
1401                 select[2] = ((tf->flag & TF_SEL3) != 0);
1402
1403                 if (mf->v4) {
1404                         vkeys[3] = (ParamKey)mf->v4;
1405                         co[3] = (mv+mf->v4)->co;
1406                         uv[3] = tf->uv[3];
1407                         pin[3] = ((tf->unwrap & TF_PIN4) != 0);
1408                         select[3] = ((tf->flag & TF_SEL4) != 0);
1409                         nverts = 4;
1410                 }
1411                 else
1412                         nverts = 3;
1413
1414                 param_face_add(handle, key, nverts, vkeys, co, uv, pin, select);
1415         }
1416
1417         if (!implicit) {
1418                 for(medge=me->medge, a=me->totedge; a>0; a--, medge++) {
1419                         if(medge->flag & ME_SEAM) {
1420                                 ParamKey vkeys[2];
1421
1422                                 vkeys[0] = (ParamKey)medge->v1;
1423                                 vkeys[1] = (ParamKey)medge->v2;
1424                                 param_edge_set_seam(handle, vkeys);
1425                         }
1426                 }
1427         }
1428
1429         param_construct_end(handle, fill, implicit);
1430
1431         return handle;
1432 }
1433
1434 void unwrap_lscm_new(void)
1435 {
1436         Mesh *me;
1437         ParamHandle *handle;
1438         
1439         me= get_mesh(OBACT);
1440         if(me==0 || me->tface==0) return;
1441
1442         handle = construct_param_handle(me, 0, 1);
1443
1444         param_lscm_begin(handle, PARAM_FALSE);
1445         param_lscm_solve(handle);
1446         param_lscm_end(handle);
1447
1448         param_pack(handle);
1449         param_flush(handle);
1450
1451         param_delete(handle);
1452
1453         BIF_undo_push("UV lscm unwrap");
1454
1455         object_uvs_changed(OBACT);
1456
1457         allqueue(REDRAWVIEW3D, 0);
1458         allqueue(REDRAWIMAGE, 0);
1459 }
1460
1461 void minimize_stretch_tface_uv(void)
1462 {
1463         Mesh *me;
1464         ParamHandle *handle;
1465         double lasttime;
1466         short doit = 1, escape = 0, val, blend = 0;
1467         unsigned short event = 0;
1468         
1469         me = get_mesh(OBACT);
1470         if(me==0 || me->tface==0) return;
1471
1472         handle = construct_param_handle(me, 1, 0);
1473
1474         lasttime = PIL_check_seconds_timer();
1475
1476         param_stretch_begin(handle);
1477
1478         while (doit) {
1479                 param_stretch_iter(handle);
1480
1481                 while (qtest()) {
1482                         event= extern_qread(&val);
1483
1484                         if (val) {
1485                                 switch (event) {
1486                                         case ESCKEY:
1487                                                 escape = 1;
1488                                         case RETKEY:
1489                                         case PADENTER:
1490                                                 doit = 0;
1491                                                 break;
1492                                         case PADPLUSKEY:
1493                                         case WHEELUPMOUSE:
1494                                                 if (blend < 10) {
1495                                                         blend++;
1496                                                         param_stretch_blend(handle, blend*0.1f);
1497                                                         param_flush(handle);
1498                                                         lasttime = 0.0f;
1499                                                 }
1500                                                 break;
1501                                         case PADMINUS:
1502                                         case WHEELDOWNMOUSE:
1503                                                 if (blend > 0) {
1504                                                         blend--;
1505                                                         param_stretch_blend(handle, blend*0.1f);
1506                                                         param_flush(handle);
1507                                                         lasttime = 0.0f;
1508                                                 }
1509                                                 break;
1510                                 }
1511                         }
1512                         else if ((event == LEFTMOUSE) || (event == RIGHTMOUSE)) {
1513                                         escape = (event == RIGHTMOUSE);
1514                                         doit = 0;
1515                         }
1516                 }
1517                 
1518                 if (!doit)
1519                         break;
1520
1521                 if (PIL_check_seconds_timer() - lasttime > 0.5) {
1522                         char str[100];
1523
1524                         param_flush(handle);
1525
1526                         sprintf(str, "Stretch minimize. Blend %.2f.", blend*0.1f);
1527                         headerprint(str);
1528
1529                         lasttime = PIL_check_seconds_timer();
1530                         if(G.sima->lock) force_draw_plus(SPACE_VIEW3D, 0);
1531                         else force_draw(0);
1532                 }
1533         }
1534
1535         if (escape)
1536                 param_flush_restore(handle);
1537         else
1538                 param_flush(handle);
1539
1540         param_stretch_end(handle);
1541
1542         param_delete(handle);
1543
1544         BIF_undo_push("UV stretch minimize");
1545
1546         object_uvs_changed(OBACT);
1547
1548         allqueue(REDRAWVIEW3D, 0);
1549         allqueue(REDRAWIMAGE, 0);
1550 }
1551
1552 /* LSCM live mode */
1553
1554 static ParamHandle *liveHandle = NULL;
1555
1556 void unwrap_lscm_live_begin(void)
1557 {
1558         Mesh *me;
1559
1560         if (CurrentUnwrapper == 0)
1561                 return;
1562         
1563         me= get_mesh(OBACT);
1564         if(me==0 || me->tface==0) return;
1565
1566         liveHandle = construct_param_handle(me, 0, 0);
1567
1568         param_lscm_begin(liveHandle, PARAM_TRUE);
1569 }
1570
1571 void unwrap_lscm_live_re_solve(void)
1572 {
1573         if (CurrentUnwrapper == 0) {
1574                 unwrap_lscm();
1575                 return;
1576         }
1577
1578         if (liveHandle) {
1579                 param_lscm_solve(liveHandle);
1580                 param_flush(liveHandle);
1581         }
1582 }
1583         
1584 void unwrap_lscm_live_end(void)
1585 {
1586         if (CurrentUnwrapper == 0)
1587                 return;
1588
1589         if (liveHandle) {
1590                 param_lscm_end(liveHandle);
1591                 param_delete(liveHandle);
1592                 liveHandle = NULL;
1593         }
1594 }
1595