# On the Effect of Control-Point Spacing on the Multisolution Phenomenon in the P3P Problem

Authors: M. Vynnycky; G. M. M. Reddy
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The perspective 3-point (P3P) problem, also known as pose estimation, has its origins in camera calibration and is of importance in many fields: for example, computer animation, automation, image analysis, and robotics. One possibility is to formulate it mathematically in terms of finding the solution to a quartic equation. However, there is yet no quantitative knowledge as to how control-point spacing affects the solution structure—in particular, the multisolution phenomenon. Here, we consider this problem through an algebraic analysis of the quartic’s coefficients and its discriminant and find that there are significant variations in the likelihood of two or four solutions, depending on how the spacing is chosen. The analysis indicates that although it is never possible to remove the occurrence of the four-solution case completely, it could be possible to choose spacings that would maximize the occurrence of two real solutions. Moreover, control-point spacing is found to impact significantly on the reality conditions for the solution of the quartic equation.


---

## Body

## 1. Introduction

The perspective 3-point (P3P) problem, also known as pose estimation, has its roots in camera calibration and is of importance in many fields: for example, computer animation, automation, image analysis, and robotics. It can be stated as follows: given the perspective projection of three points constituting the vertices of a known triangle in 3D space, it is possible to determine the position of each of the vertices. One way it can be formulated mathematically is in terms of finding the solution to a quartic equation. However, in general, the equation does not have a unique solution, and in some situations there are no solutions at all. A review of work on the problem up until 1994 is given by Haralick et al. [1]; by that stage, there were six different algorithms for the P3P problem, given by Grunert [2], Finsterwalder and Scheufele [3], Merritt [4], Smith [5], Fischler and Bolles [6], Linnainmaa et al. [7], and Grafarend et al. [8].Thus, an important area of research on the P3P problem is its multisolution phenomenon. Fischler and Bolles [6] showed that up to four solutions would be present for the problem of matching three model points to three image points, and they gave a procedure for identifying each of these solutions. A necessary condition for the existence of the solution was given for the first time by Yuan [9]. Wolfe et al. [10] gave a geometric explanation to this multisolution phenomenon in the image plane under the assumption of “canonical view”. Su et al. [11] applied the Wu-Ritt zero decomposition method to find the main solution branch and some nondegenerate branches for the P3P problem, although a complete decomposition was not given; in [12], the same authors used the Sturm sequence to give some conditions to determine the number of solutions. Yang [13] gave partial solution classifications of the P3P problem under some nondegenerate conditions. Gao et al. [14] have given a complete classification, although the procedure is lengthy, mainly as they try to solve two quadratic equations simultaneously, rather than the single quartic equation. Even more recent are the papers by Zhang and Hu [15–17], Hu et al. [18], and Rieck [19–22]; in particular, Rieck [20] focused on the multisolution phenomenon. An alternative approach is that of Vynnycky and Kanev [23], who analyzed in detail the behaviour of coefficients of the quartic polynomial derived by Linnainmaa et al. [7]; this enabled them to draw conclusions on the comparative likelihoods of obtaining different numbers of solutions, albeit only for the case of equidistant spacing between the vertices, constituting an isosceles triangle. Moreover, it should be noted that there exist other ways to formulate the problem: for example, Finsterwalder and Scheufele [3] formulate it in terms of finding a root of a cubic polynomial and the roots of two quadratic polynomials, rather than finding all the roots of a fourth-order polynomial.The purpose of this contribution is to extend the methodology of Vynnycky and Kanev [23] with a view to obtaining a better quantitative understanding of the multisolution phenomenon of the P3P problem; in contrast to other activities that seek to determine solutions to the problem numerically or to provide a geometrical interpretation of the problem [24], here we focus on analyzing the actual numbers of solutions that the problem has as a function of the properties of the known triangle in 3D space. Moreover, although such solutions can be computed numerically these days in microseconds, this ought not to preclude seeking a better analytical understanding of the underlying equations.Although lengthy, the analysis in [23] was only for one of the four different formulations that result in a quartic polynomial [2, 4, 6, 7]; moreover, it was mostly only for the case when the known triangle in 3D space was isosceles. It should be noted, however, that different algebraic manipulations of the equations lead to different quartic polynomials, and a preliminary issue concerns how this will affect the solution structure; although one might expect it to be invariant, we demonstrate that there exist situations where the structure is different. The analysis here will be based on the polynomial obtained by Grunert [2], although we will also obtain new insight on the formulation of Linnainmaa et al. [7]. Moreover, we will go as far as considering arbitrary triangles in 3D space, corresponding to nonequidistant vertices, to determine whether it would be possible to remove the four-solution case completely through a prudent choice of triangle; if so, and the answer at the outset is far from obvious, this could help to reduce the complexity of numerical algorithms that seek to solve the P3P problem in real-time applications.The layout of the paper is as follows. In Section2, the P3P problem is stated and the formulation due to Grunert [2] is presented. In Section 3, some preliminary analysis is presented regarding the properties of the polynomial, while Section 4 considers in detail the solutions for the case of equidistant control points. The main results, for nonequidistant control points, are given in Section 5, and conclusions are drawn in Section 6.


## 2. Statement of Problem

