Swine'z pages

Czech Welcome Guff Coding 3D - Engine Guestbook Links Downloads
 
About author Mail me Mailform
box_en 3D Engine 4 - clipping pyramid and polygon rasterizer box_en
So i'm here again and i have fourth part of our series with myself. Today, i'm about to explain clipping pyramid i mentioned last time and polygon rasterization along. It's slowly beginning to look like simple engine ... with this you could code some space shoot-em up game or tower of hanoi / etc ...
So, where to begin ... as i mentioned before, clipping pyramid is quad of planes, used to clip polygons so the remaining ones (or its parts) are completely in field of view. Sometimes five or six planes are used (for defining minimal and maximal view distance) I will put here some code from previous part, just for completion. You can compute common plane from three points, lying on that plane, using cross product : 


struct Plane {
    float a, b, c, d;
};

struct Vector {
    float x, y, z;
};

#define _Len(A) ((float)sqrt(A.x * A.x + A.y * A.y + A.z * A.z))
// compute length of vector

#define _Normalize(A) {float s = _Len(A); A.x /= s; A.y /= s; A.z /= s; }
// create unit vector (length = 1)

#define _Dot(A,B) (B.x * A.x + A.y * B.y)
// dot product (2 * cos(angle vectors are holding))

#define _Cross(A,B,C) C.x = B.y * A.z - A.y * B.z; \
                      C.y = B.z * A.x - A.z * B.x; \
                      C.z = B.x * A.y - A.x * B.y;
// cross product (vector C, prependicular to both A, B)

Vector u, v, w;

u.x = c.x - a.x;
u.y = c.y - a.y;
u.z = c.z - a.z;
v.x = b.x - a.x;
v.y = b.y - a.y;
v.z = b.z - a.z;
// 2 vectors, lying in single plane
    
_Cross(u, v, w);
_Normalize(w);
// perform cross product to get normal vector
// (prependicular to plane = prependicluar to both vectors)

p_plane->a = w.x;
p_plane->b = w.y;
p_plane->c = w.z;
p_plane->d = -(p_plane->a * a1 + p_plane->b * a2 + p_plane->c * a3);
// compute D - prependicular distance from plane to origin

