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