5c13c2c52fe5fd6bbc030b201b3a902aa30d476d
[blender-staging.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, *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         ccgdm->needsFree = 1;
1036         ccgdm->release(ccgdm);
1037 }
1038
1039 void multires_stitch_grids(Object *ob)
1040 {
1041         /* utility for smooth brush */
1042         if(ob && ob->derivedFinal) {
1043                 CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)ob->derivedFinal;
1044                 CCGFace **faces;
1045                 int totface;
1046
1047                 if(ccgdm->pbvh) {
1048                         BLI_pbvh_get_grid_updates(ccgdm->pbvh, 0, (void***)&faces, &totface);
1049
1050                         if(totface) {
1051                                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, faces, totface);
1052                                 MEM_freeN(faces);
1053                         }
1054                 }
1055         }
1056 }
1057
1058 DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int local_mmd, DerivedMesh *dm, Object *ob,
1059                                                         int useRenderParams, int UNUSED(isFinalCalc))
1060 {
1061         Mesh *me= ob->data;
1062         DerivedMesh *result;
1063         CCGDerivedMesh *ccgdm;
1064         DMGridData **gridData, **subGridData;
1065         int lvl= multires_get_level(ob, mmd, useRenderParams);
1066         int i, gridSize, numGrids;
1067
1068         if(lvl == 0)
1069                 return dm;
1070
1071         result = subsurf_dm_create_local(ob, dm, lvl,
1072                 mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges,
1073                 mmd->flags & eMultiresModifierFlag_PlainUv);
1074
1075         if(!local_mmd) {
1076                 ccgdm = (CCGDerivedMesh*)result;
1077
1078                 ccgdm->multires.ob = ob;
1079                 ccgdm->multires.mmd = mmd;
1080                 ccgdm->multires.local_mmd = local_mmd;
1081                 ccgdm->multires.lvl = lvl;
1082                 ccgdm->multires.totlvl = mmd->totlvl;
1083                 ccgdm->multires.modified = 0;
1084                 ccgdm->multires.update = multiresModifier_update;
1085         }
1086
1087         numGrids = result->getNumGrids(result);
1088         gridSize = result->getGridSize(result);
1089         gridData = result->getGridData(result);
1090
1091         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
1092
1093         for(i = 0; i < numGrids; i++) {
1094                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*gridSize*gridSize, "subGridData");
1095                 memcpy(subGridData[i], gridData[i], sizeof(DMGridData)*gridSize*gridSize);
1096         }
1097
1098         multires_set_tot_mdisps(me, mmd->totlvl);
1099         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
1100
1101         /*run displacement*/
1102         multiresModifier_disp_run(result, ob->data, dm, 0, 0, subGridData, mmd->totlvl);
1103
1104         for(i = 0; i < numGrids; i++)
1105                 MEM_freeN(subGridData[i]);
1106         MEM_freeN(subGridData);
1107
1108         return result;
1109 }
1110
1111 /**** Old Multires code ****
1112 ***************************/
1113
1114 /* Adapted from sculptmode.c */
1115 void old_mdisps_bilinear(float out[3], float (*disps)[3], const int st, float u, float v)
1116 {
1117         int x, y, x2, y2;
1118         const int st_max = st - 1;
1119         float urat, vrat, uopp;
1120         float d[4][3], d2[2][3];
1121         
1122         if (!disps || isnan(u) || isnan(v))
1123                 return;
1124                         
1125         if(u < 0)
1126                 u = 0;
1127         else if(u >= st)
1128                 u = st_max;
1129         if(v < 0)
1130                 v = 0;
1131         else if(v >= st)
1132                 v = st_max;
1133
1134         x = floor(u);
1135         y = floor(v);
1136         x2 = x + 1;
1137         y2 = y + 1;
1138
1139         if(x2 >= st) x2 = st_max;
1140         if(y2 >= st) y2 = st_max;
1141         
1142         urat = u - x;
1143         vrat = v - y;
1144         uopp = 1 - urat;
1145
1146         mul_v3_v3fl(d[0], disps[y * st + x], uopp);
1147         mul_v3_v3fl(d[1], disps[y * st + x2], urat);
1148         mul_v3_v3fl(d[2], disps[y2 * st + x], uopp);
1149         mul_v3_v3fl(d[3], disps[y2 * st + x2], urat);
1150
1151         add_v3_v3v3(d2[0], d[0], d[1]);
1152         add_v3_v3v3(d2[1], d[2], d[3]);
1153         mul_v3_fl(d2[0], 1 - vrat);
1154         mul_v3_fl(d2[1], vrat);
1155
1156         add_v3_v3v3(out, d2[0], d2[1]);
1157 }
1158
1159 static void old_mdisps_rotate(int S, int UNUSED(newside), int oldside, int x, int y, float *u, float *v)
1160 {
1161         float offset = oldside*0.5f - 0.5f;
1162
1163         if(S == 1) { *u= offset + x; *v = offset - y; }
1164         if(S == 2) { *u= offset + y; *v = offset + x; }
1165         if(S == 3) { *u= offset - x; *v = offset + y; }
1166         if(S == 0) { *u= offset - y; *v = offset - x; }
1167 }
1168
1169 static void old_mdisps_convert(MFace *mface, MDisps *mdisp)
1170 {
1171         int newlvl = log(sqrt(mdisp->totdisp)-1)/M_LN2;
1172         int oldlvl = newlvl+1;
1173         int oldside = multires_side_tot[oldlvl];
1174         int newside = multires_side_tot[newlvl];
1175         int nvert = (mface->v4)? 4: 3;
1176         int newtotdisp = multires_grid_tot[newlvl]*nvert;
1177         int x, y, S;
1178         float (*disps)[3], (*out)[3], u = 0.0f, v = 0.0f; /* Quite gcc barking. */
1179
1180         disps = BLI_cellalloc_calloc(sizeof(float) * 3 * newtotdisp, "multires disps");
1181
1182         out = disps;
1183         for(S = 0; S < nvert; S++) {
1184                 for(y = 0; y < newside; ++y) {
1185                         for(x = 0; x < newside; ++x, ++out) {
1186                                 old_mdisps_rotate(S, newside, oldside, x, y, &u, &v);
1187                                 old_mdisps_bilinear(*out, mdisp->disps, oldside, u, v);
1188
1189                                 if(S == 1) { (*out)[1]= -(*out)[1]; }
1190                                 else if(S == 2) { SWAP(float, (*out)[0], (*out)[1]); }
1191                                 else if(S == 3) { (*out)[0]= -(*out)[0]; }
1192                                 else if(S == 0) { SWAP(float, (*out)[0], (*out)[1]); (*out)[0]= -(*out)[0]; (*out)[1]= -(*out)[1]; };
1193                         }
1194                 }
1195         }
1196
1197         BLI_cellalloc_free(mdisp->disps);
1198
1199         mdisp->totdisp= newtotdisp;
1200         mdisp->disps= disps;
1201 }
1202
1203 void multires_load_old_250(Mesh *me)
1204 {
1205         MDisps *mdisps, *mdisps2;
1206         MFace *mf;
1207         int i, j, k;
1208
1209         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
1210
1211         if(mdisps) {
1212                 for(i=0; i<me->totface; i++)
1213                         if(mdisps[i].totdisp)
1214                                 old_mdisps_convert(&me->mface[i], &mdisps[i]);
1215                 
1216                 CustomData_add_layer(&me->ldata, CD_MDISPS, CD_CALLOC, NULL, me->totloop);
1217                 mdisps2 = CustomData_get_layer(&me->ldata, CD_MDISPS);
1218
1219                 k = 0;
1220                 mf = me->mface;
1221                 for (i=0; i<me->totface; i++, mf++) {
1222                         int nvert = mf->v4 ? 4 : 3;
1223                         int totdisp = mdisps[i].totdisp / nvert;
1224                         
1225                         for (j=0; j < mf->v4 ? 4 : 3; j++, k++) {
1226                                 mdisps2[k].disps = BLI_cellalloc_calloc(sizeof(float)*3*totdisp, "multires disp in conversion");                        
1227                                 mdisps2[k].totdisp = totdisp;
1228                                 memcpy(mdisps2[k].disps, mdisps[i].disps + totdisp*j, totdisp);
1229                         }
1230
1231                 }
1232         }
1233 }
1234
1235 /* Does not actually free lvl itself */
1236 static void multires_free_level(MultiresLevel *lvl)
1237 {
1238         if(lvl) {
1239                 if(lvl->faces) MEM_freeN(lvl->faces);
1240                 if(lvl->edges) MEM_freeN(lvl->edges);
1241                 if(lvl->colfaces) MEM_freeN(lvl->colfaces);
1242         }
1243 }
1244
1245 void multires_free(Multires *mr)
1246 {
1247         if(mr) {
1248                 MultiresLevel* lvl= mr->levels.first;
1249
1250                 /* Free the first-level data */
1251                 if(lvl) {
1252                         CustomData_free(&mr->vdata, lvl->totvert);
1253                         CustomData_free(&mr->fdata, lvl->totface);
1254                         if(mr->edge_flags)
1255                                 MEM_freeN(mr->edge_flags);
1256                         if(mr->edge_creases)
1257                                 MEM_freeN(mr->edge_creases);
1258                 }
1259
1260                 while(lvl) {
1261                         multires_free_level(lvl);                       
1262                         lvl= lvl->next;
1263                 }
1264
1265                 MEM_freeN(mr->verts);
1266
1267                 BLI_freelistN(&mr->levels);
1268
1269                 MEM_freeN(mr);
1270         }
1271 }
1272
1273 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
1274                                          const int totvert, const int totface)
1275 {
1276         int i,j;
1277         IndexNode *node = NULL;
1278         
1279         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
1280         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
1281         node = *mem;
1282         
1283         /* Find the users */
1284         for(i = 0; i < totface; ++i){
1285                 for(j = 0; j < (mface[i].v[3]?4:3); ++j, ++node) {
1286                         node->index = i;
1287                         BLI_addtail(&(*map)[mface[i].v[j]], node);
1288                 }
1289         }
1290 }
1291
1292 static void create_old_vert_edge_map(ListBase **map, IndexNode **mem, const MultiresEdge *medge,
1293                                          const int totvert, const int totedge)
1294 {
1295         int i,j;
1296         IndexNode *node = NULL;
1297         
1298         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
1299         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge*2, "vert edge map mem");
1300         node = *mem;
1301         
1302         /* Find the users */
1303         for(i = 0; i < totedge; ++i){
1304                 for(j = 0; j < 2; ++j, ++node) {
1305                         node->index = i;
1306                         BLI_addtail(&(*map)[medge[i].v[j]], node);
1307                 }
1308         }
1309 }
1310
1311 static MultiresFace *find_old_face(ListBase *map, MultiresFace *faces, int v1, int v2, int v3, int v4)
1312 {
1313         IndexNode *n1;
1314         int v[4], i, j;
1315
1316         v[0]= v1;
1317         v[1]= v2;
1318         v[2]= v3;
1319         v[3]= v4;
1320
1321         for(n1 = map[v1].first; n1; n1 = n1->next) {
1322                 int fnd[4] = {0, 0, 0, 0};
1323
1324                 for(i = 0; i < 4; ++i) {
1325                         for(j = 0; j < 4; ++j) {
1326                                 if(v[i] == faces[n1->index].v[j])
1327                                         fnd[i] = 1;
1328                         }
1329                 }
1330
1331                 if(fnd[0] && fnd[1] && fnd[2] && fnd[3])
1332                         return &faces[n1->index];
1333         }
1334
1335         return NULL;
1336 }
1337
1338 static MultiresEdge *find_old_edge(ListBase *map, MultiresEdge *edges, int v1, int v2)
1339 {
1340         IndexNode *n1, *n2;
1341
1342         for(n1 = map[v1].first; n1; n1 = n1->next) {
1343                 for(n2 = map[v2].first; n2; n2 = n2->next) {
1344                         if(n1->index == n2->index)
1345                                 return &edges[n1->index];
1346                 }
1347         }
1348
1349         return NULL;
1350 }
1351
1352 static void multires_load_old_edges(ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst, int v1, int v2, int mov)
1353 {
1354         int emid = find_old_edge(emap[2], lvl->edges, v1, v2)->mid;
1355         vvmap[dst + mov] = emid;
1356
1357         if(lvl->next->next) {
1358                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v1, emid, mov / 2);
1359                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v2, emid, -mov / 2);
1360         }
1361 }
1362
1363 static void multires_load_old_faces(ListBase **fmap, ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst,
1364                                         int v1, int v2, int v3, int v4, int st2, int st3)
1365 {
1366         int fmid;
1367         int emid13, emid14, emid23, emid24;
1368
1369         if(lvl && lvl->next) {
1370                 fmid = find_old_face(fmap[1], lvl->faces, v1, v2, v3, v4)->mid;
1371                 vvmap[dst] = fmid;
1372
1373                 emid13 = find_old_edge(emap[1], lvl->edges, v1, v3)->mid;
1374                 emid14 = find_old_edge(emap[1], lvl->edges, v1, v4)->mid;
1375                 emid23 = find_old_edge(emap[1], lvl->edges, v2, v3)->mid;
1376                 emid24 = find_old_edge(emap[1], lvl->edges, v2, v4)->mid;
1377
1378
1379                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 + st3,
1380                                         fmid, v2, emid23, emid24, st2, st3 / 2);
1381
1382                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 + st3,
1383                                         emid14, emid24, fmid, v4, st2, st3 / 2);
1384
1385                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 - st3,
1386                                         emid13, emid23, v3, fmid, st2, st3 / 2);
1387
1388                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 - st3,
1389                                         v1, fmid, emid13, emid14, st2, st3 / 2);
1390
1391                 if(lvl->next->next) {
1392                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid24, fmid, st3);
1393                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid13, fmid, -st3);
1394                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid14, fmid, -st2 * st3);
1395                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid23, fmid, st2 * st3);
1396                 }
1397         }
1398 }
1399
1400 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert)
1401 {
1402         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*) dm;
1403         CCGSubSurf *ss = ccgdm->ss;
1404         DMGridData *vd;
1405         int index;
1406         int totvert, totedge, totface;
1407         int gridSize = ccgSubSurf_getGridSize(ss);
1408         int edgeSize = ccgSubSurf_getEdgeSize(ss);
1409         int i = 0;
1410
1411         totface = ccgSubSurf_getNumFaces(ss);
1412         for(index = 0; index < totface; index++) {
1413                 CCGFace *f = ccgdm->faceMap[index].face;
1414                 int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1415
1416                 vd= ccgSubSurf_getFaceCenterData(f);
1417                 copy_v3_v3(vd->co, mvert[i].co);
1418                 i++;
1419                 
1420                 for(S = 0; S < numVerts; S++) {
1421                         for(x = 1; x < gridSize - 1; x++, i++) {
1422                                 vd= ccgSubSurf_getFaceGridEdgeData(ss, f, S, x);
1423                                 copy_v3_v3(vd->co, mvert[i].co);
1424                         }
1425                 }
1426
1427                 for(S = 0; S < numVerts; S++) {
1428                         for(y = 1; y < gridSize - 1; y++) {
1429                                 for(x = 1; x < gridSize - 1; x++, i++) {
1430                                         vd= ccgSubSurf_getFaceGridData(ss, f, S, x, y);
1431                                         copy_v3_v3(vd->co, mvert[i].co);
1432                                 }
1433                         }
1434                 }
1435         }
1436
1437         totedge = ccgSubSurf_getNumEdges(ss);
1438         for(index = 0; index < totedge; index++) {
1439                 CCGEdge *e = ccgdm->edgeMap[index].edge;
1440                 int x;
1441
1442                 for(x = 1; x < edgeSize - 1; x++, i++) {
1443                         vd= ccgSubSurf_getEdgeData(ss, e, x);
1444                         copy_v3_v3(vd->co, mvert[i].co);
1445                 }
1446         }
1447
1448         totvert = ccgSubSurf_getNumVerts(ss);
1449         for(index = 0; index < totvert; index++) {
1450                 CCGVert *v = ccgdm->vertMap[index].vert;
1451
1452                 vd= ccgSubSurf_getVertData(ss, v);
1453                 copy_v3_v3(vd->co, mvert[i].co);
1454                 i++;
1455         }
1456
1457         ccgSubSurf_updateToFaces(ss, 0, NULL, 0);
1458 }
1459
1460 /* Loads a multires object stored in the old Multires struct into the new format */
1461 static void multires_load_old_dm(DerivedMesh *dm, Mesh *me, int totlvl)
1462 {
1463         MultiresLevel *lvl, *lvl1;
1464         Multires *mr= me->mr;
1465         MVert *vsrc, *vdst;
1466         unsigned int src, dst;
1467         int st = multires_side_tot[totlvl - 1] - 1;
1468         int extedgelen = multires_side_tot[totlvl] - 2;
1469         int *vvmap; // inorder for dst, map to src
1470         int crossedgelen;
1471         int s, x, tottri, totquad;
1472         unsigned int i, j, totvert;
1473
1474         src = 0;
1475         vsrc = mr->verts;
1476         vdst = dm->getVertArray(dm);
1477         totvert = (unsigned int)dm->getNumVerts(dm);
1478         vvmap = MEM_callocN(sizeof(int) * totvert, "multires vvmap");
1479
1480         lvl1 = mr->levels.first;
1481         /* Load base verts */
1482         for(i = 0; i < lvl1->totvert; ++i) {
1483                 vvmap[totvert - lvl1->totvert + i] = src;
1484                 ++src;
1485         }
1486
1487         /* Original edges */
1488         dst = totvert - lvl1->totvert - extedgelen * lvl1->totedge;
1489         for(i = 0; i < lvl1->totedge; ++i) {
1490                 int ldst = dst + extedgelen * i;
1491                 int lsrc = src;
1492                 lvl = lvl1->next;
1493
1494                 for(j = 2; j <= mr->level_count; ++j) {
1495                         int base = multires_side_tot[totlvl - j + 1] - 2;
1496                         int skip = multires_side_tot[totlvl - j + 2] - 1;
1497                         int st = multires_side_tot[j - 1] - 1;
1498
1499                         for(x = 0; x < st; ++x)
1500                                 vvmap[ldst + base + x * skip] = lsrc + st * i + x;
1501
1502                         lsrc += lvl->totvert - lvl->prev->totvert;
1503                         lvl = lvl->next;
1504                 }
1505         }
1506
1507         /* Center points */
1508         dst = 0;
1509         for(i = 0; i < lvl1->totface; ++i) {
1510                 int sides = lvl1->faces[i].v[3] ? 4 : 3;
1511
1512                 vvmap[dst] = src + lvl1->totedge + i;
1513                 dst += 1 + sides * (st - 1) * st;
1514         }
1515
1516
1517         /* The rest is only for level 3 and up */
1518         if(lvl1->next && lvl1->next->next) {
1519                 ListBase **fmap, **emap;
1520                 IndexNode **fmem, **emem;
1521
1522                 /* Face edge cross */
1523                 tottri = totquad = 0;
1524                 crossedgelen = multires_side_tot[totlvl - 1] - 2;
1525                 dst = 0;
1526                 for(i = 0; i < lvl1->totface; ++i) {
1527                         int sides = lvl1->faces[i].v[3] ? 4 : 3;
1528
1529                         lvl = lvl1->next->next;
1530                         ++dst;
1531
1532                         for(j = 3; j <= mr->level_count; ++j) {
1533                                 int base = multires_side_tot[totlvl - j + 1] - 2;
1534                                 int skip = multires_side_tot[totlvl - j + 2] - 1;
1535                                 int st = pow(2, j - 2);
1536                                 int st2 = pow(2, j - 3);
1537                                 int lsrc = lvl->prev->totvert;
1538
1539                                 /* Skip exterior edge verts */
1540                                 lsrc += lvl1->totedge * st;
1541
1542                                 /* Skip earlier face edge crosses */
1543                                 lsrc += st2 * (tottri * 3 + totquad * 4);
1544
1545                                 for(s = 0; s < sides; ++s) {
1546                                         for(x = 0; x < st2; ++x) {
1547                                                 vvmap[dst + crossedgelen * (s + 1) - base - x * skip - 1] = lsrc;
1548                                                 ++lsrc;
1549                                         }
1550                                 }
1551
1552                                 lvl = lvl->next;
1553                         }
1554
1555                         dst += sides * (st - 1) * st;
1556
1557                         if(sides == 4) ++totquad;
1558                         else ++tottri;
1559
1560                 }
1561
1562                 /* calculate vert to edge/face maps for each level (except the last) */
1563                 fmap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires fmap");
1564                 emap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires emap");
1565                 fmem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires fmem");
1566                 emem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires emem");
1567                 lvl = lvl1;
1568                 for(i = 0; i < (unsigned int)mr->level_count - 1; ++i) {
1569                         create_old_vert_face_map(fmap + i, fmem + i, lvl->faces, lvl->totvert, lvl->totface);
1570                         create_old_vert_edge_map(emap + i, emem + i, lvl->edges, lvl->totvert, lvl->totedge);
1571                         lvl = lvl->next;
1572                 }
1573
1574                 /* Interior face verts */
1575                 /* lvl = lvl1->next->next; */ /* UNUSED */
1576                 dst = 0;
1577                 for(j = 0; j < lvl1->totface; ++j) {
1578                         int sides = lvl1->faces[j].v[3] ? 4 : 3;
1579                         int ldst = dst + 1 + sides * (st - 1);
1580
1581                         for(s = 0; s < sides; ++s) {
1582                                 int st2 = multires_side_tot[totlvl - 1] - 2;
1583                                 int st3 = multires_side_tot[totlvl - 2] - 2;
1584                                 int st4 = st3 == 0 ? 1 : (st3 + 1) / 2;
1585                                 int mid = ldst + st2 * st3 + st3;
1586                                 int cv = lvl1->faces[j].v[s];
1587                                 int nv = lvl1->faces[j].v[s == sides - 1 ? 0 : s + 1];
1588                                 int pv = lvl1->faces[j].v[s == 0 ? sides - 1 : s - 1];
1589
1590                                 multires_load_old_faces(fmap, emap, lvl1->next, vvmap, mid,
1591                                                         vvmap[dst], cv,
1592                                                         find_old_edge(emap[0], lvl1->edges, pv, cv)->mid,
1593                                                         find_old_edge(emap[0], lvl1->edges, cv, nv)->mid,
1594                                                         st2, st4);
1595
1596                                 ldst += (st - 1) * (st - 1);
1597                         }
1598
1599
1600                         dst = ldst;
1601                 }
1602
1603                 /*lvl = lvl->next;*/ /*UNUSED*/
1604
1605                 for(i = 0; i < (unsigned int)(mr->level_count - 1); ++i) {
1606                         MEM_freeN(fmap[i]);
1607                         MEM_freeN(fmem[i]);
1608                         MEM_freeN(emap[i]);
1609                         MEM_freeN(emem[i]);
1610                 }
1611
1612                 MEM_freeN(fmap);
1613                 MEM_freeN(emap);
1614                 MEM_freeN(fmem);
1615                 MEM_freeN(emem);
1616         }
1617
1618         /* Transfer verts */
1619         for(i = 0; i < totvert; ++i)
1620                 copy_v3_v3(vdst[i].co, vsrc[vvmap[i]].co);
1621
1622         MEM_freeN(vvmap);
1623
1624         multires_mvert_to_ss(dm, vdst);
1625 }
1626
1627 /* Copy the first-level vcol data to the mesh, if it exists */
1628 /* Warning: higher-level vcol data will be lost */
1629 static void multires_load_old_vcols(Mesh *me)
1630 {
1631         MultiresLevel *lvl;
1632         MultiresColFace *colface;
1633         MCol *mcol;
1634         int i, j;
1635
1636         if(!(lvl = me->mr->levels.first))
1637                 return;
1638
1639         if(!(colface = lvl->colfaces))
1640                 return;
1641
1642         /* older multires format never supported multiple vcol layers,
1643            so we can assume the active vcol layer is the correct one */
1644         if(!(mcol = CustomData_get_layer(&me->fdata, CD_MCOL)))
1645                 return;
1646         
1647         for(i = 0; i < me->totface; ++i) {
1648                 for(j = 0; j < 4; ++j) {
1649                         mcol[i*4 + j].a = colface[i].col[j].a;
1650                         mcol[i*4 + j].r = colface[i].col[j].r;
1651                         mcol[i*4 + j].g = colface[i].col[j].g;
1652                         mcol[i*4 + j].b = colface[i].col[j].b;
1653                 }
1654         }
1655 }
1656
1657 /* Copy the first-level face-flag data to the mesh */
1658 static void multires_load_old_face_flags(Mesh *me)
1659 {
1660         MultiresLevel *lvl;
1661         MultiresFace *faces;
1662         int i;
1663
1664         if(!(lvl = me->mr->levels.first))
1665                 return;
1666
1667         if(!(faces = lvl->faces))
1668                 return;
1669
1670         for(i = 0; i < me->totface; ++i)
1671                 me->mface[i].flag = faces[i].flag;
1672 }
1673
1674 void multires_load_old(Object *ob, Mesh *me)
1675 {
1676         MultiresLevel *lvl;
1677         ModifierData *md;
1678         MultiresModifierData *mmd;
1679         DerivedMesh *dm, *orig;
1680         CustomDataLayer *l;
1681         int i;
1682
1683         /* Load original level into the mesh */
1684         lvl = me->mr->levels.first;
1685         CustomData_free_layers(&me->vdata, CD_MVERT, lvl->totvert);
1686         CustomData_free_layers(&me->edata, CD_MEDGE, lvl->totedge);
1687         CustomData_free_layers(&me->fdata, CD_MFACE, lvl->totface);
1688         me->totvert = lvl->totvert;
1689         me->totedge = lvl->totedge;
1690         me->totface = lvl->totface;
1691         me->mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
1692         me->medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
1693         me->mface = CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
1694         memcpy(me->mvert, me->mr->verts, sizeof(MVert) * me->totvert);
1695         for(i = 0; i < me->totedge; ++i) {
1696                 me->medge[i].v1 = lvl->edges[i].v[0];
1697                 me->medge[i].v2 = lvl->edges[i].v[1];
1698         }
1699         for(i = 0; i < me->totface; ++i) {
1700                 me->mface[i].v1 = lvl->faces[i].v[0];
1701                 me->mface[i].v2 = lvl->faces[i].v[1];
1702                 me->mface[i].v3 = lvl->faces[i].v[2];
1703                 me->mface[i].v4 = lvl->faces[i].v[3];
1704                 me->mface[i].mat_nr = lvl->faces[i].mat_nr;
1705         }
1706
1707         /* Add a multires modifier to the object */
1708         md = ob->modifiers.first;
1709         while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
1710                 md = md->next;                          
1711         mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
1712         BLI_insertlinkbefore(&ob->modifiers, md, mmd);
1713
1714         for(i = 0; i < me->mr->level_count - 1; ++i)
1715                 multiresModifier_subdivide(mmd, ob, 1, 0);
1716
1717         mmd->lvl = mmd->totlvl;
1718         orig = CDDM_from_mesh(me, NULL);
1719         dm = multires_dm_create_from_derived(mmd, 0, orig, ob, 0, 0);
1720                                            
1721         multires_load_old_dm(dm, me, mmd->totlvl+1);
1722
1723         multires_dm_mark_as_modified(dm);
1724         dm->release(dm);
1725         orig->release(orig);
1726
1727         /* Copy the first-level data to the mesh */
1728         for(i = 0, l = me->mr->vdata.layers; i < me->mr->vdata.totlayer; ++i, ++l)
1729                 CustomData_add_layer(&me->vdata, l->type, CD_REFERENCE, l->data, me->totvert);
1730         for(i = 0, l = me->mr->fdata.layers; i < me->mr->fdata.totlayer; ++i, ++l)
1731                 CustomData_add_layer(&me->fdata, l->type, CD_REFERENCE, l->data, me->totface);
1732         memset(&me->mr->vdata, 0, sizeof(CustomData));
1733         memset(&me->mr->fdata, 0, sizeof(CustomData));
1734
1735         multires_load_old_vcols(me);
1736         multires_load_old_face_flags(me);
1737
1738         /* Remove the old multires */
1739         multires_free(me->mr);
1740         me->mr= NULL;
1741 }
1742
1743 static void multires_sync_levels(Scene *scene, Object *ob, Object *to_ob)
1744 {
1745         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1746         MultiresModifierData *to_mmd= get_multires_modifier(scene, to_ob, 1);
1747
1748         if(!mmd) {
1749                 /* object could have MDISP even when there is no multires modifier
1750                    this could lead to troubles due to i've got no idea how mdisp could be
1751                    upsampled correct without modifier data.
1752                    just remove mdisps if no multires present (nazgul) */
1753
1754                 Mesh *me= (Mesh*)ob->data;
1755
1756                 CustomData_external_remove(&me->ldata, &me->id, CD_MDISPS, me->totloop);
1757                 CustomData_free_layer_active(&me->ldata, CD_MDISPS, me->totloop);
1758         }
1759
1760         if(!mmd || !to_mmd) return;
1761
1762         if(mmd->totlvl>to_mmd->totlvl) multires_del_higher(mmd, ob, to_mmd->totlvl);
1763         else multires_subdivide(mmd, ob, to_mmd->totlvl, 0, mmd->simple);
1764 }
1765
1766 static void multires_apply_smat(Scene *scene, Object *ob, float smat[3][3])
1767 {
1768         DerivedMesh *dm= NULL, *cddm= NULL, *subdm= NULL;
1769         DMGridData **gridData, **subGridData;
1770         Mesh *me= (Mesh*)ob->data;
1771         MPoly *mpoly= me->mpoly;
1772         /* MLoop *mloop = me->mloop; */ /* UNUSED */
1773         MDisps *mdisps;
1774         int *gridOffset;
1775         int i, /*numGrids,*/ gridSize, dGridSize, dSkip, totvert;
1776         float (*vertCos)[3] = NULL;
1777         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1778         MultiresModifierData high_mmd;
1779
1780         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
1781         mdisps= CustomData_get_layer(&me->ldata, CD_MDISPS);
1782
1783         if(!mdisps || !mmd || !mmd->totlvl) return;
1784
1785         /* we need derived mesh created from highest resolution */
1786         high_mmd= *mmd;
1787         high_mmd.lvl= high_mmd.totlvl;
1788
1789         /* unscaled multires with applied displacement */
1790         subdm= get_multires_dm(scene, &high_mmd, ob);
1791
1792         /* prepare scaled CDDM to create ccgDN */
1793         cddm= mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
1794
1795         totvert= cddm->getNumVerts(cddm);
1796         vertCos= MEM_mallocN(sizeof(*vertCos) * totvert, "multiresScale vertCos");
1797         cddm->getVertCos(cddm, vertCos);
1798         for(i=0; i<totvert; i++)
1799                 mul_m3_v3(smat, vertCos[i]);
1800         CDDM_apply_vert_coords(cddm, vertCos);
1801         MEM_freeN(vertCos);
1802
1803         /* scaled ccgDM for tangent space of object with applied scale */
1804         dm= subsurf_dm_create_local(ob, cddm, high_mmd.totlvl, high_mmd.simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
1805         cddm->release(cddm);
1806
1807         /*numGrids= dm->getNumGrids(dm);*/ /*UNUSED*/
1808         gridSize= dm->getGridSize(dm);
1809         gridData= dm->getGridData(dm);
1810         gridOffset= dm->getGridOffset(dm);
1811         subGridData= subdm->getGridData(subdm);
1812
1813         dGridSize= multires_side_tot[high_mmd.totlvl];
1814         dSkip= (dGridSize-1)/(gridSize-1);
1815
1816         #pragma omp parallel for private(i) if(me->totface*gridSize*gridSize*4 >= CCG_OMP_LIMIT)
1817         for(i = 0; i < me->totpoly; ++i) {
1818                 const int numVerts= mpoly[i].totloop;
1819                 MDisps *mdisp= &mdisps[mpoly[i].loopstart];
1820                 int S, x, y, gIndex = gridOffset[i];
1821
1822                 for(S = 0; S < numVerts; ++S, ++gIndex, mdisp++) {
1823                         DMGridData *grid= gridData[gIndex];
1824                         DMGridData *subgrid= subGridData[gIndex];
1825                         float (*dispgrid)[3]= mdisp->disps;
1826
1827                         for(y = 0; y < gridSize; y++) {
1828                                 for(x = 0; x < gridSize; x++) {
1829                                         float *co= grid[x + y*gridSize].co;
1830                                         float *sco= subgrid[x + y*gridSize].co;
1831                                         float *no= grid[x + y*gridSize].no;
1832                                         float *data= dispgrid[dGridSize*y*dSkip + x*dSkip];
1833                                         float mat[3][3], tx[3], ty[3], disp[3];
1834
1835                                         /* construct tangent space matrix */
1836                                         grid_tangent(gridSize, gIndex, x, y, 0, gridData, tx);
1837                                         normalize_v3(tx);
1838
1839                                         grid_tangent(gridSize, gIndex, x, y, 1, gridData, ty);
1840                                         normalize_v3(ty);
1841
1842                                         column_vectors_to_mat3(mat, tx, ty, no);
1843
1844                                         /* scale subgrid coord and calculate displacement */
1845                                         mul_m3_v3(smat, sco);
1846                                         sub_v3_v3v3(disp, sco, co);
1847
1848                                         /* convert difference to tangent space */
1849                                         invert_m3(mat);
1850                                         mul_v3_m3v3(data, mat, disp);
1851                                 }
1852                         }
1853                 }
1854         }
1855
1856         dm->release(dm);
1857         subdm->release(subdm);
1858 }
1859
1860 int multires_mdisp_corners(MDisps *s)
1861 {
1862         int lvl= 13;
1863
1864         while(lvl > 0) {
1865                 int side = (1 << (lvl-1)) + 1;
1866                 if ((s->totdisp % (side*side)) == 0) return s->totdisp / (side*side);
1867                 lvl--;
1868         }
1869
1870         return 0;
1871 }
1872
1873 void multiresModifier_scale_disp(Scene *scene, Object *ob)
1874 {
1875         float smat[3][3];
1876
1877         /* object's scale matrix */
1878         object_scale_to_mat3(ob, smat);
1879
1880         multires_apply_smat(scene, ob, smat);
1881 }
1882
1883 void multiresModifier_prepare_join(Scene *scene, Object *ob, Object *to_ob)
1884 {
1885         float smat[3][3], tmat[3][3], mat[3][3];
1886         multires_sync_levels(scene, ob, to_ob);
1887
1888         /* construct scale matrix for displacement */
1889         object_scale_to_mat3(to_ob, tmat);
1890         invert_m3(tmat);
1891         object_scale_to_mat3(ob, smat);
1892         mul_m3_m3m3(mat, smat, tmat);
1893
1894         multires_apply_smat(scene, ob, mat);
1895 }
1896
1897 /* update multires data after topology changing */
1898 #if 0 // BMESH_TODO
1899 void multires_topology_changed(Scene *scene, Object *ob)
1900 {
1901         Mesh *me= (Mesh*)ob->data;
1902         MDisps *mdisp= NULL, *cur= NULL;
1903         int i, grid= 0, corners;
1904         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1905
1906         if(mmd)
1907                 multires_set_tot_mdisps(me, mmd->totlvl);
1908
1909         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
1910         mdisp= CustomData_get_layer(&me->fdata, CD_MDISPS);
1911
1912         if(!mdisp) return;
1913
1914         cur= mdisp;
1915         for(i = 0; i < me->totface; i++, cur++) {
1916                 if(mdisp->totdisp) {
1917                         corners= multires_mdisp_corners(mdisp);
1918                         grid= mdisp->totdisp / corners;
1919
1920                         break;
1921                 }
1922         }
1923
1924         for(i = 0; i < me->totface; i++, mdisp++) {
1925                 int nvert= me->mface[i].v4 ? 4 : 3;
1926
1927                 /* allocate memory for mdisp, the whole disp layer would be erased otherwise */
1928                 if(!mdisp->totdisp || !mdisp->disps) {
1929                         if(grid) {
1930                                 mdisp->totdisp= nvert*grid;
1931                                 mdisp->disps= MEM_callocN(mdisp->totdisp*sizeof(float)*3, "mdisp topology");
1932                         }
1933
1934                         continue;
1935                 }
1936
1937                 corners= multires_mdisp_corners(mdisp);
1938
1939                 if(corners!=nvert) {
1940                         mdisp->totdisp= (mdisp->totdisp/corners)*nvert;
1941
1942                         if(mdisp->disps)
1943                                 MEM_freeN(mdisp->disps);
1944
1945                         mdisp->disps= MEM_callocN(mdisp->totdisp*sizeof(float)*3, "mdisp topology");
1946                 }
1947         }
1948 }
1949 #endif // BMESH_TODO
1950
1951 /* makes displacement along grid boundary symmetrical */
1952 void multires_mdisp_smooth_bounds(MDisps *disps)
1953 {
1954         int x, y, side, S, corners;
1955         float (*out)[3];
1956
1957         corners = multires_mdisp_corners(disps);
1958         side = sqrt(disps->totdisp / corners);
1959
1960         out = disps->disps;
1961         for(S = 0; S < corners; S++) {
1962                 for(y = 0; y < side; ++y) {
1963                         for(x = 0; x < side; ++x, ++out) {
1964                                 float (*dispgrid)[3];
1965                                 float *data;
1966
1967                                 if(x != 0 && y != 0) continue;
1968
1969                                 if(corners == 4) {
1970                                         if(S == 0) {
1971                                                 if(y == 0) {
1972                                                         dispgrid = &disps->disps[1*side*side];
1973                                                         data = dispgrid[side * x + 0];
1974
1975                                                         (*out)[0] = (*out)[0] + data[1];
1976                                                         (*out)[1] = (*out)[1] - data[0];
1977                                                         (*out)[2] = (*out)[2] + data[2];
1978
1979                                                         mul_v3_fl(*out, 0.5);
1980
1981                                                         data[0] = -(*out)[1];
1982                                                         data[1] = (*out)[0];
1983                                                         data[2] = (*out)[2];
1984                                                 } else if (x == 0) {
1985                                                         dispgrid = &disps->disps[3 * side * side];
1986                                                         data = dispgrid[side * 0 + y];
1987
1988                                                         (*out)[0] = (*out)[0] - data[1];
1989                                                         (*out)[1] = (*out)[1] + data[0];
1990                                                         (*out)[2] = (*out)[2] + data[2];
1991
1992                                                         mul_v3_fl(*out, 0.5);
1993
1994                                                         data[0] = (*out)[1];
1995                                                         data[1] = -(*out)[0];
1996                                                         data[2] = (*out)[2];
1997                                                 }
1998                                         } else if (S == 2) {
1999                                                 if(y == 0) {
2000                                                         dispgrid = &disps->disps[3 * side * side];
2001                                                         data = dispgrid[side * x + 0];
2002
2003                                                         (*out)[0] = (*out)[0] + data[1];
2004                                                         (*out)[1] = (*out)[1] - data[0];
2005                                                         (*out)[2] = (*out)[2] + data[2];
2006
2007                                                         mul_v3_fl(*out, 0.5);
2008
2009                                                         data[0] = -(*out)[1];
2010                                                         data[1] = (*out)[0];
2011                                                         data[2] = (*out)[2];
2012                                                 } else if(x == 0) {
2013                                                         dispgrid = &disps->disps[1 * side * side];
2014                                                         data = dispgrid[side * 0 + y];
2015
2016                                                         (*out)[0] = (*out)[0] - data[1];
2017                                                         (*out)[1] = (*out)[1] + data[0];
2018                                                         (*out)[2] = (*out)[2] + data[2];
2019
2020                                                         mul_v3_fl(*out, 0.5);
2021
2022                                                         data[0] = (*out)[1];
2023                                                         data[1] = -(*out)[0];
2024                                                         data[2] = (*out)[2];
2025                                                 }
2026                                         }
2027                                 } else if (corners == 3) {
2028                                         if(S == 0) {
2029                                                 if(y == 0) {
2030                                                         dispgrid = &disps->disps[1*side*side];
2031                                                         data = dispgrid[side * x + 0];
2032
2033                                                         (*out)[0] = (*out)[0] + data[1];
2034                                                         (*out)[1] = (*out)[1] - data[0];
2035                                                         (*out)[2] = (*out)[2] + data[2];
2036
2037                                                         mul_v3_fl(*out, 0.5);
2038
2039                                                         data[0] = -(*out)[1];
2040                                                         data[1] = (*out)[0];
2041                                                         data[2] = (*out)[2];
2042                                                 } else if (x == 0) {
2043                                                         dispgrid = &disps->disps[2 * side * side];
2044                                                         data = dispgrid[side * 0 + y];
2045
2046                                                         (*out)[0] = (*out)[0] - data[1];
2047                                                         (*out)[1] = (*out)[1] + data[0];
2048                                                         (*out)[2] = (*out)[2] + data[2];
2049
2050                                                         mul_v3_fl(*out, 0.5);
2051
2052                                                         data[0] = (*out)[1];
2053                                                         data[1] = -(*out)[0];
2054                                                         data[2] = (*out)[2];
2055                                                 }
2056                                         } else if (S == 2) {
2057                                                 if(x == 0) {
2058                                                         dispgrid = &disps->disps[1 * side * side];
2059                                                         data = dispgrid[side * 0 + y];
2060
2061                                                         (*out)[0] = (*out)[0] - data[1];
2062                                                         (*out)[1] = (*out)[1] + data[0];
2063                                                         (*out)[2] = (*out)[2] + data[2];
2064
2065                                                         mul_v3_fl(*out, 0.5);
2066
2067                                                         data[0] = (*out)[1];
2068                                                         data[1] = -(*out)[0];
2069                                                         data[2] = (*out)[2];
2070                                                 }
2071                                         }
2072                                 }
2073                         }
2074                 }
2075         }
2076 }
2077
2078 /***************** Multires interpolation stuff *****************/
2079
2080 static void mdisp_get_crn_rect(int face_side, float crn[3][4][2])
2081 {
2082         float offset = face_side*0.5f - 0.5f;
2083         float mid[2];
2084
2085         mid[0] = offset * 4 / 3;
2086         mid[1] = offset * 2 / 3;
2087
2088         crn[0][0][0] = mid[0]; crn[0][0][1] = mid[1];
2089         crn[0][1][0] = offset; crn[0][1][1] = 0;
2090         crn[0][2][0] = 0; crn[0][2][1] = 0;
2091         crn[0][3][0] = offset; crn[0][3][1] = offset;
2092
2093         crn[1][0][0] = mid[0]; crn[1][0][1] = mid[1];
2094         crn[1][1][0] = offset * 2; crn[1][1][1] = offset;
2095         crn[1][2][0] = offset * 2; crn[1][2][1] = 0;
2096         crn[1][3][0] = offset; crn[1][3][1] = 0;
2097
2098         crn[2][0][0] = mid[0]; crn[2][0][1] = mid[1];
2099         crn[2][1][0] = offset; crn[2][1][1] = offset;
2100         crn[2][2][0] = offset * 2; crn[2][2][1] = offset * 2;
2101         crn[2][3][0] = offset * 2; crn[2][3][1] = offset;
2102 }
2103
2104 static int mdisp_pt_in_crn(float p[2], float crn[4][2])
2105 {
2106         float v[2][2];
2107         float a[2][2];
2108
2109         sub_v2_v2v2(v[0], crn[1], crn[0]);
2110         sub_v2_v2v2(v[1], crn[3], crn[0]);
2111
2112         sub_v2_v2v2(a[0], p, crn[0]);
2113         sub_v2_v2v2(a[1], crn[2], crn[0]);
2114
2115         if(cross_v2v2(a[0], v[0]) * cross_v2v2(a[1], v[0]) < 0)
2116                 return 0;
2117
2118         if(cross_v2v2(a[0], v[1]) * cross_v2v2(a[1], v[1]) < 0)
2119                 return 0;
2120
2121         return 1;
2122 }
2123
2124 static void face_to_crn_interp(float u, float v, float v1[2], float v2[2], float v3[2], float v4[2], float *x)
2125 {
2126         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];
2127         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];
2128         float c = (v3[1]-v)*v1[0]+(-v3[1]+v1[1])*u+v3[0]*v-v1[1]*v3[0];
2129         float d = b * b - 4 * a * c;
2130         float x1, x2;
2131
2132         if(a == 0) {
2133                 *x = -c / b;
2134                 return;
2135         }
2136
2137         x1 = (-b - sqrtf(d)) / (2 * a);
2138         x2 = (-b + sqrtf(d)) / (2 * a);
2139
2140         *x = maxf(x1, x2);
2141 }
2142
2143 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)
2144 {
2145         float offset = face_side*0.5f - 0.5f;
2146
2147         if(corners == 4) {
2148                 if(S == 1) { *u= offset + x; *v = offset - y; }
2149                 if(S == 2) { *u= offset + y; *v = offset + x; }
2150                 if(S == 3) { *u= offset - x; *v = offset + y; }
2151                 if(S == 0) { *u= offset - y; *v = offset - x; }
2152         } else {
2153                 float crn[3][4][2], vec[4][2];
2154                 float p[2];
2155
2156                 mdisp_get_crn_rect(face_side, crn);
2157
2158                 interp_v2_v2v2(vec[0], crn[S][0], crn[S][1], x / offset);
2159                 interp_v2_v2v2(vec[1], crn[S][3], crn[S][2], x / offset);
2160                 interp_v2_v2v2(vec[2], crn[S][0], crn[S][3], y / offset);
2161                 interp_v2_v2v2(vec[3], crn[S][1], crn[S][2], y / offset);
2162
2163                 isect_seg_seg_v2_point(vec[0], vec[1], vec[2], vec[3], p);
2164
2165                 (*u) = p[0];
2166                 (*v) = p[1];
2167         }
2168 }
2169
2170 /* Find per-corner coordinate with given per-face UV coord */
2171 int mdisp_rot_face_to_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2172 {
2173         const float offset = face_side*0.5f - 0.5f;
2174         int S = 0;
2175
2176         if (corners == 4) {
2177                 if(u <= offset && v <= offset) S = 0;
2178                 else if(u > offset  && v <= offset) S = 1;
2179                 else if(u > offset  && v > offset) S = 2;
2180                 else if(u <= offset && v >= offset)  S = 3;
2181
2182                 if(S == 0) {
2183                         *y = offset - u;
2184                         *x = offset - v;
2185                 } else if(S == 1) {
2186                         *x = u - offset;
2187                         *y = offset - v;
2188                 } else if(S == 2) {
2189                         *y = u - offset;
2190                         *x = v - offset;
2191                 } else if(S == 3) {
2192                         *x= offset - u;
2193                         *y = v - offset;
2194                 }
2195         } else {
2196                 int grid_size = offset;
2197                 float w = (face_side - 1) - u - v;
2198                 float W1, W2;
2199
2200                 if (u >= v && u >= w) {S = 0; W1= w; W2= v;}
2201                 else if (v >= u && v >= w) {S = 1; W1 = u; W2 = w;}
2202                 else {S = 2; W1 = v; W2 = u;}
2203
2204                 W1 /= (face_side-1);
2205                 W2 /= (face_side-1);
2206
2207                 *x = (1-(2*W1)/(1-W2)) * grid_size;
2208                 *y = (1-(2*W2)/(1-W1)) * grid_size;
2209         }
2210
2211         return S;
2212 }
2213
2214 /* Find per-corner coordinate with given per-face UV coord
2215    Practically as the previous funciton but it assumes a bit different coordinate system for triangles
2216    which is optimized for MDISP layer interpolation:
2217
2218    v
2219    ^
2220    |      /|
2221    |    /  |
2222    |  /    |
2223    |/______|___> u
2224
2225  */
2226 int mdisp_rot_face_to_quad_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2227 {
2228         const float offset = face_side*0.5f - 0.5f;
2229         int S = 0;
2230
2231         if (corners == 4) {
2232                 if(u <= offset && v <= offset) S = 0;
2233                 else if(u > offset  && v <= offset) S = 1;
2234                 else if(u > offset  && v > offset) S = 2;
2235                 else if(u <= offset && v >= offset)  S = 3;
2236
2237                 if(S == 0) {
2238                         *y = offset - u;
2239                         *x = offset - v;
2240                 } else if(S == 1) {
2241                         *x = u - offset;
2242                         *y = offset - v;
2243                 } else if(S == 2) {
2244                         *y = u - offset;
2245                         *x = v - offset;
2246                 } else if(S == 3) {
2247                         *x= offset - u;
2248                         *y = v - offset;
2249                 }
2250         } else {
2251                 float crn[3][4][2];
2252                 float p[2] = {u, v};
2253
2254                 mdisp_get_crn_rect(face_side, crn);
2255
2256                 for (S = 0; S < 3; ++S) {
2257                         if (mdisp_pt_in_crn(p, crn[S]))
2258                                 break;
2259                 }
2260
2261                 face_to_crn_interp(u, v, crn[S][0], crn[S][1], crn[S][3], crn[S][2], &p[0]);
2262                 face_to_crn_interp(u, v, crn[S][0], crn[S][3], crn[S][1], crn[S][2], &p[1]);
2263
2264                 *x = p[0] * offset;
2265                 *y = p[1] * offset;
2266         }
2267
2268         return S;
2269 }
2270
2271 void mdisp_apply_weight(const int S, const int corners, int x, int y, const int face_side,
2272         float crn_weight[4][2], float *u_r, float *v_r)
2273 {
2274         float u, v, xl, yl;
2275         float mid1[2], mid2[2], mid3[2];
2276
2277         mdisp_rot_crn_to_face(S, corners, face_side, x, y, &u, &v);
2278
2279         if(corners == 4) {
2280                 xl = u / (face_side - 1);
2281                 yl = v / (face_side - 1);
2282
2283                 mid1[0] = crn_weight[0][0] * (1 - xl) + crn_weight[1][0] * xl;
2284                 mid1[1] = crn_weight[0][1] * (1 - xl) + crn_weight[1][1] * xl;
2285                 mid2[0] = crn_weight[3][0] * (1 - xl) + crn_weight[2][0] * xl;
2286                 mid2[1] = crn_weight[3][1] * (1 - xl) + crn_weight[2][1] * xl;
2287                 mid3[0] = mid1[0] * (1 - yl) + mid2[0] * yl;
2288                 mid3[1] = mid1[1] * (1 - yl) + mid2[1] * yl;
2289         } else {
2290                 yl = v / (face_side - 1);
2291
2292                 if(v == face_side - 1) xl = 1;
2293                 else xl = 1 - (face_side - 1 - u) / (face_side - 1 - v);
2294
2295                 mid1[0] = crn_weight[0][0] * (1 - xl) + crn_weight[1][0] * xl;
2296                 mid1[1] = crn_weight[0][1] * (1 - xl) + crn_weight[1][1] * xl;
2297                 mid3[0] = mid1[0] * (1 - yl) + crn_weight[2][0] * yl;
2298                 mid3[1] = mid1[1] * (1 - yl) + crn_weight[2][1] * yl;
2299         }
2300
2301         *u_r = mid3[0];
2302         *v_r = mid3[1];
2303 }
2304
2305 void mdisp_flip_disp(const int S, const int corners, const float axis_x[2], const float axis_y[2], float disp[3])
2306 {
2307         float crn_x[2], crn_y[2];
2308         float vx[2], vy[2], coord[2];
2309
2310         if (corners == 4) {
2311                 float x[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
2312                 float y[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
2313
2314                 copy_v2_v2(crn_x, x[S]);
2315                 copy_v2_v2(crn_y, y[S]);
2316
2317                 mul_v2_v2fl(vx, crn_x, disp[0]);
2318                 mul_v2_v2fl(vy, crn_y, disp[1]);
2319                 add_v2_v2v2(coord, vx, vy);
2320
2321                 project_v2_v2v2(vx, coord, axis_x);
2322                 project_v2_v2v2(vy, coord, axis_y);
2323
2324                 disp[0] = len_v2(vx);
2325                 disp[1] = len_v2(vy);
2326
2327                 if(dot_v2v2(vx, axis_x) < 0)
2328                         disp[0] = -disp[0];
2329
2330                 if(dot_v2v2(vy, axis_y) < 0)
2331                         disp[1] = -disp[1];
2332         } else {
2333                 /* XXX: it was very overhead code to support displacement flipping
2334                         for case of tris without visible profit.
2335                         Maybe its not really big limitation? for now? (nazgul) */
2336                 disp[0] = 0;
2337                 disp[1] = 0;
2338         }
2339 }
2340
2341 /* Join two triangular displacements into one quad
2342          Corners mapping:
2343          2 -------- 3
2344          | \   tri2 |
2345          |    \     |
2346          | tri1  \  |
2347          0 -------- 1 */
2348 void mdisp_join_tris(MDisps *dst, MDisps *tri1, MDisps *tri2)
2349 {
2350         int side, st;
2351         int S, x, y, crn;
2352         float face_u, face_v, crn_u, crn_v;
2353         float (*out)[3];
2354         MDisps *src;
2355
2356         if(dst->disps)
2357                 BLI_cellalloc_free(dst->disps);
2358
2359         side = sqrt(tri1->totdisp / 3);
2360         st = (side<<1)-1;
2361
2362         dst->totdisp = 4 * side * side;
2363         out = dst->disps = BLI_cellalloc_calloc(3*dst->totdisp*sizeof(float), "join disps");
2364
2365         for(S = 0; S < 4; S++)
2366                 for(y = 0; y < side; ++y)
2367                         for(x = 0; x < side; ++x, ++out) {
2368                                 mdisp_rot_crn_to_face(S, 4, st, x, y, &face_u, &face_v);
2369                                 face_u = st - 1 - face_u;
2370
2371                                 if(face_v > face_u) {
2372                                         src = tri2;
2373                                         face_u = st - 1 - face_u;
2374                                         face_v = st - 1 - face_v;
2375                                 } else src = tri1;
2376
2377                                 crn = mdisp_rot_face_to_quad_crn(3, st, face_u, face_v, &crn_u, &crn_v);
2378
2379                                 old_mdisps_bilinear((*out), &src->disps[crn*side*side], side, crn_u, crn_v);
2380                                 (*out)[0] = 0;
2381                                 (*out)[1] = 0;
2382                         }
2383 }