Y a-t-il des structures de données éprouvées pour l'emplacement de point dans les mailles de tétraèdre où les tétraèdres sont tous disjoints mais "se toucher" mutuellement? C'est à dire. La plupart des visages sont des faces de deux tétraèdres exactement.
par emplacementi signifie que je veux savoir dans lequel des tétraèdres un point donné est situé, ou s'il n'est pas situé dans n'importe quel.
Jusqu'à présent, j'ai essayé:
un simple kd-arbre. C'était beaucoup trop lent pour mes besoins, car la profondeur moyenne de l'arbre était très élevée et que j'ai encore eu beaucoup de tétraènes individuels à tester dans chaque feuille.
une grille qui contenait tout le tétraèdre intersectant pour chaque cellule. Cela semble fonctionner beaucoup mieux, mais n'était toujours pas assez rapide. Premièrement, la grille contenait beaucoup de cellules vides car mon maillage global n'est pas très "boxy". Deuxièmement, la plupart des cellules contenaient en réalité des tétraèdres, en contiennent beaucoup (10+). Je suppose que c'est parce que beaucoup de tétraèdre partagent chaque sommet, et dès qu'un sommet est dans une cellule, tous ses tétraèdres adjacents sont également.
Quelques informations supplémentaires sur les données d'entrée: le maillage n'est généralement pas convexe et peut avoir des trous ou des inclusions. Bien que les deux derniers soient quelque peu improbables, je dois traiter avec eux, ce qui rend "marcher" impossible sans (coûteux et compliqué?) Prétraitement.
3 Réponses :
Ceci est certes un peu brainstormy.
Peut-être une coutume d'un kdtree qui utilise des plans alignés face à face au lieu des axis-alignés.
Si un point est sur le côté "correct" des quatre plans d'un tétraèdre, il doit être à l'intérieur du tétraèdre. (Droite?) Et si vous êtes du mauvais côté de n'importe quel avion, vous pouvez non seulement exclure le TET actuel, mais aussi les autres sur ce côté de l'avion.
Il semble que vous devriez pouvoir construire un arbre dans lequel chaque nœud est un seul plan, et un nœud de feuille signifie que vous êtes dans un TET spécifique (en supposant que les TET ne soient jamais intersect). L'arbre peut être profond, mais puisque chaque test est uniquement contre un plan (plutôt qu'un test triangulaire plus coûteux) et puisqu'un nœud de feuille vous donne exactement une réponse, il semble que cela devrait être rapide.
Construire efficacement l'arbre peut s'avérer difficile.
N'est-ce pas juste un arbre BSP ordinaire alors? Beaucoup de fractionnement ou de duplication devraient arriver
@LTJAX: Non, ce n'est pas un BSP ordinaire. Avec un arbre BSP ordinaire, vous traversez une feuille qui vous donne une liste de ternettes à tester. Avec l'approche que j'essaie de décrire, traverser l'arborescence à un beat vous donne un TET spécifique que le point est dans ou une indication que le point n'est dans aucun TET. Il combine la partition avec les tests contre un TET.
C'est toujours assez ordinaire. Je suppose que la quantité de duplication et la profondeur moyenne de l'arbre rendent cela irréalisable cependant. Rappelez-vous que si vous divisez un tétraèdre, vous risquez de vous retrouver avec six tétraèdres. Et vous obtiendrez de nombreux problèmes de précision construire l'arbre à moins que vous n'utilisiez quelque chose de plus «orthogonal» comme un kd-arbre ou un octree.
Je ne suis pas sûr de comprendre votre commentaire sur la division d'un tétraèdre. Ce ne seraient pas des avions arbitraires, mais les mêmes avions qui contiennent eux-mêmes les côtés de la tétraèdre eux-mêmes. Il n'y aurait pas de division impliqué. Chaque agglomération de l'arborescence règne efficacement les ternettes complètement de l'autre côté du plan d'essai. Pas de fractionnement requis.
Qu'en est-il de tétraèdre des deux côtés d'un avion sélectionné?
Quelques pensées rapides: un octree sera similaire à votre approche de la grille, mais vous permettra d'ignorer rapidement les grilles vides et de subdiviser les grilles trop pleines.
En outre, vous ne mentionnez pas comment vous testez si un point réside dans un tétraèdre. Cela fait longtemps que depuis que je l'ai regardé, mais peut-être coordonnées barycentriques Pourrait accélérer vos tests de points dans le tétraèdre? Ou un algorithme de balayage pour exclure rapidement les tétraèdres à base de sommets de tétraèdre qui sont clairement du mauvais côté de la ligne de balayage pour contenir le point.
J'utilise déjà des coordonnées barycentriques. Comment allez-vous appliquer une ligne de balayage ici?
Une méthode simple serait de trier les points sur leur coordonnée X. Tout tétraèdre dont les points ont tous des coordonnées X inférieur à la coordonnée X du point qui vous intéresse (de la même manière, toutes supérieures) ne pouvaient pas être le tétraèdre qui vous intéresse.
Si vous avez affaire à une triangulation 3D composée de tétra -édrons avec des informations de adjacence, vous pouvez simplement utiliser Pour plus d'informations, voir le papier Marcher dans une triangulation par Olivier Devillers et al. (Google it et vous trouverez un PDF de celui-ci.)
Avez-vous essayé ce qui suit (n'a pas pu trouver une référence, donc je le décris sous peu)? Commencer dans un TET arbitraire. Déterminez un visage, relativement à celui du point situé à l'extérieur du Tet (du côté opposé que le quatrième sommet Tet). Pas sur le Tet de l'autre côté du visage. Revérifier. S'il n'y a pas de visage tel, le point est dans le TET actuel. Cet algorithme fonctionne pour les mailles convexes. Est-ce que cela correspond à vos besoins?
Une autre pensée à ce sujet. Vous pouvez combiner les deux méthodes. Après avoir trouvé la cellule de grille correcte, vous pouvez rechercher le tet correct avec la méthode ci-dessus.
Cela semble soigné. Sûrement, vous pouvez le faire fonctionner pour des mailles non convexes en remplissant des concavités avec «vide» Tetrahedra?
Probablement, bien qu'il puisse être difficile de remplir les trous. Mais essayez-vous, si vous voulez.
Peut-être Arbre d'intervalle , dans votre cas, localise un plus petit nombre de tétrahédrons à tester. La profondeur est probablement comme dans KD-Tree.
Je ne sais pas quelle est votre demande et quel niveau de garantie que vous devez pouvoir faire, mais certaines techniques de recherche approximatives peuvent fonctionner très rapidement et qui ont de bonnes implémentations disponibles. En particulier, je regarderais Flann , qui est Une bibliothèque pour recherches approximatives de voisins les plus proches qui a reçu une attention particulière et une attention de performance. Cela n'effectuera que la recherche-point la plus proche, mais je pensais que cela serait bon de pointer comme une amélioration significative sur les arbres KD.
@ERIC: Qu'est-ce que la moyenne approximative dans ce contexte? Sera arbitrairement ne détectera-t-il pas le tetradron droit ou sera-t-il "flou" autour des bords?
Fondamentalement, cela signifie qu'il y a une chance que vous trouverez le deuxième plus proche au lieu du point le plus proche. FLANN a un paramètre réglable (précision de la cible) pour contrôler le compromis de vitesse / précision. Vous pouvez également consulter le ANN Bibliothèque si vous le souhaitez, qui a des implications efficaces de la recherche approximative et exacte du voisin le plus proche.