الحجم المحيط

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

يُعدّ الحجم المحيط بمجموعة من الكائنات حجمًا محيطًا أيضًا للكائن الواحد الذي يتكون من اتحادها، والعكس صحيح. لذلك، يمكن حصر الوصف في حالة الكائن الواحد، الذي يُفترض أنه غير فارغ ومحدود (منتهٍ).

تُستخدم أحجام التحديد في أغلب الأحيان لتسريع أنواع معينة من الاختبارات.

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

في عملية اكتشاف التصادم ، عندما لا يتقاطع حجمان محيطان، لا يمكن للأجسام الموجودة بداخلهما أن تتصادم.

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

للحصول على أحجام محيطة للأجسام المعقدة، تتمثل إحدى الطرق الشائعة في تقسيم الأجسام/المشهد باستخدام مخطط المشهد أو بشكل أكثر تحديدًا باستخدام تسلسل هرمي للأحجام المحيطة ، مثل أشجار OBB . وتتلخص الفكرة الأساسية وراء ذلك في تنظيم المشهد في بنية شبيهة بالشجرة، حيث يشمل الجذر المشهد بأكمله، وتحتوي كل ورقة على جزء فرعي أصغر. ^{[ 1 ]}

في مجال الرؤية المجسمة الحاسوبية ، يُعرف الحجم المحيط الذي يتم إعادة بنائه من صور ظلية لجسم ما باسم " الهيكل المرئي ". ^{[ 2 ]}

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

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

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

يُستخدم المستطيل المحيط الأدنى ( MBR ) - وهو أصغر مستطيل محيطي AABB ثنائي الأبعاد - بشكل متكرر في وصف عناصر البيانات الجغرافية (أو "المكانية")، حيث يعمل كبديل مبسط للنطاق المكاني لمجموعة البيانات (انظر البيانات الوصفية المكانية ) لأغراض البحث عن البيانات (بما في ذلك الاستعلامات المكانية عند الاقتضاء) وعرضها. كما أنه عنصر أساسي في طريقة شجرة R للفهرسة المكانية .

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

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

أالأسطوانة المحيطة هيأسطوانةتحتوي على الجسم. في معظم التطبيقات، يكون محور الأسطوانة محاذيًا للاتجاه الرأسي للمشهد. تُعد الأسطوانات مناسبة للأجسام ثلاثية الأبعاد التي لا يمكنها الدوران إلا حول محور رأسي، ولا يمكنها الدوران حول محاور أخرى، وتقتصر حركتها على الانتقال فقط. تتقاطع أسطوانتان محاذيتان للمحور الرأسي عندما تتقاطع إسقاطاتهما على المحور الرأسي - وهما قطعتان مستقيمتان - وكذلك إسقاطاتهما على المستوى الأفقي - وهما قرصان دائريان. يسهل اختبار كلا الحالتين. فيألعاب الفيديو، تُستخدم الأسطوانات المحيطة غالبًا كحجوم محيطة للأشخاص الواقفين.

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

الكرة المحيطة هي كرة تحتوي على الجسم. في الرسومات ثنائية الأبعاد، تُمثل هذه الكرة بدائرة . تُحدد الكرات المحيطة بمركزها ونصف قطرها. وتتميز هذه الكرات بسهولة وسرعة اختبار تصادمها: إذ تتقاطع كرتان عندما لا تتجاوز المسافة بين مركزيهما مجموع نصفي قطريهما. وهذا ما يجعل الكرات المحيطة مناسبة للأجسام التي يمكنها الحركة في أي عدد من الأبعاد.

أاللوح المحيط هو الحجم الذي يمتد إلى حد معين على محور، ويمكن اعتبارهاللوحالمحصور بين مستويين. أما الصندوق المحيط فهو تقاطع ألواح محيطة متعامدة. وقد استُخدمت الألواح المحيطة لتسريععملية تتبع الأشعة ^{[ 3 ].}

أيُعدّ تحديد المثلث في بُعدين مفيدًا جدًا لتسريع عملية قصّ أو اختبار رؤية منحنى B-Spline. راجعقسم "خوارزميات قصّ الدوائر ومنحنيات B-Spline"ضمن موضوع القصّ (الرسومات الحاسوبية) للاطلاع على مثال عملي.

