在GJK中实现支持功能

有没有办法预处理凸多边形的点，以便“最远点给定方向”查询有效？这是GJK算法中的一个重要步骤。微不足道的解决方案是，每次扫描多边形的点寻找最远的点。在GJK中实现支持功能

2013-11-01 saadtaame

当然，有（例如通过预先计算每个点到每个其他点的距离表），但这是计算时间和内存需求之间的一个重要折衷 - 如果您只有几点，这可能是值得的，但所需的O（N^2）内存可能会很快失去控制。 – twalberg

谢谢，如何使用表格找出指向某个方向的最远点？ – saadtaame

机会是，除非你在某种规则的网格上，否则在特定方向上不会有任何点。您可能需要检查特定方向上的点数+/-某个阈值。但是，在预先计算距离的同时，您可以轻松地预先计算每对点之间的方向矢量... – twalberg

http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf表示在实践中，您可以在重复调用中快速获得最远的顶点，方法是跟踪上一个答案，并通过从一个顶点移动到相邻顶点来找出接近的顶点来计算出下一个答案。它还提供了一个指针，指向由摩根考夫曼于2005年出版的Ericson的书籍“实时碰撞检测”（http://www.cosy.sbg.ac.at/~held/teaching/bakk_seminar/se_arbeiten_07-08/KollisionserkennungGJK.pdf）

2013-11-01 19:08:27 mcdowella

回答