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