Traversing all the points inside a triangle using loops

Question

The following is the three vertices with x,y and z co-ordinates of a triangle in 3D:

-0.2035416, 0.1107585, 0.9516008 (vertex A)
-0.0334390, -0.2526040, 0.9751212 (vertex B)
0.2569092, 0.0913718, 0.9817184 (Vertex C)

The projection plane is divided into a grid of (height*width) pixels.

I want to traverse every pixel inside the triangle inside the projection plane manually starting from the bottom to top of the triangle and print each pixel co-ordinates inside the triangle on the screen in c++. Say, I have already found the top and bottom vertex of the triangle. But now, how will I traverse from bottom to top and print each pixel co-ordinate? What's the logic behind this?

I have an idea of making two nested for loops like below but what will I do inside the loops? how will I make the sideway move after each x and y increment?

for (int y = ymin; y <= ymax; ++y) {
   for (int x = xmin; x <= xmax; ++x) {

  //what to to here?

    }
 }

Answer 1

Traversing demo:

#include <iostream>

template <size_t kD>
class Vector{
public:
  template <class... Args>
  Vector(double coord, Args&&... args) {
    static_assert( sizeof...(args)+1 == kD, "Unmatched vector dimension" );
    InitCoord(0, coord, std::forward<Args>(args)...);
  }

  Vector(const Vector &) = default;
  Vector &operator=(const Vector &) = default;

  double &operator[](const size_t i) {
    return coord_[i];
  }
  double operator[](const size_t i) const {
    return coord_[i];
  }

  friend Vector<kD> operator-(const Vector<kD> &A, const Vector<kD> &B) {
    Vector v;
    for (size_t i=0; i<kD; ++i)
      v[i] = A[i]-B[i];
    return v;
  }
private:
  Vector() = default;

  template <class... Args>
  void InitCoord(const int pos, double coord, Args&&... args) {
    coord_[pos] = coord;
    InitCoord(pos+1, std::forward<Args>(args)...);
  }

  void InitCoord(const int pos) {}

  double coord_[kD];
};

class Line {
public:
  Line(const double x1, const double y1, const double x2, const double y2)
      : x1_(x1), y1_(y1), x2_(x2), y2_(y2) {}

  Line(const Vector<2> A, const Vector<2> B)
      : x1_(A[0]), y1_(A[1]), x2_(B[0]), y2_(B[1]) {}

  double operator()(const double x, const double y) const {
    return (y-y1_)*(x2_-x1_) - (x-x1_)*(y2_-y1_);
  }

  int_fast8_t Sign(const double x, const double y) const {
    return Signum( (y-y1_)*(x2_-x1_) - (x-x1_)*(y2_-y1_) );
  }
private:
  int_fast8_t Signum(const double x) const {
    return (0.0 < x) - (x < 0.0);
  }

  const double x1_,y1_;
  const double x2_,y2_;
};

void Transpos(Vector<2> &v) {
  v[0] = (v[0]+1)/2*720; // col
  v[1] = (v[1]+1)/2*480; // row
}

double CalculateZ(const Vector<2> &D, const Vector<2> &AB, const Vector<2> &AC,
    const Vector<3> &AB3, const Vector<3> &AC3) {
  const double b = (D[1]*AB[0]-D[0]*AB[1]) / (AC[1]*AB[0]-AC[0]*AB[1]);
  const double a = AB[0]==0 ? (D[1]-b*AC[1])/AB[1] : (D[0]-b*AC[0])/AB[0];

  std::cout << a << " " << b << std::endl;

  return a*AB3[2]+b*AC3[2];
}