The P3P problem amounts to determining the distances from a camera’s focal point, or centre of perspective, to three known control points. These control points are actual points that are attached to an object that is free to move in space and whose images in the camera’s image plane can be identified. This is achieved by performing computations based on image measurements, intrinsic camera properties, and the known physical distances between the control points. In what follows, the camera is assumed to be calibrated.LetP be the centre of perspective, and A,B,C the control points, and A′,B′,C′ the image points, as shown in Figure 1. Let (1)λ1=PA,λ2=PB,λ3=PC,d12=AB,d13=AC,d23=BC,α=∡BPA,β=∡APC,γ=∡BPC, and then (2)p1=cos⁡α,p2=cos⁡β,p3=cos⁡γ,with -1<p1,p2,p3<1. From triangles PAB,PAC, and PBC, we obtain the P3P equation system:(3)λ12-2p1λ1λ2+λ22=d122,(4)λ12-2p2λ1λ3+λ32=d132,(5)λ22-2p3λ2λ3+λ32=d232.Since we are interested only in physical solutions, we assume the following reality conditions:(1)
λ1>0,λ2>0,λ3>0;(2)
d12>0,d13>0,d23>0;(3)
d12+d23>d13,d12+d13>d23,d13+d23>d12;(4)
0<α,β,γ<π,0<α+β+γ<2π,γ+β>α,α+γ>β,α+β>γ, the last three of which can also be expressed as(6)p1>p2p3-1-p221/21-p321/2,(7)p2>p1p3-1-p121/21-p321/2,(8)p3>p2p1-1-p221/21-p121/2,respectively, and, as demonstrated by [23], can be reduced to(9)p12+p22+p32-2p1p2p3-1<0,termed as the tetrahedron of reality.Figure 1
The perspective projection of a triangle on the image plane.Without loss of generality, we taked12≥d13,d23. Setting(10)λ1=d12X,λ2=d12Y,λ3=d12Z, (3)-(5) become(11)X2-2p1XY+Y2=1,(12)X2-2p2XZ+Z2=d22,(13)Y2-2p3YZ+Z2=d32,where(14)d2=d13d12,d3=d23d12. Hence, in the most general case, there will be 5 distinct parameters—p1,p2,p3,d2,d3—with(15)-1<p1,p2,p3<1,0<d2,d3≤1.Now, it is clear that(16)0<α+β+γ<2π,γ+β>α,α+γ>β,α+β>γconstitute four planes that make up a tetrahedron with vertices in α,β,γ-space at(17)0,0,0,π,π,0,π,0,π,0,π,π; in p1,p2,p3-space, this implies an inflated tetrahedron, given by (9), with vertices at(18)1,1,1,-1,-1,1,-1,1,-1,1,-1,-1, respectively.Here, we follow the formulation given by Grunert [2]. Setting(19)Y=uX,Z=vX, (11)-(13) become(20)X21+u2-2p1u=1,(21)X21+v2-2p2v=d22,(22)X2u2+v2-2p3uv=d32,whence we obtain(23)X2=11+u2-2p1u,(24)X2=d221+v2-2p2v,(25)X2=d32u2+v2-2p3uv,respectively. Equating (23) and (25) and making u2 the subject of the resulting equation give(26)u2=v2-2p3uv+d322p1u-1d32-1;using (24) and (25) instead gives(27)u2=d32d221+v2-2p2v-v2-2p3uv.Setting these two expressions for u2 equal to each other and making u the subject of the resulting equation, we obtain(28)u=1+d22-d32v2+2p2vd32-1-d22-d32+12d22vp3-p1.Note that (26) appears to have a singularity if d3=1; details of the alternative manipulation that is required in this case are given in Appendix A. Substituting (28) into (26) then leads to(29)s1v4+s2v3+s3v2+s4v+s5=0,where(30)s1=d22+2d2p3-d32+1d22-2d2p3-d32+1,(31)s2=-4d24p1p3+4d22d32p1p3+4d22d32p2+8d22p2p32-4d34p2+4d22p1p3-4d22p2+8d32p2-4p2,(32)s3=-8d22d32p1p2p3+4d24p12+4d24p32-4d22d32p12+4d34p22-8d22p1p2p3-2d24-4d22p32+2d34-8d32p22-4d32+4p22+2,(33)s4=8d22d32p12p2-4d24p1p3+4d22d32p1p3-4d22d32p2+4d22p1p3+4d22p2-4d34p2+8d32p2-4p2,(34)s5=-2d2d3p1+d22+d32-12d2d3p1+d22+d32-1.


## 3. Preliminary Analysis

Prior to finding solutions to (29), it is worth analyzing it first. Consider the case when s1,s5≠0. If s1s5>0, we set v=μ+V with μ+=s5/s11/4 to obtain(35)φ+V≔V4+σ2V3+σ3V2+σ4V+1=0,where(36)σ2=s2s1μ+,σ3=s3s1μ+2,σ4=s4s1μ+3. Since φ+0=1 and φ+→+∞ as V→+∞, it is evident that, in general, (35) can only have 0,2, or 4 positive solutions. So, if s1>0,s5>0, i.e., (37)d22-d32+12-4d22p32>0,d22+d32-12-4d22d32p12>0, respectively, we have (38)-d22-d32+1<2d2p3<d22-d32+1,-d22+d32-1<2d2d3p1<d22+d32-1, respectively, or (39)-2d2p3<d22-d32+1<2d2p3,-2d2d3p1<d22+d32-1<2d2d3p1, i.e.,(40)p1>1-d22-d322d2d3andp3>d22-d32+12d2. Alternatively, if s1<0,s5<0, we have(41)p1<1-d22-d322d2d3andp3<d22-d32+12d2.On the other hand, ifs1s5<0, we set v=μ-V with μ-=-s5/s11/4 to obtain(42)φ-V≔V4+σ2V3+σ3V2+σ4V-1=0,where(43)σ2=s2s1μ-,σ3=s3s1μ-2,σ4=s4s1μ-3. Since φ-0=-1 and φ-→+∞ as V→+∞, it is evident that, in general, (42) can only have 1 or 3 positive solutions. This occurs if(44)p1<1-d22-d322d2d3andp3>d22-d32+12d2, corresponding to s1<0 and s5>0, or(45)p1>1-d22-d322d2d3andp3<d22-d32+12d2, corresponding to s1>0 and s5<0.It is worth comparing the coefficientss1,…s5 obtained via this approach and those obtained by Linnainmaa et al. [7]. Expressions (30)-(34) are certainly more compact than those of the other approach, which will be recapped later in Section 5.2, but have a significant disadvantage: s1 and s5 change sign depending on the values of p1 and p3, which can then lead to 0,1,2,3, or 4 positive solutions. On the other hand, s1 and s5 in the other approach are always positive, and hence there can only be 0,2, or 4 positive solutions. Nevertheless, a strong reason for pursuing the Grunert approach is that it provides an independent way to check the correctness of the other approach, and vice versa.


## 4. The Case of Equidistant Control Points:d2=d3=1

We now consider the case whend2=d3=1, corresponding to the case where the control points are equidistant; this allows to make a direct comparison with the corresponding result in [23]. Equations (30)-(34) give(46)s1=1-4p32,(47)s2=4p32p2p3+p1,(48)s3=-28p1p2p3+1,(49)s4=4p12p1p2+p3,(50)s5=1-4p12.A particular case of this, which allows comparison with the results in [14, 23], is when p2=p3; this is an instructive case to consider, since the resulting algebra is straightforward and also illustrates that two different quartic polynomials derived from the same set of quadratic equations, (11)-(13), can lead to a different solution structure.


### 4.1.p2=p3

