تقسيم الفضاء الثنائي

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 12 صور
الموسوعة الحرة
عملية إنشاء شجرة BSP

في علم الحاسوب ، يُعدّ تقسيم الفضاء الثنائي ( BSP ) طريقةً لتقسيم الفضاء ، حيث يتم تقسيم الفضاء الإقليدي بشكل متكرر إلى مجموعتين محدبتين باستخدام المستويات الفائقة كعناصر فاصلة. ينتج عن عملية التقسيم هذه تمثيل للكائنات داخل الفضاء على شكل بنية بيانات شجرية تُعرف بشجرة تقسيم الفضاء الثنائي .

طُوِّرَ تقسيم الفضاء الثنائي في سياق رسومات الحاسوب ثلاثية الأبعاد عام ١٩٦٩. [ ١ ] [ ٢ ] يُعدّ هيكل شجرة تقسيم الفضاء الثنائي مفيدًا في عملية العرض لأنه يُتيح توفير معلومات مكانية فعّالة حول الكائنات في المشهد، مثل ترتيب الكائنات من الأمام إلى الخلف بالنسبة للمشاهد في موقع مُحدد . تشمل التطبيقات الأخرى لتقسيم الفضاء الثنائي: إجراء عمليات هندسية على الأشكال ( الهندسة الصلبة البنائية ) في التصميم بمساعدة الحاسوب ، [ ٣ ] واكتشاف التصادم في الروبوتات وألعاب الفيديو ثلاثية الأبعاد، وتتبع الأشعة ، ومحاكاة المناظر الطبيعية الافتراضية، [ ٤ ] وغيرها من التطبيقات التي تتضمن التعامل مع المشاهد المكانية المعقدة.

