Initial revision
[blender.git] / source / blender / render / intern / source / zbufferdatastruct.c
1 /**
2  * zbufferdatastruct.c
3  *
4  * $Id$
5  *
6  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version. The Blender
12  * Foundation also sells licenses for use in proprietary software under
13  * the Blender License.  See http://www.blender.org/BL/ for information
14  * about this.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software Foundation,
23  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
24  *
25  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
26  * All rights reserved.
27  *
28  * The Original Code is: all of this file.
29  *
30  * Contributor(s): none yet.
31  *
32  * ***** END GPL/BL DUAL LICENSE BLOCK *****
33  *
34  * The z buffer consists of an array of lists. Each list holds the objects 
35  * behind a pixel. These can be sorted for closest distance. Per object,
36  * we store: 
37  * - object type
38  * - object index
39  * - minimum distance
40  * - maximum distance
41  * - oversample flags
42  *
43  * The buffer was created to fit the new unified renderpipeline. We might 
44  * turn it into an object later on.
45  *
46  * The z buffer has an unlimited depth. The oversampling code chops at a 
47  * certain number of faces. This number is defined in 
48  * vanillaRenderPipe_types.h
49  *
50  * Version 1 of the z buffer inserted objects by means of linear
51  * search: we walk along the list until we find the right object or
52  * until we have to insert a new one. This is terribly inefficient
53  * when we are dealing with large numbers of objects. Can we find a
54  * better solution here?
55  *
56  * Because we treat halos as billboards, we optimize halo
57  * insertion. For this purpose the fillFlatObject() functions have
58  * been implemented.  */
59
60 #include <string.h>
61
62 #include "MEM_guardedalloc.h"
63 #include "zbufferdatastruct.h"
64 #include "render.h"
65 #include "render_intern.h"
66 /* if defined: all jittersamples are stored individually. _very_ serious     */
67 /* performance hit ! also gives some buffer size problems in big scenes      */
68 /* #define RE_INDIVIDUAL_SUBPIXELS */
69
70 /* ------------------------------------------------------------------------- */
71
72 static RE_APixstrExtMain RE_apsemfirst; /* pixstr bookkeeping var            */
73 static short RE_apsemteller = 0;        /* pixstr bookkeeping var            */
74 static int RE_zbufferwidth;             /* width of the z-buffer (pixels)    */
75 RE_APixstrExt *APixbufExt;     /* Zbuffer: linked list of face, halo indices */
76
77 /*-RE_APixstrExt------------------------------------------------------------ */ 
78
79 void initZbuffer(int width)
80 {
81     APixbufExt         = MEM_callocN(RE_ZBUFLEN * width * sizeof(RE_APixstrExt), 
82                                                                  "APixbufExt");
83         RE_zbufferwidth    = width;
84     RE_apsemteller     = 0;
85     RE_apsemfirst.next = NULL;
86     RE_apsemfirst.ps   = NULL;
87 } /* end of RE_APixstrExt *initZbufferDataStruct() */
88
89 /* ------------------------------------------------------------------------- */
90
91 void freeZbuffer(void)
92 {
93         if (APixbufExt) MEM_freeN(APixbufExt); 
94         freepseA(); 
95 } /* end of void freeZbuffer(void) */
96
97 /* ------------------------------------------------------------------------- */
98
99 void resetZbuffer(void)
100 {
101         int len;
102
103         freepseA(); 
104         len = sizeof(RE_APixstrExt) * RE_zbufferwidth * RE_ZBUFLEN;
105         memset(APixbufExt, 0, len);
106 } /* end of void resetZbuffer(void) */
107
108 /* ------------------------------------------------------------------------- */
109
110 RE_APixstrExt *addpsemainA()
111 {
112         RE_APixstrExtMain *psm;
113
114         psm= &RE_apsemfirst;
115
116         while(psm->next) {
117                 psm= psm->next;
118         }
119
120         psm->next= MEM_callocN(sizeof(RE_APixstrExtMain), "addpsemainA");
121
122         psm= psm->next;
123
124    /* Initialise the new structure to safe values. Memory that is newly */
125    /* allocated must be zero... Not sure if that happens everywhere now.*/
126         psm->next=0;
127         psm->ps= MEM_callocN(4096*sizeof(RE_APixstrExt),"pixstrext");
128         RE_apsemteller= 0;
129
130         return psm->ps;
131 } /* End of RE_APixstrExt *addpsemainA() */
132
133 /* ------------------------------------------------------------------------- */
134
135 void freepseA()
136 {
137         RE_APixstrExtMain *psm, *next;
138
139         psm= &RE_apsemfirst;
140
141         while(psm) {
142                 next= psm->next;
143                 if(psm->ps) {
144                         MEM_freeN(psm->ps);
145                         psm->ps= 0;
146                 }
147                 if(psm!= &RE_apsemfirst) MEM_freeN(psm);
148                 psm= next;
149         }
150
151         RE_apsemfirst.next= 0;
152         RE_apsemfirst.ps= 0;
153         RE_apsemteller= 0;
154 } /* End of void freepseA() */
155
156 /* ------------------------------------------------------------------------- */
157
158 RE_APixstrExt *addpseA(void)
159 {
160         static RE_APixstrExt *prev;
161
162         /* eerste PS maken */
163         if((RE_apsemteller & 4095)==0) prev= addpsemainA();
164         else prev++;
165         RE_apsemteller++;
166         
167         return prev;
168 } /* End of RE_APixstrExt *addpseA(void) */
169
170 /* ------------------------------------------------------------------------- */
171
172 void insertObject(int apteller,
173 /*                                int opaque, */
174                                   int obindex,
175                                   int obtype, 
176                                   int dist, 
177                                   int mask)
178 {
179         /* Guard the insertion if needed? */
180         RE_APixstrExt* apn = &APixbufExt[apteller]; 
181         
182         while(apn) {
183                 if(apn->t[0] == RE_NONE) {
184                         apn->p[0] = obindex; apn->t[0] = obtype;
185                         apn->zmin[0] = dist; apn->zmax[0] = dist;
186                         apn->mask[0] = mask;   
187                         break; 
188                 }
189 #ifndef RE_INDIVIDUAL_SUBPIXELS
190                 if((apn->p[0] == obindex) && (apn->t[0] & obtype)) {
191                         if(dist < apn->zmin[0]) apn->zmin[0] = dist;
192                         else if(dist > apn->zmax[0]) apn->zmax[0] = dist;
193                         apn->mask[0]|= mask; 
194                         break; 
195                 } 
196 #endif
197                 if(apn->t[1] == RE_NONE) {
198                         apn->p[1] = obindex; apn->t[1] = obtype;
199                         apn->zmin[1] = dist; apn->zmax[1] = dist;
200                         apn->mask[1] = mask;   
201                         break; 
202                 }
203 #ifndef RE_INDIVIDUAL_SUBPIXELS
204                 if((apn->p[1] == obindex) && (apn->t[1] & obtype)) {
205                         if(dist < apn->zmin[1]) apn->zmin[1] = dist;
206                         else if(dist > apn->zmax[1]) apn->zmax[1] = dist;
207                         apn->mask[1]|= mask; 
208                         break; 
209                 } 
210 #endif
211                 if(apn->t[2] == RE_NONE) {
212                         apn->p[2] = obindex; apn->t[2] = obtype;
213                         apn->zmin[2] = dist; apn->zmax[2] = dist;
214                         apn->mask[2] = mask;   
215                         break; 
216                 }
217 #ifndef RE_INDIVIDUAL_SUBPIXELS
218                 if((apn->p[2] == obindex) && (apn->t[2] & obtype)) {
219                         if(dist < apn->zmin[2]) apn->zmin[2] = dist;
220                         else if(dist > apn->zmax[2]) apn->zmax[2] = dist;
221                         apn->mask[2]|= mask; 
222                         break; 
223                 } 
224 #endif
225                 if(apn->t[3] == RE_NONE) {
226                         apn->p[3] = obindex; apn->t[3] = obtype;
227                         apn->zmin[3] = dist; apn->zmax[3] = dist;
228                         apn->mask[3] = mask;   
229                         break; 
230                 }
231 #ifndef RE_INDIVIDUAL_SUBPIXELS
232                 if((apn->p[3] == obindex) && (apn->t[3] & obtype)) {
233                         if(dist < apn->zmin[3]) apn->zmin[3] = dist;
234                         else if(dist > apn->zmax[3]) apn->zmax[3] = dist;
235                         apn->mask[3]|= mask; 
236                         break; 
237                 } 
238 #endif
239                 if(apn->next==0) apn->next= addpseA();
240                 apn= apn->next;
241         }                               
242 } /* end of insertObject(RE_APixstrExt*, int, int, int, int) */
243
244 /* ------------------------------------------------------------------------- */
245
246 void insertFlatObject(RE_APixstrExt *apn, int obindex, int obtype, int dist, int mask)
247 {
248         while(apn) {
249                 if(apn->t[0] == RE_NONE) {
250                         apn->p[0] = obindex; apn->zmin[0] = dist; 
251                         apn->zmax[0] = dist; apn->mask[0] = mask; 
252                         apn->t[0] = obtype;  
253                         break; 
254                 }
255 #ifndef RE_INDIVIDUAL_SUBPIXELS
256                 if( (apn->t[0] & obtype) && (apn->p[0] == obindex)) {
257                         apn->mask[0]|= mask; break; 
258                 }
259 #endif
260                 if(apn->t[1] == RE_NONE) {
261                         apn->p[1] = obindex; apn->zmin[1] = dist; 
262                         apn->zmax[1] = dist; apn->mask[1] = mask; 
263                         apn->t[1] = obtype;  
264                         break;
265                 }
266 #ifndef RE_INDIVIDUAL_SUBPIXELS
267                 if( (apn->t[1] & obtype) && (apn->p[1] == obindex)) {
268                         apn->mask[1]|= mask; break; 
269                 }
270 #endif
271                 if(apn->t[2] == RE_NONE) {
272                         apn->p[2] = obindex; apn->zmin[2] = dist; 
273                         apn->zmax[2] = dist; apn->mask[2] = mask; 
274                         apn->t[2] = obtype;  
275                         break;
276                 }
277 #ifndef RE_INDIVIDUAL_SUBPIXELS
278                 if( (apn->t[2] & obtype) && (apn->p[2] == obindex)) {
279                         apn->mask[2]|= mask; break; 
280                 }
281 #endif
282                 if(apn->t[3] == RE_NONE) {
283                         apn->p[3] = obindex; apn->zmin[3] = dist; 
284                         apn->zmax[3] = dist; apn->mask[3] = mask; 
285                         apn->t[3] = obtype;  
286                         break;
287                 }
288 #ifndef RE_INDIVIDUAL_SUBPIXELS
289                 if( (apn->t[3] & obtype) && (apn->p[3] == obindex)) {
290                         apn->mask[3]|= mask; break; 
291                 }
292 #endif
293                 if(apn->next==0) apn->next= addpseA();
294                 apn= apn->next;
295         };                    
296 } /* end of void insertFlatObject(RE_APixstrExt, int, int, int, int)*/
297
298 /* ------------------------------------------------------------------------- */
299 /* This function might be helped by an end-of-list marker                    */
300 void insertFlatObjectNoOsa(RE_APixstrExt *ap, 
301                                                    int obindex, 
302                                                    int obtype, 
303                                                    int dist, 
304                                                    int mask)
305 {
306         while(ap) {
307                 if(ap->t[0] == RE_NONE) {
308                         ap->p[0] = obindex; ap->zmin[0] = dist; 
309                         ap->zmax[0] = dist; ap->mask[0] = mask; 
310                         ap->t[0] = obtype;  
311                         break; 
312                 }
313
314                 if(ap->t[1] == RE_NONE) {
315                         ap->p[1] = obindex; ap->zmin[1] = dist; 
316                         ap->zmax[1] = dist; ap->mask[1] = mask; 
317                         ap->t[1] = obtype;  
318                         break;
319                 }
320
321                 if(ap->t[2] == RE_NONE) {
322                         ap->p[2] = obindex; ap->zmin[2] = dist; 
323                         ap->zmax[2] = dist; ap->mask[2] = mask; 
324                         ap->t[2] = obtype;  
325                         break;
326                 }
327
328                 if(ap->t[3] == RE_NONE) {
329                         ap->p[3] = obindex; ap->zmin[3] = dist; 
330                         ap->zmax[3] = dist; ap->mask[3] = mask; 
331                         ap->t[3] = obtype;  
332                         break;
333                 }
334
335                 if(ap->next==0) ap->next= addpseA();
336                 ap= ap->next;
337         };                    
338 } /* end of void insertFlatObjectNoOsa(RE_APixstrExt, int, int, int, int)*/
339
340 /* ------------------------------------------------------------------------- */
341
342 /* EOF */