Mesh Deform Modifier
[blender.git] / source / blender / src / parametrizer.c
index 65ebdd68e2d1fa541577c19d97f66f3b1cf1cc12..d0a51027ad311d88f2aaf435c1374cec562db387 100644 (file)
@@ -5,6 +5,7 @@
 #include "BLI_arithb.h"
 #include "BLI_rand.h"
 #include "BLI_heap.h"
+#include "BLI_boxpack2d.h"
 
 #include "BKE_utildefines.h"
 
@@ -144,8 +145,8 @@ static float p_vec_angle_cos(float *v1, float *v2, float *v3)
        d2[1] = v3[1] - v2[1];
        d2[2] = v3[2] - v2[2];
 
-       Normalise(d1);
-       Normalise(d2);
+       Normalize(d1);
+       Normalize(d2);
 
        return d1[0]*d2[0] + d1[1]*d2[1] + d1[2]*d2[2];
 }
@@ -211,23 +212,6 @@ static float p_face_uv_area_signed(PFace *f)
                    ((v3->uv[0] - v1->uv[0])*(v2->uv[1] - v1->uv[1])));
 }
 
-static float p_face_uv_area(PFace *f)
-{
-       return fabs(p_face_uv_area_signed(f));
-}
-
-static void p_chart_area(PChart *chart, float *uv_area, float *area)
-{
-       PFace *f;
-
-       *uv_area = *area = 0.0f;
-
-       for (f=chart->faces; f; f=f->nextlink) {
-               *uv_area += p_face_uv_area(f);
-               *area += p_face_area(f);
-       }
-}
-
 static float p_edge_length(PEdge *e)
 {
     PVert *v1 = e->vert, *v2 = e->next->vert;
@@ -600,12 +584,12 @@ static PBool p_edge_implicit_seam(PEdge *e, PEdge *ep)
                uvp2 = ep->orig_uv;
        }
 
