درخت هشت‌تایی

چپ: تقسیم بازگشتی یک مکعب به اکتان. راست: درخت هشت‌تایی معادل.

درخت هشت‌تایی (به انگلیسی: Octree) یک داده‌ساختار درخت است که در آن هر گره داخلی دقیقاً هشت فرزند دارد. درخت‌های هشت‌تایی اغلب برای افراز کردن یک فضای سه‌بعدی از طریق تقسیم بازگشتی آن فضا به هشت قسمت مساوی استفاده می‌شوند. درخت‌های هشت‌تایی در واقع معادل چاردرخت در حالت سه بعدی اند. اسم این درخت از دو کلمه انگلیسی oct و tree تشکیل شده‌است، اما توجه کنید که این کلمه معمولاً به صورت octree فقط با یک حرف t نوشته می‌شود. درخت‌های هشت‌تایی غالباً در گرافیک سه‌بعدی رایانه‌ای و موتورهای بازی سه‌بعدی استفاده می‌شوند.

درخت‌های هشت‌تایی برای نمایش فضایی

هر گره در یک درخت هشت‌تایی فضا را به هشت اکتان تقسیم می‌کند. در یک درخت هشت‌تایی نقطه‌ای ناحیه‌ای، هر گره در واقع یک نقطه سه‌بعدی را نگه می‌دارد که مرکز قسمتی است که مربوط به آن گره است؛ این نقطه گوشه مشترک هر هشت فرزند گره است. در یک درخت هشت‌تایی نقطه‌ای که حول آن فضا تقسیم می‌شود به‌طور ضمنی مرکز قسمتی است که گره نمایش می‌دهد. گره ریشه از یک درخت هشت‌تایی PR می‌تواند فضای نامحدود را نشان دهد؛ در حالی که گره ریشه از یک درخت هشت‌تایی MX باید یک فضای محدود را نشان دهد که مرکزهای هر قسمت قابل تعریف باشند. توجه داشته باشید که درخت‌ هشت‌تایی با درخت کی‌دی متفاوت است. درخت‌های کی‌دی در راستای یک بعد تقسیم‌بندی انجام می‌دهند اما درخت‌های هشت‌تایی پیرامون یک نقطه (در راستای سه‌بعد) تقسیم‌بندی انجام می‌دهند. همچنین درخت‌های کی‌دی همواره دودویی‌اند که در مورد درخت‌های هشت‌تایی این گونه نیست. با به‌کارگیری جستجوی عمق اول (dfs) باید گره‌ها پیمایش شوند اما فقط سطوح مورد نیاز در نظر گرفته شوند.

تاریخچه

درخت هشت‌تایی برای گرافیک سه‌بعدی رایانه‌ای اولین بار توسط دونالر میقر در مؤسسه پلی‌تکنیک رنسلیر استفاده شد، که در گزارش سال ۱۹۸۰ با عنوان "رمزگذاری درخت‌های هشت‌تایی: یک راه جدید برای نمایش دوباره، دست‌کاری و نمایش دلخواه اشیاء سه‌بعدی به وسیلهٔ کامپیوتر" آن را شرح داد. او صاحب ثبت اختراع ۱۹۹۵ (با تاریخ اولویت ۱۹۸۴) با عنوان "تولید سریع عکس از اشیاء جامد پیچیده به وسیلهٔ رمزگذاری درخت هشت‌تایی" نیز بود.

کاربردهای رایج درخت هشت‌تایی

• گرافیک سه‌بعدی رایانه‌ای
• نمایه‌سازی فضایی
• جستجوی نزدیکترین همسایه
• تشخیص برخورد کارآمد در فضای سه‌بعدی
• نمایش سطوح پنهان
• روش سریع چند قطبی
• شبکه‌های بدون ساختار
• تحلیل اجزاء محدود
• درخت هشت‌تایی پراکنده واکسل
• تخمین حالت
• تخمین مجموعه

کاربرد در درجه‌بندی رنگ‌ها

