假設二維平面上有一條線從 (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,這個演算法中只用了簡單的整數加減法和少量的整數除法,算出整數的座標中連接二點的直線裏所有的點。關於這個演算法,請參考下面的連結。
// 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 匯圖中面的最小單位是一個三角型,下一章的目標就是取得三角型內的所有點,很單純但也很重要,請看下去吧。