-       if((fabs(uv1[0]-uvp1[0]) > limit[0]) && (fabs(uv1[1]-uvp1[1]) > limit[1])) {
+       if((fabs(uv1[0]-uvp1[0]) > limit[0]) || (fabs(uv1[1]-uvp1[1]) > limit[1])) {
                e->flag |= PEDGE_SEAM;
                ep->flag |= PEDGE_SEAM;
                return P_TRUE;
        }
-       if((fabs(uv2[0]-uvp2[0]) > limit[0]) && (fabs(uv2[1]-uvp2[1]) > limit[1])) {
+       if((fabs(uv2[0]-uvp2[0]) > limit[0]) || (fabs(uv2[1]-uvp2[1]) > limit[1])) {
                e->flag |= PEDGE_SEAM;
                ep->flag |= PEDGE_SEAM;
                return P_TRUE;
@@ -2229,7 +2213,7 @@ static PBool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
        nlBegin(NL_MATRIX);
 
        for (i = 0; i < nvar; i++)
-               nlRightHandSideAdd(i, sys->bInterior[i]);
+               nlRightHandSideAdd(0, i, sys->bInterior[i]);
 
        for (f=chart->faces; f; f=f->nextlink) {
                float wi1, wi2, wi3, b, si, beta[3], j2[3][3], W[3][3];
@@ -2275,8 +2259,8 @@ static PBool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
                        sys->J2dt[e2->u.id][0] = j2[1][0] = p_abf_compute_sin_product(sys, v1, e2->u.id)*wi2;
                        sys->J2dt[e3->u.id][0] = j2[2][0] = p_abf_compute_sin_product(sys, v1, e3->u.id)*wi3;
 
-                       nlRightHandSideAdd(v1->u.id, j2[0][0]*beta[0]);
-                       nlRightHandSideAdd(ninterior + v1->u.id, j2[1][0]*beta[1] + j2[2][0]*beta[2]);
+                       nlRightHandSideAdd(0, v1->u.id, j2[0][0]*beta[0]);
+                       nlRightHandSideAdd(0, ninterior + v1->u.id, j2[1][0]*beta[1] + j2[2][0]*beta[2]);
 
                        row1[0] = j2[0][0]*W[0][0];
                        row2[0] = j2[0][0]*W[1][0];
@@ -2295,8 +2279,8 @@ static PBool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
                        sys->J2dt[e2->u.id][1] = j2[1][1] = 1.0*wi2;
                        sys->J2dt[e3->u.id][1] = j2[2][1] = p_abf_compute_sin_product(sys, v2, e3->u.id)*wi3;
 
-                       nlRightHandSideAdd(v2->u.id, j2[1][1]*beta[1]);
-                       nlRightHandSideAdd(ninterior + v2->u.id, j2[0][1]*beta[0] + j2[2][1]*beta[2]);
+                       nlRightHandSideAdd(0, v2->u.id, j2[1][1]*beta[1]);
+                       nlRightHandSideAdd(0, ninterior + v2->u.id, j2[0][1]*beta[0] + j2[2][1]*beta[2]);
 
                        row1[1] = j2[1][1]*W[0][1];
                        row2[1] = j2[1][1]*W[1][1];
@@ -2315,8 +2299,8 @@ static PBool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
                        sys->J2dt[e2->u.id][2] = j2[1][2] = p_abf_compute_sin_product(sys, v3, e2->u.id)*wi2;
                        sys->J2dt[e3->u.id][2] = j2[2][2] = 1.0*wi3;
 
-                       nlRightHandSideAdd(v3->u.id, j2[2][2]*beta[2]);
-                       nlRightHandSideAdd(ninterior + v3->u.id, j2[0][2]*beta[0] + j2[1][2]*beta[1]);
+                       nlRightHandSideAdd(0, v3->u.id, j2[2][2]*beta[2]);
+                       nlRightHandSideAdd(0, ninterior + v3->u.id, j2[0][2]*beta[0] + j2[1][2]*beta[1]);
 
                        row1[2] = j2[2][2]*W[0][2];
                        row2[2] = j2[2][2]*W[1][2];
@@ -2373,24 +2357,24 @@ static PBool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
                        pre[0] = pre[1] = pre[2] = 0.0;
 
                        if (v1->flag & PVERT_INTERIOR) {
-                               float x = nlGetVariable(v1->u.id);
-                               float x2 = nlGetVariable(ninterior + v1->u.id);
+                               float x = nlGetVariable(0, v1->u.id);
+                               float x2 = nlGetVariable(0, ninterior + v1->u.id);
                                pre[0] += sys->J2dt[e1->u.id][0]*x;
                                pre[1] += sys->J2dt[e2->u.id][0]*x2;
                                pre[2] += sys->J2dt[e3->u.id][0]*x2;
                        }
 
                        if (v2->flag & PVERT_INTERIOR) {
-                               float x = nlGetVariable(v2->u.id);
-                               float x2 = nlGetVariable(ninterior + v2->u.id);
+                               float x = nlGetVariable(0, v2->u.id);
+                               float x2 = nlGetVariable(0, ninterior + v2->u.id);
                                pre[0] += sys->J2dt[e1->u.id][1]*x2;
                                pre[1] += sys->J2dt[e2->u.id][1]*x;
                                pre[2] += sys->J2dt[e3->u.id][1]*x2;
                        }
 
                        if (v3->flag & PVERT_INTERIOR) {
-                               float x = nlGetVariable(v3->u.id);
-                               float x2 = nlGetVariable(ninterior + v3->u.id);
+                               float x = nlGetVariable(0, v3->u.id);
+                               float x2 = nlGetVariable(0, ninterior + v3->u.id);
                                pre[0] += sys->J2dt[e1->u.id][2]*x2;
                                pre[1] += sys->J2dt[e2->u.id][2]*x2;
                                pre[2] += sys->J2dt[e3->u.id][2]*x;
@@ -2421,8 +2405,8 @@ static PBool p_abf_matrix_invert(PAbfSystem *sys, PChart *chart)
                }
 
                for (i = 0; i < ninterior; i++) {
-                       sys->lambdaPlanar[i] += nlGetVariable(i);
-                       sys->lambdaLength[i] += nlGetVariable(ninterior + i);
+                       sys->lambdaPlanar[i] += nlGetVariable(0, i);
+                       sys->lambdaLength[i] += nlGetVariable(0, ninterior + i);
                }
        }
 
@@ -2522,13 +2506,6 @@ static PBool p_chart_abf_solve(PChart *chart)
                for (i = 0; i < ABF_MAX_ITER; i++) {
                        float norm = p_abf_compute_gradient(&sys, chart);
 
-#if 0
-                       if (norm > lastnorm)
-                               printf("convergence error: %f => %f\n", lastnorm, norm);
-                       else
-                               printf("norm: %f\n", norm);
-#endif
-
                        lastnorm = norm;
 
                        if (norm < limit)
@@ -2572,7 +2549,7 @@ static void p_chart_pin_positions(PChart *chart, PVert **pin1, PVert **pin2)
                (*pin2)->uv[1] = 0.5f;
        }
        else {
-               int diru, dirv, dir;
+               int diru, dirv, dirx, diry;
                float sub[3];
 
                VecSubf(sub, (*pin1)->co, (*pin2)->co);
@@ -2580,14 +2557,20 @@ static void p_chart_pin_positions(PChart *chart, PVert **pin1, PVert **pin2)
                sub[1] = fabs(sub[1]);
                sub[2] = fabs(sub[2]);
 
-               if ((sub[0] > sub[1]) && (sub[0] > sub[2]))
-                       dir = 0;
-               else if ((sub[1] > sub[0]) && (sub[1] > sub[2]))
-                       dir = 1;
-               else
-                       dir = 2;
+               if ((sub[0] > sub[1]) && (sub[0] > sub[2])) {
+                       dirx = 0;
+                       diry = (sub[1] > sub[2])? 1: 2;
+               }
+               else if ((sub[1] > sub[0]) && (sub[1] > sub[2])) {
+                       dirx = 1;
+                       diry = (sub[0] > sub[2])? 0: 2;
+               }
+               else {
+                       dirx = 2;
+                       diry = (sub[0] > sub[1])? 0: 1;
+               }
 
-               if (dir == 2) {
+               if (dirx == 2) {
                        diru = 1;
                        dirv = 0;
                }
@@ -2596,10 +2579,10 @@ static void p_chart_pin_positions(PChart *chart, PVert **pin1, PVert **pin2)
                        dirv = 1;
                }
 
-               (*pin1)->uv[diru] = (*pin1)->co[dir];
-               (*pin1)->uv[dirv] = (*pin1)->co[(dir+1)%3];
-               (*pin2)->uv[diru] = (*pin2)->co[dir];
-               (*pin2)->uv[dirv] = (*pin2)->co[(dir+1)%3];
+               (*pin1)->uv[diru] = (*pin1)->co[dirx];
+               (*pin1)->uv[dirv] = (*pin1)->co[diry];
+               (*pin2)->uv[diru] = (*pin2)->co[dirx];
+               (*pin2)->uv[dirv] = (*pin2)->co[diry];
        }
 }
 
@@ -2661,7 +2644,7 @@ static PBool p_chart_symmetry_pins(PChart *chart, PEdge *outer, PVert **pin1, PV
                }
        }
 
-       if (!maxe1 || (maxlen < 0.5f*totlen))
+       if (!maxe1 || !maxe2 || (maxlen < 0.5f*totlen))
                return P_FALSE;
        
        /* find pin1 in the split vertices */
@@ -2755,8 +2738,8 @@ static void p_chart_lscm_load_solution(PChart *chart)
        PVert *v;
 
        for (v=chart->verts; v; v=v->nextlink) {
-               v->uv[0] = nlGetVariable(2*v->u.id);
-               v->uv[1] = nlGetVariable(2*v->u.id + 1);
+               v->uv[0] = nlGetVariable(0, 2*v->u.id);
+               v->uv[1] = nlGetVariable(0, 2*v->u.id + 1);
        }
 }
 