الگوریتم درجه‌بندی رنگ در درخت هشت‌تایی توسط گرواتز و پورگاتوفر در سال ۱۹۸۸ ابداع شد. این الگوریتم داده‌های مربوط به رنگ یک تصویر را به صورت درخت هشت‌تایی درآورده و درخت را تا عمق ۹ سطح کدگذاری می‌کند. از آنجا که در سیستم رنگی آرجی‌بی سه مؤلفه رنگی وجود دارد و ۸=۳^۲ از درخت هشت‌تایی استفاده می‌شود. شماره مربوط به یک گره در سطح بالا با یک فرمول مشخص می‌شود که از پرارزش‌ترین بیت‌های مؤلفه‌های رنگی قرمز، سبز و آبی استفاده می‌کند، مثلاً 4r + 2g + b. سطح بعدی یا پایین‌تر از بیت‌های پرارزش بعدی استفاده می‌کند و به همین ترتیب جلو می‌رود. گاهی بیت‌های کم ارزش نادیده گرفته می‌شوند تا اندازه درخت کاهش یابد. این الگوریتم از لحاظ مصرف حافظه بسیار بهینه است چرا که اندازه درخت می‌تواند محدود باشد. سطح پایین یک درخت هشت‌تایی از برگ‌هایی که به داده‌های رنگی مربوطند و در درخت نمایش داده نمی‌شوند، تشکیل می‌گردد. این گره‌ها در ابتدا حاوی تک‌بیت‌ها هستند. اگر تعداد بیشتری از یک مقدار دلخواه رنگ از پالت‌ها وارد درخت شوند، اندازه درخت می‌تواند به صورت پیوسته کاهش یابد. این کار با دنبال کردن یک گره سطح پایین و افزایش میانگین مقدار بیتی آن تا رسیدن به برگ ادامه می‌یابد. در واقع به این ترتیب قسمتی از درخت هرس می‌شود. هنگامی که این کار به‌طور کامل انجام شود، با پیمایش همهٔ مسیرهای درخت تا برگ‌ها و در نظر گرفتن بیت‌ها در طول مسیر می‌توان به‌طور تقریبی تعداد رنگ‌های لازم را به دست آورد.

جستارهای وابسته

• افراز فضای دودویی
• درخت کی‌دی
• چاردرخت
• زیرفضا
• محدود کردن سلسله مراتب وقفه
• مسئله اندازه‌گیری Klee
• درخت‌های هشت‌تایی خطی
• مکعب ۲, موتور بازی سه بعدی که هندسه‌ آن به‌طور کامل برمبنای درخت هشت‌تایی است.
• موتور ارائه گرافیکی شی‌گرا, یک پیاده‌سازی مدیریت صحنه درخت هشت‌تایی دارد.
• ایرلیچت موتور, از گره‌های صحنهٔ درخت هشت‌تایی پشتیبانی می‌کند.
• آی‌دی تک ۶ یک موتور بازی سه‌بعدی در حال توسعه که واکسل‌هایی را که در درخت هشت‌تایی استفاده می‌شوند به‌کار می‌گیرد.
• واکسل

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Octree». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳۰ اردیبهشت ۱۳۹۳.

پیوند به بیرون

• تدریج درخت هشت‌تایی در مجلهٔ سیستم‌های مایکروسافت
• تدریج رنگ به وسیلهٔ درخت هشت‌تایی در وب‌گاه دکتر داب
• تدریج رنگ به وسیلهٔ درخت هشت‌تایی در کدمنبع دکتر داب
• خلاصهٔ تدریج رنگی درخت هشت‌تایی
• پیاده‌سازی موازی از الگوریتم تولید درخت‌هشت‌تایی، پ. سوجان لال، آ. یونیکریشان، ک پلوز جاکوب، ICIP 1997، کتابخانهٔ مجازی مؤسسه مهندسان برق و الکترونیک
• نسلی از درخت‌های هشت‌تایی از پویش شطرنجی با از دست رفتن اطلاعات کمتر، پ. سوجان لال، آ. یونیکریشان، ک پلوز جاکوب، کنفرانس بین‌المللی IASTED سال ۲۰۰۱
• پیاده‌سازی سی‌پلاس‌پلاس (مجوز عمومی همگانی گنو)
• درخت‌های هشت‌تایی موازی برای برنامه‌های عنصر محدود بایگانی‌شده در ۳ مارس ۲۰۱۶ توسط Wayback Machine
• مکعب دو: ساوربارتن - یک بازی که با موتور مکعب ۲ درخت هشت‌تایی سنگین نوشته شده
• Ogre - موتور ارائهٔ ماشینی تصاویر شی‌گرا سه‌بعدی با پیاده‌سازی مدیر صحنهٔ درخت هشت‌تایی (مجوز ام‌آی‌تی)
• دندرو: چندشبکه موازی برای شبکه‌های درخت‌هشت‌تایی (پیاده‌سازی MPI/C++)
• ویدیو: استفاده از درخت هشت‌تایی برای تخمین وضعیت
• کدمنبع یک اپلت OpenCL دنبال‌کنندهٔ اشعه به وسیلهٔ درخت هشت‌تایی