1

我目前正在使用3DIrrlicht Engine实现QuickHull算法。用户将能够通过按键逐步完成算法，逐步完成每个单独的步骤。

我想独立于主渲染循环来执行此操作，以免在等待用户输入时使整个模拟停止；用户应该能够平移相机并查看发生了什么。

我目前有一个QuickHull包含所有点和线段的容器类以及算法的方法。如何让此方法按需暂停并等待用户输入，而不会停止渲染循环或在渲染循环继续进行时意外中断递归？

4

1 回答 1

1

以下不是记忆方面的最佳解决方案，但可以工作：

当用户运行 QuickHull 时，实际上是贯穿了整个解决方案。但是，请随时保存中间状态。在最坏的情况下，如果所有点都位于凸包（即凸多边形）上并在 O(n 2 ) 时间内运行，则 QHull 需要 O(n) 内存，因此如果要生成中间状态，则需要存储大小为 1、2、3、...、n 的向量来表示每个阶段的船体，这可能会导致 O(n 3 ) 的总额外内存。

当您逐渐生成船体时，为每次迭代创建一组新的点，这些点代表船体在那个时刻的样子。要表示生成的凸包，请随时为外壳上的每个点添加球体场景节点。

您可以使用该函数将球体添加到场景中，该irr::scene::ISceneManager::addSphereSceneNode(radius)函数返回一个IMeshSceneNode*您可以将其推入表示该状态下凸包的向量中。

要显示这些点之间的边缘，您需要在球体之间画线。因此，对于当前船体中的每个点，在它们之间画一条线（也是 last 和 first 之间的一条线）

draw3DLine您可以使用以下命令画一条线irr::video::IVideoDriver：

irr::video::SMaterial lineMaterial;
lineMaterial.Lighting = false;
lineMaterial.Thickness = 2.0f;
lineMaterial.FrontfaceCulling = false;
lineMaterial.BackfaceCulling = false;
lineMaterial.MaterialType = irr::video::EMT_SOLID;
_driver->setMaterial(lineMaterial);
_driver->setTransform(irr::video::ETS_WORLD,
                irr::core::IdentityMatrix);

//draw a line
irr::core::vector3df lineStart,lineEnd; //set these equal to 2 adjacent vertices on your hull
_driver->draw3DLine(lineStart,lineEnd,irr::video::SColor(0.0,0.0,0.0,205)); //blue line

最初，IMeshSceneNode*您添加到场景中的所有内容都应该是不可见的。void irr::scene::ISceneNode::setVisible(bool isVisible)创建矢量时，在矢量中的每个球体上使用该命令。

现在，在您运行 QHull 算法之后，您可以在状态向量中创建一个索引（其中每个状态代表一个时间步长的外壳，它本身就是一个向量）。

递增索引时，可以将当前状态（递增前）的所有球体设置为不可见，然后使下一状态的所有球体可见。

你的主渲染循环也应该调用一些函数来渲染当前 ConvexHull 状态的边缘。

这个模型的好处是用户现在可以向前和向后查看算法的进展情况。如果您只是继续前进，那么您可以将它们完全从场景中移除，而不是使代表船体的先前节点不可见。

同样使用这个模型，我们不需要尝试使用一些奇怪的线程模型在执行过程中暂停 QHull 算法，我们也不需要对算法本身进行大量修改，以便它可以暂停和恢复。您只需在每一帧渲染当前的 Hull 状态，允许您移动相机并随意查看它，然后只需使用您自己的EventReceiver类按下按钮即可更新 hull。

于 2013-10-18T15:46:06.593 回答