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

This topic is 4541 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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: 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))
{
}

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;

while (cur != null)
{
Span curSpan = cur.Value;
if (span.end <= curSpan.start)
{
//Simple case, span is completely to the left of curSpan
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

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

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

//Compute the intersection of the two line equations

//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'
}

}
}
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
}
}
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

// Is there anything left of the right span that should be added?
if (right2.end > tmp.Value.end)
{
}
}
}
}

return;
}
}
// No more nodes to conflict
// So just add it
}



##### Share on other sites
Sorry about that. I missed the last couple of lines of the function, which I edited in...

##### 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 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 on other sites
yeah that usually works. when asking for help, and trying to explain the problem, you usually find the problem too :)

1. 1
2. 2
Rutin
21
3. 3
4. 4
frob
17
5. 5

• 9
• 12
• 9
• 33
• 13
• ### Forum Statistics

• Total Topics
632591
• Total Posts
3007250

×