题目链接

    UVA - 12313 A Tiny Raytracer

题意

   给出 《训练指南》题意翻译

   本题的任务是实现一个小型光线追踪渲染器。场景由若干三角形网格（triangle mesh）组成，有且仅有一个点光源（point-light）。
   相机模型
   本题使用的相机是透视相机，位置在camera_pos，指向camera_target，up向量为camera_up，横向FOV等于$f$度，拍摄出来的图片是W×H像素，如下图所示。
   上图中，假想在相机的正前方有一个矩形（称为图像平面），代表着场景在相机中的影像，则它的离散形式就是渲染器的输出。在本题中，所有像素都是正方形，因此图像平面的宽度与高度之比总是W:H。
   从camera_pos出发指向camera_target 的射线穿过图像平面的中心，而图像平面的局部y轴就是camera_up。横向FOV 是指图像平面左右边界相当于相机的张角。
   为了计算三维场景中一个点在最终图像中的位置，只需从相机出发引一条射线穿过该点，则该射线与图像平面的交点就是所求。如果没有交点，则该点不可见。不难证明，图像平面离相机的距离无关紧要，只要y轴方向为camera_up，从camera_pos出发指向camera_target的射线穿过图像平面的中心即可。
   光线追踪原理
   对于最终图像中的每个像素，我们考虑一条射线，从眼睛（也就是相机，下同）出发，穿过像素的中心。只要跟踪这条射线，看它在场景中碰到了什么颜色的物体，根据光路可逆原理，就能知道这个像素是什么颜色的。
   上述原理是高度简化的，不过足以解决本题。在最简单的情况下，所有物体既不反光也不透明，则每当射线碰到一个物体时，可以直接计算这个物体的颜色，方法是连接碰撞点和光源（本题只有一个光源），如果连线被其他物体挡住，说明这个点处于阴影中，否则用随后介绍的着色算法计算这个点的颜色。
   在真实场景中，由于玻璃和水这样的物体存在，我们需要考虑光线和物体的多次碰撞，以处理反射（reflection）和折射（refraction），方法如下：如果射线碰到了一个反射性物体，则派生出一条新的反射光线，从碰撞点射出，指向碰撞表面的外部。同理，如果射线碰到了一个有一定透明度的物体，则派生出一条新的折射光线，从碰撞点射出，指向碰撞表面的内部。如果碰撞面两侧物体的折射系数（index of refraction）不同，则光线的方向将发生改变，改变方式遵守snell定律$n_1\sin {\theta }_1=n_2\sin {\theta }_2$。
   注意，如果发生了全反射（total internal reflection），应当停止跟踪该光线，而不是派生出一条反射光线。
   事实上，反射光线和折射光线本身还能继续派生出新的光线，所以我们实际上拥有一棵光线树。为了避免无穷无尽的递归下去，我们规定树的最大高度（在本题中总是等于4），这样，每个叶子要么在深度上达到了最大值，要么碰到了一个既不反射也不折射的物体（或者什么都没射到）。
   递归过程伪代码如下。

Color trace_ray(int depth, Ray ray) {
    Color point_color = BLACK, reflect_color = BLACK, refract_color = BLACK;
    Intersection i = get_first_intersection(ray);
    if(i.objID >= 0) { //与某物体相交
        double refl = scene.obj[i.objID].refl;
        double refr = scene.obj[i.objID].refr;
        point_color = get_point_color(i) * (1 - refl - refr);
        if(depth < maxdepth && refl > 0)
            reflect_color = trace_ray(depth+1, get_reflected_ray(ray, i)) * refl;
        if(depth < maxdepth && refr > 0)
            refract_color = trace_ray(depth+1, get_refracted_ray(ray, i)) * refr;
    }
    return point_color + reflect_color + refract_color;
}

   注意，只要深度没有达到最大值，不管反射系数是多么小的正数，都应该跟踪反射光线；折射光线也是如此。两个颜色的加法将在随后定义。
   着色
   前面遗留了一个问题，就是如何计算碰撞点的颜色（即上面的get_point_color函数）。在本题中，用Lambertian着色法（也叫余弦着色法），即根据碰撞表面的法线和从碰撞点到光源的向量的点积计算亮度。当夹角增大时，亮度按照余弦函数减小。
   如果点积等于0，说明两向量垂直，此时我们并不希望这个点完全呈黑色，而是要给它一点所谓的“环境光”。我们用ambient_coefficient 来表示这个系数，而diffuse_coefficient =1-ambient_coefficient表示漫反射系数。在本题中，三角形都看成是双面反光的，因此点积部分取了绝对值。object_color是物体的一个属性，即完全照明时的颜色。着色伪代码如下。

