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