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