تاريخ

  • في عام 1969، نشر شوماكر وآخرون [ 1 ] تقريرًا يصف كيفية استخدام مستويات موضوعة بدقة في بيئة افتراضية لتسريع ترتيب المضلعات. اعتمدت هذه التقنية على تماسك العمق، الذي ينص على أن المضلع الموجود على الجانب البعيد من المستوى لا يمكنه بأي حال من الأحوال أن يعيق مضلعًا أقرب إليه. وقد استُخدمت هذه التقنية في محاكيات الطيران التي أنتجتها شركتا جنرال إلكتريك وإيفانز وسوذرلاند. مع ذلك، كان مصمم المشهد يُنشئ تنظيم بيانات المضلعات يدويًا.
  • في عام 1980، قام فوكس وآخرون [ 2 ] بتوسيع فكرة شوماكر لتشمل تمثيل الأجسام ثلاثية الأبعاد في بيئة افتراضية، وذلك باستخدام مستويات تتطابق مع المضلعات لتقسيم الفضاء ثلاثي الأبعاد بشكل متكرر. وقد وفر هذا توليدًا آليًا وخوارزميًا بالكامل لبنية بيانات مضلعية هرمية تُعرف باسم شجرة تقسيم الفضاء الثنائي (BSP Tree). تمت هذه العملية كخطوة معالجة مسبقة غير متصلة بالإنترنت، تُنفذ مرة واحدة لكل بيئة/كائن. أثناء التشغيل، يتم توليد ترتيب الرؤية المعتمد على زاوية الرؤية من خلال اجتياز الشجرة.
  • قدمت أطروحة نايلور للدكتوراه عام 1981 [ 5 ] شرحًا وافيًا لأشجار BSP ومنهجًا قائمًا على نظرية الرسوم البيانية باستخدام مكونات مترابطة بقوة لحساب الرؤية مسبقًا، بالإضافة إلى الربط بين الطريقتين. وقد تم التركيز على أشجار BSP كبنية بحث مكاني مستقلة عن الأبعاد، مع تطبيقات في تحديد الأسطح المرئية. كما تضمنت الأطروحة أول بيانات تجريبية تُظهر أن حجم الشجرة وعدد المضلعات الجديدة كانا مناسبين (باستخدام نموذج لمكوك الفضاء).
  • في عام 1983، وصف فوكس وآخرون [ 6 ] تطبيقًا برمجيًا مصغرًا لخوارزمية شجرة BSP على نظام مخزن الإطارات Ikonas . وكان هذا أول عرض توضيحي لتحديد السطح المرئي في الوقت الحقيقي باستخدام أشجار BSP.
  • في عام ١٩٨٧، وصف ثيبو ونايلور [ ٣ ] كيفية تمثيل المجسمات متعددة الأوجه باستخدام شجرة BSP بدلاً من تمثيل الحدود التقليدي (b-rep ). وقد وفر هذا تمثيلاً صلباً بدلاً من التمثيل السطحي. ووُصفت عمليات المجموعات على المجسمات متعددة الأوجه باستخدام أداة، مما أتاح إنشاء هندسة صلبة بنائية (CSG) في الوقت الفعلي. وكان هذا بمثابة مقدمة لتصميم مستويات BSP باستخدام " الفرش "، الذي طُرح في محرر Quake ثم استُخدم في محرر Unreal.
  • في عام 1990، قدم نايلور وأماناتيدس وتيبو [ 7 ] خوارزمية لدمج شجرتي BSP لتكوين شجرة BSP جديدة من الشجرتين الأصليتين. يوفر هذا العديد من المزايا، بما في ذلك دمج الأجسام المتحركة المُمثلة بأشجار BSP مع بيئة ثابتة (مُمثلة أيضًا بشجرة BSP)، وعمليات CSG فعالة للغاية على متعددات السطوح، والكشف الدقيق عن التصادمات في زمن O(log n * log n)، والترتيب الصحيح للأسطح الشفافة الموجودة في جسمين متداخلين (وقد استُخدمت هذه التقنية لتأثير الرؤية بالأشعة السينية).
  • في عام 1991 اقترح تيلر وسيكوين [ 8 ] توليد مجموعات مرئية محتملة دون اتصال بالإنترنت لتسريع تحديد السطح المرئي في البيئات ثنائية الأبعاد المتعامدة.
  • في عام ١٩٩١، وصف غوردون وتشين [ ٩ ] طريقة فعّالة لتنفيذ عملية العرض من الأمام إلى الخلف باستخدام شجرة تقسيم الفضاء الثنائي (BSP)، بدلاً من الطريقة التقليدية من الخلف إلى الأمام. وقد استخدموا بنية بيانات خاصة لتسجيل أجزاء الشاشة التي تم رسمها وتلك التي لم يتم عرضها بعد، بكفاءة عالية. هذه الخوارزمية، بالإضافة إلى وصف أشجار تقسيم الفضاء الثنائي في كتاب رسومات الحاسوب القياسي آنذاك ( رسومات الحاسوب: المبادئ والتطبيق )، استخدمها جون كارماك في تطوير لعبة Doom .
  • وصفت أطروحة الدكتوراه التي قدمها تيلر عام 1992 [ 10 ] توليد مجموعات مرئية محتملة بكفاءة كخطوة تمهيدية لتسريع تحديد الأسطح المرئية في الوقت الفعلي في بيئات ثلاثية الأبعاد متعددة الأضلاع. وقد استُخدمت هذه الطريقة في لعبة Quake وساهمت بشكل كبير في تحسين أدائها.
  • في عام ١٩٩٣، أجاب نايلور [ ١١ ] على سؤال ما الذي يميز شجرة البحث الثنائي الجيدة. استخدم نماذج الحالة المتوقعة (بدلاً من تحليل أسوأ الحالات) لقياس التكلفة المتوقعة للبحث في الشجرة رياضياً، واستخدم هذا المقياس لبناء أشجار بحث ثنائي جيدة. وبشكل بديهي، تمثل الشجرة كائنًا بطريقة متعددة الدقة (أو بتعبير أدق، كشجرة تقريبية). وتُجرى مقارنات مع رموز هوفمان وأشجار البحث الثنائي الاحتمالية.
  • وصفت أطروحة الدكتوراه التي قدمها حيدر رادها عام ١٩٩٣ [ ١٢ ] أساليب تمثيل الصور (الطبيعية) باستخدام أشجار تقسيم الفضاء الثنائي (BSP). وشمل ذلك تطوير إطار عمل أمثل لبناء أشجار تقسيم الفضاء الثنائي لأي صورة مُدخلة. يعتمد هذا الإطار على تحويل جديد للصور، يُعرف باسم تحويل خط التقسيم ذي الخطأ التربيعي الأدنى (LSE) (LPE). كما طوّرت أطروحة رادها إطار عمل أمثل لضغط الصور بمعدل تشويه منخفض (RD) وأساليب لمعالجة الصور باستخدام أشجار تقسيم الفضاء الثنائي.

