8
votes

Rasteriser un polygone 2D

J'ai besoin de créer un bitmap binaire à partir d'un polygone 2D fermé représenté comme une liste de points. Pourriez-vous s'il vous plaît me signaler des algorithmes efficaces et suffisamment simples de faire cela, ou encore mieux, certains CODE C ++?

Merci beaucoup!

PS: J'aimerais éviter d'ajouter une dépendance à mon projet. Toutefois, si vous suggérez une bibliothèque open source, je peux toujours regarder le code, afin que cela puisse être utile aussi.

algorithm c++ geometry graphics rasterizing

0 commentaires

4 Réponses :

13
votes

La phrase Google magique que vous souhaitez soit "règle d'enroulement non nulle" ou "Remplissage de polygone pair".

Voir les entrées Wikipedia pour:

règle d'enroulement non nul
Remplir de polygone pair
Les deux sont très faciles à mettre en œuvre et suffisamment rapides à la plupart des fins. Avec une certaine intelligence, ils peuvent également être fabriqués de manière antialiasée.

4 commentaires

@plinth: n'est-ce pas sur-tuer pour des polygones simples?

Qu'est-ce qu'un simple polygone? @STICTIC_RTTI ne spécifie pas le nombre de points ou si les polygones seront toujours convexes, une solution générale est donc la bonne réponse. NZW et EO sont des fesses simples et se prêtent à des solutions orientées numériques, etc., etc., etc.

@plinth: Merci, c'est exactement ce que je cherchais! Des trucs Googling peuvent être délicats quand vous n'avez pas cette phrase magique :-)

@plinth: Un simple polygone est celui dont les segments ne se croisent pas. Voir EN.Wikipedia.org/wiki/simple_polygon

3
votes

Triangulez votre polygone
raster chacun des triangles (si vous utilisez un GPU, il peut plutôt le faire pour vous, c'est une opération primitive des GPU)
- Si le triangle n'a pas de segment qui est parallèle à l'axe X, alors rompez-la en deux triangles avec une ligne parallèle à l'axe X et passe à travers son point de médiane-y
- La tâche restante est maintenant de dessiner un triangle qui a un segment parallèle à l'axe X. Un tel triangle a un segment gauche et un segment de droite
- Itéréez les lignes de balayage du triangle (min-y à max-y). Pour chaque y calculer les points de gauche et droit des points segments dans cette ligne de balayage. Remplissez le segment de la ligne de scanner ces deux points (un simple memset).
  La complexité est O (zone en pixels)

5 commentaires

Comment rasérez-vous les triangles obtenus? Un par un en parcourant toute l'image à chaque fois? N'est-ce pas susceptible d'être très lent?

@STICTIC_RTTI: Que voulez-vous dire traverser toute l'image à chaque fois?

@STICTIC_RTTI: J'ai ajouté une explication de la façon de rasteriser un triangle

Le point crucial ici est "Calculer les segments gauche et droit". Le faire séparément pour chaque ligne de balayage est prohibitif lente; Un meilleur moyen est de calculer l'incrément et de l'appliquer à la valeur de départ.

Je pense que cette réponse glousse sur la complexité impliquée dans la triangulation du polygone. Pour de simples polygones, ce n'est pas si mauvais. Mais pour les polygones auto-intersectés, cela est plutôt impliqué. - Voir angusj.com/delphi/clipper.php à titre d'exemple.

6
votes

Vous pouvez consulter la routine de remplissage de polygone dans Pygame. Regardez le 1 commentaires

Pas trop liée mais BTW Pete Vous êtes génial pour faire pygame :)

4
votes

Pour une implantation robuste du "Règle pair"

voir Remplissage efficace de polygone de Darel Rex Finley , ou Version de Blender de celui-ci.

Il s'agit d'une méthode de remplissage impair / voire qui prend en charge les lignes d'auto-intersection, sans avoir besoin de code complexe pour détecter de telles situations et ne dépend pas de l'enroulement (le polygone peut être inversé et donner les mêmes résultats) .

Mise à jour, j'ai créé une version optimisée de la méthode de Darel Rex qui évite de boucler sur toutes les coordonnées pour chaque y-pixel.
implémentations autonomes autonomes:

C99 .
rouille (avec des tests ).
tandis que SPEEDUP sera probablement exponentiel, à partir d'un test rapide, environ 7,5 fois plus vite (11x lors de la suppression de rond appel), à l'aide d'un gribouillage dessiné arbitraire sur une région 2540x1600, YMMV .

0 commentaires

Articles qui pourrait vous intéresser : Calculer la différence dans l'échelle d'évaluation alphabétique Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000 Ma vérification pour savoir si un graphique est un arbre binaire renvoie toujours faux Comment trouver le nombre d'itérations de l'algorithme de recherche binaire?