A bit of explaining ... Plane is plane, given by its normal vector [a b c] and prependicular distance from origin d. Vector is 3-space vector. _Len is length of vector. _Normalize makes vector to be unit (direction is the same, but the length is 1). And eventually _Cross computes cross-product, ie. vector w will be prependicular to both vectors u and v. (u and v lies in our plane, they mustn't be parallel !) It should be clear now. Now back to pyramid - it's structures should look like this : 


struct Plane {
    float a, b, c, d;
};

struct Pyramid {
    Plane p0, p1, p2, p3; 
};

Pyramid pyramid;
// one more global variable to fill

Now, we should know that pyramid should be eligned to our field of view. You can derive it from perspective correction. One point will be in the centre of pyramid [0 0 0], one on side of screen in unit distance (z = 1). In order to be really at the side of screen, it must be : 
       0 = 320 / 2 + (x * z_delta) / z	  	 	(320 will be our resolution)
    -160 = x * z_delta / z		   	  	(we know z = 1)
    -160 = x * z_delta
       x = -160 / z_delta
So - left plane will be lying on three points : [0 0 0] (common for all four), [-160 / z_delta 0 1] and [-160 / z_delta 1 1]. (the y coordinates are simply two different numbers in order to have three different points) With the other planes it's similar. Now, everyone should be able to write this : 


void SetFOV(float n_Width, float n_Height, float f_z_delta, Pyramid *p_pyramid)
{
    float x_right, y_bottom, x_left, y_top;

    x_left = -n_Width / (2 * f_z_delta);
    y_top =  n_Height / (2 * f_z_delta);
    x_right =  n_Width / (2 * f_z_delta);
    y_bottom = -n_Height / (2 * f_z_delta);
    // compute x-s and y-s of edges for z = 1

    SetPlane(&p_pyramid->p0, 0, 0, 0, x_right, 0, 1, x_right, 1, 1);
    SetPlane(&p_pyramid->p1, 0, 0, 0, x_left, 1, 1, x_left, 0, 1);
    SetPlane(&p_pyramid->p2, 0, 0, 0, 0, y_bottom, 1, 1, y_bottom, 1);
    SetPlane(&p_pyramid->p3, 0, 0, 0, 1, y_top, 1, 0, y_top, 1);
    // spimply compute pyramid planes
}

Parameters n_Width and n_Height are dimensions of screen, f_z_delta is perspective distortion constant. I already told you how to compute that, just for sake of completeness : 
    z_delta = n_Width / (tan(psi / 2) * 2);
Where n_Width is width of our image and psi is field of view (propably in radians). You can deduce it from similar triangles.
So, we have our pyramid generated, but what to do with it ? 


enum {
    _Front,
    _Back,
    _Onplane,
    _Split
};

int inline ClassifyVtxPl(Vertex *p_vertex, Plane *p_plane)
{
    float p;

    p = p_plane->a * p_vertex->x + p_plane->b * p_vertex->y +
        p_plane->c * p_vertex->z + p_plane->d;
    // compute plane equation

    if(p > 0) 
        return _Front;
    if(p < 0)
        return _Back;
    return _Onplane;
}

int inline ClassifyFacePl(Face *p_face, Plane *p_plane)
{
    int fn = 0, bn = 0, i;

    for(i = 0; i < 3; i ++){
        switch(ClassifyVtxPl(p_face->vertex[i], p_plane)){
        case _Front:
            fn ++;
            break;
        case _Back:
            bn ++;
            break;
        case _Onplane:
            fn ++;
            bn ++;
            break;
        }
    }

    if(fn == 3)
        return _Front;
    if(bn == 3)
        return _Back;
    return _Split;
}

So. No we can tell if face is in front of, behind or is splitting a plane. But we don't know (ok, some of us ... knows various things) how to split it. Simplest way to divide face is to do it along it's edges. Thus we need edge (= segment) / plane intersection : 


Vertex IntersectSegmentPl(Vertex *p_v1, Vertex *p_v2, Plane *p_plane)
{
    float a, b, t;
    Vertex vertex;

    a = p_plane->a * p_v1->x + p_plane->b * p_v1->y +
        p_plane->c * p_v1->z + p_plane->d;
    b = p_plane->a * p_v2->x + p_plane->b * p_v2->y +
        p_plane->c * p_v2->z + p_plane->d;
    // distances to plane for both points

    if(b - a == 0)
        return *p_v1;
    // we could solve this case, but we should
    // never get such segment to divide (both vertices are
    // on the same side in the same distance)

    t = a / (b - a);
    // compute distance ratio

    vertex.x = p_v1->x + t * (p_v1->x - p_v2->x);
    vertex.y = p_v1->y + t * (p_v1->y - p_v2->y);
    vertex.z = p_v1->z + t * (p_v1->z - p_v2->z);
    vertex.u = p_v1->u + t * (p_v1->u - p_v2->u);
    vertex.v = p_v1->v + t * (p_v1->v - p_v2->v);
    // split segment in that ratio

    return vertex;
}

It was simple and painless ... I hope it's enough to understand. Now, we need a final function that would split polygon. Wai did i say polygon ? Actually yes - after dividing face by first plane the result will be polygon - so we'd need function for dividing face and the same for dividing polygon. I will convert face to poly instead. How does that work ? You take vertex and check if it is in front. If yes, that's ok, simply add it to list. If not, check one before. If the previous one is back aswell, discard it. If it was in front, compute intersection vertex and add it to list. Do that for every vertex and done. Only a little note - you may notice we are also computing new u and v - if there would be associated any lighting values with vertex, we would have to compute them too (now i'm talking about intersection routine above) Now, our polygon splitting routine : 


struct Polygon {
    int n_vertex_num;
    Vertex vertex[7];
};

Polygon SplitPolygon(Polygon *p_poly, Plane *p_plane)
{
    int i, prev, status[7];
    Polygon tmp;

    tmp.n_vertex_num = 0;

    for(i = 0; i < p_poly->n_vertex_num; i ++)
        status[i] = ClassifyVtxPl(&p_poly->vertex[i], p_plane);
    // classify relative possition of all of vertices

    prev = p_poly->n_vertex_num - 1;
    // previous index ...

    for(i = 0; i < p_poly->n_vertex_num; i ++) {
        if(status[i] == _Front) {
            if(status[prev] == _Back) {
                tmp.vertex[tmp.n_vertex_num] =
                    IntersectSegmentPl(&p_poly->vertex[prev],
                    &p_poly->vertex[i], p_plane);
                // add new intersection

                tmp.n_vertex_num ++;
            }
            // edge meet the plane

            tmp.vertex[tmp.n_vertex_num] = p_poly->vertex[i];
            tmp.n_vertex_num ++;
            // vertex is in front of plane
        } else if(status[prev] == _Front) {
            tmp.vertex[tmp.n_vertex_num] =
                IntersectSegmentPl(&p_poly->vertex[prev],
                &p_poly->vertex[i], p_plane);
            // add new intersection

            tmp.n_vertex_num ++;
            // edge meet plane
        }

        prev = i;
        // update previous index
    }

    return tmp;
}