Using (46)-(50), polynomial (29) can be factorized as(51)v2-2p2v+2p1-14p22-1v2-2p22p1+1v+2p1+1=0, giving the solutions(52)v1,±=p2±p22-2p1+1and(53)v2,±=2p1+1p2±2p1+12p1p22-3p22+14p22-1,ifp2≠±12±1,ifp2=±12.Although (52) and (53) give all of the solutions to (29), the only ones of interest are those which are real and positive and lie within the tetrahedron of reality, which is given for this plane by(54)p1-1p1-2p22+1<0; the positivity requirement is evident because X,Y,Z>0 from (10), whence v>0 from (19). We analyze (52) and (53) in turn.For (52), we see that there will be no real solutions p1>p22+1/2 and two otherwise; however, v1,- will be negative if(55)0<p2<p22-2p1+1, i.e., p1<1/2, or(56)-p22-2p1+1<p2<0, i.e., p1<1/2. In addition, we see that both solutions will be negative if p2<0 and 1/2<p1<p22+1/2.For (53), there will be two real solutions if(57)p1>-12,p1>32-12p22, or(58)p1<-12,p1<32-12p22. The latter is not possible, and we focus on whether v2,± are positive in the case of the former. If p2>1/2, v2,±>0 if(59)2p1+1p2±2p1+12p1p22-3p22+1>0. So(i)
ifp2>1/2, then v2,±>0 if(60)2p1+1p2>2p1+12p1p22-3p22+1,i.e., p2>1/2, and hence there are two positive roots;(ii)
ifp2<-1/2, then v2,-<0 and v2,+>0 if(61)2p1+12p1p22-3p22+1>-2p1+1p2,i.e., p2<1/2; hence, v2,+<0, and there are no positive roots.On the other hand, ifp2<1/2, v2,±>0 if(62)2p1+1p2±2p1+12p1p22-3p22+1<0. So(i)
if0<p2<1/2, v2,+<0, whereas v2,->0 if(63)2p1+1p2<2p1+12p1p22-3p22+1,i.e., p2<1/2; hence, v2,->0, and so there is only one positive root;(ii)
if-1/2<p2<0, v2,->0 and v2,+>0 only if p22>1/4; hence, v2,+<0, and so there is only one positive root.The overall solution structure based on the above analysis is shown in Figure2; note that it is consistent with the preliminary analysis in Section 3 since, with d2=d3=1 and p2=p3, we should expect 0,2, or 4 positive solutions if p1>1/2 and p2>1/2 or p1<1/2 and p2<1/2, and 1 or 3 positive solutions if p1<1/2 and p2>1/2 or p1>1/2 and p2<1/2. For comparison, we also show in Figure 3 the distribution of solutions that was calculated in [23] using the polynomial of Linnainmaa et al. [7]. It is clear that while there are some similarities, the results are far from identical. For example, for the polynomial used in [23], there were mostly one or three positive solutions in the plane p2=p3, whereas, for Grunert’s polynomial, 0,1,2,3, and 4 are possible. It is therefore worth exploring why the differences arise, and how the two sets of results can be reconciled.Figure 2
The solution structure for Grunert’s polynomial whend2=d3=1 in the plane p2=p3. The integers indicate the number of positive solutions within each enclosed region. There are no positive solutions on the solid lines, one positive solution on the dashed lines, two positive solutions on the dashed-dotted lines, and three positive solutions on the dotted lines. There are zero positive solutions at the point marked ⧫, one positive solution at the point marked •, and two positive solutions at the points marked ■.Figure 3
The solution structure for the polynomial of Linnainmaa et al. [7] when d2=d3=1 in the plane p2=p3. The integers indicate the number of real strictly positive solutions within the enclosed region. On the dashed lines, there are two real strictly positive solutions and there is one real strictly positive solution at (0,0), marked ∘.The common quantity in both approaches is the solutionX. With the Grunert polynomial, we find from (21) that(64)X=11+v2-2p2v1/2,where v is given by (52) and (53). With the Linnainmaa et al. polynomial,(65)X=ξ1/2,where(66)ξ=121-p1or(67)ξ=4p1p22+1-2p22±2p221+2p12p1p22-3p22+121+p1-2p22;note that (66) gives a double root. It is now far from obvious that inserting (52) and (53) into (64) will lead to the same solutions as inserting (66) and (67) into (65), particularly as the approaches seem to lead to different numbers of solutions. Although this can be shown rigorously, the necessary algebra is rather lengthy, and we instead adopt an alternative way to see what is happening. As shown in Figure 4, we superpose Figures 2 and 3, which indicates that there are sixteen different regions to consider when comparing solutions obtained via the two methods. Then, we pick a point at random from each region and calculate all of the possible solutions for X, real as well as complex; these are documented in Table 1.Table 1
Comparison of solutions obtained using the polynomials of Grunert [2] and Linnainmaa et al. [7] (double∗ root). Note that for (0.6,0.6) in region 7, a double root numerically coincides with a single root for the Linnainmaa et al. polynomial because of the values of p1 and p2 chosen.
REGION p 1 p 2 Grunert [2] Linnainmaa et al. [7] 1 0.6 - 0.83 1.1180,1.1180,1.8467 ± 0.7349 i 1.1180,1.8467±0.7349i 2 - 0.75 - 0.7 0.4771,1.3067,1.4142,1.4142 0.4771,1.3067,1.4142∗ 3 0.75 - 0.25 0.3088,0.7473,1.4142,1.4142 0.3088,0.7473,1.4142∗ 4 0.75 0.25 0.3088,0.7473,1.4142,1.4142 0.3088,0.7473,1.4142∗ 5 0.85 0.6 0.1706,1.1410,1.8257,1.8257 0.1706,1.1410,1.8257∗ 6 0.55 0.43 0.1186,0.9298,1.0541,1.0541 0.1186,0.9298,1.0541∗ 7 0.6 0.6 0.2236,1.1180,1.1180,1.1180 0.2236,1.1180,∗1.1180 8 0.6 0.8 1.1180,1.1180,1.4832 ± 0.4873 i 1.1180,∗1.4832±0.4873i 9 0.3 - 0.75 0.8452,0.8452,1.6036 ± 1.0000 i 0.8452 , ∗ 1.6036 ± 1.0000 i 10 0.3 - 0.6 0.3623,0.8452,0.8452,1.0471 0.3623,0.8452 , ∗ 1.0471 11 0 - 0.25 0.4924,0.7071,0.7071,0.8704 0.4924,0.7071 , ∗ 0.8704 12 0 0.25 0.4924,0.7071,0.7071,0.8704 0.4924,0.7071 , ∗ 0.8704 13 0.3 0.53 0.0820,0.8452,0.8452,1.0215 0.0820,0.8452 , ∗ 1.0215 14 0.3 0.7 0.8452,0.8452,1.1068 ± 0.5244 i 0.8452 , ∗ 1.1068 ± 0.5244 i 15 - 0.75 - 0.2 0.5345,0.5345,1.5530 ± 0.2425 i 0.5345 , ∗ 1.5530 ± 0.2425 i 16 - 0.75 0.2 0.5345,0.5345,1.5530 ± 0.2425 i 0.5345,∗1.5530±0.2425iFigure 4
Superposition of Figures2 and 3, indicating that there are sixteen different regions to consider when comparing solutions.Several points are worthy of note. Even though Figures2 and 3 are rather different to each other, the solutions for X in Table 1 are identical. Even in regions where the Grunert polynomial gives no real positive solutions, i.e., regions 1 and 2, insertion of the complex solutions into (64) nevertheless leads to positive solutions for X. Moreover, although Figure 2 resembles Figure 2 from [14] more than Figure 3, it turns out that Figure 3 is in fact more reflective of the number of positive solutions as p1 and p2 are varied.


### 4.2.p12+p22+p32-2p1p2p3-1<0

