रे-बॉक्स छेड़छाड़ सिद्धांत

Question

मैं एक किरण और एक बॉक्स के बीच चौराहे बिंदु निर्धारित करना चाहता हूं। बॉक्स को इसके न्यूनतम 3 डी समन्वय और अधिकतम 3 डी समन्वय द्वारा परिभाषित किया गया है और किरण को इसकी उत्पत्ति और जिस दिशा से इंगित करता है, उसके द्वारा परिभाषित किया जाता है।

वर्तमान में, मैं बॉक्स के प्रत्येक चेहरे के लिए एक विमान बना रहा हूं और मैं विमान के साथ किरण को छेड़छाड़ कर रहा हूं। यदि किरण विमान को छेड़छाड़ करती है, तो मैं जांच करता हूं कि चौराहे बिंदु वास्तव में बॉक्स की सतह पर है या नहीं। यदि ऐसा है, तो मैं जांचता हूं कि यह इस किरण के लिए निकटतम चौराहे है या मैं निकटतम चौराहे देता हूं।

तरह से मैं यह देखना होगा कि विमान-चौराहा बिंदु बॉक्स सतह पर ही है

bool PointOnBoxFace(R3Point point, R3Point corner1, R3Point corner2) 
{ 
    double min_x = min(corner1.X(), corner2.X()); 
    double max_x = max(corner1.X(), corner2.X()); 
    double min_y = min(corner1.Y(), corner2.Y()); 
    double max_y = max(corner1.Y(), corner2.Y()); 
    double min_z = min(corner1.Z(), corner2.Z()); 
    double max_z = max(corner1.Z(), corner2.Z()); 
    if(point.X() >= min_x && point.X() <= max_x && 
    point.Y() >= min_y && point.Y() <= max_y && 
    point.Z() >= min_z && point.Z() <= max_z) 
    return true; 

    return false; 
} 

जहां corner1 कि बॉक्स चेहरे के लिए आयत के एक कोने और corner2 है दूसरे कोने है एक समारोह के माध्यम से है। मेरा कार्यान्वयन ज्यादातर समय काम करता है लेकिन कभी-कभी यह मुझे गलत चौराहे देता है। कृपया छवि देखते हैं:

छवि किरणों कैमरे की आंख से आ रहा है और बॉक्स सतह से टकराने को दर्शाता है। अन्य किरणें बॉक्स की सतह के लिए मानक हैं। यह देखा जा सकता है कि विशेष रूप से एक किरण (यह वास्तव में सामान्य है जो देखा जाता है) बॉक्स के "पीछे" से बाहर आता है, जबकि सामान्य बॉक्स के शीर्ष से ऊपर आना चाहिए। यह अजीब लगता है क्योंकि कई अन्य किरणें हैं जो बॉक्स के शीर्ष पर सही ढंग से हिट करती हैं।

मैं सोच रहा था कि जिस तरह से मैं जांच रहा हूं कि बॉक्स पर छेड़छाड़ बिंदु सही है या नहीं, तो मुझे कुछ अन्य एल्गोरिदम का उपयोग करना चाहिए।

धन्यवाद।

Answer 1

ईपीएसलॉन द्वारा बढ़ती चीजें वास्तव में ऐसा करने का एक शानदार तरीका नहीं है, क्योंकि अब आपके पास अपने बॉक्स के किनारे पर आकार ईपीएसलॉन की सीमा है जिसके माध्यम से किरणें गुजर सकती हैं। तो आप त्रुटियों के अजीब सेट (अपेक्षाकृत आम) से छुटकारा पायेंगे, और अजीब त्रुटियों के दूसरे (दुर्लभ) सेट के साथ समाप्त हो जाएंगे।

