把相邻同类格子合并成矩形,可以用更少的区域描述同一张图。但合并时不能跨过空格,也不能因为形状接近就改变原始覆盖范围。
下面是一组独立的虚构游戏输入与逐步结果。先记录单位、编号和端点是否包含,再尝试自己推算,最后对照第一处差异。所有结论都以本例规则为前提;其他作品采用不同约定时,应按它自己的说明重新计算。
二值地图的一个表示需要绘制的格子。每行先找连续的一段段一格;只把相邻行中横向起止完全相同的段向下合并。矩形左上包含、右下排除;本规则保持覆盖,不承诺矩形数量全局最少。
八列六行,1为绘制格 [1, 1, 1, 1, 0, 0, 0, 0] [1, 1, 1, 1, 0, 0, 0, 0] [1, 1, 1, 1, 0, 0, 0, 0] [1, 1, 1, 1, 0, 0, 0, 0] [1, 1, 1, 1, 0, 0, 0, 0] [0, 0, 0, 0, 0, 1, 1, 0]
第0行[1, 1, 1, 1, 0, 0, 0, 0],横段[(0, 4)];本行结束的矩形[],仍可向下延续的矩形[[0, 0, 4, 1]]。
第1行[1, 1, 1, 1, 0, 0, 0, 0],横段[(0, 4)];本行结束的矩形[],仍可向下延续的矩形[[0, 0, 4, 2]]。
第2行[1, 1, 1, 1, 0, 0, 0, 0],横段[(0, 4)];本行结束的矩形[],仍可向下延续的矩形[[0, 0, 4, 3]]。
第3行[1, 1, 1, 1, 0, 0, 0, 0],横段[(0, 4)];本行结束的矩形[],仍可向下延续的矩形[[0, 0, 4, 4]]。
第4行[1, 1, 1, 1, 0, 0, 0, 0],横段[(0, 4)];本行结束的矩形[],仍可向下延续的矩形[[0, 0, 4, 5]]。
第5行[0, 0, 0, 0, 0, 1, 1, 0],横段[(5, 7)];本行结束的矩形[[0, 0, 4, 5]],仍可向下延续的矩形[[5, 5, 7, 6]]。
输出2个矩形[[0, 0, 4, 5], [5, 5, 7, 6]],总覆盖22格。
将输出矩形逐格展开,计数应与原图完全一致,每个一格恰覆盖一次、零格从不覆盖。还可对每一种横向段分别找连续出现的行区间,独立得到矩形。
本例只合并相同类型且没有额外属性的格子。不同纹理、透明顺序、光照或交互边界可能要求分开绘制。矩形变少也不自动保证实际帧率提高,渲染开销还受其他因素影响;这里首先验证几何等价。
测试时先保留输入和中间状态,再只改变一个条件。空状态、正好相等、重复出现和最后一步都值得单独检查。若最终结果不符,应从第一处偏差查起,而不是在末尾随意增加补偿让数字表面一致。