ملخص

مثال على شجرة رباعية لتقسيم الفضاء الثنائي المتكرر لفهرس ثنائي الأبعاد

تقسيم الفضاء الثنائي هو عملية عامة لتقسيم المشهد بشكل متكرر إلى قسمين باستخدام المستويات الفائقة [ 13 ] حتى يستوفي التقسيم شرطًا واحدًا أو أكثر. ويمكن اعتباره تعميمًا لهياكل الأشجار المكانية الأخرى، مثل أشجار k -d والأشجار الرباعية ، حيث يمكن أن تتخذ المستويات الفائقة التي تقسم الفضاء أي اتجاه، بدلًا من محاذاتها لمحاور الإحداثيات كما هو الحال في أشجار k -d أو الأشجار الرباعية. عند استخدامها في رسومات الحاسوب لعرض مشاهد مكونة من مضلعات مستوية ، غالبًا ما تُختار مستويات التقسيم لتتطابق مع المستويات التي تحددها المضلعات في المشهد.

يختلف اختيار مستوى التقسيم ومعيار إنهاء عملية التقسيم تبعًا لغرض شجرة تقسيم الفضاء الثنائي (BSP). على سبيل المثال، في عرض الرسومات الحاسوبية، يُقسّم المشهد حتى تحتوي كل عقدة في شجرة BSP على مضلعات يمكن عرضها بأي ترتيب. عند استخدام تقنية إزالة الأوجه الخلفية ، تحتوي كل عقدة بالتالي على مجموعة محدبة من المضلعات، بينما عند عرض المضلعات ثنائية الجوانب، تحتوي كل عقدة في شجرة BSP على مضلعات في مستوى واحد فقط. في اكتشاف التصادم أو تتبع الأشعة، يمكن تقسيم المشهد إلى عناصر أولية يسهل اختبار التصادم أو تقاطع الأشعة عليها.

نشأت تقنية تقسيم الفضاء الثنائي من حاجة رسومات الحاسوب إلى رسم مشاهد ثلاثية الأبعاد بسرعة، تتكون من مضلعات. إحدى الطرق البسيطة لرسم هذه المشاهد هي خوارزمية الرسام ، التي تُنتج المضلعات بترتيب بُعدها عن المشاهد، من الخلف إلى الأمام، حيث تُغطي الخلفية والمضلعات السابقة مع كل مضلع أقرب. لهذه الطريقة عيبان: الوقت اللازم لترتيب المضلعات من الخلف إلى الأمام، واحتمالية حدوث أخطاء في تداخل المضلعات. أوضح فوكس وزملاؤه [ 2 ] أن إنشاء شجرة تقسيم الفضاء الثنائي يحل هاتين المشكلتين، من خلال توفير طريقة سريعة لترتيب المضلعات بالنسبة إلى نقطة رؤية معينة (خطية بالنسبة لعدد المضلعات في المشهد)، ومن خلال تقسيم المضلعات المتداخلة لتجنب الأخطاء التي قد تحدث مع خوارزمية الرسام. من عيوب تقسيم الفضاء الثنائي أن إنشاء شجرة تقسيم الفضاء الثنائي قد يستغرق وقتًا طويلاً. لذا، عادةً ما تُجرى هذه العملية مرة واحدة على الأشكال الهندسية الثابتة، كخطوة حسابية مسبقة، قبل عملية العرض أو أي عمليات أخرى في الوقت الفعلي على المشهد. إن تكلفة إنشاء شجرة BSP تجعل من الصعب وغير الفعال تنفيذ تحريك الكائنات مباشرةً في الشجرة.

جيل

