Read external mdisp when hamdling topology changes
[blender.git] / source / blender / blenkernel / intern / multires.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software  Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2007 by Nicholas Bishop
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 #include "MEM_guardedalloc.h"
31
32 #include "DNA_mesh_types.h"
33 #include "DNA_meshdata_types.h"
34 #include "DNA_object_types.h"
35 #include "DNA_scene_types.h"
36
37 #include "BLI_blenlib.h"
38 #include "BLI_math.h"
39 #include "BLI_pbvh.h"
40
41 #include "BKE_cdderivedmesh.h"
42 #include "BKE_mesh.h"
43 #include "BKE_modifier.h"
44 #include "BKE_multires.h"
45 #include "BKE_paint.h"
46 #include "BKE_scene.h"
47 #include "BKE_subsurf.h"
48 #include "BKE_utildefines.h"
49 #include "BKE_object.h"
50
51 #include "CCGSubSurf.h"
52
53 #include <math.h>
54 #include <string.h>
55
56 /* MULTIRES MODIFIER */
57 static const int multires_max_levels = 13;
58 static const int multires_grid_tot[] = {0, 4, 9, 25, 81, 289, 1089, 4225, 16641, 66049, 263169, 1050625, 4198401, 16785409};
59 static const int multires_side_tot[] = {0, 2, 3, 5,  9,  17,  33,   65,   129,   257,   513,    1025,    2049,    4097};
60
61 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert);
62 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, int invert, int add, DMGridData **oldGridData, int totlvl);
63
64 DerivedMesh *get_multires_dm(Scene *scene, MultiresModifierData *mmd, Object *ob)
65 {
66         ModifierData *md= (ModifierData *)mmd;
67         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
68         DerivedMesh *tdm = mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
69         DerivedMesh *dm;
70
71         dm = mti->applyModifier(md, ob, tdm, 0, 1);
72         if (dm == tdm) {
73                 dm = CDDM_copy(tdm);
74         }
75
76         return dm;
77 }
78
79 MultiresModifierData *find_multires_modifier_before(Scene *scene, ModifierData *lastmd)
80 {
81         ModifierData *md;
82
83         for(md = lastmd; md; md = md->prev) {
84                 if(md->type == eModifierType_Multires) {
85                         if (modifier_isEnabled(scene, md, eModifierMode_Realtime))
86                                 return (MultiresModifierData*)md;
87                 }
88         }
89
90         return NULL;
91 }
92
93 /* used for applying scale on mdisps layer and syncing subdivide levels when joining objects */
94 static MultiresModifierData *get_multires_modifier(Scene *scene, Object *ob)
95 {
96         ModifierData *md;
97         MultiresModifierData *mmd= NULL, *firstmmd= NULL;
98
99         /* find first active multires modifier */
100         for(md = ob->modifiers.first; md; md = md->next) {
101                 if(md->type == eModifierType_Multires) {
102                         if(!firstmmd)
103                                 firstmmd= (MultiresModifierData*)md;
104
105                         if (modifier_isEnabled(scene, md, eModifierMode_Realtime)) {
106                                 mmd= (MultiresModifierData*)md;
107                                 break;
108                         }
109                 }
110         }
111
112         if(!mmd) {
113                 /* active multires have not been found
114                    try to use first one */
115                 return firstmmd;
116         }
117
118         return mmd;
119 }
120
121 static int multires_get_level(Object *ob, MultiresModifierData *mmd, int render)
122 {
123         if(render)
124                 return (mmd->modifier.scene)? get_render_subsurf_level(&mmd->modifier.scene->r, mmd->renderlvl): mmd->renderlvl;
125         else if(ob->mode == OB_MODE_SCULPT)
126                 return mmd->sculptlvl;
127         else
128                 return (mmd->modifier.scene)? get_render_subsurf_level(&mmd->modifier.scene->r, mmd->lvl): mmd->lvl;
129 }
130
131 static void multires_set_tot_level(Object *ob, MultiresModifierData *mmd, int lvl)
132 {
133         mmd->totlvl = lvl;
134
135         if(ob->mode != OB_MODE_SCULPT)
136                 mmd->lvl = CLAMPIS(MAX2(mmd->lvl, lvl), 0, mmd->totlvl);
137
138         mmd->sculptlvl = CLAMPIS(MAX2(mmd->sculptlvl, lvl), 0, mmd->totlvl);
139         mmd->renderlvl = CLAMPIS(MAX2(mmd->renderlvl, lvl), 0, mmd->totlvl);
140 }
141
142 static void multires_dm_mark_as_modified(DerivedMesh *dm)
143 {
144         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)dm;
145         ccgdm->multires.modified = 1;
146 }
147
148 void multires_mark_as_modified(Object *ob)
149 {
150         if(ob && ob->derivedFinal)
151                 multires_dm_mark_as_modified(ob->derivedFinal);
152 }
153
154 void multires_force_update(Object *ob)
155 {
156         if(ob) {
157                 if(ob->derivedFinal) {
158                         ob->derivedFinal->needsFree =1;
159                         ob->derivedFinal->release(ob->derivedFinal);
160                         ob->derivedFinal = NULL;
161                 }
162                 if(ob->sculpt && ob->sculpt->pbvh) {
163                         BLI_pbvh_free(ob->sculpt->pbvh);
164                         ob->sculpt->pbvh= NULL;
165                 }
166         }
167 }
168
169 void multires_force_external_reload(Object *ob)
170 {
171         Mesh *me = get_mesh(ob);
172
173         CustomData_external_reload(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
174         multires_force_update(ob);
175 }
176
177 void multires_force_render_update(Object *ob)
178 {
179         if(ob && (ob->mode & OB_MODE_SCULPT) && modifiers_findByType(ob, eModifierType_Multires))
180                 multires_force_update(ob);
181 }
182
183 /* XXX */
184 #if 0
185 void multiresModifier_join(Object *ob)
186 {
187         Base *base = NULL;
188         int highest_lvl = 0;
189
190         /* First find the highest level of subdivision */
191         base = FIRSTBASE;
192         while(base) {
193                 if(TESTBASELIB_BGMODE(v3d, scene, base) && base->object->type==OB_MESH) {
194                         ModifierData *md;
195                         for(md = base->object->modifiers.first; md; md = md->next) {
196                                 if(md->type == eModifierType_Multires) {
197                                         int totlvl = ((MultiresModifierData*)md)->totlvl;
198                                         if(totlvl > highest_lvl)
199                                                 highest_lvl = totlvl;
200
201                                         /* Ensure that all updates are processed */
202                                         multires_force_update(base->object);
203                                 }
204                         }
205                 }
206                 base = base->next;
207         }
208
209         /* No multires meshes selected */
210         if(highest_lvl == 0)
211                 return;
212
213         /* Subdivide all the displacements to the highest level */
214         base = FIRSTBASE;
215         while(base) {
216                 if(TESTBASELIB_BGMODE(v3d, scene, base) && base->object->type==OB_MESH) {
217                         ModifierData *md = NULL;
218                         MultiresModifierData *mmd = NULL;
219
220                         for(md = base->object->modifiers.first; md; md = md->next) {
221                                 if(md->type == eModifierType_Multires)
222                                         mmd = (MultiresModifierData*)md;
223                         }
224
225                         /* If the object didn't have multires enabled, give it a new modifier */
226                         if(!mmd) {
227                                 md = base->object->modifiers.first;
228                                 
229                                 while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
230                                         md = md->next;
231                                 
232                                 mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
233                                 BLI_insertlinkbefore(&base->object->modifiers, md, mmd);
234                                 modifier_unique_name(&base->object->modifiers, mmd);
235                         }
236
237                         if(mmd)
238                                 multiresModifier_subdivide(mmd, base->object, highest_lvl - mmd->totlvl, 0, 0);
239                 }
240                 base = base->next;
241         }
242 }
243 #endif
244
245 int multiresModifier_reshapeFromDM(Scene *scene, MultiresModifierData *mmd,
246                                 Object *ob, DerivedMesh *srcdm)
247 {
248         DerivedMesh *mrdm = get_multires_dm (scene, mmd, ob);
249
250         if(mrdm && srcdm && mrdm->getNumVerts(mrdm) == srcdm->getNumVerts(srcdm)) {
251                 multires_mvert_to_ss(mrdm, srcdm->getVertArray(srcdm));
252
253                 multires_dm_mark_as_modified(mrdm);
254                 multires_force_update(ob);
255
256                 mrdm->release(mrdm);
257
258                 return 1;
259         }
260
261         mrdm->release(mrdm);
262
263         return 0;
264 }
265
266 /* Returns 1 on success, 0 if the src's totvert doesn't match */
267 int multiresModifier_reshape(Scene *scene, MultiresModifierData *mmd, Object *dst, Object *src)
268 {
269         DerivedMesh *srcdm = mesh_get_derived_final(scene, src, CD_MASK_BAREMESH);
270         return multiresModifier_reshapeFromDM(scene, mmd, dst, srcdm);
271 }
272
273 int multiresModifier_reshapeFromDeformMod(Scene *scene, MultiresModifierData *mmd,
274                                 Object *ob, ModifierData *md)
275 {
276         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
277         DerivedMesh *dm, *ndm;
278         int numVerts, result;
279         float (*deformedVerts)[3];
280
281         if(multires_get_level(ob, mmd, 0) == 0)
282                 return 0;
283
284         /* Create DerivedMesh for deformation modifier */
285         dm = get_multires_dm(scene, mmd, ob);
286         numVerts= dm->getNumVerts(dm);
287         deformedVerts= MEM_callocN(sizeof(float)*numVerts*3, "multiresReshape_deformVerts");
288
289         dm->getVertCos(dm, deformedVerts);
290         mti->deformVerts(md, ob, dm, deformedVerts, numVerts, 0, 0);
291
292         ndm= CDDM_copy(dm);
293         CDDM_apply_vert_coords(ndm, deformedVerts);
294
295         MEM_freeN(deformedVerts);
296         dm->release(dm);
297
298         /* Reshaping */
299         result= multiresModifier_reshapeFromDM(scene, mmd, ob, ndm);
300
301         /* Cleanup */
302         ndm->release(ndm);
303
304         return result;
305 }
306
307 /* reset the multires levels to match the number of mdisps */
308 static int get_levels_from_disps(Object *ob)
309 {
310         Mesh *me = ob->data;
311         MDisps *mdisp;
312         int i, totlvl= 0;
313
314         mdisp = CustomData_get_layer(&me->fdata, CD_MDISPS);
315
316         for(i = 0; i < me->totface; ++i, ++mdisp) {
317                 int S = me->mface[i].v4 ? 4 : 3;
318
319                 if(mdisp->totdisp == 0) continue;
320
321                 while(1) {
322                         int side = (1 << (totlvl-1)) + 1;
323                         int lvl_totdisp = side*side*S;
324                         if(mdisp->totdisp == lvl_totdisp)
325                                 break;
326                         else if(mdisp->totdisp < lvl_totdisp)
327                                 --totlvl;
328                         else
329                                 ++totlvl;
330
331                 }
332         }
333
334         return totlvl;
335 }
336
337 /* reset the multires levels to match the number of mdisps */
338 void multiresModifier_set_levels_from_disps(MultiresModifierData *mmd, Object *ob)
339 {
340         Mesh *me = ob->data;
341         MDisps *mdisp;
342
343         mdisp = CustomData_get_layer(&me->fdata, CD_MDISPS);
344
345         if(mdisp) {
346                 mmd->totlvl = get_levels_from_disps(ob);
347                 mmd->lvl = MIN2(mmd->sculptlvl, mmd->totlvl);
348                 mmd->sculptlvl = MIN2(mmd->sculptlvl, mmd->totlvl);
349                 mmd->renderlvl = MIN2(mmd->renderlvl, mmd->totlvl);
350         }
351 }
352
353 static void multires_set_tot_mdisps(Mesh *me, int lvl)
354 {
355         MDisps *mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
356         int i;
357
358         if(mdisps) {
359                 for(i = 0; i < me->totface; i++) {
360                         if(mdisps[i].totdisp == 0) {
361                                 int nvert = (me->mface[i].v4)? 4: 3;
362                                 mdisps[i].totdisp = multires_grid_tot[lvl]*nvert;
363                         }
364                 }
365         }
366 }
367
368 static void multires_reallocate_mdisps(Mesh *me, MDisps *mdisps, int lvl)
369 {
370         int i;
371
372         /* reallocate displacements to be filled in */
373         for(i = 0; i < me->totface; ++i) {
374                 int nvert = (me->mface[i].v4)? 4: 3;
375                 int totdisp = multires_grid_tot[lvl]*nvert;
376                 float (*disps)[3] = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
377
378                 if(mdisps[i].disps)
379                         MEM_freeN(mdisps[i].disps);
380
381                 mdisps[i].disps = disps;
382                 mdisps[i].totdisp = totdisp;
383         }
384 }
385
386 static void column_vectors_to_mat3(float mat[][3], float v1[3], float v2[3], float v3[3])
387 {
388         copy_v3_v3(mat[0], v1);
389         copy_v3_v3(mat[1], v2);
390         copy_v3_v3(mat[2], v3);
391 }
392
393 static void multires_copy_grid(float (*gridA)[3], float (*gridB)[3], int sizeA, int sizeB)
394 {
395         int x, y, j, skip;
396
397         if(sizeA > sizeB) {
398                 skip = (sizeA-1)/(sizeB-1);
399
400                 for(j = 0, y = 0; y < sizeB; y++)
401                         for(x = 0; x < sizeB; x++, j++)
402                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip], gridB[j]);
403         }
404         else {
405                 skip = (sizeB-1)/(sizeA-1);
406
407                 for(j = 0, y = 0; y < sizeA; y++)
408                         for(x = 0; x < sizeA; x++, j++)
409                                 copy_v3_v3(gridA[j], gridB[y*skip*sizeB + x*skip]);
410         }
411 }
412
413 static void multires_copy_dm_grid(DMGridData *gridA, DMGridData *gridB, int sizeA, int sizeB)
414 {
415         int x, y, j, skip;
416
417         if(sizeA > sizeB) {
418                 skip = (sizeA-1)/(sizeB-1);
419
420                 for(j = 0, y = 0; y < sizeB; y++)
421                         for(x = 0; x < sizeB; x++, j++)
422                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip].co, gridB[j].co);
423         }
424         else {
425                 skip = (sizeB-1)/(sizeA-1);
426
427                 for(j = 0, y = 0; y < sizeA; y++)
428                         for(x = 0; x < sizeA; x++, j++)
429                                 copy_v3_v3(gridA[j].co, gridB[y*skip*sizeB + x*skip].co);
430         }
431 }
432
433 static void multires_del_higher(MultiresModifierData *mmd, Object *ob, int lvl)
434 {
435         Mesh *me = (Mesh*)ob->data;
436         int levels = mmd->totlvl - lvl;
437         MDisps *mdisps;
438
439         multires_set_tot_mdisps(me, mmd->totlvl);
440         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
441         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
442
443         multires_force_update(ob);
444
445         if(mdisps && levels > 0) {
446                 if(lvl > 0) {
447                         int nsize = multires_side_tot[lvl];
448                         int hsize = multires_side_tot[mmd->totlvl];
449                         int i;
450
451                         for(i = 0; i < me->totface; ++i) {
452                                 MDisps *mdisp= &mdisps[i];
453                                 float (*disps)[3], (*ndisps)[3], (*hdisps)[3];
454                                 int nvert = (me->mface[i].v4)? 4: 3;
455                                 int totdisp = multires_grid_tot[lvl]*nvert;
456                                 int S;
457
458                                 disps = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
459
460                                 ndisps = disps;
461                                 hdisps = mdisp->disps;
462
463                                 for(S = 0; S < nvert; S++) {
464                                         multires_copy_grid(ndisps, hdisps, nsize, hsize);
465
466                                         ndisps += nsize*nsize;
467                                         hdisps += hsize*hsize;
468                                 }
469
470                                 MEM_freeN(mdisp->disps);
471                                 mdisp->disps = disps;
472                                 mdisp->totdisp = totdisp;
473                         }
474                 }
475                 else {
476                         CustomData_external_remove(&me->fdata, &me->id, CD_MDISPS, me->totface);
477                         CustomData_free_layer_active(&me->fdata, CD_MDISPS, me->totface);
478                 }
479         }
480
481         multires_set_tot_level(ob, mmd, lvl);
482 }
483
484 /* direction=1 for delete higher, direction=0 for lower (not implemented yet) */
485 void multiresModifier_del_levels(MultiresModifierData *mmd, Object *ob, int direction)
486 {
487         Mesh *me = get_mesh(ob);
488         int lvl = multires_get_level(ob, mmd, 0);
489         int levels = mmd->totlvl - lvl;
490         MDisps *mdisps;
491
492         multires_set_tot_mdisps(me, mmd->totlvl);
493         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
494         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
495
496         multires_force_update(ob);
497
498         if(mdisps && levels > 0 && direction == 1) {
499                 multires_del_higher(mmd, ob, lvl);
500         }
501
502         multires_set_tot_level(ob, mmd, lvl);
503 }
504
505 static DerivedMesh *multires_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int totlvl, int simple)
506 {
507         MultiresModifierData mmd= {{0}};
508
509         mmd.lvl = lvl;
510         mmd.sculptlvl = lvl;
511         mmd.renderlvl = lvl;
512         mmd.totlvl = totlvl;
513         mmd.simple = simple;
514
515         return multires_dm_create_from_derived(&mmd, 1, dm, ob, 0, 0);
516 }
517
518 static DerivedMesh *subsurf_dm_create_local(Object *UNUSED(ob), DerivedMesh *dm, int lvl, int simple, int optimal)
519 {
520         SubsurfModifierData smd= {{0}};
521
522         smd.levels = smd.renderLevels = lvl;
523         smd.flags |= eSubsurfModifierFlag_SubsurfUv;
524         if(simple)
525                 smd.subdivType = ME_SIMPLE_SUBSURF;
526         if(optimal)
527                 smd.flags |= eSubsurfModifierFlag_ControlEdges;
528
529         return subsurf_make_derived_from_derived(dm, &smd, 0, NULL, 0, 0);
530 }
531
532 void multires_subdivide(MultiresModifierData *mmd, Object *ob, int totlvl, int updateblock, int simple)
533 {
534         Mesh *me = ob->data;
535         MDisps *mdisps;
536         int lvl= mmd->totlvl;
537
538         if(totlvl > multires_max_levels)
539                 return;
540
541         multires_force_update(ob);
542
543         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
544         if(!mdisps)
545                 mdisps = CustomData_add_layer(&me->fdata, CD_MDISPS, CD_DEFAULT, NULL, me->totface);
546
547         if(mdisps->disps && !updateblock && totlvl > 1) {
548                 /* upsample */
549                 DerivedMesh *lowdm, *cddm, *highdm;
550                 DMGridData **highGridData, **lowGridData, **subGridData;
551                 CCGSubSurf *ss;
552                 int i, numGrids, highGridSize, lowGridSize;
553
554                 /* create subsurf DM from original mesh at high level */
555                 cddm = CDDM_from_mesh(me, NULL);
556                 DM_set_only_copy(cddm, CD_MASK_BAREMESH);
557                 highdm = subsurf_dm_create_local(ob, cddm, totlvl, simple, 0);
558
559                 /* create multires DM from original mesh at low level */
560                 lowdm = multires_dm_create_local(ob, cddm, lvl, lvl, simple);
561                 cddm->release(cddm);
562
563                 /* copy subsurf grids and replace them with low displaced grids */
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
570                 subGridData = MEM_callocN(sizeof(float*)*numGrids, "subGridData*");
571
572                 for(i = 0; i < numGrids; ++i) {
573                         /* backup subsurf grids */
574                         subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
575                         memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
576
577                         /* overwrite with current displaced grids */
578                         multires_copy_dm_grid(highGridData[i], lowGridData[i], highGridSize, lowGridSize);
579                 }
580
581                 /* low lower level dm no longer needed at this point */
582                 lowdm->release(lowdm);
583
584                 /* subsurf higher levels again with displaced data */
585                 ss= ((CCGDerivedMesh*)highdm)->ss;
586                 ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
587                 ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
588
589                 /* reallocate displacements */
590                 multires_reallocate_mdisps(me, mdisps, totlvl); 
591
592                 /* compute displacements */
593                 multiresModifier_disp_run(highdm, me, 1, 0, subGridData, totlvl);
594
595                 /* free */
596                 highdm->release(highdm);
597                 for(i = 0; i < numGrids; ++i)
598                         MEM_freeN(subGridData[i]);
599                 MEM_freeN(subGridData);
600         }
601         else {
602                 /* only reallocate, nothing to upsample */
603                 multires_reallocate_mdisps(me, mdisps, totlvl); 
604         }
605
606         multires_set_tot_level(ob, mmd, totlvl);
607 }
608
609 void multiresModifier_subdivide(MultiresModifierData *mmd, Object *ob, int updateblock, int simple)
610 {
611         multires_subdivide(mmd, ob, mmd->totlvl+1, updateblock, simple);
612 }
613
614 static void grid_tangent(int gridSize, int index, int x, int y, int axis, DMGridData **gridData, float t[3])
615 {
616         if(axis == 0) {
617                 if(x == gridSize - 1) {
618                         if(y == gridSize - 1)
619                                 sub_v3_v3v3(t, gridData[index][x + gridSize*(y - 1)].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
620                         else
621                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x - 1 + gridSize*y].co);
622                 }
623                 else
624                         sub_v3_v3v3(t, gridData[index][x + 1 + gridSize*y].co, gridData[index][x + gridSize*y].co);
625         }
626         else if(axis == 1) {
627                 if(y == gridSize - 1) {
628                         if(x == gridSize - 1)
629                                 sub_v3_v3v3(t, gridData[index][x - 1 + gridSize*y].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
630                         else
631                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x + gridSize*(y - 1)].co);
632                 }
633                 else
634                         sub_v3_v3v3(t, gridData[index][x + gridSize*(y + 1)].co, gridData[index][x + gridSize*y].co);
635         }
636 }
637
638 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, int invert, int add, DMGridData **oldGridData, int totlvl)
639 {
640         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)dm;
641         DMGridData **gridData, **subGridData;
642         MFace *mface = me->mface;
643         MDisps *mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
644         int *gridOffset;
645         int i, numGrids, gridSize, dGridSize, dSkip;
646
647         if(!mdisps) {
648                 if(invert)
649                         mdisps = CustomData_add_layer(&me->fdata, CD_MDISPS, CD_DEFAULT, NULL, me->totface);
650                 else
651                         return;
652         }
653
654         numGrids = dm->getNumGrids(dm);
655         gridSize = dm->getGridSize(dm);
656         gridData = dm->getGridData(dm);
657         gridOffset = dm->getGridOffset(dm);
658         subGridData = (oldGridData)? oldGridData: gridData;
659
660         dGridSize = multires_side_tot[totlvl];
661         dSkip = (dGridSize-1)/(gridSize-1);
662
663         #pragma omp parallel for private(i) if(me->totface*gridSize*gridSize*4 >= CCG_OMP_LIMIT)
664         for(i = 0; i < me->totface; ++i) {
665                 const int numVerts = mface[i].v4 ? 4 : 3;
666                 MDisps *mdisp = &mdisps[i];
667                 int S, x, y, gIndex = gridOffset[i];
668
669                 /* when adding new faces in edit mode, need to allocate disps */
670                 if(!mdisp->disps)
671                 #pragma omp critical
672                 {
673                         multires_reallocate_mdisps(me, mdisps, totlvl);
674                 }
675
676                 for(S = 0; S < numVerts; ++S, ++gIndex) {
677                         DMGridData *grid = gridData[gIndex];
678                         DMGridData *subgrid = subGridData[gIndex];
679                         float (*dispgrid)[3] = &mdisp->disps[S*dGridSize*dGridSize];
680
681                         for(y = 0; y < gridSize; y++) {
682                                 for(x = 0; x < gridSize; x++) {
683                                         float *co = grid[x + y*gridSize].co;
684                                         float *sco = subgrid[x + y*gridSize].co;
685                                         float *no = subgrid[x + y*gridSize].no;
686                                         float *data = dispgrid[dGridSize*y*dSkip + x*dSkip];
687                                         float mat[3][3], tx[3], ty[3], disp[3], d[3];
688
689                                         /* construct tangent space matrix */
690                                         grid_tangent(gridSize, gIndex, x, y, 0, subGridData, tx);
691                                         normalize_v3(tx);
692
693                                         grid_tangent(gridSize, gIndex, x, y, 1, subGridData, ty);
694                                         normalize_v3(ty);
695
696                                         //mul_v3_fl(tx, 1.0f/(gridSize-1));
697                                         //mul_v3_fl(ty, 1.0f/(gridSize-1));
698                                         //cross_v3_v3v3(no, tx, ty);
699
700                                         column_vectors_to_mat3(mat, tx, ty, no);
701
702                                         if(!invert) {
703                                                 /* convert to object space and add */
704                                                 mul_v3_m3v3(disp, mat, data);
705                                                 add_v3_v3v3(co, sco, disp);
706                                         }
707                                         else if(!add) {
708                                                 /* convert difference to tangent space */
709                                                 sub_v3_v3v3(disp, co, sco);
710                                                 invert_m3(mat);
711                                                 mul_v3_m3v3(data, mat, disp);
712                                         }
713                                         else {
714                                                 /* convert difference to tangent space */
715                                                 invert_m3(mat);
716                                                 mul_v3_m3v3(d, mat, co);
717                                                 add_v3_v3(data, d);
718                                         }
719                                 }
720                         }
721                 }
722         }
723
724         if(!invert) {
725                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, NULL, 0);
726                 ccgSubSurf_updateNormals(ccgdm->ss, NULL, 0);
727         }
728 }
729
730 static void multiresModifier_update(DerivedMesh *dm)
731 {
732         CCGDerivedMesh *ccgdm= (CCGDerivedMesh*)dm;
733         Object *ob;
734         Mesh *me;
735         MDisps *mdisps;
736         MultiresModifierData *mmd;
737
738         ob = ccgdm->multires.ob;
739         me = ccgdm->multires.ob->data;
740         mmd = ccgdm->multires.mmd;
741         multires_set_tot_mdisps(me, mmd->totlvl);
742         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
743         mdisps = CustomData_get_layer(&me->fdata, CD_MDISPS);
744
745         if(mdisps) {
746                 int lvl = ccgdm->multires.lvl;
747                 int totlvl = ccgdm->multires.totlvl;
748                 
749                 if(lvl < totlvl) {
750                         Mesh *me = ob->data;
751                         DerivedMesh *lowdm, *cddm, *highdm;
752                         DMGridData **highGridData, **lowGridData, **subGridData, **gridData, *diffGrid;
753                         CCGSubSurf *ss;
754                         int i, j, numGrids, highGridSize, lowGridSize;
755
756                         /* create subsurf DM from original mesh at high level */
757                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
758                         else cddm = CDDM_from_mesh(me, NULL);
759                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
760
761                         highdm = subsurf_dm_create_local(ob, cddm, totlvl, mmd->simple, 0);
762
763                         /* create multires DM from original mesh and displacements */
764                         lowdm = multires_dm_create_local(ob, cddm, lvl, totlvl, mmd->simple);
765                         cddm->release(cddm);
766
767                         /* gather grid data */
768                         numGrids = highdm->getNumGrids(highdm);
769                         highGridSize = highdm->getGridSize(highdm);
770                         highGridData = highdm->getGridData(highdm);
771                         lowGridSize = lowdm->getGridSize(lowdm);
772                         lowGridData = lowdm->getGridData(lowdm);
773                         gridData = dm->getGridData(dm);
774
775                         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
776                         diffGrid = MEM_callocN(sizeof(DMGridData)*lowGridSize*lowGridSize, "diff");
777
778                         for(i = 0; i < numGrids; ++i) {
779                                 /* backup subsurf grids */
780                                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
781                                 memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
782
783                                 /* write difference of subsurf and displaced low level into high subsurf */
784                                 for(j = 0; j < lowGridSize*lowGridSize; ++j)
785                                         sub_v3_v3v3(diffGrid[j].co, gridData[i][j].co, lowGridData[i][j].co);
786
787                                 multires_copy_dm_grid(highGridData[i], diffGrid, highGridSize, lowGridSize);
788                         }
789
790                         /* lower level dm no longer needed at this point */
791                         MEM_freeN(diffGrid);
792                         lowdm->release(lowdm);
793
794                         /* subsurf higher levels again with difference of coordinates */
795                         ss= ((CCGDerivedMesh*)highdm)->ss;
796                         ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
797                         ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
798
799                         /* add to displacements */
800                         multiresModifier_disp_run(highdm, me, 1, 1, subGridData, mmd->totlvl);
801
802                         /* free */
803                         highdm->release(highdm);
804                         for(i = 0; i < numGrids; ++i)
805                                 MEM_freeN(subGridData[i]);
806                         MEM_freeN(subGridData);
807                 }
808                 else {
809                         DerivedMesh *cddm, *subdm;
810
811                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
812                         else cddm = CDDM_from_mesh(me, NULL);
813                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
814
815                         subdm = subsurf_dm_create_local(ob, cddm, mmd->totlvl, mmd->simple, 0);
816                         cddm->release(cddm);
817
818                         multiresModifier_disp_run(dm, me, 1, 0, subdm->getGridData(subdm), mmd->totlvl);
819
820                         subdm->release(subdm);
821                 }
822         }
823 }
824
825 void multires_stitch_grids(Object *ob)
826 {
827         /* utility for smooth brush */
828         if(ob && ob->derivedFinal) {
829                 CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)ob->derivedFinal;
830                 CCGFace **faces;
831                 int totface;
832
833                 if(ccgdm->pbvh) {
834                         BLI_pbvh_get_grid_updates(ccgdm->pbvh, 0, (void***)&faces, &totface);
835
836                         if(totface) {
837                                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, faces, totface);
838                                 MEM_freeN(faces);
839                         }
840                 }
841         }
842 }
843
844 DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int local_mmd, DerivedMesh *dm, Object *ob,
845                                                         int useRenderParams, int UNUSED(isFinalCalc))
846 {
847         Mesh *me= ob->data;
848         DerivedMesh *result;
849         CCGDerivedMesh *ccgdm;
850         DMGridData **gridData, **subGridData;
851         int lvl= multires_get_level(ob, mmd, useRenderParams);
852         int i, gridSize, numGrids;
853
854         if(lvl == 0)
855                 return dm;
856
857         result = subsurf_dm_create_local(ob, dm, lvl,
858                 mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges);
859
860         if(!local_mmd) {
861                 ccgdm = (CCGDerivedMesh*)result;
862
863                 ccgdm->multires.ob = ob;
864                 ccgdm->multires.mmd = mmd;
865                 ccgdm->multires.local_mmd = local_mmd;
866                 ccgdm->multires.lvl = lvl;
867                 ccgdm->multires.totlvl = mmd->totlvl;
868                 ccgdm->multires.modified = 0;
869                 ccgdm->multires.update = multiresModifier_update;
870         }
871
872         numGrids = result->getNumGrids(result);
873         gridSize = result->getGridSize(result);
874         gridData = result->getGridData(result);
875
876         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
877
878         for(i = 0; i < numGrids; i++) {
879                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*gridSize*gridSize, "subGridData");
880                 memcpy(subGridData[i], gridData[i], sizeof(DMGridData)*gridSize*gridSize);
881         }
882
883         multires_set_tot_mdisps(me, mmd->totlvl);
884         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
885         multiresModifier_disp_run(result, ob->data, 0, 0, subGridData, mmd->totlvl);
886
887         for(i = 0; i < numGrids; i++)
888                 MEM_freeN(subGridData[i]);
889         MEM_freeN(subGridData);
890
891         return result;
892 }
893
894 /**** Old Multires code ****
895 ***************************/
896
897 /* Adapted from sculptmode.c */
898 static void old_mdisps_bilinear(float out[3], float (*disps)[3], int st, float u, float v)
899 {
900         int x, y, x2, y2;
901         const int st_max = st - 1;
902         float urat, vrat, uopp;
903         float d[4][3], d2[2][3];
904
905         if(u < 0)
906                 u = 0;
907         else if(u >= st)
908                 u = st_max;
909         if(v < 0)
910                 v = 0;
911         else if(v >= st)
912                 v = st_max;
913
914         x = floor(u);
915         y = floor(v);
916         x2 = x + 1;
917         y2 = y + 1;
918
919         if(x2 >= st) x2 = st_max;
920         if(y2 >= st) y2 = st_max;
921         
922         urat = u - x;
923         vrat = v - y;
924         uopp = 1 - urat;
925
926         mul_v3_v3fl(d[0], disps[y * st + x], uopp);
927         mul_v3_v3fl(d[1], disps[y * st + x2], urat);
928         mul_v3_v3fl(d[2], disps[y2 * st + x], uopp);
929         mul_v3_v3fl(d[3], disps[y2 * st + x2], urat);
930
931         add_v3_v3v3(d2[0], d[0], d[1]);
932         add_v3_v3v3(d2[1], d[2], d[3]);
933         mul_v3_fl(d2[0], 1 - vrat);
934         mul_v3_fl(d2[1], vrat);
935
936         add_v3_v3v3(out, d2[0], d2[1]);
937 }
938
939 static void old_mdisps_rotate(int S, int UNUSED(newside), int oldside, int x, int y, float *u, float *v)
940 {
941         float offset = oldside*0.5f - 0.5f;
942
943         if(S == 1) { *u= offset + x; *v = offset - y; }
944         if(S == 2) { *u= offset + y; *v = offset + x; }
945         if(S == 3) { *u= offset - x; *v = offset + y; }
946         if(S == 0) { *u= offset - y; *v = offset - x; }
947 }
948
949 static void old_mdisps_convert(MFace *mface, MDisps *mdisp)
950 {
951         int newlvl = log(sqrt(mdisp->totdisp)-1)/log(2);
952         int oldlvl = newlvl+1;
953         int oldside = multires_side_tot[oldlvl];
954         int newside = multires_side_tot[newlvl];
955         int nvert = (mface->v4)? 4: 3;
956         int newtotdisp = multires_grid_tot[newlvl]*nvert;
957         int x, y, S;
958         float (*disps)[3], (*out)[3], u, v;
959
960         disps = MEM_callocN(sizeof(float) * 3 * newtotdisp, "multires disps");
961
962         out = disps;
963         for(S = 0; S < nvert; S++) {
964                 for(y = 0; y < newside; ++y) {
965                         for(x = 0; x < newside; ++x, ++out) {
966                                 old_mdisps_rotate(S, newside, oldside, x, y, &u, &v);
967                                 old_mdisps_bilinear(*out, mdisp->disps, oldside, u, v);
968
969                                 if(S == 1) { (*out)[1]= -(*out)[1]; }
970                                 else if(S == 2) { SWAP(float, (*out)[0], (*out)[1]); }
971                                 else if(S == 3) { (*out)[0]= -(*out)[0]; }
972                                 else if(S == 0) { SWAP(float, (*out)[0], (*out)[1]); (*out)[0]= -(*out)[0]; (*out)[1]= -(*out)[1]; };
973                         }
974                 }
975         }
976
977         MEM_freeN(mdisp->disps);
978
979         mdisp->totdisp= newtotdisp;
980         mdisp->disps= disps;
981 }
982
983 void multires_load_old_250(Mesh *me)
984 {
985         MDisps *mdisps;
986         int a;
987
988         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
989
990         if(mdisps) {
991                 for(a=0; a<me->totface; a++)
992                         if(mdisps[a].totdisp)
993                                 old_mdisps_convert(&me->mface[a], &mdisps[a]);
994         }
995 }
996
997 /* Does not actually free lvl itself */
998 static void multires_free_level(MultiresLevel *lvl)
999 {
1000         if(lvl) {
1001                 if(lvl->faces) MEM_freeN(lvl->faces);
1002                 if(lvl->edges) MEM_freeN(lvl->edges);
1003                 if(lvl->colfaces) MEM_freeN(lvl->colfaces);
1004         }
1005 }
1006
1007 void multires_free(Multires *mr)
1008 {
1009         if(mr) {
1010                 MultiresLevel* lvl= mr->levels.first;
1011
1012                 /* Free the first-level data */
1013                 if(lvl) {
1014                         CustomData_free(&mr->vdata, lvl->totvert);
1015                         CustomData_free(&mr->fdata, lvl->totface);
1016                         if(mr->edge_flags)
1017                                 MEM_freeN(mr->edge_flags);
1018                         if(mr->edge_creases)
1019                                 MEM_freeN(mr->edge_creases);
1020                 }
1021
1022                 while(lvl) {
1023                         multires_free_level(lvl);                       
1024                         lvl= lvl->next;
1025                 }
1026
1027                 MEM_freeN(mr->verts);
1028
1029                 BLI_freelistN(&mr->levels);
1030
1031                 MEM_freeN(mr);
1032         }
1033 }
1034
1035 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
1036                                          const int totvert, const int totface)
1037 {
1038         int i,j;
1039         IndexNode *node = NULL;
1040         
1041         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
1042         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
1043         node = *mem;
1044         
1045         /* Find the users */
1046         for(i = 0; i < totface; ++i){
1047                 for(j = 0; j < (mface[i].v[3]?4:3); ++j, ++node) {
1048                         node->index = i;
1049                         BLI_addtail(&(*map)[mface[i].v[j]], node);
1050                 }
1051         }
1052 }
1053
1054 static void create_old_vert_edge_map(ListBase **map, IndexNode **mem, const MultiresEdge *medge,
1055                                          const int totvert, const int totedge)
1056 {
1057         int i,j;
1058         IndexNode *node = NULL;
1059         
1060         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
1061         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge*2, "vert edge map mem");
1062         node = *mem;
1063         
1064         /* Find the users */
1065         for(i = 0; i < totedge; ++i){
1066                 for(j = 0; j < 2; ++j, ++node) {
1067                         node->index = i;
1068                         BLI_addtail(&(*map)[medge[i].v[j]], node);
1069                 }
1070         }
1071 }
1072
1073 static MultiresFace *find_old_face(ListBase *map, MultiresFace *faces, int v1, int v2, int v3, int v4)
1074 {
1075         IndexNode *n1;
1076         int v[4], i, j;
1077
1078          v[0]= v1;
1079          v[1]= v2;
1080          v[2]= v3;
1081          v[3]= v4;
1082
1083         for(n1 = map[v1].first; n1; n1 = n1->next) {
1084                 int fnd[4] = {0, 0, 0, 0};
1085
1086                 for(i = 0; i < 4; ++i) {
1087                         for(j = 0; j < 4; ++j) {
1088                                 if(v[i] == faces[n1->index].v[j])
1089                                         fnd[i] = 1;
1090                         }
1091                 }
1092
1093                 if(fnd[0] && fnd[1] && fnd[2] && fnd[3])
1094                         return &faces[n1->index];
1095         }
1096
1097         return NULL;
1098 }
1099
1100 static MultiresEdge *find_old_edge(ListBase *map, MultiresEdge *edges, int v1, int v2)
1101 {
1102         IndexNode *n1, *n2;
1103
1104         for(n1 = map[v1].first; n1; n1 = n1->next) {
1105                 for(n2 = map[v2].first; n2; n2 = n2->next) {
1106                         if(n1->index == n2->index)
1107                                 return &edges[n1->index];
1108                 }
1109         }
1110
1111         return NULL;
1112 }
1113
1114 static void multires_load_old_edges(ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst, int v1, int v2, int mov)
1115 {
1116         int emid = find_old_edge(emap[2], lvl->edges, v1, v2)->mid;
1117         vvmap[dst + mov] = emid;
1118
1119         if(lvl->next->next) {
1120                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v1, emid, mov / 2);
1121                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v2, emid, -mov / 2);
1122         }
1123 }
1124
1125 static void multires_load_old_faces(ListBase **fmap, ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst,
1126                                         int v1, int v2, int v3, int v4, int st2, int st3)
1127 {
1128         int fmid;
1129         int emid13, emid14, emid23, emid24;
1130
1131         if(lvl && lvl->next) {
1132                 fmid = find_old_face(fmap[1], lvl->faces, v1, v2, v3, v4)->mid;
1133                 vvmap[dst] = fmid;
1134
1135                 emid13 = find_old_edge(emap[1], lvl->edges, v1, v3)->mid;
1136                 emid14 = find_old_edge(emap[1], lvl->edges, v1, v4)->mid;
1137                 emid23 = find_old_edge(emap[1], lvl->edges, v2, v3)->mid;
1138                 emid24 = find_old_edge(emap[1], lvl->edges, v2, v4)->mid;
1139
1140
1141                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 + st3,
1142                                         fmid, v2, emid23, emid24, st2, st3 / 2);
1143
1144                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 + st3,
1145                                         emid14, emid24, fmid, v4, st2, st3 / 2);
1146
1147                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 - st3,
1148                                         emid13, emid23, v3, fmid, st2, st3 / 2);
1149
1150                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 - st3,
1151                                         v1, fmid, emid13, emid14, st2, st3 / 2);
1152
1153                 if(lvl->next->next) {
1154                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid24, fmid, st3);
1155                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid13, fmid, -st3);
1156                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid14, fmid, -st2 * st3);
1157                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid23, fmid, st2 * st3);
1158                 }
1159         }
1160 }
1161
1162 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert)
1163 {
1164         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*) dm;
1165         CCGSubSurf *ss = ccgdm->ss;
1166         DMGridData *vd;
1167         int index;
1168         int totvert, totedge, totface;
1169         int gridSize = ccgSubSurf_getGridSize(ss);
1170         int edgeSize = ccgSubSurf_getEdgeSize(ss);
1171         int i = 0;
1172
1173         totface = ccgSubSurf_getNumFaces(ss);
1174         for(index = 0; index < totface; index++) {
1175                 CCGFace *f = ccgdm->faceMap[index].face;
1176                 int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1177
1178                 vd= ccgSubSurf_getFaceCenterData(f);
1179                 copy_v3_v3(vd->co, mvert[i].co);
1180                 i++;
1181                 
1182                 for(S = 0; S < numVerts; S++) {
1183                         for(x = 1; x < gridSize - 1; x++, i++) {
1184                                 vd= ccgSubSurf_getFaceGridEdgeData(ss, f, S, x);
1185                                 copy_v3_v3(vd->co, mvert[i].co);
1186                         }
1187                 }
1188
1189                 for(S = 0; S < numVerts; S++) {
1190                         for(y = 1; y < gridSize - 1; y++) {
1191                                 for(x = 1; x < gridSize - 1; x++, i++) {
1192                                         vd= ccgSubSurf_getFaceGridData(ss, f, S, x, y);
1193                                         copy_v3_v3(vd->co, mvert[i].co);
1194                                 }
1195                         }
1196                 }
1197         }
1198
1199         totedge = ccgSubSurf_getNumEdges(ss);
1200         for(index = 0; index < totedge; index++) {
1201                 CCGEdge *e = ccgdm->edgeMap[index].edge;
1202                 int x;
1203
1204                 for(x = 1; x < edgeSize - 1; x++, i++) {
1205                         vd= ccgSubSurf_getEdgeData(ss, e, x);
1206                         copy_v3_v3(vd->co, mvert[i].co);
1207                 }
1208         }
1209
1210         totvert = ccgSubSurf_getNumVerts(ss);
1211         for(index = 0; index < totvert; index++) {
1212                 CCGVert *v = ccgdm->vertMap[index].vert;
1213
1214                 vd= ccgSubSurf_getVertData(ss, v);
1215                 copy_v3_v3(vd->co, mvert[i].co);
1216                 i++;
1217         }
1218
1219         ccgSubSurf_updateToFaces(ss, 0, NULL, 0);
1220 }
1221
1222 /* Loads a multires object stored in the old Multires struct into the new format */
1223 static void multires_load_old_dm(DerivedMesh *dm, Mesh *me, int totlvl)
1224 {
1225         MultiresLevel *lvl, *lvl1;
1226         Multires *mr= me->mr;
1227         MVert *vsrc, *vdst;
1228         unsigned int src, dst;
1229         int st = multires_side_tot[totlvl - 1] - 1;
1230         int extedgelen = multires_side_tot[totlvl] - 2;
1231         int *vvmap; // inorder for dst, map to src
1232         int crossedgelen;
1233         int s, x, tottri, totquad;
1234         unsigned int i, j, totvert;
1235
1236         src = 0;
1237         dst = 0;
1238         vsrc = mr->verts;
1239         vdst = dm->getVertArray(dm);
1240         totvert = (unsigned int)dm->getNumVerts(dm);
1241         vvmap = MEM_callocN(sizeof(int) * totvert, "multires vvmap");
1242
1243         lvl1 = mr->levels.first;
1244         /* Load base verts */
1245         for(i = 0; i < lvl1->totvert; ++i) {
1246                 vvmap[totvert - lvl1->totvert + i] = src;
1247                 ++src;
1248         }
1249
1250         /* Original edges */
1251         dst = totvert - lvl1->totvert - extedgelen * lvl1->totedge;
1252         for(i = 0; i < lvl1->totedge; ++i) {
1253                 int ldst = dst + extedgelen * i;
1254                 int lsrc = src;
1255                 lvl = lvl1->next;
1256
1257                 for(j = 2; j <= mr->level_count; ++j) {
1258                         int base = multires_side_tot[totlvl - j + 1] - 2;
1259                         int skip = multires_side_tot[totlvl - j + 2] - 1;
1260                         int st = multires_side_tot[j - 1] - 1;
1261
1262                         for(x = 0; x < st; ++x)
1263                                 vvmap[ldst + base + x * skip] = lsrc + st * i + x;
1264
1265                         lsrc += lvl->totvert - lvl->prev->totvert;
1266                         lvl = lvl->next;
1267                 }
1268         }
1269
1270         /* Center points */
1271         dst = 0;
1272         for(i = 0; i < lvl1->totface; ++i) {
1273                 int sides = lvl1->faces[i].v[3] ? 4 : 3;
1274
1275                 vvmap[dst] = src + lvl1->totedge + i;
1276                 dst += 1 + sides * (st - 1) * st;
1277         }
1278
1279
1280         /* The rest is only for level 3 and up */
1281         if(lvl1->next && lvl1->next->next) {
1282                 ListBase **fmap, **emap;
1283                 IndexNode **fmem, **emem;
1284
1285                 /* Face edge cross */
1286                 tottri = totquad = 0;
1287                 crossedgelen = multires_side_tot[totlvl - 1] - 2;
1288                 dst = 0;
1289                 for(i = 0; i < lvl1->totface; ++i) {
1290                         int sides = lvl1->faces[i].v[3] ? 4 : 3;
1291
1292                         lvl = lvl1->next->next;
1293                         ++dst;
1294
1295                         for(j = 3; j <= mr->level_count; ++j) {
1296                                 int base = multires_side_tot[totlvl - j + 1] - 2;
1297                                 int skip = multires_side_tot[totlvl - j + 2] - 1;
1298                                 int st = pow(2, j - 2);
1299                                 int st2 = pow(2, j - 3);
1300                                 int lsrc = lvl->prev->totvert;
1301
1302                                 /* Skip exterior edge verts */
1303                                 lsrc += lvl1->totedge * st;
1304
1305                                 /* Skip earlier face edge crosses */
1306                                 lsrc += st2 * (tottri * 3 + totquad * 4);
1307
1308                                 for(s = 0; s < sides; ++s) {
1309                                         for(x = 0; x < st2; ++x) {
1310                                                 vvmap[dst + crossedgelen * (s + 1) - base - x * skip - 1] = lsrc;
1311                                                 ++lsrc;
1312                                         }
1313                                 }
1314
1315                                 lvl = lvl->next;
1316                         }
1317
1318                         dst += sides * (st - 1) * st;
1319
1320                         if(sides == 4) ++totquad;
1321                         else ++tottri;
1322
1323                 }
1324
1325                 /* calculate vert to edge/face maps for each level (except the last) */
1326                 fmap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires fmap");
1327                 emap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires emap");
1328                 fmem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires fmem");
1329                 emem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires emem");
1330                 lvl = lvl1;
1331                 for(i = 0; i < (unsigned int)mr->level_count - 1; ++i) {
1332                         create_old_vert_face_map(fmap + i, fmem + i, lvl->faces, lvl->totvert, lvl->totface);
1333                         create_old_vert_edge_map(emap + i, emem + i, lvl->edges, lvl->totvert, lvl->totedge);
1334                         lvl = lvl->next;
1335                 }
1336
1337                 /* Interior face verts */
1338                 lvl = lvl1->next->next;
1339                 dst = 0;
1340                 for(j = 0; j < lvl1->totface; ++j) {
1341                         int sides = lvl1->faces[j].v[3] ? 4 : 3;
1342                         int ldst = dst + 1 + sides * (st - 1);
1343
1344                         for(s = 0; s < sides; ++s) {
1345                                 int st2 = multires_side_tot[totlvl - 1] - 2;
1346                                 int st3 = multires_side_tot[totlvl - 2] - 2;
1347                                 int st4 = st3 == 0 ? 1 : (st3 + 1) / 2;
1348                                 int mid = ldst + st2 * st3 + st3;
1349                                 int cv = lvl1->faces[j].v[s];
1350                                 int nv = lvl1->faces[j].v[s == sides - 1 ? 0 : s + 1];
1351                                 int pv = lvl1->faces[j].v[s == 0 ? sides - 1 : s - 1];
1352
1353                                 multires_load_old_faces(fmap, emap, lvl1->next, vvmap, mid,
1354                                                         vvmap[dst], cv,
1355                                                         find_old_edge(emap[0], lvl1->edges, pv, cv)->mid,
1356                                                         find_old_edge(emap[0], lvl1->edges, cv, nv)->mid,
1357                                                         st2, st4);
1358
1359                                 ldst += (st - 1) * (st - 1);
1360                         }
1361
1362
1363                         dst = ldst;
1364                 }
1365
1366                 lvl = lvl->next;
1367
1368                 for(i = 0; i < (unsigned int)(mr->level_count - 1); ++i) {
1369                         MEM_freeN(fmap[i]);
1370                         MEM_freeN(fmem[i]);
1371                         MEM_freeN(emap[i]);
1372                         MEM_freeN(emem[i]);
1373                 }
1374
1375                 MEM_freeN(fmap);
1376                 MEM_freeN(emap);
1377                 MEM_freeN(fmem);
1378                 MEM_freeN(emem);
1379         }
1380
1381         /* Transfer verts */
1382         for(i = 0; i < totvert; ++i)
1383                 copy_v3_v3(vdst[i].co, vsrc[vvmap[i]].co);
1384
1385         MEM_freeN(vvmap);
1386
1387         multires_mvert_to_ss(dm, vdst);
1388 }
1389
1390
1391 void multires_load_old(Object *ob, Mesh *me)
1392 {
1393         MultiresLevel *lvl;
1394         ModifierData *md;
1395         MultiresModifierData *mmd;
1396         DerivedMesh *dm, *orig;
1397         CustomDataLayer *l;
1398         int i;
1399
1400         /* Load original level into the mesh */
1401         lvl = me->mr->levels.first;
1402         CustomData_free_layers(&me->vdata, CD_MVERT, lvl->totvert);
1403         CustomData_free_layers(&me->edata, CD_MEDGE, lvl->totedge);
1404         CustomData_free_layers(&me->fdata, CD_MFACE, lvl->totface);
1405         me->totvert = lvl->totvert;
1406         me->totedge = lvl->totedge;
1407         me->totface = lvl->totface;
1408         me->mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
1409         me->medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
1410         me->mface = CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
1411         memcpy(me->mvert, me->mr->verts, sizeof(MVert) * me->totvert);
1412         for(i = 0; i < me->totedge; ++i) {
1413                 me->medge[i].v1 = lvl->edges[i].v[0];
1414                 me->medge[i].v2 = lvl->edges[i].v[1];
1415         }
1416         for(i = 0; i < me->totface; ++i) {
1417                 me->mface[i].v1 = lvl->faces[i].v[0];
1418                 me->mface[i].v2 = lvl->faces[i].v[1];
1419                 me->mface[i].v3 = lvl->faces[i].v[2];
1420                 me->mface[i].v4 = lvl->faces[i].v[3];
1421         }
1422
1423         /* Add a multires modifier to the object */
1424         md = ob->modifiers.first;
1425         while(md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
1426                 md = md->next;                          
1427         mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
1428         BLI_insertlinkbefore(&ob->modifiers, md, mmd);
1429
1430         for(i = 0; i < me->mr->level_count - 1; ++i)
1431                 multiresModifier_subdivide(mmd, ob, 1, 0);
1432
1433         mmd->lvl = mmd->totlvl;
1434         orig = CDDM_from_mesh(me, NULL);
1435         dm = multires_dm_create_from_derived(mmd, 0, orig, ob, 0, 0);
1436                                            
1437         multires_load_old_dm(dm, me, mmd->totlvl+1);
1438
1439         multires_dm_mark_as_modified(dm);
1440         dm->release(dm);
1441         orig->release(orig);
1442
1443         /* Copy the first-level data to the mesh */
1444         for(i = 0, l = me->mr->vdata.layers; i < me->mr->vdata.totlayer; ++i, ++l)
1445                 CustomData_add_layer(&me->vdata, l->type, CD_REFERENCE, l->data, me->totvert);
1446         for(i = 0, l = me->mr->fdata.layers; i < me->mr->fdata.totlayer; ++i, ++l)
1447                 CustomData_add_layer(&me->fdata, l->type, CD_REFERENCE, l->data, me->totface);
1448         memset(&me->mr->vdata, 0, sizeof(CustomData));
1449         memset(&me->mr->fdata, 0, sizeof(CustomData));
1450
1451         /* Remove the old multires */
1452         multires_free(me->mr);
1453         me->mr= NULL;
1454 }
1455
1456 static void multires_sync_levels(Scene *scene, Object *ob, Object *to_ob)
1457 {
1458         MultiresModifierData *mmd= get_multires_modifier(scene, ob);
1459         MultiresModifierData *to_mmd= get_multires_modifier(scene, to_ob);
1460
1461         if(!mmd) {
1462                 /* object could have MDISP even when there is no multires modifier
1463                    this could lead to troubles due to i've got no idea how mdisp could be
1464                    upsampled correct without modifier data.
1465                    just remove mdisps if no multires present (nazgul) */
1466
1467                 Mesh *me= (Mesh*)ob->data;
1468
1469                 CustomData_external_remove(&me->fdata, &me->id, CD_MDISPS, me->totface);
1470                 CustomData_free_layer_active(&me->fdata, CD_MDISPS, me->totface);
1471         }
1472
1473         if(!mmd || !to_mmd) return;
1474
1475         if(mmd->totlvl>to_mmd->totlvl) multires_del_higher(mmd, ob, to_mmd->totlvl);
1476         else multires_subdivide(mmd, ob, to_mmd->totlvl, 0, mmd->simple);
1477 }
1478
1479 void multires_apply_smat(Scene *scene, Object *ob, float smat[3][3])
1480 {
1481         DerivedMesh *dm= NULL, *cddm= NULL, *subdm= NULL;
1482         DMGridData **gridData, **subGridData;
1483         Mesh *me= (Mesh*)ob->data;
1484         MFace *mface= me->mface;
1485         MVert *mvert= NULL;
1486         MDisps *mdisps;
1487         int *gridOffset;
1488         int i, numGrids, gridSize, dGridSize, dSkip, totvert;
1489         float (*vertCos)[3] = NULL;
1490         MultiresModifierData *mmd= get_multires_modifier(scene, ob);
1491         MultiresModifierData high_mmd;
1492
1493         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
1494         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
1495
1496         if(!mdisps || !mmd) return;
1497
1498         /* we need derived mesh created from highest resolution */
1499         high_mmd= *mmd;
1500         high_mmd.lvl= high_mmd.totlvl;
1501
1502         /* unscaled multires with applied displacement */
1503         subdm= get_multires_dm(scene, &high_mmd, ob);
1504
1505         /* prepare scaled CDDM to create ccgDN */
1506         cddm= mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
1507
1508         totvert= cddm->getNumVerts(cddm);
1509         vertCos= MEM_mallocN(sizeof(*vertCos) * totvert, "multiresScale vertCos");
1510         cddm->getVertCos(cddm, vertCos);
1511         for(i=0; i<totvert; i++)
1512                 mul_m3_v3(smat, vertCos[i]);
1513         CDDM_apply_vert_coords(cddm, vertCos);
1514         MEM_freeN(vertCos);
1515
1516         mvert= cddm->getVertArray(cddm);
1517
1518         /* scaled ccgDM for tangent space of object with applied scale */
1519         dm= subsurf_dm_create_local(ob, cddm, high_mmd.totlvl, high_mmd.simple, 0);
1520         cddm->release(cddm);
1521
1522         numGrids= dm->getNumGrids(dm);
1523         gridSize= dm->getGridSize(dm);
1524         gridData= dm->getGridData(dm);
1525         gridOffset= dm->getGridOffset(dm);
1526         subGridData= subdm->getGridData(subdm);
1527
1528         dGridSize= multires_side_tot[high_mmd.totlvl];
1529         dSkip= (dGridSize-1)/(gridSize-1);
1530
1531         #pragma omp parallel for private(i) if(me->totface*gridSize*gridSize*4 >= CCG_OMP_LIMIT)
1532         for(i = 0; i < me->totface; ++i) {
1533                 const int numVerts= mface[i].v4 ? 4 : 3;
1534                 MDisps *mdisp= &mdisps[i];
1535                 int S, x, y, gIndex = gridOffset[i];
1536
1537                 for(S = 0; S < numVerts; ++S, ++gIndex) {
1538                         DMGridData *grid= gridData[gIndex];
1539                         DMGridData *subgrid= subGridData[gIndex];
1540                         float (*dispgrid)[3]= &mdisp->disps[S*dGridSize*dGridSize];
1541
1542                         for(y = 0; y < gridSize; y++) {
1543                                 for(x = 0; x < gridSize; x++) {
1544                                         float *co= grid[x + y*gridSize].co;
1545                                         float *sco= subgrid[x + y*gridSize].co;
1546                                         float *no= grid[x + y*gridSize].no;
1547                                         float *data= dispgrid[dGridSize*y*dSkip + x*dSkip];
1548                                         float mat[3][3], tx[3], ty[3], disp[3];
1549
1550                                         /* construct tangent space matrix */
1551                                         grid_tangent(gridSize, gIndex, x, y, 0, gridData, tx);
1552                                         normalize_v3(tx);
1553
1554                                         grid_tangent(gridSize, gIndex, x, y, 1, gridData, ty);
1555                                         normalize_v3(ty);
1556
1557                                         column_vectors_to_mat3(mat, tx, ty, no);
1558
1559                                         /* scale subgrid coord and calculate displacement */
1560                                         mul_m3_v3(smat, sco);
1561                                         sub_v3_v3v3(disp, sco, co);
1562
1563                                         /* convert difference to tangent space */
1564                                         invert_m3(mat);
1565                                         mul_v3_m3v3(data, mat, disp);
1566                                 }
1567                         }
1568                 }
1569         }
1570
1571         dm->release(dm);
1572         subdm->release(subdm);
1573 }
1574
1575 int multires_mdisp_corners(MDisps *s)
1576 {
1577         int lvl= 13;
1578
1579         while(lvl > 0) {
1580                 int side = (1 << (lvl-1)) + 1;
1581                 if ((s->totdisp % (side*side)) == 0) return s->totdisp / (side*side);
1582                 lvl--;
1583         }
1584
1585         return 0;
1586 }
1587
1588 void multiresModifier_scale_disp(Scene *scene, Object *ob)
1589 {
1590         float smat[3][3];
1591
1592         /* object's scale matrix */
1593         object_scale_to_mat3(ob, smat);
1594
1595         multires_apply_smat(scene, ob, smat);
1596 }
1597
1598 void multiresModifier_prepare_join(Scene *scene, Object *ob, Object *to_ob)
1599 {
1600         float smat[3][3], tmat[3][3], mat[3][3];
1601         multires_sync_levels(scene, ob, to_ob);
1602
1603         /* construct scale matrix for displacement */
1604         object_scale_to_mat3(to_ob, tmat);
1605         invert_m3(tmat);
1606         object_scale_to_mat3(ob, smat);
1607         mul_m3_m3m3(mat, smat, tmat);
1608
1609         multires_apply_smat(scene, ob, mat);
1610 }
1611
1612 /* update multires data after topology changing */
1613 void multires_topology_changed(Object *ob)
1614 {
1615         Mesh *me= (Mesh*)ob->data;
1616         MDisps *mdisp= NULL;
1617         int i;
1618
1619         CustomData_external_read(&me->fdata, &me->id, CD_MASK_MDISPS, me->totface);
1620         mdisp= CustomData_get_layer(&me->fdata, CD_MDISPS);
1621
1622         if(!mdisp) return;
1623
1624         for(i = 0; i < me->totface; i++, mdisp++) {
1625                 int corners= multires_mdisp_corners(mdisp);
1626                 int nvert= me->mface[i].v4 ? 4 : 3;
1627
1628                 if(corners!=nvert) {
1629                         mdisp->totdisp= (mdisp->totdisp/corners)*nvert;
1630
1631                         if(mdisp->disps)
1632                                 MEM_freeN(mdisp->disps);
1633
1634                         mdisp->disps= MEM_callocN(mdisp->totdisp*sizeof(float)*3, "mdisp topology");
1635                 }
1636         }
1637 }