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

Question

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

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

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

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

这里展示我想达到什么图：

这是如何在最流行可用音频编辑作品的显示。用户可能会期待这种行为。我使用Audacity进行了测试，并且以这种方式工作（尽管它也显示了颜色较浅的样本的平均值）。它可以处理任意插入大声音，看似瞬间。我不打算阅读75兆字节的源代码来了解它是如何实现的。

编辑：

各种人提议表示缩小视图时涉及只考虑样本的一个子集方案。我得出的结论是，我不想这样做，因为它失去了太多有用的信息。例如，如果您正在寻找声音中的故障（如乙烯基转换中的单击），则包括所有样本都很重要。在最坏的情况下，如果毛刺只有一个样本长度，我仍然希望保证它在完全缩小视图中显示。

Answer 1

在阅读Peter Stock的回答后，我提出了以下计划。我认为将允许显示计算速度比原始方案快大约500倍，并且不应该增加任何显着的成本来插入或删除。内存开销小于1％。

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

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

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

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

Answer 2

当变焦在其中有多个样品每像素这是不值得准确计算每个像素的平均样本值的点。用户无法在缩放级别准确对齐GUI工具，因此没有任何好处。用户只需要一个定性的观点。

我只选择每屏的像素一个样本的窗口区域，跳过不必要的样品。

像这样的事情完全未经测试代码：

std::vector<double> samples(1024*1024); // [-1.0 < s < 1.0] 

int window_x = 1024; // window size in pixels 
int window_y = 768; // window size in pixels 

// visit every window pixel 
for(int x = 0; x < window_x; ++x) 
{ 
    // select relevant sample for the current screen pixel x 
    double s = samples[(x * samples.size())/window_x]; 

    int y = (window_y/2) * s; // get y size for sample value 

    // draw sample point/line at coordinate (x, f(y)) 
    gd.draw_line(x, (window_y/2) - y, x, (window_y/2) + y); 
} 

很明显，你还需要考虑窗口滚动等...

Answer 3

也许你可以使用从图形MIP映射技术，贸易使用更多的内存更快的速度？

如果您有32个样本，请保留一个缩小的缓存x2，x4，x8，...存储此数据将再次使用与原始数据相同的空间（16 + 8 + 4 + 2 + 1个样本） 。

的可视指导，用.表示存储的数据点（最小/最大采样值）和_由先前.覆盖的样品：

1st level: ................ 
2nd level: ._._._._._._._._ 
3rd level: .___.___.___.___ 
4th level: ._______._______ 
5th level: ._______________ 

然后，只需查询适当的电平的mip-map为缩放级别。

是的，当您插入/删除样本时，您将不得不重新创建mip-map缓存（或​​其一部分）。

但也许内存使用情况使这不适合你？

---

编辑

如果添加和删除是频繁操作，使高速缓存不可取的重新计算（和你想对间隔精确的采样，而不是仅仅在单个点），那么你可以更改mip映射方法以存储与本地最小/最大采样点对齐的数据，而不是基于时间的网格。

使用--------|--------表示在时间间隔的局部最大/最小值，这里有一个图形表示：

       --------|-------- 
    --------|-------- 
        --------|-------- 
            --------|-- 
------|-------- 
            . 
      .      . . 
.  . . . .   .  . .  . 
. ... . . . . . . .. . .  .  . . . 
    .  .  . . . . . . .  . . . 
        .   . .   . 
           . 
--------|-------- 
      --------|-------- 
            --------|----- 
         --------|-------- 

然后添加和只去除需要立即局部区域的开始和结束的重新计算添加/删除部分。

您可能想要索引本地最小/最大值，因此您不需要进行大量搜索。一个更复杂的实施方案 - 可能不值得你呢？