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