نقطة المثلث الكشف عن التصادم في 3D

Question

كيف يمكنني تصحيح النقطة العائمة الخطأ التالية المحاكاة الفيزيائية:

• النقطة الأصلية (x, y, z) ،
• النقطة المطلوبة (x', y', z') بعد قوات تطبيقها.
• مثلثين (أ ، ب ، ج) و (ب ، ج ، د) من حصة الحافة قبل الميلاد

أنا باستخدام هذا الأسلوب من أجل الكشف عن التصادم:

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

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

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

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

Answer 1

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

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

• العددية دقة حقا يمكن أن يسبب راي "السقوط من خلال الفجوة".المشكلة هي أننا تتقاطع راي مع الطائرة ABC (الحصول على النقطة P ، يقول) قبل اختبار ضد الخط قبل الميلاد.ثم نحن تتقاطع راي مع الطائرة BCD (الحصول على النقطة س ، يقول) قبل اختبار ضد الخط قبل الميلاد.P و Q على حد سواء ممثلة في أقرب نقطة عائمة التقريب ؛ لا يوجد سبب لتوقع أن هذه بالضبط الكذب على الطائرات التي من المفترض أن تكذب على و لذلك كل الاحتمالات التي يمكن أن يكون لديك كل من P إلى اليسار من قبل الميلاد و س أن حق قبل الميلاد.

• وذلك باستخدام أقل من أو تساوي الاختبار لن المساعدة ؛ هو عدم دقة في تقاطع راي الطائرة هذه مشكلة.

• الجذور التربيعية ليست المسألة ؛ يمكنك أن تفعل كل ما يلزم الحسابية باستخدام نقطة المنتجات و النقطة العائمة شعبة.

وهنا بعض حلول حقيقية:

• بالنسبة محدبة تنسجم ، يمكنك اختبار فقط ضد جميع الطائرات و تجاهل حواف القمم ، كما تقول (وبالتالي تجنب المشكلة تماما).

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

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

اسمحوا لي أن نوصي بشدة الكتاب في الوقت الحقيقي الكشف عن التصادم قبل كريستر اريكسون.هناك مناقشة هذه المشكلة بالضبط على صفحات 446-448 و شرح العددية الثلاثي المنتج نهج المتقاطعة راي مع مثلث على صفحات 184-188.

Answer 2

يبدو أنك لا بما في ذلك اختبار إذا كان على حافة (كنت تكتب "داخل مثلث حواف").حاول تغيير رمز إلى "أقل من أو يساوي" (داخل أو متداخلة).

Answer 3

أجد أنه من غير المحتمل إلى حد ما أن راي قد تقع بالضبط بين المثلثات بطريقة الفاصلة العائمة الدقة المفعول.هل أنت متأكد أن هذا هو في الواقع مشكلة ؟

على أي حال, ممكن حل بدلا من اطلاق النار مجرد راي واحد لاطلاق النار ثلاثة التي هي قريبة جدا من بعضها البعض.إذا كان أحد يقع بالضبط بين أن على الأقل واحد من اثنين آخرين مكفول تقع على مثلث.

هذا على الأقل تسمح لك لاختبار إذا كانت المشكلة هي حقا نقطة عائمة خطأ أو شيء أكثر احتمالا.

Answer 4

@البيان:أنا في الواقع بالفعل باستخدام "أكبر من أو يساوي" مقارنة في قانون بلدي, شكرا لك على الاقتراح.+1

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

هل هذا معقول الحل ؟

Answer 5

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

double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

منذ العملية الأخيرة لا الجذر التربيعي, لا تفقد الدقة أكثر من ذلك.

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