- added make_orco_curf, even does keys!
[blender.git] / source / blender / blenkernel / intern / displist.c
1
2 /*  displist.c
3  * 
4  * 
5  * $Id$
6  *
7  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version. The Blender
13  * Foundation also sells licenses for use in proprietary software under
14  * the Blender License.  See http://www.blender.org/BL/ for information
15  * about this.
16  *
17  * This program is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
20  * GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License
23  * along with this program; if not, write to the Free Software Foundation,
24  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
25  *
26  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
27  * All rights reserved.
28  *
29  * The Original Code is: all of this file.
30  *
31  * Contributor(s): none yet.
32  *
33  * ***** END GPL/BL DUAL LICENSE BLOCK *****
34  */
35
36 #ifdef HAVE_CONFIG_H
37 #include <config.h>
38 #endif
39
40 #include <math.h>
41 #include <stdio.h>
42 #include <string.h>
43
44 #include "MEM_guardedalloc.h"
45
46 #include "IMB_imbuf_types.h"
47
48 #include "DNA_texture_types.h"
49 #include "DNA_meta_types.h"
50 #include "DNA_curve_types.h"
51 #include "DNA_effect_types.h"
52 #include "DNA_listBase.h"
53 #include "DNA_lamp_types.h"
54 #include "DNA_object_types.h"
55 #include "DNA_object_force.h"
56 #include "DNA_mesh_types.h"
57 #include "DNA_meshdata_types.h"
58 #include "DNA_scene_types.h"
59 #include "DNA_image_types.h"
60 #include "DNA_material_types.h"
61 #include "DNA_view3d_types.h"
62 #include "DNA_lattice_types.h"
63 #include "DNA_key_types.h"
64
65 #include "BLI_blenlib.h"
66 #include "BLI_arithb.h"
67 #include "BLI_editVert.h"
68
69 #include "BKE_bad_level_calls.h"
70 #include "BKE_utildefines.h"
71 #include "BKE_global.h"
72 #include "BKE_displist.h"
73 #include "BKE_deform.h"
74 #include "BKE_DerivedMesh.h"
75 #include "BKE_object.h"
76 #include "BKE_world.h"
77 #include "BKE_mesh.h"
78 #include "BKE_effect.h"
79 #include "BKE_mball.h"
80 #include "BKE_material.h"
81 #include "BKE_curve.h"
82 #include "BKE_key.h"
83 #include "BKE_anim.h"
84 #include "BKE_screen.h"
85 #include "BKE_texture.h"
86 #include "BKE_library.h"
87 #include "BKE_font.h"
88 #include "BKE_lattice.h"
89 #include "BKE_scene.h"
90 #include "BKE_subsurf.h"
91
92 #include "nla.h" /* For __NLA: Please do not remove yet */
93 #include "render.h"
94
95
96 /***/
97
98 typedef struct _FastLamp FastLamp;
99 struct _FastLamp {
100         FastLamp *next;
101         
102         short type, mode, lay, rt;
103         float co[3];
104         float vec[3];
105         float dist, distkw, att1, att2, spotsi, spotbl, r, g, b;
106 };
107
108 /***/
109
110 static void boundbox_displist(Object *ob);
111
112 static FastLamp *fastlamplist= NULL;
113 static float fviewmat[4][4];
114
115 void displistmesh_free(DispListMesh *dlm) 
116 {
117         // also check on mvert and mface, can be NULL after decimator (ton)
118         if (!dlm->dontFreeVerts && dlm->mvert) MEM_freeN(dlm->mvert);
119         if (!dlm->dontFreeNors && dlm->nors) MEM_freeN(dlm->nors);
120         if (!dlm->dontFreeOther) {
121                 if (dlm->medge) MEM_freeN(dlm->medge);
122                 if (dlm->mface) MEM_freeN(dlm->mface);
123                 if (dlm->mcol) MEM_freeN(dlm->mcol);
124                 if (dlm->tface) MEM_freeN(dlm->tface);
125         }
126         MEM_freeN(dlm);
127 }
128
129 DispListMesh *displistmesh_copy(DispListMesh *odlm) 
130 {
131         DispListMesh *ndlm= MEM_dupallocN(odlm);
132         ndlm->mvert= MEM_dupallocN(odlm->mvert);
133         if (odlm->medge) ndlm->medge= MEM_dupallocN(odlm->medge);
134         ndlm->mface= MEM_dupallocN(odlm->mface);
135         if (odlm->nors) ndlm->nors = MEM_dupallocN(odlm->nors);
136         if (odlm->mcol) ndlm->mcol= MEM_dupallocN(odlm->mcol);
137         if (odlm->tface) ndlm->tface= MEM_dupallocN(odlm->tface);
138         
139         return ndlm;
140 }
141
142 DispListMesh *displistmesh_copyShared(DispListMesh *odlm) 
143 {
144         DispListMesh *ndlm= MEM_dupallocN(odlm);
145         ndlm->dontFreeNors = ndlm->dontFreeOther = ndlm->dontFreeVerts = 1;
146         
147         return ndlm;
148 }
149
150 void displistmesh_to_mesh(DispListMesh *dlm, Mesh *me) 
151 {
152                 /* We assume, rather courageously, that any
153                  * shared data came from the mesh itself and so
154                  * we can ignore the dlm->dontFreeOther flag.
155                  */
156
157         if (me->mvert && dlm->mvert!=me->mvert) MEM_freeN(me->mvert);
158         if (me->mface && dlm->mface!=me->mface) MEM_freeN(me->mface);
159         if (me->tface && dlm->tface!=me->tface) MEM_freeN(me->tface);
160         if (me->mcol && dlm->mcol!=me->mcol) MEM_freeN(me->mcol);
161         if (me->medge && dlm->medge!=me->medge) MEM_freeN(me->medge);
162
163         me->tface = NULL;
164         me->mcol = NULL;
165         me->medge = NULL;
166
167         if (dlm->totvert!=me->totvert) {
168                 if (me->msticky) MEM_freeN(me->msticky);
169                 me->msticky = NULL;
170
171                 if (me->dvert) free_dverts(me->dvert, me->totvert);
172                 me->dvert = NULL;
173
174                 if(me->key) me->key->id.us--;
175                 me->key = NULL;
176         }
177
178         me->totface= dlm->totface;
179         me->totvert= dlm->totvert;
180         me->totedge= 0;
181
182         me->mvert= dlm->mvert;
183         me->mface= dlm->mface;
184         if (dlm->tface)
185                 me->tface= dlm->tface;
186         if (dlm->mcol)
187                 me->mcol= dlm->mcol;
188
189         if(dlm->medge) {
190                 me->totedge= dlm->totedge;
191                 me->medge= dlm->medge;
192         }
193
194         if (dlm->nors && !dlm->dontFreeNors) MEM_freeN(dlm->nors);
195
196         MEM_freeN(dlm);
197 }
198
199 void free_disp_elem(DispList *dl)
200 {
201         if(dl) {
202                 if(dl->verts) MEM_freeN(dl->verts);
203                 if(dl->nors) MEM_freeN(dl->nors);
204                 if(dl->index) MEM_freeN(dl->index);
205                 if(dl->col1) MEM_freeN(dl->col1);
206                 if(dl->col2) MEM_freeN(dl->col2);
207                 if(dl->bevelSplitFlag) MEM_freeN(dl->bevelSplitFlag);
208                 MEM_freeN(dl);
209         }
210 }
211
212 void freedisplist(ListBase *lb)
213 {
214         DispList *dl;
215
216         dl= lb->first;
217         while(dl) {
218                 BLI_remlink(lb, dl);
219                 free_disp_elem(dl);
220                 dl= lb->first;
221         }
222 }
223
224 DispList *find_displist_create(ListBase *lb, int type)
225 {
226         DispList *dl;
227         
228         dl= lb->first;
229         while(dl) {
230                 if(dl->type==type) return dl;
231                 dl= dl->next;
232         }
233
234         dl= MEM_callocN(sizeof(DispList), "find_disp");
235         dl->type= type;
236         BLI_addtail(lb, dl);
237
238         return dl;
239 }
240
241 DispList *find_displist(ListBase *lb, int type)
242 {
243         DispList *dl;
244         
245         dl= lb->first;
246         while(dl) {
247                 if(dl->type==type) return dl;
248                 dl= dl->next;
249         }
250
251         return 0;
252 }
253
254 int displist_has_faces(ListBase *lb)
255 {
256         DispList *dl;
257         
258         dl= lb->first;
259         while(dl) {
260                 if ELEM4(dl->type, DL_INDEX3, DL_INDEX4, DL_SURF, DL_POLY)
261                         return 1;
262                 dl= dl->next;
263         }
264         return 0;
265 }
266
267 void copy_displist(ListBase *lbn, ListBase *lb)
268 {
269         DispList *dln, *dl;
270         
271         lbn->first= lbn->last= 0;
272         
273         dl= lb->first;
274         while(dl) {
275                 
276                 dln= MEM_dupallocN(dl);
277                 BLI_addtail(lbn, dln);
278                 dln->verts= MEM_dupallocN(dl->verts);
279                 dln->nors= MEM_dupallocN(dl->nors);
280                 dln->index= MEM_dupallocN(dl->index);
281                 dln->col1= MEM_dupallocN(dl->col1);
282                 dln->col2= MEM_dupallocN(dl->col2);
283                 
284                 dl= dl->next;
285         }
286 }
287
288 static void initfastshade(void)
289 {
290         Base *base;
291         Object *ob;
292         Lamp *la;
293         FastLamp *fl;
294         float mat[4][4];
295
296         init_render_world();
297         
298         if(fastlamplist) return;
299         if(G.scene->camera==0) G.scene->camera= scene_find_camera(G.scene);
300         if(G.scene->camera==0) return;
301
302         /* copied from 'roteerscene' (does that function still exist? (ton) */
303         where_is_object(G.scene->camera);
304         Mat4CpyMat4(R.viewinv, G.scene->camera->obmat);
305         Mat4Ortho(R.viewinv);
306         Mat4Invert(fviewmat, R.viewinv);
307
308         /* initrendertexture(); */
309
310         base= G.scene->base.first;
311         while(base) {
312                 ob= base->object;
313                 if( ob->type==OB_LAMP && (base->lay & G.scene->lay)) {
314                         
315                         Mat4MulMat4(mat, ob->obmat, fviewmat);
316                         
317                         la= ob->data;
318                         fl= MEM_mallocN(sizeof(FastLamp), "initfastshade2");
319
320                         fl->next= fastlamplist;
321                         fastlamplist= fl;
322
323                         fl->type= la->type;
324                         fl->mode= la->mode;
325                         fl->lay= base->lay;
326                         
327                         fl->vec[0]= mat[2][0];
328                         fl->vec[1]= mat[2][1];
329                         fl->vec[2]= mat[2][2];
330                         Normalise(fl->vec);
331                         
332                         fl->co[0]= mat[3][0];
333                         fl->co[1]= mat[3][1];
334                         fl->co[2]= mat[3][2];
335
336                         fl->dist= la->dist;
337                         fl->distkw= fl->dist*fl->dist;
338                         fl->att1= la->att1;
339                         fl->att2= la->att2;
340
341                         fl->spotsi= (float)cos( M_PI*la->spotsize/360.0 );
342                         fl->spotbl= (1.0f-fl->spotsi)*la->spotblend;
343         
344                         fl->r= la->energy*la->r;
345                         fl->g= la->energy*la->g;
346                         fl->b= la->energy*la->b;
347                 }
348                 
349                 if(base->next==0 && G.scene->set && base==G.scene->base.last) base= G.scene->set->base.first;
350                 else base= base->next;
351         }
352 }
353
354
355 void freefastshade()
356 {
357         while (fastlamplist) {
358                 FastLamp *fl= fastlamplist;
359                 fastlamplist= fl->next;
360                 
361                 MEM_freeN(fl);
362         }
363 }
364
365
366 static void fastshade(float *co, float *nor, float *orco, Material *ma, char *col1, char *col2, char *vertcol)
367 {
368         ShadeInput shi;
369         FastLamp *fl;
370         float i, t, inp, is, soft,  lv[3], lampdist, ld;
371         float diff1[3], diff2[3];
372         float isr1=0, isg1=0, isb1=0, isr=0, isg=0, isb=0;
373         int a, back;
374
375         if(ma==0) return;
376         
377         shi.mat= ma;
378         shi.vlr= NULL;  // have to do this!
379         
380         // copy all relevant material vars, note, keep this synced with render_types.h
381         memcpy(&shi.r, &shi.mat->r, 23*sizeof(float));
382         // set special cases:
383         shi.har= shi.mat->har;
384         
385         shi.osatex= 0;  // also prevents reading vlr
386         
387         VECCOPY(shi.vn, nor);
388         
389         if(ma->mode & MA_VERTEXCOLP) {
390                 if(vertcol) {
391                         shi.r= vertcol[3]/255.0;
392                         shi.g= vertcol[2]/255.0;
393                         shi.b= vertcol[1]/255.0;
394                 }
395         }
396         
397         if(ma->texco) {
398                 VECCOPY(shi.lo, orco);
399                 
400                 if(ma->texco & TEXCO_GLOB) {
401                         VECCOPY(shi.gl, shi.lo);
402                 }
403                 if(ma->texco & TEXCO_WINDOW) {
404                         VECCOPY(shi.winco, shi.lo);
405                 }
406                 if(ma->texco & TEXCO_STICKY) {
407                         VECCOPY(shi.sticky, shi.lo);
408                 }
409                 if(ma->texco & TEXCO_UV) {
410                         VECCOPY(shi.uv, shi.lo);
411                 }
412                 if(ma->texco & TEXCO_OBJECT) {
413                         VECCOPY(shi.co, shi.lo);
414                 }
415                 if(ma->texco & TEXCO_NORM) {
416                         VECCOPY(shi.orn, shi.vn);
417                 }
418                 if(ma->texco & TEXCO_REFL) {
419                         
420                         inp= 2.0*(shi.vn[2]);
421                         shi.ref[0]= (inp*shi.vn[0]);
422                         shi.ref[1]= (inp*shi.vn[1]);
423                         shi.ref[2]= (-1.0+inp*shi.vn[2]);
424                 }
425
426                 do_material_tex(&shi);
427         }
428
429         if(ma->mode & MA_SHLESS) {
430                 if(vertcol && (ma->mode & (MA_VERTEXCOL+MA_VERTEXCOLP))== MA_VERTEXCOL ) {
431                         float fac;
432                         fac= vertcol[3]*shi.r;
433                         col1[3]= fac>=1.0?255:(char)fac;
434                         fac= vertcol[2]*shi.g;
435                         col1[2]= fac>=1.0?255:(char)fac;
436                         fac= vertcol[1]*shi.b;
437                         col1[1]= fac>=1.0?255:(char)fac;
438                 }
439                 else {
440                         int fac;
441                         fac= (int) (255.0*shi.r);
442                         col1[3]= fac>255?255:(char)fac;
443                         fac= (int) (255.0*shi.g);
444                         col1[2]= fac>255?255:(char)fac;
445                         fac= (int) (255.0*shi.b);
446                         col1[1]= fac>255?255:(char)fac;
447                 }
448                 if(col2) {
449                         col2[3]= col1[3];
450                         col2[2]= col1[2];
451                         col2[1]= col1[1];
452                 }
453                 return;
454         }
455
456         if( vertcol && (ma->mode & (MA_VERTEXCOL+MA_VERTEXCOLP))== MA_VERTEXCOL ) {
457                 diff1[0]= diff2[0]= shi.r*(shi.emit+vertcol[3]/255.0);
458                 diff1[1]= diff2[1]= shi.g*(shi.emit+vertcol[2]/255.0);
459                 diff1[2]= diff2[2]= shi.b*(shi.emit+vertcol[1]/255.0);
460         }
461         else {
462                 diff1[0]= diff2[0]= shi.r*shi.emit;
463                 diff1[1]= diff2[1]= shi.g*shi.emit;
464                 diff1[2]= diff2[2]= shi.b*shi.emit;
465         }
466         
467         shi.view[0]= 0.0;
468         shi.view[1]= 0.0;
469         shi.view[2]= 1.0;
470         
471         Normalise(shi.view);
472
473         for (fl= fastlamplist; fl; fl= fl->next) {
474                 /* if(fl->mode & LA_LAYER) if((fl->lay & ma->lay)==0) continue; */
475
476                 if(fl->type==LA_SUN || fl->type==LA_HEMI) {
477                         VECCOPY(lv, fl->vec);
478                         lampdist= 1.0;
479                 }
480                 else {
481                         lv[0]= fl->co[0] - co[0];
482                         lv[1]= fl->co[1] - co[1];
483                         lv[2]= fl->co[2] - co[2];
484                         ld= sqrt(lv[0]*lv[0]+lv[1]*lv[1]+lv[2]*lv[2]);
485                         lv[0]/=ld;
486                         lv[1]/=ld;
487                         lv[2]/=ld;
488
489                         if(fl->mode & LA_QUAD) {
490                                 t= 1.0;
491                                 if(fl->att1>0.0)
492                                         t= fl->dist/(fl->dist+fl->att1*ld);
493                                 if(fl->att2>0.0)
494                                         t*= fl->distkw/(fl->distkw+fl->att2*ld*ld);
495
496                                 lampdist= t;
497                         }
498                         else {
499                                 lampdist= (fl->dist/(fl->dist+ld));
500                         }
501
502                         if(fl->mode & LA_SPHERE) {
503                                 t= fl->dist - ld;
504                                 if(t<0.0) continue;
505                                 
506                                 t/= fl->dist;
507                                 lampdist*= (t);
508                         }
509                 }
510
511                 if(fl->type==LA_SPOT) {
512                         inp= lv[0]*fl->vec[0]+lv[1]*fl->vec[1]+lv[2]*fl->vec[2];
513                         if(inp<fl->spotsi) continue;
514                         else {
515                                 t= inp-fl->spotsi;
516                                 i= 1.0;
517                                 soft= 1.0;
518                                 if(t<fl->spotbl && fl->spotbl!=0.0) {
519                                         /* soft area */
520                                         i= t/fl->spotbl;
521                                         t= i*i;
522                                         soft= (3.0*t-2.0*t*i);
523                                         inp*= soft;
524                                 }
525
526                                 lampdist*=inp;
527                         }
528                 }
529
530                 if(fl->mode & LA_NO_DIFF) is= 0.0;
531                 else {
532                         is= nor[0]*lv[0]+ nor[1]*lv[1]+ nor[2]*lv[2];
533         
534                         if(ma->diff_shader==MA_DIFF_ORENNAYAR) is= OrenNayar_Diff(nor, lv, shi.view, ma->roughness);
535                         else if(ma->diff_shader==MA_DIFF_TOON) is= Toon_Diff(nor, lv, shi.view, ma->param[0], ma->param[1]);
536                         else if(ma->diff_shader==MA_DIFF_MINNAERT) is= Minnaert_Diff(is, nor, shi.view, ma->darkness);
537                 }
538                 
539                 back= 0;
540                 if(is<0.0) {
541                         back= 1;
542                         is= -is;
543                 }
544                 inp= is*lampdist*shi.refl;
545
546                 if(back==0) {
547                         add_to_diffuse(diff1, &shi, is, inp*fl->r, inp*fl->g, inp*fl->b);
548                         //diff1[0]+= inp*fl->r;
549                         //diff1[1]+= inp*fl->g;
550                         //diff1[2]+= inp*fl->b;
551                 } else if(col2) {
552                         add_to_diffuse(diff2, &shi, is, inp*fl->r, inp*fl->g, inp*fl->b);
553                         //diff2[0]+= inp*fl->r;
554                         //diff2[1]+= inp*fl->g;
555                         //diff2[2]+= inp*fl->b;
556                 }
557                 if(shi.spec!=0.0 && (fl->mode & LA_NO_SPEC)==0) {
558                         float specfac;
559                         
560                         if(ma->spec_shader==MA_SPEC_PHONG) 
561                                 specfac= Phong_Spec(nor, lv, shi.view, shi.har);
562                         else if(ma->spec_shader==MA_SPEC_COOKTORR) 
563                                 specfac= CookTorr_Spec(nor, lv, shi.view, shi.har);
564                         else if(ma->spec_shader==MA_SPEC_BLINN) 
565                                 specfac= Blinn_Spec(nor, lv, shi.view, ma->refrac, (float)shi.har);
566                         else if(ma->spec_shader==MA_SPEC_WARDISO)
567                                 specfac= WardIso_Spec(nor, lv, shi.view, ma->rms);
568                         else 
569                                 specfac= Toon_Spec(nor, lv, shi.view, ma->param[2], ma->param[3]);
570                         
571                         if(specfac>0) {
572                                 t= specfac*shi.spec*lampdist;
573                                 if(back==0) {
574                                         if(ma->mode & MA_RAMP_SPEC) {
575                                                 float spec[3];
576                                                 do_specular_ramp(&shi, specfac, t, spec);
577                                                 isr+= t*(fl->r * spec[0]);
578                                                 isg+= t*(fl->g * spec[1]);
579                                                 isb+= t*(fl->b * spec[2]);
580                                         }
581                                         else {
582                                                 isr+= t*(fl->r * shi.specr);
583                                                 isg+= t*(fl->g * shi.specg);
584                                                 isb+= t*(fl->b * shi.specb);
585                                         }
586                                 }
587                                 else if(col2) {
588                                         if(ma->mode & MA_RAMP_SPEC) {
589                                                 float spec[3];
590                                                 do_specular_ramp(&shi, specfac, t, spec);
591                                                 isr1+= t*(fl->r * spec[0]);
592                                                 isg1+= t*(fl->g * spec[1]);
593                                                 isb1+= t*(fl->b * spec[2]);
594                                         }
595                                         else {
596                                                 isr1+= t*(fl->r * shi.specr);
597                                                 isg1+= t*(fl->g * shi.specg);
598                                                 isb1+= t*(fl->b * shi.specb);
599                                         }
600                                 }
601                         }
602                 }
603
604         }
605
606         if(ma->mode & MA_RAMP_COL) ramp_diffuse_result(diff1, &shi);
607         if(ma->mode & MA_RAMP_SPEC) ramp_spec_result(&isr, &isg, &isb, &shi);
608
609         a= 256*(diff1[0] + shi.ambr +isr);
610         if(a>255) col1[3]= 255; 
611         else col1[3]= a;
612         a= 256*(diff1[1] + shi.ambg +isg);
613         if(a>255) col1[2]= 255; 
614         else col1[2]= a;
615         a= 256*(diff1[2] + shi.ambb +isb);
616         if(a>255) col1[1]= 255; 
617         else col1[1]= a;
618
619         if(col2) {
620                 if(ma->mode & MA_RAMP_COL) ramp_diffuse_result(diff2, &shi);
621                 if(ma->mode & MA_RAMP_SPEC) ramp_spec_result(&isr1, &isg1, &isb1, &shi);
622                 
623                 a= 256*(diff2[0] + shi.ambr +isr1);
624                 if(a>255) col2[3]= 255; 
625                 else col2[3]= a;
626                 a= 256*(diff2[1] + shi.ambg +isg1);
627                 if(a>255) col2[2]= 255; 
628                 else col2[2]= a;
629                 a= 256*(diff2[2] + shi.ambb +isb1);
630                 if(a>255) col2[1]= 255; 
631                 else col2[1]= a;
632         }
633
634 }
635
636 void addnormalsDispList(Object *ob, ListBase *lb)
637 {
638         DispList *dl = NULL;
639         float *vdata, *ndata, nor[3];
640         float *v1, *v2, *v3, *v4;
641         float *n1, *n2, *n3, *n4;
642         int a, b, p1, p2, p3, p4;
643
644
645         dl= lb->first;
646         
647         while(dl) {
648                 if(dl->type==DL_INDEX3) {
649                         if(dl->nors==0) {
650                                 dl->nors= MEM_callocN(sizeof(float)*3, "dlnors");
651                                 if(dl->verts[2]<0.0) dl->nors[2]= -1.0;
652                                 else dl->nors[2]= 1.0;
653                         }
654                 }
655                 else if(dl->type==DL_SURF) {
656                         if(dl->nors==0) {
657                                 dl->nors= MEM_callocN(sizeof(float)*3*dl->nr*dl->parts, "dlnors");
658                                 
659                                 vdata= dl->verts;
660                                 ndata= dl->nors;
661                                 
662                                 for(a=0; a<dl->parts; a++) {
663         
664                                         DL_SURFINDEX(dl->flag & DL_CYCL_U, dl->flag & DL_CYCL_V, dl->nr, dl->parts);
665         
666                                         v1= vdata+ 3*p1; 
667                                         n1= ndata+ 3*p1;
668                                         v2= vdata+ 3*p2; 
669                                         n2= ndata+ 3*p2;
670                                         v3= vdata+ 3*p3; 
671                                         n3= ndata+ 3*p3;
672                                         v4= vdata+ 3*p4; 
673                                         n4= ndata+ 3*p4;
674                                         
675                                         for(; b<dl->nr; b++) {
676         
677                                                 CalcNormFloat4(v1, v3, v4, v2, nor);
678         
679                                                 VecAddf(n1, n1, nor);
680                                                 VecAddf(n2, n2, nor);
681                                                 VecAddf(n3, n3, nor);
682                                                 VecAddf(n4, n4, nor);
683         
684                                                 v2= v1; v1+= 3;
685                                                 v4= v3; v3+= 3;
686                                                 n2= n1; n1+= 3;
687                                                 n4= n3; n3+= 3;
688                                         }
689                                 }
690                                 a= dl->parts*dl->nr;
691                                 v1= ndata;
692                                 while(a--) {
693                                         Normalise(v1);
694                                         v1+= 3;
695                                 }
696                         }
697                 }
698                 dl= dl->next;
699         }
700 }
701
702 static void init_fastshade_for_ob(Object *ob, int *need_orco_r, float mat[4][4], float imat[3][3])
703 {
704         float tmat[4][4];
705         int a;
706
707         initfastshade();
708
709         Mat4MulMat4(mat, ob->obmat, fviewmat);
710         
711         Mat4Invert(tmat, mat);
712         Mat3CpyMat4(imat, tmat);
713         if(ob->transflag & OB_NEG_SCALE) Mat3MulFloat((float *)imat, -1.0);
714
715         if (need_orco_r) *need_orco_r= 0;
716         for(a=0; a<ob->totcol; a++) {
717                 Material *ma= give_current_material(ob, a+1);
718                 if(ma) {
719                         init_render_material(ma);
720                         if(ma->texco & TEXCO_ORCO) {
721                                 if (need_orco_r) *need_orco_r= 1;
722                         }
723                 }
724         }
725 }
726 static void end_fastshade_for_ob(Object *ob)
727 {
728         int a;
729
730         for(a=0; a<ob->totcol; a++) {
731                 Material *ma= give_current_material(ob, a+1);
732                 if(ma) end_render_material(ma);
733         }
734 }
735
736 void mesh_create_shadedColors(Object *ob, int onlyForMesh, unsigned int **col1_r, unsigned int **col2_r)
737 {
738         Mesh *me= ob->data;
739         int dmNeedsFree;
740         DerivedMesh *dm;
741         DispListMesh *dlm;
742         unsigned int *col1, *col2;
743         float *orco, *vnors, imat[3][3], mat[4][4], vec[3];
744         int a, i, need_orco;
745
746         init_fastshade_for_ob(ob, &need_orco, mat, imat);
747
748         if (need_orco) {
749                 orco = mesh_create_orco(ob);
750         } else {
751                 orco = NULL;
752         }
753
754         if (onlyForMesh) {
755                 dm = mesh_get_derived_deform(ob, &dmNeedsFree);
756         } else {
757                 dm = mesh_get_derived_final(ob, &dmNeedsFree);
758         }
759         dlm= dm->convertToDispListMesh(dm, 1);
760
761         col1 = MEM_mallocN(sizeof(*col1)*dlm->totface*4, "col1");
762         if (col2_r && (me->flag & ME_TWOSIDED)) {
763                 col2 = MEM_mallocN(sizeof(*col2)*dlm->totface*4, "col1");
764         } else {
765                 col2 = NULL;
766         }
767         
768         *col1_r = col1;
769         if (col2_r) *col2_r = col2;
770
771                 /* vertexnormals */
772         vnors= MEM_mallocN(dlm->totvert*3*sizeof(float), "vnors disp");
773         for (a=0; a<dlm->totvert; a++) {
774                 MVert *mv = &dlm->mvert[a];
775                 float *vn= &vnors[a*3];
776                 float xn= mv->no[0]; 
777                 float yn= mv->no[1]; 
778                 float zn= mv->no[2];
779                 
780                         /* transpose ! */
781                 vn[0]= imat[0][0]*xn+imat[0][1]*yn+imat[0][2]*zn;
782                 vn[1]= imat[1][0]*xn+imat[1][1]*yn+imat[1][2]*zn;
783                 vn[2]= imat[2][0]*xn+imat[2][1]*yn+imat[2][2]*zn;
784                 Normalise(vn);
785         }               
786
787         for (i=0; i<dlm->totface; i++) {
788                 MFace *mf= &dlm->mface[i];
789
790                 if (mf->v3) {
791                         int j, vidx[4], nverts= mf->v4?4:3;
792                         unsigned char *col1base= (unsigned char*) &col1[i*4];
793                         unsigned char *col2base= (unsigned char*) (col2?&col2[i*4]:NULL);
794                         unsigned char *mcolbase;
795                         Material *ma= give_current_material(ob, mf->mat_nr+1);
796                         float nor[3], n1[3];
797                         
798                         if(ma==0) ma= &defmaterial;
799                         
800                         if (dlm->tface) {
801                                 mcolbase = (unsigned char*) dlm->tface[i].col;
802                         } else if (dlm->mcol) {
803                                 mcolbase = (unsigned char*) &dlm->mcol[i*4];
804                         } else {
805                                 mcolbase = NULL;
806                         }
807
808                         vidx[0]= mf->v1;
809                         vidx[1]= mf->v2;
810                         vidx[2]= mf->v3;
811                         vidx[3]= mf->v4;
812
813                         if (dlm->nors) {
814                                 VECCOPY(nor, &dlm->nors[i*3]);
815                         } else {
816                                 if (mf->v4)
817                                         CalcNormFloat4(dlm->mvert[mf->v1].co, dlm->mvert[mf->v2].co, dlm->mvert[mf->v3].co, dlm->mvert[mf->v4].co, nor);
818                                 else
819                                         CalcNormFloat(dlm->mvert[mf->v1].co, dlm->mvert[mf->v2].co, dlm->mvert[mf->v3].co, nor);
820                         }
821
822                         n1[0]= imat[0][0]*nor[0]+imat[0][1]*nor[1]+imat[0][2]*nor[2];
823                         n1[1]= imat[1][0]*nor[0]+imat[1][1]*nor[1]+imat[1][2]*nor[2];
824                         n1[2]= imat[2][0]*nor[0]+imat[2][1]*nor[1]+imat[2][2]*nor[2];
825                         Normalise(n1);
826
827                         for (j=0; j<nverts; j++) {
828                                 MVert *mv= &dlm->mvert[vidx[j]];
829                                 unsigned char *col1= &col1base[j*4];
830                                 unsigned char *col2= col2base?&col2base[j*4]:NULL;
831                                 unsigned char *mcol= mcolbase?&mcolbase[j*4]:NULL;
832                                 float *vn = (mf->flag & ME_SMOOTH)?&vnors[3*vidx[j]]:n1;
833
834                                 VECCOPY(vec, mv->co);
835                                 Mat4MulVecfl(mat, vec);
836                                 fastshade(vec, vn, orco?&orco[vidx[j]*3]:mv->co, ma, col1, col2, mcol);
837                         }
838                 }
839         }
840         MEM_freeN(vnors);
841         displistmesh_free(dlm);
842
843         if (orco) {
844                 MEM_freeN(orco);
845         }
846
847         if (dmNeedsFree) dm->release(dm);
848
849         end_fastshade_for_ob(ob);
850 }
851
852 void shadeDispList(Object *ob)
853 {
854         DispList *dl, *dlob;
855         Material *ma = NULL;
856         Curve *cu;
857         float imat[3][3], mat[4][4], vec[3];
858         float *fp, *nor, n1[3];
859         unsigned int *col1;
860         int a;
861
862         if(ob->flag & OB_FROMDUPLI) return;
863
864         dl = find_displist(&ob->disp, DL_VERTCOL);
865         if (dl) {
866                 BLI_remlink(&ob->disp, dl);
867                 free_disp_elem(dl);
868         }
869
870         if(ob->type==OB_MESH) {
871                 dl= MEM_callocN(sizeof(DispList), "displistshade");
872                 BLI_addtail(&ob->disp, dl);
873                 dl->type= DL_VERTCOL;
874
875                 mesh_create_shadedColors(ob, 0, &dl->col1, &dl->col2);
876
877                 return;
878         }
879
880         init_fastshade_for_ob(ob, NULL, mat, imat);
881         
882         if ELEM3(ob->type, OB_CURVE, OB_SURF, OB_FONT) {
883         
884                 /* now we need the normals */
885                 cu= ob->data;
886                 dl= cu->disp.first;
887                 
888                 while(dl) {
889                         dlob= MEM_callocN(sizeof(DispList), "displistshade");
890                         BLI_addtail(&ob->disp, dlob);
891                         dlob->type= DL_VERTCOL;
892                         dlob->parts= dl->parts;
893                         dlob->nr= dl->nr;
894                         
895                         if(dl->type==DL_INDEX3) {
896                                 col1= dlob->col1= MEM_mallocN(sizeof(int)*dl->nr, "col1");
897                         }
898                         else {
899                                 col1= dlob->col1= MEM_mallocN(sizeof(int)*dl->parts*dl->nr, "col1");
900                         }
901                         
902                 
903                         ma= give_current_material(ob, dl->col+1);
904                         if(ma==0) ma= &defmaterial;
905
906                         if(dl->type==DL_INDEX3) {
907                                 if(dl->nors) {
908                                         /* there's just one normal */
909                                         n1[0]= imat[0][0]*dl->nors[0]+imat[0][1]*dl->nors[1]+imat[0][2]*dl->nors[2];
910                                         n1[1]= imat[1][0]*dl->nors[0]+imat[1][1]*dl->nors[1]+imat[1][2]*dl->nors[2];
911                                         n1[2]= imat[2][0]*dl->nors[0]+imat[2][1]*dl->nors[1]+imat[2][2]*dl->nors[2];
912                                         Normalise(n1);
913                                         
914                                         fp= dl->verts;
915                                         
916                                         a= dl->nr;              
917                                         while(a--) {
918                                                 VECCOPY(vec, fp);
919                                                 Mat4MulVecfl(mat, vec);
920                                                 
921                                                 fastshade(vec, n1, fp, ma, (char *)col1, 0, 0);
922                                                 
923                                                 fp+= 3; col1++;
924                                         }
925                                 }
926                         }
927                         else if(dl->type==DL_SURF) {
928                                 if(dl->nors) {
929                                         a= dl->nr*dl->parts;
930                                         fp= dl->verts;
931                                         nor= dl->nors;
932                                         
933                                         while(a--) {
934                                                 VECCOPY(vec, fp);
935                                                 Mat4MulVecfl(mat, vec);
936                                                 
937                                                 n1[0]= imat[0][0]*nor[0]+imat[0][1]*nor[1]+imat[0][2]*nor[2];
938                                                 n1[1]= imat[1][0]*nor[0]+imat[1][1]*nor[1]+imat[1][2]*nor[2];
939                                                 n1[2]= imat[2][0]*nor[0]+imat[2][1]*nor[1]+imat[2][2]*nor[2];
940                                                 Normalise(n1);
941                         
942                                                 fastshade(vec, n1, fp, ma, (char *)col1, 0, 0);
943                                                 
944                                                 fp+= 3; nor+= 3; col1++;
945                                         }
946                                 }
947                         }
948                         dl= dl->next;
949                 }
950         }
951         else if(ob->type==OB_MBALL) {
952                 /* there are normals already */
953                 dl= ob->disp.first;
954                 
955                 while(dl) {
956                         
957                         if(dl->type==DL_INDEX4) {
958                                 if(dl->nors) {
959                                         
960                                         if(dl->col1) MEM_freeN(dl->col1);
961                                         col1= dl->col1= MEM_mallocN(sizeof(int)*dl->nr, "col1");
962                         
963                                         ma= give_current_material(ob, dl->col+1);
964                                         if(ma==0) ma= &defmaterial;
965         
966                                         fp= dl->verts;
967                                         nor= dl->nors;
968                                         
969                                         a= dl->nr;              
970                                         while(a--) {
971                                                 VECCOPY(vec, fp);
972                                                 Mat4MulVecfl(mat, vec);
973                                                 
974                                                 /* transpose ! */
975                                                 n1[0]= imat[0][0]*nor[0]+imat[0][1]*nor[1]+imat[0][2]*nor[2];
976                                                 n1[1]= imat[1][0]*nor[0]+imat[1][1]*nor[1]+imat[1][2]*nor[2];
977                                                 n1[2]= imat[2][0]*nor[0]+imat[2][1]*nor[1]+imat[2][2]*nor[2];
978                                                 Normalise(n1);
979                                         
980                                                 fastshade(vec, n1, fp, ma, (char *)col1, 0, 0);
981                                                 
982                                                 fp+= 3; col1++; nor+= 3;
983                                         }
984                                 }
985                         }
986                         dl= dl->next;
987                 }
988         }
989         
990         end_fastshade_for_ob(ob);
991 }
992
993 void reshadeall_displist(void)
994 {
995         Base *base;
996         Object *ob;
997         
998         freefastshade();
999         
1000         base= G.scene->base.first;
1001         while(base) {
1002                 if(base->lay & G.scene->lay) {
1003                         ob= base->object;
1004                         
1005                         /* Metaballs have standard displist at the Object */
1006                         if(ob->type==OB_MBALL) shadeDispList(ob);
1007                         else freedisplist(&ob->disp);
1008                 }
1009                 base= base->next;
1010         }
1011 }
1012
1013 void count_displist(ListBase *lb, int *totvert, int *totface)
1014 {
1015         DispList *dl;
1016         
1017         dl= lb->first;
1018         while(dl) {
1019                 
1020                 switch(dl->type) {
1021                 case DL_SURF:
1022                         *totvert+= dl->nr*dl->parts;
1023                         *totface+= (dl->nr-1)*(dl->parts-1);
1024                         break;
1025                 case DL_INDEX3:
1026                 case DL_INDEX4:
1027                         *totvert+= dl->nr;
1028                         *totface+= dl->parts;
1029                         break;
1030                 case DL_POLY:
1031                 case DL_SEGM:
1032                         *totvert+= dl->nr*dl->parts;
1033                 }
1034                 
1035                 dl= dl->next;
1036         }
1037 }
1038
1039 static void curve_to_displist(Curve *cu, ListBase *nubase, ListBase *dispbase)
1040 {
1041         Nurb *nu;
1042         DispList *dl;
1043         BezTriple *bezt, *prevbezt;
1044         BPoint *bp;
1045         float *data, *v1, *v2;
1046         int a, len;
1047         
1048         nu= nubase->first;
1049         while(nu) {
1050                 if(nu->hide==0) {
1051                         if((nu->type & 7)==CU_BEZIER) {
1052                                 
1053                                 /* count */
1054                                 len= 0;
1055                                 a= nu->pntsu-1;
1056                                 if(nu->flagu & 1) a++;
1057
1058                                 prevbezt= nu->bezt;
1059                                 bezt= prevbezt+1;
1060                                 while(a--) {
1061                                         if(a==0 && (nu->flagu & 1)) bezt= nu->bezt;
1062                                         
1063                                         if(prevbezt->h2==HD_VECT && bezt->h1==HD_VECT) len++;
1064                                         else len+= nu->resolu;
1065                                         
1066                                         if(a==0 && (nu->flagu & 1)==0) len++;
1067                                         
1068                                         prevbezt= bezt;
1069                                         bezt++;
1070                                 }
1071                                 
1072                                 dl= MEM_callocN(sizeof(DispList), "makeDispListbez");
1073                                 /* len+1 because of 'forward_diff_bezier' function */
1074                                 dl->verts= MEM_callocN( (len+1)*3*sizeof(float), "dlverts");
1075                                 BLI_addtail(dispbase, dl);
1076                                 dl->parts= 1;
1077                                 dl->nr= len;
1078                                 dl->col= nu->mat_nr;
1079                                 dl->charidx= nu->charidx;
1080
1081                                 data= dl->verts;
1082
1083                                 if(nu->flagu & 1) {
1084                                         dl->type= DL_POLY;
1085                                         a= nu->pntsu;
1086                                 }
1087                                 else {
1088                                         dl->type= DL_SEGM;
1089                                         a= nu->pntsu-1;
1090                                 }
1091                                 
1092                                 prevbezt= nu->bezt;
1093                                 bezt= prevbezt+1;
1094                                 
1095                                 while(a--) {
1096                                         if(a==0 && dl->type== DL_POLY) bezt= nu->bezt;
1097                                         
1098                                         if(prevbezt->h2==HD_VECT && bezt->h1==HD_VECT) {
1099                                                 VECCOPY(data, prevbezt->vec[1]);
1100                                                 data+= 3;
1101                                         }
1102                                         else {
1103                                                 v1= prevbezt->vec[1];
1104                                                 v2= bezt->vec[0];
1105                                                 forward_diff_bezier(v1[0], v1[3], v2[0], v2[3], data, nu->resolu, 3);
1106                                                 forward_diff_bezier(v1[1], v1[4], v2[1], v2[4], data+1, nu->resolu, 3);
1107                                                 if((nu->type & 8)==0)
1108                                                         forward_diff_bezier(v1[2], v1[5], v2[2], v2[5], data+2, nu->resolu, 3);
1109                                                 data+= 3*nu->resolu;
1110                                         }
1111                                         
1112                                         if(a==0 && dl->type==DL_SEGM) {
1113                                                 VECCOPY(data, bezt->vec[1]);
1114                                         }
1115                                         
1116                                         prevbezt= bezt;
1117                                         bezt++;
1118                                 }
1119                         }
1120                         else if((nu->type & 7)==CU_NURBS) {
1121                                 len= nu->pntsu*nu->resolu;
1122                                 dl= MEM_callocN(sizeof(DispList), "makeDispListsurf");
1123                                 dl->verts= MEM_callocN(len*3*sizeof(float), "dlverts");
1124                                 BLI_addtail(dispbase, dl);
1125                                 dl->parts= 1;
1126                                 dl->nr= len;
1127                                 dl->col= nu->mat_nr;
1128
1129                                 data= dl->verts;
1130                                 if(nu->flagu & 1) dl->type= DL_POLY;
1131                                 else dl->type= DL_SEGM;
1132                                 makeNurbcurve(nu, data, 3);
1133                         }
1134                         else if((nu->type & 7)==CU_POLY) {
1135                                 len= nu->pntsu;
1136                                 dl= MEM_callocN(sizeof(DispList), "makeDispListpoly");
1137                                 dl->verts= MEM_callocN(len*3*sizeof(float), "dlverts");
1138                                 BLI_addtail(dispbase, dl);
1139                                 dl->parts= 1;
1140                                 dl->nr= len;
1141                                 dl->col= nu->mat_nr;
1142
1143                                 data= dl->verts;
1144                                 if(nu->flagu & 1) dl->type= DL_POLY;
1145                                 else dl->type= DL_SEGM;
1146                                 
1147                                 a= len;
1148                                 bp= nu->bp;
1149                                 while(a--) {
1150                                         VECCOPY(data, bp->vec);
1151                                         bp++;
1152                                         data+= 3;
1153                                 }
1154                         }
1155                 }
1156                 nu= nu->next;
1157         }
1158 }
1159
1160
1161 void filldisplist(ListBase *dispbase, ListBase *to)
1162 {
1163         EditVert *eve, *v1, *vlast;
1164         EditFace *efa;
1165         DispList *dlnew=0, *dl;
1166         float *f1;
1167         int colnr=0, charidx=0, cont=1, tot, a, *index;
1168         long totvert;
1169         
1170         if(dispbase==0) return;
1171         if(dispbase->first==0) return;
1172
1173         while(cont) {
1174                 cont= 0;
1175                 totvert=0;
1176                 
1177                 dl= dispbase->first;
1178                 while(dl) {
1179         
1180                         if(dl->type==DL_POLY) {
1181                                 if(charidx<dl->charidx) cont= 1;
1182                                 else if(charidx==dl->charidx) {
1183                         
1184                                         colnr= dl->col;
1185                                         charidx= dl->charidx;
1186                 
1187                                         /* make editverts and edges */
1188                                         f1= dl->verts;
1189                                         a= dl->nr;
1190                                         eve= v1= 0;
1191                                         
1192                                         while(a--) {
1193                                                 vlast= eve;
1194                                                 
1195                                                 eve= BLI_addfillvert(f1);
1196                                                 totvert++;
1197                                                 
1198                                                 if(vlast==0) v1= eve;
1199                                                 else {
1200                                                         BLI_addfilledge(vlast, eve);
1201                                                 }
1202                                                 f1+=3;
1203                                         }
1204                                 
1205                                         if(eve!=0 && v1!=0) {
1206                                                 BLI_addfilledge(eve, v1);
1207                                         }
1208                                 }
1209                         }
1210                         dl= dl->next;
1211                 }
1212                 
1213                 if(totvert && BLI_edgefill(0, (G.obedit && G.obedit->actcol)?(G.obedit->actcol-1):0)) {
1214
1215                         /* count faces  */
1216                         tot= 0;
1217                         efa= fillfacebase.first;
1218                         while(efa) {
1219                                 tot++;
1220                                 efa= efa->next;
1221                         }
1222
1223                         if(tot) {
1224                                 dlnew= MEM_callocN(sizeof(DispList), "filldisplist");
1225                                 dlnew->type= DL_INDEX3;
1226                                 dlnew->col= colnr;
1227                                 dlnew->nr= totvert;
1228                                 dlnew->parts= tot;
1229
1230                                 dlnew->index= MEM_mallocN(tot*3*sizeof(int), "dlindex");
1231                                 dlnew->verts= MEM_mallocN(totvert*3*sizeof(float), "dlverts");
1232                                 
1233                                 /* vert data */
1234                                 f1= dlnew->verts;
1235                                 totvert= 0;
1236                                 eve= fillvertbase.first;
1237                                 while(eve) {
1238                                         VECCOPY(f1, eve->co);
1239                                         f1+= 3;
1240         
1241                                         /* index number */
1242                                         eve->vn= (EditVert *)totvert;
1243                                         totvert++;
1244                                         
1245                                         eve= eve->next;
1246                                 }
1247                                 
1248                                 /* index data */
1249                                 efa= fillfacebase.first;
1250                                 index= dlnew->index;
1251                                 while(efa) {
1252                                         index[0]= (long)efa->v1->vn;
1253                                         index[1]= (long)efa->v2->vn;
1254                                         index[2]= (long)efa->v3->vn;
1255                                         
1256                                         index+= 3;
1257                                         efa= efa->next;
1258                                 }
1259                         }
1260
1261                         BLI_addhead(to, dlnew);
1262                         
1263                 }
1264                 BLI_end_edgefill();
1265
1266                 charidx++;
1267         }
1268         
1269         /* do not free polys, needed for wireframe display */
1270         
1271 }
1272
1273 static void bevels_to_filledpoly(Curve *cu, ListBase *dispbase)
1274 {
1275         ListBase front, back;
1276         DispList *dl, *dlnew;
1277         float *fp, *fp1;
1278         int a, dpoly;
1279         
1280         front.first= front.last= back.first= back.last= 0;
1281         
1282         dl= dispbase->first;
1283         while(dl) {
1284                 if(dl->type==DL_SURF) {
1285                         if( (dl->flag & DL_CYCL_V) && (dl->flag & DL_CYCL_U)==0 ) {
1286                                 if( (cu->flag & CU_BACK) && (dl->flag & DL_BACK_CURVE) ) {
1287                                         dlnew= MEM_callocN(sizeof(DispList), "filldisp");
1288                                         BLI_addtail(&front, dlnew);
1289                                         dlnew->verts= fp1= MEM_mallocN(sizeof(float)*3*dl->parts, "filldisp1");
1290                                         dlnew->nr= dl->parts;
1291                                         dlnew->parts= 1;
1292                                         dlnew->type= DL_POLY;
1293                                         dlnew->col= dl->col;
1294                                         
1295                                         fp= dl->verts;
1296                                         dpoly= 3*dl->nr;
1297                                         
1298                                         a= dl->parts;
1299                                         while(a--) {
1300                                                 VECCOPY(fp1, fp);
1301                                                 fp1+= 3;
1302                                                 fp+= dpoly;
1303                                         }
1304                                 }
1305                                 if( (cu->flag & CU_FRONT) && (dl->flag & DL_FRONT_CURVE) ) {
1306                                         dlnew= MEM_callocN(sizeof(DispList), "filldisp");
1307                                         BLI_addtail(&back, dlnew);
1308                                         dlnew->verts= fp1= MEM_mallocN(sizeof(float)*3*dl->parts, "filldisp1");
1309                                         dlnew->nr= dl->parts;
1310                                         dlnew->parts= 1;
1311                                         dlnew->type= DL_POLY;
1312                                         dlnew->col= dl->col;
1313                                         
1314                                         fp= dl->verts+3*(dl->nr-1);
1315                                         dpoly= 3*dl->nr;
1316                                         
1317                                         a= dl->parts;
1318                                         while(a--) {
1319                                                 VECCOPY(fp1, fp);
1320                                                 fp1+= 3;
1321                                                 fp+= dpoly;
1322                                         }
1323                                 }
1324                         }
1325                 }
1326                 dl= dl->next;
1327         }
1328
1329         filldisplist(&front, dispbase);
1330         filldisplist(&back, dispbase);
1331         
1332         freedisplist(&front);
1333         freedisplist(&back);
1334
1335         filldisplist(dispbase, dispbase);
1336         
1337 }
1338
1339 void curve_to_filledpoly(Curve *cu, ListBase *nurb, ListBase *dispbase)
1340 {
1341         if(cu->flag & CU_3D) return;
1342
1343         if(dispbase->first && ((DispList*) dispbase->first)->type==DL_SURF) {
1344                 bevels_to_filledpoly(cu, dispbase);
1345         }
1346         else {
1347                 filldisplist(dispbase, dispbase);
1348         }
1349 }
1350
1351
1352 /* taper rules:
1353   - only 1 curve
1354   - first point left, last point right
1355   - based on subdivided points in original curve, not on points in taper curve (still)
1356 */
1357 static float calc_taper(Object *taperobj, int cur, int tot)
1358 {
1359         Curve *cu;
1360         DispList *dl;
1361         
1362         if(taperobj==NULL) return 1.0;
1363         
1364         cu= taperobj->data;
1365         dl= cu->disp.first;
1366         if(dl==NULL) {
1367                 makeDispListCurveTypes(taperobj, 0);
1368                 dl= cu->disp.first;
1369         }
1370         if(dl) {
1371                 float fac= ((float)cur)/(float)(tot-1);
1372                 float minx, dx, *fp;
1373                 int a;
1374                 
1375                 /* horizontal size */
1376                 minx= dl->verts[0];
1377                 dx= dl->verts[3*(dl->nr-1)] - minx;
1378                 if(dx>0.0) {
1379                 
1380                         fp= dl->verts;
1381                         for(a=0; a<dl->nr; a++, fp+=3) {
1382                                 if( (fp[0]-minx)/dx >= fac) {
1383                                         /* interpolate with prev */
1384                                         if(a>0) {
1385                                                 float fac1= (fp[-3]-minx)/dx;
1386                                                 float fac2= (fp[0]-minx)/dx;
1387                                                 if(fac1!=fac2)
1388                                                         return fp[1]*(fac1-fac)/(fac1-fac2) + fp[-2]*(fac-fac2)/(fac1-fac2);
1389                                         }
1390                                         return fp[1];
1391                                 }
1392                         }
1393                         return fp[-2];  // last y coord
1394                 }
1395         }
1396         
1397         return 1.0;
1398 }
1399
1400 void makeDispListMBall(Object *ob)
1401 {
1402         if(!ob || (ob->flag&OB_FROMDUPLI) || ob->type!=OB_MBALL) return;
1403
1404         freedisplist(&(ob->disp));
1405         
1406         if(ob->type==OB_MBALL) {
1407                 if(ob==find_basis_mball(ob)) {
1408                         metaball_polygonize(ob);
1409                         tex_space_mball(ob);
1410
1411                         object_deform_mball(ob);
1412                 }
1413         }
1414         
1415         boundbox_displist(ob);
1416 }
1417 void makeDispListSurf(Object *ob, ListBase *dispbase, int forRender)
1418 {
1419         Nurb *nu;
1420         Curve *cu = ob->data;
1421         DispList *dl;
1422         float *data;
1423         int len;
1424                 
1425         if(!forRender && ob==G.obedit) nu= editNurb.first;
1426         else {
1427                 do_curve_key(cu);
1428
1429                 nu= cu->nurb.first;
1430         }
1431                 
1432         while(nu) {
1433                 if(forRender || nu->hide==0) {
1434                         if(nu->pntsv==1) {
1435                                 len= nu->pntsu*nu->resolu;
1436                                 
1437                                 dl= MEM_callocN(sizeof(DispList), "makeDispListsurf");
1438                                 dl->verts= MEM_callocN(len*3*sizeof(float), "dlverts");
1439                                 
1440                                 BLI_addtail(dispbase, dl);
1441                                 dl->parts= 1;
1442                                 dl->nr= len;
1443                                 dl->col= nu->mat_nr;
1444                                 dl->rt= nu->flag;
1445                                 
1446                                 data= dl->verts;
1447                                 if(nu->flagu & 1) dl->type= DL_POLY;
1448                                 else dl->type= DL_SEGM;
1449                                 
1450                                 makeNurbcurve(nu, data, 3);
1451                         }
1452                         else {
1453                                 len= nu->resolu*nu->resolv;
1454                                 
1455                                 dl= MEM_callocN(sizeof(DispList), "makeDispListsurf");
1456                                 dl->verts= MEM_callocN(len*3*sizeof(float), "dlverts");
1457                                 BLI_addtail(dispbase, dl);
1458
1459                                 dl->col= nu->mat_nr;
1460                                 dl->rt= nu->flag;
1461                                 
1462                                 data= dl->verts;
1463                                 dl->type= DL_SURF;
1464
1465                                 dl->parts= nu->resolu;  /* in reverse, because makeNurbfaces works that way */
1466                                 dl->nr= nu->resolv;
1467                                 if(nu->flagv & CU_CYCLIC) dl->flag|= DL_CYCL_U; /* reverse too! */
1468                                 if(nu->flagu & CU_CYCLIC) dl->flag|= DL_CYCL_V;
1469
1470                                 makeNurbfaces(nu, data, 0);
1471                         }
1472                 }
1473                 nu= nu->next;
1474         }
1475
1476         if (!forRender) {
1477                 tex_space_curve(cu);
1478         }
1479
1480         if(forRender || ob!=G.obedit) object_deform_curve(ob, dispbase);
1481 }
1482 void makeDispListCurveTypes(Object *ob, int forOrco)
1483 {
1484         Curve *cu = ob->data;
1485         ListBase *dispbase;
1486
1487         if((ob->flag&OB_FROMDUPLI) || !ELEM3(ob->type, OB_SURF, OB_CURVE, OB_FONT)) return;
1488         if(ob->flag & OB_FROMDUPLI) return;
1489
1490         freedisplist(&(ob->disp));
1491         dispbase= &(cu->disp);
1492         freedisplist(dispbase);
1493         
1494         if(ob->type==OB_SURF) {
1495                 makeDispListSurf(ob, dispbase, 0);
1496         }
1497         else if ELEM(ob->type, OB_CURVE, OB_FONT) {
1498                 int obedit= (G.obedit && G.obedit->data==ob->data);
1499                 
1500                 BLI_freelistN(&(cu->bev));
1501                 
1502                 if(cu->path) free_path(cu->path);
1503                 cu->path= NULL;
1504                 
1505                 if(ob->type==OB_FONT) text_to_curve(ob, 0);
1506                 
1507                 if(!obedit && !forOrco) do_curve_key(cu);
1508
1509                 makeBevelList(ob);
1510
1511                 if(obedit) {
1512                         if(ob->type==OB_CURVE) {
1513                                 curve_to_displist(cu, &editNurb, dispbase);
1514                                 curve_to_filledpoly(cu, &editNurb, dispbase);
1515                         }
1516                         else {
1517                                 curve_to_displist(cu, &cu->nurb, dispbase);
1518                                 if (!(cu->flag&CU_FAST)) {
1519                                         curve_to_filledpoly(cu, &cu->nurb, dispbase);
1520                                 }
1521                         }
1522                 }
1523                 else {
1524                         ListBase dlbev;;
1525
1526                                 /* If curve has no bevel will return nothing */
1527                         makebevelcurve(ob, &dlbev);
1528
1529                         if (!dlbev.first) {
1530                                 curve_to_displist(cu, &cu->nurb, dispbase);
1531                         } else {
1532                                 float widfac= cu->width-1.0;
1533                                 BevList *bl= cu->bev.first;
1534                                 Nurb *nu= cu->nurb.first;
1535
1536                                 for (; bl && nu; bl=bl->next,nu=nu->next) {
1537                                         DispList *dlb;
1538                                         
1539                                         for (dlb=dlbev.first; dlb; dlb=dlb->next) {
1540                                                 DispList *dl;
1541                                                 float *fp1, *data;
1542                                                 BevPoint *bevp;
1543                                                 int a,b;
1544
1545                                                         /* for each part of the bevel use a separate displblock */
1546                                                 dl= MEM_callocN(sizeof(DispList), "makeDispListbev1");
1547                                                 dl->verts= data= MEM_callocN(3*sizeof(float)*dlb->nr*bl->nr, "dlverts");
1548                                                 BLI_addtail(dispbase, dl);
1549
1550                                                 dl->type= DL_SURF;
1551                                                 
1552                                                 dl->flag= dlb->flag & (DL_FRONT_CURVE|DL_BACK_CURVE);
1553                                                 if(dlb->type==DL_POLY) dl->flag |= DL_CYCL_U;
1554                                                 if(bl->poly>=0) dl->flag |= DL_CYCL_V;
1555                                                 
1556                                                 dl->parts= bl->nr;
1557                                                 dl->nr= dlb->nr;
1558                                                 dl->col= nu->mat_nr;
1559                                                 dl->rt= nu->flag;
1560                                                 dl->bevelSplitFlag= MEM_callocN(sizeof(*dl->col2)*((bl->nr+0x1F)>>5), "col2");
1561                                                 bevp= (BevPoint *)(bl+1);
1562
1563                                                         /* for each point of poly make a bevel piece */
1564                                                 bevp= (BevPoint *)(bl+1);
1565                                                 for(a=0; a<bl->nr; a++,bevp++) {
1566                                                         float fac = calc_taper(cu->taperobj, a, bl->nr);
1567                                                         
1568                                                         if (bevp->f1) {
1569                                                                 dl->bevelSplitFlag[a>>5] |= 1<<(a&0x1F);
1570                                                         }
1571
1572                                                                 /* rotate bevel piece and write in data */
1573                                                         fp1= dlb->verts;
1574                                                         for (b=0; b<dlb->nr; b++,fp1+=3,data+=3) {
1575                                                                 if(cu->flag & CU_3D) {
1576                                                                         float vec[3];
1577
1578                                                                         vec[0]= fp1[1]+widfac;
1579                                                                         vec[1]= fp1[2];
1580                                                                         vec[2]= 0.0;
1581                                                                         
1582                                                                         Mat3MulVecfl(bevp->mat, vec);
1583                                                                         
1584                                                                         data[0]= bevp->x+ fac*vec[0];
1585                                                                         data[1]= bevp->y+ fac*vec[1];
1586                                                                         data[2]= bevp->z+ fac*vec[2];
1587                                                                 }
1588                                                                 else {
1589                                                                         data[0]= bevp->x+ fac*(widfac+fp1[1])*bevp->sina;
1590                                                                         data[1]= bevp->y+ fac*(widfac+fp1[1])*bevp->cosa;
1591                                                                         data[2]= bevp->z+ fac*fp1[2];
1592                                                                 }
1593                                                         }
1594                                                 }
1595                                         }
1596                                 }
1597
1598                                 freedisplist(&dlbev);
1599                         }
1600
1601                         curve_to_filledpoly(cu, &cu->nurb, dispbase);
1602                 }
1603                 if(cu->flag & CU_PATH) calc_curvepath(ob);
1604
1605                 if(!obedit) object_deform_curve(ob, &cu->disp);
1606                 tex_space_curve(cu);
1607         }
1608         
1609         boundbox_displist(ob);
1610 }
1611
1612 /*******************************/
1613 /*****       OUTLINE       *****/
1614 /*******************************/
1615
1616 typedef struct Sample{
1617         short x, y;
1618 } Sample;
1619
1620 typedef struct Segment{
1621         /* coordinates */
1622         struct Segment * next, * prev;
1623         float co[2];
1624 } Segment;
1625
1626
1627
1628 static int dflt_in_out(struct ImBuf * ibuf, int x, int y)
1629 {
1630         unsigned char * rect;
1631         
1632         if (ibuf == 0) return (0);
1633         if (x < 0 || y < 0 || x >= ibuf->x || y >= ibuf->y || ibuf->rect == 0) return (-1);
1634         
1635         rect = (unsigned char *) (ibuf->rect + (y * ibuf->x) + x);
1636         if (rect[0] > 0x81) return (1);
1637         return(0);
1638 }
1639
1640
1641 static Sample * outline(struct ImBuf * ibuf,
1642                                  int (*in_or_out)(struct ImBuf *, int, int))
1643 {
1644         static int dirs[8][2] = {
1645                 {-1,  0}, {-1,  1},     {0,  1}, {1,  1}, 
1646                 {1,  0}, {1, -1}, {0, -1}, {-1, -1}
1647         };
1648         
1649         int dir, x, y, in, i;
1650         int count, sampcount;
1651         int startx = 0, starty = 0;
1652         Sample * samp, * oldsamp;
1653         
1654         /* input:
1655          * 1 - image 
1656          * 2 - pointer to function that defines which pixel 'in' or 'out' is
1657          */
1658         
1659         if (ibuf == 0) return (0);
1660         if (ibuf->rect == 0) return (0);
1661         
1662         if (in_or_out == 0) in_or_out = dflt_in_out;
1663         in = in_or_out(ibuf, 0, 0);
1664         
1665         /* search for first transition, and continue from there */      
1666         for (y = 0; y < ibuf->y; y++) {
1667                 for (x = 0; x < ibuf->x; x++) {
1668                         if (in_or_out(ibuf, x, y) != in) {
1669                                 /* found first 'other' point !! */
1670                                 
1671                                 if (x != startx) dir = 0;
1672                                 else dir = 6;
1673                                 
1674                                 startx = x; starty = y;
1675                                 count = 1;
1676                                 sampcount = 2000;
1677                                 samp = MEM_mallocN(sampcount * sizeof(Sample), "wire_samples");
1678                                 
1679                                 do{
1680                                         samp[count].x = x; samp[count].y = y;
1681                                         count++;
1682                                         
1683                                         if (count >= sampcount) {
1684                                                 oldsamp = samp;
1685                                                 samp = MEM_mallocN(2 * sampcount * sizeof(Sample), "wire_samples");
1686                                                 memcpy(samp, oldsamp, sampcount * sizeof(Sample));
1687                                                 sampcount *= 2;
1688                                                 MEM_freeN(oldsamp);
1689                                         }
1690                                         
1691                                         i = 0;
1692                                         while(in_or_out(ibuf, x + dirs[dir][0], y + dirs[dir][1]) == in) {
1693                                                 dir = (dir + 1) & 0x7;
1694                                                 if (i++ == 9) break;
1695                                         }
1696                                         
1697                                         if (i >= 8) {
1698                                                 /* this has to be a loose point */
1699                                                 break;
1700                                         }
1701                                         
1702                                         x += dirs[dir][0];
1703                                         y += dirs[dir][1];
1704                                         dir = (dir - 3) & 0x7;
1705                                 } while(x != startx || y != starty);
1706                                 
1707                                 if (i >= 8) {
1708                                         /* patch for loose points */
1709                                         MEM_freeN(samp);
1710                                 } else {
1711                                         count = count - 1;
1712                                         samp[0].x = count >> 16;
1713                                         samp[0].y = count;
1714                                         return(samp);
1715                                 }
1716                         }
1717                 }
1718         }
1719         /* printf("no transition \n"); */
1720         return(0);
1721 }
1722
1723
1724
1725 /*******************************/
1726 /*****      WIREFRAME      *****/
1727 /*******************************/
1728
1729
1730 static float DistToLine2D(short *v1, short *v2, short *v3)   /* using Hesse formula :NO LINE PIECE! */
1731 {
1732         float a[2],deler;
1733
1734         a[0] = v2[1]-v3[1];
1735         a[1] = v3[0]-v2[0];
1736         deler = sqrt(a[0]*a[0]+a[1]*a[1]);
1737         if(deler == 0.0) return 0;
1738
1739         return fabs((v1[0]-v2[0])*a[0]+(v1[1]-v2[1])*a[1])/deler;
1740
1741 }
1742
1743 static float ComputeMaxShpError(Sample *samp, int first, int last, int *splitPoint)
1744     /* samp:  Array of digitized points */
1745     /* first, last:  Indices defining region    */
1746     /* splitpoint:  Point of maximum error      */
1747 {
1748     int         i;
1749     float       maxDist;                                /*  Maximum error               */
1750     float       dist;                                   /*  Current error               */
1751  
1752     *splitPoint = (last - first + 1) / 2;
1753     maxDist = 0.0;
1754         
1755     for (i = first + 1; i < last; i++) {                                
1756                 dist = DistToLine2D((short *)(samp+i), (short *)(samp+first), (short *)(samp+last));
1757
1758                 if (dist >= maxDist) {
1759                 maxDist = dist;
1760                 *splitPoint = i;
1761                 }
1762     }
1763
1764     return (maxDist);
1765 }
1766
1767
1768 static void FitPoly(Sample *samp, int first, int last, float shperr, ListBase *seglist)
1769     /* Samp: Array of digitized points */
1770     /* first,last: Indices of first and last pts in region */
1771     /* spherr: User-defined error squared          */
1772 {
1773     Segment     * seg;                          /* Control points segment*/
1774     float       maxError;                       /*  Maximum fitting error        */
1775     int         splitPoint;                     /*  Point to split point set at  */
1776     int         nPts;                           /*  Number of points in subset  */
1777         
1778     nPts = last - first + 1;
1779
1780     /*  Use heuristic if region only has two points in it */
1781
1782         seg = MEM_mallocN(sizeof(Segment), "wure_segment");
1783
1784         seg->co[0] = samp[first].x;
1785         seg->co[1] = samp[first].y;
1786         
1787     if (nPts == 2) {
1788                 BLI_addtail(seglist, seg);
1789                 return;
1790     }
1791
1792         maxError = ComputeMaxShpError(samp, first, last, &splitPoint);
1793         if (maxError < shperr) {
1794                 BLI_addtail(seglist, seg);
1795                 return;
1796         }
1797         
1798     /* Fitting failed -- split at max error point and fit recursively */
1799         
1800     FitPoly(samp, first, splitPoint, shperr, seglist);
1801     FitPoly(samp, splitPoint, last, shperr, seglist);
1802         
1803         MEM_freeN(seg);
1804 }
1805
1806
1807 static void ibuf2wire(ListBase * wireframe, struct ImBuf * ibuf)
1808 {
1809         int count;
1810         Sample * samp;
1811         
1812         /* first make a list of samples */
1813         
1814         samp = outline(ibuf, 0);
1815         if (samp == 0) return;
1816         
1817         count = (samp[0].x << 16) + samp[0].y;
1818         if (count) FitPoly(samp, 1, count, 1.0, wireframe); /* was 3.0. Frank */
1819
1820         MEM_freeN(samp);
1821 }
1822
1823
1824
1825 void imagestodisplist(void)
1826 {
1827         Base *base;
1828         Object *ob;
1829         Material *ma;
1830         Tex *tex;
1831         Mesh *me;
1832         ListBase _wireframe, *wireframe;
1833         DispList *dl;
1834         Segment *seg;
1835         float *data, xfac, yfac, xsi, ysi, vec[3], dum;
1836         int tot;
1837         
1838         _wireframe.first= 0;
1839         _wireframe.last= 0;
1840         wireframe = &_wireframe;
1841         
1842         init_render_textures();
1843         
1844         base= G.scene->base.first;
1845         while(base) {
1846                 if(( (base->flag & SELECT) && (base->lay & G.scene->lay) ) ) {
1847                         if( base->object->type==OB_MESH) {
1848                                 ob= base->object;
1849                                 me= ob->data;
1850                                 
1851                                 ma= give_current_material(ob, 1);
1852         
1853                                 if(ma && ma->mtex[0] && ma->mtex[0]->tex) {
1854                                         tex= ma->mtex[0]->tex;
1855                                         
1856                                         /* this takes care of correct loading of new imbufs */
1857                                         externtex(ma->mtex[0], vec, &dum, &dum, &dum, &dum, &dum);
1858                                         
1859                                         if(tex->type==TEX_IMAGE && tex->ima && tex->ima->ibuf) {                                
1860                                                 
1861                                                 ob->dtx |= OB_DRAWIMAGE;
1862                                                 
1863                                                 ibuf2wire(wireframe, tex->ima->ibuf);
1864
1865                                                 tot= 0;
1866                                                 seg = wireframe->first;
1867                                                 while (seg) {
1868                                                         tot++;
1869                                                         seg = seg->next;
1870                                                 }
1871         
1872                                                 if(tot) {
1873                                                         float size[3];
1874
1875                                                         freedisplist(&(ob->disp));
1876
1877                                                         dl= MEM_callocN(sizeof(DispList), "makeDispListimage");
1878                                                         dl->verts= MEM_callocN(3*sizeof(float)*tot, "dlverts");
1879                                                         
1880                                                         BLI_addtail(&(ob->disp), dl);
1881                                                         dl->type= DL_POLY;
1882                                                         dl->parts= 1;
1883                                                         dl->nr= tot;
1884                                                         
1885                                                         xsi= 0.5*(tex->ima->ibuf->x);
1886                                                         ysi= 0.5*(tex->ima->ibuf->y);
1887
1888                                                         mesh_get_texspace(me, NULL, NULL, size);
1889                                                         xfac= size[0]/xsi;
1890                                                         yfac= size[1]/ysi;
1891                                                                                                 
1892                                                         data= dl->verts;
1893                                                         seg = wireframe->first;
1894                                                         while (seg) {
1895                                                                 data[0]= xfac*(seg->co[0]-xsi);
1896                                                                 data[1]= yfac*(seg->co[1]-ysi);
1897                                                                 data+= 3;
1898                                                                 seg = seg->next;
1899                                                         }
1900                                                         BLI_freelistN(wireframe);
1901                                                 }
1902                                         }
1903                                 }
1904                         }
1905                 }
1906                 base= base->next;
1907         }
1908         
1909         end_render_textures();
1910         
1911         allqueue(REDRAWVIEW3D, 0);
1912 }
1913
1914 static void boundbox_displist(Object *ob)
1915 {
1916         BoundBox *bb=0;
1917         float min[3], max[3];
1918         DispList *dl;
1919         float *vert;
1920         int a, tot=0;
1921         
1922         INIT_MINMAX(min, max);
1923
1924         if(ELEM3(ob->type, OB_CURVE, OB_SURF, OB_FONT)) {
1925                 Curve *cu= ob->data;
1926
1927                 if(cu->bb==0) cu->bb= MEM_callocN(sizeof(BoundBox), "boundbox");        
1928                 bb= cu->bb;
1929                 
1930                 dl= cu->disp.first;
1931
1932                 while (dl) {
1933                         if(dl->type==DL_INDEX3) tot= dl->nr;
1934                         else tot= dl->nr*dl->parts;
1935                         
1936                         vert= dl->verts;
1937                         for(a=0; a<tot; a++, vert+=3) {
1938                                 DO_MINMAX(vert, min, max);
1939                         }
1940
1941                         dl= dl->next;
1942                 }
1943         }
1944         
1945         if(bb) {
1946                 boundbox_set_from_min_max(bb, min, max);
1947         }
1948 }
1949