BSP Traversal

//---------------------------------------------------------------------------------------------
bool traceEye( e_Ray *ray, e_RayState *state )
{
    BSPStackElem    fix_stack[80];
    BSPStackElem    *stack;
    UINT            stack_ptr;
    bool            del_stack;

    BSPNode        *node = state->limitBSP;

    Vector3f    P;
    float        midPlane, lightPos, t, d, dmax, dmin;
    BSPNode        *nearChild, *midChild, *farChild;
    bool        inRanges;
    int            cx, cy, cz;
    BOOL        mid = FALSE;

    if( state->opt->bspDepth <= 40 ) {
        stack = fix_stack;
        del_stack = false;
    } else {
        stack = new BSPStackElem [ state->opt->bspDepth * 2 ];
        del_stack = true;
    }
    stack_ptr = 0;

    while( node )
    {
        node->createChildren( state->opt->bspSize, state->opt->bspDepth,
                            state->opt->bspMethod, node->depth, node->axis );

        while( node->child && !mid )
        {
            switch( node->axis )
            {
            case X_AXIS:
                cx = 0;    cy = 1;    cz = 2;    break;
            case Y_AXIS:
                cx = 1;    cy = 2;    cz = 0;    break;
            case Z_AXIS:
                cx = 2;    cy = 0;    cz = 1;    break;
            }

            inRanges = true;

            midPlane = node->child[0].box.range[cx].max;
            lightPos = ray->pos.arr[cx];

            t = ( midPlane - ray->src.arr[cx] ) * ray->inv_dir.arr[cx];
            if( t <= 0.0f )
                inRanges = false;
            else
            {
                P.arr[cx] = midPlane;
                P.arr[cy] = ray->src.arr[cy] + ray->dir.arr[cy] * t;
                d = P.arr[cy];
                dmax = node->box.range[cy].max;
                dmin = node->box.range[cy].min;
                if( d < dmin || d > dmax )
                    inRanges = false;
                else
                {
                    P.arr[cz] = ray->src.arr[cz] + ray->dir.arr[cz] * t;
                    d = P.arr[cz];
                    dmax = node->box.range[cz].max;
                    dmin = node->box.range[cz].min;
                    if( d < dmin || d > dmax )
                        inRanges = false;
                }
            }

            if( lightPos < midPlane )
            {
                nearChild    = &node->child[0];
                midChild    = node;
                farChild    = &node->child[1];
            }
            else if( lightPos > midPlane )
            {
                nearChild    = &node->child[1];
                midChild    = node;
                farChild    = &node->child[0];
            }
            else if( lightPos == midPlane )
            {
                if( ray->dir.arr[cx] > 0.0f )
                {
                    nearChild    = &node->child[1];
                    midChild    = NULL;
                    farChild    = NULL;
                }
                else
                {
                    nearChild    = &node->child[0];
                    midChild    = NULL;
                    farChild    = NULL;
                }
            }

            node = nearChild;

            node->createChildren( state->opt->bspSize, state->opt->bspDepth,
                            state->opt->bspMethod, node->depth, node->axis );

            if( inRanges )
            {
                if( farChild ) {
                    stack[ stack_ptr ].node = farChild;
                    stack[ stack_ptr ].mid = FALSE;
                    stack[ stack_ptr ].ray_entry = P;
                    ++ stack_ptr;
                }

                if( midChild ) {
                    stack[ stack_ptr ].node = midChild;
                    stack[ stack_ptr ].mid = TRUE;
                    stack[ stack_ptr ].ray_entry = ray->pos;
                    ++ stack_ptr;
                }
            }
        }

        state->limitBSP = node;

        if( intersectEye( ray, state ) ) {
            if( del_stack )
                delete [] stack;
            return true;
        }

        if( stack_ptr != 0 ) {
            -- stack_ptr;
            node = stack[ stack_ptr ].node;
            mid = stack[ stack_ptr ].mid;
            ray->pos = stack[ stack_ptr ].ray_entry;
        } else
            node = NULL;
    }

    if( del_stack )
        delete [] stack;
    return false;
}