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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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_mesh_types.h"
  33 #include "DNA_meshdata_types.h"
  34 #include "DNA_object_types.h"
  35 #include "DNA_scene_types.h"
  36
  37 #include "BLI_blenlib.h"
  38 #include "BLI_math.h"
  39 #include "BLI_pbvh.h"
  40
  41 #include "BKE_cdderivedmesh.h"
  42 #include "BKE_mesh.h"
  43 #include "BKE_modifier.h"
  44 #include "BKE_multires.h"
  45 #include "BKE_paint.h"
  46 #include "BKE_scene.h"
  47 #include "BKE_subsurf.h"
  48 #include "BKE_utildefines.h"
  49
  50 #include "CCGSubSurf.h"
  51
  52 #include <math.h>
  53 #include <string.h>
  54
  55 /* MULTIRES MODIFIER */
  56 static const int multires_max_levels = 13;
  57 static const int multires_grid_tot[] = {0, 4, 9, 25, 81, 289, 1089, 4225, 16641, 66049, 263169, 1050625, 4198401, 16785409};
  58 static const int multires_side_tot[] = {0, 2, 3, 5,  9,  17,  33,   65,   129,   257,   513,    1025,    2049,    4097};
  59
  60 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert);
  61 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, int invert, int add, DMGridData **oldGridData, int totlvl);
  62
  63 DerivedMesh *get_multires_dm(Scene *scene, MultiresModifierData *mmd, Object *ob)
  64 {
  65         ModifierData *md= (ModifierData *)mmd;
  66         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
  67         DerivedMesh *tdm = mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
  68         DerivedMesh *dm;
  69
  70         dm = mti->applyModifier(md, ob, tdm, 0, 1);
  71         if (dm == tdm) {
  72                 dm = CDDM_copy(tdm);
  73         }
  74
  75         return dm;
  76 }
  77
  78 MultiresModifierData *find_multires_modifier_before(Scene *scene, ModifierData *lastmd)
  79 {
  80         ModifierData *md;
  81
  82         for(md = lastmd; md; md = md->prev) {
  83                 if(md->type == eModifierType_Multires) {
  84                         if (modifier_isEnabled(scene, md, eModifierMode_Realtime))
  85                                 return (MultiresModifierData*)md;
  86                 }
  87         }
  88
  89         return NULL;
  90 }
  91
  92 static int multires_get_level(Object *ob, MultiresModifierData *mmd, int render)
  93 {
  94         if(render)
  95                 return (mmd->modifier.scene)? get_render_subsurf_level(&mmd->modifier.scene->r, mmd->renderlvl): mmd->renderlvl;
  96         else if(ob->mode == OB_MODE_SCULPT)
  97                 return mmd->sculptlvl;
  98         else
  99                 return (mmd->modifier.scene)? get_render_subsurf_level(&mmd->modifier.scene->r, mmd->lvl): mmd->lvl;
 100 }
 101
 102 static void multires_set_tot_level(Object *ob, MultiresModifierData *mmd, int lvl)
 103 {
 104         mmd->totlvl = lvl;
 105
 106         if(ob->mode != OB_MODE_SCULPT)
 107                 mmd->lvl = CLAMPIS(MAX2(mmd->lvl, lvl), 0, mmd->totlvl);
 108
 109         mmd->sculptlvl = CLAMPIS(MAX2(mmd->sculptlvl, lvl), 0, mmd->totlvl);
 110         mmd->renderlvl = CLAMPIS(MAX2(mmd->renderlvl, lvl), 0, mmd->totlvl);
 111 }
 112
 113 static void multires_dm_mark_as_modified(DerivedMesh *dm)
 114 {
 115         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)dm;
 116         ccgdm->multires.modified = 1;
 117 }
 118
 119 void multires_mark_as_modified(Object *ob)
 120 {
 121         if(ob && ob->derivedFinal)
 122                 multires_dm_mark_as_modified(ob->derivedFinal);
 123 }
 124
 125 void multires_force_update(Object *ob)
 126 {
 127         if(ob) {
 128                 if(ob->derivedFinal) {
 129                         ob->derivedFinal->needsFree =1;
 130                         ob->derivedFinal->release(ob->derivedFinal);
 131                         ob->derivedFinal = NULL;
 132                 }
 133                 if(ob->sculpt && ob->sculpt->pbvh) {
 134                         BLI_pbvh_free(ob->sculpt->pbvh);
 135                         ob->sculpt->pbvh= NULL;
 136                 }
 137         }
 138 }
 139
 140 void multires_force_external_reload(Object *ob)
 141 {
 142         Mesh *me = get_mesh(ob);
 143
 144         CustomData_external_reload(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
 145         multires_force_update(ob);
 146 }
 147
 148 void multires_force_render_update(Object *ob)
 149 {
 150         if(ob && (ob->mode & OB_MODE_SCULPT) && modifiers_findByType(ob, eModifierType_Multires))
 151                 multires_force_update(ob);
 152 }
 153
 154 /* XXX */
 155 #if 0
 156 void multiresModifier_join(Object *ob)
 157 {
 158         Base *base = NULL;
 159         int highest_lvl = 0;
 160
 161         /* First find the highest level of subdivision */
 162         base = FIRSTBASE;
 163         while(base) {
 164                 if(TESTBASELIB_BGMODE(v3d, scene, base) && base->object->type==OB_MESH) {
 165                         ModifierData *md;
 166                         for(md = base->object->modifiers.first; md; md = md->next) {
 167                                 if(md->type == eModifierType_Multires) {
 168                                         int totlvl = ((MultiresModifierData*)md)->totlvl;
 169                                         if(totlvl > highest_lvl)
 170                                                 highest_lvl = totlvl;
 171
 172                                         /* Ensure that all updates are processed */
 173                                         multires_force_update(base->object);
 174                                 }
 175                         }
 176                 }
 177                 base = base->next;
 178         }
 179
 180         /* No multires meshes selected */
 181         if(highest_lvl == 0)
 182                 return;
 183
 184         /* Subdivide all the displacements to the highest level */
 185         base = FIRSTBASE;
 186         while(base) {
 187                 if(TESTBASELIB_BGMODE(v3d, scene, base) && base->object->type==OB_MESH) {
 188                         ModifierData *md = NULL;
 189                         MultiresModifierData *mmd = NULL;
 190
 191                         for(md = base->object->modifiers.first; md; md = md->next) {
 192                                 if(md->type == eModifierType_Multires)
 193                                         mmd = (MultiresModifierData*)md;
 194                         }
 195
 196                         /* If the object didn't have multires enabled, give it a new modifier */
 197                         if(!mmd) {
 198                                 md = base->object->modifiers.first;
 199
 200                                 while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
 201                                         md = md->next;
 202
 203                                 mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
 204                                 BLI_insertlinkbefore(&base->object->modifiers, md, mmd);
 205                                 modifier_unique_name(&base->object->modifiers, mmd);
 206                         }
 207
 208                         if(mmd)
 209                                 multiresModifier_subdivide(mmd, base->object, highest_lvl - mmd->totlvl, 0, 0);
 210                 }
 211                 base = base->next;
 212         }
 213 }
 214 #endif
 215
 216 int multiresModifier_reshapeFromDM(Scene *scene, MultiresModifierData *mmd,
 217                                 Object *ob, DerivedMesh *srcdm)
 218 {
 219         DerivedMesh *mrdm = get_multires_dm (scene, mmd, ob);
 220
 221         if(mrdm && srcdm && mrdm->getNumVerts(mrdm) == srcdm->getNumVerts(srcdm)) {
 222                 multires_mvert_to_ss(mrdm, srcdm->getVertArray(srcdm));
 223
 224                 multires_dm_mark_as_modified(mrdm);
 225                 multires_force_update(ob);
 226
 227                 mrdm->release(mrdm);
 228
 229                 return 1;
 230         }
 231
 232         mrdm->release(mrdm);
 233
 234         return 0;
 235 }
 236
 237 /* Returns 1 on success, 0 if the src's totvert doesn't match */
 238 int multiresModifier_reshape(Scene *scene, MultiresModifierData *mmd, Object *dst, Object *src)
 239 {
 240         DerivedMesh *srcdm = mesh_get_derived_final(scene, src, CD_MASK_BAREMESH);
 241         return multiresModifier_reshapeFromDM(scene, mmd, dst, srcdm);
 242 }
 243
 244 int multiresModifier_reshapeFromDeformMod(Scene *scene, MultiresModifierData *mmd,
 245                                 Object *ob, ModifierData *md)
 246 {
 247         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
 248         DerivedMesh *dm, *ndm;
 249         int numVerts, result;
 250         float (*deformedVerts)[3];
 251
 252         if(multires_get_level(ob, mmd, 0) == 0)
 253                 return 0;
 254
 255         /* Create DerivedMesh for deformation modifier */
 256         dm = get_multires_dm(scene, mmd, ob);
 257         numVerts= dm->getNumVerts(dm);
 258         deformedVerts= MEM_callocN(sizeof(float)*numVerts*3, "multiresReshape_deformVerts");
 259
 260         dm->getVertCos(dm, deformedVerts);
 261         mti->deformVerts(md, ob, dm, deformedVerts, numVerts, 0, 0);
 262
 263         ndm= CDDM_copy(dm);
 264         CDDM_apply_vert_coords(ndm, deformedVerts);
 265
 266         MEM_freeN(deformedVerts);
 267         dm->release(dm);
 268
 269         /* Reshaping */
 270         result= multiresModifier_reshapeFromDM(scene, mmd, ob, ndm);
 271
 272         /* Cleanup */
 273         ndm->release(ndm);
 274
 275         return result;
 276 }
 277
 278 /* reset the multires levels to match the number of mdisps */
 279 void multiresModifier_set_levels_from_disps(MultiresModifierData *mmd, Object *ob)
 280 {
 281         Mesh *me = ob->data;
 282         MDisps *mdisp;
 283         int i;
 284
 285         mdisp = CustomData_get_layer(&me->fdata, CD_MDISPS);
 286
 287         if(mdisp) {
 288                 for(i = 0; i < me->totface; ++i, ++mdisp) {
 289                         int S = me->mface[i].v4 ? 4 : 3;
 290
 291                         if(mdisp->totdisp == 0) continue;
 292
 293                         while(1) {
 294                                 int side = (1 << (mmd->totlvl-1)) + 1;
 295                                 int lvl_totdisp = side*side*S;
 296                                 if(mdisp->totdisp == lvl_totdisp)
 297                                         break;
 298                                 else if(mdisp->totdisp < lvl_totdisp)
 299                                         --mmd->totlvl;
 300                                 else
 301                                         ++mmd->totlvl;
 302
 303                         }
 304                 }
 305
 306                 mmd->lvl = MIN2(mmd->sculptlvl, mmd->totlvl);
 307                 mmd->sculptlvl = MIN2(mmd->sculptlvl, mmd->totlvl);
 308                 mmd->renderlvl = MIN2(mmd->renderlvl, mmd->totlvl);
 309         }
 310 }
 311
 312 static void multires_set_tot_mdisps(Mesh *me, int lvl)
 313 {
 314         MDisps *mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
 315         int i;
 316
 317         if(mdisps) {
 318                 for(i = 0; i < me->totface; i++) {
 319                         if(mdisps[i].totdisp == 0) {
 320                                 int nvert = (me->mface[i].v4)? 4: 3;
 321                                 mdisps[i].totdisp = multires_grid_tot[lvl]*nvert;
 322                         }
 323                 }
 324         }
 325 }
 326
 327 static void multires_reallocate_mdisps(Mesh *me, MDisps *mdisps, int lvl)
 328 {
 329         int i;
 330
 331         /* reallocate displacements to be filled in */
 332         for(i = 0; i < me->totface; ++i) {
 333                 int nvert = (me->mface[i].v4)? 4: 3;
 334                 int totdisp = multires_grid_tot[lvl]*nvert;
 335                 float (*disps)[3] = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
 336
 337                 if(mdisps[i].disps)
 338                         MEM_freeN(mdisps[i].disps);
 339
 340                 mdisps[i].disps = disps;
 341                 mdisps[i].totdisp = totdisp;
 342         }
 343 }
 344
 345 static void column_vectors_to_mat3(float mat[][3], float v1[3], float v2[3], float v3[3])
 346 {
 347         copy_v3_v3(mat[0], v1);
 348         copy_v3_v3(mat[1], v2);
 349         copy_v3_v3(mat[2], v3);
 350 }
 351
 352 static void multires_copy_grid(float (*gridA)[3], float (*gridB)[3], int sizeA, int sizeB)
 353 {
 354         int x, y, j, skip;
 355
 356         if(sizeA > sizeB) {
 357                 skip = (sizeA-1)/(sizeB-1);
 358
 359                 for(j = 0, y = 0; y < sizeB; y++)
 360                         for(x = 0; x < sizeB; x++, j++)
 361                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip], gridB[j]);
 362         }
 363         else {
 364                 skip = (sizeB-1)/(sizeA-1);
 365
 366                 for(j = 0, y = 0; y < sizeA; y++)
 367                         for(x = 0; x < sizeA; x++, j++)
 368                                 copy_v3_v3(gridA[j], gridB[y*skip*sizeB + x*skip]);
 369         }
 370 }
 371
 372 static void multires_copy_dm_grid(DMGridData *gridA, DMGridData *gridB, int sizeA, int sizeB)
 373 {
 374         int x, y, j, skip;
 375
 376         if(sizeA > sizeB) {
 377                 skip = (sizeA-1)/(sizeB-1);
 378
 379                 for(j = 0, y = 0; y < sizeB; y++)
 380                         for(x = 0; x < sizeB; x++, j++)
 381                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip].co, gridB[j].co);
 382         }
 383         else {
 384                 skip = (sizeB-1)/(sizeA-1);
 385
 386                 for(j = 0, y = 0; y < sizeA; y++)
 387                         for(x = 0; x < sizeA; x++, j++)
 388                                 copy_v3_v3(gridA[j].co, gridB[y*skip*sizeB + x*skip].co);
 389         }
 390 }
 391
 392 /* direction=1 for delete higher, direction=0 for lower (not implemented yet) */
 393 void multiresModifier_del_levels(MultiresModifierData *mmd, Object *ob, int direction)
 394 {
 395         Mesh *me = get_mesh(ob);
 396         int lvl = multires_get_level(ob, mmd, 0);
 397         int levels = mmd->totlvl - lvl;
 398         MDisps *mdisps;
 399
 400         multires_set_tot_mdisps(me, mmd->totlvl);
 401         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
 402         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
 403
 404         multires_force_update(ob);
 405
 406         if(mdisps && levels > 0 && direction == 1) {
 407                 if(lvl > 0) {
 408                         int nsize = multires_side_tot[lvl];
 409                         int hsize = multires_side_tot[mmd->totlvl];
 410                         int i;
 411
 412                         for(i = 0; i < me->totface; ++i) {
 413                                 MDisps *mdisp= &mdisps[i];
 414                                 float (*disps)[3], (*ndisps)[3], (*hdisps)[3];
 415                                 int nvert = (me->mface[i].v4)? 4: 3;
 416                                 int totdisp = multires_grid_tot[lvl]*nvert;
 417                                 int S;
 418
 419                                 disps = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
 420
 421                                 ndisps = disps;
 422                                 hdisps = mdisp->disps;
 423
 424                                 for(S = 0; S < nvert; S++) {
 425                                         multires_copy_grid(ndisps, hdisps, nsize, hsize);
 426
 427                                         ndisps += nsize*nsize;
 428                                         hdisps += hsize*hsize;
 429                                 }
 430
 431                                 MEM_freeN(mdisp->disps);
 432                                 mdisp->disps = disps;
 433                                 mdisp->totdisp = totdisp;
 434                         }
 435                 }
 436                 else {
 437                         CustomData_external_remove(&me->fdata, &me->id, CD_MDISPS, me->totface);
 438                         CustomData_free_layer_active(&me->fdata, CD_MDISPS, me->totface);
 439                 }
 440         }
 441
 442         multires_set_tot_level(ob, mmd, lvl);
 443 }
 444
 445 static DerivedMesh *multires_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int totlvl, int simple)
 446 {
 447         MultiresModifierData mmd;
 448
 449         memset(&mmd, 0, sizeof(MultiresModifierData));
 450         mmd.lvl = lvl;
 451         mmd.sculptlvl = lvl;
 452         mmd.renderlvl = lvl;
 453         mmd.totlvl = totlvl;
 454         mmd.simple = simple;
 455
 456         return multires_dm_create_from_derived(&mmd, 1, dm, ob, 0, 0);
 457 }
 458
 459 static DerivedMesh *subsurf_dm_create_local(Object *UNUSED(ob), DerivedMesh *dm, int lvl, int simple, int optimal)
 460 {
 461         SubsurfModifierData smd;
 462
 463         memset(&smd, 0, sizeof(SubsurfModifierData));
 464         smd.levels = smd.renderLevels = lvl;
 465         smd.flags |= eSubsurfModifierFlag_SubsurfUv;
 466         if(simple)
 467                 smd.subdivType = ME_SIMPLE_SUBSURF;
 468         if(optimal)
 469                 smd.flags |= eSubsurfModifierFlag_ControlEdges;
 470
 471         return subsurf_make_derived_from_derived(dm, &smd, 0, NULL, 0, 0);
 472 }
 473
 474 void multiresModifier_subdivide(MultiresModifierData *mmd, Object *ob, int updateblock, int simple)
 475 {
 476         Mesh *me = ob->data;
 477         MDisps *mdisps;
 478         int lvl= mmd->totlvl;
 479         int totlvl= mmd->totlvl+1;
 480
 481         if(totlvl > multires_max_levels)
 482                 return;
 483
 484         multires_force_update(ob);
 485
 486         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
 487         if(!mdisps)
 488                 mdisps = CustomData_add_layer(&me->fdata, CD_MDISPS, CD_DEFAULT, NULL, me->totface);
 489
 490         if(mdisps->disps && !updateblock && totlvl > 1) {
 491                 /* upsample */
 492                 DerivedMesh *lowdm, *cddm, *highdm;
 493                 DMGridData **highGridData, **lowGridData, **subGridData;
 494                 CCGSubSurf *ss;
 495                 int i, numGrids, highGridSize, lowGridSize;
 496
 497                 /* create subsurf DM from original mesh at high level */
 498                 cddm = CDDM_from_mesh(me, NULL);
 499                 DM_set_only_copy(cddm, CD_MASK_BAREMESH);
 500                 highdm = subsurf_dm_create_local(ob, cddm, totlvl, simple, 0);
 501
 502                 /* create multires DM from original mesh at low level */
 503                 lowdm = multires_dm_create_local(ob, cddm, lvl, lvl, simple);
 504                 cddm->release(cddm);
 505
 506                 /* copy subsurf grids and replace them with low displaced grids */
 507                 numGrids = highdm->getNumGrids(highdm);
 508                 highGridSize = highdm->getGridSize(highdm);
 509                 highGridData = highdm->getGridData(highdm);
 510                 lowGridSize = lowdm->getGridSize(lowdm);
 511                 lowGridData = lowdm->getGridData(lowdm);
 512
 513                 subGridData = MEM_callocN(sizeof(float*)*numGrids, "subGridData*");
 514
 515                 for(i = 0; i < numGrids; ++i) {
 516                         /* backup subsurf grids */
 517                         subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
 518                         memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
 519
 520                         /* overwrite with current displaced grids */
 521                         multires_copy_dm_grid(highGridData[i], lowGridData[i], highGridSize, lowGridSize);
 522                 }
 523
 524                 /* low lower level dm no longer needed at this point */
 525                 lowdm->release(lowdm);
 526
 527                 /* subsurf higher levels again with displaced data */
 528                 ss= ((CCGDerivedMesh*)highdm)->ss;
 529                 ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
 530                 ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
 531
 532                 /* reallocate displacements */
 533                 multires_reallocate_mdisps(me, mdisps, totlvl);
 534
 535                 /* compute displacements */
 536                 multiresModifier_disp_run(highdm, me, 1, 0, subGridData, totlvl);
 537
 538                 /* free */
 539                 highdm->release(highdm);
 540                 for(i = 0; i < numGrids; ++i)
 541                         MEM_freeN(subGridData[i]);
 542                 MEM_freeN(subGridData);
 543         }
 544         else {
 545                 /* only reallocate, nothing to upsample */
 546                 multires_reallocate_mdisps(me, mdisps, totlvl);
 547         }
 548
 549         multires_set_tot_level(ob, mmd, totlvl);
 550 }
 551
 552 static void grid_tangent(int gridSize, int index, int x, int y, int axis, DMGridData **gridData, float t[3])
 553 {
 554         if(axis == 0) {
 555                 if(x == gridSize - 1) {
 556                         if(y == gridSize - 1)
 557                                 sub_v3_v3v3(t, gridData[index][x + gridSize*(y - 1)].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
 558                         else
 559                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x - 1 + gridSize*y].co);
 560                 }
 561                 else
 562                         sub_v3_v3v3(t, gridData[index][x + 1 + gridSize*y].co, gridData[index][x + gridSize*y].co);
 563         }
 564         else if(axis == 1) {
 565                 if(y == gridSize - 1) {
 566                         if(x == gridSize - 1)
 567                                 sub_v3_v3v3(t, gridData[index][x - 1 + gridSize*y].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
 568                         else
 569                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x + gridSize*(y - 1)].co);
 570                 }
 571                 else
 572                         sub_v3_v3v3(t, gridData[index][x + gridSize*(y + 1)].co, gridData[index][x + gridSize*y].co);
 573         }
 574 }
 575
 576 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, int invert, int add, DMGridData **oldGridData, int totlvl)
 577 {
 578         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)dm;
 579         DMGridData **gridData, **subGridData;
 580         MFace *mface = me->mface;
 581         MDisps *mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
 582         int *gridOffset;
 583         int i, numGrids, gridSize, dGridSize, dSkip;
 584
 585         if(!mdisps) {
 586                 if(invert)
 587                         mdisps = CustomData_add_layer(&me->fdata, CD_MDISPS, CD_DEFAULT, NULL, me->totface);
 588                 else
 589                         return;
 590         }
 591
 592         numGrids = dm->getNumGrids(dm);
 593         gridSize = dm->getGridSize(dm);
 594         gridData = dm->getGridData(dm);
 595         gridOffset = dm->getGridOffset(dm);
 596         subGridData = (oldGridData)? oldGridData: gridData;
 597
 598         dGridSize = multires_side_tot[totlvl];
 599         dSkip = (dGridSize-1)/(gridSize-1);
 600
 601         #pragma omp parallel for private(i) if(me->totface*gridSize*gridSize*4 >= CCG_OMP_LIMIT)
 602         for(i = 0; i < me->totface; ++i) {
 603                 const int numVerts = mface[i].v4 ? 4 : 3;
 604                 MDisps *mdisp = &mdisps[i];
 605                 int S, x, y, gIndex = gridOffset[i];
 606
 607                 /* when adding new faces in edit mode, need to allocate disps */
 608                 if(!mdisp->disps)
 609                 #pragma omp critical
 610                 {
 611                         multires_reallocate_mdisps(me, mdisps, totlvl);
 612                 }
 613
 614                 for(S = 0; S < numVerts; ++S, ++gIndex) {
 615                         DMGridData *grid = gridData[gIndex];
 616                         DMGridData *subgrid = subGridData[gIndex];
 617                         float (*dispgrid)[3] = &mdisp->disps[S*dGridSize*dGridSize];
 618
 619                         for(y = 0; y < gridSize; y++) {
 620                                 for(x = 0; x < gridSize; x++) {
 621                                         float *co = grid[x + y*gridSize].co;
 622                                         float *sco = subgrid[x + y*gridSize].co;
 623                                         float *no = subgrid[x + y*gridSize].no;
 624                                         float *data = dispgrid[dGridSize*y*dSkip + x*dSkip];
 625                                         float mat[3][3], tx[3], ty[3], disp[3], d[3];
 626
 627                                         /* construct tangent space matrix */
 628                                         grid_tangent(gridSize, gIndex, x, y, 0, subGridData, tx);
 629                                         normalize_v3(tx);
 630
 631                                         grid_tangent(gridSize, gIndex, x, y, 1, subGridData, ty);
 632                                         normalize_v3(ty);
 633
 634                                         //mul_v3_fl(tx, 1.0f/(gridSize-1));
 635                                         //mul_v3_fl(ty, 1.0f/(gridSize-1));
 636                                         //cross_v3_v3v3(no, tx, ty);
 637
 638                                         column_vectors_to_mat3(mat, tx, ty, no);
 639
 640                                         if(!invert) {
 641                                                 /* convert to object space and add */
 642                                                 mul_v3_m3v3(disp, mat, data);
 643                                                 add_v3_v3v3(co, sco, disp);
 644                                         }
 645                                         else if(!add) {
 646                                                 /* convert difference to tangent space */
 647                                                 sub_v3_v3v3(disp, co, sco);
 648                                                 invert_m3(mat);
 649                                                 mul_v3_m3v3(data, mat, disp);
 650                                         }
 651                                         else {
 652                                                 /* convert difference to tangent space */
 653                                                 invert_m3(mat);
 654                                                 mul_v3_m3v3(d, mat, co);
 655                                                 add_v3_v3(data, d);
 656                                         }
 657                                 }
 658                         }
 659                 }
 660         }
 661
 662         if(!invert) {
 663                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, NULL, 0);
 664                 ccgSubSurf_updateNormals(ccgdm->ss, NULL, 0);
 665         }
 666 }
 667
 668 static void multiresModifier_update(DerivedMesh *dm)
 669 {
 670         CCGDerivedMesh *ccgdm= (CCGDerivedMesh*)dm;
 671         Object *ob;
 672         Mesh *me;
 673         MDisps *mdisps;
 674         MultiresModifierData *mmd;
 675
 676         ob = ccgdm->multires.ob;
 677         me = ccgdm->multires.ob->data;
 678         mmd = ccgdm->multires.mmd;
 679         multires_set_tot_mdisps(me, mmd->totlvl);
 680         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
 681         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
 682
 683         if(mdisps) {
 684                 int lvl = ccgdm->multires.lvl;
 685                 int totlvl = ccgdm->multires.totlvl;
 686
 687                 if(lvl < totlvl) {
 688                         Mesh *me = ob->data;
 689                         DerivedMesh *lowdm, *cddm, *highdm;
 690                         DMGridData **highGridData, **lowGridData, **subGridData, **gridData, *diffGrid;
 691                         CCGSubSurf *ss;
 692                         int i, j, numGrids, highGridSize, lowGridSize;
 693
 694                         /* create subsurf DM from original mesh at high level */
 695                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
 696                         else cddm = CDDM_from_mesh(me, NULL);
 697                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
 698
 699                         highdm = subsurf_dm_create_local(ob, cddm, totlvl, mmd->simple, 0);
 700
 701                         /* create multires DM from original mesh and displacements */
 702                         lowdm = multires_dm_create_local(ob, cddm, lvl, totlvl, mmd->simple);
 703                         cddm->release(cddm);
 704
 705                         /* gather grid data */
 706                         numGrids = highdm->getNumGrids(highdm);
 707                         highGridSize = highdm->getGridSize(highdm);
 708                         highGridData = highdm->getGridData(highdm);
 709                         lowGridSize = lowdm->getGridSize(lowdm);
 710                         lowGridData = lowdm->getGridData(lowdm);
 711                         gridData = dm->getGridData(dm);
 712
 713                         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
 714                         diffGrid = MEM_callocN(sizeof(DMGridData)*lowGridSize*lowGridSize, "diff");
 715
 716                         for(i = 0; i < numGrids; ++i) {
 717                                 /* backup subsurf grids */
 718                                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
 719                                 memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
 720
 721                                 /* write difference of subsurf and displaced low level into high subsurf */
 722                                 for(j = 0; j < lowGridSize*lowGridSize; ++j)
 723                                         sub_v3_v3v3(diffGrid[j].co, gridData[i][j].co, lowGridData[i][j].co);
 724
 725                                 multires_copy_dm_grid(highGridData[i], diffGrid, highGridSize, lowGridSize);
 726                         }
 727
 728                         /* lower level dm no longer needed at this point */
 729                         MEM_freeN(diffGrid);
 730                         lowdm->release(lowdm);
 731
 732                         /* subsurf higher levels again with difference of coordinates */
 733                         ss= ((CCGDerivedMesh*)highdm)->ss;
 734                         ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
 735                         ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
 736
 737                         /* add to displacements */
 738                         multiresModifier_disp_run(highdm, me, 1, 1, subGridData, mmd->totlvl);
 739
 740                         /* free */
 741                         highdm->release(highdm);
 742                         for(i = 0; i < numGrids; ++i)
 743                                 MEM_freeN(subGridData[i]);
 744                         MEM_freeN(subGridData);
 745                 }
 746                 else {
 747                         DerivedMesh *cddm, *subdm;
 748
 749                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
 750                         else cddm = CDDM_from_mesh(me, NULL);
 751                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
 752
 753                         subdm = subsurf_dm_create_local(ob, cddm, mmd->totlvl, mmd->simple, 0);
 754                         cddm->release(cddm);
 755
 756                         multiresModifier_disp_run(dm, me, 1, 0, subdm->getGridData(subdm), mmd->totlvl);
 757
 758                         subdm->release(subdm);
 759                 }
 760         }
 761 }
 762
 763 void multires_stitch_grids(Object *ob)
 764 {
 765         /* utility for smooth brush */
 766         if(ob && ob->derivedFinal) {
 767                 CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)ob->derivedFinal;
 768                 CCGFace **faces;
 769                 int totface;
 770
 771                 if(ccgdm->pbvh) {
 772                         BLI_pbvh_get_grid_updates(ccgdm->pbvh, 0, (void***)&faces, &totface);
 773
 774                         if(totface) {
 775                                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, faces, totface);
 776                                 MEM_freeN(faces);
 777                         }
 778                 }
 779         }
 780 }
 781
 782 DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int local_mmd, DerivedMesh *dm, Object *ob,
 783                                                         int useRenderParams, int UNUSED(isFinalCalc))
 784 {
 785         Mesh *me= ob->data;
 786         DerivedMesh *result;
 787         CCGDerivedMesh *ccgdm;
 788         DMGridData **gridData, **subGridData;
 789         int lvl= multires_get_level(ob, mmd, useRenderParams);
 790         int i, gridSize, numGrids;
 791
 792         if(lvl == 0)
 793                 return dm;
 794
 795         result = subsurf_dm_create_local(ob, dm, lvl,
 796                 mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges);
 797
 798         if(!local_mmd) {
 799                 ccgdm = (CCGDerivedMesh*)result;
 800
 801                 ccgdm->multires.ob = ob;
 802                 ccgdm->multires.mmd = mmd;
 803                 ccgdm->multires.local_mmd = local_mmd;
 804                 ccgdm->multires.lvl = lvl;
 805                 ccgdm->multires.totlvl = mmd->totlvl;
 806                 ccgdm->multires.modified = 0;
 807                 ccgdm->multires.update = multiresModifier_update;
 808         }
 809
 810         numGrids = result->getNumGrids(result);
 811         gridSize = result->getGridSize(result);
 812         gridData = result->getGridData(result);
 813
 814         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
 815
 816         for(i = 0; i < numGrids; i++) {
 817                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*gridSize*gridSize, "subGridData");
 818                 memcpy(subGridData[i], gridData[i], sizeof(DMGridData)*gridSize*gridSize);
 819         }
 820
 821         multires_set_tot_mdisps(me, mmd->totlvl);
 822         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
 823         multiresModifier_disp_run(result, ob->data, 0, 0, subGridData, mmd->totlvl);
 824
 825         for(i = 0; i < numGrids; i++)
 826                 MEM_freeN(subGridData[i]);
 827         MEM_freeN(subGridData);
 828
 829         return result;
 830 }
 831
 832 /**** Old Multires code ****
 833 ***************************/
 834
 835 /* Adapted from sculptmode.c */
 836 static void old_mdisps_bilinear(float out[3], float (*disps)[3], int st, float u, float v)
 837 {
 838         int x, y, x2, y2;
 839         const int st_max = st - 1;
 840         float urat, vrat, uopp;
 841         float d[4][3], d2[2][3];
 842
 843         if(u < 0)
 844                 u = 0;
 845         else if(u >= st)
 846                 u = st_max;
 847         if(v < 0)
 848                 v = 0;
 849         else if(v >= st)
 850                 v = st_max;
 851
 852         x = floor(u);
 853         y = floor(v);
 854         x2 = x + 1;
 855         y2 = y + 1;
 856
 857         if(x2 >= st) x2 = st_max;
 858         if(y2 >= st) y2 = st_max;
 859
 860         urat = u - x;
 861         vrat = v - y;
 862         uopp = 1 - urat;
 863
 864         mul_v3_v3fl(d[0], disps[y * st + x], uopp);
 865         mul_v3_v3fl(d[1], disps[y * st + x2], urat);
 866         mul_v3_v3fl(d[2], disps[y2 * st + x], uopp);
 867         mul_v3_v3fl(d[3], disps[y2 * st + x2], urat);
 868
 869         add_v3_v3v3(d2[0], d[0], d[1]);
 870         add_v3_v3v3(d2[1], d[2], d[3]);
 871         mul_v3_fl(d2[0], 1 - vrat);
 872         mul_v3_fl(d2[1], vrat);
 873
 874         add_v3_v3v3(out, d2[0], d2[1]);
 875 }
 876
 877 static void old_mdisps_rotate(int S, int UNUSED(newside), int oldside, int x, int y, float *u, float *v)
 878 {
 879         float offset = oldside*0.5f - 0.5f;
 880
 881         if(S == 1) { *u= offset + x; *v = offset - y; }
 882         if(S == 2) { *u= offset + y; *v = offset + x; }
 883         if(S == 3) { *u= offset - x; *v = offset + y; }
 884         if(S == 0) { *u= offset - y; *v = offset - x; }
 885 }
 886
 887 static void old_mdisps_convert(MFace *mface, MDisps *mdisp)
 888 {
 889         int newlvl = log(sqrt(mdisp->totdisp)-1)/log(2);
 890         int oldlvl = newlvl+1;
 891         int oldside = multires_side_tot[oldlvl];
 892         int newside = multires_side_tot[newlvl];
 893         int nvert = (mface->v4)? 4: 3;
 894         int newtotdisp = multires_grid_tot[newlvl]*nvert;
 895         int x, y, S;
 896         float (*disps)[3], (*out)[3], u, v;
 897
 898         disps = MEM_callocN(sizeof(float) * 3 * newtotdisp, "multires disps");
 899
 900         out = disps;
 901         for(S = 0; S < nvert; S++) {
 902                 for(y = 0; y < newside; ++y) {
 903                         for(x = 0; x < newside; ++x, ++out) {
 904                                 old_mdisps_rotate(S, newside, oldside, x, y, &u, &v);
 905                                 old_mdisps_bilinear(*out, mdisp->disps, oldside, u, v);
 906
 907                                 if(S == 1) { (*out)[1]= -(*out)[1]; }
 908                                 else if(S == 2) { SWAP(float, (*out)[0], (*out)[1]); }
 909                                 else if(S == 3) { (*out)[0]= -(*out)[0]; }
 910                                 else if(S == 0) { SWAP(float, (*out)[0], (*out)[1]); (*out)[0]= -(*out)[0]; (*out)[1]= -(*out)[1]; };
 911                         }
 912                 }
 913         }
 914
 915         MEM_freeN(mdisp->disps);
 916
 917         mdisp->totdisp= newtotdisp;
 918         mdisp->disps= disps;
 919 }
 920
 921 void multires_load_old_250(Mesh *me)
 922 {
 923         MDisps *mdisps;
 924         int a;
 925
 926         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
 927
 928         if(mdisps) {
 929                 for(a=0; a<me->totface; a++)
 930                         if(mdisps[a].totdisp)
 931                                 old_mdisps_convert(&me->mface[a], &mdisps[a]);
 932         }
 933 }
 934
 935 /* Does not actually free lvl itself */
 936 static void multires_free_level(MultiresLevel *lvl)
 937 {
 938         if(lvl) {
 939                 if(lvl->faces) MEM_freeN(lvl->faces);
 940                 if(lvl->edges) MEM_freeN(lvl->edges);
 941                 if(lvl->colfaces) MEM_freeN(lvl->colfaces);
 942         }
 943 }
 944
 945 void multires_free(Multires *mr)
 946 {
 947         if(mr) {
 948                 MultiresLevel* lvl= mr->levels.first;
 949
 950                 /* Free the first-level data */
 951                 if(lvl) {
 952                         CustomData_free(&mr->vdata, lvl->totvert);
 953                         CustomData_free(&mr->fdata, lvl->totface);
 954                         if(mr->edge_flags)
 955                                 MEM_freeN(mr->edge_flags);
 956                         if(mr->edge_creases)
 957                                 MEM_freeN(mr->edge_creases);
 958                 }
 959
 960                 while(lvl) {
 961                         multires_free_level(lvl);
 962                         lvl= lvl->next;
 963                 }
 964
 965                 MEM_freeN(mr->verts);
 966
 967                 BLI_freelistN(&mr->levels);
 968
 969                 MEM_freeN(mr);
 970         }
 971 }
 972
 973 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
 974                                          const int totvert, const int totface)
 975 {
 976         int i,j;
 977         IndexNode *node = NULL;
 978
 979         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
 980         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
 981         node = *mem;
 982
 983         /* Find the users */
 984         for(i = 0; i < totface; ++i){
 985                 for(j = 0; j < (mface[i].v[3]?4:3); ++j, ++node) {
 986                         node->index = i;
 987                         BLI_addtail(&(*map)[mface[i].v[j]], node);
 988                 }
 989         }
 990 }
 991
 992 static void create_old_vert_edge_map(ListBase **map, IndexNode **mem, const MultiresEdge *medge,
 993                                          const int totvert, const int totedge)
 994 {
 995         int i,j;
 996         IndexNode *node = NULL;
 997
 998         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
 999         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge*2, "vert edge map mem");
