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