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