اجتياز شجرة دينار كويتي (Raytracing) - هل أنا أفتقد القضية؟

Question

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

ملاحظة: لا يوجد أي من الأشعة في السؤال متوازي لأي محور.

هذه هي خوارزمية اجتيازي:

IntersectionData* intersectKDTree(const Ray &ray, KDTreeNode* node, double tMin, double tMax) const{

if (node->GetObjectCount()==0) return 0;

IntersectionData* current = 0;
bool intersected = false;

if (node->m_isLeaf){
        ...test all primitives in the leaf...
}
else{
    int axis = node->m_splitAxis;
    double splitPos = node->m_splitPos;
    double tSplit = (splitPos-ray.point[axis])/ray.direction[axis];
    KDTreeNode* nearNode = ray.point[axis]<splitPos?node->m_leftnode:node->m_rightnode;
    KDTreeNode* farNode = ray.point[axis]<splitPos?node->m_rightnode:node->m_leftnode;

    if (tSplit > tMax)
        return intersectKDTree(ray, nearNode , tMin, tMax);//case A
    else if (tSplit < tMin){
        if(tSplit>0)
            return intersectKDTree(ray, farNode, tMin, tMax);//case B
        else if(tSplit<0)
            return intersectKDTree(ray, nearNode, tMin,tMax);//case C
        else{//tSplit==0
            if(ray.direction[axis]<0)
                return intersectKDTree(ray, farNode, tMin, tMax);//case D
            else
                return intersectKDTree(ray, nearNode, tMin, tMax);//case E
        }
    }
    else{
        if(tSplit>0){//case F
            current = intersectKDTree(ray, nearNode, tMin, tSplit);
            if (current != 0)
                return current;
            else
                return intersectKDTree(ray, farNode, tSplit, tMax);
        }
        else{
            return intersectKDTree(ray,nearNode,tSplit, tMax);//case G
        }
    }
}
}

لقد أنشأت رسم مع جميع الحالات المختلفة:

_{(مصدر: cycovery.com.)}

هل أنا أفتقد القضية؟

شكرا للمساعدة!

Answer 1

فقط في حالة اهتمام شخص ما - الخطأ الذي فعلته هو عدم النظر في حالة خاصة موصوفة في هذه الورقة

http://www.cs.utexas.edu/ftp/pub/techreports/tr88-07.pdf. صفحة 12.

يحدث ذلك إذا كان مضلع واحد يكمن على متن الطائرة، بحيث يكون جزءا من كل من الخلايا ويعود راي عبر الخلايا. إذا تم اختبار NEARDCELL، لكن التقاطع الفعلي يحدث في مساحة FARCELL (هذا ممكن لأن المضلع الذي يتقاطع جزءا من كلا الخلايا)، فلا يزال هناك إمكانية، أنه في الخلية البعيدة يمكن العثور على تقاطع هو في الواقع أقرب من وجدت بالفعل. لذلك - إذا كانت موجودة لتقاطع أكبر من Tsplit، فقد يتم بالفعل اختبار FARCELL

Answer 2

لقد اتخذت نهجا مختلفا للمشكلة، إليك ما أقوم به:

if(ray.direction(current_node.split_axis)>0) {
  near=current_node.left_child
  far=current_node.right_child
} else {
  near=current_node.right_child
  far=current_node.left_child
}
tsplit=(current_node.split_value-ray.origin[current_node.split_axis])/ray.direction[current_node.split_axis]
if(tsplit>current_stack.tmax||tsplit<0) {
  only near child
} else if(tsplit<tmin) {
  only far child
} else {
  both childs
}

ترى أنني لا أستخدم أصل Ray لاختيار أي من الطفل الأيسر / الأيمن بالقرب من / بعيدا، وأخذ في حساب الحالة المسمى C. باستخدام TSPlit <0