मुझे लगता है कि आप पहले से ही कल्पना कर रहे हैं कि आपकी किरण अपने वेक्टर के साथ कुछ गति से यात्रा कर रही है और प्रत्येक विमान के साथ छेड़छाड़ का समय पाती है। इसलिए, उदाहरण के लिए, यदि आप विमान को x=x0 पर घुमा रहे हैं, और आपकी किरण (rx,ry,rz)(0,0,0) से दिशा में जा रही है, तो चौराहे का समय t = x0/rx है। यदि t नकारात्मक है, तो इसे अनदेखा करें - आप दूसरी तरफ जा रहे हैं। यदि t शून्य है, तो आपको यह तय करना होगा कि उस विशेष मामले को कैसे संभालना है - यदि आप पहले से ही विमान में हैं, तो क्या आप इसे उछालते हैं, या इसके माध्यम से गुजरते हैं? आप एक विशेष मामले के रूप में rx==0 को भी संभाल सकते हैं (ताकि आप बॉक्स के किनारे पर हिट कर सकें)।

वैसे भी, अब आपके पास उस समन्वय हैं जहां आपने उस विमान को मारा था: वे (t*rx , t*ry , t*rz) हैं। अब आप पढ़ सकते हैं कि t*ry और t*rz आयताकार के भीतर हैं, जिसमें वे होना चाहिए (यानी उन अक्षों के साथ घन के लिए न्यूनतम और अधिकतम के बीच)। आप एक्स समन्वय का परीक्षण नहीं करते हैं क्योंकि आप पहले ही जानते हैं कि आपने इसे मारा है, फिर आपको यह तय करना होगा कि एक विशेष मामले के रूप में मारने वाले कोनों को कैसे संभालना है या नहीं। इसके अलावा, अब आप समय के साथ विभिन्न सतहों के साथ अपने टकराव का ऑर्डर कर सकते हैं और अपने टकराव बिंदु के रूप में पहले को चुन सकते हैं।

यह आपको मनमाने ढंग से ईपीएसलॉन-कारकों का उपयोग किए बिना गणना करने की अनुमति देता है, भले ही आपकी किरण फ़्लोटिंग पॉइंट अंकगणित के साथ सटीकता के लिए आपके घन को छेड़छाड़ करे। परीक्षण के लिए एक है कि क्या आप यह सोचते हैं आप x मारा yz भीतर मारा, और xz और xy यह सोचते हैं कि आप y और z क्रमशः हिट के लिए इसी लोगों:

तो तुम सिर्फ तीन कार्यों एक आप पहले से ही मिल गया है की तरह की जरूरत है।

---

संपादित करें:

#define X_FACE 0 
#define Y_FACE 1 
#define Z_FACE 2 
#define MAX_FACE 4 

// true if we hit a box face, false otherwise 
bool hit_face(double uhit,double vhit, 
       double umin,double umax,double vmin,double vmax) 
{ 
    return (umin <= uhit && uhit <= umax && vmin <= vhit && vhit <= vmax); 
} 

// 0.0 if we missed, the time of impact otherwise 
double hit_box(double rx,double ry, double rz, 
       double min_x,double min_y,double min_z, 
       double max_x,double max_y,double max_z) 
{ 
    double times[6]; 
    bool hits[6]; 
    int faces[6]; 
    double t; 
    if (rx==0) { times[0] = times[1] = 0.0; } 
    else { 
    t = min_x/rx; 
    times[0] = t; faces[0] = X_FACE; 
    hits[0] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z); 
    t = max_x/rx; 
    times[1] = t; faces[1] = X_FACE + MAX_FACE; 
    hits[1] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z); 
    } 
    if (ry==0) { times[2] = times[3] = 0.0; } 
    else { 
    t = min_y/ry; 
    times[2] = t; faces[2] = Y_FACE; 
    hits[2] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z); 
    t = max_y/ry; 
    times[3] = t; faces[3] = Y_FACE + MAX_FACE; 
    hits[3] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z); 
    } 
    if (rz==0) { times[4] = times[5] = 0.0; } 
    else { 
    t = min_z/rz; 
    times[4] = t; faces[4] = Z_FACE; 
    hits[4] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y); 
    t = max_z/rz; 
    times[5] = t; faces[5] = Z_FACE + MAX_FACE; 
    hits[5] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y); 
    } 
    int first = 6; 
    t = 0.0; 
    for (int i=0 ; i<6 ; i++) { 
    if (times[i] > 0.0 && (times[i]<t || t==0.0)) { 
     first = i; 
     t = times[i]; 
    } 
    } 
    if (first>5) return 0.0; // Found nothing 
    else return times[first]; // Probably want hits[first] and faces[first] also.... 
} 

