千万级图形的模糊化表示
经过前面的方法优化，我们已经可以一次性流畅显示十万个图形项，但这个数量级对于芯片设计来说可以说是杯水车薪，对于一个大型的设计，其中可显示的图形数目可以达到千万甚至上亿的级别，在这种情况下，想要实时绘制出图像是不现实的，而且将细节显示出来也没什么意义，所以退而求其次，只要能显示出大致的样式即可。
现在的需求是，在平面上包含着上千万个矩形，它们形制相似，排列得较为密集。在一次性显示整个图像时，用户显然看不出每个矩形是什么形状，也无法对这些矩形单独进行操作（但是，仍然应该让用户感知这片区域有很多图形）。基于此，我设计了一种模糊化显示的策略，通过一些方法减少查找和绘制的图形数量，在保证最终图像大致正确的同时大幅降低绘制的开销。
四叉树的功能拓展
之前，我提到了使用四叉树作为平面内图形的索引，为了实现模糊显示的功能，我们可以对四叉树的功能进行一些拓展：
一定区域内元素数量的估算
在需要绘制的图形较少时，仍旧按照原本的方法绘制，当需要绘制的图形较多时，则改变绘制的策略。因此，首先需要一个方法来快速估计需要绘制的元素数目
-
在每个节点中，添加一个属性，用于记录本节点及其子节点所包含的元素总数，在添加与删除元素时，相应的自增或自减这个变量
通过该项记录，我们无需计算就可直接获取每个节点（包含其子节点）中的元素数量
-
添加一个方法，用于估算一定区域内的元素数量
- 如果给定区域完全包含节点区域，则直接加上节点中所有元素的总数
- 如果给定区域部分包含节点区域，则按造包含面积的比例计算出一个数，视为在该区域的元素数量
template<typename T> class Box { public: T left; T top; T width; // Must be positive T height; // Must be positive ... } template<typename T, typename GetBox, typename Equal = std::equal_to<T>, typename Float = float> class Quadtree { ... struct Node { std::array<std::unique_ptr<Node>, 4> children; std::vector<T> values; uint64_t elementNum = 0; // sum of element num, include this node and its child nodes }; ... uint64_t elementNumEstimate(Node* node, const Box<Float>& box, const Box<Float>& estimateBox) const { if(!estimateBox.intersects(box) || node->elementNum == 0) return 0; if(estimateBox.contains(box)) return node->elementNum; uint64_t cnt = 0; Box<Float> intersectBox = box.intersected(estimateBox); float intersectRatio = (float)(intersectBox.width * intersectBox.height) / (float)(box.width * box.height); cnt += (uint64_t)(intersectRatio * node->values.size()); // 如果想要更精确的结果，可以对每个元素单独判断（那大概就不能叫估算了 // for(const auto& value : node->values) { // cnt += estimateBox.intersects(mGetBox(value)); // } if(!isLeaf(node)) { return elementNumEstimate(node->children[0].get(), computeBox(box, 0), estimateBox) + elementNumEstimate(node->children[1].get(), computeBox(box, 1), estimateBox) + elementNumEstimate(node->children[2].get(), computeBox(box, 2), estimateBox) + elementNumEstimate(node->children[3].get(), computeBox(box, 3), estimateBox) + cnt; } else { return cnt; } } }这个函数返回的是一个大概值，而且在显示元素较多时，估计的结果更加准确，大多数情况下，它与真实值的差距小于20%。
更快的查找方式
在每次绘制时，会对四叉树进行一次范围查询，对于查询到的结果，我并不会全部绘制，而是预先设置一个优先级，只绘制出优先级最高的数万个元素，在图像缩放比例较小时，我会至少将其长宽画成2个像素大小，这样，即使只显示了部分内容，也可以得到还不错的视觉效果。但是，当四叉树中的元素非常多时，仅仅将所有元素写入一个数组就要花费大量的时间，根据测试，取出一个包含2000万元素的四叉树中的所有元素，需要花费近1秒的时间，这个速度基本上跟实时绘制不沾边了。
怎么解决这个问题？瓶颈出现在四叉树的查询上，而对于一般的查询，我已经做了足够的优化，不仅使用原生的数组来替代std::vector以减少可能的重新分配内存的开销，并且当四叉树节点完全被查询区域包含时，无需判断就直接将该节点及其子节点的所有元素写入数组。看起来，除了必要的相交判断外，主要的开销就在内存的写入上了，在保证返回结果正确的前提下，优化已经无从谈起。
好消息是，在这种场景中还是有空子可钻的，在进行大场景的绘制时，我们并不需要完全正确的结果，只需要看起来像那么回事儿就行了，于是我们可以少写入点结果——采取的措施则是，在查询到每一个节点时，只将其中保存的第一个元素写入返回的数组（并且不判断它是否于查询区域相交），这样，可以减少大约85%-90%的查找结果。这样的查找结果具有较好的空间局部性，如果一块区域内具有数十个元素，那么查询时至少会返回其中的几个元素。
具体能减少多少查找结果与四叉树的分裂阈值相关，在我创建的四叉树索引中，分裂阈值被设置为16。并且在元素极多的情况下，四叉树可能已经达到最大深度，此时返回的元素数量还会受到四叉树节点数量的限制。
// 示例代码
// maxSize没用上，为了减少查找时的判断，我在预先分配数组时已经保证数组足够大
void effectiveBlurQuery(Node* node, const Box<Float>& box, const Box<Float>& queryBox, T* valuesArr, int& arrSize, int& maxSize)
{
if(!node->values.empty()) {
valuesArr[arrSize++] = node->values[0];
}
if (!isLeaf(node))
{
for (auto i = std::size_t(0); i < node->children.size(); ++i)
{
auto childBox = computeBox(box, static_cast<int>(i));
if (queryBox.intersects(childBox)) {
effectiveBlurQuery(node->children[i].get(), childBox, queryBox, valuesArr, arrSize, maxSize);
}
}
}
}
模糊化绘制
有了前面描述的四叉树索引的拓展功能，我们可以很容易的设计出一种新的绘制策略：
- 首先对需要绘制的区域中包含的元素数量进行一次估计
- 如果估算数量小于设定的值a，则进行精确查询
- 如果估算数量大于设定的值a，则使用前面所述的，只返回部分结果的查询方式
- 一次绘制的元素数量有上限，如果超出了这个上限，则按照绘制优先级p的大小，只绘制p大于某个值的元素
- 在绘制时，为了保证视觉效果，如果元素在屏幕上显示得过小，则直接使用一个长宽等于2个像素的矩形代替它
采用了这样的绘制策略后，对于巨大场景的区域查询，可以节省近90%的时间，由于查询结果在空间上分布得较为均匀，再加上我们对每个元素的绘制大小的最小限制，这些元素通常可以按分布密度铺满当前展示的二维区域，用户体验无疑是比较好的。
效果展示
下面是对包含100多万个矩形元素的样例的绘制效果：
真实情况（约400ms）
限制元素绘制数量（绘制的元素约为5万个，约80ms）
限制矩形绘制数量，并且增大矩形的显示大小（约80ms）
在前面的基础上，使用快速查找（约50ms，查询时间由30ms降低至4ms）
更新
后来，我发现这种查询方式对于图形数量巨大的场景还是太勉强了，简单的做一个估算： 当四叉树深度达到10时，最坏情况下的节点数量大约为100万个（4^10），但糟糕的是，以16个元素作为树节点分裂阈值时，包含2000万个元素的四叉树的最大深度可以达到13或者14（仅限我测试的例子），这样最终写入的数据量可以达到数百万，这其实也是不太能接受的。
如果想让最终写入数组的元素数量始终保持在10万个左右，我们可以尝试另一种同样简单粗暴的方法：
- 首先，同样需要对绘制区域中的元素数量进行一次估计
- 设置一个选取元素的间隔p，对于每个遍历到的子节点，不对每个元素是否位于绘制区域内进行判断，而是直接每隔p个元素取一个值，当然，这个计数是跨节点的。至于这个p取多少，则由之前估计的元素数量来决定，估计的元素数量越多，则p的取值越大
通过这样的方式，能够控制最终获取的元素总数在一定范围内浮动。