2nd try to merge sim_physics with trunk rev 19825
[blender.git] / source / blender / blenkernel / intern / multires.c
1 /*
2  * $Id: multires.c 19805 2009-04-20 00:19:16Z genscher $
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, CustomData *fdata, int findex, 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, fdata, findex, 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 ? &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 ? &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], &me->mr->fdata, 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         /* XXX added this to prevent crash, but if it works? (ton) */
646         if(me->mr->verts==NULL)
647                 return;
648         
649         /* Prepare deltas */
650         pr_deltas= MEM_callocN(sizeof(vec3f)*last_lvl->totvert, "multires deltas 1");
651         cr_deltas= MEM_callocN(sizeof(vec3f)*last_lvl->totvert, "multires deltas 2");
652
653         /* Calculate initial deltas -- current mesh subtracted from current level*/
654         if(em) eve= em->verts.first;
655         for(i=0; i<cr_lvl->totvert; ++i) {
656                 if(em) {
657                         VecSubf(&cr_deltas[i].x, eve->co, me->mr->verts[i].co);
658                         eve= eve->next;
659                 } else
660                         VecSubf(&cr_deltas[i].x, me->mvert[i].co, me->mr->verts[i].co);
661         }
662
663
664         /* Copy current level's vertex flags and clear the rest */
665         if(em) eve= em->verts.first;    
666         for(i=0; i < last_lvl->totvert; ++i) {
667                 if(i < cr_lvl->totvert) {
668                         MVert mvflag;
669                         multires_get_vert(&mvflag, eve, &me->mvert[i], i);
670                         if(em) eve= eve->next;
671                         me->mr->verts[i].flag= mvflag.flag;
672                 }
673                 else
674                         me->mr->verts[i].flag= 0;
675         }
676
677         /* If already on the highest level, copy current verts (including flags) into current level */
678         if(cr_lvl == last_lvl) {
679                 if(em)
680                         eve= em->verts.first;
681                 for(i=0; i<cr_lvl->totvert; ++i) {
682                         multires_get_vert(&me->mr->verts[i], eve, &me->mvert[i], i);
683                         if(em) eve= eve->next;
684                 }
685         }
686
687         /* Update higher levels */
688         pr_lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
689         cr_lvl= pr_lvl->next;
690         while(cr_lvl) {
691                 multires_calc_temp_data(pr_lvl);                
692
693                 /* Swap the old/new deltas */
694                 swap_deltas= pr_deltas;
695                 pr_deltas= cr_deltas;
696                 cr_deltas= swap_deltas;
697
698                 /* Calculate and add new deltas
699                    ============================ */
700                 for(i=0; i<pr_lvl->totface; ++i) {
701                         const MultiresFace *f= &pr_lvl->faces[i];
702                         data.corner1= &pr_deltas[f->v[0]].x;
703                         data.corner2= &pr_deltas[f->v[1]].x;
704                         data.corner3= &pr_deltas[f->v[2]].x;
705                         data.corner4= &pr_deltas[f->v[3]].x;
706                         data.quad= f->v[3] ? 1 : 0;
707                         multi_apply(&cr_deltas[f->mid].x, &data, 3, catmullclark_smooth_face);
708                         
709                         for(j=0; j<(data.quad?4:3); ++j)
710                                 me->mr->verts[f->mid].flag |= me->mr->verts[f->v[j]].flag;
711                 }
712
713                 for(i=0; i<pr_lvl->totedge; ++i) {
714                         const MultiresEdge *e= &pr_lvl->edges[i];
715                         data.boundary= pr_lvl->edge_boundary_states[i];
716                         edge_face_neighbor_midpoints_accum(&data,pr_lvl,cr_deltas,sizeof(vec3f),e);
717                         data.endpoint1= &pr_deltas[e->v[0]].x;
718                         data.endpoint2= &pr_deltas[e->v[1]].x;
719                         multi_apply(&cr_deltas[e->mid].x, &data, 3, catmullclark_smooth_edge);
720                                 
721                         for(j=0; j<2; ++j)
722                                 me->mr->verts[e->mid].flag |= me->mr->verts[e->v[j]].flag;
723                 }
724
725                 for(i=0; i<pr_lvl->totvert; ++i) {
726                         data.boundary= multires_vert_is_boundary(pr_lvl,i);
727                         data.original= &pr_deltas[i].x;
728                         data.edge_count= BLI_countlist(&pr_lvl->vert_edge_map[i]);
729                         if(data.boundary)
730                                 boundary_edges_average(&data,pr_lvl,pr_deltas,sizeof(vec3f),i);
731                         else {
732                                 vert_face_neighbor_midpoints_average(&data,pr_lvl,cr_deltas,sizeof(vec3f),i);
733                                 vert_edge_neighbor_midpoints_average(&data,pr_lvl,pr_deltas,sizeof(vec3f),i);
734                         }
735                         multi_apply(&cr_deltas[i].x, &data, 3, catmullclark_smooth_vert);
736                 }
737
738                 /* Apply deltas to vertex locations */
739                 for(i=0; (cr_lvl == last_lvl) && (i < cr_lvl->totvert); ++i) {
740                         VecAddf(me->mr->verts[i].co,
741                                 me->mr->verts[i].co,
742                                 &cr_deltas[i].x);                       
743                 }
744
745                 multires_free_temp_data(pr_lvl);
746
747                 pr_lvl= pr_lvl->next;
748                 cr_lvl= cr_lvl->next;
749         }
750         if(pr_deltas) MEM_freeN(pr_deltas);
751         if(cr_deltas) MEM_freeN(cr_deltas);
752
753 }
754
755 static void multires_update_faces(Mesh *me, EditMesh *em)
756 {
757         MultiresLevel *cr_lvl= current_level(me->mr), *pr_lvl= NULL,
758                       *last_lvl= me->mr->levels.last;
759         char *pr_flag_damaged= NULL, *cr_flag_damaged= NULL, *or_flag_damaged= NULL,
760              *pr_mat_damaged= NULL, *cr_mat_damaged= NULL, *or_mat_damaged= NULL, *swap= NULL;
761         EditFace *efa= NULL;
762         unsigned i,j,curf;
763
764         /* Find for each face whether flag/mat has changed */
765         pr_flag_damaged= MEM_callocN(sizeof(char) * last_lvl->totface, "flag_damaged 1");
766         cr_flag_damaged= MEM_callocN(sizeof(char) * last_lvl->totface, "flag_damaged 1");
767         pr_mat_damaged= MEM_callocN(sizeof(char) * last_lvl->totface, "mat_damaged 1");
768         cr_mat_damaged= MEM_callocN(sizeof(char) * last_lvl->totface, "mat_damaged 1");
769         if(em) efa= em->faces.first;
770         for(i=0; i<cr_lvl->totface; ++i) {
771                 MultiresFace mftmp;
772                 multires_get_face(&mftmp, &me->mr->fdata, i, efa, &me->mface[i]);
773                 if(cr_lvl->faces[i].flag != mftmp.flag)
774                         cr_flag_damaged[i]= 1;
775                 if(cr_lvl->faces[i].mat_nr != mftmp.mat_nr)
776                         cr_mat_damaged[i]= 1;
777
778                 /* Update current level */
779                 cr_lvl->faces[i].flag= mftmp.flag;
780                 cr_lvl->faces[i].mat_nr= mftmp.mat_nr;
781
782                 if(em) efa= efa->next;
783         }
784         or_flag_damaged= MEM_dupallocN(cr_flag_damaged);
785         or_mat_damaged= MEM_dupallocN(cr_mat_damaged);
786
787         /* Update lower levels */
788         cr_lvl= cr_lvl->prev;
789         while(cr_lvl) {
790                 swap= pr_flag_damaged;
791                 pr_flag_damaged= cr_flag_damaged;
792                 cr_flag_damaged= swap;
793
794                 swap= pr_mat_damaged;
795                 pr_mat_damaged= cr_mat_damaged;
796                 cr_mat_damaged= swap;
797
798                 curf= 0;
799                 for(i=0; i<cr_lvl->totface; ++i) {
800                         const int sides= cr_lvl->faces[i].v[3] ? 4 : 3;
801                         
802                         /* Check damages */
803                         for(j=0; j<sides; ++j, ++curf) {
804                                 if(pr_flag_damaged[curf]) {
805                                         cr_lvl->faces[i].flag= cr_lvl->next->faces[curf].flag;
806                                         cr_flag_damaged[i]= 1;
807                                 }
808                                 if(pr_mat_damaged[curf]) {
809                                         cr_lvl->faces[i].mat_nr= cr_lvl->next->faces[curf].mat_nr;
810                                         cr_mat_damaged[i]= 1;
811                                 }
812                         }
813                 }
814
815                 cr_lvl= cr_lvl->prev;
816         }
817         
818         /* Clear to original damages */
819         if(cr_flag_damaged) MEM_freeN(cr_flag_damaged);
820         if(cr_mat_damaged) MEM_freeN(cr_mat_damaged);
821         cr_flag_damaged= or_flag_damaged;
822         cr_mat_damaged= or_mat_damaged;
823         
824         /* Update higher levels */
825         pr_lvl= current_level(me->mr);
826         cr_lvl= pr_lvl->next;
827         while(cr_lvl) {
828                 swap= pr_flag_damaged;
829                 pr_flag_damaged= cr_flag_damaged;
830                 cr_flag_damaged= swap;
831
832                 swap= pr_mat_damaged;
833                 pr_mat_damaged= cr_mat_damaged;
834                 cr_mat_damaged= swap;
835
836                 /* Update faces */
837                 for(i=0, curf= 0; i<pr_lvl->totface; ++i) {
838                         const int sides= cr_lvl->prev->faces[i].v[3] ? 4 : 3;
839                         for(j=0; j<sides; ++j, ++curf) {
840                                 if(pr_flag_damaged[i]) {
841                                         cr_lvl->faces[curf].flag= pr_lvl->faces[i].flag;
842                                         cr_flag_damaged[curf]= 1;
843                                 }
844                                 if(pr_mat_damaged[i]) {
845                                         cr_lvl->faces[curf].mat_nr= pr_lvl->faces[i].mat_nr;
846                                         cr_mat_damaged[curf]= 1;
847                                 }
848                         }
849                 }
850
851                 pr_lvl= pr_lvl->next;
852                 cr_lvl= cr_lvl->next;
853         }
854
855         if(pr_flag_damaged) MEM_freeN(pr_flag_damaged);
856         if(cr_flag_damaged) MEM_freeN(cr_flag_damaged);
857         if(pr_mat_damaged) MEM_freeN(pr_mat_damaged);
858         if(cr_mat_damaged) MEM_freeN(cr_mat_damaged);
859 }
860
861 static void multires_update_colors(Mesh *me, EditMesh *em)
862 {
863         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
864         MultiresCol *pr_deltas= NULL, *cr_deltas= NULL;
865         CustomData *src= em ? &em->fdata : &me->fdata;
866         EditFace *efa= NULL;
867         unsigned i,j,curf= 0;
868         
869         if(me->mr->use_col) {
870                 /* Calc initial deltas */
871                 cr_deltas= MEM_callocN(sizeof(MultiresCol)*lvl->totface*4,"initial color/uv deltas");
872
873                 if(em) efa= em->faces.first;
874                 for(i=0; i<lvl->totface; ++i) {
875                         MCol *col= em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4];
876                         for(j=0; j<4; ++j) {
877                                 if(me->mr->use_col) {
878                                         cr_deltas[i*4+j].a= col[j].a - lvl->colfaces[i].col[j].a;
879                                         cr_deltas[i*4+j].r= col[j].r - lvl->colfaces[i].col[j].r;
880                                         cr_deltas[i*4+j].g= col[j].g - lvl->colfaces[i].col[j].g;
881                                         cr_deltas[i*4+j].b= col[j].b - lvl->colfaces[i].col[j].b;
882                                 }
883                         }
884                         if(em) efa= efa->next;
885                 }
886                 
887                 /* Update current level */
888                 if(em) efa= em->faces.first;
889                 for(i=0; i<lvl->totface; ++i) {
890                         MultiresColFace *f= &lvl->colfaces[i];
891
892                         if(me->mr->use_col)
893                                 mcol_to_multires(f, em ? CustomData_em_get(src, efa->data, CD_MCOL) : &me->mcol[i*4]);
894                         
895                         if(em) efa= efa->next;
896                 }
897                 
898                 /* Update higher levels */
899                 lvl= lvl->next;
900                 while(lvl) {
901                         /* Set up new deltas, but keep the ones from the previous level */
902                         if(pr_deltas) MEM_freeN(pr_deltas);
903                         pr_deltas= cr_deltas;
904                         cr_deltas= MEM_callocN(sizeof(MultiresCol)*lvl->totface*4,"color deltas");
905
906                         curf= 0;
907                         for(i=0; i<lvl->prev->totface; ++i) {
908                                 const char sides= lvl->prev->faces[i].v[3]?4:3;
909                                 MultiresCol cntr;
910                                 
911                                 /* Find average color of 4 (or 3 for triangle) verts */
912                                 multires_col_avg(&cntr,&pr_deltas[i*4],sides);
913                                 
914                                 for(j=0; j<sides; ++j) {
915                                         multires_col_avg2(&cr_deltas[curf*4],
916                                                           &pr_deltas[i*4+j],
917                                                           &pr_deltas[i*4+(j==0?sides-1:j-1)]);
918                                         cr_deltas[curf*4+1]= pr_deltas[i*4+j];
919                                         multires_col_avg2(&cr_deltas[curf*4+2],
920                                                           &pr_deltas[i*4+j],
921                                                           &pr_deltas[i*4+(j==sides-1?0:j+1)]);
922                                         cr_deltas[curf*4+3]= cntr;
923                                         ++curf;
924                                 }
925                         }
926
927                         for(i=0; i<lvl->totface; ++i) {
928                                 for(j=0; j<4; ++j) {
929                                         lvl->colfaces[i].col[j].a+= cr_deltas[i*4+j].a;
930                                         lvl->colfaces[i].col[j].r+= cr_deltas[i*4+j].r;
931                                         lvl->colfaces[i].col[j].g+= cr_deltas[i*4+j].g;
932                                         lvl->colfaces[i].col[j].b+= cr_deltas[i*4+j].b;
933                                 }
934                         }
935
936                         lvl= lvl->next;
937                 }
938                 if(pr_deltas) MEM_freeN(pr_deltas);
939                 if(cr_deltas) MEM_freeN(cr_deltas);
940                 
941                 /* Update lower levels */
942                 lvl= me->mr->levels.last;
943                 lvl= lvl->prev;
944                 while(lvl) {
945                         MultiresColFace *nf= lvl->next->colfaces;
946                         for(i=0; i<lvl->totface; ++i) {
947                                 MultiresFace *f= &lvl->faces[i];
948                                 for(j=0; j<(f->v[3]?4:3); ++j) {
949                                         lvl->colfaces[i].col[j]= nf->col[1];
950                                         ++nf;
951                                 }
952                         }
953                         lvl= lvl->prev;
954                 }
955         }
956 }
957
958 void multires_update_levels(Mesh *me, const int render)
959 {
960         EditMesh *em= (!render && G.obedit) ? G.editMesh : NULL;
961
962         multires_update_first_level(me, em);
963         multires_update_vertices(me, em);
964         multires_update_faces(me, em);
965         multires_update_colors(me, em);
966 }
967
968 static void check_colors(Mesh *me)
969 {
970         CustomData *src= G.obedit ? &G.editMesh->fdata : &me->fdata;
971         const char col= CustomData_has_layer(src, CD_MCOL);
972
973         /* Check if vertex colors have been deleted or added */
974         if(me->mr->use_col && !col)
975                 me->mr->use_col= 0;
976         else if(!me->mr->use_col && col) {
977                 me->mr->use_col= 1;
978                 multires_load_cols(me);
979         }
980 }
981
982 static unsigned int find_mid_edge(ListBase *vert_edge_map,
983                                   MultiresLevel *lvl,
984                                   const unsigned int v1,
985                                   const unsigned int v2 )
986 {
987         MultiresMapNode *n= vert_edge_map[v1].first;
988         while(n) {
989                 if(lvl->edges[n->Index].v[0]==v2 ||
990                    lvl->edges[n->Index].v[1]==v2)
991                         return lvl->edges[n->Index].mid;
992
993                 n= n->next;
994         }
995         return -1;
996 }
997
998 static float clamp_component(const float c)
999 {
1000         if(c<0) return 0;
1001         else if(c>255) return 255;
1002         else return c;
1003 }
1004
1005 void multires_to_mcol(MultiresColFace *f, MCol mcol[4])
1006 {
1007         unsigned char j;
1008         for(j=0; j<4; ++j) {
1009                 mcol->a= clamp_component(f->col[j].a);
1010                 mcol->r= clamp_component(f->col[j].r);
1011                 mcol->g= clamp_component(f->col[j].g);
1012                 mcol->b= clamp_component(f->col[j].b);
1013                 ++mcol;
1014         }
1015 }
1016
1017 void multires_level_to_mesh(Object *ob, Mesh *me, const int render)
1018 {
1019         MultiresLevel *lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1020         int i;
1021         EditMesh *em= (!render && G.obedit) ? G.editMesh : NULL;
1022         
1023         if(em)
1024                 return;
1025
1026         CustomData_free_layer_active(&me->vdata, CD_MVERT, me->totvert);
1027         CustomData_free_layer_active(&me->edata, CD_MEDGE, me->totedge);
1028         CustomData_free_layer_active(&me->fdata, CD_MFACE, me->totface);
1029         CustomData_free_layer_active(&me->vdata, CD_MDEFORMVERT, me->totvert);
1030         CustomData_free_layers(&me->fdata, CD_MTFACE, me->totface);
1031         CustomData_free_layers(&me->fdata, CD_MCOL, me->totface);
1032                 
1033         me->totvert= lvl->totvert;
1034         me->totface= lvl->totface;
1035         me->totedge= lvl->totedge;
1036
1037         CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, me->totvert);
1038         CustomData_add_layer(&me->edata, CD_MEDGE, CD_CALLOC, NULL, me->totedge);
1039         CustomData_add_layer(&me->fdata, CD_MFACE, CD_CALLOC, NULL, me->totface);
1040         mesh_update_customdata_pointers(me);
1041
1042         /* Vertices/Edges/Faces */
1043         
1044         for(i=0; i<lvl->totvert; ++i) {
1045                 me->mvert[i]= me->mr->verts[i];
1046         }
1047         for(i=0; i<lvl->totedge; ++i) {
1048                 me->medge[i].v1= lvl->edges[i].v[0];
1049                 me->medge[i].v2= lvl->edges[i].v[1];
1050                 me->medge[i].flag &= ~ME_HIDE;
1051         }
1052         for(i=0; i<lvl->totface; ++i) {
1053                 me->mface[i].v1= lvl->faces[i].v[0];
1054                 me->mface[i].v2= lvl->faces[i].v[1];
1055                 me->mface[i].v3= lvl->faces[i].v[2];
1056                 me->mface[i].v4= lvl->faces[i].v[3];
1057                 me->mface[i].flag= lvl->faces[i].flag;
1058                 me->mface[i].flag &= ~ME_HIDE;
1059                 me->mface[i].mat_nr= lvl->faces[i].mat_nr;
1060         }
1061         
1062         /* Edge flags */
1063         if(lvl==me->mr->levels.first) {
1064                 for(i=0; i<lvl->totedge; ++i) {
1065                         me->medge[i].flag= me->mr->edge_flags[i];
1066                         me->medge[i].crease= me->mr->edge_creases[i];
1067                 }
1068         } else {
1069                 MultiresLevel *lvl1= me->mr->levels.first;
1070                 const int last= lvl1->totedge * pow(2, me->mr->current-1);
1071                 for(i=0; i<last; ++i) {
1072                         const int ndx= i / pow(2, me->mr->current-1);
1073                         
1074                         me->medge[i].flag= me->mr->edge_flags[ndx];
1075                         me->medge[i].crease= me->mr->edge_creases[ndx];
1076                 }
1077         }
1078
1079         multires_customdata_to_mesh(me, em, lvl, &me->mr->vdata, em ? &em->vdata : &me->vdata, CD_MDEFORMVERT);
1080         multires_customdata_to_mesh(me, em, lvl, &me->mr->fdata, em ? &em->fdata : &me->fdata, CD_MTFACE);
1081
1082         /* Colors */
1083         if(me->mr->use_col) {
1084                 CustomData *src= &me->fdata;
1085                 
1086                 if(me->mr->use_col) me->mcol= CustomData_add_layer(src, CD_MCOL, CD_CALLOC, NULL, me->totface);
1087                 
1088                 for(i=0; i<lvl->totface; ++i) {
1089                         if(me->mr->use_col)
1090                                 multires_to_mcol(&lvl->colfaces[i], &me->mcol[i*4]);
1091                 }
1092                         
1093         }
1094         
1095         mesh_update_customdata_pointers(me);
1096         
1097         multires_edge_level_update(ob,me);
1098         DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
1099         mesh_calc_normals(me->mvert, me->totvert, me->mface, me->totface, NULL);
1100 }
1101
1102 void multires_add_level(Object *ob, Mesh *me, const char subdiv_type)
1103 {
1104         int i,j, curf, cure;
1105         MultiresLevel *lvl= NULL;
1106         MultiApplyData data;
1107         MVert *oldverts= NULL;
1108         
1109         lvl= MEM_callocN(sizeof(MultiresLevel), "multireslevel");
1110         if(me->pv) mesh_pmv_off(ob, me);
1111
1112         check_colors(me);
1113         multires_update_levels(me, 0);
1114
1115         ++me->mr->level_count;
1116         BLI_addtail(&me->mr->levels,lvl);
1117
1118         /* Create vertices
1119            =============== */
1120         lvl->totvert= lvl->prev->totvert + lvl->prev->totedge + lvl->prev->totface;
1121         oldverts= me->mr->verts;
1122         me->mr->verts= MEM_callocN(sizeof(MVert)*lvl->totvert, "multitres verts");
1123         /* Copy old verts */
1124         for(i=0; i<lvl->prev->totvert; ++i)
1125                 me->mr->verts[i]= oldverts[i];
1126         /* Create new edge verts */
1127         for(i=0; i<lvl->prev->totedge; ++i) {
1128                 VecMidf(me->mr->verts[lvl->prev->totvert + i].co,
1129                         oldverts[lvl->prev->edges[i].v[0]].co,
1130                         oldverts[lvl->prev->edges[i].v[1]].co);
1131                 lvl->prev->edges[i].mid= lvl->prev->totvert + i;
1132         }
1133         /* Create new face verts */
1134         for(i=0; i<lvl->prev->totface; ++i) {
1135                 lvl->prev->faces[i].mid= lvl->prev->totvert + lvl->prev->totedge + i;
1136         }
1137
1138         multires_calc_temp_data(lvl->prev);
1139
1140         /* Create faces
1141            ============ */
1142         /* Allocate all the new faces (each triangle creates three, and
1143            each quad creates four */
1144         lvl->totface= 0;
1145         for(i=0; i<lvl->prev->totface; ++i)
1146                 lvl->totface+= lvl->prev->faces[i].v[3] ? 4 : 3;
1147         lvl->faces= MEM_callocN(sizeof(MultiresFace)*lvl->totface,"multires faces");
1148
1149         curf= 0;
1150         for(i=0; i<lvl->prev->totface; ++i) {
1151                 const int max= lvl->prev->faces[i].v[3] ? 3 : 2;
1152                 
1153                 for(j=0; j<max+1; ++j) {
1154                         lvl->faces[curf].v[0]= find_mid_edge(lvl->prev->vert_edge_map,lvl->prev,
1155                                                              lvl->prev->faces[i].v[j],
1156                                                              lvl->prev->faces[i].v[j==0?max:j-1]);
1157                         lvl->faces[curf].v[1]= lvl->prev->faces[i].v[j];
1158                         lvl->faces[curf].v[2]= find_mid_edge(lvl->prev->vert_edge_map,lvl->prev,
1159                                                              lvl->prev->faces[i].v[j],
1160                                                              lvl->prev->faces[i].v[j==max?0:j+1]);
1161                         lvl->faces[curf].v[3]= lvl->prev->totvert + lvl->prev->totedge + i;
1162                         lvl->faces[curf].flag= lvl->prev->faces[i].flag;
1163                         lvl->faces[curf].mat_nr= lvl->prev->faces[i].mat_nr;
1164
1165                         ++curf;
1166                 }
1167         }
1168
1169         /* Create edges
1170            ============ */
1171         /* Figure out how many edges to allocate */
1172         lvl->totedge= lvl->prev->totedge*2;
1173         for(i=0; i<lvl->prev->totface; ++i)
1174                 lvl->totedge+= lvl->prev->faces[i].v[3]?4:3;
1175         lvl->edges= MEM_callocN(sizeof(MultiresEdge)*lvl->totedge,"multires edges");
1176
1177         for(i=0; i<lvl->prev->totedge; ++i) {
1178                 lvl->edges[i*2].v[0]= lvl->prev->edges[i].v[0];
1179                 lvl->edges[i*2].v[1]= lvl->prev->edges[i].mid;
1180                 lvl->edges[i*2+1].v[0]= lvl->prev->edges[i].mid;
1181                 lvl->edges[i*2+1].v[1]= lvl->prev->edges[i].v[1];
1182         }
1183         /* Add edges inside of old polygons */
1184         curf= 0;
1185         cure= lvl->prev->totedge*2;
1186         for(i=0; i<lvl->prev->totface; ++i) {
1187                 for(j=0; j<(lvl->prev->faces[i].v[3]?4:3); ++j) {
1188                         lvl->edges[cure].v[0]= lvl->faces[curf].v[2];
1189                         lvl->edges[cure].v[1]= lvl->faces[curf].v[3];
1190                         ++cure;
1191                         ++curf;
1192                 }
1193         }
1194
1195         /* Smooth vertices
1196            =============== */
1197         for(i=0; i<lvl->prev->totface; ++i) {
1198                 const MultiresFace *f= &lvl->prev->faces[i];
1199                 data.corner1= oldverts[f->v[0]].co;
1200                 data.corner2= oldverts[f->v[1]].co;
1201                 data.corner3= oldverts[f->v[2]].co;
1202                 data.corner4= oldverts[f->v[3]].co;
1203                 data.quad= f->v[3] ? 1 : 0;
1204                 multi_apply(me->mr->verts[f->mid].co, &data, 3, catmullclark_smooth_face);
1205         }
1206
1207         if(subdiv_type == 0) {
1208                 for(i=0; i<lvl->prev->totedge; ++i) {
1209                         const MultiresEdge *e= &lvl->prev->edges[i];
1210                         data.boundary= lvl->prev->edge_boundary_states[i];
1211                         edge_face_neighbor_midpoints_accum(&data,lvl->prev, me->mr->verts, sizeof(MVert),e);
1212                         data.endpoint1= oldverts[e->v[0]].co;
1213                         data.endpoint2= oldverts[e->v[1]].co;
1214                         multi_apply(me->mr->verts[e->mid].co, &data, 3, catmullclark_smooth_edge);
1215                 }
1216                 
1217                 for(i=0; i<lvl->prev->totvert; ++i) {
1218                         data.boundary= multires_vert_is_boundary(lvl->prev,i);
1219                         data.original= oldverts[i].co;
1220                         data.edge_count= BLI_countlist(&lvl->prev->vert_edge_map[i]);
1221                         if(data.boundary)
1222                                 boundary_edges_average(&data,lvl->prev, oldverts, sizeof(MVert),i);
1223                         else {
1224                                 vert_face_neighbor_midpoints_average(&data,lvl->prev, me->mr->verts,
1225                                                                      sizeof(MVert),i);
1226                                 vert_edge_neighbor_midpoints_average(&data,lvl->prev, oldverts,
1227                                                                      sizeof(MVert),i);
1228                         }
1229                         multi_apply(me->mr->verts[i].co, &data, 3, catmullclark_smooth_vert);
1230                 }
1231         }
1232
1233         multires_free_temp_data(lvl->prev);
1234         MEM_freeN(oldverts);
1235
1236         /* Vertex Colors
1237            ============= */
1238         curf= 0;
1239         if(me->mr->use_col) {
1240                 MultiresColFace *cf= MEM_callocN(sizeof(MultiresColFace)*lvl->totface,"Multirescolfaces");
1241                 lvl->colfaces= cf;
1242                 for(i=0; i<lvl->prev->totface; ++i) {
1243                         const char sides= lvl->prev->faces[i].v[3]?4:3;
1244                         MultiresCol cntr;
1245
1246                         /* Find average color of 4 (or 3 for triangle) verts */
1247                         multires_col_avg(&cntr,lvl->prev->colfaces[i].col,sides);
1248
1249                         for(j=0; j<sides; ++j) {
1250                                 multires_col_avg2(&cf->col[0],
1251                                                   &lvl->prev->colfaces[i].col[j],
1252                                                   &lvl->prev->colfaces[i].col[j==0?sides-1:j-1]);
1253                                 cf->col[1]= lvl->prev->colfaces[i].col[j];
1254                                 multires_col_avg2(&cf->col[2],
1255                                                   &lvl->prev->colfaces[i].col[j],
1256                                                   &lvl->prev->colfaces[i].col[j==sides-1?0:j+1]);
1257                                 cf->col[3]= cntr;
1258
1259                                 ++cf;
1260                         }
1261                 }
1262         }
1263
1264         me->mr->newlvl= me->mr->level_count;
1265         me->mr->current= me->mr->newlvl;
1266         /* Unless the render level has been set to something other than the
1267            highest level (by the user), increment the render level to match
1268            the highest available level */
1269         if(me->mr->renderlvl == me->mr->level_count - 1) me->mr->renderlvl= me->mr->level_count;
1270
1271         multires_level_to_mesh(ob, me, 0);
1272 }
1273
1274 void multires_set_level(Object *ob, Mesh *me, const int render)
1275 {
1276         if(me->pv) mesh_pmv_off(ob, me);
1277
1278         check_colors(me);
1279         multires_update_levels(me, render);
1280
1281         me->mr->current= me->mr->newlvl;
1282         if(me->mr->current<1) me->mr->current= 1;
1283         else if(me->mr->current>me->mr->level_count) me->mr->current= me->mr->level_count;
1284
1285         multires_level_to_mesh(ob, me, render);
1286 }
1287
1288 /* Update the edge visibility flags to only show edges on or below the edgelvl */
1289 void multires_edge_level_update(Object *ob, Mesh *me)
1290 {
1291         if(!G.obedit) {
1292                 MultiresLevel *cr_lvl= BLI_findlink(&me->mr->levels,me->mr->current-1);
1293                 MultiresLevel *edge_lvl= BLI_findlink(&me->mr->levels,me->mr->edgelvl-1);
1294                 const int threshold= edge_lvl->totedge * pow(2, me->mr->current - me->mr->edgelvl);
1295                 unsigned i;
1296
1297                 for(i=0; i<cr_lvl->totedge; ++i) {
1298                         const int ndx= me->pv ? me->pv->edge_map[i] : i;
1299                         if(ndx != -1) { /* -1= hidden edge */
1300                                 if(me->mr->edgelvl >= me->mr->current || i<threshold)
1301                                         me->medge[ndx].flag |= ME_EDGEDRAW | ME_EDGERENDER;
1302                                 else
1303                                         me->medge[ndx].flag &= ~ME_EDGEDRAW & ~ME_EDGERENDER;
1304                         }
1305                 }
1306                 
1307                 DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
1308         }
1309 }