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