يُستخدم نموذج شجرة تقسيم الفضاء الثنائي (BSP) عادةً لعرض المضلعات (ذات الوجهين، أي بدون حذف الأوجه الخلفية ) باستخدام خوارزمية الرسام. يُحدد لكل مضلع وجه أمامي ووجه خلفي، ويمكن اختيارهما بشكل عشوائي، ولا يؤثران إلا على بنية الشجرة وليس على النتيجة المطلوبة. [ 2 ] تُنشأ هذه الشجرة من قائمة غير مرتبة لجميع المضلعات في المشهد. الخوارزمية التكرارية لإنشاء شجرة تقسيم الفضاء الثنائي من قائمة المضلعات هذه هي: [ 2 ]

  1. اختر مضلعًا P من القائمة.
  2. قم بإنشاء عقدة N في شجرة BSP، وأضف P إلى قائمة المضلعات عند تلك العقدة.
  3. لكل مضلع آخر في القائمة:
    1. إذا كان هذا المضلع يقع بالكامل أمام المستوى الذي يحتوي على النقطة P ، فانقل هذا المضلع إلى قائمة العقد الموجودة أمام النقطة P.
    2. إذا كان هذا المضلع يقع بالكامل خلف المستوى الذي يحتوي على النقطة P ، فانقل هذا المضلع إلى قائمة العقد الموجودة خلف النقطة P.
    3. إذا تقاطع هذا المضلع مع المستوى الذي يحتوي على النقطة P ، فقم بتقسيمه إلى مضلعين وانقلهما إلى قوائم المضلعات المقابلة خلف وأمام النقطة P.
    4. إذا كان هذا المضلع يقع في المستوى الذي يحتوي على النقطة P ، فأضفه إلى قائمة المضلعات عند العقدة N.
  4. قم بتطبيق هذه الخوارزمية على قائمة المضلعات الموجودة أمام النقطة P.
  5. قم بتطبيق هذه الخوارزمية على قائمة المضلعات الموجودة خلف النقطة P.

يوضح الرسم التخطيطي التالي استخدام هذه الخوارزمية في تحويل قائمة من الخطوط أو المضلعات إلى شجرة BSP. في كل خطوة من الخطوات الثماني (من 1 إلى 8)، تُطبق الخوارزمية المذكورة أعلاه على قائمة من الخطوط، وتُضاف عقدة جديدة إلى الشجرة.

ابدأ بقائمة من الخطوط (أو المضلعات في الفضاء ثلاثي الأبعاد) التي تُشكّل المشهد. في مخططات الشجرة، تُمثّل القوائم بمستطيلات ذات زوايا مستديرة، بينما تُمثّل العُقد في شجرة BSP بدوائر. في المخطط المكاني للخطوط، يُشار إلى الاتجاه المُختار ليكون "مقدمة" الخط بسهم.
أنا.باتباع خطوات الخوارزمية المذكورة أعلاه،
  1. نختار سطراً، أ، من القائمة و...
  2. ...أضفه إلى عقدة.
  3. نقوم بتقسيم الأسطر المتبقية في القائمة إلى تلك التي تسبق A (أي B2، C2، D2)، وتلك التي تليها (B1، C1، D1).
  4. نقوم أولاً بمعالجة الأسطر التي تسبق A (في الخطوات من ii إلى v)،...
  5. ... ويليهم من هم في الخلف (في الخطوات من السادسة إلى السابعة).
ii.نطبق الآن الخوارزمية على قائمة الخطوط التي تسبق النقطة A (والتي تحتوي على B2 وC2 وD2). نختار خطًا، ولنسمه B2، ونضيفه إلى عقدة، ثم نقسم بقية القائمة إلى الخطوط التي تسبق B2 (D2)، والخطوط التي تلي B2 (C2 وD3).
ثالثاً.اختر خطًا، D2، من قائمة الخطوط الموجودة أمام B2 و A. إنه الخط الوحيد في القائمة، لذلك بعد إضافته إلى عقدة، لا يلزم القيام بأي شيء آخر.
رابعاً.انتهينا من الخطوط أمام B2، لذا انظر إلى الخطوط خلف B2 (C2 وD3). اختر أحدها (C2)، وأضفه إلى عقدة، وضع الخط الآخر في القائمة (D3) في قائمة الخطوط أمام C2.
v.والآن انظر إلى قائمة الخطوط أمام C2. يوجد خط واحد فقط (D3)، لذا أضف هذا إلى عقدة واستمر.
vi.لقد أضفنا الآن جميع الخطوط الموجودة أمام A إلى شجرة BSP، لذلك نبدأ الآن بقائمة الخطوط الموجودة خلف A. باختيار خط (B1) من هذه القائمة، نضيف B1 إلى عقدة ونقسم باقي القائمة إلى خطوط أمام B1 (أي D1)، وخطوط خلف B1 (أي C1).
السابع.بعد معالجة قائمة الأسطر الموجودة أمام B1 أولاً، فإن D1 هو السطر الوحيد في هذه القائمة، لذا أضف هذا إلى عقدة واستمر.
ثامناً.بالنظر بعد ذلك إلى قائمة الخطوط خلف B1، فإن الخط الوحيد في هذه القائمة هو C1، لذا أضف هذا إلى عقدة، وبذلك تكتمل شجرة BSP.

