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