c++ - 如何将此代码从递归更改为迭代

Question

我试图通过迭代而不是递归的方式实现以下代码(BVH_node类的“命中”功能)，但是我不知道该怎么做。我确实找到了一些与此相关的主题，但是他们没有非常有帮助。有人可以帮我吗？非常感谢。(顺便说一句，这是我第三次提出这个问题，人们说我的问题没有弄清楚，请给我一些有关提出问题的建议)

class Ray {
public:
    vec3 origin;
    vec3 direction;
    float t = 10000.0f;
};
class AABB{
public:
bool hit(Ray ray){
//test if ray hit itself
//but don't write the t into the ray
}
vec3 min;
vec3 max;
};

class Geometry {
public:
    bool hit(Ray& ray) {
        float t;
        //test if the ray hit this geometry
        //ray.origin + t * ray.direction = ......
        //then solve the t
        if (t < ray.t && t>0.0f) {
            ray.t = t;
            return true;
        }

            return false;
    }

private:
    //...some private data
};

class BVH_node {
public:
    void construction(/*......some data for construction*/) {
        //is_node_or_geo = ......
        //if(is_node_or_geo == 0)
        //L_node = ......; R_node = ......;
        //if(is_node_or_geo == 1)
        //L_geo = ......; R_geo = ......;
    }
    bool hit(Ray& ray) {
        if(aabb.hit(ray)){
        if (is_node_or_geo == 0) {
            bool hit_left = L_node->hit(ray);
            bool hit_right = R_node->hit(ray);
            return hit_left || hit_right;
        }
        if (is_node_or_geo == 1) {
            bool hit_left = L_geo->hit(ray);
            bool hit_right = R_geo->hit(ray);
            return hit_left || hit_right;
        }
    }
    return false;
    }
private:
    int is_node_or_geo;//node = 0,geo = 1
    AABB aabb;
    BVH_node* L_node;
    BVH_node* R_node;
    Geometry* L_geo;
    Geometry* R_geo;
};

int main(){
    BVH_node* root = new BVH_node;
    root->construction(/*.......*/);
    Ray ray;//ray = .......;
    bool hit = root->hit(ray);
    delete root;
}

我发现的有关如何将递归更改为迭代的大多数教程(例如 http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html)都没有考虑成员变量涉及的某些情况。

Answer 1

跟进Alan Birtles的评论中提到的方法:
让我们专注于hit函数。为了使我们的生活更轻松，最好首先将其重写如下:

bool hit(Ray& ray) {
    if(!aabb.hit(ray)) return false;

    if (is_node_or_geo == 0) {
        if (L_node->hit(ray)) return true;
        if (R_node->hit(ray)) return true;
        return false;

    } else if (is_node_or_geo == 1) {
        if (L_geo->hit(ray)) return true;
        if (R_geo->hit(ray)) return true;
        return false;
    }
}

现在，我们可以添加一个循环和一个堆栈(用 std::vector实现，因为我对 std::stack不熟悉)。我们还将方法 static设置为，因为它与单个对象无关:

static bool hit(Ray& ray, BVH_node * root) {

    std::vector<BVH_node *> nodes {root};

    while (!nodes.empty()){
        BVH_node & top = *nodes.back();
        nodes.pop_back();

        if(!top.aabb.hit(ray)) continue;

        if (top.is_node_or_geo == 0) {
            nodes.push_back(top.L_node);
            nodes.push_back(top.R_node);
            continue;

        } else if (top.is_node_or_geo == 1) {
            if (top.L_geo->hit(ray)) return true;
            if (top.R_geo->hit(ray)) return true;
            continue;
        }
    }
    return false;
}

该代码未经测试，因此可能需要进行细微调整。
请注意，根据您的实现，您可能需要在每次提及 const之后添加一串 BVH_node