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