غالبًا ما يكون العدد النهائي للمضلعات أو الخطوط في الشجرة أكبر (أحيانًا أكبر بكثير [ 2 ] ) من القائمة الأصلية، نظرًا لضرورة تقسيم الخطوط أو المضلعات التي تعبر مستوى التقسيم إلى قسمين. من المستحسن تقليل هذه الزيادة، مع الحفاظ على توازن معقول في الشجرة النهائية. لذا، يُعد اختيار المضلع أو الخط المستخدم كمستوى تقسيم (في الخطوة 1 من الخوارزمية) أمرًا بالغ الأهمية لإنشاء شجرة BSP فعّالة.

اجتياز

يتم اجتياز شجرة BSP في زمن خطي، بترتيب تحدده وظيفة الشجرة. بالعودة إلى مثال رسم المضلعات ثنائية الأضلاع باستخدام خوارزمية الرسام، يتطلب رسم المضلع P بشكل صحيح رسم جميع المضلعات خلف المستوى الذي يقع فيه P أولاً، ثم المضلع P ، ثم أخيرًا المضلعات أمامه . إذا تحقق ترتيب الرسم هذا لجميع المضلعات في المشهد، فسيتم عرض المشهد بأكمله بالترتيب الصحيح. يمكن تنفيذ هذه العملية من خلال اجتياز شجرة BSP بشكل متكرر باستخدام الخوارزمية التالية. [ 2 ] من موقع عرض معين V ، لعرض شجرة BSP،

  1. إذا كانت العقدة الحالية عقدة طرفية، فقم بعرض المضلعات عند العقدة الحالية.
  2. وإلا، إذا كان موقع العرض V أمام العقدة الحالية:
    1. قم بعرض شجرة BSP الفرعية التي تحتوي على المضلعات خلف العقدة الحالية
    2. قم بعرض المضلعات عند العقدة الحالية
    3. قم بعرض شجرة تقسيم الفضاء الثنائي الفرعية التي تحتوي على مضلعات أمام العقدة الحالية
  3. وإلا، إذا كان موقع العرض V خلف العقدة الحالية:
    1. قم بعرض شجرة تقسيم الفضاء الثنائي الفرعية التي تحتوي على مضلعات أمام العقدة الحالية
    2. قم بعرض المضلعات عند العقدة الحالية
    3. قم بعرض شجرة BSP الفرعية التي تحتوي على المضلعات خلف العقدة الحالية
  4. وإلا، يجب أن يكون موقع العرض V موجودًا تمامًا على المستوى المرتبط بالعقدة الحالية. ثم:
    1. قم بعرض شجرة تقسيم الفضاء الثنائي الفرعية التي تحتوي على مضلعات أمام العقدة الحالية
    2. قم بعرض شجرة BSP الفرعية التي تحتوي على المضلعات خلف العقدة الحالية