In [23], much of the analysis of the resulting polynomial centred on the signs of the coefficients (si)i=1,…,5. In particular, s1 and s5 were found to be positive within the inflated tetrahedron given by p12+p22+p32-2p1p2p3-1<0; moreover, the fact that the roots that were of interest had to be strictly positive gave further scope for limiting the number of possibilities. Here, however, the coefficients are much simpler and s1 and s5 both change sign within the tetrahedron, as do s2,s3, and s4; also, both positive and negative roots of the polynomial are permissible. Hence, there is no scope to perform the detailed analysis of the coefficients, and we turn instead to considering the discriminant of the polynomial.Recapping from [23], the discriminant, ΔW, of (29) is given by(68)ΔW=256s13s53-192s12s2s4s52-128s12s32s52+144s12s3s42s5-27s12s44+144s1s22s3s52-6s1s22s42s5-80s1s2s32s4s5+18s1s2s3s43+16s1s34s5-4s1s33s42-27s23s53+18s23s3s4s5-4s23s43-4s22s33s5+s22s32s42.The number of real roots that the polynomial will have will be determined by the sign of ΔW and the signs of three other polynomials:(1)
(69)P=8s1s3-3s22,such that P/8s12 is the second-degree coefficient of the depressed quartic associated with (29);(2)
(70)Δ0=s32-3s2s4+12s1s5,which is zero if the quartic has a triple root;(3)
(71)D=64s13s5-16s12s32+16s1s22s3-16s12s2s4-3s24,which is zero if the quartic has two double roots.The possible cases for the nature of the roots are then as follows [25]:(i)
IfΔW<0, then the equation has two real roots and two complex conjugate roots.(ii)
IfΔW>0, then the equation’s four roots are either all real or all complex.
(a)
IfP<0 and D<0, then all four roots are real and distinct.(b)
IfP>0 or D>0, then there are two pairs of complex conjugate roots [26].(iii)
IfΔW=0, then either the polynomial has a multiple root, or it is the square of a quadratic polynomial. Here are the different cases that can occur:
(a)
IfP<0, D<0, and Δ0≠0, there are a real double root and two real simple roots.(b)
IfP>0 or D>0, there are a real double root and two complex conjugate roots.(c)
IfΔ0=0 and D≠0, there are a triple root and a simple root, all real.(d)
IfD=0, then one has the following:
(1)
IfP<0, there are two real double roots.(2)
IfP>0, there are two complex conjugate double roots.(3)
IfΔ0=0, all four roots are equal to -s2/4s1.Using a symbolic manipulator, Maple™, to process (46)-(50) and (68)-(71), we obtain ΔW,P, and Q as given in (B.1)-(B.4) in Appendix B. Comparing with (61), (62), (63), and (65) in [23], we see that whereas (B.3) and (B.4) bear no resemblance to (63) and (65), respectively, expression (B.1) in this paper and expression (61) in [23] share a common factor, f1. Furthermore, since the remainder of both expressions for ΔW is negative, it is clear that it is the factor f1 which determines the sign of ΔW in both cases and hence determines the number of roots that the respective polynomials will have.It is now evident that whenever Grunert’s polynomial has two real roots, so will the polynomial of Linnainmaa et al. [7]. However, the disparity in the two sets of expressions for P and D means that it is not entirely obvious that when one polynomial has four real roots, the other one will also. To verify this, there seems to be no choice other than to perform a numerical sweep over all (p1,p2,p3)-combinations lying within the inflated tetrahedron, in order to determine the signs of P and D; it turns out that P<0,D<0, implying that all four roots are real and distinct in both cases. Although sweeping is perhaps not entirely satisfactory from the point of view of rigour, there are a number of mitigating factors. First of all, we may vary the number of (p1,p2,p3)-combinations that we sweep over; if the results obtained are independent of this number, then we may be more certain that the result is correct. Moreover, and as we show below, the fact that sweeping carried out for two different polynomials leads to the same result is further evidence that the results are correct. More details on the sweeping are given in Section 5.A consequence of the above is that, for both polynomials, there are four relevant solutions to the problem at 25% of all available spatial locations for the control-point combinations, and two positive solutions at the remaining 75%. This result extends the conclusion in [23] to Grunert’s polynomial, but it is nevertheless only for the case when d2=d3=1. It is now of interest to see how this result changes for both polynomials if d2,d3≠1.


## 4.1.p2=p3

