source/blender/blenkernel/intern/multires.c

   1 /*
   2  * $Id$
   3  *
   4  * ***** BEGIN GPL LICENSE BLOCK *****
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License
   8  * as published by the Free Software Foundation; either version 2
   9  * of the License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software  Foundation,
  18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  19  *
  20  * The Original Code is Copyright (C) 2007 by Nicholas Bishop
  21  * All rights reserved.
  22  *
  23  * The Original Code is: all of this file.
  24  *
  25  * Contributor(s): none yet.
  26  *
  27  * ***** END GPL LICENSE BLOCK *****
  28  */
  29
  30 #include "MEM_guardedalloc.h"
  31
  32 #include "DNA_key_types.h"
  33 #include "DNA_mesh_types.h"
  34 #include "DNA_meshdata_types.h"
  35 #include "DNA_modifier_types.h"
  36 #include "DNA_object_types.h"
  37 #include "DNA_scene_types.h"
  38 #include "DNA_view3d_types.h"
  39
  40 #include "BLI_arithb.h"
  41 #include "BLI_blenlib.h"
  42
  43 #include "BKE_cdderivedmesh.h"
  44 #include "BKE_customdata.h"
  45 #include "BKE_depsgraph.h"
  46 #include "BKE_DerivedMesh.h"
  47 #include "BKE_global.h"
  48 #include "BKE_mesh.h"
  49 #include "BKE_modifier.h"
  50 #include "BKE_multires.h"
  51 #include "BKE_object.h"
  52 #include "BKE_subsurf.h"
  53
  54 #include <math.h>
  55 #include <string.h>
  56
  57 /* MULTIRES MODIFIER */
  58 static const int multires_max_levels = 13;
  59 static const int multires_quad_tot[] = {4, 9, 25, 81, 289, 1089, 4225, 16641, 66049, 263169, 1050625, 4198401, 16785409};
  60 static const int multires_side_tot[] = {2, 3, 5,  9,  17,  33,   65,   129,   257,   513,    1025,    2049,    4097};
  61
  62 MultiresModifierData *find_multires_modifier(Object *ob)
  63 {
  64         ModifierData *md;
  65         MultiresModifierData *mmd = NULL;
  66
  67         for(md = ob->modifiers.first; md; md = md->next) {
  68                 if(md->type == eModifierType_Multires) {
  69                         mmd = (MultiresModifierData*)md;
  70                         break;
  71                 }
  72         }
  73
  74         return mmd;
  75
  76 }
  77
  78 int multiresModifier_switch_level(Object *ob, const int distance)
  79 {
  80         MultiresModifierData *mmd = find_multires_modifier(ob);
  81
  82         if(mmd) {
  83                 mmd->lvl += distance;
  84                 if(mmd->lvl < 1) mmd->lvl = 1;
  85                 else if(mmd->lvl > mmd->totlvl) mmd->lvl = mmd->totlvl;
  86                 /* XXX: DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
  87                    object_handle_update(ob);*/
  88                 return 1;
  89         }
  90         else
  91                 return 0;
  92 }
  93
  94 /* XXX */
  95 #if 0
  96 void multiresModifier_join(Object *ob)
  97 {
  98         Base *base = NULL;
  99         int highest_lvl = 0;
 100
 101         /* First find the highest level of subdivision */
 102         base = FIRSTBASE;
 103         while(base) {
 104                 if(TESTBASELIB_BGMODE(v3d, base) && base->object->type==OB_MESH) {
 105                         ModifierData *md;
 106                         for(md = base->object->modifiers.first; md; md = md->next) {
 107                                 if(md->type == eModifierType_Multires) {
 108                                         int totlvl = ((MultiresModifierData*)md)->totlvl;
 109                                         if(totlvl > highest_lvl)
 110                                                 highest_lvl = totlvl;
 111
 112                                         /* Ensure that all updates are processed */
 113                                         multires_force_update(base->object);
 114                                 }
 115                         }
 116                 }
 117                 base = base->next;
 118         }
 119
 120         /* No multires meshes selected */
 121         if(highest_lvl == 0)
 122                 return;
 123
 124         /* Subdivide all the displacements to the highest level */
 125         base = FIRSTBASE;
 126         while(base) {
 127                 if(TESTBASELIB_BGMODE(v3d, base) && base->object->type==OB_MESH) {
 128                         ModifierData *md = NULL;
 129                         MultiresModifierData *mmd = NULL;
 130
 131                         for(md = base->object->modifiers.first; md; md = md->next) {
 132                                 if(md->type == eModifierType_Multires)
 133                                         mmd = (MultiresModifierData*)md;
 134                         }
 135
 136                         /* If the object didn't have multires enabled, give it a new modifier */
 137                         if(!mmd) {
 138                                 md = base->object->modifiers.first;
 139
 140                                 while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
 141                                         md = md->next;
 142
 143                                 mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
 144                                 BLI_insertlinkbefore(&base->object->modifiers, md, mmd);
 145                         }
 146
 147                         if(mmd)
 148                                 multiresModifier_subdivide(mmd, base->object, highest_lvl - mmd->totlvl, 0, 0);
 149                 }
 150                 base = base->next;
 151         }
 152 }
 153 #endif
 154
 155 /* Returns 0 on success, 1 if the src's totvert doesn't match */
 156 int multiresModifier_reshape(MultiresModifierData *mmd, Object *dst, Object *src)
 157 {
 158         Mesh *src_me = get_mesh(src);
 159         DerivedMesh *mrdm = dst->derivedFinal;
 160
 161         if(mrdm && mrdm->getNumVerts(mrdm) == src_me->totvert) {
 162                 MVert *mvert = CDDM_get_verts(mrdm);
 163                 int i;
 164
 165                 for(i = 0; i < src_me->totvert; ++i)
 166                         VecCopyf(mvert[i].co, src_me->mvert[i].co);
 167                 mrdm->needsFree = 1;
 168                 MultiresDM_mark_as_modified(mrdm);
 169                 mrdm->release(mrdm);
 170                 dst->derivedFinal = NULL;
 171
 172                 return 0;
 173         }
 174
 175         return 1;
 176 }
 177
 178 static void Mat3FromColVecs(float mat[][3], float v1[3], float v2[3], float v3[3])
 179 {
 180         VecCopyf(mat[0], v1);
 181         VecCopyf(mat[1], v2);
 182         VecCopyf(mat[2], v3);
 183 }
 184
 185 static DerivedMesh *multires_subdisp_pre(DerivedMesh *mrdm, int distance, int simple)
 186 {
 187         DerivedMesh *final;
 188         SubsurfModifierData smd;
 189
 190         memset(&smd, 0, sizeof(SubsurfModifierData));
 191         smd.levels = distance;
 192         if(simple)
 193                 smd.subdivType = ME_SIMPLE_SUBSURF;
 194
 195         final = subsurf_make_derived_from_derived_with_multires(mrdm, &smd, NULL, 0, NULL, 0, 0);
 196
 197         return final;
 198 }
 199
 200 static void VecAddUf(float a[3], float b[3])
 201 {
 202         a[0] += b[0];
 203         a[1] += b[1];
 204         a[2] += b[2];
 205 }
 206
 207 static void multires_subdisp(DerivedMesh *orig, Mesh *me, DerivedMesh *final, int lvl, int totlvl,
 208                              int totsubvert, int totsubedge, int totsubface, int addverts)
 209 {
 210         DerivedMesh *mrdm;
 211         MultiresModifierData mmd_sub;
 212         MVert *mvs = CDDM_get_verts(final);
 213         MVert *mvd, *mvd_f1, *mvs_f1, *mvd_f3, *mvd_f4;
 214         MVert *mvd_f2, *mvs_f2, *mvs_e1, *mvd_e1, *mvs_e2;
 215         int totvert;
 216         int slo1 = multires_side_tot[lvl - 1];
 217         int sll = slo1 / 2;
 218         int slo2 = multires_side_tot[totlvl - 2];
 219         int shi2 = multires_side_tot[totlvl - 1];
 220         int skip = multires_side_tot[totlvl - lvl] - 1;
 221         int i, j, k;
 222
 223         mmd_sub.lvl = mmd_sub.totlvl = totlvl;
 224         mrdm = multires_dm_create_from_derived(&mmd_sub, orig, me, 0, 0);
 225
 226         mvd = CDDM_get_verts(mrdm);
 227         /* Need to map from ccg to mrdm */
 228         totvert = mrdm->getNumVerts(mrdm);
 229
 230         if(!addverts) {
 231                 for(i = 0; i < totvert; ++i) {
 232                         float z[3] = {0,0,0};
 233                         VecCopyf(mvd[i].co, z);
 234                 }
 235         }
 236
 237         /* Load base verts */
 238         for(i = 0; i < me->totvert; ++i)
 239                 VecAddUf(mvd[totvert - me->totvert + i].co, mvs[totvert - me->totvert + i].co);
 240
 241         mvd_f1 = mvd;
 242         mvs_f1 = mvs;
 243         mvd_f2 = mvd;
 244         mvs_f2 = mvs + totvert - totsubvert;
 245         mvs_e1 = mvs + totsubface * (skip-1) * (skip-1);
 246
 247         for(i = 0; i < me->totface; ++i) {
 248                 const int end = me->mface[i].v4 ? 4 : 3;
 249                 int x, y, x2, y2, mov= 0;
 250
 251                 mvd_f1 += 1 + end * (slo2-2); //center+edgecross
 252                 mvd_f3 = mvd_f4 = mvd_f1;
 253
 254                 for(j = 0; j < end; ++j) {
 255                         mvd_f1 += (skip/2 - 1) * (slo2 - 2) + (skip/2 - 1);
 256                         /* Update sub faces */
 257                         for(y = 0; y < sll; ++y) {
 258                                 for(x = 0; x < sll; ++x) {
 259                                         /* Face center */
 260                                         VecAddUf(mvd_f1->co, mvs_f1->co);
 261                                         mvs_f1 += 1;
 262
 263                                         /* Now we hold the center of the subface at mvd_f1
 264                                            and offset it to the edge cross and face verts */
 265
 266                                         /* Edge cross */
 267                                         for(k = 0; k < 4; ++k) {
 268                                                 if(k == 0) mov = -1;
 269                                                 else if(k == 1) mov = slo2 - 2;
 270                                                 else if(k == 2) mov = 1;
 271                                                 else if(k == 3) mov = -(slo2 - 2);
 272
 273                                                 for(x2 = 1; x2 < skip/2; ++x2) {
 274                                                         VecAddUf((mvd_f1 + mov * x2)->co, mvs_f1->co);
 275                                                         ++mvs_f1;
 276                                                 }
 277                                         }
 278
 279                                         /* Main face verts */
 280                                         for(k = 0; k < 4; ++k) {
 281                                                 int movx= 0, movy= 0;
 282
 283                                                 if(k == 0) { movx = -1; movy = -(slo2 - 2); }
 284                                                 else if(k == 1) { movx = slo2 - 2; movy = -1; }
 285                                                 else if(k == 2) { movx = 1; movy = slo2 - 2; }
 286                                                 else if(k == 3) { movx = -(slo2 - 2); movy = 1; }
 287
 288                                                 for(y2 = 1; y2 < skip/2; ++y2) {
 289                                                         for(x2 = 1; x2 < skip/2; ++x2) {
 290                                                                 VecAddUf((mvd_f1 + movy * y2 + movx * x2)->co, mvs_f1->co);
 291                                                                 ++mvs_f1;
 292                                                         }
 293                                                 }
 294                                         }
 295
 296                                         mvd_f1 += skip;
 297                                 }
 298                                 mvd_f1 += (skip - 1) * (slo2 - 2) - 1;
 299                         }
 300                         mvd_f1 -= (skip - 1) * (slo2 - 2) - 1 + skip;
 301                         mvd_f1 += (slo2 - 2) * (skip/2-1) + skip/2-1 + 1;
 302                 }
 303
 304                 /* update face center verts */
 305                 VecAddUf(mvd_f2->co, mvs_f2->co);
 306
 307                 mvd_f2 += 1;
 308                 mvs_f2 += 1;
 309
 310                 /* update face edge verts */
 311                 for(j = 0; j < end; ++j) {
 312                         MVert *restore;
 313
 314                         /* Super-face edge cross */
 315                         for(k = 0; k < skip-1; ++k) {
 316                                 VecAddUf(mvd_f2->co, mvs_e1->co);
 317                                 mvd_f2++;
 318                                 mvs_e1++;
 319                         }
 320                         for(x = 1; x < sll; ++x) {
 321                                 VecAddUf(mvd_f2->co, mvs_f2->co);
 322                                 mvd_f2++;
 323                                 mvs_f2++;
 324
 325                                 for(k = 0; k < skip-1; ++k) {
 326                                         VecAddUf(mvd_f2->co, mvs_e1->co);
 327                                         mvd_f2++;
 328                                         mvs_e1++;
 329                                 }
 330                         }
 331
 332                         restore = mvs_e1;
 333                         for(y = 0; y < sll - 1; ++y) {
 334                                 for(x = 0; x < sll; ++x) {
 335                                         for(k = 0; k < skip - 1; ++k) {
 336                                                 VecAddUf(mvd_f3[(skip-1)+(y*skip) + (x*skip+k)*(slo2-2)].co,
 337                                                          mvs_e1->co);
 338                                                 ++mvs_e1;
 339                                         }
 340                                         mvs_e1 += skip-1;
 341                                 }
 342                         }
 343
 344                         mvs_e1 = restore + skip - 1;
 345                         for(y = 0; y < sll - 1; ++y) {
 346                                 for(x = 0; x < sll; ++x) {
 347                                         for(k = 0; k < skip - 1; ++k) {
 348                                                 VecAddUf(mvd_f3[(slo2-2)*(skip-1)+(x*skip)+k + y*skip*(slo2-2)].co,
 349                                                          mvs_e1->co);
 350                                                 ++mvs_e1;
 351                                         }
 352                                         mvs_e1 += skip - 1;
 353                                 }
 354                         }
 355
 356                         mvd_f3 += (slo2-2)*(slo2-2);
 357                         mvs_e1 -= skip - 1;
 358                 }
 359
 360                 /* update base (2) face verts */
 361                 for(j = 0; j < end; ++j) {
 362                         mvd_f2 += (slo2 - 1) * (skip - 1);
 363                         for(y = 0; y < sll - 1; ++y) {
 364                                 for(x = 0; x < sll - 1; ++x) {
 365                                         VecAddUf(mvd_f2->co, mvs_f2->co);
 366                                         mvd_f2 += skip;
 367                                         ++mvs_f2;
 368                                 }
 369                                 mvd_f2 += (slo2 - 1) * (skip - 1);
 370                         }
 371                         mvd_f2 -= (skip - 1);
 372                 }
 373         }
 374
 375         /* edges */
 376         mvd_e1 = mvd + totvert - me->totvert - me->totedge * (shi2-2);
 377         mvs_e2 = mvs + totvert - me->totvert - me->totedge * (slo1-2);
 378         for(i = 0; i < me->totedge; ++i) {
 379                 for(j = 0; j < skip - 1; ++j) {
 380                         VecAddUf(mvd_e1->co, mvs_e1->co);
 381                         mvd_e1++;
 382                         mvs_e1++;
 383                 }
 384                 for(j = 0; j < slo1 - 2; j++) {
 385                         VecAddUf(mvd_e1->co, mvs_e2->co);
 386                         mvd_e1++;
 387                         mvs_e2++;
 388
 389                         for(k = 0; k < skip - 1; ++k) {
 390                                 VecAddUf(mvd_e1->co, mvs_e1->co);
 391                                 mvd_e1++;
 392                                 mvs_e1++;
 393                         }
 394                 }
 395         }
 396
 397         final->needsFree = 1;
 398         final->release(final);
 399         mrdm->needsFree = 1;
 400         MultiresDM_mark_as_modified(mrdm);
 401         mrdm->release(mrdm);
 402 }
 403
 404 /* direction=1 for delete higher, direction=0 for lower (not implemented yet) */
 405 void multiresModifier_del_levels(struct MultiresModifierData *mmd, struct Object *ob, int direction)
 406 {
 407         Mesh *me = get_mesh(ob);
 408         int distance = mmd->totlvl - mmd->lvl;
 409         MDisps *mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
 410
 411         multires_force_update(ob);
 412
 413         if(mdisps && distance > 0 && direction == 1) {
 414                 int skip = multires_side_tot[distance] - 1;
 415                 int st = multires_side_tot[mmd->totlvl - 1];
 416                 int totdisp = multires_quad_tot[mmd->lvl - 1];
 417                 int i, j, x, y;
 418
 419                 for(i = 0; i < me->totface; ++i) {
 420                         float (*disps)[3] = MEM_callocN(sizeof(float) * 3 * totdisp, "multires del disps");
 421
 422                         for(j = 0, y = 0; y < st; y += skip) {
 423                                 for(x = 0; x < st; x += skip) {
 424                                         VecCopyf(disps[j], mdisps[i].disps[y * st + x]);
 425                                         ++j;
 426                                 }
 427                         }
 428
 429                         MEM_freeN(mdisps[i].disps);
 430                         mdisps[i].disps = disps;
 431                         mdisps[i].totdisp = totdisp;
 432                 }
 433         }
 434
 435         mmd->totlvl = mmd->lvl;
 436 }
 437
 438 void multiresModifier_subdivide(MultiresModifierData *mmd, Object *ob, int distance, int updateblock, int simple)
 439 {
 440         DerivedMesh *final = NULL;
 441         int totsubvert = 0, totsubface = 0, totsubedge = 0;
 442         Mesh *me = get_mesh(ob);
 443         MDisps *mdisps;
 444         int i;
 445
 446         if(distance == 0)
 447                 return;
 448
 449         if(mmd->totlvl > multires_max_levels)
 450                 mmd->totlvl = multires_max_levels;
 451         if(mmd->lvl > multires_max_levels)
 452                 mmd->lvl = multires_max_levels;
 453
 454         multires_force_update(ob);
 455
 456         mmd->lvl = mmd->totlvl;
 457         mmd->totlvl += distance;
 458
 459         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
 460         if(!mdisps)
 461                 mdisps = CustomData_add_layer(&me->fdata, CD_MDISPS, CD_DEFAULT, NULL, me->totface);
 462
 463         if(mdisps->disps && !updateblock && mmd->totlvl > 2) {
 464                 DerivedMesh *orig, *mrdm;
 465                 MultiresModifierData mmd_sub;
 466
 467                 orig = CDDM_from_mesh(me, NULL);
 468                 mmd_sub.lvl = mmd_sub.totlvl = mmd->lvl;
 469                 mrdm = multires_dm_create_from_derived(&mmd_sub, orig, me, 0, 0);
 470                 totsubvert = mrdm->getNumVerts(mrdm);
 471                 totsubedge = mrdm->getNumEdges(mrdm);
 472                 totsubface = mrdm->getNumFaces(mrdm);
 473                 orig->needsFree = 1;
 474                 orig->release(orig);
 475
 476                 final = multires_subdisp_pre(mrdm, distance, simple);
 477                 mrdm->needsFree = 1;
 478                 mrdm->release(mrdm);
 479         }
 480
 481         for(i = 0; i < me->totface; ++i) {
 482                 const int totdisp = multires_quad_tot[mmd->totlvl - 1];
 483                 float (*disps)[3] = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
 484
 485                 if(mdisps[i].disps)
 486                         MEM_freeN(mdisps[i].disps);
 487
 488                 mdisps[i].disps = disps;
 489                 mdisps[i].totdisp = totdisp;
 490         }
 491
 492
 493         if(final) {
 494                 DerivedMesh *orig;
 495
 496                 orig = CDDM_from_mesh(me, NULL);
 497
 498                 multires_subdisp(orig, me, final, mmd->lvl, mmd->totlvl, totsubvert, totsubedge, totsubface, 0);
 499
 500                 orig->needsFree = 1;
 501                 orig->release(orig);
 502         }
 503
 504         mmd->lvl = mmd->totlvl;
 505 }
 506
 507 typedef struct DisplacerEdges {
 508         /* DerivedMesh index at the start of each edge (using face x/y directions to define the start) */
 509         int base[4];
 510         /* 1 if edge moves in the positive x or y direction, -1 otherwise */
 511         int dir[4];
 512 } DisplacerEdges;
 513
 514 typedef struct DisplacerSpill {
 515         /* Index of face (in base mesh), -1 for none */
 516         int face;
 517
 518         /* Spill flag */
 519         /* 1 = Negative variable axis */
 520         /* 2 = Near fixed axis */
 521         /* 4 = Flip axes */
 522         int f;
 523
 524         /* Neighboring edges */
 525         DisplacerEdges edges;
 526 } DisplacerSpill;
 527
 528 typedef struct MultiresDisplacer {
 529         Mesh *me;
 530         MDisps *grid;
 531         MFace *face;
 532
 533         int dm_first_base_vert_index;
 534
 535         int spacing;
 536         int sidetot, interior_st, disp_st;
 537         int sidendx;
 538         int type;
 539         int invert;
 540         MVert *subco;
 541         int subco_index, face_index;
 542         float weight;
 543
 544         /* Valence for each corner */
 545         int valence[4];
 546
 547         /* Neighboring edges for current face */
 548         DisplacerEdges edges_primary;
 549
 550         /* Neighboring faces */
 551         DisplacerSpill spill_x, spill_y;
 552
 553         int *face_offsets;
 554
 555         int x, y, ax, ay;
 556 } MultiresDisplacer;
 557
 558 static int mface_v(MFace *f, int v)
 559 {
 560         return v == 0 ? f->v1 : v == 1 ? f->v2 : v == 2 ? f->v3 : v == 3 ? f->v4 : -1;
 561 }
 562
 563 /* Get the edges (and their directions) */
 564 static void find_displacer_edges(MultiresDisplacer *d, DerivedMesh *dm, DisplacerEdges *de, MFace *f)
 565 {
 566         ListBase *emap = MultiresDM_get_vert_edge_map(dm);
 567         IndexNode *n;
 568         int i, end = f->v4 ? 4 : 3;
 569         int offset = dm->getNumVerts(dm) - d->me->totvert - d->me->totedge * d->interior_st;
 570
 571         for(i = 0; i < end; ++i) {
 572                 int vcur = mface_v(f, i);
 573                 int vnext = mface_v(f, i == end - 1 ? 0 : i + 1);
 574
 575                 de->dir[i] = 1;
 576
 577                 for(n = emap[vcur].first; n; n = n->next) {
 578                         MEdge *e = &d->me->medge[n->index];
 579
 580                         if(e->v1 == vnext || e->v2 == vnext) {
 581                                 de->base[i] = n->index * d->interior_st;
 582                                 if(((i == 0 || i == 1) && e->v1 == vnext) ||
 583                                    ((i == 2 || i == 3) && e->v2 == vnext)) {
 584                                         de->dir[i] = -1;
 585                                         de->base[i] += d->interior_st - 1;
 586                                 }
 587                                 de->base[i] += offset;
 588                                 break;
 589                         }
 590                 }
 591         }
 592 }
 593
 594 /* Returns in out the corners [0-3] that use v1 and v2 */
 595 void find_face_corners(MFace *f, int v1, int v2, int out[2])
 596 {
 597         int i, end = f->v4 ? 4 : 3;
 598
 599         for(i = 0; i < end; ++i) {
 600                 int corner = mface_v(f, i);
 601                 if(corner == v1)
 602                         out[0] = i;
 603                 if(corner == v2)
 604                         out[1] = i;
 605         }
 606 }
 607
 608 static void multires_displacer_get_spill_faces(MultiresDisplacer *d, DerivedMesh *dm, MFace *mface)
 609 {
 610         ListBase *map = MultiresDM_get_vert_face_map(dm);
 611         IndexNode *n1, *n2;
 612         int v4 = d->face->v4 ? d->face->v4 : d->face->v1;
 613         int crn[2], lv;
 614
 615         memset(&d->spill_x, 0, sizeof(DisplacerSpill));
 616         memset(&d->spill_y, 0, sizeof(DisplacerSpill));
 617         d->spill_x.face = d->spill_y.face = -1;
 618
 619         for(n1 = map[d->face->v3].first; n1; n1 = n1->next) {
 620                 if(n1->index == d->face_index)
 621                         continue;
 622
 623                 for(n2 = map[d->face->v2].first; n2; n2 = n2->next) {
 624                         if(n1->index == n2->index)
 625                                 d->spill_x.face = n1->index;
 626                 }
 627                 for(n2 = map[v4].first; n2; n2 = n2->next) {
 628                         if(n1->index == n2->index)
 629                                 d->spill_y.face = n1->index;
 630                 }
 631         }
 632
 633         if(d->spill_x.face != -1) {
 634                 /* Neighbor of v2/v3 found, find flip and orientation */
 635                 find_face_corners(&mface[d->spill_x.face], d->face->v2, d->face->v3, crn);
 636                 lv = mface[d->spill_x.face].v4 ? 3 : 2;
 637
 638                 if(crn[0] == 0 && crn[1] == lv)
 639                         d->spill_x.f = 0+2+0;
 640                 else if(crn[0] == lv && crn[1] == 0)
 641                         d->spill_x.f = 1+2+0;
 642                 else if(crn[0] == 1 && crn[1] == 0)
 643                         d->spill_x.f = 1+2+4;
 644                 else if(crn[0] == 0 && crn[1] == 1)
 645                         d->spill_x.f = 0+2+4;
 646                 else if(crn[0] == 2 && crn[1] == 1)
 647                         d->spill_x.f = 1+0+0;
 648                 else if(crn[0] == 1 && crn[1] == 2)
 649                         d->spill_x.f = 0+0+0;
 650                 else if(crn[0] == 3 && crn[1] == 2)
 651                         d->spill_x.f = 0+0+4;
 652                 else if(crn[0] == 2 && crn[1] == 3)
 653                         d->spill_x.f = 1+0+4;
 654
 655                 find_displacer_edges(d, dm, &d->spill_x.edges, &mface[d->spill_x.face]);
 656         }
 657
 658         if(d->spill_y.face != -1) {
 659                 /* Neighbor of v3/v4 found, find flip and orientation */
 660                 find_face_corners(&mface[d->spill_y.face], d->face->v3, v4, crn);
 661                 lv = mface[d->spill_y.face].v4 ? 3 : 2;
 662
 663                 if(crn[0] == 1 && crn[1] == 0)
 664                         d->spill_y.f = 1+2+0;
 665                 else if(crn[0] == 0 && crn[1] == 1)
 666                         d->spill_y.f = 0+2+0;
 667                 else if(crn[0] == 2 && crn[1] == 1)
 668                         d->spill_y.f = 1+0+4;
 669                 else if(crn[0] == 1 && crn[1] == 2)
 670                         d->spill_y.f = 0+0+4;
 671                 else if(crn[0] == 3 && crn[1] == 2)
 672                         d->spill_y.f = 0+0+0;
 673                 else if(crn[0] == 2 && crn[1] == 3)
 674                         d->spill_y.f = 1+0+0;
 675                 else if(crn[0] == 0 && crn[1] == lv)
 676                         d->spill_y.f = 0+2+4;
 677                 else if(crn[0] == lv && crn[1] == 0)
 678                         d->spill_y.f = 1+2+4;
 679
 680                 find_displacer_edges(d, dm, &d->spill_y.edges, &mface[d->spill_y.face]);
 681         }
 682 }
 683
 684 static void find_corner_valences(MultiresDisplacer *d, DerivedMesh *dm)
 685 {
 686         int i;
 687
 688         d->valence[3] = -1;
 689
 690         /* Set the vertex valence for the corners */
 691         for(i = 0; i < (d->face->v4 ? 4 : 3); ++i)
 692                 d->valence[i] = BLI_countlist(&MultiresDM_get_vert_edge_map(dm)[mface_v(d->face, i)]);
 693 }
 694
 695 static void multires_displacer_init(MultiresDisplacer *d, DerivedMesh *dm,
 696                              const int face_index, const int invert)
 697 {
 698         Mesh *me = MultiresDM_get_mesh(dm);
 699
 700         d->me = me;
 701         d->face = me->mface + face_index;
 702         d->face_index = face_index;
 703         d->face_offsets = MultiresDM_get_face_offsets(dm);
 704         /* Get the multires grid from customdata */
 705         d->grid = CustomData_get_layer(&me->fdata, CD_MDISPS);
 706         if(d->grid)
 707                 d->grid += face_index;
 708
 709         d->spacing = pow(2, MultiresDM_get_totlvl(dm) - MultiresDM_get_lvl(dm));
 710         d->sidetot = multires_side_tot[MultiresDM_get_lvl(dm) - 1];
 711         d->interior_st = d->sidetot - 2;
 712         d->disp_st = multires_side_tot[MultiresDM_get_totlvl(dm) - 1];
 713         d->invert = invert;
 714
 715         multires_displacer_get_spill_faces(d, dm, me->mface);
 716         find_displacer_edges(d, dm, &d->edges_primary, d->face);
 717         find_corner_valences(d, dm);
 718
 719         d->dm_first_base_vert_index = dm->getNumVerts(dm) - me->totvert;
 720 }
 721
 722 static void multires_displacer_weight(MultiresDisplacer *d, const float w)
 723 {
 724         d->weight = w;
 725 }
 726
 727 static void multires_displacer_anchor(MultiresDisplacer *d, const int type, const int side_index)
 728 {
 729         d->sidendx = side_index;
 730         d->x = d->y = d->sidetot / 2;
 731         d->type = type;
 732
 733         if(type == 2) {
 734                 if(side_index == 0)
 735                         d->y -= 1;
 736                 else if(side_index == 1)
 737                         d->x += 1;
 738                 else if(side_index == 2)
 739                         d->y += 1;
 740                 else if(side_index == 3)
 741                         d->x -= 1;
 742         }
 743         else if(type == 3) {
 744                 if(side_index == 0) {
 745                         d->x -= 1;
 746                         d->y -= 1;
 747                 }
 748                 else if(side_index == 1) {
 749                         d->x += 1;
 750                         d->y -= 1;
 751                 }
 752                 else if(side_index == 2) {
 753                         d->x += 1;
 754                         d->y += 1;
 755                 }
 756                 else if(side_index == 3) {
 757                         d->x -= 1;
 758                         d->y += 1;
 759                 }
 760         }
 761
 762         d->ax = d->x;
 763         d->ay = d->y;
 764 }
 765
 766 static void multires_displacer_anchor_edge(MultiresDisplacer *d, int v1, int v2, int x)
 767 {
 768         d->type = 4;
 769
 770         if(v1 == d->face->v1) {
 771                 d->x = 0;
 772                 d->y = 0;
 773                 if(v2 == d->face->v2)
 774                         d->x += x;
 775                 else if(v2 == d->face->v3) {
 776                         if(x < d->sidetot / 2)
 777                                 d->y = x;
 778                         else {
 779                                 d->x = x;
 780                                 d->y = d->sidetot - 1;
 781                         }
 782                 }
 783                 else
 784                         d->y += x;
 785         }
 786         else if(v1 == d->face->v2) {
 787                 d->x = d->sidetot - 1;
 788                 d->y = 0;
 789                 if(v2 == d->face->v1)
 790                         d->x -= x;
 791                 else
 792                         d->y += x;
 793         }
 794         else if(v1 == d->face->v3) {
 795                 d->x = d->sidetot - 1;
 796                 d->y = d->sidetot - 1;
 797                 if(v2 == d->face->v2)
 798                         d->y -= x;
 799                 else if(v2 == d->face->v1) {
 800                         if(x < d->sidetot / 2)
 801                                 d->x -= x;
 802                         else {
 803                                 d->x = 0;
 804                                 d->y -= x;
 805                         }
 806                 }
 807                 else
 808                         d->x -= x;
 809         }
 810         else if(v1 == d->face->v4) {
 811                 d->x = 0;
 812                 d->y = d->sidetot - 1;
 813                 if(v2 == d->face->v3)
 814                         d->x += x;
 815                 else
 816                         d->y -= x;
 817         }
 818 }
 819
 820 static void multires_displacer_anchor_vert(MultiresDisplacer *d, const int v)
 821 {
 822         const int e = d->sidetot - 1;
 823
 824         d->type = 5;
 825
 826         d->x = d->y = 0;
 827         if(v == d->face->v2)
 828                 d->x = e;
 829         else if(v == d->face->v3)
 830                 d->x = d->y = e;
 831         else if(v == d->face->v4)
 832                 d->y = e;
 833 }
 834
 835 static void multires_displacer_jump(MultiresDisplacer *d)
 836 {
 837         if(d->sidendx == 0) {
 838                 d->x -= 1;
 839                 d->y = d->ay;
 840         }
 841         else if(d->sidendx == 1) {
 842                 d->x = d->ax;
 843                 d->y -= 1;
 844         }
 845         else if(d->sidendx == 2) {
 846                 d->x += 1;
 847                 d->y = d->ay;
 848         }
 849         else if(d->sidendx == 3) {
 850                 d->x = d->ax;
 851                 d->y += 1;
 852         }
 853 }
 854
 855 /* Treating v1 as (0,0) and v3 as (st-1,st-1),
 856    returns the index of the vertex at (x,y).
 857    If x or y is >= st, wraps over to the adjacent face,
 858    or if there is no adjacent face, returns -2. */
 859 static int multires_index_at_loc(int face_index, int x, int y, MultiresDisplacer *d, DisplacerEdges *de)
 860 {
 861         int coord_edge = d->sidetot - 1; /* Max value of x/y at edge of grid */
 862         int mid = d->sidetot / 2;
 863         int lim = mid - 1;
 864         int qtot = lim * lim;
 865         int base = d->face_offsets[face_index];
 866
 867         /* Edge spillover */
 868         if(x == d->sidetot || y == d->sidetot) {
 869                 int flags, v_axis, f_axis, lx, ly;
 870
 871                 if(x == d->sidetot && d->spill_x.face != -1) {
 872                         flags = d->spill_x.f;
 873
 874                         /* Handle triangle seam between v1 and v3 */
 875                         if(!d->me->mface[d->spill_x.face].v4 &&
 876                            ((flags == 2 && y >= mid) || (flags == 3 && y < mid)))
 877                                 flags += 2;
 878
 879                         v_axis = (flags & 1) ? d->sidetot - 1 - y : y;
 880                         f_axis = (flags & 2) ? 1 : d->sidetot - 2;
 881                         lx = f_axis, ly = v_axis;
 882
 883                         if(flags & 4) {
 884                                 lx = v_axis;
 885                                 ly = f_axis;
 886                         }
 887
 888                         return multires_index_at_loc(d->spill_x.face, lx, ly, d, &d->spill_x.edges);
 889                 }
 890                 else if(y == d->sidetot && d->spill_y.face != -1) {
 891                         flags = d->spill_y.f;
 892
 893                         /* Handle triangle seam between v1 and v3 */
 894                         if(!d->me->mface[d->spill_y.face].v4 &&
 895                            ((flags == 6 && x >= mid) || (flags == 7 && x < mid)))
 896                                 flags = ~flags;
 897
 898                         v_axis = (flags & 1) ? x : d->sidetot - 1 - x;
 899                         f_axis = (flags & 2) ? 1 : d->sidetot - 2;
 900                         lx = v_axis, ly = f_axis;
 901
 902                         if(flags & 4) {
 903                                 lx = f_axis;
 904                                 ly = v_axis;
 905                         }
 906
 907                         return multires_index_at_loc(d->spill_y.face, lx, ly, d, &d->spill_y.edges);
 908                 }
 909                 else
 910                         return -2;
 911         }
 912         /* Corners */
 913         else if(x == 0 && y == 0)
 914                 return d->dm_first_base_vert_index + d->face->v1;
 915         else if(x == coord_edge && y == 0)
 916                 return d->dm_first_base_vert_index + d->face->v2;
 917         else if(x == coord_edge && y == coord_edge)
 918                 return d->dm_first_base_vert_index + d->face->v3;
 919         else if(x == 0 && y == coord_edge)
 920                 return d->dm_first_base_vert_index + d->face->v4;
 921         /* Edges */
 922         else if(x == 0) {
 923                 if(d->face->v4)
 924                         return de->base[3] + de->dir[3] * (y - 1);
 925                 else
 926                         return de->base[2] + de->dir[2] * (y - 1);
 927         }
 928         else if(y == 0)
 929                 return de->base[0] + de->dir[0] * (x - 1);
 930         else if(x == d->sidetot - 1)
 931                 return de->base[1] + de->dir[1] * (y - 1);
 932         else if(y == d->sidetot - 1)
 933                 return de->base[2] + de->dir[2] * (x - 1);
 934         /* Face center */
 935         else if(x == mid && y == mid)
 936                 return base;
 937         /* Cross */
 938         else if(x == mid && y < mid)
 939                 return base + (mid - y);
 940         else if(y == mid && x > mid)
 941                 return base + lim + (x - mid);
 942         else if(x == mid && y > mid)
 943                 return base + lim*2 + (y - mid);
 944         else if(y == mid && x < mid) {
 945                 if(d->face->v4)
 946                         return base + lim*3 + (mid - x);
 947                 else
 948                         return base + lim*2 + (mid - x);
 949         }
 950         /* Quarters */
 951         else {
 952                 int offset = base + lim * (d->face->v4 ? 4 : 3);
 953                 if(x < mid && y < mid)
 954                         return offset + ((mid - x - 1)*lim + (mid - y));
 955                 else if(x > mid && y < mid)
 956                         return offset + qtot + ((mid - y - 1)*lim + (x - mid));
 957                 else if(x > mid && y > mid)
 958                         return offset + qtot*2 + ((x - mid - 1)*lim + (y - mid));
 959                 else if(x < mid && y > mid)
 960                         return offset + qtot*3 + ((y - mid - 1)*lim + (mid - x));
 961         }
 962
 963         return -1;
 964 }
 965
 966 /* Calculate the TS matrix used for applying displacements.
 967    Uses the undisplaced subdivided mesh's curvature to find a
 968    smoothly normal and tangents. */
 969 static void calc_disp_mat(MultiresDisplacer *d, float mat[3][3])
 970 {
 971         int u = multires_index_at_loc(d->face_index, d->x + 1, d->y, d, &d->edges_primary);
 972         int v = multires_index_at_loc(d->face_index, d->x, d->y + 1, d, &d->edges_primary);
 973         float norm[3], t1[3], t2[3], inv[3][3];
 974         MVert *base = d->subco + d->subco_index;
 975
 976         //printf("f=%d, x=%d, y=%d, i=%d, u=%d, v=%d ", d->face_index, d->x, d->y, d->subco_index, u, v);
 977
 978         norm[0] = base->no[0] / 32767.0f;
 979         norm[1] = base->no[1] / 32767.0f;
 980         norm[2] = base->no[2] / 32767.0f;
 981
 982         /* Special handling for vertices of valence 3 */
 983         if(d->valence[1] == 3 && d->x == d->sidetot - 1 && d->y == 0)
 984                 u = -1;
 985         else if(d->valence[2] == 3 && d->x == d->sidetot - 1 && d->y == d->sidetot - 1)
 986                 u = v = -1;
 987         else if(d->valence[3] == 3 && d->x == 0 && d->y == d->sidetot - 1)
 988                 v = -1;
 989
 990         /* If either u or v is -2, it's on a boundary. In this
 991            case, back up by one row/column and use the same
 992            vector as the preceeding sub-edge. */
 993
 994         if(u < 0) {
 995                 u = multires_index_at_loc(d->face_index, d->x - 1, d->y, d, &d->edges_primary);
 996                 VecSubf(t1, base->co, d->subco[u].co);
 997         }
 998         else
 999                 VecSubf(t1, d->subco[u].co, base->co);
1000
1001         if(v < 0) {
1002                 v = multires_index_at_loc(d->face_index, d->x, d->y - 1, d, &d->edges_primary);
1003                 VecSubf(t2, base->co, d->subco[v].co);
1004         }
1005         else
1006                 VecSubf(t2, d->subco[v].co, base->co);
1007
1008         //printf("uu=%d, vv=%d\n", u, v);
1009
1010         Normalize(t1);
1011         Normalize(t2);
1012         Mat3FromColVecs(mat, t1, t2, norm);
1013
1014         if(d->invert) {
1015                 Mat3Inv(inv, mat);
1016                 Mat3CpyMat3(mat, inv);
1017         }
1018 }
1019
1020 static void multires_displace(MultiresDisplacer *d, float co[3])
1021 {
1022         float disp[3], mat[3][3];
1023         float *data;
1024         MVert *subco = &d->subco[d->subco_index];
1025
1026         if(!d->grid || !d->grid->disps) return;
1027
1028         data = d->grid->disps[(d->y * d->spacing) * d->disp_st + (d->x * d->spacing)];
1029
1030         if(d->invert)
1031                 VecSubf(disp, co, subco->co);
1032         else
1033                 VecCopyf(disp, data);
1034
1035
1036         /* Apply ts matrix to displacement */
1037         calc_disp_mat(d, mat);
1038         Mat3MulVecfl(mat, disp);
1039
1040         if(d->invert) {
1041                 VecCopyf(data, disp);
1042
1043         }
1044         else {
1045                 if(d->type == 4 || d->type == 5)
1046                         VecMulf(disp, d->weight);
1047                 VecAddf(co, co, disp);
1048         }
1049
1050         if(d->type == 2) {
1051                 if(d->sidendx == 0)
1052                         d->y -= 1;
1053                 else if(d->sidendx == 1)
1054                         d->x += 1;
1055                 else if(d->sidendx == 2)
1056                         d->y += 1;
1057                 else if(d->sidendx == 3)
1058                         d->x -= 1;
1059         }
1060         else if(d->type == 3) {
1061                 if(d->sidendx == 0)
1062                         d->y -= 1;
1063                 else if(d->sidendx == 1)
1064                         d->x += 1;
1065                 else if(d->sidendx == 2)
1066                         d->y += 1;
1067                 else if(d->sidendx == 3)
1068                         d->x -= 1;
1069         }
1070 }
1071
1072 static void multiresModifier_disp_run(DerivedMesh *dm, MVert *subco, int invert)
1073 {
1074         const int lvl = MultiresDM_get_lvl(dm);
1075         const int gridFaces = multires_side_tot[lvl - 2] - 1;
1076         const int edgeSize = multires_side_tot[lvl - 1] - 1;
1077         MVert *mvert = CDDM_get_verts(dm);
1078         MEdge *medge = MultiresDM_get_mesh(dm)->medge;
1079         MFace *mface = MultiresDM_get_mesh(dm)->mface;
1080         ListBase *map = MultiresDM_get_vert_face_map(dm);
1081         Mesh *me = MultiresDM_get_mesh(dm);
1082         MultiresDisplacer d;
1083         int i, S, x, y;
1084
1085         d.subco = subco;
1086         d.subco_index = 0;
1087
1088         for(i = 0; i < me->totface; ++i) {
1089                 const int numVerts = mface[i].v4 ? 4 : 3;
1090
1091                 /* Center */
1092                 multires_displacer_init(&d, dm, i, invert);
1093                 multires_displacer_anchor(&d, 1, 0);
1094                 multires_displace(&d, mvert->co);
1095                 ++mvert;
1096                 ++d.subco_index;
1097
1098                 /* Cross */
1099                 for(S = 0; S < numVerts; ++S) {
1100                         multires_displacer_anchor(&d, 2, S);
1101                         for(x = 1; x < gridFaces; ++x) {
1102                                 multires_displace(&d, mvert->co);
1103                                 ++mvert;
1104                                 ++d.subco_index;
1105                         }
1106                 }
1107
1108                 /* Quarters */
1109                 for(S = 0; S < numVerts; S++) {
1110                         multires_displacer_anchor(&d, 3, S);
1111                         for(y = 1; y < gridFaces; y++) {
1112                                 for(x = 1; x < gridFaces; x++) {
1113                                         multires_displace(&d, mvert->co);
1114                                         ++mvert;
1115                                         ++d.subco_index;
1116                                 }
1117                                 multires_displacer_jump(&d);
1118                         }
1119                 }
1120         }
1121
1122         for(i = 0; i < me->totedge; ++i) {
1123                 const MEdge *e = &medge[i];
1124                 for(x = 1; x < edgeSize; ++x) {
1125                         IndexNode *n1, *n2;
1126                         int numFaces = 0;
1127                         for(n1 = map[e->v1].first; n1; n1 = n1->next) {
1128                                 for(n2 = map[e->v2].first; n2; n2 = n2->next) {
1129                                         if(n1->index == n2->index)
1130                                                 ++numFaces;
1131                                 }
1132                         }
1133                         multires_displacer_weight(&d, 1.0f / numFaces);
1134                         /* TODO: Better to have these loops outside the x loop */
1135                         for(n1 = map[e->v1].first; n1; n1 = n1->next) {
1136                                 for(n2 = map[e->v2].first; n2; n2 = n2->next) {
1137                                         if(n1->index == n2->index) {
1138                                                 multires_displacer_init(&d, dm, n1->index, invert);
1139                                                 multires_displacer_anchor_edge(&d, e->v1, e->v2, x);
1140                                                 multires_displace(&d, mvert->co);
1141                                         }
1142                                 }
1143                         }
1144                         ++mvert;
1145                         ++d.subco_index;
1146                 }
1147         }
1148
1149         for(i = 0; i < me->totvert; ++i) {
1150                 IndexNode *n;
1151                 multires_displacer_weight(&d, 1.0f / BLI_countlist(&map[i]));
1152                 for(n = map[i].first; n; n = n->next) {
1153                         multires_displacer_init(&d, dm, n->index, invert);
1154                         multires_displacer_anchor_vert(&d, i);
1155                         multires_displace(&d, mvert->co);
1156                 }
1157                 ++mvert;
1158                 ++d.subco_index;
1159         }
1160
1161         if(!invert)
1162                 CDDM_calc_normals(dm);
1163 }
1164
1165 static void multiresModifier_update(DerivedMesh *dm)
1166 {
1167         Mesh *me;
1168         MDisps *mdisps;
1169
1170         me = MultiresDM_get_mesh(dm);
1171         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
1172
1173         if(mdisps) {
1174                 const int lvl = MultiresDM_get_lvl(dm);
1175                 const int totlvl = MultiresDM_get_totlvl(dm);
1176
1177                 if(lvl < totlvl) {
1178                         /* Propagate disps upwards */
1179                         DerivedMesh *final, *subco_dm, *orig;
1180                         MVert *verts_new = NULL, *cur_lvl_orig_verts = NULL;
1181                         MultiresModifierData mmd;
1182                         int i;
1183
1184                         orig = CDDM_from_mesh(me, NULL);
1185
1186                         /* Regenerate the current level's vertex coordinates
1187                            (includes older displacements but not new sculpts) */
1188                         mmd.totlvl = totlvl;
1189                         mmd.lvl = lvl;
1190                         subco_dm = multires_dm_create_from_derived(&mmd, orig, me, 0, 0);
1191                         cur_lvl_orig_verts = CDDM_get_verts(subco_dm);
1192
1193                         /* Subtract the original vertex cos from the new vertex cos */
1194                         verts_new = CDDM_get_verts(dm);
1195                         for(i = 0; i < dm->getNumVerts(dm); ++i)
1196                                 VecSubf(verts_new[i].co, verts_new[i].co, cur_lvl_orig_verts[i].co);
1197
1198                         final = multires_subdisp_pre(dm, totlvl - lvl, 0);
1199
1200                         multires_subdisp(orig, me, final, lvl, totlvl, dm->getNumVerts(dm), dm->getNumEdges(dm),
1201                                          dm->getNumFaces(dm), 1);
1202
1203                         subco_dm->release(subco_dm);
1204                         orig->release(orig);
1205                 }
1206                 else
1207                         multiresModifier_disp_run(dm, MultiresDM_get_subco(dm), 1);
1208         }
1209 }
1210
1211 void multires_mark_as_modified(struct Object *ob)
1212 {
1213         if(ob && ob->derivedFinal) {
1214                 MultiresDM_mark_as_modified(ob->derivedFinal);
1215         }
1216 }
1217
1218 void multires_force_update(Object *ob)
1219 {
1220         if(ob && ob->derivedFinal) {
1221                 ob->derivedFinal->needsFree =1;
1222                 ob->derivedFinal->release(ob->derivedFinal);
1223                 ob->derivedFinal = NULL;
1224         }
1225 }
1226
1227 struct DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, DerivedMesh *dm, Mesh *me,
1228                                                     int useRenderParams, int isFinalCalc)
1229 {
1230         SubsurfModifierData smd;
1231         MultiresSubsurf ms;
1232         DerivedMesh *result;
1233         int i;
1234
1235         ms.mmd = mmd;
1236         ms.me = me;
1237
1238         memset(&smd, 0, sizeof(SubsurfModifierData));
1239         smd.levels = smd.renderLevels = mmd->lvl - 1;
1240         smd.flags |= eSubsurfModifierFlag_SubsurfUv;
1241
1242         result = subsurf_make_derived_from_derived_with_multires(dm, &smd, &ms, useRenderParams, NULL, isFinalCalc, 0);
1243         for(i = 0; i < result->getNumVerts(result); ++i)
1244                 MultiresDM_get_subco(result)[i] = CDDM_get_verts(result)[i];
1245         multiresModifier_disp_run(result, MultiresDM_get_subco(result), 0);
1246         MultiresDM_set_update(result, multiresModifier_update);
1247
1248         return result;
1249 }
1250
1251 /**** Old Multires code ****
1252 ***************************/
1253
1254 /* Does not actually free lvl itself */
1255 void multires_free_level(MultiresLevel *lvl)
1256 {
1257         if(lvl) {
1258                 if(lvl->faces) MEM_freeN(lvl->faces);
1259                 if(lvl->edges) MEM_freeN(lvl->edges);
1260                 if(lvl->colfaces) MEM_freeN(lvl->colfaces);
1261         }
1262 }
1263
1264 void multires_free(Multires *mr)
1265 {
1266         if(mr) {
1267                 MultiresLevel* lvl= mr->levels.first;
1268
1269                 /* Free the first-level data */
1270                 if(lvl) {
1271                         CustomData_free(&mr->vdata, lvl->totvert);
1272                         CustomData_free(&mr->fdata, lvl->totface);
1273                         if(mr->edge_flags)
1274                                 MEM_freeN(mr->edge_flags);
1275                         if(mr->edge_creases)
1276                                 MEM_freeN(mr->edge_creases);
1277                 }
1278
1279                 while(lvl) {
1280                         multires_free_level(lvl);
1281                         lvl= lvl->next;
1282                 }
1283
1284                 MEM_freeN(mr->verts);
1285
1286                 BLI_freelistN(&mr->levels);
1287
1288                 MEM_freeN(mr);
1289         }
1290 }
1291
1292 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
1293                                      const int totvert, const int totface)
1294 {
1295         int i,j;
1296         IndexNode *node = NULL;
1297
1298         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
1299         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
1300         node = *mem;
1301
1302         /* Find the users */
1303         for(i = 0; i < totface; ++i){
1304                 for(j = 0; j < (mface[i].v[3]?4:3); ++j, ++node) {
1305                         node->index = i;
1306                         BLI_addtail(&(*map)[mface[i].v[j]], node);
1307                 }
1308         }
1309 }
1310
1311 static void create_old_vert_edge_map(ListBase **map, IndexNode **mem, const MultiresEdge *medge,
1312                                      const int totvert, const int totedge)
1313 {
1314         int i,j;
1315         IndexNode *node = NULL;
1316
1317         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
1318         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge*2, "vert edge map mem");
1319         node = *mem;
1320
1321         /* Find the users */
1322         for(i = 0; i < totedge; ++i){
1323                 for(j = 0; j < 2; ++j, ++node) {
1324                         node->index = i;
1325                         BLI_addtail(&(*map)[medge[i].v[j]], node);
1326                 }
1327         }
1328 }
1329
1330 static MultiresFace *find_old_face(ListBase *map, MultiresFace *faces, int v1, int v2, int v3, int v4)
1331 {
1332         IndexNode *n1;
1333         int v[4] = {v1, v2, v3, v4}, i, j;
1334
1335         for(n1 = map[v1].first; n1; n1 = n1->next) {
1336                 int fnd[4] = {0, 0, 0, 0};
1337
1338                 for(i = 0; i < 4; ++i) {
1339                         for(j = 0; j < 4; ++j) {
1340                                 if(v[i] == faces[n1->index].v[j])
1341                                         fnd[i] = 1;
1342                         }
1343                 }
1344
1345                 if(fnd[0] && fnd[1] && fnd[2] && fnd[3])
1346                         return &faces[n1->index];
1347         }
1348
1349         return NULL;
1350 }
1351
1352 static MultiresEdge *find_old_edge(ListBase *map, MultiresEdge *edges, int v1, int v2)
1353 {
1354         IndexNode *n1, *n2;
1355
1356         for(n1 = map[v1].first; n1; n1 = n1->next) {
1357                 for(n2 = map[v2].first; n2; n2 = n2->next) {
1358                         if(n1->index == n2->index)
1359                                 return &edges[n1->index];
1360                 }
1361         }
1362
1363         return NULL;
1364 }
1365
1366 static void multires_load_old_edges(ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst, int v1, int v2, int mov)
1367 {
1368         int emid = find_old_edge(emap[2], lvl->edges, v1, v2)->mid;
1369         vvmap[dst + mov] = emid;
1370
1371         if(lvl->next->next) {
1372                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v1, emid, mov / 2);
1373                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v2, emid, -mov / 2);
1374         }
1375 }
1376
1377 static void multires_load_old_faces(ListBase **fmap, ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst,
1378                                     int v1, int v2, int v3, int v4, int st2, int st3)
1379 {
1380         int fmid;
1381         int emid13, emid14, emid23, emid24;
1382
1383         if(lvl && lvl->next) {
1384                 fmid = find_old_face(fmap[1], lvl->faces, v1, v2, v3, v4)->mid;
1385                 vvmap[dst] = fmid;
1386
1387                 emid13 = find_old_edge(emap[1], lvl->edges, v1, v3)->mid;
1388                 emid14 = find_old_edge(emap[1], lvl->edges, v1, v4)->mid;
1389                 emid23 = find_old_edge(emap[1], lvl->edges, v2, v3)->mid;
1390                 emid24 = find_old_edge(emap[1], lvl->edges, v2, v4)->mid;
1391
1392
1393                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 + st3,
1394                                         fmid, v2, emid23, emid24, st2, st3 / 2);
1395
1396                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 + st3,
1397                                         emid14, emid24, fmid, v4, st2, st3 / 2);
1398
1399                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 - st3,
1400                                         emid13, emid23, v3, fmid, st2, st3 / 2);
1401
1402                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 - st3,
1403                                         v1, fmid, emid13, emid14, st2, st3 / 2);
1404
1405                 if(lvl->next->next) {
1406                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid24, fmid, st3);
1407                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid13, fmid, -st3);
1408                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid14, fmid, -st2 * st3);
1409                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid23, fmid, st2 * st3);
1410                 }
1411         }
1412 }
1413
1414 /* Loads a multires object stored in the old Multires struct into the new format */
1415 void multires_load_old(DerivedMesh *dm, Multires *mr)
1416 {
1417         MultiresLevel *lvl, *lvl1;
1418         MVert *vsrc, *vdst;
1419         int src, dst;
1420         int totlvl = MultiresDM_get_totlvl(dm);
1421         int st = multires_side_tot[totlvl - 2] - 1;
1422         int extedgelen = multires_side_tot[totlvl - 1] - 2;
1423         int *vvmap; // inorder for dst, map to src
1424         int crossedgelen;
1425         int i, j, s, x, totvert, tottri, totquad;
1426
1427         src = 0;
1428         dst = 0;
1429         vsrc = mr->verts;
1430         vdst = CDDM_get_verts(dm);
1431         totvert = dm->getNumVerts(dm);
1432         vvmap = MEM_callocN(sizeof(int) * totvert, "multires vvmap");
1433
1434         lvl1 = mr->levels.first;
1435         /* Load base verts */
1436         for(i = 0; i < lvl1->totvert; ++i) {
1437                 vvmap[totvert - lvl1->totvert + i] = src;
1438                 ++src;
1439         }
1440
1441         /* Original edges */
1442         dst = totvert - lvl1->totvert - extedgelen * lvl1->totedge;
1443         for(i = 0; i < lvl1->totedge; ++i) {
1444                 int ldst = dst + extedgelen * i;
1445                 int lsrc = src;
1446                 lvl = lvl1->next;
1447
1448                 for(j = 2; j <= mr->level_count; ++j) {
1449                         int base = multires_side_tot[totlvl - j] - 2;
1450                         int skip = multires_side_tot[totlvl - j + 1] - 1;
1451                         int st = multires_side_tot[j - 2] - 1;
1452
1453                         for(x = 0; x < st; ++x)
1454                                 vvmap[ldst + base + x * skip] = lsrc + st * i + x;
1455
1456                         lsrc += lvl->totvert - lvl->prev->totvert;
1457                         lvl = lvl->next;
1458                 }
1459         }
1460
1461         /* Center points */
1462         dst = 0;
1463         for(i = 0; i < lvl1->totface; ++i) {
1464                 int sides = lvl1->faces[i].v[3] ? 4 : 3;
1465
1466                 vvmap[dst] = src + lvl1->totedge + i;
1467                 dst += 1 + sides * (st - 1) * st;
1468         }
1469
1470
1471         /* The rest is only for level 3 and up */
1472         if(lvl1->next && lvl1->next->next) {
1473                 ListBase **fmap, **emap;
1474                 IndexNode **fmem, **emem;
1475
1476                 /* Face edge cross */
1477                 tottri = totquad = 0;
1478                 crossedgelen = multires_side_tot[totlvl - 2] - 2;
1479                 dst = 0;
1480                 for(i = 0; i < lvl1->totface; ++i) {
1481                         int sides = lvl1->faces[i].v[3] ? 4 : 3;
1482
1483                         lvl = lvl1->next->next;
1484                         ++dst;
1485
1486                         for(j = 3; j <= mr->level_count; ++j) {
1487                                 int base = multires_side_tot[totlvl - j] - 2;
1488                                 int skip = multires_side_tot[totlvl - j + 1] - 1;
1489                                 int st = pow(2, j - 2);
1490                                 int st2 = pow(2, j - 3);
1491                                 int lsrc = lvl->prev->totvert;
1492
1493                                 /* Skip exterior edge verts */
1494                                 lsrc += lvl1->totedge * st;
1495
1496                                 /* Skip earlier face edge crosses */
1497                                 lsrc += st2 * (tottri * 3 + totquad * 4);
1498
1499                                 for(s = 0; s < sides; ++s) {
1500                                         for(x = 0; x < st2; ++x) {
1501                                                 vvmap[dst + crossedgelen * (s + 1) - base - x * skip - 1] = lsrc;
1502                                                 ++lsrc;
1503                                         }
1504                                 }
1505
1506                                 lvl = lvl->next;
1507                         }
1508
1509                         dst += sides * (st - 1) * st;
1510
1511                         if(sides == 4) ++totquad;
1512                         else ++tottri;
1513
1514                 }
1515
1516                 /* calculate vert to edge/face maps for each level (except the last) */
1517                 fmap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires fmap");
1518                 emap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires emap");
1519                 fmem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires fmem");
1520                 emem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires emem");
1521                 lvl = lvl1;
1522                 for(i = 0; i < mr->level_count - 1; ++i) {
1523                         create_old_vert_face_map(fmap + i, fmem + i, lvl->faces, lvl->totvert, lvl->totface);
1524                         create_old_vert_edge_map(emap + i, emem + i, lvl->edges, lvl->totvert, lvl->totedge);
1525                         lvl = lvl->next;
1526                 }
1527
1528                 /* Interior face verts */
1529                 lvl = lvl1->next->next;
1530                 dst = 0;
1531                 for(j = 0; j < lvl1->totface; ++j) {
1532                         int sides = lvl1->faces[j].v[3] ? 4 : 3;
1533                         int ldst = dst + 1 + sides * (st - 1);
1534
1535                         for(s = 0; s < sides; ++s) {
1536                                 int st2 = multires_side_tot[totlvl - 2] - 2;
1537                                 int st3 = multires_side_tot[totlvl - 3] - 2;
1538                                 int st4 = st3 == 0 ? 1 : (st3 + 1) / 2;
1539                                 int mid = ldst + st2 * st3 + st3;
1540                                 int cv = lvl1->faces[j].v[s];
1541                                 int nv = lvl1->faces[j].v[s == sides - 1 ? 0 : s + 1];
1542                                 int pv = lvl1->faces[j].v[s == 0 ? sides - 1 : s - 1];
1543
1544                                 multires_load_old_faces(fmap, emap, lvl1->next, vvmap, mid,
1545                                                         vvmap[dst], cv,
1546                                                         find_old_edge(emap[0], lvl1->edges, pv, cv)->mid,
1547                                                         find_old_edge(emap[0], lvl1->edges, cv, nv)->mid,
1548                                                         st2, st4);
1549
1550                                 ldst += (st - 1) * (st - 1);
1551                         }
1552
1553
1554                         dst = ldst;
1555                 }
1556
1557                 lvl = lvl->next;
1558
1559                 for(i = 0; i < mr->level_count - 1; ++i) {
1560                         MEM_freeN(fmap[i]);
1561                         MEM_freeN(fmem[i]);
1562                         MEM_freeN(emap[i]);
1563                         MEM_freeN(emem[i]);
1564                 }
1565
1566                 MEM_freeN(fmap);
1567                 MEM_freeN(emap);
1568                 MEM_freeN(fmem);
1569                 MEM_freeN(emem);
1570         }
1571
1572         /* Transfer verts */
1573         for(i = 0; i < totvert; ++i)
1574                 VecCopyf(vdst[i].co, vsrc[vvmap[i]].co);
1575
1576         MEM_freeN(vvmap);
1577 }