يؤدي تطبيق هذه الخوارزمية بشكل متكرر على شجرة BSP التي تم إنشاؤها أعلاه إلى الخطوات التالية:

  • تُطبَّق الخوارزمية أولاً على العقدة الجذرية للشجرة، وهي العقدة A. وبما أن V تقع أمام العقدة A ، فإننا نُطبِّق الخوارزمية أولاً على شجرة BSP الفرعية التي تحتوي على المضلعات الواقعة خلف A.
    • تحتوي هذه الشجرة على العقدة الجذرية B1 . تقع V خلف B1 ، لذا أولاً، نطبق الخوارزمية على شجرة BSP الفرعية التي تحتوي على المضلعات أمام B1 :
      • هذه الشجرة هي مجرد العقدة الورقية D1 ، لذلك يتم عرض المضلع D1 .
    • ثم نقوم برسم المضلع B1 .
    • ثم نطبق الخوارزمية على شجرة BSP الفرعية التي تحتوي على المضلعات خلف B1 :
      • هذه الشجرة هي مجرد العقدة الورقية C1 ، لذلك يتم عرض المضلع C1 .
  • ثم نرسم مضلعات A
  • ثم نطبق الخوارزمية على شجرة تقسيم الفضاء الثنائي الفرعية التي تحتوي على مضلعات أمام A
    • تحتوي هذه الشجرة على العقدة الجذرية B2 . تقع V خلف B2 ، لذا أولاً، نطبق الخوارزمية على شجرة BSP الفرعية التي تحتوي على المضلعات أمام B2 :
      • هذه الشجرة هي مجرد العقدة الورقية D2 ، لذلك يتم عرض المضلع D2 .
    • ثم نقوم برسم المضلع B2 .
    • ثم نطبق الخوارزمية على شجرة BSP الفرعية التي تحتوي على المضلعات خلف B2 :
      • تحتوي هذه الشجرة على العقدة الجذرية C2 . تقع V أمام C2 ، لذا سنطبق الخوارزمية أولاً على شجرة BSP الفرعية التي تحتوي على المضلعات خلف C2 . ولكن لا توجد شجرة كهذه، لذا نتابع.
      • نقوم برسم المضلع C2 .
      • نطبق الخوارزمية على شجرة BSP الفرعية التي تحتوي على مضلعات أمام C2
        • هذه الشجرة هي مجرد العقدة الورقية D3 ، لذلك يتم عرض المضلع D3 .

يتم اجتياز الشجرة في وقت خطي ويتم عرض المضلعات بترتيب من البعيد إلى القريب ( D1 ، B1 ، C1 ، A ، D2 ، B2 ، C2 ، D3 ) وهو ترتيب مناسب لخوارزمية الرسام.

طلب

تُستخدم أشجار تقسيم الفضاء الثنائي (BSP) بكثرة في ألعاب الفيديو ثلاثية الأبعاد ، وخاصةً ألعاب التصويب من منظور الشخص الأول والألعاب التي تدور أحداثها في بيئات داخلية. ومن محركات الألعاب التي تستخدم أشجار BSP : Doom و Quake و GoldSrc و Source . في هذه المحركات، تُستخدم أشجار BSP التي تحتوي على الهندسة الثابتة للمشهد غالبًا مع مخزن العمق (Z-buffer ) لدمج العناصر المتحركة، مثل الأبواب والشخصيات، بشكل صحيح مع خلفية المشهد. ورغم أن تقسيم الفضاء الثنائي يوفر طريقة ملائمة لتخزين واسترجاع المعلومات المكانية حول المضلعات في المشهد، إلا أنه لا يحل مشكلة تحديد الأسطح المرئية . كما طُبقت أشجار BSP أيضًا في ضغط الصور. [ 14 ]

انظر أيضاً