Using (46)-(50), polynomial (29) can be factorized as(51)v2-2p2v+2p1-14p22-1v2-2p22p1+1v+2p1+1=0, giving the solutions(52)v1,±=p2±p22-2p1+1and(53)v2,±=2p1+1p2±2p1+12p1p22-3p22+14p22-1,ifp2≠±12±1,ifp2=±12.Although (52) and (53) give all of the solutions to (29), the only ones of interest are those which are real and positive and lie within the tetrahedron of reality, which is given for this plane by(54)p1-1p1-2p22+1<0; the positivity requirement is evident because X,Y,Z>0 from (10), whence v>0 from (19). We analyze (52) and (53) in turn.For (52), we see that there will be no real solutions p1>p22+1/2 and two otherwise; however, v1,- will be negative if(55)0<p2<p22-2p1+1, i.e., p1<1/2, or(56)-p22-2p1+1<p2<0, i.e., p1<1/2. In addition, we see that both solutions will be negative if p2<0 and 1/2<p1<p22+1/2.For (53), there will be two real solutions if(57)p1>-12,p1>32-12p22, or(58)p1<-12,p1<32-12p22. The latter is not possible, and we focus on whether v2,± are positive in the case of the former. If p2>1/2, v2,±>0 if(59)2p1+1p2±2p1+12p1p22-3p22+1>0. So(i)
ifp2>1/2, then v2,±>0 if(60)2p1+1p2>2p1+12p1p22-3p22+1,i.e., p2>1/2, and hence there are two positive roots;(ii)
ifp2<-1/2, then v2,-<0 and v2,+>0 if(61)2p1+12p1p22-3p22+1>-2p1+1p2,i.e., p2<1/2; hence, v2,+<0, and there are no positive roots.On the other hand, ifp2<1/2, v2,±>0 if(62)2p1+1p2±2p1+12p1p22-3p22+1<0. So(i)
if0<p2<1/2, v2,+<0, whereas v2,->0 if(63)2p1+1p2<2p1+12p1p22-3p22+1,i.e., p2<1/2; hence, v2,->0, and so there is only one positive root;(ii)
if-1/2<p2<0, v2,->0 and v2,+>0 only if p22>1/4; hence, v2,+<0, and so there is only one positive root.The overall solution structure based on the above analysis is shown in Figure2; note that it is consistent with the preliminary analysis in Section 3 since, with d2=d3=1 and p2=p3, we should expect 0,2, or 4 positive solutions if p1>1/2 and p2>1/2 or p1<1/2 and p2<1/2, and 1 or 3 positive solutions if p1<1/2 and p2>1/2 or p1>1/2 and p2<1/2. For comparison, we also show in Figure 3 the distribution of solutions that was calculated in [23] using the polynomial of Linnainmaa et al. [7]. It is clear that while there are some similarities, the results are far from identical. For example, for the polynomial used in [23], there were mostly one or three positive solutions in the plane p2=p3, whereas, for Grunert’s polynomial, 0,1,2,3, and 4 are possible. It is therefore worth exploring why the differences arise, and how the two sets of results can be reconciled.Figure 2
The solution structure for Grunert’s polynomial whend2=d3=1 in the plane p2=p3. The integers indicate the number of positive solutions within each enclosed region. There are no positive solutions on the solid lines, one positive solution on the dashed lines, two positive solutions on the dashed-dotted lines, and three positive solutions on the dotted lines. There are zero positive solutions at the point marked ⧫, one positive solution at the point marked •, and two positive solutions at the points marked ■.Figure 3
The solution structure for the polynomial of Linnainmaa et al. [7] when d2=d3=1 in the plane p2=p3. The integers indicate the number of real strictly positive solutions within the enclosed region. On the dashed lines, there are two real strictly positive solutions and there is one real strictly positive solution at (0,0), marked ∘.The common quantity in both approaches is the solutionX. With the Grunert polynomial, we find from (21) that(64)X=11+v2-2p2v1/2,where v is given by (52) and (53). With the Linnainmaa et al. polynomial,(65)X=ξ1/2,where(66)ξ=121-p1or(67)ξ=4p1p22+1-2p22±2p221+2p12p1p22-3p22+121+p1-2p22;note that (66) gives a double root. It is now far from obvious that inserting (52) and (53) into (64) will lead to the same solutions as inserting (66) and (67) into (65), particularly as the approaches seem to lead to different numbers of solutions. Although this can be shown rigorously, the necessary algebra is rather lengthy, and we instead adopt an alternative way to see what is happening. As shown in Figure 4, we superpose Figures 2 and 3, which indicates that there are sixteen different regions to consider when comparing solutions obtained via the two methods. Then, we pick a point at random from each region and calculate all of the possible solutions for X, real as well as complex; these are documented in Table 1.Table 1
Comparison of solutions obtained using the polynomials of Grunert [2] and Linnainmaa et al. [7] (double∗ root). Note that for (0.6,0.6) in region 7, a double root numerically coincides with a single root for the Linnainmaa et al. polynomial because of the values of p1 and p2 chosen.
REGION p 1 p 2 Grunert [2] Linnainmaa et al. [7] 1 0.6 - 0.83 1.1180,1.1180,1.8467 ± 0.7349 i 1.1180,1.8467±0.7349i 2 - 0.75 - 0.7 0.4771,1.3067,1.4142,1.4142 0.4771,1.3067,1.4142∗ 3 0.75 - 0.25 0.3088,0.7473,1.4142,1.4142 0.3088,0.7473,1.4142∗ 4 0.75 0.25 0.3088,0.7473,1.4142,1.4142 0.3088,0.7473,1.4142∗ 5 0.85 0.6 0.1706,1.1410,1.8257,1.8257 0.1706,1.1410,1.8257∗ 6 0.55 0.43 0.1186,0.9298,1.0541,1.0541 0.1186,0.9298,1.0541∗ 7 0.6 0.6 0.2236,1.1180,1.1180,1.1180 0.2236,1.1180,∗1.1180 8 0.6 0.8 1.1180,1.1180,1.4832 ± 0.4873 i 1.1180,∗1.4832±0.4873i 9 0.3 - 0.75 0.8452,0.8452,1.6036 ± 1.0000 i 0.8452 , ∗ 1.6036 ± 1.0000 i 10 0.3 - 0.6 0.3623,0.8452,0.8452,1.0471 0.3623,0.8452 , ∗ 1.0471 11 0 - 0.25 0.4924,0.7071,0.7071,0.8704 0.4924,0.7071 , ∗ 0.8704 12 0 0.25 0.4924,0.7071,0.7071,0.8704 0.4924,0.7071 , ∗ 0.8704 13 0.3 0.53 0.0820,0.8452,0.8452,1.0215 0.0820,0.8452 , ∗ 1.0215 14 0.3 0.7 0.8452,0.8452,1.1068 ± 0.5244 i 0.8452 , ∗ 1.1068 ± 0.5244 i 15 - 0.75 - 0.2 0.5345,0.5345,1.5530 ± 0.2425 i 0.5345 , ∗ 1.5530 ± 0.2425 i 16 - 0.75 0.2 0.5345,0.5345,1.5530 ± 0.2425 i 0.5345,∗1.5530±0.2425iFigure 4
Superposition of Figures2 and 3, indicating that there are sixteen different regions to consider when comparing solutions.Several points are worthy of note. Even though Figures2 and 3 are rather different to each other, the solutions for X in Table 1 are identical. Even in regions where the Grunert polynomial gives no real positive solutions, i.e., regions 1 and 2, insertion of the complex solutions into (64) nevertheless leads to positive solutions for X. Moreover, although Figure 2 resembles Figure 2 from [14] more than Figure 3, it turns out that Figure 3 is in fact more reflective of the number of positive solutions as p1 and p2 are varied.


## 4.2.p12+p22+p32-2p1p2p3-1<0

