计算机图形学算法流程图

㈠ 计算机图形学， 光线跟踪算法的过程是什么

光线跟踪思路：从视点出发，通过图像平面上每个像素中心向场景发出一条光线，光线的起点为视点，方向为像素中心和视点连线单位向量。光线与离视点最近的场景物体表面交点有三种可能：
当前交点所在的物体表面为理想漫射面，跟踪结束。
当前交点所在的物体表面为理想镜面，光线沿其镜面发射方向继续跟踪。
当前交点所在的物体表面为规则透射面，光线沿其规则透射方向继续跟踪。

伪代码：

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,然后就是四则运算,再填入矩阵,计算复合矩阵,按现在的教学大纲小学生都会,计算机写程序一点没难度,重点其实在图像变换的理解上.