← Back to branch summary

~hilaire-fernandes/drgeo/trunk

« back to all changes in this revision

Viewing changes to VMs/iPad/source/Cross/plugins/Squeak3D/b3dMain.c

  • Committer: Hilaire Fernandes
  • Date: 2012-01-27 21:15:40 UTC
  • Revision ID: hilaire.fernandes@gmail.com-20120127211540-912spf97bhpx6mve
Initial additions

Show diffs side-by-side

added added

removed removed

Lines of Context:
VMs/iPad/source/Cross/plugins/Squeak3D/b3dMain.c
 
1
/****************************************************************************
 
2
*   PROJECT: Balloon 3D Graphics Subsystem for Squeak
 
3
*   FILE:    b3dMain.c
 
4
*   CONTENT: Main rasterizer body
 
5
*
 
6
*   AUTHOR:  Andreas Raab (ar)
 
7
*   ADDRESS: Walt Disney Imagineering, Glendale, CA
 
8
*   EMAIL:   andreasr@wdi.disney.com
 
9
*   RCSID:   $Id: b3dMain.c 2 2001-10-24 23:11:49Z rowledge $
 
10
*
 
11
*   NOTES:
 
12
*
 
13
*
 
14
*****************************************************************************/
 
15
#include <stdio.h>  /* printf() */
 
16
#include <stdlib.h> /* exit()   */
 
17
#include <assert.h> /* assert() */
 
18
#include "b3d.h"
 
19
 
 
20
#ifndef NULL
 
21
#define NULL ((void*)0)
 
22
#endif
 
23
 
 
24
#ifdef B3D_PROFILE
 
25
unsigned int b3dObjSetupTime;
 
26
unsigned int b3dMapObjectTime;
 
27
unsigned int b3dVertexOrderTime;
 
28
unsigned int b3dSortFaceTime;
 
29
#endif
 
30
 
 
31
/* helpers */
 
32
#define rasterPosX rasterPos[0]
 
33
#define rasterPosY rasterPos[1]
 
34
#define rasterPosZ rasterPos[2]
 
35
#define rasterPosW rasterPos[3]
 
36
 
 
37
#define windowPosX windowPos[0]
 
38
#define windowPosY windowPos[1]
 
39
 
 
40
#define texCoordS texCoord[0]
 
41
#define texCoordT texCoord[1]
 
42
 
 
43
#define redValue   cc.color[RED_INDEX]
 
44
#define greenValue cc.color[GREEN_INDEX]
 
45
#define blueValue  cc.color[BLUE_INDEX]
 
46
#define alphaValue cc.color[ALPHA_INDEX]
 
47
 
 
48
/* globals */
 
49
B3DRasterizerState *currentState;
 
50
 
 
51
B3DActiveEdgeTable *aet;
 
52
B3DPrimitiveEdgeList *addedEdges;
 
53
 
 
54
B3DEdgeAllocList *edgeAlloc;
 
55
B3DFaceAllocList *faceAlloc;
 
56
B3DAttrAllocList *attrAlloc;
 
57
 
 
58
int nFaces = 0;
 
59
int maxFaces = 0;
 
60
int maxEdges = 0;
 
61
/*************************************************************/
 
62
/*************************************************************/
 
63
/*************************************************************/
 
64
 
 
65
void b3dAbort(char *msg){
 
66
        printf(msg);
 
67
        exit(-1);
 
68
}
 
69
 
 
70
void b3dValidateEdgeOrder(B3DPrimitiveEdgeList *list)
 
71
{
 
72
        int i;
 
73
 
 
74
        if(list->size)
 
75
                if(list->data[0]->leftFace == list->data[0]->rightFace) {
 
76
                        b3dAbort("Left face == right face");
 
77
                }
 
78
        for(i=1; i<list->size; i++) {
 
79
                if(list->data[i-1]->xValue > list->data[i]->xValue) {
 
80
                        b3dAbort("Edge list is broken");
 
81
                }
 
82
                if(list->data[i]->leftFace == list->data[i]->rightFace) {
 
83
                        b3dAbort("Left face == right face");
 
84
                }
 
85
        }
 
86
}
 
87
 
 
88
void b3dValidateAETOrder(B3DActiveEdgeTable *list)
 
89
{
 
90
        int i;
 
91
 
 
92
        if(list->size)
 
93
                if(list->data[0]->leftFace == list->data[0]->rightFace) {
 
94
                        b3dAbort("Left face == right face");
 
95
                }
 
96
        for(i=1; i<list->size; i++) {
 
97
                if(list->data[i-1]->xValue > list->data[i]->xValue) {
 
98
                        b3dAbort("Edge list is broken");
 
99
                }
 
100
                if(list->data[i]->leftFace == list->data[i]->rightFace) {
 
101
                        b3dAbort("Left face == right face");
 
102
                }
 
103
        }
 
104
}
 
105
 
 
106
/*************************************************************/
 
107
/*************************************************************/
 
108
/*************************************************************/
 
109
/* b3dInitializeFace:
 
110
        Allocate a new primitive face based on the given vertices.
 
111
        Do the necessary initial setup, but don't set up any drawing attributes yet.
 
112
        Return the newly created face.
 
113
        NOTE: May cause allocation of one face!
 
114
*/
 
115
B3DPrimitiveFace *b3dInitializeFace(B3DPrimitiveVertex *v0,
 
116
                                                                        B3DPrimitiveVertex *v1,
 
117
                                                                        B3DPrimitiveVertex *v2,
 
118
                                                                        B3DTexture *texture, 
 
119
                                                                        int attrFlags)
 
120
{
 
121
        B3DPrimitiveFace *face;
 
122
 
 
123
        /* Compute major and minor reference edges */
 
124
        {
 
125
                float majorDx = v2->rasterPosX - v0->rasterPosX;
 
126
                float majorDy = v2->rasterPosY - v0->rasterPosY;
 
127
                float minorDx = v1->rasterPosX - v0->rasterPosX;
 
128
                float minorDy = v1->rasterPosY - v0->rasterPosY;
 
129
                float area = (majorDx * minorDy) - (minorDx * majorDy);
 
130
 
 
131
                if(area > -0.001 && area < 0.001) return NULL;
 
132
                /* Now that we know the face is valid, do the actual allocation */
 
133
                b3dAllocFace(faceAlloc, face);
 
134
 
 
135
                if(b3dDebug)
 
136
                        if(!face) b3dAbort("Face allocation failed");
 
137
 
 
138
                face->v0 = v0;
 
139
                face->v1 = v1;
 
140
                face->v2 = v2;
 
141
                face->leftEdge = NULL;
 
142
                face->rightEdge = NULL;
 
143
                face->attributes = NULL;
 
144
                face->oneOverArea = (float) (1.0 / area);
 
145
                face->majorDx = majorDx;
 
146
                face->majorDy = majorDy;
 
147
                face->minorDx = minorDx;
 
148
                face->minorDy = minorDy;
 
149
                face->texture = texture;
 
150
                face->flags |= attrFlags & (B3D_ATTR_MASK << B3D_ATTR_SHIFT);
 
151
 
 
152
                { /* Compute dzdx and dzdy */
 
153
                        float majorDz = v2->rasterPosZ - v0->rasterPosZ;
 
154
                        float minorDz = v1->rasterPosZ - v0->rasterPosZ;
 
155
 
 
156
                        face->dzdx = face->oneOverArea * ((majorDz * minorDy) - (minorDz * majorDy));
 
157
                        face->dzdy = face->oneOverArea * ((majorDx * minorDz) - (minorDx * majorDz));
 
158
                }
 
159
        }
 
160
 
 
161
        {/* Compute minZ/maxZ */
 
162
                float z0 = v0->rasterPosZ;
 
163
                float z1 = v1->rasterPosZ;
 
164
                float z2 = v2->rasterPosZ;
 
165
                if(z0 <= z1) {
 
166
                        if(z1 <= z2) {
 
167
                                face->minZ = z0;
 
168
                                face->maxZ = z2;
 
169
                        } else if(z0 <= z2) {
 
170
                                face->minZ = z0;
 
171
                                face->maxZ = z1;
 
172
                        } else {
 
173
                                face->minZ = z2;
 
174
                                face->maxZ = z1;
 
175
                        }
 
176
                } else if(z2 <= z1) {
 
177
                        face->minZ = z2;
 
178
                        face->maxZ = z0;
 
179
                } else if(z0 <= z2) {
 
180
                        face->minZ = z1;
 
181
                        face->maxZ = z0;
 
182
                } else {
 
183
                        face->minZ = z1;
 
184
                        face->maxZ = z0;
 
185
                }
 
186
        } /* End of minZ/maxZ */
 
187
 
 
188
        return face;
 
189
}
 
190
 
 
191
/* b3dInitializePass2:
 
192
        Do a second initialization pass if the face is known to be visible.
 
193
*/
 
194
int b3dInitializePass2(B3DPrimitiveFace *face)
 
