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