In [23], much of the analysis of the resulting polynomial centred on the signs of the coefficients (si)i=1,…,5. In particular, s1 and s5 were found to be positive within the inflated tetrahedron given by p12+p22+p32-2p1p2p3-1<0; moreover, the fact that the roots that were of interest had to be strictly positive gave further scope for limiting the number of possibilities. Here, however, the coefficients are much simpler and s1 and s5 both change sign within the tetrahedron, as do s2,s3, and s4; also, both positive and negative roots of the polynomial are permissible. Hence, there is no scope to perform the detailed analysis of the coefficients, and we turn instead to considering the discriminant of the polynomial.Recapping from [23], the discriminant, ΔW, of (29) is given by(68)ΔW=256s13s53-192s12s2s4s52-128s12s32s52+144s12s3s42s5-27s12s44+144s1s22s3s52-6s1s22s42s5-80s1s2s32s4s5+18s1s2s3s43+16s1s34s5-4s1s33s42-27s23s53+18s23s3s4s5-4s23s43-4s22s33s5+s22s32s42.The number of real roots that the polynomial will have will be determined by the sign of ΔW and the signs of three other polynomials:(1)
(69)P=8s1s3-3s22,such that P/8s12 is the second-degree coefficient of the depressed quartic associated with (29);(2)
(70)Δ0=s32-3s2s4+12s1s5,which is zero if the quartic has a triple root;(3)
(71)D=64s13s5-16s12s32+16s1s22s3-16s12s2s4-3s24,which is zero if the quartic has two double roots.The possible cases for the nature of the roots are then as follows [25]:(i)
IfΔW<0, then the equation has two real roots and two complex conjugate roots.(ii)
IfΔW>0, then the equation’s four roots are either all real or all complex.
(a)
IfP<0 and D<0, then all four roots are real and distinct.(b)
IfP>0 or D>0, then there are two pairs of complex conjugate roots [26].(iii)
IfΔW=0, then either the polynomial has a multiple root, or it is the square of a quadratic polynomial. Here are the different cases that can occur:
(a)
IfP<0, D<0, and Δ0≠0, there are a real double root and two real simple roots.(b)
IfP>0 or D>0, there are a real double root and two complex conjugate roots.(c)
IfΔ0=0 and D≠0, there are a triple root and a simple root, all real.(d)
IfD=0, then one has the following:
(1)
IfP<0, there are two real double roots.(2)
IfP>0, there are two complex conjugate double roots.(3)
IfΔ0=0, all four roots are equal to -s2/4s1.Using a symbolic manipulator, Maple™, to process (46)-(50) and (68)-(71), we obtain ΔW,P, and Q as given in (B.1)-(B.4) in Appendix B. Comparing with (61), (62), (63), and (65) in [23], we see that whereas (B.3) and (B.4) bear no resemblance to (63) and (65), respectively, expression (B.1) in this paper and expression (61) in [23] share a common factor, f1. Furthermore, since the remainder of both expressions for ΔW is negative, it is clear that it is the factor f1 which determines the sign of ΔW in both cases and hence determines the number of roots that the respective polynomials will have.It is now evident that whenever Grunert’s polynomial has two real roots, so will the polynomial of Linnainmaa et al. [7]. However, the disparity in the two sets of expressions for P and D means that it is not entirely obvious that when one polynomial has four real roots, the other one will also. To verify this, there seems to be no choice other than to perform a numerical sweep over all (p1,p2,p3)-combinations lying within the inflated tetrahedron, in order to determine the signs of P and D; it turns out that P<0,D<0, implying that all four roots are real and distinct in both cases. Although sweeping is perhaps not entirely satisfactory from the point of view of rigour, there are a number of mitigating factors. First of all, we may vary the number of (p1,p2,p3)-combinations that we sweep over; if the results obtained are independent of this number, then we may be more certain that the result is correct. Moreover, and as we show below, the fact that sweeping carried out for two different polynomials leads to the same result is further evidence that the results are correct. More details on the sweeping are given in Section 5.A consequence of the above is that, for both polynomials, there are four relevant solutions to the problem at 25% of all available spatial locations for the control-point combinations, and two positive solutions at the remaining 75%. This result extends the conclusion in [23] to Grunert’s polynomial, but it is nevertheless only for the case when d2=d3=1. It is now of interest to see how this result changes for both polynomials if d2,d3≠1.


## 5.d2,d3≠1

In this section, we consider first, in Section5.1, all of the roots of the quartic polynomial; then, in Section 5.2, having established beyond doubt that the Grunert and Linnainmaa et al. formulations give the same results, we consider the positive roots only, which is the case of direct relevance to the P3P problem.


### 5.1. All Solutions

For the general case whend2,d3≠1, we recall first that we need only consider d2+d3>1,0<d2≤1,0<d3≤1. In what follows, we seek to determine what fraction of the inflated tetrahedron consists of (p1,p2,p3)-combinations that lead to two or four solutions, as a function of d2 and d3. To do this requires us to use the Maple-generated expressions for ΔW,P, and D to perform the requisite volume integrals over the inflated tetrahedron, restricted to where each of these is of one sign. The volume integrals were computed via a rather unusual use of the finite-element software Comsol Multiphysics. Although this software is more often used for solving partial differential equations, the fact that it is able to discretize a given geometry into elements can be exploited to evaluate the required integrals; in particular, we discretized the (p1,p2,p3)-space, -1<p1,p2,p3<1, using first-order tetrahedral elements. Note also that we use the software to calculate the quadratures, i.e., volume integrals, of known functions—ΔW,P, and D—of three variables (p1,p2,p3); thus, no initial conditions are required.Prior to the full computations, we tested that the results obtained were mesh-independent. Within the software, it is straightforward to refine the mesh, and benchmark results were generated ford2=1/3 and 2/3 as a function of d3 for meshes having 17090, 60643, and 188936 elements. Figure 5 shows the percentage, Π, of (p1,p2,p3)-combinations for which ΔW>0 as a function of d3. For both values of d2, the results for each mesh are literally on top of each other, and hence the results are indeed independent of the mesh used; subsequent calculations were then carried out using the mesh with 60643 elements.Figure 5
Percentage,Π, of (p1,p2,p3)-combinations for which ΔW>0, as a function of d3 for d2=1/3 and 2/3, as calculated using three different meshes and the formulation of Grunert [2].Figures6 and 7 show Π as a function of d3 for d2=0.25,0.5,0.75,1 using the formulations of Grunert [2] and Linnainmaa et al. [7], respectively. Also, denoting by ΔWG and ΔWL the discriminant of the polynomials arising from the Grunert and Linnainmaa et al. formulations, respectively, we find that(72)ΔWG=4096d28Δ132Δ¯W,whereas(73)ΔWL=16777216ΔT2Δ122Δ132Δ232Δ¯W,where (74)ΔT=p12+p22+p32-2p1p2p3-1,Δ12=21-d22p1p2p3+d22-d32-1p12+d32+d22-1p22,Δ13=2d32-1p1p2p3+p321-d22-d32+1+d22-d32p12,Δ23=2d22-d32p1p2p3-1+d22-d32p22+1+d32-d22p32, with Δ¯W being a lengthy expression, which we omit here, that contains p1,p2,p3,d2, and d3 and satisfies (75)Δ¯Wp1,p2,p3,d2,d3=Δ¯Wp1,p3,p2,d3,d2;hence, in Figures 6 and 7,(76)Πd2,d3=Πd3,d2. Moreover, when d2=d3=1, Δ¯W reduces to f1, which is given in (B.2). It is clear that although ΔWG≠ΔWL, it is their common factor Δ¯W which explains the similarity between Figures 6 and 7.Figure 6
Percentage,Π, of (p1,p2,p3)-combinations for which ΔW>0, as a function of d3 for d2=0.25,0.5,0.75,1, using the formulation of Grunert [2].Figure 7
Percentage,Π, of (p1,p2,p3)-combinations for which ΔW>0, as a function of d3 for d2=0.25,0.5,0.75,1, using the formulation of Linnainmaa et al. [7].However, Figures6 and 7 only consider the sign of ΔW, without considering the signs of P and D; in the analysis in [23] for d2=d3=1, it turned out that whenever ΔW<0, then P,D>0, which meant that the sign alone was enough to indicate four real solutions. In this context, consider Figure 8 which shows Π,ΠD,ΠP, and ΠD,P, where(i)
ΠD is the percentage of (p1,p2,p3)-combinations for which ΔW>0 and D<0;(ii)
ΠP is the percentage for which ΔW>0 and P<0;(iii)
ΠD,P is the percentage for which ΔW>0 and D,P<0.Figure 8
Π , Π D , Π P , Π D , P as functions of d3 for d2=0.6, using the formulation of [2].This figure is for the case whend2=0.6 and is computed using Grunert’s polynomial, but qualitatively similar results were obtained for other values of d2. Similarly, Figure 9 shows the corresponding result when using the polynomial of [7]; hence, although we were not able analytically to reconcile the two forms for D and P obtained here and in [23], the behaviour for Π and ΠD,P appears to be nevertheless the same.Figure 9
Π , Π D , Π P , Π D , P as functions of d3 for d2=0.6, using the formulation of [7].


