Triangle Scan Conversion
Author
I am trying to write a triangle scan converter that draws any pixels the triangle touches( as opposed to just those that the triangle passes through the center of).
I keep ending up with simething very messy with a bunch of special cases, that still dosen't work in all of them. Is there some clean and easy way to do this i'm missing?
a VERY simple and VERY inefficent way is as follows.
there are basically 3 cases
1: you have a very small triangle and the entire triangle is encaptulated in the pixel. this is a very simple test, just test if any vertex of the triangle is in the pixel.
2: one of the triangle edges intersects with the pixel edge. This second case can be taken care of by traceing rays, this basically a ray to axis aligned box test. (if you want more info on this, I'll post up some math for you)
3: the most comon case is the triangle completely covers the pixel, this is taken care of simply. one highly simple but inefficent way would be to calculate the barycentric coordinate for the center of the pixel, and checking to see if the values are all >0(non-negative).
this method is highly inefficent and I'm just saying one way it could be done. a better way would be to first determin all obvious pixels using the scanline algorithm, then only do test 2 for the pixels that are directly surrounding the pixels you already determined the triangle touched via the scanline algorithm.
Tim
there are basically 3 cases
1: you have a very small triangle and the entire triangle is encaptulated in the pixel. this is a very simple test, just test if any vertex of the triangle is in the pixel.
2: one of the triangle edges intersects with the pixel edge. This second case can be taken care of by traceing rays, this basically a ray to axis aligned box test. (if you want more info on this, I'll post up some math for you)
3: the most comon case is the triangle completely covers the pixel, this is taken care of simply. one highly simple but inefficent way would be to calculate the barycentric coordinate for the center of the pixel, and checking to see if the values are all >0(non-negative).
this method is highly inefficent and I'm just saying one way it could be done. a better way would be to first determin all obvious pixels using the scanline algorithm, then only do test 2 for the pixels that are directly surrounding the pixels you already determined the triangle touched via the scanline algorithm.
Tim
here is a simple solution.
1. take bounding box of your triangle and enlarge it by 0.5 in each direction
2. take every edge of your triangle and move it depending on its normal
direction 0.5 left or right and 0.5 up or down
this way you get 7 edges
4. now rasterize all pixels whose centers lie inside this set of edges
1. take bounding box of your triangle and enlarge it by 0.5 in each direction
2. take every edge of your triangle and move it depending on its normal
direction 0.5 left or right and 0.5 up or down
this way you get 7 edges
4. now rasterize all pixels whose centers lie inside this set of edges
You could adjust the triangle coordinates/ spans so that it works fine with a traditional scan coverter.
Or, you have to generate your spans such that they include all the pixels that the triangle touches.
Maybe I am missing something but it should be simple to cover all the pixels. All you are doing is modifying your fill rule. Instead of top left, it would be top left + bottom right.
If your +ve Y axis runs from top to bottom,
then your spans would run from Y = floor(y_coordinate_of_uppermost_vertex) to ceil(y_coordinate_of_bottommost_vertex), including those two values. Similarly for the X values you would use ceil and floor accordingly so that you would be including the pixel that the edge lands on.
So you should be simply altering the fill rules of a traditional scan converter. Please do post if the suggested methods solve your problem or not. I am interested in this.
Or, you have to generate your spans such that they include all the pixels that the triangle touches.
Maybe I am missing something but it should be simple to cover all the pixels. All you are doing is modifying your fill rule. Instead of top left, it would be top left + bottom right.
If your +ve Y axis runs from top to bottom,
then your spans would run from Y = floor(y_coordinate_of_uppermost_vertex) to ceil(y_coordinate_of_bottommost_vertex), including those two values. Similarly for the X values you would use ceil and floor accordingly so that you would be including the pixel that the edge lands on.
So you should be simply altering the fill rules of a traditional scan converter. Please do post if the suggested methods solve your problem or not. I am interested in this.
Author
Thanks for all the input.
"You could adjust the triangle coordinates/ spans so that it works fine with a traditional scan coverter."
I tried this but the problem is it ends up including a bunch of pixels that aren't in the original triangle,especially in long skinny triangles. They end up streching to near infinity.
But I think biki_'s suggestion would work by keeping the triangle in the bounding box.
"If your +ve Y axis runs from top to bottom,
then your spans would run from Y = floor(y_coordinate_of_uppermost_vertex) to ceil(y_coordinate_of_bottommost_vertex), including those two values. Similarly for the X values you would use ceil and floor accordingly so that you would be including the pixel that the edge lands on."
Things are a little more complicated in scanlines that contain vertices. I end up with alot of special cases depending on which part of the edge is farthest out. But I think this is the way I'll go.
"You could adjust the triangle coordinates/ spans so that it works fine with a traditional scan coverter."
I tried this but the problem is it ends up including a bunch of pixels that aren't in the original triangle,especially in long skinny triangles. They end up streching to near infinity.
But I think biki_'s suggestion would work by keeping the triangle in the bounding box.
"If your +ve Y axis runs from top to bottom,
then your spans would run from Y = floor(y_coordinate_of_uppermost_vertex) to ceil(y_coordinate_of_bottommost_vertex), including those two values. Similarly for the X values you would use ceil and floor accordingly so that you would be including the pixel that the edge lands on."
Things are a little more complicated in scanlines that contain vertices. I end up with alot of special cases depending on which part of the edge is farthest out. But I think this is the way I'll go.
I needed something similar in the past, here is the test for my code.
I'll try to dig up the code to see if I did something fancy :)
Edit:
Found it, it's actually a template, not everything is included so it wouldn't compile out of the box.
Here it is:
I'll try to dig up the code to see if I did something fancy :)
Edit:
Found it, it's actually a template, not everything is included so it wouldn't compile out of the box.
Here it is:
/* Converts any convex polygon/line or point into scan-lines, with clipping. Polygons needs to be defined in clockwise order, otherwise the results are undefined. The coordinate fetching is done via a Functor to separate the algorithm from any data. Approximately one division per edge is performed and two fetches of data per vertex.Usage: ScanlineConverter<P> conv(P(), vertexCount, minX, minY, maxX, maxY) float minX, maxX; int scanline; while (conv.getScanline(scanline, minX, minY){ // Do something from minX to maxX }Samples: Drawing a polygon including all pixels/cells that are touched struct GetXY // Functor used to get the XY coordinates for an array of vectors { GetXY(const Vec2* const vertices) : m_vertcies(vertices) { } void operator()(float& x, float& y, const uint index) const { x = m_vertices[index][0]; y = m_vertices[index][1]; } const Vec2* m_vertices; }; std::vector<Vec2> vertices; // Filled with vertices ScanlineConverter<GetXY> conv(GetXY(&vertices[0]), vertcies.size(), 0, 0, 640, 480); float minX, maxX; int scanline; while (conv.getScanline(scanline, minX, maxX){ int i0 = int(floorf(minX)); int i1 = int(ceilf(maxX + 0.00000001f)); // Bias is used, otherwise if minX == maxX and minX is an integer, nothing will be processed. int i; for (i = i0; i < i1; ++ i) plot(i, scanLine, color); } Drawing a polygon, excluding left and bottom edge (no overdraw for adjecent edges) uses the same functor and setup. while (conv.getScanline(scanline, minX, maxX, true){ int i0 = int(floorf(minX)); int i1 = int(floorf(maxX)); int i; for (i = i0; i < i1; ++ i) plot(i, scanLine, color); }*/template <class P> class ScanlineConverter{public: static inline int myFloor(const float x) { // Since normal floorf treats -0 diffrent from +0 (but no floating point compares) we need to handle this case if (*((uint*)&x) == 0x80000000) return 0; return Math::floori(x); } enum { big = 0x7ffffff }; ScanlineConverter(const P& p, const uint vertexCount, const int minX = -big, const int minY = -big, const int maxX = big, const int maxY = big) : m_p(p) { init(vertexCount, minX, minY, maxX, maxY); } bool getScanline(int& scanLine, float& minX, float& maxX, const bool exclusive = false); ScanlineConverter(const P& p) : m_p(p) { } void init(const uint vertexCount, const int minX = -big, const int minY = -big, const int maxX = big, const int maxY = big);private: void nextLeft(void); void nextRight(void); const P& m_p; int m_count; int m_minX; int m_minY; int m_maxX; int m_maxY; int m_scanLine; uint m_flags;// Left edge int m_leftIndex; int m_leftNextIndex; int m_leftStopY; float m_leftX; float m_leftY; float m_newMinX; float m_leftSlope; float m_leftNewX; float m_leftNewY;// Right edge int m_rightIndex; int m_rightNextIndex; int m_rightStopY; float m_rightX; float m_rightY; float m_newMaxX; float m_rightSlope; float m_rightNewX; float m_rightNewY;};template <class P>boolScanlineConverter<P>::getScanline(int& scanLine, float& minX, float& maxX, const bool exclusive){ for (; m_flags != 3; ++ m_scanLine){ // No need to parse more scan-lines if (m_scanLine >= m_maxY) return false; // Setup min and max for this scan-line minX = m_newMinX; maxX = m_newMaxX; // Process left edge while ((m_flags & 1) == 0){ // Process vertices on the same scan-line (as the current) if (m_scanLine == m_leftStopY){ m_leftIndex = m_leftNextIndex; minX = min(minX, m_leftNewX); m_leftX = m_leftNewX; m_leftY = m_leftNewY; nextLeft(); continue; } // Must calculate intersection point float d = (float(m_scanLine + 1) - m_leftY) * m_leftSlope; float x = m_leftNewX * d; x += m_leftX * (1.0f - d); minX = min(minX, x); m_newMinX = x; break; } // Process right edge if (exclusive){ while ((m_flags & 2) == 0){ // Process vertices on the same scan-line (as the current) if (m_scanLine == m_rightStopY){ m_rightIndex = m_rightNextIndex; maxX = min(maxX, m_rightNewX); m_rightX = m_rightNewX; m_rightY = m_rightNewY; nextRight(); continue; } // Must calculate intersection point float d = (float(m_scanLine + 1) - m_rightY) * m_rightSlope; float x = m_rightNewX * d; x += m_rightX * (1.0f - d); maxX = min(maxX, x); m_newMaxX = x; break; } }else { while ((m_flags & 2) == 0){ // Process vertices on the same scan-line (as the current) if (m_scanLine == m_rightStopY){ m_rightIndex = m_rightNextIndex; maxX = max(maxX, m_rightNewX); m_rightX = m_rightNewX; m_rightY = m_rightNewY; nextRight(); continue; } // Must calculate intersection point float d = (float(m_scanLine + 1) - m_rightY) * m_rightSlope; float x = m_rightNewX * d; x += m_rightX * (1.0f - d); maxX = max(maxX, x); m_newMaxX = x; break; } } // Clip if (m_scanLine < m_minY) continue; float temp = float(m_minX); minX = max(minX, temp); if (minX >= float(m_maxX)) continue; float t = float(m_maxX); maxX = min(maxX, t); if (maxX < float(m_minX)) continue; // return scan-line and exit scanLine = m_scanLine; ++ m_scanLine; return true; } return false;}template <class P>voidScanlineConverter<P>::init(const uint vertexCount, const int minX, const int minY, const int maxX, const int maxY){ m_count = vertexCount; m_minX = minX; m_minY = minY; m_maxX = maxX; m_maxY = maxY; PHAT_ASSERT(vertexCount > 0); PHAT_ASSERT(minX < maxX); PHAT_ASSERT(minY < maxY);// Find top, left vertex int minIndex = 0; float mx, my; m_p(mx, my, minIndex); int index; for (index = 1; index < m_count; ++ index){ float x, y; m_p(x, y, index); if ((my == y) && (x >= mx)) continue; if (y < my){ mx = x; my = y; minIndex = index; } }// Setup scan-line conversion m_leftIndex = minIndex; m_leftX = mx; m_leftY = my; m_rightIndex = minIndex; m_rightX = mx; m_rightY = my; m_scanLine = myFloor(my); m_newMinX = m_leftX; m_newMaxX = m_rightX; m_leftNewX = m_leftX; m_leftNewY = m_leftY; m_rightNewX = m_rightX; m_rightNewY = m_rightY; m_leftNextIndex = m_leftIndex; m_rightNextIndex = m_rightIndex; m_leftSlope = 0.0f; m_rightSlope = 0.0f; m_leftStopY = m_scanLine; m_rightStopY = m_scanLine; m_flags = 0; nextLeft(); nextRight(); if (m_flags == 3) // For points we need to do this -- m_flags;}template <class P>voidScanlineConverter<P>::nextLeft(void){ -- m_leftNextIndex; if (m_leftNextIndex < 0) m_leftNextIndex += m_count; if (m_leftNextIndex == m_rightIndex){ m_flags |= 1; return; } m_p(m_leftNewX, m_leftNewY, m_leftNextIndex); if (m_leftNewY < m_leftY){ m_flags |= 1; return; } m_leftStopY = myFloor(m_leftNewY); m_leftSlope = 1.0f / (m_leftNewY - m_leftY);}template <class P>voidScanlineConverter<P>::nextRight(void){ ++ m_rightNextIndex; if (m_rightNextIndex >= m_count) m_rightNextIndex -= m_count; if (m_rightNextIndex == m_leftIndex){ m_flags |= 2; return; } m_p(m_rightNewX, m_rightNewY, m_rightNextIndex); if (m_rightNewY < m_rightY){ m_flags |= 2; return; } m_rightStopY = myFloor(m_rightNewY); m_rightSlope = 1.0f / (m_rightNewY - m_rightY);}
I think if you're not sure 100percent your method takes care of all cases you should do something like I suggested to test your results of a more efficent implimentation, I'm very certian it's correct, I'm also certian it's inefficent lol. Biki's suggestions seems to be a reasonable one tho, however it might have special cases which mine doesn't. but it seems the way to go for efficency purpose.
Tim
Tim
I'm quite sure that my method is covering all cases.
As you've noticed it handles any convex polygon, including points and lines and degenerate cases (multiple vertices at the same point).
Also with clipping (quite easy to remove if not needed).
As you can see I use a slight bias for inclusive rendering, so in VERY odd cases an extra cell (pixel) can be produced. It could be avoided with an extra compare and special case (as stated in the comments).
For the things I used it for this was not a problem.
I projected the view frustum onto a grid to determine visibility etc.
I'm sure it's not the fastest renderer out there, but it's very exact and robust.
As you've noticed it handles any convex polygon, including points and lines and degenerate cases (multiple vertices at the same point).
Also with clipping (quite easy to remove if not needed).
As you can see I use a slight bias for inclusive rendering, so in VERY odd cases an extra cell (pixel) can be produced. It could be avoided with an extra compare and special case (as stated in the comments).
For the things I used it for this was not a problem.
I projected the view frustum onto a grid to determine visibility etc.
I'm sure it's not the fastest renderer out there, but it's very exact and robust.
Author
Thank you all for your help. I think I've got some working code now.
I narrowed the problem down to 2 cases:
Scanline with no vertices on it:
Follow the edges from the top/bottom of the scanline based on whether the edge slopes inwards or outwards.
Scanline with vertices on it:
Take the min/max of the entry point,exit point and vertex that lies on the scanline.
Here's the code I came up in case anyone's interested. It only works for triangles, but it could be modified to support all convex polys fairly easily I think. Also it's in 16.16 fixed point.
I narrowed the problem down to 2 cases:
Scanline with no vertices on it:
Follow the edges from the top/bottom of the scanline based on whether the edge slopes inwards or outwards.
Scanline with vertices on it:
Take the min/max of the entry point,exit point and vertex that lies on the scanline.
Here's the code I came up in case anyone's interested. It only works for triangles, but it could be modified to support all convex polys fairly easily I think. Also it's in 16.16 fixed point.
struct tf_vert // linked list vertex{ int x,y; tf_vert *p,*n;};inline int fixmul(int m1,int m2) { return (int)(((__int64)m1*(__int64)m2)>>16); }inline int fixdiv(int n,int d) { return (int)(((__int64)n<<16)/d); }void trifill_line(int x1,int x2,int scanline){ // x1=first cell(straight integers,not fixed point) // x2=1+last cell}void trifill_outside(ivec2 *ivts){ tf_vert vts[3]; tf_vert *top=vts; int i; for(i=0;i<3;i++) { vts.x=ivts.x; vts.y=ivts.y; if(top->y>vts.y) top=vts+i; // find top vert } vts[0].p=vts+2; vts[0].n=vts+1; // make tri a linked list vts[1].p=vts+0; vts[1].n=vts+2; vts[2].p=vts+1; vts[2].n=vts+0; tf_vert *left=top,*right=top,*mid; int x1,x2,s1,s2,m1,m2,segs=2; m1=top->x; m2=top->x; // m1,m2 are the left,right edges for complex // scanlines(lines with vertices in them) if(top->n->y<top->p->y) mid=top->n; // find mid vertex else mid=top->p; if(left->p->y>>16==left->y>>16) { left=left->p; if(left->x<m1) m1=left->x; segs--; } // flat top if(right->n->y>>16==right->y>>16) { right=right->n; if(right->x>m2) m2=right->x; segs--; } if(segs==0) // the whole tri is in one scanline { trifill_line(m1>>16,(m2>>16)+1,left->y>>16); return; } s1=fixdiv(left->p->x-left->x,left->p->y-left->y); // get slopes s2=fixdiv(right->n->x-right->x,right->n->y-right->y); x1=left->x+fixmul(s1,0xFFFF-(left->y&0xFFFF)); x2=right->x+fixmul(s2,0xFFFF-(right->y&0xFFFF)); if(m1>x1) m1=x1; if(m2<x2) m2=x2; trifill_line(m1>>16,(m2>>16)+1,left->y>>16); // draw top scanline if(s1<0) x1+=s1; // move to the bottom of the pixel if(s2>0) x2+=s2; int y=(left->y>>16)+1; // y=current scanline if(segs==2) { while(y<mid->y>>16) // draw top half { trifill_line(x1>>16,(x2>>16)+1,y); x1+=s1; x2+=s2; y++; } if(left->p==mid) // update left slope { left=left->p; m1=left->x; m2=x2; if(s1>0 && x1<m1) m1=x1; if((left->p->y>>16)>(left->y>>16)) { s1=fixdiv(left->p->x-left->x,left->p->y-left->y); // new slope x1=left->x+fixmul(s1,0xFFFF-(left->y&0xFFFF)); if(x1<m1) m1=x1; } else { if(s2>0 && right->n->x<m2) m2=right->n->x; segs=0; // flat bottom } trifill_line(m1>>16,(m2>>16)+1,y); // draw middle if(!segs) return; // no bottom half(flat bottom) if(s1<0) x1+=s1; // move to the bottom of the pixel x2+=s2; } else // update right slope { right=right->n; m1=x1; m2=right->x; if(s2<0 && x2>m2) m2=x2; if((right->n->y>>16)>(right->y>>16)) { s2=fixdiv(right->n->x-right->x,right->n->y-right->y); // new slope x2=right->x+fixmul(s2,0xFFFF-(right->y&0xFFFF)); if(x2>m2) m2=x2; } else { if(s1<0 && left->p->x>m1) m1=left->p->x; segs=0; // flat bottom } trifill_line(m1>>16,(m2>>16)+1,y); // draw middle if(!segs) return; // no bottom half(flat bottom) if(s2>0) x2+=s2; // move to the bottom of the pixel x1+=s1; } y++; } mid=left->p; while(y<mid->y>>16) // draw bottom half { trifill_line(x1>>16,(x2>>16)+1,y); x1+=s1; x2+=s2; y++; } if(s1<0) x1=mid->x; if(s2>0) x2=mid->x; trifill_line(x1>>16,(x2>>16)+1,y);}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
