Outils systèmes pour aider au développement
Comment obtenir les fonctions d'une librairie statique ? Taper le one-liner ci-dessous et hop !
nm -gop --demangle --defined-only <static lib.a> | grep ' T '
Source : comps.os.linux.development.apps
Multithread sous Linux
Applications -> Framework
Je veux designer des applications, très simples au départ, qui couvrent un spectre assez large de domaines (algos, système, bonnes pratiques etc) pour en déduire un framework qui en facilite l'écriture, les tests, la maintenance et la compréhension externe.
Application 1 : Mandelbrot threadé.
But assez simple : n threads qui font tourner un code de calcul de l'ensemble de Mandelbrot. Quand les n threads ont terminées leur travail, l'application sort.
#include <pthread.h>
//Le tableau des Ids système des threads
pthread_t* ThreadIds = NULL;
//Deux mutex : l'indice de la dernière thread créée et le nombre de threads qui tournent à un moment donné.
pthread_mutex_t ThreadIndexMutex, ThreadCountMutex;
int ThreadIndex = 0, ThreadCount = 0;
void* ThreadMain(void* arg); //La fonction qui démarre une thread du pool.
struct ThreadObject { int Index; }; //Les prémisses de la future classe Thread
void Mandelbrot(ThreadObject* host); //La fonction de calcul.
int main(int argc, char *argv[])
{
cout << "Test de gestion de threads" << endl;
//
int NbMaxThreads = 12;
ThreadIds = new pthread_t[NbMaxThreads];
pthread_mutex_init(&ThreadIndexMutex, NULL);
pthread_mutex_init(&ThreadCountMutex, NULL);
int i;
for(i=0; i<NbMaxThreads; i++) assert(pthread_create(ThreadIds+i, NULL, ThreadMain, NULL) == 0);
timespec Delay;
Delay.tv_sec = 0; Delay.tv_nsec = 100000;
nanosleep(&Delay, NULL);
while(ThreadCount) nanosleep(&Delay, NULL);
pthread_mutex_destroy(&ThreadIndexMutex);
pthread_mutex_destroy(&ThreadCountMutex);
return EXIT_SUCCESS;
}
void* ThreadMain(void* arg)
{
pthread_mutex_lock(&ThreadCountMutex);
ThreadCount++;
pthread_mutex_unlock(&ThreadCountMutex);
//
pthread_mutex_lock(&ThreadIndexMutex);
ThreadObject* Obj = new ThreadObject();
Obj->Index = ThreadIndex++;
pthread_mutex_unlock(&ThreadIndexMutex);
Mandelbrot(Obj);
//
pthread_mutex_lock(&ThreadCountMutex);
ThreadCount--;
pthread_mutex_unlock(&ThreadCountMutex);
}
//Mandelbrot en float
void Mandelbrot(ThreadObject* host)
{
static float xmin = -2.0, xmax = 0.6;
static float ymin = -1.2, ymax = 1.2;
int x, y, w = 800, h = 800;
float xinc = (xmax-xmin) / w;
float yinc = (ymax-ymin) / h;
float ci, cr;
for(ci=ymin, y=0; y<h; y++, ci+=yinc) {
for(cr=xmin, x=0; x<w; x++, cr+=xinc) {
float curr = cr, curi = ci;
int NbIter = 0;
while(NbIter < 255 && curr*curr + curi*curi < 4.0f) {
float tempr = curr;
curr = curr*curr - curi*curi + cr;
curi = 2.0f * tempr*curi + ci;
NbIter++;
}
}
printf("Thread %d : %.2f\n", host->Index, 100.0f*y/h);
}
}
Un code assez simple à comprendre mais qui contient tout un tas d'appels système qui compliquent la rédaction et la compréhension externe de l'application. Voilà à quoi elle peut ressembler si on fait un petit saut conceptuel :
class MandelbrotThread : WorkingThread
{
public:
virtual void init()
{
}
virtual void run()
{
static float xmin = -2.0, xmax = 0.6;
static float ymin = -1.2, ymax = 1.2;
int x, y, w = 800, h = 800;
float xinc = (xmax-xmin) / w;
float yinc = (ymax-ymin) / h;
float ci, cr;
for(ci=ymin, y=0; y<h; y++, ci+=yinc) {
for(cr=xmin, x=0; x<w; x++, cr+=xinc) {
float curr = cr, curi = ci;
int NbIter = 0;
while(NbIter < 255 && curr*curr + curi*curi < 4.0f) {
float tempr = curr;
curr = curr*curr - curi*curi + cr;
curi = 2.0f * tempr*curi + ci;
NbIter++;
}
}
printf("Thread %d : %.2f\n", Index, 100.0f*y/h);
}
}
virtual void exit()
{
}
protected:
};
int main(int argc, char *argv[])
{
cout << "Threads with classes !" << endl;
//
int i, NbMaxThread = 12;
for(i=0; i<NbMaxThread; i++) MandelbrotThread* CurThread = new MandelbrotThread();
while(ThreadCount.Value) WorkingThread::sleep(0, 100000);
return EXIT_SUCCESS;
}
Cette fois on ne se concentre que sur le but premier de l'application : créer n tâches (la boucle for de la fonction main()), le calcul des n tâches (la fonction virtuelle run de la classe MandelbrotThread) et attendre qu'il n'y ait plus aucune thread qui calcule (ThreadCount.Value doit être nul). Le problème étant qu'il y a beaucoup d'implicite dans ce code : c'est le framework qui prend forme :). Voilà ce qu'on doit inclure en .h ou en librairie pour que le code ci-dessus fonctionne (rappel : je travaille sous KDevelop avec GCC 3.4.6, YMMV)
template <class T> class Mutex
{
public:
Mutex()
{
pthread_mutex_init(&Internal, NULL);
}
~Mutex()
{
pthread_mutex_destroy(&Internal);
}
void lock()
{
pthread_mutex_lock(&Internal);
}
void unlock()
{
pthread_mutex_unlock(&Internal);
}
//
T Value; //La valeur qu'héberge le mutex
protected:
pthread_mutex_t Internal; //The system mutex
};
Mutex<int> ThreadIndex; //Indice maximal des threads de l'application
Mutex<int> ThreadCount; //Nombre de thread concurrentes
class WorkingThread
{
public:
//L'exécution du constructeur de la classe de base d'une thread ne s'exécute pas dans la file d'exécution elle-même : la thread système n'est pas encore créée !
WorkingThread() //TODO : trouver un mécanisme pour ajouter des paramètres à ce constructeur, params qui viendraient du new Thread...
{
assert(pthread_create(&SystemThread, NULL, (void* (*) (void*)) ThreadMain, this) == 0);
}
virtual void init() = 0; //Equivalent du constructeur pour une thread
virtual void run() = 0;
virtual void exit() = 0; //Equivalent du destructeur
//Helper pour qu'une thread se mette en sommeil (attention, non thread-safe !)
static void sleep(int sec, int nsec)
{
timespec Delay;
Delay.tv_sec = sec; Delay.tv_nsec = nsec;
nanosleep(&Delay, NULL);
}
protected:
int Index; //Indice interne, i.e. une ID
pthread_t SystemThread; //Identifiant système de la thread
static void* ThreadMain(WorkingThread* host)
{
ThreadIndex.lock(); host->Index = ThreadIndex.Value++; ThreadIndex.unlock();
ThreadCount.lock(); ThreadCount.Value++; ThreadCount.unlock();
//
host->init();
host->run();
host->exit();
//
ThreadCount.lock(); ThreadCount.Value--; ThreadCount.unlock();
//Que retourner ???
}
};
Bien sûr que tout cela est foncièrement basique, mais ça prend forme, nous avons une classe de base pour les threads, un type pour les mutex et deux mutexes globaux pré-instanciés qui décomptent le nombre de threads actives et l'Id maximale d'une thread. De la même façon, le mécanisme de création générique de thread est lancé : un new XXXThread dans une thread parente va appeler le constructeur de la classe de base WorkingThread qui va créer la thread système (une p(osix)thread sous linux), trois méthodes virtuelles (init, run et exit) qui vont être appelée automatiquement par le framework au fur et à mesure de la vie de la tâche. C'est peu mais c'est déjà beaucoup.
J'ai déplacé des membres et l'helper 'sleep' de WorkingThread dans Thread, mais j'ai laissé la création de la working thread où elle se trouvait : ça fonctionne donc pas touche et comme Thread est une classe de base, elle ne va peut-être jamais représenter de thread concrètes et ce mécanisme permet d'avoir des thread potentiellement différentes dans chaque classe dérivée de Thread ce qui est bien ! Je laisse les virtuelles pures dans WorkingThread car elles ont leur place, alors que je ne sais pas encore ce que je vais faire de Thread... Je crée une classe Application plutôt vide pour l'instant et une classe dérivée pour le haut-niveau qui représente mon application : elle contient l'ancien contenu de la fonction main qui était auparavant apparente. J'ai créé une macro préprocesseur pour générer une fonction main() valide qui fait le lien avec l'objet dérivé d'Application : FFW_MAINENTRY.
J'ai profité de l'application précédente qui fonctionnait pour implémenter un système rudimentaire de messages inter-threads. Ainsi chacune des threads filles peut envoyer sous forme de simples chaînes de caractères son niveau de complétion pour le calcul qui la préoccupe. Ce message une fois reçu par la thread maîtresse est affiché (via la librairie ncurses) pour indiquer la complétion globale du programme.
class MandelbrotThread : public WorkingThread
{
public:
virtual ~MandelbrotThread() { }
virtual void run()
{
static float xmin = -2.0, xmax = 0.6;
static float ymin = -1.2, ymax = 1.2;
int x, y, w = 800, h = 800;
float xinc = (xmax-xmin) / w;
float yinc = (ymax-ymin) / h;
float ci, cr;
for(ci=ymin, y=0; y<h; y++, ci+=yinc) {
for(cr=xmin, x=0; x<w; x++, cr+=xinc) {
float curr = cr, curi = ci;
int NbIter = 0;
while(NbIter < 255 && curr*curr + curi*curi < 4.0f) {
float tempr = curr;
curr = curr*curr - curi*curi + cr;
curi = 2.0f * tempr*curi + ci;
NbIter++;
}
}
char* Str = NULL;
string_format(&Str, "%d:%.2f", Index, 100.0f*y/h);
sendTo(ParentThread, Str);
string_release(&Str);
sleep(0, 10); //Important pour que les threads plus équilibrées
}
}
};
class MandelApp : public Application
{
public:
virtual int run()
{
mtrace();
int AppRet;
if ((AppRet = Application::run()) != EXIT_SUCCESS) return AppRet;
initscr(); //Initialisation de NCurses
//
ThreadCount.Value = 0;
ThreadIndex.Value = 1;
cout << "Threads with classes !" << endl;
int i, NbMaxThread = 8;
Thread** ThreadsList = new Thread*[NbMaxThread];
float* Completions = new float[NbMaxThread];
for(i=0; i<NbMaxThread; i++) {
ThreadsList[i] = new MandelbrotThread();
}
WorkingThread::sleep(0, 100);
char* msg = NULL;
bool StillActives = true;
for(i=0; i<NbMaxThread; i++) Completions[i] = 0.0f;
while(ThreadCount.Value || StillActives) {
for(i=0, StillActives = false; i<NbMaxThread; i++) StillActives |= ThreadsList[i]->Index != 0;
int StoreNbMsgs = _Queue._Counter; //On sauve le nombre de messages en attente
while (hasMessage() && getMessage(&msg)) {
int ThreadNumber;
float Completion;
sscanf(msg, "%d:%f", &ThreadNumber, &Completion);
Completions[ThreadNumber-1] = Completion;
}
//On va afficher un panel contenant l'état d'avancement de chaque thread de calcul
char *ThreadMsg = NULL, *MainMsg = NULL;
string_format(&MainMsg, "Nombre de message en attente dans la pile principale : %d ", StoreNbMsgs);
mvprintw(0, 5, MainMsg);
for(i=0; i<NbMaxThread; i++) {
string_format(&ThreadMsg, "Avancement de la thread %d : %.2f / 100", i, Completions[i]);
mvprintw(i+2, 0, ThreadMsg);
}
refresh();
string_release(&ThreadMsg);
string_release(&MainMsg);
//
Thread::sleep(0, 10*1000*1000);
}
//
printf("On détruit les objets Thread\n");
for(i=0; i<NbMaxThread; i++) { delete ThreadsList[i]; ThreadsList[i] = NULL; }
printf("On détruit le tableau hébergeant la liste des threads\n");
delete []ThreadsList;
delete []Completions;
endwin(); //Sortie de NCurses
//
return EXIT_SUCCESS;
}
};
FFW_MAINENTRY(MandelApp)Pour faire ce programme j'ai modifié la hiérarchie des classes et ait eu besoin de créer la classe de base Thread. Pourquoi ? Parce que pendant qu'on y était, il était très simple de créer une classe Application (wrapper plus sympa que le classique main(...)) dérivée elle-même de Thread et d'avoir avec cette simple application un test utilisant deux types de threads différents toutes deux équipées d'une queue de messages qui leur permet de communiquer très simplement. Ma \"librairie\" (trop pompeux pour l'instant) est comme suit :
//Premières fonctions de la future classe String
void string_release(char** str)
{
if (*str) delete [](*str);
*str = NULL;
}
void string_create(char** pStr, int ln)
{
*pStr = new char[ln+1];
(*pStr)[ln] = '\0';
}
int string_format(char** destStr, const char* format, ...)
{
string_release(destStr);
//On détermine la taille de la future string
va_list StrVars;
va_start(StrVars, format);
int Len = vsnprintf(NULL, 0, format, StrVars);
string_create(destStr, Len);
va_end(StrVars);
//On refait la même chose mais en créant la string cette fois
va_start(StrVars, format);
vsnprintf(*destStr, Len+1, format, StrVars); //Len+1 car vsnprintf renvoie la taille sans '\0' mais écrit Len+1 chars y compris '\0'
va_end(StrVars);
return Len;
}
void string_affectCopy(char** pStr, const char* newVal)
{
string_release(pStr);
int Len;
string_create(pStr, Len = strlen(newVal));
strcpy(*pStr, newVal);
}
template <class T> class Mutex
{
public:
Mutex() { pthread_mutex_init(&_Internal, NULL); /*_Owner = 0;*/ }
~Mutex() { pthread_mutex_destroy(&_Internal); }
void lock() { pthread_mutex_lock(&_Internal); /*_Owner = pthread_self();*/}
void unlock() { pthread_mutex_unlock(&_Internal); /*_Owner = 0;*/ }
//
T Value; //La valeur qu'héberge le mutex
protected:
pthread_mutex_t _Internal; //The system mutex
// pthread_t _Owner; //Pour une future gestion des locks
};
class Thread
{
public:
class MessageQueue
{
public:
class Message
{
public:
Message(const char* str=NULL) { _Next = NULL; _Str = NULL; setStr(str); }
~Message() { string_release(&_Str); }
void setStr(const char* str) { string_affectCopy(&_Str, str); }
char* _Str;
Message *_Next;
};
//
MessageQueue()
{
_FirstMessage = _LastMessage = NULL;
_Counter = 0;
}
~MessageQueue()
{
ListReady.lock();
Message* CurMessage = _FirstMessage;
while (_FirstMessage) {
CurMessage = _FirstMessage->_Next;
delete _FirstMessage;
_FirstMessage = CurMessage;
}
_LastMessage = NULL;
ListReady.unlock();
}
//On empile un message à la fin de la liste
void push(const char* msg)
{
ListReady.lock();
//
Message* Shell = new Message(msg);
Shell->_Next = NULL;
if (_LastMessage) _LastMessage->_Next = Shell;
_LastMessage = Shell;
if (!_FirstMessage) _FirstMessage = _LastMessage;
_Counter++;
//
ListReady.unlock();
}
//On dépile le premier message de la liste
bool pop(char** str)
{
ListReady.lock();
//
if (!_Counter) { ListReady.unlock(); return false; }
Message* TempMsg = _FirstMessage;
_FirstMessage = _FirstMessage ? _FirstMessage->_Next : NULL;
if (TempMsg) {
string_affectCopy(str, TempMsg->_Str);
TempMsg->_Next = NULL;
delete TempMsg;
} else string_release(str);
if (!_FirstMessage) _LastMessage = NULL;
_Counter--;
//
ListReady.unlock();
return true;
}
//
Message *_FirstMessage, *_LastMessage;
int _Counter;
Mutex<int> ListReady;
};
public:
Thread() { }
virtual ~Thread() { ParentThread = NULL; SystemThread = 0; }
//Renvoie true si la thread courant a des messages en attente, false sinon.
bool hasMessage() const { return _Queue._Counter; }
//Renvoie true si msg a été rempli avec le premier message de la liste d'attente, false si cette liste ne contenait aucun message en attente.
bool getMessage(char** msg) { return _Queue.pop(msg); }
//TODO : accèder à une thread par son index plutôt que par un pointeur.
void sendTo(Thread* target, const char* msg) { target->_Queue.push(msg); }
//Helper pour qu'une thread se mette en sommeil (attention, non thread-safe !)
static void sleep(int sec, int nsec)
{
timespec Delay;
Delay.tv_sec = sec; Delay.tv_nsec = nsec;
nanosleep(&Delay, NULL);
}
//
int Index; //Indice interne, i.e. une ID
pthread_t SystemThread; //Identifiant système de la thread
MessageQueue _Queue;
Thread* ParentThread;
};
class Application : public Thread
{
public:
Application() { ParentThread = NULL; SystemThread = pthread_self(); }
virtual int run()
{ cout << "Application..." << endl; return EXIT_SUCCESS; }
};
static Application* MainApp = NULL;
//Intégration de la fonction main(), obligatoire en C++, et d'un objet dérivé d'Application.
#define FFW_MAINENTRY(AppClassName) \
int main(int argc, char *argv[]) \
{ \
MainApp = new AppClassName(); \
int Ret = MainApp->run(); \
delete MainApp; \
return Ret; \
}
Mutex<int> ThreadIndex; //Indice maximal des threads de l'application
Mutex<int> ThreadCount; //Nombre de thread concurrentes
class WorkingThread : public Thread
{
public:
//L'exécution du constructeur de la classe de base d'une thread ne s'exécute pas dans la file d'exécution elle-même : la thread système n'est pas encore créée !
WorkingThread() //TODO : trouver un mécanisme pour ajouter des paramètres à ce constructeur, params qui viendraient du new Thread...
{
int Ret = pthread_create(&SystemThread, NULL, (void* (*) (void*)) ThreadMain, this);
assert(!Ret);
}
virtual ~WorkingThread() { }
virtual void init() {} //Equivalent du constructeur pour une thread
virtual void run() {};
virtual void exit() {}; //Equivalent du destructeur
protected:
static void* ThreadMain(WorkingThread* host)
{
ThreadIndex.lock(); host->Index = ThreadIndex.Value++; ThreadIndex.unlock();
ThreadCount.lock(); ThreadCount.Value++; ThreadCount.unlock();
//
host->ParentThread = MainApp;
host->init();
host->run();
host->exit();
//
ThreadCount.lock(); ThreadCount.Value--; ThreadCount.unlock();
//
ThreadIndex.lock();
host->Index = 0;
ThreadIndex.unlock();
//
return EXIT_SUCCESS;
}
};GUI Simple : apprentissage de X11
Des objets simples (carrés, rectangles, ronds) que l'on déplace sur un canevas, dont on peut modifier et visualiser les propriétés et que l'on peut importer/exporter. On va réaliser l'application en deux temps : design préliminaire + pseudo-code pour réaliser l'application suivante et retour sur une implémentation réaliste.
MiniGUI
Fenêtres, boutons, statics (en utilisant FreeType ou Pango ?), custom-control. Rien de bien complexe mais il faut apprendre X11 en en profitant pour améliorer/corriger le framework et peut-être implémenter des nouveaux mécanismes.
Testeur de ma HashTable
Quelques actions pour remplir et tester la table, et un panel de profile (temps machine, remplissage de la table).
Mandelbrot Renderer
Un panel de calcul et de rendu et un autre de stats (position, temps machine détaillé, méthode utilisée etc).
Moteur 3D simplifié
Un ensemble d'objets simples (cubes et sphère) avec la possibilité de se promener, de cliquer sur un objet et d'obtenir ses propriétés.
Commentaires...
//Comment lier tout ce joli schéma ci-dessous avec un double tableau ID<-->Pointeur ?
class SmartPointer
{
public:
SmartPointer(const T*); //Copy-constructeur
operator=(const T*); //Copy-constructeur
T* operator->() const;
T& operator.() const;
protected:
T* _Pointee;
};
//Un Array avec des méthodes facilitant le parcours de ses éléments
template <class T> class Collection
{
public:
Collection() { _Cursor = 0; _Count = 0; _List = NULL; }
~Collection() { }
//Helpers
void start() { _Cursor = 0; }
void end() { _Cursor = _Count-1; }
bool isLast() const { return _Cursor == _Count; }
int length() const { return _Count; }
//Manipulation de la liste
int push(T*);
bool set(index, T*);
bool get(index, SmartPointer<T>& item) const
{
item = _List[index]; //Copie-constructeur du SmartPointer
return true;
}
merge(const Collection<T>)
//Parcours de la liste
bool forEach(SmartPointer<T>& item) const
{
if (isLast()) return false;
return get(_Cursor++, item);
}
protected:
T** _List;
mutable int _Cursor;
int _Count;
};
Collection<Object3D> Coll;
//On remplit la collection avec des pointeurs vers des éléments de type Object3D
Coll.start();
SmartPointer<Object3D> Object;
while(Coll.forEach(Object)) {
printf(Object.position);
}
Génération de PDF
Applications -> Framework
#include <libxml/parser.h>
#include "pdflib.h"
//Essai d'utilisation de LibXML2
xmlDocPtr doc;
xmlNodePtr cur;
doc = xmlParseFile("synthereports.xml");
//doc = xmlParseFile("test.xml");
xmlErrorPtr LastErr = xmlGetLastError();
if (doc == NULL ) {
fprintf(stderr, "Document not parsed successfully. \n");
return EXIT_FAILURE;
}
cur = xmlDocGetRootElement(doc);
if (cur == NULL) {
fprintf(stderr,"empty document\n");
xmlFreeDoc(doc);
return EXIT_FAILURE;
}
if (xmlStrcmp(cur->name, (const xmlChar *) "html")) {
fprintf(stderr,"document of the wrong type, root node != html");
xmlFreeDoc(doc);
return EXIT_FAILURE;
}
//Essai d'utilisation de PDFLib
PDF *p;
int font;
// create a new PDFlib object
if ((p = PDF_new()) == (PDF *) 0)
{
printf("Couldn't create PDFlib object (out of memory)!\n");
return(2);
}
PDF_TRY(p) {
/* This means we must check return values of load_font() etc. */
PDF_set_parameter(p, "errorpolicy", "return");
if (PDF_begin_document(p, "hello.pdf", 0, "") == -1) {
printf("Error: %s\n", PDF_get_errmsg(p));
return(2);
}
/* This line is required to avoid problems on Japanese systems */
PDF_set_parameter(p, "hypertextencoding", "host");
PDF_set_info(p, "Creator", "hello.c");
PDF_set_info(p, "Author", "Thomas Merz");
PDF_set_info(p, "Title", "Hello, world (C)!");
PDF_begin_page_ext(p, a4_width, a4_height, "");
/* Change "host" encoding to "winansi" or whatever you need! */
font = PDF_load_font(p, "Helvetica-Bold", 0, "host", "");
if (font == -1) {
printf("Error: %s\n", PDF_get_errmsg(p));
PDF_delete(p);
return(2);
}
PDF_setfont(p, font, 24);
PDF_set_text_pos(p, 50, 700);
PDF_show(p, "Hello, world!");
PDF_continue_text(p, "(says C)");
//
int font2 = PDF_load_font(p, "Times", 0, "host", "");
if (font2 == -1) {
printf("Error: %s\n", PDF_get_errmsg(p));
PDF_delete(p);
return(2);
}
PDF_setfont(p, font2, 24);
PDF_set_text_pos(p, 50, 500);
PDF_show(p, "Suite...");
PDF_continue_text(p, "(says Flubb)");
//
PDF_end_page_ext(p, "");
PDF_end_document(p, "");
}
PDF_CATCH(p) {
printf("PDFlib exception occurred in hello sample:\n");
printf("[%d] %s: %s\n",
PDF_get_errnum(p), PDF_get_apiname(p), PDF_get_errmsg(p));
PDF_delete(p);
return(2);
}
PDF_delete(p);
Nouveau framework et moteur 3D
Schéma d'un moteur 3D simple à appréhender, fonctionnel (objets procéduraux - metaball, terrains -, effets type post-prod, rendus hiérarchiques - personnages -, GUI 3D, films en tant que textures, particules. Il faut rassembler toutes les idées qui surgissent.
Plusieurs Scene3D gérées par un moteur de gestion d'objets (faut-il plusieurs moteur 3D ?). Chaque objets à une interface de rendu qui prépare ses données spécifiquement pour un moteur de rendu, géré par Renderer appelé par le moteur. Un objet 3D est rattaché à une scène et un viewport est rattaché à un moteur 3D. Une scène peut être rattachée à plusieurs viewport. Un objet 3D contient sa description 3D qu'il peut communiquer sous certaines formes à son renderer via son interface de rendu. S'il y a n objets il y a approximativement log(n) interfaces de rendus présentes en run-time. Une interface de rendu peut être : objet classique (géo+topo+texture), objet procédural, moteur de particule etc. Des sous renderer pourront gérer les films au sein de textures. La hiérarchie est gérée par le moteur haut-niveau, la position et l'orientation d'un objet sont contenues dans l'objet lui-même.
A faire de toute urgence donc.
J'ai rassemblé ci-dessous des notes C++ représentant les axiomes de bases implémentées par le framework pour toutes les utilisations auxquelles je le destine.
class BaseObject
{
private:
BaseObject(); //On ne peut pas faire de new Engine() par exemple
~BaseObject(); //Seul une factory peut effacer réellement un objet, sinon il est collecté lors d'un remove
friend class Factory();
public:
//Fonctions génériques de (dé)sérialisations et d'import/export XML
HCODE toXML(XMLElement* dest);
HCODE toXML(String& dest);
HCODE fromXML(const XMLElement* obj); //Initialise l'objet courant depuis une description XML
HCODE fromXML(const String& obj); //Initialise l'objet courant depuis une description XML
HCODE serialize(Flow& output);
HCODE unserialize(Flow& input);
//Fonctions communiquant avec d'autres objets
HCODE send(ObjectId dest, Message& msg)
HCODE getNextMessage(Message& msg);
HCODE flushMessage();
//Thread management de l'objet
//Gestion des propriétés de l'objet : ses données / champs, ses méthodes / actions
HCODE Get(const String& fieldName, Field& field); //Récupère la valeur d'un champ de l'objet courant
HCODE Set(const String& fieldName, const Field& field); //Fixe la valeur d'un champ de l'objet courant
String compName = type de l'objet
//Références maintenues par l'objet : des références
delete(); //Efface l'objet et les éventuels liens qu'il avait avec d'autres
//.............
//Ses champs
Array<Field> Fields;
ObjectId ObjectSchema; //Référence du schéma (la structure) de l'objet
uint Id; //L'Id unique de l'objet courant
};
Objets utilitaires : Field, Array, String, HashTable, Flow (pour les flux de lecture ou d'écriture, sur disque, HTTP ou autres.).
//Tous les objets sont représentés par leur Id, unique, et gérées par un singleton : Objects
class ObjectId
{
operator->(const String& funcName);
};
//Une classe qui crée des composants
class Objects
{
HCODE RegisterType() //Enregistre un type connu et ses champs
HCODE FromType //IDs de tous les objets d'un certain type
HCODE Select //Requête complète (plus complexe mais adapté à des utilisations plus pointues que FromType)
ObjectId FromId() //Renvoie l'ObjectId d'un objet donné
ObjectId createComponent(const String& compName)
{
BaseObject* NewObject = new BaseObject();
NewObject->ObjectSchema = Type[compName][\"schema\"];
}
};
//Une fonction globale pour créer des composants
ObjectId CreateComponent(const String& compName)
{
ObjectId Fact = Objects->getFactory();
if (!Fact) return LastError();
return Fact->createComponent(compName);
};
Classe de base dont devrait hériter tous les composants
Selection d'objets
Il faut une méthode pour, avec une zone rectangulaire de sélection, sélectionner le plus rapidement possible les objets, 2D pour commencer, dont la bounding-box est interceptée. Je pense à deux range trees (ou des priority tree) pour le stockage des bbox (AABB) - un arbre pour chacune des dimensions considérées, et à deux hash-tables pour le parcours des deux arbres et l'instersection des 4 interrogations suivantes, si S est l'ensemble des objets de la scène :
L1 = { o de S tel que (o.bbox.x1 || o.bbox.x2) >= selectArea.y1 && !(o.bbox.x1 > selectArea.y2) }
L2 = L1 ∩ { o de S tel que (o.bbox.x1 || o.bbox.x2) <= selectArea.y2 && !(o.bbox.x2 < selectArea.y1) }
L3 = L2 ∩ { o de S tel que (o.bbox.y1 || o.bbox.y2) >= selectArea.y1 && !(o.bbox.y1 > selectArea.y2) }
L4 = L3 ∩ { o de S tel que (o.bbox.y1 || o.bbox.y2) >= selectArea.y2 && !(o.bbox.y2 > selectArea.y1) }
Librairie de Math
Librairie de math
La librairie que je suis en train de concevoir pour exécuter, entre autres choses, des calculs sur des polynômes, des vecteurs et des matrices.
#include <stdarg.h>
#include <math.h>
using namespace std;
class QiXMath : public std::exception
{
public:
QiXMath(char* msg) { _whatMsg = msg; }
virtual const char* what() const throw() { return _whatMsg; }
protected:
char* _whatMsg;
};
//Pour représenter des fractions, ce qui est très utile pour les polynôme quand on veut des calculs exacts.
//Note : pour simplifier des nombres décimaux qui ont des séquences répétitives voir http://en.wikipedia.org/wiki/QiFraction_(mathematics)
//TOCHECK : l'opérateur /(int) ne doit pas être nécéssaire puisque j'ai un constructeur qui a un int en entrée, pourquoi dois-je en avoir un ???
template <class T>
class QiFraction
{
public:
//Faire un constructeur avec un seul paramètre : le numérateur.
QiFraction(T n, T d) { _n = n; _d = d; }
QiFraction(T n=0) { _n = n; _d = 1; }
QiFraction(float n) { _n = (T) n; _d = 1; }
QiFraction(int n) { _n = (T) n; _d = 1; }
void dump() const
{
if (_n == 0 || _d == 1) cout << _n;
else {
if (_n == _d) cout << "1";
else cout << _n << "/" << _d;
}
}
QiFraction<T>& operator+=(const QiFraction<T>& a)
{
T P = pgcd(_d, a._d);
T NewD = (_d * a._d) / P;
_n = _n * (NewD / _d) + a._n * (NewD / a._d);
_d = NewD;
return *this;
}
QiFraction<T>& operator-=(const QiFraction<T>& a)
{
T P = pgcd(_d, a._d);
T NewD = (_d * a._d) / P;
_n = _n * (NewD / _d) - a._n * (NewD / a._d);
_d = NewD;
return *this;
}
QiFraction<T>& operator*=(const QiFraction<T>& a)
{
_n *= a._n;
_d *= a._d;
//On simplifie la fraction
T Common = pgcd(_n, _d);
_n /= Common;
_d /= Common;
return *this;
}
QiFraction<T>& operator/=(const QiFraction<T>& a)
{
_n *= a._d;
_d *= a._n;
//On simplifie la fraction
T Common = pgcd(_n, _d);
_n /= Common;
_d /= Common;
return *this;
}
QiFraction<T> operator+(const QiFraction<T>& a) const
{
QiFraction Result(_n, _d);
return Result += a;
}
QiFraction<T> operator-(const QiFraction<T>& a) const
{
QiFraction Result(_n, _d);
return Result -= a;
}
QiFraction<T> operator*(const QiFraction<T>& a) const
{
QiFraction Result(_n, _d);
return Result *= a;
}
QiFraction<T> operator/(const QiFraction<T>& a) const
{
QiFraction Result(_n, _d);
return Result /= a;
}
QiFraction<T> operator/(T a) const
{
QiFraction<T> Result(_n, _d);
return Result /= QiFraction<T>(a);
}
QiFraction<T> operator/(int a) const
{
QiFraction<T> Result(_n, _d);
return Result /= QiFraction<T>(a);
}
bool operator>=(float t) const { return (float)_n/(float)_d > t; }
bool operator==(float t) const { return (float)_n/(float)_d == t; }
operator float() const { return (float)_n/(float)_d; }
QiFraction<T>& inverse()
{
T Tmp = _n;
_n = _d;
_d = _n;
return *this;
}
T pgcd(T u, T v/*, int verbose=false*/)
{
T M = 1;
if (u<0) u = (T)0-u;
if (v<0) v = (T)0-v;
while (u && v) {
// if (verbose) printf("pgcd(%d, %d)\n", u, v);
if (!(u&1) && !(v&1)) { M <<= 1; u>>=1, v>>=1; }
else if (!(u&1) && v&1) u>>=1;
else if (u&1 && !(v&1)) v>>=1;
else { //Les deux nombres sont impairs
if (u>v) u=(u-v)>>1;
else v=(v-u)>>1;
}
}
return M * (u ? u : v);
}
//Note : ppcm(a,b) = (a*b)/pgcd(a,b)
T _n, _d; //Numérateur et dénominateur
};
//###TODO (25%) : Exceptions
//###TODO : cacher l'évaluation du degré d'un polynôme
//###TODO : faire la factorisation simple d'un polynôme
//###TODO : faire des opérateurs pour QiMatrix et QiPolynomial
//###TODO : faire des opérateurs pour QiVector
template <class T>
class QiPolynomial
{
public:
QiPolynomial(int rank)
{
_comps = NULL;
_init(rank);
}
~QiPolynomial()
{
DELETEARRAY(_comps);
}
QiPolynomial(const QiPolynomial<T>& original)
{
if (this != &original) {
_init(original.rank());
int i;
for(i=0; i<=rank(); i++) _comps[i] = original.get(i);
}
}
protected:
void _init(int rank)
{
if (rank<0) return;
_rank = rank;
_comps = new T[_rank+1];
}
void _expand(int nbWantedSlots)
{
int NewSize = nbWantedSlots;
_comps = new T[NewSize];
if (!_comps) throw new QiXMath("QiPolynomial::_expand : NotImplemented");
// memcpy();
}
public:
//
void null()
{
int i;
for(i=0; i<=rank(); i++) _comps[i] = 0.0f;
}
void primitive()
{
int Degree = degree();
if (rank() < Degree+1) _expand(Degree+1);
int i, MaxIndex = degree();
for(i=MaxIndex; i>=0; i--) _comps[i+1] = _comps[i]/(i+1);
_comps[0] = 0.0f;
}
void add(const QiPolynomial<T>& op)
{
int i;
int MaxIndex = op.rank();
if (rank() < MaxIndex) MaxIndex = rank();
for(i=0; i<=MaxIndex; i++) set(i, get(i) + op.get(i));
}
QiPolynomial<T>& operator *= (const QiPolynomial<T>& a)
{
multiply(a);
return *this;
}
bool multiply(const QiPolynomial<T>& op)
{
if (degree() + op.degree() > rank()) return false;
QiPolynomial Temp(degree() + op.degree());
int MaxIt = op.degree(), i, j;
int CurrentDegree = degree();
Temp.null();
for(i=0; i<=MaxIt; i++) {
for(j=0; j<=CurrentDegree; j++) {
T CurrentValue = Temp.get(i+j);
T NewInc = op.get(i) * get(j);
Temp.set(i+j, CurrentValue + NewInc);
}
}
set(Temp);
return true;
}
void multiply(T coeff)
{
int i;
int MaxIndex = degree();
for(i=0; i<=MaxIndex; i++) set(i, get(i)*coeff);
}
QiPolynomial<T>& operator /= (const T& a)
{
int i;
int MaxIndex = degree();
for(i=0; i<=MaxIndex; i++) {
set(i, get(i) / a);
}
return *this;
}
void set(const QiPolynomial& src)
{
int i;
null();
int MaxIndex = rank();
if (MaxIndex>src.rank()) MaxIndex = src.rank();
for(i=0; i<=MaxIndex; i++) set(i, src.get(i));
// _rank = src.rank();
}
void setRaw(int maxDegree, ...)
{
if (maxDegree > rank()) return;
va_list args;
va_start(args, maxDegree);
int i, j;
for(i=maxDegree; i>=0; i--) {
float Value = (float) va_arg(args, double);
_comps[i] = Value;
}
va_end(args);
}
//On remplace la variable x du polynôme par un autre polynôme (x par x+1 par exemple).
//On substitue donc Q(x) à x dans P(x), ce qui donne P(Q(x)), un autre polynôme en x.
//La méthode :
void substitute(const QiPolynomial& newVar)
{
QiPolynomial Value(newVar.degree() + degree()), Total(newVar.degree() + degree());
QiPolynomial Param(newVar.degree() + degree());
int i;
Param.null();
Param.set(0, 1.0f);
for(i=0; i<=degree(); i++) {
Value.set(Param);
Value.multiply(get(i));
Total.add(Value);
Param.multiply(newVar);
}
set(Total);
}
T get(int index) const
{
if (index<0 || index>rank()+1) throw new QiXMath("QiPolynomial::get out of bound");
return _comps[index];
}
void set(int index, T value)
{
if (index<0 || index>rank()+1) throw new QiXMath("QiPolynomial::set out of bound");
_comps[index] = value;
}
float evaluate(T x) const
{
int MaxIndex = degree();
float Current = 1.0f, Total = 0.0f;
int i;
for(i=0; i<=MaxIndex; i++) {
Total += Current * _comps[i];
Current *= x;
}
return Total;
}
int degree() const //Renvoie le degré du polynôme courant : l'indice du premier coefficient non-nul en partant des puissances élevées.
{
int i = rank();
while (get(i) == 0.0f && i>0) i--;
return i;
}
void dump() const
{
int i, Degree = degree();
for(i=Degree; i>=0; i--) {
if (i<Degree && get(i)>=0.0f) printf("+");
printf("%.10f", (float) get(i));
if (!i) continue;
if (i==1) printf("X");
if (i>1) printf("X^%d", i);
}
printf("\n");
}
void dumpObjects() const
{
int i, Degree = degree();
for(i=Degree; i>=0; i--) {
T CurValue = get(i);
if (i<Degree && CurValue>=0.0f) printf("+");
if (CurValue != 0.0f) {
get(i).dump();
if (!i) continue;
if (i==1) printf("X");
if (i>1) printf("X^%d", i);
}
}
printf("\n");
}
int rank() const { return _rank; }
protected:
T* _comps;
int _rank;
};
template <class T>
class QiVector
{
public:
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
class ExQiVector : public std::exception
{
public:
ExQiVector(char*) { }
};
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
QiVector(int rank) { _comps = new T[rank]; _rank = rank;}
~QiVector() { DELETEARRAY(_comps) }
void null() {
int i;
for(i=0; i<rank(); i++) _comps[i] = 0.0f;
}
//On crée un vecteur de base
void base(int index)
{
if (index<0 || index>=rank()) return;
null();
set(index, 1.0f);
}
//###TODO : faire des exceptions pour les out of bounds.
bool set(int index, const T& value) {
if (index<0 || index >= rank()) return false;
_comps[index] = value;
return true;
}
bool set(QiVector<T>& newValue)
{
if (rank() != newValue.rank()) return false;
int i;
for(i=0; i<rank(); i++) _comps[i] = newValue.get(i);
return true;
}
bool add(int index, const T& value)
{
if (index<0 || index>=rank()) return false;
return set(index, get(index) + value);
}
T get(int index) const
{
return _comps[index];
}
QiVector<T>& operator=(const QiVector<T>& original)
{
//###TODO : si les rangs sont différents on doit changer le rang de l'objet courant
if (this != &original && rank() == original.rank()) {
int i;
for(i=0; i<rank(); i++) _comps[i] = original.get(i);
}
return *this;
}
int rank() const { return _rank; }
void dump() const
{
int i;
printf("(");
for(i=0; i<rank(); i++) {
if(i) printf(", ");
printf("%f", _comps[i]);
}
printf(")\n");
}
void dumpObjects() const
{
int i;
printf("(");
for(i=0; i<rank(); i++) {
if(i) printf(", ");
_comps[i].dump();
}
printf(")\n");
}
protected:
T* _comps;
int _rank;
};
//Matrice carrée constituée de vecteurs QiVector
template <class T>
class QiMatrix
{
public:
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
class ExQiMatrix : public std::exception
{
public:
ExQiMatrix(char*) { }
};
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
QiMatrix(int rank) { _init(rank); }
protected:
bool _init(int rank)
{
_comps = new QiVector<T>*[rank];
int i;
for(i=0; i<rank; i++) _comps[i] = new QiVector<T>(rank);
_rank = rank;
return true;
}
bool _release()
{
int i;
for(i=0; i<rank(); i++) {
DELETESINGLE(_comps[i]);
}
DELETEARRAY(_comps);
}
void _count() const
{
_nbUps = 0, _nbLows = 0, _nbDiags = 0;
int i, j;
for(i=0; i<rank(); i++) {
for(j=0; j<rank(); j++) {
float Value = get(i, j);
if (i>j && Value) _nbLows++;
if (i<j && Value) _nbUps++;
if (i==j && Value) _nbDiags++;
}
}
//
_nbItemsInHalf = _rank*(_rank-1)/2 + _rank;
}
public:
~QiMatrix() { _release(); }
void null() { int i; for(i=0; i<rank(); i++) _comps[i]->null(); }
void identity()
{
null();
int i;
for(i=0; i<rank(); i++) _comps[i]->set(i, 1.0f);
}
T get(int i, int j) const
{
if (i<0 || j<0) return 0.0f;
if (i>=rank() || j>=rank()) return 0.0f;
return _comps[i]->get(j);
}
QiVector<T>& get(int index) const
{
if (index<0 || index>=rank()) return *_comps[0];
return *_comps[index];
}
bool set(int i, int j, T value)
{
if (j<0 || j>=rank()) return false;
_comps[i]->set(j, value);
return true;
}
bool setRaw(int setRank, ...) {
if (setRank != rank()) return false;
va_list args;
va_start(args, setRank);
int i, j;
for(i=0; i<rank(); i++) {
for(j=0; j<rank(); j++) {
if (!_comps[i]->set(j, (float) va_arg(args, double))) {
va_end(args);
return false;
}
}
}
va_end(args);
return true;
}
bool setRow(int index, QiVector<T>& row)
{
if (rank() != row.rank()) return false;
_comps[index]->set(row);
return true;
}
//Multiplication matrice-matrice inplace
QiMatrix<T>& operator *= (const QiMatrix<T>& op)
{
multiply(op);
return *this;
}
bool multiply(const QiMatrix<T>& op)
{
if (rank() != op.rank()) return false;
QiVector<T> Temp(rank());
int i, j, k;
for(i=0; i<rank(); i++) {
for(Temp.null(), j=0; j<rank(); j++) {
for(k=0; k<rank(); k++) {
Temp.add(j, get(i, k) * op.get(k, j));
}
}
setRow(i, Temp);
}
return true;
}
//
QiVector<T> operator * (const QiVector<T>& op) const
{
QiVector<T> Result(op.rank());
multiply(op, Result);
return Result;
}
void multiply(const QiVector<T>& op, QiVector<T>& result) const
{
int i, j;
for(i=0; i<rank(); i++) {
T Total = 0.0f;
for(j=0; j<rank(); j++) {
Total += get(i, j) * op.get(j);
}
result.set(i, Total);
}
}
//Copy constructor
QiMatrix(const QiMatrix<T>& original)
{
_init(original.rank());
int i;
for(i=0; i<rank(); i++) *_comps[i] = original.get(i);
}
bool isLower() const
{
_count();
return _nbLows + _nbDiags == _nbItemsInHalf;
}
bool isDiagonal() const
{
_count();
return _nbDiags == rank();
}
//Inverse la matrice courante "inplace"
void inverse()
{
if (isLower()) {
//Cas pour les matrices triangulaires inférieures
QiVector<T> Temp(rank());
int i, j, k;
T Total;
for(i=0; i<rank(); i++) {
Temp.null();
for(j=0; j<=i; j++) {
Total = 0.0f;
for(k=j; k<i; k++) {
T NormalIK = get(i, k);
T InvKJ = get(k, j);
Total += NormalIK * InvKJ;
}
T DeltaIJ = i == j ? 1.0f : 0.0f;
T MainCoeff = get(i, i);
T InverseCoeff = (DeltaIJ - Total) / MainCoeff;
Temp.set(j, InverseCoeff);
}
setRow(i, Temp);
}
} else if(isDiagonal()) {
int i;
for(i=0; i<rank(); i++) set(i, i, 1.0f/get(i, i));
} else throw new QiXMath("QiMatrix::inverse : not yet implemented.");
}
void dump() const
{
int i;
for(i=0; i<rank(); i++) _comps[i]->dump();
}
void dumpObjects() const
{
int i;
for(i=0; i<rank(); i++) _comps[i]->dumpObjects();
}
int rank() const { return _rank; }
//
bool isUpper() const;
bool isInversible() const;
protected:
QiVector<T>** _comps;
int _rank;
//
mutable int _nbUps, _nbLows, _nbDiags, _nbItemsInHalf;
};
Bien se souvenir qu'ici je cherche plus à être exact que rapide, c'est sûr que pour un moteur 3D j'utiliserai les classes QiMatrix et QiVector avec beaucoup de pincettes !!!