真实感图像渲染系列：光线追踪算法(Ray Tracing)及基于Hash的抗锯齿方法

这是真实感图像渲染系列的第四篇文章。

算法概述

光线追踪算法可以算是图像渲染中的Hello World了，不过这个Hello World可没有那么好写。通过前两篇文章，我们已经知道了渲染算法包含的核心要素，如颜色，物体等表示。

算法本身网上已经有很多详细的教程，多说无益，本质上RayTracing就是最直接的通过视线反推光路，并忽视一切不容易追踪的光路的算法。

光线追踪本身可以处理的光路需要满足两个限制：

只经过了一次漫反射面
漫反射面是作为摄像机到光源光路中最后一个界面存在

我们可以通过一个玻璃球在地上是否会聚焦光线形成光斑来判断一个算法是不是普通的RayTracing。这里，漫反射面（地面）并没有作为光路的最后一个面（中间还插入了玻璃球的投射面）。光线追踪算法会在玻璃球下产生一个黑色的阴影。

算法步骤

下面，我将以最简练的方式概述RayTracing的算法。

对于屏幕上的每一个像素，我们可以通过摄像机(camera)找到一条视线光路，RayTracing算法目的就是得到这条光路的颜色。当然，倘若光路直接射到了光源内部（即与光源产生碰撞），那么颜色就是光源颜色。否则，倘若光路射到了无穷远处，那么我们将提前设置好的背景光颜色作为实现颜色。

多数情况，视线既不会与光源碰撞，也不会到达无穷远处。视线沿着这个光路行进，在物体表面可能由于“折射”，“反射”等而分叉，我们递归得处理折射，反射后视线的颜色。这里，递归总深度，光线强度皆可作为停止递归的信号。

最终，部分视线将到达一个漫反射平面，这时，光线亮度设置为能够直接照亮该位置的光源亮度。对于复杂光源，诸如面光源，我们需要在光源处随机取点，计算出光源中多少光可以不受遮挡到达反射面。

基于hash的边缘超采样

通过基本的光线追踪算法，我们可以得到如下的图片

可以发现，球体的边沿存在较严重的锯齿效应。通过基于hash的边缘超采样后，效果如下

锯齿处的颜色变味了两边颜色的混合，从而在肉眼看来消除了锯齿。

在RayTracing中，实现的函数调用可以看做是一棵树结构，每一个节点都会碰撞一个物体。在每一次碰撞后，我们可以维护光路hash值 $hash' = hash \times 19 + object_{hash}$ 。通过如下方法迭代出来的hash值，只要中途光路的折射顺序有任何细微差别，都会导致hash值的变化。我们对于摄像机每一个像素的hash值进行比较，倘若一个像素四周hash值都和他相同，则其不在边缘上。否则，我们对该像素(x,y)进行超采样。其颜色为(x,y),(x+1/3,y+1/3),(x-1/3,y+1/3),…,(x-1/3,y-1/3)这九个像素位置对应颜色的平均值。

在实际运行中，超采样的运行时间相对会比较长。毕竟稍微复杂一点的场景，会有很多边缘点，而每个边缘点的重采样时间是原来的9倍。

源代码

ray_tracing.h

#ifndef RAYTRACING_H
#define RAYTRACING_H

#include <vector>
#include "../core/light.h"
#include "../core/object.h"
#include "../core/color.h"
#include "scene.h"
#include "json/json.h"
#include "render.h"

class RayTracing : private Scene,public Render{
	private:
		unsigned **hash_table;
		int max_depth;
		int shade_quality;
		int spec_power;
		int start_rows;
		int bazier_quality;
	public:
		//INIT
		RayTracing();
		~RayTracing();
		virtual void accept(const Json::Value& val);


		//RayTrace
		Color calcReflection(const Object& obj, const Collision& obj_coll, int depth, unsigned& hash);
		Color calcRefraction(const Object& obj, const Collision& obj_coll, int depth, unsigned& hash);
		Color calcDiffusion(const Object& obj, const Collision& obj_coll);

		Color rayTrace(const Vector& rayO, const Vector& rayD, int depth, unsigned& hash);

		void run();
};

#endif

ray_tracing.cpp

#include "raytracing.h"
#include <string>
#include <iostream>

#ifdef USE_OPENMP
#include <omp.h>
#pragma message("The openmp is enable!")
#endif

RayTracing::RayTracing() {
}

RayTracing::~RayTracing() {
}

void RayTracing::accept(const Json::Value& val) {
	Render::accept(val);
	Scene::accept(val,rx,ry);

	max_depth = val["max_depth"].asInt();
	shade_quality = val["shade_quality"].asInt();
	spec_power = val["spec_power"].asInt();
	start_rows = val["start_rows"].asInt();
	bazier_quality = val["bazier_quality"].asInt();
	board = new Color[rx*ry];
	for (int i=0;i<rx*ry;i++)
		board[i] = Color(1,1,1);
}