195
{
 
196
        double majorDv, minorDv, baseValue;
 
197
        double dvdx, dvdy;
 
198
        B3DPrimitiveAttribute *attr;
 
199
        B3DPrimitiveVertex *v0 = face->v0;
 
200
        B3DPrimitiveVertex *v1 = face->v1;
 
201
        B3DPrimitiveVertex *v2 = face->v2;
 
202
 
 
203
        {
 
204
                int ok;
 
205
                b3dAllocAttrib(attrAlloc, face, ok);
 
206
                if(!ok) return 0; /* NOT initalized */
 
207
        }
 
208
 
 
209
        attr = face->attributes;
 
210
        assert(attr);
 
211
        
 
212
        if(face->flags & B3D_FACE_RGB) {
 
213
                /* Setup RGB interpolation */
 
214
                majorDv = v2->redValue - v0->redValue;
 
215
                minorDv = v1->redValue - v0->redValue;
 
216
                dvdx = face->oneOverArea * ((majorDv * face->minorDy) - (minorDv * face->majorDy));
 
217
                dvdy = face->oneOverArea * ((minorDv * face->majorDx) - (majorDv * face->minorDx));
 
218
                attr->value = (float) v0->redValue;
 
219
                attr->dvdx  = (float) dvdx;
 
220
                attr->dvdy  = (float) dvdy;
 
221
                attr = attr->next;
 
222
 
 
223
                majorDv = v2->greenValue - v0->greenValue;
 
224
                minorDv = v1->greenValue - v0->greenValue;
 
225
                dvdx = face->oneOverArea * ((majorDv * face->minorDy) - (minorDv * face->majorDy));
 
226
                dvdy = face->oneOverArea * ((minorDv * face->majorDx) - (majorDv * face->minorDx));
 
227
                attr->value = (float) v0->greenValue;
 
228
                attr->dvdx  = (float) dvdx;
 
229
                attr->dvdy  = (float) dvdy;
 
230
                attr = attr->next;
 
231
 
 
232
                majorDv = v2->blueValue - v0->blueValue;
 
233
                minorDv = v1->blueValue - v0->blueValue;
 
234
                dvdx = face->oneOverArea * ((majorDv * face->minorDy) - (minorDv * face->majorDy));
 
235
                dvdy = face->oneOverArea * ((minorDv * face->majorDx) - (majorDv * face->minorDx));
 
236
                attr->value = (float) v0->blueValue;
 
237
                attr->dvdx  = (float) dvdx;
 
238
                attr->dvdy  = (float) dvdy;
 
239
                attr = attr->next;
 
240
        }
 
241
        if(face->flags & B3D_FACE_ALPHA) {
 
242
                /* Setup alpha interpolation */
 
243
                majorDv = v2->alphaValue - v0->alphaValue;
 
244
                minorDv = v1->alphaValue - v0->alphaValue;
 
245
                dvdx = face->oneOverArea * ((majorDv * face->minorDy) - (minorDv * face->majorDy));
 
246
                dvdy = face->oneOverArea * ((minorDv * face->majorDx) - (majorDv * face->minorDx));
 
247
                attr->value = (float) v0->alphaValue;
 
248
                attr->dvdx  = (float) dvdx;
 
249
                attr->dvdy  = (float) dvdy;
 
250
                attr = attr->next;
 
251
        }
 
252
        if(face->flags & B3D_FACE_STW) {
 
253
                /* Setup texture coordinate interpolation */
 
254
                double w0 = v0->rasterPosW;
 
255
                double w1 = v1->rasterPosW;
 
256
                double w2 = v2->rasterPosW;
 
257
 
 
258
                majorDv = w2 - w0;
 
259
                minorDv = w1 - w0;
 
260
                dvdx = face->oneOverArea * ((majorDv * face->minorDy) - (minorDv * face->majorDy));
 
261
                dvdy = face->oneOverArea * ((minorDv * face->majorDx) - (majorDv * face->minorDx));
 
262
                attr->value = (float) w0;
 
263
                attr->dvdx  = (float) dvdx;
 
264
                attr->dvdy  = (float) dvdy;
 
265
                attr = attr->next;
 
266
 
 
267
                baseValue = v0->texCoordS * w0;
 
268
                majorDv = (v2->texCoordS * w2) - baseValue;
 
269
                minorDv = (v1->texCoordS * w1) - baseValue;
 
270
                dvdx = face->oneOverArea * ((majorDv * face->minorDy) - (minorDv * face->majorDy));
 
271
                dvdy = face->oneOverArea * ((minorDv * face->majorDx) - (majorDv * face->minorDx));
 
272
                attr->value = (float) baseValue;
 
273
                attr->dvdx  = (float) dvdx;
 
274
                attr->dvdy  = (float) dvdy;
 
275
                attr = attr->next;
 
276
 
 
277
                baseValue = v0->texCoordT * w0;
 
278
                majorDv = (v2->texCoordT * w2) - baseValue;
 
279
                minorDv = (v1->texCoordT * w1) - baseValue;
 
280
                dvdx = face->oneOverArea * ((majorDv * face->minorDy) - (minorDv * face->majorDy));
 
281
                dvdy = face->oneOverArea * ((minorDv * face->majorDx) - (majorDv * face->minorDx));
 
282
                attr->value = (float) baseValue;
 
283
                attr->dvdx  = (float) dvdx;
 
284
                attr->dvdy  = (float) dvdy;
 
285
                attr = attr->next;
 
286
        }
 
287
        face->flags |= B3D_FACE_INITIALIZED;
 
288
        return 1;
 
289
}
 
290
 
 
291
/* b3dInitializeEdge:
 
292
        Initialize the incremental values of the given edge.
 
293
*/
 
294
/* INLINE b3dInitializeEdge(edge) */
 
295
void b3dInitializeEdge(B3DPrimitiveEdge *edge)
 
296
{
 
297
        assert(edge);
 
298
        assert(edge->nLines);
 
299
        edge->xValue = edge->v0->windowPosX;
 
300
        edge->zValue = edge->v0->rasterPosZ;
 
301
        if(edge->nLines > 1) {
 
302
                edge->xIncrement = (edge->v1->windowPosX - edge->v0->windowPosX) / edge->nLines;
 
303
                edge->zIncrement = (edge->v1->rasterPosZ - edge->v0->rasterPosZ) / (float) edge->nLines;
 
304
        } else {
 
305
                edge->xIncrement = (edge->v1->windowPosX - edge->v0->windowPosX);
 
306
                edge->zIncrement = (edge->v1->rasterPosZ - edge->v0->rasterPosZ);
 
307
        }
 
308
}
 
309
/* --INLINE-- */
 
310
 
 
311
 
 
312
/*************************************************************/
 
313
/*************************************************************/
 
314
/*************************************************************/
 
315
 
 
316
/* b3dFirstIndexForInserting:
 
317
        Return the first possible index for inserting an edge with the given x value.
 
318
*/
 
319
 
 
320
int b3dFirstIndexForInserting(B3DPrimitiveEdgeList *list, int xValue)
 
321
{
 
322
        int low, high, index;
 
323
        low = 0;
 
324
        high = list->size-1;
 
325
        while(low <= high) {
 
326
                index = (low + high) >> 1;
 
327
                if(list->data[index]->xValue <= xValue)
 
328
                        low = index+1;
 
329
                else
 
330
                        high = index-1;
 
331
        }
 
332
        index = low;
 
333
        while(index > 0 && (list->data[index-1]->xValue) == xValue)
 
334
                index--;
 
335
        return index;
 
336
}
 
337
 
 
338
/* b3dAddEdgeBeforeIndex:
 
339
        Insert the edge to the list before the given index.
 
340
*/
 
341
/* INLINE b3dAddEdgeBeforeIndex(list, edge, index) */
 
342
void b3dAddEdgeBeforeIndex(B3DPrimitiveEdgeList *list, B3DPrimitiveEdge *edge, int index)
 
343
{
 
344
        int i;
 
345
 
 
346
        if(b3dDebug)
 
347
                if(list->size == list->max)
 
348
                        b3dAbort("No more space for adding edges");
 
349
 
 
350
        assert( (list->size == index) || (list->data[index]->xValue >= edge->xValue));
 
351
        for(i=list->size-1; i >= index; i--)
 
352
                list->data[i+1] = list->data[i];
 
353
        list->data[index] = edge;
 
354
        list->size++;
 
355
}
 
356
/* --INLINE-- */
 
357
 
 
358
/* b3d2AddEdgesBeforeIndex:
 
359
        Insert the two edge to the list before the given index.
 
360
*/
 
361
/* INLINE b3dAdd2EdgesBeforeIndex(list, edge1, edge2, index) */
 
362
void b3dAdd2EdgesBeforeIndex(B3DPrimitiveEdgeList *list, 
 
363
                                                         B3DPrimitiveEdge *edge1, 
 
364
                                                         B3DPrimitiveEdge *edge2, 
 
365
                                                         int index)
 
366
{
 
367
        int i;
 
368
 
 
369
        if(b3dDebug)
 
370
                if(list->size+1 >= list->max)
 
371
                        b3dAbort("No more space for adding edges");
 
372
 
 
373
        assert( edge1->xValue == edge2->xValue);
 
374
        assert( (list->size == index) || (list->data[index]->xValue >= edge1->xValue));
 
375
 
 
376
        for(i=list->size-1; i >= index; i--)
 
377
                list->data[i+2] = list->data[i];
 
378
        list->data[index] = edge1;
 
379
        list->data[index+1] = edge2;
 
380
        list->size += 2;
 
381
}
 