(मैं सिर्फ यह आपके द्वारा लिखा गया है, यह संकलन नहीं किया, इसलिए कीड़े से सावधान: कोड (verbosely) दिखाने के प्रत्येक अक्ष के लिए अलग तरह से परीक्षण करने के लिए कैसे करने के लिए जोड़ा।) (संपादित करें: सिर्फ एक i को सही ->first)

वैसे भी, मुद्दा यह है कि आप तीन दिशाओं अलग से करते हैं, और परीक्षण देखने के लिए प्रभाव में सही बॉक्स के भीतर हुई है या नहीं है (यू, वी)। निर्देशांक, जहां (यू, वी) या तो हैं (एक्स , वाई), (एक्स, जेड), या (वाई, जेड) आप जिस विमान पर हिट करते हैं उसके आधार पर।

Answer 2

कोड ठीक दिखता है। इस विशेष किरण को खोजने और इसे डीबग करने का प्रयास करें।

Answer 3

संपादित करें: इस उत्तर को अनदेखा करें (नीचे दी गई टिप्पणियां देखें जहां मैं काफी हद तक अपने तरीकों की त्रुटि दिखा रहा हूं)।

आप परीक्षण कर रहे हैं कि बिंदु मात्रा के अंदर है, लेकिन बिंदु उस मात्रा की परिधि पर है, इसलिए आप पाते हैं कि यह मात्रा के बाहर एक "infinitesimal" दूरी है। कुछ छोटे एप्सिलॉन से बॉक्स से बढ़ प्रयास करें, जैसे:

double epsilon = 1e-10; // Depends the scale of things in your code. 
double min_x = min(corner1.X(), corner2.X()) - epsilon; 
double max_x = max(corner1.X(), corner2.X()) + epsilon; 
double min_y = min(corner1.Y(), corner2.Y()) - epsilon; 
... 

तकनीकी तौर पर, लगभग बराबर संख्याओं की तुलना करने का सही तरीका ints के लिए थोड़ा प्रयास अभ्यावेदन कास्ट करने के लिए और ऑफसेट कुछ छोटे के लिए पूर्णांकों की तुलना, जैसे, सी में है :

#define EPSILON 10 /* some small int; tune to suit */ 
int almostequal(double a, double b) { 
    return llabs(*(long long*)&a - *(long long*)&b) < EPSILON; 
} 

बेशक

, इस सी # में इतना आसान नहीं है, लेकिन शायद असुरक्षित अर्थ विज्ञान एक ही प्रभाव को प्राप्त कर सकते हैं। (@Novox को उनकी टिप्पणियों के लिए धन्यवाद, जो मुझे इस तकनीक को विस्तार से समझाते हुए page पर ले जाता है।)

Answer 4

क्या यह हो सकता है कि किरण बिल्कुल बॉक्स के किनारे से गुजरती है? फ़्लोटिंग पॉइंट राउंडऑफ त्रुटियों से इसे दाएं और पीछे के चेहरे दोनों से याद किया जा सकता है।

Answer 5

PointOnBoxFace त्रि-आयामी के बजाय एक द्वि-आयामी जांच होना चाहिए। उदाहरण के लिए, यदि आप z = z_min विमान के विरुद्ध परीक्षण कर रहे हैं, तो आपको केवल x और y की तुलना अपनी संबंधित सीमाओं से करना चाहिए। आप पहले ही पता लगा चुके हैं कि z समन्वय सही है। फ्लोटिंग पॉइंट परिशुद्धता आपको तीसरे समन्वय के "पुनः जांच" के रूप में आपको ऊपर ले जाने की संभावना है।

उदाहरण के लिए, यदि z_min 1.0 है, तो आप पहले उस विमान के खिलाफ परीक्षण करते हैं। आपको एक चौराहे बिंदु (x, y, 0.9 99 99 99 99) मिलता है। अब, भले ही x और y सीमाओं के भीतर हैं, z बिल्कुल सही नहीं है।