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