1000         node = *mem;
1001
1002         /* Find the users */
1003         for(i = 0; i < totedge; ++i){
1004                 for(j = 0; j < 2; ++j, ++node) {
1005                         node->index = i;
1006                         BLI_addtail(&(*map)[medge[i].v[j]], node);
1007                 }
1008         }
1009 }
1010
1011 static MultiresFace *find_old_face(ListBase *map, MultiresFace *faces, int v1, int v2, int v3, int v4)
1012 {
1013         IndexNode *n1;
1014         int v[4] = {v1, v2, v3, v4}, i, j;
1015
1016         for(n1 = map[v1].first; n1; n1 = n1->next) {
1017                 int fnd[4] = {0, 0, 0, 0};
1018
1019                 for(i = 0; i < 4; ++i) {
1020                         for(j = 0; j < 4; ++j) {
1021                                 if(v[i] == faces[n1->index].v[j])
1022                                         fnd[i] = 1;
1023                         }
1024                 }
1025
1026                 if(fnd[0] && fnd[1] && fnd[2] && fnd[3])
1027                         return &faces[n1->index];
1028         }
1029
1030         return NULL;
1031 }
1032
1033 static MultiresEdge *find_old_edge(ListBase *map, MultiresEdge *edges, int v1, int v2)
1034 {
1035         IndexNode *n1, *n2;
1036
1037         for(n1 = map[v1].first; n1; n1 = n1->next) {
1038                 for(n2 = map[v2].first; n2; n2 = n2->next) {
1039                         if(n1->index == n2->index)
1040                                 return &edges[n1->index];
1041                 }
1042         }
1043
1044         return NULL;
1045 }
1046
1047 static void multires_load_old_edges(ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst, int v1, int v2, int mov)
1048 {
1049         int emid = find_old_edge(emap[2], lvl->edges, v1, v2)->mid;
1050         vvmap[dst + mov] = emid;
1051
1052         if(lvl->next->next) {
1053                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v1, emid, mov / 2);
1054                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v2, emid, -mov / 2);
1055         }
1056 }
1057
1058 static void multires_load_old_faces(ListBase **fmap, ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst,
1059                                         int v1, int v2, int v3, int v4, int st2, int st3)
1060 {
1061         int fmid;
1062         int emid13, emid14, emid23, emid24;
1063
1064         if(lvl && lvl->next) {
1065                 fmid = find_old_face(fmap[1], lvl->faces, v1, v2, v3, v4)->mid;
1066                 vvmap[dst] = fmid;
1067
1068                 emid13 = find_old_edge(emap[1], lvl->edges, v1, v3)->mid;
1069                 emid14 = find_old_edge(emap[1], lvl->edges, v1, v4)->mid;
1070                 emid23 = find_old_edge(emap[1], lvl->edges, v2, v3)->mid;
1071                 emid24 = find_old_edge(emap[1], lvl->edges, v2, v4)->mid;
1072
1073
1074                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 + st3,
1075                                         fmid, v2, emid23, emid24, st2, st3 / 2);
1076
1077                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 + st3,
1078                                         emid14, emid24, fmid, v4, st2, st3 / 2);
1079
1080                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 - st3,
1081                                         emid13, emid23, v3, fmid, st2, st3 / 2);
1082
1083                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 - st3,
1084                                         v1, fmid, emid13, emid14, st2, st3 / 2);
1085
1086                 if(lvl->next->next) {
1087                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid24, fmid, st3);
1088                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid13, fmid, -st3);
1089                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid14, fmid, -st2 * st3);
1090                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid23, fmid, st2 * st3);
1091                 }
1092         }
1093 }
1094
1095 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert)
1096 {
1097         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*) dm;
1098         CCGSubSurf *ss = ccgdm->ss;
1099         DMGridData *vd;
1100         int index;
1101         int totvert, totedge, totface;
1102         int gridSize = ccgSubSurf_getGridSize(ss);
1103         int edgeSize = ccgSubSurf_getEdgeSize(ss);
1104         int i = 0;
1105
1106         totface = ccgSubSurf_getNumFaces(ss);
1107         for(index = 0; index < totface; index++) {
1108                 CCGFace *f = ccgdm->faceMap[index].face;
1109                 int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1110
1111                 vd= ccgSubSurf_getFaceCenterData(f);
1112                 copy_v3_v3(vd->co, mvert[i].co);
1113                 i++;
1114
1115                 for(S = 0; S < numVerts; S++) {
1116                         for(x = 1; x < gridSize - 1; x++, i++) {
1117                                 vd= ccgSubSurf_getFaceGridEdgeData(ss, f, S, x);
1118                                 copy_v3_v3(vd->co, mvert[i].co);
1119                         }
1120                 }
1121
1122                 for(S = 0; S < numVerts; S++) {
1123                         for(y = 1; y < gridSize - 1; y++) {
1124                                 for(x = 1; x < gridSize - 1; x++, i++) {
1125                                         vd= ccgSubSurf_getFaceGridData(ss, f, S, x, y);
1126                                         copy_v3_v3(vd->co, mvert[i].co);
1127                                 }
1128                         }
1129                 }
1130         }
1131
1132         totedge = ccgSubSurf_getNumEdges(ss);
1133         for(index = 0; index < totedge; index++) {
1134                 CCGEdge *e = ccgdm->edgeMap[index].edge;
1135                 int x;
1136
1137                 for(x = 1; x < edgeSize - 1; x++, i++) {
1138                         vd= ccgSubSurf_getEdgeData(ss, e, x);
1139                         copy_v3_v3(vd->co, mvert[i].co);
1140                 }
1141         }
1142
1143         totvert = ccgSubSurf_getNumVerts(ss);
1144         for(index = 0; index < totvert; index++) {
1145                 CCGVert *v = ccgdm->vertMap[index].vert;
1146
1147                 vd= ccgSubSurf_getVertData(ss, v);
1148                 copy_v3_v3(vd->co, mvert[i].co);
1149                 i++;
1150         }
1151
1152         ccgSubSurf_updateToFaces(ss, 0, NULL, 0);
1153 }
1154
1155 /* Loads a multires object stored in the old Multires struct into the new format */
1156 static void multires_load_old_dm(DerivedMesh *dm, Mesh *me, int totlvl)
1157 {
1158         MultiresLevel *lvl, *lvl1;
1159         Multires *mr= me->mr;
1160         MVert *vsrc, *vdst;
1161         int src, dst;
1162         int st = multires_side_tot[totlvl - 1] - 1;
1163         int extedgelen = multires_side_tot[totlvl] - 2;
1164         int *vvmap; // inorder for dst, map to src
1165         int crossedgelen;
1166         int i, j, s, x, totvert, tottri, totquad;
1167
1168         src = 0;
1169         dst = 0;
1170         vsrc = mr->verts;
1171         vdst = dm->getVertArray(dm);
1172         totvert = dm->getNumVerts(dm);
1173         vvmap = MEM_callocN(sizeof(int) * totvert, "multires vvmap");
1174
1175         lvl1 = mr->levels.first;
1176         /* Load base verts */
1177         for(i = 0; i < lvl1->totvert; ++i) {
1178                 vvmap[totvert - lvl1->totvert + i] = src;
1179                 ++src;
1180         }
1181
1182         /* Original edges */
1183         dst = totvert - lvl1->totvert - extedgelen * lvl1->totedge;
1184         for(i = 0; i < lvl1->totedge; ++i) {
1185                 int ldst = dst + extedgelen * i;
1186                 int lsrc = src;
1187                 lvl = lvl1->next;
1188
1189                 for(j = 2; j <= mr->level_count; ++j) {
1190                         int base = multires_side_tot[totlvl - j + 1] - 2;
1191                         int skip = multires_side_tot[totlvl - j + 2] - 1;
1192                         int st = multires_side_tot[j - 1] - 1;
1193
1194                         for(x = 0; x < st; ++x)
1195                                 vvmap[ldst + base + x * skip] = lsrc + st * i + x;
1196
1197                         lsrc += lvl->totvert - lvl->prev->totvert;
1198                         lvl = lvl->next;
1199                 }
1200         }
1201
1202         /* Center points */
1203         dst = 0;
1204         for(i = 0; i < lvl1->totface; ++i) {
1205                 int sides = lvl1->faces[i].v[3] ? 4 : 3;
1206
1207                 vvmap[dst] = src + lvl1->totedge + i;
1208                 dst += 1 + sides * (st - 1) * st;
1209         }
1210
1211
1212         /* The rest is only for level 3 and up */
1213         if(lvl1->next && lvl1->next->next) {
1214                 ListBase **fmap, **emap;
1215                 IndexNode **fmem, **emem;
1216
1217                 /* Face edge cross */
1218                 tottri = totquad = 0;
1219                 crossedgelen = multires_side_tot[totlvl - 1] - 2;
1220                 dst = 0;
1221                 for(i = 0; i < lvl1->totface; ++i) {
1222                         int sides = lvl1->faces[i].v[3] ? 4 : 3;
1223
1224                         lvl = lvl1->next->next;
1225                         ++dst;
1226
1227                         for(j = 3; j <= mr->level_count; ++j) {
1228                                 int base = multires_side_tot[totlvl - j + 1] - 2;
1229                                 int skip = multires_side_tot[totlvl - j + 2] - 1;
1230                                 int st = pow(2, j - 2);
1231                                 int st2 = pow(2, j - 3);
1232                                 int lsrc = lvl->prev->totvert;
1233
1234                                 /* Skip exterior edge verts */
1235                                 lsrc += lvl1->totedge * st;
1236
1237                                 /* Skip earlier face edge crosses */
1238                                 lsrc += st2 * (tottri * 3 + totquad * 4);
1239
1240                                 for(s = 0; s < sides; ++s) {
1241                                         for(x = 0; x < st2; ++x) {
1242                                                 vvmap[dst + crossedgelen * (s + 1) - base - x * skip - 1] = lsrc;
1243                                                 ++lsrc;
1244                                         }
1245                                 }
1246
1247                                 lvl = lvl->next;
1248                         }
1249
1250                         dst += sides * (st - 1) * st;
1251
1252                         if(sides == 4) ++totquad;
1253                         else ++tottri;
1254
1255                 }
1256
1257                 /* calculate vert to edge/face maps for each level (except the last) */
1258                 fmap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires fmap");
1259                 emap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires emap");
1260                 fmem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires fmem");
1261                 emem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires emem");
1262                 lvl = lvl1;
1263                 for(i = 0; i < mr->level_count - 1; ++i) {
1264                         create_old_vert_face_map(fmap + i, fmem + i, lvl->faces, lvl->totvert, lvl->totface);
1265                         create_old_vert_edge_map(emap + i, emem + i, lvl->edges, lvl->totvert, lvl->totedge);
1266                         lvl = lvl->next;
1267                 }
1268
1269                 /* Interior face verts */
1270                 lvl = lvl1->next->next;
1271                 dst = 0;
1272                 for(j = 0; j < lvl1->totface; ++j) {
1273                         int sides = lvl1->faces[j].v[3] ? 4 : 3;
1274                         int ldst = dst + 1 + sides * (st - 1);
1275
1276                         for(s = 0; s < sides; ++s) {
1277                                 int st2 = multires_side_tot[totlvl - 1] - 2;
1278                                 int st3 = multires_side_tot[totlvl - 2] - 2;
1279                                 int st4 = st3 == 0 ? 1 : (st3 + 1) / 2;
1280                                 int mid = ldst + st2 * st3 + st3;
1281                                 int cv = lvl1->faces[j].v[s];
1282                                 int nv = lvl1->faces[j].v[s == sides - 1 ? 0 : s + 1];
1283                                 int pv = lvl1->faces[j].v[s == 0 ? sides - 1 : s - 1];
1284
1285                                 multires_load_old_faces(fmap, emap, lvl1->next, vvmap, mid,
1286                                                         vvmap[dst], cv,
1287                                                         find_old_edge(emap[0], lvl1->edges, pv, cv)->mid,
1288                                                         find_old_edge(emap[0], lvl1->edges, cv, nv)->mid,
1289                                                         st2, st4);
1290
1291                                 ldst += (st - 1) * (st - 1);
1292                         }
1293
1294
1295                         dst = ldst;
1296                 }
1297
1298                 lvl = lvl->next;
1299
1300                 for(i = 0; i < mr->level_count - 1; ++i) {
1301                         MEM_freeN(fmap[i]);
1302                         MEM_freeN(fmem[i]);
1303                         MEM_freeN(emap[i]);
1304                         MEM_freeN(emem[i]);
1305                 }
1306
1307                 MEM_freeN(fmap);
1308                 MEM_freeN(emap);
1309                 MEM_freeN(fmem);
1310                 MEM_freeN(emem);
1311         }
1312
1313         /* Transfer verts */
1314         for(i = 0; i < totvert; ++i)
1315                 copy_v3_v3(vdst[i].co, vsrc[vvmap[i]].co);
1316
1317         MEM_freeN(vvmap);
1318
1319         multires_mvert_to_ss(dm, vdst);
1320 }
1321
1322
1323 void multires_load_old(Object *ob, Mesh *me)
1324 {
1325         MultiresLevel *lvl;
1326         ModifierData *md;
1327         MultiresModifierData *mmd;
1328         DerivedMesh *dm, *orig;
1329         CustomDataLayer *l;
1330         int i;
1331
1332         /* Load original level into the mesh */
1333         lvl = me->mr->levels.first;
1334         CustomData_free_layers(&me->vdata, CD_MVERT, lvl->totvert);
1335         CustomData_free_layers(&me->edata, CD_MEDGE, lvl->totedge);
1336         CustomData_free_layers(&me->fdata, CD_MFACE, lvl->totface);
1337         me->totvert = lvl->totvert;
1338         me->totedge = lvl->totedge;
1339         me->totface = lvl->totface;
1340         me->mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
1341         me->medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
1342         me->mface = CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
1343         memcpy(me->mvert, me->mr->verts, sizeof(MVert) * me->totvert);
1344         for(i = 0; i < me->totedge; ++i) {
1345                 me->medge[i].v1 = lvl->edges[i].v[0];
1346                 me->medge[i].v2 = lvl->edges[i].v[1];
1347         }
1348         for(i = 0; i < me->totface; ++i) {
1349                 me->mface[i].v1 = lvl->faces[i].v[0];
1350                 me->mface[i].v2 = lvl->faces[i].v[1];
1351                 me->mface[i].v3 = lvl->faces[i].v[2];
1352                 me->mface[i].v4 = lvl->faces[i].v[3];
1353         }
1354
1355         /* Add a multires modifier to the object */
1356         md = ob->modifiers.first;
1357         while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
1358                 md = md->next;
1359         mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
1360         BLI_insertlinkbefore(&ob->modifiers, md, mmd);
1361
1362         for(i = 0; i < me->mr->level_count - 1; ++i)
1363                 multiresModifier_subdivide(mmd, ob, 1, 0);
1364
1365         mmd->lvl = mmd->totlvl;
1366         orig = CDDM_from_mesh(me, NULL);
1367         dm = multires_dm_create_from_derived(mmd, 0, orig, ob, 0, 0);
1368
1369         multires_load_old_dm(dm, me, mmd->totlvl+1);
1370
1371         multires_dm_mark_as_modified(dm);
1372         dm->release(dm);
1373         orig->release(orig);
1374
1375         /* Copy the first-level data to the mesh */
1376         for(i = 0, l = me->mr->vdata.layers; i < me->mr->vdata.totlayer; ++i, ++l)
1377                 CustomData_add_layer(&me->vdata, l->type, CD_REFERENCE, l->data, me->totvert);
1378         for(i = 0, l = me->mr->fdata.layers; i < me->mr->fdata.totlayer; ++i, ++l)
1379                 CustomData_add_layer(&me->fdata, l->type, CD_REFERENCE, l->data, me->totface);
1380         memset(&me->mr->vdata, 0, sizeof(CustomData));
1381         memset(&me->mr->fdata, 0, sizeof(CustomData));
1382
1383         /* Remove the old multires */
1384         multires_free(me->mr);
1385         me->mr= NULL;
1386 }
1387