شبكة مثلثة

إحدى طرق مشاركة بيانات الرؤوس بين المثلثات هي شريط المثلثات. في هذا الشريط، يشترك كل مثلث في ضلع كامل مع جاره الأول، وضلع آخر مع الجار التالي. وهناك طريقة أخرى هي مروحة المثلثات ، وهي مجموعة من المثلثات المتصلة التي تشترك في رأس مركزي واحد. بهذه الطرق، تتم معالجة الرؤوس بكفاءة، مما يقلل الحاجة إلى معالجة N+2 رأسًا فقط لرسم N مثلثًا. ^{[ 3 ]}

تعتبر شرائح المثلثات فعالة، لكن تحويل شبكة المثلثات إلى مجموعة دنيا من شرائح المثلثات يمثل مشكلة NP-كاملة . ^{[ 4 ]}

توفر بنية البيانات التي تمثل الشبكة دعمًا لعمليتين أساسيتين: إدراج المثلثات وإزالتها. كما تدعم عملية دمج الحواف، وهي مفيدة في مخططات تقليل عدد المثلثات. لا تدعم هذه البنية مواقع الرؤوس، ولكنها تفترض أن لكل رأس مُعرّفًا صحيحًا فريدًا، عادةً ما يكون فهرس ذلك الرأس في مصفوفة من مواقع الرؤوس المتجاورة. يُعرَّف رأس الشبكة بعدد صحيح واحد ويُرمز له بـ hvi. تُعرَّف حافة الشبكة بزوج من الأعداد الصحيحة hv0 و v1i، حيث يُمثل كل عدد نقطة نهاية للحافة. ​​لدعم خرائط الحواف، تُخزَّن الحواف بحيث يكون v0 = min(v0,v1). يُعرَّف مُكوِّن المثلث بثلاثية من الأعداد الصحيحة hv0 و v1 و v2i، حيث يُمثل كل عدد رأسًا من رؤوس المثلث. لدعم خرائط المثلثات، تُخزَّن المثلثات بحيث يكون v0 = min(v0,v1,v2). لاحظ أن hv0,v1,v2i و hv0,v2,v1i تُعاملان كمثلثين مختلفين. يجب على أي تطبيق يتطلب مثلثات ثنائية الأضلاع إدراج كلا الثلاثيتين في بنية البيانات. ولتجنب التذكير المستمر بترتيب الفهارس، لا تشير معلومات الزوج/الثلاثية في بقية المستند إلى ترتيب الرؤوس بأي شكل من الأشكال (مع أن التنفيذ يتعامل مع الترتيب).

تُحدد مجموعة الثلاثيات التي تُمثل المثلثات الاتصال بين مكونات المثلث. المثلث t = hv0,v1,v2i له رؤوس v0 و v1 و v2. وله أضلاع e0 = hv0,v1i و e1 = hv1,v2i و e2 = hv2,v0i. الاتصالات العكسية معروفة أيضًا. الرأس v0 مجاور للضلعين e0 و e2 وللمثلث t. الرأس v1 مجاور للضلعين e0 و e1 وللمثلث t. الرأس v2 مجاور للضلعين e1 و e2 وللمثلث t. جميع الأضلاع الثلاثة e0 و e1 و e2 مجاورة للمثلث t.

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

Vertex = <عدد صحيح>; // v الحافة = <عدد صحيح، عدد صحيح>؛ // v0، v1 مثلث <عدد صحيح، عدد صحيح، عدد صحيح>؛ // v0، v1، v2 VData = <بيانات الرؤوس الخاصة بالتطبيق>؛ EData = <بيانات الحافة الخاصة بالتطبيق>؛ TData = <بيانات المثلث الخاصة بالتطبيق>؛ VAttribute = <VData, set<Edge>,set<Triangle>>; // data, eset, tset EAttribute = <EData, set<Triangle>>; // data, tset TAttribute = <TData>; // البيانات VPair = pair<Vertex,VAttribute>; EPair = pair<Edge,EAttribute>; TPair = pair<Triangle,TAttribute>; VMap = map<VPair>; EMap = map<EPair>; TMap = map<TPair>; Mesh = <VMap,EMap,TMap>; // vmap, emap, tmap 

تدعم الخرائط وظائف الإضافة والحذف القياسية لجدول التجزئة. تتم الإضافة فقط إذا لم يكن العنصر موجودًا مسبقًا، وتتم الحذف فقط إذا كان العنصر موجودًا.

تتضمن هذه العملية تحديد ضلع hvk, vti، حيث يُسمى vk رأس الاحتفاظ وvt رأس الرمي. تُزال المثلثات التي تشترك في هذا الضلع من الشبكة. كما يُزال الرأس vt من الشبكة. أي مثلثات تشترك في الرأس vt يُستبدل هذا الرأس بالرأس vk. يوضح الشكل 1 شبكة مثلثات وتسلسلًا لثلاث عمليات دمج للأضلاع مُطبقة على الشبكة.

باستخدام مصفوفات الفهرسة، تُمثَّل الشبكة بمصفوفتين منفصلتين، إحداهما تحتوي على الرؤوس، والأخرى تحتوي على مجموعات من ثلاثة فهارس تُحدِّد المثلث. يُعالج نظام الرسومات الرؤوس أولًا، ثم يُرسم المثلثات لاحقًا، مستخدمًا مجموعات الفهرسة التي تعمل على البيانات المُحوَّلة. في OpenGL، يدعم ذلك الدالة glDrawElements() عند استخدام كائن مخزن مؤقت للرؤوس (VBO).

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