نظرية تقاطع راي بوكس

Question

أرغب في تحديد نقطة التقاطع بين شعاع وصندوق. يتم تعريف المربع من خلال إحداثيات MIN 3D والإحداثيات MAX 3D ويتم تعريف الأشعة من خلال أصله والاتجاه الذي يشير إليه.

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

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

bool PointOnBoxFace(R3Point point, R3Point corner1, R3Point corner2)
{
  double min_x = min(corner1.X(), corner2.X());
  double max_x = max(corner1.X(), corner2.X());
  double min_y = min(corner1.Y(), corner2.Y());
  double max_y = max(corner1.Y(), corner2.Y());
  double min_z = min(corner1.Z(), corner2.Z());
  double max_z = max(corner1.Z(), corner2.Z());
  if(point.X() >= min_x && point.X() <= max_x && 
     point.Y() >= min_y && point.Y() <= max_y &&
     point.Z() >= min_z && point.Z() <= max_z)
     return true;

  return false;
}

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

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

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

شكرًا.

Answer 1

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

أفترض أنك تصور بالفعل أن شعاعك يسافر بسرعة على طول متجهه وتجد وقت التقاطع مع كل طائرة. لذلك ، على سبيل المثال ، إذا كنت تتقاطع مع الطائرة في x=x0, ، وشعرك يسير في الاتجاه (rx,ry,rz) من عند (0,0,0), ، ثم وقت التقاطع t = x0/rx. لو t سلبي ، تجاهلها-أنت تسير في الاتجاه الآخر. لو t هل يجب أن تقرر كيفية التعامل مع هذه الحالة الخاصة-إذا كنت في طائرة بالفعل ، هل ترتد أو تمر عبرها؟ قد ترغب أيضًا في التعامل معها rx==0 كحالة خاصة (بحيث يمكنك ضرب حافة الصندوق).

على أي حال ، لديك الآن الإحداثيات بالضبط حيث ضربت تلك الطائرة: هم (t*rx , t*ry , t*rz). الآن يمكنك فقط قراءة ما إذا كان t*ry و t*rz في المستطيل ، يجب أن يكونوا في (أي بين Min و Max للمكعب على طول تلك المحاور). لا تختبر إحداثيات X لأنك تعلم بالفعل أنك تضربها مرة أخرى ، عليك أن تقرر ما إذا كان/كيفية التعامل مع الزوايا الضرب كحالة خاصة. علاوة على ذلك ، يمكنك الآن طلب تصادماتك مع الأسطح المختلفة حسب الوقت واختيار الأول كنقطة تصادمك.

يتيح لك ذلك الحساب ، دون اللجوء إلى العوامل التعسفية Epsilon ، سواء أكان وأين تقاطع شعاعك المكعب ، إلى الدقة الممكنة مع الحساب العائم.

لذلك تحتاج فقط إلى ثلاث وظائف مثل تلك التي حصلت عليها بالفعل: واحدة لاختبار ما إذا كنت قد ضرب yz على افتراض أنك ضربت x, والأخرى المقابلة ل xz و xy على افتراض أنك ضربت y و z على التوالى.

---

تحرير: تم إضافة رمز إلى (عام)

#define X_FACE 0
#define Y_FACE 1
#define Z_FACE 2
#define MAX_FACE 4

// true if we hit a box face, false otherwise
bool hit_face(double uhit,double vhit,
                 double umin,double umax,double vmin,double vmax)
{
  return (umin <= uhit && uhit <= umax && vmin <= vhit && vhit <= vmax);
}

