我目前正在使用3DIrrlicht Engine
实现QuickHull
算法。用户将能够通过按键逐步完成算法,逐步完成每个单独的步骤。
我想独立于主渲染循环来执行此操作,以免在等待用户输入时使整个模拟停止;用户应该能够平移相机并查看发生了什么。
我目前有一个QuickHull
包含所有点和线段的容器类以及算法的方法。如何让此方法按需暂停并等待用户输入,而不会停止渲染循环或在渲染循环继续进行时意外中断递归?
我目前正在使用3DIrrlicht Engine
实现QuickHull
算法。用户将能够通过按键逐步完成算法,逐步完成每个单独的步骤。
我想独立于主渲染循环来执行此操作,以免在等待用户输入时使整个模拟停止;用户应该能够平移相机并查看发生了什么。
我目前有一个QuickHull
包含所有点和线段的容器类以及算法的方法。如何让此方法按需暂停并等待用户输入,而不会停止渲染循环或在渲染循环继续进行时意外中断递归?
以下不是记忆方面的最佳解决方案,但可以工作:
当用户运行 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。