Now just write core function and we can use some fun : 


Polygon Clip_Face(Face *p_face, Pyramid *p_pyramid)
{
    int a, b, c, d, i;
    Polygon poly;

    a = ClassifyFacePl(p_face, &p_pyramid->p0);
    b = ClassifyFacePl(p_face, &p_pyramid->p1);
    c = ClassifyFacePl(p_face, &p_pyramid->p2);
    d = ClassifyFacePl(p_face, &p_pyramid->p3);
    // relative face positions

    poly.n_vertex_num = 3;
    for(i = 0; i < 3; i ++)
        poly.vertex[i] = p_face->vertex[i][0];
    // convert face to polygon ...

    if(a == _Front && b == _Front && c == _Front && d == _Front)
        return poly;
    // face is completely inside pyramid

    if(a == _Back || b == _Back || c == _Back || d == _Back) {
        poly.n_vertex_num = 0;
        return poly;
    }
    // when behind of any of pyramid sides, discard

    if(a == _Split)
        poly = SplitPolygon(&poly, &p_pyramid->p0);
    if(b == _Split)
        poly = SplitPolygon(&poly, &p_pyramid->p1);
    if(c == _Split)
        poly = SplitPolygon(&poly, &p_pyramid->p2);
    if(d == _Split)
        poly = SplitPolygon(&poly, &p_pyramid->p3);
    // split when necessary

    return poly;
}

We have to rewrite our old DrawObject() to cooperate with pyramid : 


void DrawObject(Matrix *m_object, Matrix *m_camera,
    Object *p_object, unsigned __int32 *video)
{
    Face *cur_face, face;
    float tx, ty, tz;
    float x, y, z;    
    Matrix m, im;
    Polygon poly;
    Vertex v[3];
    int i, j;

    face.vertex[0] = &v[0];
    face.vertex[1] = &v[1];
    face.vertex[2] = &v[2];
    // vertices for temporal face

    Matrix_Inverse(m_camera, &m);
    Matrix_Multiply(&m, m_object, &m);
    Matrix_Inverse(&m, &im);
    // calc transformation matrices

    for(i = 0; i < p_object->n_face_num; i ++){
        if((p_object->face[i].normal.c * im[3][2] +
           p_object->face[i].normal.a * im[3][0] +
           p_object->face[i].normal.b * im[3][1] +
           p_object->face[i].normal.d) > 0.1)
            continue;
        // backface culling

        cur_face = &p_object->face[i];
        for(j = 0; j < 3; j ++){
            x = cur_face->vertex[j]->x;
            y = cur_face->vertex[j]->y;
            z = cur_face->vertex[j]->z;
            //
            tx = x * m[0][0] + y * m[1][0] + 
                 z * m[2][0] +     m[3][0];
            ty = x * m[0][1] + y * m[1][1] + 
                 z * m[2][1] +     m[3][1];
            tz = x * m[0][2] + y * m[1][2] + 
                 z * m[2][2] +     m[3][2];
            //
            face.vertex[j]->x = tx;
            face.vertex[j]->y = ty;
            face.vertex[j]->z = tz;
        }

        poly = Clip_Face(&face, &pyramid);
        // clip face by our pyramid

        if(poly.n_vertex_num) {
            // if face pass clipping pyramid, this should be non-zero
            for(j = 0; j < poly.n_vertex_num; j ++) {
                if(poly.vertex[j].z < 0.1) {
                    poly.n_vertex_num = 0;
                    break;
                }
                // when z is too small, toss it away
                // (shouldn't happen when clipping it by pyramid)

                poly.vertex[j].x = (n_Width / 2) + (poly.vertex[j].x *
                    z_delta) / poly.vertex[j].z;
                poly.vertex[j].y = (n_Height / 2) + (poly.vertex[j].y *
                    z_delta) / poly.vertex[j].z;
                // perspective correction
            }

            DrawPolygon(&poly, video);
            // draw poly to screen
        }
    }
}

