Sign in to follow this  
sebastiansylvan

[.net] Need a second perspective to track down annoying bug...

Recommended Posts

Hi. I've been struggling with a bug in my software rasterizer (written in C#) for a while. The particular area is not very hard so even if you know nothing about software rasterizer you can help. I'm beginning to think that I'm missing something quite obvious (like an off-by-one error or something), so I think the best way to find the error is to get someone else to read through the code, try to understand it, and hopefully discover an error along the way. So I'm using a technique called "sorted spans" to resolve visibility (instead of, say, a Z-buffer). The idea is quite simple. To render a triangle it is converted into horizontal "spans". These spans are inserted into a per-scanline sorted list. So each scanline has a list of spans that reside on that scanline. The idea here is that when you insert a new span, you clip it against the existing spans (taking their depth in mind), splitting them up as needed to get a zero-overdraw list of spans sorted by x-value. A span is basically just an integer start and end-point, and 1/z, u/z, v/z, and a gradient (how much each of those vary with x, so we can compute the value of, say, 1/z by adding the x-distance multiplied by the gradient). They are divided by z so that they can be interpolated linearly in screen space, anyway, that's not that important. The algorithm for insertion only needs to worry about the 1/z value (to compare depths of spans at various points). The insertion algorithm doesn't work properly. I've looked through it for hours and I can't find any errors. I probably just need someone fresh to look at it and spot the error (the algorithm isn't that difficult to understand). Most of the spans render fine, but when two spans occupy the same horizontal space one or both of them disappears and the background shines through. Image: HSR error Here's the code
private void AddSpan(ITexture tex, Span span, int scanline)
{
    // Create this span-list if it doesn't exist
    if (!spanBuckets.ContainsKey(tex))
    {
        LinkedList<Span>[] spanBucket = new LinkedList<Span>[height];
        spanBuckets.Add(tex, spanBucket);
    }

    if (spanBuckets[tex][scanline] == null)
        spanBuckets[tex][scanline] = new LinkedList<Span>();

    LinkedList<Span> spanList = spanBuckets[tex][scanline];


    // Insertion algorithm starts here:

    LinkedListNode<Span> cur = spanList.First;
    LinkedListNode<Span> spanNode = new LinkedListNode<Span>(span);

    while (cur != null)
    {
        Span curSpan = cur.Value;
        if (span.end <= curSpan.start)
        {
            //Simple case, span is completely to the left of curSpan
            spanList.AddBefore(cur, new LinkedListNode<Span>(span));
            return;
        }
        else if (span.start >= curSpan.end)
        {
            //Simple case, span is completely to the right of curSpan
            //so we continue traversing...
            cur = cur.Next;
        }
        else
        {
            //span overlaps curSpan somehow

            
            //Insert the new node to the left or to the right
            //depending on its start-coordinate
            LinkedListNode<Span> leftNode, rightNode;

            if (span.start < curSpan.start)
            {
                leftNode = spanNode;
                rightNode = cur;
                spanList.AddBefore(rightNode,leftNode);
            }
            else
            {
                leftNode = cur;
                rightNode = spanNode;
                spanList.AddAfter(leftNode,rightNode);
            }

            //Now we want to clip these two spans against each other
            

            //Compute the intersection of the two line equations
            float denom = rightNode.Value.grad.dOneOverZ_dx - leftNode.Value.grad.dOneOverZ_dx;
            int x = (int)Math.Ceiling((leftNode.Value.OneOverZ-rightNode.Value.OneOverZ+rightNode.Value.grad.dOneOverZ_dx*rightNode.Value.start-leftNode.Value.grad.dOneOverZ_dx*leftNode.Value.start)/denom);
      
   

            //Interpolate left's 1/z to find its value at the beginning of right.
            float leftOneOverZ = leftNode.Value.OneOverZ + leftNode.Value.grad.dOneOverZ_dx*(rightNode.Value.start - leftNode.Value.start);

            if (leftOneOverZ < rightNode.Value.OneOverZ)
            {
                // beginning of right is behind left

                
                if (x > leftNode.Value.end)
                {
                    
                    //left is completely in front of curSpan
                    if (leftNode.Value.end < rightNode.Value.start)
                    {
                        rightNode.Value.SplitAt(leftNode.Value.end);
                    }
                    else
                    {
                        // right is completely covered
                        spanList.Remove(rightNode);
                    }
                   
                }
                else
                {
                    
                    //right intersects left at some point
                    Span left2 = leftNode.Value.SplitAt(x);                                    
                    Span right2 = rightNode.Value.SplitAt(x);
             

                    if (right2.end < left2.end)
                    {
                        //Ther's a bit of the 'left' span left on the right hand side of 'right'
                        spanList.AddAfter(rightNode,new LinkedListNode<Span>(left2.SplitAt(right2.end)));
                    }
                   
                }
            }
            else
            {
                //beginning of right is in front of left
                

                if (x > rightNode.Value.end || x > leftNode.Value.end || x < rightNode.Value.start || x < leftNode.Value.start)
                {   
                         
                    //left is completely behind of right
                    Span left2 = leftNode.Value.SplitAt(rightNode.Value.start);

                    if (left2.end > rightNode.Value.end)
                    {
                        // Add what's left of the left span to the right of the right span
                        spanList.AddAfter(rightNode,new LinkedListNode<Span>(left2.SplitAt(rightNode.Value.end)));
                    }                        
                }
                else
                {   
                  
                    //right intersects left at some point
  
                    // compute the part of 'left' which is left after
                    // inserting the part before 'right'
                    Span left2 = leftNode.Value.SplitAt(rightNode.Value.start);
                    
                    if (x < left2.end)
                    {
                        // chop of right so that only the part before the
                        // intersection remains
                        Span right2 = rightNode.Value.SplitAt(x);
                       

                        // Now insert the second part of left, but split
                        // it at the intersection
                        LinkedListNode<Span> tmp = new LinkedListNode<Span>(left2.SplitAt(x));
                        spanList.AddAfter(rightNode,tmp);

                        // Is there anything left of the right span that should be added?
                        if (right2.end > tmp.Value.end)
                        {
                            spanList.AddAfter(tmp,new LinkedListNode<Span>(right2.SplitAt(tmp.Value.end)));
                        }
                    }                                                      
                }
            }


            


            return;
        }
    }
    // No more nodes to conflict
    // So just add it                
    spanList.AddLast(new LinkedListNode<Span>(span));
}





Share this post


Link to post
Share on other sites
Oh! I should note that the Span.SplitAt(int x) function will split a span in two, returning the second half.

so

span0 = span1.SplitAt(4);

will modify span1 so that it ends at 4, and span0 will contain the remainder.

Share this post


Link to post
Share on other sites
Funny how the brain works. You can think about something really hard and not notice anything. But as soon as you let it go for a second (for instance, by asking someone else for help) you figure it out easily once you look at the problem again.

I found the offending line(s). Thanks to anyone who read it and tried to help!

Share this post


Link to post
Share on other sites
orbano    130
yeah that usually works. when asking for help, and trying to explain the problem, you usually find the problem too :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this