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