試圖優化線條與圓柱體相交

我一直在努力研究線段 - 圓筒交叉口例程，我的大腦已經融化。試圖優化線條與圓柱體相交

/// Line segment VS <cylinder> 
// - cylinder (A, B, r) (start point, end point, radius) 
// - line has starting point (x0, y0, z0) and ending point (x0+ux, y0+uy, z0+uz) ((ux, uy, uz) is "direction") 
// => start = (x0, y0, z0) 
// dir = (ux, uy, uz) 
// A 
// B 
// r 
// optimize? (= don't care for t > 1) 
// <= t = "time" of intersection 
// norm = surface normal of intersection point 
void CollisionExecuter::cylinderVSline(const Ogre::Vector3& start, const Ogre::Vector3& dir, const Ogre::Vector3& A, const Ogre::Vector3& B, const double r, 
      const bool optimize, double& t, Ogre::Vector3& normal) { 
    t = NaN; 

    // Solution : http://www.gamedev.net/community/forums/topic.asp?topic_id=467789 
    double cxmin, cymin, czmin, cxmax, cymax, czmax; 
    if (A.z < B.z) { czmin = A.z - r; czmax = B.z + r; } else { czmin = B.z - r; czmax = A.z + r; } 
    if (A.y < B.y) { cymin = A.y - r; cymax = B.y + r; } else { cymin = B.y - r; cymax = A.y + r; } 
    if (A.x < B.x) { cxmin = A.x - r; cxmax = B.x + r; } else { cxmin = B.x - r; cxmax = A.x + r; } 
    if (optimize) { 
    if (start.z >= czmax && (start.z + dir.z) > czmax) return; 
    if (start.z <= czmin && (start.z + dir.z) < czmin) return; 
    if (start.y >= cymax && (start.y + dir.y) > cymax) return; 
    if (start.y <= cymin && (start.y + dir.y) < cymin) return; 
    if (start.x >= cxmax && (start.x + dir.x) > cxmax) return; 
    if (start.x <= cxmin && (start.x + dir.x) < cxmin) return; 
    } 

    Ogre::Vector3 AB = B - A; 
    Ogre::Vector3 AO = start - A; 
    Ogre::Vector3 AOxAB = AO.crossProduct(AB); 
    Ogre::Vector3 VxAB = dir.crossProduct(AB); 
    double ab2 = AB.dotProduct(AB); 
    double a = VxAB.dotProduct(VxAB); 
    double b = 2 * VxAB.dotProduct(AOxAB); 
    double c = AOxAB.dotProduct(AOxAB) - (r*r * ab2); 
    double d = b * b - 4 * a * c; 
    if (d < 0) return; 
    double time = (-b - sqrt(d))/(2 * a); 
    if (time < 0) return; 

    Ogre::Vector3 intersection = start + dir * time;  /// intersection point 
    Ogre::Vector3 projection = A + (AB.dotProduct(intersection - A)/ab2) * AB; /// intersection projected onto cylinder axis 
    if ((projection - A).length() + (B - projection).length() > AB.length()) return; /// THIS IS THE SLOW SAFE WAY 
    //if (projection.z > czmax - r || projection.z < czmin + r || 
    // projection.y > cymax - r || projection.y < cymin + r || 
    // projection.x > cxmax - r || projection.x < cxmin + r) return; /// THIS IS THE FASTER BUGGY WAY 

    normal = (intersection - projection); 
    normal.normalise(); 
    t = time; /// at last 
}

我曾想過這樣的方式來加速發現交點投影是否位於圓柱體長度內。然而，它不起作用，我無法真正瞭解它，因爲它看起來很合邏輯：如果投影點的x，y或z座標不在圓柱體的極限範圍內，則應該在外部考慮。看來雖然這在實踐中並不奏效。

任何幫助將不勝感激！

乾杯，

比爾Kotsias

編輯：看來，問題上升與邊界的情況下，即當氣缸是平行於軸線的一個。舍入誤差進入公式，「優化」停止正常工作。

