Quelle est la logique d'intersection de l'arbre kd?

J'essaie de comprendre comment implémenter un arbre KD.

À la page 322 de «Détection de collision en temps réel» par Ericson

La section de texte est incluse ci-dessous au cas où l'aperçu du livre Google ne vous permet pas de le voir au moment où vous cliquez sur le lien

section de texte

Section pertinente:

L'idée de base derrière l'intersection d'un rayon ou d'un segment de ligne dirigée avec un arbre kd est simple. La ligne est intersectée contre le plan de division du nœud et la valeur t de l'intersection est calculée. Si t est dans l'intervalle de la ligne, 0 <= t <= tmax, la ligne chevauche le plan et les deux enfants de l'arbre descendent récursivement. Sinon, seul le côté contenant l'origine du segment est visité récursivement.

Voici donc ce que j'ai: ( ouvrez l'image dans un nouvel onglet si vous ne voyez pas le lettrage)

L'arbre logique

Ici, le rayon orange traverse la scène 3D. Les x représentent l'intersection avec un plan. À GAUCHE, le rayon frappe:

• La face avant du cube englobant de la scène,
• Le (1) plan de division
• Le plan de séparation (2.2)
• Le côté droit du cube englobant de la scène

Mais voici ce qui se passerait, suivant naïvement la description de base d'Ericson ci-dessus:

• Test contre le plan de fendage (1). Ray frappe le plan de division (1), donc les enfants gauche et droit du plan de division (1) sont inclus dans le test suivant.
• Essai contre le plan de fendage (2.1). Ray frappe en fait cet avion (loin vers la droite) afin que les deux enfants soient inclus dans le prochain niveau de tests. (Ceci est contre-intuitif - ne devrait pas seulement inclure le nœud inférieur dans les tests ultérieurs)

Quelqu'un peut-il décrire ce qui se passe lorsque le rayon orange traverse correctement la scène?

C'est assez simple vraiment; l'essai contre le plan de fendage (2.1) devrait échouer pour les raisons suivantes:

Lorsque le rayon frappe le plan de division (1), vous "divisez le rayon", ou; vous définissez la tplage -pour laquelle elle est valide et continuez dans l'arborescence avec les parties résultantes.

Ainsi, lors de la vérification par rapport au plan (2.1), vous devez vérifier si seule la partie du rayon à gauche du plan (1) coupe le plan (2.1), ce qui n'est pas le cas. L'intersection "loin à droite" dont vous parlez a t> la tvaleur où vous divisez le rayon avec le plan (1).

J'espère que c'est assez clair.

Résumé: Les intersections rayons / plans suivantes doivent être effectuées uniquement avec la partie du rayon restante après l'avoir divisé avec le plan en question.