Write Your Own 3D Engine (2) Chapter 2. 畫線

假設二維平面上有一條線從 (x1, y1) 開始, (x2, y2)  結束,(x, y) 是線上的某一點,如果已知 x,請問 y 為多少? (拿筆出來畫畫看?)

首先,線上每一點的斜率都相同,所以 (y2 – y1 ) / (x2 – x1 ) = (y – y1 ) / ( x – x1 ),再來左右都乘 (x2 – x1 ),再個加一個 y1,就得到 y 的公式了。因為電腦螢幕的座標是整數,所以把 x 和 y 前面再加一個 (int) 或是 static_cast<int> 就可以開始畫線了,真簡單。

當然這樣是畫的了線沒錯啦,但是裏面用了大量的浮點運算,而且還是大量的浮點除法。為了效率,浮點運算能避免就避免吧。

在真實的3D引擎 (軟體或硬體),畫線使用基本上還是脫離不了 1962 年就被發表的 Bresenham line’s algorithm,這個演算法中只用了簡單的整數加減法和少量的整數除法,算出整數的座標中連接二點的直線裏所有的點。關於這個演算法,請參考下面的連結。

Bresemham 的方法可以套用到 3D 上嗎? 像是給二個點 (x1, y1, z1) 和 (x2, y2, z2) 然後算出直線上所有的點? 當然是可以,基本的邏輯是一樣的。
// line3d uses Bresenham's algorithm to generate 
// the 3 dimensional points on a line from (x1, y1, z1) 
// to (x2, y2, z2), reference implementation found here
// http://www.ict.griffith.edu.au/anthony/info/graphics/bresenham.procs (3D)
inline static void bresenham3d(
  PointI pt1, PointI pt2, 
  std::vector<PointI>& out)
{
  PointI pos(pt1);
  PointI delta = pt2 - pt1;
  PointI abs_delta(
    abs(delta.x_), 
    abs(delta.y_), 
    abs(delta.z_));
  PointI double_delta(
    abs_delta.x_ << 1, 
    abs_delta.y_ << 1, 
    abs_delta.z_ << 1);

  int_fast32_t x_inc, y_inc, z_inc;

  out.reserve(abs_delta.x_ + abs_delta.y_ + abs_delta.z_);

  x_inc = (delta.x_ < 0) ? -1 : 1;
  y_inc = (delta.y_ < 0) ? -1 : 1;
  z_inc = (delta.z_ < 0) ? -1 : 1;

  if (abs_delta.x_ >= abs_delta.y_ 
   && abs_delta.x_ >= abs_delta.z_)
  {
    int_fast32_t err_1 = double_delta.y_ - abs_delta.x_;
    int_fast32_t err_2 = double_delta.z_ - abs_delta.x_;

    for (int_fast32_t i = 0; i < abs_delta.x_; i++)
    {
      out.push_back(pos);

      if (err_1 > 0)
      {
        pos.y_ += y_inc;
        err_1 -= double_delta.x_;
      }

      if (err_2 > 0)
      {
        pos.z_ += z_inc;
        err_2 -= double_delta.x_;
      }

      err_1 += double_delta.y_;
      err_2 += double_delta.z_;

      pos.x_ += x_inc;
    }
  }
  else if (abs_delta.y_ >= abs_delta.x_ 
    && abs_delta.y_ >= abs_delta.z_)
  {
    int_fast32_t err_1 = double_delta.x_ - abs_delta.y_;
    int_fast32_t err_2 = double_delta.z_ - abs_delta.y_;

    for (int_fast32_t i = 0; i < abs_delta.y_; i++)
    {
      out.push_back(pos);

      if (err_1 > 0)
      {
        pos.x_ += x_inc;
        err_1 -= double_delta.y_;
      }

      if (err_2 > 0)
      {
        pos.z_ += z_inc;
        err_2 -= double_delta.y_;
      }

      err_1 += double_delta.x_;
      err_2 += double_delta.z_;

      pos.y_ += y_inc;
    }
  }
  else
  {
    int_fast32_t err_1 = double_delta.y_ - abs_delta.z_;
    int_fast32_t err_2 = double_delta.x_ - abs_delta.z_;

    for (int_fast32_t i = 0; i < abs_delta.z_; i++)
    {
      // if x, y are the same, we don't have to store the pixel
      out.push_back(pos);

      if (err_1 > 0)
      {
        pos.y_ += y_inc;
        err_1 -= double_delta.z_;
      }

      if (err_2 > 0)
      {
        pos.x_ += x_inc;
        err_2 -= double_delta.z_;
      }

      err_1 += double_delta.y_;
      err_2 += double_delta.x_;

      pos.z_ += z_inc;
    }
  }

  out.push_back(pos);
}

