معالجة الهندسة

الموسوعة الحرة
كتاب "معالجة شبكة المضلعات" لماريو بوتش وآخرون هو كتاب مدرسي حول موضوع معالجة الهندسة. [ 1 ]

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

تغطي تطبيقات خوارزميات معالجة الهندسة بالفعل مجموعة واسعة من المجالات بدءًا من الوسائط المتعددة والترفيه والتصميم بمساعدة الحاسوب الكلاسيكي ، وصولاً إلى الحوسبة الطبية الحيوية والهندسة العكسية والحوسبة العلمية . [ 1 ]

تُعد معالجة الهندسة موضوعًا بحثيًا شائعًا في SIGGRAPH ، وهو المؤتمر الأكاديمي الرائد في مجال رسومات الحاسوب ، والموضوع الرئيسي للندوة السنوية حول معالجة الهندسة .

معالجة الهندسة كدورة حياة

شبكة لنبات الصبار توضح انحناء غاوس عند كل رأس، باستخدام طريقة عيب الزاوية

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

التمثيل المنفصل للشكل

كما هو الحال مع أي شكل آخر، فإن الأشكال المستخدمة في معالجة الهندسة لها خصائص تتعلق بهندستها وطوبولوجيتها . تتعلق هندسة الشكل بموقع نقاطه في الفضاء ، والمماسات ، والمتجهات العمودية ، والانحناء . كما تشمل البعد الذي يوجد فيه الشكل (مثلاً:R2{\displaystyle R^{2}}أوR3{\displaystyle R^{3}}تُعرَّف طوبولوجيا الشكل بأنها مجموعة من الخصائص التي لا تتغير حتى بعد تطبيق تحويلات سلسة عليه. وهي تتعلق بأبعاد مثل عدد الثقوب والحدود ، بالإضافة إلى قابلية الشكل للتوجيه. ومن الأمثلة على الأشكال غير القابلة للتوجيه شريط موبيوس .

في الحواسيب، يجب تقسيم كل شيء إلى أجزاء منفصلة. تُمثَّل الأشكال في معالجة الهندسة عادةً بشبكات مثلثية ، والتي يمكن اعتبارها رسمًا بيانيًا . كل عقدة في الرسم البياني هي رأس (عادةً فيR3{\displaystyle R^{3}}يُحدد هذا الموضع هندسة الشكل. تربط الحواف الموجهة هذه الرؤوس لتكوين مثلثات، والتي، وفقًا لقاعدة اليد اليمنى، يكون لها اتجاه يُسمى العمودي. يُشكل كل مثلث وجهًا من أوجه الشبكة. هذه الأشكال تركيبية بطبيعتها وتُحدد طوبولوجيا الشكل. بالإضافة إلى المثلثات، يمكن أيضًا استخدام فئة أعم من شبكات المضلعات لتمثيل شكل ما. تُحدد التمثيلات الأكثر تقدمًا، مثل الشبكات التدريجية، تمثيلًا تقريبيًا مع سلسلة من التحويلات، والتي تُنتج تمثيلًا دقيقًا أو عالي الدقة للشكل عند تطبيقها. تُعد هذه الشبكات مفيدة في مجموعة متنوعة من التطبيقات، بما في ذلك الجيومورفولوجيا، والنقل التدريجي، وضغط الشبكة، والتحسين الانتقائي. [ 2 ]

شبكة لأرنب ستانفورد الشهير. عادةً ما يتم تمثيل الأشكال كشبكة، وهي عبارة عن مجموعة من المضلعات التي تحدد ملامح الشكل.

خصائص الشكل

خصائص أويلر

إحدى الخصائص المهمة بشكل خاص للشكل ثلاثي الأبعاد هي خاصية أويلر ، والتي يمكن تعريفها أيضًا بدلالة جنسه . صيغة هذه الخاصية في السياق المتصل هيχ=2ج-2ح-ب{\displaystyle \chi =2c-2h-b}، أينج{\displaystyle c}يمثل عدد المكونات المتصلة،ح{\displaystyle h}عدد الثقوب (كما في ثقوب الدونات، انظر الطارة )، وب{\displaystyle b}يمثل عدد المكونات المتصلة لحدود السطح. مثال عملي على ذلك هو شبكة بنطال . يوجد مكون متصل واحد، ولا توجد فتحات، وثلاثة مكونات متصلة للحدود (الخصر وفتحتان للساقين). لذا، في هذه الحالة، تكون خاصية أويلر -1. ولتطبيق ذلك على العالم المتقطع، تُحسب خاصية أويلر للشبكة بدلالة رؤوسها وحوافها ووجوهها.χ=|V|-|هـ|+|F|{\displaystyle \chi =|V|-|E|+|F|}.

تُظهر هذه الصورة شبكةً لسروال، ذات خاصية أويلر -1. ويُفسَّر ذلك بالمعادلة المستخدمة لحساب الخاصية: 2c - 2h - b. تحتوي الشبكة على مُكوِّن مُتصل واحد، وصفر ثقوب طوبولوجية، وثلاثة حدود (فتحة الخصر وفتحة كل ساق): 2 - 0 - 3 = -1.

إعادة بناء السطح

إعادة بناء بواسون من نقاط السطح إلى الشبكة

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

اعتمادًا على كيفية تهيئة الشكل أو "إنشائه"، قد يوجد الشكل فقط كسديم من النقاط المأخوذة عينات منها والتي تمثل سطحه في الفضاء. لتحويل نقاط السطح إلى شبكة، يمكن استخدام استراتيجية إعادة بناء بواسون [ 3 ] . تنص هذه الطريقة على أنه يمكن حساب دالة المؤشر ، وهي دالة تحدد أي النقاط في الفضاء تنتمي إلى سطح الشكل، من النقاط المأخوذة عينات منها. المفهوم الأساسي هو أن تدرج دالة المؤشر يساوي صفرًا في كل مكان، باستثناء النقاط المأخوذة عينات منها، حيث يساوي متجه السطح العمودي الداخلي. بتعبير أدق، لنفترض أن مجموعة النقاط المأخوذة عينات منها من السطح يُرمز لها بـS{\displaystyle S}، كل نقطة في الفضاء بواسطةصأنا{\displaystyle p_{i}}، والعمودي المقابل عند تلك النقطة بواسطةنأنا{\displaystyle n_{i}}ثم يُعرَّف تدرج دالة المؤشر على النحو التالي:

▽ز={نأنا،∀صأنا∈S0،خلاف ذلك{\displaystyle \triangledown g={\begin{cases}{\textbf {n}}_{i},&\forall p_{i}\in S\\0,&{\text{otherwise}}\end{cases}}}

تصبح مهمة إعادة البناء حينها مسألة حسابية . لإيجاد دالة المؤشر للسطح، يجب علينا إيجاد دالةχ{\displaystyle \chi }بحيث‖▽χ-V‖{\displaystyle \lVert \triangledown \chi -{\textbf {V}}\rVert }يتم تقليلها إلى الحد الأدنى، حيثV{\displaystyle {\textbf {V}}}يمثل حقل المتجهات المحدد بواسطة العينات. وباعتبارها مسألة حسابية، يمكن النظر إلى المُصغِّر على أنهχ{\displaystyle \chi }كحل لمعادلة بواسون . [ 3 ] بعد الحصول على تقريب جيد لـχ{\displaystyle \chi }وقيمةσ{\displaystyle \sigma } والتي تُمنح عليها النقاط(x،y،z){\displaystyle (x,y,z)}معχ(x،y،z)=σ{\displaystyle \chi (x,y,z)=\sigma }يمكن استخدام خوارزمية المكعبات المتحركة لإنشاء شبكة مثلثية من الدالة ، وذلك بوضعها على السطح المراد إعادة بنائه.χ{\displaystyle \chi }والتي يمكن تطبيقها بعد ذلك في تطبيقات رسومات الحاسوب اللاحقة.

تسجيل

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

إحدى المشكلات الشائعة في معالجة البيانات الهندسية هي كيفية دمج عدة صور لجسم واحد تم التقاطها من زوايا أو مواقع مختلفة. تُعرف هذه المشكلة باسم التسجيل . في عملية التسجيل، نسعى لإيجاد تحويل صلب مثالي يُحاذي السطح.X{\displaystyle X}مع السطحY{\displaystyle Y}بصورة أكثر رسمية، إذاPY(x){\displaystyle P_{Y}(x)}هو إسقاط نقطة x من السطحX{\displaystyle X}على السطحY{\displaystyle Y}نريد إيجاد مصفوفة الدوران المثلىR{\displaystyle R}ومتجه الترجمةت{\displaystyle t}التي تقلل من دالة الهدف التالية:

∫x∈X||Rx+ت-PY(x)||2دx{\displaystyle \int _{x\in X}||Rx+t-P_{Y}(x)||^{2}dx}

على الرغم من أن الدورانات غير خطية بشكل عام، إلا أنه يمكن تحويل الدورانات الصغيرة إلى مصفوفات متناظرة معكوسة. علاوة على ذلك، فإن دالة المسافةx-PY(x){\displaystyle x-P_{Y}(x)}هي غير خطية، ولكنها قابلة للتقريب الخطي إذا كان التغير فيX{\displaystyle X}صغيرة. لذلك، يُستخدم حل تكراري مثل طريقة أقرب نقطة تكرارية (ICP) لحل التحويلات الصغيرة بشكل تكراري، بدلاً من حل التحويل الكبير المحتمل دفعة واحدة. في طريقة ICP، يتم اختيار n نقطة عشوائية منX{\displaystyle X}يتم اختيارها وعرضها علىY{\displaystyle Y}لأخذ عينات عشوائية منتظمة من النقاط على سطح شبكة المثلثات، تُقسّم عملية أخذ العينات العشوائية إلى مرحلتين: أخذ عينات منتظمة من النقاط داخل المثلث؛ وأخذ عينات غير منتظمة من المثلثات، بحيث يكون احتمال كل مثلث متناسبًا مع مساحة سطحه. [ 4 ] بعد ذلك، تُحسب التحويلة المثلى بناءً على الفرق بين كلx{\displaystyle x}وإسقاطها. في التكرار التالي، تُحسب الإسقاطات بناءً على نتيجة تطبيق التحويل السابق على العينات. وتُكرر العملية حتى الوصول إلى التقارب.

التنعيم

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

يتم اشتقاق دالة لاغرانج ذات الصلة المراد تقليلها عن طريق تسجيل مدى مطابقتها للإشارة الأوليةو¯{\displaystyle {\bar {f}}}ونعومة الإشارة الناتجة، والتي يتم تقريبها بمقدار التدرج مع وزن معين.λ{\displaystyle \lambda }:

ل(و)=∫Ω‖و-و¯‖2+λ‖∇و‖2دx{\displaystyle {\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx}.

اتخاذ شكل مختلفدلتاو{\displaystyle \delta f}علىل{\displaystyle {\mathcal {L}}}يُصدر الشرط اللازم

0=دلتال(و)=∫Ωدلتاو(أنا+λ∇2)و-دلتاوو¯دx{\displaystyle 0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx}.

بتقسيم هذا إلى عناصر ثابتة جزئياً مع وجود إشارتنا على الرؤوس، نحصل على

∑أنامأنادلتاوأناو¯أنا=∑أنامأنادلتاوأنا∑ج(أنا+λ∇2)وج=∑أنادلتاوأنا∑ج(م+λم∇2)وج،{\displaystyle {\begin{aligned}\sum _{i}M_{i}\delta f_{i}{\bar {f}}_{i}&=\sum _{i}M_{i}\delta f_{i}\sum _{j}(\mathbf {I} +\lambda \nabla ^{2})f_{j}=\sum _{i}\delta f_{i}\sum _{j}(M+\lambda M\nabla ^{2})f_{j},\end{aligned}}}

كرة صاخبة يتم تنعيمها بشكل متكرر

حيث اختيارنا لـ∇2{\displaystyle \nabla ^{2}}يتم اختياره ليكونم-1ل{\displaystyle M^{-1}\mathbf {L} }بالنسبة لظل التمام لابلاسل{\displaystyle \mathbf {L} }وم-1{\displaystyle M^{-1}}يُستخدم هذا المصطلح لرسم صورة لابلاس من المناطق إلى النقاط. ولأن التغير حر، ينتج عن ذلك مسألة خطية ذاتية الترافق تُحل باستخدام مُعامل.λ{\displaystyle \lambda }:و¯=(م+λل)و.{\displaystyle {\bar {f}}=(M+\lambda \mathbf {L} )f.}عند العمل مع شبكات المثلثات، إحدى طرق تحديد قيم مصفوفة لابلاس هيل{\displaystyle L}يتم ذلك من خلال تحليل هندسة المثلثات المتصلة على الشبكة.

لأناج={12(سرير أطفال⁡(αأناج)+سرير أطفال⁡(βأناج))الحافة ij موجودة-∑أنا≠جلأناجأنا=ج0خلاف ذلك{\displaystyle L_{ij}={\begin{cases}{\frac {1}{2}}(\cot(\alpha _{ij})+\cot(\beta _{ij}))&{\text{الحافة ij موجودة}}\\-\sum \limits _{i\neq j}L_{ij}&i=j\\0&{\text{فيما عدا ذلك}}\end{cases}}}

أينαأناج{\displaystyle \alpha _{ij}}وβأناج{\displaystyle \beta _{ij}}هي الزوايا المقابلة للحافة(أنا،ج){\displaystyle (i,j)}[ 5 ] تقوم مصفوفةالكتلةM كعامل حساب التكامل المحلي لقيمة الدالة، وغالبًا ما يتم تعيينها لشبكة تحتوي على m مثلثًا على النحو التالي:

مأناج={13∑ت=1م{أرهـأ(ت)إذا كان المثلث t يحتوي على الرأس i0خلاف ذلكإذا كان i=j0خلاف ذلك{\displaystyle M_{ij}={\begin{cases}{\frac {1}{3}}\sum \limits _{t=1}^{m}{\begin{cases}Area(t)&{\text{إذا كان المثلث t يحتوي على الرأس i}}\\0&{\text{فيما عدا ذلك}}\end{cases}}&{\text{إذا كان i=j}}\\0&{\text{فيما عدا ذلك}}\end{cases}}}

تحديد المعلمات

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

طريقة النوابض الكتلية

يُظهر نموذج Tutte Embedding معلمات غير سلسة على جانب الخنفساء.

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

مينيو∑أناج∈هـ||uأنا-uج||2{\displaystyle {\underset {U}{\text{min}}}\sum _{ij\in E}||u_{i}-u_{j}||^{2}}

أينهـ{\displaystyle E}هي مجموعة حواف الشبكة ويو{\displaystyle U}تمثل مجموعة الرؤوس. مع ذلك، فإن تحسين دالة الهدف هذه سيؤدي إلى حل يربط جميع الرؤوس برأس واحد في إحداثيات uv . باستعارة فكرة من نظرية الرسوم البيانية، نطبق رسم توت ونقيد رؤوس حدود الشبكة على دائرة الوحدة أو مضلع محدب آخر . يمنع هذا الإجراء الرؤوس من الانهيار في رأس واحد عند تطبيق الرسم. ثم توضع الرؤوس غير الحدودية عند الاستيفاء المركزي لجيرانها. مع ذلك، لا يزال رسم توت يعاني من تشوهات كبيرة لأنه يحاول جعل أطوال الحواف متساوية، وبالتالي لا يأخذ في الحسبان أحجام المثلثات على شبكة السطح الفعلية بشكل صحيح.

التحويلات المطابقة باستخدام طريقة المربعات الصغرى

مقارنة بين طريقة تضمين توت وطريقة التعيين المطابق للمربعات الصغرى. لاحظ كيف أن طريقة التعيين المطابق للمربعات الصغرى سلسة على جانب الخنفساء.

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

مينu،v∫S||∇u||2+||∇v||2دأ{\displaystyle {\underset {u,v}{\text{min}}}\int _{S}||\nabla u||^{2}+||\nabla v||^{2}dA}

هناك بعض الأمور الأخرى التي يجب مراعاتها. نرغب في تقليل تشوه الزاوية إلى أدنى حد ممكن للحفاظ على التعامد . وهذا يعني أننا نرغب في∇u=∇v⊥{\displaystyle \nabla u=\nabla v^{\perp }}بالإضافة إلى ذلك، نرغب أيضًا في أن تحتوي الخريطة على مناطق ذات أحجام متناسبة مع المناطق الأصلية. وينتج عن ذلك ضبط مصفوفة جاكوبي لدالتي الإحداثيات u و v على 1.

[∂u∂x∂u∂y∂v∂x∂v∂y]=1{\displaystyle {\begin{bmatrix}{\dfrac {\partial u}{\partial x}}&{\dfrac {\partial u}{\partial y}}\\[1em]{\dfrac {\partial v}{\partial x}}&{\dfrac {\partial v}{\partial y}}\end{bmatrix}}=1}

بجمع هذه المتطلبات معًا، يمكننا زيادة طاقة ديريشليه بحيث تصبح دالة الهدف لدينا كما يلي: [ 6 ] [ 7 ]

مينu،v∫S12||∇u||2+12||∇v||2-∇u⋅∇v⊥{\displaystyle {\underset {u,v}{\text{min}}}\int _{S}{\frac {1}{2}}||\nabla u||^{2}+{\frac {1}{2}}||\nabla v||^{2}-\nabla u\cdot \nabla v^{\perp }}

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

التشوه

مثال على التشوه بأقصى قدر ممكن من الصلابة

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

التشوه القائم على النقاط

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

سطح استراحةS^{\displaystyle {\hat {S}}}منغمس فيR3{\displaystyle \mathbb {R} ^{3}}يمكن وصفها باستخدام رسم خرائطيx^:Ω→R3{\displaystyle {\hat {x}}:\Omega \rightarrow \mathbb {R} ^{3}}، أينΩ{\displaystyle \Omega }هو مجال ثنائي الأبعاد ذو معلمات. ويمكن فعل الشيء نفسه مع عملية تحويل أخرى.x{\displaystyle x}للسطح المتحولS{\displaystyle S}من الناحية المثالية، يُضيف الشكل المُحوَّل أقل قدر ممكن من التشوه إلى الشكل الأصلي. إحدى طرق نمذجة هذا التشوه هي من حيث الإزاحات.د=x-x^{\displaystyle d=x-{\hat {x}}}باستخدام طاقة تعتمد على لابلاس. [ 9 ] يسمح لنا تطبيق مؤثر لابلاس على هذه التحويلات بقياس كيفية تغير موضع نقطة ما بالنسبة إلى جوارها، مما يحافظ على سلاسة المقابض. وبالتالي، يمكن كتابة الطاقة التي نرغب في تقليلها على النحو التالي:

ميند∫Ω||Δد||2دأ{\displaystyle \min _{\textbf {d}}\int _{\Omega }||\Delta {\textbf {d}}||^{2}dA}.

على الرغم من أن هذه الطريقة ثابتة عند الانتقال، إلا أنها لا تستطيع مراعاة الدوران. يطبق مخطط التشوه "As-Rigid-As-Possible" [ 10 ] تحويلاً صلباً.xأنا=Rxأنا^+ت{\displaystyle x_{i}=R{\hat {x_{i}}}+t}لكل مقبض i، حيثR∈Sيا(3)⊂R3{\displaystyle R\in SO(3)\subset \mathbb {R} ^{3}}هي مصفوفة دوران وت∈R3{\displaystyle t\in \mathbb {R} ^{3}}هو متجه إزاحة. لسوء الحظ، لا توجد طريقة لمعرفة الدورانات مسبقًا، لذا نختار بدلاً من ذلك دورانًا "أفضل" يقلل الإزاحات. ومع ذلك، يتطلب تحقيق ثبات الدوران المحلي دالة.R:Ω→Sيا(3){\displaystyle {\textbf {R}}:\Omega \rightarrow SO(3)}والذي يُخرج أفضل دوران لكل نقطة على السطح. وبالتالي، يجب تحسين الطاقة الناتجة على كلا الجانبين.x{\displaystyle {\textbf {x}}}وR{\displaystyle {\textbf {R}}}:

مينx,R∈Sيا(3)∫Ω||∇x-R∇x^||2دأ{\displaystyle \min _{{\textbf {x,R}}\in SO(3)}\int _{\Omega }||\nabla {\textbf {x}}-{\textbf {R}}\nabla {\hat {\textbf {x}}}||^{2}dA}

لاحظ أن متجه الإزاحة غير موجود في دالة الهدف النهائية لأن الإزاحات لها تدرج ثابت.

التجزئة الداخلية والخارجية

على الرغم من أن الأمر يبدو بسيطاً، إلا أن تحديد الجزء الداخلي من الجزء الخارجي لشبكة مثلثية ليس بالأمر السهل في كثير من الحالات. بشكل عام، عند إعطاء سطح ماS{\displaystyle S}نطرح هذه المشكلة على أنها تحديد دالةأناsأنانsأنادهـ(q){\displaystyle isInside(q)}والتي ستعود1{\displaystyle 1}إذا كانت النقطةq{\displaystyle q}موجود بالداخلS{\displaystyle S}، و0{\displaystyle 0}خلاف ذلك.

في أبسط الحالات، يكون الشكل مغلقًا. في هذه الحالة، لتحديد ما إذا كانت النقطةq{\displaystyle q}سواء كان داخل السطح أو خارجه، يمكننا إطلاق شعاعر{\displaystyle r}في أي اتجاه من نقطة الاستعلام، واحسب عدد المراتجouنتر{\displaystyle count_{r}}يمر عبر السطح. إذاq{\displaystyle q}كان بالخارجS{\displaystyle S}إذن، يجب ألا يمر الشعاع من خلالS{\displaystyle S}(في هذه الحالة)جouنتر=0{\displaystyle count_{r}=0}أو في كل مرة يدخل فيهاS{\displaystyle S}يجب أن يمر الشعاع مرتين، لأن S محدودة، لذا فإن أي شعاع يدخلها يجب أن يخرج منها. لذلك إذاq{\displaystyle q}في الخارج،جouنتر{\displaystyle count_{r}}زوجي. وبالمثل إذاq{\displaystyle q}إذا كان في الداخل، ينطبق المنطق نفسه على الحالة السابقة، ولكن يجب أن يتقاطع الشعاعS{\displaystyle S}مرة إضافية للمرة الأولى التي يغادر فيهاS{\displaystyle S}. لذا:

أناsأنانsأنادهـر(q)={1جouنتر أناs oدد0جouنتر أناs هـvهـن{\displaystyle isInside_{r}(q)=\left\{{\begin{array}{ll}1&count_{r}\ is\ odd\\0&count_{r}\ is\ even\\\end{array}}\right.}

في كثير من الأحيان، لا يمكننا ضمان ذلك.S{\displaystyle S}مغلق. خذ مثال البنطال من أعلى هذه المقالة. من الواضح أن هذا النسيج الشبكي له معنى داخلي وخارجي، على الرغم من وجود فتحات عند الخصر والساقين.

تقريب تجزئة الداخل والخارج عن طريق إطلاق أشعة من نقطة استعلام لعدد متغير من الأشعة

تتمثل المحاولة الساذجة لحل هذه المشكلة في إطلاق العديد من الأشعة في اتجاهات عشوائية، وتصنيفها.q{\displaystyle q}باعتبارها داخلية إذا وفقط إذا تقاطعت معظم الأشعةS{\displaystyle S}عدد فردي من المرات. ولتحديد ذلك كمياً، لنفترض أننا ألقيناك{\displaystyle k}أشعة،ر1،ر2،...،رك{\displaystyle r_{1},r_{2},\dots ,r_{k}}نربط رقماًرأyتيهـsت(q)=1ك∑أنا=1كأناsأنانsأنادهـرأنا(q){\displaystyle rayTest(q)={\frac {1}{k}}\sum _{i=1}^{k}isInside_{r_{i}}(q)}وهو متوسط ​​قيمةأناsأنانsأنادهـر{\displaystyle isInside_{r}}من كل شعاع. لذلك:

أناsأنانsأنادهـ(q)={1رأyتيهـsت(q)≥0.50رأyتيهـsت(q)<0.5{\displaystyle isInside(q)=\left\{{\begin{array}{ll}1&rayTest(q)\geq 0.5\\0&rayTest(q)<0.5\\\end{array}}\right.}

في حالة إطلاق عدد هائل من الأشعة، تُعالج هذه الطريقة الشبكات المفتوحة، إلا أنها تتطلب عددًا كبيرًا جدًا من الأشعة لتحقيق الدقة المطلوبة، مما يجعلها غير مثالية من الناحية الحسابية. ولذلك، يُعدّ رقم اللف المعمم نهجًا أكثر قوة. [ 11 ] يستوحي هذا النهج فكرته من رقم اللف ثنائي الأبعاد ، ويستخدم الزاوية المجسمة عندq{\displaystyle q}لكل مثلث في الشبكة لتحديد ما إذا كانq{\displaystyle q}يكون في الداخل أو الخارج. قيمة رقم اللف المعمم عندq{\displaystyle q}،wن(q){\displaystyle wn(q)}يتناسب مع مجموع مساهمة الزاوية المجسمة من كل مثلث في الشبكة:

wن(q)=14π∑ت∈Fsoلأنادأنزلهـ(ت){\displaystyle wn(q)={\frac {1}{4\pi }}\sum _{t\in F}solidAngle(t)}

بالنسبة للشبكة المغلقة،wن(q){\displaystyle wn(q)}وهي تعادل الدالة المميزة للحجم المُمثَّل بـS{\displaystyle S}لذلك نقول:

أناsأنانsأنادهـ(q)={1wن(q)≥0.50wن(q)<0.5{\displaystyle isInside(q)=\left\{{\begin{array}{ll}1&wn(q)\geq 0.5\\0&wn(q)<0.5\\\end{array}}\right.}

لأنwن(q){\displaystyle wn(q)}بما أن دالة الالتفاف المعممة دالة توافقية ، فإنها تتدهور بسلاسة، مما يعني أن تقسيم الشبكة المغلقة إلى داخلية وخارجية لن يتغير كثيرًا إذا أحدثنا ثقوبًا فيها. ولهذا السبب، تتعامل دالة الالتفاف المعممة بكفاءة مع الشبكات المفتوحة. يمر الحد الفاصل بين الداخل والخارج بسلاسة فوق الثقوب في الشبكة. في الواقع، في النهاية، تُصبح دالة الالتفاف المعممة مكافئة لطريقة إسقاط الأشعة عندما يؤول عدد الأشعة إلى اللانهاية.

التطبيقات

انظر أيضاً

مراجع

  1. 1 2 بوتش، ماريو؛ كوبيلت، ليف؛ بولي، مارك. أليز، بيير (2010). معالجة شبكة المضلع . الصحافة اتفاقية حقوق الطفل . رقم ISBN 9781568814261.
  2. ↑ هيوز هوب. "الشبكات التقدمية" (ملف PDF) .
  3. 1 2 "إعادة بناء سطح بواسون" . hhoppe.com . تم الاسترجاع في 26-01-2017 .
  4. ↑ سيمون روسينكيويتش، مارك ليفوي. "متغيرات فعالة لخوارزمية ICP" (PDF) .
  5. ↑ "كريس ترالي : شبكات لابلاس" . www.ctralie.com . تاريخ الاسترجاع: 16 مارس 2017 . 
  6. ↑ ديسبورن، ماثيو (2002). "المعاملات الجوهرية لشبكات الأسطح" (ملف PDF) . يوروغرافيكس . 21 .
  7. ↑ ليفي، برونو (2002). "خرائط المربعات الصغرى المطابقة لتوليد أطلس النسيج التلقائي" (ملف PDF) . معاملات ACM في الرسومات . 21 (3): 362-371 . doi : 10.1145/566654.566590 . مؤرشف من الأصل (ملف PDF) بتاريخ 15 مارس 2017. تم الاطلاع عليه بتاريخ 14 مارس 2017 .
  8. ↑ جاكوبسون، أليك؛ باران، إيليا؛ بوبوفيتش، يوفان؛ سوركين، أولغا (2011). "أوزان ثنائية التوافق محدودة للتشويه في الوقت الحقيقي" (ملف PDF) . معاملات ACM في الرسومات . 30 (4): 1. doi : 10.1145/2010324.1964973 .
  9. ↑ مارك، أليكسا (2003). "الإحداثيات التفاضلية للتشكيل والتشويه الموضعي للشبكة". الحاسوب المرئي . 19 (2): 105-114 . doi : 10.1007/s00371-002-0180-0 . S2CID 6847571 . 
  10. ↑ سوركين، أولغا ؛ أليكسا، مارك (2007). "نمذجة الأسطح بأقصى قدر من الصلابة" (ملف PDF) . وقائع ندوة EUROGRAPHICS/ACM SIGGRAPH حول معالجة الهندسة : 109-116 .
  11. ↑ جاكوبسون، أليك؛ لاديسلاف، كافان؛ سوركين-هورنونغ، أولغا (2013). "تقسيم قوي من الداخل إلى الخارج باستخدام أرقام اللف المعممة" (ملف PDF) . معاملات ACM في الرسومات . 32 (4): 1. doi : 10.1145/2461912.2461916 . S2CID 207202533 .