2

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 !

Tyler B. Joudrey
  • 421
  • 1
  • 8
  • 22
  • It's not trivial, but it is tedious and error prone. There are four cases: flat on top, flat on the bottom, vertex on the left, and vertex on the right. In all cases you'll need [Bresenham's_line_algorithm](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#All_cases) to find the points on the lines. (Bresenham's has eight cases for the eight octants). One more thing: triangle filling usually includes the left and excludes the right, so the pixels that form lines on the left of the triangle are included in the triangle, but pixels on the lines on the right are excluded. – user3386109 Jul 29 '22 at 23:13
  • Oh wow... Please do not use that. It is an unnecessary complication at this point. That algorithm was designed (as an optimization!) for older processors, when instructions meant exactly what they say. Nowadays (past couple decades) those if statements in the middle are more costly than a multiply. And if you actually want to optimize, just go wide. – beothunder Jul 29 '22 at 23:23
  • 1
    @beothunder Those `if` statements should turn into `cmov` instructions and be really cheap. But that's actually besides the point. The reason why you should still use Bresenham is that it doesn't have rounding errors resulting in different lines. If you use multiply then you have to work with floats or doubles and then you have to be real careful about rounding errors or drawing a mesh will have holes where adjacent triangles rounded the line in different ways. – Goswin von Brederlow Jul 30 '22 at 13:57
  • First thing you should do is create a `struct Point { float x, y; };`. Using `std::pair` makes the code much harder to read. Similar for scanline, pair of pair is horrible. Then in the `sort` you should sort by `(left.y < right.y) || (left.x < right.x)` to simplify the case of a triangle with 2 points on the same scanline. Then continue as user3386109 or beothunder suggested. – Goswin von Brederlow Jul 30 '22 at 14:03
  • see [how to rasterize rotated rectangle (in 2d by setpixel)](https://stackoverflow.com/a/19078088/2521214) the content of the left right buffers is what you want as output ... – Spektre Aug 04 '22 at 07:16

1 Answers1

0

(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
};
beothunder
  • 551
  • 2
  • 14