考慮一個狀況,假設螢幕是 X-Y 平面,有一條線從 ( 0, 0, -1000) 畫到 (1, 0, 1000)。就算考慮到 3D 的景深問題,在螢幕上我們只需要知道 (0, 0) 這點的 Z 軸深度 (i.e. -1000),和 (1, 0) 時的 Z 軸深度 (i.e. 1000)。但是使用上面的 Bresemham 3D 演算法會產生約 2000 個最後無任何用處的點。似乎是有些浪廢效能與記憶體。不過這可以很簡單的用 “忽略 delta-z 為最大的情況” 甚至是 “結合 Bresemham 2D 與內插法約略估計每點的 Z 軸值” 來解決,我提供的 Sample Code 裏面有個 bresenham2d2() 使用的是較簡單的前者的作法。

實際來畫畫看吧。


Sample_1::Sample_1()
{
  // vertices for a cube
  pts_[0].set(1, 1, 1);
  pts_[1].set(-1, 1, 1);
  pts_[2].set(-1, -1, 1);
  pts_[3].set(1, -1, 1);
  pts_[4].set(1, 1, -1);
  pts_[5].set(-1, 1, -1);
  pts_[6].set(-1, -1, -1);
  pts_[7].set(1, -1, -1);

  rotate_degree_ = 0;
}

// paint cube with line 
void Sample_1::paintCubeLines(
  BYTE* buf, LONG width, 
  LONG height, 
  WORD bytePerPixel) 
{ 
  // 8 integer point 
  PointI pts[8]; 
  
  // line points 
  std::vector<PointI> lines; 
  
  // matrix 
  Matrix<double> scale_matrix(4, 4); 
  Matrix<double> translate_matrix(4, 4); 
  Matrix<double> rotate_matrixX(4, 4); 
  Matrix<double> rotate_matrixY(4, 4); 
  Matrix<double> rotate_matrixZ(4, 4); 
  
  // add one degree each time paint() has been called 
  rotate_degree_ += 1; 
  double radian = (rotate_degree_ % 360) * 2 * pi_ / 360; 
  
  Utility::set_rotateX(rotate_matrixX, radian); 
  Utility::set_rotateY(rotate_matrixY, radian); 
  Utility::set_rotateZ(rotate_matrixZ, radian); 
  Utility::set_scale(scale_matrix, 20); 
  Utility::set_translate(translate_matrix, 200, 200, 200); 
  
  // final matrix 
  Matrix<double> world_matrix = 
    scale_matrix * rotate_matrixX * 
    rotate_matrixY * rotate_matrixZ * 
    translate_matrix; 
    
  // get new position for each vertices 
  for (int i = 0; i < 8; i++) 
  { 
    PointF pt = pts_[i] * world_matrix; 
    pts[i] = pt; 
  } 
  
  // draw 12 lines 
  Utility::bresenham3d(pts[0], pts[1], lines); 
  Utility::bresenham3d(pts[1], pts[2], lines); 
  Utility::bresenham3d(pts[2], pts[3], lines); 
  Utility::bresenham3d(pts[0], pts[3], lines); 
  
  Utility::bresenham3d(pts[4], pts[5], lines); 
  Utility::bresenham3d(pts[5], pts[6], lines); 
  Utility::bresenham3d(pts[6], pts[7], lines); 
  Utility::bresenham3d(pts[4], pts[7], lines); 
  
  Utility::bresenham3d(pts[0], pts[4], lines); 
  Utility::bresenham3d(pts[2], pts[6], lines); 
  Utility::bresenham3d(pts[3], pts[7], lines); 
  
  for (PointI pti : lines) 
  { 
    // ignore the point if outside the screen 
    if (pti.x_ <= 0 || pti.x_ >= width 
     || pti.y_ <= 0 || pti.y_ >= height) 
    { 
      return; 
    } 
    
    // draw a white point RGB(255, 255, 255) on x and y 
    int anchor = (pti.y_ * width + pti.x_) * bytePerPixel; 
    buf[anchor] = 0xFF; 
    buf[anchor + 1] = 0xFF; 
    buf[anchor + 2] = 0xFF; 
  } 
  
  return; 
}

會旋轉的立方體出現了。

下一章開始要從 “點”、”線” 進階到 “面” 了。在 3D 匯圖中面的最小單位是一個三角型,下一章的目標就是取得三角型內的所有點,很單純但也很重要,請看下去吧。