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