python api for ID property access by Joseph Eager, copied from blender 2.4x.
[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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, 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 #include "MEM_guardedalloc.h"
31
32 #include "DNA_key_types.h"
33 #include "DNA_mesh_types.h"
34 #include "DNA_meshdata_types.h"
35 #include "DNA_modifier_types.h"
36 #include "DNA_object_types.h"
37 #include "DNA_scene_types.h"
38 #include "DNA_view3d_types.h"
39
40 #include "BLI_math.h"
41 #include "BLI_blenlib.h"
42
43 #include "BKE_cdderivedmesh.h"
44 #include "BKE_customdata.h"
45 #include "BKE_depsgraph.h"
46 #include "BKE_DerivedMesh.h"
47 #include "BKE_global.h"
48 #include "BKE_mesh.h"
49 #include "BKE_modifier.h"
50 #include "BKE_multires.h"
51 #include "BKE_object.h"
52 #include "BKE_subsurf.h"
53
54 #include <math.h>
55 #include <string.h>
56
57 /* MULTIRES MODIFIER */
58 static const int multires_max_levels = 13;
59 static const int multires_quad_tot[] = {4, 9, 25, 81, 289, 1089, 4225, 16641, 66049, 263169, 1050625, 4198401, 16785409};
60 static const int multires_side_tot[] = {2, 3, 5,  9,  17,  33,   65,   129,   257,   513,    1025,    2049,    4097};
61
62 MultiresModifierData *find_multires_modifier(Object *ob)
63 {
64         ModifierData *md;
65         MultiresModifierData *mmd = NULL;
66
67         for(md = ob->modifiers.first; md; md = md->next) {
68                 if(md->type == eModifierType_Multires) {
69                         mmd = (MultiresModifierData*)md;
70                         break;
71                 }
72         }
73
74         return mmd;
75
76 }
77
78 int multiresModifier_switch_level(Object *ob, const int distance)
79 {
80         MultiresModifierData *mmd = find_multires_modifier(ob);
81
82         if(mmd) {
83                 mmd->lvl += distance;
84                 if(mmd->lvl < 1) mmd->lvl = 1;
85                 else if(mmd->lvl > mmd->totlvl) mmd->lvl = mmd->totlvl;
86                 /* XXX: DAG_id_flush_update(&ob->id, OB_RECALC_DATA); 
87                    object_handle_update(ob);*/
88                 return 1;
89         }
90         else
91                 return 0;
92 }
93
94 /* XXX */
95 #if 0
96 void multiresModifier_join(Object *ob)
97 {
98         Base *base = NULL;
99         int highest_lvl = 0;
100
101         /* First find the highest level of subdivision */
102         base = FIRSTBASE;
103         while(base) {
104                 if(TESTBASELIB_BGMODE(v3d, scene, base) && base->object->type==OB_MESH) {
105                         ModifierData *md;
106                         for(md = base->object->modifiers.first; md; md = md->next) {
107                                 if(md->type == eModifierType_Multires) {
108                                         int totlvl = ((MultiresModifierData*)md)->totlvl;
109                                         if(totlvl > highest_lvl)
110                                                 highest_lvl = totlvl;
111
112                                         /* Ensure that all updates are processed */
113                                         multires_force_update(base->object);
114                                 }
115                         }
116                 }
117                 base = base->next;
118         }
119
120         /* No multires meshes selected */
121         if(highest_lvl == 0)
122                 return;
123
124         /* Subdivide all the displacements to the highest level */
125         base = FIRSTBASE;
126         while(base) {
127                 if(TESTBASELIB_BGMODE(v3d, scene, base) && base->object->type==OB_MESH) {
128                         ModifierData *md = NULL;
129                         MultiresModifierData *mmd = NULL;
130
131                         for(md = base->object->modifiers.first; md; md = md->next) {
132                                 if(md->type == eModifierType_Multires)
133                                         mmd = (MultiresModifierData*)md;
134                         }
135
136                         /* If the object didn't have multires enabled, give it a new modifier */
137                         if(!mmd) {
138                                 md = base->object->modifiers.first;
139                                 
140                                 while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
141                                         md = md->next;
142                                 
143                                 mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
144                                 BLI_insertlinkbefore(&base->object->modifiers, md, mmd);
145                                 modifier_unique_name(&base->object->modifiers, mmd);
146                         }
147
148                         if(mmd)
149                                 multiresModifier_subdivide(mmd, base->object, highest_lvl - mmd->totlvl, 0, 0);
150                 }
151                 base = base->next;
152         }
153 }
154 #endif
155
156 /* Returns 0 on success, 1 if the src's totvert doesn't match */
157 int multiresModifier_reshape(MultiresModifierData *mmd, Object *dst, Object *src)
158 {
159         Mesh *src_me = get_mesh(src);
160         DerivedMesh *mrdm = dst->derivedFinal;
161
162         if(mrdm && mrdm->getNumVerts(mrdm) == src_me->totvert) {
163                 MVert *mvert = CDDM_get_verts(mrdm);
164                 int i;
165
166                 for(i = 0; i < src_me->totvert; ++i)
167                         copy_v3_v3(mvert[i].co, src_me->mvert[i].co);
168                 mrdm->needsFree = 1;
169                 MultiresDM_mark_as_modified(mrdm);
170                 mrdm->release(mrdm);
171                 dst->derivedFinal = NULL;
172
173                 return 0;
174         }
175
176         return 1;
177 }
178
179 static void Mat3FromColVecs(float mat[][3], float v1[3], float v2[3], float v3[3])
180 {
181         copy_v3_v3(mat[0], v1);
182         copy_v3_v3(mat[1], v2);
183         copy_v3_v3(mat[2], v3);
184 }
185
186 static DerivedMesh *multires_subdisp_pre(DerivedMesh *mrdm, int distance, int simple)
187 {
188         DerivedMesh *final;
189         SubsurfModifierData smd;
190
191         memset(&smd, 0, sizeof(SubsurfModifierData));
192         smd.levels = distance;
193         if(simple)
194                 smd.subdivType = ME_SIMPLE_SUBSURF;
195
196         final = subsurf_make_derived_from_derived_with_multires(mrdm, &smd, NULL, 0, NULL, 0, 0);
197
198         return final;
199 }
200
201 static void VecAddUf(float a[3], float b[3])
202 {
203         a[0] += b[0];
204         a[1] += b[1];
205         a[2] += b[2];
206 }
207
208 static void multires_subdisp(DerivedMesh *orig, Object *ob, DerivedMesh *final, int lvl, int totlvl,
209                              int totsubvert, int totsubedge, int totsubface, int addverts)
210 {
211         DerivedMesh *mrdm;
212         Mesh *me = ob->data;
213         MultiresModifierData mmd_sub;
214         MVert *mvs = CDDM_get_verts(final);
215         MVert *mvd, *mvd_f1, *mvs_f1, *mvd_f3, *mvd_f4;
216         MVert *mvd_f2, *mvs_f2, *mvs_e1, *mvd_e1, *mvs_e2;
217         int totvert;
218         int slo1 = multires_side_tot[lvl - 1];
219         int sll = slo1 / 2;
220         int slo2 = multires_side_tot[totlvl - 2];
221         int shi2 = multires_side_tot[totlvl - 1];
222         int skip = multires_side_tot[totlvl - lvl] - 1;
223         int i, j, k;
224
225         memset(&mmd_sub, 0, sizeof(MultiresModifierData));
226         mmd_sub.lvl = mmd_sub.totlvl = totlvl;
227         mrdm = multires_dm_create_from_derived(&mmd_sub, 1, orig, ob, 0, 0);
228                 
229         mvd = CDDM_get_verts(mrdm);
230         /* Need to map from ccg to mrdm */
231         totvert = mrdm->getNumVerts(mrdm);
232
233         if(!addverts) {
234                 for(i = 0; i < totvert; ++i) {
235                         float z[3] = {0,0,0};
236                         copy_v3_v3(mvd[i].co, z);
237                 }
238         }
239
240         /* Load base verts */
241         for(i = 0; i < me->totvert; ++i)
242                 VecAddUf(mvd[totvert - me->totvert + i].co, mvs[totvert - me->totvert + i].co);
243
244         mvd_f1 = mvd;
245         mvs_f1 = mvs;
246         mvd_f2 = mvd;
247         mvs_f2 = mvs + totvert - totsubvert;
248         mvs_e1 = mvs + totsubface * (skip-1) * (skip-1);
249
250         for(i = 0; i < me->totface; ++i) {
251                 const int end = me->mface[i].v4 ? 4 : 3;
252                 int x, y, x2, y2, mov= 0;
253
254                 mvd_f1 += 1 + end * (slo2-2); //center+edgecross
255                 mvd_f3 = mvd_f4 = mvd_f1;
256
257                 for(j = 0; j < end; ++j) {
258                         mvd_f1 += (skip/2 - 1) * (slo2 - 2) + (skip/2 - 1);
259                         /* Update sub faces */
260                         for(y = 0; y < sll; ++y) {
261                                 for(x = 0; x < sll; ++x) {
262                                         /* Face center */
263                                         VecAddUf(mvd_f1->co, mvs_f1->co);
264                                         mvs_f1 += 1;
265
266                                         /* Now we hold the center of the subface at mvd_f1
267                                            and offset it to the edge cross and face verts */
268
269                                         /* Edge cross */
270                                         for(k = 0; k < 4; ++k) {
271                                                 if(k == 0) mov = -1;
272                                                 else if(k == 1) mov = slo2 - 2;
273                                                 else if(k == 2) mov = 1;
274                                                 else if(k == 3) mov = -(slo2 - 2);
275
276                                                 for(x2 = 1; x2 < skip/2; ++x2) {
277                                                         VecAddUf((mvd_f1 + mov * x2)->co, mvs_f1->co);
278                                                         ++mvs_f1;
279                                                 }
280                                         }
281
282                                         /* Main face verts */
283                                         for(k = 0; k < 4; ++k) {
284                                                 int movx= 0, movy= 0;
285
286                                                 if(k == 0) { movx = -1; movy = -(slo2 - 2); }
287                                                 else if(k == 1) { movx = slo2 - 2; movy = -1; }
288                                                 else if(k == 2) { movx = 1; movy = slo2 - 2; }
289                                                 else if(k == 3) { movx = -(slo2 - 2); movy = 1; }
290
291                                                 for(y2 = 1; y2 < skip/2; ++y2) {
292                                                         for(x2 = 1; x2 < skip/2; ++x2) {
293                                                                 VecAddUf((mvd_f1 + movy * y2 + movx * x2)->co, mvs_f1->co);
294                                                                 ++mvs_f1;
295                                                         }
296                                                 }
297                                         }
298                                                         
299                                         mvd_f1 += skip;
300                                 }
301                                 mvd_f1 += (skip - 1) * (slo2 - 2) - 1;
302                         }
303                         mvd_f1 -= (skip - 1) * (slo2 - 2) - 1 + skip;
304                         mvd_f1 += (slo2 - 2) * (skip/2-1) + skip/2-1 + 1;
305                 }
306
307                 /* update face center verts */
308                 VecAddUf(mvd_f2->co, mvs_f2->co);
309
310                 mvd_f2 += 1;
311                 mvs_f2 += 1;
312
313                 /* update face edge verts */
314                 for(j = 0; j < end; ++j) {
315                         MVert *restore;
316
317                         /* Super-face edge cross */
318                         for(k = 0; k < skip-1; ++k) {
319                                 VecAddUf(mvd_f2->co, mvs_e1->co);
320                                 mvd_f2++;
321                                 mvs_e1++;
322                         }
323                         for(x = 1; x < sll; ++x) {
324                                 VecAddUf(mvd_f2->co, mvs_f2->co);
325                                 mvd_f2++;
326                                 mvs_f2++;
327
328                                 for(k = 0; k < skip-1; ++k) {
329                                         VecAddUf(mvd_f2->co, mvs_e1->co);
330                                         mvd_f2++;
331                                         mvs_e1++;
332                                 }
333                         }
334
335                         restore = mvs_e1;
336                         for(y = 0; y < sll - 1; ++y) {
337                                 for(x = 0; x < sll; ++x) {
338                                         for(k = 0; k < skip - 1; ++k) {
339                                                 VecAddUf(mvd_f3[(skip-1)+(y*skip) + (x*skip+k)*(slo2-2)].co,
340                                                          mvs_e1->co);
341                                                 ++mvs_e1;
342                                         }
343                                         mvs_e1 += skip-1;
344                                 }
345                         }
346                         
347                         mvs_e1 = restore + skip - 1;
348                         for(y = 0; y < sll - 1; ++y) {
349                                 for(x = 0; x < sll; ++x) {
350                                         for(k = 0; k < skip - 1; ++k) {
351                                                 VecAddUf(mvd_f3[(slo2-2)*(skip-1)+(x*skip)+k + y*skip*(slo2-2)].co,
352                                                          mvs_e1->co);
353                                                 ++mvs_e1;
354                                         }
355                                         mvs_e1 += skip - 1;
356                                 }
357                         }
358
359                         mvd_f3 += (slo2-2)*(slo2-2);
360                         mvs_e1 -= skip - 1;
361                 }
362
363                 /* update base (2) face verts */
364                 for(j = 0; j < end; ++j) {
365                         mvd_f2 += (slo2 - 1) * (skip - 1);
366                         for(y = 0; y < sll - 1; ++y) {
367                                 for(x = 0; x < sll - 1; ++x) {
368                                         VecAddUf(mvd_f2->co, mvs_f2->co);
369                                         mvd_f2 += skip;
370                                         ++mvs_f2;
371                                 }
372                                 mvd_f2 += (slo2 - 1) * (skip - 1);
373                         }
374                         mvd_f2 -= (skip - 1);
375                 }
376         }
377
378         /* edges */
379         mvd_e1 = mvd + totvert - me->totvert - me->totedge * (shi2-2);
380         mvs_e2 = mvs + totvert - me->totvert - me->totedge * (slo1-2);
381         for(i = 0; i < me->totedge; ++i) {
382                 for(j = 0; j < skip - 1; ++j) {
383                         VecAddUf(mvd_e1->co, mvs_e1->co);
384                         mvd_e1++;
385                         mvs_e1++;
386                 }
387                 for(j = 0; j < slo1 - 2; j++) {
388                         VecAddUf(mvd_e1->co, mvs_e2->co);
389                         mvd_e1++;
390                         mvs_e2++;
391                         
392                         for(k = 0; k < skip - 1; ++k) {
393                                 VecAddUf(mvd_e1->co, mvs_e1->co);
394                                 mvd_e1++;
395                                 mvs_e1++;
396                         }
397                 }
398         }
399
400         final->needsFree  = 1;
401         final->release(final);
402         mrdm->needsFree = 1;
403         MultiresDM_mark_as_modified(mrdm);
404         mrdm->release(mrdm);
405 }
406
407 /* direction=1 for delete higher, direction=0 for lower (not implemented yet) */
408 void multiresModifier_del_levels(struct MultiresModifierData *mmd, struct Object *ob, int direction)
409 {
410         Mesh *me = get_mesh(ob);
411         int distance = mmd->totlvl - mmd->lvl;
412         MDisps *mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
413
414         multires_force_update(ob);
415
416         if(mdisps && distance > 0 && direction == 1) {
417                 int skip = multires_side_tot[distance] - 1;
418                 int st = multires_side_tot[mmd->totlvl - 1];
419                 int totdisp = multires_quad_tot[mmd->lvl - 1];
420                 int i, j, x, y;
421
422                 for(i = 0; i < me->totface; ++i) {
423                         float (*disps)[3] = MEM_callocN(sizeof(float) * 3 * totdisp, "multires del disps");
424                         
425                         for(j = 0, y = 0; y < st; y += skip) {
426                                 for(x = 0; x < st; x += skip) {
427                                         copy_v3_v3(disps[j], mdisps[i].disps[y * st + x]);
428                                         ++j;
429                                 }
430                         }
431
432                         MEM_freeN(mdisps[i].disps);
433                         mdisps[i].disps = disps;
434                         mdisps[i].totdisp = totdisp;
435                 }
436         }
437
438         mmd->totlvl = mmd->lvl;
439 }
440
441 void multiresModifier_subdivide(MultiresModifierData *mmd, Object *ob, int distance, int updateblock, int simple)
442 {
443         DerivedMesh *final = NULL;
444         int totsubvert = 0, totsubface = 0, totsubedge = 0;
445         Mesh *me = get_mesh(ob);
446         MDisps *mdisps;
447         int i;
448
449         if(distance == 0)
450                 return;
451
452         if(mmd->totlvl > multires_max_levels)
453                 mmd->totlvl = multires_max_levels;
454         if(mmd->lvl > multires_max_levels)
455                 mmd->lvl = multires_max_levels;
456
457         multires_force_update(ob);
458
459         mmd->lvl = mmd->totlvl;
460         mmd->totlvl += distance;
461
462         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
463         if(!mdisps)
464                 mdisps = CustomData_add_layer(&me->fdata, CD_MDISPS, CD_DEFAULT, NULL, me->totface);
465
466         if(mdisps->disps && !updateblock && mmd->totlvl > 2) {
467                 DerivedMesh *orig, *mrdm;
468                 MultiresModifierData mmd_sub;
469
470                 orig = CDDM_from_mesh(me, NULL);
471                 memset(&mmd_sub, 0, sizeof(MultiresModifierData));
472                 mmd_sub.lvl = mmd_sub.totlvl = mmd->lvl;
473                 mmd_sub.simple = simple;
474                 mrdm = multires_dm_create_from_derived(&mmd_sub, 1, orig, ob, 0, 0);
475                 totsubvert = mrdm->getNumVerts(mrdm);
476                 totsubedge = mrdm->getNumEdges(mrdm);
477                 totsubface = mrdm->getNumFaces(mrdm);
478                 orig->needsFree = 1;
479                 orig->release(orig);
480                 
481                 final = multires_subdisp_pre(mrdm, distance, simple);
482                 mrdm->needsFree = 1;
483                 mrdm->release(mrdm);
484         }
485
486         for(i = 0; i < me->totface; ++i) {
487                 const int totdisp = multires_quad_tot[mmd->totlvl - 1];
488                 float (*disps)[3] = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
489
490                 if(mdisps[i].disps)
491                         MEM_freeN(mdisps[i].disps);
492
493                 mdisps[i].disps = disps;
494                 mdisps[i].totdisp = totdisp;
495         }
496
497
498         if(final) {
499                 DerivedMesh *orig;
500
501                 orig = CDDM_from_mesh(me, NULL);
502
503                 multires_subdisp(orig, ob, final, mmd->lvl, mmd->totlvl, totsubvert, totsubedge, totsubface, 0);
504
505                 orig->needsFree = 1;
506                 orig->release(orig);
507         }
508
509         mmd->lvl = mmd->totlvl;
510 }
511
512 typedef struct DisplacerEdges {
513         /* DerivedMesh index at the start of each edge (using face x/y directions to define the start) */
514         int base[4];
515         /* 1 if edge moves in the positive x or y direction, -1 otherwise */
516         int dir[4];
517 } DisplacerEdges;
518
519 typedef struct DisplacerSpill {
520         /* Index of face (in base mesh), -1 for none */
521         int face;
522
523         /* Spill flag */
524         /* 1 = Negative variable axis */
525         /* 2 = Near fixed axis */
526         /* 4 = Flip axes */
527         int f;
528
529         /* Neighboring edges */
530         DisplacerEdges edges;
531 } DisplacerSpill;
532
533 typedef struct MultiresDisplacer {
534         Mesh *me;
535         MDisps *grid;
536         MFace *face;
537         
538         int dm_first_base_vert_index;
539
540         int spacing;
541         int sidetot, interior_st, disp_st;
542         int sidendx;
543         int type;
544         int invert;
545         MVert *subco;
546         int subco_index, face_index;
547         float weight;
548
549         /* Valence for each corner */
550         int valence[4];
551
552         /* Neighboring edges for current face */
553         DisplacerEdges edges_primary;
554
555         /* Neighboring faces */
556         DisplacerSpill spill_x, spill_y;
557
558         int *face_offsets;
559
560         int x, y, ax, ay;
561 } MultiresDisplacer;
562
563 static int mface_v(MFace *f, int v)
564 {
565         return v == 0 ? f->v1 : v == 1 ? f->v2 : v == 2 ? f->v3 : v == 3 ? f->v4 : -1;
566 }
567
568 /* Get the edges (and their directions) */
569 static void find_displacer_edges(MultiresDisplacer *d, DerivedMesh *dm, DisplacerEdges *de, MFace *f)
570 {
571         ListBase *emap = MultiresDM_get_vert_edge_map(dm);
572         IndexNode *n;
573         int i, end = f->v4 ? 4 : 3;
574         int offset = dm->getNumVerts(dm) - d->me->totvert - d->me->totedge * d->interior_st;
575
576         for(i = 0; i < end; ++i) {
577                 int vcur = mface_v(f, i);
578                 int vnext = mface_v(f, i == end - 1 ? 0 : i + 1);
579
580                 de->dir[i] = 1;
581                 
582                 for(n = emap[vcur].first; n; n = n->next) {
583                         MEdge *e = &d->me->medge[n->index];
584                         
585                         if(e->v1 == vnext || e->v2 == vnext) {
586                                 de->base[i] = n->index * d->interior_st;
587                                 if(((i == 0 || i == 1) && e->v1 == vnext) ||
588                                    ((i == 2 || i == 3) && e->v2 == vnext)) {
589                                         de->dir[i] = -1;
590                                         de->base[i] += d->interior_st - 1;
591                                 }
592                                 de->base[i] += offset;
593                                 break;
594                         }
595                 }
596         }
597 }
598
599 /* Returns in out the corners [0-3] that use v1 and v2 */
600 static void find_face_corners(MFace *f, int v1, int v2, int out[2])
601 {
602         int i, end = f->v4 ? 4 : 3;
603
604         for(i = 0; i < end; ++i) {
605                 int corner = mface_v(f, i);
606                 if(corner == v1)
607                         out[0] = i;
608                 if(corner == v2)
609                         out[1] = i;
610         }
611 }
612
613 static void multires_displacer_get_spill_faces(MultiresDisplacer *d, DerivedMesh *dm, MFace *mface)
614 {
615         ListBase *map = MultiresDM_get_vert_face_map(dm);
616         IndexNode *n1, *n2;
617         int v4 = d->face->v4 ? d->face->v4 : d->face->v1;
618         int crn[2], lv;
619
620         memset(&d->spill_x, 0, sizeof(DisplacerSpill));
621         memset(&d->spill_y, 0, sizeof(DisplacerSpill));
622         d->spill_x.face = d->spill_y.face = -1;
623
624         for(n1 = map[d->face->v3].first; n1; n1 = n1->next) {
625                 if(n1->index == d->face_index)
626                         continue;
627
628                 for(n2 = map[d->face->v2].first; n2; n2 = n2->next) {
629                         if(n1->index == n2->index)
630                                 d->spill_x.face = n1->index;
631                 }
632                 for(n2 = map[v4].first; n2; n2 = n2->next) {
633                         if(n1->index == n2->index)
634                                 d->spill_y.face = n1->index;
635                 }
636         }
637
638         if(d->spill_x.face != -1) {
639                 /* Neighbor of v2/v3 found, find flip and orientation */
640                 find_face_corners(&mface[d->spill_x.face], d->face->v2, d->face->v3, crn);
641                 lv = mface[d->spill_x.face].v4 ? 3 : 2;
642
643                 if(crn[0] == 0 && crn[1] == lv)
644                         d->spill_x.f = 0+2+0;
645                 else if(crn[0] == lv && crn[1] == 0)
646                         d->spill_x.f = 1+2+0;
647                 else if(crn[0] == 1 && crn[1] == 0)
648                         d->spill_x.f = 1+2+4;
649                 else if(crn[0] == 0 && crn[1] == 1)
650                         d->spill_x.f = 0+2+4;
651                 else if(crn[0] == 2 && crn[1] == 1)
652                         d->spill_x.f = 1+0+0;
653                 else if(crn[0] == 1 && crn[1] == 2)
654                         d->spill_x.f = 0+0+0;
655                 else if(crn[0] == 3 && crn[1] == 2)
656                         d->spill_x.f = 0+0+4;
657                 else if(crn[0] == 2 && crn[1] == 3)
658                         d->spill_x.f = 1+0+4;
659
660                 find_displacer_edges(d, dm, &d->spill_x.edges, &mface[d->spill_x.face]);
661         }
662
663         if(d->spill_y.face != -1) {
664                 /* Neighbor of v3/v4 found, find flip and orientation */
665                 find_face_corners(&mface[d->spill_y.face], d->face->v3, v4, crn);
666                 lv = mface[d->spill_y.face].v4 ? 3 : 2;
667
668                 if(crn[0] == 1 && crn[1] == 0)
669                         d->spill_y.f = 1+2+0;
670                 else if(crn[0] == 0 && crn[1] == 1)
671                         d->spill_y.f = 0+2+0;
672                 else if(crn[0] == 2 && crn[1] == 1)
673                         d->spill_y.f = 1+0+4;
674                 else if(crn[0] == 1 && crn[1] == 2)
675                         d->spill_y.f = 0+0+4;
676                 else if(crn[0] == 3 && crn[1] == 2)
677                         d->spill_y.f = 0+0+0;
678                 else if(crn[0] == 2 && crn[1] == 3)
679                         d->spill_y.f = 1+0+0;
680                 else if(crn[0] == 0 && crn[1] == lv)
681                         d->spill_y.f = 0+2+4;
682                 else if(crn[0] == lv && crn[1] == 0)
683                         d->spill_y.f = 1+2+4;
684
685                 find_displacer_edges(d, dm, &d->spill_y.edges, &mface[d->spill_y.face]);
686         }
687 }
688
689 static void find_corner_valences(MultiresDisplacer *d, DerivedMesh *dm)
690 {
691         int i;
692
693         d->valence[3] = -1;
694
695         /* Set the vertex valence for the corners */
696         for(i = 0; i < (d->face->v4 ? 4 : 3); ++i)
697                 d->valence[i] = BLI_countlist(&MultiresDM_get_vert_edge_map(dm)[mface_v(d->face, i)]);
698 }
699
700 static void multires_displacer_init(MultiresDisplacer *d, DerivedMesh *dm,
701                              const int face_index, const int invert)
702 {
703         Mesh *me = MultiresDM_get_mesh(dm);
704
705         d->me = me;
706         d->face = me->mface + face_index;
707         d->face_index = face_index;
708         d->face_offsets = MultiresDM_get_face_offsets(dm);
709         /* Get the multires grid from customdata */
710         d->grid = CustomData_get_layer(&me->fdata, CD_MDISPS);
711         if(d->grid)
712                 d->grid += face_index;
713
714         d->spacing = pow(2, MultiresDM_get_totlvl(dm) - MultiresDM_get_lvl(dm));
715         d->sidetot = multires_side_tot[MultiresDM_get_lvl(dm) - 1];
716         d->interior_st = d->sidetot - 2;
717         d->disp_st = multires_side_tot[MultiresDM_get_totlvl(dm) - 1];
718         d->invert = invert;
719
720         multires_displacer_get_spill_faces(d, dm, me->mface);
721         find_displacer_edges(d, dm, &d->edges_primary, d->face);
722         find_corner_valences(d, dm);
723
724         d->dm_first_base_vert_index = dm->getNumVerts(dm) - me->totvert;
725 }
726
727 static void multires_displacer_weight(MultiresDisplacer *d, const float w)
728 {
729         d->weight = w;
730 }
731
732 static void multires_displacer_anchor(MultiresDisplacer *d, const int type, const int side_index)
733 {
734         d->sidendx = side_index;
735         d->x = d->y = d->sidetot / 2;
736         d->type = type;
737
738         if(type == 2) {
739                 if(side_index == 0)
740                         d->y -= 1;
741                 else if(side_index == 1)
742                         d->x += 1;
743                 else if(side_index == 2)
744                         d->y += 1;
745                 else if(side_index == 3)
746                         d->x -= 1;
747         }
748         else if(type == 3) {
749                 if(side_index == 0) {
750                         d->x -= 1;
751                         d->y -= 1;
752                 }
753                 else if(side_index == 1) {
754                         d->x += 1;
755                         d->y -= 1;
756                 }
757                 else if(side_index == 2) {
758                         d->x += 1;
759                         d->y += 1;
760                 }
761                 else if(side_index == 3) {
762                         d->x -= 1;
763                         d->y += 1;
764                 }
765         }
766
767         d->ax = d->x;
768         d->ay = d->y;
769 }
770
771 static void multires_displacer_anchor_edge(MultiresDisplacer *d, int v1, int v2, int x)
772 {
773         d->type = 4;
774
775         if(v1 == d->face->v1) {
776                 d->x = 0;
777                 d->y = 0;
778                 if(v2 == d->face->v2)
779                         d->x += x;
780                 else if(v2 == d->face->v3) {
781                         if(x < d->sidetot / 2)
782                                 d->y = x;
783                         else {
784                                 d->x = x;
785                                 d->y = d->sidetot - 1;
786                         }
787                 }
788                 else
789                         d->y += x;
790         }
791         else if(v1 == d->face->v2) {
792                 d->x = d->sidetot - 1;
793                 d->y = 0;
794                 if(v2 == d->face->v1)
795                         d->x -= x;
796                 else
797                         d->y += x;
798         }
799         else if(v1 == d->face->v3) {
800                 d->x = d->sidetot - 1;
801                 d->y = d->sidetot - 1;
802                 if(v2 == d->face->v2)
803                         d->y -= x;
804                 else if(v2 == d->face->v1) {
805                         if(x < d->sidetot / 2)
806                                 d->x -= x;
807                         else {
808                                 d->x = 0;
809                                 d->y -= x;
810                         }
811                 }
812                 else
813                         d->x -= x;
814         }
815         else if(v1 == d->face->v4) {
816                 d->x = 0;
817                 d->y = d->sidetot - 1;
818                 if(v2 == d->face->v3)
819                         d->x += x;
820                 else
821                         d->y -= x;
822         }
823 }
824
825 static void multires_displacer_anchor_vert(MultiresDisplacer *d, const int v)
826 {
827         const int e = d->sidetot - 1;
828
829         d->type = 5;
830
831         d->x = d->y = 0;
832         if(v == d->face->v2)
833                 d->x = e;
834         else if(v == d->face->v3)
835                 d->x = d->y = e;
836         else if(v == d->face->v4)
837                 d->y = e;
838 }
839
840 static void multires_displacer_jump(MultiresDisplacer *d)
841 {
842         if(d->sidendx == 0) {
843                 d->x -= 1;
844                 d->y = d->ay;
845         }
846         else if(d->sidendx == 1) {
847                 d->x = d->ax;
848                 d->y -= 1;
849         }
850         else if(d->sidendx == 2) {
851                 d->x += 1;
852                 d->y = d->ay;
853         }
854         else if(d->sidendx == 3) {
855                 d->x = d->ax;
856                 d->y += 1;
857         }
858 }
859
860 /* Treating v1 as (0,0) and v3 as (st-1,st-1),
861    returns the index of the vertex at (x,y).
862    If x or y is >= st, wraps over to the adjacent face,
863    or if there is no adjacent face, returns -2. */
864 static int multires_index_at_loc(int face_index, int x, int y, MultiresDisplacer *d, DisplacerEdges *de)
865 {
866         int coord_edge = d->sidetot - 1; /* Max value of x/y at edge of grid */
867         int mid = d->sidetot / 2;
868         int lim = mid - 1;
869         int qtot = lim * lim;
870         int base = d->face_offsets[face_index];
871  
872         /* Edge spillover */
873         if(x == d->sidetot || y == d->sidetot) {
874                 int flags, v_axis, f_axis, lx, ly;
875
876                 if(x == d->sidetot && d->spill_x.face != -1) {
877                         flags = d->spill_x.f;
878
879                         /* Handle triangle seam between v1 and v3 */
880                         if(!d->me->mface[d->spill_x.face].v4 &&
881                            ((flags == 2 && y >= mid) || (flags == 3 && y < mid)))
882                                 flags += 2;
883
884                         v_axis = (flags & 1) ? d->sidetot - 1 - y : y;
885                         f_axis = (flags & 2) ? 1 : d->sidetot - 2;
886                         lx = f_axis, ly = v_axis;
887
888                         if(flags & 4) {
889                                 lx = v_axis;
890                                 ly = f_axis;
891                         }
892
893                         return multires_index_at_loc(d->spill_x.face, lx, ly, d, &d->spill_x.edges);
894                 }
895                 else if(y == d->sidetot && d->spill_y.face != -1) {
896                         flags = d->spill_y.f;
897
898                         /* Handle triangle seam between v1 and v3 */
899                         if(!d->me->mface[d->spill_y.face].v4 &&
900                            ((flags == 6 && x >= mid) || (flags == 7 && x < mid)))
901                                 flags = ~flags;
902
903                         v_axis = (flags & 1) ? x : d->sidetot - 1 - x;
904                         f_axis = (flags & 2) ? 1 : d->sidetot - 2;
905                         lx = v_axis, ly = f_axis;
906
907                         if(flags & 4) {
908                                 lx = f_axis;
909                                 ly = v_axis;
910                         }
911                         
912                         return multires_index_at_loc(d->spill_y.face, lx, ly, d, &d->spill_y.edges);
913                 }
914                 else
915                         return -2;
916         }
917         /* Corners */
918         else if(x == 0 && y == 0)
919                 return d->dm_first_base_vert_index + d->face->v1;
920         else if(x == coord_edge && y == 0)
921                 return d->dm_first_base_vert_index + d->face->v2;
922         else if(x == coord_edge && y == coord_edge)
923                 return d->dm_first_base_vert_index + d->face->v3;
924         else if(x == 0 && y == coord_edge)
925                 return d->dm_first_base_vert_index + d->face->v4;
926         /* Edges */
927         else if(x == 0) {
928                 if(d->face->v4)
929                         return de->base[3] + de->dir[3] * (y - 1);
930                 else
931                         return de->base[2] + de->dir[2] * (y - 1);
932         }
933         else if(y == 0)
934                 return de->base[0] + de->dir[0] * (x - 1);
935         else if(x == d->sidetot - 1)
936                 return de->base[1] + de->dir[1] * (y - 1);
937         else if(y == d->sidetot - 1)
938                 return de->base[2] + de->dir[2] * (x - 1);
939         /* Face center */
940         else if(x == mid && y == mid)
941                 return base;
942         /* Cross */
943         else if(x == mid && y < mid)
944                 return base + (mid - y);
945         else if(y == mid && x > mid)
946                 return base + lim + (x - mid);
947         else if(x == mid && y > mid)
948                 return base + lim*2 + (y - mid);
949         else if(y == mid && x < mid) {
950                 if(d->face->v4)
951                         return base + lim*3 + (mid - x);
952                 else
953                         return base + lim*2 + (mid - x);
954         }
955         /* Quarters */
956         else {
957                 int offset = base + lim * (d->face->v4 ? 4 : 3);
958                 if(x < mid && y < mid)
959                         return offset + ((mid - x - 1)*lim + (mid - y));
960                 else if(x > mid && y < mid)
961                         return offset + qtot + ((mid - y - 1)*lim + (x - mid));
962                 else if(x > mid && y > mid)
963                         return offset + qtot*2 + ((x - mid - 1)*lim + (y - mid));
964                 else if(x < mid && y > mid)
965                         return offset + qtot*3 + ((y - mid - 1)*lim + (mid - x));
966         }
967                 
968         return -1;
969 }
970
971 /* Calculate the TS matrix used for applying displacements.
972    Uses the undisplaced subdivided mesh's curvature to find a
973    smoothly normal and tangents. */
974 static void calc_disp_mat(MultiresDisplacer *d, float mat[3][3])
975 {
976         int u = multires_index_at_loc(d->face_index, d->x + 1, d->y, d, &d->edges_primary);
977         int v = multires_index_at_loc(d->face_index, d->x, d->y + 1, d, &d->edges_primary);
978         float norm[3], t1[3], t2[3], inv[3][3];
979         MVert *base = d->subco + d->subco_index;
980
981         //printf("f=%d, x=%d, y=%d, i=%d, u=%d, v=%d ", d->face_index, d->x, d->y, d->subco_index, u, v);
982         
983         norm[0] = base->no[0] / 32767.0f;
984         norm[1] = base->no[1] / 32767.0f;
985         norm[2] = base->no[2] / 32767.0f;
986
987         /* Special handling for vertices of valence 3 */
988         if(d->valence[1] == 3 && d->x == d->sidetot - 1 && d->y == 0)
989                 u = -1;
990         else if(d->valence[2] == 3 && d->x == d->sidetot - 1 && d->y == d->sidetot - 1)
991                 u = v = -1;
992         else if(d->valence[3] == 3 && d->x == 0 && d->y == d->sidetot - 1)
993                 v = -1;
994
995         /* If either u or v is -2, it's on a boundary. In this
996            case, back up by one row/column and use the same
997            vector as the preceeding sub-edge. */
998
999         if(u < 0) {
1000                 u = multires_index_at_loc(d->face_index, d->x - 1, d->y, d, &d->edges_primary);
1001                 sub_v3_v3v3(t1, base->co, d->subco[u].co);
1002         }
1003         else
1004                 sub_v3_v3v3(t1, d->subco[u].co, base->co);
1005
1006         if(v < 0) {
1007                 v = multires_index_at_loc(d->face_index, d->x, d->y - 1, d, &d->edges_primary);
1008                 sub_v3_v3v3(t2, base->co, d->subco[v].co);
1009         }
1010         else
1011                 sub_v3_v3v3(t2, d->subco[v].co, base->co);
1012
1013         //printf("uu=%d, vv=%d\n", u, v);
1014
1015         normalize_v3(t1);
1016         normalize_v3(t2);
1017         Mat3FromColVecs(mat, t1, t2, norm);
1018
1019         if(d->invert) {
1020                 invert_m3_m3(inv, mat);
1021                 copy_m3_m3(mat, inv);
1022         }
1023 }
1024
1025 static void multires_displace(MultiresDisplacer *d, float co[3])
1026 {
1027         float disp[3], mat[3][3];
1028         float *data;
1029         MVert *subco = &d->subco[d->subco_index];
1030
1031         if(!d->grid || !d->grid->disps) return;
1032
1033         data = d->grid->disps[(d->y * d->spacing) * d->disp_st + (d->x * d->spacing)];
1034
1035         if(d->invert)
1036                 sub_v3_v3v3(disp, co, subco->co);
1037         else
1038                 copy_v3_v3(disp, data);
1039
1040
1041         /* Apply ts matrix to displacement */
1042         calc_disp_mat(d, mat);
1043         mul_m3_v3(mat, disp);
1044
1045         if(d->invert) {
1046                 copy_v3_v3(data, disp);
1047                 
1048         }
1049         else {
1050                 if(d->type == 4 || d->type == 5)
1051                         mul_v3_fl(disp, d->weight);
1052                 add_v3_v3v3(co, co, disp);
1053         }
1054
1055         if(d->type == 2) {
1056                 if(d->sidendx == 0)
1057                         d->y -= 1;
1058                 else if(d->sidendx == 1)
1059                         d->x += 1;
1060                 else if(d->sidendx == 2)
1061                         d->y += 1;
1062                 else if(d->sidendx == 3)
1063                         d->x -= 1;
1064         }
1065         else if(d->type == 3) {
1066                 if(d->sidendx == 0)
1067                         d->y -= 1;
1068                 else if(d->sidendx == 1)
1069                         d->x += 1;
1070                 else if(d->sidendx == 2)
1071                         d->y += 1;
1072                 else if(d->sidendx == 3)
1073                         d->x -= 1;
1074         }
1075 }
1076
1077 static void multiresModifier_disp_run(DerivedMesh *dm, MVert *subco, int invert)
1078 {
1079         const int lvl = MultiresDM_get_lvl(dm);
1080         const int gridFaces = multires_side_tot[lvl - 2] - 1;
1081         const int edgeSize = multires_side_tot[lvl - 1] - 1;
1082         MVert *mvert = CDDM_get_verts(dm);
1083         MEdge *medge = MultiresDM_get_mesh(dm)->medge;
1084         MFace *mface = MultiresDM_get_mesh(dm)->mface;
1085         ListBase *map = MultiresDM_get_vert_face_map(dm);
1086         Mesh *me = MultiresDM_get_mesh(dm);
1087         MultiresDisplacer d;
1088         int i, S, x, y;
1089
1090         d.subco = subco;
1091         d.subco_index = 0;
1092
1093         for(i = 0; i < me->totface; ++i) {
1094                 const int numVerts = mface[i].v4 ? 4 : 3;
1095                 
1096                 /* Center */
1097                 multires_displacer_init(&d, dm, i, invert);
1098                 multires_displacer_anchor(&d, 1, 0);
1099                 multires_displace(&d, mvert->co);
1100                 ++mvert;
1101                 ++d.subco_index;
1102
1103                 /* Cross */
1104                 for(S = 0; S < numVerts; ++S) {
1105                         multires_displacer_anchor(&d, 2, S);
1106                         for(x = 1; x < gridFaces; ++x) {
1107                                 multires_displace(&d, mvert->co);
1108                                 ++mvert;
1109                                 ++d.subco_index;
1110                         }
1111                 }
1112
1113                 /* Quarters */
1114                 for(S = 0; S < numVerts; S++) {
1115                         multires_displacer_anchor(&d, 3, S);
1116                         for(y = 1; y < gridFaces; y++) {
1117                                 for(x = 1; x < gridFaces; x++) {
1118                                         multires_displace(&d, mvert->co);
1119                                         ++mvert;
1120                                         ++d.subco_index;
1121                                 }
1122                                 multires_displacer_jump(&d);
1123                         }
1124                 }
1125         }
1126
1127         for(i = 0; i < me->totedge; ++i) {
1128                 const MEdge *e = &medge[i];
1129                 for(x = 1; x < edgeSize; ++x) {
1130                         IndexNode *n1, *n2;
1131                         int numFaces = 0;
1132                         for(n1 = map[e->v1].first; n1; n1 = n1->next) {
1133                                 for(n2 = map[e->v2].first; n2; n2 = n2->next) {
1134                                         if(n1->index == n2->index)
1135                                                 ++numFaces;
1136                                 }
1137                         }
1138                         multires_displacer_weight(&d, 1.0f / numFaces);
1139                         /* TODO: Better to have these loops outside the x loop */
1140                         for(n1 = map[e->v1].first; n1; n1 = n1->next) {
1141                                 for(n2 = map[e->v2].first; n2; n2 = n2->next) {
1142                                         if(n1->index == n2->index) {
1143                                                 multires_displacer_init(&d, dm, n1->index, invert);
1144                                                 multires_displacer_anchor_edge(&d, e->v1, e->v2, x);
1145                                                 multires_displace(&d, mvert->co);
1146                                         }
1147                                 }
1148                         }
1149                         ++mvert;
1150                         ++d.subco_index;
1151                 }
1152         }
1153                 
1154         for(i = 0; i < me->totvert; ++i) {
1155                 IndexNode *n;
1156                 multires_displacer_weight(&d, 1.0f / BLI_countlist(&map[i]));
1157                 for(n = map[i].first; n; n = n->next) {
1158                         multires_displacer_init(&d, dm, n->index, invert);
1159                         multires_displacer_anchor_vert(&d, i);
1160                         multires_displace(&d, mvert->co);
1161                 }
1162                 ++mvert;
1163                 ++d.subco_index;
1164         }
1165
1166         if(!invert)
1167                 CDDM_calc_normals(dm);
1168 }
1169
1170 static void multiresModifier_update(DerivedMesh *dm)
1171 {
1172         Object *ob;
1173         Mesh *me;
1174         MDisps *mdisps;
1175
1176         ob = MultiresDM_get_object(dm);
1177         me = MultiresDM_get_mesh(dm);
1178         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
1179
1180         if(mdisps) {
1181                 const int lvl = MultiresDM_get_lvl(dm);
1182                 const int totlvl = MultiresDM_get_totlvl(dm);
1183                 
1184                 if(lvl < totlvl) {
1185                         /* Propagate disps upwards */
1186                         DerivedMesh *final, *subco_dm, *orig;
1187                         MVert *verts_new = NULL, *cur_lvl_orig_verts = NULL;
1188                         MultiresModifierData mmd;
1189                         int i;
1190
1191                         orig = CDDM_from_mesh(me, NULL);
1192                         
1193                         /* Regenerate the current level's vertex coordinates
1194                            (includes older displacements but not new sculpts) */
1195                         mmd.totlvl = totlvl;
1196                         mmd.lvl = lvl;
1197                         subco_dm = multires_dm_create_from_derived(&mmd, 1, orig, ob, 0, 0);
1198                         cur_lvl_orig_verts = CDDM_get_verts(subco_dm);
1199
1200                         /* Subtract the original vertex cos from the new vertex cos */
1201                         verts_new = CDDM_get_verts(dm);
1202                         for(i = 0; i < dm->getNumVerts(dm); ++i)
1203                                 sub_v3_v3v3(verts_new[i].co, verts_new[i].co, cur_lvl_orig_verts[i].co);
1204
1205                         final = multires_subdisp_pre(dm, totlvl - lvl, 0);
1206
1207                         multires_subdisp(orig, ob, final, lvl, totlvl, dm->getNumVerts(dm), dm->getNumEdges(dm),
1208                                          dm->getNumFaces(dm), 1);
1209
1210                         subco_dm->release(subco_dm);
1211                         orig->release(orig);
1212                 }
1213                 else
1214                         multiresModifier_disp_run(dm, MultiresDM_get_subco(dm), 1);
1215         }
1216 }
1217
1218 void multires_mark_as_modified(struct Object *ob)
1219 {
1220         if(ob && ob->derivedFinal) {
1221                 MultiresDM_mark_as_modified(ob->derivedFinal);
1222         }
1223 }
1224
1225 void multires_force_update(Object *ob)
1226 {
1227         if(ob && ob->derivedFinal) {
1228                 ob->derivedFinal->needsFree =1;
1229                 ob->derivedFinal->release(ob->derivedFinal);
1230                 ob->derivedFinal = NULL;
1231         }
1232 }
1233
1234 struct DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int local_mmd, DerivedMesh *dm, Object *ob,
1235                                                     int useRenderParams, int isFinalCalc)
1236 {
1237         SubsurfModifierData smd;
1238         MultiresSubsurf ms;
1239         DerivedMesh *result;
1240         int i;
1241
1242         ms.mmd = mmd;
1243         ms.ob = ob;
1244         ms.local_mmd = local_mmd;
1245
1246         memset(&smd, 0, sizeof(SubsurfModifierData));
1247         smd.levels = smd.renderLevels = mmd->lvl - 1;
1248         smd.flags |= eSubsurfModifierFlag_SubsurfUv;
1249
1250         result = subsurf_make_derived_from_derived_with_multires(dm, &smd, &ms, useRenderParams, NULL, isFinalCalc, 0);
1251         for(i = 0; i < result->getNumVerts(result); ++i)
1252                 MultiresDM_get_subco(result)[i] = CDDM_get_verts(result)[i];
1253         multiresModifier_disp_run(result, MultiresDM_get_subco(result), 0);
1254         MultiresDM_set_update(result, multiresModifier_update);
1255
1256         return result;
1257 }
1258
1259 /**** Old Multires code ****
1260 ***************************/
1261
1262 /* Does not actually free lvl itself */
1263 static void multires_free_level(MultiresLevel *lvl)
1264 {
1265         if(lvl) {
1266                 if(lvl->faces) MEM_freeN(lvl->faces);
1267                 if(lvl->edges) MEM_freeN(lvl->edges);
1268                 if(lvl->colfaces) MEM_freeN(lvl->colfaces);
1269         }
1270 }
1271
1272 void multires_free(Multires *mr)
1273 {
1274         if(mr) {
1275                 MultiresLevel* lvl= mr->levels.first;
1276
1277                 /* Free the first-level data */
1278                 if(lvl) {
1279                         CustomData_free(&mr->vdata, lvl->totvert);
1280                         CustomData_free(&mr->fdata, lvl->totface);
1281                         if(mr->edge_flags)
1282                                 MEM_freeN(mr->edge_flags);
1283                         if(mr->edge_creases)
1284                                 MEM_freeN(mr->edge_creases);
1285                 }
1286
1287                 while(lvl) {
1288                         multires_free_level(lvl);                       
1289                         lvl= lvl->next;
1290                 }
1291
1292                 MEM_freeN(mr->verts);
1293
1294                 BLI_freelistN(&mr->levels);
1295
1296                 MEM_freeN(mr);
1297         }
1298 }
1299
1300 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
1301                                      const int totvert, const int totface)
1302 {
1303         int i,j;
1304         IndexNode *node = NULL;
1305         
1306         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
1307         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
1308         node = *mem;
1309         
1310         /* Find the users */
1311         for(i = 0; i < totface; ++i){
1312                 for(j = 0; j < (mface[i].v[3]?4:3); ++j, ++node) {
1313                         node->index = i;
1314                         BLI_addtail(&(*map)[mface[i].v[j]], node);
1315                 }
1316         }
1317 }
1318
1319 static void create_old_vert_edge_map(ListBase **map, IndexNode **mem, const MultiresEdge *medge,
1320                                      const int totvert, const int totedge)
1321 {
1322         int i,j;
1323         IndexNode *node = NULL;
1324         
1325         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
1326         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge*2, "vert edge map mem");
1327         node = *mem;
1328         
1329         /* Find the users */
1330         for(i = 0; i < totedge; ++i){
1331                 for(j = 0; j < 2; ++j, ++node) {
1332                         node->index = i;
1333                         BLI_addtail(&(*map)[medge[i].v[j]], node);
1334                 }
1335         }
1336 }
1337
1338 static MultiresFace *find_old_face(ListBase *map, MultiresFace *faces, int v1, int v2, int v3, int v4)
1339 {
1340         IndexNode *n1;
1341         int v[4] = {v1, v2, v3, v4}, i, j;
1342
1343         for(n1 = map[v1].first; n1; n1 = n1->next) {
1344                 int fnd[4] = {0, 0, 0, 0};
1345
1346                 for(i = 0; i < 4; ++i) {
1347                         for(j = 0; j < 4; ++j) {
1348                                 if(v[i] == faces[n1->index].v[j])
1349                                         fnd[i] = 1;
1350                         }
1351                 }
1352
1353                 if(fnd[0] && fnd[1] && fnd[2] && fnd[3])
1354                         return &faces[n1->index];
1355         }
1356
1357         return NULL;
1358 }
1359
1360 static MultiresEdge *find_old_edge(ListBase *map, MultiresEdge *edges, int v1, int v2)
1361 {
1362         IndexNode *n1, *n2;
1363
1364         for(n1 = map[v1].first; n1; n1 = n1->next) {
1365                 for(n2 = map[v2].first; n2; n2 = n2->next) {
1366                         if(n1->index == n2->index)
1367                                 return &edges[n1->index];
1368                 }
1369         }
1370
1371         return NULL;
1372 }
1373
1374 static void multires_load_old_edges(ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst, int v1, int v2, int mov)
1375 {
1376         int emid = find_old_edge(emap[2], lvl->edges, v1, v2)->mid;
1377         vvmap[dst + mov] = emid;
1378
1379         if(lvl->next->next) {
1380                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v1, emid, mov / 2);
1381                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v2, emid, -mov / 2);
1382         }
1383 }
1384
1385 static void multires_load_old_faces(ListBase **fmap, ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst,
1386                                     int v1, int v2, int v3, int v4, int st2, int st3)
1387 {
1388         int fmid;
1389         int emid13, emid14, emid23, emid24;
1390
1391         if(lvl && lvl->next) {
1392                 fmid = find_old_face(fmap[1], lvl->faces, v1, v2, v3, v4)->mid;
1393                 vvmap[dst] = fmid;
1394
1395                 emid13 = find_old_edge(emap[1], lvl->edges, v1, v3)->mid;
1396                 emid14 = find_old_edge(emap[1], lvl->edges, v1, v4)->mid;
1397                 emid23 = find_old_edge(emap[1], lvl->edges, v2, v3)->mid;
1398                 emid24 = find_old_edge(emap[1], lvl->edges, v2, v4)->mid;
1399
1400
1401                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 + st3,
1402                                         fmid, v2, emid23, emid24, st2, st3 / 2);
1403
1404                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 + st3,
1405                                         emid14, emid24, fmid, v4, st2, st3 / 2);
1406
1407                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 - st3,
1408                                         emid13, emid23, v3, fmid, st2, st3 / 2);
1409
1410                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 - st3,
1411                                         v1, fmid, emid13, emid14, st2, st3 / 2);
1412
1413                 if(lvl->next->next) {
1414                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid24, fmid, st3);
1415                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid13, fmid, -st3);
1416                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid14, fmid, -st2 * st3);
1417                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid23, fmid, st2 * st3);
1418                 }
1419         }
1420 }
1421
1422 /* Loads a multires object stored in the old Multires struct into the new format */
1423 void multires_load_old(DerivedMesh *dm, Multires *mr)
1424 {
1425         MultiresLevel *lvl, *lvl1;
1426         MVert *vsrc, *vdst;
1427         int src, dst;
1428         int totlvl = MultiresDM_get_totlvl(dm);
1429         int st = multires_side_tot[totlvl - 2] - 1;
1430         int extedgelen = multires_side_tot[totlvl - 1] - 2;
1431         int *vvmap; // inorder for dst, map to src
1432         int crossedgelen;
1433         int i, j, s, x, totvert, tottri, totquad;
1434
1435         src = 0;
1436         dst = 0;
1437         vsrc = mr->verts;
1438         vdst = CDDM_get_verts(dm);
1439         totvert = dm->getNumVerts(dm);
1440         vvmap = MEM_callocN(sizeof(int) * totvert, "multires vvmap");
1441
1442         lvl1 = mr->levels.first;
1443         /* Load base verts */
1444         for(i = 0; i < lvl1->totvert; ++i) {
1445                 vvmap[totvert - lvl1->totvert + i] = src;
1446                 ++src;
1447         }
1448
1449         /* Original edges */
1450         dst = totvert - lvl1->totvert - extedgelen * lvl1->totedge;
1451         for(i = 0; i < lvl1->totedge; ++i) {
1452                 int ldst = dst + extedgelen * i;
1453                 int lsrc = src;
1454                 lvl = lvl1->next;
1455
1456                 for(j = 2; j <= mr->level_count; ++j) {
1457                         int base = multires_side_tot[totlvl - j] - 2;
1458                         int skip = multires_side_tot[totlvl - j + 1] - 1;
1459                         int st = multires_side_tot[j - 2] - 1;
1460
1461                         for(x = 0; x < st; ++x)
1462                                 vvmap[ldst + base + x * skip] = lsrc + st * i + x;
1463
1464                         lsrc += lvl->totvert - lvl->prev->totvert;
1465                         lvl = lvl->next;
1466                 }
1467         }
1468
1469         /* Center points */
1470         dst = 0;
1471         for(i = 0; i < lvl1->totface; ++i) {
1472                 int sides = lvl1->faces[i].v[3] ? 4 : 3;
1473
1474                 vvmap[dst] = src + lvl1->totedge + i;
1475                 dst += 1 + sides * (st - 1) * st;
1476         }
1477
1478
1479         /* The rest is only for level 3 and up */
1480         if(lvl1->next && lvl1->next->next) {
1481                 ListBase **fmap, **emap;
1482                 IndexNode **fmem, **emem;
1483
1484                 /* Face edge cross */
1485                 tottri = totquad = 0;
1486                 crossedgelen = multires_side_tot[totlvl - 2] - 2;
1487                 dst = 0;
1488                 for(i = 0; i < lvl1->totface; ++i) {
1489                         int sides = lvl1->faces[i].v[3] ? 4 : 3;
1490
1491                         lvl = lvl1->next->next;
1492                         ++dst;
1493
1494                         for(j = 3; j <= mr->level_count; ++j) {
1495                                 int base = multires_side_tot[totlvl - j] - 2;
1496                                 int skip = multires_side_tot[totlvl - j + 1] - 1;
1497                                 int st = pow(2, j - 2);
1498                                 int st2 = pow(2, j - 3);
1499                                 int lsrc = lvl->prev->totvert;
1500
1501                                 /* Skip exterior edge verts */
1502                                 lsrc += lvl1->totedge * st;
1503
1504                                 /* Skip earlier face edge crosses */
1505                                 lsrc += st2 * (tottri * 3 + totquad * 4);
1506
1507                                 for(s = 0; s < sides; ++s) {
1508                                         for(x = 0; x < st2; ++x) {
1509                                                 vvmap[dst + crossedgelen * (s + 1) - base - x * skip - 1] = lsrc;
1510                                                 ++lsrc;
1511                                         }
1512                                 }
1513
1514                                 lvl = lvl->next;
1515                         }
1516
1517                         dst += sides * (st - 1) * st;
1518
1519                         if(sides == 4) ++totquad;
1520                         else ++tottri;
1521
1522                 }
1523
1524                 /* calculate vert to edge/face maps for each level (except the last) */
1525                 fmap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires fmap");
1526                 emap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires emap");
1527                 fmem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires fmem");
1528                 emem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires emem");
1529                 lvl = lvl1;
1530                 for(i = 0; i < mr->level_count - 1; ++i) {
1531                         create_old_vert_face_map(fmap + i, fmem + i, lvl->faces, lvl->totvert, lvl->totface);
1532                         create_old_vert_edge_map(emap + i, emem + i, lvl->edges, lvl->totvert, lvl->totedge);
1533                         lvl = lvl->next;
1534                 }
1535
1536                 /* Interior face verts */
1537                 lvl = lvl1->next->next;
1538                 dst = 0;
1539                 for(j = 0; j < lvl1->totface; ++j) {
1540                         int sides = lvl1->faces[j].v[3] ? 4 : 3;
1541                         int ldst = dst + 1 + sides * (st - 1);
1542
1543                         for(s = 0; s < sides; ++s) {
1544                                 int st2 = multires_side_tot[totlvl - 2] - 2;
1545                                 int st3 = multires_side_tot[totlvl - 3] - 2;
1546                                 int st4 = st3 == 0 ? 1 : (st3 + 1) / 2;
1547                                 int mid = ldst + st2 * st3 + st3;
1548                                 int cv = lvl1->faces[j].v[s];
1549                                 int nv = lvl1->faces[j].v[s == sides - 1 ? 0 : s + 1];
1550                                 int pv = lvl1->faces[j].v[s == 0 ? sides - 1 : s - 1];
1551
1552                                 multires_load_old_faces(fmap, emap, lvl1->next, vvmap, mid,
1553                                                         vvmap[dst], cv,
1554                                                         find_old_edge(emap[0], lvl1->edges, pv, cv)->mid,
1555                                                         find_old_edge(emap[0], lvl1->edges, cv, nv)->mid,
1556                                                         st2, st4);
1557
1558                                 ldst += (st - 1) * (st - 1);
1559                         }
1560
1561
1562                         dst = ldst;
1563                 }
1564
1565                 lvl = lvl->next;
1566
1567                 for(i = 0; i < mr->level_count - 1; ++i) {
1568                         MEM_freeN(fmap[i]);
1569                         MEM_freeN(fmem[i]);
1570                         MEM_freeN(emap[i]);
1571                         MEM_freeN(emem[i]);
1572                 }
1573
1574                 MEM_freeN(fmap);
1575                 MEM_freeN(emap);
1576                 MEM_freeN(fmem);
1577                 MEM_freeN(emem);
1578         }
1579
1580         /* Transfer verts */
1581         for(i = 0; i < totvert; ++i)
1582                 copy_v3_v3(vdst[i].co, vsrc[vvmap[i]].co);
1583
1584         MEM_freeN(vvmap);
1585 }