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