382
/* --INLINE-- */
 
383
 
 
384
/* b3dAdjustFaceEdges:
 
385
        Assign left and right edges to the given face.
 
386
*/
 
387
/* INLINE b3dAdjustFaceEdges(face, edge1, edge2) */
 
388
void b3dAdjustFaceEdges(B3DPrimitiveFace *face, B3DPrimitiveEdge *edge1, B3DPrimitiveEdge *edge2)
 
389
{
 
390
        assert(face);
 
391
        assert(edge1);
 
392
        assert(edge2);
 
393
        if(edge1->xValue == edge2->xValue) {
 
394
                if(edge1->xIncrement <= edge2->xIncrement) {
 
395
                        face->leftEdge = edge1;
 
396
                        face->rightEdge = edge2;
 
397
                } else {
 
398
                        face->leftEdge = edge2;
 
399
                        face->rightEdge = edge1;
 
400
                }
 
401
        } else {
 
402
                if(edge1->xValue <= edge2->xValue) {
 
403
                        face->leftEdge = edge1;
 
404
                        face->rightEdge = edge2;
 
405
                } else {
 
406
                        face->leftEdge = edge2;
 
407
                        face->rightEdge = edge1;
 
408
                }
 
409
        }
 
410
}
 
411
/* --INLINE-- */
 
412
 
 
413
/* b3dAddLowerEdgeFromFace:
 
414
        Add a new lower edge from the given face.
 
415
        NOTE: oldEdge may be NULL!
 
416
        NOTE: May cause allocation of one edge!
 
417
*/
 
418
B3DPrimitiveEdge *b3dAddLowerEdgeFromFace(B3DPrimitiveFace *face, B3DPrimitiveEdge *oldEdge)
 
419
{
 
420
        B3DPrimitiveVertex *v0 = face->v0;
 
421
        B3DPrimitiveVertex *v1 = face->v1;
 
422
        B3DPrimitiveVertex *v2 = face->v2;
 
423
        int xValue = v1->windowPosX;
 
424
        int index;
 
425
 
 
426
        /* Search the list of added edges to merge the edges from the face */
 
427
        index = b3dFirstIndexForInserting(addedEdges, xValue);
 
428
        for(;index<addedEdges->size; index++) {
 
429
                B3DPrimitiveEdge *edge = addedEdges->data[index];
 
430
                if(edge->xValue != xValue) break;
 
431
                if(edge->rightFace) continue;
 
432
                if((edge->v0 == v1 && edge->v1 == v2) || /* The simple test*/
 
433
                        /* The complex test */
 
434
                        (edge->v0->windowPosX == v1->windowPosX &&
 
435
                         edge->v0->windowPosY == v1->windowPosY &&
 
436
                         edge->v0->rasterPosZ == v1->rasterPosZ &&
 
437
                         edge->v1->windowPosX == v2->windowPosX &&
 
438
                         edge->v1->windowPosY == v2->windowPosY &&
 
439
                         edge->v1->rasterPosZ == v2->rasterPosZ)) {
 
440
                        /* Found the edge */
 
441
                        if(face->leftEdge == oldEdge)
 
442
                                face->leftEdge = edge;
 
443
                        else
 
444
                                face->rightEdge = edge;
 
445
                        edge->rightFace = face;
 
446
                        return edge;
 
447
                }
 
448
        }
 
449
        /* Need to create a new edge.
 
450
           NOTE: Index already points to the right insertion point.
 
451
        */
 
452
        {
 
453
                B3DPrimitiveEdge *minorEdge;
 
454
                int nLines = (v2->windowPosY >> B3D_FixedToIntShift) - (v1->windowPosY >> B3D_FixedToIntShift);
 
455
                if(!nLines) return NULL; /* Edge is horizontal */
 
456
                b3dAllocEdge(edgeAlloc, minorEdge);
 
457
 
 
458
                if(b3dDebug)
 
459
                        if(!minorEdge)
 
460
                                b3dAbort("Edge allocation failed");
 
461
 
 
462
                minorEdge->v0 = v1;
 
463
                minorEdge->v1 = v2;
 
464
                minorEdge->nLines = nLines;
 
465
                minorEdge->leftFace = face;
 
466
                minorEdge->rightFace = NULL;
 
467
                if(face->leftEdge == oldEdge)
 
468
                        face->leftEdge = minorEdge;
 
469
                else
 
470
                        face->rightEdge = minorEdge;
 
471
                b3dInitializeEdge(minorEdge);
 
472
                b3dAddEdgeBeforeIndex(addedEdges, minorEdge, index);
 
473
                return minorEdge;
 
474
        }
 
475
        /* NOT REACHED */
 
476
}
 
477
 
 
478
/* b3dAddEdgesFromFace:
 
479
        Add the two new edges from the given primitive face.
 
480
        NOTE: May cause allocation of two edges (but not three)!
 
481
*/
 
482
void b3dAddEdgesFromFace(B3DPrimitiveFace *face, int yValue)
 
483
{
 
484
        int needMajor = 1;
 
485
        int needMinor = 1;
 
486
        B3DPrimitiveEdge *majorEdge = NULL;
 
487
        B3DPrimitiveEdge *minorEdge = NULL;
 
488
        B3DPrimitiveVertex *v0 = face->v0;
 
489
        B3DPrimitiveVertex *v1 = face->v1;
 
490
        B3DPrimitiveVertex *v2 = face->v2;
 
491
        int xValue = v0->windowPosX;
 
492
        int index;
 
493
 
 
494
        /* Search the list of added edges to merge the edges from the face */
 
495
        index = b3dFirstIndexForInserting(addedEdges, xValue);
 
496
        for(;index<addedEdges->size; index++) {
 
497
                B3DPrimitiveEdge *edge = addedEdges->data[index];
 
498
                if(edge->xValue != xValue) break;
 
499
                if(edge->rightFace) continue;
 
500
                if(edge->v0 != v0 &&
 
501
                        (edge->v0->windowPosY != v0->windowPosY ||
 
502
                         edge->v0->rasterPosZ != v0->rasterPosZ)) continue;
 
503
                /* If we come to this point the edge might be usable for merging the face */
 
504
                if(needMajor && /* Test only if major edge is needed */
 
505
                        (edge->v1 == v2 || /* Simple test */
 
506
                        /* A more complex test */
 
507
                        (edge->v1->windowPosX == v2->windowPosX &&
 
508
                         edge->v1->windowPosY == v2->windowPosY &&
 
509
                         edge->v1->rasterPosZ == v2->rasterPosZ))) {
 
510
                        /* Yepp. That's the new major */
 
511
                        majorEdge = edge;
 
512
                        majorEdge->rightFace = face;
 
513
                        majorEdge->flags  |= B3D_EDGE_RIGHT_MAJOR;
 
514
                        
 
515
                        if(b3dDoStats) nFaces++;
 
516
 
 
517
                        if(!needMinor) {
 
518
                                b3dAdjustFaceEdges(face, majorEdge, minorEdge);
 
519
                                return; /* done */
 
520
                        }
 
521
                        needMajor = 0;
 
522
                } else if(needMinor && /* Test only if minor edge is needed */
 
523
                        (edge->v1 == v1 || /* Simple test */
 
524
                        /* A more complex test */
 
525
                        (edge->v1->windowPosX == v1->windowPosX &&
 
526
                         edge->v1->windowPosY == v1->windowPosY &&
 
527
                         edge->v1->rasterPosZ == v1->rasterPosZ))) {
 
528
                        /* Yepp. That's the new minor */
 
529
                        minorEdge = edge;
 
530
                        minorEdge->rightFace = face;
 
531
                        minorEdge->flags |= B3D_EDGE_CONTINUE_RIGHT;
 
532
                        if(!needMajor) {
 
533
                                b3dAdjustFaceEdges(face, majorEdge, minorEdge);
 
534
                                return; /* done */
 
535
                        }
 
536
                        needMinor = 0;
 
537
                }
 
538
        }
 
539
        /*  Need to create new edges.
 
540
                Note: index already points to the right insertion point in addedEdges 
 
541
        */
 
542
        if(needMajor) {
 
543
                int nLines = (v2->windowPosY >> B3D_FixedToIntShift) - (v0->windowPosY >> B3D_FixedToIntShift);
 
544
 
 
545
                if(!nLines) {
 
546
                        /* The major edge is horizontal. */
 
547
                        b3dFreeFace(faceAlloc, face);
 
548
                        return;
 
549
                }
 
550
                b3dAllocEdge(edgeAlloc, majorEdge);
 
551
                if(b3dDebug)
 
552
                        if(!majorEdge) b3dAbort("Edge allocation failed");
 
553
                majorEdge->v0 = v0;
 
554
                majorEdge->v1 = v2;
 
555
                majorEdge->nLines = nLines;
 
556
                majorEdge->leftFace = face;
 
557
                majorEdge->rightFace = NULL;
 
558
                majorEdge->flags  |= B3D_EDGE_LEFT_MAJOR;
 
559
                b3dInitializeEdge(majorEdge);
 
560
                if(b3dDoStats) nFaces++;
 
561
        }
 
562
 
 
563
        if(needMinor) {
 
564
                int nLines = (v1->windowPosY >> B3D_FixedToIntShift) - (v0->windowPosY >> B3D_FixedToIntShift);
 
565
 
 
566
                if(!nLines) {
 
567
                        /* Note: If the (upper) minor edge is horizontal, use the lower one.
 
568
                           Note: The lower edge cannot be horizontal if the major edge isn't
 
569
                        */
 
570
                        if(needMajor) {
 
571
                                b3dAddEdgeBeforeIndex(addedEdges, majorEdge, index);
 
572
                        }
 
573
                        minorEdge = b3dAddLowerEdgeFromFace(face,NULL);
 
574
 
 
575
                        if(b3dDebug)
 
576
                                if(!minorEdge || minorEdge->nLines == 0)
 
577
                                        b3dAbort("minor edge is horizontal");
 
578
 
 
579
                        b3dAdjustFaceEdges(face, majorEdge, minorEdge);
 
580
                        return;
 
581
                }
 
582
 
 
583
                b3dAllocEdge(edgeAlloc, minorEdge);
 
584
 
 
585
                if(b3dDebug)
 
586
                        if(!minorEdge) b3dAbort("Edge allocation failed");
 
587
 
 
588
                minorEdge->v0 = v0;
 
589
                minorEdge->v1 = v1;
 
590
                minorEdge->nLines = nLines;
 
591
                minorEdge->leftFace = face;
 
592
                minorEdge->rightFace = NULL;
 
593
                minorEdge->flags  |= B3D_EDGE_CONTINUE_LEFT;
 
594
                b3dInitializeEdge(minorEdge);
 
595
        }
 
596
 
 
597
        /* Add the newly created edges to addedEdges */
 
598
        if(needMinor && needMajor) {
 
599
                b3dAdd2EdgesBeforeIndex(addedEdges, majorEdge, minorEdge, index);
 
600
        } else if(needMajor) {
 
601
                b3dAddEdgeBeforeIndex(addedEdges, majorEdge, index);
 
602
        } else {
 
603
                b3dAddEdgeBeforeIndex(addedEdges, minorEdge, index);
 
604
        }
 
605
        b3dAdjustFaceEdges(face, majorEdge, minorEdge);
 
606
}
 