// 0.0 if we missed, the time of impact otherwise
double hit_box(double rx,double ry, double rz,
                double min_x,double min_y,double min_z,
                double max_x,double max_y,double max_z)
{
  double times[6];
  bool hits[6];
  int faces[6];
  double t;
  if (rx==0) { times[0] = times[1] = 0.0; }
  else {
    t = min_x/rx;
    times[0] = t; faces[0] = X_FACE; 
    hits[0] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z);
    t = max_x/rx;
    times[1] = t; faces[1] = X_FACE + MAX_FACE;
    hits[1] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z);
  }
  if (ry==0) { times[2] = times[3] = 0.0; }
  else {
    t = min_y/ry;
    times[2] = t; faces[2] = Y_FACE;
    hits[2] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z);
    t = max_y/ry;
    times[3] = t; faces[3] = Y_FACE + MAX_FACE;
    hits[3] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z);
  }
  if (rz==0) { times[4] = times[5] = 0.0; }
  else {
    t = min_z/rz;
    times[4] = t; faces[4] = Z_FACE;
    hits[4] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y);
    t = max_z/rz;
    times[5] = t; faces[5] = Z_FACE + MAX_FACE;
    hits[5] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y);
  }
  int first = 6;
  t = 0.0;
  for (int i=0 ; i<6 ; i++) {
    if (times[i] > 0.0 && (times[i]<t || t==0.0)) {
      first = i;
      t = times[i];
    }
  }
  if (first>5) return 0.0;  // Found nothing
  else return times[first];  // Probably want hits[first] and faces[first] also....
}

(لقد كتبت هذا للتو ، لم أتجمعه ، لذا احذر من الأخطاء.) (تحرير: فقط تصحيح i -> first.)

على أي حال ، النقطة المهمة هي أنك تعامل الاتجاهات الثلاثة بشكل منفصل ، واختبار لمعرفة ما إذا كان التأثير قد حدث داخل المربع الأيمن في إحداثيات (u ، v) ، حيث (u ، v) إما (x ، y) ، (x ، z) ، أو (y ، z) اعتمادًا على الطائرة التي ضربتها.

Answer 2

PointOnBoxFace يجب أن يكون فحص ثنائي الأبعاد بدلاً من ثلاثية الأبعاد. على سبيل المثال ، إذا كنت تختبر مقابل z = z_min الطائرة ، ثم يجب أن تحتاج فقط إلى المقارنة x و y إلى حدود كل منها. لقد اكتشفت ذلك بالفعل z التنسيق صحيح. من المحتمل أن تعزفك الدقة العائمة النقطة كما تقوم "بإعادة التحقق" الإحداثيات الثالثة.

على سبيل المثال ، إذا z_min هو 1.0 ، يمكنك الاختبار الأول ضد تلك الطائرة. تجد نقطة تقاطع (x, y, ، 0.999999999). الآن ، رغم ذلك x و y داخل الحدود ، z ليس صحيحا تماما.

Answer 3

الرمز يبدو جيدا. حاول العثور على هذا الشعاع بالذات وتصحيحه.

Answer 4

هل يمكن أن يكون أن راي ينتهي بالمرور بالضبط عبر حافة الصندوق؟ قد تسبب أخطاء Roundoff Floating Point من قبل كل من الوجه الأيمن والخلفي.

Answer 5

تحرير: تجاهل هذه الإجابة (انظر التعليقات أدناه حيث أظهرت بشكل مقنع خطأ طرقي).

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

double epsilon = 1e-10; // Depends the scale of things in your code.
double min_x = min(corner1.X(), corner2.X()) - epsilon;
double max_x = max(corner1.X(), corner2.X()) + epsilon;
double min_y = min(corner1.Y(), corner2.Y()) - epsilon;
...

من الناحية الفنية ، تتمثل الطريقة الصحيحة لمقارنة الأرقام تقريبًا في الإدلاء بتمثيلاتها بت على ints ومقارنة الأعداد الصحيحة لبعض الإزاحة الصغيرة ، على سبيل المثال ، في ج:

#define EPSILON 10 /* some small int; tune to suit */
int almostequal(double a, double b) {
    return llabs(*(long long*)&a - *(long long*)&b) < EPSILON;
}

بالطبع ، هذا ليس بالأمر السهل في C#، ولكن ربما يمكن أن تحقق الدلالات غير الآمنة نفس التأثير. (بفضل novox على تعليقاته ، والتي تقودني إلى لطيفة صفحة شرح هذه التقنية بالتفصيل.)