pep8 cleanup, also print message when attempting to run in animation player mode.
[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 *ob, DerivedMesh *dm, int lvl, int simple, int optimal, int plain_uv)
469 {
470         SubsurfModifierData smd= {{NULL}};
471
472         smd.levels = smd.renderLevels = lvl;
473         if(!plain_uv)
474                 smd.flags |= eSubsurfModifierFlag_SubsurfUv;
475         if(simple)
476                 smd.subdivType = ME_SIMPLE_SUBSURF;
477         if(optimal)
478                 smd.flags |= eSubsurfModifierFlag_ControlEdges;
479
480         return subsurf_make_derived_from_derived(dm, &smd, 0, NULL, 0, 0, (ob->mode & OB_MODE_EDIT));
481 }
482
483
484
485 /* assumes no is normalized; return value's sign is negative if v is on
486    the other side of the plane */
487 static float v3_dist_from_plane(float v[3], float center[3], float no[3])
488 {
489         float s[3];
490         sub_v3_v3v3(s, v, center);
491         return dot_v3v3(s, no);
492 }
493
494 void multiresModifier_base_apply(MultiresModifierData *mmd, Object *ob)
495 {
496         DerivedMesh *cddm, *dispdm, *origdm;
497         Mesh *me;
498         ListBase *fmap;
499         float (*origco)[3];
500         int i, j, offset, totlvl;
501
502         multires_force_update(ob);
503
504         me = get_mesh(ob);
505         totlvl = mmd->totlvl;
506
507         /* nothing to do */
508         if(!totlvl)
509                 return;
510
511         /* XXX - probably not necessary to regenerate the cddm so much? */
512
513         /* generate highest level with displacements */
514         cddm = CDDM_from_mesh(me, NULL);
515         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
516         dispdm = multires_dm_create_local(ob, cddm, totlvl, totlvl, 0);
517         cddm->release(cddm);
518
519         /* copy the new locations of the base verts into the mesh */
520         offset = dispdm->getNumVerts(dispdm) - me->totvert;
521         for(i = 0; i < me->totvert; ++i) {
522                 dispdm->getVertCo(dispdm, offset + i, me->mvert[i].co);
523         }
524
525         /* heuristic to produce a better-fitting base mesh */
526
527         cddm = CDDM_from_mesh(me, NULL);
528         fmap = cddm->getFaceMap(ob, cddm);
529         origco = MEM_callocN(sizeof(float)*3*me->totvert, "multires apply base origco");
530         for(i = 0; i < me->totvert ;++i)
531                 copy_v3_v3(origco[i], me->mvert[i].co);
532
533         for(i = 0; i < me->totvert; ++i) {
534                 IndexNode *n;
535                 float avg_no[3] = {0,0,0}, center[3] = {0,0,0}, push[3];
536                 float dist;
537                 int tot;
538
539                 /* don't adjust verts not used by at least one face */
540                 if(!fmap[i].first)
541                         continue;
542
543                 /* find center */
544                 for(n = fmap[i].first, tot = 0; n; n = n->next) {
545                         MFace *f = &me->mface[n->index];
546                         int S = f->v4 ? 4 : 3;
547                         
548                         /* this double counts, not sure if that's bad or good */
549                         for(j = 0; j < S; ++j) {
550                                 int vndx = (&f->v1)[j];
551                                 if(vndx != i) {
552                                         add_v3_v3(center, origco[vndx]);
553                                         ++tot;
554                                 }
555                         }
556                 }
557                 mul_v3_fl(center, 1.0f / tot);
558
559                 /* find normal */
560                 for(n = fmap[i].first; n; n = n->next) {
561                         MFace *f = &me->mface[n->index];
562                         int S = f->v4 ? 4 : 3;
563                         float v[4][3], no[3];
564                         
565                         for(j = 0; j < S; ++j) {
566                                 int vndx = (&f->v1)[j];
567                                 if(vndx == i)
568                                         copy_v3_v3(v[j], center);
569                                 else
570                                         copy_v3_v3(v[j], origco[vndx]);
571                         }
572                         
573                         if(S == 4)
574                                 normal_quad_v3(no, v[0], v[1], v[2], v[3]);
575                         else
576                                 normal_tri_v3(no, v[0], v[1], v[2]);
577                         add_v3_v3(avg_no, no);
578                 }
579                 normalize_v3(avg_no);
580
581                 /* push vertex away from the plane */
582                 dist = v3_dist_from_plane(me->mvert[i].co, center, avg_no);
583                 copy_v3_v3(push, avg_no);
584                 mul_v3_fl(push, dist);
585                 add_v3_v3(me->mvert[i].co, push);
586                 
587         }
588
589         MEM_freeN(origco);
590         cddm->release(cddm);
591
592         /* subdivide the mesh to highest level without displacements */
593         cddm = CDDM_from_mesh(me, NULL);
594         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
595         origdm = subsurf_dm_create_local(ob, cddm, totlvl, 0, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
596         cddm->release(cddm);
597
598         /* calc disps */
599         multiresModifier_disp_run(dispdm, me, 1, 0, origdm->getGridData(origdm), totlvl);
600
601         origdm->release(origdm);
602         dispdm->release(dispdm);
603 }
604
605 static void multires_subdivide(MultiresModifierData *mmd, Object *ob, int totlvl, int updateblock, int simple)
606 {
607         Mesh *me = ob->data;
608         MDisps *mdisps;
609         int lvl= mmd->totlvl;
610
611         if(totlvl > multires_max_levels)
612                 return;
613
614         multires_force_update(ob);
615
616         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
617         if(!mdisps)
618                 mdisps = CustomData_add_layer(&me->fdata, CD_MDISPS, CD_DEFAULT, NULL, me->totface);
619
620         if(mdisps->disps && !updateblock && totlvl > 1) {
621                 /* upsample */
622                 DerivedMesh *lowdm, *cddm, *highdm;
623                 DMGridData **highGridData, **lowGridData, **subGridData;
624                 CCGSubSurf *ss;
625                 int i, numGrids, highGridSize, lowGridSize;
626
627                 /* create subsurf DM from original mesh at high level */
628                 cddm = CDDM_from_mesh(me, NULL);
629                 DM_set_only_copy(cddm, CD_MASK_BAREMESH);
630                 highdm = subsurf_dm_create_local(ob, cddm, totlvl, simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
631
632                 /* create multires DM from original mesh at low level */
633                 lowdm = multires_dm_create_local(ob, cddm, lvl, lvl, simple);
634                 cddm->release(cddm);
635
636                 /* copy subsurf grids and replace them with low displaced grids */
637                 numGrids = highdm->getNumGrids(highdm);
638                 highGridSize = highdm->getGridSize(highdm);
639                 highGridData = highdm->getGridData(highdm);
640                 lowGridSize = lowdm->getGridSize(lowdm);
641                 lowGridData = lowdm->getGridData(lowdm);
642
643                 subGridData = MEM_callocN(sizeof(float*)*numGrids, "subGridData*");
644
645                 for(i = 0; i < numGrids; ++i) {
646                         /* backup subsurf grids */
647                         subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
648                         memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
649
650                         /* overwrite with current displaced grids */
651                         multires_copy_dm_grid(highGridData[i], lowGridData[i], highGridSize, lowGridSize);
652                 }
653
654                 /* low lower level dm no longer needed at this point */
655                 lowdm->release(lowdm);
656
657                 /* subsurf higher levels again with displaced data */
658                 ss= ((CCGDerivedMesh*)highdm)->ss;
659                 ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
660                 ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
661
662                 /* reallocate displacements */
663                 multires_reallocate_mdisps(me, mdisps, totlvl); 
664
665                 /* compute displacements */
666                 multiresModifier_disp_run(highdm, me, 1, 0, subGridData, totlvl);
667
668                 /* free */
669                 highdm->release(highdm);
670                 for(i = 0; i < numGrids; ++i)
671                         MEM_freeN(subGridData[i]);
672                 MEM_freeN(subGridData);
673         }
674         else {
675                 /* only reallocate, nothing to upsample */
676                 multires_reallocate_mdisps(me, mdisps, totlvl); 
677         }
678
679         multires_set_tot_level(ob, mmd, totlvl);
680 }
681
682 void multiresModifier_subdivide(MultiresModifierData *mmd, Object *ob, int updateblock, int simple)
683 {
684         multires_subdivide(mmd, ob, mmd->totlvl+1, updateblock, simple);
685 }
686
687 static void grid_tangent(int gridSize, int index, int x, int y, int axis, DMGridData **gridData, float t[3])
688 {
689         if(axis == 0) {
690                 if(x == gridSize - 1) {
691                         if(y == gridSize - 1)
692                                 sub_v3_v3v3(t, gridData[index][x + gridSize*(y - 1)].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
693                         else
694                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x - 1 + gridSize*y].co);
695                 }
696                 else
697                         sub_v3_v3v3(t, gridData[index][x + 1 + gridSize*y].co, gridData[index][x + gridSize*y].co);
698         }
699         else if(axis == 1) {
700                 if(y == gridSize - 1) {
701                         if(x == gridSize - 1)
702                                 sub_v3_v3v3(t, gridData[index][x - 1 + gridSize*y].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
703                         else
704                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x + gridSize*(y - 1)].co);
705                 }
706                 else
707                         sub_v3_v3v3(t, gridData[index][x + gridSize*(y + 1)].co, gridData[index][x + gridSize*y].co);
708         }
709 }
710
711 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, int invert, int add, DMGridData **oldGridData, int totlvl)
712 {
713         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)dm;
714         DMGridData **gridData, **subGridData;
715         MFace *mface = me->mface;
716         MDisps *mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
717         int *gridOffset;
718         int i, /*numGrids,*/ gridSize, dGridSize, dSkip;
719
720         if(!mdisps) {
721                 if(invert)
722                         mdisps = CustomData_add_layer(&me->fdata, CD_MDISPS, CD_DEFAULT, NULL, me->totface);
723                 else
724                         return;
725         }
726
727         /*numGrids = dm->getNumGrids(dm);*/ /*UNUSED*/
728         gridSize = dm->getGridSize(dm);
729         gridData = dm->getGridData(dm);
730         gridOffset = dm->getGridOffset(dm);
731         subGridData = (oldGridData)? oldGridData: gridData;
732
733         dGridSize = multires_side_tot[totlvl];
734         dSkip = (dGridSize-1)/(gridSize-1);
735
736         #pragma omp parallel for private(i) if(me->totface*gridSize*gridSize*4 >= CCG_OMP_LIMIT)
737         for(i = 0; i < me->totface; ++i) {
738                 const int numVerts = mface[i].v4 ? 4 : 3;
739                 MDisps *mdisp = &mdisps[i];
740                 int S, x, y, gIndex = gridOffset[i];
741
742                 /* when adding new faces in edit mode, need to allocate disps */
743                 if(!mdisp->disps)
744                 #pragma omp critical
745                 {
746                         multires_reallocate_mdisps(me, mdisps, totlvl);
747                 }
748
749                 for(S = 0; S < numVerts; ++S, ++gIndex) {
750                         DMGridData *grid = gridData[gIndex];
751                         DMGridData *subgrid = subGridData[gIndex];
752                         float (*dispgrid)[3] = &mdisp->disps[S*dGridSize*dGridSize];
753
754                         for(y = 0; y < gridSize; y++) {
755                                 for(x = 0; x < gridSize; x++) {
756                                         float *co = grid[x + y*gridSize].co;
757                                         float *sco = subgrid[x + y*gridSize].co;
758                                         float *no = subgrid[x + y*gridSize].no;
759                                         float *data = dispgrid[dGridSize*y*dSkip + x*dSkip];
760                                         float mat[3][3], tx[3], ty[3], disp[3], d[3];
761
762                                         /* construct tangent space matrix */
763                                         grid_tangent(gridSize, gIndex, x, y, 0, subGridData, tx);
764                                         normalize_v3(tx);
765
766                                         grid_tangent(gridSize, gIndex, x, y, 1, subGridData, ty);
767                                         normalize_v3(ty);
768
769                                         //mul_v3_fl(tx, 1.0f/(gridSize-1));
770                                         //mul_v3_fl(ty, 1.0f/(gridSize-1));
771                                         //cross_v3_v3v3(no, tx, ty);
772
773                                         column_vectors_to_mat3(mat, tx, ty, no);
774
775                                         if(!invert) {
776                                                 /* convert to object space and add */
777                                                 mul_v3_m3v3(disp, mat, data);
778                                                 add_v3_v3v3(co, sco, disp);
779                                         }
780                                         else if(!add) {
781                                                 /* convert difference to tangent space */
782                                                 sub_v3_v3v3(disp, co, sco);
783                                                 invert_m3(mat);
784                                                 mul_v3_m3v3(data, mat, disp);
785                                         }
786                                         else {
787                                                 /* convert difference to tangent space */
788                                                 invert_m3(mat);
789                                                 mul_v3_m3v3(d, mat, co);
790                                                 add_v3_v3(data, d);
791                                         }
792                                 }
793                         }
794                 }
795         }
796
797         if(!invert) {
798                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, NULL, 0);
799                 ccgSubSurf_updateNormals(ccgdm->ss, NULL, 0);
800         }
801 }
802
803 static void multiresModifier_update(DerivedMesh *dm)
804 {
805         CCGDerivedMesh *ccgdm= (CCGDerivedMesh*)dm;
806         Object *ob;
807         Mesh *me;
808         MDisps *mdisps;
809         MultiresModifierData *mmd;
810
811         ob = ccgdm->multires.ob;
812         me = ccgdm->multires.ob->data;
813         mmd = ccgdm->multires.mmd;
814         multires_set_tot_mdisps(me, mmd->totlvl);
815         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
816         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
817
818         if(mdisps) {
819                 int lvl = ccgdm->multires.lvl;
820                 int totlvl = ccgdm->multires.totlvl;
821                 
822                 if(lvl < totlvl) {
823                         Mesh *me = ob->data;
824                         DerivedMesh *lowdm, *cddm, *highdm;
825                         DMGridData **highGridData, **lowGridData, **subGridData, **gridData, *diffGrid;
826                         CCGSubSurf *ss;
827                         int i, j, numGrids, highGridSize, lowGridSize;
828
829                         /* create subsurf DM from original mesh at high level */
830                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
831                         else cddm = CDDM_from_mesh(me, NULL);
832                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
833
834                         highdm = subsurf_dm_create_local(ob, cddm, totlvl, mmd->simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
835
836                         /* create multires DM from original mesh and displacements */
837                         lowdm = multires_dm_create_local(ob, cddm, lvl, totlvl, mmd->simple);
838                         cddm->release(cddm);
839
840                         /* gather grid data */
841                         numGrids = highdm->getNumGrids(highdm);
842                         highGridSize = highdm->getGridSize(highdm);
843                         highGridData = highdm->getGridData(highdm);
844                         lowGridSize = lowdm->getGridSize(lowdm);
845                         lowGridData = lowdm->getGridData(lowdm);
846                         gridData = dm->getGridData(dm);
847
848                         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
849                         diffGrid = MEM_callocN(sizeof(DMGridData)*lowGridSize*lowGridSize, "diff");
850
851                         for(i = 0; i < numGrids; ++i) {
852                                 /* backup subsurf grids */
853                                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
854                                 memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
855
856                                 /* write difference of subsurf and displaced low level into high subsurf */
857                                 for(j = 0; j < lowGridSize*lowGridSize; ++j)
858                                         sub_v3_v3v3(diffGrid[j].co, gridData[i][j].co, lowGridData[i][j].co);
859
860                                 multires_copy_dm_grid(highGridData[i], diffGrid, highGridSize, lowGridSize);
861                         }
862
863                         /* lower level dm no longer needed at this point */
864                         MEM_freeN(diffGrid);
865                         lowdm->release(lowdm);
866
867                         /* subsurf higher levels again with difference of coordinates */
868                         ss= ((CCGDerivedMesh*)highdm)->ss;
869                         ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
870                         ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
871
872                         /* add to displacements */
873                         multiresModifier_disp_run(highdm, me, 1, 1, subGridData, mmd->totlvl);
874
875                         /* free */
876                         highdm->release(highdm);
877                         for(i = 0; i < numGrids; ++i)
878                                 MEM_freeN(subGridData[i]);
879                         MEM_freeN(subGridData);
880                 }
881                 else {
882                         DerivedMesh *cddm, *subdm;
883
884                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
885                         else cddm = CDDM_from_mesh(me, NULL);
886                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
887
888                         subdm = subsurf_dm_create_local(ob, cddm, mmd->totlvl, mmd->simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
889                         cddm->release(cddm);
890
891                         multiresModifier_disp_run(dm, me, 1, 0, subdm->getGridData(subdm), mmd->totlvl);
892
893                         subdm->release(subdm);
894                 }
895         }
896 }
897
898 void multires_stitch_grids(Object *ob)
899 {
900         /* utility for smooth brush */
901         if(ob && ob->derivedFinal) {
902                 CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)ob->derivedFinal;
903                 CCGFace **faces;
904                 int totface;
905
906                 if(ccgdm->pbvh) {
907                         BLI_pbvh_get_grid_updates(ccgdm->pbvh, 0, (void***)&faces, &totface);
908
909                         if(totface) {
910                                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, faces, totface);
911                                 MEM_freeN(faces);
912                         }
913                 }
914         }
915 }
916
917 DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int local_mmd, DerivedMesh *dm, Object *ob,
918                                                         int useRenderParams, int UNUSED(isFinalCalc))
919 {
920         Mesh *me= ob->data;
921         DerivedMesh *result;
922         CCGDerivedMesh *ccgdm;
923         DMGridData **gridData, **subGridData;
924         int lvl= multires_get_level(ob, mmd, useRenderParams);
925         int i, gridSize, numGrids;
926
927         if(lvl == 0)
928                 return dm;
929
930         result = subsurf_dm_create_local(ob, dm, lvl,
931                 mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges,
932                 mmd->flags & eMultiresModifierFlag_PlainUv);
933
934         if(!local_mmd) {
935                 ccgdm = (CCGDerivedMesh*)result;
936
937                 ccgdm->multires.ob = ob;
938                 ccgdm->multires.mmd = mmd;
939                 ccgdm->multires.local_mmd = local_mmd;
940                 ccgdm->multires.lvl = lvl;
941                 ccgdm->multires.totlvl = mmd->totlvl;
942                 ccgdm->multires.modified = 0;
943                 ccgdm->multires.update = multiresModifier_update;
944         }
945
946         numGrids = result->getNumGrids(result);
947         gridSize = result->getGridSize(result);
948         gridData = result->getGridData(result);
949
950         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
951
952         for(i = 0; i < numGrids; i++) {
953                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*gridSize*gridSize, "subGridData");
954                 memcpy(subGridData[i], gridData[i], sizeof(DMGridData)*gridSize*gridSize);
955         }
956
957         multires_set_tot_mdisps(me, mmd->totlvl);
958         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
959         multiresModifier_disp_run(result, ob->data, 0, 0, subGridData, mmd->totlvl);
960
961         for(i = 0; i < numGrids; i++)
962                 MEM_freeN(subGridData[i]);
963         MEM_freeN(subGridData);
964
965         return result;
966 }
967
968 /**** Old Multires code ****
969 ***************************/
970
971 /* Adapted from sculptmode.c */
972 void old_mdisps_bilinear(float out[3], float (*disps)[3], const int st, float u, float v)
973 {
974         int x, y, x2, y2;
975         const int st_max = st - 1;
976         float urat, vrat, uopp;
977         float d[4][3], d2[2][3];
978
979         if(u < 0)
980                 u = 0;
981         else if(u >= st)
982                 u = st_max;
983         if(v < 0)
984                 v = 0;
985         else if(v >= st)
986                 v = st_max;
987
988         x = floor(u);
989         y = floor(v);
990         x2 = x + 1;
991         y2 = y + 1;
992
993         if(x2 >= st) x2 = st_max;
994         if(y2 >= st) y2 = st_max;
995         
996         urat = u - x;
997         vrat = v - y;
998         uopp = 1 - urat;
999
1000         mul_v3_v3fl(d[0], disps[y * st + x], uopp);
1001         mul_v3_v3fl(d[1], disps[y * st + x2], urat);
1002         mul_v3_v3fl(d[2], disps[y2 * st + x], uopp);
1003         mul_v3_v3fl(d[3], disps[y2 * st + x2], urat);
1004
1005         add_v3_v3v3(d2[0], d[0], d[1]);
1006         add_v3_v3v3(d2[1], d[2], d[3]);
1007         mul_v3_fl(d2[0], 1 - vrat);
1008         mul_v3_fl(d2[1], vrat);
1009
1010         add_v3_v3v3(out, d2[0], d2[1]);
1011 }
1012
1013 static void old_mdisps_rotate(int S, int UNUSED(newside), int oldside, int x, int y, float *u, float *v)
1014 {
1015         float offset = oldside*0.5f - 0.5f;
1016
1017         if(S == 1) { *u= offset + x; *v = offset - y; }
1018         if(S == 2) { *u= offset + y; *v = offset + x; }
1019         if(S == 3) { *u= offset - x; *v = offset + y; }
1020         if(S == 0) { *u= offset - y; *v = offset - x; }
1021 }
1022
1023 static void old_mdisps_convert(MFace *mface, MDisps *mdisp)
1024 {
1025         int newlvl = log(sqrt(mdisp->totdisp)-1)/M_LN2;
1026         int oldlvl = newlvl+1;
1027         int oldside = multires_side_tot[oldlvl];
1028         int newside = multires_side_tot[newlvl];
1029         int nvert = (mface->v4)? 4: 3;
1030         int newtotdisp = multires_grid_tot[newlvl]*nvert;
1031         int x, y, S;
1032         float (*disps)[3], (*out)[3], u, v;
1033
1034         disps = MEM_callocN(sizeof(float) * 3 * newtotdisp, "multires disps");
1035
1036         out = disps;
1037         for(S = 0; S < nvert; S++) {
1038                 for(y = 0; y < newside; ++y) {
1039                         for(x = 0; x < newside; ++x, ++out) {
1040                                 old_mdisps_rotate(S, newside, oldside, x, y, &u, &v);
1041                                 old_mdisps_bilinear(*out, mdisp->disps, oldside, u, v);
1042
1043                                 if(S == 1) { (*out)[1]= -(*out)[1]; }
1044                                 else if(S == 2) { SWAP(float, (*out)[0], (*out)[1]); }
1045                                 else if(S == 3) { (*out)[0]= -(*out)[0]; }
1046                                 else if(S == 0) { SWAP(float, (*out)[0], (*out)[1]); (*out)[0]= -(*out)[0]; (*out)[1]= -(*out)[1]; };
1047                         }
1048                 }
1049         }
1050
1051         MEM_freeN(mdisp->disps);
1052
1053         mdisp->totdisp= newtotdisp;
1054         mdisp->disps= disps;
1055 }
1056
1057 void multires_load_old_250(Mesh *me)
1058 {
1059         MDisps *mdisps;
1060         int a;
1061
1062         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
1063
1064         if(mdisps) {
1065                 for(a=0; a<me->totface; a++)
1066                         if(mdisps[a].totdisp)
1067                                 old_mdisps_convert(&me->mface[a], &mdisps[a]);
1068         }
1069 }
1070
1071 /* Does not actually free lvl itself */
1072 static void multires_free_level(MultiresLevel *lvl)
1073 {
1074         if(lvl) {
1075                 if(lvl->faces) MEM_freeN(lvl->faces);
1076                 if(lvl->edges) MEM_freeN(lvl->edges);
1077                 if(lvl->colfaces) MEM_freeN(lvl->colfaces);
1078         }
1079 }
1080
1081 void multires_free(Multires *mr)
1082 {
1083         if(mr) {
1084                 MultiresLevel* lvl= mr->levels.first;
1085
1086                 /* Free the first-level data */
1087                 if(lvl) {
1088                         CustomData_free(&mr->vdata, lvl->totvert);
1089                         CustomData_free(&mr->fdata, lvl->totface);
1090                         if(mr->edge_flags)
1091                                 MEM_freeN(mr->edge_flags);
1092                         if(mr->edge_creases)
1093                                 MEM_freeN(mr->edge_creases);
1094                 }
1095
1096                 while(lvl) {
1097                         multires_free_level(lvl);                       
1098                         lvl= lvl->next;
1099                 }
1100
1101                 MEM_freeN(mr->verts);
1102
1103                 BLI_freelistN(&mr->levels);
1104
1105                 MEM_freeN(mr);
1106         }
1107 }
1108
1109 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
1110                                          const int totvert, const int totface)
1111 {
1112         int i,j;
1113         IndexNode *node = NULL;
1114         
1115         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
1116         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
1117         node = *mem;
1118         
1119         /* Find the users */
1120         for(i = 0; i < totface; ++i){
1121                 for(j = 0; j < (mface[i].v[3]?4:3); ++j, ++node) {
1122                         node->index = i;
1123                         BLI_addtail(&(*map)[mface[i].v[j]], node);
1124                 }
1125         }
1126 }
1127
1128 static void create_old_vert_edge_map(ListBase **map, IndexNode **mem, const MultiresEdge *medge,
1129                                          const int totvert, const int totedge)
1130 {
1131         int i,j;
1132         IndexNode *node = NULL;
1133         
1134         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
1135         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge*2, "vert edge map mem");
1136         node = *mem;
1137         
1138         /* Find the users */
1139         for(i = 0; i < totedge; ++i){
1140                 for(j = 0; j < 2; ++j, ++node) {
1141                         node->index = i;
1142                         BLI_addtail(&(*map)[medge[i].v[j]], node);
1143                 }
1144         }
1145 }
1146
1147 static MultiresFace *find_old_face(ListBase *map, MultiresFace *faces, int v1, int v2, int v3, int v4)
1148 {
1149         IndexNode *n1;
1150         int v[4], i, j;
1151
1152          v[0]= v1;
1153          v[1]= v2;
1154          v[2]= v3;
1155          v[3]= v4;
1156
1157         for(n1 = map[v1].first; n1; n1 = n1->next) {
1158                 int fnd[4] = {0, 0, 0, 0};
1159
1160                 for(i = 0; i < 4; ++i) {
1161                         for(j = 0; j < 4; ++j) {
1162                                 if(v[i] == faces[n1->index].v[j])
1163                                         fnd[i] = 1;
1164                         }
1165                 }
1166
1167                 if(fnd[0] && fnd[1] && fnd[2] && fnd[3])
1168                         return &faces[n1->index];
1169         }
1170
1171         return NULL;
1172 }
1173
1174 static MultiresEdge *find_old_edge(ListBase *map, MultiresEdge *edges, int v1, int v2)
1175 {
1176         IndexNode *n1, *n2;
1177
1178         for(n1 = map[v1].first; n1; n1 = n1->next) {
1179                 for(n2 = map[v2].first; n2; n2 = n2->next) {
1180                         if(n1->index == n2->index)
1181                                 return &edges[n1->index];
1182                 }
1183         }
1184
1185         return NULL;
1186 }
1187
1188 static void multires_load_old_edges(ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst, int v1, int v2, int mov)
1189 {
1190         int emid = find_old_edge(emap[2], lvl->edges, v1, v2)->mid;
1191         vvmap[dst + mov] = emid;
1192
1193         if(lvl->next->next) {
1194                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v1, emid, mov / 2);
1195                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v2, emid, -mov / 2);
1196         }
1197 }
1198
1199 static void multires_load_old_faces(ListBase **fmap, ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst,
1200                                         int v1, int v2, int v3, int v4, int st2, int st3)
1201 {
1202         int fmid;
1203         int emid13, emid14, emid23, emid24;
1204
1205         if(lvl && lvl->next) {
1206                 fmid = find_old_face(fmap[1], lvl->faces, v1, v2, v3, v4)->mid;
1207                 vvmap[dst] = fmid;
1208
1209                 emid13 = find_old_edge(emap[1], lvl->edges, v1, v3)->mid;
1210                 emid14 = find_old_edge(emap[1], lvl->edges, v1, v4)->mid;
1211                 emid23 = find_old_edge(emap[1], lvl->edges, v2, v3)->mid;
1212                 emid24 = find_old_edge(emap[1], lvl->edges, v2, v4)->mid;
1213
1214
1215                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 + st3,
1216                                         fmid, v2, emid23, emid24, st2, st3 / 2);
1217
1218                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 + st3,
1219                                         emid14, emid24, fmid, v4, st2, st3 / 2);
1220
1221                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 - st3,
1222                                         emid13, emid23, v3, fmid, st2, st3 / 2);
1223
1224                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 - st3,
1225                                         v1, fmid, emid13, emid14, st2, st3 / 2);
1226
1227                 if(lvl->next->next) {
1228                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid24, fmid, st3);
1229                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid13, fmid, -st3);
1230                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid14, fmid, -st2 * st3);
1231                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid23, fmid, st2 * st3);
1232                 }
1233         }
1234 }
1235
1236 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert)
1237 {
1238         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*) dm;
1239         CCGSubSurf *ss = ccgdm->ss;
1240         DMGridData *vd;
1241         int index;
1242         int totvert, totedge, totface;
1243         int gridSize = ccgSubSurf_getGridSize(ss);
1244         int edgeSize = ccgSubSurf_getEdgeSize(ss);
1245         int i = 0;
1246
1247         totface = ccgSubSurf_getNumFaces(ss);
1248         for(index = 0; index < totface; index++) {
1249                 CCGFace *f = ccgdm->faceMap[index].face;
1250                 int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1251
1252                 vd= ccgSubSurf_getFaceCenterData(f);
1253                 copy_v3_v3(vd->co, mvert[i].co);
1254                 i++;
1255                 
1256                 for(S = 0; S < numVerts; S++) {
1257                         for(x = 1; x < gridSize - 1; x++, i++) {
1258                                 vd= ccgSubSurf_getFaceGridEdgeData(ss, f, S, x);
1259                                 copy_v3_v3(vd->co, mvert[i].co);
1260                         }
1261                 }
1262
1263                 for(S = 0; S < numVerts; S++) {
1264                         for(y = 1; y < gridSize - 1; y++) {
1265                                 for(x = 1; x < gridSize - 1; x++, i++) {
1266                                         vd= ccgSubSurf_getFaceGridData(ss, f, S, x, y);
1267                                         copy_v3_v3(vd->co, mvert[i].co);
1268                                 }
1269                         }
1270                 }
1271         }
1272
1273         totedge = ccgSubSurf_getNumEdges(ss);
1274         for(index = 0; index < totedge; index++) {
1275                 CCGEdge *e = ccgdm->edgeMap[index].edge;
1276                 int x;
1277
1278                 for(x = 1; x < edgeSize - 1; x++, i++) {
1279                         vd= ccgSubSurf_getEdgeData(ss, e, x);
1280                         copy_v3_v3(vd->co, mvert[i].co);
1281                 }
1282         }
1283
1284         totvert = ccgSubSurf_getNumVerts(ss);
1285         for(index = 0; index < totvert; index++) {
1286                 CCGVert *v = ccgdm->vertMap[index].vert;
1287
1288                 vd= ccgSubSurf_getVertData(ss, v);
1289                 copy_v3_v3(vd->co, mvert[i].co);
1290                 i++;
1291         }
1292
1293         ccgSubSurf_updateToFaces(ss, 0, NULL, 0);
1294 }
1295
1296 /* Loads a multires object stored in the old Multires struct into the new format */
1297 static void multires_load_old_dm(DerivedMesh *dm, Mesh *me, int totlvl)
1298 {
1299         MultiresLevel *lvl, *lvl1;
1300         Multires *mr= me->mr;
1301         MVert *vsrc, *vdst;
1302         unsigned int src, dst;
1303         int st = multires_side_tot[totlvl - 1] - 1;
1304         int extedgelen = multires_side_tot[totlvl] - 2;
1305         int *vvmap; // inorder for dst, map to src
1306         int crossedgelen;
1307         int s, x, tottri, totquad;
1308         unsigned int i, j, totvert;
1309
1310         src = 0;
1311         vsrc = mr->verts;
1312         vdst = dm->getVertArray(dm);
1313         totvert = (unsigned int)dm->getNumVerts(dm);
1314         vvmap = MEM_callocN(sizeof(int) * totvert, "multires vvmap");
1315
1316         lvl1 = mr->levels.first;
1317         /* Load base verts */
1318         for(i = 0; i < lvl1->totvert; ++i) {
1319                 vvmap[totvert - lvl1->totvert + i] = src;
1320                 ++src;
1321         }
1322
1323         /* Original edges */
1324         dst = totvert - lvl1->totvert - extedgelen * lvl1->totedge;
1325         for(i = 0; i < lvl1->totedge; ++i) {
1326                 int ldst = dst + extedgelen * i;
1327                 int lsrc = src;
1328                 lvl = lvl1->next;
1329
1330                 for(j = 2; j <= mr->level_count; ++j) {
1331                         int base = multires_side_tot[totlvl - j + 1] - 2;
1332                         int skip = multires_side_tot[totlvl - j + 2] - 1;
1333                         int st = multires_side_tot[j - 1] - 1;
1334
1335                         for(x = 0; x < st; ++x)
1336                                 vvmap[ldst + base + x * skip] = lsrc + st * i + x;
1337
1338                         lsrc += lvl->totvert - lvl->prev->totvert;
1339                         lvl = lvl->next;
1340                 }
1341         }
1342
1343         /* Center points */
1344         dst = 0;
1345         for(i = 0; i < lvl1->totface; ++i) {
1346                 int sides = lvl1->faces[i].v[3] ? 4 : 3;
1347
1348                 vvmap[dst] = src + lvl1->totedge + i;
1349                 dst += 1 + sides * (st - 1) * st;
1350         }
1351
1352
1353         /* The rest is only for level 3 and up */
1354         if(lvl1->next && lvl1->next->next) {
1355                 ListBase **fmap, **emap;
1356                 IndexNode **fmem, **emem;
1357
1358                 /* Face edge cross */
1359                 tottri = totquad = 0;
1360                 crossedgelen = multires_side_tot[totlvl - 1] - 2;
1361                 dst = 0;
1362                 for(i = 0; i < lvl1->totface; ++i) {
1363                         int sides = lvl1->faces[i].v[3] ? 4 : 3;
1364
1365                         lvl = lvl1->next->next;
1366                         ++dst;
1367
1368                         for(j = 3; j <= mr->level_count; ++j) {
1369                                 int base = multires_side_tot[totlvl - j + 1] - 2;
1370                                 int skip = multires_side_tot[totlvl - j + 2] - 1;
1371                                 int st = pow(2, j - 2);
1372                                 int st2 = pow(2, j - 3);
1373                                 int lsrc = lvl->prev->totvert;
1374
1375                                 /* Skip exterior edge verts */
1376                                 lsrc += lvl1->totedge * st;
1377
1378                                 /* Skip earlier face edge crosses */
1379                                 lsrc += st2 * (tottri * 3 + totquad * 4);
1380
1381                                 for(s = 0; s < sides; ++s) {
1382                                         for(x = 0; x < st2; ++x) {
1383                                                 vvmap[dst + crossedgelen * (s + 1) - base - x * skip - 1] = lsrc;
1384                                                 ++lsrc;
1385                                         }
1386                                 }
1387
1388                                 lvl = lvl->next;
1389                         }
1390
1391                         dst += sides * (st - 1) * st;
1392
1393                         if(sides == 4) ++totquad;
1394                         else ++tottri;
1395
1396                 }
1397
1398                 /* calculate vert to edge/face maps for each level (except the last) */
1399                 fmap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires fmap");
1400                 emap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires emap");
1401                 fmem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires fmem");
1402                 emem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires emem");
1403                 lvl = lvl1;
1404                 for(i = 0; i < (unsigned int)mr->level_count - 1; ++i) {
1405                         create_old_vert_face_map(fmap + i, fmem + i, lvl->faces, lvl->totvert, lvl->totface);
1406                         create_old_vert_edge_map(emap + i, emem + i, lvl->edges, lvl->totvert, lvl->totedge);
1407                         lvl = lvl->next;
1408                 }
1409
1410                 /* Interior face verts */
1411                 lvl = lvl1->next->next;
1412                 dst = 0;
1413                 for(j = 0; j < lvl1->totface; ++j) {
1414                         int sides = lvl1->faces[j].v[3] ? 4 : 3;
1415                         int ldst = dst + 1 + sides * (st - 1);
1416
1417                         for(s = 0; s < sides; ++s) {
1418                                 int st2 = multires_side_tot[totlvl - 1] - 2;
1419                                 int st3 = multires_side_tot[totlvl - 2] - 2;
1420                                 int st4 = st3 == 0 ? 1 : (st3 + 1) / 2;
1421                                 int mid = ldst + st2 * st3 + st3;
1422                                 int cv = lvl1->faces[j].v[s];
1423                                 int nv = lvl1->faces[j].v[s == sides - 1 ? 0 : s + 1];
1424                                 int pv = lvl1->faces[j].v[s == 0 ? sides - 1 : s - 1];
1425
1426                                 multires_load_old_faces(fmap, emap, lvl1->next, vvmap, mid,
1427                                                         vvmap[dst], cv,
1428                                                         find_old_edge(emap[0], lvl1->edges, pv, cv)->mid,
1429                                                         find_old_edge(emap[0], lvl1->edges, cv, nv)->mid,
1430                                                         st2, st4);
1431
1432                                 ldst += (st - 1) * (st - 1);
1433                         }
1434
1435
1436                         dst = ldst;
1437                 }
1438
1439                 /*lvl = lvl->next;*/ /*UNUSED*/
1440
1441                 for(i = 0; i < (unsigned int)(mr->level_count - 1); ++i) {
1442                         MEM_freeN(fmap[i]);
1443                         MEM_freeN(fmem[i]);
1444                         MEM_freeN(emap[i]);
1445                         MEM_freeN(emem[i]);
1446                 }
1447
1448                 MEM_freeN(fmap);
1449                 MEM_freeN(emap);
1450                 MEM_freeN(fmem);
1451                 MEM_freeN(emem);
1452         }
1453
1454         /* Transfer verts */
1455         for(i = 0; i < totvert; ++i)
1456                 copy_v3_v3(vdst[i].co, vsrc[vvmap[i]].co);
1457
1458         MEM_freeN(vvmap);
1459
1460         multires_mvert_to_ss(dm, vdst);
1461 }
1462
1463 /* Copy the first-level vcol data to the mesh, if it exists */
1464 /* Warning: higher-level vcol data will be lost */
1465 static void multires_load_old_vcols(Mesh *me)
1466 {
1467         MultiresLevel *lvl;
1468         MultiresColFace *colface;
1469         MCol *mcol;
1470         int i, j;
1471
1472         if(!(lvl = me->mr->levels.first))
1473                 return;
1474
1475         if(!(colface = lvl->colfaces))
1476                 return;
1477
1478         /* older multires format never supported multiple vcol layers,
1479            so we can assume the active vcol layer is the correct one */
1480         if(!(mcol = CustomData_get_layer(&me->fdata, CD_MCOL)))
1481                 return;
1482         
1483         for(i = 0; i < me->totface; ++i) {
1484                 for(j = 0; j < 4; ++j) {
1485                         mcol[i*4 + j].a = colface[i].col[j].a;
1486                         mcol[i*4 + j].r = colface[i].col[j].r;
1487                         mcol[i*4 + j].g = colface[i].col[j].g;
1488                         mcol[i*4 + j].b = colface[i].col[j].b;
1489                 }
1490         }
1491 }
1492
1493 /* Copy the first-level face-flag data to the mesh */
1494 static void multires_load_old_face_flags(Mesh *me)
1495 {
1496         MultiresLevel *lvl;
1497         MultiresFace *faces;
1498         int i;
1499
1500         if(!(lvl = me->mr->levels.first))
1501                 return;
1502
1503         if(!(faces = lvl->faces))
1504                 return;
1505
1506         for(i = 0; i < me->totface; ++i)
1507                 me->mface[i].flag = faces[i].flag;
1508 }
1509
1510 void multires_load_old(Object *ob, Mesh *me)
1511 {
1512         MultiresLevel *lvl;
1513         ModifierData *md;
1514         MultiresModifierData *mmd;
1515         DerivedMesh *dm, *orig;
1516         CustomDataLayer *l;
1517         int i;
1518
1519         /* Load original level into the mesh */
1520         lvl = me->mr->levels.first;
1521         CustomData_free_layers(&me->vdata, CD_MVERT, lvl->totvert);
1522         CustomData_free_layers(&me->edata, CD_MEDGE, lvl->totedge);
1523         CustomData_free_layers(&me->fdata, CD_MFACE, lvl->totface);
1524         me->totvert = lvl->totvert;
1525         me->totedge = lvl->totedge;
1526         me->totface = lvl->totface;
1527         me->mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
1528         me->medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
1529         me->mface = CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
1530         memcpy(me->mvert, me->mr->verts, sizeof(MVert) * me->totvert);
1531         for(i = 0; i < me->totedge; ++i) {
1532                 me->medge[i].v1 = lvl->edges[i].v[0];
1533                 me->medge[i].v2 = lvl->edges[i].v[1];
1534         }
1535         for(i = 0; i < me->totface; ++i) {
1536                 me->mface[i].v1 = lvl->faces[i].v[0];
1537                 me->mface[i].v2 = lvl->faces[i].v[1];
1538                 me->mface[i].v3 = lvl->faces[i].v[2];
1539                 me->mface[i].v4 = lvl->faces[i].v[3];
1540         }
1541
1542         /* Add a multires modifier to the object */
1543         md = ob->modifiers.first;
1544         while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
1545                 md = md->next;                          
1546         mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
1547         BLI_insertlinkbefore(&ob->modifiers, md, mmd);
1548
1549         for(i = 0; i < me->mr->level_count - 1; ++i)
1550                 multiresModifier_subdivide(mmd, ob, 1, 0);
1551
1552         mmd->lvl = mmd->totlvl;
1553         orig = CDDM_from_mesh(me, NULL);
1554         dm = multires_dm_create_from_derived(mmd, 0, orig, ob, 0, 0);
1555                                            
1556         multires_load_old_dm(dm, me, mmd->totlvl+1);
1557
1558         multires_dm_mark_as_modified(dm);
1559         dm->release(dm);
1560         orig->release(orig);
1561
1562         /* Copy the first-level data to the mesh */
1563         for(i = 0, l = me->mr->vdata.layers; i < me->mr->vdata.totlayer; ++i, ++l)
1564                 CustomData_add_layer(&me->vdata, l->type, CD_REFERENCE, l->data, me->totvert);
1565         for(i = 0, l = me->mr->fdata.layers; i < me->mr->fdata.totlayer; ++i, ++l)
1566                 CustomData_add_layer(&me->fdata, l->type, CD_REFERENCE, l->data, me->totface);
1567         memset(&me->mr->vdata, 0, sizeof(CustomData));
1568         memset(&me->mr->fdata, 0, sizeof(CustomData));
1569
1570         multires_load_old_vcols(me);
1571         multires_load_old_face_flags(me);
1572
1573         /* Remove the old multires */
1574         multires_free(me->mr);
1575         me->mr= NULL;
1576 }
1577
1578 static void multires_sync_levels(Scene *scene, Object *ob, Object *to_ob)
1579 {
1580         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1581         MultiresModifierData *to_mmd= get_multires_modifier(scene, to_ob, 1);
1582
1583         if(!mmd) {
1584                 /* object could have MDISP even when there is no multires modifier
1585                    this could lead to troubles due to i've got no idea how mdisp could be
1586                    upsampled correct without modifier data.
1587                    just remove mdisps if no multires present (nazgul) */
1588
1589                 Mesh *me= (Mesh*)ob->data;
1590
1591                 CustomData_external_remove(&me->fdata, &me->id, CD_MDISPS, me->totface);
1592                 CustomData_free_layer_active(&me->fdata, CD_MDISPS, me->totface);
1593         }
1594
1595         if(!mmd || !to_mmd) return;
1596
1597         if(mmd->totlvl>to_mmd->totlvl) multires_del_higher(mmd, ob, to_mmd->totlvl);
1598         else multires_subdivide(mmd, ob, to_mmd->totlvl, 0, mmd->simple);
1599 }
1600
1601 static void multires_apply_smat(Scene *scene, Object *ob, float smat[3][3])
1602 {
1603         DerivedMesh *dm= NULL, *cddm= NULL, *subdm= NULL;
1604         DMGridData **gridData, **subGridData;
1605         Mesh *me= (Mesh*)ob->data;
1606         MFace *mface= me->mface;
1607         MDisps *mdisps;
1608         int *gridOffset;
1609         int i, /*numGrids,*/ gridSize, dGridSize, dSkip, totvert;
1610         float (*vertCos)[3] = NULL;
1611         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1612         MultiresModifierData high_mmd;
1613
1614         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
1615         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
1616
1617         if(!mdisps || !mmd) return;
1618
1619         /* we need derived mesh created from highest resolution */
1620         high_mmd= *mmd;
1621         high_mmd.lvl= high_mmd.totlvl;
1622
1623         /* unscaled multires with applied displacement */
1624         subdm= get_multires_dm(scene, &high_mmd, ob);
1625
1626         /* prepare scaled CDDM to create ccgDN */
1627         cddm= mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
1628
1629         totvert= cddm->getNumVerts(cddm);
1630         vertCos= MEM_mallocN(sizeof(*vertCos) * totvert, "multiresScale vertCos");
1631         cddm->getVertCos(cddm, vertCos);
1632         for(i=0; i<totvert; i++)
1633                 mul_m3_v3(smat, vertCos[i]);
1634         CDDM_apply_vert_coords(cddm, vertCos);
1635         MEM_freeN(vertCos);
1636
1637         /* scaled ccgDM for tangent space of object with applied scale */
1638         dm= subsurf_dm_create_local(ob, cddm, high_mmd.totlvl, high_mmd.simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
1639         cddm->release(cddm);
1640
1641         /*numGrids= dm->getNumGrids(dm);*/ /*UNUSED*/
1642         gridSize= dm->getGridSize(dm);
1643         gridData= dm->getGridData(dm);
1644         gridOffset= dm->getGridOffset(dm);
1645         subGridData= subdm->getGridData(subdm);
1646
1647         dGridSize= multires_side_tot[high_mmd.totlvl];
1648         dSkip= (dGridSize-1)/(gridSize-1);
1649
1650         #pragma omp parallel for private(i) if(me->totface*gridSize*gridSize*4 >= CCG_OMP_LIMIT)
1651         for(i = 0; i < me->totface; ++i) {
1652                 const int numVerts= mface[i].v4 ? 4 : 3;
1653                 MDisps *mdisp= &mdisps[i];
1654                 int S, x, y, gIndex = gridOffset[i];
1655
1656                 for(S = 0; S < numVerts; ++S, ++gIndex) {
1657                         DMGridData *grid= gridData[gIndex];
1658                         DMGridData *subgrid= subGridData[gIndex];
1659                         float (*dispgrid)[3]= &mdisp->disps[S*dGridSize*dGridSize];
1660
1661                         for(y = 0; y < gridSize; y++) {
1662                                 for(x = 0; x < gridSize; x++) {
1663                                         float *co= grid[x + y*gridSize].co;
1664                                         float *sco= subgrid[x + y*gridSize].co;
1665                                         float *no= grid[x + y*gridSize].no;
1666                                         float *data= dispgrid[dGridSize*y*dSkip + x*dSkip];
1667                                         float mat[3][3], tx[3], ty[3], disp[3];
1668
1669                                         /* construct tangent space matrix */
1670                                         grid_tangent(gridSize, gIndex, x, y, 0, gridData, tx);
1671                                         normalize_v3(tx);
1672
1673                                         grid_tangent(gridSize, gIndex, x, y, 1, gridData, ty);
1674                                         normalize_v3(ty);
1675
1676                                         column_vectors_to_mat3(mat, tx, ty, no);
1677
1678                                         /* scale subgrid coord and calculate displacement */
1679                                         mul_m3_v3(smat, sco);
1680                                         sub_v3_v3v3(disp, sco, co);
1681
1682                                         /* convert difference to tangent space */
1683                                         invert_m3(mat);
1684                                         mul_v3_m3v3(data, mat, disp);
1685                                 }
1686                         }
1687                 }
1688         }
1689
1690         dm->release(dm);
1691         subdm->release(subdm);
1692 }
1693
1694 int multires_mdisp_corners(MDisps *s)
1695 {
1696         int lvl= 13;
1697
1698         while(lvl > 0) {
1699                 int side = (1 << (lvl-1)) + 1;
1700                 if ((s->totdisp % (side*side)) == 0) return s->totdisp / (side*side);
1701                 lvl--;
1702         }
1703
1704         return 0;
1705 }
1706
1707 void multiresModifier_scale_disp(Scene *scene, Object *ob)
1708 {
1709         float smat[3][3];
1710
1711         /* object's scale matrix */
1712         object_scale_to_mat3(ob, smat);
1713
1714         multires_apply_smat(scene, ob, smat);
1715 }
1716
1717 void multiresModifier_prepare_join(Scene *scene, Object *ob, Object *to_ob)
1718 {
1719         float smat[3][3], tmat[3][3], mat[3][3];
1720         multires_sync_levels(scene, ob, to_ob);
1721
1722         /* construct scale matrix for displacement */
1723         object_scale_to_mat3(to_ob, tmat);
1724         invert_m3(tmat);
1725         object_scale_to_mat3(ob, smat);
1726         mul_m3_m3m3(mat, smat, tmat);
1727
1728         multires_apply_smat(scene, ob, mat);
1729 }
1730
1731 /* update multires data after topology changing */
1732 void multires_topology_changed(Scene *scene, Object *ob)
1733 {
1734         Mesh *me= (Mesh*)ob->data;
1735         MDisps *mdisp= NULL, *cur= NULL;
1736         int i, grid= 0, corners;
1737         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
1738
1739         if(mmd)
1740                 multires_set_tot_mdisps(me, mmd->totlvl);
1741
1742         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
1743         mdisp= CustomData_get_layer(&me->fdata, CD_MDISPS);
1744
1745         if(!mdisp) return;
1746
1747         cur= mdisp;
1748         for(i = 0; i < me->totface; i++, cur++) {
1749                 if(mdisp->totdisp) {
1750                         corners= multires_mdisp_corners(mdisp);
1751                         grid= mdisp->totdisp / corners;
1752
1753                         break;
1754                 }
1755         }
1756
1757         for(i = 0; i < me->totface; i++, mdisp++) {
1758                 int nvert= me->mface[i].v4 ? 4 : 3;
1759
1760                 /* allocate memory for mdisp, the whole disp layer would be erased otherwise */
1761                 if(!mdisp->totdisp || !mdisp->disps) {
1762                         if(grid) {
1763                                 mdisp->totdisp= nvert*grid;
1764                                 mdisp->disps= MEM_callocN(mdisp->totdisp*sizeof(float)*3, "mdisp topology");
1765                         }
1766
1767                         continue;
1768                 }
1769
1770                 corners= multires_mdisp_corners(mdisp);
1771
1772                 if(corners!=nvert) {
1773                         mdisp->totdisp= (mdisp->totdisp/corners)*nvert;
1774
1775                         if(mdisp->disps)
1776                                 MEM_freeN(mdisp->disps);
1777
1778                         mdisp->disps= MEM_callocN(mdisp->totdisp*sizeof(float)*3, "mdisp topology");
1779                 }
1780         }
1781 }
1782
1783 /* makes displacement along grid boundary symmetrical */
1784 void multires_mdisp_smooth_bounds(MDisps *disps)
1785 {
1786         int x, y, side, S, corners;
1787         float (*out)[3];
1788
1789         corners = multires_mdisp_corners(disps);
1790         side = sqrt(disps->totdisp / corners);
1791
1792         out = disps->disps;
1793         for(S = 0; S < corners; S++) {
1794                 for(y = 0; y < side; ++y) {
1795                         for(x = 0; x < side; ++x, ++out) {
1796                                 float (*dispgrid)[3];
1797                                 float *data;
1798
1799                                 if(x != 0 && y != 0) continue;
1800
1801                                 if(corners == 4) {
1802                                         if(S == 0) {
1803                                                 if(y == 0) {
1804                                                         dispgrid = &disps->disps[1*side*side];
1805                                                         data = dispgrid[side * x + 0];
1806
1807                                                         (*out)[0] = (*out)[0] + data[1];
1808                                                         (*out)[1] = (*out)[1] - data[0];
1809                                                         (*out)[2] = (*out)[2] + data[2];
1810
1811                                                         mul_v3_fl(*out, 0.5);
1812
1813                                                         data[0] = -(*out)[1];
1814                                                         data[1] = (*out)[0];
1815                                                         data[2] = (*out)[2];
1816                                                 } else if (x == 0) {
1817                                                         dispgrid = &disps->disps[3 * side * side];
1818                                                         data = dispgrid[side * 0 + y];
1819
1820                                                         (*out)[0] = (*out)[0] - data[1];
1821                                                         (*out)[1] = (*out)[1] + data[0];
1822                                                         (*out)[2] = (*out)[2] + data[2];
1823
1824                                                         mul_v3_fl(*out, 0.5);
1825
1826                                                         data[0] = (*out)[1];
1827                                                         data[1] = -(*out)[0];
1828                                                         data[2] = (*out)[2];
1829                                                 }
1830                                         } else if (S == 2) {
1831                                                 if(y == 0) {
1832                                                         dispgrid = &disps->disps[3 * side * side];
1833                                                         data = dispgrid[side * x + 0];
1834
1835                                                         (*out)[0] = (*out)[0] + data[1];
1836                                                         (*out)[1] = (*out)[1] - data[0];
1837                                                         (*out)[2] = (*out)[2] + data[2];
1838
1839                                                         mul_v3_fl(*out, 0.5);
1840
1841                                                         data[0] = -(*out)[1];
1842                                                         data[1] = (*out)[0];
1843                                                         data[2] = (*out)[2];
1844                                                 } else if(x == 0) {
1845                                                         dispgrid = &disps->disps[1 * side * side];
1846                                                         data = dispgrid[side * 0 + y];
1847
1848                                                         (*out)[0] = (*out)[0] - data[1];
1849                                                         (*out)[1] = (*out)[1] + data[0];
1850                                                         (*out)[2] = (*out)[2] + data[2];
1851
1852                                                         mul_v3_fl(*out, 0.5);
1853
1854                                                         data[0] = (*out)[1];
1855                                                         data[1] = -(*out)[0];
1856                                                         data[2] = (*out)[2];
1857                                                 }
1858                                         }
1859                                 } else if (corners == 3) {
1860                                         if(S == 0) {
1861                                                 if(y == 0) {
1862                                                         dispgrid = &disps->disps[1*side*side];
1863                                                         data = dispgrid[side * x + 0];
1864
1865                                                         (*out)[0] = (*out)[0] + data[1];
1866                                                         (*out)[1] = (*out)[1] - data[0];
1867                                                         (*out)[2] = (*out)[2] + data[2];
1868
1869                                                         mul_v3_fl(*out, 0.5);
1870
1871                                                         data[0] = -(*out)[1];
1872                                                         data[1] = (*out)[0];
1873                                                         data[2] = (*out)[2];
1874                                                 } else if (x == 0) {
1875                                                         dispgrid = &disps->disps[2 * side * side];
1876                                                         data = dispgrid[side * 0 + y];
1877
1878                                                         (*out)[0] = (*out)[0] - data[1];
1879                                                         (*out)[1] = (*out)[1] + data[0];
1880                                                         (*out)[2] = (*out)[2] + data[2];
1881
1882                                                         mul_v3_fl(*out, 0.5);
1883
1884                                                         data[0] = (*out)[1];
1885                                                         data[1] = -(*out)[0];
1886                                                         data[2] = (*out)[2];
1887                                                 }
1888                                         } else if (S == 2) {
1889                                                 if(x == 0) {
1890                                                         dispgrid = &disps->disps[1 * side * side];
1891                                                         data = dispgrid[side * 0 + y];
1892
1893                                                         (*out)[0] = (*out)[0] - data[1];
1894                                                         (*out)[1] = (*out)[1] + data[0];
1895                                                         (*out)[2] = (*out)[2] + data[2];
1896
1897                                                         mul_v3_fl(*out, 0.5);
1898
1899                                                         data[0] = (*out)[1];
1900                                                         data[1] = -(*out)[0];
1901                                                         data[2] = (*out)[2];
1902                                                 }
1903                                         }
1904                                 }
1905                         }
1906                 }
1907         }
1908 }
1909
1910 /***************** Multires interpolation stuff *****************/
1911
1912 static void mdisp_get_crn_rect(int face_side, float crn[3][4][2])
1913 {
1914         float offset = face_side*0.5f - 0.5f;
1915         float mid[2];
1916
1917         mid[0] = offset * 4 / 3;
1918         mid[1] = offset * 2 / 3;
1919
1920         crn[0][0][0] = mid[0]; crn[0][0][1] = mid[1];
1921         crn[0][1][0] = offset; crn[0][1][1] = 0;
1922         crn[0][2][0] = 0; crn[0][2][1] = 0;
1923         crn[0][3][0] = offset; crn[0][3][1] = offset;
1924
1925         crn[1][0][0] = mid[0]; crn[1][0][1] = mid[1];
1926         crn[1][1][0] = offset * 2; crn[1][1][1] = offset;
1927         crn[1][2][0] = offset * 2; crn[1][2][1] = 0;
1928         crn[1][3][0] = offset; crn[1][3][1] = 0;
1929
1930         crn[2][0][0] = mid[0]; crn[2][0][1] = mid[1];
1931         crn[2][1][0] = offset; crn[2][1][1] = offset;
1932         crn[2][2][0] = offset * 2; crn[2][2][1] = offset * 2;
1933         crn[2][3][0] = offset * 2; crn[2][3][1] = offset;
1934 }
1935
1936 static int mdisp_pt_in_crn(float p[2], float crn[4][2])
1937 {
1938         float v[2][2];
1939         float a[2][2];
1940
1941         sub_v2_v2v2(v[0], crn[1], crn[0]);
1942         sub_v2_v2v2(v[1], crn[3], crn[0]);
1943
1944         sub_v2_v2v2(a[0], p, crn[0]);
1945         sub_v2_v2v2(a[1], crn[2], crn[0]);
1946
1947         if(cross_v2v2(a[0], v[0]) * cross_v2v2(a[1], v[0]) < 0)
1948                 return 0;
1949
1950         if(cross_v2v2(a[0], v[1]) * cross_v2v2(a[1], v[1]) < 0)
1951                 return 0;
1952
1953         return 1;
1954 }
1955
1956 static void face_to_crn_interp(float u, float v, float v1[2], float v2[2], float v3[2], float v4[2], float *x)
1957 {
1958         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];
1959         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];
1960         float c = (v3[1]-v)*v1[0]+(-v3[1]+v1[1])*u+v3[0]*v-v1[1]*v3[0];
1961         float d = b * b - 4 * a * c;
1962         float x1, x2;
1963
1964         if(a == 0) {
1965                 *x = -c / b;
1966                 return;
1967         }
1968
1969         x1 = (-b - sqrtf(d)) / (2 * a);
1970         x2 = (-b + sqrtf(d)) / (2 * a);
1971
1972         *x = maxf(x1, x2);
1973 }
1974
1975 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)
1976 {
1977         float offset = face_side*0.5f - 0.5f;
1978
1979         if(corners == 4) {
1980                 if(S == 1) { *u= offset + x; *v = offset - y; }
1981                 if(S == 2) { *u= offset + y; *v = offset + x; }
1982                 if(S == 3) { *u= offset - x; *v = offset + y; }
1983                 if(S == 0) { *u= offset - y; *v = offset - x; }
1984         } else {
1985                 float crn[3][4][2], vec[4][2];
1986                 float p[2];
1987
1988                 mdisp_get_crn_rect(face_side, crn);
1989
1990                 interp_v2_v2v2(vec[0], crn[S][0], crn[S][1], x / offset);
1991                 interp_v2_v2v2(vec[1], crn[S][3], crn[S][2], x / offset);
1992                 interp_v2_v2v2(vec[2], crn[S][0], crn[S][3], y / offset);
1993                 interp_v2_v2v2(vec[3], crn[S][1], crn[S][2], y / offset);
1994
1995                 isect_seg_seg_v2_point(vec[0], vec[1], vec[2], vec[3], p);
1996
1997                 (*u) = p[0];
1998                 (*v) = p[1];
1999         }
2000 }
2001
2002 /* Find per-corner coordinate with given per-face UV coord */
2003 int mdisp_rot_face_to_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2004 {
2005         const float offset = face_side*0.5f - 0.5f;
2006         int S = 0;
2007
2008         if (corners == 4) {
2009                 if(u <= offset && v <= offset) S = 0;
2010                 else if(u > offset  && v <= offset) S = 1;
2011                 else if(u > offset  && v > offset) S = 2;
2012                 else if(u <= offset && v >= offset)  S = 3;
2013
2014                 if(S == 0) {
2015                         *y = offset - u;
2016                         *x = offset - v;
2017                 } else if(S == 1) {
2018                         *x = u - offset;
2019                         *y = offset - v;
2020                 } else if(S == 2) {
2021                         *y = u - offset;
2022                         *x = v - offset;
2023                 } else if(S == 3) {
2024                         *x= offset - u;
2025                         *y = v - offset;
2026                 }
2027         } else {
2028                 int grid_size = offset;
2029                 float w = (face_side - 1) - u - v;
2030                 float W1, W2;
2031
2032                 if (u >= v && u >= w) {S = 0; W1= w; W2= v;}
2033                 else if (v >= u && v >= w) {S = 1; W1 = u; W2 = w;}
2034                 else {S = 2; W1 = v; W2 = u;}
2035
2036                 W1 /= (face_side-1);
2037                 W2 /= (face_side-1);
2038
2039                 *x = (1-(2*W1)/(1-W2)) * grid_size;
2040                 *y = (1-(2*W2)/(1-W1)) * grid_size;
2041         }
2042
2043         return S;
2044 }
2045
2046 /* Find per-corner coordinate with given per-face UV coord
2047    Practically as the previous funciton but it assumes a bit different coordinate system for triangles
2048    which is optimized for MDISP layer interpolation:
2049
2050    v
2051    ^
2052    |      /|
2053    |    /  |
2054    |  /    |
2055    |/______|___> u
2056
2057  */
2058 int mdisp_rot_face_to_quad_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2059 {
2060         const float offset = face_side*0.5f - 0.5f;
2061         int S = 0;
2062
2063         if (corners == 4) {
2064                 if(u <= offset && v <= offset) S = 0;
2065                 else if(u > offset  && v <= offset) S = 1;
2066                 else if(u > offset  && v > offset) S = 2;
2067                 else if(u <= offset && v >= offset)  S = 3;
2068
2069                 if(S == 0) {
2070                         *y = offset - u;
2071                         *x = offset - v;
2072                 } else if(S == 1) {
2073                         *x = u - offset;
2074                         *y = offset - v;
2075                 } else if(S == 2) {
2076                         *y = u - offset;
2077                         *x = v - offset;
2078                 } else if(S == 3) {
2079                         *x= offset - u;
2080                         *y = v - offset;
2081                 }
2082         } else {
2083                 float crn[3][4][2];
2084                 float p[2] = {u, v};
2085
2086                 mdisp_get_crn_rect(face_side, crn);
2087
2088                 for (S = 0; S < 3; ++S) {
2089                         if (mdisp_pt_in_crn(p, crn[S]))
2090                                 break;
2091                 }
2092
2093                 face_to_crn_interp(u, v, crn[S][0], crn[S][1], crn[S][3], crn[S][2], &p[0]);
2094                 face_to_crn_interp(u, v, crn[S][0], crn[S][3], crn[S][1], crn[S][2], &p[1]);
2095
2096                 *x = p[0] * offset;
2097                 *y = p[1] * offset;
2098         }
2099
2100         return S;
2101 }
2102
2103 void mdisp_apply_weight(const int S, const int corners, int x, int y, const int face_side,
2104         float crn_weight[4][2], float *u_r, float *v_r)
2105 {
2106         float u, v, xl, yl;
2107         float mid1[2], mid2[2], mid3[2];
2108
2109         mdisp_rot_crn_to_face(S, corners, face_side, x, y, &u, &v);
2110
2111         if(corners == 4) {
2112                 xl = u / (face_side - 1);
2113                 yl = v / (face_side - 1);
2114
2115                 mid1[0] = crn_weight[0][0] * (1 - xl) + crn_weight[1][0] * xl;
2116                 mid1[1] = crn_weight[0][1] * (1 - xl) + crn_weight[1][1] * xl;
2117                 mid2[0] = crn_weight[3][0] * (1 - xl) + crn_weight[2][0] * xl;
2118                 mid2[1] = crn_weight[3][1] * (1 - xl) + crn_weight[2][1] * xl;
2119                 mid3[0] = mid1[0] * (1 - yl) + mid2[0] * yl;
2120                 mid3[1] = mid1[1] * (1 - yl) + mid2[1] * yl;
2121         } else {
2122                 yl = v / (face_side - 1);
2123
2124                 if(v == face_side - 1) xl = 1;
2125                 else xl = 1 - (face_side - 1 - u) / (face_side - 1 - v);
2126
2127                 mid1[0] = crn_weight[0][0] * (1 - xl) + crn_weight[1][0] * xl;
2128                 mid1[1] = crn_weight[0][1] * (1 - xl) + crn_weight[1][1] * xl;
2129                 mid3[0] = mid1[0] * (1 - yl) + crn_weight[2][0] * yl;
2130                 mid3[1] = mid1[1] * (1 - yl) + crn_weight[2][1] * yl;
2131         }
2132
2133         *u_r = mid3[0];
2134         *v_r = mid3[1];
2135 }
2136
2137 void mdisp_flip_disp(const int S, const int corners, const float axis_x[2], const float axis_y[2], float disp[3])
2138 {
2139         float crn_x[2], crn_y[2];
2140         float vx[2], vy[2], coord[2];
2141
2142         if (corners == 4) {
2143                 float x[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
2144                 float y[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
2145
2146                 copy_v2_v2(crn_x, x[S]);
2147                 copy_v2_v2(crn_y, y[S]);
2148
2149                 mul_v2_v2fl(vx, crn_x, disp[0]);
2150                 mul_v2_v2fl(vy, crn_y, disp[1]);
2151                 add_v2_v2v2(coord, vx, vy);
2152
2153                 project_v2_v2v2(vx, coord, axis_x);
2154                 project_v2_v2v2(vy, coord, axis_y);
2155
2156                 disp[0] = len_v2(vx);
2157                 disp[1] = len_v2(vy);
2158
2159                 if(dot_v2v2(vx, axis_x) < 0)
2160                         disp[0] = -disp[0];
2161
2162                 if(dot_v2v2(vy, axis_y) < 0)
2163                         disp[1] = -disp[1];
2164         } else {
2165                 /* XXX: it was very overhead code to support displacement flipping
2166                         for case of tris without visible profit.
2167                         Maybe its not really big limitation? for now? (nazgul) */
2168                 disp[0] = 0;
2169                 disp[1] = 0;
2170         }
2171 }
2172
2173 /* Join two triangular displacements into one quad
2174          Corners mapping:
2175          2 -------- 3
2176          | \   tri2 |
2177          |    \     |
2178          | tri1  \  |
2179          0 -------- 1 */
2180 void mdisp_join_tris(MDisps *dst, MDisps *tri1, MDisps *tri2)
2181 {
2182         int side, st;
2183         int S, x, y, crn;
2184         float face_u, face_v, crn_u, crn_v;
2185         float (*out)[3];
2186         MDisps *src;
2187
2188         if(dst->disps)
2189                 MEM_freeN(dst->disps);
2190
2191         side = sqrt(tri1->totdisp / 3);
2192         st = (side<<1)-1;
2193
2194         dst->totdisp = 4 * side * side;
2195         out = dst->disps = MEM_callocN(3*dst->totdisp*sizeof(float), "join disps");
2196
2197         for(S = 0; S < 4; S++)
2198                 for(y = 0; y < side; ++y)
2199                         for(x = 0; x < side; ++x, ++out) {
2200                                 mdisp_rot_crn_to_face(S, 4, st, x, y, &face_u, &face_v);
2201                                 face_u = st - 1 - face_u;
2202
2203                                 if(face_v > face_u) {
2204                                         src = tri2;
2205                                         face_u = st - 1 - face_u;
2206                                         face_v = st - 1 - face_v;
2207                                 } else src = tri1;
2208
2209                                 crn = mdisp_rot_face_to_quad_crn(3, st, face_u, face_v, &crn_u, &crn_v);
2210
2211                                 old_mdisps_bilinear((*out), &src->disps[crn*side*side], side, crn_u, crn_v);
2212                                 (*out)[0] = 0;
2213                                 (*out)[1] = 0;
2214                         }
2215 }