← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/blender/gutsy-security

« back to all changes in this revision

Viewing changes to source/blender/src/unwrapper.c

  • Committer: Bazaar Package Importer
  • Author(s): Florian Ernst
  • Date: 2005-11-06 12:40:03 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051106124003-3pgs7tcg5rox96xg
Tags: 2.37a-1.1
http://bugs.debian.org/333958
* Non-maintainer upload.
* Split out parts of 01_SConstruct_debian.dpatch again: root_build_dir
  really needs to get adjusted before the clean target runs - closes: #333958,
  see #288882 for reference

Show diffs side-by-side

added added

removed removed

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