Writing a scanline algorithm for filling triangles in c++

user_3668936 0
Viewed 102

I am attempting to write a a function that takes in a vector of coordinates describing the outline of a triangle and returns a vector of pairs reperesenting lines used to fill the triangle described by the points

std::vector<std::pair<std::pair<int, int>, std::pair<int, int>>> 
SoftwareRendererImp::scanline(std::vector<std::pair<float, float>> points)
{

std::vector<std::pair<std::pair<int, int>, std::pair<int, int>>> lines;
// sort by y
std::sort(points.begin(), points.end(), [](auto &left, auto &right)
          { return left.second < right.second; });

//iterate through the sorted list and do some logic to determine scan lines

return lines;
}

I have taken a few swings at trying to get this to work however I cannot seem to come up with a solid solution. I am quite rusty at c/c++ so I could be fumbling around with the language or I may be misunderstanding how this kind of algorithim is supposed to work.

If this seems trivial to anyone please point mein the right direction. Thanks !

graphics algorithm c++
1 Answers

(Assuming scan lines are horizontal).

  1. Split the triangle into 2 triangles along the scan line with the y coordinate of the middle (y) point.
  2. (for both triangles) for every scan line between top and bottom vertices, solve the line equation for the two non-horizontal triangle sides for the y coordinate of that scan line.

Also, why all the templates?.

Also also, there is a ton of redundant information here. Perhaps a better starting point would be this:

struct ScanLine
{
    int y;
    int x;// leftmost
    int w;// not including x+w
};
user_119208920
Related