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