優化函數來計算線上點的投影？

Question

考慮以下問題：

我的問題是：如何優化以下獨立功能：

// Computation of the coordinates of P 
inline std::array<double, 3> P(const std::array<double, 3>& A, 
           const std::array<double, 3>& B, 
           const std::array<double, 3>& M) 
{ 
    // The most inefficient version in the world (to be verified) 
    std::array<double, 3> AB = {B[0]-A[0], B[1]-A[1], B[2]-A[2]}; 
    std::array<double, 3> AM = {M[0]-A[0], M[1]-A[1], M[2]-A[2]}; 
    double norm = std::sqrt(AB[0]*AB[0]+AB[1]*AB[1]+AB[2]*AB[2]); 
    double dot = AB[0]*AM[0]+AB[1]*AM[1]+AB[2]*AM[2]; 
    double d1 = dot/norm; 
    std::array<double, 3> AP = {AB[0]/d1, AB[1]/d1, AB[2]/d1}; 
    std::array<double, 3> P = {AP[0]-A[0], AP[1]-A[1], AP[2]-A[2]}; 
    return P; 
} 

// Computation of the distance d0 
inline double d0(const std::array<double, 3>& A, 
       const std::array<double, 3>& B, 
       const std::array<double, 3>& M) 
{ 
    // The most inefficient version in the world (to be verified) 
    std::array<double, 3> AB = {B[0]-A[0], B[1]-A[1], B[2]-A[2]}; 
    std::array<double, 3> AM = {M[0]-A[0], M[1]-A[1], M[2]-A[2]}; 
    double norm = std::sqrt(AB[0]*AB[0]+AB[1]*AB[1]+AB[2]*AB[2]); 
    double dot = AB[0]*AM[0]+AB[1]*AM[1]+AB[2]*AM[2]; 
    double d1 = dot/norm; 
    std::array<double, 3> AP = {AB[0]/d1, AB[1]/d1, AB[2]/d1}; 
    std::array<double, 3> P = {AP[0]-A[0], AP[1]-A[1], AP[2]-A[2]}; 
    std::array<double, 3> MP = {P[0]-M[0], P[1]-M[1], P[2]-M[2]}; 
    double d0 = std::sqrt(MP[0]*MP[0]+MP[1]*MP[1]+MP[2]*MP[2]); 
    return d0; 
} 

// Computation of the distance d1 
inline double d1(const std::array<double, 3>& A, 
       const std::array<double, 3>& B, 
       const std::array<double, 3>& M) 
{ 
    // The most inefficient version in the world (to be verified) 
    std::array<double, 3> AB = {B[0]-A[0], B[1]-A[1], B[2]-A[2]}; 
    std::array<double, 3> AM = {M[0]-A[0], M[1]-A[1], M[2]-A[2]}; 
    double norm = std::sqrt(AB[0]*AB[0]+AB[1]*AB[1]+AB[2]*AB[2]); 
    double dot = AB[0]*AM[0]+AB[1]*AM[1]+AB[2]*AM[2]; 
    double d1 = dot/norm; 
} 

// Computation of the distance d2 
inline double d2(const std::array<double, 3>& A, 
       const std::array<double, 3>& B, 
       const std::array<double, 3>& M) 
{ 
    // The most inefficient version in the world (to be verified) 
    std::array<double, 3> AB = {B[0]-A[0], B[1]-A[1], B[2]-A[2]}; 
    std::array<double, 3> AM = {M[0]-A[0], M[1]-A[1], M[2]-A[2]}; 
    double norm = std::sqrt(AB[0]*AB[0]+AB[1]*AB[1]+AB[2]*AB[2]); 
    double dot = AB[0]*AM[0]+AB[1]*AM[1]+AB[2]*AM[2]; 
    double d1 = dot/norm; 
    double d2 = norm-d1; 
    return d2; 
} 

讓每個功能將盡可能地儘可能多的優化？ （我會執行這些功能十億次）。

Answer 1

但從算法來看，你不能使用SQRT通話

的僞代碼從這裏 http://www.euclideanspace.com/maths/geometry/elements/line/projections/

// projection of vector v1 onto v2 
inline vector3 projection(const vector3& v1, const vector3& v2) { 
    float v2_ls = v2.len_squared(); 
     return v2 * (dot(v2, v1)/v2_ls); 

} 

其中圓點（）是兩個點積計算矢量投影到另一個向量向量和len_squared是向量與自我的點積。

注意：儘可能在主循環之前預先計算v2_ls的逆。

Answer 2

在一次性計算中計算所有請求的數量可能會更好。

讓P = A + t . AB給出位置P的向量方程。表示MP和AB是正交的：MP . AB = 0 = (MA + t . AB) . AB，其產生t= - (MA . AB)/AB^2和P。

t是比率AP/AB，因此d1 = t . |AB|。同樣，d2 = (1 - t) . |AB|。 d0得自畢達哥拉斯，d0^2 = MA^2 - d1^2，或通過直接計算|MP|。

會計：計算MA（3 ADD），AB（3 ADD），AB^2（2加，3 MUL），MA.AB（2加，3 MUL），t（1 DIV），P（3添加，3 MUL ），|AB|（1 sqrt），d1（1 mul），d2（1 add，1 mul），MA^2（2 add，3 mul），d0（1 add，1 mul，1 sqrt）。

共17個添加，15 mul，1 div，2 sqrt。

Answer 3

如果你想移植的代碼，所以沒有使用處理器的具體特點，我建議如下： -

1）正如我在評論中提及上面，創建一個三維矢量類，它只會令它容易得多寫代碼（優化發展時間）

2）創建一個使用懶評價拿到P，D0和D1的交集類，像這樣： -

class Intersection 
{ 
public: 
    Intersection (A, B, M) { store A, B, M; constants_calculated = false } 
    Point GetP() { CalculateConstants; Return P; } 
    double GetD0() { CalculateConstants; Return D0; } 
    double GetD1() { CalculateConstants; Return D1; } 
private: 
    CalculateConstants() 
    { 
    if (!constants_calculate) 
    { 
     calculate and store common expressions required for P, d0 and d1 
     constants_calculate = true 
    } 
    } 

3）不要噸稱它十億次。不做事情無限快。爲什麼需要頻繁地調用它？有沒有辦法用更少的電話來查找P，d0和d1來做同樣的事情？

如果您可以使用處理器特定功能，那麼您可以考慮使用SIMD等操作，但這可能需要將精度從雙精度值降低到浮點值。