svn merge ^/trunk/blender -r40644:40720
[blender-staging.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, mmd->flags & eMultiresModifierFlag_PlainUv);
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]; */ /* UNUSED */
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 = 0.0f, v = 0.0f; /* Quite gcc barking. */
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; */ /* UNUSED */
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                 me->mface[i].mat_nr = lvl->faces[i].mat_nr;
1707         }
1708
1709         /* Add a multires modifier to the object */
1710         md = ob->modifiers.first;
1711         while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
1712                 md = md->next;                          
1713         mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
1714         BLI_insertlinkbefore(&ob->modifiers, md, mmd);
1715
1716         for(i = 0; i < me->mr->level_count - 1; ++i)
1717                 multiresModifier_subdivide(mmd, ob, 1, 0);
1718
1719         mmd->lvl = mmd->totlvl;
1720         orig = CDDM_from_mesh(me, NULL);
1721         dm = multires_dm_create_from_derived(mmd, 0, orig, ob, 0, 0);
1722                                            
1723         multires_load_old_dm(dm, me, mmd->totlvl+1);
1724
1725         multires_dm_mark_as_modified(dm);
1726         dm->release(dm);
1727         orig->release(orig);
1728
1729         /* Copy the first-level data to the mesh */
1730         for(i = 0, l = me->mr->vdata.layers; i < me->mr->vdata.totlayer; ++i, ++l)
1731                 CustomData_add_layer(&me->vdata, l->type, CD_REFERENCE, l->data, me->totvert);
1732         for(i = 0, l = me->mr->fdata.layers; i < me->mr->fdata.totlayer; ++i, ++l)
1733                 CustomData_add_layer(&me->fdata, l->type, CD_REFERENCE, l->data, me->totface);
1734         memset(&me->mr->vdata, 0, sizeof(CustomData));
1735         memset(&me->mr->fdata, 0, sizeof(CustomData));
1736
1737         multires_load_old_vcols(me);
1738         multires_load_old_face_flags(me);
1739
1740         /* Remove the old multires */
1741         multires_free(me->mr);
1742         me->mr= NULL;
1743 }
1744
1745 static void multires_sync_levels(Scene *scene, Object *ob, Object *to_ob)
1746 {
1747         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1748         MultiresModifierData *to_mmd= get_multires_modifier(scene, to_ob, 1);
1749
1750         if(!mmd) {
1751                 /* object could have MDISP even when there is no multires modifier
1752                    this could lead to troubles due to i've got no idea how mdisp could be
1753                    upsampled correct without modifier data.
1754                    just remove mdisps if no multires present (nazgul) */
1755
1756                 Mesh *me= (Mesh*)ob->data;
1757
1758                 CustomData_external_remove(&me->ldata, &me->id, CD_MDISPS, me->totloop);
1759                 CustomData_free_layer_active(&me->ldata, CD_MDISPS, me->totloop);
1760         }
1761
1762         if(!mmd || !to_mmd) return;
1763
1764         if(mmd->totlvl>to_mmd->totlvl) multires_del_higher(mmd, ob, to_mmd->totlvl);
1765         else multires_subdivide(mmd, ob, to_mmd->totlvl, 0, mmd->simple);
1766 }
1767
1768 static void multires_apply_smat(Scene *scene, Object *ob, float smat[3][3])
1769 {
1770         DerivedMesh *dm= NULL, *cddm= NULL, *subdm= NULL;
1771         DMGridData **gridData, **subGridData;
1772         Mesh *me= (Mesh*)ob->data;
1773         MPoly *mpoly= me->mpoly;
1774         /* MLoop *mloop = me->mloop; */ /* UNUSED */
1775         MDisps *mdisps;
1776         int *gridOffset;
1777         int i, /*numGrids,*/ gridSize, dGridSize, dSkip, totvert;
1778         float (*vertCos)[3] = NULL;
1779         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1780         MultiresModifierData high_mmd;
1781
1782         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
1783         mdisps= CustomData_get_layer(&me->ldata, CD_MDISPS);
1784
1785         if(!mdisps || !mmd) return;
1786
1787         /* we need derived mesh created from highest resolution */
1788         high_mmd= *mmd;
1789         high_mmd.lvl= high_mmd.totlvl;
1790
1791         /* unscaled multires with applied displacement */
1792         subdm= get_multires_dm(scene, &high_mmd, ob);
1793
1794         /* prepare scaled CDDM to create ccgDN */
1795         cddm= mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
1796
1797         totvert= cddm->getNumVerts(cddm);
1798         vertCos= MEM_mallocN(sizeof(*vertCos) * totvert, "multiresScale vertCos");
1799         cddm->getVertCos(cddm, vertCos);
1800         for(i=0; i<totvert; i++)
1801                 mul_m3_v3(smat, vertCos[i]);
1802         CDDM_apply_vert_coords(cddm, vertCos);
1803         MEM_freeN(vertCos);
1804
1805         /* scaled ccgDM for tangent space of object with applied scale */
1806         dm= subsurf_dm_create_local(ob, cddm, high_mmd.totlvl, high_mmd.simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
1807         cddm->release(cddm);
1808
1809         /*numGrids= dm->getNumGrids(dm);*/ /*UNUSED*/
1810         gridSize= dm->getGridSize(dm);
1811         gridData= dm->getGridData(dm);
1812         gridOffset= dm->getGridOffset(dm);
1813         subGridData= subdm->getGridData(subdm);
1814
1815         dGridSize= multires_side_tot[high_mmd.totlvl];
1816         dSkip= (dGridSize-1)/(gridSize-1);
1817
1818         #pragma omp parallel for private(i) if(me->totface*gridSize*gridSize*4 >= CCG_OMP_LIMIT)
1819         for(i = 0; i < me->totpoly; ++i) {
1820                 const int numVerts= mpoly[i].totloop;
1821                 MDisps *mdisp= &mdisps[mpoly[i].loopstart];
1822                 int S, x, y, gIndex = gridOffset[i];
1823
1824                 for(S = 0; S < numVerts; ++S, ++gIndex, mdisp++) {
1825                         DMGridData *grid= gridData[gIndex];
1826                         DMGridData *subgrid= subGridData[gIndex];
1827                         float (*dispgrid)[3]= mdisp->disps;
1828
1829                         for(y = 0; y < gridSize; y++) {
1830                                 for(x = 0; x < gridSize; x++) {
1831                                         float *co= grid[x + y*gridSize].co;
1832                                         float *sco= subgrid[x + y*gridSize].co;
1833                                         float *no= grid[x + y*gridSize].no;
1834                                         float *data= dispgrid[dGridSize*y*dSkip + x*dSkip];
1835                                         float mat[3][3], tx[3], ty[3], disp[3];
1836
1837                                         /* construct tangent space matrix */
1838                                         grid_tangent(gridSize, gIndex, x, y, 0, gridData, tx);
1839                                         normalize_v3(tx);
1840
1841                                         grid_tangent(gridSize, gIndex, x, y, 1, gridData, ty);
1842                                         normalize_v3(ty);
1843
1844                                         column_vectors_to_mat3(mat, tx, ty, no);
1845
1846                                         /* scale subgrid coord and calculate displacement */
1847                                         mul_m3_v3(smat, sco);
1848                                         sub_v3_v3v3(disp, sco, co);
1849
1850                                         /* convert difference to tangent space */
1851                                         invert_m3(mat);
1852                                         mul_v3_m3v3(data, mat, disp);
1853                                 }
1854                         }
1855                 }
1856         }
1857
1858         dm->release(dm);
1859         subdm->release(subdm);
1860 }
1861
1862 int multires_mdisp_corners(MDisps *s)
1863 {
1864         int lvl= 13;
1865
1866         while(lvl > 0) {
1867                 int side = (1 << (lvl-1)) + 1;
1868                 if ((s->totdisp % (side*side)) == 0) return s->totdisp / (side*side);
1869                 lvl--;
1870         }
1871
1872         return 0;
1873 }
1874
1875 void multiresModifier_scale_disp(Scene *scene, Object *ob)
1876 {
1877         float smat[3][3];
1878
1879         /* object's scale matrix */
1880         object_scale_to_mat3(ob, smat);
1881
1882         multires_apply_smat(scene, ob, smat);
1883 }
1884
1885 void multiresModifier_prepare_join(Scene *scene, Object *ob, Object *to_ob)
1886 {
1887         float smat[3][3], tmat[3][3], mat[3][3];
1888         multires_sync_levels(scene, ob, to_ob);
1889
1890         /* construct scale matrix for displacement */
1891         object_scale_to_mat3(to_ob, tmat);
1892         invert_m3(tmat);
1893         object_scale_to_mat3(ob, smat);
1894         mul_m3_m3m3(mat, smat, tmat);
1895
1896         multires_apply_smat(scene, ob, mat);
1897 }
1898
1899 /* update multires data after topology changing */
1900 #if 0 // BMESH_TODO
1901 void multires_topology_changed(Scene *scene, Object *ob)
1902 {
1903         Mesh *me= (Mesh*)ob->data;
1904         MDisps *mdisp= NULL, *cur= NULL;
1905         int i, grid= 0, corners;
1906         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1907
1908         if(mmd)
1909                 multires_set_tot_mdisps(me, mmd->totlvl);
1910
1911         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
1912         mdisp= CustomData_get_layer(&me->fdata, CD_MDISPS);
1913
1914         if(!mdisp) return;
1915
1916         cur= mdisp;
1917         for(i = 0; i < me->totface; i++, cur++) {
1918                 if(mdisp->totdisp) {
1919                         corners= multires_mdisp_corners(mdisp);
1920                         grid= mdisp->totdisp / corners;
1921
1922                         break;
1923                 }
1924         }
1925
1926         for(i = 0; i < me->totface; i++, mdisp++) {
1927                 int nvert= me->mface[i].v4 ? 4 : 3;
1928
1929                 /* allocate memory for mdisp, the whole disp layer would be erased otherwise */
1930                 if(!mdisp->totdisp || !mdisp->disps) {
1931                         if(grid) {
1932                                 mdisp->totdisp= nvert*grid;
1933                                 mdisp->disps= MEM_callocN(mdisp->totdisp*sizeof(float)*3, "mdisp topology");
1934                         }
1935
1936                         continue;
1937                 }
1938
1939                 corners= multires_mdisp_corners(mdisp);
1940
1941                 if(corners!=nvert) {
1942                         mdisp->totdisp= (mdisp->totdisp/corners)*nvert;
1943
1944                         if(mdisp->disps)
1945                                 MEM_freeN(mdisp->disps);
1946
1947                         mdisp->disps= MEM_callocN(mdisp->totdisp*sizeof(float)*3, "mdisp topology");
1948                 }
1949         }
1950 }
1951 #endif // BMESH_TODO
1952
1953 /* makes displacement along grid boundary symmetrical */
1954 void multires_mdisp_smooth_bounds(MDisps *disps)
1955 {
1956         int x, y, side, S, corners;
1957         float (*out)[3];
1958
1959         corners = multires_mdisp_corners(disps);
1960         side = sqrt(disps->totdisp / corners);
1961
1962         out = disps->disps;
1963         for(S = 0; S < corners; S++) {
1964                 for(y = 0; y < side; ++y) {
1965                         for(x = 0; x < side; ++x, ++out) {
1966                                 float (*dispgrid)[3];
1967                                 float *data;
1968
1969                                 if(x != 0 && y != 0) continue;
1970
1971                                 if(corners == 4) {
1972                                         if(S == 0) {
1973                                                 if(y == 0) {
1974                                                         dispgrid = &disps->disps[1*side*side];
1975                                                         data = dispgrid[side * x + 0];
1976
1977                                                         (*out)[0] = (*out)[0] + data[1];
1978                                                         (*out)[1] = (*out)[1] - data[0];
1979                                                         (*out)[2] = (*out)[2] + data[2];
1980
1981                                                         mul_v3_fl(*out, 0.5);
1982
1983                                                         data[0] = -(*out)[1];
1984                                                         data[1] = (*out)[0];
1985                                                         data[2] = (*out)[2];
1986                                                 } else if (x == 0) {
1987                                                         dispgrid = &disps->disps[3 * side * side];
1988                                                         data = dispgrid[side * 0 + y];
1989
1990                                                         (*out)[0] = (*out)[0] - data[1];
1991                                                         (*out)[1] = (*out)[1] + data[0];
1992                                                         (*out)[2] = (*out)[2] + data[2];
1993
1994                                                         mul_v3_fl(*out, 0.5);
1995
1996                                                         data[0] = (*out)[1];
1997                                                         data[1] = -(*out)[0];
1998                                                         data[2] = (*out)[2];
1999                                                 }
2000                                         } else if (S == 2) {
2001                                                 if(y == 0) {
2002                                                         dispgrid = &disps->disps[3 * side * side];
2003                                                         data = dispgrid[side * x + 0];
2004
2005                                                         (*out)[0] = (*out)[0] + data[1];
2006                                                         (*out)[1] = (*out)[1] - data[0];
2007                                                         (*out)[2] = (*out)[2] + data[2];
2008
2009                                                         mul_v3_fl(*out, 0.5);
2010
2011                                                         data[0] = -(*out)[1];
2012                                                         data[1] = (*out)[0];
2013                                                         data[2] = (*out)[2];
2014                                                 } else if(x == 0) {
2015                                                         dispgrid = &disps->disps[1 * side * side];
2016                                                         data = dispgrid[side * 0 + y];
2017
2018                                                         (*out)[0] = (*out)[0] - data[1];
2019                                                         (*out)[1] = (*out)[1] + data[0];
2020                                                         (*out)[2] = (*out)[2] + data[2];
2021
2022                                                         mul_v3_fl(*out, 0.5);
2023
2024                                                         data[0] = (*out)[1];
2025                                                         data[1] = -(*out)[0];
2026                                                         data[2] = (*out)[2];
2027                                                 }
2028                                         }
2029                                 } else if (corners == 3) {
2030                                         if(S == 0) {
2031                                                 if(y == 0) {
2032                                                         dispgrid = &disps->disps[1*side*side];
2033                                                         data = dispgrid[side * x + 0];
2034
2035                                                         (*out)[0] = (*out)[0] + data[1];
2036                                                         (*out)[1] = (*out)[1] - data[0];
2037                                                         (*out)[2] = (*out)[2] + data[2];
2038
2039                                                         mul_v3_fl(*out, 0.5);
2040
2041                                                         data[0] = -(*out)[1];
2042                                                         data[1] = (*out)[0];
2043                                                         data[2] = (*out)[2];
2044                                                 } else if (x == 0) {
2045                                                         dispgrid = &disps->disps[2 * side * side];
2046                                                         data = dispgrid[side * 0 + y];
2047
2048                                                         (*out)[0] = (*out)[0] - data[1];
2049                                                         (*out)[1] = (*out)[1] + data[0];
2050                                                         (*out)[2] = (*out)[2] + data[2];
2051
2052                                                         mul_v3_fl(*out, 0.5);
2053
2054                                                         data[0] = (*out)[1];
2055                                                         data[1] = -(*out)[0];
2056                                                         data[2] = (*out)[2];
2057                                                 }
2058                                         } else if (S == 2) {
2059                                                 if(x == 0) {
2060                                                         dispgrid = &disps->disps[1 * side * side];
2061                                                         data = dispgrid[side * 0 + y];
2062
2063                                                         (*out)[0] = (*out)[0] - data[1];
2064                                                         (*out)[1] = (*out)[1] + data[0];
2065                                                         (*out)[2] = (*out)[2] + data[2];
2066
2067                                                         mul_v3_fl(*out, 0.5);
2068
2069                                                         data[0] = (*out)[1];
2070                                                         data[1] = -(*out)[0];
2071                                                         data[2] = (*out)[2];
2072                                                 }
2073                                         }
2074                                 }
2075                         }
2076                 }
2077         }
2078 }
2079
2080 /***************** Multires interpolation stuff *****************/
2081
2082 static void mdisp_get_crn_rect(int face_side, float crn[3][4][2])
2083 {
2084         float offset = face_side*0.5f - 0.5f;
2085         float mid[2];
2086
2087         mid[0] = offset * 4 / 3;
2088         mid[1] = offset * 2 / 3;
2089
2090         crn[0][0][0] = mid[0]; crn[0][0][1] = mid[1];
2091         crn[0][1][0] = offset; crn[0][1][1] = 0;
2092         crn[0][2][0] = 0; crn[0][2][1] = 0;
2093         crn[0][3][0] = offset; crn[0][3][1] = offset;
2094
2095         crn[1][0][0] = mid[0]; crn[1][0][1] = mid[1];
2096         crn[1][1][0] = offset * 2; crn[1][1][1] = offset;
2097         crn[1][2][0] = offset * 2; crn[1][2][1] = 0;
2098         crn[1][3][0] = offset; crn[1][3][1] = 0;
2099
2100         crn[2][0][0] = mid[0]; crn[2][0][1] = mid[1];
2101         crn[2][1][0] = offset; crn[2][1][1] = offset;
2102         crn[2][2][0] = offset * 2; crn[2][2][1] = offset * 2;
2103         crn[2][3][0] = offset * 2; crn[2][3][1] = offset;
2104 }
2105
2106 static int mdisp_pt_in_crn(float p[2], float crn[4][2])
2107 {
2108         float v[2][2];
2109         float a[2][2];
2110
2111         sub_v2_v2v2(v[0], crn[1], crn[0]);
2112         sub_v2_v2v2(v[1], crn[3], crn[0]);
2113
2114         sub_v2_v2v2(a[0], p, crn[0]);
2115         sub_v2_v2v2(a[1], crn[2], crn[0]);
2116
2117         if(cross_v2v2(a[0], v[0]) * cross_v2v2(a[1], v[0]) < 0)
2118                 return 0;
2119
2120         if(cross_v2v2(a[0], v[1]) * cross_v2v2(a[1], v[1]) < 0)
2121                 return 0;
2122
2123         return 1;
2124 }
2125
2126 static void face_to_crn_interp(float u, float v, float v1[2], float v2[2], float v3[2], float v4[2], float *x)
2127 {
2128         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];
2129         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];
2130         float c = (v3[1]-v)*v1[0]+(-v3[1]+v1[1])*u+v3[0]*v-v1[1]*v3[0];
2131         float d = b * b - 4 * a * c;
2132         float x1, x2;
2133
2134         if(a == 0) {
2135                 *x = -c / b;
2136                 return;
2137         }
2138
2139         x1 = (-b - sqrtf(d)) / (2 * a);
2140         x2 = (-b + sqrtf(d)) / (2 * a);
2141
2142         *x = maxf(x1, x2);
2143 }
2144
2145 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)
2146 {
2147         float offset = face_side*0.5f - 0.5f;
2148
2149         if(corners == 4) {
2150                 if(S == 1) { *u= offset + x; *v = offset - y; }
2151                 if(S == 2) { *u= offset + y; *v = offset + x; }
2152                 if(S == 3) { *u= offset - x; *v = offset + y; }
2153                 if(S == 0) { *u= offset - y; *v = offset - x; }
2154         } else {
2155                 float crn[3][4][2], vec[4][2];
2156                 float p[2];
2157
2158                 mdisp_get_crn_rect(face_side, crn);
2159
2160                 interp_v2_v2v2(vec[0], crn[S][0], crn[S][1], x / offset);
2161                 interp_v2_v2v2(vec[1], crn[S][3], crn[S][2], x / offset);
2162                 interp_v2_v2v2(vec[2], crn[S][0], crn[S][3], y / offset);
2163                 interp_v2_v2v2(vec[3], crn[S][1], crn[S][2], y / offset);
2164
2165                 isect_seg_seg_v2_point(vec[0], vec[1], vec[2], vec[3], p);
2166
2167                 (*u) = p[0];
2168                 (*v) = p[1];
2169         }
2170 }
2171
2172 /* Find per-corner coordinate with given per-face UV coord */
2173 int mdisp_rot_face_to_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2174 {
2175         const float offset = face_side*0.5f - 0.5f;
2176         int S = 0;
2177
2178         if (corners == 4) {
2179                 if(u <= offset && v <= offset) S = 0;
2180                 else if(u > offset  && v <= offset) S = 1;
2181                 else if(u > offset  && v > offset) S = 2;
2182                 else if(u <= offset && v >= offset)  S = 3;
2183
2184                 if(S == 0) {
2185                         *y = offset - u;
2186                         *x = offset - v;
2187                 } else if(S == 1) {
2188                         *x = u - offset;
2189                         *y = offset - v;
2190                 } else if(S == 2) {
2191                         *y = u - offset;
2192                         *x = v - offset;
2193                 } else if(S == 3) {
2194                         *x= offset - u;
2195                         *y = v - offset;
2196                 }
2197         } else {
2198                 int grid_size = offset;
2199                 float w = (face_side - 1) - u - v;
2200                 float W1, W2;
2201
2202                 if (u >= v && u >= w) {S = 0; W1= w; W2= v;}
2203                 else if (v >= u && v >= w) {S = 1; W1 = u; W2 = w;}
2204                 else {S = 2; W1 = v; W2 = u;}
2205
2206                 W1 /= (face_side-1);
2207                 W2 /= (face_side-1);
2208
2209                 *x = (1-(2*W1)/(1-W2)) * grid_size;
2210                 *y = (1-(2*W2)/(1-W1)) * grid_size;
2211         }
2212
2213         return S;
2214 }
2215
2216 /* Find per-corner coordinate with given per-face UV coord
2217    Practically as the previous funciton but it assumes a bit different coordinate system for triangles
2218    which is optimized for MDISP layer interpolation:
2219
2220    v
2221    ^
2222    |      /|
2223    |    /  |
2224    |  /    |
2225    |/______|___> u
2226
2227  */
2228 int mdisp_rot_face_to_quad_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2229 {
2230         const float offset = face_side*0.5f - 0.5f;
2231         int S = 0;
2232
2233         if (corners == 4) {
2234                 if(u <= offset && v <= offset) S = 0;
2235                 else if(u > offset  && v <= offset) S = 1;
2236                 else if(u > offset  && v > offset) S = 2;
2237                 else if(u <= offset && v >= offset)  S = 3;
2238
2239                 if(S == 0) {
2240                         *y = offset - u;
2241                         *x = offset - v;
2242                 } else if(S == 1) {
2243                         *x = u - offset;
2244                         *y = offset - v;
2245                 } else if(S == 2) {
2246                         *y = u - offset;
2247                         *x = v - offset;
2248                 } else if(S == 3) {
2249                         *x= offset - u;
2250                         *y = v - offset;
2251                 }
2252         } else {
2253                 float crn[3][4][2];
2254                 float p[2] = {u, v};
2255
2256                 mdisp_get_crn_rect(face_side, crn);
2257
2258                 for (S = 0; S < 3; ++S) {
2259                         if (mdisp_pt_in_crn(p, crn[S]))
2260                                 break;
2261                 }
2262
2263                 face_to_crn_interp(u, v, crn[S][0], crn[S][1], crn[S][3], crn[S][2], &p[0]);
2264                 face_to_crn_interp(u, v, crn[S][0], crn[S][3], crn[S][1], crn[S][2], &p[1]);
2265
2266                 *x = p[0] * offset;
2267                 *y = p[1] * offset;
2268         }
2269
2270         return S;
2271 }
2272
2273 void mdisp_apply_weight(const int S, const int corners, int x, int y, const int face_side,
2274         float crn_weight[4][2], float *u_r, float *v_r)
2275 {
2276         float u, v, xl, yl;
2277         float mid1[2], mid2[2], mid3[2];
2278
2279         mdisp_rot_crn_to_face(S, corners, face_side, x, y, &u, &v);
2280
2281         if(corners == 4) {
2282                 xl = u / (face_side - 1);
2283                 yl = v / (face_side - 1);
2284
2285                 mid1[0] = crn_weight[0][0] * (1 - xl) + crn_weight[1][0] * xl;
2286                 mid1[1] = crn_weight[0][1] * (1 - xl) + crn_weight[1][1] * xl;
2287                 mid2[0] = crn_weight[3][0] * (1 - xl) + crn_weight[2][0] * xl;
2288                 mid2[1] = crn_weight[3][1] * (1 - xl) + crn_weight[2][1] * xl;
2289                 mid3[0] = mid1[0] * (1 - yl) + mid2[0] * yl;
2290                 mid3[1] = mid1[1] * (1 - yl) + mid2[1] * yl;
2291         } else {
2292                 yl = v / (face_side - 1);
2293
2294                 if(v == face_side - 1) xl = 1;
2295                 else xl = 1 - (face_side - 1 - u) / (face_side - 1 - v);
2296
2297                 mid1[0] = crn_weight[0][0] * (1 - xl) + crn_weight[1][0] * xl;
2298                 mid1[1] = crn_weight[0][1] * (1 - xl) + crn_weight[1][1] * xl;
2299                 mid3[0] = mid1[0] * (1 - yl) + crn_weight[2][0] * yl;
2300                 mid3[1] = mid1[1] * (1 - yl) + crn_weight[2][1] * yl;
2301         }
2302
2303         *u_r = mid3[0];
2304         *v_r = mid3[1];
2305 }
2306
2307 void mdisp_flip_disp(const int S, const int corners, const float axis_x[2], const float axis_y[2], float disp[3])
2308 {
2309         float crn_x[2], crn_y[2];
2310         float vx[2], vy[2], coord[2];
2311
2312         if (corners == 4) {
2313                 float x[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
2314                 float y[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
2315
2316                 copy_v2_v2(crn_x, x[S]);
2317                 copy_v2_v2(crn_y, y[S]);
2318
2319                 mul_v2_v2fl(vx, crn_x, disp[0]);
2320                 mul_v2_v2fl(vy, crn_y, disp[1]);
2321                 add_v2_v2v2(coord, vx, vy);
2322
2323                 project_v2_v2v2(vx, coord, axis_x);
2324                 project_v2_v2v2(vy, coord, axis_y);
2325
2326                 disp[0] = len_v2(vx);
2327                 disp[1] = len_v2(vy);
2328
2329                 if(dot_v2v2(vx, axis_x) < 0)
2330                         disp[0] = -disp[0];
2331
2332                 if(dot_v2v2(vy, axis_y) < 0)
2333                         disp[1] = -disp[1];
2334         } else {
2335                 /* XXX: it was very overhead code to support displacement flipping
2336                         for case of tris without visible profit.
2337                         Maybe its not really big limitation? for now? (nazgul) */
2338                 disp[0] = 0;
2339                 disp[1] = 0;
2340         }
2341 }
2342
2343 /* Join two triangular displacements into one quad
2344          Corners mapping:
2345          2 -------- 3
2346          | \   tri2 |
2347          |    \     |
2348          | tri1  \  |
2349          0 -------- 1 */
2350 void mdisp_join_tris(MDisps *dst, MDisps *tri1, MDisps *tri2)
2351 {
2352         int side, st;
2353         int S, x, y, crn;
2354         float face_u, face_v, crn_u, crn_v;
2355         float (*out)[3];
2356         MDisps *src;
2357
2358         if(dst->disps)
2359                 BLI_cellalloc_free(dst->disps);
2360
2361         side = sqrt(tri1->totdisp / 3);
2362         st = (side<<1)-1;
2363
2364         dst->totdisp = 4 * side * side;
2365         out = dst->disps = BLI_cellalloc_calloc(3*dst->totdisp*sizeof(float), "join disps");
2366
2367         for(S = 0; S < 4; S++)
2368                 for(y = 0; y < side; ++y)
2369                         for(x = 0; x < side; ++x, ++out) {
2370                                 mdisp_rot_crn_to_face(S, 4, st, x, y, &face_u, &face_v);
2371                                 face_u = st - 1 - face_u;
2372
2373                                 if(face_v > face_u) {
2374                                         src = tri2;
2375                                         face_u = st - 1 - face_u;
2376                                         face_v = st - 1 - face_v;
2377                                 } else src = tri1;
2378
2379                                 crn = mdisp_rot_face_to_quad_crn(3, st, face_u, face_v, &crn_u, &crn_v);
2380
2381                                 old_mdisps_bilinear((*out), &src->disps[crn*side*side], side, crn_u, crn_v);
2382                                 (*out)[0] = 0;
2383                                 (*out)[1] = 0;
2384                         }
2385 }