607
 
 
608
 
 
609
/* b3dRemoveAETEdge:
 
610
        Remove the given edge from the AET.
 
611
        NOTE: May cause allocation of two edges!
 
612
*/
 
613
/* INLINE b3dRemoveAETEdge(aet, edge, yValue, aetPos) */
 
614
void b3dRemoveAETEdge(B3DActiveEdgeTable *aet, B3DPrimitiveEdge *edge, int yValue, int aetPos)
 
615
{
 
616
        /* Remove edge and add lower edges if necessary */
 
617
        int j;
 
618
        B3DPrimitiveEdge **aetData = aet->data;
 
619
 
 
620
        assert(aetData[aetPos] == edge);
 
621
 
 
622
        if(b3dDebug)
 
623
                if( (edge->v1->windowPosY >> B3D_FixedToIntShift) != yValue )
 
624
                        b3dAbort("Edge exceeds range");
 
625
 
 
626
        /* Remove the edge and adjust the stuff */
 
627
        for(j=aetPos+1; j < aet->size; j++) aetData[j-1] = aetData[j];
 
628
        aet->size--;
 
629
        /* Add new lower edges */
 
630
        if(edge->flags & B3D_EDGE_CONTINUE_LEFT) {
 
631
                b3dAddLowerEdgeFromFace(edge->leftFace, edge);
 
632
        }
 
633
        if(edge->flags & B3D_EDGE_CONTINUE_RIGHT) {
 
634
                b3dAddLowerEdgeFromFace(edge->rightFace, edge);
 
635
        }
 
636
        if(edge->flags & B3D_EDGE_LEFT_MAJOR) {
 
637
                /* Free left face */
 
638
                b3dFreeAttrib(attrAlloc, edge->leftFace);
 
639
                b3dFreeFace(faceAlloc, edge->leftFace);
 
640
                if(b3dDoStats) nFaces--;
 
641
        }
 
642
        if(edge->flags & B3D_EDGE_RIGHT_MAJOR) {
 
643
                /* Free right face */
 
644
                b3dFreeAttrib(attrAlloc, edge->rightFace);
 
645
                b3dFreeFace(faceAlloc, edge->rightFace);
 
646
                if(b3dDoStats) nFaces--;
 
647
        }
 
648
        /* And free old edge */
 
649
        b3dFreeEdge(edgeAlloc, edge);
 
650
}
 
651
/* --INLINE-- */
 
652
 
 
653
/* b3dMergeAETEdgesFrom:
 
654
        Merge the edges from the given source into the AET.
 
655
*/
 
656
void b3dMergeAETEdgesFrom(B3DActiveEdgeTable *aet, B3DPrimitiveEdgeList *src)
 
657
{
 
658
        int srcIndex, aetIndex, outIndex, i;
 
659
        B3DPrimitiveEdge *srcEdge, *aetEdge;
 
660
 
 
661
        assert(aet);
 
662
        assert(src);
 
663
        assert(src->size);
 
664
        assert(aet->size + src->size <= aet->max);
 
665
 
 
666
        if(!aet->size) {
 
667
                for(i=0; i<src->size; i++) aet->data[i] = src->data[i];
 
668
                aet->size += src->size;
 
669
                return;
 
670
        }
 
671
 
 
672
        /* Merge the input by stepping backwards through the aet and checking each edge */
 
673
        outIndex = aet->size + src->size - 1;
 
674
        srcIndex = src->size-1;
 
675
        aetIndex = aet->size-1;
 
676
        srcEdge = src->data[srcIndex];
 
677
        aetEdge = aet->data[aetIndex];
 
678
        aet->size += src->size;
 
679
        while(1) {
 
680
                if(srcEdge->xValue >= aetEdge->xValue) {
 
681
                        /* output srcEdge */
 
682
                        aet->data[outIndex--] = srcEdge;
 
683
                        if(!srcIndex--) return;
 
684
                        srcEdge = src->data[srcIndex];
 
685
                } else {
 
686
                        /* output aetEdge */
 
687
                        aet->data[outIndex--] = aetEdge;
 
688
                        if(!aetIndex--) {
 
689
                                for(i=0; i <= srcIndex; i++) aet->data[i] = src->data[i];
 
690
                                return;
 
691
                        }
 
692
                        aetEdge = aet->data[aetIndex];
 
693
                }
 
694
        }
 
695
}
 
696
 
 
697
/* INLINE b3dAdvanceAETEdge(edge, aetData, aetStart) */
 
698
void b3dAdvanceAETEdge(B3DPrimitiveEdge *edge,
 
699
                                        B3DPrimitiveEdge **aetData,
 
700
                                        int aetStart)
 
701
{
 
702
        /* Advance to next scan line */
 
703
        edge->zValue += edge->zIncrement;
 
704
        edge->xValue += edge->xIncrement;
 
705
        /* Check if AET sort order is okay */
 
706
        if(aetStart && aetData[aetStart-1]->xValue > edge->xValue) {
 
707
                /* Must resort rightEdge */
 
708
                int xValue = edge->xValue;
 
709
                int j = aetStart;
 
710
                /* Move the edge left */
 
711
                while(j>0 && aetData[j-1]->xValue > xValue) {
 
712
                        aetData[j] = aetData[j-1];
 
713
                        j--;
 
714
                }
 
715
                aetData[j] = edge;
 
716
        }
 
717
}
 
718
/* --INLINE-- */
 
719
 
 
720
/*************************************************************/
 
721
/*************************************************************/
 
722
/*************************************************************/
 
723
#ifdef DEBUG
 
724
double zValueAt(B3DPrimitiveFace *face, double xValue, double yValue)
 
725
{
 
726
        return 
 
727
                (face->v0->rasterPosZ +
 
728
                        (((double)xValue - face->v0->rasterPosX) * face->dzdx) +
 
729
                        (((double)yValue - face->v0->rasterPosY) * face->dzdy));
 
730
}
 
731
#else
 
732
#define zValueAt(face, xValue, yValue) \
 
733
                ((face)->v0->rasterPosZ + \
 
734
                        (((double)(xValue) - (face)->v0->rasterPosX) * (face)->dzdx) +\
 
735
                        (((double)(yValue) - (face)->v0->rasterPosY) * (face)->dzdy))
 
736
#endif
 
737
 
 
738
/*************************************************************/
 
739
/*************************************************************/
 
740
/*************************************************************/
 
741
 
 
742
int b3dComputeIntersection(B3DPrimitiveFace *frontFace, 
 
743
                                                   B3DPrimitiveFace *backFace, 
 
744
                                                   int yValue, 
 
745
                                                   int errorValue)
 
746
{
 
747
        double dx1 = frontFace->rightEdge->xValue - frontFace->leftEdge->xValue;
 
748
        double dz1 = frontFace->rightEdge->zValue - frontFace->leftEdge->zValue;
 
749
        double dx2 = backFace->rightEdge->xValue - backFace->leftEdge->xValue;
 
750
        double dz2 = backFace->rightEdge->zValue - backFace->leftEdge->zValue;
 
751
        double px = backFace->leftEdge->xValue - frontFace->leftEdge->xValue;
 
752
        double pz = backFace->leftEdge->zValue - frontFace->leftEdge->zValue;
 
753
        double det = (dx1 * dz2) - (dx2 * dz1);
 
754
        if(det == 0.0) return errorValue;
 
755
        { 
 
756
                double det2 = ((px * dz2) - (pz * dx2)) / det;
 
757
                return frontFace->leftEdge->xValue + (int)(dx1 * det2);
 
758
        }
 
759
        /* not reached */
 
760
}
 
