a709b45f60cf3ce0e0c8f4d991424877d9e5bec3
[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_btex.h"
44 #include "BKE_cdderivedmesh.h"
45 #include "BKE_customdata.h"
46 #include "BKE_depsgraph.h"
47 #include "BKE_DerivedMesh.h"
48 #include "BKE_global.h"
49 #include "BKE_mesh.h"
50 #include "BKE_modifier.h"
51 #include "BKE_multires.h"
52 #include "BKE_object.h"
53 #include "BKE_subsurf.h"
54 #include "BKE_utildefines.h"
55
56 #include "CCGSubSurf.h"
57
58 #include <math.h>
59 #include <string.h>
60
61 /* MULTIRES MODIFIER */
62 static const int multires_max_levels = 13;
63 static const int multires_grid_tot[] = {1, 4, 9, 25, 81, 289, 1089, 4225, 16641, 66049, 263169, 1050625, 4198401, 16785409};
64 static const int multires_side_tot[] = {1, 2, 3, 5,  9,  17,  33,   65,   129,   257,   513,    1025,    2049,    4097};
65
66 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, int invert, int add, DMGridData **oldGridData, int totlvl);
67
68 MultiresModifierData *find_multires_modifier(Object *ob)
69 {
70         ModifierData *md;
71         MultiresModifierData *mmd = NULL;
72
73         for(md = ob->modifiers.first; md; md = md->next) {
74                 if(md->type == eModifierType_Multires) {
75                         mmd = (MultiresModifierData*)md;
76                         break;
77                 }
78         }
79
80         return mmd;
81 }
82
83 static int multires_get_level(Object *ob, MultiresModifierData *mmd, int render)
84 {
85         if(render)
86                 return mmd->renderlvl;
87         else if(ob->mode == OB_MODE_SCULPT)
88                 return mmd->sculptlvl;
89         else
90                 return mmd->lvl;
91 }
92
93 static void multires_set_tot_level(Object *ob, MultiresModifierData *mmd, int lvl)
94 {
95         mmd->totlvl = lvl;
96
97         if(ob->mode != OB_MODE_SCULPT) {
98                 mmd->lvl = MAX2(mmd->lvl, lvl);
99                 CLAMP(mmd->lvl, 0, mmd->totlvl);
100         }
101
102         mmd->sculptlvl = MAX2(mmd->sculptlvl, lvl);
103         CLAMP(mmd->sculptlvl, 0, mmd->totlvl);
104
105         mmd->renderlvl = MAX2(mmd->renderlvl, lvl);
106         CLAMP(mmd->renderlvl, 0, mmd->totlvl);
107 }
108
109 /* XXX */
110 #if 0
111 void multiresModifier_join(Object *ob)
112 {
113         Base *base = NULL;
114         int highest_lvl = 0;
115
116         /* First find the highest level of subdivision */
117         base = FIRSTBASE;
118         while(base) {
119                 if(TESTBASELIB_BGMODE(v3d, scene, base) && base->object->type==OB_MESH) {
120                         ModifierData *md;
121                         for(md = base->object->modifiers.first; md; md = md->next) {
122                                 if(md->type == eModifierType_Multires) {
123                                         int totlvl = ((MultiresModifierData*)md)->totlvl;
124                                         if(totlvl > highest_lvl)
125                                                 highest_lvl = totlvl;
126
127                                         /* Ensure that all updates are processed */
128                                         multires_force_update(base->object);
129                                 }
130                         }
131                 }
132                 base = base->next;
133         }
134
135         /* No multires meshes selected */
136         if(highest_lvl == 0)
137                 return;
138
139         /* Subdivide all the displacements to the highest level */
140         base = FIRSTBASE;
141         while(base) {
142                 if(TESTBASELIB_BGMODE(v3d, scene, base) && base->object->type==OB_MESH) {
143                         ModifierData *md = NULL;
144                         MultiresModifierData *mmd = NULL;
145
146                         for(md = base->object->modifiers.first; md; md = md->next) {
147                                 if(md->type == eModifierType_Multires)
148                                         mmd = (MultiresModifierData*)md;
149                         }
150
151                         /* If the object didn't have multires enabled, give it a new modifier */
152                         if(!mmd) {
153                                 md = base->object->modifiers.first;
154                                 
155                                 while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
156                                         md = md->next;
157                                 
158                                 mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
159                                 BLI_insertlinkbefore(&base->object->modifiers, md, mmd);
160                                 modifier_unique_name(&base->object->modifiers, mmd);
161                         }
162
163                         if(mmd)
164                                 multiresModifier_subdivide(mmd, base->object, highest_lvl - mmd->totlvl, 0, 0);
165                 }
166                 base = base->next;
167         }
168 }
169 #endif
170
171 /* Returns 0 on success, 1 if the src's totvert doesn't match */
172 int multiresModifier_reshape(MultiresModifierData *mmd, Object *dst, Object *src)
173 {
174         /* XXX */
175 #if 0
176         Mesh *src_me = get_mesh(src);
177         DerivedMesh *mrdm = dst->derivedFinal;
178
179         if(mrdm && mrdm->getNumVerts(mrdm) == src_me->totvert) {
180                 MVert *mvert = CDDM_get_verts(mrdm);
181                 int i;
182
183                 for(i = 0; i < src_me->totvert; ++i)
184                         copy_v3_v3(mvert[i].co, src_me->mvert[i].co);
185                 mrdm->needsFree = 1;
186                 MultiresDM_mark_as_modified(mrdm);
187                 mrdm->release(mrdm);
188                 dst->derivedFinal = NULL;
189
190                 return 0;
191         }
192 #endif
193
194         return 1;
195 }
196
197 static void column_vectors_to_mat3(float mat[][3], float v1[3], float v2[3], float v3[3])
198 {
199         copy_v3_v3(mat[0], v1);
200         copy_v3_v3(mat[1], v2);
201         copy_v3_v3(mat[2], v3);
202 }
203
204 static void multires_copy_grid(float (*gridA)[3], float (*gridB)[3], int sizeA, int sizeB)
205 {
206         int x, y, j, skip;
207
208         if(sizeA > sizeB) {
209                 skip = (sizeA-1)/(sizeB-1);
210
211                 for(j = 0, y = 0; y < sizeB; y++)
212                         for(x = 0; x < sizeB; x++, j++)
213                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip], gridB[j]);
214         }
215         else {
216                 skip = (sizeB-1)/(sizeA-1);
217
218                 for(j = 0, y = 0; y < sizeA; y++)
219                         for(x = 0; x < sizeA; x++, j++)
220                                 copy_v3_v3(gridA[j], gridB[y*skip*sizeB + x*skip]);
221         }
222 }
223
224 static void multires_copy_dm_grid(DMGridData *gridA, DMGridData *gridB, int sizeA, int sizeB)
225 {
226         int x, y, j, skip;
227
228         if(sizeA > sizeB) {
229                 skip = (sizeA-1)/(sizeB-1);
230
231                 for(j = 0, y = 0; y < sizeB; y++)
232                         for(x = 0; x < sizeB; x++, j++)
233                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip].co, gridB[j].co);
234         }
235         else {
236                 skip = (sizeB-1)/(sizeA-1);
237
238                 for(j = 0, y = 0; y < sizeA; y++)
239                         for(x = 0; x < sizeA; x++, j++)
240                                 copy_v3_v3(gridA[j].co, gridB[y*skip*sizeB + x*skip].co);
241         }
242 }
243
244 /* direction=1 for delete higher, direction=0 for lower (not implemented yet) */
245 void multiresModifier_del_levels(struct MultiresModifierData *mmd, struct Object *ob, int direction)
246 {
247         Mesh *me = get_mesh(ob);
248         int lvl = multires_get_level(ob, mmd, 0);
249         int levels = mmd->totlvl - lvl;
250         MDisps *mdisps;
251         
252         CustomData_external_read(&me->fdata, CD_MASK_MDISPS, me->totface);
253         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
254
255         multires_force_update(ob);
256
257         if(mdisps && levels > 0 && direction == 1) {
258                 int nsize = multires_side_tot[lvl];
259                 int hsize = multires_side_tot[mmd->totlvl];
260                 int i;
261
262                 for(i = 0; i < me->totface; ++i) {
263                         MDisps *mdisp= &mdisps[i];
264                         float (*disps)[3], (*ndisps)[3], (*hdisps)[3];
265                         int nvert = (me->mface[i].v4)? 4: 3;
266                         int totdisp = multires_grid_tot[lvl]*nvert;
267                         int S;
268
269                         disps = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
270
271                         ndisps = disps;
272                         hdisps = mdisp->disps;
273
274                         for(S = 0; S < nvert; S++) {
275                                 multires_copy_grid(ndisps, hdisps, nsize, hsize);
276
277                                 ndisps += nsize*nsize;
278                                 hdisps += hsize*hsize;
279                         }
280
281                         MEM_freeN(mdisp->disps);
282                         mdisp->disps = disps;
283                         mdisp->totdisp = totdisp;
284                 }
285         }
286
287         multires_set_tot_level(ob, mmd, lvl);
288 }
289
290 static DerivedMesh *multires_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int totlvl, int simple)
291 {
292         MultiresModifierData mmd;
293
294         memset(&mmd, 0, sizeof(MultiresModifierData));
295         mmd.lvl = lvl;
296         mmd.sculptlvl = lvl;
297         mmd.renderlvl = lvl;
298         mmd.totlvl = totlvl;
299         mmd.simple = simple;
300
301         return multires_dm_create_from_derived(&mmd, 1, dm, ob, 0, 0);
302 }
303
304 static DerivedMesh *subsurf_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int simple)
305 {
306         SubsurfModifierData smd;
307
308         memset(&smd, 0, sizeof(SubsurfModifierData));
309         smd.levels = smd.renderLevels = lvl;
310         smd.flags |= eSubsurfModifierFlag_SubsurfUv;
311         if(simple)
312                 smd.subdivType = ME_SIMPLE_SUBSURF;
313
314         return subsurf_make_derived_from_derived(dm, &smd, 0, NULL, 0, 0);
315 }
316
317 static void multires_reallocate_mdisps(Mesh *me, MDisps *mdisps, int lvl)
318 {
319         int i;
320
321         /* reallocate displacements to be filled in */
322         for(i = 0; i < me->totface; ++i) {
323                 int nvert = (me->mface[i].v4)? 4: 3;
324                 int totdisp = multires_grid_tot[lvl]*nvert;
325                 float (*disps)[3] = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
326
327                 if(mdisps[i].disps)
328                         MEM_freeN(mdisps[i].disps);
329
330                 mdisps[i].disps = disps;
331                 mdisps[i].totdisp = totdisp;
332         }
333 }
334
335 void multiresModifier_subdivide(MultiresModifierData *mmd, Object *ob, int updateblock, int simple)
336 {
337         Mesh *me = ob->data;
338         MDisps *mdisps;
339         int lvl= mmd->totlvl;
340         int totlvl= mmd->totlvl+1;
341
342         if(totlvl > multires_max_levels)
343                 return;
344
345         multires_force_update(ob);
346
347         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
348         if(!mdisps)
349                 mdisps = CustomData_add_layer(&me->fdata, CD_MDISPS, CD_DEFAULT, NULL, me->totface);
350
351         if(mdisps->disps && !updateblock && totlvl > 1) {
352                 /* upsample */
353                 DerivedMesh *lowdm, *cddm, *highdm;
354                 DMGridData **highGridData, **lowGridData, **subGridData;
355                 CCGSubSurf *ss;
356                 int i, numGrids, highGridSize, lowGridSize;
357
358                 /* create subsurf DM from original mesh at high level */
359                 cddm = CDDM_from_mesh(me, NULL);
360                 highdm = subsurf_dm_create_local(ob, cddm, totlvl, simple);
361
362                 /* create multires DM from original mesh at low level */
363                 lowdm = multires_dm_create_local(ob, cddm, lvl, lvl, simple);
364                 cddm->release(cddm);
365
366                 /* copy subsurf grids and replace them with low displaced grids */
367                 numGrids = highdm->getNumGrids(highdm);
368                 highGridSize = highdm->getGridSize(highdm);
369                 highGridData = highdm->getGridData(highdm);
370                 lowGridSize = lowdm->getGridSize(lowdm);
371                 lowGridData = lowdm->getGridData(lowdm);
372
373                 subGridData = MEM_callocN(sizeof(float*)*numGrids, "subGridData*");
374
375                 for(i = 0; i < numGrids; ++i) {
376                         /* backup subsurf grids */
377                         subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
378                         memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
379
380                         /* overwrite with current displaced grids */
381                         multires_copy_dm_grid(highGridData[i], lowGridData[i], highGridSize, lowGridSize);
382                 }
383
384                 /* low lower level dm no longer needed at this point */
385                 lowdm->release(lowdm);
386
387                 /* subsurf higher levels again with displaced data */
388                 ss= ((CCGDerivedMesh*)highdm)->ss;
389                 ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
390                 ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
391
392                 /* reallocate displacements */
393                 multires_reallocate_mdisps(me, mdisps, totlvl); 
394
395                 /* compute displacements */
396                 multiresModifier_disp_run(highdm, me, 1, 0, subGridData, totlvl);
397
398                 /* free */
399                 highdm->release(highdm);
400                 for(i = 0; i < numGrids; ++i)
401                         MEM_freeN(subGridData[i]);
402                 MEM_freeN(subGridData);
403         }
404         else {
405                 /* only reallocate, nothing to upsample */
406                 multires_reallocate_mdisps(me, mdisps, totlvl); 
407         }
408
409         multires_set_tot_level(ob, mmd, totlvl);
410 }
411
412 static void grid_adjacent_rotate(int rotation, int gridSize, int *x, int *y)
413 {
414         /* we rotate (rotation * 90°) counterclockwise around center */
415         int nx, ny;
416
417         switch(rotation) {
418                 case 0: nx = *x; ny = *y; break;
419                 case 1: nx = *y; ny = *x; break;
420                 case 2: nx = *x; ny = *y; break; //gridSize - 1 - *x; ny = gridSize - 1 - *y; break;
421                 case 3: nx = *y; ny = *x; break;
422         }
423
424         *x = nx;
425         *y = ny;
426 }
427
428 static void grid_adjacent_jump(DMGridAdjacency *adj, int gridSize, int *index, int *x, int *y)
429 {
430         if(*x < 0) {
431                 if(adj->index[3] == -1) {
432                         /* no adjacent grid, clamp */
433                         *x = 0;
434                 }
435                 else {
436                         /* jump to adjacent grid */
437                         *index = adj->index[3];
438                         *x += gridSize;
439                         grid_adjacent_rotate(adj->rotation[3], gridSize, x, y);
440                 }
441         }
442         else if(*x >= gridSize) {
443                 if(adj->index[1] == -1) {
444                         /* no adjacent grid, take a step back */
445                         *x = gridSize - 1;
446                 }
447                 else {
448                         /* jump to adjacent grid */
449                         *index = adj->index[1];
450                         *x -= gridSize;
451                         grid_adjacent_rotate(adj->rotation[1], gridSize, x, y);
452                 }
453         }
454         else if(*y < 0) {
455                 if(adj->index[0] == -1) {
456                         /* no adjacent grid, clamp */
457                         *y = 0;
458                 }
459                 else {
460                         /* jump to adjacent grid */
461                         *index = adj->index[0];
462                         *y += gridSize;
463                         grid_adjacent_rotate(adj->rotation[0], gridSize, x, y);
464                 }
465         }
466         else if(*y >= gridSize) {
467                 if(adj->index[2] == -1) {
468                         /* no adjacent grid, take a step back */
469                         *y = gridSize - 1;
470                 }
471                 else {
472                         /* jump to adjacent grid */
473                         *index = adj->index[2];
474                         *y -= gridSize;
475                         grid_adjacent_rotate(adj->rotation[2], gridSize, x, y);
476                 }
477         }
478 }
479
480 static void grid_tangent(DMGridAdjacency *adj, int gridSize, int index, int x, int y, int axis, DMGridData **gridData, float t[3])
481 {
482         int jindex = index, jx = x, jy = y;
483
484         if(axis == 0) {
485                 if(adj->index[1] == -1 && x == gridSize - 1) {
486                         if(adj->index[2] == -1 && y == gridSize - 1)
487                                 sub_v3_v3v3(t, gridData[index][x + gridSize*(y - 1)].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
488                         else
489                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x - 1 + gridSize*y].co);
490                 }
491                 else {
492                         jx += 1;
493                         grid_adjacent_jump(adj, gridSize, &jindex, &jx, &jy);
494                         sub_v3_v3v3(t, gridData[jindex][jx + gridSize*jy].co, gridData[index][x + gridSize*y].co);
495                 }
496         }
497         else if(axis == 1) {
498                 if(adj->index[2] == -1 && y == gridSize - 1) {
499                         if(adj->index[1] == -1 && x == gridSize - 1) {
500                                 sub_v3_v3v3(t, gridData[index][x - 1 + gridSize*y].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
501                         }
502                         else {
503                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x + gridSize*(y - 1)].co);
504                         }
505                 }
506                 else {
507                         jy += 1;
508                         grid_adjacent_jump(adj, gridSize, &jindex, &jx, &jy);
509                         sub_v3_v3v3(t, gridData[jindex][jx + gridSize*jy].co, gridData[index][x + gridSize*y].co);
510                 }
511         }
512 }
513
514 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, int invert, int add, DMGridData **oldGridData, int totlvl)
515 {
516         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)dm;
517         DMGridData **gridData, **subGridData;
518         DMGridAdjacency *gridAdjacency;
519         MFace *mface = me->mface;
520         MDisps *mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
521         int i, S, x, y, numGrids, gIndex, gridSize, dGridSize, dSkip;
522
523         numGrids = dm->getNumGrids(dm);
524         gridSize = dm->getGridSize(dm);
525         gridData = dm->getGridData(dm);
526         gridAdjacency = dm->getGridAdjacency(dm);
527         subGridData = (oldGridData)? oldGridData: gridData;
528
529         dGridSize = multires_side_tot[totlvl];
530         dSkip = (dGridSize-1)/(gridSize-1);
531
532         for(gIndex = 0, i = 0; i < me->totface; ++i) {
533                 const int numVerts = mface[i].v4 ? 4 : 3;
534                 MDisps *mdisp = &mdisps[i];
535
536                 for(S = 0; S < numVerts; ++S, ++gIndex) {
537                         DMGridData *grid = gridData[gIndex];
538                         DMGridData *subgrid = subGridData[gIndex];
539                         DMGridAdjacency *adj = &gridAdjacency[gIndex];
540                         float (*dispgrid)[3] = &mdisp->disps[S*dGridSize*dGridSize];
541
542                         for(y = 0; y < gridSize; y++) {
543                                 for(x = 0; x < gridSize; x++) {
544                                         float *co = grid[x + y*gridSize].co;
545                                         float *sco = subgrid[x + y*gridSize].co;
546                                         float *no = subgrid[x + y*gridSize].no;
547                                         float *data = dispgrid[dGridSize*y*dSkip + x*dSkip];
548                                         float mat[3][3], tx[3], ty[3], disp[3], d[3];
549
550                                         /* construct tangent space matrix */
551                                         grid_tangent(adj, gridSize, gIndex, x, y, 0, subGridData, tx);
552                                         normalize_v3(tx);
553
554                                         grid_tangent(adj, gridSize, gIndex, x, y, 1, subGridData, ty);
555                                         normalize_v3(ty);
556
557                                         column_vectors_to_mat3(mat, tx, ty, no);
558
559                                         if(!invert) {
560                                                 /* convert to object space and add */
561                                                 mul_v3_m3v3(disp, mat, data);
562                                                 add_v3_v3v3(co, sco, disp);
563                                         }
564                                         else if(!add) {
565                                                 /* convert difference to tangent space */
566                                                 sub_v3_v3v3(disp, co, sco);
567                                                 invert_m3(mat);
568                                                 mul_v3_m3v3(data, mat, disp);
569                                         }
570                                         else {
571                                                 /* convert difference to tangent space */
572                                                 invert_m3(mat);
573                                                 mul_v3_m3v3(d, mat, co);
574                                                 add_v3_v3(data, d);
575                                         }
576                                 }
577                         }
578                 }
579         }
580
581         if(!invert) {
582                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, NULL, 0);
583                 ccgSubSurf_updateNormals(ccgdm->ss, NULL, 0);
584         }
585 }
586
587 static void multiresModifier_update(DerivedMesh *dm)
588 {
589         CCGDerivedMesh *ccgdm= (CCGDerivedMesh*)dm;
590         Object *ob;
591         Mesh *me;
592         MDisps *mdisps;
593         MultiresModifierData *mmd;
594
595         ob = ccgdm->multires.ob;
596         me = ccgdm->multires.ob->data;
597         mmd = ccgdm->multires.mmd;
598         CustomData_external_read(&me->fdata, CD_MASK_MDISPS, me->totface);
599         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
600
601         if(mdisps) {
602                 int lvl = ccgdm->multires.lvl;
603                 int totlvl = ccgdm->multires.totlvl;
604                 
605                 if(lvl < totlvl) {
606                         Mesh *me = ob->data;
607                         DerivedMesh *lowdm, *cddm, *highdm;
608                         DMGridData **highGridData, **lowGridData, **subGridData, **gridData, *diffGrid;
609                         CCGSubSurf *ss;
610                         int i, j, numGrids, highGridSize, lowGridSize;
611
612                         /* create subsurf DM from original mesh at high level */
613                         cddm = CDDM_from_mesh(me, NULL);
614                         highdm = subsurf_dm_create_local(ob, cddm, totlvl, mmd->simple);
615
616                         /* create multires DM from original mesh and displacements */
617                         lowdm = multires_dm_create_local(ob, cddm, lvl, totlvl, mmd->simple);
618                         cddm->release(cddm);
619
620                         /* gather grid data */
621                         numGrids = highdm->getNumGrids(highdm);
622                         highGridSize = highdm->getGridSize(highdm);
623                         highGridData = highdm->getGridData(highdm);
624                         lowGridSize = lowdm->getGridSize(lowdm);
625                         lowGridData = lowdm->getGridData(lowdm);
626                         gridData = dm->getGridData(dm);
627
628                         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
629                         diffGrid = MEM_callocN(sizeof(DMGridData)*lowGridSize*lowGridSize, "diff");
630
631                         for(i = 0; i < numGrids; ++i) {
632                                 /* backup subsurf grids */
633                                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
634                                 memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
635
636                                 /* write difference of subsurf and displaced low level into high subsurf */
637                                 for(j = 0; j < lowGridSize*lowGridSize; ++j)
638                                         sub_v3_v3v3(diffGrid[j].co, gridData[i][j].co, lowGridData[i][j].co);
639
640                                 multires_copy_dm_grid(highGridData[i], diffGrid, highGridSize, lowGridSize);
641                         }
642
643                         /* lower level dm no longer needed at this point */
644                         MEM_freeN(diffGrid);
645                         lowdm->release(lowdm);
646
647                         /* subsurf higher levels again with difference of coordinates */
648                         ss= ((CCGDerivedMesh*)highdm)->ss;
649                         ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
650                         ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
651
652                         /* add to displacements */
653                         multiresModifier_disp_run(highdm, me, 1, 1, subGridData, mmd->totlvl);
654
655                         /* free */
656                         highdm->release(highdm);
657                         for(i = 0; i < numGrids; ++i)
658                                 MEM_freeN(subGridData[i]);
659                         MEM_freeN(subGridData);
660                 }
661                 else {
662                         DerivedMesh *cddm, *subdm;
663
664                         cddm = CDDM_from_mesh(me, NULL);
665                         subdm = subsurf_dm_create_local(ob, cddm, mmd->totlvl, mmd->simple);
666                         cddm->release(cddm);
667
668                         multiresModifier_disp_run(dm, me, 1, 0, subdm->getGridData(subdm), mmd->totlvl);
669
670                         subdm->release(subdm);
671                 }
672         }
673 }
674
675 void multires_mark_as_modified(struct Object *ob)
676 {
677         if(ob && ob->derivedFinal) {
678                 CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)ob->derivedFinal;
679                 ccgdm->multires.modified = 1;
680         }
681 }
682
683 void multires_force_update(Object *ob)
684 {
685         if(ob && ob->derivedFinal) {
686                 ob->derivedFinal->needsFree =1;
687                 ob->derivedFinal->release(ob->derivedFinal);
688                 ob->derivedFinal = NULL;
689         }
690 }
691
692 struct DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int local_mmd, DerivedMesh *dm, Object *ob,
693                                                     int useRenderParams, int isFinalCalc)
694 {
695         Mesh *me= ob->data;
696         DerivedMesh *result;
697         CCGDerivedMesh *ccgdm;
698         DMGridData **gridData, **subGridData;
699         int lvl= multires_get_level(ob, mmd, useRenderParams);
700         int i, gridSize, numGrids;
701
702         if(lvl == 0)
703                 return dm;
704
705         result = subsurf_dm_create_local(ob, dm, lvl, 0);
706
707         if(!local_mmd) {
708                 ccgdm = (CCGDerivedMesh*)result;
709
710                 ccgdm->multires.ob = ob;
711                 ccgdm->multires.mmd = mmd;
712                 ccgdm->multires.local_mmd = local_mmd;
713                 ccgdm->multires.lvl = lvl;
714                 ccgdm->multires.totlvl = mmd->totlvl;
715                 ccgdm->multires.modified = 0;
716                 ccgdm->multires.update = multiresModifier_update;
717         }
718
719         numGrids = result->getNumGrids(result);
720         gridSize = result->getGridSize(result);
721         gridData = result->getGridData(result);
722
723         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
724
725         for(i = 0; i < numGrids; i++) {
726                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*gridSize*gridSize, "subGridData");
727                 memcpy(subGridData[i], gridData[i], sizeof(DMGridData)*gridSize*gridSize);
728         }
729
730         CustomData_external_read(&me->fdata, CD_MASK_MDISPS, me->totface);
731         multiresModifier_disp_run(result, ob->data, 0, 0, subGridData, mmd->totlvl);
732
733         for(i = 0; i < numGrids; i++)
734                 MEM_freeN(subGridData[i]);
735         MEM_freeN(subGridData);
736
737         return result;
738 }
739
740 /**** Old Multires code ****
741 ***************************/
742
743 /* Does not actually free lvl itself */
744 static void multires_free_level(MultiresLevel *lvl)
745 {
746         if(lvl) {
747                 if(lvl->faces) MEM_freeN(lvl->faces);
748                 if(lvl->edges) MEM_freeN(lvl->edges);
749                 if(lvl->colfaces) MEM_freeN(lvl->colfaces);
750         }
751 }
752
753 void multires_free(Multires *mr)
754 {
755         if(mr) {
756                 MultiresLevel* lvl= mr->levels.first;
757
758                 /* Free the first-level data */
759                 if(lvl) {
760                         CustomData_free(&mr->vdata, lvl->totvert);
761                         CustomData_free(&mr->fdata, lvl->totface);
762                         if(mr->edge_flags)
763                                 MEM_freeN(mr->edge_flags);
764                         if(mr->edge_creases)
765                                 MEM_freeN(mr->edge_creases);
766                 }
767
768                 while(lvl) {
769                         multires_free_level(lvl);                       
770                         lvl= lvl->next;
771                 }
772
773                 MEM_freeN(mr->verts);
774
775                 BLI_freelistN(&mr->levels);
776
777                 MEM_freeN(mr);
778         }
779 }
780
781 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
782                                      const int totvert, const int totface)
783 {
784         int i,j;
785         IndexNode *node = NULL;
786         
787         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
788         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
789         node = *mem;
790         
791         /* Find the users */
792         for(i = 0; i < totface; ++i){
793                 for(j = 0; j < (mface[i].v[3]?4:3); ++j, ++node) {
794                         node->index = i;
795                         BLI_addtail(&(*map)[mface[i].v[j]], node);
796                 }
797         }
798 }
799
800 static void create_old_vert_edge_map(ListBase **map, IndexNode **mem, const MultiresEdge *medge,
801                                      const int totvert, const int totedge)
802 {
803         int i,j;
804         IndexNode *node = NULL;
805         
806         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
807         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge*2, "vert edge map mem");
808         node = *mem;
809         
810         /* Find the users */
811         for(i = 0; i < totedge; ++i){
812                 for(j = 0; j < 2; ++j, ++node) {
813                         node->index = i;
814                         BLI_addtail(&(*map)[medge[i].v[j]], node);
815                 }
816         }
817 }
818
819 static MultiresFace *find_old_face(ListBase *map, MultiresFace *faces, int v1, int v2, int v3, int v4)
820 {
821         IndexNode *n1;
822         int v[4] = {v1, v2, v3, v4}, i, j;
823
824         for(n1 = map[v1].first; n1; n1 = n1->next) {
825                 int fnd[4] = {0, 0, 0, 0};
826
827                 for(i = 0; i < 4; ++i) {
828                         for(j = 0; j < 4; ++j) {
829                                 if(v[i] == faces[n1->index].v[j])
830                                         fnd[i] = 1;
831                         }
832                 }
833
834                 if(fnd[0] && fnd[1] && fnd[2] && fnd[3])
835                         return &faces[n1->index];
836         }
837
838         return NULL;
839 }
840
841 static MultiresEdge *find_old_edge(ListBase *map, MultiresEdge *edges, int v1, int v2)
842 {
843         IndexNode *n1, *n2;
844
845         for(n1 = map[v1].first; n1; n1 = n1->next) {
846                 for(n2 = map[v2].first; n2; n2 = n2->next) {
847                         if(n1->index == n2->index)
848                                 return &edges[n1->index];
849                 }
850         }
851
852         return NULL;
853 }
854
855 static void multires_load_old_edges(ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst, int v1, int v2, int mov)
856 {
857         int emid = find_old_edge(emap[2], lvl->edges, v1, v2)->mid;
858         vvmap[dst + mov] = emid;
859
860         if(lvl->next->next) {
861                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v1, emid, mov / 2);
862                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v2, emid, -mov / 2);
863         }
864 }
865
866 static void multires_load_old_faces(ListBase **fmap, ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst,
867                                     int v1, int v2, int v3, int v4, int st2, int st3)
868 {
869         int fmid;
870         int emid13, emid14, emid23, emid24;
871
872         if(lvl && lvl->next) {
873                 fmid = find_old_face(fmap[1], lvl->faces, v1, v2, v3, v4)->mid;
874                 vvmap[dst] = fmid;
875
876                 emid13 = find_old_edge(emap[1], lvl->edges, v1, v3)->mid;
877                 emid14 = find_old_edge(emap[1], lvl->edges, v1, v4)->mid;
878                 emid23 = find_old_edge(emap[1], lvl->edges, v2, v3)->mid;
879                 emid24 = find_old_edge(emap[1], lvl->edges, v2, v4)->mid;
880
881
882                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 + st3,
883                                         fmid, v2, emid23, emid24, st2, st3 / 2);
884
885                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 + st3,
886                                         emid14, emid24, fmid, v4, st2, st3 / 2);
887
888                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 - st3,
889                                         emid13, emid23, v3, fmid, st2, st3 / 2);
890
891                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 - st3,
892                                         v1, fmid, emid13, emid14, st2, st3 / 2);
893
894                 if(lvl->next->next) {
895                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid24, fmid, st3);
896                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid13, fmid, -st3);
897                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid14, fmid, -st2 * st3);
898                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid23, fmid, st2 * st3);
899                 }
900         }
901 }
902
903 /* Loads a multires object stored in the old Multires struct into the new format */
904 void multires_load_old(DerivedMesh *dm, Multires *mr)
905 {
906         MultiresLevel *lvl, *lvl1;
907         MVert *vsrc, *vdst;
908         int src, dst;
909         int totlvl = 2; // XXX MultiresDM_get_totlvl(dm);
910         int st = multires_side_tot[totlvl - 1] - 1;
911         int extedgelen = multires_side_tot[totlvl] - 2;
912         int *vvmap; // inorder for dst, map to src
913         int crossedgelen;
914         int i, j, s, x, totvert, tottri, totquad;
915
916         src = 0;
917         dst = 0;
918         vsrc = mr->verts;
919         vdst = CDDM_get_verts(dm);
920         totvert = dm->getNumVerts(dm);
921         vvmap = MEM_callocN(sizeof(int) * totvert, "multires vvmap");
922
923         lvl1 = mr->levels.first;
924         /* Load base verts */
925         for(i = 0; i < lvl1->totvert; ++i) {
926                 vvmap[totvert - lvl1->totvert + i] = src;
927                 ++src;
928         }
929
930         /* Original edges */
931         dst = totvert - lvl1->totvert - extedgelen * lvl1->totedge;
932         for(i = 0; i < lvl1->totedge; ++i) {
933                 int ldst = dst + extedgelen * i;
934                 int lsrc = src;
935                 lvl = lvl1->next;
936
937                 for(j = 2; j <= mr->level_count; ++j) {
938                         int base = multires_side_tot[totlvl - j + 1] - 2;
939                         int skip = multires_side_tot[totlvl - j + 2] - 1;
940                         int st = multires_side_tot[j - 1] - 1;
941
942                         for(x = 0; x < st; ++x)
943                                 vvmap[ldst + base + x * skip] = lsrc + st * i + x;
944
945                         lsrc += lvl->totvert - lvl->prev->totvert;
946                         lvl = lvl->next;
947                 }
948         }
949
950         /* Center points */
951         dst = 0;
952         for(i = 0; i < lvl1->totface; ++i) {
953                 int sides = lvl1->faces[i].v[3] ? 4 : 3;
954
955                 vvmap[dst] = src + lvl1->totedge + i;
956                 dst += 1 + sides * (st - 1) * st;
957         }
958
959
960         /* The rest is only for level 3 and up */
961         if(lvl1->next && lvl1->next->next) {
962                 ListBase **fmap, **emap;
963                 IndexNode **fmem, **emem;
964
965                 /* Face edge cross */
966                 tottri = totquad = 0;
967                 crossedgelen = multires_side_tot[totlvl - 1] - 2;
968                 dst = 0;
969                 for(i = 0; i < lvl1->totface; ++i) {
970                         int sides = lvl1->faces[i].v[3] ? 4 : 3;
971
972                         lvl = lvl1->next->next;
973                         ++dst;
974
975                         for(j = 3; j <= mr->level_count; ++j) {
976                                 int base = multires_side_tot[totlvl - j + 1] - 2;
977                                 int skip = multires_side_tot[totlvl - j + 2] - 1;
978                                 int st = pow(2, j - 2);
979                                 int st2 = pow(2, j - 3);
980                                 int lsrc = lvl->prev->totvert;
981
982                                 /* Skip exterior edge verts */
983                                 lsrc += lvl1->totedge * st;
984
985                                 /* Skip earlier face edge crosses */
986                                 lsrc += st2 * (tottri * 3 + totquad * 4);
987
988                                 for(s = 0; s < sides; ++s) {
989                                         for(x = 0; x < st2; ++x) {
990                                                 vvmap[dst + crossedgelen * (s + 1) - base - x * skip - 1] = lsrc;
991                                                 ++lsrc;
992                                         }
993                                 }
994
995                                 lvl = lvl->next;
996                         }
997
998                         dst += sides * (st - 1) * st;
999
1000                         if(sides == 4) ++totquad;
1001                         else ++tottri;
1002
1003                 }
1004
1005                 /* calculate vert to edge/face maps for each level (except the last) */
1006                 fmap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires fmap");
1007                 emap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires emap");
1008                 fmem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires fmem");
1009                 emem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires emem");
1010                 lvl = lvl1;
1011                 for(i = 0; i < mr->level_count - 1; ++i) {
1012                         create_old_vert_face_map(fmap + i, fmem + i, lvl->faces, lvl->totvert, lvl->totface);
1013                         create_old_vert_edge_map(emap + i, emem + i, lvl->edges, lvl->totvert, lvl->totedge);
1014                         lvl = lvl->next;
1015                 }
1016
1017                 /* Interior face verts */
1018                 lvl = lvl1->next->next;
1019                 dst = 0;
1020                 for(j = 0; j < lvl1->totface; ++j) {
1021                         int sides = lvl1->faces[j].v[3] ? 4 : 3;
1022                         int ldst = dst + 1 + sides * (st - 1);
1023
1024                         for(s = 0; s < sides; ++s) {
1025                                 int st2 = multires_side_tot[totlvl - 1] - 2;
1026                                 int st3 = multires_side_tot[totlvl - 2] - 2;
1027                                 int st4 = st3 == 0 ? 1 : (st3 + 1) / 2;
1028                                 int mid = ldst + st2 * st3 + st3;
1029                                 int cv = lvl1->faces[j].v[s];
1030                                 int nv = lvl1->faces[j].v[s == sides - 1 ? 0 : s + 1];
1031                                 int pv = lvl1->faces[j].v[s == 0 ? sides - 1 : s - 1];
1032
1033                                 multires_load_old_faces(fmap, emap, lvl1->next, vvmap, mid,
1034                                                         vvmap[dst], cv,
1035                                                         find_old_edge(emap[0], lvl1->edges, pv, cv)->mid,
1036                                                         find_old_edge(emap[0], lvl1->edges, cv, nv)->mid,
1037                                                         st2, st4);
1038
1039                                 ldst += (st - 1) * (st - 1);
1040                         }
1041
1042
1043                         dst = ldst;
1044                 }
1045
1046                 lvl = lvl->next;
1047
1048                 for(i = 0; i < mr->level_count - 1; ++i) {
1049                         MEM_freeN(fmap[i]);
1050                         MEM_freeN(fmem[i]);
1051                         MEM_freeN(emap[i]);
1052                         MEM_freeN(emem[i]);
1053                 }
1054
1055                 MEM_freeN(fmap);
1056                 MEM_freeN(emap);
1057                 MEM_freeN(fmem);
1058                 MEM_freeN(emem);
1059         }
1060
1061         /* Transfer verts */
1062         for(i = 0; i < totvert; ++i)
1063                 copy_v3_v3(vdst[i].co, vsrc[vvmap[i]].co);
1064
1065         MEM_freeN(vvmap);
1066 }
1067