= Multires =
[blender.git] / source / blender / src / multires.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software  Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2006 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  * Implements the multiresolution modeling tools.
30  *
31  * multires.h
32  *
33  */
34
35 #include "MEM_guardedalloc.h"
36
37 #include "BLI_blenlib.h"
38 #include "BLI_arithb.h"
39
40 #include "DNA_key_types.h"
41 #include "DNA_mesh_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_modifier_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_scene_types.h"
46 #include "DNA_vec_types.h"
47 #include "DNA_view3d_types.h"
48
49 #include "BKE_customdata.h"
50 #include "BKE_depsgraph.h"
51 #include "BKE_global.h"
52 #include "BKE_key.h"
53 #include "BKE_mesh.h"
54 #include "BKE_modifier.h"
55
56 #include "BIF_editmesh.h"
57 #include "BIF_screen.h"
58 #include "BIF_space.h"
59 #include "BIF_toolbox.h"
60
61 #include "BDR_editobject.h"
62 #include "BDR_sculptmode.h"
63
64 #include "BLI_editVert.h"
65
66 #include "BSE_edit.h"
67 #include "BSE_view.h"
68
69 #include "IMB_imbuf.h"
70 #include "IMB_imbuf_types.h"
71
72 #include "blendef.h"
73 #include "editmesh.h"
74 #include "multires.h"
75 #include "mydevice.h"
76 #include "parametrizer.h"
77
78 #include <math.h>
79
80 const CustomDataMask vdata_mask= CD_MASK_MDEFORMVERT;
81
82 int multires_test()
83 {
84         Mesh *me= get_mesh(OBACT);
85         if(me && me->mr) {
86                 error("Unable to complete action with multires enabled.");
87                 return 1;
88         }
89         return 0;
90 }
91 int multires_level1_test()
92 {
93         Mesh *me= get_mesh(OBACT);
94         if(me && me->mr && me->mr->current != 1) {
95                 error("Operation only available for multires level 1.");
96                 return 1;
97         }
98         return 0;
99 }
100
101 /* Sculptmode */
102
103 void multires_check_state()
104 {
105         if(G.f & G_SCULPTMODE && !G.obedit)
106                 sculptmode_correct_state();
107 }
108
109 void multires_undo_push(char *str)
110 {
111         if(G.f & G_SCULPTMODE && !G.obedit)
112                 sculptmode_undo_push(str, SUNDO_VERT | SUNDO_TOPO | SUNDO_PVIS | SUNDO_MRES);
113         else
114                 BIF_undo_push(str);
115 }
116
117 typedef struct MultiresMapNode {
118         struct MultiresMapNode *next, *prev;
119         unsigned Index;
120 } MultiresMapNode;
121
122 MultiresLevel *current_level(Multires *mr)
123 {
124         return BLI_findlink(&mr->levels, mr->current - 1);
125 }
126
127 MultiresLevel *multires_level_n(Multires *mr, int n)
128 {
129         if(mr)
130                 return BLI_findlink(&mr->levels, n - 1);
131         else
132                 return NULL;
133 }
134
135 void Vec3fAvg3(float *out, float *v1, float *v2, float *v3)
136 {
137         out[0]= (v1[0]+v2[0]+v3[0])/3;
138         out[1]= (v1[1]+v2[1]+v3[1])/3;
139         out[2]= (v1[2]+v2[2]+v3[2])/3;
140 }
141 void Vec3fAvg4(float *out, float *v1, float *v2, float *v3, float *v4)
142 {
143         out[0]= (v1[0]+v2[0]+v3[0]+v4[0])/4;
144         out[1]= (v1[1]+v2[1]+v3[1]+v4[1])/4;
145         out[2]= (v1[2]+v2[2]+v3[2]+v4[2])/4;
146 }
147
148 short multires_edge_is_boundary(MultiresLevel *lvl, unsigned e)
149 {
150         MultiresMapNode *n1= lvl->vert_face_map[lvl->edges[e].v[0]].first;
151         unsigned total= 0;
152
153         while(n1) {
154                 MultiresMapNode *n2= lvl->vert_face_map[lvl->edges[e].v[1]].first;
155                 while(n2) {
156                         if(n1->Index == n2->Index) {
157                                 ++total;
158
159                                 if(total > 1)
160                                         return 0;
161                         }
162
163                         n2= n2->next;
164                 }
165                 n1= n1->next;
166         }
167
168         return 1;
169 }
170
171 short multires_vert_is_boundary(MultiresLevel *lvl, unsigned v)
172 {
173         MultiresMapNode *node= lvl->vert_edge_map[v].first;
174         while(node) {
175                 if(multires_edge_is_boundary(lvl,node->Index))
176                         return 1;
177                 node= node->next;
178         }
179         return 0;
180 }
181
182 typedef struct FloatNode {
183         struct FloatNode *next, *prev;
184         float value;
185 } FloatNode;
186 typedef struct FloatArrayNode {
187         struct FloatArrayNode *next, *prev;
188         float *value;
189 } FloatArrayNode;
190
191 typedef struct MultiApplyData {
192         /* Smooth faces */
193         float *corner1, *corner2, *corner3, *corner4;
194         char quad;
195
196         /* Smooth edges */
197         char boundary;
198         float edge_face_neighbor_midpoints_accum[3];
199         unsigned edge_face_neighbor_midpoints_total;
200         float *endpoint1, *endpoint2;
201
202         /* Smooth verts */
203         /* uses 'char boundary' */
204         float *original;
205         int edge_count;
206         float vert_face_neighbor_midpoints_average[3];
207         float vert_edge_neighbor_midpoints_average[3];
208         float boundary_edges_average[3];
209 } MultiApplyData;
210
211 /* CATMULL-CLARK
212    ============= */
213
214 /* Simply averages the four corners of a polygon. */
215 float catmullclark_smooth_face(MultiApplyData *data, const unsigned i)
216 {
217         const float total= data->corner1[i]+data->corner2[i]+data->corner3[i];
218         return data->quad ? (total+data->corner4[i])/4 : total/3;
219 }
220
221 float catmullclark_smooth_edge(MultiApplyData *data, const unsigned i)
222 {
223         float accum= 0;
224         unsigned count= 2;
225
226         accum+= data->endpoint1[i] + data->endpoint2[i];
227
228         if(!data->boundary) {
229                 accum+= data->edge_face_neighbor_midpoints_accum[i];
230                 count+= data->edge_face_neighbor_midpoints_total;
231         }
232
233         return accum / count;
234 }
235 float catmullclark_smooth_vert(MultiApplyData *data, const unsigned i)
236 {
237         if(data->boundary) {
238                 return data->original[i]*0.75 + data->boundary_edges_average[i]*0.25;
239         } else {
240                 return (data->vert_face_neighbor_midpoints_average[i] +
241                         2*data->vert_edge_neighbor_midpoints_average[i] +
242                         data->original[i]*(data->edge_count-3))/data->edge_count;
243         }
244 }
245
246
247
248 /* Call func count times, passing in[i] as the input and storing the output in out[i] */
249 void multi_apply(float *out, MultiApplyData *data,
250                  const unsigned count, float (*func)(MultiApplyData *, const unsigned))
251 {
252         unsigned i;
253         for(i=0; i<count; ++i)
254                 out[i]= func(data,i);
255 }
256
257 float get_float(void *array, const unsigned i, const unsigned j, const char stride)
258 {
259         return ((float*)((char*)array+(i*stride)))[j];
260 }
261
262 void edge_face_neighbor_midpoints_accum(MultiApplyData *data, MultiresLevel *lvl,
263                                         void *array, const char stride, const MultiresEdge *e)
264 {
265         ListBase *neighbors1= &lvl->vert_face_map[e->v[0]];
266         ListBase *neighbors2= &lvl->vert_face_map[e->v[1]];
267         MultiresMapNode *n1, *n2;
268         unsigned j,count= 0;
269         float *out= data->edge_face_neighbor_midpoints_accum;
270         
271         out[0]=out[1]=out[2]= 0;
272
273         for(n1= neighbors1->first; n1; n1= n1->next) {
274                 for(n2= neighbors2->first; n2; n2= n2->next) {
275                         if(n1->Index == n2->Index) {
276                                 for(j=0; j<3; ++j)
277                                         out[j]+= get_float(array,lvl->faces[n1->Index].mid,j,stride);
278                                 ++count;
279                         }
280                 }
281         }
282
283         data->edge_face_neighbor_midpoints_total= count;
284 }
285 void vert_face_neighbor_midpoints_average(MultiApplyData *data, MultiresLevel *lvl,
286                                           void *array, const char stride, const unsigned i)
287 {
288         ListBase *neighbors= &lvl->vert_face_map[i];
289         MultiresMapNode *n1;
290         unsigned j,count= 0;
291         float *out= data->vert_face_neighbor_midpoints_average;
292
293         out[0]=out[1]=out[2]= 0;
294
295         for(n1= neighbors->first; n1; n1= n1->next) {
296                 for(j=0; j<3; ++j)
297                         out[j]+= get_float(array,lvl->faces[n1->Index].mid,j,stride);
298                 ++count;
299         }
300         for(j=0; j<3; ++j) out[j]/= count;
301 }
302 void vert_edge_neighbor_midpoints_average(MultiApplyData *data, MultiresLevel *lvl,
303                                           void *array, const char stride, const unsigned i)
304 {
305         ListBase *neighbors= &lvl->vert_edge_map[i];
306         MultiresMapNode *n1;
307         unsigned j,count= 0;
308         float *out= data->vert_edge_neighbor_midpoints_average;
309
310         out[0]=out[1]=out[2]= 0;
311
312         for(n1= neighbors->first; n1; n1= n1->next) {
313                 for(j=0; j<3; ++j)
314                         out[j]+= (get_float(array,lvl->edges[n1->Index].v[0],j,stride) +
315                                   get_float(array,lvl->edges[n1->Index].v[1],j,stride)) / 2;
316                 ++count;
317         }
318         for(j=0; j<3; ++j) out[j]/= count;
319 }
320 void boundary_edges_average(MultiApplyData *data, MultiresLevel *lvl,
321                             void *array, const char stride, const unsigned i)
322 {
323         ListBase *neighbors= &lvl->vert_edge_map[i];
324         MultiresMapNode *n1;
325         unsigned j,count= 0;
326         float *out= data->boundary_edges_average;
327
328         out[0]=out[1]=out[2]= 0;
329         
330         for(n1= neighbors->first; n1; n1= n1->next) {
331                 const MultiresEdge *e= &lvl->edges[n1->Index];
332                 const unsigned end= e->v[0]==i ? e->v[1] : e->v[0];
333                 
334                 if(multires_edge_is_boundary(lvl,n1->Index)) {
335                         for(j=0; j<3; ++j)
336                                 out[j]+= get_float(array,end,j,stride);
337                         ++count;
338                 }
339         }
340         for(j=0; j<3; ++j) out[j]/= count;
341 }
342
343 /* For manipulating vertex colors / uvs */
344 void mcol_to_multires(MultiresColFace *mrf, MCol *mcol)
345 {
346         char i;
347         for(i=0; i<4; ++i) {
348                 mrf->col[i].a= mcol[i].a;
349                 mrf->col[i].r= mcol[i].r;
350                 mrf->col[i].g= mcol[i].g;
351                 mrf->col[i].b= mcol[i].b;
352         }
353 }
354
355 float clamp_component(const float c)
356 {
357         if(c<0) return 0;
358         else if(c>255) return 255;
359         else return c;
360 }
361
362 void multires_to_mcol(MultiresColFace *f, MCol mcol[4])
363 {
364         unsigned char j;
365         for(j=0; j<4; ++j) {
366                 mcol->a= clamp_component(f->col[j].a);
367                 mcol->r= clamp_component(f->col[j].r);
368                 mcol->g= clamp_component(f->col[j].g);
369                 mcol->b= clamp_component(f->col[j].b);
370                 ++mcol;
371         }
372 }
373
374 /* 1 <= count <= 4 */
375 void multires_col_avg(MultiresCol *avg, MultiresCol cols[4], char count)
376 {
377         unsigned i;
378         avg->a= avg->r= avg->g= avg->b= 0;
379         for(i=0; i<count; ++i) {
380                 avg->a+= cols[i].a;
381                 avg->r+= cols[i].r;
382                 avg->g+= cols[i].g;
383                 avg->b+= cols[i].b;
384         }
385         avg->a/= count;
386         avg->r/= count;
387         avg->g/= count;
388         avg->b/= count;
389 }
390
391 void multires_col_avg2(MultiresCol *avg, MultiresCol *c1, MultiresCol *c2)
392 {
393         MultiresCol in[2];
394         in[0]= *c1;
395         in[1]= *c2;
396         multires_col_avg(avg,in,2);
397 }
398
399 void multires_load_cols(Mesh *me)
400 {
401         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1), *cur;
402         EditMesh *em= G.obedit ? G.editMesh : NULL;
403         CustomData *src= em ? &em->fdata : &me->fdata;
404         EditFace *efa= NULL;
405         unsigned i,j;
406
407         if(!CustomData_has_layer(src, CD_MCOL) && !CustomData_has_layer(src, CD_MTFACE)) return;
408
409         /* Add texcol data */
410         for(cur= me->mr->levels.first; cur; cur= cur->next)
411                 if(!cur->colfaces)
412                         cur->colfaces= MEM_callocN(sizeof(MultiresColFace)*cur->totface,"ColFaces");
413
414         me->mr->use_col= CustomData_has_layer(src, CD_MCOL);
415
416         if(em) efa= em->faces.first;
417         for(i=0; i<lvl->totface; ++i) {
418                 MultiresColFace *f= &lvl->colfaces[i];
419
420                 if(me->mr->use_col)
421                         mcol_to_multires(f, em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4]);
422                 
423                 if(em) efa= efa->next;
424         }
425
426         /* Update higher levels */
427         lvl= lvl->next;
428         while(lvl) {
429                 MultiresColFace *cf= lvl->colfaces;
430                 for(i=0; i<lvl->prev->totface; ++i) {
431                         const char sides= lvl->prev->faces[i].v[3]?4:3;
432                         MultiresCol cntr;
433                         
434                         /* Find average color of 4 (or 3 for triangle) verts */
435                         multires_col_avg(&cntr,lvl->prev->colfaces[i].col,sides);
436                         
437                         for(j=0; j<sides; ++j) {
438                                 MultiresColFace *pf= &lvl->prev->colfaces[i];
439
440                                 multires_col_avg2(&cf->col[0],
441                                                   &pf->col[j],
442                                                   &pf->col[j==0?sides-1:j-1]);
443                                 cf->col[1]= pf->col[j];
444                                 multires_col_avg2(&cf->col[2],
445                                                   &pf->col[j],
446                                                   &pf->col[j==sides-1?0:j+1]);
447                                 cf->col[3]= cntr;
448                                 
449                                 ++cf;
450                         }
451                 }
452                 lvl= lvl->next;
453         }
454
455         /* Update lower levels */
456         lvl= me->mr->levels.last;
457         lvl= lvl->prev;
458         while(lvl) {
459                 unsigned curf= 0;
460                 for(i=0; i<lvl->totface; ++i) {
461                         MultiresFace *f= &lvl->faces[i];
462                         for(j=0; j<(f->v[3]?4:3); ++j) {
463                                 lvl->colfaces[i].col[j]= lvl->next->colfaces[curf].col[1];
464                                 ++curf;
465                         }
466                 }
467                 lvl= lvl->prev;
468         }
469 }
470
471 void multires_get_vert(MVert *out, EditVert *eve, MVert *m, int i)
472 {
473         if(eve) {
474                 VecCopyf(out->co, eve->co);
475                 out->flag= 0;
476                 if(eve->f & SELECT) out->flag |= 1;
477                 if(eve->h) out->flag |= ME_HIDE;
478                 eve->tmp.l= i;
479         }
480         else
481                 *out= *m;
482 }
483
484 void multires_get_face(MultiresFace *f, EditFace *efa, MFace *m)
485 {
486         if(efa) {
487                 MFace tmp;
488                 int j;
489                 tmp.v1= efa->v1->tmp.l;
490                 tmp.v2= efa->v2->tmp.l;
491                 tmp.v3= efa->v3->tmp.l;
492                 tmp.v4= 0;
493                 if(efa->v4) tmp.v4= efa->v4->tmp.l;
494                 tmp.flag= efa->flag;
495                 if(efa->f & 1) tmp.flag |= ME_FACE_SEL;
496                 else f->flag &= ~ME_FACE_SEL;
497                 if(efa->h) tmp.flag |= ME_HIDE;
498                 test_index_face(&tmp, NULL, 0, efa->v4?4:3);
499                 for(j=0; j<4; ++j) f->v[j]= (&tmp.v1)[j];
500                 f->flag= tmp.flag;
501                 f->mat_nr= efa->mat_nr;
502         } else {                
503                 f->v[0]= m->v1;
504                 f->v[1]= m->v2;
505                 f->v[2]= m->v3;
506                 f->v[3]= m->v4;
507                 f->flag= m->flag;
508                 f->mat_nr= m->mat_nr;
509         }
510 }
511
512 void multires_get_edge(MultiresEdge *e, EditEdge *eed, MEdge *m, short *flag)
513 {
514         if(eed) {
515                 e->v[0]= eed->v1->tmp.l;
516                 e->v[1]= eed->v2->tmp.l;
517                 *flag= 0;
518                 if(eed->seam)
519                         *flag |= ME_SEAM;
520         } else {                
521                 e->v[0]= m->v1;
522                 e->v[1]= m->v2;
523                 *flag= m->flag;
524         }
525 }
526
527 void multires_make(void *ob, void *me_v)
528 {
529         Mesh *me= me_v;
530         MultiresLevel *lvl;
531         EditMesh *em= G.obedit ? G.editMesh : NULL;
532         EditVert *eve= NULL;
533         EditFace *efa= NULL;
534         EditEdge *eed= NULL;
535         Key *key;
536         int i;
537         
538         /* Check for shape keys */
539         key= me->key;
540         if(key) {
541                 int ret= okee("Adding multires will delete all shape keys, proceed?");
542                 if(ret) {
543                         free_key(key);
544                         me->key= NULL;
545                 } else
546                         return;
547         }
548         
549         lvl= MEM_callocN(sizeof(MultiresLevel), "multires level");
550
551         waitcursor(1);
552         
553         multires_check_state();
554
555         if(me->pv) sculptmode_pmv_off(me);
556
557         me->mr= MEM_callocN(sizeof(Multires), "multires data");
558         
559         BLI_addtail(&me->mr->levels,lvl);
560         me->mr->current= 1;
561         me->mr->level_count= 1;
562         me->mr->edgelvl= 1;
563         me->mr->pinlvl= 1;
564         me->mr->renderlvl= 1;
565         
566         /* Load mesh (or editmesh) into multires data */
567
568         /* Load vertices and vdata (MDeformVerts) */
569         lvl->totvert= em ? BLI_countlist(&em->verts) : me->totvert;
570         lvl->verts= MEM_callocN(sizeof(MVert)*lvl->totvert,"multires verts");
571         multires_update_customdata(me->mr->levels.first, em ? &em->vdata : &me->vdata,
572                                    &me->mr->vdata, CD_MDEFORMVERT);
573         if(em) eve= em->verts.first;
574         for(i=0; i<lvl->totvert; ++i) {
575                 multires_get_vert(&lvl->verts[i], eve, &me->mvert[i], i);
576                 if(em) eve= eve->next;
577         }
578
579         /* Load faces and fdata (MTFaces) */
580         lvl->totface= em ? BLI_countlist(&em->faces) : me->totface;
581         lvl->faces= MEM_callocN(sizeof(MultiresFace)*lvl->totface,"multires faces");
582         multires_update_customdata(me->mr->levels.first, em ? &em->fdata : &me->fdata,
583                                    &me->mr->fdata, CD_MTFACE);
584         if(em) efa= em->faces.first;
585         for(i=0; i<lvl->totface; ++i) {
586                 multires_get_face(&lvl->faces[i], efa, &me->mface[i]);
587                 if(em) efa= efa->next;
588         }
589
590         /* Load edges and edge_flags */
591         lvl->totedge= em ? BLI_countlist(&em->edges) : me->totedge;
592         lvl->edges= MEM_callocN(sizeof(MultiresEdge)*lvl->totedge,"multires edges");
593         me->mr->edge_flags= MEM_callocN(sizeof(short)*lvl->totedge, "multires edge flags");
594         if(em) eed= em->edges.first;
595         for(i=0; i<lvl->totedge; ++i) {
596                 multires_get_edge(&lvl->edges[i], eed, &me->medge[i], &me->mr->edge_flags[i]);
597                 if(em) eed= eed->next;
598         }
599
600         multires_load_cols(me);
601
602         multires_calc_level_maps(lvl);
603         
604         allqueue(REDRAWBUTSEDIT, 0);
605
606         multires_undo_push("Make multires");
607
608         waitcursor(0);
609 }
610
611 void multires_delete(void *ob, void *me_v)
612 {
613         Mesh *me= me_v;
614         multires_free(me->mr);
615         me->mr= NULL;
616         
617         multires_check_state();
618
619         allqueue(REDRAWBUTSEDIT, 0);
620
621         multires_undo_push("Apply multires");
622 }
623
624 MultiresLevel *multires_level_copy(MultiresLevel *orig)
625 {
626         if(orig) {
627                 MultiresLevel *lvl= MEM_dupallocN(orig);
628                 
629                 lvl->next= lvl->prev= NULL;
630                 lvl->verts= MEM_dupallocN(orig->verts);
631                 lvl->faces= MEM_dupallocN(orig->faces);
632                 lvl->colfaces= MEM_dupallocN(orig->colfaces);
633                 lvl->edges= MEM_dupallocN(orig->edges);
634                 lvl->vert_edge_map= lvl->vert_face_map= NULL;
635                 multires_calc_level_maps(lvl);
636                 
637                 return lvl;
638         }
639         return NULL;
640 }
641
642 Multires *multires_copy(Multires *orig)
643 {
644         if(orig) {
645                 Multires *mr= MEM_dupallocN(orig);
646                 MultiresLevel *lvl;
647                 
648                 mr->levels.first= mr->levels.last= NULL;
649                 
650                 for(lvl= orig->levels.first; lvl; lvl= lvl->next)
651                         BLI_addtail(&mr->levels, multires_level_copy(lvl));
652                 
653                 lvl= mr->levels.first;
654                 if(lvl) {
655                         CustomData_copy(&orig->vdata, &mr->vdata, vdata_mask, CD_DUPLICATE, lvl->totvert);
656                         CustomData_copy(&orig->fdata, &mr->fdata, CD_MASK_MTFACE, CD_DUPLICATE, lvl->totface);
657                         mr->edge_flags= MEM_dupallocN(orig->edge_flags);
658                 }
659                 
660                 return mr;
661         }
662         return NULL;
663 }
664
665 void multires_free(Multires *mr)
666 {
667         if(mr) {
668                 MultiresLevel* lvl= mr->levels.first;
669
670                 /* Free the first-level data */
671                 if(lvl) {
672                         CustomData_free(&mr->vdata, lvl->totvert);
673                         CustomData_free(&mr->fdata, lvl->totface);
674                         MEM_freeN(mr->edge_flags);
675                 }
676
677                 while(lvl) {
678                         multires_free_level(lvl);                       
679                         lvl= lvl->next;
680                 }
681
682                 BLI_freelistN(&mr->levels);
683
684                 MEM_freeN(mr);
685         }
686 }
687
688 /* Does not actually free lvl itself! */
689 void multires_free_level(MultiresLevel *lvl)
690 {
691         if(lvl) {
692                 if(lvl->verts) MEM_freeN(lvl->verts);
693                 if(lvl->faces) MEM_freeN(lvl->faces);
694                 if(lvl->edges) MEM_freeN(lvl->edges);
695                 if(lvl->colfaces) MEM_freeN(lvl->colfaces);
696                 
697                 /* Free all vertex maps */
698                 MEM_freeN(lvl->vert_edge_map);
699                 MEM_freeN(lvl->vert_face_map);
700                 MEM_freeN(lvl->map_mem);
701         }
702 }
703
704 /* Make sure that all level indices are clipped to [1, mr->level_count] */
705 void multires_clip_levels(Multires *mr)
706 {
707         if(mr) {
708                 const int cnt = mr->level_count;
709         
710                 if(mr->current < 1) mr->current = 1;
711                 if(mr->edgelvl < 1) mr->edgelvl = 1;
712                 if(mr->pinlvl < 1) mr->pinlvl = 1;
713                 if(mr->renderlvl < 1) mr->renderlvl = 1;
714                 
715                 if(mr->current > cnt) mr->current = cnt;
716                 if(mr->edgelvl > cnt) mr->edgelvl = cnt;
717                 if(mr->pinlvl > cnt) mr->pinlvl = cnt;
718                 if(mr->renderlvl > cnt) mr->renderlvl = cnt;
719         }
720 }
721
722 /* Delete all multires levels beneath current level. Subdivide special
723    first-level data up to the new lowest level. */
724 void multires_del_lower(void *ob, void *me)
725 {
726         Multires *mr= ((Mesh*)me)->mr;
727         MultiresLevel *lvl1= mr->levels.first, *cr_lvl= current_level(mr);
728         MultiresLevel *lvl= NULL, *lvlprev= NULL;
729         short *edgeflags= NULL;
730         int i, last;
731         
732         if(cr_lvl == lvl1) return;
733         
734         multires_check_state();
735         
736         /* Subdivide the edge flags to the current level */
737         edgeflags= MEM_callocN(sizeof(short)*current_level(mr)->totedge, "Multires Edge Flags");
738         last= lvl1->totedge * pow(2, mr->current-1);
739         for(i=0; i<last; ++i)
740                 edgeflags[i] = mr->edge_flags[(int)(i / pow(2, mr->current-1))];
741         MEM_freeN(mr->edge_flags);
742         mr->edge_flags= edgeflags;
743         
744         multires_del_lower_customdata(mr, cr_lvl);
745         
746         lvl= cr_lvl->prev;
747         while(lvl) {
748                 lvlprev= lvl->prev;
749                 
750                 multires_free_level(lvl);
751                 BLI_freelinkN(&mr->levels, lvl);
752                 
753                 mr->current-= 1;
754                 mr->level_count-= 1;
755                 
756                 lvl= lvlprev;
757         }
758         mr->newlvl= mr->current;
759         
760         multires_clip_levels(mr);
761
762         allqueue(REDRAWBUTSEDIT, 0);
763
764         multires_undo_push("Multires delete lower");
765 }
766
767 void multires_del_higher(void *ob, void *me)
768 {
769         Multires *mr= ((Mesh*)me)->mr;
770         MultiresLevel *lvl= BLI_findlink(&mr->levels,mr->current-1);
771         MultiresLevel *lvlnext;
772         
773         multires_check_state();
774         
775         lvl= lvl->next;
776         while(lvl) {
777                 lvlnext= lvl->next;
778                 
779                 multires_free_level(lvl);
780                 BLI_freelinkN(&mr->levels,lvl);
781
782                 mr->level_count-= 1;
783                 
784                 lvl= lvlnext;
785         }
786         
787         multires_clip_levels(mr);
788
789         allqueue(REDRAWBUTSEDIT, 0);
790
791         multires_undo_push("Multires delete higher");
792 }
793
794 unsigned int find_mid_edge(ListBase *vert_edge_map,
795                            MultiresLevel *lvl,
796                            const unsigned int v1,
797                            const unsigned int v2 )
798 {
799         MultiresMapNode *n= vert_edge_map[v1].first;
800         while(n) {
801                 if(lvl->edges[n->Index].v[0]==v2 ||
802                    lvl->edges[n->Index].v[1]==v2)
803                         return lvl->edges[n->Index].mid;
804
805                 n= n->next;
806         }
807         return -1;
808 }
809
810 void check_colors(Mesh *me)
811 {
812         CustomData *src= G.obedit ? &G.editMesh->fdata : &me->fdata;
813         const char col= CustomData_has_layer(src, CD_MCOL);
814
815         /* Check if vertex colors have been deleted or added */
816         if(me->mr->use_col && !col)
817                 me->mr->use_col= 0;
818         else if(!me->mr->use_col && col) {
819                 me->mr->use_col= 1;
820                 multires_load_cols(me);
821         }
822 }
823
824 void multires_add_level(void *ob, void *me_v)
825 {
826         int i,j, curf, cure;
827         Mesh *me= me_v;
828         MultiresLevel *lvl= MEM_callocN(sizeof(MultiresLevel), "multireslevel");
829         MultiApplyData data;
830         
831         multires_check_state();
832
833         waitcursor(1);
834
835         if(me->pv) sculptmode_pmv_off(me);
836
837         check_colors(me);
838
839         ++me->mr->level_count;
840         BLI_addtail(&me->mr->levels,lvl);
841
842         /* Create vertices
843            =============== */
844         lvl->totvert= lvl->prev->totvert + lvl->prev->totedge + lvl->prev->totface;
845         lvl->verts= MEM_callocN(sizeof(MVert)*lvl->totvert,"multires verts");
846         /* Copy previous level's verts */
847         for(i=0; i<lvl->prev->totvert; ++i)
848                 lvl->verts[i]= lvl->prev->verts[i];
849         /* Create new edge verts */
850         for(i=0; i<lvl->prev->totedge; ++i) {
851                 VecMidf(lvl->verts[lvl->prev->totvert + i].co,
852                         lvl->prev->verts[lvl->prev->edges[i].v[0]].co,
853                         lvl->prev->verts[lvl->prev->edges[i].v[1]].co);
854                 lvl->prev->edges[i].mid= lvl->prev->totvert + i;
855         }
856         /* Create new face verts */
857         for(i=0; i<lvl->prev->totface; ++i) {
858                 lvl->prev->faces[i].mid= lvl->prev->totvert + lvl->prev->totedge + i;
859         }
860
861         /* Create faces
862            ============ */
863         /* Allocate all the new faces (each triangle creates three, and
864            each quad creates four */
865         lvl->totface= 0;
866         for(i=0; i<lvl->prev->totface; ++i)
867                 lvl->totface+= lvl->prev->faces[i].v[3] ? 4 : 3;
868         lvl->faces= MEM_callocN(sizeof(MultiresFace)*lvl->totface,"multires faces");
869
870         curf= 0;
871         for(i=0; i<lvl->prev->totface; ++i) {
872                 const int max= lvl->prev->faces[i].v[3] ? 3 : 2;
873                 
874                 lvl->prev->faces[i].childrenstart= curf;
875                 for(j=0; j<max+1; ++j) {
876                         lvl->faces[curf].v[0]= find_mid_edge(lvl->prev->vert_edge_map,lvl->prev,
877                                                              lvl->prev->faces[i].v[j],
878                                                              lvl->prev->faces[i].v[j==0?max:j-1]);
879                         lvl->faces[curf].v[1]= lvl->prev->faces[i].v[j];
880                         lvl->faces[curf].v[2]= find_mid_edge(lvl->prev->vert_edge_map,lvl->prev,
881                                                              lvl->prev->faces[i].v[j],
882                                                              lvl->prev->faces[i].v[j==max?0:j+1]);
883                         lvl->faces[curf].v[3]= lvl->prev->totvert + lvl->prev->totedge + i;
884                         lvl->faces[curf].flag= lvl->prev->faces[i].flag;
885                         lvl->faces[curf].mat_nr= lvl->prev->faces[i].mat_nr;
886
887                         ++curf;
888                 }
889         }
890
891         /* Create edges
892            ============ */
893         /* Figure out how many edges to allocate */
894         lvl->totedge= lvl->prev->totedge*2;
895         for(i=0; i<lvl->prev->totface; ++i)
896                 lvl->totedge+= lvl->prev->faces[i].v[3]?4:3;
897         lvl->edges= MEM_callocN(sizeof(MultiresEdge)*lvl->totedge,"multires edges");
898
899         for(i=0; i<lvl->prev->totedge; ++i) {
900                 lvl->edges[i*2].v[0]= lvl->prev->edges[i].v[0];
901                 lvl->edges[i*2].v[1]= lvl->prev->edges[i].mid;
902                 lvl->edges[i*2+1].v[0]= lvl->prev->edges[i].mid;
903                 lvl->edges[i*2+1].v[1]= lvl->prev->edges[i].v[1];
904         }
905         /* Add edges inside of old polygons */
906         curf= 0;
907         cure= lvl->prev->totedge*2;
908         for(i=0; i<lvl->prev->totface; ++i) {
909                 for(j=0; j<(lvl->prev->faces[i].v[3]?4:3); ++j) {
910                         lvl->edges[cure].v[0]= lvl->faces[curf].v[2];
911                         lvl->edges[cure].v[1]= lvl->faces[curf].v[3];
912                         ++cure;
913                         ++curf;
914                 }
915         }
916
917         multires_calc_level_maps(lvl);
918         
919         /* Smooth vertices
920            =============== */
921         for(i=0; i<lvl->prev->totface; ++i) {
922                 const MultiresFace *f= &lvl->prev->faces[i];
923                 data.corner1= lvl->prev->verts[f->v[0]].co;
924                 data.corner2= lvl->prev->verts[f->v[1]].co;
925                 data.corner3= lvl->prev->verts[f->v[2]].co;
926                 data.corner4= lvl->prev->verts[f->v[3]].co;
927                 data.quad= f->v[3] ? 1 : 0;
928                 multi_apply(lvl->verts[f->mid].co, &data, 3, catmullclark_smooth_face);
929         }
930
931         for(i=0; i<lvl->prev->totedge; ++i) {
932                 const MultiresEdge *e= &lvl->prev->edges[i];
933                 data.boundary= multires_edge_is_boundary(lvl->prev,i);
934                 edge_face_neighbor_midpoints_accum(&data,lvl->prev,lvl->verts,sizeof(MVert),e);
935                 data.endpoint1= lvl->prev->verts[e->v[0]].co;
936                 data.endpoint2= lvl->prev->verts[e->v[1]].co;
937                 multi_apply(lvl->verts[e->mid].co, &data, 3, catmullclark_smooth_edge);
938         }
939         
940         for(i=0; i<lvl->prev->totvert; ++i) {
941                 data.boundary= multires_vert_is_boundary(lvl->prev,i);
942                 data.original= lvl->verts[i].co;
943                 data.edge_count= BLI_countlist(&lvl->prev->vert_edge_map[i]);
944                 if(data.boundary)
945                         boundary_edges_average(&data,lvl->prev,lvl->prev->verts,sizeof(MVert),i);
946                 else {
947                         vert_face_neighbor_midpoints_average(&data,lvl->prev,lvl->verts,sizeof(MVert),i);
948                         vert_edge_neighbor_midpoints_average(&data,lvl->prev,lvl->prev->verts,sizeof(MVert),i);
949                 }
950                 multi_apply(lvl->verts[i].co, &data, 3, catmullclark_smooth_vert);
951         }
952
953         /* Vertex Colors
954            ============= */
955         curf= 0;
956         if(me->mr->use_col) {
957                 MultiresColFace *cf= MEM_callocN(sizeof(MultiresColFace)*lvl->totface,"Multirescolfaces");
958                 lvl->colfaces= cf;
959                 for(i=0; i<lvl->prev->totface; ++i) {
960                         const char sides= lvl->prev->faces[i].v[3]?4:3;
961                         MultiresCol cntr;
962
963                         /* Find average color of 4 (or 3 for triangle) verts */
964                         multires_col_avg(&cntr,lvl->prev->colfaces[i].col,sides);
965
966                         for(j=0; j<sides; ++j) {
967                                 multires_col_avg2(&cf->col[0],
968                                                   &lvl->prev->colfaces[i].col[j],
969                                                   &lvl->prev->colfaces[i].col[j==0?sides-1:j-1]);
970                                 cf->col[1]= lvl->prev->colfaces[i].col[j];
971                                 multires_col_avg2(&cf->col[2],
972                                                   &lvl->prev->colfaces[i].col[j],
973                                                   &lvl->prev->colfaces[i].col[j==sides-1?0:j+1]);
974                                 cf->col[3]= cntr;
975
976                                 ++cf;
977                         }
978                 }
979         }
980
981         multires_update_levels(me);
982         me->mr->newlvl= me->mr->level_count;
983         me->mr->current= me->mr->newlvl;
984         /* Unless the render level has been set to something other than the
985            highest level (by the user), increment the render level to match
986            the highest available level */
987         if(me->mr->renderlvl == me->mr->level_count - 1) me->mr->renderlvl= me->mr->level_count;
988         
989         multires_level_to_mesh(ob,me);
990         
991         allqueue(REDRAWBUTSEDIT, 0);
992
993         multires_undo_push("Add multires level");
994
995         waitcursor(0);
996 }
997
998 void multires_set_level(void *ob, void *me_v)
999 {
1000         Mesh *me= me_v;
1001
1002         waitcursor(1);
1003         
1004         multires_check_state();
1005
1006         if(me->pv) sculptmode_pmv_off(me);
1007
1008         check_colors(me);
1009         multires_update_levels(me);
1010
1011         me->mr->current= me->mr->newlvl;
1012         if(me->mr->current<1) me->mr->current= 1;
1013         else if(me->mr->current>me->mr->level_count) me->mr->current= me->mr->level_count;
1014
1015         multires_level_to_mesh(ob,me);
1016         
1017         if(G.obedit || G.f & G_SCULPTMODE)
1018                 multires_undo_push("Multires set level");
1019
1020         allqueue(REDRAWBUTSEDIT, 0);
1021         
1022         waitcursor(0);
1023 }
1024
1025 /* note, function is called in background render too, without UI */
1026 void multires_level_to_mesh(Object *ob, Mesh *me)
1027 {
1028         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1029         int i;
1030         EditMesh *em= G.obedit ? G.editMesh : NULL;
1031         EditVert **eves= NULL;
1032         EditEdge *eed= NULL;
1033         
1034         if(em) {
1035                 /* Remove editmesh elements */
1036                 free_vertlist(&em->verts);
1037                 free_edgelist(&em->edges);
1038                 free_facelist(&em->faces);
1039                 
1040                 CustomData_free(&G.editMesh->vdata, 0);
1041                 CustomData_free(&G.editMesh->fdata, 0);
1042                 
1043                 eves= MEM_callocN(sizeof(EditVert)*lvl->totvert, "editvert pointers");
1044         } else {
1045                 CustomData_free_layer_active(&me->vdata, CD_MVERT, me->totvert);
1046                 CustomData_free_layer_active(&me->edata, CD_MEDGE, me->totedge);
1047                 CustomData_free_layer_active(&me->fdata, CD_MFACE, me->totface);
1048                 CustomData_free_layer_active(&me->vdata, CD_MDEFORMVERT, me->totvert);
1049                 CustomData_free_layers(&me->fdata, CD_MTFACE, me->totface);
1050                 CustomData_free_layers(&me->fdata, CD_MCOL, me->totface);
1051                 
1052                 me->totvert= lvl->totvert;
1053                 me->totface= lvl->totface;
1054                 me->totedge= lvl->totedge;
1055
1056                 CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
1057                 CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
1058                 CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
1059                 mesh_update_customdata_pointers(me);
1060         }
1061
1062         /* Vertices/Edges/Faces */
1063         
1064         for(i=0; i<lvl->totvert; ++i) {
1065                 if(em) {
1066                         eves[i]= addvertlist(lvl->verts[i].co, NULL); /* TODO */
1067                         if(lvl->verts[i].flag & 1) eves[i]->f |= SELECT;
1068                         if(lvl->verts[i].flag & ME_HIDE) eves[i]->h= 1;
1069                         eves[i]->data= NULL;
1070                 }
1071                 else
1072                         me->mvert[i]= lvl->verts[i];
1073         }
1074         for(i=0; i<lvl->totedge; ++i) {
1075                 if(em) {
1076                         addedgelist(eves[lvl->edges[i].v[0]], eves[lvl->edges[i].v[1]], NULL);
1077                 } else {
1078                         me->medge[i].v1= lvl->edges[i].v[0];
1079                         me->medge[i].v2= lvl->edges[i].v[1];
1080                         me->medge[i].flag &= ~ME_HIDE;
1081                 }
1082         }
1083         for(i=0; i<lvl->totface; ++i) {
1084                 if(em) {
1085                         EditVert *eve4= lvl->faces[i].v[3] ? eves[lvl->faces[i].v[3]] : NULL;
1086                         EditFace *efa= addfacelist(eves[lvl->faces[i].v[0]], eves[lvl->faces[i].v[1]],
1087                                        eves[lvl->faces[i].v[2]], eve4, NULL, NULL); /* TODO */
1088                         efa->flag= lvl->faces[i].flag;
1089                         efa->mat_nr= lvl->faces[i].mat_nr;
1090                         efa->data= NULL;
1091                 }
1092                 else {
1093                         me->mface[i].v1= lvl->faces[i].v[0];
1094                         me->mface[i].v2= lvl->faces[i].v[1];
1095                         me->mface[i].v3= lvl->faces[i].v[2];
1096                         me->mface[i].v4= lvl->faces[i].v[3];
1097                         me->mface[i].flag= lvl->faces[i].flag;
1098                         me->mface[i].flag &= ~ME_HIDE;
1099                         me->mface[i].mat_nr= lvl->faces[i].mat_nr;
1100                 }
1101         }
1102         
1103         /* Edge flags */
1104         if(em) eed= em->edges.first;
1105         if(lvl==me->mr->levels.first) {
1106                 for(i=0; i<lvl->totedge; ++i) {
1107                         if(em) {
1108                                 if(me->mr->edge_flags[i] & ME_SEAM)
1109                                         eed->seam= 1;
1110                                 eed= eed->next;
1111                         }
1112                         else
1113                                 me->medge[i].flag= me->mr->edge_flags[i];
1114                 }
1115         } else {
1116                 MultiresLevel *lvl1= me->mr->levels.first;
1117                 const int last= lvl1->totedge * pow(2, me->mr->current-1);
1118                 for(i=0; i<last; ++i) {
1119                         const int ndx= i / pow(2, me->mr->current-1);
1120                         if(me->mr->edge_flags[ndx] & ME_SEAM) {
1121                                 if(em)
1122                                         eed->seam= 1;
1123                                 else
1124                                         me->medge[i].flag |= ME_SEAM;
1125                         }
1126                         if(em) eed= eed->next;
1127                 }
1128         }
1129
1130         multires_customdata_to_mesh(me, em, lvl, &me->mr->vdata, em ? &em->vdata : &me->vdata, CD_MDEFORMVERT);
1131         multires_customdata_to_mesh(me, em, lvl, &me->mr->fdata, em ? &em->fdata : &me->fdata, CD_MTFACE);
1132
1133         /* Colors */
1134         if(me->mr->use_col) {
1135                 MCol c[4];
1136                 EditFace *efa= NULL;
1137                 CustomData *src= em ? &em->fdata : &me->fdata;
1138                 if(em) {
1139                         if(me->mr->use_col) EM_add_data_layer(src, CD_MCOL);
1140                         efa= em->faces.first;
1141                 }
1142                 else {
1143                         if(me->mr->use_col) me->mcol= CustomData_add_layer(src, CD_MCOL, CD_CALLOC, NULL, me->totface);
1144                 }
1145                 
1146                 for(i=0; i<lvl->totface; ++i) {
1147                         if(em) {
1148                                 if(me->mr->use_col) {
1149                                         multires_to_mcol(&lvl->colfaces[i], c);
1150                                         CustomData_em_set(src, efa->data, CD_MCOL, c);
1151                                 }
1152                                 efa= efa->next;
1153                         }
1154                         else if(me->mr->use_col) multires_to_mcol(&lvl->colfaces[i], &me->mcol[i*4]);
1155                 }
1156                         
1157         }
1158         
1159         if(em) {
1160                 MEM_freeN(eves);
1161                 DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
1162         } else {
1163                 multires_edge_level_update(ob,me);
1164                 DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
1165                 mesh_calc_normals(me->mvert, me->totvert, me->mface, me->totface, NULL);
1166         }
1167         
1168         mesh_update_customdata_pointers(me);
1169
1170         /* friendly check for background render */
1171         if(G.background==0) {
1172                 countall();
1173                 
1174                 if(G.vd && G.vd->depths) G.vd->depths->damaged= 1;
1175                 allqueue(REDRAWVIEW3D, 0);
1176                 allqueue(REDRAWIMAGE, 0);
1177         }
1178 }
1179
1180 void multires_update_colors(Mesh *me)
1181 {
1182         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1183         MultiresCol *pr_deltas= NULL, *cr_deltas= NULL;
1184         EditMesh *em= G.obedit ? G.editMesh : NULL;
1185         CustomData *src= em ? &em->fdata : &me->fdata;
1186         EditFace *efa= NULL;
1187         unsigned i,j,curf= 0;
1188         
1189         if(me->mr->use_col) {
1190                 /* Calc initial deltas */
1191                 cr_deltas= MEM_callocN(sizeof(MultiresCol)*lvl->totface*4,"initial color/uv deltas");
1192
1193                 if(em) efa= em->faces.first;
1194                 for(i=0; i<lvl->totface; ++i) {
1195                         MCol *col= em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4];
1196                         for(j=0; j<4; ++j) {
1197                                 if(me->mr->use_col) {
1198                                         cr_deltas[i*4+j].a= col[j].a - lvl->colfaces[i].col[j].a;
1199                                         cr_deltas[i*4+j].r= col[j].r - lvl->colfaces[i].col[j].r;
1200                                         cr_deltas[i*4+j].g= col[j].g - lvl->colfaces[i].col[j].g;
1201                                         cr_deltas[i*4+j].b= col[j].b - lvl->colfaces[i].col[j].b;
1202                                 }
1203                         }
1204                         if(em) efa= efa->next;
1205                 }
1206                 
1207                 /* Update current level */
1208                 if(em) efa= em->faces.first;
1209                 for(i=0; i<lvl->totface; ++i) {
1210                         MultiresColFace *f= &lvl->colfaces[i];
1211
1212                         if(me->mr->use_col)
1213                                 mcol_to_multires(f, em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4]);
1214                         
1215                         if(em) efa= efa->next;
1216                 }
1217                 
1218                 /* Update higher levels */
1219                 lvl= lvl->next;
1220                 while(lvl) {
1221                         /* Set up new deltas, but keep the ones from the previous level */
1222                         if(pr_deltas) MEM_freeN(pr_deltas);
1223                         pr_deltas= cr_deltas;
1224                         cr_deltas= MEM_callocN(sizeof(MultiresCol)*lvl->totface*4,"color deltas");
1225
1226                         curf= 0;
1227                         for(i=0; i<lvl->prev->totface; ++i) {
1228                                 const char sides= lvl->prev->faces[i].v[3]?4:3;
1229                                 MultiresCol cntr;
1230                                 
1231                                 /* Find average color of 4 (or 3 for triangle) verts */
1232                                 multires_col_avg(&cntr,&pr_deltas[i*4],sides);
1233                                 
1234                                 for(j=0; j<sides; ++j) {
1235                                         multires_col_avg2(&cr_deltas[curf*4],
1236                                                           &pr_deltas[i*4+j],
1237                                                           &pr_deltas[i*4+(j==0?sides-1:j-1)]);
1238                                         cr_deltas[curf*4+1]= pr_deltas[i*4+j];
1239                                         multires_col_avg2(&cr_deltas[curf*4+2],
1240                                                           &pr_deltas[i*4+j],
1241                                                           &pr_deltas[i*4+(j==sides-1?0:j+1)]);
1242                                         cr_deltas[curf*4+3]= cntr;
1243                                         ++curf;
1244                                 }
1245                         }
1246
1247                         for(i=0; i<lvl->totface; ++i) {
1248                                 for(j=0; j<4; ++j) {
1249                                         lvl->colfaces[i].col[j].a+= cr_deltas[i*4+j].a;
1250                                         lvl->colfaces[i].col[j].r+= cr_deltas[i*4+j].r;
1251                                         lvl->colfaces[i].col[j].g+= cr_deltas[i*4+j].g;
1252                                         lvl->colfaces[i].col[j].b+= cr_deltas[i*4+j].b;
1253                                 }
1254                         }
1255
1256                         lvl= lvl->next;
1257                 }
1258                 if(pr_deltas) MEM_freeN(pr_deltas);
1259                 if(cr_deltas) MEM_freeN(cr_deltas);
1260                 
1261                 /* Update lower levels */
1262                 lvl= me->mr->levels.last;
1263                 lvl= lvl->prev;
1264                 while(lvl) {
1265                         MultiresColFace *nf= lvl->next->colfaces;
1266                         for(i=0; i<lvl->totface; ++i) {
1267                                 MultiresFace *f= &lvl->faces[i];
1268                                 for(j=0; j<(f->v[3]?4:3); ++j) {
1269                                         lvl->colfaces[i].col[j]= nf->col[1];
1270                                         ++nf;
1271                                 }
1272                         }
1273                         lvl= lvl->prev;
1274                 }
1275         }
1276 }
1277
1278 void multires_update_edge_flags(Multires *mr, Mesh *me, EditMesh *em)
1279 {
1280         MultiresLevel *lvl= current_level(mr);
1281         EditEdge *eed= NULL;
1282         int i;
1283         
1284         if(em) eed= em->edges.first;
1285         for(i=0; i<lvl->totedge; ++i) {
1286                 if(em) {
1287                         mr->edge_flags[i]= 0;
1288                         if(eed->seam)
1289                                 mr->edge_flags[i] |= ME_SEAM;
1290                         eed= eed->next;
1291                 }
1292                 else
1293                         mr->edge_flags[i]= me->medge[i].flag;
1294         }
1295 }
1296
1297 void multires_update_levels(Mesh *me)
1298 {
1299         /* cr=current, pr=previous, or=original */
1300         MultiresLevel *cr_lvl= current_level(me->mr), *pr_lvl;
1301         MultiresLevel *or_lvl= cr_lvl;
1302         vec3f *pr_deltas= NULL, *cr_deltas= NULL;
1303         char *pr_flag_damaged= NULL, *cr_flag_damaged= NULL, *pr_mat_damaged= NULL, *cr_mat_damaged= NULL;
1304         char *or_flag_damaged= NULL, *or_mat_damaged= NULL;
1305         EditMesh *em= G.obedit ? G.editMesh : NULL;
1306         EditVert *eve= NULL;
1307         EditFace *efa= NULL;
1308         MultiApplyData data;
1309         unsigned i,j,curf;
1310
1311         /* Update special first-level data */
1312         if(cr_lvl==me->mr->levels.first) {
1313                 multires_update_customdata(me->mr->levels.first, em ? &em->vdata : &me->vdata,
1314                                            &me->mr->vdata, CD_MDEFORMVERT);
1315                 multires_update_customdata(me->mr->levels.first, em ? &em->fdata : &me->fdata,
1316                                            &me->mr->fdata, CD_MTFACE);
1317                 multires_update_edge_flags(me->mr, me, em);
1318         }
1319
1320         /* Prepare deltas */
1321         cr_deltas= MEM_callocN(sizeof(vec3f)*cr_lvl->totvert,"initial deltas");
1322
1323         /* Calculate initial deltas -- current mesh subtracted from current level*/
1324         if(em) eve= em->verts.first;
1325         for(i=0; i<cr_lvl->totvert; ++i) {
1326                 if(em) {
1327                         VecSubf(&cr_deltas[i].x, eve->co, cr_lvl->verts[i].co);
1328                         eve= eve->next;
1329                 } else
1330                         VecSubf(&cr_deltas[i].x, me->mvert[i].co, cr_lvl->verts[i].co);
1331         }
1332         
1333         /* Faces -- find whether flag/mat has changed */
1334         cr_flag_damaged= MEM_callocN(sizeof(char)*cr_lvl->totface, "flag_damaged 1");
1335         cr_mat_damaged= MEM_callocN(sizeof(char)*cr_lvl->totface, "mat_damaged 1");
1336         if(em) efa= em->faces.first;
1337         for(i=0; i<cr_lvl->totface; ++i) {
1338                 if(cr_lvl->faces[i].flag != (em ? efa->flag : me->mface[i].flag))
1339                         cr_flag_damaged[i]= 1;
1340                 if(cr_lvl->faces[i].mat_nr != (em ? efa->mat_nr : me->mface[i].mat_nr))
1341                         cr_mat_damaged[i]= 1;
1342                 if(em) efa= efa->next;
1343         }
1344         or_flag_damaged= MEM_dupallocN(cr_flag_damaged);
1345         or_mat_damaged= MEM_dupallocN(cr_mat_damaged);
1346
1347         /* Update current level -- copy current mesh into current level */
1348         if(em) {
1349                 eve= em->verts.first;
1350                 efa= em->faces.first;
1351         }
1352         for(i=0; i<cr_lvl->totvert; ++i) {
1353                 multires_get_vert(&cr_lvl->verts[i], eve, &me->mvert[i], i);
1354                 if(em) eve= eve->next;
1355         }
1356         for(i=0; i<cr_lvl->totface; ++i) {
1357                 cr_lvl->faces[i].flag= em ? efa->flag : me->mface[i].flag;
1358                 cr_lvl->faces[i].mat_nr= em ? efa->mat_nr : me->mface[i].mat_nr;
1359                 if(em) efa= efa->next;
1360         }
1361
1362         /* Update higher levels */
1363         pr_lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1364         cr_lvl= pr_lvl->next;
1365         while(cr_lvl) {
1366                 /* Set up new deltas, but keep the ones from the previous level */
1367                 if(pr_deltas) MEM_freeN(pr_deltas);
1368                 pr_deltas= cr_deltas;
1369                 cr_deltas= MEM_callocN(sizeof(vec3f)*cr_lvl->totvert,"deltas");
1370                 if(pr_flag_damaged) MEM_freeN(pr_flag_damaged);
1371                 pr_flag_damaged= cr_flag_damaged;
1372                 cr_flag_damaged= MEM_callocN(sizeof(char)*cr_lvl->totface,"flag_damaged 2");
1373                 if(pr_mat_damaged) MEM_freeN(pr_mat_damaged);
1374                 pr_mat_damaged= cr_mat_damaged;
1375                 cr_mat_damaged= MEM_callocN(sizeof(char)*cr_lvl->totface,"mat_damaged 2");
1376
1377                 /* Calculate and add new deltas
1378                    ============================*/
1379                 for(i=0; i<pr_lvl->totface; ++i) {
1380                         const MultiresFace *f= &pr_lvl->faces[i];
1381                         data.corner1= &pr_deltas[f->v[0]].x;
1382                         data.corner2= &pr_deltas[f->v[1]].x;
1383                         data.corner3= &pr_deltas[f->v[2]].x;
1384                         data.corner4= &pr_deltas[f->v[3]].x;
1385                         data.quad= f->v[3] ? 1 : 0;
1386                         multi_apply(&cr_deltas[f->mid].x, &data, 3, catmullclark_smooth_face);
1387
1388                         VecAddf(cr_lvl->verts[f->mid].co,
1389                                 cr_lvl->verts[f->mid].co,
1390                                 &cr_deltas[f->mid].x);
1391                         
1392                         cr_lvl->verts[f->mid].flag= 0;
1393                         for(j=0; j<(data.quad?4:3); ++j) {
1394                                 if(pr_lvl->verts[f->v[j]].flag & 1)
1395                                         cr_lvl->verts[f->mid].flag |= 1;
1396                                 if(pr_lvl->verts[f->v[j]].flag & ME_HIDE)
1397                                         cr_lvl->verts[f->mid].flag |= ME_HIDE;
1398                         }
1399                 }
1400
1401                 for(i=0; i<pr_lvl->totedge; ++i) {
1402                         const MultiresEdge *e= &pr_lvl->edges[i];
1403                         data.boundary= multires_edge_is_boundary(pr_lvl,i);
1404                         edge_face_neighbor_midpoints_accum(&data,pr_lvl,cr_deltas,sizeof(vec3f),e);
1405                         data.endpoint1= &pr_deltas[e->v[0]].x;
1406                         data.endpoint2= &pr_deltas[e->v[1]].x;
1407                         multi_apply(&cr_deltas[e->mid].x, &data, 3, catmullclark_smooth_edge);
1408                         
1409                         cr_lvl->verts[e->mid].flag= 0;
1410                         for(j=0; j<2; ++j) {
1411                                 if(pr_lvl->verts[e->v[j]].flag & 1)
1412                                         cr_lvl->verts[e->mid].flag |= 1;
1413                                 if(pr_lvl->verts[e->v[j]].flag & ME_HIDE)
1414                                         cr_lvl->verts[e->mid].flag |= ME_HIDE;
1415                         }
1416                 }
1417                 for(i=0; i<pr_lvl->totedge; ++i) {
1418                         const unsigned ndx= pr_lvl->edges[i].mid;
1419                         VecAddf(cr_lvl->verts[ndx].co,
1420                                 cr_lvl->verts[ndx].co,
1421                                 &cr_deltas[ndx].x);
1422                 }
1423
1424                 for(i=0; i<pr_lvl->totvert; ++i) {
1425                         data.boundary= multires_vert_is_boundary(pr_lvl,i);
1426                         data.original= &pr_deltas[i].x;
1427                         data.edge_count= BLI_countlist(&pr_lvl->vert_edge_map[i]);
1428                         if(data.boundary)
1429                                 boundary_edges_average(&data,pr_lvl,pr_deltas,sizeof(vec3f),i);
1430                         else {
1431                                 vert_face_neighbor_midpoints_average(&data,pr_lvl,cr_deltas,sizeof(vec3f),i);
1432                                 vert_edge_neighbor_midpoints_average(&data,pr_lvl,pr_deltas,sizeof(vec3f),i);
1433                         }
1434                         multi_apply(&cr_deltas[i].x, &data, 3, catmullclark_smooth_vert);
1435                         cr_lvl->verts[i].flag= 0;
1436                         if(pr_lvl->verts[i].flag & 1) cr_lvl->verts[i].flag |= 1;
1437                         if(pr_lvl->verts[i].flag & ME_HIDE) cr_lvl->verts[i].flag |= ME_HIDE;
1438                 }
1439                 for(i=0; i<pr_lvl->totvert; ++i) {
1440                         VecAddf(cr_lvl->verts[i].co,
1441                                 cr_lvl->verts[i].co,
1442                                 &cr_deltas[i].x);
1443                 }
1444
1445                 /* Update faces */
1446                 curf= 0;
1447                 for(i=0; i<pr_lvl->totface; ++i) {
1448                         const int sides= cr_lvl->prev->faces[i].v[3] ? 4 : 3;
1449                         for(j=0; j<sides; ++j) {
1450                                 if(pr_flag_damaged[i]) {
1451                                         cr_lvl->faces[curf].flag= pr_lvl->faces[i].flag;
1452                                         cr_flag_damaged[curf]= 1;
1453                                 }
1454                                 if(pr_mat_damaged[i]) {
1455                                         cr_lvl->faces[curf].mat_nr= pr_lvl->faces[i].mat_nr;
1456                                         cr_mat_damaged[curf]= 1;
1457                                 }
1458                                 ++curf;
1459                         }
1460                 }
1461
1462                 pr_lvl= pr_lvl->next;
1463                 cr_lvl= cr_lvl->next;
1464         }
1465         if(pr_deltas) MEM_freeN(pr_deltas);
1466         if(cr_deltas) MEM_freeN(cr_deltas);
1467
1468         /* Update lower levels */
1469         cr_lvl= me->mr->levels.last;
1470         cr_lvl= cr_lvl->prev;
1471         /* Update Verts */
1472         while(cr_lvl) {
1473                 for(i=0; i<cr_lvl->totvert; ++i)
1474                         cr_lvl->verts[i]= cr_lvl->next->verts[i];
1475                 cr_lvl= cr_lvl->prev;
1476         }
1477         
1478         /* Update Faces */
1479         
1480         /* Clear to original damages */
1481         if(cr_flag_damaged) MEM_freeN(cr_flag_damaged);
1482         if(cr_mat_damaged) MEM_freeN(cr_mat_damaged);
1483         cr_flag_damaged= or_flag_damaged;
1484         cr_mat_damaged= or_mat_damaged;
1485         
1486         cr_lvl= or_lvl->prev;
1487         while(cr_lvl) {
1488                 if(pr_flag_damaged) MEM_freeN(pr_flag_damaged);
1489                 pr_flag_damaged= cr_flag_damaged;
1490                 cr_flag_damaged= MEM_callocN(sizeof(char)*cr_lvl->totface,"flag_damaged 3");
1491                 if(pr_mat_damaged) MEM_freeN(pr_mat_damaged);
1492                 pr_mat_damaged= cr_mat_damaged;
1493                 cr_mat_damaged= MEM_callocN(sizeof(char)*cr_lvl->totface,"mat_damaged 3");
1494
1495                 /* Update faces */
1496                 curf= 0;
1497                 for(i=0; i<cr_lvl->totface; ++i) {
1498                         const int sides= cr_lvl->faces[i].v[3] ? 4 : 3;
1499                         
1500                         /* Check damages */
1501                         for(j=0; j<sides; ++j, ++curf) {
1502                                 if(pr_flag_damaged[curf]) {
1503                                         cr_lvl->faces[i].flag= cr_lvl->next->faces[curf].flag;
1504                                         cr_flag_damaged[i]= 1;
1505                                 }
1506                                 if(pr_mat_damaged[curf]) {
1507                                         cr_lvl->faces[i].mat_nr= cr_lvl->next->faces[curf].mat_nr;
1508                                         cr_mat_damaged[i]= 1;
1509                                 }
1510                         }
1511                 }
1512
1513                 cr_lvl= cr_lvl->prev;
1514         }
1515
1516         if(pr_flag_damaged) MEM_freeN(pr_flag_damaged);
1517         if(cr_flag_damaged) MEM_freeN(cr_flag_damaged);
1518         if(pr_mat_damaged) MEM_freeN(pr_mat_damaged);
1519         if(cr_mat_damaged) MEM_freeN(cr_mat_damaged);
1520
1521         multires_update_colors(me);
1522
1523 }
1524
1525 void multires_calc_level_maps(MultiresLevel *lvl)
1526 {
1527         unsigned i,j;
1528         MultiresMapNode *indexnode= NULL;
1529         
1530         lvl->map_mem= MEM_mallocN(sizeof(MultiresMapNode)*(lvl->totedge*2 + lvl->totface*4), "map_mem");
1531         indexnode= lvl->map_mem;
1532         
1533         lvl->vert_edge_map= MEM_callocN(sizeof(ListBase)*lvl->totvert,"vert_edge_map");
1534         for(i=0; i<lvl->totedge; ++i) {
1535                 for(j=0; j<2; ++j, ++indexnode) {
1536                         indexnode->Index= i;
1537                         BLI_addtail(&lvl->vert_edge_map[lvl->edges[i].v[j]], indexnode);
1538                 }
1539         }
1540
1541         lvl->vert_face_map= MEM_callocN(sizeof(ListBase)*lvl->totvert,"vert_face_map");
1542         for(i=0; i<lvl->totface; ++i){
1543                 for(j=0; j<(lvl->faces[i].v[3]?4:3); ++j, ++indexnode) {
1544                         indexnode->Index= i;
1545                         BLI_addtail(&lvl->vert_face_map[lvl->faces[i].v[j]], indexnode);
1546                 }
1547         }
1548 }
1549
1550 void multires_edge_level_update(void *ob, void *me_v)
1551 {
1552         if(!G.obedit) {
1553                 Mesh *me= me_v;
1554                 MultiresLevel *cr_lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1555                 MultiresLevel *edge_lvl= BLI_findlink(&me->mr->levels,me->mr->edgelvl-1);
1556                 const int threshold= edge_lvl->totedge * powf(2, me->mr->current - me->mr->edgelvl);
1557                 unsigned i;
1558
1559                 for(i=0; i<cr_lvl->totedge; ++i) {
1560                         const int ndx= me->pv ? me->pv->edge_map[i] : i;
1561                         if(ndx != -1) { /* -1= hidden edge */
1562                                 if(me->mr->edgelvl >= me->mr->current || i<threshold)
1563                                         me->medge[ndx].flag |= ME_EDGEDRAW;
1564                                 else
1565                                         me->medge[ndx].flag &= ~ME_EDGEDRAW;
1566                         }
1567                 }
1568
1569                 allqueue(REDRAWVIEW3D, 0);
1570         }
1571 }
1572
1573 int multires_modifier_warning()
1574 {
1575         ModifierData *md;
1576         
1577         for(md= modifiers_getVirtualModifierList(OBACT); md; md= md->next) {
1578                 if(md->mode & eModifierMode_Render) {
1579                         switch(md->type) {
1580                         case eModifierType_Subsurf:
1581                         case eModifierType_Build:
1582                         case eModifierType_Mirror:
1583                         case eModifierType_Decimate:
1584                         case eModifierType_Boolean:
1585                         case eModifierType_Array:
1586                         case eModifierType_EdgeSplit:
1587                                 return 1;
1588                         }
1589                 }
1590         }
1591         
1592         return 0;
1593 }