Archived

This topic is now archived and is closed to further replies.

trzy

2D BSP: Front/Back Test

Recommended Posts

Hello, I''ve written a BSP compiler (for 2D BSP trees made up of line segments) and a renderer to view my worlds in 3D but I''ve noticed some annoying bugs which I can''t seem to track down. They have something to do with my front/back test (testing a line segment to see whether it is in front or behind a splitter). Lines like this are a particular problem: |A | | -> | -----------B | V These lines form an L shape (they are perpendicular.) The arrows indicate which way they are facing (they are only visible from one side.) If line A is chosen as the root line in the above scene, it thinks that line B is BEHIND it for some reason. The intersection happens at t = 0 (I''m using parametric line intersection testing.) Similar problems occur whenever a splitting line falls exactly on t=0 or t=1.0 of some other line. Here is my code (I learned this from Abrash''s book):
static int BuildBSPTree(BSP **tree, LINE *rootline, LINE *lines)
{
    LINE        *frontlist, *backlist, *current;
    float       norm_x, norm_y, numer, denom, tintersect;
    int         error_code;

    /*
     * Calculate normal to the splitter (which is the infinite root line) by
     * exchanging the X and Y lengths of the root line segment and negating
     * the Y
     */

    norm_x = (rootline->y1 - rootline->y2);
    norm_y = -(rootline->x1 - rootline->x2);

    /*
     * Categorize all lines (except the root) as either in front or behind the
     * the root and add them to the appropriate list
     */

    frontlist = backlist = NULL;

    current = lines;
    while (current != NULL)
    {
        if (current == rootline)    // skip the root line
        {
            current = current->next;
            continue;
        }

        /*
         * Calculate the numerator and denominator of the parametric
         * intersection formula
         */

        numer = norm_x * (current->x1 - rootline->x1) + norm_y * (current->y1 - rootline->y1);
        denom = (-norm_x) * (current->x2 - current->x1) + (-norm_y) * (current->y2 - current->y1);

        /*
         * Now see if the splitter and the current line segment intersect
         */

        if (denom == 0) // if denominator is 0, lines are parallel
        {
            LINE    **l;

            if (numer < 0)  // current line is in front of root
                l = &frontlist;
            else            // current line is behind root
                l = &backlist;

            if (AddLineToList(l, current))
            {
                KillList(frontlist);
                KillList(backlist);
                return 1;   // error (BSP tree must be killed by caller)
            }
        }
        else            // there may or may not be an intersection
        {
            LINE    **l;

            tintersect = numer / denom;

            /*
             * NOTE: If we test for <0 || >1, errors occur when we create line
             * segments where both tend and tstart = 1 or 0.
             */


            if ((tintersect <= current->tstart) || (tintersect >= current->tend))
            {
                // NOTE: Testing for numer<0 (as Abrash does) does not seem to
                // work for walls with are perpendicular at the endpoints like an L
                if (numer < 0)  // current line is in front of root
                    l = &frontlist;
                else            // current line is behind root
                    l = &backlist;

                if (AddLineToList(l, current))
                {
                    KillList(frontlist);
                    KillList(backlist);
                    return 1;   // error (BSP tree must be killed by caller)
                }
            }
            else                                    // intersection!
            {
                LINE    *splitline;

                if ((splitline = malloc(sizeof(LINE))) == NULL)
                {
                    KillList(frontlist);
                    KillList(backlist);
                    return 1;
                }

                *splitline = *current;
                
                splitline->id = line_id++;
                splitline->tstart = tintersect;

                splitline->next = current->next;    // insert right after currentline
                current->next = splitline;
              
                current->tend = tintersect;

                if (numer < 0)  // split part is behind of root
                {
                    error_code = AddLineToList(&backlist, splitline);
                    error_code |= AddLineToList(&frontlist, current);
                }
                else            // split part is in front of root
                {
                    error_code = AddLineToList(&frontlist, splitline);
                    error_code |= AddLineToList(&backlist, current);
                }

                if (error_code)
                {
                    KillList(frontlist);
                    KillList(backlist);
                    return 1;   // error (BSP tree must be killed by caller)
                }

                current = current->next;    // advance twice
            }
        }

        current = current->next;
    }

    /*
     * Create a BSP tree node out of the root line and add the front and back
     * lists to it
     */

    error_code = 0;
    if ((*tree = malloc(sizeof(BSP))) != NULL)
    {
        (*tree)->id = rootline->id;

        (*tree)->x1 = rootline->x1;
        (*tree)->y1 = rootline->y1;
        (*tree)->x2 = rootline->x2;
        (*tree)->y2 = rootline->y2;
        (*tree)->tstart = rootline->tstart;
        (*tree)->tend = rootline->tend;

        (*tree)->f = NULL;
        (*tree)->n = NULL;

        if (frontlist != NULL)
        {
            if (BuildBSPTree(&((*tree)->n), frontlist, frontlist))
            {
                KillList(frontlist);
                KillList(backlist);
                return 1;
            }
        }

        if (backlist != NULL)
        {
            if (BuildBSPTree(&((*tree)->f), backlist, backlist))
            {
                KillList(frontlist);
                KillList(backlist);
                return 1;
            }
        }
    }
    else
        error_code = 1; // malloc() failed

    KillList(frontlist);
    KillList(backlist);
        
    return error_code;
}
[/CODE]

