J'ai des polygones convexes stockés comme un vecteur stl de points (plus ou moins). Je veux Tessellate eux vraiment rapidement, de préférence dans des morceaux de taille assez équitablement, et sans "ruisseau" .
Je vais l'utiliser pour exploser des objets en petits morceaux. Est-ce que quelqu'un connaît une belle bibliothèque pour tesseller des polygones (partitionner dans un maillage de polygones ou de triangles convexes plus petits)?
J'ai regardé quelques-uns j'ai déjà trouvé en ligne, mais je ne peux même pas les amener à compiler. Ce type académique ne donne pas grand-respect pour la facilité d'utilisation.
7 Réponses :
CGAL a des forfaits pour résoudre ce problème. Le meilleur serait probablement d'utiliser le Partitionnement 2D Polygon A > paquet. Par exemple, vous pouvez générer une partition Y-monotone d'un polygone (fonctionne pour des polygones non convexes, aussi bien) et vous obtiendrez quelque chose comme ceci: Le temps de course est O (n journal n). p> en termes de facilité d'utilisation Ceci est un petit code d'exemple Génération d'un polygone aléatoire et partitionnez-le (basé sur Ce manuel Exemple ): p> 
p> typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K> Traits;
typedef Traits::Point_2 Point_2;
typedef Traits::Polygon_2 Polygon_2;
typedef std::list<Polygon_2> Polygon_list;
typedef CGAL::Creator_uniform_2<int, Point_2> Creator;
typedef CGAL::Random_points_in_square_2<Point_2, Creator> Point_generator;
int main( )
{
Polygon_2 polygon;
Polygon_list partition_polys;
CGAL::random_polygon_2(50, std::back_inserter(polygon),
Point_generator(100));
CGAL::y_monotone_partition_2(polygon.vertices_begin(),
polygon.vertices_end(),
std::back_inserter(partition_polys));
// at this point partition_polys contains the partition of the input polygons
return 0;
}
J'essayais réellement cgal avant ... c'est moche comme l'enfer. Il suffit de regarder ces typefs! Peut-être que je vais lui donner un autre. Partitionnement que j'ai déjà eu cependant. La tessellation est un peu différente, à moins que je n'ai mélangé ma terminologie. Je veux un maillage fin, pas seulement convexer des polies de la taille aléatoirement; dont ces 2 ont l'air assez terrible. Trop de rubases.
Vous avez écrit "Vous n'êtes pas inquiet de la qualité du maillage", alors je pensais que cette partition serait ce que vous recherchez. Voulez-vous trianguler un polygone de telle sorte que vous ayez un contrôle sur la qualité et la taille des triangles? Si vous avez une question, vous pouvez regarder dans ce package ci-dessus: cgal .org / manuel / 3.3 / doc_html / cgal_Manual / maillage_2 / ...
Err ... désolé, par la qualité, je voulais dire que je ne suis pas aussi difficile à leur sujet, tous les angles étant au moins une certaine mesure ou ayant des tailles totalement cohérentes sur toutes les subdivisions ... elle fait cependant, besoin de produire une sorte de maillage. J'aurais dû faire cela plus clair. Ce dernier lien ressemble beaucoup plus à ce que je veux. Merci!
Si vous souhaitez éviter les ruraux (comme vous l'avez écrit dans votre premier commentaire), cela signifie implicitement que vous préférez une liaison sur l'angle minimum. Voulez-vous quelque chose comme ça? www-sop.inria.fr/members/jane.tournois/ Images / Seattle_big.pn g Cette image et l'emballage de maillage 2D CGAL reposent sur une méthode appelée raffinement de Delaunay. Et il y a un autre générateur OpenSource Delaunay Mesh ici: CS.CMU.EDU/~QUAKE/ triangle.html , aussi.
Un peu plus de détails sur votre entrée et votre sortie souhaités peut être utile.
Par exemple, si vous essayez simplement d'obtenir les polygones dans les triangles, un fan de triangle fonctionnerait probablement. Si vous essayez de couper un polygone en petits morceaux, vous pouvez mettre en œuvre une sorte de carrés de marche.
D'accord, j'ai fait une mauvaise hypothèse - j'ai supposé que les carrés de marche seraient plus similaires aux cubes de marche. S'avère que c'est assez différent, et pas ce que je voulais dire du tout ..: |
Dans tous les cas, pour répondre directement à votre question, je ne connais aucune bibliothèque simple qui fait ce que vous recherchez. Je suis d'accord sur la convivialité de CGAL.
L'algorithme que j'avais pensé était fondamentalement des polygones avec des lignes, où les lignes sont une grille, vous obtenez donc surtout des quads. Si vous aviez une intersection de la ligne polygone, la mise en œuvre serait simple. Une autre façon de poser ce problème traite du polygone 2D comme une fonction et de superposer une grille de points. Ensuite, vous venez de faire quelque chose de similaire à la marche des cubes de marche. Si tous les 4 points sont dans le polygone, faites un quad, si 3 sont en train de faire un triangle, 2 sont en train de faire un rectangle, etc. Probablement surpoids. Si vous vouliez des polygones légèrement irréguliers, vous pouvez randomiser les emplacements des points de grille.
D'autre part, vous pouvez faire une subdivision de style Catmull-Clark, mais omettez le lissage. L'algorithme est fondamentalement que vous ajoutez un point au centroïde et au milieu de chaque bord. Ensuite, pour chaque coin du polygone d'origine, vous établissez un nouveau polygone plus petit qui relie le point médiocre de bord précédent dans le coin, le coin, le point central de bord suivant et le centroïde. Cela dose l'espace et aura des angles similaires à votre polygone d'entrée.
Donc, beaucoup d'options, et j'aime les solutions de brainstorming, mais je n'ai toujours aucune idée de ce que vous envisagez d'utiliser cela pour. Est-ce pour créer des mailles destructibles? Faites-vous une sorte de traitement de maille qui nécessite des éléments plus petits? Essayer d'éviter les artefacts d'ombrage de Gouraud? Est-ce quelque chose qui fonctionne comme pré-processus ou en temps réel? Quelle est l'importance de l'exactitude? Plus d'informations entraîneraient de meilleures suggestions.
Eh bien, comme je l'ai dit, j'explose des formes dans de petites bits. Je ne suis pas préoccupé par les bits parfaitement de taille uniforme, mais ils devraient toujours être des morceaux, pas des triangles allongés. Je ne vois pas à quel point les carrés de marche sont du tout pertinents ... est-ce que non pas pour transformer les bitmaps dans des polygones essentiellement?
Meshes destructibles, oui. Je pensais que je l'ai mentionné. Sera fait en temps réel, mais espérons-le, pas tous les cadres :) C'est pour un jeu ... Juste lorsque deux objets se heurtent fort, je veux qu'ils explosent. Je vais prendre en compte vos suggestions, merci!
Si vous ne voulez pas construire l'ensemble de GCAL dans votre application - c'est probablement plus simple à mettre en œuvre.
http://www.flipcode.com/archives/efficient_polygon_triangulation.shtml
FWIW, ce code Tessellate de flipcode est excellent. Rapide et correct pour des polygones arbitrairement complexes.
Comme Balint.Miklos mentionné dans un commentaire ci-dessus, le Shewchuk's Triangle Le paquet est assez bon. Je l'ai utilisé à plusieurs reprises; Il s'intègre bien dans des projets et il y a le Triangle ++ interface C ++. Si vous souhaitez éviter les rubans, laissez le triangle d'ajouter des points (intérieurs) Steiner, de sorte que vous générez un maillage de qualité (généralement une triangulation de Delaunay conforme contrainte).
Si vous avez des polygones convexes, et que vous n'êtes pas trop raccroché sur la qualité, c'est vraiment simple - juste faire Si vous voulez un triangulateur plus robuste basé sur une coupure d'oreille, consultez Fist .
Je suis au courant de l'écrouement des oreilles, mais cela ne produit pas de très bons résultats, comme vous l'avez souligné. Mais merci :)
Poly2tri ressemble à une très belle bibliothèque C ++ léger pour 2D Delaunay Triangulation.
Voulez-vous simplement ajouter que Poly2tri ne prend pas en charge les polygones d'auto-intersection.
Je viens de commencer à regarder dans ce même problème et que je considère la tessellation de Voronoi. Le polygone d'origine obtiendra une dispersion de points semi-aléatoires qui seront les centres des cellules Voronoi, plus ils sont répartis de manière uniformément les cellules les plus régulières des cellules, mais elles ne devraient pas être dans une grille parfaite sinon les polygones d'intérieur va tous regarder la même chose. Donc, la première chose à faire est de pouvoir générer ces points de centre de cellule - les générer sur la boîte à bornes du polygone source et un test intérieur / extérieur ne doit pas être trop difficile.
Les bords Voronoi sont les lignes pointillées de cette image et sont en quelque sorte le complément de la triangulation Delaunay. Tous les points triangle tranchants deviennent émoussés:
Boost a une fonctionnalité Voronoi: http://www.boost.org/doc/ LIBS / 1_55_0 / LIBS / POLYGON / DOC / VORONOI_BASIC_TURTORIAL.HTM
La prochaine étape consiste à créer les polygones Voronoi. Voro ++ http://math.lbl.gov/voro++/ est orienté 3D mais il est suggéré ailleurs Cette structure d'environ 2D fonctionnera, mais être beaucoup plus lente que les logiciels orientés vers 2D Voronoi. L'autre forfait qui semble être beaucoup mieux qu'un projet d'orphelinisme académique aléatoire est https://github.com/ Anewallin / Openvoronoi .
On dirait que OpenCv était utilisé pour soutenir faire quelque chose sur ces lignes, mais elle a été obsolète (mais la C-API fonctionne toujours?). CV :: DistTransform est toujours maintenu mais fonctionne sur des pixels et génère des sorties de pixels, pas des vertices et des structures de données de polygone de bord, mais peut être suffisante pour mes besoins si ce n'est pas le vôtre.
Je vais mettre à jour cela une fois que j'ai appris plus.
