svn merge -r 13177:13240 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender-staging.git] / source / blender / render / intern / source / renderdatabase.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. 
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * Contributor(s): 2004-2006, Blender Foundation, full recode
24  *
25  * ***** END GPL/BL DUAL LICENSE BLOCK *****
26  */
27
28 /*
29  * Storage, retrieval and query of render specific data.
30  *
31  * All data from a Blender scene is converted by the renderconverter/
32  * into a special format that is used by the render module to make
33  * images out of. These functions interface to the render-specific
34  * database.  
35  *
36  * The blo{ha/ve/vl} arrays store pointers to blocks of 256 data
37  * entries each.
38  *
39  * The index of an entry is >>8 (the highest 24 * bits), to find an
40  * offset in a 256-entry block.
41  *
42  * - If the 256-entry block entry has an entry in the
43  * vertnodes/vlaknodes/bloha array of the current block, the i-th entry in
44  * that block is allocated to this entry.
45  *
46  * - If the entry has no block allocated for it yet, memory is
47  * allocated.
48  *
49  * The pointer to the correct entry is returned. Memory is guarateed
50  * to exist (as long as the malloc does not break). Since guarded
51  * allocation is used, memory _must_ be available. Otherwise, an
52  * exit(0) would occur.
53  * 
54  */
55
56 #include <limits.h>
57 #include <math.h>
58 #include <string.h>
59
60 #include "MEM_guardedalloc.h"
61 #include "BKE_utildefines.h"
62
63 #include "BLI_arithb.h"
64 #include "BLI_blenlib.h"
65 #include "BLI_ghash.h"
66 #include "BLI_memarena.h"
67
68 #include "DNA_material_types.h" 
69 #include "DNA_mesh_types.h" 
70 #include "DNA_meshdata_types.h" 
71 #include "DNA_texture_types.h" 
72
73 #include "BKE_customdata.h"
74 #include "BKE_texture.h" 
75 #include "BKE_DerivedMesh.h"
76
77 #include "RE_render_ext.h"      /* externtex */
78
79 #include "renderpipeline.h"
80 #include "render_types.h"
81 #include "renderdatabase.h"
82 #include "texture.h"
83 #include "strand.h"
84 #include "zbuf.h"
85
86 /* ------------------------------------------------------------------------- */
87
88 /* More dynamic allocation of options for render vertices and faces, so we dont
89    have to reserve this space inside vertices.
90    Important; vertices and faces, should have been created already (to get tables
91    checked) that's a reason why the calls demand VertRen/VlakRen * as arg, not
92    the index */
93
94 /* NOTE! the hardcoded table size 256 is used still in code for going quickly over vertices/faces */
95
96 #define RE_STICKY_ELEMS         2
97 #define RE_STRESS_ELEMS         1
98 #define RE_RAD_ELEMS            4
99 #define RE_STRAND_ELEMS         1
100 #define RE_TANGENT_ELEMS        3
101 #define RE_STRESS_ELEMS         1
102 #define RE_WINSPEED_ELEMS       4
103 #define RE_MTFACE_ELEMS         1
104 #define RE_MCOL_ELEMS           4
105 #define RE_UV_ELEMS                     2
106 #define RE_SURFNOR_ELEMS        3
107 #define RE_SIMPLIFY_ELEMS       2
108
109 float *RE_vertren_get_sticky(ObjectRen *obr, VertRen *ver, int verify)
110 {
111         float *sticky;
112         int nr= ver->index>>8;
113         
114         sticky= obr->vertnodes[nr].sticky;
115         if(sticky==NULL) {
116                 if(verify) 
117                         sticky= obr->vertnodes[nr].sticky= MEM_mallocN(256*RE_STICKY_ELEMS*sizeof(float), "sticky table");
118                 else
119                         return NULL;
120         }
121         return sticky + (ver->index & 255)*RE_STICKY_ELEMS;
122 }
123
124 float *RE_vertren_get_stress(ObjectRen *obr, VertRen *ver, int verify)
125 {
126         float *stress;
127         int nr= ver->index>>8;
128         
129         stress= obr->vertnodes[nr].stress;
130         if(stress==NULL) {
131                 if(verify) 
132                         stress= obr->vertnodes[nr].stress= MEM_mallocN(256*RE_STRESS_ELEMS*sizeof(float), "stress table");
133                 else
134                         return NULL;
135         }
136         return stress + (ver->index & 255)*RE_STRESS_ELEMS;
137 }
138
139 /* this one callocs! */
140 float *RE_vertren_get_rad(ObjectRen *obr, VertRen *ver, int verify)
141 {
142         float *rad;
143         int nr= ver->index>>8;
144         
145         rad= obr->vertnodes[nr].rad;
146         if(rad==NULL) {
147                 if(verify) 
148                         rad= obr->vertnodes[nr].rad= MEM_callocN(256*RE_RAD_ELEMS*sizeof(float), "rad table");
149                 else
150                         return NULL;
151         }
152         return rad + (ver->index & 255)*RE_RAD_ELEMS;
153 }
154
155 float *RE_vertren_get_strand(ObjectRen *obr, VertRen *ver, int verify)
156 {
157         float *strand;
158         int nr= ver->index>>8;
159         
160         strand= obr->vertnodes[nr].strand;
161         if(strand==NULL) {
162                 if(verify) 
163                         strand= obr->vertnodes[nr].strand= MEM_mallocN(256*RE_STRAND_ELEMS*sizeof(float), "strand table");
164                 else
165                         return NULL;
166         }
167         return strand + (ver->index & 255)*RE_STRAND_ELEMS;
168 }
169
170 /* needs calloc */
171 float *RE_vertren_get_tangent(ObjectRen *obr, VertRen *ver, int verify)
172 {
173         float *tangent;
174         int nr= ver->index>>8;
175         
176         tangent= obr->vertnodes[nr].tangent;
177         if(tangent==NULL) {
178                 if(verify) 
179                         tangent= obr->vertnodes[nr].tangent= MEM_callocN(256*RE_TANGENT_ELEMS*sizeof(float), "tangent table");
180                 else
181                         return NULL;
182         }
183         return tangent + (ver->index & 255)*RE_TANGENT_ELEMS;
184 }
185
186 /* needs calloc! not all renderverts have them */
187 /* also winspeed is exception, it is stored per instance */
188 float *RE_vertren_get_winspeed(ObjectInstanceRen *obi, VertRen *ver, int verify)
189 {
190         float *winspeed;
191         int totvector;
192         
193         winspeed= obi->vectors;
194         if(winspeed==NULL) {
195                 if(verify) {
196                         totvector= obi->obr->totvert + obi->obr->totstrand;
197                         winspeed= obi->vectors= MEM_callocN(totvector*RE_WINSPEED_ELEMS*sizeof(float), "winspeed table");
198                 }
199                 else
200                         return NULL;
201         }
202         return winspeed + ver->index*RE_WINSPEED_ELEMS;
203 }
204
205 VertRen *RE_vertren_copy(ObjectRen *obr, VertRen *ver)
206 {
207         VertRen *v1= RE_findOrAddVert(obr, obr->totvert++);
208         float *fp1, *fp2;
209         int index= v1->index;
210         
211         *v1= *ver;
212         v1->index= index;
213         
214         fp1= RE_vertren_get_sticky(obr, ver, 0);
215         if(fp1) {
216                 fp2= RE_vertren_get_sticky(obr, v1, 1);
217                 memcpy(fp2, fp1, RE_STICKY_ELEMS*sizeof(float));
218         }
219         fp1= RE_vertren_get_stress(obr, ver, 0);
220         if(fp1) {
221                 fp2= RE_vertren_get_stress(obr, v1, 1);
222                 memcpy(fp2, fp1, RE_STRESS_ELEMS*sizeof(float));
223         }
224         fp1= RE_vertren_get_rad(obr, ver, 0);
225         if(fp1) {
226                 fp2= RE_vertren_get_rad(obr, v1, 1);
227                 memcpy(fp2, fp1, RE_RAD_ELEMS*sizeof(float));
228         }
229         fp1= RE_vertren_get_strand(obr, ver, 0);
230         if(fp1) {
231                 fp2= RE_vertren_get_strand(obr, v1, 1);
232                 memcpy(fp2, fp1, RE_STRAND_ELEMS*sizeof(float));
233         }
234         fp1= RE_vertren_get_tangent(obr, ver, 0);
235         if(fp1) {
236                 fp2= RE_vertren_get_tangent(obr, v1, 1);
237                 memcpy(fp2, fp1, RE_TANGENT_ELEMS*sizeof(float));
238         }
239         return v1;
240 }
241
242 VertRen *RE_findOrAddVert(ObjectRen *obr, int nr)
243 {
244         VertTableNode *temp;
245         VertRen *v;
246         int a;
247
248         if(nr<0) {
249                 printf("error in findOrAddVert: %d\n",nr);
250                 return NULL;
251         }
252         a= nr>>8;
253         
254         if (a>=obr->vertnodeslen-1) {  /* Need to allocate more columns..., and keep last element NULL for free loop */
255                 temp= obr->vertnodes;
256                 
257                 obr->vertnodes= MEM_mallocN(sizeof(VertTableNode)*(obr->vertnodeslen+TABLEINITSIZE) , "vertnodes");
258                 if(temp) memcpy(obr->vertnodes, temp, obr->vertnodeslen*sizeof(VertTableNode));
259                 memset(obr->vertnodes+obr->vertnodeslen, 0, TABLEINITSIZE*sizeof(VertTableNode));
260                 
261                 obr->vertnodeslen+=TABLEINITSIZE; 
262                 if(temp) MEM_freeN(temp);       
263         }
264         
265         v= obr->vertnodes[a].vert;
266         if(v==NULL) {
267                 int i;
268                 
269                 v= (VertRen *)MEM_callocN(256*sizeof(VertRen),"findOrAddVert");
270                 obr->vertnodes[a].vert= v;
271                 
272                 for(i= (nr & 0xFFFFFF00), a=0; a<256; a++, i++) {
273                         v[a].index= i;
274                 }
275         }
276         v+= (nr & 255);
277         return v;
278 }
279
280 /* ------------------------------------------------------------------------ */
281
282 MTFace *RE_vlakren_get_tface(ObjectRen *obr, VlakRen *vlr, int n, char **name, int verify)
283 {
284         VlakTableNode *node;
285         int nr= vlr->index>>8, vlakindex= (vlr->index&255);
286         int index= (n<<8) + vlakindex;
287
288         node= &obr->vlaknodes[nr];
289
290         if(verify) {
291                 if(n>=node->totmtface) {
292                         MTFace *mtface= node->mtface;
293                         int size= size= (n+1)*256;
294
295                         node->mtface= MEM_callocN(size*sizeof(MTFace), "Vlak mtface");
296
297                         if(mtface) {
298                                 size= node->totmtface*256;
299                                 memcpy(node->mtface, mtface, size*sizeof(MTFace));
300                                 MEM_freeN(mtface);
301                         }
302
303                         node->totmtface= n+1;
304                 }
305         }
306         else {
307                 if(n>=node->totmtface)
308                         return NULL;
309
310                 if(name) *name= obr->mtface[n];
311         }
312
313         return node->mtface + index;
314 }
315
316 MCol *RE_vlakren_get_mcol(ObjectRen *obr, VlakRen *vlr, int n, char **name, int verify)
317 {
318         VlakTableNode *node;
319         int nr= vlr->index>>8, vlakindex= (vlr->index&255);
320         int index= (n<<8) + vlakindex;
321
322         node= &obr->vlaknodes[nr];
323
324         if(verify) {
325                 if(n>=node->totmcol) {
326                         MCol *mcol= node->mcol;
327                         int size= (n+1)*256;
328
329                         node->mcol= MEM_callocN(size*sizeof(MCol)*RE_MCOL_ELEMS, "Vlak mcol");
330
331                         if(mcol) {
332                                 size= node->totmcol*256;
333                                 memcpy(node->mcol, mcol, size*sizeof(MCol)*RE_MCOL_ELEMS);
334                                 MEM_freeN(mcol);
335                         }
336
337                         node->totmcol= n+1;
338                 }
339         }
340         else {
341                 if(n>=node->totmcol)
342                         return NULL;
343
344                 if(name) *name= obr->mcol[n];
345         }
346
347         return node->mcol + index*RE_MCOL_ELEMS;
348 }
349
350 float *RE_vlakren_get_surfnor(ObjectRen *obr, VlakRen *vlak, int verify)
351 {
352         float *surfnor;
353         int nr= vlak->index>>8;
354         
355         surfnor= obr->vlaknodes[nr].surfnor;
356         if(surfnor==NULL) {
357                 if(verify) 
358                         surfnor= obr->vlaknodes[nr].surfnor= MEM_callocN(256*RE_SURFNOR_ELEMS*sizeof(float), "surfnor table");
359                 else
360                         return NULL;
361         }
362         return surfnor + (vlak->index & 255)*RE_SURFNOR_ELEMS;
363 }
364
365 VlakRen *RE_vlakren_copy(ObjectRen *obr, VlakRen *vlr)
366 {
367         VlakRen *vlr1 = RE_findOrAddVlak(obr, obr->totvlak++);
368         MTFace *mtface, *mtface1;
369         MCol *mcol, *mcol1;
370         float *surfnor, *surfnor1;
371         int i, index = vlr1->index;
372         char *name;
373
374         *vlr1= *vlr;
375         vlr1->index= index;
376
377         for (i=0; (mtface=RE_vlakren_get_tface(obr, vlr, i, &name, 0)) != NULL; i++) {
378                 mtface1= RE_vlakren_get_tface(obr, vlr1, i, &name, 1);
379                 memcpy(mtface1, mtface, sizeof(MTFace)*RE_MTFACE_ELEMS);
380         }
381
382         for (i=0; (mcol=RE_vlakren_get_mcol(obr, vlr, i, &name, 0)) != NULL; i++) {
383                 mcol1= RE_vlakren_get_mcol(obr, vlr1, i, &name, 1);
384                 memcpy(mcol1, mcol, sizeof(MCol)*RE_MCOL_ELEMS);
385         }
386
387         surfnor= RE_vlakren_get_surfnor(obr, vlr, 0);
388         if(surfnor) {
389                 surfnor1= RE_vlakren_get_surfnor(obr, vlr1, 1);
390                 VECCOPY(surfnor1, surfnor);
391         }
392
393         return vlr1;
394 }
395
396 int RE_vlakren_get_normal(Render *re, ObjectInstanceRen *obi, VlakRen *vlr, float *nor)
397 {
398         float xn, yn, zn, v1[3];
399         float (*imat)[3]= obi->imat;
400         int flipped= 0;
401
402         if(obi->flag & R_TRANSFORMED) {
403                 xn= vlr->n[0];
404                 yn= vlr->n[1];
405                 zn= vlr->n[2];
406                 
407                 /* transpose! */
408                 nor[0]= imat[0][0]*xn+imat[0][1]*yn+imat[0][2]*zn;
409                 nor[1]= imat[1][0]*xn+imat[1][1]*yn+imat[1][2]*zn;
410                 nor[2]= imat[2][0]*xn+imat[2][1]*yn+imat[2][2]*zn;
411         }
412         else
413                 VECCOPY(nor, vlr->n);
414
415         if((vlr->flag & R_NOPUNOFLIP)==0) {
416                 if(re->r.mode & R_ORTHO) {
417                         if(nor[2] > 0.0f)
418                                 flipped= 1;
419                 }
420                 else {
421                         VECCOPY(v1, vlr->v1->co);
422                         if(obi->flag & R_TRANSFORMED)
423                                 Mat4MulVecfl(obi->mat, v1);
424                         if(INPR(v1, nor) < 0.0f) {
425                                 flipped= 1;
426                         }
427                 }
428
429                 if(flipped) {
430                         nor[0]= -nor[0];
431                         nor[1]= -nor[1];
432                         nor[2]= -nor[2];
433                 }
434         }
435
436         return flipped;
437 }
438
439 void RE_set_customdata_names(ObjectRen *obr, CustomData *data)
440 {
441         /* CustomData layer names are stored per object here, because the
442            DerivedMesh which stores the layers is freed */
443         
444         CustomDataLayer *layer;
445         int numlayers, i, mtfn, mcn;
446
447         if (CustomData_has_layer(data, CD_MTFACE)) {
448                 numlayers= CustomData_number_of_layers(data, CD_MTFACE);
449                 obr->mtface= MEM_callocN(sizeof(*obr->mtface)*numlayers, "mtfacenames");
450         }
451
452         if (CustomData_has_layer(data, CD_MCOL)) {
453                 numlayers= CustomData_number_of_layers(data, CD_MCOL);
454                 obr->mcol= MEM_callocN(sizeof(*obr->mcol)*numlayers, "mcolnames");
455         }
456
457         for (i=0, mtfn=0, mcn=0; i < data->totlayer; i++) {
458                 layer= &data->layers[i];
459
460                 if (layer->type == CD_MTFACE) {
461                         strcpy(obr->mtface[mtfn++], layer->name);
462                         obr->actmtface= layer->active_rnd;
463                 }
464                 else if (layer->type == CD_MCOL) {
465                         strcpy(obr->mcol[mcn++], layer->name);
466                         obr->actmcol= layer->active_rnd;
467                 }
468         }
469 }
470
471 VlakRen *RE_findOrAddVlak(ObjectRen *obr, int nr)
472 {
473         VlakTableNode *temp;
474         VlakRen *v;
475         int a;
476
477         if(nr<0) {
478                 printf("error in findOrAddVlak: %d\n",nr);
479                 return obr->vlaknodes[0].vlak;
480         }
481         a= nr>>8;
482         
483         if (a>=obr->vlaknodeslen-1){  /* Need to allocate more columns..., and keep last element NULL for free loop */
484                 temp= obr->vlaknodes;
485                 
486                 obr->vlaknodes= MEM_mallocN(sizeof(VlakTableNode)*(obr->vlaknodeslen+TABLEINITSIZE) , "vlaknodes");
487                 if(temp) memcpy(obr->vlaknodes, temp, obr->vlaknodeslen*sizeof(VlakTableNode));
488                 memset(obr->vlaknodes+obr->vlaknodeslen, 0, TABLEINITSIZE*sizeof(VlakTableNode));
489
490                 obr->vlaknodeslen+=TABLEINITSIZE;  /*Does this really need to be power of 2?*/
491                 if(temp) MEM_freeN(temp);       
492         }
493
494         v= obr->vlaknodes[a].vlak;
495         
496         if(v==NULL) {
497                 int i;
498
499                 v= (VlakRen *)MEM_callocN(256*sizeof(VlakRen),"findOrAddVlak");
500                 obr->vlaknodes[a].vlak= v;
501
502                 for(i= (nr & 0xFFFFFF00), a=0; a<256; a++, i++)
503                         v[a].index= i;
504         }
505         v+= (nr & 255);
506         return v;
507 }
508
509 /* ------------------------------------------------------------------------ */
510
511 float *RE_strandren_get_surfnor(ObjectRen *obr, StrandRen *strand, int verify)
512 {
513         float *surfnor;
514         int nr= strand->index>>8;
515         
516         surfnor= obr->strandnodes[nr].surfnor;
517         if(surfnor==NULL) {
518                 if(verify) 
519                         surfnor= obr->strandnodes[nr].surfnor= MEM_callocN(256*RE_SURFNOR_ELEMS*sizeof(float), "surfnor table");
520                 else
521                         return NULL;
522         }
523         return surfnor + (strand->index & 255)*RE_SURFNOR_ELEMS;
524 }
525
526 float *RE_strandren_get_uv(ObjectRen *obr, StrandRen *strand, int n, char **name, int verify)
527 {
528         StrandTableNode *node;
529         int nr= strand->index>>8, strandindex= (strand->index&255);
530         int index= (n<<8) + strandindex;
531
532         node= &obr->strandnodes[nr];
533
534         if(verify) {
535                 if(n>=node->totuv) {
536                         float *uv= node->uv;
537                         int size= (n+1)*256;
538
539                         node->uv= MEM_callocN(size*sizeof(float)*RE_UV_ELEMS, "Strand uv");
540
541                         if(uv) {
542                                 size= node->totuv*256;
543                                 memcpy(node->uv, uv, size*sizeof(float)*RE_UV_ELEMS);
544                                 MEM_freeN(uv);
545                         }
546
547                         node->totuv= n+1;
548                 }
549         }
550         else {
551                 if(n>=node->totuv)
552                         return NULL;
553
554                 if(name) *name= obr->mtface[n];
555         }
556
557         return node->uv + index*RE_UV_ELEMS;
558 }
559
560 MCol *RE_strandren_get_mcol(ObjectRen *obr, StrandRen *strand, int n, char **name, int verify)
561 {
562         StrandTableNode *node;
563         int nr= strand->index>>8, strandindex= (strand->index&255);
564         int index= (n<<8) + strandindex;
565
566         node= &obr->strandnodes[nr];
567
568         if(verify) {
569                 if(n>=node->totmcol) {
570                         MCol *mcol= node->mcol;
571                         int size= (n+1)*256;
572
573                         node->mcol= MEM_callocN(size*sizeof(MCol)*RE_MCOL_ELEMS, "Strand mcol");
574
575                         if(mcol) {
576                                 size= node->totmcol*256;
577                                 memcpy(node->mcol, mcol, size*sizeof(MCol)*RE_MCOL_ELEMS);
578                                 MEM_freeN(mcol);
579                         }
580
581                         node->totmcol= n+1;
582                 }
583         }
584         else {
585                 if(n>=node->totmcol)
586                         return NULL;
587
588                 if(name) *name= obr->mcol[n];
589         }
590
591         return node->mcol + index*RE_MCOL_ELEMS;
592 }
593
594 float *RE_strandren_get_simplify(struct ObjectRen *obr, struct StrandRen *strand, int verify)
595 {
596         float *simplify;
597         int nr= strand->index>>8;
598         
599         simplify= obr->strandnodes[nr].simplify;
600         if(simplify==NULL) {
601                 if(verify) 
602                         simplify= obr->strandnodes[nr].simplify= MEM_callocN(256*RE_SIMPLIFY_ELEMS*sizeof(float), "simplify table");
603                 else
604                         return NULL;
605         }
606         return simplify + (strand->index & 255)*RE_SIMPLIFY_ELEMS;
607 }
608
609 /* winspeed is exception, it is stored per instance */
610 float *RE_strandren_get_winspeed(ObjectInstanceRen *obi, StrandRen *strand, int verify)
611 {
612         float *winspeed;
613         int totvector;
614         
615         winspeed= obi->vectors;
616         if(winspeed==NULL) {
617                 if(verify) {
618                         totvector= obi->obr->totvert + obi->obr->totstrand;
619                         winspeed= obi->vectors= MEM_callocN(totvector*RE_WINSPEED_ELEMS*sizeof(float), "winspeed table");
620                 }
621                 else
622                         return NULL;
623         }
624         return winspeed + (obi->obr->totvert + strand->index)*RE_WINSPEED_ELEMS;
625 }
626
627 StrandRen *RE_findOrAddStrand(ObjectRen *obr, int nr)
628 {
629         StrandTableNode *temp;
630         StrandRen *v;
631         int a;
632
633         if(nr<0) {
634                 printf("error in findOrAddStrand: %d\n",nr);
635                 return obr->strandnodes[0].strand;
636         }
637         a= nr>>8;
638         
639         if (a>=obr->strandnodeslen-1){  /* Need to allocate more columns..., and keep last element NULL for free loop */
640                 temp= obr->strandnodes;
641                 
642                 obr->strandnodes= MEM_mallocN(sizeof(StrandTableNode)*(obr->strandnodeslen+TABLEINITSIZE) , "strandnodes");
643                 if(temp) memcpy(obr->strandnodes, temp, obr->strandnodeslen*sizeof(StrandTableNode));
644                 memset(obr->strandnodes+obr->strandnodeslen, 0, TABLEINITSIZE*sizeof(StrandTableNode));
645
646                 obr->strandnodeslen+=TABLEINITSIZE;  /*Does this really need to be power of 2?*/
647                 if(temp) MEM_freeN(temp);       
648         }
649
650         v= obr->strandnodes[a].strand;
651         
652         if(v==NULL) {
653                 int i;
654
655                 v= (StrandRen *)MEM_callocN(256*sizeof(StrandRen),"findOrAddStrand");
656                 obr->strandnodes[a].strand= v;
657
658                 for(i= (nr & 0xFFFFFF00), a=0; a<256; a++, i++)
659                         v[a].index= i;
660         }
661         v+= (nr & 255);
662         return v;
663 }
664
665 StrandBuffer *RE_addStrandBuffer(ObjectRen *obr, int totvert)
666 {
667         StrandBuffer *strandbuf;
668
669         strandbuf= MEM_callocN(sizeof(StrandBuffer), "StrandBuffer");
670         strandbuf->vert= MEM_callocN(sizeof(StrandVert)*totvert, "StrandVert");
671         strandbuf->totvert= totvert;
672         strandbuf->obr= obr;
673
674         BLI_addtail(&obr->strandbufs, strandbuf);
675
676         return strandbuf;
677 }
678
679 /* ------------------------------------------------------------------------ */
680
681 ObjectRen *RE_addRenderObject(Render *re, Object *ob, Object *par, int index, int psysindex)
682 {
683         ObjectRen *obr= MEM_callocN(sizeof(ObjectRen), "object render struct");
684         
685         BLI_addtail(&re->objecttable, obr);
686         obr->ob= ob;
687         obr->par= par;
688         obr->index= index;
689         obr->psysindex= psysindex;
690
691         return obr;
692 }
693
694 void free_renderdata_vertnodes(VertTableNode *vertnodes)
695 {
696         int a;
697         
698         if(vertnodes==NULL) return;
699         
700         for(a=0; vertnodes[a].vert; a++) {
701                 MEM_freeN(vertnodes[a].vert);
702                 
703                 if(vertnodes[a].rad)
704                         MEM_freeN(vertnodes[a].rad);
705                 if(vertnodes[a].sticky)
706                         MEM_freeN(vertnodes[a].sticky);
707                 if(vertnodes[a].strand)
708                         MEM_freeN(vertnodes[a].strand);
709                 if(vertnodes[a].tangent)
710                         MEM_freeN(vertnodes[a].tangent);
711                 if(vertnodes[a].stress)
712                         MEM_freeN(vertnodes[a].stress);
713                 if(vertnodes[a].winspeed)
714                         MEM_freeN(vertnodes[a].winspeed);
715         }
716         
717         MEM_freeN(vertnodes);
718 }
719
720 void free_renderdata_vlaknodes(VlakTableNode *vlaknodes)
721 {
722         int a;
723         
724         if(vlaknodes==NULL) return;
725         
726         for(a=0; vlaknodes[a].vlak; a++) {
727                 MEM_freeN(vlaknodes[a].vlak);
728                 
729                 if(vlaknodes[a].mtface)
730                         MEM_freeN(vlaknodes[a].mtface);
731                 if(vlaknodes[a].mcol)
732                         MEM_freeN(vlaknodes[a].mcol);
733                 if(vlaknodes[a].surfnor)
734                         MEM_freeN(vlaknodes[a].surfnor);
735         }
736         
737         MEM_freeN(vlaknodes);
738 }
739
740 void free_renderdata_strandnodes(StrandTableNode *strandnodes)
741 {
742         int a;
743         
744         if(strandnodes==NULL) return;
745         
746         for(a=0; strandnodes[a].strand; a++) {
747                 MEM_freeN(strandnodes[a].strand);
748                 
749                 if(strandnodes[a].uv)
750                         MEM_freeN(strandnodes[a].uv);
751                 if(strandnodes[a].mcol)
752                         MEM_freeN(strandnodes[a].mcol);
753                 if(strandnodes[a].winspeed)
754                         MEM_freeN(strandnodes[a].winspeed);
755                 if(strandnodes[a].surfnor)
756                         MEM_freeN(strandnodes[a].surfnor);
757                 if(strandnodes[a].simplify)
758                         MEM_freeN(strandnodes[a].simplify);
759         }
760         
761         MEM_freeN(strandnodes);
762 }
763
764 void free_renderdata_tables(Render *re)
765 {
766         ObjectInstanceRen *obi;
767         ObjectRen *obr;
768         StrandBuffer *strandbuf;
769         int a=0;
770         
771         for(obr=re->objecttable.first; obr; obr=obr->next) {
772                 if(obr->vertnodes) {
773                         free_renderdata_vertnodes(obr->vertnodes);
774                         obr->vertnodes= NULL;
775                         obr->vertnodeslen= 0;
776                 }
777
778                 if(obr->vlaknodes) {
779                         free_renderdata_vlaknodes(obr->vlaknodes);
780                         obr->vlaknodes= NULL;
781                         obr->vlaknodeslen= 0;
782                         obr->totvlak= 0;
783                 }
784
785                 if(obr->bloha) {
786                         for(a=0; obr->bloha[a]; a++)
787                                 MEM_freeN(obr->bloha[a]);
788
789                         MEM_freeN(obr->bloha);
790                         obr->bloha= NULL;
791                         obr->blohalen= 0;
792                 }
793
794                 if(obr->strandnodes) {
795                         free_renderdata_strandnodes(obr->strandnodes);
796                         obr->strandnodes= NULL;
797                         obr->strandnodeslen= 0;
798                 }
799
800                 for(strandbuf=obr->strandbufs.first; strandbuf; strandbuf=strandbuf->next)
801                         if(strandbuf->vert) MEM_freeN(strandbuf->vert);
802                 BLI_freelistN(&obr->strandbufs);
803
804                 if(obr->mtface)
805                         MEM_freeN(obr->mtface);
806                 if(obr->mcol)
807                         MEM_freeN(obr->mcol);
808         }
809
810         if(re->objectinstance) {
811                 for(obi=re->instancetable.first; obi; obi=obi->next)
812                         if(obi->vectors)
813                                 MEM_freeN(obi->vectors);
814
815                 MEM_freeN(re->objectinstance);
816                 re->objectinstance= NULL;
817                 re->totinstance= 0;
818                 re->instancetable.first= re->instancetable.last= NULL;
819         }
820
821         if(re->sortedhalos) {
822                 MEM_freeN(re->sortedhalos);
823                 re->sortedhalos= NULL;
824         }
825
826         if(re->strandbuckets) {
827                 free_buckets(re->strandbuckets);
828                 re->strandbuckets= NULL;
829         }
830
831         BLI_freelistN(&re->customdata_names);
832         BLI_freelistN(&re->objecttable);
833         BLI_freelistN(&re->instancetable);
834 }
835
836 /* ------------------------------------------------------------------------ */
837
838 HaloRen *RE_findOrAddHalo(ObjectRen *obr, int nr)
839 {
840         HaloRen *h, **temp;
841         int a;
842
843         if(nr<0) {
844                 printf("error in findOrAddHalo: %d\n",nr);
845                 return NULL;
846         }
847         a= nr>>8;
848         
849         if (a>=obr->blohalen-1){  /* Need to allocate more columns..., and keep last element NULL for free loop */
850                 //printf("Allocating %i more halo groups.  %i total.\n", 
851                 //      TABLEINITSIZE, obr->blohalen+TABLEINITSIZE );
852                 temp=obr->bloha;
853                 
854                 obr->bloha=(HaloRen**)MEM_callocN(sizeof(void*)*(obr->blohalen+TABLEINITSIZE) , "Bloha");
855                 if(temp) memcpy(obr->bloha, temp, obr->blohalen*sizeof(void*));
856                 memset(&(obr->bloha[obr->blohalen]), 0, TABLEINITSIZE*sizeof(void*));
857                 obr->blohalen+=TABLEINITSIZE;  /*Does this really need to be power of 2?*/
858                 if(temp) MEM_freeN(temp);       
859         }
860         
861         h= obr->bloha[a];
862         if(h==NULL) {
863                 h= (HaloRen *)MEM_callocN(256*sizeof(HaloRen),"findOrAdHalo");
864                 obr->bloha[a]= h;
865         }
866         h+= (nr & 255);
867         return h;
868 }
869
870 /* ------------------------------------------------------------------------- */
871
872 HaloRen *RE_inithalo(Render *re, ObjectRen *obr, Material *ma,   float *vec,   float *vec1, 
873                                   float *orco,   float hasize,   float vectsize, int seed)
874 {
875         HaloRen *har;
876         MTex *mtex;
877         float tin, tr, tg, tb, ta;
878         float xn, yn, zn, texvec[3], hoco[4], hoco1[4];
879
880         if(hasize==0.0) return NULL;
881
882         projectverto(vec, re->winmat, hoco);
883         if(hoco[3]==0.0) return NULL;
884         if(vec1) {
885                 projectverto(vec1, re->winmat, hoco1);
886                 if(hoco1[3]==0.0) return NULL;
887         }
888
889         har= RE_findOrAddHalo(obr, obr->tothalo++);
890         VECCOPY(har->co, vec);
891         har->hasize= hasize;
892
893         /* actual projectvert is done in function project_renderdata() because of parts/border/pano */
894         /* we do it here for sorting of halos */
895         zn= hoco[3];
896         har->xs= 0.5*re->winx*(hoco[0]/zn);
897         har->ys= 0.5*re->winy*(hoco[1]/zn);
898         har->zs= 0x7FFFFF*(hoco[2]/zn);
899         
900         har->zBufDist = 0x7FFFFFFF*(hoco[2]/zn); 
901         
902         /* halovect */
903         if(vec1) {
904
905                 har->type |= HA_VECT;
906
907                 xn=  har->xs - 0.5*re->winx*(hoco1[0]/hoco1[3]);
908                 yn=  har->ys - 0.5*re->winy*(hoco1[1]/hoco1[3]);
909                 if(xn==0.0 || (xn==0.0 && yn==0.0)) zn= 0.0;
910                 else zn= atan2(yn, xn);
911
912                 har->sin= sin(zn);
913                 har->cos= cos(zn);
914                 zn= VecLenf(vec1, vec);
915
916                 har->hasize= vectsize*zn + (1.0-vectsize)*hasize;
917                 
918                 VecSubf(har->no, vec, vec1);
919                 Normalize(har->no);
920         }
921
922         if(ma->mode & MA_HALO_XALPHA) har->type |= HA_XALPHA;
923
924         har->alfa= ma->alpha;
925         har->r= ma->r;
926         har->g= ma->g;
927         har->b= ma->b;
928         har->add= (255.0*ma->add);
929         har->mat= ma;
930         har->hard= ma->har;
931         har->seed= seed % 256;
932
933         if(ma->mode & MA_STAR) har->starpoints= ma->starc;
934         if(ma->mode & MA_HALO_LINES) har->linec= ma->linec;
935         if(ma->mode & MA_HALO_RINGS) har->ringc= ma->ringc;
936         if(ma->mode & MA_HALO_FLARE) har->flarec= ma->flarec;
937
938
939         if(ma->mtex[0]) {
940
941                 if( (ma->mode & MA_HALOTEX) ) har->tex= 1;
942                 else {
943
944                         mtex= ma->mtex[0];
945                         VECCOPY(texvec, vec);
946
947                         if(mtex->texco & TEXCO_NORM) {
948                                 ;
949                         }
950                         else if(mtex->texco & TEXCO_OBJECT) {
951                                 /* texvec[0]+= imatbase->ivec[0]; */
952                                 /* texvec[1]+= imatbase->ivec[1]; */
953                                 /* texvec[2]+= imatbase->ivec[2]; */
954                                 /* Mat3MulVecfl(imatbase->imat, texvec); */
955                         }
956                         else {
957                                 if(orco) {
958                                         VECCOPY(texvec, orco);
959                                 }
960                         }
961
962                         externtex(mtex, texvec, &tin, &tr, &tg, &tb, &ta);
963
964                         yn= tin*mtex->colfac;
965                         zn= tin*mtex->varfac;
966
967                         if(mtex->mapto & MAP_COL) {
968                                 zn= 1.0-yn;
969                                 har->r= (yn*tr+ zn*ma->r);
970                                 har->g= (yn*tg+ zn*ma->g);
971                                 har->b= (yn*tb+ zn*ma->b);
972                         }
973                         if(mtex->texco & 16) {
974                                 har->alfa= tin;
975                         }
976                 }
977         }
978
979         return har;
980 }
981
982 HaloRen *RE_inithalo_particle(Render *re, ObjectRen *obr, DerivedMesh *dm, Material *ma,   float *vec,   float *vec1, 
983                                   float *orco, float *uvco, float hasize, float vectsize, int seed)
984 {
985         HaloRen *har;
986         MTex *mtex;
987         float tin, tr, tg, tb, ta;
988         float xn, yn, zn, texvec[3], hoco[4], hoco1[4], in[3],tex[3],out[3];
989         int i;
990
991         if(hasize==0.0) return NULL;
992
993         projectverto(vec, re->winmat, hoco);
994         if(hoco[3]==0.0) return NULL;
995         if(vec1) {
996                 projectverto(vec1, re->winmat, hoco1);
997                 if(hoco1[3]==0.0) return NULL;
998         }
999
1000         har= RE_findOrAddHalo(obr, obr->tothalo++);
1001         VECCOPY(har->co, vec);
1002         har->hasize= hasize;
1003
1004         /* actual projectvert is done in function project_renderdata() because of parts/border/pano */
1005         /* we do it here for sorting of halos */
1006         zn= hoco[3];
1007         har->xs= 0.5*re->winx*(hoco[0]/zn);
1008         har->ys= 0.5*re->winy*(hoco[1]/zn);
1009         har->zs= 0x7FFFFF*(hoco[2]/zn);
1010         
1011         har->zBufDist = 0x7FFFFFFF*(hoco[2]/zn); 
1012         
1013         /* halovect */
1014         if(vec1) {
1015
1016                 har->type |= HA_VECT;
1017
1018                 xn=  har->xs - 0.5*re->winx*(hoco1[0]/hoco1[3]);
1019                 yn=  har->ys - 0.5*re->winy*(hoco1[1]/hoco1[3]);
1020                 if(xn==0.0 || (xn==0.0 && yn==0.0)) zn= 0.0;
1021                 else zn= atan2(yn, xn);
1022
1023                 har->sin= sin(zn);
1024                 har->cos= cos(zn);
1025                 zn= VecLenf(vec1, vec)*0.5;
1026
1027                 har->hasize= vectsize*zn + (1.0-vectsize)*hasize;
1028                 
1029                 VecSubf(har->no, vec, vec1);
1030                 Normalize(har->no);
1031         }
1032
1033         if(ma->mode & MA_HALO_XALPHA) har->type |= HA_XALPHA;
1034
1035         har->alfa= ma->alpha;
1036         har->r= ma->r;
1037         har->g= ma->g;
1038         har->b= ma->b;
1039         har->add= (255.0*ma->add);
1040         har->mat= ma;
1041         har->hard= ma->har;
1042         har->seed= seed % 256;
1043
1044         if(ma->mode & MA_STAR) har->starpoints= ma->starc;
1045         if(ma->mode & MA_HALO_LINES) har->linec= ma->linec;
1046         if(ma->mode & MA_HALO_RINGS) har->ringc= ma->ringc;
1047         if(ma->mode & MA_HALO_FLARE) har->flarec= ma->flarec;
1048
1049         if((ma->mode & MA_HALOTEX) && ma->mtex[0]){
1050                 har->tex= 1;
1051                 i=1;
1052         }
1053         
1054         for(i=0; i<MAX_MTEX; i++)
1055                 if(ma->mtex[i] && (ma->septex & (1<<i))==0) {
1056                         mtex= ma->mtex[i];
1057                         VECCOPY(texvec, vec);
1058
1059                         if(mtex->texco & TEXCO_NORM) {
1060                                 ;
1061                         }
1062                         else if(mtex->texco & TEXCO_OBJECT) {
1063                                 if(mtex->object){
1064                                         float imat[4][4];
1065                                         /* imat should really be cached somewhere before this */
1066                                         Mat4Invert(imat,mtex->object->obmat);
1067                                         Mat4MulVecfl(imat,texvec);
1068                                 }
1069                                 /* texvec[0]+= imatbase->ivec[0]; */
1070                                 /* texvec[1]+= imatbase->ivec[1]; */
1071                                 /* texvec[2]+= imatbase->ivec[2]; */
1072                                 /* Mat3MulVecfl(imatbase->imat, texvec); */
1073                         }
1074                         else if(mtex->texco & TEXCO_GLOB){
1075                                 VECCOPY(texvec,vec);
1076                         }
1077                         else if(mtex->texco & TEXCO_UV && uvco){
1078                                 int uv_index=CustomData_get_named_layer_index(&dm->faceData,CD_MTFACE,mtex->uvname);
1079                                 if(uv_index<0)
1080                                         uv_index=CustomData_get_active_layer_index(&dm->faceData,CD_MTFACE);
1081
1082                                 uv_index-=CustomData_get_layer_index(&dm->faceData,CD_MTFACE);
1083
1084                                 texvec[0]=2.0f*uvco[2*uv_index]-1.0f;
1085                                 texvec[1]=2.0f*uvco[2*uv_index+1]-1.0f;
1086                                 texvec[2]=0.0f;
1087                         }
1088                         else if(orco) {
1089                                 VECCOPY(texvec, orco);
1090                         }
1091
1092                         externtex(mtex, texvec, &tin, &tr, &tg, &tb, &ta);
1093
1094                         //yn= tin*mtex->colfac;
1095                         //zn= tin*mtex->varfac;
1096                         if(mtex->mapto & MAP_COL) {
1097                                 tex[0]=tr;
1098                                 tex[1]=tg;
1099                                 tex[2]=tb;
1100                                 out[0]=har->r;
1101                                 out[1]=har->g;
1102                                 out[2]=har->b;
1103
1104                                 texture_rgb_blend(in,tex,out,tin,mtex->colfac,mtex->blendtype);
1105                         //      zn= 1.0-yn;
1106                                 //har->r= (yn*tr+ zn*ma->r);
1107                                 //har->g= (yn*tg+ zn*ma->g);
1108                                 //har->b= (yn*tb+ zn*ma->b);
1109                                 har->r= in[0];
1110                                 har->g= in[1];
1111                                 har->b= in[2];
1112                         }
1113                         if(mtex->mapto & MAP_ALPHA)
1114                                 har->alfa = texture_value_blend(mtex->def_var,har->alfa,tin,mtex->varfac,mtex->blendtype,mtex->maptoneg & MAP_ALPHA);
1115                         if(mtex->mapto & MAP_HAR)
1116                                 har->hard = 1.0+126.0*texture_value_blend(mtex->def_var,((float)har->hard)/127.0,tin,mtex->varfac,mtex->blendtype,mtex->maptoneg & MAP_HAR);
1117                         if(mtex->mapto & MAP_RAYMIRR)
1118                                 har->hasize = 100.0*texture_value_blend(mtex->def_var,har->hasize/100.0,tin,mtex->varfac,mtex->blendtype,mtex->maptoneg & MAP_RAYMIRR);
1119                         /* now what on earth is this good for?? */
1120                         //if(mtex->texco & 16) {
1121                         //      har->alfa= tin;
1122                         //}
1123                 }
1124
1125         return har;
1126 }
1127
1128 /* -------------------------- operations on entire database ----------------------- */
1129
1130 /* ugly function for halos in panorama */
1131 static int panotestclip(Render *re, int do_pano, float *v)
1132 {
1133         /* to be used for halos en infos */
1134         float abs4;
1135         short c=0;
1136
1137         if(do_pano==0) return testclip(v);
1138
1139         abs4= fabs(v[3]);
1140
1141         if(v[2]< -abs4) c=16;           /* this used to be " if(v[2]<0) ", see clippz() */
1142         else if(v[2]> abs4) c+= 32;
1143
1144         if( v[1]>abs4) c+=4;
1145         else if( v[1]< -abs4) c+=8;
1146
1147         abs4*= re->xparts;
1148         if( v[0]>abs4) c+=2;
1149         else if( v[0]< -abs4) c+=1;
1150
1151         return c;
1152 }
1153
1154 /*
1155   This adds the hcs coordinates to vertices. It iterates over all
1156   vertices, halos and faces. After the conversion, we clip in hcs.
1157
1158   Elsewhere, all primites are converted to vertices. 
1159   Called in 
1160   - envmapping (envmap.c)
1161   - shadow buffering (shadbuf.c)
1162 */
1163
1164 void project_renderdata(Render *re, void (*projectfunc)(float *, float mat[][4], float *),  int do_pano, float xoffs, int do_buckets)
1165 {
1166         ObjectRen *obr;
1167         HaloRen *har = NULL;
1168         float zn, vec[3], hoco[4];
1169         int a;
1170
1171         if(do_pano) {
1172                 float panophi= xoffs;
1173                 
1174                 re->panosi= sin(panophi);
1175                 re->panoco= cos(panophi);
1176         }
1177
1178         for(obr=re->objecttable.first; obr; obr=obr->next) {
1179                 /* calculate view coordinates (and zbuffer value) */
1180                 for(a=0; a<obr->tothalo; a++) {
1181                         if((a & 255)==0) har= obr->bloha[a>>8];
1182                         else har++;
1183
1184                         if(do_pano) {
1185                                 vec[0]= re->panoco*har->co[0] + re->panosi*har->co[2];
1186                                 vec[1]= har->co[1];
1187                                 vec[2]= -re->panosi*har->co[0] + re->panoco*har->co[2];
1188                         }
1189                         else {
1190                                 VECCOPY(vec, har->co);
1191                         }
1192
1193                         projectfunc(vec, re->winmat, hoco);
1194                         
1195                         /* we clip halos less critical, but not for the Z */
1196                         hoco[0]*= 0.5;
1197                         hoco[1]*= 0.5;
1198                         
1199                         if( panotestclip(re, do_pano, hoco) ) {
1200                                 har->miny= har->maxy= -10000;   /* that way render clips it */
1201                         }
1202                         else if(hoco[3]<0.0) {
1203                                 har->miny= har->maxy= -10000;   /* render clips it */
1204                         }
1205                         else /* do the projection...*/
1206                         {
1207                                 /* bring back hocos */
1208                                 hoco[0]*= 2.0;
1209                                 hoco[1]*= 2.0;
1210                                 
1211                                 zn= hoco[3];
1212                                 har->xs= 0.5*re->winx*(1.0+hoco[0]/zn); /* the 0.5 negates the previous 2...*/
1213                                 har->ys= 0.5*re->winy*(1.0+hoco[1]/zn);
1214                         
1215                                 /* this should be the zbuffer coordinate */
1216                                 har->zs= 0x7FFFFF*(hoco[2]/zn);
1217                                 /* taking this from the face clip functions? seems ok... */
1218                                 har->zBufDist = 0x7FFFFFFF*(hoco[2]/zn);
1219                                 
1220                                 vec[0]+= har->hasize;
1221                                 projectfunc(vec, re->winmat, hoco);
1222                                 vec[0]-= har->hasize;
1223                                 zn= hoco[3];
1224                                 har->rad= fabs(har->xs- 0.5*re->winx*(1.0+hoco[0]/zn));
1225                         
1226                                 /* this clip is not really OK, to prevent stars to become too large */
1227                                 if(har->type & HA_ONLYSKY) {
1228                                         if(har->rad>3.0) har->rad= 3.0;
1229                                 }
1230                         
1231                                 har->radsq= har->rad*har->rad;
1232                         
1233                                 har->miny= har->ys - har->rad/re->ycor;
1234                                 har->maxy= har->ys + har->rad/re->ycor;
1235                         
1236                                 /* the Zd value is still not really correct for pano */
1237                         
1238                                 vec[2]-= har->hasize;   /* z negative, otherwise it's clipped */
1239                                 projectfunc(vec, re->winmat, hoco);
1240                                 zn= hoco[3];
1241                                 zn= fabs( (float)har->zs - 0x7FFFFF*(hoco[2]/zn));
1242                                 har->zd= CLAMPIS(zn, 0, INT_MAX);
1243                         
1244                         }
1245                         
1246                 }
1247         }
1248
1249         project_strands(re, projectfunc, do_pano, do_buckets);
1250 }
1251
1252 /* ------------------------------------------------------------------------- */
1253
1254 ObjectInstanceRen *RE_addRenderInstance(Render *re, ObjectRen *obr, Object *ob, Object *par, int index, int psysindex, float mat[][4])
1255 {
1256         ObjectInstanceRen *obi;
1257         float mat3[3][3];
1258
1259         obi= MEM_callocN(sizeof(ObjectInstanceRen), "ObjectInstanceRen");
1260         obi->obr= obr;
1261         obi->ob= ob;
1262         obi->par= par;
1263         obi->index= index;
1264         obi->psysindex= psysindex;
1265
1266         if(mat) {
1267                 Mat4CpyMat4(obi->mat, mat);
1268                 Mat3CpyMat4(mat3, mat);
1269                 Mat3Inv(obi->imat, mat3);
1270                 obi->flag |= R_DUPLI_TRANSFORMED;
1271         }
1272
1273         BLI_addtail(&re->instancetable, obi);
1274
1275         return obi;
1276 }
1277
1278 void find_dupli_objectren(Render *re, ObjectInstanceRen *obi, ObjectInstanceRen *lastobi)
1279 {
1280         ObjectRen *obr;
1281
1282         /* see if last object did the same lookup, so we can just reuse result */
1283         if(lastobi && obi->ob == lastobi->ob && obi->par == lastobi->par && obi->psysindex == lastobi->psysindex) {
1284                 obi->obr= lastobi->obr;
1285                 return;
1286         }
1287
1288         /* dupli objects are created after object instances, so we look through
1289          * object list to find it */
1290         obr= re->objecttable.first;
1291         while(obr && (obr->ob != obi->ob || obr->par != obi->par || obr->psysindex != obi->psysindex))
1292                 obr= obr->next;
1293
1294         if(!obr) {
1295                 obr= re->objecttable.first;
1296                 while(obr && (obr->ob != obi->ob || obr->psysindex != obi->psysindex) && obr->par == NULL)
1297                         obr= obr->next;
1298         }
1299
1300         obi->obr= obr;
1301 }
1302
1303 void RE_makeRenderInstances(Render *re)
1304 {
1305         ObjectInstanceRen *obi, *oldobi, *lastobi= NULL;
1306         ListBase newlist;
1307         int tot;
1308
1309         /* convert list of object instances to an array for index based lookup */
1310         tot= BLI_countlist(&re->instancetable);
1311         re->objectinstance= MEM_callocN(sizeof(ObjectInstanceRen)*tot, "ObjectInstance");
1312         re->totinstance= tot;
1313         newlist.first= newlist.last= NULL;
1314
1315         obi= re->objectinstance;
1316         for(oldobi=re->instancetable.first; oldobi; oldobi=oldobi->next) {
1317                 *obi= *oldobi;
1318
1319                 if(!obi->obr) {
1320                         find_dupli_objectren(re, obi, lastobi);
1321                         lastobi= obi;
1322                 }
1323
1324                 if(obi->obr) {
1325                         obi->prev= obi->next= NULL;
1326                         BLI_addtail(&newlist, obi);
1327                         obi++;
1328                 }
1329                 else
1330                         re->totinstance--;
1331         }
1332
1333         BLI_freelistN(&re->instancetable);
1334         re->instancetable= newlist;
1335 }
1336