الزلزال هو الجذر التربيعي العكسي السريع - 💡 Fix My Ideas

الزلزال هو الجذر التربيعي العكسي السريع

الزلزال هو الجذر التربيعي العكسي السريع


مؤلف: Ethan Holmes, 2019

تُستخدم وظيفة الجذر التربيعي العكسي (1 / sqrt (x)) بكثافة أثناء حلقة السحب في محرك اللعبة لتطبيع الموجهات في متجهات "وحدة" بطول 1. تكون المتجهات الطبيعية مهمة لأنك عندما تأخذ منتج نقطة لاثنين من لهم (Ax * Bx + Ay * By + Az * Bz) ، والنتيجة هي جيب تمام الزاوية بين المتجهين.

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

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

ولكن إذا كنت لا تمانع في التخلص قليلاً من الدقة ، فهناك طريقة أسرع.

هناك وظيفة الجذر التربيعي العكسي التي تستخدمها الكثير من محركات الألعاب والتي نشأ أنها نشأت في Quake III بواسطة مبرمج Nvidia Gary Tarolli. تبدو هكذا:

float InvSqrt (float x) {float xhalf = 0.5f * x؛ int i = * (int *) & x؛ // get bits for value floating i = 0x5f3759df - (i >> 1)؛ // يعطي التخمين الأولي y0 x = * (float *) & i؛ // convert bits back to float x = x * (1.5f-xhalf * x * x)؛ // نيوتن الخطوة ، كرر يزيد من دقة عودة س ؛ }

انتظر ، ماذا كان ذلك؟!؟!

إذاً ، عند العودة إلى الوراء ، جاء نيوتن بطريقة ذكية لتقريب الجذر التربيعي العكسي. أولاً ، يمكنك تقسيم الرقم الأصلي x على اثنين. دعنا ندعو أن "xhalf". ثم ، يمكنك إجراء تخمين وثيق بشكل معقول في الجذر التربيعي العكسي. دعنا نسمي ذلك g. بعد ذلك ، تأخذ هذين المتغيرين وتنفذ هذا الحساب (الذي ستتعرف عليه كخطوة أخيرة في وظيفة InvSqrt):

g = g * (1.5 - xhalf * g * g)

إذا قمت بذلك مرارًا وتكرارًا ، والاستعاضة عن g المحدثة في كل تكرار ، فسوف يتم g بسرعة في الجذر التربيعي العكسي لـ x! في الواقع ، إذا قمت باختيار g لائق لتبدأ به ، فإن تكرارًا واحدًا أو اثنين سيجعلك قريبًا جدًا من القيمة الصحيحة.

والسؤال هو ، كيف تجد هذا التخمين الأولي لأول ز؟ يستخدم مبرمجو محركات اللعبة خدعة بكيفية تمثيل أرقام الفاصلة العائمة بالثنائي ، حيث يتم تقسيم الأسس والفسخ بشكل مشابه للترميز العلمي. في تعويم 32 بت ، تكون بت أقصى يسار بت تسجيل ويكون 0 للأرقام الموجبة. ويلي ذلك 8 أجزاء من الأس (منحازة بـ 127 لتمثيل الأسس السلبية والإيجابية) ، ويمثل الجزء الأخير من 23 بتة المانتيسا.

حسنًا ، للقيام بجذر التربيع العكسي ، ستحتاج في الأساس إلى ضرب الأس ب -1/2. عندما تقوم بتحويل هذه البتات إلى اليمين (عملية سريعة جدًا) ، فإن التأثير على الأس هو تقسيمها على 2. لا تزال بحاجة إلى طرح الأس من 0 إلى تغيير علامتها ، وماذا تفعل حيال السرعوف الذي تأثر أيضا في عملية التحول قليلا؟

هذا هو المكان الذي يظهر فيه رقم 0x5f3759df السحري. إنه حقًا ممتلئ تمامًا ، ولكن من خلال طرح نتيجة تحول البت من 0x5f3759df ، تتم إعادة تعيين mantissa إلى ما يقرب من حالته الأصلية ويتم طرح الأس من 0 (مع الأخذ في الاعتبار أنه من 127) .

النتيجة قريبة جدًا من الجذر التربيعي العكسي. أغلق بما يكفي لتمرير واحد عبر معادلة نيوتن لينتهي بقيمة محددة بما يكفي لأغراض عملية.

فهم الجذر التربيعي العكسي للمربع التجريبي للزاوية السريعة - التفاصيل والرياضيات وراء الرقم السحري (PDF)



قد تكون مهتمة

لوحات EL وجلد: Space Invader Cuff

لوحات EL وجلد: Space Invader Cuff


نشرة Maker Pro الإخبارية - آلة أخرى ، الطباعة ثلاثية الأبعاد في آسيا ، Google I / O

نشرة Maker Pro الإخبارية - آلة أخرى ، الطباعة ثلاثية الأبعاد في آسيا ، Google I / O


لا يصدق الفن المعبأة في زجاجات الرمال من 1800s

لا يصدق الفن المعبأة في زجاجات الرمال من 1800s


تعديل وحدة تحكم Xbox One لضمور العضلات الجزء 2

تعديل وحدة تحكم Xbox One لضمور العضلات الجزء 2