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

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

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

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

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

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

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

其中

(30)的判別式為：

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

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