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