Brevet FR2622320A1 — publié le 19890428

I OPERATEUR D'INTERPOLATION LINEAIRE La présente invention concerne un opérateur d'interpola- tion linéaire, c'est-à-dire un dispositif de calcul permettant, si l'on considère qu'une valeur y est une fonction linéaire de x et que l'on connait les valeurs de y (Y1 et y2) correspondant à deux valeurs particulières de x (x1 et x2) de trouver la valeur de y correspondant à toute valeur de x choisie comprise dans l'inter- valle [xl, x2[. Un tel opérateur d'interpolation linéaire trouve notam- ment des applications dans le domaine des appareils graphiques de synthèse d'image bi- ou tri-dimensionnelle pour le tracé de vec- teurs, le lissage de couleurs (Gouraud), le lissage de normales (Phong), le lissage de formes (S-plines), le lancé de rayons, et plus généralement dans le traitement numérique du signal. En termes mathématiques, une interpolation linéaire se traduit par l'expression suivante: Y = Yl + (x - xl)(y2 - yl)/(x2 - x1) (1) D'autre part, la présente invention vise à résoudre des calculs du type y = (aA + bB) / (a + b) et A * B / C. Selon les techniques de l'art antérieur, toutes ces opérations exigent l'emploi de dispositifs de calcul, logiciels ou matériels, utilisant une durée de calcul de l'ordre de celle de trois multiplications (de façon générale, la durée d'une division est sensiblement identique à celle de deux multiplications). Un objet de la présente invention est de prévoir un opérateur d'interpolation linéaire permettant d'effectuer les calculs susmentionnés (et des calculs analogues et dérivés) en une durée de l'ordre de celle d'une seule multiplication. Pour atteindre cet objet, la présente invention prévoit un opérateur d'interpolation linéaire pour déterminer la valeur y d'une fonction de x quand on connatt une valeur Y1 correspondant à xl, et une valeur Y2 correspondant à x2 (x2 > xl), comprenant des premiers moyens de calcul de (xm + xM)/2, (avec xm ' XM, valeur initiale de xm = xl, valeur initiale de xM = x2); des seconds moyens de calcul de (ym + YM)/2, (valeur initiale de Ym = Y1, et valeur initiale de YM = Y2); des moyens de comparaison de x à (xm + xM)/2 pour déterminer lequel des intervalles [Xm, (Xm + xM)/2[, [(xm + xM)/2, XM[ contient x et renvoyer les limites de l'inter- valle sélectionné dans les premiers moyens de calcul et les limi- tes de l'intervalle correspondant en y dans les deuxièmes moyens de calcul; et des moyens de sortie fournissant en tant que valeur y recherchée la sortie des seconds moyens de calcul après un nom- bre de cycles choisi. Ainsi, selon la présente invention, on remplace des opérations de multiplications successives par des opérations de type logique en nombre sensiblement égal à celui d'une seule multiplication. En outre, le matériel constituant l'opérateur est considérablement simplifié par rapport aux dispositifs de l'art antérieur. En outre, on notera que l'opérateur selon la présente invention peut être mis en oeuvre de diverses façons, par exemple par un logiciel ou par différents types de dispositifs câblés. Ces objets, caractéristiques et avantages ainsi que d'autres de la présente invention seront exposés plus en détail dans la description suivante de modes de réalisation particuliers faite en relation avec les figures jointes parmi lesquelles: la figure 1 est un organigramme illustrant le procédé mis en oeuvre par un opérateur selon la présente invention; la figure 2 représente schématiquement le fonctionnement d'un opérateur selon la présent invention; et la figure 3 illustre un opérateur sous forme d'un dispo- sitif câblé à fonctionnement synchrone. Comme le représente la figure 1, l'organigramme du procédé selon la présente invention commence par un bloc d'initia- lisation 100 au niveau duquel on-introduit les données initiales xl, x2, Yl, Y2, et x. Au niveau du bloc 101, on calcule la demi- somme (xm + xM)/2 de la valeur minimale et de la valeur maximale de x, en l'occurence, au début, (x1 + x2)/2. Et l'on calcule parallèlement (ym + YM)/2, initialement (Y1 + Y2)/2. Au bloc 102, on détermine si (xm + xM)/2 est supérieur à x. Si la réponse est NON, on passe au bloc 103 o l'on pose que la nouvelle valeur de xm est (xm + xM)/2, que la valeur de xM est inchangée, que la nouvelle valeur de Ym est (ym + YM)/2 et que yM est inchangé. Si la réponse est OUI, on passe au bloc 104 o l'on fixe que xm est inchangé, que la nouvelle valeur de xM est (xm + xM)/2, que Ym est inchangé et que la nouvelle valeur de YM est (ym + YM)/2. Au bloc 105, on détermine si la différence entre la nou- velle valeur de YM et la nouvelle valeur de Ym est inférieure à un seuil prédéterminé. Si la réponse est NON, on revient au bloc 101 et l'on recommence un cycle. Si la réponse est OUI, on fournit un résultat y = (ym + YM)/2 au bloc 106 et le calcul s'achève au bloc de fin 107. Le procédé soustendu par l'organigramme de la figure 1 peut être mis en oeuvre par des moyens purement logiciels ou par des moyens matériels. Les figures 2 et 3 illustrent des exemples de mise en oeuvre du procédé selon la présente invention par des' moyens matériels. L'opérateur algorithmique de la figure 2 est directement dérivé de l'organigramme de la figure 1. En figure 2, il est prévu initialement quatre registres 201, 202, 203 et 204 destinés à recevoir respectivement les valeurs xm, XM, Ym' YM, c'est-à-dire initialement les valeurs xl, x2, Y1, Y2. Des dispositifs de som- mation 205 et 206 effectuent respectivement la somme des valeurs Xm + XM et Ym + YM' Les résultats de sommation sont divisés par 2 dans des diviseurs respectifs 207 et 208. Un comparateur 209 compare la sortie du diviseur 207 à la valeur x pour laquelle on cherche la valeur y correspondante. Selon le résultat de la com- paraison, des portes 210 et 211 envoient la sortie du diviseur par 2 207 vers l'un ou l'autre des registres 201 ou 202, le contenu de l'autre registre restant inchangé et, parallèlement, des portes 212 et 213 envoient la sortie du diviseur par deux 208 vers le registre 203 ou 204, l'autre registre gardant la valeur précédente inchangée. On n'a pas représenté en figure 2 de moyens d'horloge destines à synchroniser le fonctionnement des divers registres, ceci étant bien connu de l'homme de l'art. On n'a pas non plus représenté de moyens destinés à assurer l'arrêt du cycle et la fourniture à un instant donné du signal y de sortie du diviseur par 2 208 quand l'itération a été poursuivie un nombre de cycles suffisant. Cette fin de cycle peut être déterminée par le choix systématique d'un nombre de cycles prédéterminé, par une comparai- son entre les valeurs YM et Ym' ou par une comparaison entre l'une et/ou l'autre des valeurs xm et xM à la valeur x. On notera que les seuls calculs effectués par l'opéra- teur de la figure 2 sont une addition et une division par 2, ces opérations étant particulièrement simples dans le système binaire, et la durée d'un certain nombre N d'additions correspondant à la durée d'une seule multiplication de nombres à N bits. La figure 3 représente une variante de mise en oeuvre de la présente invention dans laquelle, au lieu d'utiliser N cycles de fonctionnement d'un opérateur tel que celui de la figure 2, on utilise un opérateur de type pipe-line à N étages. Des données peuvent donc être introduites successivement au rythme d'une horloge dans le premier étage tandis que les résultats successifs sont obtenus au niveau du N-ième étage. Chaque étage comprend des - registres d'entrée 301 à 304 correspondant aux registres 201 à 204 de la figure 2, des additionneurs 305 et 306 correspondant aux additionneurs 205 et 206, des diviseurs par 2 307 et 308 corres- pondant aux diviseurs 207 et 208, et un comparateur 309 correspon- dant au comparateur 209. Le comparateur 309 reçoit la valeur x à partir d'un cinquième registre d'entrée 310. Ce comparateur four- nit des signaux de commande à des circuits d'aiguillage 311 à 314 dont chacun fournit selon le résultat de la comparaison, ou bien la sortie du registre d'entrée correspondant ou bien la sortie du diviseur 307 ou 308, c'est-à-dire la demi somme des contenus des registres d'entrée. Les étages suivants (2 à N), sont tous identiques au premier et l'on recueille à la sortie du dernier étage la valeur y -recherchée. De même que dans le cas précédent, ce circuit est muni de moyens d'horloge nécessaires à sa synchronisation. On notera, qu'au lieu de prévoir un opérateur pipe-line avec des registres intermédiaires, on pourrait prévoir un opéra- teur à fonctionnement asynchrone mais, en ce cas, il faudrait cha- que fois attendre le résultat des calculs des N étages avant d'effectuer une nouvelle opération. Bien entendu, les opérateurs illustrés en figures 2 et 3 peuvent se prêter à de nombreuses variantes de réalisation. L'invention trouve un domaine d'application particuliè- rement intéressant par rapport aux systèmes de l'art antérieur quand on est amené à interpoler simultanément plusieurs variables en fonction de la variation d'un même paramètre. C'est notamment le cas des applications graphiques tridimentionnelles o l'on cherche à interpoler une dimension z en même temps que la dimen- sion y et/ou dans le cas d'images polychromes. On cherchera par exemple à interpoler en même temps que les coordonnées spatiales y et z trois paramètres de couleur R (rouge), Y (jaune) et B (bleu). Pour ce faire, en reprenant les figures 2 et 3, on ajoutera en plus du bloc de calcul de y un bloc de calcul pour chacun de ces autres paramètres, commandé par le même signal de sortie de compa- rateur (respectivement 209 et 309). D'autre part, comme cela a été indiqué en tête de la présente demande, de tels op&rateurs permettent par une sélection convenable des valeurs d'entrée d'effectuer des calculs autres que des calculs d'interpolation linéaire par exemple des calculs bary- centriques, ou du type rapport de deux produits. I1 est d'ailleurs clair que si l'on peut faire l'opération A * B / C on peut égale- ment faire les opérations A/C, A/B et 1/C. Il ne semble pas qu'il y a un avantage notable à utiliser un opérateur selon la présente invention pour faire ces dernières opérations, mais c'est un avan- tage de cet opérateur que de présenter une grande souplesse et de permettre d'effectuer divers types de calculs.- Pour un calcul du type barycentrique, c'est-à-dire y = (aA + bB)(A + B), on choisira comme valeurs des paramètres d'entrée: 1= 0; x2 = a + b; Y1 = A; Y2 = B et x = b. On a bien alors, en reprenant la formule (1): y = A + (b - 0)(B - A)/(a + b - 0) = (aA + bA + bB - bA)/(a + b) = (aA + bB)/(a + b) Pour le calcul d'un produit de deux nombres (A et B) suivi d'une division par un troisième (C) on choisira comme va- leurs des paramètres d'entrée: xi = 0; x2 = C; Y1 = 0; Y2 = B et x = A. On a bien alors en reprenant la formule (1): y = O + (A- O)(B - 0)/(C -O) = AB/C. REVENDICATIONS 1. Opérateur d'interpolation linéaire pour déterminer la valeur y d'une fonction de x quand on connait une valeur Y1 correspondant à xl, et une valeur Y2 correspondant à x2 (avec xi des moyens de comparaison de x à (xm + xM)/2 pour déter- miner lequel des intervalles [xm,(xm + xM)/2[, [(xm + XM)/2, XM[ contient x et renvoyer les limites de l'intervalle sélectionné dans les premiers moyens de calcul et les limites de l'intervalle correspondant en y dans les deuxièmes moyens de calcul; et des moyens de sortie fournissant en tant que valeur y recherchée la sortie des seconds moyens de calcul après un nombre de cycles choisi. 2. Opérateur d'interpolation linéaire selon la revendi- cation 1, caractérisé en ce que: les premiers moyens de calcul comprennent des registres d'entrée (201, 202; 301, 302), un additionneur (205; 305), un diviseur par 2 (207; 307); les seconds moyens de calcul comprennent des registres d'entrée (203, 204; 303, 304), un additionneur (206; 306), un diviseur par 2 (208; 308); les moyens de comparaison comprennent un comparateur (209; 309) recevant, d'une part, la sortie du diviseur par 2, d'autre part, le signal x et commandant des portes (210, 211; 212, 213) pour envoyer en fonction du résultat de la comparaison, la sortie du diviseur par 2 (207, 208; 307, 308), respectivement, vers l'un ou l'autre des registres d'entrée (201 à 204; 301 à 304), les autres registres gardant la valeur initialement reçue. 3. Opérateur d'interpolation linéaire selon la revendi- cation 2, caractérisé en ce que les mêmes moyens de calcul effec- tuent cycliquement des calculs. 4. Opérateur d'interpolation linéaire selon la revendi- cation 2, caractérisé en ce que les premiers et les seconds moyens de calcul, respectivement, sont connectés en pipe-line, la sortie d'un moyen de calcul étant envoyé vers le moyen de calcul immédia- tement suivant. 5. Application de l'opérateur selon l'une quelconque des revendications 1 à 4, à des calculs de type barycentrique dans lesquels on cherche à calculer y = (aA + bB)/(A + B), caractérisée en ce que l'on fixe comme valeur des paramètres: 1= 0; x2 = a + b; Y1 = A; Y2 = B et x = b. 6. Application de l'opérateur selon l'une quelconque des revendications 1 à 4, au calcul du produit de deux nombres A et B divisé par un troisième nombre C (y = A * B/C), caractérisée en ce que l'on fixe comme valeur des paramètres: x = 0; x2 = C; Y1 = O; Y2 = B et x = A.