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