sebastiansylvan 166 Report post Posted April 15, 2006 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)) { 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)); } 0 Share this post Link to post Share on other sites
sebastiansylvan 166 Report post Posted April 15, 2006 Sorry about that. I missed the last couple of lines of the function, which I edited in... 0 Share this post Link to post Share on other sites
sebastiansylvan 166 Report post Posted April 15, 2006 Oh! I should note that the Span.SplitAt(int x) function will split a span in two, returning the second half.sospan0 = span1.SplitAt(4);will modify span1 so that it ends at 4, and span0 will contain the remainder. 0 Share this post Link to post Share on other sites
sebastiansylvan 166 Report post Posted April 15, 2006 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! 0 Share this post Link to post Share on other sites
orbano 130 Report post Posted April 16, 2006 yeah that usually works. when asking for help, and trying to explain the problem, you usually find the problem too :) 0 Share this post Link to post Share on other sites