### 5.2. Solutions to the P3P Problem

From the previous sections, it has become apparent that the formulation of Linnainmaa et al. provides the solution structure more transparently than the formulation of Grunert. For example, it provides zero, two, or four positive solutions for all values ofp1,p2,p3,d2,d3, whereas the Grunert polynomial gives 0,2, or 4 for some values, and 1 and 3 for others. Thus, in order to consider the positive solutions, rather than just the real ones, we revert to the formulation of Linnainmaa et al.; the relevant polynomial coefficients are now, as in [7, 23],(77)s1=16p12+p22+p32-2p1p2p3-12,(78)s2=-32p12+p22+p32-2p1p2p3-11+d22p32-d22+d32+1p1p2p3+2d32p12p22+d22-d32p12+1-d32p22+d32-d22-1,(79)s3=16d22-d322p14+2d32-12p24+21+4d22+d24p34-8d22+1-d325d22+1-5d32p12-d22+5-5d32p22+86d32d22-5d24-d34-5-14d22+6d32p32+322d22d32-d34-d24-d32-d22p12-d32d22+1-2d32+d22+d34p22-d32d22+1+4d22+d32+d24p33p1p2+64d22d32+d22+d32p12p22p32+163d34+d24-4d32-4d22d32+1p12p22+1+2d22+d34-4d32d22+3d24p13p32+3+2d22-4d32+d24+d34p32p22+1+d34+d24+10d22-2d32-2d22d32p1p2p3+24d22+1-d322,(80)s4=82d222d22d32-d34-1-d24p32+d22-d321+d22-d322p12+22d32-d24-d34-1p32+1-d321+d22-d322p22+4d22d22+d32+1p32+1+d22-d32d24-6d22+1-d34p1p2p3-4p32d22-1+d22-d3221+d22p32-1-d22+d32,(81)s5=1+d22-d32+2d2p321+d22-d32-2d2p32.A further advantage of this formulation is thats1>0 and s5>0 for all values of p1,p2,p3,d2,d3. Consequently, we note that if ΔW>0,P<0,D<0,s2<0,s3>0,s4<0, then there cannot be any negative solutions. Indeed, in [23], this was found to be the case when d2=d3=1, which suggests exploring this possibility when d2,d3≠1. While it is not possible to verify analytically whether these six inequalities are always satisfied simultaneously, it is possible to carry out a numerical sweep over (p1,p2,p3) for different (d2,d3)-combinations. First of all, Figure 10 shows ΠD,P for d2=0.25,0.5,0.75,1, whereas Figure 11   shows ΠD,P,+ for d2=0.25,0.5,0.75,1, where ΠD,P,+ denotes the percentage of (p1,p2,p3)-combinations for which there are four real solutions and s2<0,s3>0,s4<0. It is clear that there is no difference between the two plots for the values of d2 chosen, which strongly indicates that when there are four real solutions, they are all positive for all values of d2.Figure 10
Percentage,ΠD,P, of (p1,p2,p3)-combinations for which there are four real solutions, as a function of d3 for d2=0.25,0.5,0.75,1.Figure 11
Percentage,ΠD,P,+, of (p1,p2,p3)-combinations for which there are four real solutions and s3>0,s2<0,s4<0, as a function of d3 for d2=0.25,0.5,0.75,1.In fact, Figure11 indicates that, for each value of d2, there exists a range in d3 for which the possibility of four positive solutions is practically zero; roughly speaking, 1-d2<d3<1.15-d2. However, as d3 approaches 1-d2 the possibility of four complex solutions rises rapidly; thus, a plausible compromise for achieving the situation of two real solutions is to employ a value of d3 that is not too close to 1-d2. It is also evident that choosing a value of d2 that is small will lower this possibility still further.


## 5.1. All Solutions

For the general case whend2,d3≠1, we recall first that we need only consider d2+d3>1,0<d2≤1,0<d3≤1. In what follows, we seek to determine what fraction of the inflated tetrahedron consists of (p1,p2,p3)-combinations that lead to two or four solutions, as a function of d2 and d3. To do this requires us to use the Maple-generated expressions for ΔW,P, and D to perform the requisite volume integrals over the inflated tetrahedron, restricted to where each of these is of one sign. The volume integrals were computed via a rather unusual use of the finite-element software Comsol Multiphysics. Although this software is more often used for solving partial differential equations, the fact that it is able to discretize a given geometry into elements can be exploited to evaluate the required integrals; in particular, we discretized the (p1,p2,p3)-space, -1<p1,p2,p3<1, using first-order tetrahedral elements. Note also that we use the software to calculate the quadratures, i.e., volume integrals, of known functions—ΔW,P, and D—of three variables (p1,p2,p3); thus, no initial conditions are required.Prior to the full computations, we tested that the results obtained were mesh-independent. Within the software, it is straightforward to refine the mesh, and benchmark results were generated ford2=1/3 and 2/3 as a function of d3 for meshes having 17090, 60643, and 188936 elements. Figure 5 shows the percentage, Π, of (p1,p2,p3)-combinations for which ΔW>0 as a function of d3. For both values of d2, the results for each mesh are literally on top of each other, and hence the results are indeed independent of the mesh used; subsequent calculations were then carried out using the mesh with 60643 elements.Figure 5
Percentage,Π, of (p1,p2,p3)-combinations for which ΔW>0, as a function of d3 for d2=1/3 and 2/3, as calculated using three different meshes and the formulation of Grunert [2].Figures6 and 7 show Π as a function of d3 for d2=0.25,0.5,0.75,1 using the formulations of Grunert [2] and Linnainmaa et al. [7], respectively. Also, denoting by ΔWG and ΔWL the discriminant of the polynomials arising from the Grunert and Linnainmaa et al. formulations, respectively, we find that(72)ΔWG=4096d28Δ132Δ¯W,whereas(73)ΔWL=16777216ΔT2Δ122Δ132Δ232Δ¯W,where (74)ΔT=p12+p22+p32-2p1p2p3-1,Δ12=21-d22p1p2p3+d22-d32-1p12+d32+d22-1p22,Δ13=2d32-1p1p2p3+p321-d22-d32+1+d22-d32p12,Δ23=2d22-d32p1p2p3-1+d22-d32p22+1+d32-d22p32, with Δ¯W being a lengthy expression, which we omit here, that contains p1,p2,p3,d2, and d3 and satisfies (75)Δ¯Wp1,p2,p3,d2,d3=Δ¯Wp1,p3,p2,d3,d2;hence, in Figures 6 and 7,(76)Πd2,d3=Πd3,d2. Moreover, when d2=d3=1, Δ¯W reduces to f1, which is given in (B.2). It is clear that although ΔWG≠ΔWL, it is their common factor Δ¯W which explains the similarity between Figures 6 and 7.Figure 6
Percentage,Π, of (p1,p2,p3)-combinations for which ΔW>0, as a function of d3 for d2=0.25,0.5,0.75,1, using the formulation of Grunert [2].Figure 7
Percentage,Π, of (p1,p2,p3)-combinations for which ΔW>0, as a function of d3 for d2=0.25,0.5,0.75,1, using the formulation of Linnainmaa et al. [7].However, Figures6 and 7 only consider the sign of ΔW, without considering the signs of P and D; in the analysis in [23] for d2=d3=1, it turned out that whenever ΔW<0, then P,D>0, which meant that the sign alone was enough to indicate four real solutions. In this context, consider Figure 8 which shows Π,ΠD,ΠP, and ΠD,P, where(i)
ΠD is the percentage of (p1,p2,p3)-combinations for which ΔW>0 and D<0;(ii)
ΠP is the percentage for which ΔW>0 and P<0;(iii)
ΠD,P is the percentage for which ΔW>0 and D,P<0.Figure 8
Π , Π D , Π P , Π D , P as functions of d3 for d2=0.6, using the formulation of [2].This figure is for the case whend2=0.6 and is computed using Grunert’s polynomial, but qualitatively similar results were obtained for other values of d2. Similarly, Figure 9 shows the corresponding result when using the polynomial of [7]; hence, although we were not able analytically to reconcile the two forms for D and P obtained here and in [23], the behaviour for Π and ΠD,P appears to be nevertheless the same.Figure 9
Π , Π D , Π P , Π D , P as functions of d3 for d2=0.6, using the formulation of [7].


