原理

把整个空间一次分成八个卦限。每个卦限存放在八叉树的某个节点中。父节点存放未分割的空间。

叶节点存放与该空间有重叠的三角面。

需要用到的 API

Mesh->getBoundingBox()
获得整个 Mesh 所在的 BoundingBox。
Mesh->getBoundingBox(uint32_t idx)
获得下标为 idx 的三角面所在的 BoundingBox
BoundingBox3f(const Vector3f &min, const Vector3f &max)
获得以 min 和 max 两个三维空间中的点为体对角线的 BoundingBox
BoundingBox.getCenter()
获得该 BoundingBox 的中心所在坐标。
BoundingBox.getCorner(int idx)
获得该 BoundingBox 的第 idx 个角的坐标。
BoundingBox.overlaps(BoundingBox)
返回两个 BoundingBox 是否有交叠。
BoundingBox.rayIntersect(ray)
返回 ray 光线是否穿过该 BoundingBox。
BoundingBox.distanceTo(Point)
返回该 BoundingBox 到给定 Point 的最近距离。

具体实现

Part 1: Octree construction

八叉树的构造

节点构造

每个节点如下构造：

class OctNode {
   public:
    OctNode(BoundingBox3f);
    virtual ~OctNode(){};

    OctNode* son[8];
    BoundingBox3f bbox;
};

class OctLeaf : public OctNode {
   public:
    OctLeaf(std::vector<uint32_t>, BoundingBox3f);
    virtual ~OctLeaf(){};

    std::vector<uint32_t> indice;
};

所有的儿子节点存放在 son[8] 指针数组中。

每个节点的 BoundingBox 存放在 bbox 中。

叶节点包含的三角面下标存放在 vector<uint32_t> indice 中。

树的生成

根据官方提示，对原来的 build 做如下修改和重载：

void Accel::build() {
    std::vector<uint32_t> triangles;
    for (uint32_t idx = 0; idx < m_mesh->getTriangleCount(); ++idx) {
        triangles.push_back(idx);
    }
    m_tree = build(m_mesh->getBoundingBox(), triangles, 0);
}

OctNode* Accel::build(BoundingBox3f box, std::vector<uint32_t> triangles, uint32_t depth) {
    if (triangles.empty())
        return nullptr;
    if (triangles.size() <= MAX_TRIANGLE || depth >= MAX_DEPTH)
        return new OctLeaf(triangles, box);

    std::vector<uint32_t> list[8];
    BoundingBox3f bbox[8];

    for (int i = 0; i < 8; i++) {
        Vector3f min_point, max_point;
        Vector3f center = box.getCenter();
        Vector3f corner = box.getCorner(i);
        for (int j = 0; j < 3; j++) {
            min_point[j] = std::min(center[j], corner[j]);
            max_point[j] = std::max(center[j], corner[j]);
        }
        bbox[i] = BoundingBox3f(min_point, max_point);
    }

    for (auto triangle : triangles) {
        for (int i = 0; i < 8; i++) {
            if (m_mesh->getBoundingBox(triangle).overlaps(bbox[i])) {
                list[i].push_back(triangle);
            }
        }
    }

    OctNode* node = new OctNode(box);
    for (int i = 0; i < 8; i++) {
        node->son[i] = build(bbox[i], list[i], depth + 1);
    }
    return node;
}

Part 2: Ray traversal

使用八叉树对空间求交进行初步加速。

针对 rayIntersect 函数进行修改和重载。

bool Accel::rayIntersect(OctNode* node, uint32_t& f, Ray3f& ray, Intersection& its, bool shadowRay) const {
    bool foundIntersection = false;

    if (OctLeaf* leaf = dynamic_cast<OctLeaf*>(node)) {
        for (const auto& idx : leaf->indice) {
            float u, v, t;
            if (m_mesh->rayIntersect(idx, ray, u, v, t) && t < ray.maxt) {
                if (shadowRay)
                    return true;
                ray.maxt = its.t = t;
                its.uv = Point2f(u, v);
                its.mesh = m_mesh;
                f = idx;
                foundIntersection = true;
            }
        }
    } else {
        for (const auto& son : node->son) {
            if (!son)
                continue;
            if (!son->bbox.rayIntersect(ray))
                continue;
            foundIntersection |= rayIntersect(son, f, ray, its, shadowRay);
        }
    }
    return foundIntersection;
}

bool Accel::rayIntersect(const Ray3f& ray_, Intersection& its, bool shadowRay) const {
    bool foundIntersection = false;  // Was an intersection found so far?
    uint32_t f = (uint32_t)-1;       // Triangle index of the closest intersection

    Ray3f ray(ray_);  /// Make a copy of the ray (we will need to update its '.maxt' value)

    // /* Brute force search through all triangles */
    // for (uint32_t idx = 0; idx < m_mesh->getTriangleCount(); ++idx) {
    //     float u, v, t;
    //     if (m_mesh->rayIntersect(idx, ray, u, v, t) && t < ray.maxt) {
    //         /* An intersection was found! Can terminate
    //            immediately if this is a shadow ray query */
    //         if (shadowRay)
    //             return true;
    //         ray.maxt = its.t = t;
    //         its.uv = Point2f(u, v);
    //         its.mesh = m_mesh;
    //         f = idx;
    //         foundIntersection = true;
    //     }
    // }

    foundIntersection = rayIntersect(m_tree, f, ray, its, shadowRay);

    // PA3 update:
    if (shadowRay)
        return foundIntersection;

    if (foundIntersection) {
        // ...
    }
}

做 PA3 时回来 update：

rayIntersect 中没有考虑 shadowRay 情况。导致 PA3 中点光源情况爆炸。

从八叉树根节点开始查找，如果某个父节点与光线没有交，则该节点的所有儿子与该光线都没有交。

经过此次优化，PA1 中的 bunny.xml 渲染时间从 1.5 s 加速到 62 ms，PA2 中的 ajax_normal.xml 渲染用时 2.8 s。

Part 3: Improved ray traversal

使用 std::sort 进行进一步优化。

由于只需要找到光线最先穿过的三角面，因此每次查找时可以先对所有的儿子节点进行排序。依据其距离光线发出点的距离进行排序。如果在较近的儿子节点中找到了有交点的三角面，则不用继续在其他儿子节点中寻找。

对 rayIntersect 函数进行如下修改：

bool Accel::rayIntersect(OctNode* node, uint32_t& f, Ray3f& ray, Intersection& its, bool shadowRay) const {
    bool foundIntersection = false;

    if (OctLeaf* leaf = dynamic_cast<OctLeaf*>(node)) {
        // ...
    } else {
        std::pair<OctNode*, float> sons[8];
        int tot_son = 0;
        for (const auto& son : node->son) {
            if (!son)
                continue;
            if (!son->bbox.rayIntersect(ray))
                continue;
            sons[tot_son++] = std::make_pair(son, son->bbox.distanceTo(ray.o));
        }
        std::sort(sons, sons + tot_son, [](const auto& a, const auto& b) { return a.second < b.second; });
        for (int i = 0; i < tot_son; i++) {
            foundIntersection |= rayIntersect(sons[i].first, f, ray, its, shadowRay);
            // PA4 update:
            // if (foundIntersection)
            //     break;
        }
    }
    return foundIntersection;
}