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