实例数据管理

Question

我试着用实例画几千个粒子。它正在工作，而且速度很快，但我有一个瓶颈来减缓整个程序的速度。

我的Particle类类似于以下内容：

public class Particle
{
    public Vector2 Position;

    //More data not used for drawing
    //....
}

现在，在我的DrawLoop()中，我得到了这样的东西：

Vector2[] instanceData = new Vector2[numParticles];

public void Draw()
{
    for(int i = 0; i < numParticles; ++i)
        instanceData[i] = Particles[i].Position; //THAT'S the slow part

    instanceBuffer.SetData(instanceData);

    //Now draw VertexBuffer using instancing
    //...
}

我试过使用Parallel.For，但速度还不够快，因为我有大约8000个粒子。此外，我还查看了来自MSDN的particlesystem示例。但是它们的Particle结构只包含绘制粒子的数据，并且位置是在着色器中计算的。但是，我需要一些算法的额外数据。

我想不出一个类的设计，所以我不需要为每个帧的数组分配粒子位置。

Answer 1

由于这个问题最终是由正在使用的数据结构引起的，所以让我向您介绍一个常见的替代方案，用于类似此场景的链接列表。

链接列表通常不是存储粒子的好主意，原因有两个:第一，您不能像这里所发现的那样，随机地访问它们；第二个，链接列表的参考地点很差。考虑到粒子系统的性能要求，后一点可能是致命的。

标准列表具有更好的引用局部性，但正如您已经发现的，添加和删除项可能很慢，这是粒子引擎中常见的事情。

我们能改进一下吗？

让我们从一个比列表更基本的东西开始，一个简单的数组。为了简单起见，让我们硬限制引擎中粒子的数量(稍后我们将纠正这一点)。

private const Int32 ParticleCount = 8000;
private readonly Particle[] particles = new Particle[ParticleCount];
private Int32 activeParticles = 0;

假设您有空间，则始终可以在固定时间内将一个粒子添加到数组的末尾：

particles[activeParticles++] = newParticleData;

但是移除一个粒子是O(n)，因为它之后的所有粒子都需要向下移动：

var indexOfRemovedParticle = 12;
particles.RemoveAt(indexOfRemovedParticle);
activeParticles--;

我们还能在恒定的时间里做些什么？我们可以在周围移动粒子：

particles[n] = particles[m];

我们能用这个来提高我们的表现吗？

是!将remove操作更改为move操作，O(n)就变成O(1)：

var indexOfRemovedParticle = 12;
var temp = particles[indexOfRemovedParticle];
particles[indexOfRemovedParticles] = particles[activeParticles - 1];
particles[activeParticles - 1] = temp;
activeParticles--;

我们划分我们的数组:开始时的所有粒子都是活动的，末端的所有粒子都是不活动的。所以要去除一个粒子，我们要做的就是用最后一个活性粒子交换它，然后减少活性粒子的数量。

(请注意，您需要删除粒子数组中的索引。如果您必须搜索这一点，则最终返回到O(n)时间；但是，由于粒子的通常工作流程是“循环遍历整个列表，更新每个粒子，如果是死的，则从列表中删除它”，因此通常会得到“免费”的死粒子索引。

现在，这都假设有固定数量的粒子，但是如果您需要更多的灵活性，您可以像List<T>类那样解决这个问题:当您没有空间时，只需分配一个更大的数组并将所有内容复制到其中。

这种数据结构提供了快速的插入和删除、快速的随机访问和良好的引用局部性。后者可以通过将您的Particle类变成一个结构来进一步改进，这样您的所有粒子数据都将连续地存储在内存中。