int main()
{
  const auto A3 = Vector<3>(0.0, 0.0, 7.0);
  const auto B3 = Vector<3>(0.0, 0.3, 9.0);
  const auto C3 = Vector<3>(0.4, 0.0, 1.0);

  const auto AB3 = B3-A3;
  const auto AC3 = C3-A3;
  const auto BC3 = C3-B3;

  // Some projection works here, which I am not good at.
  // A B C store the projected triangle coordiate in the [-1,1][-1,1] area

  auto A = Vector<2>(0.0, 0.0);
  auto B = Vector<2>(0.0, 0.3);
  auto C = Vector<2>(0.4, 0.0);

  Transpos(A);
  Transpos(B);
  Transpos(C);

  const auto AB2 = B-A;
  const auto AC2 = C-A;
  const auto BC2 = C-B;

  const Line AB(A, B);
  const Line AC(A, C);
  const Line BC(B, C);

  const auto signAB = AB.Sign(C[0],C[1]);
  const auto signAC = AC.Sign(B[0],B[1]);
  const auto signBC = BC.Sign(A[0],A[1]);

  // top
  // 0------------720 (col x)
  // |
  // |
  // |
  // |
  // 480 (row y)
  // bottom

  for (int row=480-1; row>=0; --row) {
    for (int col=0; col<720; ++col) {
      if (signAB*AB.Sign(col,row)>=0 && signAC*AC.Sign(col,row)>=0 &&
          signBC*BC.Sign(col,row)>=0 )
        std::cout << row << "," << col << " Z:"
          << CalculateZ(Vector<2>(col, row)-A, AB2, AC2, AB3, AC3) + A3[2]
          << std::endl;
    }
  }

  return 0;
}

Projection:

• first space [-1,1][-1,1]
• second space [0,720][0,480]

Let's say we have a (x1,y1) in the first space, then (x_,y_) with x_=(x1+1)/2*720, y_=(y1+1)/2*480 will be in the second space.

More generalize:

first space [xmin,xmax][ymin,ymax]
second space [xmin_,xmax_][ymin_,ymax_]
(x1,y1)
->
( (x1-xmin)/(xmax-xmin)*(xmax_-xmin_)+xmin_ ,  
  (y1-ymin)/(ymax-ymin)*(ymax_-ymin_)+ymin_ )

If you just want to zoom it, not twist it or something...

Edit #1:

• Thanks to @Adrian Colomitchi's advices, which is outstanding, I have improved the demo.
• Ax Ay Bx By Cx Cy are now coordinates in the first space, they are then "transposed" into the second space. As a result, Line AB AC BC are now "in" the second space. And the two loops are modified accordingly, they now iterate the points of the second space.

How to find z value from (x,y):

AB represents a vector from A(Ax,Ay) to B(Bx,By), i.e. AB = B-A = (Bx-Ax,By-Ay).

For any given point D(Dx,Dy) in the triangle, represent it into AD = aAB + bAC : (Dx-Ax, Dy-Ay) = a*(Bx-Ax, By-Ay) + b*(Cx-Ax, Cy-Ay) where Dx Dy Ax Ay Bx By Cx Cy is known. Find out a and b, and then Dz = a*(Bz-Az) + b*(Cz-Az). Dx Dy in the 3D space can be calculated the same way.

Edit #2:

Z value calculation added to the demo.

I tried to keep the demo simple, but calculating the Z value really involved lots of variables and calculations. I declare a new class called Vector to manage points and vectors, while the Line class remains unchanged.

Answer 2

You need to change the inner loop slightly; don't go from xmin to xmax. For each value of y from ymin to ymax there will be exactly two different pixels (two different x values) which lie exactly on the two edges of the triangle. Calculate those points and then all points between them will be inside the triangle. And you'll have to handle some edge cases such as when one of the edges is horizontal.

Answer 3

First you must transform your {0,1} ranges (vert & horz) to pixel coordinates. You speak of 720x480. This is not a square, but a rectangle. If you decide to keep one-to-one scale, you'll get a distorted triangle. If not, perhaps you only use 480x480 pixels.

Second, now you have your three vertices in pixel-space, you can iterate every pixel in this pixel-space and tell if it belongs to the triangle or not. The function 'InTriangle' for this job is what @felix posted in the code of his solution:

if (signAB*AB(i,j)>=0 && signAC*AC(i,j)>=0  && signBC*BC(i,j)>=0 )