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

Question

我对在Windows和Linux上用C或C ++实现音频编辑器感兴趣。我无法弄清楚如何在完全缩小的视图中足够快地显示波形。我不是在寻找有关快速帧缓冲技术的信息。这是关于有效确定显示内容的算法和数据结构的问题。

假设我希望能够编辑2小时长的5通道，48 KHz，24位声音。这是5 GB的样本数据。我希望能够一直缩小到每个样本一个像素，直到一次可以看到所有样本数据。我希望应用程序即使在速度较慢的计算机上也能感觉到响应，例如，出于论证的原因，它是1 GHz Atom。当我说“响应”时，我希望GUI更新通常在用户输入的1/30秒之内进行。

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

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

这是显示我想要实现的图：

这就是大多数当前可用的音频编辑器中的显示方式。用户可能会期望这种行为。我使用Audacity进行了测试，并且它以这种方式工作（尽管它也以较浅的颜色显示了样本均值）。它可以立即处理大型声音中的任意插入内容。我不会阅读75 MB的源代码来了解它是如何做到的。

编辑：

各种各样的人提出了一些方案，这些方案在显示缩小视图时只考虑样本的子集。我得出的结论是，我不想这样做，因为它会丢失太多有用的信息。例如，如果您要寻找声音中的毛刺（例如单击黑胶转换中的声音），则包括所有样本非常重要。在最坏的情况下，如果毛刺只有一个样本长，我仍然希望保证它可以在完全缩小的视图中显示。

Answer 1

阅读 Peter Stock 的回答后，我提出了以下方案。我认为它的显示计算速度比简单方案快大约 500 倍，并且不会为插入或删除增加任何明显的成本。内存开销小于1%。

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

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

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

插入后，情况稍微复杂一些。现在，两个块的末端都有无效区域。最大查找表中的条目现在对应于样本的部分空区域。这些条目的值只需取现有样本的最大值即可找到。