L'algorithme de Sutherland-Hodgman est un algorithme utilisé en infographie pour le clipping de polygones. Son principe consiste à étendre chaque segment du polygone de sélection et à ne garder du polygone sujet que les faces situées dans le côté visible.
L'algorithme de Algorithme de Sutherland-Hodgman commence par une liste d'entrées contenant tous les sommets du polygone cible. Ensuite, un côté du polygone de découpage est étendu indéfiniment dans les deux directions, et le tracé du polygone cible est parcouru. Les sommets de la liste d'entrée sont insérés dans une liste de sortie s'ils se trouvent du côté visible du polygone de découpage étendu, et de nouveaux sommets sont ajoutés à la liste de sortie aux endroits où le tracé du polygone cible croise ce polygone.
Ce processus est répété itérativement pour chaque côté du polygone de découpage, en utilisant la liste de sortie d'une étape comme liste d'entrée pour la suivante. Une fois tous les côtés du polygone de découpage traités, la liste finale de sommets générée définit un nouveau polygone unique entièrement visible. Notez que si le polygone cible était concave au niveau de sommets situés à l'extérieur du polygone de découpage, le nouveau polygone peut présenter des arêtes coïncidentes (c'est-à-dire superposées) ; ceci est acceptable pour le rendu, mais pas pour d'autres applications telles que le calcul des ombres.
Toutes les étapes pour découper un polygone concave en forme de «W» avec un polygone convexe à 5 côtés
L'algorithme de Weiler-Atherton(en) résout ce problème en renvoyant un ensemble de polygones divisés, mais il est plus complexe et plus gourmand en ressources de calcul. C'est pourquoi l'algorithme de Sutherland-Hodgman est utilisé dans de nombreuses applications de rendu. Il peut également être étendu à l'espace 3D en découpant les trajectoires des polygones selon les limites des plans définis par l'espace de visualisation.
Bibliographie
(en) Mel Slater, Anthony Steed, Yiorgos Chrysanthou: Computer Graphics and Virtual Environments: From Realism to Real-Time. Addison Wesley, 2002. (ISBN0-201-62420-6).
