تخزين فعال ل OCTREE متفرق؟

Question

هل يمكن لأي شخص أن يقترح أداة بسرعة ، وسيلة فعالة لتخزينها والوصول إلى Octree Sparse؟

يفضل أن يتم تنفيذ شيء يمكن تنفيذه بسهولة في HLSL.(أنا أعمل تطبيق Raycasting / Voxel)

في هذه الحالة، يمكن إدخال الشجرة، لذلك أنا مهتم في الغالب بالحجم ووقت البحث.

تحديث

لأي شخص يتطلع إلى القيام بذلك، قد يكون هناك حل أكثر كفاءة هو تخزين العقد كعقد octree الخطي الذي تم إنشاؤه مع شجرة منحنى Z- ترتيب / مورتون.يؤدي القيام بذلك إلى القضاء على تخزين العقد الداخلي، ولكن قد يتطلب الرجوع عبر مجموعة الشجرة الخطية مع "نسيج البيانات" الثاني يحتوي على معلومات حول Voxel الفردية.

Answer 1

أنا لست من ذوي الخبرة للغاية في HLSL، لذلك لست متأكدا من أن هذا سيلبي احتياجاتك، إليك أفكاري. اسمحوا لي أن أعرف ما إذا كان هناك شيء هنا ليس سانا لاحتياجاتك - أود مناقشة ذلك، ربما أستطيع أن أتعلم شيئا نفسي.

1. يمكن أن توجد كل عقدة في OCTREE كمكون Vector3، حيث يمثل مكون (x، y، z) نقطة المركزية للعقدة. يمكن استخدام مكون W كحقل إشارات. أ. يمكن أن يشير حقل Flags W-Flags إلى أن العقد التي تتبعها تنتج العقدة الحالية. هذا سيتطلب 8 بت من القيمة.
2. يمكن تخزين كل كيان مخزوم في OCTREE كمربع محيط، حيث يمكن أن يكون R، G، B أبعاد المربع المحيط، ويمكن استخدام W لأي شيء.
3. حدد ناقلات خاص يشير إلى أن قائمة كائن يتبع. على سبيل المثال، إذا كانت (W + Z) هي بعض القيمة السحرية. يمكن لبعض Func (x، y)، أن يكون عدد الكائنات التالية. أو أيا كان يعمل. أ. يحتمل أن يتبع كل عقدة هذا المتجه الخاص هذا، مما يشير إلى وجود كائنات مخزنة في العقدة. ناقلات X التالية كلها فقط معرفات كائن أو شيء من هذا القبيل. ب. بدلا من ذلك، يمكنك الحصول على عقدة واحدة تحدد فقط قائمة كائنات في الذاكرة. مرة أخرى، لست متأكدا ما تحتاجه هنا أو القيود على كيفية الوصول إلى الكائنات.

لذلك، أولا، قم ببناء OCTREE وأشياء مع الأشياء الخاصة بك. ثم، فقط امشي OCTREE، إخراج المتجهات إلى المخزن المؤقت للذاكرة.

أعتقد أن نسيج 512x512 يمكن أن يحمل مستويات OCTREE 5 معبأة بالكامل (32،768 العقد)، كل منها يحتوي على 8 كائنات. أو، octree معبأة بالكامل من 4 مستويات مع 64 كائنات لكل منهما.

Answer 2

هناك مقال كبير حول octrees متفرق يركز على GPUS: كفاءة Voxel Voxeloctrees - التحليل والملحقات والتنفيذ