2

我需要帮助来有效地绘制/剔除一系列不透明的矩形，换句话说，这是桌子上的一堆索引卡。具体如下：

  • 没有旋转，所以一切都是简单的整数坐标，轴对齐
  • 卡片完全不透明
  • 卡片可以有任何整数 X,Y 位置
  • 所有卡片尺寸相同
  • 我有一张按 z 顺序排列的卡片列表

我想我（基本上）有两个选择：

1) 蛮力画家的方法，其中桌面视口内的所有卡片都以反向 z 顺序完全绘制。优点：简单。缺点：a) 需要一个屏幕外缓冲区以避免闪烁，b) 可能会浪费大量时间来绘制每张卡片的昂贵区域，而该区域最终可能会被遮挡，最坏的情况是整张卡片都被覆盖。

2) 一种算法，它为每张卡片生成可见（或模糊）矩形列表，以便只绘制可见部分。

选择 2 是我需要建议的地方，尤其是在算法方面，以及“更智能”抽牌周期的优缺点。

感谢任何语言/平台无关的建议。如果重要，这将在 MS Windows 上实现。

我愿意接受任何建议，包括混合方法。我意识到一个精确的答案可能非常依赖于代码的细节，但即使在这一点上，我也会很高兴有概括的概念！

附加说明：有可能将数千张卡片堆叠在一起，所以我非常积极地避免使用纯粹的蛮力画家的方法 - 至少没有某种预处理来剔除完全模糊的卡片。对于许多紧密平铺的卡片也是如此，更糟糕的情况是它们的边框显示 - 如果可能的话，我想在这些情况下跳过绘制复杂的内脏。

4

2 回答 2

0

如果只画每张卡片从最底部到最顶部的轮廓线呢？然后你可以做一个洪水填充来绘制轮廓内部。这样，您将只重新绘制与有交叉点的边界相对应的几个像素。

编辑：上传图片来帮助我解释这个想法。

方法的第 1 部分 第2部分

第一步是标记分配其 Z 顺序的卡片的边界（左上图）。这样，有覆盖，但只在少量像素的边界上。

之后，您可以按照以下两条规则绘制卡片的纹理（首先是最低 Z 顺序）：

  • 您从边界开始绘制空白直到到达边界；
  • 如果边框的 Z 顺序是当前的，则绘制它；
  • 如果找到的边框 Z 顺序小于当前 Z 顺序，则继续绘制，因为它是空白的；
  • 否则，您会找到具有更大 Z 顺序的边框，因此您跳过该块；
  • 下一张牌。

希望能帮助到你 ：）

于 2012-10-24T20:58:19.790 回答
0

好的，这里有一些松散的伪代码，我认为可以解决这个问题。

从卡片的 z 顺序排序列表开始。每张卡片都有一个可见矩形列表（稍后解释），需要从一个矩形开始，设置为卡片的完整边界框。循环首先从最低 z 顺序卡开始。

Cards.SortZOrder();
foreach Card in Cards do
  Card.ResetVisibleRects; // VisibleRects.DeleteAll; VisibleRects.Add(BoundingBox);

CurrentCard = Cards.Last;
TestCard = CurrentCard;

这里的想法是，我们将从我们的“当前”卡向上工作，看看每张更高的卡对它有什么影响。当我们测试每张更高的卡片时，有 3 种可能性。它要么完全错过，要么完全模糊，要么部分模糊。对于完全错过，我们忽略测试卡，因为它不会影响我们当前的卡。为了完全模糊，我们当前的卡被剔除。部分重叠是可见矩形列表的来源，因为部分重叠可以（可能）将下部矩形分成两部分。（如果您只抓两张扑克牌或索引卡，很容易看出这是如何发挥作用的。顶部的一张会导致底部的一张调整它的一侧，如果它们共享任何边缘，或者它会导致底部的一张分裂如果它们不共享边，则分成两个矩形。）

警告：这是非常未优化的展开代码......只是为了谈论原则。是的，我即将使用“goto”......如果你必须嘲笑我。

[GetNextCard]
TestCard = Cards.NextHighest(TestCard);

[OverlapTest]
// Test the overlap of TestCard against all our VisibleRects.
// The first time through this test, CurrentCard will have only one
// rect in the VisibleRect list, but that rect may get split up later.
// OverlapTests() checks each rect in the VisibleRects list, and
// creates an Overlap record for any of the rects that do overlap,
// like: Overlap.RectIndex, Overlap.Type. It also summarizes the
// results into the .Summary field. 

Result = CurrentCard.OverlapTests(TestCard);

case Result.Summary
  none: 
    goto [GetNextCard];

  complete:
    CurrentCard.Culled = true;

    // we're now done with this CurrentCard, so we move upwards
    CurrentCard = TestCard;
    goto [GetNextCard]

  partial:
    // since there was some overlap, we need to adjust,
    // split, or delete some or all of our visible rectangles.
    // (we won't delete them all, that would have been caught above)

    foreach Overlap in Result.Overlaps
      R = CurrentCard.VisibleRects[Overlap.RectIndex];
      case Overlap.Type
        partial: CurrentCard.SplitOrAdjust(R, TestCard);
        complete: CurrentCard.Delete(R);
      end case

    // so we've either added new rects, or deleted some, but either 
    // way, we're done with this test card. We leave CurrentCard
    // where it is and loop to look at the next higher card.
    goto [GetNextCard]

CurrentCard = Cards.First由于最上面的卡片始终完全可见，因此测试完成。

这里还有一些想法......

我认为这在实际代码中会相当简单。关于它的最复杂的事情是将一个矩形分成两部分，并且考虑到这都是整数数学，即使那是微不足道的。

此外，不必在每个绘制周期都执行此操作。仅当内容、位置或 z 顺序发生任何变化时才需要执行此操作。

在通过列表之后，您会得到一个可绘制的卡片列表，每张未剔除的卡片至少有一个矩形，可能会落在显示器的剪切/脏区域内。当你绘制一张卡片时，你可以检查它的可见矩形列表，并且可能会跳过卡片的绘制部分，这些部分可能渲染起来很昂贵。

于 2012-11-03T05:30:12.217 回答