الغلاف المحدب هو أصغر حجم محدب يحتوي على الجسم. إذا كان الجسم عبارة عن اتحاد مجموعة محدودة من النقاط، فإن غلافه المحدب يكون متعدد السطوح.

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

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

في حالة AABB، تصبح هذه الاختبارات مجموعة بسيطة من اختبارات التداخل بدلالة محاور الوحدة. بالنسبة لـ AABB معرف بواسطة M و N مقابل واحد معرف بواسطة O و P ، فإنهما لا يتقاطعان إذا كان ( Mx > Px ₎ أو ( _{Ox > Nx )} أو ₍ My > Py ₎ أو ( Oy > Ny ₎ أو ( Mz > Pz ₎ أو ( Oz > _{Nz ) .}            

يمكن أيضًا إسقاط AABB على طول محور، على سبيل المثال، إذا كانت له حواف بطول L وكان مركزه عند C ، ويتم إسقاطه على طول المحور N: ${\displaystyle r=0.5L_{x}|N_{x}|+0.5L_{y}|N_{y}|+0.5L_{z}|N_{z}|\,}$، و${\displaystyle b=C*N\,}$أو${\displaystyle b=C_{x}N_{x}+C_{y}N_{y}+C_{z}N_{z}\,}$، و${\displaystyle m=br,n=b+r\,}$ حيث يمثل m و n الحد الأدنى والحد الأقصى للمدى.

يُشابه مخطط OBB هذا الأمر من هذه الناحية، ولكنه أكثر تعقيدًا بعض الشيء. بالنسبة لمخطط OBB ذي المحورين L و C كما هو موضح أعلاه، وذو المحاور I و J و K كمحاور أساسية، فإن:

${\displaystyle r=0.5L_{x}|N*I|+0.5L_{y}|N*J|+0.5L_{z}|N*K|\,}$

${\displaystyle m=C*Nr{\mbox{ و }}n=C*N+r\,}$

بالنسبة للمدىين m و n و o و p ، يمكن القول إنهما لا يتقاطعان إذا كان m  > p أو o > n . وبالتالي، من خلال إسقاط مدىي منطقتين محددتين على المحاور I و J و K لكل منطقة، والتحقق من عدم التقاطع، يمكن اكتشاف عدم التقاطع. وبإجراء فحص إضافي على طول حاصل الضرب الاتجاهي لهذه المحاور (I₀ _× I₁ _، I₀ _× J₁ _، ...)، يمكن التأكد بشكل أكبر من استحالة التقاطع.   

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

يمكن حساب تقاطع مجموعتين من نوع k -DOP بطريقة مشابهة جدًا لحساب تقاطع مجموعات المربعات المحاذية للمحاور (AABBs): لكل اتجاه، يتم التحقق من الفترتين المتناظرتين في المجموعتين. لذا، وكما أن مجموعات DOP هي تعميم لمجموعات AABBs، فإن اختبار التقاطع هو تعميم لاختبار تداخل مجموعات AABBs. تبلغ تعقيدية اختبار تداخل مجموعتين من نوع DOP من الرتبة O( k ) . مع ذلك، يفترض هذا أن كلا المجموعتين معطيتان بالنسبة لنفس مجموعة الاتجاهات. إذا تم تدوير إحداهما، فإن هذا الافتراض لا ينطبق. في هذه الحالة، توجد طريقة سهلة نسبيًا للتحقق من المجموعتين.${\displaystyle D^{1},D^{2}}$لأن التقاطع هو إحاطة الجزء المدور،${\displaystyle D^{2}}$، بواسطة DOP آخر أصغر محيط${\displaystyle {\tilde {D}}^{2}}$ذلك الموجه بالنسبة لاتجاهات DOP الأول${\displaystyle D^{1}}$إن إجراء ذلك أكثر تعقيدًا بعض الشيء، ولكنه في النهاية يصل إلى ضرب المصفوفة بالمتجه بتعقيد O( k ) أيضًا. ^{[ 4 ]}

• خوارزميات الغلاف المحدب
• المؤشر المكاني
• منطقة الإصابة

• رسم توضيحي لعدة لقطات فيديو لنفس النموذج، من موقع epicgames.com