計算機圖形學演算法流程圖

㈠ 計算機圖形學， 光線跟蹤演算法的過程是什麼

光線跟蹤思路：從視點出發，通過圖像平面上每個像素中心向場景發出一條光線，光線的起點為視點，方向為像素中心和視點連線單位向量。光線與離視點最近的場景物體表面交點有三種可能：
當前交點所在的物體表面為理想漫射面，跟蹤結束。
當前交點所在的物體表面為理想鏡面，光線沿其鏡面發射方向繼續跟蹤。
當前交點所在的物體表面為規則透射面，光線沿其規則透射方向繼續跟蹤。

偽代碼：

void TraceRay(const Vec3& start, const Vec3& direction, int depth, Color& color)
{
Vec3 intersectionPoint, reflectedDirection, transmittedDirection;
Color localColor, reflectedColor, transmittedColor;
if (depth >= MAX_DEPTH) {
color = Black; //#000
}
else {
Ray ray(start, direction); //取start起點，方向direction為跟蹤射線；
if ( !scene->HasIntersection(ray) )
color = BackgroundColor;
else {
計算理起始點start最近的交點intersectionPoint,
記錄相交物體intersectionObject,

// #1
Shade(intersectionObject, intersectionPoint, localColor);

// #2
if ( intersectionPoint所在面為鏡面 ) {
計算跟蹤光想S在intersectionPoint處的反射光線方向reflectedDirection,
TraceRay(intersectionPoint, reflectedDirection, depth+1, reflectedColor);
}
// #3
if ( intersectionPoint所在的表面為透明面 ) {
計算跟蹤光線S在intersectionPoint處的規則透射光線方向transmittedDirection,
TraceRay(intersectionPoint, transmittedDirection, depth+1, transmittedColor);
}
// #summarize
color = localColor + Ks * reflectedColor + Kt * transmittedColor;
}// else
} //else
}
// 局部光照模型計算交點intersectionPoint處的局部光亮度localColor
void Shade(const Object& intersectionObj, const Vec3& intersectionPoint, Color& localColor)
{
確定intersectionObj在intersectionPoint處的單位法向量N,
漫反射系數Kd,
鏡面反射系數Ks,
環境反射系數Ka;
localColor = Ka * Ia; //Ia為環境光亮度
for ( 每一個點光源PointLight ) {
計算入射光線單位向量L和虛擬鏡面法向單位向量H,
// 由Phong模型計算光源PointLight在intersectionPoint處的漫反射和鏡面反射光亮度
localColor += ( Ipointlight * ( Kd * (N.dot(L)) + Ks * (N.dot(H))^n ) );
}
}

㈡ Bresenham直線演算法

Bresenham直線演算法在計算機圖形學中是繪制直線的高效經典方法。實際直線是連續的，但計算機顯示有限精度，無法真正繪制連續直線。我們使用一系列離散像素點來近似表示直線。本文將逐步演示實現一個簡單直線演算法，最終引出Bresenham演算法，並詳解其原理和步驟。

首先，我們規定坐標系以左下為原點，橫軸為x，縱軸為y。通常，我們會將直線分為多個像素點，以簡化繪制。然而，這樣繪制的直線會出現空洞，效果不理想。我們可以通過按x軸逐像素繪制來改善。為此，需要輸入兩點坐標(x0, y0)和(x1, y1)，並計算直線上的y值隨x值的變化。

使用逐像素繪制方法時，對於直線斜率在0-1之間的情況，效果良好。但是，當斜率大於1或小於0時，直線會缺失部分像素點，形成空洞。為解決此問題，可以將直線斜率轉換為絕對值在0-1之間的形式。具體做法是通過坐標變換，將起點與終點位置互換，以便處理斜率大於1或小於0的情況。

進一步優化演算法，避免多次浮點運算，將除法運算移出循環外，提升效率。在此過程中，理解誤差概念至關重要。當x值遞增時，通過計算誤差值來決定是否跳轉到下一個像素點。誤差值大於0.5時，表示像素點跨越了當前網格，需要在y值上增加1。同時，為了保持網格中心像素的准確性，通過調整誤差值來確保像素精確定位。

最終，優化演算法時需添加邊界控制，使用無符號整型以避免負數問題，並採用Eigen向量替代普通整型傳值，提升演算法性能。通過上述步驟，我們可以得到一條平滑、准確的直線。

綜上所述，Bresenham直線演算法通過巧妙的誤差控制策略，實現了高效、精確地在計算機屏幕上繪制直線。演算法簡化了浮點運算，優化了性能，並通過變換和邊界處理解決了多種斜率和起點終點位置的情況，確保了直線的連續性和精度。

㈢ 計算機圖形學旋轉演算法

繞任意點旋轉的思路是,先將任意旋轉點一起平移到原點,圖像隨旋轉點一起平移,然後根據旋轉矩陣將圖像旋轉,然後再將旋轉點與圖像一起平移回原先的位置.

旋轉矩陣:將所需旋轉角轉換為弧度後算出COS和SIN函數結果並填入矩陣,將旋轉點與組成圖像的所有頂點坐標與矩陣相乘獲得變換後的新坐標.

任意點旋轉的復合矩陣

矩陣相乘的順序很重要,因為矩陣相乘先後結果是不對等的,而矩陣表達上是從右到左的,比如T*R*-T,計算過程相當於T*(R*-T),另外矩陣相乘是採用交叉點乘,而M矩陣也是個3*3的矩陣

得到M復合矩陣後,再將原點與圖像頂點與M相乘,即可得到變換後的新坐標.即P'=M*P

圖像變換演算法其實特簡單,就是cos和sin,然後就是四則運算,再填入矩陣,計算復合矩陣,按現在的教學大綱小學生都會,計算機寫程序一點沒難度,重點其實在圖像變換的理解上.