165b4b1e6e79da31b0fe126f4fef4a8ca3881124
[blender.git] / source / blender / blenkernel / intern / multires.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software  Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2007 by Nicholas Bishop
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/multires.c
29  *  \ingroup bke
30  */
31
32
33 #include "MEM_guardedalloc.h"
34
35 /* for reading old multires */
36 #define DNA_DEPRECATED_ALLOW
37
38 #include "DNA_mesh_types.h"
39 #include "DNA_meshdata_types.h"
40 #include "DNA_object_types.h"
41 #include "DNA_scene_types.h"
42
43 #include "BLI_bitmap.h"
44 #include "BLI_blenlib.h"
45 #include "BLI_math.h"
46 #include "BLI_utildefines.h"
47
48 #include "BKE_pbvh.h"
49 #include "BKE_ccg.h"
50 #include "BKE_cdderivedmesh.h"
51 #include "BKE_mesh.h"
52 #include "BKE_mesh_mapping.h"
53 #include "BKE_modifier.h"
54 #include "BKE_multires.h"
55 #include "BKE_paint.h"
56 #include "BKE_scene.h"
57 #include "BKE_subsurf.h"
58 #include "BKE_editmesh.h"
59
60 #include "BKE_object.h"
61
62 #include "CCGSubSurf.h"
63
64 #include <math.h>
65 #include <string.h>
66
67 /* MULTIRES MODIFIER */
68 static const int multires_max_levels = 13;
69 static const int multires_grid_tot[] = {0, 4, 9, 25, 81, 289, 1089, 4225, 16641, 66049, 263169, 1050625, 4198401, 16785409};
70 static const int multires_side_tot[] = {0, 2, 3, 5,  9,  17,  33,   65,   129,   257,   513,    1025,    2049,    4097};
71
72 /* See multiresModifier_disp_run for description of each operation */
73 typedef enum {
74         APPLY_DISPLACEMENTS,
75         CALC_DISPLACEMENTS,
76         ADD_DISPLACEMENTS,
77 } DispOp;
78
79 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert);
80 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, DerivedMesh *dm2, DispOp op, CCGElem **oldGridData, int totlvl);
81
82 /** Customdata **/
83
84 void multires_customdata_delete(Mesh *me)
85 {
86         if (me->edit_btmesh) {
87                 BMEditMesh *em = me->edit_btmesh;
88                 /* CustomData_external_remove is used here only to mark layer
89                  * as non-external for further free-ing, so zero element count
90                  * looks safer than em->totface */
91                 CustomData_external_remove(&em->bm->ldata, &me->id,
92                                            CD_MDISPS, 0);
93                 BM_data_layer_free(em->bm, &em->bm->ldata, CD_MDISPS);
94
95                 BM_data_layer_free(em->bm, &em->bm->ldata, CD_GRID_PAINT_MASK);
96         }
97         else {
98                 CustomData_external_remove(&me->ldata, &me->id,
99                                            CD_MDISPS, me->totloop);
100                 CustomData_free_layer_active(&me->ldata, CD_MDISPS,
101                                              me->totloop);
102
103                 CustomData_free_layer_active(&me->ldata, CD_GRID_PAINT_MASK,
104                                              me->totloop);
105         }
106 }
107
108 /** Grid hiding **/
109 static BLI_bitmap *multires_mdisps_upsample_hidden(BLI_bitmap *lo_hidden,
110                                                    int lo_level,
111                                                    int hi_level,
112
113                                                    /* assumed to be at hi_level (or
114                                                     *  null) */
115                                                    BLI_bitmap *prev_hidden)
116 {
117         BLI_bitmap *subd;
118         int hi_gridsize = BKE_ccg_gridsize(hi_level);
119         int lo_gridsize = BKE_ccg_gridsize(lo_level);
120         int yh, xh, xl, yl, xo, yo, hi_ndx;
121         int offset, factor;
122
123         BLI_assert(lo_level <= hi_level);
124
125         /* fast case */
126         if (lo_level == hi_level)
127                 return MEM_dupallocN(lo_hidden);
128
129         subd = BLI_BITMAP_NEW(hi_gridsize * hi_gridsize, "MDisps.hidden upsample");
130
131         factor = BKE_ccg_factor(lo_level, hi_level);
132         offset = 1 << (hi_level - lo_level - 1);
133
134         /* low-res blocks */
135         for (yl = 0; yl < lo_gridsize; yl++) {
136                 for (xl = 0; xl < lo_gridsize; xl++) {
137                         int lo_val = BLI_BITMAP_GET(lo_hidden, yl * lo_gridsize + xl);
138
139                         /* high-res blocks */
140                         for (yo = -offset; yo <= offset; yo++) {
141                                 yh = yl * factor + yo;
142                                 if (yh < 0 || yh >= hi_gridsize)
143                                         continue;
144
145                                 for (xo = -offset; xo <= offset; xo++) {
146                                         xh = xl * factor + xo;
147                                         if (xh < 0 || xh >= hi_gridsize)
148                                                 continue;
149
150                                         hi_ndx = yh * hi_gridsize + xh;
151
152                                         if (prev_hidden) {
153                                                 /* If prev_hidden is available, copy it to
154                                                  * subd, except when the equivalent element in
155                                                  * lo_hidden is different */
156                                                 if (lo_val != prev_hidden[hi_ndx]) {
157                                                         BLI_BITMAP_MODIFY(subd, hi_ndx, lo_val);
158                                                 }
159                                                 else {
160                                                         BLI_BITMAP_MODIFY(subd, hi_ndx, prev_hidden[hi_ndx]);
161                                                 }
162                                         }
163                                         else {
164                                                 BLI_BITMAP_MODIFY(subd, hi_ndx, lo_val);
165                                         }
166                                 }
167                         }
168                 }
169         }
170
171         return subd;
172 }
173
174 static BLI_bitmap *multires_mdisps_downsample_hidden(BLI_bitmap *old_hidden,
175                                                      int old_level,
176                                                      int new_level)
177 {
178         BLI_bitmap *new_hidden;
179         int new_gridsize = BKE_ccg_gridsize(new_level);
180         int old_gridsize = BKE_ccg_gridsize(old_level);
181         int x, y, factor, old_value;
182
183         BLI_assert(new_level <= old_level);
184         factor = BKE_ccg_factor(new_level, old_level);
185         new_hidden = BLI_BITMAP_NEW(new_gridsize * new_gridsize,
186                                     "downsample hidden");
187
188
189
190         for (y = 0; y < new_gridsize; y++) {
191                 for (x = 0; x < new_gridsize; x++) {
192                         old_value = BLI_BITMAP_GET(old_hidden,
193                                                    factor * y * old_gridsize + x * factor);
194                         
195                         BLI_BITMAP_MODIFY(new_hidden, y * new_gridsize + x, old_value);
196                 }
197         }
198
199         return new_hidden;
200 }
201
202 static void multires_output_hidden_to_ccgdm(CCGDerivedMesh *ccgdm,
203                                             Mesh *me, int level)
204 {
205         const MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
206         BLI_bitmap **grid_hidden = ccgdm->gridHidden;
207         int *gridOffset;
208         int i, j;
209         
210         gridOffset = ccgdm->dm.getGridOffset(&ccgdm->dm);
211
212         for (i = 0; i < me->totpoly; i++) {
213                 for (j = 0; j < me->mpoly[i].totloop; j++) {
214                         int g = gridOffset[i] + j;
215                         const MDisps *md = &mdisps[g];
216                         BLI_bitmap *gh = md->hidden;
217                         
218                         if (gh) {
219                                 grid_hidden[g] =
220                                         multires_mdisps_downsample_hidden(gh, md->level, level);
221                         }
222                 }
223         }
224 }
225
226 /* subdivide mdisps.hidden if needed (assumes that md.level reflects
227  * the current level of md.hidden) */
228 static void multires_mdisps_subdivide_hidden(MDisps *md, int new_level)
229 {
230         BLI_bitmap *subd;
231         
232         BLI_assert(md->hidden);
233
234         /* nothing to do if already subdivided enough */
235         if (md->level >= new_level)
236                 return;
237
238         subd = multires_mdisps_upsample_hidden(md->hidden,
239                                                md->level,
240                                                new_level,
241                                                NULL);
242         
243         /* swap in the subdivided data */
244         MEM_freeN(md->hidden);
245         md->hidden = subd;
246 }
247
248 static MDisps *multires_mdisps_initialize_hidden(Mesh *me, int level)
249 {
250         MDisps *mdisps = CustomData_add_layer(&me->ldata, CD_MDISPS,
251                                               CD_CALLOC, NULL, me->totloop);
252         int gridsize = BKE_ccg_gridsize(level);
253         int gridarea = gridsize * gridsize;
254         int i, j, k;
255         
256         for (i = 0; i < me->totpoly; i++) {
257                 int hide = 0;
258
259                 for (j = 0; j < me->mpoly[i].totloop; j++) {
260                         if (me->mvert[me->mloop[me->mpoly[i].loopstart + j].v].flag & ME_HIDE) {
261                                 hide = 1;
262                                 break;
263                         }
264                 }
265
266                 if (!hide)
267                         continue;
268
269                 for (j = 0; j < me->mpoly[i].totloop; j++) {
270                         MDisps *md = &mdisps[me->mpoly[i].loopstart + j];
271
272                         BLI_assert(!md->hidden);
273
274                         md->hidden = BLI_BITMAP_NEW(gridarea, "MDisps.hidden initialize");
275
276                         for (k = 0; k < gridarea; k++)
277                                 BLI_BITMAP_SET(md->hidden, k);
278                 }
279         }
280
281         return mdisps;
282 }
283
284 DerivedMesh *get_multires_dm(Scene *scene, MultiresModifierData *mmd, Object *ob)
285 {
286         ModifierData *md = (ModifierData *)mmd;
287         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
288         DerivedMesh *tdm = mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
289         DerivedMesh *dm;
290
291         dm = mti->applyModifier(md, ob, tdm, MOD_APPLY_USECACHE | MOD_APPLY_IGNORE_SIMPLIFY);
292         if (dm == tdm) {
293                 dm = CDDM_copy(tdm);
294         }
295
296         return dm;
297 }
298
299 MultiresModifierData *find_multires_modifier_before(Scene *scene, ModifierData *lastmd)
300 {
301         ModifierData *md;
302
303         for (md = lastmd; md; md = md->prev) {
304                 if (md->type == eModifierType_Multires) {
305                         if (modifier_isEnabled(scene, md, eModifierMode_Realtime))
306                                 return (MultiresModifierData *)md;
307                 }
308         }
309
310         return NULL;
311 }
312
313 /* used for applying scale on mdisps layer and syncing subdivide levels when joining objects
314  * use_first - return first multires modifier if all multires'es are disabled
315  */
316 MultiresModifierData *get_multires_modifier(Scene *scene, Object *ob, bool use_first)
317 {
318         ModifierData *md;
319         MultiresModifierData *mmd = NULL, *firstmmd = NULL;
320
321         /* find first active multires modifier */
322         for (md = ob->modifiers.first; md; md = md->next) {
323                 if (md->type == eModifierType_Multires) {
324                         if (!firstmmd)
325                                 firstmmd = (MultiresModifierData *)md;
326
327                         if (modifier_isEnabled(scene, md, eModifierMode_Realtime)) {
328                                 mmd = (MultiresModifierData *)md;
329                                 break;
330                         }
331                 }
332         }
333
334         if (!mmd && use_first) {
335                 /* active multires have not been found
336                  * try to use first one */
337                 return firstmmd;
338         }
339
340         return mmd;
341 }
342
343 static int multires_get_level(Object *ob, MultiresModifierData *mmd,
344                               bool render, bool ignore_simplify)
345 {
346         if (render)
347                 return (mmd->modifier.scene) ? get_render_subsurf_level(&mmd->modifier.scene->r, mmd->renderlvl) : mmd->renderlvl;
348         else if (ob->mode == OB_MODE_SCULPT)
349                 return mmd->sculptlvl;
350         else if (ignore_simplify)
351                 return mmd->lvl;
352         else
353                 return (mmd->modifier.scene) ? get_render_subsurf_level(&mmd->modifier.scene->r, mmd->lvl) : mmd->lvl;
354 }
355
356 void multires_set_tot_level(Object *ob, MultiresModifierData *mmd, int lvl)
357 {
358         mmd->totlvl = lvl;
359
360         if (ob->mode != OB_MODE_SCULPT)
361                 mmd->lvl = CLAMPIS(MAX2(mmd->lvl, lvl), 0, mmd->totlvl);
362
363         mmd->sculptlvl = CLAMPIS(MAX2(mmd->sculptlvl, lvl), 0, mmd->totlvl);
364         mmd->renderlvl = CLAMPIS(MAX2(mmd->renderlvl, lvl), 0, mmd->totlvl);
365 }
366
367 static void multires_dm_mark_as_modified(DerivedMesh *dm, MultiresModifiedFlags flags)
368 {
369         CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
370         ccgdm->multires.modified_flags |= flags;
371 }
372
373 void multires_mark_as_modified(Object *ob, MultiresModifiedFlags flags)
374 {
375         if (ob && ob->derivedFinal)
376                 multires_dm_mark_as_modified(ob->derivedFinal, flags);
377 }
378
379 void multires_force_update(Object *ob)
380 {
381         if (ob) {
382                 BKE_object_free_derived_caches(ob);
383
384                 if (ob->sculpt && ob->sculpt->pbvh) {
385                         BKE_pbvh_free(ob->sculpt->pbvh);
386                         ob->sculpt->pbvh = NULL;
387                 }
388         }
389 }
390
391 void multires_force_external_reload(Object *ob)
392 {
393         Mesh *me = BKE_mesh_from_object(ob);
394
395         CustomData_external_reload(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
396         multires_force_update(ob);
397 }
398
399 void multires_force_render_update(Object *ob)
400 {
401         if (ob && (ob->mode & OB_MODE_SCULPT) && modifiers_findByType(ob, eModifierType_Multires))
402                 multires_force_update(ob);
403 }
404
405 int multiresModifier_reshapeFromDM(Scene *scene, MultiresModifierData *mmd,
406                                    Object *ob, DerivedMesh *srcdm)
407 {
408         DerivedMesh *mrdm = get_multires_dm(scene, mmd, ob);
409
410         if (mrdm && srcdm && mrdm->getNumVerts(mrdm) == srcdm->getNumVerts(srcdm)) {
411                 multires_mvert_to_ss(mrdm, srcdm->getVertArray(srcdm));
412
413                 multires_dm_mark_as_modified(mrdm, MULTIRES_COORDS_MODIFIED);
414                 multires_force_update(ob);
415
416                 mrdm->release(mrdm);
417
418                 return 1;
419         }
420
421         if (mrdm) mrdm->release(mrdm);
422
423         return 0;
424 }
425
426 /* Returns 1 on success, 0 if the src's totvert doesn't match */
427 int multiresModifier_reshape(Scene *scene, MultiresModifierData *mmd, Object *dst, Object *src)
428 {
429         DerivedMesh *srcdm = mesh_get_derived_final(scene, src, CD_MASK_BAREMESH);
430         return multiresModifier_reshapeFromDM(scene, mmd, dst, srcdm);
431 }
432
433 int multiresModifier_reshapeFromDeformMod(Scene *scene, MultiresModifierData *mmd,
434                                           Object *ob, ModifierData *md)
435 {
436         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
437         DerivedMesh *dm, *ndm;
438         int numVerts, result;
439         float (*deformedVerts)[3];
440
441         if (multires_get_level(ob, mmd, false, true) == 0)
442                 return 0;
443
444         /* Create DerivedMesh for deformation modifier */
445         dm = get_multires_dm(scene, mmd, ob);
446         numVerts = dm->getNumVerts(dm);
447         deformedVerts = MEM_mallocN(sizeof(float[3]) * numVerts, "multiresReshape_deformVerts");
448
449         dm->getVertCos(dm, deformedVerts);
450         mti->deformVerts(md, ob, dm, deformedVerts, numVerts, 0);
451
452         ndm = CDDM_copy(dm);
453         CDDM_apply_vert_coords(ndm, deformedVerts);
454
455         MEM_freeN(deformedVerts);
456         dm->release(dm);
457
458         /* Reshaping */
459         result = multiresModifier_reshapeFromDM(scene, mmd, ob, ndm);
460
461         /* Cleanup */
462         ndm->release(ndm);
463
464         return result;
465 }
466
467 /* reset the multires levels to match the number of mdisps */
468 static int get_levels_from_disps(Object *ob)
469 {
470         Mesh *me = ob->data;
471         MDisps *mdisp, *md;
472         int i, j, totlvl = 0;
473
474         mdisp = CustomData_get_layer(&me->ldata, CD_MDISPS);
475
476         for (i = 0; i < me->totpoly; ++i) {
477                 md = mdisp + me->mpoly[i].loopstart;
478
479                 for (j = 0; j < me->mpoly[i].totloop; j++, md++) {
480                         if (md->totdisp == 0) continue;
481         
482                         while (1) {
483                                 int side = (1 << (totlvl - 1)) + 1;
484                                 int lvl_totdisp = side * side;
485                                 if (md->totdisp == lvl_totdisp)
486                                         break;
487                                 else if (md->totdisp < lvl_totdisp)
488                                         totlvl--;
489                                 else
490                                         totlvl++;
491         
492                         }
493                         
494                         break;
495                 }
496         }
497
498         return totlvl;
499 }
500
501 /* reset the multires levels to match the number of mdisps */
502 void multiresModifier_set_levels_from_disps(MultiresModifierData *mmd, Object *ob)
503 {
504         Mesh *me = ob->data;
505         MDisps *mdisp;
506
507         if (me->edit_btmesh)
508                 mdisp = CustomData_get_layer(&me->edit_btmesh->bm->ldata, CD_MDISPS);
509         else
510                 mdisp = CustomData_get_layer(&me->ldata, CD_MDISPS);
511
512         if (mdisp) {
513                 mmd->totlvl = get_levels_from_disps(ob);
514                 mmd->lvl = MIN2(mmd->sculptlvl, mmd->totlvl);
515                 mmd->sculptlvl = MIN2(mmd->sculptlvl, mmd->totlvl);
516                 mmd->renderlvl = MIN2(mmd->renderlvl, mmd->totlvl);
517         }
518 }
519
520 static void multires_set_tot_mdisps(Mesh *me, int lvl)
521 {
522         MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
523         int i;
524
525         if (mdisps) {
526                 for (i = 0; i < me->totloop; i++, mdisps++) {
527                         mdisps->totdisp = multires_grid_tot[lvl];
528                         mdisps->level = lvl;
529                 }
530         }
531 }
532
533 static void multires_reallocate_mdisps(int totloop, MDisps *mdisps, int lvl)
534 {
535         int i;
536
537         /* reallocate displacements to be filled in */
538         for (i = 0; i < totloop; ++i) {
539                 int totdisp = multires_grid_tot[lvl];
540                 float (*disps)[3] = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
541
542                 if (mdisps[i].disps)
543                         MEM_freeN(mdisps[i].disps);
544                 
545                 if (mdisps[i].level && mdisps[i].hidden)
546                         multires_mdisps_subdivide_hidden(&mdisps[i], lvl);
547
548                 mdisps[i].disps = disps;
549                 mdisps[i].totdisp = totdisp;
550                 mdisps[i].level = lvl;
551         }
552 }
553
554 static void multires_copy_grid(float (*gridA)[3], float (*gridB)[3], int sizeA, int sizeB)
555 {
556         int x, y, j, skip;
557
558         if (sizeA > sizeB) {
559                 skip = (sizeA - 1) / (sizeB - 1);
560
561                 for (j = 0, y = 0; y < sizeB; y++)
562                         for (x = 0; x < sizeB; x++, j++)
563                                 copy_v3_v3(gridA[y * skip * sizeA + x * skip], gridB[j]);
564         }
565         else {
566                 skip = (sizeB - 1) / (sizeA - 1);
567
568                 for (j = 0, y = 0; y < sizeA; y++)
569                         for (x = 0; x < sizeA; x++, j++)
570                                 copy_v3_v3(gridA[j], gridB[y * skip * sizeB + x * skip]);
571         }
572 }
573
574 static void multires_copy_dm_grid(CCGElem *gridA, CCGElem *gridB, CCGKey *keyA, CCGKey *keyB)
575 {
576         int x, y, j, skip;
577
578         if (keyA->grid_size > keyB->grid_size) {
579                 skip = (keyA->grid_size - 1) / (keyB->grid_size - 1);
580
581                 for (j = 0, y = 0; y < keyB->grid_size; y++)
582                         for (x = 0; x < keyB->grid_size; x++, j++)
583                                 memcpy(CCG_elem_offset_co(keyA, gridA, y * skip * keyA->grid_size + x * skip),
584                                        CCG_elem_offset_co(keyB, gridB, j),
585                                        sizeof(float) * keyA->num_layers);
586         }
587         else {
588                 skip = (keyB->grid_size - 1) / (keyA->grid_size - 1);
589
590                 for (j = 0, y = 0; y < keyA->grid_size; y++)
591                         for (x = 0; x < keyA->grid_size; x++, j++)
592                                 memcpy(CCG_elem_offset_co(keyA, gridA, j),
593                                        CCG_elem_offset_co(keyB, gridB, y * skip * keyB->grid_size + x * skip),
594                                        sizeof(float) * keyA->num_layers);
595         }
596 }
597
598 /* Reallocate gpm->data at a lower resolution and copy values over
599  * from the original high-resolution data */
600 static void multires_grid_paint_mask_downsample(GridPaintMask *gpm, int level)
601 {
602         if (level < gpm->level) {
603                 int gridsize = BKE_ccg_gridsize(level);
604                 float *data = MEM_callocN(sizeof(float) * gridsize * gridsize,
605                                           "multires_grid_paint_mask_downsample");
606                 int x, y;
607
608                 for (y = 0; y < gridsize; y++) {
609                         for (x = 0; x < gridsize; x++) {
610                                 data[y * gridsize + x] =
611                                     paint_grid_paint_mask(gpm, level, x, y);
612                         }
613                 }
614
615                 MEM_freeN(gpm->data);
616                 gpm->data = data;
617                 gpm->level = level;
618         }
619 }
620
621 static void multires_del_higher(MultiresModifierData *mmd, Object *ob, int lvl)
622 {
623         Mesh *me = (Mesh *)ob->data;
624         int levels = mmd->totlvl - lvl;
625         MDisps *mdisps;
626         GridPaintMask *gpm;
627
628         multires_set_tot_mdisps(me, mmd->totlvl);
629         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
630         mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
631         gpm = CustomData_get_layer(&me->ldata, CD_GRID_PAINT_MASK);
632
633         multires_force_update(ob);
634
635         if (mdisps && levels > 0) {
636                 if (lvl > 0) {
637                         /* MLoop *ml = me->mloop; */ /*UNUSED*/
638                         int nsize = multires_side_tot[lvl];
639                         int hsize = multires_side_tot[mmd->totlvl];
640                         int i, j;
641
642                         for (i = 0; i < me->totpoly; ++i) {
643                                 for (j = 0; j < me->mpoly[i].totloop; j++) {
644                                         int g = me->mpoly[i].loopstart + j;
645                                         MDisps *mdisp = &mdisps[g];
646                                         float (*disps)[3], (*ndisps)[3], (*hdisps)[3];
647                                         int totdisp = multires_grid_tot[lvl];
648
649                                         disps = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
650
651                                         ndisps = disps;
652                                         hdisps = mdisp->disps;
653
654                                         multires_copy_grid(ndisps, hdisps, nsize, hsize);
655                                         if (mdisp->hidden) {
656                                                 BLI_bitmap *gh =
657                                                     multires_mdisps_downsample_hidden(mdisp->hidden,
658                                                                                       mdisp->level,
659                                                                                       lvl);
660                                                 MEM_freeN(mdisp->hidden);
661                                                 mdisp->hidden = gh;
662                                         }
663
664                                         ndisps += nsize * nsize;
665                                         hdisps += hsize * hsize;
666
667                                         MEM_freeN(mdisp->disps);
668                                         mdisp->disps = disps;
669                                         mdisp->totdisp = totdisp;
670                                         mdisp->level = lvl;
671
672                                         if (gpm) {
673                                                 multires_grid_paint_mask_downsample(&gpm[g], lvl);
674                                         }
675                                 }
676                         }
677                 }
678                 else {
679                         multires_customdata_delete(me);
680                 }
681         }
682
683         multires_set_tot_level(ob, mmd, lvl);
684 }
685
686 /* (direction = 1) for delete higher, (direction = 0) for lower (not implemented yet) */
687 void multiresModifier_del_levels(MultiresModifierData *mmd, Object *ob, int direction)
688 {
689         Mesh *me = BKE_mesh_from_object(ob);
690         int lvl = multires_get_level(ob, mmd, false, true);
691         int levels = mmd->totlvl - lvl;
692         MDisps *mdisps;
693
694         multires_set_tot_mdisps(me, mmd->totlvl);
695         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
696         mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
697
698         multires_force_update(ob);
699
700         if (mdisps && levels > 0 && direction == 1) {
701                 multires_del_higher(mmd, ob, lvl);
702         }
703
704         multires_set_tot_level(ob, mmd, lvl);
705 }
706
707 static DerivedMesh *multires_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int totlvl, int simple, bool alloc_paint_mask)
708 {
709         MultiresModifierData mmd = {{NULL}};
710         MultiresFlags flags = MULTIRES_USE_LOCAL_MMD;
711
712         mmd.lvl = lvl;
713         mmd.sculptlvl = lvl;
714         mmd.renderlvl = lvl;
715         mmd.totlvl = totlvl;
716         mmd.simple = simple;
717
718         if (alloc_paint_mask)
719                 flags |= MULTIRES_ALLOC_PAINT_MASK;
720
721         return multires_make_derived_from_derived(dm, &mmd, ob, flags);
722 }
723
724 static DerivedMesh *subsurf_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int simple, int optimal, int plain_uv, int alloc_paint_mask)
725 {
726         SubsurfModifierData smd = {{NULL}};
727         SubsurfFlags flags = 0;
728
729         smd.levels = smd.renderLevels = lvl;
730         if (!plain_uv)
731                 smd.flags |= eSubsurfModifierFlag_SubsurfUv;
732         if (simple)
733                 smd.subdivType = ME_SIMPLE_SUBSURF;
734         if (optimal)
735                 smd.flags |= eSubsurfModifierFlag_ControlEdges;
736
737         if (ob->mode & OB_MODE_EDIT)
738                 flags |= SUBSURF_IN_EDIT_MODE;
739
740         if (alloc_paint_mask)
741                 flags |= SUBSURF_ALLOC_PAINT_MASK;
742         
743         return subsurf_make_derived_from_derived(dm, &smd, NULL, flags);
744 }
745
746
747
748 /* assumes no is normalized; return value's sign is negative if v is on
749  * the other side of the plane */
750 static float v3_dist_from_plane(float v[3], float center[3], float no[3])
751 {
752         float s[3];
753         sub_v3_v3v3(s, v, center);
754         return dot_v3v3(s, no);
755 }
756
757 void multiresModifier_base_apply(MultiresModifierData *mmd, Object *ob)
758 {
759         DerivedMesh *cddm, *dispdm, *origdm;
760         Mesh *me;
761         const MeshElemMap *pmap;
762         float (*origco)[3];
763         int i, j, k, offset, totlvl;
764
765         multires_force_update(ob);
766
767         me = BKE_mesh_from_object(ob);
768         totlvl = mmd->totlvl;
769
770         /* nothing to do */
771         if (!totlvl)
772                 return;
773
774         /* XXX - probably not necessary to regenerate the cddm so much? */
775
776         /* generate highest level with displacements */
777         cddm = CDDM_from_mesh(me);
778         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
779         dispdm = multires_dm_create_local(ob, cddm, totlvl, totlvl, 0, 0);
780         cddm->release(cddm);
781
782         /* copy the new locations of the base verts into the mesh */
783         offset = dispdm->getNumVerts(dispdm) - me->totvert;
784         for (i = 0; i < me->totvert; ++i) {
785                 dispdm->getVertCo(dispdm, offset + i, me->mvert[i].co);
786         }
787
788         /* heuristic to produce a better-fitting base mesh */
789
790         cddm = CDDM_from_mesh(me);
791         pmap = cddm->getPolyMap(ob, cddm);
792         origco = MEM_callocN(sizeof(float) * 3 * me->totvert, "multires apply base origco");
793         for (i = 0; i < me->totvert; ++i)
794                 copy_v3_v3(origco[i], me->mvert[i].co);
795
796         for (i = 0; i < me->totvert; ++i) {
797                 float avg_no[3] = {0, 0, 0}, center[3] = {0, 0, 0}, push[3];
798                 float dist;
799                 int tot = 0;
800
801                 /* don't adjust verts not used by at least one poly */
802                 if (!pmap[i].count)
803                         continue;
804
805                 /* find center */
806                 for (j = 0; j < pmap[i].count; j++) {
807                         const MPoly *p = &me->mpoly[pmap[i].indices[j]];
808                         
809                         /* this double counts, not sure if that's bad or good */
810                         for (k = 0; k < p->totloop; ++k) {
811                                 int vndx = me->mloop[p->loopstart + k].v;
812                                 if (vndx != i) {
813                                         add_v3_v3(center, origco[vndx]);
814                                         tot++;
815                                 }
816                         }
817                 }
818                 mul_v3_fl(center, 1.0f / tot);
819
820                 /* find normal */
821                 for (j = 0; j < pmap[i].count; j++) {
822                         const MPoly *p = &me->mpoly[pmap[i].indices[j]];
823                         MPoly fake_poly;
824                         MLoop *fake_loops;
825                         float (*fake_co)[3];
826                         float no[3];
827
828                         /* set up poly, loops, and coords in order to call
829                          * BKE_mesh_calc_poly_normal_coords() */
830                         fake_poly.totloop = p->totloop;
831                         fake_poly.loopstart = 0;
832                         fake_loops = MEM_mallocN(sizeof(MLoop) * p->totloop, "fake_loops");
833                         fake_co = MEM_mallocN(sizeof(float) * 3 * p->totloop, "fake_co");
834                         
835                         for (k = 0; k < p->totloop; ++k) {
836                                 int vndx = me->mloop[p->loopstart + k].v;
837                                 
838                                 fake_loops[k].v = k;
839                                 
840                                 if (vndx == i)
841                                         copy_v3_v3(fake_co[k], center);
842                                 else
843                                         copy_v3_v3(fake_co[k], origco[vndx]);
844                         }
845                         
846                         BKE_mesh_calc_poly_normal_coords(&fake_poly, fake_loops,
847                                                          (const float(*)[3])fake_co, no);
848                         MEM_freeN(fake_loops);
849                         MEM_freeN(fake_co);
850
851                         add_v3_v3(avg_no, no);
852                 }
853                 normalize_v3(avg_no);
854
855                 /* push vertex away from the plane */
856                 dist = v3_dist_from_plane(me->mvert[i].co, center, avg_no);
857                 copy_v3_v3(push, avg_no);
858                 mul_v3_fl(push, dist);
859                 add_v3_v3(me->mvert[i].co, push);
860                 
861         }
862
863         MEM_freeN(origco);
864         cddm->release(cddm);
865
866         /* Vertices were moved around, need to update normals after all the vertices are updated
867          * Probably this is possible to do in the loop above, but this is rather tricky because
868          * we don't know all needed vertices' coordinates there yet.
869          */
870         BKE_mesh_calc_normals(me);
871
872         /* subdivide the mesh to highest level without displacements */
873         cddm = CDDM_from_mesh(me);
874         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
875         origdm = subsurf_dm_create_local(ob, cddm, totlvl, 0, 0, mmd->flags & eMultiresModifierFlag_PlainUv, 0);
876         cddm->release(cddm);
877
878         /* calc disps */
879         multiresModifier_disp_run(dispdm, me, NULL, CALC_DISPLACEMENTS, origdm->getGridData(origdm), totlvl);
880
881         origdm->release(origdm);
882         dispdm->release(dispdm);
883 }
884
885 static void multires_subdivide(MultiresModifierData *mmd, Object *ob, int totlvl, int updateblock, int simple)
886 {
887         Mesh *me = ob->data;
888         MDisps *mdisps;
889         int lvl = mmd->totlvl;
890
891         if ((totlvl > multires_max_levels) || (me->totpoly == 0))
892                 return;
893
894         multires_force_update(ob);
895
896         mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
897         if (!mdisps)
898                 mdisps = multires_mdisps_initialize_hidden(me, totlvl);
899
900         if (mdisps->disps && !updateblock && totlvl > 1) {
901                 /* upsample */
902                 DerivedMesh *lowdm, *cddm, *highdm;
903                 CCGElem **highGridData, **lowGridData, **subGridData;
904                 CCGKey highGridKey, lowGridKey;
905                 CCGSubSurf *ss;
906                 int i, numGrids, highGridSize;
907                 const bool has_mask = CustomData_has_layer(&me->ldata, CD_GRID_PAINT_MASK);
908
909                 /* create subsurf DM from original mesh at high level */
910                 cddm = CDDM_from_mesh(me);
911                 DM_set_only_copy(cddm, CD_MASK_BAREMESH);
912                 highdm = subsurf_dm_create_local(ob, cddm, totlvl, simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv, has_mask);
913                 ss = ((CCGDerivedMesh *)highdm)->ss;
914
915                 /* create multires DM from original mesh at low level */
916                 lowdm = multires_dm_create_local(ob, cddm, lvl, lvl, simple, has_mask);
917                 cddm->release(cddm);
918
919                 /* copy subsurf grids and replace them with low displaced grids */
920                 numGrids = highdm->getNumGrids(highdm);
921                 highGridSize = highdm->getGridSize(highdm);
922                 highGridData = highdm->getGridData(highdm);
923                 highdm->getGridKey(highdm, &highGridKey);
924                 lowGridData = lowdm->getGridData(lowdm);
925                 lowdm->getGridKey(lowdm, &lowGridKey);
926
927                 subGridData = MEM_callocN(sizeof(float *) * numGrids, "subGridData*");
928
929                 for (i = 0; i < numGrids; ++i) {
930                         /* backup subsurf grids */
931                         subGridData[i] = MEM_callocN(highGridKey.elem_size * highGridSize * highGridSize, "subGridData");
932                         memcpy(subGridData[i], highGridData[i], highGridKey.elem_size * highGridSize * highGridSize);
933
934                         /* overwrite with current displaced grids */
935                         multires_copy_dm_grid(highGridData[i], lowGridData[i], &highGridKey, &lowGridKey);
936                 }
937
938                 /* low lower level dm no longer needed at this point */
939                 lowdm->release(lowdm);
940
941                 /* subsurf higher levels again with displaced data */
942                 ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
943                 ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
944
945                 /* reallocate displacements */
946                 multires_reallocate_mdisps(me->totloop, mdisps, totlvl); 
947
948                 /* compute displacements */
949                 multiresModifier_disp_run(highdm, me, NULL, CALC_DISPLACEMENTS, subGridData, totlvl);
950
951                 /* free */
952                 highdm->release(highdm);
953                 for (i = 0; i < numGrids; ++i)
954                         MEM_freeN(subGridData[i]);
955                 MEM_freeN(subGridData);
956         }
957         else {
958                 /* only reallocate, nothing to upsample */
959                 multires_reallocate_mdisps(me->totloop, mdisps, totlvl); 
960         }
961
962         multires_set_tot_level(ob, mmd, totlvl);
963 }
964
965 void multiresModifier_subdivide(MultiresModifierData *mmd, Object *ob, int updateblock, int simple)
966 {
967         multires_subdivide(mmd, ob, mmd->totlvl + 1, updateblock, simple);
968 }
969
970 static void grid_tangent(const CCGKey *key, int x, int y, int axis, CCGElem *grid, float t[3])
971 {
972         if (axis == 0) {
973                 if (x == key->grid_size - 1) {
974                         if (y == key->grid_size - 1)
975                                 sub_v3_v3v3(t, CCG_grid_elem_co(key, grid, x, y - 1), CCG_grid_elem_co(key, grid, x - 1, y - 1));
976                         else
977                                 sub_v3_v3v3(t, CCG_grid_elem_co(key, grid, x, y), CCG_grid_elem_co(key, grid, x - 1, y));
978                 }
979                 else
980                         sub_v3_v3v3(t, CCG_grid_elem_co(key, grid, x + 1, y), CCG_grid_elem_co(key, grid, x, y));
981         }
982         else if (axis == 1) {
983                 if (y == key->grid_size - 1) {
984                         if (x == key->grid_size - 1)
985                                 sub_v3_v3v3(t, CCG_grid_elem_co(key, grid, x - 1, y), CCG_grid_elem_co(key, grid, x - 1, (y - 1)));
986                         else
987                                 sub_v3_v3v3(t, CCG_grid_elem_co(key, grid, x, y), CCG_grid_elem_co(key, grid, x, (y - 1)));
988                 }
989                 else
990                         sub_v3_v3v3(t, CCG_grid_elem_co(key, grid, x, (y + 1)), CCG_grid_elem_co(key, grid, x, y));
991         }
992 }
993
994 /* Construct 3x3 tangent-space matrix in 'mat' */
995 static void grid_tangent_matrix(float mat[3][3], const CCGKey *key,
996                                 int x, int y, CCGElem *grid)
997 {
998         grid_tangent(key, x, y, 0, grid, mat[0]);
999         normalize_v3(mat[0]);
1000
1001         grid_tangent(key, x, y, 1, grid, mat[1]);
1002         normalize_v3(mat[1]);
1003
1004         copy_v3_v3(mat[2], CCG_grid_elem_no(key, grid, x, y));
1005 }
1006
1007 /* XXX WARNING: subsurf elements from dm and oldGridData *must* be of the same format (size),
1008  *              because this code uses CCGKey's info from dm to access oldGridData's normals
1009  *              (through the call to grid_tangent_matrix())! */
1010 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, DerivedMesh *dm2, DispOp op, CCGElem **oldGridData, int totlvl)
1011 {
1012         CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1013         CCGElem **gridData, **subGridData;
1014         CCGKey key;
1015         MPoly *mpoly = me->mpoly;
1016         MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
1017         GridPaintMask *grid_paint_mask = NULL;
1018         int *gridOffset;
1019         int i, k, /*numGrids, */ gridSize, dGridSize, dSkip;
1020         int totloop, totpoly;
1021         
1022         /* this happens in the dm made by bmesh_mdisps_space_set */
1023         if (dm2 && CustomData_has_layer(&dm2->loopData, CD_MDISPS)) {
1024                 mpoly = CustomData_get_layer(&dm2->polyData, CD_MPOLY);
1025                 mdisps = CustomData_get_layer(&dm2->loopData, CD_MDISPS);
1026                 totloop = dm2->numLoopData;
1027                 totpoly = dm2->numPolyData;
1028         }
1029         else {
1030                 totloop = me->totloop;
1031                 totpoly = me->totpoly;
1032         }
1033         
1034         if (!mdisps) {
1035                 if (op == CALC_DISPLACEMENTS)
1036                         mdisps = CustomData_add_layer(&me->ldata, CD_MDISPS, CD_DEFAULT, NULL, me->totloop);
1037                 else
1038                         return;
1039         }
1040
1041         /*numGrids = dm->getNumGrids(dm);*/ /*UNUSED*/
1042         gridSize = dm->getGridSize(dm);
1043         gridData = dm->getGridData(dm);
1044         gridOffset = dm->getGridOffset(dm);
1045         dm->getGridKey(dm, &key);
1046         subGridData = (oldGridData) ? oldGridData : gridData;
1047
1048         dGridSize = multires_side_tot[totlvl];
1049         dSkip = (dGridSize - 1) / (gridSize - 1);
1050
1051         /* multires paint masks */
1052         if (key.has_mask)
1053                 grid_paint_mask = CustomData_get_layer(&me->ldata, CD_GRID_PAINT_MASK);
1054
1055         k = 0; /*current loop/mdisp index within the mloop array*/
1056
1057 #pragma omp parallel for private(i) if (totloop * gridSize * gridSize >= CCG_OMP_LIMIT)
1058
1059         for (i = 0; i < totpoly; ++i) {
1060                 const int numVerts = mpoly[i].totloop;
1061                 int S, x, y, gIndex = gridOffset[i];
1062
1063                 for (S = 0; S < numVerts; ++S, ++gIndex, ++k) {
1064                         GridPaintMask *gpm = grid_paint_mask ? &grid_paint_mask[gIndex] : NULL;
1065                         MDisps *mdisp = &mdisps[mpoly[i].loopstart + S];
1066                         CCGElem *grid = gridData[gIndex];
1067                         CCGElem *subgrid = subGridData[gIndex];
1068                         float (*dispgrid)[3] = NULL;
1069
1070                         /* when adding new faces in edit mode, need to allocate disps */
1071                         if (!mdisp->disps)
1072 #pragma omp critical
1073                         {
1074                                 multires_reallocate_mdisps(totloop, mdisps, totlvl);
1075                         }
1076
1077                         dispgrid = mdisp->disps;
1078
1079                         /* if needed, reallocate multires paint mask */
1080                         if (gpm && gpm->level < key.level) {
1081                                 gpm->level = key.level;
1082 #pragma omp critical
1083                                 {
1084                                         if (gpm->data)
1085                                                 MEM_freeN(gpm->data);
1086                                         gpm->data = MEM_callocN(sizeof(float) * key.grid_area, "gpm.data");
1087                                 }
1088                         }
1089
1090                         for (y = 0; y < gridSize; y++) {
1091                                 for (x = 0; x < gridSize; x++) {
1092                                         float *co = CCG_grid_elem_co(&key, grid, x, y);
1093                                         float *sco = CCG_grid_elem_co(&key, subgrid, x, y);
1094                                         float *data = dispgrid[dGridSize * y * dSkip + x * dSkip];
1095                                         float mat[3][3], disp[3], d[3], mask;
1096
1097                                         /* construct tangent space matrix */
1098                                         grid_tangent_matrix(mat, &key, x, y, subgrid);
1099
1100                                         switch (op) {
1101                                                 case APPLY_DISPLACEMENTS:
1102                                                         /* Convert displacement to object space
1103                                                          * and add to grid points */
1104                                                         mul_v3_m3v3(disp, mat, data);
1105                                                         add_v3_v3v3(co, sco, disp);
1106                                                         break;
1107                                                 case CALC_DISPLACEMENTS:
1108                                                         /* Calculate displacement between new and old
1109                                                          * grid points and convert to tangent space */
1110                                                         sub_v3_v3v3(disp, co, sco);
1111                                                         invert_m3(mat);
1112                                                         mul_v3_m3v3(data, mat, disp);
1113                                                         break;
1114                                                 case ADD_DISPLACEMENTS:
1115                                                         /* Convert subdivided displacements to tangent
1116                                                          * space and add to the original displacements */
1117                                                         invert_m3(mat);
1118                                                         mul_v3_m3v3(d, mat, co);
1119                                                         add_v3_v3(data, d);
1120                                                         break;
1121                                         }
1122
1123                                         if (gpm) {
1124                                                 switch (op) {
1125                                                         case APPLY_DISPLACEMENTS:
1126                                                                 /* Copy mask from gpm to DM */
1127                                                                 *CCG_grid_elem_mask(&key, grid, x, y) =
1128                                                                     paint_grid_paint_mask(gpm, key.level, x, y);
1129                                                                 break;
1130                                                         case CALC_DISPLACEMENTS:
1131                                                                 /* Copy mask from DM to gpm */
1132                                                                 mask = *CCG_grid_elem_mask(&key, grid, x, y);
1133                                                                 gpm->data[y * gridSize + x] = CLAMPIS(mask, 0, 1);
1134                                                                 break;
1135                                                         case ADD_DISPLACEMENTS:
1136                                                                 /* Add mask displacement to gpm */
1137                                                                 gpm->data[y * gridSize + x] +=
1138                                                                     *CCG_grid_elem_mask(&key, grid, x, y);
1139                                                                 break;
1140                                                 }
1141                                         }
1142                                 }
1143                         }
1144                 }
1145         }
1146         
1147         if (op == APPLY_DISPLACEMENTS) {
1148                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, NULL, 0);
1149                 ccgSubSurf_updateNormals(ccgdm->ss, NULL, 0);
1150         }
1151 }
1152
1153 void multires_modifier_update_mdisps(struct DerivedMesh *dm)
1154 {
1155         CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1156         Object *ob;
1157         Mesh *me;
1158         MDisps *mdisps;
1159         MultiresModifierData *mmd;
1160
1161         ob = ccgdm->multires.ob;
1162         me = ccgdm->multires.ob->data;
1163         mmd = ccgdm->multires.mmd;
1164         multires_set_tot_mdisps(me, mmd->totlvl);
1165         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
1166         mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
1167
1168         if (mdisps) {
1169                 int lvl = ccgdm->multires.lvl;
1170                 int totlvl = ccgdm->multires.totlvl;
1171                 
1172                 if (lvl < totlvl) {
1173                         DerivedMesh *lowdm, *cddm, *highdm;
1174                         CCGElem **highGridData, **lowGridData, **subGridData, **gridData, *diffGrid;
1175                         CCGKey highGridKey, lowGridKey;
1176                         CCGSubSurf *ss;
1177                         int i, j, numGrids, highGridSize, lowGridSize;
1178                         const bool has_mask = CustomData_has_layer(&me->ldata, CD_GRID_PAINT_MASK);
1179
1180                         /* create subsurf DM from original mesh at high level */
1181                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
1182                         else cddm = CDDM_from_mesh(me);
1183                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
1184
1185                         highdm = subsurf_dm_create_local(ob, cddm, totlvl, mmd->simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv, has_mask);
1186                         ss = ((CCGDerivedMesh *)highdm)->ss;
1187
1188                         /* create multires DM from original mesh and displacements */
1189                         lowdm = multires_dm_create_local(ob, cddm, lvl, totlvl, mmd->simple, has_mask);
1190                         cddm->release(cddm);
1191
1192                         /* gather grid data */
1193                         numGrids = highdm->getNumGrids(highdm);
1194                         highGridSize = highdm->getGridSize(highdm);
1195                         highGridData = highdm->getGridData(highdm);
1196                         highdm->getGridKey(highdm, &highGridKey);
1197                         lowGridSize = lowdm->getGridSize(lowdm);
1198                         lowGridData = lowdm->getGridData(lowdm);
1199                         lowdm->getGridKey(lowdm, &lowGridKey);
1200                         gridData = dm->getGridData(dm);
1201
1202                         BLI_assert(highGridKey.elem_size == lowGridKey.elem_size);
1203
1204                         subGridData = MEM_callocN(sizeof(CCGElem *) * numGrids, "subGridData*");
1205                         diffGrid = MEM_callocN(lowGridKey.elem_size * lowGridSize * lowGridSize, "diff");
1206
1207                         for (i = 0; i < numGrids; ++i) {
1208                                 /* backup subsurf grids */
1209                                 subGridData[i] = MEM_callocN(highGridKey.elem_size * highGridSize * highGridSize, "subGridData");
1210                                 memcpy(subGridData[i], highGridData[i], highGridKey.elem_size * highGridSize * highGridSize);
1211
1212                                 /* write difference of subsurf and displaced low level into high subsurf */
1213                                 for (j = 0; j < lowGridSize * lowGridSize; ++j) {
1214                                         sub_v4_v4v4(CCG_elem_offset_co(&lowGridKey, diffGrid, j),
1215                                                     CCG_elem_offset_co(&lowGridKey, gridData[i], j),
1216                                                     CCG_elem_offset_co(&lowGridKey, lowGridData[i], j));
1217                                 }
1218
1219                                 multires_copy_dm_grid(highGridData[i], diffGrid, &highGridKey, &lowGridKey);
1220                         }
1221
1222                         /* lower level dm no longer needed at this point */
1223                         MEM_freeN(diffGrid);
1224                         lowdm->release(lowdm);
1225
1226                         /* subsurf higher levels again with difference of coordinates */
1227                         ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
1228                         ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
1229
1230                         /* add to displacements */
1231                         multiresModifier_disp_run(highdm, me, NULL, ADD_DISPLACEMENTS, subGridData, mmd->totlvl);
1232
1233                         /* free */
1234                         highdm->release(highdm);
1235                         for (i = 0; i < numGrids; ++i)
1236                                 MEM_freeN(subGridData[i]);
1237                         MEM_freeN(subGridData);
1238                 }
1239                 else {
1240                         DerivedMesh *cddm, *subdm;
1241                         const bool has_mask = CustomData_has_layer(&me->ldata, CD_GRID_PAINT_MASK);
1242
1243                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
1244                         else cddm = CDDM_from_mesh(me);
1245                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
1246
1247                         subdm = subsurf_dm_create_local(ob, cddm, mmd->totlvl, mmd->simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv, has_mask);
1248                         cddm->release(cddm);
1249
1250                         multiresModifier_disp_run(dm, me, NULL, CALC_DISPLACEMENTS, subdm->getGridData(subdm), mmd->totlvl);
1251
1252                         subdm->release(subdm);
1253                 }
1254         }
1255 }
1256
1257 void multires_modifier_update_hidden(DerivedMesh *dm)
1258 {
1259         CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)dm;
1260         BLI_bitmap **grid_hidden = ccgdm->gridHidden;
1261         Mesh *me = ccgdm->multires.ob->data;
1262         MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
1263         int totlvl = ccgdm->multires.totlvl;
1264         int lvl = ccgdm->multires.lvl;
1265
1266         if (mdisps) {
1267                 int i;
1268                 
1269                 for (i = 0; i < me->totloop; i++) {
1270                         MDisps *md = &mdisps[i];
1271                         BLI_bitmap *gh = grid_hidden[i];
1272
1273                         if (!gh && md->hidden) {
1274                                 MEM_freeN(md->hidden);
1275                                 md->hidden = NULL;
1276                         }
1277                         else if (gh) {
1278                                 gh = multires_mdisps_upsample_hidden(gh, lvl, totlvl,
1279                                                                      md->hidden);
1280                                 if (md->hidden)
1281                                         MEM_freeN(md->hidden);
1282                                 
1283                                 md->hidden = gh;
1284                         }
1285                 }
1286         }
1287 }
1288
1289 void multires_set_space(DerivedMesh *dm, Object *ob, int from, int to)
1290 {
1291         DerivedMesh *ccgdm = NULL, *subsurf = NULL;
1292         CCGElem **gridData, **subGridData = NULL;
1293         CCGKey key;
1294         MPoly *mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
1295         MDisps *mdisps;
1296         MultiresModifierData *mmd = get_multires_modifier(NULL, ob, 1);
1297         int *gridOffset, totlvl;
1298         int i, k, numGrids, gridSize, dGridSize, dSkip;
1299         
1300         if (!mmd)
1301                 return;
1302         
1303         mdisps = CustomData_get_layer(&dm->loopData, CD_MDISPS);
1304
1305         if (!mdisps) {
1306                 goto cleanup;
1307         }
1308
1309         totlvl = mmd->totlvl;
1310         ccgdm = multires_dm_create_local(ob, dm, totlvl, totlvl, mmd->simple, false);
1311         
1312         subsurf = subsurf_dm_create_local(ob, dm, totlvl,
1313                                           mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges, mmd->flags & eMultiresModifierFlag_PlainUv, 0);
1314
1315         numGrids = subsurf->getNumGrids(subsurf);
1316         gridSize = subsurf->getGridSize(subsurf);
1317         gridData = subsurf->getGridData(subsurf);
1318         subsurf->getGridKey(subsurf, &key);
1319
1320         subGridData = MEM_callocN(sizeof(CCGElem *) * numGrids, "subGridData*");
1321
1322         for (i = 0; i < numGrids; i++) {
1323                 subGridData[i] = MEM_callocN(key.elem_size * gridSize * gridSize, "subGridData");
1324                 memcpy(subGridData[i], gridData[i], key.elem_size * gridSize * gridSize);
1325         }
1326         
1327         /* numGrids = ccgdm->dm->getNumGrids((DerivedMesh *)ccgdm); */ /*UNUSED*/
1328         gridSize = ccgdm->getGridSize((DerivedMesh *)ccgdm);
1329         gridData = ccgdm->getGridData((DerivedMesh *)ccgdm);
1330         gridOffset = ccgdm->getGridOffset((DerivedMesh *)ccgdm);
1331
1332         dGridSize = multires_side_tot[totlvl];
1333         dSkip = (dGridSize - 1) / (gridSize - 1);
1334
1335         k = 0; /*current loop/mdisp index within the mloop array*/
1336
1337         //#pragma omp parallel for private(i) if (dm->numLoopData * gridSize * gridSize >= CCG_OMP_LIMIT)
1338
1339         for (i = 0; i < dm->numPolyData; ++i) {
1340                 const int numVerts = mpoly[i].totloop;
1341                 int S, x, y, gIndex = gridOffset[i];
1342                                                 
1343                 for (S = 0; S < numVerts; ++S, ++gIndex, ++k) {
1344                         MDisps *mdisp = &mdisps[mpoly[i].loopstart + S];
1345                         /* CCGElem *grid = gridData[gIndex]; */ /* UNUSED */
1346                         CCGElem *subgrid = subGridData[gIndex];
1347                         float (*dispgrid)[3] = NULL;
1348
1349                         /* when adding new faces in edit mode, need to allocate disps */
1350                         if (!mdisp->disps) {
1351                                 mdisp->totdisp = gridSize * gridSize;
1352                                 mdisp->level = totlvl;
1353                                 mdisp->disps = MEM_callocN(sizeof(float) * 3 * mdisp->totdisp, "disp in multires_set_space");
1354                         }
1355
1356                         dispgrid = mdisp->disps;
1357
1358                         for (y = 0; y < gridSize; y++) {
1359                                 for (x = 0; x < gridSize; x++) {
1360                                         float *data = dispgrid[dGridSize * y * dSkip + x * dSkip];
1361                                         float *co = CCG_grid_elem_co(&key, subgrid, x, y);
1362                                         float mat[3][3], dco[3];
1363                                         
1364                                         /* construct tangent space matrix */
1365                                         grid_tangent_matrix(mat, &key, x, y, subgrid);
1366
1367                                         /* convert to absolute coordinates in space */
1368                                         if (from == MULTIRES_SPACE_TANGENT) {
1369                                                 mul_v3_m3v3(dco, mat, data);
1370                                                 add_v3_v3(dco, co);
1371                                         }
1372                                         else if (from == MULTIRES_SPACE_OBJECT) {
1373                                                 add_v3_v3v3(dco, co, data);
1374                                         }
1375                                         else if (from == MULTIRES_SPACE_ABSOLUTE) {
1376                                                 copy_v3_v3(dco, data);
1377                                         }
1378                                         
1379                                         /*now, convert to desired displacement type*/
1380                                         if (to == MULTIRES_SPACE_TANGENT) {
1381                                                 invert_m3(mat);
1382
1383                                                 sub_v3_v3(dco, co);
1384                                                 mul_v3_m3v3(data, mat, dco);
1385                                         }
1386                                         else if (to == MULTIRES_SPACE_OBJECT) {
1387                                                 sub_v3_v3(dco, co);
1388                                                 mul_v3_m3v3(data, mat, dco);
1389                                         }
1390                                         else if (to == MULTIRES_SPACE_ABSOLUTE) {
1391                                                 copy_v3_v3(data, dco);
1392                                         }
1393                                 }
1394                         }
1395                 }
1396         }
1397
1398 cleanup:
1399         if (subsurf) {
1400                 subsurf->needsFree = 1;
1401                 subsurf->release(subsurf);
1402         }
1403
1404         if (ccgdm) {
1405                 ccgdm->needsFree = 1;
1406                 ccgdm->release(ccgdm);
1407         }
1408 }
1409
1410 void multires_stitch_grids(Object *ob)
1411 {
1412         /* utility for smooth brush */
1413         if (ob && ob->derivedFinal) {
1414                 CCGDerivedMesh *ccgdm = (CCGDerivedMesh *)ob->derivedFinal;
1415                 CCGFace **faces;
1416                 int totface;
1417
1418                 if (ccgdm->pbvh) {
1419                         BKE_pbvh_get_grid_updates(ccgdm->pbvh, 0, (void ***)&faces, &totface);
1420
1421                         if (totface) {
1422                                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, faces, totface);
1423                                 MEM_freeN(faces);
1424                         }
1425                 }
1426         }
1427 }
1428
1429 DerivedMesh *multires_make_derived_from_derived(DerivedMesh *dm,
1430                                                 MultiresModifierData *mmd,
1431                                                 Object *ob,
1432                                                 MultiresFlags flags)
1433 {
1434         Mesh *me = ob->data;
1435         DerivedMesh *result;
1436         CCGDerivedMesh *ccgdm = NULL;
1437         CCGElem **gridData, **subGridData;
1438         CCGKey key;
1439         const bool render = (flags & MULTIRES_USE_RENDER_PARAMS) != 0;
1440         const bool ignore_simplify = (flags & MULTIRES_IGNORE_SIMPLIFY) != 0;
1441         int lvl = multires_get_level(ob, mmd, render, ignore_simplify);
1442         int i, gridSize, numGrids;
1443
1444         if (lvl == 0)
1445                 return dm;
1446
1447         result = subsurf_dm_create_local(ob, dm, lvl,
1448                                          mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges,
1449                                          mmd->flags & eMultiresModifierFlag_PlainUv,
1450                                          flags & MULTIRES_ALLOC_PAINT_MASK);
1451
1452         if (!(flags & MULTIRES_USE_LOCAL_MMD)) {
1453                 ccgdm = (CCGDerivedMesh *)result;
1454
1455                 ccgdm->multires.ob = ob;
1456                 ccgdm->multires.mmd = mmd;
1457                 ccgdm->multires.local_mmd = 0;
1458                 ccgdm->multires.lvl = lvl;
1459                 ccgdm->multires.totlvl = mmd->totlvl;
1460                 ccgdm->multires.modified_flags = 0;
1461         }
1462
1463         numGrids = result->getNumGrids(result);
1464         gridSize = result->getGridSize(result);
1465         gridData = result->getGridData(result);
1466         result->getGridKey(result, &key);
1467
1468         subGridData = MEM_callocN(sizeof(CCGElem *) * numGrids, "subGridData*");
1469
1470         for (i = 0; i < numGrids; i++) {
1471                 subGridData[i] = MEM_callocN(key.elem_size * gridSize * gridSize, "subGridData");
1472                 memcpy(subGridData[i], gridData[i], key.elem_size * gridSize * gridSize);
1473         }
1474
1475         multires_set_tot_mdisps(me, mmd->totlvl);
1476         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
1477
1478         /*run displacement*/
1479         multiresModifier_disp_run(result, ob->data, dm, APPLY_DISPLACEMENTS, subGridData, mmd->totlvl);
1480
1481         /* copy hidden elements for this level */
1482         if (ccgdm)
1483                 multires_output_hidden_to_ccgdm(ccgdm, me, lvl);
1484
1485         for (i = 0; i < numGrids; i++)
1486                 MEM_freeN(subGridData[i]);
1487         MEM_freeN(subGridData);
1488
1489         return result;
1490 }
1491
1492 /**** Old Multires code ****
1493  ***************************/
1494
1495 /* Adapted from sculptmode.c */
1496 void old_mdisps_bilinear(float out[3], float (*disps)[3], const int st, float u, float v)
1497 {
1498         int x, y, x2, y2;
1499         const int st_max = st - 1;
1500         float urat, vrat, uopp;
1501         float d[4][3], d2[2][3];
1502         
1503         if (!disps || isnan(u) || isnan(v))
1504                 return;
1505                         
1506         if (u < 0)
1507                 u = 0;
1508         else if (u >= st)
1509                 u = st_max;
1510         if (v < 0)
1511                 v = 0;
1512         else if (v >= st)
1513                 v = st_max;
1514
1515         x = floor(u);
1516         y = floor(v);
1517         x2 = x + 1;
1518         y2 = y + 1;
1519
1520         if (x2 >= st) x2 = st_max;
1521         if (y2 >= st) y2 = st_max;
1522         
1523         urat = u - x;
1524         vrat = v - y;
1525         uopp = 1 - urat;
1526
1527         mul_v3_v3fl(d[0], disps[y * st + x], uopp);
1528         mul_v3_v3fl(d[1], disps[y * st + x2], urat);
1529         mul_v3_v3fl(d[2], disps[y2 * st + x], uopp);
1530         mul_v3_v3fl(d[3], disps[y2 * st + x2], urat);
1531
1532         add_v3_v3v3(d2[0], d[0], d[1]);
1533         add_v3_v3v3(d2[1], d[2], d[3]);
1534         mul_v3_fl(d2[0], 1 - vrat);
1535         mul_v3_fl(d2[1], vrat);
1536
1537         add_v3_v3v3(out, d2[0], d2[1]);
1538 }
1539
1540 static void old_mdisps_rotate(int S, int UNUSED(newside), int oldside, int x, int y, float *u, float *v)
1541 {
1542         float offset = oldside * 0.5f - 0.5f;
1543
1544         if (S == 1) { *u = offset + x; *v = offset - y; }
1545         if (S == 2) { *u = offset + y; *v = offset + x; }
1546         if (S == 3) { *u = offset - x; *v = offset + y; }
1547         if (S == 0) { *u = offset - y; *v = offset - x; }
1548 }
1549
1550 static void old_mdisps_convert(MFace *mface, MDisps *mdisp)
1551 {
1552         int newlvl = log(sqrt(mdisp->totdisp) - 1) / M_LN2;
1553         int oldlvl = newlvl + 1;
1554         int oldside = multires_side_tot[oldlvl];
1555         int newside = multires_side_tot[newlvl];
1556         int nvert = (mface->v4) ? 4 : 3;
1557         int newtotdisp = multires_grid_tot[newlvl] * nvert;
1558         int x, y, S;
1559         float (*disps)[3], (*out)[3], u = 0.0f, v = 0.0f; /* Quite gcc barking. */
1560
1561         disps = MEM_callocN(sizeof(float) * 3 * newtotdisp, "multires disps");
1562
1563         out = disps;
1564         for (S = 0; S < nvert; S++) {
1565                 for (y = 0; y < newside; ++y) {
1566                         for (x = 0; x < newside; ++x, ++out) {
1567                                 old_mdisps_rotate(S, newside, oldside, x, y, &u, &v);
1568                                 old_mdisps_bilinear(*out, mdisp->disps, oldside, u, v);
1569
1570                                 if (S == 1) { (*out)[1] = -(*out)[1]; }
1571                                 else if (S == 2) { SWAP(float, (*out)[0], (*out)[1]); }
1572                                 else if (S == 3) { (*out)[0] = -(*out)[0]; }
1573                                 else if (S == 0) { SWAP(float, (*out)[0], (*out)[1]); (*out)[0] = -(*out)[0]; (*out)[1] = -(*out)[1]; }
1574                         }
1575                 }
1576         }
1577
1578         MEM_freeN(mdisp->disps);
1579
1580         mdisp->totdisp = newtotdisp;
1581         mdisp->level = newlvl;
1582         mdisp->disps = disps;
1583 }
1584
1585 void multires_load_old_250(Mesh *me)
1586 {
1587         MDisps *mdisps, *mdisps2;
1588         MFace *mf;
1589         int i, j, k;
1590
1591         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
1592
1593         if (mdisps) {
1594                 for (i = 0; i < me->totface; i++)
1595                         if (mdisps[i].totdisp)
1596                                 old_mdisps_convert(&me->mface[i], &mdisps[i]);
1597                 
1598                 CustomData_add_layer(&me->ldata, CD_MDISPS, CD_CALLOC, NULL, me->totloop);
1599                 mdisps2 = CustomData_get_layer(&me->ldata, CD_MDISPS);
1600
1601                 k = 0;
1602                 mf = me->mface;
1603                 for (i = 0; i < me->totface; i++, mf++) {
1604                         int nvert = mf->v4 ? 4 : 3;
1605                         int totdisp = mdisps[i].totdisp / nvert;
1606                         
1607                         for (j = 0; j < mf->v4 ? 4 : 3; j++, k++) {
1608                                 mdisps2[k].disps = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disp in conversion");
1609                                 mdisps2[k].totdisp = totdisp;
1610                                 mdisps2[k].level = mdisps[i].level;
1611                                 memcpy(mdisps2[k].disps, mdisps[i].disps + totdisp * j, totdisp);
1612                         }
1613
1614                 }
1615         }
1616 }
1617
1618 /* Does not actually free lvl itself */
1619 static void multires_free_level(MultiresLevel *lvl)
1620 {
1621         if (lvl) {
1622                 if (lvl->faces) MEM_freeN(lvl->faces);
1623                 if (lvl->edges) MEM_freeN(lvl->edges);
1624                 if (lvl->colfaces) MEM_freeN(lvl->colfaces);
1625         }
1626 }
1627
1628 void multires_free(Multires *mr)
1629 {
1630         if (mr) {
1631                 MultiresLevel *lvl = mr->levels.first;
1632
1633                 /* Free the first-level data */
1634                 if (lvl) {
1635                         CustomData_free(&mr->vdata, lvl->totvert);
1636                         CustomData_free(&mr->fdata, lvl->totface);
1637                         if (mr->edge_flags)
1638                                 MEM_freeN(mr->edge_flags);
1639                         if (mr->edge_creases)
1640                                 MEM_freeN(mr->edge_creases);
1641                 }
1642
1643                 while (lvl) {
1644                         multires_free_level(lvl);
1645                         lvl = lvl->next;
1646                 }
1647
1648                 MEM_freeN(mr->verts);
1649
1650                 BLI_freelistN(&mr->levels);
1651
1652                 MEM_freeN(mr);
1653         }
1654 }
1655
1656 typedef struct IndexNode {
1657         struct IndexNode *next, *prev;
1658         int index;
1659 } IndexNode;
1660
1661 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
1662                                      const int totvert, const int totface)
1663 {
1664         int i, j;
1665         IndexNode *node = NULL;
1666         
1667         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
1668         (*mem) = MEM_callocN(sizeof(IndexNode) * totface * 4, "vert face map mem");
1669         node = *mem;
1670         
1671         /* Find the users */
1672         for (i = 0; i < totface; ++i) {
1673                 for (j = 0; j < (mface[i].v[3] ? 4 : 3); ++j, ++node) {
1674                         node->index = i;
1675                         BLI_addtail(&(*map)[mface[i].v[j]], node);
1676                 }
1677         }
1678 }
1679
1680 static void create_old_vert_edge_map(ListBase **map, IndexNode **mem, const MultiresEdge *medge,
1681                                      const int totvert, const int totedge)
1682 {
1683         int i, j;
1684         IndexNode *node = NULL;
1685         
1686         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
1687         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge * 2, "vert edge map mem");
1688         node = *mem;
1689         
1690         /* Find the users */
1691         for (i = 0; i < totedge; ++i) {
1692                 for (j = 0; j < 2; ++j, ++node) {
1693                         node->index = i;
1694                         BLI_addtail(&(*map)[medge[i].v[j]], node);
1695                 }
1696         }
1697 }
1698
1699 static MultiresFace *find_old_face(ListBase *map, MultiresFace *faces, int v1, int v2, int v3, int v4)
1700 {
1701         IndexNode *n1;
1702         int v[4], i, j;
1703
1704         v[0] = v1;
1705         v[1] = v2;
1706         v[2] = v3;
1707         v[3] = v4;
1708
1709         for (n1 = map[v1].first; n1; n1 = n1->next) {
1710                 int fnd[4] = {0, 0, 0, 0};
1711
1712                 for (i = 0; i < 4; ++i) {
1713                         for (j = 0; j < 4; ++j) {
1714                                 if (v[i] == faces[n1->index].v[j])
1715                                         fnd[i] = 1;
1716                         }
1717                 }
1718
1719                 if (fnd[0] && fnd[1] && fnd[2] && fnd[3])
1720                         return &faces[n1->index];
1721         }
1722
1723         return NULL;
1724 }
1725
1726 static MultiresEdge *find_old_edge(ListBase *map, MultiresEdge *edges, int v1, int v2)
1727 {
1728         IndexNode *n1, *n2;
1729
1730         for (n1 = map[v1].first; n1; n1 = n1->next) {
1731                 for (n2 = map[v2].first; n2; n2 = n2->next) {
1732                         if (n1->index == n2->index)
1733                                 return &edges[n1->index];
1734                 }
1735         }
1736
1737         return NULL;
1738 }
1739
1740 static void multires_load_old_edges(ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst, int v1, int v2, int mov)
1741 {
1742         int emid = find_old_edge(emap[2], lvl->edges, v1, v2)->mid;
1743         vvmap[dst + mov] = emid;
1744
1745         if (lvl->next->next) {
1746                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v1, emid, mov / 2);
1747                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v2, emid, -mov / 2);
1748         }
1749 }
1750
1751 static void multires_load_old_faces(ListBase **fmap, ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst,
1752                                     int v1, int v2, int v3, int v4, int st2, int st3)
1753 {
1754         int fmid;
1755         int emid13, emid14, emid23, emid24;
1756
1757         if (lvl && lvl->next) {
1758                 fmid = find_old_face(fmap[1], lvl->faces, v1, v2, v3, v4)->mid;
1759                 vvmap[dst] = fmid;
1760
1761                 emid13 = find_old_edge(emap[1], lvl->edges, v1, v3)->mid;
1762                 emid14 = find_old_edge(emap[1], lvl->edges, v1, v4)->mid;
1763                 emid23 = find_old_edge(emap[1], lvl->edges, v2, v3)->mid;
1764                 emid24 = find_old_edge(emap[1], lvl->edges, v2, v4)->mid;
1765
1766
1767                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 + st3,
1768                                         fmid, v2, emid23, emid24, st2, st3 / 2);
1769
1770                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 + st3,
1771                                         emid14, emid24, fmid, v4, st2, st3 / 2);
1772
1773                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 - st3,
1774                                         emid13, emid23, v3, fmid, st2, st3 / 2);
1775
1776                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 - st3,
1777                                         v1, fmid, emid13, emid14, st2, st3 / 2);
1778
1779                 if (lvl->next->next) {
1780                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid24, fmid, st3);
1781                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid13, fmid, -st3);
1782                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid14, fmid, -st2 * st3);
1783                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid23, fmid, st2 * st3);
1784                 }
1785         }
1786 }
1787
1788 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert)
1789 {
1790         CCGDerivedMesh *ccgdm = (CCGDerivedMesh *) dm;
1791         CCGSubSurf *ss = ccgdm->ss;
1792         CCGElem *vd;
1793         CCGKey key;
1794         int index;
1795         int totvert, totedge, totface;
1796         int gridSize = ccgSubSurf_getGridSize(ss);
1797         int edgeSize = ccgSubSurf_getEdgeSize(ss);
1798         int i = 0;
1799
1800         dm->getGridKey(dm, &key);
1801
1802         totface = ccgSubSurf_getNumFaces(ss);
1803         for (index = 0; index < totface; index++) {
1804                 CCGFace *f = ccgdm->faceMap[index].face;
1805                 int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1806
1807                 vd = ccgSubSurf_getFaceCenterData(f);
1808                 copy_v3_v3(CCG_elem_co(&key, vd), mvert[i].co);
1809                 i++;
1810                 
1811                 for (S = 0; S < numVerts; S++) {
1812                         for (x = 1; x < gridSize - 1; x++, i++) {
1813                                 vd = ccgSubSurf_getFaceGridEdgeData(ss, f, S, x);
1814                                 copy_v3_v3(CCG_elem_co(&key, vd), mvert[i].co);
1815                         }
1816                 }
1817
1818                 for (S = 0; S < numVerts; S++) {
1819                         for (y = 1; y < gridSize - 1; y++) {
1820                                 for (x = 1; x < gridSize - 1; x++, i++) {
1821                                         vd = ccgSubSurf_getFaceGridData(ss, f, S, x, y);
1822                                         copy_v3_v3(CCG_elem_co(&key, vd), mvert[i].co);
1823                                 }
1824                         }
1825                 }
1826         }
1827
1828         totedge = ccgSubSurf_getNumEdges(ss);
1829         for (index = 0; index < totedge; index++) {
1830                 CCGEdge *e = ccgdm->edgeMap[index].edge;
1831                 int x;
1832
1833                 for (x = 1; x < edgeSize - 1; x++, i++) {
1834                         vd = ccgSubSurf_getEdgeData(ss, e, x);
1835                         copy_v3_v3(CCG_elem_co(&key, vd), mvert[i].co);
1836                 }
1837         }
1838
1839         totvert = ccgSubSurf_getNumVerts(ss);
1840         for (index = 0; index < totvert; index++) {
1841                 CCGVert *v = ccgdm->vertMap[index].vert;
1842
1843                 vd = ccgSubSurf_getVertData(ss, v);
1844                 copy_v3_v3(CCG_elem_co(&key, vd), mvert[i].co);
1845                 i++;
1846         }
1847
1848         ccgSubSurf_updateToFaces(ss, 0, NULL, 0);
1849 }
1850
1851 /* Loads a multires object stored in the old Multires struct into the new format */
1852 static void multires_load_old_dm(DerivedMesh *dm, Mesh *me, int totlvl)
1853 {
1854         MultiresLevel *lvl, *lvl1;
1855         Multires *mr = me->mr;
1856         MVert *vsrc, *vdst;
1857         unsigned int src, dst;
1858         int st = multires_side_tot[totlvl - 1] - 1;
1859         int extedgelen = multires_side_tot[totlvl] - 2;
1860         int *vvmap; // inorder for dst, map to src
1861         int crossedgelen;
1862         int s, x, tottri, totquad;
1863         unsigned int i, j, totvert;
1864
1865         src = 0;
1866         vsrc = mr->verts;
1867         vdst = dm->getVertArray(dm);
1868         totvert = (unsigned int)dm->getNumVerts(dm);
1869         vvmap = MEM_callocN(sizeof(int) * totvert, "multires vvmap");
1870
1871         lvl1 = mr->levels.first;
1872         /* Load base verts */
1873         for (i = 0; i < lvl1->totvert; ++i) {
1874                 vvmap[totvert - lvl1->totvert + i] = src;
1875                 src++;
1876         }
1877
1878         /* Original edges */
1879         dst = totvert - lvl1->totvert - extedgelen * lvl1->totedge;
1880         for (i = 0; i < lvl1->totedge; ++i) {
1881                 int ldst = dst + extedgelen * i;
1882                 int lsrc = src;
1883                 lvl = lvl1->next;
1884
1885                 for (j = 2; j <= mr->level_count; ++j) {
1886                         int base = multires_side_tot[totlvl - j + 1] - 2;
1887                         int skip = multires_side_tot[totlvl - j + 2] - 1;
1888                         int st = multires_side_tot[j - 1] - 1;
1889
1890                         for (x = 0; x < st; ++x)
1891                                 vvmap[ldst + base + x * skip] = lsrc + st * i + x;
1892
1893                         lsrc += lvl->totvert - lvl->prev->totvert;
1894                         lvl = lvl->next;
1895                 }
1896         }
1897
1898         /* Center points */
1899         dst = 0;
1900         for (i = 0; i < lvl1->totface; ++i) {
1901                 int sides = lvl1->faces[i].v[3] ? 4 : 3;
1902
1903                 vvmap[dst] = src + lvl1->totedge + i;
1904                 dst += 1 + sides * (st - 1) * st;
1905         }
1906
1907
1908         /* The rest is only for level 3 and up */
1909         if (lvl1->next && lvl1->next->next) {
1910                 ListBase **fmap, **emap;
1911                 IndexNode **fmem, **emem;
1912
1913                 /* Face edge cross */
1914                 tottri = totquad = 0;
1915                 crossedgelen = multires_side_tot[totlvl - 1] - 2;
1916                 dst = 0;
1917                 for (i = 0; i < lvl1->totface; ++i) {
1918                         int sides = lvl1->faces[i].v[3] ? 4 : 3;
1919
1920                         lvl = lvl1->next->next;
1921                         dst++;
1922
1923                         for (j = 3; j <= mr->level_count; ++j) {
1924                                 int base = multires_side_tot[totlvl - j + 1] - 2;
1925                                 int skip = multires_side_tot[totlvl - j + 2] - 1;
1926                                 int st = pow(2, j - 2);
1927                                 int st2 = pow(2, j - 3);
1928                                 int lsrc = lvl->prev->totvert;
1929
1930                                 /* Skip exterior edge verts */
1931                                 lsrc += lvl1->totedge * st;
1932
1933                                 /* Skip earlier face edge crosses */
1934                                 lsrc += st2 * (tottri * 3 + totquad * 4);
1935
1936                                 for (s = 0; s < sides; ++s) {
1937                                         for (x = 0; x < st2; ++x) {
1938                                                 vvmap[dst + crossedgelen * (s + 1) - base - x * skip - 1] = lsrc;
1939                                                 lsrc++;
1940                                         }
1941                                 }
1942
1943                                 lvl = lvl->next;
1944                         }
1945
1946                         dst += sides * (st - 1) * st;
1947
1948                         if (sides == 4) ++totquad;
1949                         else ++tottri;
1950
1951                 }
1952
1953                 /* calculate vert to edge/face maps for each level (except the last) */
1954                 fmap = MEM_callocN(sizeof(ListBase *) * (mr->level_count - 1), "multires fmap");
1955                 emap = MEM_callocN(sizeof(ListBase *) * (mr->level_count - 1), "multires emap");
1956                 fmem = MEM_callocN(sizeof(IndexNode *) * (mr->level_count - 1), "multires fmem");
1957                 emem = MEM_callocN(sizeof(IndexNode *) * (mr->level_count - 1), "multires emem");
1958                 lvl = lvl1;
1959                 for (i = 0; i < (unsigned int)mr->level_count - 1; ++i) {
1960                         create_old_vert_face_map(fmap + i, fmem + i, lvl->faces, lvl->totvert, lvl->totface);
1961                         create_old_vert_edge_map(emap + i, emem + i, lvl->edges, lvl->totvert, lvl->totedge);
1962                         lvl = lvl->next;
1963                 }
1964
1965                 /* Interior face verts */
1966                 /* lvl = lvl1->next->next; */ /* UNUSED */
1967                 dst = 0;
1968                 for (j = 0; j < lvl1->totface; ++j) {
1969                         int sides = lvl1->faces[j].v[3] ? 4 : 3;
1970                         int ldst = dst + 1 + sides * (st - 1);
1971
1972                         for (s = 0; s < sides; ++s) {
1973                                 int st2 = multires_side_tot[totlvl - 1] - 2;
1974                                 int st3 = multires_side_tot[totlvl - 2] - 2;
1975                                 int st4 = st3 == 0 ? 1 : (st3 + 1) / 2;
1976                                 int mid = ldst + st2 * st3 + st3;
1977                                 int cv = lvl1->faces[j].v[s];
1978                                 int nv = lvl1->faces[j].v[s == sides - 1 ? 0 : s + 1];
1979                                 int pv = lvl1->faces[j].v[s == 0 ? sides - 1 : s - 1];
1980
1981                                 multires_load_old_faces(fmap, emap, lvl1->next, vvmap, mid,
1982                                                         vvmap[dst], cv,
1983                                                         find_old_edge(emap[0], lvl1->edges, pv, cv)->mid,
1984                                                         find_old_edge(emap[0], lvl1->edges, cv, nv)->mid,
1985                                                         st2, st4);
1986
1987                                 ldst += (st - 1) * (st - 1);
1988                         }
1989
1990
1991                         dst = ldst;
1992                 }
1993
1994                 /*lvl = lvl->next;*/ /*UNUSED*/
1995
1996                 for (i = 0; i < (unsigned int)(mr->level_count - 1); ++i) {
1997                         MEM_freeN(fmap[i]);
1998                         MEM_freeN(fmem[i]);
1999                         MEM_freeN(emap[i]);
2000                         MEM_freeN(emem[i]);
2001                 }
2002
2003                 MEM_freeN(fmap);
2004                 MEM_freeN(emap);
2005                 MEM_freeN(fmem);
2006                 MEM_freeN(emem);
2007         }
2008
2009         /* Transfer verts */
2010         for (i = 0; i < totvert; ++i)
2011                 copy_v3_v3(vdst[i].co, vsrc[vvmap[i]].co);
2012
2013         MEM_freeN(vvmap);
2014
2015         multires_mvert_to_ss(dm, vdst);
2016 }
2017
2018 /* Copy the first-level vcol data to the mesh, if it exists */
2019 /* Warning: higher-level vcol data will be lost */
2020 static void multires_load_old_vcols(Mesh *me)
2021 {
2022         MultiresLevel *lvl;
2023         MultiresColFace *colface;
2024         MCol *mcol;
2025         int i, j;
2026
2027         if (!(lvl = me->mr->levels.first))
2028                 return;
2029
2030         if (!(colface = lvl->colfaces))
2031                 return;
2032
2033         /* older multires format never supported multiple vcol layers,
2034          * so we can assume the active vcol layer is the correct one */
2035         if (!(mcol = CustomData_get_layer(&me->fdata, CD_MCOL)))
2036                 return;
2037         
2038         for (i = 0; i < me->totface; ++i) {
2039                 for (j = 0; j < 4; ++j) {
2040                         mcol[i * 4 + j].a = colface[i].col[j].a;
2041                         mcol[i * 4 + j].r = colface[i].col[j].r;
2042                         mcol[i * 4 + j].g = colface[i].col[j].g;
2043                         mcol[i * 4 + j].b = colface[i].col[j].b;
2044                 }
2045         }
2046 }
2047
2048 /* Copy the first-level face-flag data to the mesh */
2049 static void multires_load_old_face_flags(Mesh *me)
2050 {
2051         MultiresLevel *lvl;
2052         MultiresFace *faces;
2053         int i;
2054
2055         if (!(lvl = me->mr->levels.first))
2056                 return;
2057
2058         if (!(faces = lvl->faces))
2059                 return;
2060
2061         for (i = 0; i < me->totface; ++i)
2062                 me->mface[i].flag = faces[i].flag;
2063 }
2064
2065 void multires_load_old(Object *ob, Mesh *me)
2066 {
2067         MultiresLevel *lvl;
2068         ModifierData *md;
2069         MultiresModifierData *mmd;
2070         DerivedMesh *dm, *orig;
2071         CustomDataLayer *l;
2072         int i;
2073
2074         /* Load original level into the mesh */
2075         lvl = me->mr->levels.first;
2076         CustomData_free_layers(&me->vdata, CD_MVERT, lvl->totvert);
2077         CustomData_free_layers(&me->edata, CD_MEDGE, lvl->totedge);
2078         CustomData_free_layers(&me->fdata, CD_MFACE, lvl->totface);
2079         me->totvert = lvl->totvert;
2080         me->totedge = lvl->totedge;
2081         me->totface = lvl->totface;
2082         me->mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
2083         me->medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
2084         me->mface = CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
2085         memcpy(me->mvert, me->mr->verts, sizeof(MVert) * me->totvert);
2086         for (i = 0; i < me->totedge; ++i) {
2087                 me->medge[i].v1 = lvl->edges[i].v[0];
2088                 me->medge[i].v2 = lvl->edges[i].v[1];
2089         }
2090         for (i = 0; i < me->totface; ++i) {
2091                 me->mface[i].v1 = lvl->faces[i].v[0];
2092                 me->mface[i].v2 = lvl->faces[i].v[1];
2093                 me->mface[i].v3 = lvl->faces[i].v[2];
2094                 me->mface[i].v4 = lvl->faces[i].v[3];
2095                 me->mface[i].mat_nr = lvl->faces[i].mat_nr;
2096         }
2097
2098         /* Copy the first-level data to the mesh */
2099         /* XXX We must do this before converting tessfaces to polys/lopps! */
2100         for (i = 0, l = me->mr->vdata.layers; i < me->mr->vdata.totlayer; ++i, ++l)
2101                 CustomData_add_layer(&me->vdata, l->type, CD_REFERENCE, l->data, me->totvert);
2102         for (i = 0, l = me->mr->fdata.layers; i < me->mr->fdata.totlayer; ++i, ++l)
2103                 CustomData_add_layer(&me->fdata, l->type, CD_REFERENCE, l->data, me->totface);
2104         CustomData_reset(&me->mr->vdata);
2105         CustomData_reset(&me->mr->fdata);
2106
2107         multires_load_old_vcols(me);
2108         multires_load_old_face_flags(me);
2109
2110         /* multiresModifier_subdivide (actually, multires_subdivide) expects polys, not tessfaces! */
2111         BKE_mesh_convert_mfaces_to_mpolys(me);
2112
2113         /* Add a multires modifier to the object */
2114         md = ob->modifiers.first;
2115         while (md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
2116                 md = md->next;                          
2117         mmd = (MultiresModifierData *)modifier_new(eModifierType_Multires);
2118         BLI_insertlinkbefore(&ob->modifiers, md, mmd);
2119
2120         for (i = 0; i < me->mr->level_count - 1; ++i)
2121                 multiresModifier_subdivide(mmd, ob, 1, 0);
2122
2123         mmd->lvl = mmd->totlvl;
2124         orig = CDDM_from_mesh(me);
2125         /* XXX We *must* alloc paint mask here, else we have some kind of mismatch in
2126          *     multires_modifier_update_mdisps() (called by dm->release(dm)), which always creates the
2127          *     reference subsurfed dm with this option, before calling multiresModifier_disp_run(),
2128          *     which implicitly expects both subsurfs from its first dm and oldGridData parameters to
2129          *     be of the same "format"! */
2130         dm = multires_make_derived_from_derived(orig, mmd, ob, 0);
2131
2132         multires_load_old_dm(dm, me, mmd->totlvl + 1);
2133
2134         multires_dm_mark_as_modified(dm, MULTIRES_COORDS_MODIFIED);
2135         dm->release(dm);
2136         orig->release(orig);
2137
2138         /* Remove the old multires */
2139         multires_free(me->mr);
2140         me->mr = NULL;
2141 }
2142
2143 /* If 'ob' and 'to_ob' both have multires modifiers, synchronize them
2144  * such that 'ob' has the same total number of levels as 'to_ob'. */
2145 static void multires_sync_levels(Scene *scene, Object *ob, Object *to_ob)
2146 {
2147         MultiresModifierData *mmd = get_multires_modifier(scene, ob, 1);
2148         MultiresModifierData *to_mmd = get_multires_modifier(scene, to_ob, 1);
2149
2150         if (!mmd) {
2151                 /* object could have MDISP even when there is no multires modifier
2152                  * this could lead to troubles due to i've got no idea how mdisp could be
2153                  * upsampled correct without modifier data.
2154                  * just remove mdisps if no multires present (nazgul) */
2155
2156                 multires_customdata_delete(ob->data);
2157         }
2158
2159         if (mmd && to_mmd) {
2160                 if (mmd->totlvl > to_mmd->totlvl)
2161                         multires_del_higher(mmd, ob, to_mmd->totlvl);
2162                 else
2163                         multires_subdivide(mmd, ob, to_mmd->totlvl, 0, mmd->simple);
2164         }
2165 }
2166
2167 static void multires_apply_smat(Scene *scene, Object *ob, float smat[3][3])
2168 {
2169         DerivedMesh *dm = NULL, *cddm = NULL, *subdm = NULL;
2170         CCGElem **gridData, **subGridData;
2171         CCGKey dm_key, subdm_key;
2172         Mesh *me = (Mesh *)ob->data;
2173         MPoly *mpoly = me->mpoly;
2174         /* MLoop *mloop = me->mloop; */ /* UNUSED */
2175         MDisps *mdisps;
2176         int *gridOffset;
2177         int i, /*numGrids, */ gridSize, dGridSize, dSkip, totvert;
2178         float (*vertCos)[3] = NULL;
2179         MultiresModifierData *mmd = get_multires_modifier(scene, ob, 1);
2180         MultiresModifierData high_mmd;
2181
2182         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
2183         mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
2184
2185         if (!mdisps || !mmd || !mmd->totlvl) return;
2186
2187         /* we need derived mesh created from highest resolution */
2188         high_mmd = *mmd;
2189         high_mmd.lvl = high_mmd.totlvl;
2190
2191         /* unscaled multires with applied displacement */
2192         subdm = get_multires_dm(scene, &high_mmd, ob);
2193
2194         /* prepare scaled CDDM to create ccgDN */
2195         cddm = mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
2196
2197         totvert = cddm->getNumVerts(cddm);
2198         vertCos = MEM_mallocN(sizeof(*vertCos) * totvert, "multiresScale vertCos");
2199         cddm->getVertCos(cddm, vertCos);
2200         for (i = 0; i < totvert; i++)
2201                 mul_m3_v3(smat, vertCos[i]);
2202         CDDM_apply_vert_coords(cddm, vertCos);
2203         MEM_freeN(vertCos);
2204
2205         /* scaled ccgDM for tangent space of object with applied scale */
2206         dm = subsurf_dm_create_local(ob, cddm, high_mmd.totlvl, high_mmd.simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv, 0);
2207         cddm->release(cddm);
2208
2209         gridSize = dm->getGridSize(dm);
2210         gridData = dm->getGridData(dm);
2211         gridOffset = dm->getGridOffset(dm);
2212         dm->getGridKey(dm, &dm_key);
2213         subGridData = subdm->getGridData(subdm);
2214         subdm->getGridKey(subdm, &subdm_key);
2215
2216         dGridSize = multires_side_tot[high_mmd.totlvl];
2217         dSkip = (dGridSize - 1) / (gridSize - 1);
2218
2219 #pragma omp parallel for private(i) if (me->totface * gridSize * gridSize * 4 >= CCG_OMP_LIMIT)
2220         for (i = 0; i < me->totpoly; ++i) {
2221                 const int numVerts = mpoly[i].totloop;
2222                 MDisps *mdisp = &mdisps[mpoly[i].loopstart];
2223                 int S, x, y, gIndex = gridOffset[i];
2224
2225                 for (S = 0; S < numVerts; ++S, ++gIndex, mdisp++) {
2226                         CCGElem *grid = gridData[gIndex];
2227                         CCGElem *subgrid = subGridData[gIndex];
2228                         float (*dispgrid)[3] = mdisp->disps;
2229
2230                         for (y = 0; y < gridSize; y++) {
2231                                 for (x = 0; x < gridSize; x++) {
2232                                         float *co = CCG_grid_elem_co(&dm_key, grid, x, y);
2233                                         float *sco = CCG_grid_elem_co(&subdm_key, subgrid, x, y);
2234                                         float *data = dispgrid[dGridSize * y * dSkip + x * dSkip];
2235                                         float mat[3][3], disp[3];
2236
2237                                         /* construct tangent space matrix */
2238                                         grid_tangent_matrix(mat, &dm_key, x, y, grid);
2239
2240                                         /* scale subgrid coord and calculate displacement */
2241                                         mul_m3_v3(smat, sco);
2242                                         sub_v3_v3v3(disp, sco, co);
2243
2244                                         /* convert difference to tangent space */
2245                                         invert_m3(mat);
2246                                         mul_v3_m3v3(data, mat, disp);
2247                                 }
2248                         }
2249                 }
2250         }
2251
2252         dm->release(dm);
2253         subdm->release(subdm);
2254 }
2255
2256 int multires_mdisp_corners(MDisps *s)
2257 {
2258         int lvl = 13;
2259
2260         while (lvl > 0) {
2261                 int side = (1 << (lvl - 1)) + 1;
2262                 if ((s->totdisp % (side * side)) == 0) return s->totdisp / (side * side);
2263                 lvl--;
2264         }
2265
2266         return 0;
2267 }
2268
2269 void multiresModifier_scale_disp(Scene *scene, Object *ob)
2270 {
2271         float smat[3][3];
2272
2273         /* object's scale matrix */
2274         BKE_object_scale_to_mat3(ob, smat);
2275
2276         multires_apply_smat(scene, ob, smat);
2277 }
2278
2279 void multiresModifier_prepare_join(Scene *scene, Object *ob, Object *to_ob)
2280 {
2281         float smat[3][3], tmat[3][3], mat[3][3];
2282         multires_sync_levels(scene, ob, to_ob);
2283
2284         /* construct scale matrix for displacement */
2285         BKE_object_scale_to_mat3(to_ob, tmat);
2286         invert_m3(tmat);
2287         BKE_object_scale_to_mat3(ob, smat);
2288         mul_m3_m3m3(mat, smat, tmat);
2289
2290         multires_apply_smat(scene, ob, mat);
2291 }
2292
2293 /* update multires data after topology changing */
2294 void multires_topology_changed(Mesh *me)
2295 {
2296         MDisps *mdisp = NULL, *cur = NULL;
2297         int i, grid = 0;
2298
2299         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
2300         mdisp = CustomData_get_layer(&me->ldata, CD_MDISPS);
2301
2302         if (!mdisp)
2303                 return;
2304
2305         cur = mdisp;
2306         for (i = 0; i < me->totloop; i++, cur++) {
2307                 if (cur->totdisp) {
2308                         grid = mdisp->totdisp;
2309
2310                         break;
2311                 }
2312         }
2313
2314         for (i = 0; i < me->totloop; i++, mdisp++) {
2315                 /* allocate memory for mdisp, the whole disp layer would be erased otherwise */
2316                 if (!mdisp->totdisp || !mdisp->disps) {
2317                         if (grid) {
2318                                 mdisp->totdisp = grid;
2319                                 mdisp->disps = MEM_callocN(3 * mdisp->totdisp * sizeof(float), "mdisp topology");
2320                         }
2321
2322                         continue;
2323                 }
2324         }
2325 }
2326
2327 /***************** Multires interpolation stuff *****************/
2328
2329 /* Find per-corner coordinate with given per-face UV coord */
2330 int mdisp_rot_face_to_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2331 {
2332         const float offset = face_side * 0.5f - 0.5f;
2333         int S = 0;
2334
2335         if (corners == 4) {
2336                 if (u <= offset && v <= offset) S = 0;
2337                 else if (u > offset  && v <= offset) S = 1;
2338                 else if (u > offset  && v > offset) S = 2;
2339                 else if (u <= offset && v >= offset) S = 3;
2340
2341                 if (S == 0) {
2342                         *y = offset - u;
2343                         *x = offset - v;
2344                 }
2345                 else if (S == 1) {
2346                         *x = u - offset;
2347                         *y = offset - v;
2348                 }
2349                 else if (S == 2) {
2350                         *y = u - offset;
2351                         *x = v - offset;
2352                 }
2353                 else if (S == 3) {
2354                         *x = offset - u;
2355                         *y = v - offset;
2356                 }
2357         }
2358         else {
2359                 int grid_size = offset;
2360                 float w = (face_side - 1) - u - v;
2361                 float W1, W2;
2362
2363                 if (u >= v && u >= w) {S = 0; W1 = w; W2 = v; }
2364                 else if (v >= u && v >= w) {S = 1; W1 = u; W2 = w; }
2365                 else {S = 2; W1 = v; W2 = u; }
2366
2367                 W1 /= (face_side - 1);
2368                 W2 /= (face_side - 1);
2369
2370                 *x = (1 - (2 * W1) / (1 - W2)) * grid_size;
2371                 *y = (1 - (2 * W2) / (1 - W1)) * grid_size;
2372         }
2373
2374         return S;
2375 }