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