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