CVPR2023 | 如何設計一個(gè)更快更魯棒的P3P求解器？（2）

（11）中三次方程的通解可能有四種情況： 三個(gè)實(shí)根，一個(gè)實(shí)根和兩個(gè)復根，一個(gè)實(shí)根和一個(gè)重根、一個(gè)實(shí)三重根。 這四種可能性對應于直線(xiàn)和交點(diǎn)的不同情況。在本文的例子中，第一個(gè)圓錐曲線(xiàn)（4）是不定的，第二個(gè)圓錐曲線(xiàn)（5）是雙曲線(xiàn)（b>0）。不失一般性，假設第一個(gè)是橢圓，并在圖3中展示兩個(gè)圓錐曲線(xiàn)的可能相對位置。 簡(jiǎn)要起見(jiàn)，以圖3b作為示例。兩個(gè)圓錐曲線(xiàn)有四個(gè)實(shí)交點(diǎn)，特征三次方程有三個(gè)實(shí)根，每個(gè)實(shí)根對應于一對實(shí)直線(xiàn)。每對實(shí)直線(xiàn)在四個(gè)實(shí)交點(diǎn)處與兩個(gè)圓錐曲線(xiàn)中的任何一個(gè)相交（圖3b）。在其他情況下也存在類(lèi)似的情況。

圖3：雙曲線(xiàn)和橢圓相對位置的八種可能情況的圖解。具有不同顏色的一對線(xiàn)對應于不同的三次根。(a)-(c): 兩個(gè)圓錐曲線(xiàn)分別具有零、四和兩個(gè)實(shí)交點(diǎn)的一般情況。(d)-(f): 兩個(gè)圓錐曲線(xiàn)相切的臨界情況，分別有一個(gè)二重交點(diǎn)、兩個(gè)二重交點(diǎn)、一個(gè)二重交點(diǎn)和兩個(gè)交點(diǎn)。(g)-(h): 兩個(gè)圓錐曲線(xiàn)彼此密切（兩個(gè)圓錐在切點(diǎn)具有相同的曲率），分別有一個(gè)三重交點(diǎn)和一個(gè)四重交點(diǎn)

三次方程的根、線(xiàn)的數量和交點(diǎn)之間的關(guān)系如表1所示。

表1：三次方程的根、退化圓錐曲線(xiàn)的直線(xiàn)數和兩個(gè)圓錐曲線(xiàn)交點(diǎn)之間的關(guān)系。1D、1T和1Q分別表示一個(gè)二重交點(diǎn)、一個(gè)三重交點(diǎn)和一個(gè)四重交點(diǎn)

假設三次方程（11）可以寫(xiě)成

進(jìn)行變量替換可得關(guān)于的沮喪三次方程(沒(méi)有二次項)

其中

(30)的判別式為：

• 若,（30）有三個(gè)不同的實(shí)根，其對應于情況（a）和（b）。對于情況（a），由于所有的實(shí)根都不對應于任何實(shí)交點(diǎn)，我們可以選擇三個(gè)根中的任何一個(gè)。使用三角解找到根,該根可以對應于一對實(shí)線(xiàn)，也可以不對應于實(shí)線(xiàn)。如果選擇的實(shí)根給出一對實(shí)線(xiàn)，可以在驗證第一條直線(xiàn)沒(méi)有實(shí)交點(diǎn)后跳過(guò)第二條直線(xiàn)。對于情況（b），三個(gè)根中的任何一個(gè)都將產(chǎn)生一對實(shí)線(xiàn)和四個(gè)實(shí)交點(diǎn)。
• 若,（30）具有一個(gè)實(shí)根和兩個(gè)共軛復根，這對應于情況（c）。使用Cardano公式可以找到實(shí)根，并且可以得到一對實(shí)直線(xiàn)。如果其中第一條直線(xiàn)與圓錐曲線(xiàn)有實(shí)交點(diǎn)，則可以跳過(guò)第二條直線(xiàn)。否則，如果第一條直線(xiàn)沒(méi)有實(shí)交點(diǎn)，就需要檢查第二條直線(xiàn)。
• 若且,則（30）有一個(gè)單實(shí)根和一個(gè)重實(shí)根，這對應于情況（d）、（e）和（f）。對于情況（d），可以看到重實(shí)根在虛直線(xiàn)中產(chǎn)生。因此，對于這種情況，可以使用單實(shí)數根。
• 若且，則。在這種情況下，方程（30）有三重根γ，這對應于情況（g）和（h）。三次方的實(shí)根給出了一對實(shí)線(xiàn)，并且可以很容易地找到實(shí)交點(diǎn)。

基于以上分析和表1，可以注意到，可以使用任何一對實(shí)線(xiàn)來(lái)恢復實(shí)交點(diǎn)，并且除了情況（d）之外，三次方程的任何實(shí)根都對應于一對實(shí)直線(xiàn)。只需要在且時(shí)避免使用重實(shí)根。 另一方面，如果，則這對直線(xiàn)和圓錐曲線(xiàn)之間一定有雙重交點(diǎn)。為了避免重復的解，需要檢查直線(xiàn)和圓錐曲線(xiàn)之間的交點(diǎn)。整個(gè)過(guò)程如算法1所示。