761
 
 
762
/* b3dCheckIntersectionOfFaces:
 
763
        Compute the possible intersection of frontFace and backFace.
 
764
        Store the result in nextIntersection if it is before any other
 
765
        intersection. Return true if other intersections tests should
 
766
        be performed, false otherwise.
 
767
*/
 
768
int b3dCheckIntersectionOfFaces(B3DPrimitiveFace *frontFace,
 
769
                                                                 B3DPrimitiveFace *backFace,
 
770
                                                                 int yValue,
 
771
                                                                 B3DPrimitiveEdge *leftEdge,
 
772
                                                                 B3DPrimitiveEdge *nextIntersection)
 
773
{
 
774
        double frontZ, backZ;
 
775
        int xValue, rightX;
 
776
 
 
777
        /* Check if the backFace is completely behind the front face */
 
778
        if(backFace->minZ >= frontFace->maxZ) return 0; /* abort */
 
779
 
 
780
        /* Check if front and back face share any edges */
 
781
        if(frontFace->leftEdge == backFace->leftEdge) return 1; /* proceed */
 
782
        if(frontFace->rightEdge == backFace->rightEdge) return 1; /* proceed */
 
783
 
 
784
        /* Check if either front or back face are less than 1 pixel wide */
 
785
        if( (frontFace->leftEdge->xValue >> B3D_FixedToIntShift) ==
 
786
                (frontFace->rightEdge->xValue >> B3D_FixedToIntShift)) return 0; /* abort */
 
787
        if( (backFace->leftEdge->xValue >> B3D_FixedToIntShift) ==
 
788
                (backFace->rightEdge->xValue >> B3D_FixedToIntShift)) return 1; /* proceed */
 
789
 
 
790
        /* Choose the right x value of either front or back face,
 
791
                whichever is less (this is so we sample inside both faces) */
 
792
        if(frontFace->rightEdge->xValue <= backFace->rightEdge->xValue) {
 
793
                rightX = frontFace->rightEdge->xValue;
 
794
                frontZ = frontFace->rightEdge->zValue;
 
795
                backZ = zValueAt(backFace, rightX * B3D_FixedToFloat, yValue);
 
796
        } else {
 
797
                rightX = backFace->rightEdge->xValue;
 
798
                backZ = backFace->rightEdge->zValue;
 
799
                frontZ = zValueAt(frontFace, rightX * B3D_FixedToFloat, yValue);
 
800
        }
 
801
 
 
802
        if(backZ < frontZ) {
 
803
                /* possible intersection found */
 
804
                xValue = b3dComputeIntersection(frontFace, backFace, yValue, leftEdge->xValue);
 
805
                if(xValue > rightX) xValue = rightX;
 
806
                /* Ignore intersections at or before the leftEdge's x value. Important. */
 
807
                if((xValue >> B3D_FixedToIntShift) <= (leftEdge->xValue >> B3D_FixedToIntShift))
 
808
                        xValue = ((leftEdge->xValue >> B3D_FixedToIntShift) + 1) << B3D_IntToFixedShift;
 
809
                if(xValue < nextIntersection->xValue) {
 
810
                        nextIntersection->xValue = xValue;
 
811
                        nextIntersection->leftFace = frontFace;
 
812
                        nextIntersection->rightFace = backFace;
 
813
                }
 
814
        }
 
815
        return 1;
 
816
}
 
817
 
 
818
/* b3dAdjustIntersections:
 
819
        Compute the possible intersections of the current front face
 
820
        with all active faces. Store the next intersection if any.
 
821
*/
 
822
/* INLINE b3dAdjustIntersections(fillList, yValue, topEdge, nextIntersection) */
 
823
void b3dAdjustIntersections(B3DFillList *fillList,
 
824
                                                        int yValue,
 
825
                                                        B3DPrimitiveEdge *topEdge,
 
826
                                                        B3DPrimitiveEdge *nextIntersection)
 
827
{
 
828
        B3DPrimitiveFace *frontFace = fillList->firstFace;
 
829
        if(frontFace) {
 
830
                B3DPrimitiveFace *backFace = frontFace->nextFace;
 
831
                int proceed = 1;
 
832
                while(backFace && proceed) {
 
833
                        proceed = b3dCheckIntersectionOfFaces(frontFace, backFace, yValue, topEdge, nextIntersection);
 
834
                        backFace = backFace->nextFace;
 
835
                }
 
836
        }
 
837
}
 
838
/* --INLINE-- */
 
839
 
 
840
/*************************************************************/
 
841
/*************************************************************/
 
842
/*************************************************************/
 
843
 
 
844
void b3dValidateFillList(B3DFillList *list)
 
845
{
 
846
        B3DPrimitiveFace *firstFace = list->firstFace;
 
847
        B3DPrimitiveFace *lastFace = list->lastFace;
 
848
        B3DPrimitiveFace *face;
 
849
 
 
850
        if(!firstFace && !lastFace) return;
 
851
        if(firstFace->prevFace)
 
852
                b3dAbort("Bad fill list");
 
853
        if(lastFace->nextFace)
 
854
                b3dAbort("Bad fill list");
 
855
        face = firstFace;
 
856
        while(face != lastFace)
 
857
                face = face->nextFace;
 
858
        /* Validate sort order */
 
859
        if(firstFace == lastFace)
 
860
                return; /* 0 or 1 element */
 
861
        face = firstFace->nextFace;
 
862
        while(face->nextFace) {
 
863
                if(face->minZ > face->nextFace->minZ)
 
864
                        b3dAbort("Fill list sorting problem");
 
865
                face = face->nextFace;
 
866
        }
 
867
}
 
868
 
 
869
/* INLINE b3dAddFirstFill(fillList, aFace) */
 
870
void b3dAddFirstFill(B3DFillList *fillList, B3DPrimitiveFace *aFace)
 
871
{
 
872
        B3DPrimitiveFace *firstFace = fillList->firstFace;
 
873
        if(firstFace)
 
874
                firstFace->prevFace = aFace;
 
875
        else
 
876
                fillList->lastFace = aFace;
 
877
        aFace->nextFace = firstFace;
 
878
        aFace->prevFace = NULL;
 
879
        fillList->firstFace = aFace;
 
880
        if(b3dDebug) b3dValidateFillList(fillList);
 
881
}
 
882
/* --INLINE-- */
 
883
 
 
884
/* INLINE b3dAddLastFill(fillList, aFace) */
 
885
void b3dAddLastFill(B3DFillList *fillList, B3DPrimitiveFace *aFace)
 
886
{
 
887
        B3DPrimitiveFace *lastFace = fillList->lastFace;
 
888
        if(lastFace)
 
889
                lastFace->nextFace = aFace;
 
890
        else
 
891
                fillList->firstFace = aFace;
 
892
        aFace->prevFace = lastFace;
 
893
        aFace->nextFace = NULL;
 
894
        fillList->lastFace = aFace;
 
895
        if(b3dDebug) b3dValidateFillList(fillList);
 
896
}
 
897
/* --INLINE-- */
 
898
 
 
899
/* INLINE b3dRemoveFill(fillList, aFace) */
 
900
void b3dRemoveFill(B3DFillList *fillList, B3DPrimitiveFace *aFace)
 
901
{
 
902
        if(b3dDebug) b3dValidateFillList(fillList);
 
903
        if(aFace->prevFace)
 
904
                aFace->prevFace->nextFace = aFace->nextFace;
 
905
        else
 
906
                fillList->firstFace = aFace->nextFace;
 
907
        if(aFace->nextFace)
 
908
                aFace->nextFace->prevFace = aFace->prevFace;
 
909
        else
 
910
                fillList->lastFace = aFace->prevFace;
 
911
}
 
912
/* --INLINE-- */
 
913
 
 
914
/* INLINE b3dInsertBeforeFill(fillList, aFace, otherFace) */
 
915
void b3dInsertBeforeFill(B3DFillList *fillList, B3DPrimitiveFace *aFace, B3DPrimitiveFace *otherFace)
 
916
{
 
917
        assert(otherFace != fillList->firstFace);
 
918
 
 
919
        aFace->nextFace = otherFace;
 
920
        aFace->prevFace = otherFace->prevFace;
 
921
        aFace->prevFace->nextFace = aFace;
 
922
        otherFace->prevFace = aFace;
 
923
        if(b3dDebug) b3dValidateFillList(fillList);
 
924
}
 
925
/* --INLINE-- */
 
926
 
 
927
/* INLINE b3dAddFrontFill(fillList, aFace) */
 
928
void b3dAddFrontFill(B3DFillList *fillList, B3DPrimitiveFace *aFace)
 