@@ -2788,8 +2771,6 @@ static void p_chart_lscm_begin(PChart *chart, PBool live, PBool abf)
 #endif
 
                if (abf) {
-                       PBool p_chart_abf_solve(PChart *chart);
-
                        if (!p_chart_abf_solve(chart))
                                param_warning("ABF solving failed: falling back to LSCM.\n");
                }
@@ -2815,6 +2796,7 @@ static void p_chart_lscm_begin(PChart *chart, PBool live, PBool abf)
 
                nlNewContext();
                nlSolverParameteri(NL_NB_VARIABLES, 2*chart->nverts);
+               nlSolverParameteri(NL_NB_ROWS, 2*chart->nfaces);
                nlSolverParameteri(NL_LEAST_SQUARES, NL_TRUE);
 
                chart->u.lscm.context = nlGetCurrent();
@@ -2826,6 +2808,7 @@ static PBool p_chart_lscm_solve(PChart *chart)
        PVert *v, *pin1 = chart->u.lscm.pin1, *pin2 = chart->u.lscm.pin2;
        PFace *f;
        float *alpha = chart->u.lscm.abf_alpha;
+       int row;
 
        nlMakeCurrent(chart->u.lscm.context);
 
@@ -2845,10 +2828,10 @@ static PBool p_chart_lscm_solve(PChart *chart)
                nlLockVariable(2*pin2->u.id);
                nlLockVariable(2*pin2->u.id + 1);
        