Note that ->f is the far side (back) and ->n is the near side (front.)

The "if (tintersect <= current->tstart..." test which determines if a line is NOT split will count T=0 and T=1 as not splitting a line (even though t=0 and t=1 are on the line) because otherwise, errors still occur.

Should I forego this testing method and use something entirely different (such as just calculating unit normals and trying to find the angle between vectors?) 

Or do I have to perform more tests? 

Thanks!    
--- Bart

Share this post


Link to post
Share on other sites
It might have to do with the parametric intersection checking. If I had to do this, I would do it different. I would first find the normal of line A. I would then find the dot product of both points on line B to the normal. We can check here to see if both dot products are the same sign. If so, the lines don't intersect, and line B is either completely in front or in back of line A (if the DPs were positive, it's front; otherwise it's back). If one of the DPs is zero, we know there is an intersection at the point that generated that DP.

Otherwise, find the ratio of one of the dot products to the sum of the absolute values of both dot products (i.e DP1 / (fabs(DP1) + fabs(DP2))). Multiply a unit vector representing line B by this scalar. Add to the starting point of the unit vector. Viola, instant intersection. Or is it? Problem is, it might be a false intersection. You then do a bounding box check with this intersection to line A. If it's false, then it's not a true intersection. However, with BSP trees, splits are also important. This would then be the point on line B where you want to do a split.

I just don't like parametric intersection testing, I just don't Can you tell? :D

P.S If you need any pseudo-code for my method, feel free to ask. It's actually a lot shorter and easier to understand.

[edited by - Zipster on July 14, 2002 12:44:40 AM]

Share this post


Link to post
Share on other sites
I''m not sure I completely understand your method but it sounds similar to 3D line clipping using planes.

The parametric method works out to be very handy in my renderer because having T start and end values really makes storing walls a breeze.

It''s t=0.0 and t=1.0 that cause problems. If I manage to fix one problem (such as the L problem), another one crops up (for example, walls might not be connected in an L shape, but the splitting line of one wall will still hit at t=0 of another wall much further away and that causes problems in determining front-back.)

I think I''ll do some more math on paper because this is really bugging the heck out of me Algorithms often seem easy, but the devil''s in the implementation it seems.


---
Bart

Share this post


Link to post
Share on other sites
Ahh, so the parametric way ties in to the method you store your walls. Hmmm... once you find a true intersection, I''m pretty sure you can still convert that into a T value using a ratio, i.e (distance from start to intersection) / (distance from start to end). But I''m not too familiar with parametric implementation details. I work better with them on paper

Share this post


Link to post
Share on other sites