It's cool and clean, but we could do this better. Now we first transform each face and then clipping. Assume we are in some kind of labyrinth and field of view is 90 degrees. We would see only one quadrant of labyrinth, that's 25% of faces, but we would have to transform them all. Better sollution would be to transform clipping pyramid. (but there will be more polygon vertices to transform - nothing is ideal. but - polygon is up to seven vertices, that's 2.5 times three vertices of face - it will be still better than to transform four times more faces) So, let's transform clipping pyramid : 


void TransformPlane(Plane *p, Matrix m)
{
    p->ta = p->a * m[0][0] + p->b * m[1][1] + p->c * m[1][2];
    p->tb = p->a * m[1][0] + p->b * m[1][1] + p->c * m[0][2];
    p->tc = p->a * m[2][0] + p->b * m[2][1] + p->c * m[2][2];
    p->td = p->d - (p->ta * m[3][0] + p->tb * m[3][1] + p->tc * m[3][2]);
    // používáme transponovanou matici !!!
}
// don't forget to change ClassifyVtxPl() and IntersectSegmentPl() so they're
// using transformed planes (switch a -> ta, b -> tb, c -> tc, d -> td)

If you try to implement this, you'll see it's not working. When you do some computing, you'll find out that you need transponded matrix for transformation !!!
Just to be sure - modified DrawObject() for pyramid transformation : 


void DrawObject(Matrix *m_object, Matrix *m_camera,
    Object *p_object, unsigned __int32 *video)
{
    Face *cur_face, face;
    float tx, ty, tz;
    float x, y, z;    
    Matrix m, im;
    Polygon poly;
    Vertex v[3];
    int i, j;

    face.vertex[0] = &v[0];
    face.vertex[1] = &v[1];
    face.vertex[2] = &v[2];
    // set vertices for our temporal face

    Matrix_Inverse(m_camera, &m);
    Matrix_Multiply(&m, m_object, &m);
    Matrix_Inverse(&m, &im);
    // transformation matrices

    TransformPlane(&pyramid.p0, camera);
    TransformPlane(&pyramid.p1, camera);
    TransformPlane(&pyramid.p2, camera);
    TransformPlane(&pyramid.p3, camera);
    // transform pyramid

    for(i = 0; i < p_object->n_face_num; i ++){
        if((p_object->face[i].normal.c * im[3][2] +
           p_object->face[i].normal.a * im[3][0] +
           p_object->face[i].normal.b * im[3][1] +
           p_object->face[i].normal.d) > 0.1)
            continue;
        // backface culling

        poly = Clip_Face(&p_object->face[i], &pyramid);
        // clip face

        if(!poly.n_vertex_num)
            continue;
        // check if face wasn't culled away by pyramid

        for(j = 0; j < poly.n_vertex_num; j ++) {
            x = cur_face->vertex[j]->x;
            y = cur_face->vertex[j]->y;
            z = cur_face->vertex[j]->z;
            //
            tx = x * m[0][0] + y * m[1][0] + 
                 z * m[2][0] +     m[3][0];
            ty = x * m[0][1] + y * m[1][1] + 
                 z * m[2][1] +     m[3][1];
            tz = x * m[0][2] + y * m[1][2] + 
                 z * m[2][2] +     m[3][2];
            //
            if((poly.vertex[j].z = tz) < 0.1) {
                poly.n_vertex_num = 0;
                break;
            }
            // check all vertices have positive z

            poly.vertex[j].x = (n_Width / 2) + (tx * z_delta) / tz;
            poly.vertex[j].y = (n_Height / 2) + (ty * z_delta) / tz;
            // perspective correction
        }

        if(poly.n_vertex_num)
            DrawPolygon(&poly, video);
            // draw polygon ...
    }
}

... and i promised pyramid and ... rasterization !!
We will use Brensham once again. We will take our polygon, select top and bottom (2d) vertex and (assuming counterclockwise sorted polygon vertices - that will do 3d-studio for us) we can tell which vertices are on left and which are on right side of polygons. We will follow left and right edges at each scanline and simply fill space (line) between them. It's simple again.
Now look at generating edges (note : in good optimalised engine there is no edge structure, you compute edges directly during rasterization, but this is simple to understand) : 


struct Poly_Edge {                            
    int x, y, num, dxdy;            
};

static Poly_Edge left_edge_buff[7];
static Poly_Edge right_edge_buff[7];
static Poly_Edge *p_left_edge;
static Poly_Edge *p_right_edge;
static int n_left_edge_num, n_right_edge_num;

We have Poly_Edge structure - coordinate of it's first point, number of scanlines (= vertical length) and delta-x-per-delta-y. It's change of x coordinate when y increases by 1. Why is that integer ? It can't be enough ! Yes, we could do that float, but we can simply use fixed point. It's simple trick when you multiply float value by 65536 (= 16-bit shift for integer) and voila ! Bottom 16 bits of number contain fractional part of number and the upper 16 integer part. We can simply shift back and have integer. Why that ? It's faster than float, we will use it lots of times ... That was a little delay so back to edge generation : 


int Add_Edge(Vertex *v_cur, Vertex *v_next, Poly_Edge *edge)
{
    float y1, y2;
    int num;

    y1 = (float)ceil(v_cur->y);
    y2 = (float)ceil(v_next->y);
    num = (int)(y2 - y1);

    if(!num)
        return 0;

    edge->dxdy = (int)((v_next->x - v_cur->x) / (v_next->y - v_cur->y) * 65536);
    edge->x = (int)(v_cur->x * 65536 + (y1 - v_cur->y) * edge->dxdy);
    edge->y = (int)y1;
    edge->num = num;
    // compute first x and y, angle (dxdy) and length

    return 1;
}

int Create_Edges(Polygon *p_poly)
{
    int n_bottom, n_top, n_cur;
    float f_min_y;
    float f_max_y;

    n_left_edge_num = 0;
    n_right_edge_num = 0;
    // number of left and right edges

    f_min_y =  0x10000;
    f_max_y = -0x10000;
    n_cur = 0;
    while(n_cur < p_poly->n_vertex_num) {
        if(p_poly->vertex[n_cur].y < f_min_y) {
            f_min_y = p_poly->vertex[n_cur].y;
            n_top = n_cur;
        }
        if(p_poly->vertex[n_cur].y > f_max_y) {
            f_max_y = p_poly->vertex[n_cur].y;
            n_bottom = n_cur;
        }
        n_cur ++;
    }
    // find bottom and top vertex ...

    if((int)ceil(f_min_y) >= (int)ceil(f_max_y))
        return 0;
    // check if it's large enough to rasterize

    n_cur = n_top;
    while(n_cur != n_bottom) {
        if(Add_Edge(&p_poly->vertex[n_cur], &p_poly->vertex[(n_cur + 1) %
           p_poly->n_vertex_num], &right_edge_buff[n_right_edge_num]))
            n_right_edge_num ++;
        n_cur = (n_cur + 1) % p_poly->n_vertex_num;
    }
    // right edges ...

    n_cur = n_bottom;
    while(n_cur != n_top) {
        if(Add_Edge(&p_poly->vertex[(n_cur + 1) % p_poly->n_vertex_num],
           &p_poly->vertex[n_cur], &left_edge_buff[n_left_edge_num]))
            n_left_edge_num ++;
        n_cur = (n_cur + 1) % p_poly->n_vertex_num;
    }
    // left edges ...

    p_left_edge = left_edge_buff + n_left_edge_num - 1;
    p_right_edge = right_edge_buff;

    // pointers to first left and right edge
    return 1;
}

So we have edges and can draw. It would be boring to draw just one color so we will make some advancement. It's flat shading. We will also transform normal vector of face and according to it's z - coordinate we can tell how inclined is that to camera. We will simply multiply our RGB values by transformed normal z and it will look like there's a light in camera : 


void DrawObject(Matrix *m_object, Matrix *m_camera,
    Object *p_object, unsigned __int32 *video, unsigned __int32 color)
{
    unsigned __int32 n_color;
    float tx, ty, tz;
    float x, y, z;    
    Matrix m, im;
    Polygon poly;
    Vertex v[3];
    Face *cur_face, face;
    int i, j;

    face.vertex[0] = &v[0];
    face.vertex[1] = &v[1];
    face.vertex[2] = &v[2];
    // temporal face

    Matrix_Inverse(m_camera, &m);
    Matrix_Multiply(&m, m_object, &m);
    Matrix_Inverse(&m, &im);
    // matrices

    for(i = 0; i < p_object->n_face_num; i ++){
        if((p_object->face[i].normal.c * im[3][2] +
           p_object->face[i].normal.a * im[3][0] +
           p_object->face[i].normal.b * im[3][1] +
           p_object->face[i].normal.d) > 0.1)
            continue;
        // backface culling

        cur_face = &p_object->face[i];
        for(j = 0; j < 3; j ++){
            x = cur_face->vertex[j]->x;
            y = cur_face->vertex[j]->y;
            z = cur_face->vertex[j]->z;
            //
            tx = x * m[0][0] + y * m[1][0] + 
                 z * m[2][0] +     m[3][0];
            ty = x * m[0][1] + y * m[1][1] + 
                 z * m[2][1] +     m[3][1];
            tz = x * m[0][2] + y * m[1][2] + 
                 z * m[2][2] +     m[3][2];
            //
            face.vertex[j]->x = tx;
            face.vertex[j]->y = ty;
            face.vertex[j]->z = tz;
        }

        poly = Clip_Face(&face, &pyramid);
        // clip face

        x = p_object->face[i].normal.a;
        y = p_object->face[i].normal.b;
        z = p_object->face[i].normal.c;
        tx = x * m[0][0] + y * m[1][0] + z * m[2][0];
        ty = x * m[0][1] + y * m[1][1] + z * m[2][1];
        tz = x * m[0][2] + y * m[1][2] + z * m[2][2];
        // transform normal

        x = (float)sqrt(tx * tx + ty * ty + tz * tz);
        // normalize it

        j = abs((int)(tz / x * 255));
        if(j > 255)
            j = 255;
        // calculate brightness from it's z-component
        
        n_color = ((((color & 0xff0000) * j) & 0xff000000) +
                   (((color & 0x00ff00) * j) & 0x00ff0000) +
                   (((color & 0x0000ff) * j) & 0x0000ff00)) >> 8;
        // color processing - unpack R, B a B
        // multiply by brightnes and pack ...

        if(poly.n_vertex_num) { // pokud je face vidět, bude to nenulové číslo
            for(j = 0; j < poly.n_vertex_num; j ++) {
                if(poly.vertex[j].z < 0.1) {
                    poly.n_vertex_num = 0;
                    break;
                }
                // when too near, discard

                poly.vertex[j].x = (n_Width / 2) + (poly.vertex[j].x *
                    z_delta) / poly.vertex[j].z;
                poly.vertex[j].y = (n_Height / 2) + (poly.vertex[j].y *
                    z_delta) / poly.vertex[j].z;
                // perspective correction
            }

            DrawPolygon(&poly, video, n_color);
            // rasterize polygon on screen
        }
    }
}

We aren't using clipping pyramid transformation (excercise for reader :P)) But we slightly jumped over DrawPolygon(poly, video, color). Here it is : 


int DrawPolygon(Polygon *p, unsigned __int32 *video, unsigned __int32 color)
{
    int start_y, left_x, right_x;
    int l, c;

    if(!Create_Edges(p)) 
        return 0;

    start_y = p_right_edge->y;
    left_x = p_left_edge->x;
    right_x = p_right_edge->x;
    // edge properties

    video += n_Width * start_y;
    // set pointer to first raster scanline ...

    while(1) {
        c = left_x >> 16;
        l = right_x >> 16;
        // back to int

        for(; l < c; l ++)
            video[l] = color;
        // fill horizontal segment

        video += n_Width;
        z_buff += n_Width;
        z += dzdy;
        // next scanline ...

        if(-- p_left_edge->num == 0) {
            if(p_left_edge -- == left_edge_buff)
                return 1;
            // end of buffer - polygon was drawn whole
            left_x = p_left_edge->x;
        } else
            left_x += p_left_edge->dxdy;

        if(-- p_right_edge->num == 0) {
            p_right_edge ++;
            right_x = p_right_edge->x;
        } else 
            right_x += p_right_edge->dxdy;
    }

    return 1;
}

Well, i haven't written so much of source code yet ... Now we can draw simple objects, but ve haven't counted on visibility ! The surfaces overlaps according to their order in file ... that's nasty. Easiest way to fix it is to sort them by their distance from camera. (it's called painter's algorithm) You need quite fast method, quicksort is good for that ... It has some disatvantages - faces musn't intersect and there are some issues when sorting faces of different size. (you can see it for example in Tomb Raider I / II game) But now download examples and bye !

    -tHE SWINe-

Tomb Raider 2
Tomb raider 2 - Lara has smaller polygons than floor - left leg shouldn't be visible


flatshaded

 Flat - shading


painter's algorithm + flatshaded

 Painter's algorithm

back


Valid HTML 4.01!
Valid HTML 4.01