929
{
 
930
        B3DPrimitiveFace *firstFace = fillList->firstFace;
 
931
        if(firstFace != fillList->lastFace) {
 
932
                /* Meaning that we must find the new position for the old front face */
 
933
                B3DPrimitiveFace *backFace = firstFace->nextFace;
 
934
                float minZ = firstFace->minZ;
 
935
 
 
936
                while(backFace && backFace->minZ < minZ)
 
937
                        backFace = backFace->nextFace;
 
938
 
 
939
                /* Insert firstFace before backFace */
 
940
                if(firstFace->nextFace != backFace) {
 
941
                        B3DPrimitiveFace *tempFace = firstFace;
 
942
 
 
943
                        b3dRemoveFill(fillList, tempFace);
 
944
                        if(backFace) {
 
945
                                b3dInsertBeforeFill(fillList, tempFace, backFace);
 
946
                        } else {
 
947
                                b3dAddLastFill(fillList, tempFace);
 
948
                        }
 
949
                }
 
950
        }
 
951
        b3dAddFirstFill(fillList, aFace);
 
952
        if(b3dDebug) b3dValidateFillList(fillList);
 
953
}
 
954
/* --INLINE-- */
 
955
 
 
956
/* INLINE b3dAddBackFill(fillList, aFace) */
 
957
void b3dAddBackFill(B3DFillList *fillList, B3DPrimitiveFace *aFace)
 
958
{
 
959
        B3DPrimitiveFace *firstFace = fillList->firstFace;
 
960
        B3DPrimitiveFace *lastFace = fillList->lastFace;
 
961
        B3DPrimitiveFace *face;
 
962
        float minZ = aFace->minZ;
 
963
 
 
964
        assert(firstFace);
 
965
 
 
966
        if(firstFace == lastFace || minZ >= lastFace->minZ) {
 
967
                b3dAddLastFill(fillList, aFace);
 
968
        } else {
 
969
                /* Try an estimation on how to search */
 
970
                if(minZ <= (firstFace->minZ + lastFace->minZ) * 0.5) {
 
971
                        /* search front to back */
 
972
                        face = firstFace->nextFace;
 
973
                        while(face->minZ < minZ) face = face->nextFace;
 
974
                } else {
 
975
                        /* search back to front */
 
976
                        face = lastFace->prevFace; /* already checked if lastFace->minZ <= minZ */
 
977
                        while(face->minZ > minZ) face = face->prevFace;
 
978
                        face = face->nextFace;
 
979
                }
 
980
                b3dInsertBeforeFill(fillList, aFace, face);
 
981
        }
 
982
        if(b3dDebug) b3dValidateFillList(fillList);
 
983
}
 
984
/* --INLINE-- */
 
985
 
 
986
/* INLINE b3dCleanupFill(fillList) */
 
987
void b3dCleanupFill(B3DFillList *fillList)
 
988
{
 
989
        B3DPrimitiveFace *firstFace = fillList->firstFace;
 
990
 
 
991
        while(firstFace) {
 
992
                firstFace->flags ^= B3D_FACE_ACTIVE;
 
993
                firstFace = firstFace->nextFace;
 
994
        }
 
995
        fillList->firstFace = fillList->lastFace = NULL;
 
996
}
 
997
/* --INLINE-- */
 
998
 
 
999
void b3dSearchForNewTopFill(B3DFillList *fillList, int scaledX, int yValue)
 
1000
{
 
1001
        B3DPrimitiveFace *topFace = fillList->firstFace;
 
1002
 
 
1003
        if(b3dDebug) b3dValidateFillList(fillList);
 
1004
        if(topFace) { /* only if there is any */
 
1005
                B3DPrimitiveFace *face = topFace->nextFace;
 
1006
                double xValue = scaledX * B3D_FixedToFloat;
 
1007
                double topZ = zValueAt(topFace, xValue, yValue);
 
1008
 
 
1009
                /* Note: since the list is ordered we need only to search until face->minZ >= topZ */
 
1010
                while(face && face->minZ <= topZ) {
 
1011
                        double faceZ = zValueAt(face, xValue, yValue);
 
1012
                        if(faceZ < topZ) {
 
1013
                                topZ = faceZ;
 
1014
                                topFace = face;
 
1015
                        }
 
1016
                        face = face->nextFace;
 
1017
                }
 
1018
                /* and move the guy to front */
 
1019
                b3dRemoveFill(fillList, topFace);
 
1020
                b3dAddFrontFill(fillList, topFace);
 
1021
        }
 
1022
}
 
1023
 
 
1024
/* INLINE b3dToggleTopFills(fillList, edge, yValue) */
 
1025
void b3dToggleTopFills(B3DFillList *fillList, B3DPrimitiveEdge *edge, int yValue)
 
1026
{
 
1027
        B3DPrimitiveFace *leftFace = edge->leftFace;
 
1028
        B3DPrimitiveFace *rightFace = edge->rightFace;
 
1029
        if(b3dDebug) b3dValidateFillList(fillList);
 
1030
        assert(leftFace != rightFace);
 
1031
        if(rightFace) {
 
1032
                int xorMask = leftFace->flags ^ rightFace->flags;
 
1033
                if(xorMask & B3D_FACE_ACTIVE) {
 
1034
                        if(leftFace->flags & B3D_FACE_ACTIVE) {
 
1035
                                b3dRemoveFill(fillList, leftFace);
 
1036
                                b3dAddFrontFill(fillList, rightFace);
 
1037
                        } else {
 
1038
                                b3dRemoveFill(fillList, rightFace);
 
1039
                                b3dAddFrontFill(fillList, leftFace);
 
1040
                        }
 
1041
                } else {
 
1042
                        if(leftFace->flags & B3D_FACE_ACTIVE) {
 
1043
                                b3dRemoveFill(fillList, leftFace);
 
1044
                                b3dRemoveFill(fillList, rightFace);
 
1045
                                b3dSearchForNewTopFill(fillList, edge->xValue, yValue);
 
1046
                        } else {
 
1047
                                if(leftFace->dzdx <= rightFace->dzdx) {
 
1048
                                        b3dAddFrontFill(fillList, leftFace);
 
1049
                                        b3dAddBackFill(fillList, rightFace);
 
1050
                                } else {
 
1051
                                        b3dAddFrontFill(fillList, rightFace);
 
1052
                                        b3dAddBackFill(fillList, leftFace);
 
1053
                                }
 
1054
                        }
 
1055
                }
 
1056
                leftFace->flags ^= B3D_FACE_ACTIVE;
 
1057
                rightFace->flags ^= B3D_FACE_ACTIVE;
 
1058
        } else {
 
1059
                if(leftFace->flags & B3D_FACE_ACTIVE) {
 
1060
                        b3dRemoveFill(fillList, leftFace);
 
1061
                        b3dSearchForNewTopFill(fillList, edge->xValue, yValue);
 
1062
                } else {
 
1063
                        b3dAddFrontFill(fillList, leftFace);
 
1064
                }
 
1065
                leftFace->flags ^= B3D_FACE_ACTIVE;
 
1066
        }
 
1067
        if(b3dDebug) b3dValidateFillList(fillList);
 
1068
}
 
1069
/* --INLINE-- */
 
1070
 
 
1071
/* INLINE b3dToggleBackFills(fillList, edge, yValue, nextIntersection) */
 
1072
void b3dToggleBackFills(B3DFillList *fillList, 
 
1073
                                                B3DPrimitiveEdge *edge, 
 
1074
                                                int yValue,
 
1075
                                                B3DPrimitiveEdge *nextIntersection)
 
1076
{
 
1077
        B3DPrimitiveFace *face = edge->leftFace;
 
1078
        if(b3dDebug) b3dValidateFillList(fillList);
 
1079
        if(face->flags & B3D_FACE_ACTIVE) {
 
1080
                b3dRemoveFill(fillList, face);
 
1081
        } else {
 
1082
                b3dAddBackFill(fillList, face);
 
1083
                b3dCheckIntersectionOfFaces(fillList->firstFace, face, yValue, edge, nextIntersection);
 
1084
        }
 
1085
        face->flags ^= B3D_FACE_ACTIVE;
 
1086
        face = edge->rightFace;
 
1087
        if(face) {
 
1088
                if(face->flags & B3D_FACE_ACTIVE) {
 
1089
                        b3dRemoveFill(fillList, face);
 
1090
                } else {
 
1091
                        b3dAddBackFill(fillList, face);
 
1092
                        b3dCheckIntersectionOfFaces(fillList->firstFace, face, yValue, edge, nextIntersection);
 
1093
                }
 
1094
                face->flags ^= B3D_FACE_ACTIVE;
 
1095
        }
 
1096
        if(b3dDebug) b3dValidateFillList(fillList);
 
1097
}
 
1098
/* --INLINE-- */
 
1099
 
 
1100
/*************************************************************/
 
1101
/*************************************************************/
 
1102
/*************************************************************/
 
1103
 
 
1104
/* INLINE b3dClearSpanBuffer(aet) */
 
1105
void b3dClearSpanBuffer(B3DActiveEdgeTable *aet)
 
1106
{
 
1107
        int i, leftX, rightX;
 
1108
        unsigned int *buffer = currentState->spanBuffer;
 
1109
        if(aet->size && buffer) {
 
1110
                leftX = aet->data[0]->xValue >> B3D_FixedToIntShift;
 
1111
                rightX = aet->data[aet->size-1]->xValue >> B3D_FixedToIntShift;
 
1112
                if(leftX < 0) leftX = 0;
 
1113
                if(rightX >= currentState->spanSize) rightX = currentState->spanSize-1;
 
1114
                for(i=leftX;i<=rightX;i++) buffer[i] = 0;
 
1115
        }
 
1116
}
 
