code cleanup: function naming, use BKE_*type* prefix.
[blender.git] / source / blender / blenkernel / intern / multires.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software  Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2007 by Nicholas Bishop
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/multires.c
29  *  \ingroup bke
30  */
31
32
33 #include "MEM_guardedalloc.h"
34
35 /* for reading old multires */
36 #define DNA_DEPRECATED_ALLOW
37
38 #include "DNA_mesh_types.h"
39 #include "DNA_meshdata_types.h"
40 #include "DNA_object_types.h"
41 #include "DNA_scene_types.h"
42
43 #include "BLI_bitmap.h"
44 #include "BLI_blenlib.h"
45 #include "BLI_math.h"
46 #include "BLI_pbvh.h"
47 #include "BLI_utildefines.h"
48
49 #include "BKE_cdderivedmesh.h"
50 #include "BKE_mesh.h"
51 #include "BKE_modifier.h"
52 #include "BKE_multires.h"
53 #include "BKE_paint.h"
54 #include "BKE_scene.h"
55 #include "BKE_subsurf.h"
56 #include "BKE_tessmesh.h"
57
58 #include "BKE_object.h"
59
60 #include "CCGSubSurf.h"
61
62 #include <math.h>
63 #include <string.h>
64
65 /* MULTIRES MODIFIER */
66 static const int multires_max_levels = 13;
67 static const int multires_grid_tot[] = {0, 4, 9, 25, 81, 289, 1089, 4225, 16641, 66049, 263169, 1050625, 4198401, 16785409};
68 static const int multires_side_tot[] = {0, 2, 3, 5,  9,  17,  33,   65,   129,   257,   513,    1025,    2049,    4097};
69
70 /* See multiresModifier_disp_run for description of each operation */
71 typedef enum {
72         APPLY_DISPLACEMENTS,
73         CALC_DISPLACEMENTS,
74         ADD_DISPLACEMENTS,
75 } DispOp;
76
77 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert);
78 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, DerivedMesh *dm2, DispOp op, DMGridData **oldGridData, int totlvl);
79
80 /** Customdata **/
81
82 void multires_customdata_delete(Mesh *me)
83 {
84         if (me->edit_btmesh) {
85                 BMEditMesh *em= me->edit_btmesh;
86                 /* CustomData_external_remove is used here only to mark layer
87                  * as non-external for further free-ing, so zero element count
88                  * looks safer than em->totface */
89                 CustomData_external_remove(&em->bm->ldata, &me->id,
90                                                                    CD_MDISPS, 0);
91                 BM_data_layer_free(em->bm, &em->bm->ldata, CD_MDISPS);
92         }
93         else {
94                 CustomData_external_remove(&me->ldata, &me->id,
95                                                                    CD_MDISPS, me->totloop);
96                 CustomData_free_layer_active(&me->ldata, CD_MDISPS,
97                                                                          me->totloop);
98         }
99 }
100
101 /** Grid hiding **/
102 static BLI_bitmap multires_mdisps_upsample_hidden(BLI_bitmap lo_hidden,
103                                                                                                   int lo_level,
104                                                                                                   int hi_level,
105                                                                          
106                                                                                                   /* assumed to be at hi_level (or
107                                                                                                    *  null) */
108                                                                                                   BLI_bitmap prev_hidden)
109 {
110         BLI_bitmap subd;
111         int hi_gridsize = ccg_gridsize(hi_level);
112         int lo_gridsize = ccg_gridsize(lo_level);
113         int yh, xh, xl, yl, xo, yo, hi_ndx;
114         int offset, factor;
115
116         BLI_assert(lo_level <= hi_level);
117
118         /* fast case */
119         if (lo_level == hi_level)
120                 return MEM_dupallocN(lo_hidden);
121
122         subd = BLI_BITMAP_NEW(hi_gridsize * hi_gridsize, "MDisps.hidden upsample");
123
124         factor = ccg_factor(lo_level, hi_level);
125         offset = 1 << (hi_level - lo_level - 1);
126
127         /* low-res blocks */
128         for (yl = 0; yl < lo_gridsize; yl++) {
129                 for (xl = 0; xl < lo_gridsize; xl++) {
130                         int lo_val = BLI_BITMAP_GET(lo_hidden, yl * lo_gridsize + xl);
131
132                         /* high-res blocks */
133                         for (yo = -offset; yo <= offset; yo++) {
134                                 yh = yl * factor + yo;
135                                 if (yh < 0 || yh >= hi_gridsize)
136                                         continue;
137
138                                 for (xo = -offset; xo <= offset; xo++) {
139                                         xh = xl * factor + xo;
140                                         if (xh < 0 || xh >= hi_gridsize)
141                                                 continue;
142
143                                         hi_ndx = yh * hi_gridsize + xh;
144
145                                         if (prev_hidden) {
146                                                 /* If prev_hidden is available, copy it to
147                                                  * subd, except when the equivalent element in
148                                                  * lo_hidden is different */
149                                                 if (lo_val != prev_hidden[hi_ndx])
150                                                         BLI_BITMAP_MODIFY(subd, hi_ndx, lo_val);
151                                                 else
152                                                         BLI_BITMAP_MODIFY(subd, hi_ndx, prev_hidden[hi_ndx]);
153                                         }
154                                         else {
155                                                 BLI_BITMAP_MODIFY(subd, hi_ndx, lo_val);
156                                         }
157                                 }
158                         }
159                 }
160         }
161
162         return subd;
163 }
164
165 static BLI_bitmap multires_mdisps_downsample_hidden(BLI_bitmap old_hidden,
166                                                                                                         int old_level,
167                                                                                                         int new_level)
168 {
169         BLI_bitmap new_hidden;
170         int new_gridsize = ccg_gridsize(new_level);
171         int old_gridsize = ccg_gridsize(old_level);
172         int x, y, factor, old_value;
173
174         BLI_assert(new_level <= old_level);
175         factor = ccg_factor(new_level, old_level);
176         new_hidden = BLI_BITMAP_NEW(new_gridsize * new_gridsize,
177                                                                 "downsample hidden");
178
179
180
181         for (y = 0; y < new_gridsize; y++) {
182                 for (x = 0; x < new_gridsize; x++) {
183                         old_value = BLI_BITMAP_GET(old_hidden,
184                                                                            factor*y*old_gridsize + x*factor);
185                         
186                         BLI_BITMAP_MODIFY(new_hidden, y*new_gridsize + x, old_value);
187                 }
188         }
189
190         return new_hidden;
191 }
192
193 static void multires_output_hidden_to_ccgdm(CCGDerivedMesh *ccgdm,
194                                                                                         Mesh *me, int level)
195 {
196         const MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
197         BLI_bitmap *grid_hidden = ccgdm->gridHidden;
198         int *gridOffset;
199         int i, j;
200         
201         gridOffset = ccgdm->dm.getGridOffset(&ccgdm->dm);
202
203         for (i = 0; i < me->totpoly; i++) {
204                 for (j = 0; j < me->mpoly[i].totloop; j++) {
205                         int g = gridOffset[i] + j;
206                         const MDisps *md = &mdisps[g];
207                         BLI_bitmap gh = md->hidden;
208                         
209                         if (gh) {
210                                 grid_hidden[g] =
211                                         multires_mdisps_downsample_hidden(gh, md->level, level);
212                         }
213                 }
214         }
215 }
216
217 /* subdivide mdisps.hidden if needed (assumes that md.level reflects
218  * the current level of md.hidden) */
219 static void multires_mdisps_subdivide_hidden(MDisps *md, int new_level)
220 {
221         BLI_bitmap subd;
222         
223         BLI_assert(md->hidden);
224
225         /* nothing to do if already subdivided enough */
226         if (md->level >= new_level)
227                 return;
228
229         subd = multires_mdisps_upsample_hidden(md->hidden,
230                                                                                    md->level,
231                                                                                    new_level,
232                                                                                    NULL);
233         
234         /* swap in the subdivided data */
235         MEM_freeN(md->hidden);
236         md->hidden = subd;
237 }
238
239 static MDisps *multires_mdisps_initialize_hidden(Mesh *me, int level)
240 {
241         MDisps *mdisps = CustomData_add_layer(&me->ldata, CD_MDISPS,
242                                                                                   CD_CALLOC, 0, me->totloop);
243         int gridsize = ccg_gridsize(level);
244         int gridarea = gridsize * gridsize;
245         int i, j, k;
246         
247         for (i = 0; i < me->totpoly; i++) {
248                 int hide = 0;
249
250                 for (j = 0; j < me->mpoly[i].totloop; j++) {
251                         if (me->mvert[me->mloop[me->mpoly[i].loopstart + j].v].flag & ME_HIDE) {
252                                 hide = 1;
253                                 break;
254                         }
255                 }
256
257                 if (!hide)
258                         continue;
259
260                 for (j = 0; j < me->mpoly[i].totloop; j++) {
261                         MDisps *md = &mdisps[me->mpoly[i].loopstart + j];
262
263                         BLI_assert(!md->hidden);
264
265                         md->hidden = BLI_BITMAP_NEW(gridarea, "MDisps.hidden initialize");
266
267                         for (k = 0; k < gridarea; k++)
268                                 BLI_BITMAP_SET(md->hidden, k);
269                 }
270         }
271
272         return mdisps;
273 }
274
275 DerivedMesh *get_multires_dm(Scene *scene, MultiresModifierData *mmd, Object *ob)
276 {
277         ModifierData *md= (ModifierData *)mmd;
278         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
279         DerivedMesh *tdm = mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
280         DerivedMesh *dm;
281
282         dm = mti->applyModifier(md, ob, tdm, 0, 1);
283         if (dm == tdm) {
284                 dm = CDDM_copy(tdm);
285         }
286
287         return dm;
288 }
289
290 MultiresModifierData *find_multires_modifier_before(Scene *scene, ModifierData *lastmd)
291 {
292         ModifierData *md;
293
294         for (md = lastmd; md; md = md->prev) {
295                 if (md->type == eModifierType_Multires) {
296                         if (modifier_isEnabled(scene, md, eModifierMode_Realtime))
297                                 return (MultiresModifierData*)md;
298                 }
299         }
300
301         return NULL;
302 }
303
304 /* used for applying scale on mdisps layer and syncing subdivide levels when joining objects
305  * use_first - return first multires modifier if all multires'es are disabled
306  */
307 MultiresModifierData *get_multires_modifier(Scene *scene, Object *ob, int use_first)
308 {
309         ModifierData *md;
310         MultiresModifierData *mmd= NULL, *firstmmd= NULL;
311
312         /* find first active multires modifier */
313         for (md = ob->modifiers.first; md; md = md->next) {
314                 if (md->type == eModifierType_Multires) {
315                         if (!firstmmd)
316                                 firstmmd= (MultiresModifierData*)md;
317
318                         if (modifier_isEnabled(scene, md, eModifierMode_Realtime)) {
319                                 mmd= (MultiresModifierData*)md;
320                                 break;
321                         }
322                 }
323         }
324
325         if (!mmd && use_first) {
326                 /* active multires have not been found
327                  * try to use first one */
328                 return firstmmd;
329         }
330
331         return mmd;
332 }
333
334 static int multires_get_level(Object *ob, MultiresModifierData *mmd, int render)
335 {
336         if (render)
337                 return (mmd->modifier.scene)? get_render_subsurf_level(&mmd->modifier.scene->r, mmd->renderlvl): mmd->renderlvl;
338         else if (ob->mode == OB_MODE_SCULPT)
339                 return mmd->sculptlvl;
340         else
341                 return (mmd->modifier.scene)? get_render_subsurf_level(&mmd->modifier.scene->r, mmd->lvl): mmd->lvl;
342 }
343
344 static void multires_set_tot_level(Object *ob, MultiresModifierData *mmd, int lvl)
345 {
346         mmd->totlvl = lvl;
347
348         if (ob->mode != OB_MODE_SCULPT)
349                 mmd->lvl = CLAMPIS(MAX2(mmd->lvl, lvl), 0, mmd->totlvl);
350
351         mmd->sculptlvl = CLAMPIS(MAX2(mmd->sculptlvl, lvl), 0, mmd->totlvl);
352         mmd->renderlvl = CLAMPIS(MAX2(mmd->renderlvl, lvl), 0, mmd->totlvl);
353 }
354
355 static void multires_dm_mark_as_modified(DerivedMesh *dm, MultiresModifiedFlags flags)
356 {
357         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)dm;
358         ccgdm->multires.modified_flags |= flags;
359 }
360
361 void multires_mark_as_modified(Object *ob, MultiresModifiedFlags flags)
362 {
363         if (ob && ob->derivedFinal)
364                 multires_dm_mark_as_modified(ob->derivedFinal, flags);
365 }
366
367 void multires_force_update(Object *ob)
368 {
369         if (ob) {
370                 if (ob->derivedFinal) {
371                         ob->derivedFinal->needsFree =1;
372                         ob->derivedFinal->release(ob->derivedFinal);
373                         ob->derivedFinal = NULL;
374                 }
375                 if (ob->sculpt && ob->sculpt->pbvh) {
376                         BLI_pbvh_free(ob->sculpt->pbvh);
377                         ob->sculpt->pbvh= NULL;
378                 }
379         }
380 }
381
382 void multires_force_external_reload(Object *ob)
383 {
384         Mesh *me = get_mesh(ob);
385
386         CustomData_external_reload(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
387         multires_force_update(ob);
388 }
389
390 void multires_force_render_update(Object *ob)
391 {
392         if (ob && (ob->mode & OB_MODE_SCULPT) && modifiers_findByType(ob, eModifierType_Multires))
393                 multires_force_update(ob);
394 }
395
396 int multiresModifier_reshapeFromDM(Scene *scene, MultiresModifierData *mmd,
397                                 Object *ob, DerivedMesh *srcdm)
398 {
399         DerivedMesh *mrdm = get_multires_dm (scene, mmd, ob);
400
401         if (mrdm && srcdm && mrdm->getNumVerts(mrdm) == srcdm->getNumVerts(srcdm)) {
402                 multires_mvert_to_ss(mrdm, srcdm->getVertArray(srcdm));
403
404                 multires_dm_mark_as_modified(mrdm, MULTIRES_COORDS_MODIFIED);
405                 multires_force_update(ob);
406
407                 mrdm->release(mrdm);
408
409                 return 1;
410         }
411
412         if (mrdm) mrdm->release(mrdm);
413
414         return 0;
415 }
416
417 /* Returns 1 on success, 0 if the src's totvert doesn't match */
418 int multiresModifier_reshape(Scene *scene, MultiresModifierData *mmd, Object *dst, Object *src)
419 {
420         DerivedMesh *srcdm = mesh_get_derived_final(scene, src, CD_MASK_BAREMESH);
421         return multiresModifier_reshapeFromDM(scene, mmd, dst, srcdm);
422 }
423
424 int multiresModifier_reshapeFromDeformMod(Scene *scene, MultiresModifierData *mmd,
425                                 Object *ob, ModifierData *md)
426 {
427         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
428         DerivedMesh *dm, *ndm;
429         int numVerts, result;
430         float (*deformedVerts)[3];
431
432         if (multires_get_level(ob, mmd, 0) == 0)
433                 return 0;
434
435         /* Create DerivedMesh for deformation modifier */
436         dm = get_multires_dm(scene, mmd, ob);
437         numVerts= dm->getNumVerts(dm);
438         deformedVerts= MEM_callocN(sizeof(float)*numVerts*3, "multiresReshape_deformVerts");
439
440         dm->getVertCos(dm, deformedVerts);
441         mti->deformVerts(md, ob, dm, deformedVerts, numVerts, 0, 0);
442
443         ndm= CDDM_copy(dm);
444         CDDM_apply_vert_coords(ndm, deformedVerts);
445
446         MEM_freeN(deformedVerts);
447         dm->release(dm);
448
449         /* Reshaping */
450         result= multiresModifier_reshapeFromDM(scene, mmd, ob, ndm);
451
452         /* Cleanup */
453         ndm->release(ndm);
454
455         return result;
456 }
457
458 /* reset the multires levels to match the number of mdisps */
459 static int get_levels_from_disps(Object *ob)
460 {
461         Mesh *me = ob->data;
462         MDisps *mdisp, *md;
463         int i, j, totlvl= 0;
464
465         mdisp = CustomData_get_layer(&me->ldata, CD_MDISPS);
466
467         for (i = 0; i < me->totpoly; ++i) {
468                 md = mdisp + me->mpoly[i].loopstart;
469
470                 for (j=0; j<me->mpoly[i].totloop; j++, md++) {
471                         if (md->totdisp == 0) continue;
472         
473                         while (1) {
474                                 int side = (1 << (totlvl-1)) + 1;
475                                 int lvl_totdisp = side*side;
476                                 if (md->totdisp == lvl_totdisp)
477                                         break;
478                                 else if (md->totdisp < lvl_totdisp)
479                                         --totlvl;
480                                 else
481                                         ++totlvl;
482         
483                         }
484                         
485                         break;
486                 }
487         }
488
489         return totlvl;
490 }
491
492 /* reset the multires levels to match the number of mdisps */
493 void multiresModifier_set_levels_from_disps(MultiresModifierData *mmd, Object *ob)
494 {
495         Mesh *me = ob->data;
496         MDisps *mdisp;
497
498         if (me->edit_btmesh)
499                 mdisp = CustomData_get_layer(&me->edit_btmesh->bm->ldata, CD_MDISPS);
500         else
501                 mdisp = CustomData_get_layer(&me->ldata, CD_MDISPS);
502
503         if (mdisp) {
504                 mmd->totlvl = get_levels_from_disps(ob);
505                 mmd->lvl = MIN2(mmd->sculptlvl, mmd->totlvl);
506                 mmd->sculptlvl = MIN2(mmd->sculptlvl, mmd->totlvl);
507                 mmd->renderlvl = MIN2(mmd->renderlvl, mmd->totlvl);
508         }
509 }
510
511 static void multires_set_tot_mdisps(Mesh *me, int lvl)
512 {
513         MDisps *mdisps= CustomData_get_layer(&me->ldata, CD_MDISPS);
514         int i;
515
516         if (mdisps) {
517                 for (i = 0; i < me->totloop; i++, mdisps++) {
518                         mdisps->totdisp = multires_grid_tot[lvl];
519                         mdisps->level = lvl;
520                 }
521         }
522 }
523
524 static void multires_reallocate_mdisps(int totloop, MDisps *mdisps, int lvl)
525 {
526         int i;
527
528         /* reallocate displacements to be filled in */
529         for (i = 0; i < totloop; ++i) {
530                 int totdisp = multires_grid_tot[lvl];
531                 float (*disps)[3] = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
532
533                 if (mdisps[i].disps)
534                         MEM_freeN(mdisps[i].disps);
535                 
536                 if (mdisps[i].level && mdisps[i].hidden)
537                         multires_mdisps_subdivide_hidden(&mdisps[i], lvl);
538
539                 mdisps[i].disps = disps;
540                 mdisps[i].totdisp = totdisp;
541                 mdisps[i].level = lvl;
542         }
543 }
544
545 static void column_vectors_to_mat3(float mat[][3], float v1[3], float v2[3], float v3[3])
546 {
547         copy_v3_v3(mat[0], v1);
548         copy_v3_v3(mat[1], v2);
549         copy_v3_v3(mat[2], v3);
550 }
551
552 static void multires_copy_grid(float (*gridA)[3], float (*gridB)[3], int sizeA, int sizeB)
553 {
554         int x, y, j, skip;
555
556         if (sizeA > sizeB) {
557                 skip = (sizeA-1)/(sizeB-1);
558
559                 for (j = 0, y = 0; y < sizeB; y++)
560                         for (x = 0; x < sizeB; x++, j++)
561                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip], gridB[j]);
562         }
563         else {
564                 skip = (sizeB-1)/(sizeA-1);
565
566                 for (j = 0, y = 0; y < sizeA; y++)
567                         for (x = 0; x < sizeA; x++, j++)
568                                 copy_v3_v3(gridA[j], gridB[y*skip*sizeB + x*skip]);
569         }
570 }
571
572 static void multires_copy_dm_grid(DMGridData *gridA, DMGridData *gridB, int sizeA, int sizeB)
573 {
574         int x, y, j, skip;
575
576         if (sizeA > sizeB) {
577                 skip = (sizeA-1)/(sizeB-1);
578
579                 for (j = 0, y = 0; y < sizeB; y++)
580                         for (x = 0; x < sizeB; x++, j++)
581                                 copy_v3_v3(gridA[y*skip*sizeA + x*skip].co, gridB[j].co);
582         }
583         else {
584                 skip = (sizeB-1)/(sizeA-1);
585
586                 for (j = 0, y = 0; y < sizeA; y++)
587                         for (x = 0; x < sizeA; x++, j++)
588                                 copy_v3_v3(gridA[j].co, gridB[y*skip*sizeB + x*skip].co);
589         }
590 }
591
592 static void multires_del_higher(MultiresModifierData *mmd, Object *ob, int lvl)
593 {
594         Mesh *me = (Mesh*)ob->data;
595         int levels = mmd->totlvl - lvl;
596         MDisps *mdisps;
597
598         multires_set_tot_mdisps(me, mmd->totlvl);
599         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
600         mdisps= CustomData_get_layer(&me->ldata, CD_MDISPS);
601
602         multires_force_update(ob);
603
604         if (mdisps && levels > 0) {
605                 if (lvl > 0) {
606                         /* MLoop *ml = me->mloop; */ /*UNUSED*/
607                         int nsize = multires_side_tot[lvl];
608                         int hsize = multires_side_tot[mmd->totlvl];
609                         int i, j;
610
611                         for (i = 0; i < me->totpoly; ++i) {
612                                 for (j=0; j<me->mpoly[i].totloop; j++) {
613                                         MDisps *mdisp= &mdisps[me->mpoly[i].loopstart+j];
614                                         float (*disps)[3], (*ndisps)[3], (*hdisps)[3];
615                                         int totdisp = multires_grid_tot[lvl];
616
617                                         disps = MEM_callocN(sizeof(float) * 3 * totdisp, "multires disps");
618
619                                         ndisps = disps;
620                                         hdisps = mdisp->disps;
621
622                                         multires_copy_grid(ndisps, hdisps, nsize, hsize);
623                                         if (mdisp->hidden) {
624                                                 BLI_bitmap gh =
625                                                         multires_mdisps_downsample_hidden(mdisp->hidden,
626                                                                                                                           mdisp->level,
627                                                                                                                           lvl);
628                                                 MEM_freeN(mdisp->hidden);
629                                                 mdisp->hidden = gh;
630                                         }
631
632                                         ndisps += nsize*nsize;
633                                         hdisps += hsize*hsize;
634
635                                         MEM_freeN(mdisp->disps);
636                                         mdisp->disps = disps;
637                                         mdisp->totdisp = totdisp;
638                                         mdisp->level = lvl;
639                                 }
640                         }
641                 }
642                 else {
643                         multires_customdata_delete(me);
644                 }
645         }
646
647         multires_set_tot_level(ob, mmd, lvl);
648 }
649
650 /* direction=1 for delete higher, direction=0 for lower (not implemented yet) */
651 void multiresModifier_del_levels(MultiresModifierData *mmd, Object *ob, int direction)
652 {
653         Mesh *me = get_mesh(ob);
654         int lvl = multires_get_level(ob, mmd, 0);
655         int levels = mmd->totlvl - lvl;
656         MDisps *mdisps;
657
658         multires_set_tot_mdisps(me, mmd->totlvl);
659         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
660         mdisps= CustomData_get_layer(&me->ldata, CD_MDISPS);
661
662         multires_force_update(ob);
663
664         if (mdisps && levels > 0 && direction == 1) {
665                 multires_del_higher(mmd, ob, lvl);
666         }
667
668         multires_set_tot_level(ob, mmd, lvl);
669 }
670
671 static DerivedMesh *multires_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int totlvl, int simple)
672 {
673         MultiresModifierData mmd= {{NULL}};
674
675         mmd.lvl = lvl;
676         mmd.sculptlvl = lvl;
677         mmd.renderlvl = lvl;
678         mmd.totlvl = totlvl;
679         mmd.simple = simple;
680
681         return multires_dm_create_from_derived(&mmd, 1, dm, ob, 0);
682 }
683
684 static DerivedMesh *subsurf_dm_create_local(Object *ob, DerivedMesh *dm, int lvl, int simple, int optimal, int plain_uv)
685 {
686         SubsurfModifierData smd= {{NULL}};
687
688         smd.levels = smd.renderLevels = lvl;
689         if (!plain_uv)
690                 smd.flags |= eSubsurfModifierFlag_SubsurfUv;
691         if (simple)
692                 smd.subdivType = ME_SIMPLE_SUBSURF;
693         if (optimal)
694                 smd.flags |= eSubsurfModifierFlag_ControlEdges;
695
696         return subsurf_make_derived_from_derived(dm, &smd, 0, NULL, 0, 0, (ob->mode & OB_MODE_EDIT));
697 }
698
699
700
701 /* assumes no is normalized; return value's sign is negative if v is on
702  * the other side of the plane */
703 static float v3_dist_from_plane(float v[3], float center[3], float no[3])
704 {
705         float s[3];
706         sub_v3_v3v3(s, v, center);
707         return dot_v3v3(s, no);
708 }
709
710 void multiresModifier_base_apply(MultiresModifierData *mmd, Object *ob)
711 {
712         DerivedMesh *cddm, *dispdm, *origdm;
713         Mesh *me;
714         const MeshElemMap *pmap;
715         float (*origco)[3];
716         int i, j, k, offset, totlvl;
717
718         multires_force_update(ob);
719
720         me = get_mesh(ob);
721         totlvl = mmd->totlvl;
722
723         /* nothing to do */
724         if (!totlvl)
725                 return;
726
727         /* XXX - probably not necessary to regenerate the cddm so much? */
728
729         /* generate highest level with displacements */
730         cddm = CDDM_from_mesh(me, NULL);
731         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
732         dispdm = multires_dm_create_local(ob, cddm, totlvl, totlvl, 0);
733         cddm->release(cddm);
734
735         /* copy the new locations of the base verts into the mesh */
736         offset = dispdm->getNumVerts(dispdm) - me->totvert;
737         for (i = 0; i < me->totvert; ++i) {
738                 dispdm->getVertCo(dispdm, offset + i, me->mvert[i].co);
739         }
740
741         /* heuristic to produce a better-fitting base mesh */
742
743         cddm = CDDM_from_mesh(me, NULL);
744         pmap = cddm->getPolyMap(ob, cddm);
745         origco = MEM_callocN(sizeof(float)*3*me->totvert, "multires apply base origco");
746         for (i = 0; i < me->totvert ;++i)
747                 copy_v3_v3(origco[i], me->mvert[i].co);
748
749         for (i = 0; i < me->totvert; ++i) {
750                 float avg_no[3] = {0, 0, 0}, center[3] = {0, 0, 0}, push[3];
751                 float dist;
752                 int tot = 0;
753
754                 /* don't adjust verts not used by at least one poly */
755                 if (!pmap[i].count)
756                         continue;
757
758                 /* find center */
759                 for (j = 0; j < pmap[i].count; j++) {
760                         const MPoly *p = &me->mpoly[pmap[i].indices[j]];
761                         
762                         /* this double counts, not sure if that's bad or good */
763                         for (k = 0; k < p->totloop; ++k) {
764                                 int vndx = me->mloop[p->loopstart + k].v;
765                                 if (vndx != i) {
766                                         add_v3_v3(center, origco[vndx]);
767                                         ++tot;
768                                 }
769                         }
770                 }
771                 mul_v3_fl(center, 1.0f / tot);
772
773                 /* find normal */
774                 for (j = 0; j < pmap[i].count; j++) {
775                         const MPoly *p = &me->mpoly[pmap[i].indices[j]];
776                         MPoly fake_poly;
777                         MLoop *fake_loops;
778                         float (*fake_co)[3];
779                         float no[3];
780
781                         /* set up poly, loops, and coords in order to call
782                          * mesh_calc_poly_normal_coords() */
783                         fake_poly.totloop = p->totloop;
784                         fake_poly.loopstart = 0;
785                         fake_loops = MEM_mallocN(sizeof(MLoop) * p->totloop, "fake_loops");
786                         fake_co = MEM_mallocN(sizeof(float) * 3 * p->totloop, "fake_co");
787                         
788                         for (k = 0; k < p->totloop; ++k) {
789                                 int vndx = me->mloop[p->loopstart + k].v;
790                                 
791                                 fake_loops[k].v = k;
792                                 
793                                 if (vndx == i)
794                                         copy_v3_v3(fake_co[k], center);
795                                 else
796                                         copy_v3_v3(fake_co[k], origco[vndx]);
797                         }
798                         
799                         mesh_calc_poly_normal_coords(&fake_poly, fake_loops,
800                                                                                  (const float(*)[3])fake_co, no);
801                         MEM_freeN(fake_loops);
802                         MEM_freeN(fake_co);
803
804                         add_v3_v3(avg_no, no);
805                 }
806                 normalize_v3(avg_no);
807
808                 /* push vertex away from the plane */
809                 dist = v3_dist_from_plane(me->mvert[i].co, center, avg_no);
810                 copy_v3_v3(push, avg_no);
811                 mul_v3_fl(push, dist);
812                 add_v3_v3(me->mvert[i].co, push);
813                 
814         }
815
816         MEM_freeN(origco);
817         cddm->release(cddm);
818
819         /* subdivide the mesh to highest level without displacements */
820         cddm = CDDM_from_mesh(me, NULL);
821         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
822         origdm = subsurf_dm_create_local(ob, cddm, totlvl, 0, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
823         cddm->release(cddm);
824
825         /* calc disps */
826         multiresModifier_disp_run(dispdm, me, NULL, CALC_DISPLACEMENTS, origdm->getGridData(origdm), totlvl);
827
828         origdm->release(origdm);
829         dispdm->release(dispdm);
830 }
831
832 static void multires_subdivide(MultiresModifierData *mmd, Object *ob, int totlvl, int updateblock, int simple)
833 {
834         Mesh *me = ob->data;
835         MDisps *mdisps;
836         int lvl= mmd->totlvl;
837
838         if ((totlvl > multires_max_levels) || (me->totpoly == 0))
839                 return;
840
841         multires_force_update(ob);
842
843         mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
844         if (!mdisps)
845                 mdisps = multires_mdisps_initialize_hidden(me, totlvl);
846
847         if (mdisps->disps && !updateblock && totlvl > 1) {
848                 /* upsample */
849                 DerivedMesh *lowdm, *cddm, *highdm;
850                 DMGridData **highGridData, **lowGridData, **subGridData;
851                 CCGSubSurf *ss;
852                 int i, numGrids, highGridSize, lowGridSize;
853
854                 /* create subsurf DM from original mesh at high level */
855                 cddm = CDDM_from_mesh(me, NULL);
856                 DM_set_only_copy(cddm, CD_MASK_BAREMESH);
857                 highdm = subsurf_dm_create_local(ob, cddm, totlvl, simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
858
859                 /* create multires DM from original mesh at low level */
860                 lowdm = multires_dm_create_local(ob, cddm, lvl, lvl, simple);
861                 cddm->release(cddm);
862
863                 /* copy subsurf grids and replace them with low displaced grids */
864                 numGrids = highdm->getNumGrids(highdm);
865                 highGridSize = highdm->getGridSize(highdm);
866                 highGridData = highdm->getGridData(highdm);
867                 lowGridSize = lowdm->getGridSize(lowdm);
868                 lowGridData = lowdm->getGridData(lowdm);
869
870                 subGridData = MEM_callocN(sizeof(float*)*numGrids, "subGridData*");
871
872                 for (i = 0; i < numGrids; ++i) {
873                         /* backup subsurf grids */
874                         subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
875                         memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
876
877                         /* overwrite with current displaced grids */
878                         multires_copy_dm_grid(highGridData[i], lowGridData[i], highGridSize, lowGridSize);
879                 }
880
881                 /* low lower level dm no longer needed at this point */
882                 lowdm->release(lowdm);
883
884                 /* subsurf higher levels again with displaced data */
885                 ss= ((CCGDerivedMesh*)highdm)->ss;
886                 ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
887                 ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
888
889                 /* reallocate displacements */
890                 multires_reallocate_mdisps(me->totloop, mdisps, totlvl); 
891
892                 /* compute displacements */
893                 multiresModifier_disp_run(highdm, me, NULL, CALC_DISPLACEMENTS, subGridData, totlvl);
894
895                 /* free */
896                 highdm->release(highdm);
897                 for (i = 0; i < numGrids; ++i)
898                         MEM_freeN(subGridData[i]);
899                 MEM_freeN(subGridData);
900         }
901         else {
902                 /* only reallocate, nothing to upsample */
903                 multires_reallocate_mdisps(me->totloop, mdisps, totlvl); 
904         }
905
906         multires_set_tot_level(ob, mmd, totlvl);
907 }
908
909 void multiresModifier_subdivide(MultiresModifierData *mmd, Object *ob, int updateblock, int simple)
910 {
911         multires_subdivide(mmd, ob, mmd->totlvl+1, updateblock, simple);
912 }
913
914 void grid_tangent(int gridSize, int index, int x, int y, int axis, DMGridData **gridData, float t[3])
915 {
916         if (axis == 0) {
917                 if (x == gridSize - 1) {
918                         if (y == gridSize - 1)
919                                 sub_v3_v3v3(t, gridData[index][x + gridSize*(y - 1)].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
920                         else
921                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x - 1 + gridSize*y].co);
922                 }
923                 else
924                         sub_v3_v3v3(t, gridData[index][x + 1 + gridSize*y].co, gridData[index][x + gridSize*y].co);
925         }
926         else if (axis == 1) {
927                 if (y == gridSize - 1) {
928                         if (x == gridSize - 1)
929                                 sub_v3_v3v3(t, gridData[index][x - 1 + gridSize*y].co, gridData[index][x - 1 + gridSize*(y - 1)].co);
930                         else
931                                 sub_v3_v3v3(t, gridData[index][x + gridSize*y].co, gridData[index][x + gridSize*(y - 1)].co);
932                 }
933                 else
934                         sub_v3_v3v3(t, gridData[index][x + gridSize*(y + 1)].co, gridData[index][x + gridSize*y].co);
935         }
936 }
937
938 static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, DerivedMesh *dm2, DispOp op, DMGridData **oldGridData, int totlvl)
939 {
940         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)dm;
941         DMGridData **gridData, **subGridData;
942         MPoly *mpoly = me->mpoly;
943         MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
944         int *gridOffset;
945         int i, k, /*numGrids, */ gridSize, dGridSize, dSkip;
946         int totloop, totpoly;
947         
948         /* this happens in the dm made by bmesh_mdisps_space_set */
949         if (dm2 && CustomData_has_layer(&dm2->loopData, CD_MDISPS)) {
950                 mpoly = CustomData_get_layer(&dm2->polyData, CD_MPOLY);
951                 mdisps = CustomData_get_layer(&dm2->loopData, CD_MDISPS);
952                 totloop = dm2->numLoopData;
953                 totpoly = dm2->numPolyData;
954         }
955         else {
956                 totloop = me->totloop;
957                 totpoly = me->totpoly;
958         }
959         
960         if (!mdisps) {
961                 if (op == CALC_DISPLACEMENTS)
962                         mdisps = CustomData_add_layer(&me->ldata, CD_MDISPS, CD_DEFAULT, NULL, me->totloop);
963                 else
964                         return;
965         }
966
967         /*numGrids = dm->getNumGrids(dm);*/ /*UNUSED*/
968         gridSize = dm->getGridSize(dm);
969         gridData = dm->getGridData(dm);
970         gridOffset = dm->getGridOffset(dm);
971         subGridData = (oldGridData)? oldGridData: gridData;
972
973         dGridSize = multires_side_tot[totlvl];
974         dSkip = (dGridSize-1)/(gridSize-1);
975
976         k = 0; /*current loop/mdisp index within the mloop array*/
977
978         #pragma omp parallel for private(i) if (totloop*gridSize*gridSize >= CCG_OMP_LIMIT)
979
980         for (i = 0; i < totpoly; ++i) {
981                 const int numVerts = mpoly[i].totloop;
982                 int S, x, y, gIndex = gridOffset[i];
983
984                 for (S = 0; S < numVerts; ++S, ++gIndex, ++k) {
985                         MDisps *mdisp = &mdisps[mpoly[i].loopstart+S];
986                         DMGridData *grid = gridData[gIndex];
987                         DMGridData *subgrid = subGridData[gIndex];
988                         float (*dispgrid)[3] = NULL;
989
990                         /* when adding new faces in edit mode, need to allocate disps */
991                         if (!mdisp->disps)
992                         #pragma omp critical
993                         {
994                                 multires_reallocate_mdisps(totloop, mdisps, totlvl);
995                         }
996
997                         dispgrid = mdisp->disps;
998
999                         for (y = 0; y < gridSize; y++) {
1000                                 for (x = 0; x < gridSize; x++) {
1001                                         float *co = grid[x + y*gridSize].co;
1002                                         float *sco = subgrid[x + y*gridSize].co;
1003                                         float *no = subgrid[x + y*gridSize].no;
1004                                         float *data = dispgrid[dGridSize*y*dSkip + x*dSkip];
1005                                         float mat[3][3], tx[3], ty[3], disp[3], d[3];
1006
1007                                         /* construct tangent space matrix */
1008                                         grid_tangent(gridSize, gIndex, x, y, 0, subGridData, tx);
1009                                         normalize_v3(tx);
1010
1011                                         grid_tangent(gridSize, gIndex, x, y, 1, subGridData, ty);
1012                                         normalize_v3(ty);
1013
1014                                         //mul_v3_fl(tx, 1.0f/(gridSize-1));
1015                                         //mul_v3_fl(ty, 1.0f/(gridSize-1));
1016                                         //cross_v3_v3v3(no, tx, ty);
1017
1018                                         column_vectors_to_mat3(mat, tx, ty, no);
1019
1020                                         switch (op) {
1021                                         case APPLY_DISPLACEMENTS:
1022                                                 /* Convert displacement to object space
1023                                                  * and add to grid points */
1024                                                 mul_v3_m3v3(disp, mat, data);
1025                                                 add_v3_v3v3(co, sco, disp);
1026                                                 break;
1027                                         case CALC_DISPLACEMENTS:
1028                                                 /* Calculate displacement between new and old
1029                                                  * grid points and convert to tangent space */
1030                                                 sub_v3_v3v3(disp, co, sco);
1031                                                 invert_m3(mat);
1032                                                 mul_v3_m3v3(data, mat, disp);
1033                                                 break;
1034                                         case ADD_DISPLACEMENTS:
1035                                                 /* Convert subdivided displacements to tangent
1036                                                  * space and add to the original displacements */
1037                                                 invert_m3(mat);
1038                                                 mul_v3_m3v3(d, mat, co);
1039                                                 add_v3_v3(data, d);
1040                                                 break;
1041                                         }
1042                                 }
1043                         }
1044                 }
1045         }
1046
1047         if (op == APPLY_DISPLACEMENTS) {
1048                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, NULL, 0);
1049                 ccgSubSurf_updateNormals(ccgdm->ss, NULL, 0);
1050         }
1051 }
1052
1053 void multires_modifier_update_mdisps(struct DerivedMesh *dm)
1054 {
1055         CCGDerivedMesh *ccgdm= (CCGDerivedMesh*)dm;
1056         Object *ob;
1057         Mesh *me;
1058         MDisps *mdisps;
1059         MultiresModifierData *mmd;
1060
1061         ob = ccgdm->multires.ob;
1062         me = ccgdm->multires.ob->data;
1063         mmd = ccgdm->multires.mmd;
1064         multires_set_tot_mdisps(me, mmd->totlvl);
1065         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
1066         mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
1067
1068         if (mdisps) {
1069                 int lvl = ccgdm->multires.lvl;
1070                 int totlvl = ccgdm->multires.totlvl;
1071                 
1072                 if (lvl < totlvl) {
1073                         Mesh *me = ob->data;
1074                         DerivedMesh *lowdm, *cddm, *highdm;
1075                         DMGridData **highGridData, **lowGridData, **subGridData, **gridData, *diffGrid;
1076                         CCGSubSurf *ss;
1077                         int i, j, numGrids, highGridSize, lowGridSize;
1078
1079                         /* create subsurf DM from original mesh at high level */
1080                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
1081                         else cddm = CDDM_from_mesh(me, NULL);
1082                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
1083
1084                         highdm = subsurf_dm_create_local(ob, cddm, totlvl, mmd->simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
1085
1086                         /* create multires DM from original mesh and displacements */
1087                         lowdm = multires_dm_create_local(ob, cddm, lvl, totlvl, mmd->simple);
1088                         cddm->release(cddm);
1089
1090                         /* gather grid data */
1091                         numGrids = highdm->getNumGrids(highdm);
1092                         highGridSize = highdm->getGridSize(highdm);
1093                         highGridData = highdm->getGridData(highdm);
1094                         lowGridSize = lowdm->getGridSize(lowdm);
1095                         lowGridData = lowdm->getGridData(lowdm);
1096                         gridData = dm->getGridData(dm);
1097
1098                         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
1099                         diffGrid = MEM_callocN(sizeof(DMGridData)*lowGridSize*lowGridSize, "diff");
1100
1101                         for (i = 0; i < numGrids; ++i) {
1102                                 /* backup subsurf grids */
1103                                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*highGridSize*highGridSize, "subGridData");
1104                                 memcpy(subGridData[i], highGridData[i], sizeof(DMGridData)*highGridSize*highGridSize);
1105
1106                                 /* write difference of subsurf and displaced low level into high subsurf */
1107                                 for (j = 0; j < lowGridSize*lowGridSize; ++j)
1108                                         sub_v3_v3v3(diffGrid[j].co, gridData[i][j].co, lowGridData[i][j].co);
1109
1110                                 multires_copy_dm_grid(highGridData[i], diffGrid, highGridSize, lowGridSize);
1111                         }
1112
1113                         /* lower level dm no longer needed at this point */
1114                         MEM_freeN(diffGrid);
1115                         lowdm->release(lowdm);
1116
1117                         /* subsurf higher levels again with difference of coordinates */
1118                         ss= ((CCGDerivedMesh*)highdm)->ss;
1119                         ccgSubSurf_updateFromFaces(ss, lvl, NULL, 0);
1120                         ccgSubSurf_updateLevels(ss, lvl, NULL, 0);
1121
1122                         /* add to displacements */
1123                         multiresModifier_disp_run(highdm, me, NULL, ADD_DISPLACEMENTS, subGridData, mmd->totlvl);
1124
1125                         /* free */
1126                         highdm->release(highdm);
1127                         for (i = 0; i < numGrids; ++i)
1128                                 MEM_freeN(subGridData[i]);
1129                         MEM_freeN(subGridData);
1130                 }
1131                 else {
1132                         DerivedMesh *cddm, *subdm;
1133
1134                         if (ob->derivedDeform) cddm = CDDM_copy(ob->derivedDeform);
1135                         else cddm = CDDM_from_mesh(me, NULL);
1136                         DM_set_only_copy(cddm, CD_MASK_BAREMESH);
1137
1138                         subdm = subsurf_dm_create_local(ob, cddm, mmd->totlvl, mmd->simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
1139                         cddm->release(cddm);
1140
1141                         multiresModifier_disp_run(dm, me, NULL, CALC_DISPLACEMENTS, subdm->getGridData(subdm), mmd->totlvl);
1142
1143                         subdm->release(subdm);
1144                 }
1145         }
1146 }
1147
1148 void multires_modifier_update_hidden(DerivedMesh *dm)
1149 {
1150         CCGDerivedMesh *ccgdm= (CCGDerivedMesh*)dm;
1151         BLI_bitmap *grid_hidden= ccgdm->gridHidden;
1152         Mesh *me = ccgdm->multires.ob->data;
1153         MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS);
1154         int totlvl = ccgdm->multires.totlvl;
1155         int lvl = ccgdm->multires.lvl;
1156
1157         if (mdisps) {
1158                 int i;
1159                 
1160                 for (i = 0; i < me->totloop; i++) {
1161                         MDisps *md = &mdisps[i];
1162                         BLI_bitmap gh = grid_hidden[i];
1163
1164                         if (!gh && md->hidden) {
1165                                 MEM_freeN(md->hidden);
1166                                 md->hidden = NULL;
1167                         }
1168                         else if (gh) {
1169                                 gh = multires_mdisps_upsample_hidden(gh, lvl, totlvl,
1170                                                                                                                          md->hidden);
1171                                 if (md->hidden)
1172                                         MEM_freeN(md->hidden);
1173                                 
1174                                 md->hidden = gh;
1175                         }
1176                 }
1177         }
1178 }
1179
1180 void multires_set_space(DerivedMesh *dm, Object *ob, int from, int to)
1181 {
1182         DerivedMesh *ccgdm = NULL, *subsurf = NULL;
1183         DMGridData **gridData, **subGridData=NULL;
1184         MPoly *mpoly = CustomData_get_layer(&dm->polyData, CD_MPOLY);
1185         MDisps *mdisps;
1186         MultiresModifierData *mmd = get_multires_modifier(NULL, ob, 1);
1187         int *gridOffset, totlvl;
1188         int i, k, numGrids, gridSize, dGridSize, dSkip;
1189         
1190         if (!mmd)
1191                 return;
1192         
1193         mdisps = CustomData_get_layer(&dm->loopData, CD_MDISPS);
1194
1195         if (!mdisps) {
1196                 goto cleanup;
1197         }
1198
1199         totlvl = mmd->totlvl;
1200         ccgdm = multires_dm_create_local(ob, dm, totlvl, totlvl, mmd->simple);
1201         
1202         subsurf = subsurf_dm_create_local(ob, dm, totlvl,
1203                 mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges, mmd->flags & eMultiresModifierFlag_PlainUv);
1204
1205         numGrids = subsurf->getNumGrids(subsurf);
1206         gridSize = subsurf->getGridSize(subsurf);
1207         gridData = subsurf->getGridData(subsurf);
1208
1209         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
1210
1211         for (i = 0; i < numGrids; i++) {
1212                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*gridSize*gridSize, "subGridData");
1213                 memcpy(subGridData[i], gridData[i], sizeof(DMGridData)*gridSize*gridSize);
1214         }
1215         
1216         /*numGrids = ccgdm->dm->getNumGrids((DerivedMesh*)ccgdm);*/ /*UNUSED*/
1217         gridSize = ccgdm->getGridSize((DerivedMesh*)ccgdm);
1218         gridData = ccgdm->getGridData((DerivedMesh*)ccgdm);
1219         gridOffset = ccgdm->getGridOffset((DerivedMesh*)ccgdm);
1220
1221         dGridSize = multires_side_tot[totlvl];
1222         dSkip = (dGridSize-1)/(gridSize-1);
1223
1224         k = 0; /*current loop/mdisp index within the mloop array*/
1225
1226         //#pragma omp parallel for private(i) if (dm->numLoopData*gridSize*gridSize >= CCG_OMP_LIMIT)
1227
1228         for (i = 0; i < dm->numPolyData; ++i) {
1229                 const int numVerts = mpoly[i].totloop;
1230                 int S, x, y, gIndex = gridOffset[i];
1231                                                 
1232                 for (S = 0; S < numVerts; ++S, ++gIndex, ++k) {
1233                         MDisps *mdisp = &mdisps[mpoly[i].loopstart+S];
1234                         /* DMGridData *grid = gridData[gIndex]; */ /* UNUSED */
1235                         DMGridData *subgrid = subGridData[gIndex];
1236                         float (*dispgrid)[3] = NULL;
1237
1238                         /* when adding new faces in edit mode, need to allocate disps */
1239                         if (!mdisp->disps) {
1240                                 mdisp->totdisp = gridSize*gridSize;
1241                                 mdisp->level = totlvl;
1242                                 mdisp->disps = MEM_callocN(sizeof(float)*3*mdisp->totdisp, "disp in multires_set_space");
1243                         }
1244
1245                         dispgrid = mdisp->disps;
1246
1247                         for (y = 0; y < gridSize; y++) {
1248                                 for (x = 0; x < gridSize; x++) {
1249                                         float *data = dispgrid[dGridSize*y*dSkip + x*dSkip];
1250                                         float *no = subgrid[x + y*gridSize].no;
1251                                         float *co = subgrid[x + y*gridSize].co;
1252                                         float mat[3][3], tx[3], ty[3], dco[3];
1253                                         
1254                                         /* construct tangent space matrix */
1255                                         grid_tangent(gridSize, gIndex, x, y, 0, subGridData, tx);
1256                                         normalize_v3(tx);
1257
1258                                         grid_tangent(gridSize, gIndex, x, y, 1, subGridData, ty);
1259                                         normalize_v3(ty);
1260                                         column_vectors_to_mat3(mat, tx, ty, no);
1261
1262                                         /* convert to absolute coordinates in space */
1263                                         if (from == MULTIRES_SPACE_TANGENT) {
1264                                                 mul_v3_m3v3(dco, mat, data);
1265                                                 add_v3_v3(dco, co);
1266                                         }
1267                                         else if (from == MULTIRES_SPACE_OBJECT) {
1268                                                 add_v3_v3v3(dco, co, data);
1269                                         }
1270                                         else if (from == MULTIRES_SPACE_ABSOLUTE) {
1271                                                 copy_v3_v3(dco, data);
1272                                         }
1273                                         
1274                                         column_vectors_to_mat3(mat, tx, ty, no);
1275
1276                                         /*now, convert to desired displacement type*/
1277                                         if (to == MULTIRES_SPACE_TANGENT) {
1278                                                 invert_m3(mat);
1279
1280                                                 sub_v3_v3(dco, co);
1281                                                 mul_v3_m3v3(data, mat, dco);
1282                                         }
1283                                         else if (to == MULTIRES_SPACE_OBJECT) {
1284                                                 sub_v3_v3(dco, co);
1285                                                 mul_v3_m3v3(data, mat, dco);
1286                                         }
1287                                         else if (to == MULTIRES_SPACE_ABSOLUTE) {
1288                                                 copy_v3_v3(data, dco);
1289                                         }
1290                                 }
1291                         }
1292                 }
1293         }
1294
1295 cleanup:
1296         if (subsurf) {
1297                 subsurf->needsFree = 1;
1298                 subsurf->release(subsurf);
1299         }
1300
1301         if (ccgdm) {
1302                 ccgdm->needsFree = 1;
1303                 ccgdm->release(ccgdm);
1304         }
1305 }
1306
1307 void multires_stitch_grids(Object *ob)
1308 {
1309         /* utility for smooth brush */
1310         if (ob && ob->derivedFinal) {
1311                 CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)ob->derivedFinal;
1312                 CCGFace **faces;
1313                 int totface;
1314
1315                 if (ccgdm->pbvh) {
1316                         BLI_pbvh_get_grid_updates(ccgdm->pbvh, 0, (void***)&faces, &totface);
1317
1318                         if (totface) {
1319                                 ccgSubSurf_stitchFaces(ccgdm->ss, 0, faces, totface);
1320                                 MEM_freeN(faces);
1321                         }
1322                 }
1323         }
1324 }
1325
1326 DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd,
1327                                                                                          int local_mmd, DerivedMesh *dm,
1328                                                                                          Object *ob, int useRenderParams)
1329 {
1330         Mesh *me= ob->data;
1331         DerivedMesh *result;
1332         CCGDerivedMesh *ccgdm = NULL;
1333         DMGridData **gridData, **subGridData;
1334         int lvl= multires_get_level(ob, mmd, useRenderParams);
1335         int i, gridSize, numGrids;
1336
1337         if (lvl == 0)
1338                 return dm;
1339
1340         result = subsurf_dm_create_local(ob, dm, lvl,
1341                 mmd->simple, mmd->flags & eMultiresModifierFlag_ControlEdges,
1342                 mmd->flags & eMultiresModifierFlag_PlainUv);
1343
1344         if (!local_mmd) {
1345                 ccgdm = (CCGDerivedMesh*)result;
1346
1347                 ccgdm->multires.ob = ob;
1348                 ccgdm->multires.mmd = mmd;
1349                 ccgdm->multires.local_mmd = local_mmd;
1350                 ccgdm->multires.lvl = lvl;
1351                 ccgdm->multires.totlvl = mmd->totlvl;
1352                 ccgdm->multires.modified_flags = 0;
1353         }
1354
1355         numGrids = result->getNumGrids(result);
1356         gridSize = result->getGridSize(result);
1357         gridData = result->getGridData(result);
1358
1359         subGridData = MEM_callocN(sizeof(DMGridData*)*numGrids, "subGridData*");
1360
1361         for (i = 0; i < numGrids; i++) {
1362                 subGridData[i] = MEM_callocN(sizeof(DMGridData)*gridSize*gridSize, "subGridData");
1363                 memcpy(subGridData[i], gridData[i], sizeof(DMGridData)*gridSize*gridSize);
1364         }
1365
1366         multires_set_tot_mdisps(me, mmd->totlvl);
1367         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
1368
1369         /*run displacement*/
1370         multiresModifier_disp_run(result, ob->data, dm, APPLY_DISPLACEMENTS, subGridData, mmd->totlvl);
1371
1372         /* copy hidden elements for this level */
1373         if (ccgdm)
1374                 multires_output_hidden_to_ccgdm(ccgdm, me, lvl);
1375
1376         for (i = 0; i < numGrids; i++)
1377                 MEM_freeN(subGridData[i]);
1378         MEM_freeN(subGridData);
1379
1380         return result;
1381 }
1382
1383 /**** Old Multires code ****
1384  ***************************/
1385
1386 /* Adapted from sculptmode.c */
1387 void old_mdisps_bilinear(float out[3], float (*disps)[3], const int st, float u, float v)
1388 {
1389         int x, y, x2, y2;
1390         const int st_max = st - 1;
1391         float urat, vrat, uopp;
1392         float d[4][3], d2[2][3];
1393         
1394         if (!disps || isnan(u) || isnan(v))
1395                 return;
1396                         
1397         if (u < 0)
1398                 u = 0;
1399         else if (u >= st)
1400                 u = st_max;
1401         if (v < 0)
1402                 v = 0;
1403         else if (v >= st)
1404                 v = st_max;
1405
1406         x = floor(u);
1407         y = floor(v);
1408         x2 = x + 1;
1409         y2 = y + 1;
1410
1411         if (x2 >= st) x2 = st_max;
1412         if (y2 >= st) y2 = st_max;
1413         
1414         urat = u - x;
1415         vrat = v - y;
1416         uopp = 1 - urat;
1417
1418         mul_v3_v3fl(d[0], disps[y * st + x], uopp);
1419         mul_v3_v3fl(d[1], disps[y * st + x2], urat);
1420         mul_v3_v3fl(d[2], disps[y2 * st + x], uopp);
1421         mul_v3_v3fl(d[3], disps[y2 * st + x2], urat);
1422
1423         add_v3_v3v3(d2[0], d[0], d[1]);
1424         add_v3_v3v3(d2[1], d[2], d[3]);
1425         mul_v3_fl(d2[0], 1 - vrat);
1426         mul_v3_fl(d2[1], vrat);
1427
1428         add_v3_v3v3(out, d2[0], d2[1]);
1429 }
1430
1431 static void old_mdisps_rotate(int S, int UNUSED(newside), int oldside, int x, int y, float *u, float *v)
1432 {
1433         float offset = oldside*0.5f - 0.5f;
1434
1435         if (S == 1) { *u= offset + x; *v = offset - y; }
1436         if (S == 2) { *u= offset + y; *v = offset + x; }
1437         if (S == 3) { *u= offset - x; *v = offset + y; }
1438         if (S == 0) { *u= offset - y; *v = offset - x; }
1439 }
1440
1441 static void old_mdisps_convert(MFace *mface, MDisps *mdisp)
1442 {
1443         int newlvl = log(sqrt(mdisp->totdisp)-1)/M_LN2;
1444         int oldlvl = newlvl+1;
1445         int oldside = multires_side_tot[oldlvl];
1446         int newside = multires_side_tot[newlvl];
1447         int nvert = (mface->v4)? 4: 3;
1448         int newtotdisp = multires_grid_tot[newlvl]*nvert;
1449         int x, y, S;
1450         float (*disps)[3], (*out)[3], u = 0.0f, v = 0.0f; /* Quite gcc barking. */
1451
1452         disps = MEM_callocN(sizeof(float) * 3 * newtotdisp, "multires disps");
1453
1454         out = disps;
1455         for (S = 0; S < nvert; S++) {
1456                 for (y = 0; y < newside; ++y) {
1457                         for (x = 0; x < newside; ++x, ++out) {
1458                                 old_mdisps_rotate(S, newside, oldside, x, y, &u, &v);
1459                                 old_mdisps_bilinear(*out, mdisp->disps, oldside, u, v);
1460
1461                                 if (S == 1) { (*out)[1]= -(*out)[1]; }
1462                                 else if (S == 2) { SWAP(float, (*out)[0], (*out)[1]); }
1463                                 else if (S == 3) { (*out)[0]= -(*out)[0]; }
1464                                 else if (S == 0) { SWAP(float, (*out)[0], (*out)[1]); (*out)[0]= -(*out)[0]; (*out)[1]= -(*out)[1]; };
1465                         }
1466                 }
1467         }
1468
1469         MEM_freeN(mdisp->disps);
1470
1471         mdisp->totdisp= newtotdisp;
1472         mdisp->level= newlvl;
1473         mdisp->disps= disps;
1474 }
1475
1476 void multires_load_old_250(Mesh *me)
1477 {
1478         MDisps *mdisps, *mdisps2;
1479         MFace *mf;
1480         int i, j, k;
1481
1482         mdisps= CustomData_get_layer(&me->fdata, CD_MDISPS);
1483
1484         if (mdisps) {
1485                 for (i=0; i<me->totface; i++)
1486                         if (mdisps[i].totdisp)
1487                                 old_mdisps_convert(&me->mface[i], &mdisps[i]);
1488                 
1489                 CustomData_add_layer(&me->ldata, CD_MDISPS, CD_CALLOC, NULL, me->totloop);
1490                 mdisps2 = CustomData_get_layer(&me->ldata, CD_MDISPS);
1491
1492                 k = 0;
1493                 mf = me->mface;
1494                 for (i=0; i<me->totface; i++, mf++) {
1495                         int nvert = mf->v4 ? 4 : 3;
1496                         int totdisp = mdisps[i].totdisp / nvert;
1497                         
1498                         for (j=0; j < mf->v4 ? 4 : 3; j++, k++) {
1499                                 mdisps2[k].disps = MEM_callocN(sizeof(float)*3*totdisp, "multires disp in conversion");                 
1500                                 mdisps2[k].totdisp = totdisp;
1501                                 mdisps2[k].level = mdisps[i].level;
1502                                 memcpy(mdisps2[k].disps, mdisps[i].disps + totdisp*j, totdisp);
1503                         }
1504
1505                 }
1506         }
1507 }
1508
1509 /* Does not actually free lvl itself */
1510 static void multires_free_level(MultiresLevel *lvl)
1511 {
1512         if (lvl) {
1513                 if (lvl->faces) MEM_freeN(lvl->faces);
1514                 if (lvl->edges) MEM_freeN(lvl->edges);
1515                 if (lvl->colfaces) MEM_freeN(lvl->colfaces);
1516         }
1517 }
1518
1519 void multires_free(Multires *mr)
1520 {
1521         if (mr) {
1522                 MultiresLevel* lvl= mr->levels.first;
1523
1524                 /* Free the first-level data */
1525                 if (lvl) {
1526                         CustomData_free(&mr->vdata, lvl->totvert);
1527                         CustomData_free(&mr->fdata, lvl->totface);
1528                         if (mr->edge_flags)
1529                                 MEM_freeN(mr->edge_flags);
1530                         if (mr->edge_creases)
1531                                 MEM_freeN(mr->edge_creases);
1532                 }
1533
1534                 while (lvl) {
1535                         multires_free_level(lvl);                       
1536                         lvl= lvl->next;
1537                 }
1538
1539                 MEM_freeN(mr->verts);
1540
1541                 BLI_freelistN(&mr->levels);
1542
1543                 MEM_freeN(mr);
1544         }
1545 }
1546
1547 static void create_old_vert_face_map(ListBase **map, IndexNode **mem, const MultiresFace *mface,
1548                                      const int totvert, const int totface)
1549 {
1550         int i, j;
1551         IndexNode *node = NULL;
1552         
1553         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert face map");
1554         (*mem) = MEM_callocN(sizeof(IndexNode) * totface*4, "vert face map mem");
1555         node = *mem;
1556         
1557         /* Find the users */
1558         for (i = 0; i < totface; ++i) {
1559                 for (j = 0; j < (mface[i].v[3]?4:3); ++j, ++node) {
1560                         node->index = i;
1561                         BLI_addtail(&(*map)[mface[i].v[j]], node);
1562                 }
1563         }
1564 }
1565
1566 static void create_old_vert_edge_map(ListBase **map, IndexNode **mem, const MultiresEdge *medge,
1567                                          const int totvert, const int totedge)
1568 {
1569         int i, j;
1570         IndexNode *node = NULL;
1571         
1572         (*map) = MEM_callocN(sizeof(ListBase) * totvert, "vert edge map");
1573         (*mem) = MEM_callocN(sizeof(IndexNode) * totedge*2, "vert edge map mem");
1574         node = *mem;
1575         
1576         /* Find the users */
1577         for (i = 0; i < totedge; ++i) {
1578                 for (j = 0; j < 2; ++j, ++node) {
1579                         node->index = i;
1580                         BLI_addtail(&(*map)[medge[i].v[j]], node);
1581                 }
1582         }
1583 }
1584
1585 static MultiresFace *find_old_face(ListBase *map, MultiresFace *faces, int v1, int v2, int v3, int v4)
1586 {
1587         IndexNode *n1;
1588         int v[4], i, j;
1589
1590         v[0]= v1;
1591         v[1]= v2;
1592         v[2]= v3;
1593         v[3]= v4;
1594
1595         for (n1 = map[v1].first; n1; n1 = n1->next) {
1596                 int fnd[4] = {0, 0, 0, 0};
1597
1598                 for (i = 0; i < 4; ++i) {
1599                         for (j = 0; j < 4; ++j) {
1600                                 if (v[i] == faces[n1->index].v[j])
1601                                         fnd[i] = 1;
1602                         }
1603                 }
1604
1605                 if (fnd[0] && fnd[1] && fnd[2] && fnd[3])
1606                         return &faces[n1->index];
1607         }
1608
1609         return NULL;
1610 }
1611
1612 static MultiresEdge *find_old_edge(ListBase *map, MultiresEdge *edges, int v1, int v2)
1613 {
1614         IndexNode *n1, *n2;
1615
1616         for (n1 = map[v1].first; n1; n1 = n1->next) {
1617                 for (n2 = map[v2].first; n2; n2 = n2->next) {
1618                         if (n1->index == n2->index)
1619                                 return &edges[n1->index];
1620                 }
1621         }
1622
1623         return NULL;
1624 }
1625
1626 static void multires_load_old_edges(ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst, int v1, int v2, int mov)
1627 {
1628         int emid = find_old_edge(emap[2], lvl->edges, v1, v2)->mid;
1629         vvmap[dst + mov] = emid;
1630
1631         if (lvl->next->next) {
1632                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v1, emid, mov / 2);
1633                 multires_load_old_edges(emap + 1, lvl->next, vvmap, dst + mov, v2, emid, -mov / 2);
1634         }
1635 }
1636
1637 static void multires_load_old_faces(ListBase **fmap, ListBase **emap, MultiresLevel *lvl, int *vvmap, int dst,
1638                                         int v1, int v2, int v3, int v4, int st2, int st3)
1639 {
1640         int fmid;
1641         int emid13, emid14, emid23, emid24;
1642
1643         if (lvl && lvl->next) {
1644                 fmid = find_old_face(fmap[1], lvl->faces, v1, v2, v3, v4)->mid;
1645                 vvmap[dst] = fmid;
1646
1647                 emid13 = find_old_edge(emap[1], lvl->edges, v1, v3)->mid;
1648                 emid14 = find_old_edge(emap[1], lvl->edges, v1, v4)->mid;
1649                 emid23 = find_old_edge(emap[1], lvl->edges, v2, v3)->mid;
1650                 emid24 = find_old_edge(emap[1], lvl->edges, v2, v4)->mid;
1651
1652
1653                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 + st3,
1654                                         fmid, v2, emid23, emid24, st2, st3 / 2);
1655
1656                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 + st3,
1657                                         emid14, emid24, fmid, v4, st2, st3 / 2);
1658
1659                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst + st2 * st3 - st3,
1660                                         emid13, emid23, v3, fmid, st2, st3 / 2);
1661
1662                 multires_load_old_faces(fmap + 1, emap + 1, lvl->next, vvmap, dst - st2 * st3 - st3,
1663                                         v1, fmid, emid13, emid14, st2, st3 / 2);
1664
1665                 if (lvl->next->next) {
1666                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid24, fmid, st3);
1667                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid13, fmid, -st3);
1668                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid14, fmid, -st2 * st3);
1669                         multires_load_old_edges(emap, lvl->next, vvmap, dst, emid23, fmid, st2 * st3);
1670                 }
1671         }
1672 }
1673
1674 static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert)
1675 {
1676         CCGDerivedMesh *ccgdm = (CCGDerivedMesh*) dm;
1677         CCGSubSurf *ss = ccgdm->ss;
1678         DMGridData *vd;
1679         int index;
1680         int totvert, totedge, totface;
1681         int gridSize = ccgSubSurf_getGridSize(ss);
1682         int edgeSize = ccgSubSurf_getEdgeSize(ss);
1683         int i = 0;
1684
1685         totface = ccgSubSurf_getNumFaces(ss);
1686         for (index = 0; index < totface; index++) {
1687                 CCGFace *f = ccgdm->faceMap[index].face;
1688                 int x, y, S, numVerts = ccgSubSurf_getFaceNumVerts(f);
1689
1690                 vd= ccgSubSurf_getFaceCenterData(f);
1691                 copy_v3_v3(vd->co, mvert[i].co);
1692                 i++;
1693                 
1694                 for (S = 0; S < numVerts; S++) {
1695                         for (x = 1; x < gridSize - 1; x++, i++) {
1696                                 vd= ccgSubSurf_getFaceGridEdgeData(ss, f, S, x);
1697                                 copy_v3_v3(vd->co, mvert[i].co);
1698                         }
1699                 }
1700
1701                 for (S = 0; S < numVerts; S++) {
1702                         for (y = 1; y < gridSize - 1; y++) {
1703                                 for (x = 1; x < gridSize - 1; x++, i++) {
1704                                         vd= ccgSubSurf_getFaceGridData(ss, f, S, x, y);
1705                                         copy_v3_v3(vd->co, mvert[i].co);
1706                                 }
1707                         }
1708                 }
1709         }
1710
1711         totedge = ccgSubSurf_getNumEdges(ss);
1712         for (index = 0; index < totedge; index++) {
1713                 CCGEdge *e = ccgdm->edgeMap[index].edge;
1714                 int x;
1715
1716                 for (x = 1; x < edgeSize - 1; x++, i++) {
1717                         vd= ccgSubSurf_getEdgeData(ss, e, x);
1718                         copy_v3_v3(vd->co, mvert[i].co);
1719                 }
1720         }
1721
1722         totvert = ccgSubSurf_getNumVerts(ss);
1723         for (index = 0; index < totvert; index++) {
1724                 CCGVert *v = ccgdm->vertMap[index].vert;
1725
1726                 vd= ccgSubSurf_getVertData(ss, v);
1727                 copy_v3_v3(vd->co, mvert[i].co);
1728                 i++;
1729         }
1730
1731         ccgSubSurf_updateToFaces(ss, 0, NULL, 0);
1732 }
1733
1734 /* Loads a multires object stored in the old Multires struct into the new format */
1735 static void multires_load_old_dm(DerivedMesh *dm, Mesh *me, int totlvl)
1736 {
1737         MultiresLevel *lvl, *lvl1;
1738         Multires *mr= me->mr;
1739         MVert *vsrc, *vdst;
1740         unsigned int src, dst;
1741         int st = multires_side_tot[totlvl - 1] - 1;
1742         int extedgelen = multires_side_tot[totlvl] - 2;
1743         int *vvmap; // inorder for dst, map to src
1744         int crossedgelen;
1745         int s, x, tottri, totquad;
1746         unsigned int i, j, totvert;
1747
1748         src = 0;
1749         vsrc = mr->verts;
1750         vdst = dm->getVertArray(dm);
1751         totvert = (unsigned int)dm->getNumVerts(dm);
1752         vvmap = MEM_callocN(sizeof(int) * totvert, "multires vvmap");
1753
1754         lvl1 = mr->levels.first;
1755         /* Load base verts */
1756         for (i = 0; i < lvl1->totvert; ++i) {
1757                 vvmap[totvert - lvl1->totvert + i] = src;
1758                 ++src;
1759         }
1760
1761         /* Original edges */
1762         dst = totvert - lvl1->totvert - extedgelen * lvl1->totedge;
1763         for (i = 0; i < lvl1->totedge; ++i) {
1764                 int ldst = dst + extedgelen * i;
1765                 int lsrc = src;
1766                 lvl = lvl1->next;
1767
1768                 for (j = 2; j <= mr->level_count; ++j) {
1769                         int base = multires_side_tot[totlvl - j + 1] - 2;
1770                         int skip = multires_side_tot[totlvl - j + 2] - 1;
1771                         int st = multires_side_tot[j - 1] - 1;
1772
1773                         for (x = 0; x < st; ++x)
1774                                 vvmap[ldst + base + x * skip] = lsrc + st * i + x;
1775
1776                         lsrc += lvl->totvert - lvl->prev->totvert;
1777                         lvl = lvl->next;
1778                 }
1779         }
1780
1781         /* Center points */
1782         dst = 0;
1783         for (i = 0; i < lvl1->totface; ++i) {
1784                 int sides = lvl1->faces[i].v[3] ? 4 : 3;
1785
1786                 vvmap[dst] = src + lvl1->totedge + i;
1787                 dst += 1 + sides * (st - 1) * st;
1788         }
1789
1790
1791         /* The rest is only for level 3 and up */
1792         if (lvl1->next && lvl1->next->next) {
1793                 ListBase **fmap, **emap;
1794                 IndexNode **fmem, **emem;
1795
1796                 /* Face edge cross */
1797                 tottri = totquad = 0;
1798                 crossedgelen = multires_side_tot[totlvl - 1] - 2;
1799                 dst = 0;
1800                 for (i = 0; i < lvl1->totface; ++i) {
1801                         int sides = lvl1->faces[i].v[3] ? 4 : 3;
1802
1803                         lvl = lvl1->next->next;
1804                         ++dst;
1805
1806                         for (j = 3; j <= mr->level_count; ++j) {
1807                                 int base = multires_side_tot[totlvl - j + 1] - 2;
1808                                 int skip = multires_side_tot[totlvl - j + 2] - 1;
1809                                 int st = pow(2, j - 2);
1810                                 int st2 = pow(2, j - 3);
1811                                 int lsrc = lvl->prev->totvert;
1812
1813                                 /* Skip exterior edge verts */
1814                                 lsrc += lvl1->totedge * st;
1815
1816                                 /* Skip earlier face edge crosses */
1817                                 lsrc += st2 * (tottri * 3 + totquad * 4);
1818
1819                                 for (s = 0; s < sides; ++s) {
1820                                         for (x = 0; x < st2; ++x) {
1821                                                 vvmap[dst + crossedgelen * (s + 1) - base - x * skip - 1] = lsrc;
1822                                                 ++lsrc;
1823                                         }
1824                                 }
1825
1826                                 lvl = lvl->next;
1827                         }
1828
1829                         dst += sides * (st - 1) * st;
1830
1831                         if (sides == 4) ++totquad;
1832                         else ++tottri;
1833
1834                 }
1835
1836                 /* calculate vert to edge/face maps for each level (except the last) */
1837                 fmap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires fmap");
1838                 emap = MEM_callocN(sizeof(ListBase*) * (mr->level_count-1), "multires emap");
1839                 fmem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires fmem");
1840                 emem = MEM_callocN(sizeof(IndexNode*) * (mr->level_count-1), "multires emem");
1841                 lvl = lvl1;
1842                 for (i = 0; i < (unsigned int)mr->level_count - 1; ++i) {
1843                         create_old_vert_face_map(fmap + i, fmem + i, lvl->faces, lvl->totvert, lvl->totface);
1844                         create_old_vert_edge_map(emap + i, emem + i, lvl->edges, lvl->totvert, lvl->totedge);
1845                         lvl = lvl->next;
1846                 }
1847
1848                 /* Interior face verts */
1849                 /* lvl = lvl1->next->next; */ /* UNUSED */
1850                 dst = 0;
1851                 for (j = 0; j < lvl1->totface; ++j) {
1852                         int sides = lvl1->faces[j].v[3] ? 4 : 3;
1853                         int ldst = dst + 1 + sides * (st - 1);
1854
1855                         for (s = 0; s < sides; ++s) {
1856                                 int st2 = multires_side_tot[totlvl - 1] - 2;
1857                                 int st3 = multires_side_tot[totlvl - 2] - 2;
1858                                 int st4 = st3 == 0 ? 1 : (st3 + 1) / 2;
1859                                 int mid = ldst + st2 * st3 + st3;
1860                                 int cv = lvl1->faces[j].v[s];
1861                                 int nv = lvl1->faces[j].v[s == sides - 1 ? 0 : s + 1];
1862                                 int pv = lvl1->faces[j].v[s == 0 ? sides - 1 : s - 1];
1863
1864                                 multires_load_old_faces(fmap, emap, lvl1->next, vvmap, mid,
1865                                                         vvmap[dst], cv,
1866                                                         find_old_edge(emap[0], lvl1->edges, pv, cv)->mid,
1867                                                         find_old_edge(emap[0], lvl1->edges, cv, nv)->mid,
1868                                                         st2, st4);
1869
1870                                 ldst += (st - 1) * (st - 1);
1871                         }
1872
1873
1874                         dst = ldst;
1875                 }
1876
1877                 /*lvl = lvl->next;*/ /*UNUSED*/
1878
1879                 for (i = 0; i < (unsigned int)(mr->level_count - 1); ++i) {
1880                         MEM_freeN(fmap[i]);
1881                         MEM_freeN(fmem[i]);
1882                         MEM_freeN(emap[i]);
1883                         MEM_freeN(emem[i]);
1884                 }
1885
1886                 MEM_freeN(fmap);
1887                 MEM_freeN(emap);
1888                 MEM_freeN(fmem);
1889                 MEM_freeN(emem);
1890         }
1891
1892         /* Transfer verts */
1893         for (i = 0; i < totvert; ++i)
1894                 copy_v3_v3(vdst[i].co, vsrc[vvmap[i]].co);
1895
1896         MEM_freeN(vvmap);
1897
1898         multires_mvert_to_ss(dm, vdst);
1899 }
1900
1901 /* Copy the first-level vcol data to the mesh, if it exists */
1902 /* Warning: higher-level vcol data will be lost */
1903 static void multires_load_old_vcols(Mesh *me)
1904 {
1905         MultiresLevel *lvl;
1906         MultiresColFace *colface;
1907         MCol *mcol;
1908         int i, j;
1909
1910         if (!(lvl = me->mr->levels.first))
1911                 return;
1912
1913         if (!(colface = lvl->colfaces))
1914                 return;
1915
1916         /* older multires format never supported multiple vcol layers,
1917          * so we can assume the active vcol layer is the correct one */
1918         if (!(mcol = CustomData_get_layer(&me->fdata, CD_MCOL)))
1919                 return;
1920         
1921         for (i = 0; i < me->totface; ++i) {
1922                 for (j = 0; j < 4; ++j) {
1923                         mcol[i*4 + j].a = colface[i].col[j].a;
1924                         mcol[i*4 + j].r = colface[i].col[j].r;
1925                         mcol[i*4 + j].g = colface[i].col[j].g;
1926                         mcol[i*4 + j].b = colface[i].col[j].b;
1927                 }
1928         }
1929 }
1930
1931 /* Copy the first-level face-flag data to the mesh */
1932 static void multires_load_old_face_flags(Mesh *me)
1933 {
1934         MultiresLevel *lvl;
1935         MultiresFace *faces;
1936         int i;
1937
1938         if (!(lvl = me->mr->levels.first))
1939                 return;
1940
1941         if (!(faces = lvl->faces))
1942                 return;
1943
1944         for (i = 0; i < me->totface; ++i)
1945                 me->mface[i].flag = faces[i].flag;
1946 }
1947
1948 void multires_load_old(Object *ob, Mesh *me)
1949 {
1950         MultiresLevel *lvl;
1951         ModifierData *md;
1952         MultiresModifierData *mmd;
1953         DerivedMesh *dm, *orig;
1954         CustomDataLayer *l;
1955         int i;
1956
1957         /* Load original level into the mesh */
1958         lvl = me->mr->levels.first;
1959         CustomData_free_layers(&me->vdata, CD_MVERT, lvl->totvert);
1960         CustomData_free_layers(&me->edata, CD_MEDGE, lvl->totedge);
1961         CustomData_free_layers(&me->fdata, CD_MFACE, lvl->totface);
1962         me->totvert = lvl->totvert;
1963         me->totedge = lvl->totedge;
1964         me->totface = lvl->totface;
1965         me->mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
1966         me->medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
1967         me->mface = CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
1968         memcpy(me->mvert, me->mr->verts, sizeof(MVert) * me->totvert);
1969         for (i = 0; i < me->totedge; ++i) {
1970                 me->medge[i].v1 = lvl->edges[i].v[0];
1971                 me->medge[i].v2 = lvl->edges[i].v[1];
1972         }
1973         for (i = 0; i < me->totface; ++i) {
1974                 me->mface[i].v1 = lvl->faces[i].v[0];
1975                 me->mface[i].v2 = lvl->faces[i].v[1];
1976                 me->mface[i].v3 = lvl->faces[i].v[2];
1977                 me->mface[i].v4 = lvl->faces[i].v[3];
1978                 me->mface[i].mat_nr = lvl->faces[i].mat_nr;
1979         }
1980
1981         /* Add a multires modifier to the object */
1982         md = ob->modifiers.first;
1983         while (md && modifierType_getInfo(md->type)->type == eModifierTypeType_OnlyDeform)
1984                 md = md->next;                          
1985         mmd = (MultiresModifierData*)modifier_new(eModifierType_Multires);
1986         BLI_insertlinkbefore(&ob->modifiers, md, mmd);
1987
1988         for (i = 0; i < me->mr->level_count - 1; ++i)
1989                 multiresModifier_subdivide(mmd, ob, 1, 0);
1990
1991         mmd->lvl = mmd->totlvl;
1992         orig = CDDM_from_mesh(me, NULL);
1993         dm = multires_dm_create_from_derived(mmd, 0, orig, ob, 0);
1994                                            
1995         multires_load_old_dm(dm, me, mmd->totlvl+1);
1996
1997         multires_dm_mark_as_modified(dm, MULTIRES_COORDS_MODIFIED);
1998         dm->release(dm);
1999         orig->release(orig);
2000
2001         /* Copy the first-level data to the mesh */
2002         for (i = 0, l = me->mr->vdata.layers; i < me->mr->vdata.totlayer; ++i, ++l)
2003                 CustomData_add_layer(&me->vdata, l->type, CD_REFERENCE, l->data, me->totvert);
2004         for (i = 0, l = me->mr->fdata.layers; i < me->mr->fdata.totlayer; ++i, ++l)
2005                 CustomData_add_layer(&me->fdata, l->type, CD_REFERENCE, l->data, me->totface);
2006         memset(&me->mr->vdata, 0, sizeof(CustomData));
2007         memset(&me->mr->fdata, 0, sizeof(CustomData));
2008
2009         multires_load_old_vcols(me);
2010         multires_load_old_face_flags(me);
2011
2012         /* Remove the old multires */
2013         multires_free(me->mr);
2014         me->mr= NULL;
2015 }
2016
2017 static void multires_sync_levels(Scene *scene, Object *ob, Object *to_ob)
2018 {
2019         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
2020         MultiresModifierData *to_mmd= get_multires_modifier(scene, to_ob, 1);
2021
2022         if (!mmd) {
2023                 /* object could have MDISP even when there is no multires modifier
2024                  * this could lead to troubles due to i've got no idea how mdisp could be
2025                  * upsampled correct without modifier data.
2026                  * just remove mdisps if no multires present (nazgul) */
2027
2028                 multires_customdata_delete(ob->data);
2029         }
2030
2031         if (!mmd || !to_mmd) return;
2032
2033         if (mmd->totlvl>to_mmd->totlvl) multires_del_higher(mmd, ob, to_mmd->totlvl);
2034         else multires_subdivide(mmd, ob, to_mmd->totlvl, 0, mmd->simple);
2035 }
2036
2037 static void multires_apply_smat(Scene *scene, Object *ob, float smat[3][3])
2038 {
2039         DerivedMesh *dm= NULL, *cddm= NULL, *subdm= NULL;
2040         DMGridData **gridData, **subGridData;
2041         Mesh *me= (Mesh*)ob->data;
2042         MPoly *mpoly= me->mpoly;
2043         /* MLoop *mloop = me->mloop; */ /* UNUSED */
2044         MDisps *mdisps;
2045         int *gridOffset;
2046         int i, /*numGrids, */ gridSize, dGridSize, dSkip, totvert;
2047         float (*vertCos)[3] = NULL;
2048         MultiresModifierData *mmd= get_multires_modifier(scene, ob, 1);
2049         MultiresModifierData high_mmd;
2050
2051         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totloop);
2052         mdisps= CustomData_get_layer(&me->ldata, CD_MDISPS);
2053
2054         if (!mdisps || !mmd || !mmd->totlvl) return;
2055
2056         /* we need derived mesh created from highest resolution */
2057         high_mmd= *mmd;
2058         high_mmd.lvl= high_mmd.totlvl;
2059
2060         /* unscaled multires with applied displacement */
2061         subdm= get_multires_dm(scene, &high_mmd, ob);
2062
2063         /* prepare scaled CDDM to create ccgDN */
2064         cddm= mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
2065
2066         totvert= cddm->getNumVerts(cddm);
2067         vertCos= MEM_mallocN(sizeof(*vertCos) * totvert, "multiresScale vertCos");
2068         cddm->getVertCos(cddm, vertCos);
2069         for (i=0; i<totvert; i++)
2070                 mul_m3_v3(smat, vertCos[i]);
2071         CDDM_apply_vert_coords(cddm, vertCos);
2072         MEM_freeN(vertCos);
2073
2074         /* scaled ccgDM for tangent space of object with applied scale */
2075         dm= subsurf_dm_create_local(ob, cddm, high_mmd.totlvl, high_mmd.simple, 0, mmd->flags & eMultiresModifierFlag_PlainUv);
2076         cddm->release(cddm);
2077
2078         /*numGrids= dm->getNumGrids(dm);*/ /*UNUSED*/
2079         gridSize= dm->getGridSize(dm);
2080         gridData= dm->getGridData(dm);
2081         gridOffset= dm->getGridOffset(dm);
2082         subGridData= subdm->getGridData(subdm);
2083
2084         dGridSize= multires_side_tot[high_mmd.totlvl];
2085         dSkip= (dGridSize-1)/(gridSize-1);
2086
2087         #pragma omp parallel for private(i) if (me->totface*gridSize*gridSize*4 >= CCG_OMP_LIMIT)
2088         for (i = 0; i < me->totpoly; ++i) {
2089                 const int numVerts= mpoly[i].totloop;
2090                 MDisps *mdisp= &mdisps[mpoly[i].loopstart];
2091                 int S, x, y, gIndex = gridOffset[i];
2092
2093                 for (S = 0; S < numVerts; ++S, ++gIndex, mdisp++) {
2094                         DMGridData *grid= gridData[gIndex];
2095                         DMGridData *subgrid= subGridData[gIndex];
2096                         float (*dispgrid)[3]= mdisp->disps;
2097
2098                         for (y = 0; y < gridSize; y++) {
2099                                 for (x = 0; x < gridSize; x++) {
2100                                         float *co= grid[x + y*gridSize].co;
2101                                         float *sco= subgrid[x + y*gridSize].co;
2102                                         float *no= grid[x + y*gridSize].no;
2103                                         float *data= dispgrid[dGridSize*y*dSkip + x*dSkip];
2104                                         float mat[3][3], tx[3], ty[3], disp[3];
2105
2106                                         /* construct tangent space matrix */
2107                                         grid_tangent(gridSize, gIndex, x, y, 0, gridData, tx);
2108                                         normalize_v3(tx);
2109
2110                                         grid_tangent(gridSize, gIndex, x, y, 1, gridData, ty);
2111                                         normalize_v3(ty);
2112
2113                                         column_vectors_to_mat3(mat, tx, ty, no);
2114
2115                                         /* scale subgrid coord and calculate displacement */
2116                                         mul_m3_v3(smat, sco);
2117                                         sub_v3_v3v3(disp, sco, co);
2118
2119                                         /* convert difference to tangent space */
2120                                         invert_m3(mat);
2121                                         mul_v3_m3v3(data, mat, disp);
2122                                 }
2123                         }
2124                 }
2125         }
2126
2127         dm->release(dm);
2128         subdm->release(subdm);
2129 }
2130
2131 int multires_mdisp_corners(MDisps *s)
2132 {
2133         int lvl= 13;
2134
2135         while (lvl > 0) {
2136                 int side = (1 << (lvl-1)) + 1;
2137                 if ((s->totdisp % (side*side)) == 0) return s->totdisp / (side*side);
2138                 lvl--;
2139         }
2140
2141         return 0;
2142 }
2143
2144 void multiresModifier_scale_disp(Scene *scene, Object *ob)
2145 {
2146         float smat[3][3];
2147
2148         /* object's scale matrix */
2149         BKE_object_scale_to_mat3(ob, smat);
2150
2151         multires_apply_smat(scene, ob, smat);
2152 }
2153
2154 void multiresModifier_prepare_join(Scene *scene, Object *ob, Object *to_ob)
2155 {
2156         float smat[3][3], tmat[3][3], mat[3][3];
2157         multires_sync_levels(scene, ob, to_ob);
2158
2159         /* construct scale matrix for displacement */
2160         BKE_object_scale_to_mat3(to_ob, tmat);
2161         invert_m3(tmat);
2162         BKE_object_scale_to_mat3(ob, smat);
2163         mul_m3_m3m3(mat, smat, tmat);
2164
2165         multires_apply_smat(scene, ob, mat);
2166 }
2167
2168 /* update multires data after topology changing */
2169 void multires_topology_changed(Mesh *me)
2170 {
2171         MDisps *mdisp = NULL, *cur = NULL;
2172         int i, grid = 0;
2173
2174         CustomData_external_read(&me->ldata, &me->id, CD_MASK_MDISPS, me->totface);
2175         mdisp = CustomData_get_layer(&me->ldata, CD_MDISPS);
2176
2177         if (!mdisp)
2178                 return;
2179
2180         cur = mdisp;
2181         for (i = 0; i < me->totloop; i++, cur++) {
2182                 if (cur->totdisp) {
2183                         grid = mdisp->totdisp;
2184
2185                         break;
2186                 }
2187         }
2188
2189         for (i = 0; i < me->totloop; i++, mdisp++) {
2190                 /* allocate memory for mdisp, the whole disp layer would be erased otherwise */
2191                 if (!mdisp->totdisp || !mdisp->disps) {
2192                         if (grid) {
2193                                 mdisp->totdisp = grid;
2194                                 mdisp->disps = MEM_callocN(3 * mdisp->totdisp * sizeof(float), "mdisp topology");
2195                         }
2196
2197                         continue;
2198                 }
2199         }
2200 }
2201
2202 /***************** Multires interpolation stuff *****************/
2203
2204 /* Find per-corner coordinate with given per-face UV coord */
2205 int mdisp_rot_face_to_crn(const int corners, const int face_side, const float u, const float v, float *x, float *y)
2206 {
2207         const float offset = face_side*0.5f - 0.5f;
2208         int S = 0;
2209
2210         if (corners == 4) {
2211                 if (u <= offset && v <= offset) S = 0;
2212                 else if (u > offset  && v <= offset) S = 1;
2213                 else if (u > offset  && v > offset) S = 2;
2214                 else if (u <= offset && v >= offset)  S = 3;
2215
2216                 if (S == 0) {
2217                         *y = offset - u;
2218                         *x = offset - v;
2219                 }
2220                 else if (S == 1) {
2221                         *x = u - offset;
2222                         *y = offset - v;
2223                 }
2224                 else if (S == 2) {
2225                         *y = u - offset;
2226                         *x = v - offset;
2227                 }
2228                 else if (S == 3) {
2229                         *x= offset - u;
2230                         *y = v - offset;
2231                 }
2232         }
2233         else {
2234                 int grid_size = offset;
2235                 float w = (face_side - 1) - u - v;
2236                 float W1, W2;
2237
2238                 if (u >= v && u >= w) {S = 0; W1= w; W2= v;}
2239                 else if (v >= u && v >= w) {S = 1; W1 = u; W2 = w;}
2240                 else {S = 2; W1 = v; W2 = u;}
2241
2242                 W1 /= (face_side-1);
2243                 W2 /= (face_side-1);
2244
2245                 *x = (1-(2*W1)/(1-W2)) * grid_size;
2246                 *y = (1-(2*W2)/(1-W1)) * grid_size;
2247         }
2248
2249         return S;
2250 }