खोजें दो त्रिकोण एक दूसरे को काटना या नहीं,

Question

को देखते हुए अंक के 2 सेट

((x1, y1, z1), (x2, y2, z2), (x3, Y3, z3)) और

((पी 1, क्यू 1, आर 1), (पी 2, क्यू 2, आर 2), (पी 3, क्यू 3, आर 3)) प्रत्येक 3 डी स्पेस में त्रिकोण बनाते हैं।

आप कैसे पता लगाएंगे कि ये त्रिभुज छेड़छाड़ करते हैं या नहीं?

इस समस्या का एक स्पष्ट समाधान प्रत्येक त्रिभुज द्वारा बनाए गए विमान के समीकरण को ढूंढना है। यदि विमान समानांतर हैं, तो वे अंतर नहीं करते हैं।

अन्यथा, इन विमानों के सामान्य वैक्टरों का उपयोग करके इन विमानों के चौराहे से गठित लाइन के समीकरण को ढूंढें।

अब, यदि यह रेखा त्रिकोणीय क्षेत्रों दोनों में निहित है, तो इन दो त्रिकोणों का अंतर होता है, अन्यथा नहीं।

trianglesIntersect(Triangle T1, Triangle T2) 
{ 
    if(trianglesOnParallelPlanes(T1, T2)) 
    { 
     return false 
    } 
    Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2)) 
    if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1)) 
    { 
     return true 
    } 
    return false 
} 

यह देखते हुए कि मुझे उपर्युक्त कार्यों को कैसे लिखना है, त्रिकोणों के अन्य कार्यान्वयन क्या मुझे समझना चाहिए?

क्या इस समस्या को हल करने वाले तेज़ एल्गोरिदम हैं?

Answer 1

जाएँ this table of geometric intersection algorithmsrealtimerendering.com के सौजन्य से, त्रिकोण/त्रिकोण चौराहों के लिए प्रवेश को देखें, और क्रिस्टर Ericson, Real-Time Collision Detection, पेज 172, उदाहरण के लिए संदर्भ का पालन करें, (किताब जो मैं अत्यधिक की सलाह देते हैं।)

बुनियादी विचार सरल है। यदि दो त्रिभुज छेड़छाड़ करते हैं, तो एक त्रिकोण के दोनों किनारों को दूसरे (नीचे दिए गए आरेख में बाएं कॉन्फ़िगरेशन) को अलग करता है, या प्रत्येक त्रिभुज का एक किनारा दूसरे (दाएं कॉन्फ़िगरेशन) को छेड़छाड़ करता है।

तो छह रेखा खंड-त्रिकोण चौराहे परीक्षण करने और यदि इन विन्यास की या तो पाया जाता है देखते हैं।

अब, आप पूछते हैं, आप लाइन सेगमेंट/त्रिकोण चौराहे परीक्षण कैसे करते हैं? अच्छा, यह आसान है। this table of geometric intersection algorithms पर जाएं, लाइन सेगमेंट (रे)/त्रिकोण चौराहे के लिए प्रविष्टि देखें, और संदर्भों का पालन करें ...

(यह उल्लेख करना महत्वपूर्ण है कि ऊपर उल्लिखित सरल परीक्षण coplanar त्रिकोण सही ढंग से संभाल नहीं करता है। कई अनुप्रयोगों के लिए इससे कोई फर्क नहीं पड़ता: उदाहरण के लिए, त्रिभुज के मेष के बीच टकराव का पता लगाने पर, कोपलानर के मामले संदिग्ध होते हैं, इससे कोई फर्क नहीं पड़ता कि कौन सा परिणाम लौटाया गया है। लेकिन यदि आपका आवेदन अपवादों में से एक है, तो आपको इसकी जांच करनी होगी एक विशेष मामले के रूप में, या पर Ericson में कुछ अन्य तरीकों के लिए separating-axis method पढ़ते हैं, उदाहरण के लिए, या टॉमस Möller के interval overlap method।)