## 5.2. Solutions to the P3P Problem

From the previous sections, it has become apparent that the formulation of Linnainmaa et al. provides the solution structure more transparently than the formulation of Grunert. For example, it provides zero, two, or four positive solutions for all values ofp1,p2,p3,d2,d3, whereas the Grunert polynomial gives 0,2, or 4 for some values, and 1 and 3 for others. Thus, in order to consider the positive solutions, rather than just the real ones, we revert to the formulation of Linnainmaa et al.; the relevant polynomial coefficients are now, as in [7, 23],(77)s1=16p12+p22+p32-2p1p2p3-12,(78)s2=-32p12+p22+p32-2p1p2p3-11+d22p32-d22+d32+1p1p2p3+2d32p12p22+d22-d32p12+1-d32p22+d32-d22-1,(79)s3=16d22-d322p14+2d32-12p24+21+4d22+d24p34-8d22+1-d325d22+1-5d32p12-d22+5-5d32p22+86d32d22-5d24-d34-5-14d22+6d32p32+322d22d32-d34-d24-d32-d22p12-d32d22+1-2d32+d22+d34p22-d32d22+1+4d22+d32+d24p33p1p2+64d22d32+d22+d32p12p22p32+163d34+d24-4d32-4d22d32+1p12p22+1+2d22+d34-4d32d22+3d24p13p32+3+2d22-4d32+d24+d34p32p22+1+d34+d24+10d22-2d32-2d22d32p1p2p3+24d22+1-d322,(80)s4=82d222d22d32-d34-1-d24p32+d22-d321+d22-d322p12+22d32-d24-d34-1p32+1-d321+d22-d322p22+4d22d22+d32+1p32+1+d22-d32d24-6d22+1-d34p1p2p3-4p32d22-1+d22-d3221+d22p32-1-d22+d32,(81)s5=1+d22-d32+2d2p321+d22-d32-2d2p32.A further advantage of this formulation is thats1>0 and s5>0 for all values of p1,p2,p3,d2,d3. Consequently, we note that if ΔW>0,P<0,D<0,s2<0,s3>0,s4<0, then there cannot be any negative solutions. Indeed, in [23], this was found to be the case when d2=d3=1, which suggests exploring this possibility when d2,d3≠1. While it is not possible to verify analytically whether these six inequalities are always satisfied simultaneously, it is possible to carry out a numerical sweep over (p1,p2,p3) for different (d2,d3)-combinations. First of all, Figure 10 shows ΠD,P for d2=0.25,0.5,0.75,1, whereas Figure 11   shows ΠD,P,+ for d2=0.25,0.5,0.75,1, where ΠD,P,+ denotes the percentage of (p1,p2,p3)-combinations for which there are four real solutions and s2<0,s3>0,s4<0. It is clear that there is no difference between the two plots for the values of d2 chosen, which strongly indicates that when there are four real solutions, they are all positive for all values of d2.Figure 10
Percentage,ΠD,P, of (p1,p2,p3)-combinations for which there are four real solutions, as a function of d3 for d2=0.25,0.5,0.75,1.Figure 11
Percentage,ΠD,P,+, of (p1,p2,p3)-combinations for which there are four real solutions and s3>0,s2<0,s4<0, as a function of d3 for d2=0.25,0.5,0.75,1.In fact, Figure11 indicates that, for each value of d2, there exists a range in d3 for which the possibility of four positive solutions is practically zero; roughly speaking, 1-d2<d3<1.15-d2. However, as d3 approaches 1-d2 the possibility of four complex solutions rises rapidly; thus, a plausible compromise for achieving the situation of two real solutions is to employ a value of d3 that is not too close to 1-d2. It is also evident that choosing a value of d2 that is small will lower this possibility still further.


## 6. Conclusions

In this paper, we have analyzed the effect of control-point spacing on solutions to the quartic equation that arises in the P3P problem; as a diagnostic to verify the analysis, the formulations due to Grunert [2] and Linnainmaa et al. [7] were considered. Although both polynomials come from the original set of three quadratic equations, (3)-(5), their coefficients are completely different. Through analysis of solutions for the particular case when d2=d3=1 and p2=p3, it is evident that the polynomials will not necessarily have the same number of solutions at all values of (p1,p2,p3); however, we were subsequently able to show how the two solution structures could be reconciled. Moreover, through symbolic manipulation, we are able to determine that, for a given combination (d2,d3), the polynomials have the same percentage of all possible (p1,p2,p3)-combinations which have four positive solutions; when d2=d3=1, this is 25%.Moreover, a sweep over all admissible combinations of (d2,d3) enables us to explore whether it might be possible to choose d2 and d3 so that the case of four positive solutions can be avoided completely, since it may be computationally advantageous to only have to choose from two positive solutions, rather than four. It turns out that, for all admissible (d2,d3)-combinations, there will always be some (p1,p2,p3)-combinations which give four positive solutions. Nevertheless, prudent choice of d2 and d3 can reduce the percentage of (p1,p2,p3)-combinations giving four positive solutions to practically zero. To achieve this, it is necessary to take either d2 or d3 close to 1, and then to take the other one greater than around 0.15. In addition, it ensures that all (p1,p2,p3)-combinations within the so-called inflated tetrahedron of reality are used, something which is not the case if d2+d3 is too close to one; an interpretation of this situation is that the solution becomes less sensitive to the displacement of the control points.



---

*Source: 5932508-2018-06-21.xml*