如何保留类的实例列表? [英] How to keep a list of instances of a class?

问题描述

我正在用 C++ 编写光线追踪器，需要能够检查场景中每个对象的交集(稍后会进行优化)，为此，我需要保留一个正在运行的类实例列表.创建新实例时更新的指针列表将不起作用，因为据我所知，在初始化后无法增加数组的大小.如果有的话，我真的很想要一个内置的(到 C++)解决方案.

I'm writing a raytracer in C++ and need to be able to check intersections with every object in a scene (optimizations will come later), and to do this, I need to keep a running list of class instances. A list of pointers, updated when a new instance is created, won't work because as far as I know there is no way to increase the size of the array after it is initialized. I'd really like a built-in (to C++) solution if there is one.

推荐答案

我正在用 C++ 编写光线追踪器，需要能够检查场景中每个对象的交集 [...]

I'm writing a raytracer in C++ and need to be able to check intersections with every object in a scene [...]

标准方法是空间图.最常用的是八叉树，因为它们可以表示 3 维空间中的位置.简单地说，空间树看起来像这样:

The standard approach is a spatial graph. Most commonly, octrees are used, since they can express location in 3-dimensional space. Trivially, the spatial tree would look something like this:

struct SpatialNode {
    SpatialNode * children[8];
    std::vector<object*> objects;
};

每个节点都有一个(隐式或显式)位置和大小.当一个新对象被添加到世界场景中时，树会穿过子元素(它们占据被 xy、yz 和 zx 平面分割的八分圆:上面 4 个，下面 4 个；左边 4 个，右边 4 个；后面 4 个), 4 在前面)并且对象仅添加到可以完全包含它的最小节点.(显然，您需要能够计算对象的尺寸以及它们是否可以完全包含在给定区域内.)

Each node has an (implicit or explicit) position and size. When a new object is added to the world scene, the tree is walked through the children (which occupy the octants that are split by the x-y, y-z, and z-x planes: 4 above, 4 below; 4 left, 4 right; 4 behind, 4 in front) and the object is added only to the smallest node that can fully contain it. (Obviously, you'll need to be able to calculate the dimensions of your object and whether they can be fully contained within a given region.)

这样做的好处是相当快(只有被检查的树的部分实际上是相关的)，无论是在填充它还是在搜索它.您可以在维基百科、GameDev.net 和其他地方阅读有关它的几篇文章.

This has the benefit of being fairly fast (only the portions of the tree that are examined are actually relevant), both in populating it and in searching it. There are several articles on it that you can read at Wikipedia, GameDev.net, and elsewhere.

这篇关于如何保留类的实例列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！