if (projection.z > czmax - r + 0.001 || projection.z < czmin + r - 0.001 || ... etc...

來源

2010-11-02 Bill Kotsias

氣缸是圓形，右：

也許，如果邏輯爲正確，問題將通過插入有點像寬容走嗎？您可以轉換座標，使圓柱的中心線作爲Z軸。然後你有一個與圓相交的2D問題。交點將根據沿線長度從0到1的參數表示，因此您可以計算它們在該座標系中的位置並與圓柱體的頂部和底部進行比較。

你應該能夠以封閉的形式做到這一切。沒有容差。當然，你會得到奇點和想象的解決方案。你似乎想到了這一切，所以我想我不確定問題是什麼。

來源

2010-11-02 16:14:47

邁克的回答很好。對於任何棘手的形狀，你最好找到轉換矩陣T，它將它映射成一個不錯的直立版本，在這種情況下，半徑爲1的直徑圓柱體將很好地完成這項工作。在這個新空間中找出你的新線路，執行計算，轉換回來。然而，如果你正在尋找優化（聽起來像你），那麼你可能會做負載。

例如，您可以計算兩條線之間的最短距離 - 可能使用點積規則 - 想象一個線程連接兩條線。那麼如果這個線程是所有可能線程中最短的線程，那麼它將垂直於兩條線，所以Thread.LineA = Thread.LineB = 0

如果最短距離大於圓柱半徑，一個小姐。

你可以使用x，y，z定義圓柱體的軌跡，並將整個事物作爲一些可怕的二次方程式進行排列，並通過首先計算判別式進行優化，如果是負數則返回無打擊。

要定義軌跡，取任意點P =（x，y，z）。將它垂直放置在圓柱體的中心線上，並觀察其大小的平方。如果這等於該點所在的R^2。

然後你把你的線{s = U + lamda * V}放入那個混亂中，最後你會在lamda中得到一些屁股醜陋的二次方。但是這可能比擺弄矩陣要快，除非你可以讓硬件做到這一點（我猜OpenGL有一些功能可以讓硬件做到這一點）。

這一切都取決於你想要多少優化;個人而言，除非有充分理由不這樣做，否則我會和邁克的答案一起去。

PS如果你解釋你使用的技術而不是僅僅傾銷代碼，你可能會得到更多的幫助，讓讀者去弄清楚你在做什麼。

來源

2010-11-03 07:41:45

這是我使用的東西，它可以幫助：

bool d3RayCylinderIntersection(const DCylinder &cylinder,const DVector3 &org,const DVector3 &dir,float &lambda,DVector3 &normal,DVector3 &newPosition) 
// Ray and cylinder intersection 
// If hit, returns true and the intersection point in 'newPosition' with a normal and distance along 
// the ray ('lambda') 
{ 
    DVector3 RC; 
    float d; 
    float t,s; 
    DVector3 n,D,O; 
    float ln; 
    float in,out; 

    RC=org; RC.Subtract(&cylinder.position); 
    n.Cross(&dir,&cylinder.axis); 

    ln=n.Length(); 

    // Parallel? (?) 
    if((ln<D3_EPSILON)&&(ln>-D3_EPSILON)) 
    return false; 

    n.Normalize(); 

    d=fabs(RC.Dot(n)); 

    if (d<=cylinder.radius) 
    { 
    O.Cross(&RC,&cylinder.axis); 
    //TVector::cross(RC,cylinder._Axis,O); 
    t=-O.Dot(n)/ln; 
    //TVector::cross(n,cylinder._Axis,O); 
    O.Cross(&n,&cylinder.axis); 
    O.Normalize(); 
    s=fabs(sqrtf(cylinder.radius*cylinder.radius-d*d)/dir.Dot(O)); 

    in=t-s; 
    out=t+s; 

    if (in<-D3_EPSILON) 
    { 
     if(out<-D3_EPSILON) 
     return false; 
     else lambda=out; 
    } else if(out<-D3_EPSILON) 
    { 
     lambda=in; 
    } else if(in<out) 
    { 
     lambda=in; 
    } else 
    { 
     lambda=out; 
    } 

    // Calculate intersection point 
    newPosition=org; 
    newPosition.x+=dir.x*lambda; 
    newPosition.y+=dir.y*lambda; 
    newPosition.z+=dir.z*lambda; 
    DVector3 HB; 
    HB=newPosition; 
    HB.Subtract(&cylinder.position); 

    float scale=HB.Dot(&cylinder.axis); 
    normal.x=HB.x-cylinder.axis.x*scale; 
    normal.y=HB.y-cylinder.axis.y*scale; 
    normal.z=HB.z-cylinder.axis.z*scale; 
    normal.Normalize(); 
    return true; 
    } 

    return false; 
}

來源

2012-03-23 10:30:20

你有沒有想過這樣說？

圓柱體本質上是一個「粗」線段，因此一種方法是找到線段（圓柱體中心線）到線段（您正在測試交點的線段）上的最近點。

從那裏檢查此最近點與其他線段之間的距離，並將其與半徑進行比較。

在這一點上，你有一個「藥丸vs線段」測試，但你可以做一些飛機測試來「切斷」藥丸上的瓶蓋來製作一個圓柱體。

從臀部拍攝有點雖然所以希望它有幫助（：

來源

2013-09-25 21:32:38

試圖優化線條與圓柱體相交

回答

相關問題