Algorithme pour déterminer si un point est à l'intérieur d'un maillage 3D

Qu'est ce qu'un algorithme rapide permettant de déterminer si un point est à l'intérieur d'un maillage 3D? Pour plus de simplicité vous pouvez supposer que le maillage est de tous les triangles et n'a pas de trous.

Ce que je sais, c'est que l'un des moyens populaires de déterminer si oui ou non un rayon a franchi un maillage consiste à compter le nombre de rayon/triangle intersections. Il doit être rapide, car je l'utilise pour une haptique à la simulation médicale. Donc je ne peut pas tester tous les triangles pour ray intersection. J'ai besoin d'une sorte de hachage ou d'un arbre de structure de données pour stocker les triangles pour les aider à déterminer les triangle sont pertinentes.

Aussi, je sais que si j'ai un quelconque arbitraire projection 2D des sommets, un simple point/triangle intersection de test est nécessaire. Cependant, j'ai encore besoin de savoir qui triangles sont pertinentes et, en outre, qui triangles mentir devant un le point et de tester ces triangles.

source d'informationauteur Jeff Jenkins

  1. 15

    J'ai résolu mon problème. En gros, je prends de l'arbitraire projection en 2D (jetez un des coordonnées), de hachage et de la AABBs (Axe Aligné Boîtes Englobantes) des triangles pour un tableau 2D. (Un ensemble de cubes 3D, comme mentionné par tite est exagéré, car il vous donne uniquement un facteur constant de l'accélération.) Utiliser le tableau 2D et la projection 2D du point à tester pour obtenir un petit ensemble de triangles, ce qui vous faire une 3D de rayon/triangle intersection de test (voir Les Intersections des Rayons, des Segments, des Avions et des Triangles en 3D) et de compter le nombre de triangles le rayon intersection où la coordonnée z (coordonnées jetée) est plus grande que la coordonnée z du point. Un même nombre d'intersections signifie qu'il est à l'extérieur de la maille. Un nombre impair d'intersections signifie qu'il est à l'intérieur de la maille. Cette méthode n'est pas seulement rapide, mais très facile à mettre en œuvre (ce qui est exactement ce que je cherchais).

  2. 3

    C'est l'algorithme est efficace seulement si vous avez beaucoup de requêtes pour justifier le temps nécessaire pour la construction de la structure de données.

    De diviser l'espace en cubes de même taille (nous allons trouver la taille plus tard). Pour chaque cube de savoir qui triangles a au moins un point. Jetez les cubes qui ne contiennent pas de quoi que ce soit. Faire une projection de rayons algorithme tel que présenté sur wikipédia, mais au lieu de o de tester si la ligne de coupe de chaque triangle, obtenir tous les cubes qui sont en intersection avec la ligne, et ensuite faire ray casting uniquement avec les triangles dans ces cubes. Attention de ne pas tester le même triangle plus d'une fois parce qu'il est présent dans les deux cubes.

    Trouver la bonne dimension du cube est délicat, il ne devrait pas être ni gros ni trop petit. Il ne peut être trouvée par essais et erreurs.
    Disons number of cubes est c et number of triangles est t.

    Le nombre moyen de triangles dans un cube est t/c

    k est le nombre moyen de cubes qui se croisent les rayons

    ligne-cube intersections + ligne-triangle d'intersection de ces cubes minimum

    c+k*t/c=minimal => c=sqrt(t*k)

    Vous aurez à tester les valeurs de la taille des cubes jusqu'à ce que c=sqrt(t*k) est vrai

    Un bon point de départ pour deviner la taille du cube serait sqrt(mesh width)

    Pour avoir un peu de perspective, pour 1M triangles vous aurez essai sur l'ordre de 1k intersections

  3. 0

    Ray Triangle Intersection semble être un bon algorithme quand il s'agit de l'exactitude de ce discussion. Le Wiki a quelques algorithmes. Je suis un lien ici, mais vous pourriez avoir vu déjà.

    Pouvez-vous, peut-être improviser, le maintien d'une matrice de relation entre les points et le plan à qui ils font les sommets? Ce sujet semble être un sujet de recherche dans le milieu universitaire. Vous ne savez pas comment accéder à de plus amples discussions relatives à cette.