double shade;
if(is_shadowed(i)) //判断交点i是否在阴影中
    shade = 0;
else
    shade = fabs(Dot(light_vector, normal_vector)); //注意两个向量都应归一化
return object_color * light_color * (ambient_coeff + diffuse_coeff*shade);

   简单起见，只要连接交点和光源的线段被一个物体阻挡（即使该物体反光或者透明），就算作该交点在阴影中。这样做的确会让渲染结果不正确，但在本题中请忽略这个Bug。
   在本题中，颜色用三元组(r, g, b)表示，其中实数r, g, b满足0≤r,g,b≤1。颜色加法和向量加法一样，也是每一维分别相加。不难发现，如果严格按照上面的规则编写代码，颜色加法的结果总是合法的（即相加后的结果仍满足0≤r,g,b≤1）。

分析

    按照中文翻译即可清晰地写出代码，说几点需要注意的：1、“发生全反射（total internal reflection）时应该停止追踪该光线”指的是停止追踪折射光线，反射光线依然要追踪的，也就是说入射角满足全反射时要将refr系数置为0；2、与0比的阈值eps，推荐设置成1e-10(太小，比如1e-12会导致WA)；3、射线（Ray）需要记录所在媒介的介质系数（初始在真空，取值1），后面如果折射进入了某个object，则介质系数为此object的介质系数，然后再反射时介质系数不变，但再折射出去时介质系数回到1；4、题目说最大深度4，要注意初始射线的深度为0。
    给一份测试数据。

AC 代码

#include <iostream>
#include <cmath>
using namespace std;
struct Point3 {
    double x, y, z;
    Point3(double x = 0., double y = 0., double z = 0.): x(x), y(y), z(z) {}
    void Normalize() {
        double l = sqrt(x*x + y*y + z*z); x /= l; y /= l; z /= l;
    }
};
typedef Point3 Vector3;

Vector3 operator+ (const Vector3& A, const Vector3& B) {
    return Vector3(A.x + B.x, A.y + B.y, A.z + B.z);
}

Vector3 operator- (const Vector3& A, const Vector3& B) {
    return Vector3(A.x - B.x, A.y - B.y, A.z - B.z);
}

Vector3 operator* (const Vector3& A, double p) {
    return Vector3(A.x * p, A.y * p, A.z * p);
}

double Dot(const Vector3& A, const Vector3& B) {
    return A.x * B.x + A.y * B.y + A.z * B.z;
}

Vector3 Cross(const Vector3& A, const Vector3& B) {
    return Vector3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}

#define eps 1e-10
#define M 202
#define N 22
#define P 26
#define T 52
#define X 4
struct {Point3 v[P], n[T], c; int f[T][3], p, t; double l, r, m;} obj[N];
struct Ray {
    Point3 p; Vector3 v; double m;
    Ray(const Point3& p, const Vector3 v, double m): p(p), v(v), m(m) {this->v.Normalize();}
};
struct Ints {Point3 p; int i, j; Ints():i(-1){}};
Point3 img[M][M], p, t, g, c; Vector3 up; double a, f; int w, h, n, q;

Ints get_ints(const Point3& p, const Vector3& v) {
    double t = -1.; Ints it;
    for (int i=0; i<n; ++i) for (int j=0; j<obj[i].t; ++j) {
        if (abs(Dot(v, obj[i].n[j])) < eps) continue;
        const Point3 &a = obj[i].v[obj[i].f[j][0]], &b = obj[i].v[obj[i].f[j][1]], &c = obj[i].v[obj[i].f[j][2]];
        const Vector3 &n = obj[i].n[j]; double q = Dot(n, a-p) / Dot(n, v);
        if (q < eps || (t>eps && q>=t)) continue;
        Point3 r = p + v*q; Vector3 c1 = Cross(b-a, r-a), c2 = Cross(c-b, r-b), c3 = Cross(a-c, r-c);
        if (Dot(c1, c2)>0. && Dot(c1, c3)>eps) t = q, it.p = r, it.i = i, it.j = j;
    }
    return it;
}

