SOUM, Christophe (18 rue Jean Richepin, Clermont-Ferrand, Clermont-Ferrand, F-63000, FR)
| Revendications 1. Moteur de génération d'images susceptible de générer des images pour une application hôte à partir de données procédurales sous forme de graphes séquentiels comportant des nœuds simples, des nœuds de résultats intermédiaires et des nœuds de résultats finaux, comprenant : - au moins un microprocesseur ; - une liste d'instructions ; - un module de parcours de graphe procédural séquentiel de génération d'image, adapté pour recevoir d'une application hôte au moins un graphe G procédural séquentiel de génération d'image et pour parcourir ce graphe et au moins une liste LO de rendus contenant les requêtes d'images à générer non encore satisfaites ; - un module de calcul de résultats intermédiaires, permettant de calculer des résultats intermédiaires correspondant à des nœuds du graphe procédural séquentiel de génération d'image ; - un module de calcul de temps de rendu de résultats intermédiaires ; - un module de calcul de poids des résultats intermédiaires ; - un module mémoire pour mémoriser le graphe G procédural séquentiel de génération d'image ; - un module mémoire mémoriser une liste LO de rendus contenant les requêtes d'images à générer reçue d'une application hôte et non encore satisfaites ; - un module mémoire pour mémoriser une liste L1 de résultats intermédiaires ; - un module mémoire pour mémoriser une liste L2 de temps de rendu des résultats intermédiaires ; - un module mémoire pour mémoriser une liste L3 de poids des résultats intermédiaires ; - un module mémoire pour mémoriser une liste M d'images résultats intermédiaires ; - un module de comparaison et de suppression, adapté pour comparer la capacité mémoire disponible pour la mémorisation de nouvelles données de résultats intermédiaires ou de données préalablement existantes à un seuil minimum donné, et pour supprimer des données de résultats intermédiaires si ladite capacité mémoire disponible pour la mémorisation de nouvelles données de résultats intermédiaires est inférieure audit seuil. 2. Moteur de génération d'images selon la revendication 1 , dans lequel le graphe est sous forme de liste avec indications des résultats intermédiaires prérequis à une étape donnée. 3. Procédé de génération d'images pour moteur de génération d'images susceptible de générer des images à partir de données procédurales sous forme de graphes séquentiels comportant des noeuds simples, des noeuds de résultats intermédiaires et des nœuds de résultats finaux, dans lequel le moteur de génération d'images : a) reçoit d'une application hôte au moins un graphe G procédural séquentiel de génération d'image et au moins une liste LO de rendus contenant les requêtes d'images à générer non encore satisfaites ; b) - établi une liste L1 de résultats intermédiaires pour stockage dans un module de liste de résultats intermédiaires ; c) - établi une liste L2 de temps de rendu des résultats intermédiaires pour stockage dans un module de liste de temps de rendu des résultats intermédiaires ; d) - établi une liste L3 de poids des résultats intermédiaires pour stockage dans un module de poids des résultats intermédiaires ; e) - établi une liste M d'images résultats intermédiaires pour stockage dans un module d'images de résultats intermédiaires ; et dans lequel lorsque, après obtention d'un nouveau résultat intermédiaire, le stockage des éléments correspondants entraînerait un dépassement de la capacité mémoire disponible, un module de comparaison et de suppression : f) - procède à l'identification du résultat intermédiaire de poids le plus faible ; g) - procède à la suppression de données correspondant au résultat intermédiaire de poids le plus faible identifié ; h) - procède à la vérification de l'espace mémoire disponible ; i) - si l'espace mémoire disponible est supérieur à un seuil minimum donné, le module de comparaison et de suppression cesse la suppression de données ; j)- si l'espace mémoire disponible est encore au-dessous du seuil minimum donné, le module de comparaison et de suppression poursuit le procédé à l'étape « f », jusqu'à ce que l'espace mémoire disponible soit sous ledit seuil. 4. Procédé de génération d'images selon la revendication 3, dans lequel le graphe est sous forme de liste avec indications des résultats intermédiaires prérequis à une étape donnée. 5. Procédé de génération d'images selon la revendication 4, dans lequel une modification de la liste L0 de rendus entraine un nouveau calcul des poids des résultats intermédiaires. 6. Procédé de génération d'images selon l'une des revendications 4 ou 5, dans lequel le module de calcul de poids des résultats intermédiaires effectue un tri de poids par ordre de poids croissants. 7. Procédé de génération d'images selon l'une des revendications 4 à 6, dans lequel le résultat intermédiaire nouvellement obtenu avant l'étape de suppression de données est pris en compte dans l'étape d'identification du résultat intermédiaire de poids le plus faible. 8. Procédé de génération d'images selon l'une des revendications 4 à 7, dans lequel le module de calcul de résultats intermédiaires détermine les résultats intermédiaires en fonction de la liste L0 de rendus. 9. Procédé de génération d'images selon l'une des revendications 4 à 8, dans lequel le module de calcul de poids effectue les calculs de poids en considérant la taille occupée par l'image résultat en mémoire. 10. Procédé de génération d'images selon l'une des revendications 4 à 9, dans lequel le module de calcul de poids effectue les calculs de poids en considérant la quantité de calculs requis pour calculer ledit résultat intermédiaire. 11. Procédé de génération d'images selon l'une des revendications 4 à 10, dans lequel le module de calcul de poids effectue les calculs de poids en considérant la distance temporelle avant réutilisation dudit résultat intermédiaire. 12. Procédé de génération d'images selon l'une des revendications 4 à 11 , dans lequel dans l'étape de suppression de données correspondant au résultat intermédiaire, le moteur de génération d'images effectue la suppression de données de l'image du résultat intermédiaire. 13. Procédé de génération d'images selon l'une des revendications 4 à 12, dans lequel dans l'étape de suppression de données correspondant au résultat intermédiaire, le moteur de génération d'images effectue la suppression de données parmi les listes L1 , L2 et L3. 14. Procédé de génération d'images selon l'une des revendications 4 à 13, dans lequel une modification du niveau de seuil minimum de mémoire disponible entraine un nouveau calcul de poids. |
CACHE
DOMAINE TECHNIQUE DE L'INVENTION
[0001] La présente invention concerne un moteur de génération d'images susceptible de générer des images pour une application hôte à partir de données procédurales sous forme de graphes séquentiels comportant des nœuds simples, des nœuds de résultats intermédiaires et des nœuds de résultats finaux. Elle concerne également un procédé de génération d'images correspondant.
ETAT DE LA TECHNIQUE ANTERIEURE
[0002] De nombreuses applications graphiques sont amenées à manier des quantités significatives de données consommant une place importante en mémoire et dont la manipulation nécessite un grand nombre de calculs complexes. De plus, certaines catégories d'applications graphiques interactives doivent autant que possible minimiser leur temps de réponse afin de fournir une expérience utilisateur satisfaisante : jeux vidéo, simulateurs d'entraînement, logiciels d'édition ou de composition vidéo. Ces applications dédient une part importante des ressources à la manipulation d'images appelées « textures », qui représentent par exemple l'aspect de surface d'un objet, un décor de fond, ou bien des masques de composition. Les textures sont non seulement utilisées pour stocker des informations de couleurs, mais également tout autre paramètre utile à l'application. Dans un jeu vidéo les textures stockent typiquement les couleurs, les petits reliefs de surface, ainsi que les coefficients de réflexion des matériaux.
[0003] L'édition, le stockage et l'affichage de ces textures sont des problèmes clés des applications graphiques. Généralement, les textures sont peintes par des infographistes, parfois à partir de photographies. Une fois peinte, la texture a une résolution figée et il est très difficile de l'adapter à un autre contexte. Les applications utilisant de plus en plus de textures, il devient très coûteux de peindre à la main suffisamment de textures différentes et il n'est pas rare d'observer des répétitions à l'écran. De plus, les textures sont stockées sous forme de grilles de pixels (points de couleur), que nous appellerons « bitmaps » par la suite. Même après compression, il est très coûteux de stocker ces informations sur un média de masse type DVD ou disque dur, et très lent de les transférer via un réseau. [0004] Bien entendu, certaines techniques ont été proposées pour répondre à ces difficultés, et en particulier la notion de « texture procédurale ». Selon ce concept, l'image est le résultat d'un calcul plutôt que peinte à la main. Sous certaines conditions, le calcul de l'image peut être effectué au dernier moment, juste avant l'affichage, limitant ainsi le besoin de stocker l'image entière. Il est également aisé d'introduire des variations dans les textures procédurales, évitant ainsi les répétitions. Cependant, les textures procédurales ne peuvent pas être facilement créées et manipulées par les infographistes, et leur utilisation reste limitée à quelques cas particuliers de matériaux. Malgré les nombreuses tentatives, aucun système n'a su offrir un outil complet permettant l'édition, la manipulation et l'affichage efficaces de textures procédurales.
[0005] Pour pallier ces différents inconvénients, l'invention prévoit différents moyens techniques.
EXPOSE DE L'INVENTION
[0006] Tout d'abord, un premier objet de l'invention consiste à prévoir un dispositif permettant d'optimiser la génération d'images et/ou de textures.
[0007] Un autre objet de l'invention consiste à prévoir un procédé permettant d'optimiser la génération d'images et/ou de textures.
[0008] Encore un autre objet de l'invention consiste à prévoir un procédé permettant de réutiliser et/ou de conserver des portions de calculs pour la génération de plusieurs séries d'images ou textures procédurales.
[0009] Encore un autre objet de l'invention consiste à prévoir un procédé de rendu de textures permettant un fonctionnement pour des applications en temps réel.
[0010] Pour ce faire, l'invention prévoit un moteur de génération d'images susceptible de générer des images pour une application hôte à partir de données procédurales sous forme de graphes séquentiels comportant des nœuds simples, des nœuds de résultats intermédiaires et des nœuds de résultats finaux, comprenant :
- au moins un microprocesseur ;
- une liste d'instructions ; - un module de parcours de graphe procédural séquentiel de génération d'image, adapté pour recevoir d'une application hôte au moins un graphe G procédural séquentiel de génération d'image et pour parcourir ce graphe et au moins une liste LO de rendus contenant les requêtes d'images à générer non encore satisfaites ;
- un module de calcul de résultats intermédiaires, permettant de calculer des résultats intermédiaires correspondant à des nœuds du graphe procédural séquentiel de génération d'image ;
- un module de calcul de temps de rendu de résultats intermédiaires ;
- un module de calcul de poids des résultats intermédiaires ;
- un module mémoire pour mémoriser le graphe G procédural séquentiel de génération d'image ;
- un module mémoire mémoriser une liste LO de rendus contenant les requêtes d'images à générer reçue d'une application hôte et non encore satisfaites ;
- un module mémoire pour mémoriser une liste L1 de résultats intermédiaires ;
- un module mémoire pour mémoriser une liste L2 de temps de rendu des résultats intermédiaires ;
- un module mémoire pour mémoriser une liste L3 de poids des résultats intermédiaires ;
- un module mémoire pour mémoriser une liste M d'images résultats intermédiaires ;
- un module de comparaison et de suppression, adapté pour comparer la capacité mémoire disponible pour la mémorisation de nouvelles données de résultats intermédiaires ou de données préalablement existantes à un seuil minimum donné, et pour supprimer des données de résultats intermédiaires si ladite capacité mémoire disponible pour la mémorisation de nouvelles données de résultats intermédiaires est inférieure audit seuil.
[0011] Grâce à ce type de dispositif, la vitesse de génération ou de rendu des images est fortement augmentée, rendant possible la réalisation de certains montages en temps réel, sans interruption ou encore avec des interruptions dont la durée est réduite.
[0012] Les résultats intermédiaires conservés sont utilisés pour tous les calculs ultérieurs de textures résultats pour lesquels ces résultats intermédiaires sont applicables. Les résultats non conservés sont recalculés lorsque nécessaire.
[0013] Dans un mode de réalisation avantageux, le graphe est sous forme de liste avec indications des résultats intermédiaires prérequis à une étape donnée. [0014] L'invention prévoit également un procédé de génération d'images pour moteur de génération d'images susceptible de générer des images à partir de données procédurales sous forme de graphes séquentiels comportant des nœuds simples, des nœuds de résultats intermédiaires et des nœuds de résultats finaux, dans lequel le moteur de génération d'images :
a) reçoit d'une application hôte au moins un graphe G procédural séquentiel de génération d'image et au moins une liste LO de rendus contenant les requêtes d'images à générer non encore satisfaites ;
b) - établi une liste L1 de résultats intermédiaires pour stockage dans un module de liste de résultats intermédiaires ;
c) - établi une liste L2 de temps de rendu des résultats intermédiaires pour stockage dans un module de liste de temps de rendu des résultats intermédiaires ;
d) - établi une liste L3 de poids des résultats intermédiaires pour stockage dans un module de poids des résultats intermédiaires ;
e) - établi une liste M d'images résultats intermédiaires pour stockage dans un module d'images de résultats intermédiaires ;
et dans lequel lorsque, après obtention d'un nouveau résultat intermédiaire, le stockage des éléments correspondants entraînerait un dépassement de la capacité mémoire disponible, un module de comparaison et de suppression :
f) - procède à l'identification du résultat intermédiaire de poids le plus faible ;
g) - procède à la suppression de données correspondant au résultat intermédiaire de poids le plus faible identifié ;
h) - procède à la vérification de l'espace mémoire disponible ;
i) - si l'espace mémoire disponible est supérieur à un seuil minimum donné, le module de comparaison et de suppression cesse la suppression de données ;
j)- si l'espace mémoire disponible est encore au-dessous du seuil minimum donné, le module de comparaison et de suppression poursuit le procédé à l'étape « f », jusqu'à ce que l'espace mémoire disponible soit sous ledit seuil.
[0015] La solution selon l'invention est basée sur le fait que les infographistes décrivent des textures à l'aide d'un outil dédié qui permet un fort contrôle sur l'aspect final des images. Cet outil encourage la réutilisation de morceaux d'images existants, et permet de générer une infinité de variations d'une texture de base. L'outil ne mémorise pas l'image finale, mais plutôt la description de l'image, c'est-à-dire les étapes successives qui permettent de la calculer. Dans l'immense majorité des cas, cette description est de taille très inférieure à l'image sous forme « bitmap ». De plus, la technologie de l'invention a été conçue pour permettre une génération très efficace des images sous forme « bitmap » à partir de leurs descriptions. Les descriptions issues de l'éditeur sont préparées pour être générées à l'exécution. Les applications n'ont besoin de connaître que ces descriptions retravaillées. Lorsque l'application hôte souhaite utiliser une texture, elle demande au composant de génération appelé « engine », de convertir la description retravaillée en image « bitmap ». Par la suite l'image « bitmap » est utilisée comme une image classique.
[0016] Ainsi, la technologie de l'invention fait appel à la génération des images sous forme de graphe. Chaque nœud du graphe applique une opération sur une ou plusieurs images d'entrée (flou, déformation, changement colorimétrique, etc.). Chaque nœud possède également des paramètres manipulables par l'utilisateur, ou spécifiables via des expressions arithmétiques à partir d'autres paramètres. Certains nœuds génèrent directement des images à partir des paramètres, sans demander d'autre image en entrée. L'infographiste décrit une image résultat à l'aide de ce graphe, via un outil logiciel dédié.
[0017] Dans un mode de réalisation avantageux, une modification de la liste L0 de rendus entraine un nouveau calcul des poids des résultats intermédiaires.
[0018] Selon une variante avantageuse, le module de calcul de poids des résultats intermédiaires effectue un tri de poids par ordre de poids croissants. Ce mode est intéressant dans le cas où le résultat intermédiaire est conservé si le poids a une valeur élevée.
[0019] Le résultat intermédiaire nouvellement obtenu avant l'étape de suppression de données est de préférence pris en compte dans l'étape d'identification du résultat intermédiaire de poids le plus faible.
[0020] Selon un autre mode de réalisation avantageux, le module de calcul de résultats intermédiaires détermine les résultats intermédiaires en fonction de la liste L0 de rendus.
[0021] Selon diverse variantes de réalisation, le module de calcul de poids effectue les calculs de poids en considérant la taille occupée par l'image résultat en mémoire, et/ou la quantité de calculs requis pour calculer ledit résultat intermédiaire et/ou la distance temporelle avant réutilisation dudit résultat intermédiaire. ,
MIWAJ 1 | / U U 1 7 3 0
[0022] Selon encore d'autres variantes de réalisation, dans l'étape de suppression de données correspondant au résultat intermédiaire, le moteur de génération d'images effectue la suppression de données de l'image du résultat intermédiaire, et/ou de données parmi les listes L1 , L2 et L3.
[0023] Selon encore une autre variante avantageuse, une modification du niveau de seuil minimum de mémoire disponible entraine un nouveau calcul de poids.
DESCRIPTION DES FIGURES
[0024] Tous les détails de réalisation sont donnés dans la description qui suit, complétée par les figures 1 à 12, présentées uniquement à des fins d'exemples non limitatifs, et dans lesquelles:
-les figures 1 à 6, ainsi que la figure 8 sont des représentations schématiques d'exemples de graphes de génération d'images selon l'invention;
-les figures 7 et 9 représentent schématiquement une scène dans laquelle des images sont à générer pour une application hôte;
-la figure 10 représente schématiquement un moteur de rendu selon l'invention ;
-les figures 11 et 12 sont des organigrammes fonctionnels présentant certaines étapes clé du procédé de génération d'image selon l'invention.
DESCRIPTION DETAILLEE DE L'INVENTION
[0025] Un exemple de graphe de génération est illustré à la figure 1. Les nœuds [a,b,c,d,e,g,h,i] produisent des résultats intermédiaires alors que les nœuds [f,j] sont les calculs produisant les images résultats désirées par l'utilisateur. Afin d'obtenir les images résultats, il faut traverser tous les autres nœuds, en respectant l'ordre défini par l'orientation des arêtes du graphe. Un nœud ne pouvant être calculé avant que toutes ses entrées ne soient disponibles, deux sous-branches indépendantes peuvent être évaluées en parallèle mais doivent être synchronisées lorsqu'elles rejoignent un même nœud.
[0026] Chaque calcul est réalisé dans un temps qui lui est propre, dépendant de sa complexité et du volume des données à traiter. Chaque nœud produit une image, qui requiert une certaine quantité de mémoire pour sa sauvegarde. Cette quantité de mémoire est dépendante de la taille de l'image et propre à chaque nœud. Par exemple, pour un nœud donné, traiter une image B deux fois plus haute et large qu'une image A entraînera le traitement de quatre fois plus de données, et donc potentiellement un temps d'exécution quatre fois supérieur et un espace mémoire quatre fois plus grand pour stocker le résultat.
[0027] Afin de réaliser le calcul d'un nœud il faut disposer en mémoire des images utilisées en entrée. Supposons par exemple que le graphe de la figure 1 est évalué en séquence, nœud après nœud, dans l'ordre montré figure 2.
[0028] Les nœuds sont calculés de gauche à droite. Les flèches indiquent les résultats intermédiaires qui doivent être stockés. La ligne en pointillé indique une étape de calcul particulière. A cette étape les résultats intermédiaires des nœuds [h] et [c] sont stockés en mémoire. En effet, ces résultats seront utilisés respectivement par les nœuds [i] et [d], évalués par la suite. Ceci signifie qu'ils seront utiles plus tard dans la même séquence de calcul, ou bien lors d'une prochaine séquence de calcul (dans cet exemple, on peut imaginer calculer l'image [j] seule, puis dans un second temps l'image [f]).
[0029] Il est donc nécessaire de maintenir en mémoire un ensemble de résultats intermédiaires. Le nombre d'images intermédiaires à stocker dépend de la complexité du graphe. Cependant, la mémoire étant une ressource finie, il est fréquent que l'application hôte ne confie qu'une quantité de mémoire limitée au moteur de rendu d'images procédurales. Il faudra donc parfois effacer un (ou des) résultat(s) intermédiaire(s) afin de respecter le « budget mémoire » imposé par l'application hôte au moteur de rendu. Dans ce cas, si un résultat intermédiaire effacé est à nouveau utilisé plus tard dans le processus de génération, il faudra le régénérer à partir des résultats intermédiaires conservés en mémoire, ou le cas échéant, à partir du début de la branche du graphe menant à ce résultat. Ainsi, pour l'exemple de la figure 2, supposons que la mémoire disponible ne permette pas de stocker les résultats intermédiaires des nœuds [c] et [h] simultanément. Lors du calcul du nœud [h], le résultat du nœud [c] devra être supprimé, comme montré à la figure 3.
[0030] A la figure 4, on voit que la génération se poursuit alors jusqu'au nœud [j], le résultat de [c] étant inutile pour ces nœuds. A la figure 5, lorsque [c] est à nouveau nécessaire (en arrivant sur le nœud [d]), l'algorithme le régénère à partir du début du graphe. Puis la génération se termine (figure 6). A aucun moment les résultats intermédiaires [c] et [h] n'ont ' i ' v u i / j y
été présents simultanément en mémoire, réduisant l'espace nécessaire. En échange, les nœuds [a,b,c] ont été calculés deux fois. En fonction du budget mémoire imposé par l'application hôte, il est donc possible d'effectuer un compromis entre la quantité de mémoire occupée et le temps de calcul nécessaire pour générer toutes les sorties du graphe. Il est donc crucial de bien choisir quels résultats sont conservés en mémoire ou éliminés, afin de maximiser l'utilisation mémoire dans la limite du budget fixé sans avoir à répéter trop souvent des calculs déjà effectués au préalable. Cependant, une difficulté importante réside dans le fait que l'ordre des opérations n'est pas toujours connu à l'avance. En effet, pour le graphe de la figure 1 , l'application hôte peut d'abord demander la génération de l'image [f] puis celle de l'image [j], ou à l'inverse demander d'abord la génération du résultat [j] puis la génération de [f]. Définir un choix optimal est donc rarement possible. De plus, comme évoqué précédemment, ce problème existe à la fois au sein de la génération d'un graphe - comme décrit ci-dessus - mais également temporellement, lorsque les images sont générées les unes après les autres, à la demande de l'utilisateur. Cette problématique, dite de « streaming », est décrite plus en détail ci-dessous.
[0031] La technologie de l'invention permet le « streaming » des images résultats, lorsque celles-ci sont utilisées comme textures (images appliquées sur de la géométrie) dans une application graphique. Le « streaming » permet de générer les textures uniquement lorsqu'elles deviennent visibles à l'écran, selon les déplacements de l'utilisateur. Les textures qui ne sont plus visibles sont effacées de la mémoire afin de libérer de l'espace. Ceci permet de limiter la consommation mémoire aux seules textures nécessaires pour l'affichage du point de vue courant.
[0032] Typiquement, le moteur d'affichage maintient un ensemble de textures nécessaires à l'affichage du point de vue courant, et fait évoluer cet ensemble en fonction des déplacements de l'utilisateur, en y ajoutant les textures préalablement invisibles et qui sont devenues visibles, ou à l'inverse en en retirant les textures préalablement visibles et devenues invisibles. Le moteur d'affichage peut aussi anticiper ces changements à partir des déplacements de l'utilisateur afin que toutes les textures utiles soient présentes en mémoire avant de devenir visibles, afin de ne pas avoir de trop nombreuses images à charger dans un temps limité, ce qui entraînerait un ralentissement sensible de l'application. Le moteur d'affichage envoie typiquement trois types d'événements :
- une texture deviendra probablement visible dans T unités de temps ;
- une texture devient visible immédiatement (T=0) ; - une texture n'est plus visible.
Les événements du premier type permettent d'anticiper les chargements avec une priorité qui dépend de T: Les demandes de chargement de textures sont ainsi stockées dans une liste de rendu ordonnée en fonction du temps T au-delà duquel chaque texture doit absolument être disponible.
[0033] Le « streaming » est une technologie répandue pour charger des textures stockées sous forme de bitmaps classiques. Cependant la technologie des textures procédurales présente des particularités qui peuvent être exploitées pour optimiser la génération des textures pendant le « streaming » : il est possible de conserver les résultats intermédiaires (images) internes au graphe et communs à plusieurs images résultats. Ceci évite leur recalcul et permet d'accélérer la génération. Ce problème est donc le même que celui évoqué précédemment pour un graphe complet : l'objectif est de garder en mémoire autant de résultats intermédiaires que possible tout en minimisant les calculs redondants.
[0034] De par les caractéristiques du processus de calcul des images procédurales via le graphe de génération, il est possible de conserver les résultats intermédiaires communs à plusieurs images résultats pour une génération plus rapide. Un des éléments de la solution consiste à garder autant de résultats que possible dans le budget mémoire imparti et à décider du meilleur candidat à l'effacement seulement lorsque c'est nécessaire.
[0035] Pour l'exemple, considérons la scène de la figure 7 découpée en pièces (cellules). Chaque pièce utilise un sous-ensemble parmi trois textures différentes (images résultats) notées [u,v,w]. Le graphe de génération est donné à la figure 8. L'ordre de génération des textures sera ici déterminé par les déplacements de l'utilisateur dans la scène, c'est-à-dire l'ordre d'apparition des textures nécessaires pour afficher les points de vue successifs. De manière générale, cet ordre n'est pas connu à l'avance.
[0036] Comme il a été décrit précédemment, il est possible de conserver en mémoire le résultat des nœuds utilisés plusieurs fois dans un même calcul. Par exemple, pour le point de vue présenté à la figure 9 à gauche, les pièces A, B et C sont visibles. Les textures [u,v] ont donc été calculées, ainsi que les résultats intermédiaires [a,b,c,d,e,g,h,i]. Le second point de vue de la figure 9 (à droite) requiert les pièces C et D et donc les textures [u,w].La texture [w] peut être calculée très rapidement à partir du seul résultat intermédiaire [h], calculé au point de vue précédent. On voit donc bien que [h] est un excellent résultat intermédiaire à conserver en mémoire, puisqu'il permet de calculer à la fois [v] et [w] rapidement. De même, [c] est impliqué dans le calcul des trois textures résultats, et il est probable que l'on souhaite le conserver en mémoire.
[0037] Ceci fait apparaître la principale difficulté associée à l'idée de conserver les résultats intermédiaires : il faut déterminer quels résultats conserver ou non, et ce bien entendu en fonction de la mémoire de travail disponible. Par défaut tous les résultats intermédiaires sont conservés, et l'élimination des résultats les moins intéressants n'a lieu que lorsque le budget mémoire est dépassé.
[0038] Le budget mémoire peut être constant ou dynamique (c'est-à-dire réactualisé au besoin par l'application hôte). Donc à chaque fois qu'un résultat intermédiaire est jugé utile pour la suite des calculs, le générateur doit évaluer s'il est possible de conserver ce résultat vis-à-vis du budget mémoire. Plus généralement, cette problématique est récurrente durant toute la vie du résultat intermédiaire : dans le cas où un autre résultat intermédiaire plus intéressant doit être conservé « à sa place », ou bien dans le cas d'une diminution du budget mémoire fixé par l'application hôte.
[0039] Un exemple de dispositif implémentant la présente invention est illustré schématiquement à la Figure 10. Ce dispositif se compose des parties suivantes :
- un organe de calcul (le CPU), chargé du parcours et de l'exécution du graphe, de la gestion du budget mémoire, de la détermination des résultats intermédiaires à supprimer lorsque le budget mémoire est dépassé ;
- une mémoire vive contenant les informations suivantes :
a. une zone G contenant le graphe linéarisé, tel que représenté figure 2 ;
b. une zone L0 contenant la liste des rendus présents dans la queue à exécuter ultérieurement ;
c. une zone L1 contenant la liste des résultats intermédiaires ;
d. une zone L2 contenant la liste des temps de rendu associés aux résultats intermédiaires déjà calculés ;
e. une zone L3 contenant la liste des poids associés aux résultats intermédiaires conservés en mémoire à un instant donné (voir ci-dessous) ;
f. une zone M contenant les résultats intermédiaires eux-mêmes, stockés sous forme de tableaux listant la valeur (luminosité ou couleur) de chaque pixel. „ .
[0040] Le CPU est connecté à la mémoire vive par l'intermédiaire d'un bus et peut y lire et y écrire librement. Le CPU doit de plus être capable de mesurer le temps écoulé entre deux événements, que ce soit par l'intermédiaire de registres internes ou d'un périphérique externe (non représenté sur la figure 10. Lors du parcours du graphe, le temps consommé par l'exécution de chaque nœud est stocké dans la liste L2.
[0041] Comme indiqué précédemment, tous les résultats intermédiaires sont conservés par défaut, et c'est uniquement lors du dépassement du budget imparti que se pose le problème de la détermination des résultats à conserver ou à éliminer. L'invention proposée définit une stratégie de choix des résultats intermédiaires à éliminer afin de minimiser le temps nécessaire pour effectuer les éventuelles générations ultérieures des images résultats du même graphe.
[0042] Le moteur de génération d'images maintient en permanence une liste des résultats intermédiaires conservés en mémoire, ainsi qu'une liste de rendu contenant les requêtes envoyées par l'application hôte et non encore satisfaites. Le procédé selon la présente invention permet d'associer à chaque résultat intermédiaire une métrique composite (dénommée « poids » par la suite) qui va indiquer l'intérêt potentiel de la conservation de ce résultat intermédiaire pour la réduction du temps de génération des images ultérieures. Une fois que chaque résultat intermédiaire s'est vu attribuer un poids, la liste des résultats intermédiaires est triée par ordre de poids afin de supprimer les résultats les moins pertinents. La mesure des pertinences relatives de deux résultats intermédiaires est donnée par la comparaison de leur poids.
[0043] En particulier lorsque le budget mémoire va être dépassé, les nœuds sont supprimés par ordre de poids jusqu'à ce que l'occupation mémoire totale des résultats intermédiaires respecte le budget mémoire imposé.
[0044] Le choix de la méthode de calcul du poids de chaque résultat intermédiaire détermine le comportement du gestionnaire mémoire, ainsi que l'ordre de tri et de suppression des résultats intermédiaires. Dans tous les cas, il est important de prendre en compte les critères suivants :
- la taille occupée par l'image résultat en mémoire ;
- la quantité de calculs nécessaire afin de calculer ce résultat, qui représente le « coût » associé à la génération de ce résultat ; - la distance temporelle avant la réutilisation du résultat intermédiaire, mesurée par la position de la première occurrence du résultat intermédiaire en cours d'évaluation dans la liste de rendu.
[0045] Le poids de chaque résultat intermédiaire peut donc être calculé à tout moment par une formule intégrant ces trois données. Un exemple d'une telle formule est donné ci- dessous :
Les variables utilisées sont :
- t, la taille de l'image résultat, en octets ;
- e, le temps nécessaire au recalcul de ce résultat, mesuré en millisecondes ;
- r, l'index de la première occurrence du résultat intermédiaire dans la liste de rendu (+∞ si le résultat intermédiaire n'est pas utilisé). Les constantes k 0 et k x sont déterminées empiriquement et définies à k 0 = et ^ = 2. Il est important de noter que le paramètre r dépend de la liste de rendu, et doit donc être réévalué si la liste de rendu a été modifiée depuis le calcul du poids originel. La formule proposée satisfait les contraintes qu'une métrique de poids doit respecter dans le contexte de la présente invention : plus un résultat intermédiaire est long à calculer et plus son poids est élevé, ce qui signifie qu'il est à privilégier par rapport à un résultat intermédiaire que l'on peut recalculer plus rapidement, à occupations mémoire et dates de réutilisation égales. Plus un résultat intermédiaire prend de la place en mémoire et plus son poids est faible, ce qui signifie qu'en cas de budget mémoire dépassé, supprimer ce résultat intermédiaire est plus intéressant que supprimer un résultat plus léger, à temps de calcul et dates de réutilisation égaux plus un résultat intermédiaire est utilisé tardivement et plus son poids est faible, ce qui signifie qu'en cas de budget mémoire dépassé, il est moins important de conserver ce résultat qu'un autre qui serait réutilisé plus tôt dans la liste de rendu, à temps de calcul et occupations mémoire égaux.
[0046] Cette formule associe un poids élevé aux résultats intermédiaires présentant un fort intérêt à être conservés en mémoire. Le tri de la liste des poids et la suppression des résultats intermédiaires est donc effectuée par ordre de poids croissants. Il est tout à fait possible d'envisager d'autres formulations du poids qui associent un poids faible aux résultats intermédiaires les plus intéressants. Dans ce cas, le tri de la liste et la suppression des résultats intermédiaires se font bien entendu par ordre de poids décroissants. Le procédé associé à un tel système est illustré à la figure 1 1.
[0047] Il est possible d'envisager un processus d'élimination des résultats intermédiaires ne rebouclant pas jusqu'à la première étape du procédé illustré, et se contentant de supprimer le premier élément de la liste L3 triée tant que la somme des occupations mémoire des nœuds restant dans L3 est supérieure au budget mémoire imposé. Ainsi, les poids ne sont pas recalculés à chaque suppression de résultat intermédiaire. Cela introduit une incertitude sur le poids des résultats intermédiaires mais permet de diminuer le temps global pris par l'étape d'identification et de suppression des résultats intermédiaires en cas de dépassement du budget mémoire. Une telle optimisation est illustrée à la figure 12.
[0048] La mise en oeuvre des différents modules préalablement décrits (par exemple les modules de comparaison et suppression, de parcours, de calcul de résultats intermédiaires, de calcul de temps de rendu, de calcul de poids, etc) est avantageusement réalisée au moyen d'instructions de mise en œuvre, permettant aux modules d'effectuer la ou les opérations spécifiquement prévues pour le module concerné. Les instructions peuvent être sous la forme d'un ou plusieurs logiciels ou modules de logiciels mis en œuvre par un ou plusieurs microprocesseurs. Le ou les modules et/ou le ou les logiciels sont avantageusement prévus dans un produit programme d'ordinateur comprenant un support d'enregistrement ou médium d'enregistrement utilisable par un ordinateur et comportant un code programmé lisible par un ordinateur intégré dans ledit support ou médium, permettant à un logiciel applicatif son exécution sur un ordinateur ou autre dispositif comportant un microprocesseur.
Next Patent: SUPRAMOLECULAR AGGREGATES AS DRUG CARRIERS ON CELL EXPRESSING RECEPTORS FOR BRANCHED NEUROTENSIN