Color RayTracing::calcReflection(const Object& obj, const Collision& obj_coll, int depth, unsigned&hash) {
	if (depth > max_depth) {
		hash = hash * 17 + 233;
		return bg_color;
	}
	hash = hash * 17 + obj.getHash();
	Vector resO,resD;
	obj_coll.reflection(resO,resD);
	return (rayTrace(resO,resD,depth,hash) * obj.getMaterial().refl).adjust();
}

Color RayTracing::calcRefraction(const Object& obj, const Collision& obj_coll, int depth, unsigned& hash) {
	if (depth > max_depth) {
		hash = hash * 19 + 233;
		return bg_color;
	}
	hash = hash * 19 + obj.getHash();
	Vector rayD;
	Vector rayO;
	Color acol;
	obj_coll.refraction(rayO,rayD);
	Color rcol = rayTrace(rayO,rayD,depth,hash);
	if (obj_coll.face)
		rcol = rcol*obj.getMaterial().refr;
	if (!obj_coll.face)
		acol = (obj.getAbsorb().getColor(0,0)*-obj_coll.dist).exp();
	else
		acol = Color(1,1,1);

	return (rcol*acol).adjust();
}

Color RayTracing::calcDiffusion(const Object& obj, const Collision& obj_coll) {
	Color color = obj.getColor(obj_coll.C);
	Color ret = color * bg_color *(1-obj.getMaterial().diff-obj.getMaterial().spec);
	for (auto &lgt : lights) {
		double shade = lgt->getShade(obj_coll.getSurfaceC(),objects,shade_quality);
		ret += color * lgt->getColor(lgt->getCenter()) * shade * obj.getMaterial().diff;
		double spec_ratio = (lgt->getCenter() - obj_coll.C).unit() ^ obj_coll.N.unit();
		if (spec_ratio > 0)
			ret += color * lgt->getColor(lgt->getCenter()) * shade * pow(spec_ratio,spec_power) * obj.getMaterial().spec;
	}
	return ret.adjust();
}

Color RayTracing::rayTrace(const Vector& rayO, const Vector& rayD, int depth, unsigned& hash) {
	Collision obj_coll,lgt_coll;
	const Object* obj = findCollidedObject(rayO,rayD,obj_coll);
	const Light* lgt = findCollidedLight(rayO,rayD,lgt_coll);
	if (!obj && !lgt) {
		hash = hash * 17 + 235;
		return bg_color;
	}else if (!obj || (obj && lgt && obj_coll.dist > lgt_coll.dist)) {
		hash = hash * 17 + lgt->getHash();
		return lgt->getColor(lgt->getCenter());
	}else {
		Color ret;
		if (obj->getMaterial().refl>feps)
			ret += calcReflection(*obj,obj_coll,depth+1,hash);
		if (obj->getMaterial().diff>feps || obj->getMaterial().spec>feps)
			ret += calcDiffusion(*obj,obj_coll);
		if (obj->getMaterial().refr>feps)
			ret += calcRefraction(*obj,obj_coll,depth+1,hash);
		return ret.adjust();
	}
}

void RayTracing::run() {
	hash_table = new unsigned*[rx];
	for (int i=0;i<rx;i++)
		hash_table[i] = new unsigned[ry];
#ifdef USE_OPENMP
#pragma omp parallel
#pragma omp for schedule(dynamic,3)
#endif
	for (int _i=start_rows;_i<rx;_i++){
		int i = _i;
#ifdef USE_OPENMP
		if (!i)
			std::cout<<omp_get_num_threads()<<std::endl;
#endif
		printf("Render row #%d\n",i);
		for (int j=0;j<ry;j++) {
			Vector rayO,rayD;
			camera->getRay(i,j,rayO,rayD);
			Color cc = rayTrace(rayO,rayD,0,hash_table[i][j]);
			board[i*ry+j] = cc;
		}
	}
#ifdef USE_OPENMP
#pragma omp for schedule(dynamic,5)
#endif
	for (int i=0;i<rx;i++) {
		printf("Resample row #%d\n",i);
		for (int j=0;j<ry;j++) {
			bool flag = false;
			if (i!=0 && hash_table[i][j] != hash_table[i-1][j])
				flag = true;
			if (i!=rx-1 && hash_table[i][j] != hash_table[i+1][j])
				flag = true;
			if (j!=0 && hash_table[i][j] != hash_table[i][j-1])
				flag = true;
			if (j!=ry-1 && hash_table[i][j] != hash_table[i][j+1])
				flag = true;
			if (flag) {
				Color res;
				for (int k1=-1; k1<=1; k1++) {
					for (int k2=-1; k2<=1; k2++) {
						unsigned hash = 0;
						Vector rayO,rayD;
						camera->getRay(i+k1/3.0,j+k2/3.0,rayO,rayD);
						res += rayTrace(rayO,rayD,0,hash);
					}
				}
				res = res*(1.0/9);
				board[i*ry + j] = res;
			}
		}
	}
	for (int i=0;i<rx;i++) {
		delete[] hash_table[i];
	}
	delete[] hash_table;
}