二维重叠矩形遮挡
2D overlapping rectangles occlusion
我正在寻找一种可以找到相互重叠的相交矩形的算法。
要注意的是，我的数据结构类似于四叉树，带有边界框而不是点。
我正在做一个基本的矩形相交检查，但问题是当我放大树时，检测到子节点和父节点，如果它被给定相机矩形的子节点完全遮挡，我想排除父节点。
zoom animation
正如您从上图中看到的那样，相机矩形（黑框）位于绿色节点内，紫色节点仍然突出显示（填充），因此随着我越来越大地缩放，父节点总是突出显示，甚至虽然相机矩形只能完全填充子节点。
这是有道理的，因为相机矩形仍在父级内部，但我已经搜索并思考了一段时间的问题，但似乎无法找到一个优雅的解决方案。对于 3D 空间似乎有几种方法可以做到这一点，但对于 2D AABB 矩形我找不到任何简单的方法。
我想到的几个解决方案：
- 从父节点中减去子节点得到凹多边形，然后进行多边形交集。
- 使用填充颜色检查哪些矩形可见，从而遮挡后面的矩形。
- 执行光线投射或细分并检查哪个是给定部分的最小节点。
有更好的方法吗？
谢谢
更新 1
我已经通过将相机细分为更小的部分并为每个部分找到最小的相交节点解决了这个问题。这 works 但必须有一种更有效、更清洁的方法来做到这一点。
更新 2
谢谢 Trentium 的回答。我可以清楚地看到这样的算法会比我目前正在做的算法更高效。
最终我会将其实现为将矩形拆分为更小的矩形而不是多边形，这听起来像是一个有趣的挑战。
此外，我对当前方法做了一些非常不科学的基准测试，过滤和绘制所有内容都需要 0.5ms-1ms，所以目前性能仍然不是问题。
建议考虑您提出的第一个解决方案的变体“从 parent 中减去 child 节点得到凹多边形，然后执行多边形相交。”
具体来说，如果直接 children 完全包含在 parent 中，则建议对于每个矩形，还应维护一个关联的可见剩余矩形数组。然后使用这个剩余矩形数组作为确定相机/视口矩形是否包含 parent 的手段。
例如，假设 parent 矩形是 (0,0) - (100,100)，并且在 (75,75)-(100,100) 处添加了一个初始 child 矩形。数据结构将显示为...
- parent.rectangle = {0,0,100,100}
- parent.visible = [ {0,0,100,75}, {0,75,75,100} ]
- child1.rectangle = {75,75,100,100}
- child1.visible = [ {75,75,100,100} ]
parent.visible 数组中的每个剩余矩形进行检查, 根据需要进一步细分 parent 可见矩形...
- parent.rectangle = {0,0,100,100}
- parent.visible = [ {0,0,100,50}, {0,50,50,75}, {75,50,100,75}, {0,75,50,100}, {50,90 ,75,100} ]
- child1.rectangle = {75,75,100,100}
- child1.visible = [ {75,75,100,100} ]
- child2.rectangle = {50,50,75,90}
- child2.visible = [ {50,50,75,90} ]
随着 children 的添加，此方法会预先调整直接 parent 的可见矩形，但应该会大大减少矩形相交测试相对于当前算法涉及相机/视口的细分。另外，这个提议的算法只使用 rectangle-to-rectangle 相交测试（在将 child 添加到 parent 时，以及在测试相机/视口相交时！）而不是建议的 rectangle-to-polygon 测试...
我正在寻找一种可以找到相互重叠的相交矩形的算法。
要注意的是，我的数据结构类似于四叉树，带有边界框而不是点。 我正在做一个基本的矩形相交检查，但问题是当我放大树时，检测到子节点和父节点，如果它被给定相机矩形的子节点完全遮挡，我想排除父节点。
zoom animation
正如您从上图中看到的那样，相机矩形（黑框）位于绿色节点内，紫色节点仍然突出显示（填充），因此随着我越来越大地缩放，父节点总是突出显示，甚至虽然相机矩形只能完全填充子节点。
这是有道理的，因为相机矩形仍在父级内部，但我已经搜索并思考了一段时间的问题，但似乎无法找到一个优雅的解决方案。对于 3D 空间似乎有几种方法可以做到这一点，但对于 2D AABB 矩形我找不到任何简单的方法。
我想到的几个解决方案：
- 从父节点中减去子节点得到凹多边形，然后进行多边形交集。
- 使用填充颜色检查哪些矩形可见，从而遮挡后面的矩形。
- 执行光线投射或细分并检查哪个是给定部分的最小节点。
有更好的方法吗？ 谢谢
更新 1
我已经通过将相机细分为更小的部分并为每个部分找到最小的相交节点解决了这个问题。这 works 但必须有一种更有效、更清洁的方法来做到这一点。
更新 2
谢谢 Trentium 的回答。我可以清楚地看到这样的算法会比我目前正在做的算法更高效。
最终我会将其实现为将矩形拆分为更小的矩形而不是多边形，这听起来像是一个有趣的挑战。
此外，我对当前方法做了一些非常不科学的基准测试，过滤和绘制所有内容都需要 0.5ms-1ms，所以目前性能仍然不是问题。
建议考虑您提出的第一个解决方案的变体“从 parent 中减去 child 节点得到凹多边形，然后执行多边形相交。”
具体来说，如果直接 children 完全包含在 parent 中，则建议对于每个矩形，还应维护一个关联的可见剩余矩形数组。然后使用这个剩余矩形数组作为确定相机/视口矩形是否包含 parent 的手段。
例如，假设 parent 矩形是 (0,0) - (100,100)，并且在 (75,75)-(100,100) 处添加了一个初始 child 矩形。数据结构将显示为...
- parent.rectangle = {0,0,100,100}
- parent.visible = [ {0,0,100,75}, {0,75,75,100} ]
- child1.rectangle = {75,75,100,100}
- child1.visible = [ {75,75,100,100} ]
parent.visible 数组中的每个剩余矩形进行检查, 根据需要进一步细分 parent 可见矩形...
- parent.rectangle = {0,0,100,100}
- parent.visible = [ {0,0,100,50}, {0,50,50,75}, {75,50,100,75}, {0,75,50,100}, {50,90 ,75,100} ]
- child1.rectangle = {75,75,100,100}
- child1.visible = [ {75,75,100,100} ]
- child2.rectangle = {50,50,75,90}
- child2.visible = [ {50,50,75,90} ]
随着 children 的添加，此方法会预先调整直接 parent 的可见矩形，但应该会大大减少矩形相交测试相对于当前算法涉及相机/视口的细分。另外，这个提议的算法只使用 rectangle-to-rectangle 相交测试（在将 child 添加到 parent 时，以及在测试相机/视口相交时！）而不是建议的 rectangle-to-polygon 测试...