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

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

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

三次方程的根、線的數量和交點之間的關系如表1所示。

表1：三次方程的根、退化圓錐曲線的直線數和兩個圓錐曲線交點之間的關系。1D、1T和1Q分別表示一個二重交點、一個三重交點和一個四重交點

假設三次方程（11）可以寫成

進行變量替換可得關于的沮喪三次方程(沒有二次項)

其中

(30)的判別式為：

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

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