1117
/* --INLINE-- */
 
1118
 
 
1119
/* INLINE b3dDrawSpanBuffer(aet, yValue) */
 
1120
void b3dDrawSpanBuffer(B3DActiveEdgeTable *aet, int yValue)
 
1121
{
 
1122
        int leftX, rightX;
 
1123
        if(aet->size && currentState->spanDrawer) {
 
1124
                leftX = aet->data[0]->xValue >> B3D_FixedToIntShift;
 
1125
                rightX = aet->data[aet->size-1]->xValue >> B3D_FixedToIntShift;
 
1126
                if(leftX < 0) leftX = 0;
 
1127
                if(rightX > currentState->spanSize) rightX = currentState->spanSize;
 
1128
                currentState->spanDrawer(leftX, rightX, yValue);
 
1129
        }
 
1130
}
 
1131
/* --INLINE-- */
 
1132
 
 
1133
/*************************************************************/
 
1134
/*************************************************************/
 
1135
/*************************************************************/
 
1136
/* General failure */
 
1137
#define FAIL(reason,resume) { aet->yValue = yValue; return reason | resume; }
 
1138
#define PROCEED { yValue = aet->yValue; }
 
1139
 
 
1140
/* Failure adding objects */
 
1141
#define FAIL_ADDING(reason) { obj->start = objStart; FAIL(reason, B3D_RESUME_ADDING) }
 
1142
#define PROCEED_ADDING { objStart = obj->start; PROCEED }
 
1143
 
 
1144
/* Failure merging objects */
 
1145
#define FAIL_MERGING(reason) { FAIL(reason, B3D_RESUME_MERGING); }
 
1146
#define PROCEED_MERGING { PROCEED }
 
1147
 
 
1148
/* Failure during paint */
 
1149
#define FAIL_PAINTING(reason) { aet->start = aetStart; aet->leftEdge = leftEdge; aet->rightEdge = rightEdge; FAIL(reason, B3D_RESUME_PAINTING) }
 
1150
#define PROCEED_PAINTING(reason) { aetStart = aet->start; leftEdge = aet->leftEdge; rightEdge = aet->rightEdge; PROCEED }
 
1151
 
 
1152
#define FAIL_UPDATING(reason)
 
1153
 
 
1154
int b3dMainLoop(B3DRasterizerState *state, int stopReason)
 
