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

چپ: تقسیم بازگشتی یک مکعب به اکتان. راست: درخت هشت‌تایی معادل.
درخت هشت‌تایی (به انگلیسی: Octree) یک داده‌ساختار درخت است که در آن هر گره داخلی دقیقا هشت فرزند دارد. درخت‌های هشت‌تایی اغلب برای افراز کردن یک فضای سه‌بعدی از طریق تقسیم بازگشتی آن فضا به هشت قسمت مساوی استفاده می‌شوند. درخت‌های هشت‌تایی در واقع معادل چاردرخت در حالت سه بعدی‌اند. اسم این درخت از دو کلمه انگلیسی oct و tree تشکیل شده‌است، اما توجه کنید که این کلمه معمولا به صورت octree فقط با یک حرف t نوشته می‌شود. درخت‌های هشت‌تایی غالبا در گرافیک سه‌بعدی رایانه‌ای و موتورهای بازی سه‌بعدی استفاده می‌شوند.
درخت‌های هشت‌تایی برای نمایش فضایی
هر گره در یک درخت هشت‌تایی فضا را به هشت اکتان تقسیم می‌کند. در یک درخت هشت‌تایی نقطه‌ای ناحیه‌ای، هر گره در واقع یک نقطه سه‌بعدی را نگه می‌دارد که مرکز قسمتی است که مربوط به آن گره است؛ این نقطه گوشه مشترک هر هشت فرزند گره است. در یک درخت هشت‌تایی نقطه‌ای که حول آن فضا تقسیم می‌شود به‌طور ضمنی مرکز قسمتی است که گره نمایش می‌دهد. گره ریشه از یک درخت هشت‌تایی PR می‌تواند فضای نامحدود را نشان دهد؛ در حالی که گره ریشه از یک درخت هشت‌تایی MX باید یک فضای محدود را نشان دهد که مرکزهای هر قسمت قابل تعریف باشند. توجه داشته باشید که درخت هشت‌تایی با درخت کی‌دی متفاوت است. درخت‌های کی‌دی در راستای یک بعد تقسیم‌بندی انجام می‌دهند اما درخت‌های هشت‌تایی پیرامون یک نقطه (در راستای سه‌بعد) تقسیم‌بندی انجام می‌دهند. همچنین درخت‌های کی‌دی همواره دودویی‌اند که در مورد درخت‌های هشت‌تایی این گونه نیست. با به‌کارگیری جستجوی عمق اول (dfs) باید گره‌ها پیمایش شوند اما فقط سطوح مورد نیاز در نظر گرفته شوند.
تاریخچه
درخت هشت‌تایی برای گرافیک سه‌بعدی رایانه‌ای اولین بار توسط دونالر میقر در موسسه پلی‌تکنیک رنسلیر استفاده شد، که در گزارش سال ۱۹۸۰ با عنوان "رمزگذاری درخت‌های هشت‌تایی: یک راه جدید برای نمایش دوباره، دست‌کاری و نمایش دلخواه اشیاء سه‌بعدی به وسیله کامپیوتر" آن را شرح داد. او صاحب ثبت اختراع ۱۹۹۵ (با تاریخ اولویت ۱۹۸۴) با عنوان "تولید سریع عکس از اشیاء جامد پیچیده به وسیله رمزگذاری درخت هشت‌تایی" نیز بود.
کاربردهای رایج درخت هشت‌تایی
گرافیک سه‌بعدی رایانه‌ای
نمایه‌سازی فضایی
جستجوی نزدیکترین همسایه
تشخیص برخورد کارآمد در فضای سه‌بعدی
نمایش سطوح پنهان
روش سریع چند قطبی
شبکه‌های بدون ساختار
تحلیل اجزاء محدود
درخت هشت‌تایی پراکنده واکسل
تخمین حالت
تخمین مجموعه
کاربرد در درجه‌بندی رنگ‌ها
الگوریتم درجه‌بندی رنگ در درخت هشت‌تایی توسط گرواتز و پورگاتوفر در سال ۱۹۸۸ ابداع شد. این الگوریتم داده‌های مربوط به رنگ یک تصویر را به صورت درخت هشت‌تایی درآورده و درخت را تا عمق ۹ سطح کدگذاری می‌کند. از آنجا که در سیستم رنگی آرجی‌بی سه مولفه رنگی وجود دارد و ۸=۳^۲ از درخت هشت‌تایی استفاده می‌شود. شماره مربوط به یک گره در سطح بالا با یک فرمول مشخص می‌شود که از پرارزش‌ترین بیت‌های مولفه‌های رنگی قرمز، سبز و آبی استفاده می‌کند، مثلا 4r + 2g + b. سطح بعدی یا پایین‌تر از بیت‌های پرارزش بعدی استفاده می‌کند و به همین ترتیب جلو می‌رود. گاهی بیت‌های کم ارزش نادیده گرفته می‌شوند تا اندازه درخت کاهش یابد.
این الگوریتم از لحاظ مصرف حافظه بسیار بهینه است چرا که اندازه درخت می‌تواند محدود باشد. سطح پایین یک درخت هشت‌تایی از برگ‌هایی که به داده‌های رنگی مربوطند و در درخت نمایش داده نمی‌شوند، تشکیل می‌گردد. این گره‌ها در ابتدا حاوی تک‌بیت‌ها هستند. اگر تعداد بیشتری از یک مقدار دلخواه رنگ از پالت‌ها وارد درخت شوند، اندازه درخت می‌تواند به صورت پیوسته کاهش یابد. این کار با دنبال کردن یک گره سطح پایین و افزایش میانگین مقدار بیتی آن تا رسیدن به برگ ادامه می‌یابد. در واقع به این ترتیب قسمتی از درخت هرس می‌شود. هنگامی که این کار به‌طور کامل انجام شود، با پیمایش همه مسیرهای درخت تا برگ‌ها و در نظر گرفتن بیت‌ها در طول مسیر می‌توان به‌طور تقریبی تعداد رنگ‌های لازم را به دست آورد.
افراز فضای دودویی
درخت کی‌دی
چاردرخت
زیرفضا
محدود کردن سلسله مراتب وقفه
مسئله اندازه‌گیری Klee
درخت‌های هشت‌تایی خطی
مکعب ۲, موتور بازی سه بعدی که هندسه آن به‌طور کامل برمبنای درخت هشت‌تایی است.
موتور ارائه گرافیکی شی‌گرا, یک پیاده‌سازی مدیریت صحنه درخت هشت‌تایی دارد.
ایرلیچت موتور, از گره‌های صحنه درخت هشت‌تایی پشتیبانی می‌کند.
آی‌دی تک ۶ یک موتور بازی سه‌بعدی در حال توسعه که واکسل‌هایی را که در درخت هشت‌تایی استفاده می‌شوند به‌کار می‌گیرد.
واکسل