-               nlSetVariable(2*pin1->u.id, pin1->uv[0]);
-               nlSetVariable(2*pin1->u.id + 1, pin1->uv[1]);
-               nlSetVariable(2*pin2->u.id, pin2->uv[0]);
-               nlSetVariable(2*pin2->u.id + 1, pin2->uv[1]);
+               nlSetVariable(0, 2*pin1->u.id, pin1->uv[0]);
+               nlSetVariable(0, 2*pin1->u.id + 1, pin1->uv[1]);
+               nlSetVariable(0, 2*pin2->u.id, pin2->uv[0]);
+               nlSetVariable(0, 2*pin2->u.id + 1, pin2->uv[1]);
        }
        else {
                /* set and lock the pins */
@@ -2857,8 +2840,8 @@ static PBool p_chart_lscm_solve(PChart *chart)
                                nlLockVariable(2*v->u.id);
                                nlLockVariable(2*v->u.id + 1);
 
-                               nlSetVariable(2*v->u.id, v->uv[0]);
-                               nlSetVariable(2*v->u.id + 1, v->uv[1]);
+                               nlSetVariable(0, 2*v->u.id, v->uv[0]);
+                               nlSetVariable(0, 2*v->u.id + 1, v->uv[1]);
                        }
                }
        }
@@ -2867,6 +2850,7 @@ static PBool p_chart_lscm_solve(PChart *chart)
 
        nlBegin(NL_MATRIX);
 
+       row = 0;
        for (f=chart->faces; f; f=f->nextlink) {
                PEdge *e1 = f->edge, *e2 = e1->next, *e3 = e2->next;
                PVert *v1 = e1->vert, *v2 = e2->vert, *v3 = e3->vert;
@@ -2905,10 +2889,11 @@ static PBool p_chart_lscm_solve(PChart *chart)
                }
 
                /* angle based lscm formulation */
-               ratio = (sina3 == 0.0f)? 0.0f: sina2/sina3;
+               ratio = (sina3 == 0.0f)? 1.0f: sina2/sina3;
                cosine = cos(a1)*ratio;
                sine = sina1*ratio;
 
+#if 0
                nlBegin(NL_ROW);
                nlCoefficient(2*v1->u.id,   cosine - 1.0);
                nlCoefficient(2*v1->u.id+1, -sine);
@@ -2924,6 +2909,21 @@ static PBool p_chart_lscm_solve(PChart *chart)
                nlCoefficient(2*v2->u.id+1, -cosine);
                nlCoefficient(2*v3->u.id+1, 1.0);
                nlEnd(NL_ROW);
+#else
+               nlMatrixAdd(row, 2*v1->u.id,   cosine - 1.0);
+               nlMatrixAdd(row, 2*v1->u.id+1, -sine);
+               nlMatrixAdd(row, 2*v2->u.id,   -cosine);
+               nlMatrixAdd(row, 2*v2->u.id+1, sine);
+               nlMatrixAdd(row, 2*v3->u.id,   1.0);
+               row++;
+
+               nlMatrixAdd(row, 2*v1->u.id,   sine);
+               nlMatrixAdd(row, 2*v1->u.id+1, cosine - 1.0);
+               nlMatrixAdd(row, 2*v2->u.id,   -sine);
+               nlMatrixAdd(row, 2*v2->u.id+1, -cosine);
+               nlMatrixAdd(row, 2*v3->u.id+1, 1.0);
+               row++;
+#endif
        }
 
        nlEnd(NL_MATRIX);