1155
{
 
1156
        B3DPrimitiveObject *activeStart, *passiveStart;
 
1157
        int yValue, nextObjY, nextEdgeY;
 
1158
        B3DFillList *fillList;
 
1159
        B3DPrimitiveEdge *lastIntersection, *nextIntersection;
 
1160
 
 
1161
 
 
1162
        if(!state)
 
1163
                return B3D_GENERIC_ERROR;
 
1164
 
 
1165
        if(!state->nObjects)
 
1166
                return B3D_NO_ERROR;
 
1167
 
 
1168
        if(b3dValidateAndRemapState(state) != B3D_NO_ERROR)
 
1169
                return B3D_GENERIC_ERROR;
 
1170
 
 
1171
        if(stopReason == B3D_NO_ERROR)
 
1172
                if(b3dSetupObjects(state) != B3D_NO_ERROR)
 
1173
                        return B3D_GENERIC_ERROR;
 
1174
 
 
1175
        if(b3dDebug) {
 
1176
                /* check the sort order of objects */
 
1177
                int i;
 
1178
                for(i=2; i<state->nObjects;i++)
 
1179
                        if(!objSortsBefore(state->objects[i-1], state->objects[i]))
 
1180
                                b3dAbort("Objects not sorted");
 
1181
        }
 
1182
 
 
1183
        currentState = state;
 
1184
        faceAlloc = state->faceAlloc;
 
1185
        edgeAlloc = state->edgeAlloc;
 
1186
        attrAlloc = state->attrAlloc;
 
1187
        addedEdges = state->addedEdges;
 
1188
        fillList = state->fillList;
 
1189
        aet = state->aet;
 
1190
        nextIntersection = aet->nextIntersection;
 
1191
        lastIntersection = aet->lastIntersection;
 
1192
 
 
1193
        if(b3dDoStats) nFaces = 0;
 
1194
 
 
1195
        if(stopReason == B3D_NO_ERROR) {
 
1196
                activeStart = passiveStart = state->objects[0];
 
1197
                yValue = nextEdgeY = nextObjY = passiveStart->minY;
 
1198
        } else {
 
1199
                int resumeCode;
 
1200
                resumeCode = stopReason & B3D_RESUME_MASK;
 
1201
                if(resumeCode == B3D_RESUME_ADDING  ) goto RESUME_ADDING;
 
1202
                if(resumeCode == B3D_RESUME_MERGING ) goto RESUME_MERGING;
 
1203
                if(resumeCode == B3D_RESUME_PAINTING) goto RESUME_PAINTING;
 
1204
                if(resumeCode == B3D_RESUME_UPDATING) goto RESUME_UPDATING;
 
1205
                return B3D_GENERIC_ERROR;
 
1206
        }
 
1207
 
 
1208
        /**** BEGIN MAINLOOP ****/
 
1209
        while(activeStart || passiveStart || aet->size) {
 
1210
 
 
1211
RESUME_ADDING:
 
1212
 
 
1213
                /* STEP 1: Add new objects if necessary */
 
1214
                if(yValue == nextObjY) {
 
1215
                        nextEdgeY = nextObjY;
 
1216
                        while(passiveStart && passiveStart->minY == nextObjY) {
 
1217
                                passiveStart->flags |= B3D_OBJECT_ACTIVE;
 
1218
                                passiveStart = passiveStart->next;
 
1219
                        }
 
1220
                        if(passiveStart)
 
1221
                                nextObjY = passiveStart->minY;
 
1222
                        else
 
1223
                                nextObjY = 99999;
 
1224
                } /* End of adding objects */
 
1225
 
 
1226
 
 
1227
 
 
1228
                /* STEP 2: Add new edges if necessary */
 
1229
                if(yValue == nextEdgeY) {
 
1230
                        B3DPrimitiveObject *obj = activeStart;
 
1231
                        int scaledY = (yValue+1) << B3D_IntToFixedShift;
 
1232
 
 
1233
                        nextEdgeY = nextObjY << B3D_IntToFixedShift;
 
1234
                        while(obj != passiveStart) {
 
1235
                                B3DInputFace *objFaces = obj->faces;
 
1236
                                B3DPrimitiveVertex *objVtx = obj->vertices;
 
1237
                                int objStart = obj->start;
 
1238
                                int objSize = obj->nFaces;
 
1239
                                int tempY;
 
1240
 
 
1241
                                assert(obj->flags & B3D_OBJECT_ACTIVE);
 
1242
 
 
1243
                                while(objStart < objSize && ((tempY = objVtx[objFaces[objStart].i0].windowPosY) < scaledY)) {
 
1244
                                        /* add edges from face at objFaces[objStart] */
 
1245
                                        B3DInputFace *inputFace = objFaces + objStart;
 
1246
                                        B3DPrimitiveFace *face;
 
1247
 
 
1248
                                        /* NOTE: If any of the following fails, 
 
1249
                                                 we can re-enter the main loop later on. */
 
1250
 
 
1251
                                        if(faceAlloc->nFree == 0)
 
1252
                                                FAIL_ADDING(B3D_NO_MORE_FACES);
 
1253
                                        
 
1254
                                        if(edgeAlloc->nFree < 2)
 
1255
                                                FAIL_ADDING(B3D_NO_MORE_EDGES);
 
1256
 
 
1257
                                        if(addedEdges->size+2 > addedEdges->max)
 
1258
                                                FAIL_ADDING(B3D_NO_MORE_ADDED);
 
1259
 
 
1260
                                        /* Allocate a new face and do the initial setup */
 
1261
                                        face = b3dInitializeFace(objVtx + inputFace->i0, 
 
1262
                                                                                         objVtx + inputFace->i1,
 
1263
                                                                                         objVtx + inputFace->i2,
 
1264
                                                                                         obj->texture,
 
1265
                                                                                         obj->flags);
 
1266
                                        if(face) {
 
1267
                                                b3dAddEdgesFromFace(face, yValue);
 
1268
                                        }
 
1269
                                        objStart++;
 
1270
                                }
 
1271
 
 
1272
                                obj->start = objStart;
 
1273
                                if(objStart != objSize) {
 
1274
                                        if(tempY < nextEdgeY) nextEdgeY = tempY;
 
1275
                                } else {
 
1276
                                        /* Unlink obj from activeStart list */
 
1277
                                        obj->flags |= B3D_OBJECT_DONE;
 
1278
                                        if(obj == activeStart) {
 
1279
                                                activeStart = obj->next;
 
1280
                                        } else {
 
1281
                                                obj->prev->next = obj->next;
 
1282
                                        }
 
1283
                                }
 
1284
                                obj = obj->next;
 
1285
                        }
 
1286
 
 
1287
                        nextEdgeY >>= B3D_FixedToIntShift;
 
1288
                } /* End of adding edges */
 
1289
 
 
1290
 
 
1291
                /* STEP 3: Merge all newly added edges from addedList into the AET */
 
1292
                if(addedEdges->size) {
 
1293
RESUME_MERGING:
 
1294
                        if(b3dDebug)
 
1295
                                b3dValidateEdgeOrder(addedEdges);
 
1296
                        /* NOTE: If the following fails, we can re-enter the main loop later on. */
 
1297
                        if(aet->size + addedEdges->size > aet->max)
 
1298
                                FAIL_MERGING(B3D_NO_MORE_AET);
 
1299
                        b3dMergeAETEdgesFrom(aet, addedEdges);
 
1300
                        if(b3dDebug) {
 
1301
                                b3dValidateAETOrder(aet);
 
1302
                        }
 
1303
                        addedEdges->size = 0; /* reset added */
 
1304
                } /* End of merging edges */
 
1305
 
 
1306
 
 
1307
                /********** THIS IS THE CORE LOOP ********/
 
1308
                /* while(yValue < nextEdgeY && !addedEdges->size && aet->size) { */
 
1309
 
 
1310
                        if(b3dDoStats) {
 
1311
                                /* Gather stats */
 
1312
                                if(aet->size > maxEdges) maxEdges = aet->size;
 
1313
                                if(nFaces > maxFaces) maxFaces = nFaces;
 
1314
                        }
 
1315
 
 
1316
                        /* STEP 4: Draw the current span */
 
1317
 
 
1318
                        /* STEP 4a: Clear the span buffer */
 
1319
                        b3dClearSpanBuffer(aet);
 
1320
 
 
1321
                        /* STEP 4b: Scan out the AET */
 
1322
                        if(aet->size) {
 
1323
                                B3DPrimitiveEdge *leftEdge;
 
1324
                                B3DPrimitiveEdge *rightEdge;
 
1325
                                B3DPrimitiveEdge **aetData = aet->data;
 
1326
                                int aetStart = 1;
 
1327
                                int aetSize = aet->size;
 
1328
 
 
1329
                                /* clean up old fills if any */
 
1330
                                b3dCleanupFill(fillList);
 
1331
 
 
1332
                                nextIntersection->xValue = B3D_MAX_X;
 
1333
                                leftEdge = aetData[0];
 
1334
                                while(aetStart < aetSize) {
 
1335
 
 
1336
                                        /*-- Toggle the faces of the top edge (the left edge is always on top) --*/
 
1337
                                        if(leftEdge == lastIntersection) {
 
1338
                                                /* Special case if this is a intersection edge */
 
1339
                                                assert(fillList->firstFace == leftEdge->leftFace);
 
1340
                                                b3dRemoveFill(fillList, leftEdge->rightFace);
 
1341
                                                b3dAddFrontFill(fillList, leftEdge->rightFace);
 
1342
                                        } else {
 
1343
                                                b3dToggleTopFills(fillList, leftEdge, yValue);
 
1344
                                        }
 
1345
                                        /*-- end of toggling top edge faces --*/
 
1346
 
 
1347
                                        /* after getting a new top fill we must adjust intersections */
 
1348
                                        b3dAdjustIntersections(fillList, yValue, leftEdge, nextIntersection);
 
1349
 
 
1350
                                        /*-- search for the next top edge which will be the right edge --*/
 
1351
                                        assert(aetStart < aetSize);
 
1352
                                        if(!fillList->firstFace)
 
1353
                                                rightEdge = aetData[aetStart++]; /* If no current top fill just use the next edge */
 
1354
                                        else while(aetStart < aetSize) { /* Search for the next top edge in the AET */
 
1355
                                                rightEdge = aetData[aetStart];
 
1356
                                                /* If we have an intersection use the intersection edge */
 
1357
                                                if(nextIntersection->xValue <= rightEdge->xValue) {
 
1358
                                                        rightEdge = nextIntersection;
 
1359
                                                        break;
 
1360
                                                }
 
1361
                                                aetStart++;
 
1362
                                                /* Check if this edge is on top */
 
1363
                                                assert(fillList->firstFace);
 
1364
                                                {
 
1365
                                                        double xValue = rightEdge->xValue * B3D_FixedToFloat;
 
1366
                                                        B3DPrimitiveFace *topFace = fillList->firstFace;
 
1367
                                                        if( rightEdge->leftFace == topFace || 
 
1368
                                                                rightEdge->rightFace == topFace || 
 
1369
                                                                rightEdge->zValue < zValueAt(topFace, xValue, yValue))
 
1370
                                                                break; /* rightEdge is on top */
 
1371
                                                }
 
1372
                                                /* If the edge is not on top toggle its (back) fills */
 
1373
                                                b3dToggleBackFills(fillList, rightEdge, yValue, nextIntersection);
 
1374
                                                rightEdge = NULL;
 
1375
                                        }
 
1376
                                        /*-- end of search for next top edge --*/
 
1377
 
 
1378
                                        /*-- Now do the drawing from leftEdge to rightEdge --*/
 
1379
                                        assert(rightEdge);
 
1380
                                        if(fillList->firstFace) {
 
1381
                                                /* Note: We fill *including* leftX and rightX */
 
1382
                                                int leftX = (leftEdge->xValue >> B3D_FixedToIntShift) + 1;
 
1383
                                                int rightX = (rightEdge->xValue >> B3D_FixedToIntShift);
 
1384
                                                B3DPrimitiveFace *topFace = fillList->firstFace;
 
1385
 
 
1386
                                                if(leftX < 0) leftX = 0;
 
1387
                                                if(rightX >= currentState->spanSize) rightX = currentState->spanSize-1;
 
1388
                                                if(leftX <= rightX) {
 
1389
                                                        /* Since we know now that some serious filling operation
 
1390
                                                           will happen, initialize the attributes of the face if
 
1391
                                                           this hasn't been done before. */
 
1392
RESUME_PAINTING:
 
1393
                                                        if( (topFace->flags & B3D_FACE_INITIALIZED) == 0) {
 
1394
                                                                assert(topFace->attributes == NULL);
 
1395
                                                                if(!b3dInitializePass2(topFace))
 
1396
                                                                        FAIL_PAINTING(B3D_NO_MORE_ATTRS);
 
1397
                                                        }
 
1398
                                                        /* And dispatch on the actual pixel drawers */
 
1399
                                                        (*B3D_FILL_FUNCTIONS[(topFace->flags >> B3D_ATTR_SHIFT) & B3D_ATTR_MASK])
 
1400
                                                                (leftX, rightX, yValue, topFace);
 
1401
                                                }
 
1402
                                        }
 
1403
                                        /*-- End of drawing -- */
 
1404
 
 
1405
                                        /* prepare for new top edge */
 
1406
                                        leftEdge = rightEdge;
 
1407
                                        /* use a new intersection if necessary */
 
1408
                                        if(leftEdge == nextIntersection) {
 
1409
                                                nextIntersection = lastIntersection;
 
1410
                                                lastIntersection = leftEdge;
 
1411
                                        }
 
1412
                                        nextIntersection->xValue = B3D_MAX_X;
 
1413
                                }
 
1414
                                /* clean up old fills if any */
 
1415
                                b3dCleanupFill(fillList);
 
1416
                        }
 
1417
 
 
1418
                        /* STEP 4c: Display the pixels from the span buffer */
 
1419
                        b3dDrawSpanBuffer(aet, yValue);
 
1420
 
 
1421
                        /* STEP 5: Go to next y value and update AET entries */
 
1422
                        yValue++;
 
1423
                        if(aet->size) {
 
1424
                                int aetStart = 0;
 
1425
                                int aetSize = aet->size;
 
1426
                                B3DPrimitiveEdge **aetData = aet->data;
 
1427
 
 
1428
                                aetStart = 0;
 
1429
                                while(aetStart < aetSize) {
 
1430
                                        B3DPrimitiveEdge *edge = aetData[aetStart];
 
1431
 
 
1432
                                        if(--(edge->nLines)) {
 
1433
                                                /* Advance to next scan line and resort edge */
 
1434
                                                b3dAdvanceAETEdge(edge, aetData, aetStart);
 
1435
                                                aetStart++;
 
1436
                                        } else {
 
1437
                                                /* Remove edge and add lower edges if necessary */
 
1438
RESUME_UPDATING:
 
1439
                                                if(edgeAlloc->nFree < 2)
 
1440
                                                        FAIL_UPDATING(B3D_NO_MORE_EDGES);
 
1441
                                                if(addedEdges->size + 2 > addedEdges->max)
 
1442
                                                        FAIL_UPDATING(B3D_NO_MORE_ADDED);
 
1443
                                                b3dRemoveAETEdge(aet, edge, yValue, aetStart);
 
1444
                                                aetSize = aet->size;
 
1445
                                                /* Do NOT advance aetStart here */
 
1446
                                        }
 
1447
                                }
 
1448
                        }
 
1449
                        /* End of AET update */
 
1450
                        if(b3dDebug) {
 
1451
                                b3dValidateAETOrder(aet);
 
1452
                        }
 
1453
 
 
1454
                /*}*/ /******** END OF CORE LOOP ********/
 
1455
 
 
1456
        }  /**** END MAINLOOP ****/
 
1457
 
 
1458
        return B3D_NO_ERROR;
 
1459
}