double shade(const Point3& p, const Vector3& norm) {
    Vector3 v = g-p; double l = sqrt(v.x*v.x + v.y*v.y + v.z*v.z); v.x /= l; v.y /= l; v.z /= l;
    for (int i=0; i<n; ++i) for (int j=0; j<obj[i].t; ++j) {
        if (abs(Dot(v, obj[i].n[j])) < eps) continue;
        const Point3 &a = obj[i].v[obj[i].f[j][0]], &b = obj[i].v[obj[i].f[j][1]], &c = obj[i].v[obj[i].f[j][2]];
        const Vector3 &n = obj[i].n[j]; double q = Dot(n, a-p) / Dot(n, v);
        if (q < eps || q > l-eps) continue;
        Point3 r = p + v*q; Vector3 c1 = Cross(b-a, r-a), c2 = Cross(c-b, r-b), c3 = Cross(a-c, r-c);
        if (Dot(c1, c2)>eps && Dot(c1, c3)>eps) return 0.;
    }
    return abs(Dot(v, norm));
}

Vector3 get_point_color(const Point3& p, const Vector3& v, const Vector3& oc) {
    return Vector3(oc.x*c.x, oc.y*c.y, oc.z*c.z) * (a + (1.-a)*shade(p, v));
}

bool tir(const Vector3& v, const Vector3& n, double m, double q) {
    double c = Dot(v, n);
    return m*sqrt(1.-c*c) >= q*(1.-eps);
}

Vector3 fl_vec(const Vector3& v, const Vector3& n) {
    return v - n * (2.*Dot(v, n));
}

Vector3 fr_vec(const Vector3& v, const Vector3& n, double m,  double q) {
    double c = Dot(v, n), s = m*sqrt(1.-c*c)/q; Vector3 n1 = n*c, t = v-n1; n1.Normalize(); t.Normalize();
    return n1 * sqrt(1.-s*s) + t * s;
}

Vector3 trace_ray(int d, const Ray& ray) {
    Vector3 c, l, r; Ints it = get_ints(ray.p, ray.v);
    if (it.i >= 0) {
        double fl = obj[it.i].l, fr = obj[it.i].r, m = ray.m==1. ? obj[it.i].m : 1.;
        c = get_point_color(it.p, obj[it.i].n[it.j], obj[it.i].c) * (1. - fl - fr);
        if (d == X) return c;
        if (tir(ray.v, obj[it.i].n[it.j], ray.m, obj[it.i].m)) fr = 0.;
        if (fl > 0.) l = trace_ray(d+1, Ray(it.p, fl_vec(ray.v, obj[it.i].n[it.j]), ray.m)) * fl;
        if (fr > 0.) r = trace_ray(d+1, Ray(it.p, fr_vec(ray.v, obj[it.i].n[it.j], ray.m, m), m)) * fr;
    }
    return c + l + r;
}

void print(double c) {
    int v = int(c*255.+.5), a = v>>4, b = v&15;
    a < 10 ? cout << a : cout << char('a'+a-10); b < 10 ? cout << b : cout << char('a'+b-10);
}

void print(const Vector3& c) {
    print(c.x); print(c.y); print(c.z); cout << ' ';
}

void solve() {
    for (int i=0; i<n; ++i) {
        cin >> obj[i].p;
        for (int j=0; j<obj[i].p; ++j) cin >> obj[i].v[j].x >> obj[i].v[j].y >> obj[i].v[j].z;
        cin >> obj[i].t;
        for (int j=0; j<obj[i].t; ++j) {
            cin >> obj[i].f[j][0] >> obj[i].f[j][1] >> obj[i].f[j][2];
            const Point3 &a = obj[i].v[obj[i].f[j][0]], &b = obj[i].v[obj[i].f[j][1]], &c = obj[i].v[obj[i].f[j][2]];
            Vector3& v = obj[i].n[j] = Cross(b-a, c-a); v.Normalize();
        }
        cin >> obj[i].c.x >> obj[i].c.y >> obj[i].c.z >> obj[i].l >> obj[i].r >> obj[i].m;
    }
    cin >> g.x >> g.y >> g.z >> a >> c.x >> c.y >> c.z >> q;
    while (q--) {
        cin >> p.x >> p.y >> p.z >> t.x >> t.y >> t.z >> up.x >> up.y >> up.z >> f >> w >> h;
        Vector3 z = t-p; z.Normalize(); Vector3 x = Cross(z, up);
        double d = tan(f*M_PI/360.)/w, xi = d*(1-w), y0 = d*(h-1); d *= 2.;
        for (int i=0; i<w; ++i, xi+=d) {
            double yi = y0;
            for (int j=0; j<h; ++j, yi-=d) img[i][j] = trace_ray(0, Ray(p, x*xi + up*yi + z, 1.));
        }
        cout << w << ' ' << h << endl;
        for (int i=0; i<h; ++i) {
            for (int j=0; j<w; ++j) print(img[j][i]);
            cout << endl;
        }
    }
}

int main() {
    while (cin >> n && n) solve();
    return 0;
}