Jump to content
  • Advertisement
Sign in to follow this  
kiniport

Triangle Scan Conversion

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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:

/* 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>
bool
ScanlineConverter<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>
void
ScanlineConverter<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>
void
ScanlineConverter<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>
void
ScanlineConverter<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);
}

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.



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);

}




Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!