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