WO1989006033A3 - Procede de tessellage d'une figure dans un systeme de representation graphique - Google Patents

Abstract

Le procédé décrit sert à tracer une figure géométrique convexe dans une mémoire de tampon de trame adressable séquentiellement sous la forme de plusieurs réseaux de mise à jour d'origines déterminées qui recouvrent par tessellage le tampon de trame. Un réseau comprend des sites de stockage de pixels, qui peuvent être chacun spécifié par un déplacement depuis l'origine du réseau et qui peuvent être mis à jour simultanément. Une figure est spécifiée comme constituant un groupe de lignes orientées, dont des segments placés entre des intersections mutuelles comprennent la limite de la figure, en parcourant la limite dans un seul sens. La figure est recouverte par tessellage au moyen d'un sous-ensemble de réseaux de mis à jour. L'accès à un premier réseau est sollicité. On effectue des tests pour déterminer si la figure s'étend vers des résaux se trouvant au-dessus ou au-dessous du réseau ayant fait l'objet d'un accès. Si c'est la cas, l'adresse du réseau est stockée et marquée pour l'une et/ou ou l'autre des extensions. Dans un mode de réalisation, on effectue un test pour l'extension gauche et les étapes sont répétées jusqu'à ce qu'on ne trouve aucune autre extension gauche. Après retour au réseau initial, on répète les étapes pour l'extension droite, afin de compléter le sous-ensemble horizontal. L'accès au résau marqué pour l'extension supérieure ou inférieure est ensuite sollicité et les étapes sont répétées pour le réseau verticalement adjacent indiqué jusqu'à ce qu'on ne trouve aucune autre extension dans cette direction verticale. Les étapes sont répétées pour l'autre direction verticale, jusqu'à ce que la figure soit entièrement recouverte par tessellage. Le test des extensions permet de vérifier la juxtaposition de chaque pixel échantillon dans une paire de pixels échantillons adjacente au réseau interrogé par rapport à chacune des lignes orientées.