@@ -2934,6 +2934,12 @@ static PBool p_chart_lscm_solve(PChart *chart)
                p_chart_lscm_load_solution(chart);
                return P_TRUE;
        }
+       else {
+               for (v=chart->verts; v; v=v->nextlink) {
+                       v->uv[0] = 0.0f;
+                       v->uv[1] = 0.0f;
+               }
+       }
 
        return P_FALSE;
 }
@@ -3099,144 +3105,6 @@ static void p_chart_stretch_minimize(PChart *chart, RNG *rng)
        }
 }
 
-/* Packing */
-
-static int p_compare_chart_area(const void *a, const void *b)
-{
-       PChart *ca = *((PChart**)a);
-       PChart *cb = *((PChart**)b);
-
-    if (ca->u.pack.area > cb->u.pack.area)
-               return -1;
-       else if (ca->u.pack.area == cb->u.pack.area)
-               return 0;
-       else
-               return 1;
-}
-
-static PBool p_pack_try(PHandle *handle, float side)
-{
-       PChart *chart;
-       float packx, packy, rowh, groupw, w, h;
-       int i;
-
-       packx= packy= 0.0;
-       rowh= 0.0;
-       groupw= 1.0/sqrt(handle->ncharts);
-
-       for (i = 0; i < handle->ncharts; i++) {
-               chart = handle->charts[i];
-
-               if (chart->flag & PCHART_NOPACK)
-                       continue;
-
-               w = chart->u.pack.size[0];
-               h = chart->u.pack.size[1];
-
-               if(w <= (side-packx)) {
-                       chart->u.pack.trans[0] = packx;
-                       chart->u.pack.trans[1] = packy;
-
-                       packx += w;
-                       rowh= MAX2(rowh, h);
-               }
-               else {
-                       packy += rowh;
-                       packx = w;
-                       rowh = h;
-
-                       chart->u.pack.trans[0] = 0.0;
-                       chart->u.pack.trans[1] = packy;
-               }
-
-               if (packy+rowh > side)
-                       return P_FALSE;
-       }
-
-       return P_TRUE;
-}
-
-#define PACK_SEARCH_DEPTH 15
-
-void p_charts_pack(PHandle *handle)
-{
-       PChart *chart;
-       float uv_area, area, trans[2], minside, maxside, totarea, side;
-       int i;
-
-       /* very simple rectangle packing */
-
-       if (handle->ncharts == 0)
-               return;
-
-       totarea = 0.0f;
-       maxside = 0.0f;
-
-       for (i = 0; i < handle->ncharts; i++) {
-               chart = handle->charts[i];
-
-               if (chart->flag & PCHART_NOPACK) {
-                       chart->u.pack.area = 0.0f;
-                       continue;
-               }
-
-               p_chart_area(chart, &uv_area, &area);
-               p_chart_uv_bbox(chart, trans, chart->u.pack.size);
-
-               /* translate to origin and make area equal to 3d area */
-               chart->u.pack.rescale = (uv_area > 0.0f)? sqrt(area)/sqrt(uv_area): 0.0f;
-               chart->u.pack.area = area;
-               totarea += area;
-
-               trans[0] = -trans[0];
-               trans[1] = -trans[1];
-               p_chart_uv_translate(chart, trans);
-               p_chart_uv_scale(chart, chart->u.pack.rescale);
-
-               /* compute new dimensions for packing */
-               chart->u.pack.size[0] += trans[0];
-               chart->u.pack.size[1] += trans[1];
-               chart->u.pack.size[0] *= chart->u.pack.rescale;
-               chart->u.pack.size[1] *= chart->u.pack.rescale;
-
-               maxside = MAX3(maxside, chart->u.pack.size[0], chart->u.pack.size[1]);
-       }
-
-       /* sort by chart area, largest first */
-       qsort(handle->charts, handle->ncharts, sizeof(PChart*), p_compare_chart_area);
-
-       /* binary search over pack region size */
-       minside = MAX2(sqrt(totarea), maxside);
-       maxside = (((int)sqrt(handle->ncharts-1))+1)*maxside;
-
-       if (minside < maxside) { /* should always be true */
-
-               for (i = 0; i < PACK_SEARCH_DEPTH; i++) {
-                       if (p_pack_try(handle, (minside+maxside)*0.5f + 1e-5))
-                               maxside = (minside+maxside)*0.5f;
-                       else
-                               minside = (minside+maxside)*0.5f;
-               }
-       }
-
-       /* do the actual packing */
-       side = maxside + 1e-5;
-       if (!p_pack_try(handle, side))
-               param_warning("packing failed.\n");
-
-       for (i = 0; i < handle->ncharts; i++) {
-               chart = handle->charts[i];
-
-               if (chart->flag & PCHART_NOPACK)
-                       continue;
-
-               p_chart_uv_scale(chart, 1.0f/side);
-               trans[0] = chart->u.pack.trans[0]/side;
-               trans[1] = chart->u.pack.trans[1]/side;
-               p_chart_uv_translate(chart, trans);
-       }
-}
-
 /* Minimum area enclosing rectangle for packing */
 
 static int p_compare_geometric_uv(const void *a, const void *b)
