मैं एक व्यक्तिगत शिक्षण परियोजना (Enlight) के रूप में एक 3 डी रेट्रेटर लिख रहा हूं और एक किरण और वस्तुओं के दृश्य के बीच छेड़छाड़ परीक्षण करने से संबंधित एक दिलचस्प समस्या में भाग गया हूं।कुशल रेट्रैसिंग के लिए डेटा संरचना/दृष्टिकोण
स्थिति है:
- मैं पुरातन कि रे (क्षेत्रों, बक्से, विमानों, आदि) और समूहों उसके साथ एक दूसरे को काटना कर सकते हैं की एक संख्या है। सामूहिक रूप से मैं इन दृश्य वस्तुओं को बुला रहा हूँ।
- मैं
Transformऑब्जेक्ट में उन्हें लपेटकर मनमानी एफ़िन ट्रांसफॉर्मेशन के साथ ऑब्जेक्ट प्राइमेटिव्स को देखने में सक्षम होना चाहता हूं (महत्वपूर्ण रूप से, यह दृश्य में विभिन्न स्थितियों में उपयोग किए जाने वाले समान आदिम के कई उदाहरणों को सक्षम करेगा क्योंकि प्राइमेटिव हैं अपरिवर्तनीय) - दृश्य वस्तुओं बाउंडिंग मात्रा पदानुक्रम में संग्रहित किया जा सकता (यानी मैं स्थानिक विभाजन कर रहा हूँ)
- मेरे चौराहे परीक्षण
Rayवस्तुओं है कि एक आंशिक रे खंड प्रतिनिधित्व करते हैं के साथ काम (वेक्टर, सामान्यीकृत दिशा वेक्टर शुरू करते हैं, दूरी शुरू , अंत दूरी)
समस्या यह है कि जब एक किरण एक ट्रांसफॉर्म ऑब्जेक्ट के बाउंडिंग बॉक्स को हिट करती है, तो ऐसा लगता है कि इसमें परिवर्तित ट्रांसफॉर्म किए गए प्राइमेटिव्स के साथ एक चौराहे परीक्षण करने का एकमात्र तरीका है, Ray को परिवर्तित समन्वय स्थान में बदलना है। यह काफी आसान है, लेकिन फिर यदि किरण किसी भी रूपांतरित वस्तुओं को हिट नहीं करती है तो मुझे ट्रेस जारी रखने के लिए मूल Ray पर वापस गिरने की आवश्यकता है। चूंकि ट्रांसफॉर्म को घोंसला दिया जा सकता है, इसका मतलब है कि मुझे प्रत्येक छेड़छाड़ के निशान के लिए Ray एस का पूरा ढेर बनाए रखना है।
यह निश्चित रूप से पूरे आवेदन के आंतरिक पाश और प्राथमिक प्रदर्शन बाधा के भीतर है। इसे एक सेकंड में लाखों बार बुलाया जाएगा, इसलिए मैं जटिलता को कम करने/अनावश्यक स्मृति आवंटन से बचने के लिए उत्सुक हूं।
क्या नया Ray एस आवंटित करने से बचने के लिए एक चालाक तरीका है/Ray स्टैक रखें?
या क्या यह पूरी तरह से करने का एक चालाक तरीका है?
मुझे यकीन नहीं है कि यह स्मृति आवंटन से तेज़ होगा, लेकिन आप एक कुशल ट्रांसफॉर्म इनवर्जन एल्गोरिदम के साथ आने का प्रयास कर सकते हैं और फिर मौजूदा ऑब्जेक्ट से बैक अप करते समय मौजूदा रे को उलटा परिवर्तन के साथ गुणा कर सकते हैं। –
@Ivan - दिलचस्प विचार। मुझे लगता है कि यह मामूली तेजी से हो सकता है, हालांकि मैं संख्यात्मक परिशुद्धता समस्याओं को जोड़कर चिंतित हूं ..... – mikera
आप प्रत्येक ऑब्जेक्ट के साथ एक रूपांतरण और उलटा परिवर्तन (आईई एक मैट्रिक्स ऑब्जेक्ट) की गणना और कैश कर सकते हैं (साथ ही साथ समूह में वस्तुओं) जो वैश्विक फ्रेम में और से परिवर्तित हो जाएगा। इस तरह आपको घोंसले पदानुक्रम की आवश्यकता नहीं है क्योंकि आप प्रत्येक वस्तु पर सीधे हिट टेस्ट कर सकते हैं। अर्थात। वस्तु को फ्रेम के रूप में संशोधित करें, फिर वैश्विक फ्रेम में हिट पॉइंट प्राप्त करने के लिए वापस बदलें। मैं इसे अपने ट्रेसर में करता हूं: http://github.com/danieljfarrell/pvtrace –