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