مراجع

  1. 1 2 شوماكر، ر.أ.؛ براند، ب.؛ جيلاند، م.ج.؛ شارب، و.هـ. (1969). دراسة لتطبيق الصور المولدة بالحاسوب على المحاكاة المرئية (تقرير). مختبر الموارد البشرية التابع للقوات الجوية الأمريكية. AFHRL-TR-69-14.
  2. 1 2 3 4 5 6 7 فوكس، هنري؛ كيدم، تسفي م؛ نايلور، بروس ف. (1980). "حول توليد الأسطح المرئية بواسطة هياكل شجرية مسبقة" (ملف PDF) . وقائع مؤتمر SIGGRAPH '80، المؤتمر السنوي السابع حول رسومات الحاسوب والتقنيات التفاعلية . ACM. الصفحات 124-133 . doi : 10.1145/965105.807481 . 
  3. 1 2 ثيبولت، ويليام سي؛ نايلور، بروس إف (1987). "عمليات المجموعات على متعددات السطوح باستخدام أشجار تقسيم الفضاء الثنائي". وقائع مؤتمر SIGGRAPH '87، المؤتمر السنوي الرابع عشر حول رسومات الحاسوب والتقنيات التفاعلية . ACM. ص 153-162 . doi : 10.1145/37402.37421 . 
  4. ↑ إيثرينغتون، توماس ر.؛ مورغان، فريزر ج.؛ أوسوليفان، ديفيد (2022). "تقسيم الفضاء الثنائي يُنتج نماذج هرمية وخطية محايدة للمناظر الطبيعية مناسبة للمناظر الطبيعية التي يهيمن عليها الإنسان" . علم بيئة المناظر الطبيعية . 37 (7): 1761-1769 . Bibcode : 2022LaEco..37.1761E . doi : 10.1007/s10980-022-01452-6 .
  5. ↑ نايلور، بروس (مايو 1981). تقنيات قائمة على المعرفة المسبقة لتحديد أولوية الرؤية للمشاهد ثلاثية الأبعاد (أطروحة دكتوراه). جامعة تكساس في دالاس . تم الاطلاع عليه في 5 يونيو 2025 .
  6. ↑ فوكس، هنري؛ أبرام، غريغوري د.؛ غرانت، إريك د. (1983). "عرض مظلل شبه فوري للأجسام الصلبة". وقائع المؤتمر السنوي العاشر حول رسومات الحاسوب والتقنيات التفاعلية . ACM. ص 65-72 . doi : 10.1145/800059.801134 . ISBN  978-0-89791-109-2.
  7. ↑ نايلور، بروس؛ أماناتيدس، جون؛ ثيبو، ويليام (أغسطس 1990). "دمج أشجار BSP ينتج عنه عمليات مجموعة متعددة السطوح" . مجلة ACM SIGGRAPH لرسومات الحاسوب . 24 (4). رابطة آلات الحوسبة: 115-124 . CiteSeerX 10.1.1.69.292 . doi : 10.1145/97880.97892 . تاريخ الاسترجاع: 5 يونيو 2025 . 
  8. ↑ تيلر، سيث جيه؛ سيكوين، كارلو إتش. (1 يوليو 1991). "معالجة الرؤية المسبقة للجولات التفاعلية" . مجلة ACM SIGGRAPH لرسومات الحاسوب . 25 (4). رابطة آلات الحوسبة: 61-70 . تم الاطلاع عليه في 5 يونيو 2025 .
  9. ↑ تشين، س.؛ جوردون، د. (أكتوبر 1991). "عرض من الأمام إلى الخلف لأشجار BSP" . مجلة IEEE لرسومات الحاسوب وتطبيقاتها . 11 (5): 79-85 . doi : 10.1109/38.90569 . S2CID 19056967 . 
  10. ↑ تيلر، سيث (1992). حسابات الرؤية في بيئات متعددة السطوح محجوبة بكثافة (أطروحة دكتوراه). جامعة كاليفورنيا في بيركلي . تم الاطلاع عليه في 5 يونيو 2025 .
  11. ↑ نايلور، بروس ( 1993). "بناء أشجار تقسيم جيدة" (ملف PDF) . واجهة الرسومات . الجمعية الكندية لمعالجة المعلومات: 181-191 . تم الاطلاع عليه في 5 يونيو 2025 .
  12. ↑ رادها، حيدر (1993). تمثيل الصور بكفاءة باستخدام أشجار تقسيم الفضاء الثنائي (أطروحة دكتوراه). جامعة كولومبيا . تم الاطلاع عليه في 5 يونيو 2025 .
  13. ↑ نايلور، بروس (يناير 2005). "دليل تعليمي حول تقسيم الأشجار في الفضاء الثنائي" . ResearchGate . تم الاطلاع عليه في 1 يوليو 2025 .
  14. ↑ رادها، هـ.؛ فيترلي، م.؛ ليوناردي، ر. (1996). "ضغط الصور باستخدام أشجار تقسيم الفضاء الثنائي" (ملف PDF) . معاملات IEEE في معالجة الصور . 5 (12): 1610-1624 . Bibcode : 1996ITIP....5.1610R . doi : 10.1109/83.544569 . PMID 18290079 . 

مراجع إضافية