Assignment 5¶
文本统计：约 1665 个字 • 497 行代码
这一次作业实现的内容是增加了网格结构，为后续加速图形相交提供了基础。整体难度比之前要大，各种函数的使用逻辑更加复杂。
整体思路是将 grid 视为一个 primitive，但是这个是不放到 group 里面去的，可以选择单独渲染。
Tasks¶
（1）给 Object3D 类 增加一个指向 BoundingBox的指针，代表这个物体的包围盒，相应地增加访问函数 BoundingBox* Object3D::getBoundingBox()
同时对派生类的包围盒进行初始化，注意不用初始化平面的包围盒。
（2）增加 Object3D 的派生类 Grid，相应的参数有网格在三个维度的分割数量，同时还有一个记录每个网格信息的变量，一开始仅仅只需要存储一个网格中是否含有物体，之后改为存储包含这个网格的物体的数组。
（3）给 Object3D 类中增加一个新的方法
注意这个函数并不是纯虚函数，这个函数不一定需要在派生类中重写，用于将该物体插入到网格中，这个函数是保守的，意思就是包含该物体的一定插入，不包含该物体的也可能插入（为了方便计算）。
（4）给 RayTracer 类增加一个指向 Grid 的指针，增加命令行参数：nx, ny, nz, visualizeGrid，分别代表 Grid 在三个方向的格数以及是否显示网格。根据这些参数对 Grid 进行初始化，然后将所有的物体调用 insertIntoGrid 插入到 Grid 中，要完成这个需要写 Group::insertIntoGrid 用于插入group中的所有物体
完成上述内容后，开始着手完成 Grid 的相关内容，我们需要完成 Grid::paint() 以及 Grid::intersect
（5）对于前者来说，比较容易，我们可以选择渲染被标记的格子的6个面，当然我们可以省略那些在物体中间被遮挡的面，只渲染被标记与不被标记的各自之间的面，注意面的法线方向。
（6）而为了实现后者我们需要完成一个 Grid 的辅助类 MarchingInfo，用于跟踪光线在网格中的穿行过程，我们使用的是 3DDDA（3D-DDA) 这样效率更高，而不用一个格子一个格子循环的去判断。
在这个 MarchingInfo 类中，需要记录的是
int i,j,k; //代表当前光线处在哪个格子里面
float tMin; //光线传播了多久了
float tNextX, tNextY, tNextZ; //到达某一维度下一个格子还需要的时间
float dTx, dTy, dTz; //穿越某一维度一个格子需要的时间
int signX, signY, signZ; //光线在某一维度的方向
先初始化，让光线先打到 Grid 上（实际上就是打到包围盒上），然后再慢慢在网格中移动，直到触碰到被标记的物体，或者射出了 Grid。前者写一个函数
后者写一个函数
为了更好地 debug，题目提供了一些可视化函数，用于描述光线经过的面，可以选择将光线经过的 grid 都展现出来，也可以选择只展示经过的面。
（7）然后更改前面简单的记录格子中是否有物体，改为物体的数组
（8）接着处理变换的部分，完成 Transform 下的 insertIntoGrid ，注意 Transform 可能会发生嵌套
这里是题目原文：But it's also easy to just push all the transformations down to the primitive objects. Now we'll use the 2nd argument (Matrix *m) to Object3D::insertIntoGrid (and it's derived methods). Initially m = NULL. When you encounter a transformation node in the hierarchy you will concatenate it to the previous transformation (if any). Make sure you apply the transformations in the correct order.
Implementation¶
BoundingBox¶
求包围盒主要是对于 Sphere triangle group transform 类
Sphere(const Vec3f ¢er, float radius,Material *m) :
center(center), radius(radius),Object3D(m) {
Vec3f min = center - Vec3f(radius, radius, radius);
Vec3f max = center + Vec3f(radius, radius, radius);
boundingBox = new BoundingBox(min, max);
}
Triangle(Vec3f &a, Vec3f &b, Vec3f &c, Material *m) : Object3D(m) {
v0 = a;
v1 = b;
v2 = c;
Vec3f::Cross3(normal, v1 - v0, v2 - v0);
normal.Normalize();
Vec3f min = Vec3f(std::min(std::min(v0.x(), v1.x()), v2.x()),
std::min(std::min(v0.y(), v1.y()), v2.y()),
std::min(std::min(v0.z(), v1.z()), v2.z()));
Vec3f max = Vec3f(std::max(std::max(v0.x(), v1.x()), v2.x()),
std::max(std::max(v0.y(), v1.y()), v2.y()),
std::max(std::max(v0.z(), v1.z()), v2.z()));
boundingBox = new BoundingBox(min, max);
}
group 的包围盒就是底下物体包围盒的并，放到 addobject 函数中，解析器每解析出一个物体，就将包围盒与现有 group 的包围盒求并，如果原来原来没有包围盒就新创建一个。
void addObject(int index, Object3D *object){
assert(index<objectNum);
objects[index] = object;
auto bb = object->getBoundingBox();
if (boundingBox == nullptr)
{
boundingBox = new BoundingBox(*bb);
}
else if (bb != nullptr)
{
boundingBox->Extend(bb);
}
}
transform 类的包围盒就是先得到未变换的物体的包围盒，然后将包围盒的八个点进行变换，得到的东西再求一个包围盒。代码比较冗长，这里略。
Grid¶
这是这次作业的重点，分为 (1) 类的定义 (2) insertIntoGrid()(3) Grid::paint() (4) Grid::intersect 四部分来阐述。
类的定义¶
class Grid : public Object3D {
public:
Grid(BoundingBox *bb, int nx, int ny, int nz){
this->boundingBox = bb;
this->nx = nx;
this->ny = ny;
this->nz = nz;
dx = (bb->getMax().x() - bb->getMin().x()) / nx;
dy = (bb->getMax().y() - bb->getMin().y()) / ny;
dz = (bb->getMax().z() - bb->getMin().z()) / nz;
//一开始是简单的做标记
//isopaque = new bool[nx * ny * nz];
//for (int i = 0; i < nx * ny * nz; i++) {
// isopaque[i] = false;
//}
//后来每个格子都存储了 Object3D 的数组
objects = new Object3DVector[nx * ny * nz];
}
~Grid() {
delete[] objects;
}
bool intersect(const Ray &r, Hit &h, float tMin) override;
void paint() override;
//下面五个函数是用来获得 grid 的相关信息的
std::tuple<int, int, int> getGridSize() {
return {nx, ny, nz};
}
Vec3f getVoxelSize() {
return {dx, dy, dz};
}
Vec3f getVoxelCenter(int i, int j, int k) {
return Vec3f(boundingBox->getMin().x() + (i + 0.5) * dx,
boundingBox->getMin().y() + (j + 0.5) * dy,
boundingBox->getMin().z() + (k + 0.5) * dz);
}
//这个函数是为了方便后面画出Grid
std::array<Vec3f, 8> getVoxelVertices(int i, int j, int k) {
auto bMin = boundingBox->getMin();
auto p1 = bMin + Vec3f(i * dx, j * dy, k * dz),
p2 = bMin + Vec3f((i + 1) * dx, j * dy, k * dz),
p3 = bMin + Vec3f((i + 1) * dx, (j + 1) * dy, k * dz),
p4 = bMin + Vec3f(i * dx, (j + 1) * dy, k * dz),
p5 = bMin + Vec3f(i * dx, j * dy, (k + 1) * dz),
p6 = bMin + Vec3f((i + 1) * dx, j * dy, (k + 1) * dz),
p7 = bMin + Vec3f((i + 1) * dx, (j + 1) * dy, (k + 1) * dz),
p8 = bMin + Vec3f(i * dx, (j + 1) * dy, (k + 1) * dz);
return {p1, p2, p3, p4, p5, p6, p7, p8};
}
Vec3f getMin() const {
return boundingBox->getMin();
}
/*
void setOpaque(int i, int j, int k) {
isopaque[i * ny * nz + j * nz + k] = true;
}
bool isOpaque(int i, int j, int k) {
return isopaque[i * ny * nz + j * nz + k];
}
*/
bool occupied(int i, int j, int k) {
assert (i >=0 && i< nx);
assert (j >=0 && j< ny);
assert (k >=0 && k< nz);
return objects[i * ny * nz + j * nz + k].getNumObjects()>0;
}
void insertObject(int x, int y, int z, Object3D *obj) {
assert(x>=0&&x<nx);
assert(y>=0&&y<ny);
assert(z>=0&&z<nz);
objects[x * ny * nz + y * nz + z].addObject(obj);
}
int initializeRayMarch(MarchingInfo &mi, const Ray &r, float tmin) const;
void hitFace (BoundingBox *bb, MarchingInfo &mi, int ret,
Vec3f &p1, Vec3f &p2, Vec3f &p3, Vec3f &p4, Vec3f &normal);
protected:
int nx, ny, nz;
float dx, dy, dz;
//bool *isopaque;
Object3DVector *objects;
};
insertIntoGrid¶
insertIntoGrid 为 Object3D 的一个虚函数，可以被派生类所重写
sphere 类，注意一下这里处理变换的细节，采用的是逆变换网格来判断变换后的球是否在网格中，因为球相应的变换写起来比较困难
void Sphere::insertIntoGrid(Grid *g, Matrix *m) {
Vec3f min = boundingBox->getMin();
Vec3f max = boundingBox->getMax();
Vec3f size = g->getVoxelSize();
int nx, ny, nz;
std::tie(nx, ny, nz) = g->getGridSize();
float diaghalf = size.Length() / 2;
Matrix mInv;
if (m!= nullptr) m->Inverse(mInv);
for (int i = 0; i < nx; i++) {
for (int j = 0; j < ny; j++) {
for (int k = 0; k < nz; k++) {
Vec3f Voxcenter = g->getVoxelCenter(i, j, k);
if (m!= nullptr) mInv.Transform(Voxcenter);
if ((Voxcenter-center).Length() <= radius+diaghalf)
g->insertObject(i, j, k,this);
}
}
}
}
triangle 类，这里就是直接将斌桓侯的包围盒直接全部标记
void Triangle::insertIntoGrid(Grid *g, Matrix *m)
{
int nx, ny, nz;
std::tie(nx, ny, nz) = g->getGridSize();
Vec3f voxel = g->getVoxelSize();
Vec3f ta = v0, tb = v1, tc = v2;
Vec3f pMin = g->getMin();
if (m != nullptr)
{
m->Transform(ta);
m->Transform(tb);
m->Transform(tc);
}
auto min = Vec3f(std::min({ta.x(), tb.x(), tc.x()}),
std::min({ta.y(), tb.y(), tc.y()}),
std::min({ta.z(), tb.z(), tc.z()})),
max = Vec3f(std::max({ta.x(), tb.x(), tc.x()}),
std::max({ta.y(), tb.y(), tc.y()}),
std::max({ta.z(), tb.z(), tc.z()}));
auto iMin = (int) floor((min.x() - pMin.x()) / voxel.x()),
iMax = (int) ceil((max.x() - pMin.x()) / voxel.x()),
jMin = (int) floor((min.y() - pMin.y()) / voxel.y()),
jMax = (int) ceil((max.y() - pMin.y()) / voxel.y()),
kMin = (int) floor((min.z() - pMin.z()) / voxel.z()),
kMax = (int) ceil((max.z() - pMin.z()) / voxel.z());
for (int i = std::max(iMin, 0); i <= std::min(iMax, nx - 1); i++) {
for (int j = std::max(jMin, 0); j <= std::min(jMax, ny - 1); j++) {
for (int k = std::max(kMin, 0); k <= std::min(kMax, nz - 1); k++) {
g->insertObject(i, j, k, this);
}
}
}
}
transform 类，本身就要完成一次变换（this->m），然后还要来一次变换 m，两次变换叠加
void insertIntoGrid(Grid *g, Matrix *m) override {
auto nowmat = Matrix(this->m);
if (m != nullptr) {
nowmat = (*m) * nowmat;
}
object->insertIntoGrid(g, &nowmat);
}
从这里更可以看出，在该函数中加入矩阵这一项就是为了完成变换的一层一层嵌套
嵌套 Transform
最后完成 group 类
void Group::insertIntoGrid(Grid *g, Matrix *m) {
for (int i = 0; i < objectNum; i++) {
objects[i]->insertIntoGrid(g, m);
}
}
Grid::paint()¶
关于 Grid::paint() 在 Tasks 中已经阐述的比较清楚了，就是每一个格子分别判断六个面是不是起始面或者终止面以及被标记与不被标记的分界面。
void Grid::paint() {
auto bMin = boundingBox->getMin();
for (int i = 0; i < nx; i++) {
for (int j = 0; j < ny; j++) {
for (int k = 0; k < nz; k++) {
if (!occupied(i, j, k)) continue;
std::array<Vec3f, 8> vertices = getVoxelVertices(i, j, k);
Vec3f p1 = vertices[0];
Vec3f p2 = vertices[1];
Vec3f p3 = vertices[2];
Vec3f p4 = vertices[3];
Vec3f p5 = vertices[4];
Vec3f p6 = vertices[5];
Vec3f p7 = vertices[6];
Vec3f p8 = vertices[7];
glBegin(GL_QUADS);
if (k == 0 || !occupied(i, j, k - 1))
{
glNormal3f(0, 0, -1);
glVertex3f(p1.x(), p1.y(), p1.z());
glVertex3f(p2.x(), p2.y(), p2.z());
glVertex3f(p3.x(), p3.y(), p3.z());
glVertex3f(p4.x(), p4.y(), p4.z());
}
if (k == nz - 1 || !occupied(i, j, k + 1))
{
glNormal3f(0, 0, 1);
glVertex3f(p5.x(), p5.y(), p5.z());
glVertex3f(p6.x(), p6.y(), p6.z());
glVertex3f(p7.x(), p7.y(), p7.z());
glVertex3f(p8.x(), p8.y(), p8.z());
}
if (j == 0 || !occupied(i, j - 1, k))
{
glNormal3f(0, -1, 0);
glVertex3f(p1.x(), p1.y(), p1.z());
glVertex3f(p2.x(), p2.y(), p2.z());
glVertex3f(p6.x(), p6.y(), p6.z());
glVertex3f(p5.x(), p5.y(), p5.z());
}
if (j == ny - 1 || !occupied(i, j + 1, k))
{
glNormal3f(0, 1, 0);
glVertex3f(p3.x(), p3.y(), p3.z());
glVertex3f(p4.x(), p4.y(), p4.z());
glVertex3f(p8.x(), p8.y(), p8.z());
glVertex3f(p7.x(), p7.y(), p7.z());
}
if (i == 0 || !occupied(i - 1, j, k))
{
glNormal3f(-1, 0, 0);
glVertex3f(p1.x(), p1.y(), p1.z());
glVertex3f(p4.x(), p4.y(), p4.z());
glVertex3f(p8.x(), p8.y(), p8.z());
glVertex3f(p5.x(), p5.y(), p5.z());
}
if (i == nx - 1 || !occupied(i + 1, j, k))
{
glNormal3f(1, 0, 0);
glVertex3f(p2.x(), p2.y(), p2.z());
glVertex3f(p3.x(), p3.y(), p3.z());
glVertex3f(p7.x(), p7.y(), p7.z());
glVertex3f(p6.x(), p6.y(), p6.z());
}
glEnd();
}
}
}
}
Grid::intersect¶
Grid::intersect 的难度要更大一些，需要两个辅助函数 Grid::initializeRayMarch 以及MarchingInfo::nextCell 以及一个辅助的类 MarchingInfo，来记录光线的移动
class MarchingInfo{
public:
float tMin;
int i,j,k;
float tNextX, tNextY, tNextZ;
float dTx, dTy, dTz;
int signX, signY, signZ;
Grid* grid;
bool valid; //代表光线是否还在grid中
int nextCell();
};
注意一下，返回值的意思是现在触及到的面的法向量是哪个轴的。0为x轴，1为y轴，2为z轴。
int Grid::initializeRayMarch(MarchingInfo &mi, const Ray &r, float tmin) const
{
int ret; //代表光线从哪个方向的面进入
Vec3f rayDir = r.getDirection();
Vec3f rayOrigin = r.getOrigin();
Vec3f pMin = boundingBox->getMin();
Vec3f pMax = boundingBox->getMax();
//平行的情况
for (int i = 0; i < 3; i++)
{
if(rayDir[i] == 0 && (rayOrigin[i] < pMin[i] || rayOrigin[i] > pMax[i]))
{
mi.valid = false;
return -1;
}
}
//包围盒的算法
float tNear,tFar;
for (int i = 0; i < 3; i++)
{
float t1 = (pMin[i] - rayOrigin[i]) / rayDir[i];
float t2 = (pMax[i] - rayOrigin[i]) / rayDir[i];
if(t1 > t2)
{
float temp = t1;
t1 = t2;
t2 = temp;
}
if (i == 0 || tNear < t1)
{
tNear = t1;
ret = i;
}
if (i == 0 || tFar > t2)
{
tFar = t2;
}
}
if (tNear > tFar || tFar < tmin)
{
mi.valid = false;
return -1;
}
mi.valid = true;
mi.dTx = std::abs(dx / rayDir.x());
mi.dTy = std::abs(dy / rayDir.y());
mi.dTz = std::abs(dz / rayDir.z());
mi.signX = rayDir.x() < 0 ? -1 : 1;
mi.signY = rayDir.y() < 0 ? -1 : 1;
mi.signZ = rayDir.z() < 0 ? -1 : 1;
//光线起始点在外面
if (tNear > tmin)
{
mi.tMin = tNear;
}
//光线起始点在内部
else
{
mi.tMin = tmin;
ret = -1;
}
Vec3f p = rayOrigin + mi.tMin * rayDir - pMin;
mi.i = std::min((int) (p.x() / dx), nx - 1);
mi.j = std::min((int) (p.y() / dy), ny - 1);
mi.k = std::min((int) (p.z() / dz), nz - 1);
mi.tNextX = ((mi.i + (mi.signX < 0 ? 0 : 1)) * dx + pMin.x() - rayOrigin.x()) / rayDir.x();
mi.tNextY = ((mi.j + (mi.signY < 0 ? 0 : 1)) * dy + pMin.y() - rayOrigin.y()) / rayDir.y();
mi.tNextZ = ((mi.k + (mi.signZ < 0 ? 0 : 1)) * dz + pMin.z() - rayOrigin.z()) / rayDir.z();
mi.grid = const_cast<Grid*>(this);
return ret;
}
在 tNextX tNextY tNextZ 三个中选择最快的，说明这个是下一个打到的面
int MarchingInfo::nextCell()
{
int ret;
tMin = std::min({tNextX, tNextY, tNextZ});
if (tMin == tNextX)
{
tNextX += dTx;
i += signX;
ret = 0;
}
else if (tMin == tNextY)
{
tNextY += dTy;
j += signY;
ret = 1;
}
else
{
tNextZ += dTz;
k += signZ;
ret = 2;
}
int nx, ny, nz;
std::tie(nx, ny, nz) = grid->getGridSize();
if ((i < 0 || i >= nx) || (j < 0 || j >= ny) || (k < 0 || k >= nz))
{
valid = false;
}
return ret;
}
由于我选择可视化打到的面，为方便得到四个点，还写了一个函数 Grid::hitFace 用来返回打到的面的四个顶点以及法向量
void Grid::hitFace (BoundingBox *bb, MarchingInfo &mi, int ret,
Vec3f &p1, Vec3f &p2, Vec3f &p3, Vec3f &p4, Vec3f &normal)
{
Vec3f min = bb->getMin();
int i = mi.i, j = mi.j, k = mi.k;
if (ret == 0)
{
if (mi.signX < 0) i++;
p1 = min + Vec3f(i*dx, j*dy, k*dz);
p2 = min + Vec3f(i*dx, j*dy, (k+1)*dz);
p3 = min + Vec3f(i*dx, (j+1)*dy, (k+1)*dz);
p4 = min + Vec3f(i*dx, (j+1)*dy, k*dz);
normal.Set(1,0,0);
}
else if (ret == 1)
{
if (mi.signY < 0) j++;
p1 = min + Vec3f(i*dx, j*dy, k*dz);
p2 = min + Vec3f((i+1)*dx, j*dy, k*dz);
p3 = min + Vec3f((i+1)*dx, j*dy, (k+1)*dz);
p4 = min + Vec3f(i*dx, j*dy, (k+1)*dz);
normal.Set(0,1,0);
}
else if (ret == 2)
{
if (mi.signZ < 0) k++;
p1 = min + Vec3f(i*dx, j*dy, k*dz);
p2 = min + Vec3f((i+1)*dx, j*dy, k*dz);
p3 = min + Vec3f((i+1)*dx, (j+1)*dy, k*dz);
p4 = min + Vec3f(i*dx, (j+1)*dy, k*dz);
normal.Set(0,0,1);
}
}
利用上面的三个函数，我就可以实现 Grid::intersect 函数了
bool Grid::intersect(const Ray &r, Hit &h, float tMin)
{
Material* m = new PhongMaterial(
{1,1,1},{0,0,0},1,
{0,0,0},{0,0,0},1
);
MarchingInfo mi;
//先初始化，让光线先打到grid上
int ret = initializeRayMarch(mi, r, tMin);
//穿过透明项
while (mi.valid && !occupied(mi.i, mi.j, mi.k))
{
Vec3f p1, p2, p3, p4, normal;
hitFace(boundingBox, mi, ret, p1, p2, p3, p4, normal);
if (r.getDirection().Dot3(normal) > 0) normal.Negate();
//绘制穿过的面
RayTree::AddHitCellFace(p1, p2, p3, p4, normal, m);
ret = mi.nextCell();
}
//如果穿过透明的项后直接出去了，说明无交点
//如果 mi.valid 仍为真，那么说明打到了grid
if (mi.valid)
{
Vec3f p1, p2, p3, p4, normal;
hitFace(boundingBox, mi, ret, p1, p2, p3, p4, normal);
if (r.getDirection().Dot3(normal) > 0) normal.Negate();
m->setDiffuseColor(getColor(mi.i, mi.j, mi.k));
//绘制打到的面
RayTree::AddEnteredFace(p1, p2, p3, p4, normal, m);
h.set(mi.tMin, m, normal,r);
return true;
}
return false;
}
Summary¶
本次作业可谓是耗神耗力，前前后后花了三天时间，期间不停地修改，检查bug，筋疲力尽；好在最后顺利完成了相应的内容。遇到的主要bug大致如下
-
使用C++ 20，出现莫名其妙的错误，无法解决，改回C++ 14
-
写渲染函数的时候，把
auto tracer = new RayTracer(scene, maxBounces, cutoffWeight);放到循环里面去了，导致内存爆炸。
void RayTracerRenderer::Render() {
Renderer::Render(); // preparations
auto tracer = new RayTracer(scene, maxBounces, cutoffWeight);
for (int i = 0; i < image->Width(); i++) {
for (int j = 0; j < image->Height(); j++) {
auto ray = camera->generateRay(Vec2f((float) i / image->Width(),
(float) j / image->Height()));
Hit hit;
image->SetPixel(i, j, tracer->traceRay(ray, camera->getTMin(), 0, 1, 1, hit));
//printf("%d %d\n",i,j);
}
}
}
最后我在写文档的时候，按照题目要求将grid染上了颜色，相关内容未写入文档，实际上只需要更改相应的材质即可。
下次作业一定要将题目要求完全搞清楚再写（虽然及其痛苦），将各个函数的逻辑什么的理理顺，不然写的时候就是一团浆糊。还有四个 Assignment，希望能在寒假前写完，呜呜呜~
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！