svn merge -r38718:38804 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[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 static void column_vectors_to_mat3(float mat[][3], float v1[3], float v2[3], float v3[3])
343 {
344         copy_v3_v3(mat[0], v1);
345         copy_v3_v3(mat[1], v2);
346         copy_v3_v3(mat[2], v3);
347 }
348
349 static void multires_copy_grid(float (*gridA)[3], float (*gridB)[3], int sizeA, int sizeB)
350 {
351         int x, y, j, skip;
352
353         if(sizeA > sizeB) {
354                 skip = (sizeA-1)/(sizeB-1);
355
356                 for(j = 0, y = 0; y < sizeB; y++)
357                         for(x = 0; x < sizeB; x++, j++)
358                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip], gridB[j]);
359         }
360         else {
361                 skip = (sizeB-1)/(sizeA-1);
362
363                 for(j = 0, y = 0; y < sizeA; y++)
364                         for(x = 0; x < sizeA; x++, j++)
365                                 copy_v3_v3(gridA[j], gridB[y*skip*sizeB + x*skip]);
366         }
367 }
368
369 static void multires_copy_dm_grid(DMGridData *gridA, DMGridData *gridB, int sizeA, int sizeB)
370 {
371         int x, y, j, skip;
372
373         if(sizeA > sizeB) {
374                 skip = (sizeA-1)/(sizeB-1);
375
376                 for(j = 0, y = 0; y < sizeB; y++)
377                         for(x = 0; x < sizeB; x++, j++)
378                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip].co, gridB[j].co);
379         }
380         else {
381                 skip = (sizeB-1)/(sizeA-1);
382
383                 for(j = 0, y = 0; y < sizeA; y++)
384                         for(x = 0; x < sizeA; x++, j++)
385                                 copy_v3_v3(gridA[j].co, gridB[y*skip*sizeB + x*skip].co);
386         }
387 }
388
389 static void multires_del_higher(MultiresModifierData *mmd, Object *ob, int lvl)
390 {
391         Mesh *me = (Mesh*)ob->data;
392         int levels = mmd->totlvl - lvl;
393         MDisps *mdisps;
394
395         multires_set_tot_mdisps(me, mmd->totlvl);
396         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
397         mdisps= CustomData_get_layer(&me->ldata, CD_MDISPS);
398
399         multires_force_update(ob);
400
401         if(mdisps && levels > 0) {
402                 if(lvl > 0) {
403                         /* MLoop *ml = me->mloop; */ /*UNUSED*/
404                         int nsize = multires_side_tot[lvl];
405                         int hsize = multires_side_tot[mmd->totlvl];
406                         int i, j;
407
408                         for(i = 0; i < me->totpoly; ++i) {
409                                 for (j=0; j<me->mpoly[i].totloop; j++) {
410                                         MDisps *mdisp= &mdisps[me->mpoly[i].loopstart+j];
411                                         float (*disps)[3], (*ndisps)[3], (*hdisps)[3];
412                                         int totdisp = multires_grid_tot[lvl];
413
414                                         disps = BLI_cellalloc_calloc(sizeof(float) * 3 * totdisp, "multires disps");
415
416                                         ndisps = disps;
417                                         hdisps = mdisp->disps;
418
419                                         multires_copy_grid(ndisps, hdisps, nsize, hsize);
420
421                                         ndisps += nsize*nsize;
422                                         hdisps += hsize*hsize;
423
424                                         BLI_cellalloc_free(mdisp->disps);
425                                         mdisp->disps = disps;
426                                         mdisp->totdisp = totdisp;
427                                 }
428                         }
429                 }
430                 else {
431                         CustomData_external_remove(&me->ldata, &me->id, CD_MDISPS, me->totloop);
432                         CustomData_free_layer_active(&me->ldata, CD_MDISPS, me->totloop);
433                 }
434         }
435
436         multires_set_tot_level(ob, mmd, lvl);
437 }
438
439 /* direction=1 for delete higher, direction=0 for lower (not implemented yet) */
440 void multiresModifier_del_levels(MultiresModifierData *mmd, Object *ob, int direction)
441 {
442         Mesh *me = get_mesh(ob);
443         int lvl = multires_get_level(ob, mmd, 0);
444         int levels = mmd->totlvl - lvl;
445         MDisps *mdisps;
446
447         multires_set_tot_mdisps(me, mmd->totlvl);
448         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
449         mdisps= CustomData_get_layer(&me->ldata, CD_MDISPS);
450
451         multires_force_update(ob);
452
453         if(mdisps && levels > 0 && direction == 1) {
454                 multires_del_higher(mmd, ob, lvl);
455         }
456
457         multires_set_tot_level(ob, mmd, lvl);
458 }
459
460 static DerivedMesh *multires_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int totlvl, int simple)
461 {
462         MultiresModifierData mmd= {{NULL}};
463
464         mmd.lvl = lvl;
465         mmd.sculptlvl = lvl;
466         mmd.renderlvl = lvl;
467         mmd.totlvl = totlvl;
468         mmd.simple = simple;
469
470         return multires_dm_create_from_derived(&mmd, 1, dm, ob, 0, 0);
471 }
472
473 static DerivedMesh *subsurf_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int simple, int optimal, int plain_uv)
474 {
475         SubsurfModifierData smd= {{NULL}};
476
477         smd.levels = smd.renderLevels = lvl;
478         if(!plain_uv)
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, (ob->mode & OB_MODE_EDIT));
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, mmd->flags & eMultiresModifierFlag_PlainUv);
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, mmd->flags & eMultiresModifierFlag_PlainUv);
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         multires_set_tot_mdisps(me, mmd->totlvl);
837         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
838         mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
839
840         if(mdisps) {
841                 int lvl = ccgdm->multires.lvl;
842                 int totlvl = ccgdm->multires.totlvl;
843                 
844                 if(lvl < totlvl) {
845                         Mesh *me = ob->data;
846                         DerivedMesh *lowdm, *cddm, *highdm;
847                         DMGridData **highGridData, **lowGridData, **subGridData, **gridData, *diffGrid;
848                         CCGSubSurf *ss;
849                         int i, j, numGrids, highGridSize, lowGridSize;
850
851                         /* create subsurf DM from original mesh at high level */
852                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform, 0);
853                         else cddm = CDDM_from_mesh(me, NULL);
854                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
855
856                         highdm = subsurf_dm_create_local(ob, cddm, totlvl, mmd->simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
857
858                         /* create multires DM from original mesh and displacements */
859                         lowdm = multires_dm_create_local(ob, cddm, lvl, totlvl, mmd->simple);
860                         cddm->release(cddm);
861
862                         /* gather grid data */
863                         numGrids = highdm->getNumGrids(highdm);
864                         highGridSize = highdm->getGridSize(highdm);
865                         highGridData = highdm->getGridData(highdm);
866                         lowGridSize = lowdm->getGridSize(lowdm);
867                         lowGridData = lowdm->getGridData(lowdm);
868                         gridData = dm->getGridData(dm);
869
870                         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
871                         diffGrid = MEM_callocN(sizeof(DMGridData)*lowGridSize*lowGridSize, "diff");
872
873                         for(i = 0; i < numGrids; ++i) {
874                                 /* backup subsurf grids */
875                                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
876                                 memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
877
878                                 /* write difference of subsurf and displaced low level into high subsurf */
879                                 for(j = 0; j < lowGridSize*lowGridSize; ++j)
880                                         sub_v3_v3v3(diffGrid[j].co, gridData[i][j].co, lowGridData[i][j].co);
881
882                                 multires_copy_dm_grid(highGridData[i], diffGrid, highGridSize, lowGridSize);
883                         }
884
885                         /* lower level dm no longer needed at this point */
886                         MEM_freeN(diffGrid);
887                         lowdm->release(lowdm);
888
889                         /* subsurf higher levels again with difference of coordinates */
890                         ss= ((CCGDerivedMesh*)highdm)->ss;
891                         ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
892                         ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
893
894                         /* add to displacements */
895                         multiresModifier_disp_run(highdm, me, NULL, 1, 1, subGridData, mmd->totlvl);
896
897                         /* free */
898                         highdm->release(highdm);
899                         for(i = 0; i < numGrids; ++i)
900                                 MEM_freeN(subGridData[i]);
901                         MEM_freeN(subGridData);
902                 }
903                 else {
904                         DerivedMesh *cddm, *subdm;
905
906                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform, 0);
907                         else cddm = CDDM_from_mesh(me, NULL);
908                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
909
910                         subdm = subsurf_dm_create_local(ob, cddm, mmd->totlvl, mmd->simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
911                         cddm->release(cddm);
912
913                         multiresModifier_disp_run(dm, me, NULL, 1, 0, subdm->getGridData(subdm), mmd->totlvl);
914
915                         subdm->release(subdm);
916                 }
917         }
918 }
919
920
921 void multires_set_space(DerivedMesh *dm, Object *ob, int from, int to)
922 {
923         DerivedMesh *ccgdm, *subsurf=NULL;
924         DMGridData **gridData, **subGridData=NULL;
925         MPoly *mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
926         MDisps *mdisps;
927         MultiresModifierData *mmd = get_multires_modifier(NULL, ob, 1);
928         int *gridOffset, totlvl;
929         int i, k, numGrids, gridSize, dGridSize, dSkip;
930         
931         if (!mmd)
932                 return;
933         
934         mdisps = CustomData_get_layer(&dm->loopData, CD_MDISPS);
935
936         if(!mdisps) {
937                 goto cleanup;
938         }
939
940         totlvl = mmd->totlvl;
941         ccgdm = multires_dm_create_local(ob, dm, totlvl, totlvl, mmd->simple);
942         
943         subsurf = subsurf_dm_create_local(ob, dm, totlvl,
944                 mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges);
945
946         numGrids = subsurf->getNumGrids(subsurf);
947         gridSize = subsurf->getGridSize(subsurf);
948         gridData = subsurf->getGridData(subsurf);
949
950         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
951
952         for(i = 0; i < numGrids; i++) {
953                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*gridSize*gridSize, "subGridData");
954                 memcpy(subGridData[i], gridData[i], sizeof(DMGridData)*gridSize*gridSize);
955         }
956         
957         /*numGrids = ccgdm->dm->getNumGrids((DerivedMesh*)ccgdm);*/ /*UNUSED*/
958         gridSize = ccgdm->getGridSize((DerivedMesh*)ccgdm);
959         gridData = ccgdm->getGridData((DerivedMesh*)ccgdm);
960         gridOffset = ccgdm->getGridOffset((DerivedMesh*)ccgdm);
961
962         dGridSize = multires_side_tot[totlvl];
963         dSkip = (dGridSize-1)/(gridSize-1);
964
965         k = 0; /*current loop/mdisp index within the mloop array*/
966
967         //#pragma omp parallel for private(i) if(dm->numLoopData*gridSize*gridSize >= CCG_OMP_LIMIT)
968
969         for(i = 0; i < dm->numPolyData; ++i) {
970                 const int numVerts = mpoly[i].totloop;
971                 int S, x, y, gIndex = gridOffset[i];
972                                                 
973                 for(S = 0; S < numVerts; ++S, ++gIndex, ++k) {
974                         MDisps *mdisp = &mdisps[mpoly[i].loopstart+S];
975                         DMGridData *grid = gridData[gIndex];
976                         DMGridData *subgrid = subGridData[gIndex];
977                         float (*dispgrid)[3] = NULL;
978
979                         /* when adding new faces in edit mode, need to allocate disps */
980                         if(!mdisp->disps) {
981                                 mdisp->totdisp = gridSize*gridSize;
982                                 mdisp->disps = BLI_cellalloc_calloc(sizeof(float)*3*mdisp->totdisp, "disp in multires_set_space");
983                         }
984
985                         dispgrid = mdisp->disps;
986
987                         for(y = 0; y < gridSize; y++) {
988                                 for(x = 0; x < gridSize; x++) {
989                                         float *data = dispgrid[dGridSize*y*dSkip + x*dSkip];
990                                         float *no = subgrid[x + y*gridSize].no;
991                                         float *co = subgrid[x + y*gridSize].co;
992                                         float mat[3][3], tx[3], ty[3], dco[3];
993                                         
994                                         /* construct tangent space matrix */
995                                         grid_tangent(gridSize, gIndex, x, y, 0, subGridData, tx);
996                                         normalize_v3(tx);
997
998                                         grid_tangent(gridSize, gIndex, x, y, 1, subGridData, ty);
999                                         normalize_v3(ty);
1000                                         column_vectors_to_mat3(mat, tx, ty, no);
1001
1002                                         /* convert to absolute coordinates in space */
1003                                         if (from == MULTIRES_SPACE_TANGENT) {
1004                                                 mul_v3_m3v3(dco, mat, data);
1005                                                 add_v3_v3(dco, co);
1006                                         } else if (from == MULTIRES_SPACE_OBJECT) {
1007                                                 add_v3_v3v3(dco, co, data);
1008                                         } else if (from == MULTIRES_SPACE_ABSOLUTE) {
1009                                                 copy_v3_v3(dco, data);
1010                                         }
1011                                         
1012                                         column_vectors_to_mat3(mat, tx, ty, no);
1013
1014                                         /*now, convert to desired displacement type*/
1015                                         if (to == MULTIRES_SPACE_TANGENT) {
1016                                                 invert_m3(mat);
1017
1018                                                 sub_v3_v3(dco, co);
1019                                                 mul_v3_m3v3(data, mat, dco);
1020                                         } else if (to == MULTIRES_SPACE_OBJECT) {
1021                                                 sub_v3_v3(dco, co);
1022                                                 mul_v3_m3v3(data, mat, dco);
1023                                         } else if (to == MULTIRES_SPACE_ABSOLUTE) {
1024                                                 copy_v3_v3(data, dco);
1025                                         }
1026                                 }
1027                         }
1028                 }
1029         }
1030
1031 cleanup:
1032         if (subsurf) {
1033                 subsurf->needsFree = 1;
1034                 subsurf->release(subsurf);
1035         }
1036         
1037         ccgdm->needsFree = 1;
1038         ccgdm->release(ccgdm);
1039 }
1040
1041 void multires_stitch_grids(Object *ob)
1042 {
1043         /* utility for smooth brush */
1044         if(ob && ob->derivedFinal) {
1045                 CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)ob->derivedFinal;
1046                 CCGFace **faces;
1047                 int totface;
1048
1049                 if(ccgdm->pbvh) {
1050                         BLI_pbvh_get_grid_updates(ccgdm->pbvh, 0, (void***)&faces, &totface);
1051
1052                         if(totface) {
1053                                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, faces, totface);
1054                                 MEM_freeN(faces);
1055                         }
1056                 }
1057         }
1058 }
1059
1060 DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int local_mmd, DerivedMesh *dm, Object *ob,
1061                                                         int useRenderParams, int UNUSED(isFinalCalc))
1062 {
1063         Mesh *me= ob->data;
1064         DerivedMesh *result;
1065         CCGDerivedMesh *ccgdm;
1066         DMGridData **gridData, **subGridData;
1067         int lvl= multires_get_level(ob, mmd, useRenderParams);
1068         int i, gridSize, numGrids;
1069
1070         if(lvl == 0)
1071                 return dm;
1072
1073         result = subsurf_dm_create_local(ob, dm, lvl,
1074                 mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges,
1075                 mmd->flags & eMultiresModifierFlag_PlainUv);
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)/M_LN2;
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; */ /* UNUSED */
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, mmd->flags & eMultiresModifierFlag_PlainUv);
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 /* update multires data after topology changing */
1899 #if 0 // BMESH_TODO
1900 void multires_topology_changed(Scene *scene, Object *ob)
1901 {
1902         Mesh *me= (Mesh*)ob->data;
1903         MDisps *mdisp= NULL, *cur= NULL;
1904         int i, grid= 0, corners;
1905         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1906
1907         if(mmd)
1908                 multires_set_tot_mdisps(me, mmd->totlvl);
1909
1910         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
1911         mdisp= CustomData_get_layer(&me->fdata, CD_MDISPS);
1912
1913         if(!mdisp) return;
1914
1915         cur= mdisp;
1916         for(i = 0; i < me->totface; i++, cur++) {
1917                 if(mdisp->totdisp) {
1918                         corners= multires_mdisp_corners(mdisp);
1919                         grid= mdisp->totdisp / corners;
1920
1921                         break;
1922                 }
1923         }
1924
1925         for(i = 0; i < me->totface; i++, mdisp++) {
1926                 int nvert= me->mface[i].v4 ? 4 : 3;
1927
1928                 /* allocate memory for mdisp, the whole disp layer would be erased otherwise */
1929                 if(!mdisp->totdisp || !mdisp->disps) {
1930                         if(grid) {
1931                                 mdisp->totdisp= nvert*grid;
1932                                 mdisp->disps= MEM_callocN(mdisp->totdisp*sizeof(float)*3, "mdisp topology");
1933                         }
1934
1935                         continue;
1936                 }
1937
1938                 corners= multires_mdisp_corners(mdisp);
1939
1940                 if(corners!=nvert) {
1941                         mdisp->totdisp= (mdisp->totdisp/corners)*nvert;
1942
1943                         if(mdisp->disps)
1944                                 MEM_freeN(mdisp->disps);
1945
1946                         mdisp->disps= MEM_callocN(mdisp->totdisp*sizeof(float)*3, "mdisp topology");
1947                 }
1948         }
1949 }
1950 #endif // BMESH_TODO
1951
1952 /* makes displacement along grid boundary symmetrical */
1953 void multires_mdisp_smooth_bounds(MDisps *disps)
1954 {
1955         int x, y, side, S, corners;
1956         float (*out)[3];
1957
1958         corners = multires_mdisp_corners(disps);
1959         side = sqrt(disps->totdisp / corners);
1960
1961         out = disps->disps;
1962         for(S = 0; S < corners; S++) {
1963                 for(y = 0; y < side; ++y) {
1964                         for(x = 0; x < side; ++x, ++out) {
1965                                 float (*dispgrid)[3];
1966                                 float *data;
1967
1968                                 if(x != 0 && y != 0) continue;
1969
1970                                 if(corners == 4) {
1971                                         if(S == 0) {
1972                                                 if(y == 0) {
1973                                                         dispgrid = &disps->disps[1*side*side];
1974                                                         data = dispgrid[side * x + 0];
1975
1976                                                         (*out)[0] = (*out)[0] + data[1];
1977                                                         (*out)[1] = (*out)[1] - data[0];
1978                                                         (*out)[2] = (*out)[2] + data[2];
1979
1980                                                         mul_v3_fl(*out, 0.5);
1981
1982                                                         data[0] = -(*out)[1];
1983                                                         data[1] = (*out)[0];
1984                                                         data[2] = (*out)[2];
1985                                                 } else if (x == 0) {
1986                                                         dispgrid = &disps->disps[3 * side * side];
1987                                                         data = dispgrid[side * 0 + y];
1988
1989                                                         (*out)[0] = (*out)[0] - data[1];
1990                                                         (*out)[1] = (*out)[1] + data[0];
1991                                                         (*out)[2] = (*out)[2] + data[2];
1992
1993                                                         mul_v3_fl(*out, 0.5);
1994
1995                                                         data[0] = (*out)[1];
1996                                                         data[1] = -(*out)[0];
1997                                                         data[2] = (*out)[2];
1998                                                 }
1999                                         } else if (S == 2) {
2000                                                 if(y == 0) {
2001                                                         dispgrid = &disps->disps[3 * side * side];
2002                                                         data = dispgrid[side * x + 0];
2003
2004                                                         (*out)[0] = (*out)[0] + data[1];
2005                                                         (*out)[1] = (*out)[1] - data[0];
2006                                                         (*out)[2] = (*out)[2] + data[2];
2007
2008                                                         mul_v3_fl(*out, 0.5);
2009
2010                                                         data[0] = -(*out)[1];
2011                                                         data[1] = (*out)[0];
2012                                                         data[2] = (*out)[2];
2013                                                 } else if(x == 0) {
2014                                                         dispgrid = &disps->disps[1 * side * side];
2015                                                         data = dispgrid[side * 0 + y];
2016
2017                                                         (*out)[0] = (*out)[0] - data[1];
2018                                                         (*out)[1] = (*out)[1] + data[0];
2019                                                         (*out)[2] = (*out)[2] + data[2];
2020
2021                                                         mul_v3_fl(*out, 0.5);
2022
2023                                                         data[0] = (*out)[1];
2024                                                         data[1] = -(*out)[0];
2025                                                         data[2] = (*out)[2];
2026                                                 }
2027                                         }
2028                                 } else if (corners == 3) {
2029                                         if(S == 0) {
2030                                                 if(y == 0) {
2031                                                         dispgrid = &disps->disps[1*side*side];
2032                                                         data = dispgrid[side * x + 0];
2033
2034                                                         (*out)[0] = (*out)[0] + data[1];
2035                                                         (*out)[1] = (*out)[1] - data[0];
2036                                                         (*out)[2] = (*out)[2] + data[2];
2037
2038                                                         mul_v3_fl(*out, 0.5);
2039
2040                                                         data[0] = -(*out)[1];
2041                                                         data[1] = (*out)[0];
2042                                                         data[2] = (*out)[2];
2043                                                 } else if (x == 0) {
2044                                                         dispgrid = &disps->disps[2 * side * side];
2045                                                         data = dispgrid[side * 0 + y];
2046
2047                                                         (*out)[0] = (*out)[0] - data[1];
2048                                                         (*out)[1] = (*out)[1] + data[0];
2049                                                         (*out)[2] = (*out)[2] + data[2];
2050
2051                                                         mul_v3_fl(*out, 0.5);
2052
2053                                                         data[0] = (*out)[1];
2054                                                         data[1] = -(*out)[0];
2055                                                         data[2] = (*out)[2];
2056                                                 }
2057                                         } else if (S == 2) {
2058                                                 if(x == 0) {
2059                                                         dispgrid = &disps->disps[1 * side * side];
2060                                                         data = dispgrid[side * 0 + y];
2061
2062                                                         (*out)[0] = (*out)[0] - data[1];
2063                                                         (*out)[1] = (*out)[1] + data[0];
2064                                                         (*out)[2] = (*out)[2] + data[2];
2065
2066                                                         mul_v3_fl(*out, 0.5);
2067
2068                                                         data[0] = (*out)[1];
2069                                                         data[1] = -(*out)[0];
2070                                                         data[2] = (*out)[2];
2071                                                 }
2072                                         }
2073                                 }
2074                         }
2075                 }
2076         }
2077 }
2078
2079 /***************** Multires interpolation stuff *****************/
2080
2081 static void mdisp_get_crn_rect(int face_side, float crn[3][4][2])
2082 {
2083         float offset = face_side*0.5f - 0.5f;
2084         float mid[2];
2085
2086         mid[0] = offset * 4 / 3;
2087         mid[1] = offset * 2 / 3;
2088
2089         crn[0][0][0] = mid[0]; crn[0][0][1] = mid[1];
2090         crn[0][1][0] = offset; crn[0][1][1] = 0;
2091         crn[0][2][0] = 0; crn[0][2][1] = 0;
2092         crn[0][3][0] = offset; crn[0][3][1] = offset;
2093
2094         crn[1][0][0] = mid[0]; crn[1][0][1] = mid[1];
2095         crn[1][1][0] = offset * 2; crn[1][1][1] = offset;
2096         crn[1][2][0] = offset * 2; crn[1][2][1] = 0;
2097         crn[1][3][0] = offset; crn[1][3][1] = 0;
2098
2099         crn[2][0][0] = mid[0]; crn[2][0][1] = mid[1];
2100         crn[2][1][0] = offset; crn[2][1][1] = offset;
2101         crn[2][2][0] = offset * 2; crn[2][2][1] = offset * 2;
2102         crn[2][3][0] = offset * 2; crn[2][3][1] = offset;
2103 }
2104
2105 static int mdisp_pt_in_crn(float p[2], float crn[4][2])
2106 {
2107         float v[2][2];
2108         float a[2][2];
2109
2110         sub_v2_v2v2(v[0], crn[1], crn[0]);
2111         sub_v2_v2v2(v[1], crn[3], crn[0]);
2112
2113         sub_v2_v2v2(a[0], p, crn[0]);
2114         sub_v2_v2v2(a[1], crn[2], crn[0]);
2115
2116         if(cross_v2v2(a[0], v[0]) * cross_v2v2(a[1], v[0]) < 0)
2117                 return 0;
2118
2119         if(cross_v2v2(a[0], v[1]) * cross_v2v2(a[1], v[1]) < 0)
2120                 return 0;
2121
2122         return 1;
2123 }
2124
2125 static void face_to_crn_interp(float u, float v, float v1[2], float v2[2], float v3[2], float v4[2], float *x)
2126 {
2127         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];
2128         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];
2129         float c = (v3[1]-v)*v1[0]+(-v3[1]+v1[1])*u+v3[0]*v-v1[1]*v3[0];
2130         float d = b * b - 4 * a * c;
2131         float x1, x2;
2132
2133         if(a == 0) {
2134                 *x = -c / b;
2135                 return;
2136         }
2137
2138         x1 = (-b - sqrtf(d)) / (2 * a);
2139         x2 = (-b + sqrtf(d)) / (2 * a);
2140
2141         *x = maxf(x1, x2);
2142 }
2143
2144 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)
2145 {
2146         float offset = face_side*0.5f - 0.5f;
2147
2148         if(corners == 4) {
2149                 if(S == 1) { *u= offset + x; *v = offset - y; }
2150                 if(S == 2) { *u= offset + y; *v = offset + x; }
2151                 if(S == 3) { *u= offset - x; *v = offset + y; }
2152                 if(S == 0) { *u= offset - y; *v = offset - x; }
2153         } else {
2154                 float crn[3][4][2], vec[4][2];
2155                 float p[2];
2156
2157                 mdisp_get_crn_rect(face_side, crn);
2158
2159                 interp_v2_v2v2(vec[0], crn[S][0], crn[S][1], x / offset);
2160                 interp_v2_v2v2(vec[1], crn[S][3], crn[S][2], x / offset);
2161                 interp_v2_v2v2(vec[2], crn[S][0], crn[S][3], y / offset);
2162                 interp_v2_v2v2(vec[3], crn[S][1], crn[S][2], y / offset);
2163
2164                 isect_seg_seg_v2_point(vec[0], vec[1], vec[2], vec[3], p);
2165
2166                 (*u) = p[0];
2167                 (*v) = p[1];
2168         }
2169 }
2170
2171 /* Find per-corner coordinate with given per-face UV coord */
2172 int mdisp_rot_face_to_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2173 {
2174         const float offset = face_side*0.5f - 0.5f;
2175         int S = 0;
2176
2177         if (corners == 4) {
2178                 if(u <= offset && v <= offset) S = 0;
2179                 else if(u > offset  && v <= offset) S = 1;
2180                 else if(u > offset  && v > offset) S = 2;
2181                 else if(u <= offset && v >= offset)  S = 3;
2182
2183                 if(S == 0) {
2184                         *y = offset - u;
2185                         *x = offset - v;
2186                 } else if(S == 1) {
2187                         *x = u - offset;
2188                         *y = offset - v;
2189                 } else if(S == 2) {
2190                         *y = u - offset;
2191                         *x = v - offset;
2192                 } else if(S == 3) {
2193                         *x= offset - u;
2194                         *y = v - offset;
2195                 }
2196         } else {
2197                 int grid_size = offset;
2198                 float w = (face_side - 1) - u - v;
2199                 float W1, W2;
2200
2201                 if (u >= v && u >= w) {S = 0; W1= w; W2= v;}
2202                 else if (v >= u && v >= w) {S = 1; W1 = u; W2 = w;}
2203                 else {S = 2; W1 = v; W2 = u;}
2204
2205                 W1 /= (face_side-1);
2206                 W2 /= (face_side-1);
2207
2208                 *x = (1-(2*W1)/(1-W2)) * grid_size;
2209                 *y = (1-(2*W2)/(1-W1)) * grid_size;
2210         }
2211
2212         return S;
2213 }
2214
2215 /* Find per-corner coordinate with given per-face UV coord
2216    Practically as the previous funciton but it assumes a bit different coordinate system for triangles
2217    which is optimized for MDISP layer interpolation:
2218
2219    v
2220    ^
2221    |      /|
2222    |    /  |
2223    |  /    |
2224    |/______|___> u
2225
2226  */
2227 int mdisp_rot_face_to_quad_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2228 {
2229         const float offset = face_side*0.5f - 0.5f;
2230         int S = 0;
2231
2232         if (corners == 4) {
2233                 if(u <= offset && v <= offset) S = 0;
2234                 else if(u > offset  && v <= offset) S = 1;
2235                 else if(u > offset  && v > offset) S = 2;
2236                 else if(u <= offset && v >= offset)  S = 3;
2237
2238                 if(S == 0) {
2239                         *y = offset - u;
2240                         *x = offset - v;
2241                 } else if(S == 1) {
2242                         *x = u - offset;
2243                         *y = offset - v;
2244                 } else if(S == 2) {
2245                         *y = u - offset;
2246                         *x = v - offset;
2247                 } else if(S == 3) {
2248                         *x= offset - u;
2249                         *y = v - offset;
2250                 }
2251         } else {
2252                 float crn[3][4][2];
2253                 float p[2] = {u, v};
2254
2255                 mdisp_get_crn_rect(face_side, crn);
2256
2257                 for (S = 0; S < 3; ++S) {
2258                         if (mdisp_pt_in_crn(p, crn[S]))
2259                                 break;
2260                 }
2261
2262                 face_to_crn_interp(u, v, crn[S][0], crn[S][1], crn[S][3], crn[S][2], &p[0]);
2263                 face_to_crn_interp(u, v, crn[S][0], crn[S][3], crn[S][1], crn[S][2], &p[1]);
2264
2265                 *x = p[0] * offset;
2266                 *y = p[1] * offset;
2267         }
2268
2269         return S;
2270 }
2271
2272 void mdisp_apply_weight(const int S, const int corners, int x, int y, const int face_side,
2273         float crn_weight[4][2], float *u_r, float *v_r)
2274 {
2275         float u, v, xl, yl;
2276         float mid1[2], mid2[2], mid3[2];
2277
2278         mdisp_rot_crn_to_face(S, corners, face_side, x, y, &u, &v);
2279
2280         if(corners == 4) {
2281                 xl = u / (face_side - 1);
2282                 yl = v / (face_side - 1);
2283
2284                 mid1[0] = crn_weight[0][0] * (1 - xl) + crn_weight[1][0] * xl;
2285                 mid1[1] = crn_weight[0][1] * (1 - xl) + crn_weight[1][1] * xl;
2286                 mid2[0] = crn_weight[3][0] * (1 - xl) + crn_weight[2][0] * xl;
2287                 mid2[1] = crn_weight[3][1] * (1 - xl) + crn_weight[2][1] * xl;
2288                 mid3[0] = mid1[0] * (1 - yl) + mid2[0] * yl;
2289                 mid3[1] = mid1[1] * (1 - yl) + mid2[1] * yl;
2290         } else {
2291                 yl = v / (face_side - 1);
2292
2293                 if(v == face_side - 1) xl = 1;
2294                 else xl = 1 - (face_side - 1 - u) / (face_side - 1 - v);
2295
2296                 mid1[0] = crn_weight[0][0] * (1 - xl) + crn_weight[1][0] * xl;
2297                 mid1[1] = crn_weight[0][1] * (1 - xl) + crn_weight[1][1] * xl;
2298                 mid3[0] = mid1[0] * (1 - yl) + crn_weight[2][0] * yl;
2299                 mid3[1] = mid1[1] * (1 - yl) + crn_weight[2][1] * yl;
2300         }
2301
2302         *u_r = mid3[0];
2303         *v_r = mid3[1];
2304 }
2305
2306 void mdisp_flip_disp(const int S, const int corners, const float axis_x[2], const float axis_y[2], float disp[3])
2307 {
2308         float crn_x[2], crn_y[2];
2309         float vx[2], vy[2], coord[2];
2310
2311         if (corners == 4) {
2312                 float x[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
2313                 float y[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
2314
2315                 copy_v2_v2(crn_x, x[S]);
2316                 copy_v2_v2(crn_y, y[S]);
2317
2318                 mul_v2_v2fl(vx, crn_x, disp[0]);
2319                 mul_v2_v2fl(vy, crn_y, disp[1]);
2320                 add_v2_v2v2(coord, vx, vy);
2321
2322                 project_v2_v2v2(vx, coord, axis_x);
2323                 project_v2_v2v2(vy, coord, axis_y);
2324
2325                 disp[0] = len_v2(vx);
2326                 disp[1] = len_v2(vy);
2327
2328                 if(dot_v2v2(vx, axis_x) < 0)
2329                         disp[0] = -disp[0];
2330
2331                 if(dot_v2v2(vy, axis_y) < 0)
2332                         disp[1] = -disp[1];
2333         } else {
2334                 /* XXX: it was very overhead code to support displacement flipping
2335                         for case of tris without visible profit.
2336                         Maybe its not really big limitation? for now? (nazgul) */
2337                 disp[0] = 0;
2338                 disp[1] = 0;
2339         }
2340 }
2341
2342 /* Join two triangular displacements into one quad
2343          Corners mapping:
2344          2 -------- 3
2345          | \   tri2 |
2346          |    \     |
2347          | tri1  \  |
2348          0 -------- 1 */
2349 void mdisp_join_tris(MDisps *dst, MDisps *tri1, MDisps *tri2)
2350 {
2351         int side, st;
2352         int S, x, y, crn;
2353         float face_u, face_v, crn_u, crn_v;
2354         float (*out)[3];
2355         MDisps *src;
2356
2357         if(dst->disps)
2358                 BLI_cellalloc_free(dst->disps);
2359
2360         side = sqrt(tri1->totdisp / 3);
2361         st = (side<<1)-1;
2362
2363         dst->totdisp = 4 * side * side;
2364         out = dst->disps = BLI_cellalloc_calloc(3*dst->totdisp*sizeof(float), "join disps");
2365
2366         for(S = 0; S < 4; S++)
2367                 for(y = 0; y < side; ++y)
2368                         for(x = 0; x < side; ++x, ++out) {
2369                                 mdisp_rot_crn_to_face(S, 4, st, x, y, &face_u, &face_v);
2370                                 face_u = st - 1 - face_u;
2371
2372                                 if(face_v > face_u) {
2373                                         src = tri2;
2374                                         face_u = st - 1 - face_u;
2375                                         face_v = st - 1 - face_v;
2376                                 } else src = tri1;
2377
2378                                 crn = mdisp_rot_face_to_quad_crn(3, st, face_u, face_v, &crn_u, &crn_v);
2379
2380                                 old_mdisps_bilinear((*out), &src->disps[crn*side*side], side, crn_u, crn_v);
2381                                 (*out)[0] = 0;
2382                                 (*out)[1] = 0;
2383                         }
2384 }