== Multires ==
[blender.git] / source / blender / blenkernel / intern / multires.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software  Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2007 by Nicholas Bishop
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 #include "MEM_guardedalloc.h"
31
32 #include "DNA_key_types.h"
33 #include "DNA_mesh_types.h"
34 #include "DNA_meshdata_types.h"
35 #include "DNA_object_types.h"
36 #include "DNA_vec_types.h"
37
38 #include "BDR_sculptmode.h"
39
40 #include "BIF_editmesh.h"
41
42 #include "BLI_arithb.h"
43 #include "BLI_blenlib.h"
44 #include "BLI_editVert.h"
45
46 #include "BKE_customdata.h"
47 #include "BKE_depsgraph.h"
48 #include "BKE_global.h"
49 #include "BKE_multires.h"
50
51 #include "blendef.h"
52 #include "editmesh.h"
53
54 #include <math.h>
55
56 /* Returns the active multires level (currently applied to the mesh) */
57 MultiresLevel *current_level(Multires *mr)
58 {
59         return BLI_findlink(&mr->levels, mr->current - 1);
60 }
61
62 /* Returns the nth multires level, starting at 1 */
63 MultiresLevel *multires_level_n(Multires *mr, int n)
64 {
65         if(mr)
66                 return BLI_findlink(&mr->levels, n - 1);
67         else
68                 return NULL;
69 }
70
71 /* Free and clear the temporary connectivity data */
72 static void multires_free_temp_data(MultiresLevel *lvl)
73 {
74         if(lvl) {
75                 if(lvl->edge_boundary_states) MEM_freeN(lvl->edge_boundary_states);
76                 if(lvl->vert_edge_map) MEM_freeN(lvl->vert_edge_map);
77                 if(lvl->vert_face_map) MEM_freeN(lvl->vert_face_map);
78                 if(lvl->map_mem) MEM_freeN(lvl->map_mem);
79
80                 lvl->edge_boundary_states = NULL;
81                 lvl->vert_edge_map = lvl->vert_face_map = NULL;
82                 lvl->map_mem = NULL;
83         }
84 }
85
86 /* Does not actually free lvl itself */
87 void multires_free_level(MultiresLevel *lvl)
88 {
89         if(lvl) {
90                 if(lvl->faces) MEM_freeN(lvl->faces);
91                 if(lvl->edges) MEM_freeN(lvl->edges);
92                 if(lvl->colfaces) MEM_freeN(lvl->colfaces);
93                 
94                 multires_free_temp_data(lvl);
95         }
96 }
97
98 void multires_free(Multires *mr)
99 {
100         if(mr) {
101                 MultiresLevel* lvl= mr->levels.first;
102
103                 /* Free the first-level data */
104                 if(lvl) {
105                         CustomData_free(&mr->vdata, lvl->totvert);
106                         CustomData_free(&mr->fdata, lvl->totface);
107                         MEM_freeN(mr->edge_flags);
108                         MEM_freeN(mr->edge_creases);
109                 }
110
111                 while(lvl) {
112                         multires_free_level(lvl);                       
113                         lvl= lvl->next;
114                 }
115
116                 MEM_freeN(mr->verts);
117
118                 BLI_freelistN(&mr->levels);
119
120                 MEM_freeN(mr);
121         }
122 }
123
124 static MultiresLevel *multires_level_copy(MultiresLevel *orig)
125 {
126         if(orig) {
127                 MultiresLevel *lvl= MEM_dupallocN(orig);
128                 
129                 lvl->next= lvl->prev= NULL;
130                 lvl->faces= MEM_dupallocN(orig->faces);
131                 lvl->colfaces= MEM_dupallocN(orig->colfaces);
132                 lvl->edges= MEM_dupallocN(orig->edges);
133                 lvl->edge_boundary_states = NULL;
134                 lvl->vert_edge_map= lvl->vert_face_map= NULL;
135                 lvl->map_mem= NULL;
136                 
137                 return lvl;
138         }
139         return NULL;
140 }
141
142 Multires *multires_copy(Multires *orig)
143 {
144         const CustomDataMask vdata_mask= CD_MASK_MDEFORMVERT;
145
146         if(orig) {
147                 Multires *mr= MEM_dupallocN(orig);
148                 MultiresLevel *lvl;
149                 
150                 mr->levels.first= mr->levels.last= NULL;
151                 
152                 for(lvl= orig->levels.first; lvl; lvl= lvl->next)
153                         BLI_addtail(&mr->levels, multires_level_copy(lvl));
154
155                 mr->verts= MEM_dupallocN(orig->verts);
156                 
157                 lvl= mr->levels.first;
158                 if(lvl) {
159                         CustomData_copy(&orig->vdata, &mr->vdata, vdata_mask, CD_DUPLICATE, lvl->totvert);
160                         CustomData_copy(&orig->fdata, &mr->fdata, CD_MASK_MTFACE, CD_DUPLICATE, lvl->totface);
161                         mr->edge_flags= MEM_dupallocN(orig->edge_flags);
162                         mr->edge_creases= MEM_dupallocN(orig->edge_creases);
163                 }
164                 
165                 return mr;
166         }
167         return NULL;
168 }
169
170 static void multires_get_vert(MVert *out, EditVert *eve, MVert *m, int i)
171 {
172         if(eve) {
173                 VecCopyf(out->co, eve->co);
174                 out->flag= 0;
175                 if(eve->f & SELECT) out->flag |= 1;
176                 if(eve->h) out->flag |= ME_HIDE;
177                 eve->tmp.l= i;
178         }
179         else
180                 *out= *m;
181 }
182
183 void eed_to_medge_flag(EditEdge *eed, short *flag, char *crease)
184 {
185         if(!eed || !flag) return;
186
187         /* Would be nice if EditMesh edge flags could be unified with Mesh flags! */
188         *flag= (eed->f & SELECT) | ME_EDGERENDER;
189         if(eed->f2<2) *flag |= ME_EDGEDRAW;
190         if(eed->f2==0) *flag |= ME_LOOSEEDGE;
191         if(eed->sharp) *flag |= ME_SHARP;
192         if(eed->seam) *flag |= ME_SEAM;
193         if(eed->h & EM_FGON) *flag |= ME_FGON;
194         if(eed->h & 1) *flag |= ME_HIDE;
195         
196         *crease= (char)(255.0*eed->crease);
197 }
198
199 static void multires_get_edge(MultiresEdge *e, EditEdge *eed, MEdge *m, short *flag, char *crease)
200 {
201         if(eed) {
202                 e->v[0]= eed->v1->tmp.l;
203                 e->v[1]= eed->v2->tmp.l;
204                 eed_to_medge_flag(eed, flag, crease);
205         } else {                
206                 e->v[0]= m->v1;
207                 e->v[1]= m->v2;
208                 *flag= m->flag;
209                 *crease= m->crease;
210         }
211 }
212
213 static void multires_get_face(MultiresFace *f, EditFace *efa, MFace *m)
214 {
215         if(efa) {
216                 MFace tmp;
217                 int j;
218                 tmp.v1= efa->v1->tmp.l;
219                 tmp.v2= efa->v2->tmp.l;
220                 tmp.v3= efa->v3->tmp.l;
221                 tmp.v4= 0;
222                 if(efa->v4) tmp.v4= efa->v4->tmp.l;
223                 test_index_face(&tmp, NULL, 0, efa->v4?4:3);
224                 for(j=0; j<4; ++j) f->v[j]= (&tmp.v1)[j];
225
226                 /* Flags */
227                 f->flag= efa->flag;
228                 if(efa->f & 1) f->flag |= ME_FACE_SEL;
229                 else f->flag &= ~ME_FACE_SEL;
230                 if(efa->h) f->flag |= ME_HIDE;
231                 f->mat_nr= efa->mat_nr;
232         } else {                
233                 f->v[0]= m->v1;
234                 f->v[1]= m->v2;
235                 f->v[2]= m->v3;
236                 f->v[3]= m->v4;
237                 f->flag= m->flag;
238                 f->mat_nr= m->mat_nr;
239         }
240 }
241
242 /* For manipulating vertex colors / uvs */
243 static void mcol_to_multires(MultiresColFace *mrf, MCol *mcol)
244 {
245         char i;
246         for(i=0; i<4; ++i) {
247                 mrf->col[i].a= mcol[i].a;
248                 mrf->col[i].r= mcol[i].r;
249                 mrf->col[i].g= mcol[i].g;
250                 mrf->col[i].b= mcol[i].b;
251         }
252 }
253
254 /* 1 <= count <= 4 */
255 static void multires_col_avg(MultiresCol *avg, MultiresCol cols[4], char count)
256 {
257         unsigned i;
258         avg->a= avg->r= avg->g= avg->b= 0;
259         for(i=0; i<count; ++i) {
260                 avg->a+= cols[i].a;
261                 avg->r+= cols[i].r;
262                 avg->g+= cols[i].g;
263                 avg->b+= cols[i].b;
264         }
265         avg->a/= count;
266         avg->r/= count;
267         avg->g/= count;
268         avg->b/= count;
269 }
270
271 static void multires_col_avg2(MultiresCol *avg, MultiresCol *c1, MultiresCol *c2)
272 {
273         MultiresCol in[2];
274         in[0]= *c1;
275         in[1]= *c2;
276         multires_col_avg(avg,in,2);
277 }
278
279 void multires_load_cols(Mesh *me)
280 {
281         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1), *cur;
282         EditMesh *em= G.obedit ? G.editMesh : NULL;
283         CustomData *src= em ? &em->fdata : &me->fdata;
284         EditFace *efa= NULL;
285         unsigned i,j;
286
287         if(!CustomData_has_layer(src, CD_MCOL) && !CustomData_has_layer(src, CD_MTFACE)) return;
288
289         /* Add texcol data */
290         for(cur= me->mr->levels.first; cur; cur= cur->next)
291                 if(!cur->colfaces)
292                         cur->colfaces= MEM_callocN(sizeof(MultiresColFace)*cur->totface,"ColFaces");
293
294         me->mr->use_col= CustomData_has_layer(src, CD_MCOL);
295
296         if(em) efa= em->faces.first;
297         for(i=0; i<lvl->totface; ++i) {
298                 MultiresColFace *f= &lvl->colfaces[i];
299
300                 if(me->mr->use_col)
301                         mcol_to_multires(f, em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4]);
302                 
303                 if(em) efa= efa->next;
304         }
305
306         /* Update higher levels */
307         lvl= lvl->next;
308         while(lvl) {
309                 MultiresColFace *cf= lvl->colfaces;
310                 for(i=0; i<lvl->prev->totface; ++i) {
311                         const char sides= lvl->prev->faces[i].v[3]?4:3;
312                         MultiresCol cntr;
313                         
314                         /* Find average color of 4 (or 3 for triangle) verts */
315                         multires_col_avg(&cntr,lvl->prev->colfaces[i].col,sides);
316                         
317                         for(j=0; j<sides; ++j) {
318                                 MultiresColFace *pf= &lvl->prev->colfaces[i];
319
320                                 multires_col_avg2(&cf->col[0],
321                                                   &pf->col[j],
322                                                   &pf->col[j==0?sides-1:j-1]);
323                                 cf->col[1]= pf->col[j];
324                                 multires_col_avg2(&cf->col[2],
325                                                   &pf->col[j],
326                                                   &pf->col[j==sides-1?0:j+1]);
327                                 cf->col[3]= cntr;
328                                 
329                                 ++cf;
330                         }
331                 }
332                 lvl= lvl->next;
333         }
334
335         /* Update lower levels */
336         lvl= me->mr->levels.last;
337         lvl= lvl->prev;
338         while(lvl) {
339                 unsigned curf= 0;
340                 for(i=0; i<lvl->totface; ++i) {
341                         MultiresFace *f= &lvl->faces[i];
342                         for(j=0; j<(f->v[3]?4:3); ++j) {
343                                 lvl->colfaces[i].col[j]= lvl->next->colfaces[curf].col[1];
344                                 ++curf;
345                         }
346                 }
347                 lvl= lvl->prev;
348         }
349 }
350
351 void multires_create(Mesh *me)
352 {
353         MultiresLevel *lvl;
354         EditMesh *em= G.obedit ? G.editMesh : NULL;
355         EditVert *eve= NULL;
356         EditFace *efa= NULL;
357         EditEdge *eed= NULL;
358         int i;
359         
360         lvl= MEM_callocN(sizeof(MultiresLevel), "multires level");
361
362         if(me->pv) sculptmode_pmv_off(me);
363
364         me->mr= MEM_callocN(sizeof(Multires), "multires data");
365         
366         BLI_addtail(&me->mr->levels,lvl);
367         me->mr->current= 1;
368         me->mr->level_count= 1;
369         me->mr->edgelvl= 1;
370         me->mr->pinlvl= 1;
371         me->mr->renderlvl= 1;
372         
373         /* Load mesh (or editmesh) into multires data */
374
375         /* Load vertices and vdata (MDeformVerts) */
376         lvl->totvert= em ? BLI_countlist(&em->verts) : me->totvert;
377         me->mr->verts= MEM_callocN(sizeof(MVert)*lvl->totvert,"multires verts");
378         multires_update_customdata(me->mr->levels.first, em ? &em->vdata : &me->vdata,
379                                    &me->mr->vdata, CD_MDEFORMVERT);
380         if(em) eve= em->verts.first;
381         for(i=0; i<lvl->totvert; ++i) {
382                 multires_get_vert(&me->mr->verts[i], eve, &me->mvert[i], i);
383                 if(em) eve= eve->next;
384         }
385
386         /* Load faces and fdata (MTFaces) */
387         lvl->totface= em ? BLI_countlist(&em->faces) : me->totface;
388         lvl->faces= MEM_callocN(sizeof(MultiresFace)*lvl->totface,"multires faces");
389         multires_update_customdata(me->mr->levels.first, em ? &em->fdata : &me->fdata,
390                                    &me->mr->fdata, CD_MTFACE);
391         if(em) efa= em->faces.first;
392         for(i=0; i<lvl->totface; ++i) {
393                 multires_get_face(&lvl->faces[i], efa, &me->mface[i]);
394                 if(em) efa= efa->next;
395         }
396
397         /* Load edges and edge_flags */
398         lvl->totedge= em ? BLI_countlist(&em->edges) : me->totedge;
399         lvl->edges= MEM_callocN(sizeof(MultiresEdge)*lvl->totedge,"multires edges");
400         me->mr->edge_flags= MEM_callocN(sizeof(short)*lvl->totedge, "multires edge flags");
401         me->mr->edge_creases= MEM_callocN(sizeof(short)*lvl->totedge, "multires edge creases");
402         if(em) eed= em->edges.first;
403         for(i=0; i<lvl->totedge; ++i) {
404                 multires_get_edge(&lvl->edges[i], eed, &me->medge[i], &me->mr->edge_flags[i], &me->mr->edge_creases[i]);
405                 if(em) eed= eed->next;
406         }
407
408         multires_load_cols(me);
409 }
410
411 typedef struct MultiresMapNode {
412         struct MultiresMapNode *next, *prev;
413         unsigned Index;
414 } MultiresMapNode;
415
416 /* Produces temporary connectivity data for the multires lvl */
417 static void multires_calc_temp_data(MultiresLevel *lvl)
418 {
419         unsigned i, j, emax;
420         MultiresMapNode *indexnode= NULL;
421
422         lvl->map_mem= MEM_mallocN(sizeof(MultiresMapNode)*(lvl->totedge*2 + lvl->totface*4), "map_mem");
423         indexnode= lvl->map_mem;
424         
425         /* edge map */
426         lvl->vert_edge_map= MEM_callocN(sizeof(ListBase)*lvl->totvert,"vert_edge_map");
427         for(i=0; i<lvl->totedge; ++i) {
428                 for(j=0; j<2; ++j, ++indexnode) {
429                         indexnode->Index= i;
430                         BLI_addtail(&lvl->vert_edge_map[lvl->edges[i].v[j]], indexnode);
431                 }
432         }
433
434         /* face map */
435         lvl->vert_face_map= MEM_callocN(sizeof(ListBase)*lvl->totvert,"vert_face_map");
436         for(i=0; i<lvl->totface; ++i){
437                 for(j=0; j<(lvl->faces[i].v[3]?4:3); ++j, ++indexnode) {
438                         indexnode->Index= i;
439                         BLI_addtail(&lvl->vert_face_map[lvl->faces[i].v[j]], indexnode);
440                 }
441         }
442
443         /* edge boundaries */
444         emax = (lvl->prev ? (lvl->prev->totedge * 2) : lvl->totedge);
445         lvl->edge_boundary_states= MEM_callocN(sizeof(char)*lvl->totedge, "edge_boundary_states");
446         for(i=0; i<emax; ++i) {
447                 MultiresMapNode *n1= lvl->vert_face_map[lvl->edges[i].v[0]].first;
448                 unsigned total= 0;
449                 
450                 lvl->edge_boundary_states[i] = 1;
451                 while(n1 && lvl->edge_boundary_states[i] == 1) {
452                         MultiresMapNode *n2= lvl->vert_face_map[lvl->edges[i].v[1]].first;
453                         while(n2) {
454                                 if(n1->Index == n2->Index) {
455                                         ++total;
456                                         
457                                         if(total > 1) {
458                                                 lvl->edge_boundary_states[i] = 0;
459                                                 break;
460                                         }
461                                 }
462                                 
463                                 n2= n2->next;
464                         }
465                         n1= n1->next;
466                 }
467         }
468 }
469
470 /* CATMULL-CLARK
471    ============= */
472
473 typedef struct MultiApplyData {
474         /* Smooth faces */
475         float *corner1, *corner2, *corner3, *corner4;
476         char quad;
477
478         /* Smooth edges */
479         char boundary;
480         float edge_face_neighbor_midpoints_accum[3];
481         unsigned edge_face_neighbor_midpoints_total;
482         float *endpoint1, *endpoint2;
483
484         /* Smooth verts */
485         /* uses 'char boundary' */
486         float *original;
487         int edge_count;
488         float vert_face_neighbor_midpoints_average[3];
489         float vert_edge_neighbor_midpoints_average[3];
490         float boundary_edges_average[3];
491 } MultiApplyData;
492
493 /* Simply averages the four corners of a polygon. */
494 static float catmullclark_smooth_face(MultiApplyData *data, const unsigned i)
495 {
496         const float total= data->corner1[i]+data->corner2[i]+data->corner3[i];
497         return data->quad ? (total+data->corner4[i])/4 : total/3;
498 }
499
500 static float catmullclark_smooth_edge(MultiApplyData *data, const unsigned i)
501 {
502         float accum= 0;
503         unsigned count= 2;
504
505         accum+= data->endpoint1[i] + data->endpoint2[i];
506
507         if(!data->boundary) {
508                 accum+= data->edge_face_neighbor_midpoints_accum[i];
509                 count+= data->edge_face_neighbor_midpoints_total;
510         }
511
512         return accum / count;
513 }
514
515 static float catmullclark_smooth_vert(MultiApplyData *data, const unsigned i)
516 {
517         if(data->boundary) {
518                 return data->original[i]*0.75 + data->boundary_edges_average[i]*0.25;
519         } else {
520                 return (data->vert_face_neighbor_midpoints_average[i] +
521                         2*data->vert_edge_neighbor_midpoints_average[i] +
522                         data->original[i]*(data->edge_count-3))/data->edge_count;
523         }
524 }
525
526
527
528 /* Call func count times, passing in[i] as the input and storing the output in out[i] */
529 static void multi_apply(float *out, MultiApplyData *data,
530                  const unsigned count, float (*func)(MultiApplyData *, const unsigned))
531 {
532         unsigned i;
533         for(i=0; i<count; ++i)
534                 out[i]= func(data,i);
535 }
536
537 static short multires_vert_is_boundary(MultiresLevel *lvl, unsigned v)
538 {
539         MultiresMapNode *node= lvl->vert_edge_map[v].first;
540         while(node) {
541                 if(lvl->edge_boundary_states[node->Index])
542                         return 1;
543                 node= node->next;
544         }
545         return 0;
546 }
547
548 #define GET_FLOAT(array, i, j, stride) (((float*)((char*)(array)+((i)*(stride))))[(j)])
549
550 static void edge_face_neighbor_midpoints_accum(MultiApplyData *data, MultiresLevel *lvl,
551                                               void *array, const char stride, const MultiresEdge *e)
552 {
553         ListBase *neighbors1= &lvl->vert_face_map[e->v[0]];
554         ListBase *neighbors2= &lvl->vert_face_map[e->v[1]];
555         MultiresMapNode *n1, *n2;
556         unsigned j,count= 0;
557         float *out= data->edge_face_neighbor_midpoints_accum;
558         
559         out[0]=out[1]=out[2]= 0;
560
561         for(n1= neighbors1->first; n1; n1= n1->next) {
562                 for(n2= neighbors2->first; n2; n2= n2->next) {
563                         if(n1->Index == n2->Index) {
564                                 for(j=0; j<3; ++j)
565                                         out[j]+= GET_FLOAT(array,lvl->faces[n1->Index].mid,j,stride);
566                                 ++count;
567                         }
568                 }
569         }
570
571         data->edge_face_neighbor_midpoints_total= count;
572 }
573
574 static void vert_face_neighbor_midpoints_average(MultiApplyData *data, MultiresLevel *lvl,
575                                                  void *array, const char stride, const unsigned i)
576 {
577         ListBase *neighbors= &lvl->vert_face_map[i];
578         MultiresMapNode *n1;
579         unsigned j,count= 0;
580         float *out= data->vert_face_neighbor_midpoints_average;
581
582         out[0]=out[1]=out[2]= 0;
583
584         for(n1= neighbors->first; n1; n1= n1->next) {
585                 for(j=0; j<3; ++j)
586                         out[j]+= GET_FLOAT(array,lvl->faces[n1->Index].mid,j,stride);
587                 ++count;
588         }
589         for(j=0; j<3; ++j) out[j]/= count;
590 }
591
592 static void vert_edge_neighbor_midpoints_average(MultiApplyData *data, MultiresLevel *lvl,
593                                                  void *array, const char stride, const unsigned i)
594 {
595         ListBase *neighbors= &lvl->vert_edge_map[i];
596         MultiresMapNode *n1;
597         unsigned j,count= 0;
598         float *out= data->vert_edge_neighbor_midpoints_average;
599
600         out[0]=out[1]=out[2]= 0;
601
602         for(n1= neighbors->first; n1; n1= n1->next) {
603                 for(j=0; j<3; ++j)
604                         out[j]+= (GET_FLOAT(array,lvl->edges[n1->Index].v[0],j,stride) +
605                                   GET_FLOAT(array,lvl->edges[n1->Index].v[1],j,stride)) / 2;
606                 ++count;
607         }
608         for(j=0; j<3; ++j) out[j]/= count;
609 }
610
611 static void boundary_edges_average(MultiApplyData *data, MultiresLevel *lvl,
612                                    void *array, const char stride, const unsigned i)
613 {
614         ListBase *neighbors= &lvl->vert_edge_map[i];
615         MultiresMapNode *n1;
616         unsigned j,count= 0;
617         float *out= data->boundary_edges_average;
618
619         out[0]=out[1]=out[2]= 0;
620         
621         for(n1= neighbors->first; n1; n1= n1->next) {
622                 const MultiresEdge *e= &lvl->edges[n1->Index];
623                 const unsigned end= e->v[0]==i ? e->v[1] : e->v[0];
624                 
625                 if(lvl->edge_boundary_states[n1->Index]) {
626                         for(j=0; j<3; ++j)
627                                 out[j]+= GET_FLOAT(array,end,j,stride);
628                         ++count;
629                 }
630         }
631         for(j=0; j<3; ++j) out[j]/= count;
632 }
633
634 /* END CATMULL-CLARK
635    ================= */
636
637 /* Update vertex locations and vertex flags */
638 static void multires_update_vertices(Mesh *me, EditMesh *em)
639 {
640         MultiresLevel *cr_lvl= current_level(me->mr), *pr_lvl= NULL,
641                       *last_lvl= me->mr->levels.last;
642         vec3f *pr_deltas= NULL, *cr_deltas= NULL, *swap_deltas= NULL;
643         EditVert *eve= NULL;
644         MultiApplyData data;
645         int i, j;
646
647         /* Prepare deltas */
648         pr_deltas= MEM_callocN(sizeof(vec3f)*last_lvl->totvert, "multires deltas 1");
649         cr_deltas= MEM_callocN(sizeof(vec3f)*last_lvl->totvert, "multires deltas 2");
650
651         /* Calculate initial deltas -- current mesh subtracted from current level*/
652         if(em) eve= em->verts.first;
653         for(i=0; i<cr_lvl->totvert; ++i) {
654                 if(em) {
655                         VecSubf(&cr_deltas[i].x, eve->co, me->mr->verts[i].co);
656                         eve= eve->next;
657                 } else
658                         VecSubf(&cr_deltas[i].x, me->mvert[i].co, me->mr->verts[i].co);
659         }
660
661
662         /* Copy current level's vertex flags and clear the rest */
663         if(em) eve= em->verts.first;    
664         for(i=0; i < last_lvl->totvert; ++i) {
665                 if(i < cr_lvl->totvert) {
666                         MVert mvflag;
667                         multires_get_vert(&mvflag, eve, &me->mvert[i], i);
668                         if(em) eve= eve->next;
669                         me->mr->verts[i].flag= mvflag.flag;
670                 }
671                 else
672                         me->mr->verts[i].flag= 0;
673         }
674
675         /* If already on the highest level, copy current verts (including flags) into current level */
676         if(cr_lvl == last_lvl) {
677                 if(em)
678                         eve= em->verts.first;
679                 for(i=0; i<cr_lvl->totvert; ++i) {
680                         multires_get_vert(&me->mr->verts[i], eve, &me->mvert[i], i);
681                         if(em) eve= eve->next;
682                 }
683         }
684
685         /* Update higher levels */
686         pr_lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
687         cr_lvl= pr_lvl->next;
688         while(cr_lvl) {
689                 multires_calc_temp_data(pr_lvl);                
690
691                 /* Swap the old/new deltas */
692                 swap_deltas= pr_deltas;
693                 pr_deltas= cr_deltas;
694                 cr_deltas= swap_deltas;
695
696                 /* Calculate and add new deltas
697                    ============================ */
698                 for(i=0; i<pr_lvl->totface; ++i) {
699                         const MultiresFace *f= &pr_lvl->faces[i];
700                         data.corner1= &pr_deltas[f->v[0]].x;
701                         data.corner2= &pr_deltas[f->v[1]].x;
702                         data.corner3= &pr_deltas[f->v[2]].x;
703                         data.corner4= &pr_deltas[f->v[3]].x;
704                         data.quad= f->v[3] ? 1 : 0;
705                         multi_apply(&cr_deltas[f->mid].x, &data, 3, catmullclark_smooth_face);
706                         
707                         for(j=0; j<(data.quad?4:3); ++j)
708                                 me->mr->verts[f->mid].flag |= me->mr->verts[f->v[j]].flag;
709                 }
710
711                 for(i=0; i<pr_lvl->totedge; ++i) {
712                         const MultiresEdge *e= &pr_lvl->edges[i];
713                         data.boundary= pr_lvl->edge_boundary_states[i];
714                         edge_face_neighbor_midpoints_accum(&data,pr_lvl,cr_deltas,sizeof(vec3f),e);
715                         data.endpoint1= &pr_deltas[e->v[0]].x;
716                         data.endpoint2= &pr_deltas[e->v[1]].x;
717                         multi_apply(&cr_deltas[e->mid].x, &data, 3, catmullclark_smooth_edge);
718                                 
719                         for(j=0; j<2; ++j)
720                                 me->mr->verts[e->mid].flag |= me->mr->verts[e->v[j]].flag;
721                 }
722
723                 for(i=0; i<pr_lvl->totvert; ++i) {
724                         data.boundary= multires_vert_is_boundary(pr_lvl,i);
725                         data.original= &pr_deltas[i].x;
726                         data.edge_count= BLI_countlist(&pr_lvl->vert_edge_map[i]);
727                         if(data.boundary)
728                                 boundary_edges_average(&data,pr_lvl,pr_deltas,sizeof(vec3f),i);
729                         else {
730                                 vert_face_neighbor_midpoints_average(&data,pr_lvl,cr_deltas,sizeof(vec3f),i);
731                                 vert_edge_neighbor_midpoints_average(&data,pr_lvl,pr_deltas,sizeof(vec3f),i);
732                         }
733                         multi_apply(&cr_deltas[i].x, &data, 3, catmullclark_smooth_vert);
734                 }
735
736                 /* Apply deltas to vertex locations */
737                 for(i=0; (cr_lvl == last_lvl) && (i < cr_lvl->totvert); ++i) {
738                         VecAddf(me->mr->verts[i].co,
739                                 me->mr->verts[i].co,
740                                 &cr_deltas[i].x);                       
741                 }
742
743                 multires_free_temp_data(pr_lvl);
744
745                 pr_lvl= pr_lvl->next;
746                 cr_lvl= cr_lvl->next;
747         }
748         if(pr_deltas) MEM_freeN(pr_deltas);
749         if(cr_deltas) MEM_freeN(cr_deltas);
750
751 }
752
753 static void multires_update_faces(Mesh *me, EditMesh *em)
754 {
755         MultiresLevel *cr_lvl= current_level(me->mr), *pr_lvl= NULL,
756                       *last_lvl= me->mr->levels.last;
757         char *pr_flag_damaged= NULL, *cr_flag_damaged= NULL, *or_flag_damaged= NULL,
758              *pr_mat_damaged= NULL, *cr_mat_damaged= NULL, *or_mat_damaged= NULL, *swap= NULL;
759         EditFace *efa= NULL;
760         unsigned i,j,curf;
761
762         /* Find for each face whether flag/mat has changed */
763         pr_flag_damaged= MEM_callocN(sizeof(char) * last_lvl->totface, "flag_damaged 1");
764         cr_flag_damaged= MEM_callocN(sizeof(char) * last_lvl->totface, "flag_damaged 1");
765         pr_mat_damaged= MEM_callocN(sizeof(char) * last_lvl->totface, "mat_damaged 1");
766         cr_mat_damaged= MEM_callocN(sizeof(char) * last_lvl->totface, "mat_damaged 1");
767         if(em) efa= em->faces.first;
768         for(i=0; i<cr_lvl->totface; ++i) {
769                 MultiresFace mftmp;
770                 multires_get_face(&mftmp, efa, &me->mface[i]);
771                 if(cr_lvl->faces[i].flag != mftmp.flag)
772                         cr_flag_damaged[i]= 1;
773                 if(cr_lvl->faces[i].mat_nr != mftmp.mat_nr)
774                         cr_mat_damaged[i]= 1;
775
776                 /* Update current level */
777                 cr_lvl->faces[i].flag= mftmp.flag;
778                 cr_lvl->faces[i].mat_nr= mftmp.mat_nr;
779
780                 if(em) efa= efa->next;
781         }
782         or_flag_damaged= MEM_dupallocN(cr_flag_damaged);
783         or_mat_damaged= MEM_dupallocN(cr_mat_damaged);
784
785         /* Update lower levels */
786         cr_lvl= cr_lvl->prev;
787         while(cr_lvl) {
788                 swap= pr_flag_damaged;
789                 pr_flag_damaged= cr_flag_damaged;
790                 cr_flag_damaged= swap;
791
792                 swap= pr_mat_damaged;
793                 pr_mat_damaged= cr_mat_damaged;
794                 cr_mat_damaged= swap;
795
796                 curf= 0;
797                 for(i=0; i<cr_lvl->totface; ++i) {
798                         const int sides= cr_lvl->faces[i].v[3] ? 4 : 3;
799                         
800                         /* Check damages */
801                         for(j=0; j<sides; ++j, ++curf) {
802                                 if(pr_flag_damaged[curf]) {
803                                         cr_lvl->faces[i].flag= cr_lvl->next->faces[curf].flag;
804                                         cr_flag_damaged[i]= 1;
805                                 }
806                                 if(pr_mat_damaged[curf]) {
807                                         cr_lvl->faces[i].mat_nr= cr_lvl->next->faces[curf].mat_nr;
808                                         cr_mat_damaged[i]= 1;
809                                 }
810                         }
811                 }
812
813                 cr_lvl= cr_lvl->prev;
814         }
815         
816         /* Clear to original damages */
817         if(cr_flag_damaged) MEM_freeN(cr_flag_damaged);
818         if(cr_mat_damaged) MEM_freeN(cr_mat_damaged);
819         cr_flag_damaged= or_flag_damaged;
820         cr_mat_damaged= or_mat_damaged;
821         
822         /* Update higher levels */
823         pr_lvl= current_level(me->mr);
824         cr_lvl= pr_lvl->next;
825         while(cr_lvl) {
826                 swap= pr_flag_damaged;
827                 pr_flag_damaged= cr_flag_damaged;
828                 cr_flag_damaged= swap;
829
830                 swap= pr_mat_damaged;
831                 pr_mat_damaged= cr_mat_damaged;
832                 cr_mat_damaged= swap;
833
834                 /* Update faces */
835                 for(i=0, curf= 0; i<pr_lvl->totface; ++i) {
836                         const int sides= cr_lvl->prev->faces[i].v[3] ? 4 : 3;
837                         for(j=0; j<sides; ++j, ++curf) {
838                                 if(pr_flag_damaged[i]) {
839                                         cr_lvl->faces[curf].flag= pr_lvl->faces[i].flag;
840                                         cr_flag_damaged[curf]= 1;
841                                 }
842                                 if(pr_mat_damaged[i]) {
843                                         cr_lvl->faces[curf].mat_nr= pr_lvl->faces[i].mat_nr;
844                                         cr_mat_damaged[curf]= 1;
845                                 }
846                         }
847                 }
848
849                 pr_lvl= pr_lvl->next;
850                 cr_lvl= cr_lvl->next;
851         }
852
853         if(pr_flag_damaged) MEM_freeN(pr_flag_damaged);
854         if(cr_flag_damaged) MEM_freeN(cr_flag_damaged);
855         if(pr_mat_damaged) MEM_freeN(pr_mat_damaged);
856         if(cr_mat_damaged) MEM_freeN(cr_mat_damaged);
857 }
858
859 static void multires_update_colors(Mesh *me, EditMesh *em)
860 {
861         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
862         MultiresCol *pr_deltas= NULL, *cr_deltas= NULL;
863         CustomData *src= em ? &em->fdata : &me->fdata;
864         EditFace *efa= NULL;
865         unsigned i,j,curf= 0;
866         
867         if(me->mr->use_col) {
868                 /* Calc initial deltas */
869                 cr_deltas= MEM_callocN(sizeof(MultiresCol)*lvl->totface*4,"initial color/uv deltas");
870
871                 if(em) efa= em->faces.first;
872                 for(i=0; i<lvl->totface; ++i) {
873                         MCol *col= em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4];
874                         for(j=0; j<4; ++j) {
875                                 if(me->mr->use_col) {
876                                         cr_deltas[i*4+j].a= col[j].a - lvl->colfaces[i].col[j].a;
877                                         cr_deltas[i*4+j].r= col[j].r - lvl->colfaces[i].col[j].r;
878                                         cr_deltas[i*4+j].g= col[j].g - lvl->colfaces[i].col[j].g;
879                                         cr_deltas[i*4+j].b= col[j].b - lvl->colfaces[i].col[j].b;
880                                 }
881                         }
882                         if(em) efa= efa->next;
883                 }
884                 
885                 /* Update current level */
886                 if(em) efa= em->faces.first;
887                 for(i=0; i<lvl->totface; ++i) {
888                         MultiresColFace *f= &lvl->colfaces[i];
889
890                         if(me->mr->use_col)
891                                 mcol_to_multires(f, em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4]);
892                         
893                         if(em) efa= efa->next;
894                 }
895                 
896                 /* Update higher levels */
897                 lvl= lvl->next;
898                 while(lvl) {
899                         /* Set up new deltas, but keep the ones from the previous level */
900                         if(pr_deltas) MEM_freeN(pr_deltas);
901                         pr_deltas= cr_deltas;
902                         cr_deltas= MEM_callocN(sizeof(MultiresCol)*lvl->totface*4,"color deltas");
903
904                         curf= 0;
905                         for(i=0; i<lvl->prev->totface; ++i) {
906                                 const char sides= lvl->prev->faces[i].v[3]?4:3;
907                                 MultiresCol cntr;
908                                 
909                                 /* Find average color of 4 (or 3 for triangle) verts */
910                                 multires_col_avg(&cntr,&pr_deltas[i*4],sides);
911                                 
912                                 for(j=0; j<sides; ++j) {
913                                         multires_col_avg2(&cr_deltas[curf*4],
914                                                           &pr_deltas[i*4+j],
915                                                           &pr_deltas[i*4+(j==0?sides-1:j-1)]);
916                                         cr_deltas[curf*4+1]= pr_deltas[i*4+j];
917                                         multires_col_avg2(&cr_deltas[curf*4+2],
918                                                           &pr_deltas[i*4+j],
919                                                           &pr_deltas[i*4+(j==sides-1?0:j+1)]);
920                                         cr_deltas[curf*4+3]= cntr;
921                                         ++curf;
922                                 }
923                         }
924
925                         for(i=0; i<lvl->totface; ++i) {
926                                 for(j=0; j<4; ++j) {
927                                         lvl->colfaces[i].col[j].a+= cr_deltas[i*4+j].a;
928                                         lvl->colfaces[i].col[j].r+= cr_deltas[i*4+j].r;
929                                         lvl->colfaces[i].col[j].g+= cr_deltas[i*4+j].g;
930                                         lvl->colfaces[i].col[j].b+= cr_deltas[i*4+j].b;
931                                 }
932                         }
933
934                         lvl= lvl->next;
935                 }
936                 if(pr_deltas) MEM_freeN(pr_deltas);
937                 if(cr_deltas) MEM_freeN(cr_deltas);
938                 
939                 /* Update lower levels */
940                 lvl= me->mr->levels.last;
941                 lvl= lvl->prev;
942                 while(lvl) {
943                         MultiresColFace *nf= lvl->next->colfaces;
944                         for(i=0; i<lvl->totface; ++i) {
945                                 MultiresFace *f= &lvl->faces[i];
946                                 for(j=0; j<(f->v[3]?4:3); ++j) {
947                                         lvl->colfaces[i].col[j]= nf->col[1];
948                                         ++nf;
949                                 }
950                         }
951                         lvl= lvl->prev;
952                 }
953         }
954 }
955
956 void multires_update_levels(Mesh *me, const int render)
957 {
958         EditMesh *em= (!render && G.obedit) ? G.editMesh : NULL;
959
960         multires_update_first_level(me, em);
961         multires_update_vertices(me, em);
962         multires_update_faces(me, em);
963         multires_update_colors(me, em);
964 }
965
966 static void check_colors(Mesh *me)
967 {
968         CustomData *src= G.obedit ? &G.editMesh->fdata : &me->fdata;
969         const char col= CustomData_has_layer(src, CD_MCOL);
970
971         /* Check if vertex colors have been deleted or added */
972         if(me->mr->use_col && !col)
973                 me->mr->use_col= 0;
974         else if(!me->mr->use_col && col) {
975                 me->mr->use_col= 1;
976                 multires_load_cols(me);
977         }
978 }
979
980 static unsigned int find_mid_edge(ListBase *vert_edge_map,
981                                   MultiresLevel *lvl,
982                                   const unsigned int v1,
983                                   const unsigned int v2 )
984 {
985         MultiresMapNode *n= vert_edge_map[v1].first;
986         while(n) {
987                 if(lvl->edges[n->Index].v[0]==v2 ||
988                    lvl->edges[n->Index].v[1]==v2)
989                         return lvl->edges[n->Index].mid;
990
991                 n= n->next;
992         }
993         return -1;
994 }
995
996 static float clamp_component(const float c)
997 {
998         if(c<0) return 0;
999         else if(c>255) return 255;
1000         else return c;
1001 }
1002
1003 void multires_to_mcol(MultiresColFace *f, MCol mcol[4])
1004 {
1005         unsigned char j;
1006         for(j=0; j<4; ++j) {
1007                 mcol->a= clamp_component(f->col[j].a);
1008                 mcol->r= clamp_component(f->col[j].r);
1009                 mcol->g= clamp_component(f->col[j].g);
1010                 mcol->b= clamp_component(f->col[j].b);
1011                 ++mcol;
1012         }
1013 }
1014
1015 void multires_level_to_mesh(Object *ob, Mesh *me, const int render)
1016 {
1017         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1018         int i;
1019         EditMesh *em= (!render && G.obedit) ? G.editMesh : NULL;
1020         
1021         if(em)
1022                 return;
1023
1024         CustomData_free_layer_active(&me->vdata, CD_MVERT, me->totvert);
1025         CustomData_free_layer_active(&me->edata, CD_MEDGE, me->totedge);
1026         CustomData_free_layer_active(&me->fdata, CD_MFACE, me->totface);
1027         CustomData_free_layer_active(&me->vdata, CD_MDEFORMVERT, me->totvert);
1028         CustomData_free_layers(&me->fdata, CD_MTFACE, me->totface);
1029         CustomData_free_layers(&me->fdata, CD_MCOL, me->totface);
1030                 
1031         me->totvert= lvl->totvert;
1032         me->totface= lvl->totface;
1033         me->totedge= lvl->totedge;
1034
1035         CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
1036         CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
1037         CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
1038         mesh_update_customdata_pointers(me);
1039
1040         /* Vertices/Edges/Faces */
1041         
1042         for(i=0; i<lvl->totvert; ++i) {
1043                 me->mvert[i]= me->mr->verts[i];
1044         }
1045         for(i=0; i<lvl->totedge; ++i) {
1046                 me->medge[i].v1= lvl->edges[i].v[0];
1047                 me->medge[i].v2= lvl->edges[i].v[1];
1048                 me->medge[i].flag &= ~ME_HIDE;
1049         }
1050         for(i=0; i<lvl->totface; ++i) {
1051                 me->mface[i].v1= lvl->faces[i].v[0];
1052                 me->mface[i].v2= lvl->faces[i].v[1];
1053                 me->mface[i].v3= lvl->faces[i].v[2];
1054                 me->mface[i].v4= lvl->faces[i].v[3];
1055                 me->mface[i].flag= lvl->faces[i].flag;
1056                 me->mface[i].flag &= ~ME_HIDE;
1057                 me->mface[i].mat_nr= lvl->faces[i].mat_nr;
1058         }
1059         
1060         /* Edge flags */
1061         if(lvl==me->mr->levels.first) {
1062                 for(i=0; i<lvl->totedge; ++i) {
1063                         me->medge[i].flag= me->mr->edge_flags[i];
1064                         me->medge[i].crease= me->mr->edge_creases[i];
1065                 }
1066         } else {
1067                 MultiresLevel *lvl1= me->mr->levels.first;
1068                 const int last= lvl1->totedge * pow(2, me->mr->current-1);
1069                 for(i=0; i<last; ++i) {
1070                         const int ndx= i / pow(2, me->mr->current-1);
1071                         
1072                         me->medge[i].flag= me->mr->edge_flags[ndx];
1073                         me->medge[i].crease= me->mr->edge_creases[ndx];
1074                 }
1075         }
1076
1077         multires_customdata_to_mesh(me, em, lvl, &me->mr->vdata, em ? &em->vdata : &me->vdata, CD_MDEFORMVERT);
1078         multires_customdata_to_mesh(me, em, lvl, &me->mr->fdata, em ? &em->fdata : &me->fdata, CD_MTFACE);
1079
1080         /* Colors */
1081         if(me->mr->use_col) {
1082                 CustomData *src= &me->fdata;
1083                 
1084                 if(me->mr->use_col) me->mcol= CustomData_add_layer(src, CD_MCOL, CD_CALLOC, NULL, me->totface);
1085                 
1086                 for(i=0; i<lvl->totface; ++i) {
1087                         if(me->mr->use_col)
1088                                 multires_to_mcol(&lvl->colfaces[i], &me->mcol[i*4]);
1089                 }
1090                         
1091         }
1092         
1093         mesh_update_customdata_pointers(me);
1094         
1095         multires_edge_level_update(ob,me);
1096         DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
1097         mesh_calc_normals(me->mvert, me->totvert, me->mface, me->totface, NULL);
1098 }
1099
1100 void multires_add_level(Object *ob, Mesh *me, const char subdiv_type)
1101 {
1102         int i,j, curf, cure;
1103         MultiresLevel *lvl= NULL;
1104         MultiApplyData data;
1105         MVert *oldverts= NULL;
1106         
1107         lvl= MEM_callocN(sizeof(MultiresLevel), "multireslevel");
1108         if(me->pv) sculptmode_pmv_off(me);
1109
1110         check_colors(me);
1111         multires_update_levels(me, 0);
1112
1113         ++me->mr->level_count;
1114         BLI_addtail(&me->mr->levels,lvl);
1115
1116         /* Create vertices
1117            =============== */
1118         lvl->totvert= lvl->prev->totvert + lvl->prev->totedge + lvl->prev->totface;
1119         oldverts= me->mr->verts;
1120         me->mr->verts= MEM_callocN(sizeof(MVert)*lvl->totvert, "multitres verts");
1121         /* Copy old verts */
1122         for(i=0; i<lvl->prev->totvert; ++i)
1123                 me->mr->verts[i]= oldverts[i];
1124         /* Create new edge verts */
1125         for(i=0; i<lvl->prev->totedge; ++i) {
1126                 VecMidf(me->mr->verts[lvl->prev->totvert + i].co,
1127                         oldverts[lvl->prev->edges[i].v[0]].co,
1128                         oldverts[lvl->prev->edges[i].v[1]].co);
1129                 lvl->prev->edges[i].mid= lvl->prev->totvert + i;
1130         }
1131         /* Create new face verts */
1132         for(i=0; i<lvl->prev->totface; ++i) {
1133                 lvl->prev->faces[i].mid= lvl->prev->totvert + lvl->prev->totedge + i;
1134         }
1135
1136         multires_calc_temp_data(lvl->prev);
1137
1138         /* Create faces
1139            ============ */
1140         /* Allocate all the new faces (each triangle creates three, and
1141            each quad creates four */
1142         lvl->totface= 0;
1143         for(i=0; i<lvl->prev->totface; ++i)
1144                 lvl->totface+= lvl->prev->faces[i].v[3] ? 4 : 3;
1145         lvl->faces= MEM_callocN(sizeof(MultiresFace)*lvl->totface,"multires faces");
1146
1147         curf= 0;
1148         for(i=0; i<lvl->prev->totface; ++i) {
1149                 const int max= lvl->prev->faces[i].v[3] ? 3 : 2;
1150                 
1151                 for(j=0; j<max+1; ++j) {
1152                         lvl->faces[curf].v[0]= find_mid_edge(lvl->prev->vert_edge_map,lvl->prev,
1153                                                              lvl->prev->faces[i].v[j],
1154                                                              lvl->prev->faces[i].v[j==0?max:j-1]);
1155                         lvl->faces[curf].v[1]= lvl->prev->faces[i].v[j];
1156                         lvl->faces[curf].v[2]= find_mid_edge(lvl->prev->vert_edge_map,lvl->prev,
1157                                                              lvl->prev->faces[i].v[j],
1158                                                              lvl->prev->faces[i].v[j==max?0:j+1]);
1159                         lvl->faces[curf].v[3]= lvl->prev->totvert + lvl->prev->totedge + i;
1160                         lvl->faces[curf].flag= lvl->prev->faces[i].flag;
1161                         lvl->faces[curf].mat_nr= lvl->prev->faces[i].mat_nr;
1162
1163                         ++curf;
1164                 }
1165         }
1166
1167         /* Create edges
1168            ============ */
1169         /* Figure out how many edges to allocate */
1170         lvl->totedge= lvl->prev->totedge*2;
1171         for(i=0; i<lvl->prev->totface; ++i)
1172                 lvl->totedge+= lvl->prev->faces[i].v[3]?4:3;
1173         lvl->edges= MEM_callocN(sizeof(MultiresEdge)*lvl->totedge,"multires edges");
1174
1175         for(i=0; i<lvl->prev->totedge; ++i) {
1176                 lvl->edges[i*2].v[0]= lvl->prev->edges[i].v[0];
1177                 lvl->edges[i*2].v[1]= lvl->prev->edges[i].mid;
1178                 lvl->edges[i*2+1].v[0]= lvl->prev->edges[i].mid;
1179                 lvl->edges[i*2+1].v[1]= lvl->prev->edges[i].v[1];
1180         }
1181         /* Add edges inside of old polygons */
1182         curf= 0;
1183         cure= lvl->prev->totedge*2;
1184         for(i=0; i<lvl->prev->totface; ++i) {
1185                 for(j=0; j<(lvl->prev->faces[i].v[3]?4:3); ++j) {
1186                         lvl->edges[cure].v[0]= lvl->faces[curf].v[2];
1187                         lvl->edges[cure].v[1]= lvl->faces[curf].v[3];
1188                         ++cure;
1189                         ++curf;
1190                 }
1191         }
1192
1193         /* Smooth vertices
1194            =============== */
1195         for(i=0; i<lvl->prev->totface; ++i) {
1196                 const MultiresFace *f= &lvl->prev->faces[i];
1197                 data.corner1= oldverts[f->v[0]].co;
1198                 data.corner2= oldverts[f->v[1]].co;
1199                 data.corner3= oldverts[f->v[2]].co;
1200                 data.corner4= oldverts[f->v[3]].co;
1201                 data.quad= f->v[3] ? 1 : 0;
1202                 multi_apply(me->mr->verts[f->mid].co, &data, 3, catmullclark_smooth_face);
1203         }
1204
1205         if(subdiv_type == 0) {
1206                 for(i=0; i<lvl->prev->totedge; ++i) {
1207                         const MultiresEdge *e= &lvl->prev->edges[i];
1208                         data.boundary= lvl->prev->edge_boundary_states[i];
1209                         edge_face_neighbor_midpoints_accum(&data,lvl->prev, me->mr->verts, sizeof(MVert),e);
1210                         data.endpoint1= oldverts[e->v[0]].co;
1211                         data.endpoint2= oldverts[e->v[1]].co;
1212                         multi_apply(me->mr->verts[e->mid].co, &data, 3, catmullclark_smooth_edge);
1213                 }
1214                 
1215                 for(i=0; i<lvl->prev->totvert; ++i) {
1216                         data.boundary= multires_vert_is_boundary(lvl->prev,i);
1217                         data.original= oldverts[i].co;
1218                         data.edge_count= BLI_countlist(&lvl->prev->vert_edge_map[i]);
1219                         if(data.boundary)
1220                                 boundary_edges_average(&data,lvl->prev, oldverts, sizeof(MVert),i);
1221                         else {
1222                                 vert_face_neighbor_midpoints_average(&data,lvl->prev, me->mr->verts,
1223                                                                      sizeof(MVert),i);
1224                                 vert_edge_neighbor_midpoints_average(&data,lvl->prev, oldverts,
1225                                                                      sizeof(MVert),i);
1226                         }
1227                         multi_apply(me->mr->verts[i].co, &data, 3, catmullclark_smooth_vert);
1228                 }
1229         }
1230
1231         multires_free_temp_data(lvl->prev);
1232         MEM_freeN(oldverts);
1233
1234         /* Vertex Colors
1235            ============= */
1236         curf= 0;
1237         if(me->mr->use_col) {
1238                 MultiresColFace *cf= MEM_callocN(sizeof(MultiresColFace)*lvl->totface,"Multirescolfaces");
1239                 lvl->colfaces= cf;
1240                 for(i=0; i<lvl->prev->totface; ++i) {
1241                         const char sides= lvl->prev->faces[i].v[3]?4:3;
1242                         MultiresCol cntr;
1243
1244                         /* Find average color of 4 (or 3 for triangle) verts */
1245                         multires_col_avg(&cntr,lvl->prev->colfaces[i].col,sides);
1246
1247                         for(j=0; j<sides; ++j) {
1248                                 multires_col_avg2(&cf->col[0],
1249                                                   &lvl->prev->colfaces[i].col[j],
1250                                                   &lvl->prev->colfaces[i].col[j==0?sides-1:j-1]);
1251                                 cf->col[1]= lvl->prev->colfaces[i].col[j];
1252                                 multires_col_avg2(&cf->col[2],
1253                                                   &lvl->prev->colfaces[i].col[j],
1254                                                   &lvl->prev->colfaces[i].col[j==sides-1?0:j+1]);
1255                                 cf->col[3]= cntr;
1256
1257                                 ++cf;
1258                         }
1259                 }
1260         }
1261
1262         me->mr->newlvl= me->mr->level_count;
1263         me->mr->current= me->mr->newlvl;
1264         /* Unless the render level has been set to something other than the
1265            highest level (by the user), increment the render level to match
1266            the highest available level */
1267         if(me->mr->renderlvl == me->mr->level_count - 1) me->mr->renderlvl= me->mr->level_count;
1268
1269         multires_level_to_mesh(ob, me, 0);
1270 }
1271
1272 void multires_set_level(Object *ob, Mesh *me, const int render)
1273 {
1274         if(me->pv) sculptmode_pmv_off(me);
1275
1276         check_colors(me);
1277         multires_update_levels(me, render);
1278
1279         me->mr->current= me->mr->newlvl;
1280         if(me->mr->current<1) me->mr->current= 1;
1281         else if(me->mr->current>me->mr->level_count) me->mr->current= me->mr->level_count;
1282
1283         multires_level_to_mesh(ob, me, render);
1284 }
1285
1286 /* Update the edge visibility flags to only show edges on or below the edgelvl */
1287 void multires_edge_level_update(Object *ob, Mesh *me)
1288 {
1289         if(!G.obedit) {
1290                 MultiresLevel *cr_lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1291                 MultiresLevel *edge_lvl= BLI_findlink(&me->mr->levels,me->mr->edgelvl-1);
1292                 const int threshold= edge_lvl->totedge * powf(2, me->mr->current - me->mr->edgelvl);
1293                 unsigned i;
1294
1295                 for(i=0; i<cr_lvl->totedge; ++i) {
1296                         const int ndx= me->pv ? me->pv->edge_map[i] : i;
1297                         if(ndx != -1) { /* -1= hidden edge */
1298                                 if(me->mr->edgelvl >= me->mr->current || i<threshold)
1299                                         me->medge[ndx].flag |= ME_EDGEDRAW | ME_EDGERENDER;
1300                                 else
1301                                         me->medge[ndx].flag &= ~ME_EDGEDRAW & ~ME_EDGERENDER;
1302                         }
1303                 }
1304                 
1305                 DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
1306         }
1307 }