@@ -4132,8 +4000,8 @@ void param_lscm_solve(ParamHandle *handle)
                if (chart->u.lscm.context) {
                        result = p_chart_lscm_solve(chart);
 
-                       /*if (result)
-                               p_chart_rotate_minimum_area(chart);*/
+                       if (result && !(chart->flag & PCHART_NOPACK))
+                               p_chart_rotate_minimum_area(chart);
 
                        if (!result || (chart->u.lscm.pin1))
                                p_chart_lscm_end(chart);
@@ -4237,10 +4105,66 @@ void param_smooth_area(ParamHandle *handle)
                p_smooth(chart);
        }
 }
-
 void param_pack(ParamHandle *handle)
 {
-       p_charts_pack((PHandle*)handle);
+       /* box packing variables */
+       boxPack *boxarray, *box;
+       float tot_width, tot_height, scale;
+        
+       PChart *chart;
+       int i, unpacked=0;
+       float trans[2];
+       
+       PHandle *phandle = (PHandle*)handle;
+       
+       
+       if (phandle->ncharts == 0)
+               return;
+       
+       /* we may not use all these boxes */
+       boxarray = MEM_mallocN( phandle->ncharts*sizeof(boxPack), "boxPack box");
+       
+       for (i = 0; i < phandle->ncharts; i++) {
+               chart = phandle->charts[i];
+               
+               
+               if (chart->flag & PCHART_NOPACK) {
+                       unpacked++;
+                       continue;
+               }
+               
+               box = boxarray+(i-unpacked);
+               
+               p_chart_uv_bbox(chart, trans, chart->u.pack.size);
+               
+               trans[0] = -trans[0];
+               trans[1] = -trans[1];
+               
+               p_chart_uv_translate(chart, trans);
+               
+               box->w =  chart->u.pack.size[0] + trans[0];
+               box->h =  chart->u.pack.size[1] + trans[1];
+               box->index = i; /* warning this index skips PCHART_NOPACK boxes */
+       }
+       
+       boxPack2D(boxarray, phandle->ncharts-unpacked, &tot_width, &tot_height);
+       
+       if (tot_height>tot_width)
+               scale = 1.0/tot_height;
+       else
+               scale = 1.0/tot_width;
+       
+       for (i = 0; i < phandle->ncharts-unpacked; i++) {
+               box = boxarray+i;
+               trans[0] = box->x;
+               trans[1] = box->y;
+               
+               chart = phandle->charts[box->index];
+               p_chart_uv_translate(chart, trans);
+               p_chart_uv_scale(chart, scale);
+       }
+       MEM_freeN(boxarray);
 }
 
 void param_flush(ParamHandle *handle)