== 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 void multires_update_colors(Mesh *me)
860 {
861         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
862         MultiresCol *pr_deltas= NULL, *cr_deltas= NULL;
863         EditMesh *em= G.obedit ? G.editMesh : NULL;
864         CustomData *src= em ? &em->fdata : &me->fdata;
865         EditFace *efa= NULL;
866         unsigned i,j,curf= 0;
867         
868         if(me->mr->use_col) {
869                 /* Calc initial deltas */
870                 cr_deltas= MEM_callocN(sizeof(MultiresCol)*lvl->totface*4,"initial color/uv deltas");
871
872                 if(em) efa= em->faces.first;
873                 for(i=0; i<lvl->totface; ++i) {
874                         MCol *col= em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4];
875                         for(j=0; j<4; ++j) {
876                                 if(me->mr->use_col) {
877                                         cr_deltas[i*4+j].a= col[j].a - lvl->colfaces[i].col[j].a;
878                                         cr_deltas[i*4+j].r= col[j].r - lvl->colfaces[i].col[j].r;
879                                         cr_deltas[i*4+j].g= col[j].g - lvl->colfaces[i].col[j].g;
880                                         cr_deltas[i*4+j].b= col[j].b - lvl->colfaces[i].col[j].b;
881                                 }
882                         }
883                         if(em) efa= efa->next;
884                 }
885                 
886                 /* Update current level */
887                 if(em) efa= em->faces.first;
888                 for(i=0; i<lvl->totface; ++i) {
889                         MultiresColFace *f= &lvl->colfaces[i];
890
891                         if(me->mr->use_col)
892                                 mcol_to_multires(f, em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4]);
893                         
894                         if(em) efa= efa->next;
895                 }
896                 
897                 /* Update higher levels */
898                 lvl= lvl->next;
899                 while(lvl) {
900                         /* Set up new deltas, but keep the ones from the previous level */
901                         if(pr_deltas) MEM_freeN(pr_deltas);
902                         pr_deltas= cr_deltas;
903                         cr_deltas= MEM_callocN(sizeof(MultiresCol)*lvl->totface*4,"color deltas");
904
905                         curf= 0;
906                         for(i=0; i<lvl->prev->totface; ++i) {
907                                 const char sides= lvl->prev->faces[i].v[3]?4:3;
908                                 MultiresCol cntr;
909                                 
910                                 /* Find average color of 4 (or 3 for triangle) verts */
911                                 multires_col_avg(&cntr,&pr_deltas[i*4],sides);
912                                 
913                                 for(j=0; j<sides; ++j) {
914                                         multires_col_avg2(&cr_deltas[curf*4],
915                                                           &pr_deltas[i*4+j],
916                                                           &pr_deltas[i*4+(j==0?sides-1:j-1)]);
917                                         cr_deltas[curf*4+1]= pr_deltas[i*4+j];
918                                         multires_col_avg2(&cr_deltas[curf*4+2],
919                                                           &pr_deltas[i*4+j],
920                                                           &pr_deltas[i*4+(j==sides-1?0:j+1)]);
921                                         cr_deltas[curf*4+3]= cntr;
922                                         ++curf;
923                                 }
924                         }
925
926                         for(i=0; i<lvl->totface; ++i) {
927                                 for(j=0; j<4; ++j) {
928                                         lvl->colfaces[i].col[j].a+= cr_deltas[i*4+j].a;
929                                         lvl->colfaces[i].col[j].r+= cr_deltas[i*4+j].r;
930                                         lvl->colfaces[i].col[j].g+= cr_deltas[i*4+j].g;
931                                         lvl->colfaces[i].col[j].b+= cr_deltas[i*4+j].b;
932                                 }
933                         }
934
935                         lvl= lvl->next;
936                 }
937                 if(pr_deltas) MEM_freeN(pr_deltas);
938                 if(cr_deltas) MEM_freeN(cr_deltas);
939                 
940                 /* Update lower levels */
941                 lvl= me->mr->levels.last;
942                 lvl= lvl->prev;
943                 while(lvl) {
944                         MultiresColFace *nf= lvl->next->colfaces;
945                         for(i=0; i<lvl->totface; ++i) {
946                                 MultiresFace *f= &lvl->faces[i];
947                                 for(j=0; j<(f->v[3]?4:3); ++j) {
948                                         lvl->colfaces[i].col[j]= nf->col[1];
949                                         ++nf;
950                                 }
951                         }
952                         lvl= lvl->prev;
953                 }
954         }
955 }
956
957 void multires_update_levels(Mesh *me, const int render)
958 {
959         EditMesh *em= (!render && G.obedit) ? G.editMesh : NULL;
960
961         multires_update_first_level(me, em);
962         multires_update_vertices(me, em);
963         multires_update_faces(me, em);
964         multires_update_colors(me);
965 }
966
967 static void check_colors(Mesh *me)
968 {
969         CustomData *src= G.obedit ? &G.editMesh->fdata : &me->fdata;
970         const char col= CustomData_has_layer(src, CD_MCOL);
971
972         /* Check if vertex colors have been deleted or added */
973         if(me->mr->use_col && !col)
974                 me->mr->use_col= 0;
975         else if(!me->mr->use_col && col) {
976                 me->mr->use_col= 1;
977                 multires_load_cols(me);
978         }
979 }
980
981 static unsigned int find_mid_edge(ListBase *vert_edge_map,
982                                   MultiresLevel *lvl,
983                                   const unsigned int v1,
984                                   const unsigned int v2 )
985 {
986         MultiresMapNode *n= vert_edge_map[v1].first;
987         while(n) {
988                 if(lvl->edges[n->Index].v[0]==v2 ||
989                    lvl->edges[n->Index].v[1]==v2)
990                         return lvl->edges[n->Index].mid;
991
992                 n= n->next;
993         }
994         return -1;
995 }
996
997 static float clamp_component(const float c)
998 {
999         if(c<0) return 0;
1000         else if(c>255) return 255;
1001         else return c;
1002 }
1003
1004 void multires_to_mcol(MultiresColFace *f, MCol mcol[4])
1005 {
1006         unsigned char j;
1007         for(j=0; j<4; ++j) {
1008                 mcol->a= clamp_component(f->col[j].a);
1009                 mcol->r= clamp_component(f->col[j].r);
1010                 mcol->g= clamp_component(f->col[j].g);
1011                 mcol->b= clamp_component(f->col[j].b);
1012                 ++mcol;
1013         }
1014 }
1015
1016 void multires_level_to_mesh(Object *ob, Mesh *me, const int render)
1017 {
1018         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1019         int i;
1020         EditMesh *em= (!render && G.obedit) ? G.editMesh : NULL;
1021         
1022         if(em)
1023                 return;
1024
1025         CustomData_free_layer_active(&me->vdata, CD_MVERT, me->totvert);
1026         CustomData_free_layer_active(&me->edata, CD_MEDGE, me->totedge);
1027         CustomData_free_layer_active(&me->fdata, CD_MFACE, me->totface);
1028         CustomData_free_layer_active(&me->vdata, CD_MDEFORMVERT, me->totvert);
1029         CustomData_free_layers(&me->fdata, CD_MTFACE, me->totface);
1030         CustomData_free_layers(&me->fdata, CD_MCOL, me->totface);
1031                 
1032         me->totvert= lvl->totvert;
1033         me->totface= lvl->totface;
1034         me->totedge= lvl->totedge;
1035
1036         CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
1037         CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
1038         CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
1039         mesh_update_customdata_pointers(me);
1040
1041         /* Vertices/Edges/Faces */
1042         
1043         for(i=0; i<lvl->totvert; ++i) {
1044                 me->mvert[i]= me->mr->verts[i];
1045         }
1046         for(i=0; i<lvl->totedge; ++i) {
1047                 me->medge[i].v1= lvl->edges[i].v[0];
1048                 me->medge[i].v2= lvl->edges[i].v[1];
1049                 me->medge[i].flag &= ~ME_HIDE;
1050         }
1051         for(i=0; i<lvl->totface; ++i) {
1052                 me->mface[i].v1= lvl->faces[i].v[0];
1053                 me->mface[i].v2= lvl->faces[i].v[1];
1054                 me->mface[i].v3= lvl->faces[i].v[2];
1055                 me->mface[i].v4= lvl->faces[i].v[3];
1056                 me->mface[i].flag= lvl->faces[i].flag;
1057                 me->mface[i].flag &= ~ME_HIDE;
1058                 me->mface[i].mat_nr= lvl->faces[i].mat_nr;
1059         }
1060         
1061         /* Edge flags */
1062         if(lvl==me->mr->levels.first) {
1063                 for(i=0; i<lvl->totedge; ++i) {
1064                         me->medge[i].flag= me->mr->edge_flags[i];
1065                         me->medge[i].crease= me->mr->edge_creases[i];
1066                 }
1067         } else {
1068                 MultiresLevel *lvl1= me->mr->levels.first;
1069                 const int last= lvl1->totedge * pow(2, me->mr->current-1);
1070                 for(i=0; i<last; ++i) {
1071                         const int ndx= i / pow(2, me->mr->current-1);
1072                         
1073                         me->medge[i].flag= me->mr->edge_flags[ndx];
1074                         me->medge[i].crease= me->mr->edge_creases[ndx];
1075                 }
1076         }
1077
1078         multires_customdata_to_mesh(me, em, lvl, &me->mr->vdata, em ? &em->vdata : &me->vdata, CD_MDEFORMVERT);
1079         multires_customdata_to_mesh(me, em, lvl, &me->mr->fdata, em ? &em->fdata : &me->fdata, CD_MTFACE);
1080
1081         /* Colors */
1082         if(me->mr->use_col) {
1083                 CustomData *src= &me->fdata;
1084                 
1085                 if(me->mr->use_col) me->mcol= CustomData_add_layer(src, CD_MCOL, CD_CALLOC, NULL, me->totface);
1086                 
1087                 for(i=0; i<lvl->totface; ++i) {
1088                         if(me->mr->use_col)
1089                                 multires_to_mcol(&lvl->colfaces[i], &me->mcol[i*4]);
1090                 }
1091                         
1092         }
1093         
1094         mesh_update_customdata_pointers(me);
1095         
1096         multires_edge_level_update(ob,me);
1097         DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
1098         mesh_calc_normals(me->mvert, me->totvert, me->mface, me->totface, NULL);
1099 }
1100
1101 void multires_add_level(Object *ob, Mesh *me, const char subdiv_type)
1102 {
1103         int i,j, curf, cure;
1104         MultiresLevel *lvl= NULL;
1105         MultiApplyData data;
1106         MVert *oldverts= NULL;
1107         
1108         lvl= MEM_callocN(sizeof(MultiresLevel), "multireslevel");
1109         if(me->pv) sculptmode_pmv_off(me);
1110
1111         check_colors(me);
1112         multires_update_levels(me, 0);
1113
1114         ++me->mr->level_count;
1115         BLI_addtail(&me->mr->levels,lvl);
1116
1117         /* Create vertices
1118            =============== */
1119         lvl->totvert= lvl->prev->totvert + lvl->prev->totedge + lvl->prev->totface;
1120         oldverts= me->mr->verts;
1121         me->mr->verts= MEM_callocN(sizeof(MVert)*lvl->totvert, "multitres verts");
1122         /* Copy old verts */
1123         for(i=0; i<lvl->prev->totvert; ++i)
1124                 me->mr->verts[i]= oldverts[i];
1125         /* Create new edge verts */
1126         for(i=0; i<lvl->prev->totedge; ++i) {
1127                 VecMidf(me->mr->verts[lvl->prev->totvert + i].co,
1128                         oldverts[lvl->prev->edges[i].v[0]].co,
1129                         oldverts[lvl->prev->edges[i].v[1]].co);
1130                 lvl->prev->edges[i].mid= lvl->prev->totvert + i;
1131         }
1132         /* Create new face verts */
1133         for(i=0; i<lvl->prev->totface; ++i) {
1134                 lvl->prev->faces[i].mid= lvl->prev->totvert + lvl->prev->totedge + i;
1135         }
1136
1137         multires_calc_temp_data(lvl->prev);
1138
1139         /* Create faces
1140            ============ */
1141         /* Allocate all the new faces (each triangle creates three, and
1142            each quad creates four */
1143         lvl->totface= 0;
1144         for(i=0; i<lvl->prev->totface; ++i)
1145                 lvl->totface+= lvl->prev->faces[i].v[3] ? 4 : 3;
1146         lvl->faces= MEM_callocN(sizeof(MultiresFace)*lvl->totface,"multires faces");
1147
1148         curf= 0;
1149         for(i=0; i<lvl->prev->totface; ++i) {
1150                 const int max= lvl->prev->faces[i].v[3] ? 3 : 2;
1151                 
1152                 for(j=0; j<max+1; ++j) {
1153                         lvl->faces[curf].v[0]= find_mid_edge(lvl->prev->vert_edge_map,lvl->prev,
1154                                                              lvl->prev->faces[i].v[j],
1155                                                              lvl->prev->faces[i].v[j==0?max:j-1]);
1156                         lvl->faces[curf].v[1]= lvl->prev->faces[i].v[j];
1157                         lvl->faces[curf].v[2]= find_mid_edge(lvl->prev->vert_edge_map,lvl->prev,
1158                                                              lvl->prev->faces[i].v[j],
1159                                                              lvl->prev->faces[i].v[j==max?0:j+1]);
1160                         lvl->faces[curf].v[3]= lvl->prev->totvert + lvl->prev->totedge + i;
1161                         lvl->faces[curf].flag= lvl->prev->faces[i].flag;
1162                         lvl->faces[curf].mat_nr= lvl->prev->faces[i].mat_nr;
1163
1164                         ++curf;
1165                 }
1166         }
1167
1168         /* Create edges
1169            ============ */
1170         /* Figure out how many edges to allocate */
1171         lvl->totedge= lvl->prev->totedge*2;
1172         for(i=0; i<lvl->prev->totface; ++i)
1173                 lvl->totedge+= lvl->prev->faces[i].v[3]?4:3;
1174         lvl->edges= MEM_callocN(sizeof(MultiresEdge)*lvl->totedge,"multires edges");
1175
1176         for(i=0; i<lvl->prev->totedge; ++i) {
1177                 lvl->edges[i*2].v[0]= lvl->prev->edges[i].v[0];
1178                 lvl->edges[i*2].v[1]= lvl->prev->edges[i].mid;
1179                 lvl->edges[i*2+1].v[0]= lvl->prev->edges[i].mid;
1180                 lvl->edges[i*2+1].v[1]= lvl->prev->edges[i].v[1];
1181         }
1182         /* Add edges inside of old polygons */
1183         curf= 0;
1184         cure= lvl->prev->totedge*2;
1185         for(i=0; i<lvl->prev->totface; ++i) {
1186                 for(j=0; j<(lvl->prev->faces[i].v[3]?4:3); ++j) {
1187                         lvl->edges[cure].v[0]= lvl->faces[curf].v[2];
1188                         lvl->edges[cure].v[1]= lvl->faces[curf].v[3];
1189                         ++cure;
1190                         ++curf;
1191                 }
1192         }
1193
1194         /* Smooth vertices
1195            =============== */
1196         for(i=0; i<lvl->prev->totface; ++i) {
1197                 const MultiresFace *f= &lvl->prev->faces[i];
1198                 data.corner1= oldverts[f->v[0]].co;
1199                 data.corner2= oldverts[f->v[1]].co;
1200                 data.corner3= oldverts[f->v[2]].co;
1201                 data.corner4= oldverts[f->v[3]].co;
1202                 data.quad= f->v[3] ? 1 : 0;
1203                 multi_apply(me->mr->verts[f->mid].co, &data, 3, catmullclark_smooth_face);
1204         }
1205
1206         if(subdiv_type == 0) {
1207                 for(i=0; i<lvl->prev->totedge; ++i) {
1208                         const MultiresEdge *e= &lvl->prev->edges[i];
1209                         data.boundary= lvl->prev->edge_boundary_states[i];
1210                         edge_face_neighbor_midpoints_accum(&data,lvl->prev, me->mr->verts, sizeof(MVert),e);
1211                         data.endpoint1= oldverts[e->v[0]].co;
1212                         data.endpoint2= oldverts[e->v[1]].co;
1213                         multi_apply(me->mr->verts[e->mid].co, &data, 3, catmullclark_smooth_edge);
1214                 }
1215                 
1216                 for(i=0; i<lvl->prev->totvert; ++i) {
1217                         data.boundary= multires_vert_is_boundary(lvl->prev,i);
1218                         data.original= oldverts[i].co;
1219                         data.edge_count= BLI_countlist(&lvl->prev->vert_edge_map[i]);
1220                         if(data.boundary)
1221                                 boundary_edges_average(&data,lvl->prev, oldverts, sizeof(MVert),i);
1222                         else {
1223                                 vert_face_neighbor_midpoints_average(&data,lvl->prev, me->mr->verts,
1224                                                                      sizeof(MVert),i);
1225                                 vert_edge_neighbor_midpoints_average(&data,lvl->prev, oldverts,
1226                                                                      sizeof(MVert),i);
1227                         }
1228                         multi_apply(me->mr->verts[i].co, &data, 3, catmullclark_smooth_vert);
1229                 }
1230         }
1231
1232         multires_free_temp_data(lvl->prev);
1233         MEM_freeN(oldverts);
1234
1235         /* Vertex Colors
1236            ============= */
1237         curf= 0;
1238         if(me->mr->use_col) {
1239                 MultiresColFace *cf= MEM_callocN(sizeof(MultiresColFace)*lvl->totface,"Multirescolfaces");
1240                 lvl->colfaces= cf;
1241                 for(i=0; i<lvl->prev->totface; ++i) {
1242                         const char sides= lvl->prev->faces[i].v[3]?4:3;
1243                         MultiresCol cntr;
1244
1245                         /* Find average color of 4 (or 3 for triangle) verts */
1246                         multires_col_avg(&cntr,lvl->prev->colfaces[i].col,sides);
1247
1248                         for(j=0; j<sides; ++j) {
1249                                 multires_col_avg2(&cf->col[0],
1250                                                   &lvl->prev->colfaces[i].col[j],
1251                                                   &lvl->prev->colfaces[i].col[j==0?sides-1:j-1]);
1252                                 cf->col[1]= lvl->prev->colfaces[i].col[j];
1253                                 multires_col_avg2(&cf->col[2],
1254                                                   &lvl->prev->colfaces[i].col[j],
1255                                                   &lvl->prev->colfaces[i].col[j==sides-1?0:j+1]);
1256                                 cf->col[3]= cntr;
1257
1258                                 ++cf;
1259                         }
1260                 }
1261         }
1262
1263         me->mr->newlvl= me->mr->level_count;
1264         me->mr->current= me->mr->newlvl;
1265         /* Unless the render level has been set to something other than the
1266            highest level (by the user), increment the render level to match
1267            the highest available level */
1268         if(me->mr->renderlvl == me->mr->level_count - 1) me->mr->renderlvl= me->mr->level_count;
1269
1270         multires_level_to_mesh(ob, me, 0);
1271 }
1272
1273 void multires_set_level(Object *ob, Mesh *me, const int render)
1274 {
1275         if(me->pv) sculptmode_pmv_off(me);
1276
1277         check_colors(me);
1278         multires_update_levels(me, render);
1279
1280         me->mr->current= me->mr->newlvl;
1281         if(me->mr->current<1) me->mr->current= 1;
1282         else if(me->mr->current>me->mr->level_count) me->mr->current= me->mr->level_count;
1283
1284         multires_level_to_mesh(ob, me, render);
1285 }
1286
1287 /* Update the edge visibility flags to only show edges on or below the edgelvl */
1288 void multires_edge_level_update(Object *ob, Mesh *me)
1289 {
1290         if(!G.obedit) {
1291                 MultiresLevel *cr_lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1292                 MultiresLevel *edge_lvl= BLI_findlink(&me->mr->levels,me->mr->edgelvl-1);
1293                 const int threshold= edge_lvl->totedge * powf(2, me->mr->current - me->mr->edgelvl);
1294                 unsigned i;
1295
1296                 for(i=0; i<cr_lvl->totedge; ++i) {
1297                         const int ndx= me->pv ? me->pv->edge_map[i] : i;
1298                         if(ndx != -1) { /* -1= hidden edge */
1299                                 if(me->mr->edgelvl >= me->mr->current || i<threshold)
1300                                         me->medge[ndx].flag |= ME_EDGEDRAW | ME_EDGERENDER;
1301                                 else
1302                                         me->medge[ndx].flag &= ~ME_EDGEDRAW & ~ME_EDGERENDER;
1303                         }
1304                 }
1305                 
1306                 DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
1307         }
1308 }