- added Mesh->derived and Mesh->decimated DerivedMesh pointers
[blender.git] / source / blender / blenkernel / intern / subsurf.c
1
2 /*  subsurf.c
3  * 
4  *  jun 2001
5  *  
6  * 
7  * $Id$
8  *
9  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version. The Blender
15  * Foundation also sells licenses for use in proprietary software under
16  * the Blender License.  See http://www.blender.org/BL/ for information
17  * about this.
18  *
19  * This program is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
22  * GNU General Public License for more details.
23  *
24  * You should have received a copy of the GNU General Public License
25  * along with this program; if not, write to the Free Software Foundation,
26  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
27  *
28  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
29  * All rights reserved.
30  *
31  * The Original Code is: all of this file.
32  *
33  * Contributor(s): none yet.
34  *
35  * ***** END GPL/BL DUAL LICENSE BLOCK *****
36  */
37
38 #ifdef HAVE_CONFIG_H
39 #include <config.h>
40 #endif
41
42 #include <stdlib.h>
43 #include <stdio.h>
44 #include <math.h>
45 #include "MEM_guardedalloc.h"
46
47 #include "DNA_mesh_types.h"
48 #include "DNA_meshdata_types.h"
49 #include "DNA_object_types.h"
50
51 #include "BKE_bad_level_calls.h"
52 #include "BKE_global.h"
53 #include "BKE_mesh.h"
54 #include "BKE_subsurf.h"
55 #include "BKE_displist.h"
56 #include "BKE_DerivedMesh.h"
57
58 #include "BLI_blenlib.h"
59 #include "BLI_editVert.h"
60 #include "BLI_arithb.h"
61 #include "BLI_linklist.h"
62 #include "BLI_memarena.h"
63
64 /*
65  * TODO
66  * 
67  * make uvco's && vcol's properly subdivided
68  *   - requires moving uvco and vcol data to vertices 
69  *        (where it belongs?), or making sharedness explicit
70  * remove/integrate zsl functions
71  * clean up uvco && vcol stuff
72  * add option to update subsurf only after done transverting
73  * decouple display subdivlevel and render subdivlevel
74  * look into waves/particles with subsurfs
75  * groan... make it work with sticky? 
76  * U check if storing tfaces (clut, tpage) in a displist is 
77  *     going to be a mem problem (for example, on duplicate)
78  * U write game blender convert routine
79  * U thorough rendering check + background
80  * 
81  */
82
83 /****/
84
85 static float *Vec2Cpy(float *t, float *a) {
86         t[0]= a[0];
87         t[1]= a[1];
88         return t;
89 }
90 static float *Vec3Cpy(float *t, float *a) {
91         t[0]= a[0];
92         t[1]= a[1];
93         t[2]= a[2];
94         return t;
95 }
96
97 static float *Vec2CpyI(float *t, float x, float y) {
98         t[0]= x;
99         t[1]= y;
100         return t;
101 }
102 static float *Vec3CpyI(float *t, float x, float y, float z) {
103         t[0]= x;
104         t[1]= y;
105         t[2]= z;
106         return t;
107 }
108
109 static float *Vec2AvgT(float *t, float *a, float *b) {
110         t[0]= (a[0]+b[0])*0.5f;
111         t[1]= (a[1]+b[1])*0.5f;
112         return t;
113 }
114 static float *Vec3AvgT(float *t, float *a, float *b) {
115         t[0]= (a[0]+b[0])*0.5f;
116         t[1]= (a[1]+b[1])*0.5f;
117         t[2]= (a[2]+b[2])*0.5f;
118         return t;
119 }
120
121 static float *Vec3AddT(float *t, float *a, float *b) {
122         t[0]= a[0]+b[0];
123         t[1]= a[1]+b[1];
124         t[2]= a[2]+b[2];
125         return t;
126 }
127 static float *Vec2Add(float *ta, float *b) {
128         ta[0]+= b[0];
129         ta[1]+= b[1];
130         return ta;
131 }
132
133
134 static float *Vec3MulNT(float *t, float *a, float n) {
135         t[0]= a[0]*n;
136         t[1]= a[1]*n;
137         t[2]= a[2]*n;
138         return t;
139 }
140
141 static float *Vec3Add(float *ta, float *b) {
142         ta[0]+= b[0];
143         ta[1]+= b[1];
144         ta[2]+= b[2];
145         return ta;
146 }
147
148 static float *Vec2MulN(float *ta, float n) {
149         ta[0]*= n;
150         ta[1]*= n;
151         return ta;
152 }
153 static float *Vec3MulN(float *ta, float n) {
154         ta[0]*= n;
155         ta[1]*= n;
156         ta[2]*= n;
157         return ta;
158 }
159
160 /****/
161
162 typedef struct _HyperVert HyperVert;
163 typedef struct _HyperEdge HyperEdge;
164 typedef struct _HyperFace HyperFace;
165 typedef struct _HyperMesh HyperMesh;
166
167 struct _HyperVert {
168         HyperVert *next;
169         
170         float co[3];
171         EditVert *orig; // if set, pointer to original vertex
172         HyperVert *nmv;
173         LinkNode *edges, *faces;
174 };
175
176 /* hyper edge flags */
177 #define DR_OPTIM        1
178 #define HE_SEAM     2
179
180 struct _HyperEdge {
181         HyperEdge *next;
182
183         HyperVert *v[2];
184         HyperVert *ep;
185         int flag;               // added for drawing optimal
186         float sharp;    // sharpness weight
187         EditEdge *ee;   // for selection state
188         LinkNode *faces;
189 };
190
191 struct _HyperFace {
192         HyperFace *next;
193
194         int nverts;
195         HyperVert **verts;      
196         HyperEdge **edges;
197         
198         HyperVert *mid;
199
200         unsigned char (*vcol)[4];
201         float (*uvco)[2];
202         short unwrap;
203                 
204                 /* for getting back tface, matnr, etc */
205         union {
206                 int ind;
207                 EditFace *ef;
208         } orig;
209 };
210
211 struct _HyperMesh {
212         HyperVert *verts;
213         HyperEdge *edges;
214         HyperFace *faces;
215         HyperFace *lastface;    // we add faces in same order they get delivered now (ton)
216         Mesh *orig_me;
217         short hasuvco, hasvcol;
218         
219         MemArena *arena;
220 };
221
222 /***/
223
224 static HyperEdge *hypervert_find_edge(HyperVert *v, HyperVert *to) {
225         LinkNode *l;
226         
227         for (l= v->edges; l; l= l->next) {
228                 HyperEdge *e= l->link;
229                 
230                 if ((e->v[0]==v&&e->v[1]==to) || (e->v[1]==v&&e->v[0]==to))
231                          return e;
232         }
233
234         return NULL;
235 }
236
237 static int hyperedge_is_boundary(HyperEdge *e) {
238                 /* len(e->faces) <= 1 */
239         return (!e->faces || !e->faces->next);
240 }
241
242 static int hypervert_is_boundary(HyperVert *v) {
243         LinkNode *l;
244         
245         for (l= v->edges; l; l= l->next)
246                 if (hyperedge_is_boundary(l->link))
247                         return 1;
248                         
249         return 0;
250 }
251
252 static HyperVert *hyperedge_other_vert(HyperEdge *e, HyperVert *a) {
253         return (a==e->v[0])?e->v[1]:e->v[0];
254 }
255
256 static HyperVert *hypermesh_add_vert(HyperMesh *hme, float *co, EditVert *orig) {
257         HyperVert *hv= BLI_memarena_alloc(hme->arena, sizeof(*hv));
258         
259         hv->nmv= NULL;
260         hv->edges= NULL;
261         hv->faces= NULL;
262         
263         Vec3Cpy(hv->co, co);
264         hv->orig= orig;
265         
266         hv->next= hme->verts;
267         hme->verts= hv;
268         
269         return hv;
270 }
271
272 static HyperEdge *hypermesh_add_edge(HyperMesh *hme, 
273                         HyperVert *v1, HyperVert *v2, int flag, float sharp, EditEdge *ee) {
274         HyperEdge *he= BLI_memarena_alloc(hme->arena, sizeof(*he));
275         
276         BLI_linklist_prepend_arena(&v1->edges, he, hme->arena);
277         BLI_linklist_prepend_arena(&v2->edges, he, hme->arena);
278
279         he->v[0]= v1;
280         he->v[1]= v2;
281         he->ep= NULL;
282         he->faces= NULL;
283         he->sharp = sharp;
284         he->flag= flag;
285         he->ee= ee;
286         
287         he->next= hme->edges;
288         hme->edges= he;
289         
290         return he;
291 }
292
293 static HyperFace *hypermesh_add_face(HyperMesh *hme, HyperVert **verts, int nverts, int flag) {
294         HyperFace *f= BLI_memarena_alloc(hme->arena, sizeof(*f));
295         HyperVert *last;
296         int j;
297
298         f->mid= NULL;
299         f->vcol= NULL;
300         f->uvco= NULL;
301
302         f->nverts= nverts;
303         f->verts= BLI_memarena_alloc(hme->arena, sizeof(*f->verts)*f->nverts);
304         f->edges= BLI_memarena_alloc(hme->arena, sizeof(*f->edges)*f->nverts);
305         
306         last= verts[nverts-1];
307         for (j=0; j<nverts; j++) {
308                 HyperVert *v= verts[j];
309                 HyperEdge *e= hypervert_find_edge(v, last);
310
311                 if (!e)
312                         e= hypermesh_add_edge(hme, v, last, flag, 0, NULL);
313
314                 f->verts[j]= v;
315                 f->edges[j]= e;
316
317                 BLI_linklist_prepend_arena(&v->faces, f, hme->arena);
318                 BLI_linklist_prepend_arena(&e->faces, f, hme->arena);
319                 
320                 last= v;
321         }
322
323         // less elegant, but for many reasons i prefer the order of faces to remain same (vpaint etc) (ton)
324         f->next= NULL;
325         if(hme->lastface) hme->lastface->next= f;
326         else hme->faces= f;
327         hme->lastface= f;
328
329         return f;       
330 }
331
332 static HyperMesh *hypermesh_new(void) {
333         HyperMesh *hme= MEM_mallocN(sizeof(*hme), "hme");
334
335         hme->verts= NULL;
336         hme->edges= NULL;
337         hme->faces= hme->lastface= NULL;
338         hme->orig_me= NULL;
339         hme->hasuvco= hme->hasvcol= 0;
340         hme->arena= BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE);
341         
342         return hme;
343 }
344
345 static HyperMesh *hypermesh_from_mesh(Mesh *me, int subdivLevels) {
346         HyperMesh *hme= hypermesh_new();
347         HyperVert **vert_tbl;
348         MFace *mface= me->mface;
349         MEdge *medge= me->medge;
350         float creasefac= ((float)subdivLevels)/255.0; // in Mesh sharpness is byte
351         int i, j, flag;
352
353         hme->orig_me= me;
354         if (me->tface)
355                 hme->hasvcol= hme->hasuvco= 1;
356         else if (me->mcol)
357                 hme->hasvcol= 1;
358                 
359         vert_tbl= MEM_mallocN(sizeof(*vert_tbl)*me->totvert, "vert_tbl");
360         
361         for (i= 0; i<me->totvert; i++) {
362                 vert_tbl[i]= hypermesh_add_vert(hme, me->mvert[i].co, NULL);
363         }
364
365         if(medge) {
366                 for (i=0; i<me->totedge; i++) {
367                         MEdge *med= &medge[i];
368
369                         flag= DR_OPTIM;
370                         if(med->flag & ME_SEAM) flag |= HE_SEAM;
371                         
372                         hypermesh_add_edge(hme, vert_tbl[med->v1], vert_tbl[med->v2], flag, 
373                                 creasefac*((float)med->crease), NULL);
374                 }
375         }
376
377         for (i=0; i<me->totface; i++) {
378                 MFace *mf= &mface[i];
379                 
380                 if (mf->v3) {
381                         int nverts= mf->v4?4:3;
382                         HyperVert *verts[4];
383                         HyperFace *f;
384                 
385                         verts[0]= vert_tbl[mf->v1];
386                         verts[1]= vert_tbl[mf->v2];
387                         verts[2]= vert_tbl[mf->v3];
388                         if (nverts>3)
389                                 verts[3]= vert_tbl[mf->v4];
390                 
391                         f= hypermesh_add_face(hme, verts, nverts, DR_OPTIM); 
392                         f->orig.ind= i;
393
394                         if (hme->hasuvco) {
395                                 TFace *tf= &((TFace*) me->tface)[i];
396                         
397                                 f->uvco= BLI_memarena_alloc(hme->arena, sizeof(*f->uvco)*nverts);
398                                 for (j=0; j<nverts; j++)
399                                         Vec2Cpy(f->uvco[j], tf->uv[j]);
400
401                                 f->vcol= BLI_memarena_alloc(hme->arena, sizeof(*f->vcol)*nverts);
402                                 for (j=0; j<nverts; j++)
403                                         *((unsigned int*) f->vcol[j])= tf->col[j];
404
405                                 f->unwrap= tf->unwrap;
406                         } else if (hme->hasvcol) {
407                                 MCol *mcol= &me->mcol[i*4];
408                         
409                                 f->vcol= BLI_memarena_alloc(hme->arena, sizeof(*f->vcol)*nverts);
410                                 for (j=0; j<nverts; j++)
411                                         *((unsigned int*) f->vcol[j])= *((unsigned int*) &mcol[j]);
412                         }
413                 } else if(medge==NULL) {
414                         hypermesh_add_edge(hme, vert_tbl[mf->v1], vert_tbl[mf->v2], DR_OPTIM, 0.0, NULL); 
415                 }
416         }
417
418         MEM_freeN(vert_tbl);
419         
420         return hme;
421 }
422
423 static HyperMesh *hypermesh_from_editmesh(EditMesh *em, int subdivLevels) {
424         HyperMesh *hme= hypermesh_new();
425         EditVert *ev, *prevev;
426         EditEdge *ee;
427         EditFace *ef;
428         float creasefac= (float)subdivLevels;
429         int flag;
430
431         /* hide flags rule: 
432                 - face hidden, not do. is easy
433                 - edge hidden, always means face is hidden too
434                 - vertex hidden, always means edge is hidden too
435         */
436         
437                 /* we only add vertices with edges, 'f1' is a free flag */
438                 /* added: check for hide flag in vertices */
439         for (ev= em->verts.first; ev; ev= ev->next) {
440                 ev->f1= 1;      
441                 ev->prev= NULL;
442         }
443
444                 /* hack, tuck the new hypervert pointer into
445                  * the ev->prev link so we can find it easy, 
446                  * then restore real prev links later.
447                  */
448         for (ee= em->edges.first; ee; ee= ee->next) {
449
450                 if(ee->v1->f1) {
451                         ee->v1->prev= (EditVert*) hypermesh_add_vert(hme, ee->v1->co, ee->v1);
452                         ee->v1->f1= 0;
453                 }
454                 if(ee->v2->f1) {
455                         ee->v2->prev= (EditVert*) hypermesh_add_vert(hme, ee->v2->co, ee->v2);
456                         ee->v2->f1= 0;
457                 }
458                 if((ee->h & 1)==0) {
459
460                         flag= DR_OPTIM;
461                         if(ee->seam) flag |= HE_SEAM;
462                         
463                         hypermesh_add_edge(hme, (HyperVert*) ee->v1->prev, (HyperVert*) ee->v2->prev, flag, 
464                                 creasefac*ee->crease, ee);
465                 }
466         }
467         for (ef= em->faces.first; ef; ef= ef->next) {
468                 if(ef->h==0) {
469                         int nverts= ef->v4?4:3;
470                         HyperVert *verts[4];
471                         HyperFace *f;
472                         
473                         verts[0]= (HyperVert*) ef->v1->prev;
474                         verts[1]= (HyperVert*) ef->v2->prev;
475                         verts[2]= (HyperVert*) ef->v3->prev;
476                         if (nverts>3)
477                                 verts[3]= (HyperVert*) ef->v4->prev;
478         
479                         f= hypermesh_add_face(hme, verts, nverts, DR_OPTIM);
480                         f->orig.ef= ef;
481                 }
482         }
483
484                 /* see hack above, restore the prev links */
485         for (prevev= NULL, ev= em->verts.first; ev; prevev= ev, ev= ev->next)
486                 ev->prev= prevev;
487         
488         return hme;
489 }
490
491 static void VColAvgT(unsigned char *t, unsigned char *a, unsigned char *b) {
492         t[0]= (a[0]+b[0])>>1;
493         t[1]= (a[1]+b[1])>>1;
494         t[2]= (a[2]+b[2])>>1;
495         t[3]= (a[3]+b[3])>>1;
496 }
497
498 static void hypermesh_calc_sharp_edge(HyperEdge *e, float co[3])
499 {
500         Vec3AvgT(co, e->v[0]->co, e->v[1]->co);
501 }
502
503 static void hypermesh_calc_smooth_edge(HyperEdge *e, float co[3])
504 {
505         int count;
506         LinkNode *link;
507         HyperFace *f;
508         
509         Vec3AddT(co, e->v[0]->co, e->v[1]->co);
510         for (count=2, link= e->faces; link; count++, link= link->next) {
511                 f= (HyperFace *) link->link;
512                 Vec3Add(co, f->mid->co);
513         }
514         Vec3MulN(co, (float)(1.0/count));
515 }
516
517 static void hypermesh_lininterp_vert(float co[3], float co1[3], float co2[3], float w)
518 {
519         float codiff[3];
520         
521         codiff[0] = co2[0] - co1[0];
522         codiff[1] = co2[1] - co1[1];
523         codiff[2] = co2[2] - co1[2];
524         
525         Vec3MulN(codiff, w);
526         
527         Vec3AddT(co, co1, codiff);
528 }
529
530 static void hypermesh_calc_interp_edge(HyperEdge *e, float co[3])
531 {
532         float co1[3];
533         float co2[3];
534         
535         hypermesh_calc_smooth_edge(e, co1);
536         hypermesh_calc_sharp_edge(e, co2);
537         
538         hypermesh_lininterp_vert(co, co1, co2, e->sharp);
539 }
540
541
542 static void hypermesh_calc_smooth_vert(HyperVert *v, float co[3])
543 {
544         float q[3], r[3], s[3];
545         LinkNode *link;
546         HyperFace *f;
547         HyperEdge *e;
548         int count = 0;
549         
550         if (hypervert_is_boundary(v)) {
551                 Vec3CpyI(r, 0.0, 0.0, 0.0);
552         
553                 for (count= 0, link= v->edges; link; link= link->next) {
554                         if (hyperedge_is_boundary(link->link)) {
555                                 HyperVert *ov= hyperedge_other_vert(link->link, v);
556                 
557                                 Vec3Add(r, ov->co);
558                                 count++;
559                         }
560                 }
561         
562                 /* I believe CC give the factors as
563                         3/2k and 1/4k, but that doesn't make
564                         sense (to me) as they don't sum to unity... 
565                         It's rarely important.
566                 */
567                 Vec3MulNT(s, v->co, 0.75f);
568                 Vec3Add(s, Vec3MulN(r, (float)(1.0/(4.0*count))));
569         } else {
570                 Vec3Cpy(q, Vec3Cpy(r, Vec3CpyI(s, 0.0f, 0.0f, 0.0f)));
571         
572                 for (count=0, link= v->faces; link; count++, link= link->next) {
573                         f= (HyperFace *) link->link;
574                         Vec3Add(q, f->mid->co);
575                 }
576                 Vec3MulN(q, (float)(1.0/count));
577         
578                 for (count=0, link= v->edges; link; count++, link= link->next) {
579                         e= (HyperEdge *) link->link;
580                         Vec3Add(r, hyperedge_other_vert(e, v)->co);
581                 }
582                 Vec3MulN(r, (float)(1.0/count));
583         
584                 Vec3MulNT(s, v->co, (float)(count-2));
585         
586                 Vec3Add(s, q);
587                 Vec3Add(s, r);
588                 Vec3MulN(s, (float)(1.0/count));
589         }
590         
591         Vec3Cpy(co, s);
592         
593 }
594
595 static void hypermesh_calc_sharp_vert(HyperVert *v, float co[3])
596 {
597         co[0] = v->co[0];
598         co[1] = v->co[1];
599         co[2] = v->co[2];
600 }
601
602 static void hypermesh_calc_creased_vert(HyperVert *v, float co[3], float w)
603 {
604         LinkNode *l;
605         float epSum[3] = {0,0,0};
606         int count = 0;
607         
608         /* use the crease rule */
609         for (l= v->edges; l; l= l->next) {
610                 HyperEdge *he = l->link;
611                 if (he->sharp != 0.0) {
612                         HyperVert *oV = hyperedge_other_vert(he, v);
613                         epSum[0] += oV->co[0];
614                         epSum[1] += oV->co[1];
615                         epSum[2] += oV->co[2];
616                         count++;
617                 }
618         }
619
620         epSum[0] /= count;
621         epSum[1] /= count;
622         epSum[2] /= count;
623
624         if (count!=2) {
625                 epSum[0] = epSum[0] + (v->co[0] - epSum[0])*w;
626                 epSum[1] = epSum[1] + (v->co[1] - epSum[1])*w;
627                 epSum[2] = epSum[2] + (v->co[2] - epSum[2])*w;
628         }
629
630         co[0] = (3.0 * v->co[0] + epSum[0]) / 4.0;
631         co[1] = (3.0 * v->co[1] + epSum[1]) / 4.0;
632         co[2] = (3.0 * v->co[2] + epSum[2]) / 4.0;
633 }
634
635 static void hypermesh_calc_interp_vert(HyperVert *v, float co[3], float w)
636 {
637         float co1[3];
638         float co2[3];
639         
640         hypermesh_calc_smooth_vert(v, co1);
641         hypermesh_calc_creased_vert(v, co2, w);
642         
643         hypermesh_lininterp_vert(co, co1, co2, w);
644 }
645
646 static void hypermesh_subdivide(HyperMesh *me, HyperMesh *nme) {
647         HyperVert *v;
648         HyperEdge *e;
649         HyperFace *f;
650         LinkNode *link;
651         float co[3];
652         int j, k;
653
654         for (f= me->faces; f; f= f->next) {
655                 Vec3CpyI(co, 0.0, 0.0, 0.0);
656                 for (j=0; j<f->nverts; j++)
657                         Vec3Add(co, f->verts[j]->co);
658                 Vec3MulN(co, (float)(1.0/f->nverts));
659
660                 f->mid= hypermesh_add_vert(nme, co, NULL);
661         }
662                 
663         for (e= me->edges; e; e= e->next) {
664                 if (hyperedge_is_boundary(e) || (e->sharp > 1.0)) {
665          hypermesh_calc_sharp_edge(e, co);
666       }
667       else {
668          hypermesh_calc_interp_edge(e, co);
669       }
670                 
671                 e->ep= hypermesh_add_vert(nme, co, NULL);
672         }
673
674         for (v= me->verts; v; v= v->next) {
675                 float s[3];
676                 int sharpcnt = 0;
677                 float avgw = 0.0;
678
679                 /* count the sharp edges */
680                 for (link= v->edges; link; link= link->next) {
681                         if (((HyperEdge *)link->link)->sharp != 0.0) {
682                                 sharpcnt++;
683                                 avgw += ((HyperEdge *)link->link)->sharp;
684                         }
685                 }
686                 
687                 avgw /= (float)sharpcnt;
688                 if (avgw > 1.0)
689                         avgw = 1.0;
690                 
691                 switch (sharpcnt) {
692                 case 0:
693                 case 1:
694                         hypermesh_calc_smooth_vert(v, s);
695                         break;
696                 case 2:
697                 default:
698                         hypermesh_calc_interp_vert(v, s, avgw);
699                         break;
700                 }
701                 
702                 v->nmv= hypermesh_add_vert(nme, s, v->orig);
703         }
704
705         for (e= me->edges; e; e= e->next) {
706                 hypermesh_add_edge(nme, e->v[0]->nmv, e->ep, e->flag, e->sharp>1.0?e->sharp-1.0:0.0, e->ee);
707                 hypermesh_add_edge(nme, e->v[1]->nmv, e->ep, e->flag, e->sharp>1.0?e->sharp-1.0:0.0, e->ee);
708         }
709
710         for (f= me->faces; f; f= f->next) {
711                 int last= f->nverts-1;
712                 unsigned char vcol_mid[4];
713                 unsigned char vcol_edge[4][4];
714                 float uvco_mid[2];
715                 float uvco_edge[4][4];
716                 
717                 if (me->hasvcol) {
718                         int t[4]= {0, 0, 0, 0};
719                         for (j=0; j<f->nverts; j++) {
720                                 t[0]+= f->vcol[j][0];
721                                 t[1]+= f->vcol[j][1];
722                                 t[2]+= f->vcol[j][2];
723                                 t[3]+= f->vcol[j][3];
724                         }
725                         vcol_mid[0]= t[0]/f->nverts;
726                         vcol_mid[1]= t[1]/f->nverts;
727                         vcol_mid[2]= t[2]/f->nverts;
728                         vcol_mid[3]= t[3]/f->nverts;
729                         
730                         for (j=0; j<f->nverts; last= j, j++)
731                                 VColAvgT(vcol_edge[j], f->vcol[last], f->vcol[j]);
732                         last= f->nverts-1;
733                 }
734                 if (me->hasuvco) {
735                         Vec2CpyI(uvco_mid, 0.0, 0.0);
736                         for (j=0; j<f->nverts; j++)
737                                 Vec2Add(uvco_mid, f->uvco[j]);
738                         Vec2MulN(uvco_mid, (float)(1.0/f->nverts));
739
740                         for (j=0; j<f->nverts; last= j, j++)
741                                 Vec2AvgT(uvco_edge[j], f->uvco[last], f->uvco[j]);
742                         last= f->nverts-1;
743                 }
744                 
745                 for (j=0; j<f->nverts; last=j, j++) {
746                         HyperVert *nv[4];
747                         HyperFace *nf;
748                         
749                         nv[0]= f->verts[last]->nmv;
750                         nv[1]= f->edges[j]->ep;
751                         nv[2]= f->mid;
752                         nv[3]= f->edges[last]->ep;
753                         
754                         nf= hypermesh_add_face(nme, nv, 4, 0);
755                         nf->orig= f->orig;
756                         
757                         if (me->hasvcol) {
758                                 nf->vcol= BLI_memarena_alloc(nme->arena, sizeof(*nf->vcol)*4);
759                                 
760                                 for (k=0; k<4; k++) {
761                                         nf->vcol[0][k]= f->vcol[last][k];
762                                         nf->vcol[1][k]= vcol_edge[j][k];
763                                         nf->vcol[2][k]= vcol_mid[k];
764                                         nf->vcol[3][k]= vcol_edge[last][k];
765                                 }
766                         }
767                         if (me->hasuvco) {
768                                 nf->uvco= BLI_memarena_alloc(nme->arena, sizeof(*nf->uvco)*4);
769                                 
770                                 Vec2Cpy(nf->uvco[0], f->uvco[last]);
771                                 Vec2Cpy(nf->uvco[1], uvco_edge[j]);
772                                 Vec2Cpy(nf->uvco[2], uvco_mid);
773                                 Vec2Cpy(nf->uvco[3], uvco_edge[last]);
774
775                                 if(j==0 && (f->unwrap & ((f->nverts==4)?TF_PIN4:TF_PIN3)))
776                                         nf->unwrap= TF_PIN1;
777                                 else if(j==1 && f->unwrap & TF_PIN1) nf->unwrap= TF_PIN1;
778                                 else if(j==2 && f->unwrap & TF_PIN2) nf->unwrap= TF_PIN1;
779                                 else if(j==3 && f->unwrap & TF_PIN3) nf->unwrap= TF_PIN1;
780                                 else nf->unwrap= 0;
781                         }
782                 }
783         }
784 }
785
786 /* Simple subdivision surface for radio and displacement */
787 static void hypermesh_simple_subdivide(HyperMesh *me, HyperMesh *nme) {
788         HyperVert *v;
789         HyperEdge *e;
790         HyperFace *f;
791         float co[3];
792         int j, k;
793
794         for (f= me->faces; f; f= f->next) { /* Adds vert at center of each existing face */
795                 Vec3CpyI(co, 0.0, 0.0, 0.0);
796                 for (j=0; j<f->nverts; j++)     Vec3Add(co, f->verts[j]->co);
797                 Vec3MulN(co, (float)(1.0/f->nverts));
798
799                 f->mid= hypermesh_add_vert(nme, co, NULL);
800         }
801                 
802         for (e= me->edges; e; e= e->next) {  /* Add vert in middle of each edge */      
803                 Vec3AvgT(co, e->v[0]->co, e->v[1]->co);
804                 e->ep= hypermesh_add_vert(nme, co, NULL);
805         }
806
807         for (v= me->verts; v; v= v->next) {
808                 v->nmv= hypermesh_add_vert(nme, v->co, v->orig);
809         }
810
811         for (e= me->edges; e; e= e->next) { /* Add original edges */
812                 hypermesh_add_edge(nme, e->v[0]->nmv, e->ep, e->flag, 0.0, e->ee);
813                 hypermesh_add_edge(nme, e->v[1]->nmv, e->ep, e->flag, 0.0, e->ee);
814         }
815
816         for (f= me->faces; f; f= f->next) {
817                 int last= f->nverts-1;
818                 unsigned char vcol_mid[4];
819                 unsigned char vcol_edge[4][4];
820                 float uvco_mid[2];
821                 float uvco_edge[4][4];
822                 
823                 if (me->hasvcol) {
824                         int t[4]= {0, 0, 0, 0};
825                         for (j=0; j<f->nverts; j++) {
826                                 t[0]+= f->vcol[j][0];
827                                 t[1]+= f->vcol[j][1];
828                                 t[2]+= f->vcol[j][2];
829                                 t[3]+= f->vcol[j][3];
830                         }
831                         vcol_mid[0]= t[0]/f->nverts;
832                         vcol_mid[1]= t[1]/f->nverts;
833                         vcol_mid[2]= t[2]/f->nverts;
834                         vcol_mid[3]= t[3]/f->nverts;
835                         
836                         for (j=0; j<f->nverts; last= j, j++)
837                                 VColAvgT(vcol_edge[j], f->vcol[last], f->vcol[j]);
838                         last= f->nverts-1;
839                 }
840                 if (me->hasuvco) {
841                         Vec2CpyI(uvco_mid, 0.0, 0.0);
842                         for (j=0; j<f->nverts; j++)
843                                 Vec2Add(uvco_mid, f->uvco[j]);
844                         Vec2MulN(uvco_mid, (float)(1.0/f->nverts));
845
846                         for (j=0; j<f->nverts; last= j, j++)
847                                 Vec2AvgT(uvco_edge[j], f->uvco[last], f->uvco[j]);
848                         last= f->nverts-1;
849                 }
850                 
851                 for (j=0; j<f->nverts; last=j, j++) {
852                         HyperVert *nv[4];
853                         HyperFace *nf;
854                         
855                         nv[0]= f->verts[last]->nmv;
856                         nv[1]= f->edges[j]->ep;
857                         nv[2]= f->mid;
858                         nv[3]= f->edges[last]->ep;
859                         
860                         nf= hypermesh_add_face(nme, nv, 4, 0);
861                         nf->orig= f->orig;
862                         
863                         if (me->hasvcol) {
864                                 nf->vcol= BLI_memarena_alloc(nme->arena, sizeof(*nf->vcol)*4);
865                                 
866                                 for (k=0; k<4; k++) {
867                                         nf->vcol[0][k]= f->vcol[last][k];
868                                         nf->vcol[1][k]= vcol_edge[j][k];
869                                         nf->vcol[2][k]= vcol_mid[k];
870                                         nf->vcol[3][k]= vcol_edge[last][k];
871                                 }
872                         }
873                         if (me->hasuvco) {
874                                 nf->uvco= BLI_memarena_alloc(nme->arena, sizeof(*nf->uvco)*4);
875                                 
876                                 Vec2Cpy(nf->uvco[0], f->uvco[last]);
877                                 Vec2Cpy(nf->uvco[1], uvco_edge[j]);
878                                 Vec2Cpy(nf->uvco[2], uvco_mid);
879                                 Vec2Cpy(nf->uvco[3], uvco_edge[last]);
880                         }
881                 }
882         }
883 }
884
885
886 static void hypermesh_free(HyperMesh *me) {
887         BLI_memarena_free(me->arena);
888                         
889         MEM_freeN(me);
890 }
891
892 /*****/
893
894 static int hypermesh_get_nverts(HyperMesh *hme) {
895         HyperVert *v;
896         int count= 0;
897         
898         for (v= hme->verts; v; v= v->next)
899                 count++;
900         
901         return count;
902 }
903
904 static int hypermesh_get_nfaces(HyperMesh *hme) {
905         HyperFace *f;
906         int count= 0;
907         
908         for (f= hme->faces; f; f= f->next)
909                 count++;
910         
911         return count;
912 }
913
914 static int hypermesh_get_nedges(HyperMesh *hme) {
915         HyperEdge *e;
916         int count= 0;
917         
918         for (e= hme->edges; e; e= e->next)
919                         count++;
920         
921         return count;
922 }
923
924 /* flag is me->flag, for 'optim' */
925 static DispListMesh *hypermesh_to_displistmesh(HyperMesh *hme, short flag) {
926         int nverts= hypermesh_get_nverts(hme);
927         int nedges= hypermesh_get_nedges(hme);
928         int nfaces= hypermesh_get_nfaces(hme);
929         DispListMesh *dlm= MEM_callocN(sizeof(*dlm), "dlmesh");
930         HyperFace *f;
931         HyperVert *v;
932         HyperEdge *e;
933         TFace *tfaces;
934         MEdge *med;
935         MFace *mfaces, *mf;
936         int i, j;
937
938                 /* hme->orig_me==NULL if we are working on an editmesh */
939         if (hme->orig_me) {
940                 tfaces= hme->orig_me->tface;
941                 mfaces= hme->orig_me->mface;
942         } else {
943                 tfaces= NULL;
944                 mfaces= NULL;
945         }
946
947         /* removed: handles for editmode. it now stores pointer to subsurfed vertex in editvert */
948         dlm->totvert= nverts;
949         dlm->totface= nfaces;
950         dlm->totedge= nedges;
951         
952         /* calloc for clear flag and nor in mvert */
953         dlm->mvert= MEM_callocN(dlm->totvert*sizeof(*dlm->mvert), "dlm->mvert");
954         dlm->medge= MEM_callocN(dlm->totedge*sizeof(*dlm->medge), "dlm->medge");
955         dlm->mface= MEM_mallocN(dlm->totface*sizeof(*dlm->mface), "dlm->mface");
956         /* these two blocks for live update of selection in editmode */
957         if (hme->orig_me==NULL) {
958                 dlm->editedge= MEM_callocN(dlm->totedge*sizeof(EditEdge *), "dlm->editface");
959                 dlm->editface= MEM_mallocN(dlm->totface*sizeof(EditFace *), "dlm->editedge");
960         }
961         if (hme->orig_me) {
962                 dlm->flag= hme->orig_me->flag;
963         } else {
964                 dlm->flag= flag;
965         }
966         
967         if (hme->hasuvco)
968                 dlm->tface= MEM_callocN(dlm->totface*sizeof(*dlm->tface), "dlm->tface");
969         else if (hme->hasvcol)
970                 dlm->mcol= MEM_mallocN(dlm->totface*4*sizeof(*dlm->mcol), "dlm->mcol");
971                                 
972         for (i=0, v= hme->verts; i<nverts; i++, v= v->next) {
973                 MVert *mv= &dlm->mvert[i];
974                 Vec3Cpy(mv->co, v->co);
975                 v->nmv= (void*) i;
976         }
977         
978         /* we use by default edges for displistmesh now */
979         med= dlm->medge;
980         for (i=0, e= hme->edges; e; e= e->next, med++, i++) {
981                 med->v1= (int) e->v[0]->nmv;
982                 med->v2= (int) e->v[1]->nmv;
983                 
984                 if (hme->orig_me==NULL) dlm->editedge[i]= e->ee;
985
986                 if(e->flag & DR_OPTIM) med->flag |= ME_EDGEDRAW;
987                 if(e->flag & HE_SEAM) med->flag |= ME_SEAM;
988         }
989         
990         /* and we add pointer to subsurfed vertex in editvert */
991         if(hme->orig_me==NULL) {
992                 MVert *mv= dlm->mvert;
993                 for (v= hme->verts; v; v= v->next, mv++) {
994                         if(v->orig) v->orig->ssco= mv->co;
995                 }
996         }
997
998         /* faces */
999         mf= dlm->mface;
1000         for (i=0, f= hme->faces; f; i++, f= f->next) {
1001                         /* There is a complicated dependancy here:
1002                          * After a subdivision the points that were shifted will always be
1003                          * first in the hme->verts list (because they are added last, but to
1004                          * the head). This means that the HVert with index 0 will always be
1005                          * a shifted vertice, and the shifted vertices (corners) are always
1006                          * HFace->verts[0]. Therefore it is guaranteed that if any vertice
1007                          * index is 0, it will always be in mf->v1, so we do not have to worry
1008                          * about tweaking the indices.
1009                          */
1010                 mf->v1= (int) f->verts[0]->nmv;
1011                 mf->v2= (int) f->verts[1]->nmv;
1012                 mf->v3= (int) f->verts[2]->nmv;
1013                 mf->v4= (int) f->verts[3]->nmv;
1014
1015                 if (hme->orig_me) {                     
1016                         MFace *origmf= &mfaces[f->orig.ind];
1017
1018                         mf->mat_nr= origmf->mat_nr;
1019                         mf->flag= origmf->flag;
1020                         mf->puno= 0;
1021                 } else {
1022                         EditFace *origef= f->orig.ef;
1023                         
1024                         mf->mat_nr= origef->mat_nr;
1025                         mf->flag= origef->flag;
1026                         mf->puno= 0;
1027                         
1028                         // for subsurf draw in editmode
1029                         dlm->editface[i]= origef;
1030                 }
1031                 
1032                 /* although not used by 3d display, still needed for wire-render */
1033                 mf->edcode= 0;
1034                 if (f->edges[0]->flag) mf->edcode|= ME_V4V1;
1035                 if (f->edges[1]->flag) mf->edcode|= ME_V1V2;
1036                 if (f->edges[2]->flag) mf->edcode|= ME_V2V3;
1037                 if (f->edges[3]->flag) mf->edcode|= ME_V3V4;
1038
1039                 if (hme->hasuvco) {
1040                         TFace *origtf, *tf= &dlm->tface[i];
1041                         
1042                         //if (hme->orig_me)
1043                                 origtf= &tfaces[f->orig.ind];
1044                         //else          ton: removed, hme->hasuvco doesn't happen in editmode (yet?)
1045                         //      origtf= f->orig.ef->tface;
1046                         
1047                         for (j=0; j<4; j++) {
1048                                 Vec2Cpy(tf->uv[j], f->uvco[j]);
1049                                 tf->col[j]= *((unsigned int*) f->vcol[j]);
1050                         }
1051                         
1052                         tf->tpage= origtf->tpage;
1053                         tf->flag= origtf->flag;
1054                         tf->transp= origtf->transp;
1055                         tf->mode= origtf->mode;
1056                         tf->tile= origtf->tile;
1057                         tf->unwrap= f->unwrap;
1058                 } else if (hme->hasvcol) {
1059                         MCol *mcolbase= &dlm->mcol[i*4];
1060                         
1061                         for (j=0; j<4; j++)
1062                                 *((unsigned int*) &mcolbase[j])= *((unsigned int*) f->vcol[j]);
1063                 }
1064                 
1065                 mf++;
1066         }       
1067         
1068         displistmesh_calc_normals(dlm);
1069
1070         return dlm;
1071 }
1072
1073 /* flag is me->flag, and 'optim' */
1074 static DispListMesh *subsurf_subdivide_to_displistmesh(HyperMesh *hme, short subdiv,
1075                                                                                                 short flag, short type) {
1076         DispListMesh *dlm;
1077         int i;
1078
1079         for (i= 0; i<subdiv; i++) {
1080                 HyperMesh *tmp= hypermesh_new();
1081                 tmp->hasvcol= hme->hasvcol;
1082                 tmp->hasuvco= hme->hasuvco;
1083                 tmp->orig_me= hme->orig_me;
1084                 
1085                 if (type == ME_SIMPLE_SUBSURF) hypermesh_simple_subdivide(hme, tmp);
1086                 else hypermesh_subdivide(hme, tmp);      /* default to CC subdiv. */
1087                 
1088                 hypermesh_free(hme);
1089                 hme= tmp;
1090         }
1091
1092         dlm= hypermesh_to_displistmesh(hme, flag);
1093         hypermesh_free(hme);
1094         
1095         return dlm;
1096 }
1097
1098 static DispListMesh *subsurf_make_dispListMesh_from_editmesh(EditMesh *em, int subdivLevels, int flags, short type) {
1099         if (subdivLevels<1) {
1100                 return displistmesh_from_editmesh(em);
1101 #ifdef USE_CCGSUBSURFLIB
1102         } else if (type==ME_CCG_SUBSURF) {
1103                 return subsurf_ccg_make_dispListMesh_from_editmesh(em, subdivLevels, flags);
1104 #endif
1105         } else {
1106                 HyperMesh *hme= hypermesh_from_editmesh(em, subdivLevels);
1107         
1108                 return subsurf_subdivide_to_displistmesh(hme, subdivLevels, flags, type);
1109         }
1110 }
1111
1112 DerivedMesh *subsurf_make_derived_from_editmesh(EditMesh *em, int subdivLevels, int flags, short type) {
1113         return derivedmesh_from_displistmesh(em, subsurf_make_dispListMesh_from_editmesh(em, subdivLevels, flags, type));
1114 }
1115
1116 static DispListMesh *subsurf_make_dispListMesh_from_mesh(Mesh *me, int subdivLevels, int flags) {
1117         if (subdivLevels<1) {
1118                 return displistmesh_from_mesh(me, NULL);
1119 #ifdef USE_CCGSUBSURFLIB
1120         } else if (me->subsurftype==ME_CCG_SUBSURF) {
1121                 return subsurf_ccg_make_dispListMesh_from_mesh(me, subdivLevels, flags);
1122 #endif
1123         } else {
1124                 HyperMesh *hme= hypermesh_from_mesh(me, subdivLevels);
1125
1126                 return subsurf_subdivide_to_displistmesh(hme, subdivLevels, flags, me->subsurftype);
1127         }
1128 }
1129
1130 DerivedMesh *subsurf_make_derived_from_mesh(Mesh *me, int subdivLevels, int flags) {
1131         return derivedmesh_from_displistmesh(NULL, subsurf_make_dispListMesh_from_mesh(me, subdivLevels, flags));
1132 }
1133
1134         // editarmature.c
1135 void subsurf_calculate_limit_positions(Mesh *me, float (*positions_r)[3]) 
1136 {
1137         /* Finds the subsurf limit positions for the verts in a mesh 
1138          * and puts them in an array of floats. Please note that the 
1139          * calculated vert positions is incorrect for the verts 
1140          * on the boundary of the mesh.
1141          */
1142         HyperMesh *hme= hypermesh_from_mesh(me, 1);     // 1=subdivlevel
1143         HyperMesh *nme= hypermesh_new();
1144         float edge_sum[3], face_sum[3];
1145         HyperVert *hv;
1146         LinkNode *l;
1147         int i;
1148
1149         hypermesh_subdivide(hme, nme);
1150
1151         for (i= me->totvert-1,hv=hme->verts; i>=0; i--,hv=hv->next) {
1152                 int N= 0;
1153                 
1154                 edge_sum[0]= edge_sum[1]= edge_sum[2]= 0.0;
1155                 face_sum[0]= face_sum[1]= face_sum[2]= 0.0;
1156
1157                 for (N=0,l=hv->edges; l; N++,l= l->next) {
1158                         Vec3Add(edge_sum, ((HyperEdge*) l->link)->ep->co);
1159                 }
1160                 for (l=hv->faces; l; l= l->next) {
1161                         Vec3Add(face_sum, ((HyperFace*) l->link)->mid->co);
1162                 }
1163
1164                 positions_r[i][0] = 
1165                         (hv->nmv->co[0]*N*N + edge_sum[0]*4 + face_sum[0])/(N*(N+5));
1166                 positions_r[i][1] = 
1167                         (hv->nmv->co[1]*N*N + edge_sum[1]*4 + face_sum[1])/(N*(N+5));
1168                 positions_r[i][2] = 
1169                         (hv->nmv->co[2]*N*N + edge_sum[2]*4 + face_sum[2])/(N*(N+5));
1170         }
1171
1172         hypermesh_free(nme);
1173         hypermesh_free(hme);
1174 }
1175