UVa12313 A Tiny Raytracer

题目链接

    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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

   注意，只要深度没有达到最大值，不管反射系数是多么小的正数，都应该跟踪反射光线；折射光线也是如此。两个颜色的加法将在随后定义。
   着色
   前面遗留了一个问题，就是如何计算碰撞点的颜色（即上面的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);
1
2
3
4
5
6

   简单起见，只要连接交点和光源的线段被一个物体阻挡（即使该物体反光或者透明），就算作该交点在阴影中。这样做的确会让渲染结果不正确，但在本题中请忽略这个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 
#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145