c++ - 在 C/C++ 中快速显示波形

Question

我有兴趣在 Windows 和 Linux 上用 C 或 C++ 实现音频编辑器。我不知道如何在完全缩小的 View 中足够快地显示波形。我不是在寻找有关快速帧缓冲技术的信息。这是一个关于算法和数据结构的问题，可以有效地确定要显示的内容。

假设我希望能够编辑 2 小时长的 5 声道、48 KHz、24 位声音。这是 5 GB 的示例数据。我希望能够从每个样本一个像素一直缩小，直到所有样本数据一次可见。我希望应用程序感觉响应迅速，即使是在速度较慢的机器上，例如 1 GHz Atom。当我说响应时，我希望 GUI 更新通常在用户输入的 1/30 秒内发生。

在决定为完全缩小的 View 渲染什么时，天真的实现会扫描整个波形中的每个样本 - 它需要找到显示器的每个像素宽度“覆盖”的所有样本的最大和最小样本值.我写了一个简单的应用程序来测试这种方法的速度。我在我的 2015 3.5 GHz Xeon 上测试了一个 1 小时长的单声道 16 位 44.1 KHz 样本。耗时 0.12 秒。这太慢了数百倍。

您可以想象维护缩小数据的缓存，但我看不出如何避免在大多数插入或删除操作后必须重新计算整个缓存。感觉一定有更好的办法。

这是显示我想要实现的目标的图表:

这是大多数当前可用的音频编辑器中的显示方式。用户可能会预料到这种行为。我使用 Audacity 进行了测试，它以这种方式工作(尽管它也以较浅的颜色显示了类似于样本平均值的内容)。它可以处理任意插入到大声音中，看似瞬间。我不会阅读 75 MB 的源代码来了解它是如何做到的。

编辑:

许多人提出了在显示缩小 View 时仅考虑样本子集的方案。我得出的结论是我不想这样做，因为它会丢失太多有用的信息。例如，如果您正在寻找声音中的故障(例如黑胶唱片转换中的咔嗒声)，那么包括所有样本非常重要。在最坏的情况下，如果毛刺只有一个样本长，我仍然希望保证它显示在完全缩小的 View 中。

Answer 1

阅读 Peter Stock 的回答后，我想出了以下方案。我认为它将允许显示计算比原始方案快 500 倍，并且不应该为插入或删除增加任何明显的成本。内存开销小于1%。

声音数据将分配到 131072 个样本 block 中，因此插入和删除不需要重新分配和复制整个声音。首次加载声音时，每个 block 都将被完全填充(可能最后一个除外)。插入和删除会导致一种碎片化。为简单起见，我将安排每个 block 的开头始终包含有效样本数据，任何间隙都将在 block 的末尾。

每个 block 都有两个与之关联的查找表，一个用于最大值，一个用于最小值。查找表中的每一项对应1024个样本。

下图显示了如何计算显示器一个像素宽度的最大值。它显示了一些与计算相关的 block 。它假设没有“碎片化”。

插入后，情况稍微复杂一些。两个 block 现在在它们的末端有无效区域。最大查找表中的条目现在对应于样本的部分空区域。这些条目的值是通过取存在的样本的最大值来找到的。