Graphic Stream : Coding

Annexe : Intégration de Xna dans WPF

valentin — Mon, 20 Jul 2009 11:58:00 GMT

Il existe de nombreuses méthodes pour afficher des scènes 3D à base de Xna dans un environnement WPF. Certaines souffrent de problèmes de lenteur (réalisées le plus souvent à base de WindowsFormHost), d’autres ne permettent qu’une interaction limitée avec les contrôles et l’interface WPF. Réaliser des affichages multiples comme on peut en avoir dans des logiciels comme Maya devient alors problématique :

Il existe pourtant un moyen, relativement simple d’arriver à ses fins. Ce moyen consiste tout simplement à donner une impression visuelle à l’utilisateur d’une intégration Xna parfaite dans un widget WPF alors qu’il n’en est rien. La clé de cet effet réside dans une parfaite manipulation des fenêtres.

Principe

Nous voulons pouvoir intégrer notre scène Xna dans une interface WPF de la même manière que nous intégrons un Canvas ou un quelconque widget à une interface. Or le meilleur moyen d’afficher une scène 3D en Xna est de l’incorporer dans une fenêtre. Impossible en effet d’obtenir le handle de tout contrôle en WPF comme on peut le faire en Winform. L’astuce consiste alors à réécrire une partie du framework Xna tournant autour de la classe Game. Le but étant de faire hériter une nouvelle classe Game d’un Panel (dans notre cas un Canvas) afin de pouvoir l’intégrer dans l’arborescence visuel WPF. La surface visuelle de ce panel sera ainsi la zone d’affichage de la scène Xna liée. Pourtant nous venons de dire qu’il n’était pas possible d’obtenir un handle d’un contrôle visuel qui n’hérite pas de Window. Comment y afficher de la 3D avec Xna donc ? Nous allons tout simplement afficher une fenêtre sans bordure exactement au dessus de ce panel. Cette fenêtre sera toujours au dessus lorsque l’application aura le focus et que le panel sera visible, et sera cachée dans le cas contraire. De même, lorsque le panel n’est pas visible, nous stopperons l’activité du jeu.

Chaque modification de la taille ou de la position du panel entrainera une modification équivalente chez la fenêtre sus-jacente.

Cette fenêtre se trouvant donc exactement au dessus du panel et ayant une taille identique l’illusion est parfaite.

Réalisation

La première étape consiste donc à réécrire une partie des classes de l’assembly Microsoft.Xna.Framework et Microsoft.Xna.Framework.Game. Ce afin de s’émanciper du fonctionnement de base de la classe Game trop fortement couplée à un fonctionnement sur fenêtre unique. Le projet Arcane.Xna.Presentation reprend donc une partie des classes de ces assemblies pour une utilisation avec WPF.

Rien de bien compliqué. Seules les classes Game et GameHost sont réellement intéressantes ici.

La classe Game comme précisé précédemment correspond à la zone d’affichage de nos scènes 3D dans les interfaces utilisateurs WPF. Elle hérite de Canvas. L’utilisation de Canvas répond à un besoin bien particulier que nous présenterons plus loin. La classe Game ne se différencie de la classe Game de l’assembly Microsoft.Xna.Framework.Game que par quelques membres. Tout d’abord elle possède un membre de type GameHost qui est en fait la fenêtre se positionnant juste au dessus. Elle possède de même un membre nommé _tichGenerator qui va permettre de mettre à jour l’affichage à intervalle réguliers.

Le constructeur initialise ses membres ainsi :

this._window = new GameHost(this);

this._window.Closed += new EventHandler(_window_Closed);

this._tickGenerator = new DispatcherTimer();

this._tickGenerator.Tick += new EventHandler(_tickGenerator_Tick);

Il commence par créer la fenêtre qui sera située au dessus de lui, et enregistre l’événement Closed afin de fermer la scène 3D. L’object de type DispatcherTimer est utilisé pour la boucle de jeu et permet donc d’appeler de manière régulière les méthodes Update et Draw. Sa vélocité dépend de la propriété IsFixedTimeStep.

Dernier élément important, l’enregistrement de l’événement IsVisibleChange :

this.IsVisibleChanged += new DependencyPropertyChangedEventHandler(GameCanvas_IsVisibleChanged);

L’activation du DispatcherTimer est en fonction de cette visibilité.

La classe GameHost est tout aussi simple. Elle créé une fenêtre sans bordure, invisible sur la barre des tâches et qui enregistre l’événement SizeChanged du panel Xna et LocationChanged de la fenêtre de plus haut niveau. Ces deux événements lui permettent de toujours être au dessus du panel Xna en effectuant un appel à la méthode UpdateBounds :

public void UpdateBounds()
{
    if (this.IsVisible)
    {
        GeneralTransform gt = this.game.TransformToVisual(this.TopLevelWindow);

        this.Width = this.game.ActualWidth;
        this.Height = this.game.ActualHeight;

        this.Left = this.TopLevelWindow.Left + gt.Transform(new Point(0, 0)).X;
        this.Top = this.TopLevelWindow.Top + gt.Transform(new Point(0, 0)).Y;
    }
}

Cette méthode détermine la position de la fenêtre courante en se basant sur la fenêtre de plus haut niveau (la fenêtre contenant le panel Xna de la classe Game). Elle lui affecte en outre, la même largeur et hauteur que le panel Xna.

Là encore la fenêtre s’enregistre sur l’événement IsVisibleChange de ce dernier afin de se rendre visible ou non.

Premier Exemple

Nous baserons nos exemple sur le framework AvalonDock (http://www.codeplex.com/AvalonDock), un moyen efficace de créer des interfaces dockable à la Visual Studio très facilement. Un moyen aussi pour nous de montrer la puissance et la simplicité de notre système dans des interfaces WPF très avancées.

Notre solution contient donc un projet nommé Demo qui correspond au projet d’exemple d’AvanlonDock légèrement modifié. Nous avons ajouté une classe héritant de Game qui va afficher un cube tournant sur lui-même.

Cette classe a tout simplement été extraite d’une application Xna pur pour être ajouté dans ce projet, et ce, sans aucune modification (ou presque) :

public class RotatingCubeGame : Arcane.Xna.Presentation.Game
{

    #region Fields

    Arcane.Xna.Presentation.GraphicsDeviceManager graphics;
    SpriteBatch spriteBatch;
    BasicEffect effect;
    VertexPositionColor[] vertices;
    Vector3 position = Vector3.Zero;
    Vector3 size = Vector3.One;
    VertexBuffer vertexBuffer;
    IndexBuffer indexBuffer;

    #endregion

    #region Constructors

    public RotatingCubeGame()
    {
        if (!(System.ComponentModel.DesignerProperties.GetIsInDesignMode(this)))
        {
            graphics = new Arcane.Xna.Presentation.GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
        }
    }

    #endregion

    /// <summary>
    /// Allows the game to perform any initialization it needs to before starting to run.
    /// This is where it can query for any required services and load any non-graphic
    /// related content. Calling base.Initialize will enumerate through any components
    /// and initialize them as well.
    /// </summary>
    protected override void Initialize()
    {
         base.Initialize();
       // TODO: Add your initialization logic here
        this.graphics.IsFullScreen = false;
        this.graphics.PreferredBackBufferWidth = 800;
        this.graphics.PreferredBackBufferHeight = 600;
        this.graphics.ApplyChanges();

        this.Window.Title = "";

        this.InitializeVertices();
        this.InitializeIndices();

    }

    private void InitializeVertices()
    {
        vertices = new VertexPositionColor[ 8 ];
        vertices[0].Position = new Vector3(-10f, -10f, 10f);
        vertices[0].Color = Color.Yellow;
        vertices[1].Position = new Vector3(-10f, 10f, 10f);
        vertices[1].Color = Color.Green;
        vertices[2].Position = new Vector3(10f, 10f, 10f);
        vertices[2].Color = Color.Blue;
        vertices[3].Position = new Vector3(10f, -10f, 10f);
        vertices[3].Color = Color.Black;
        vertices[4].Position = new Vector3(10f, 10f, -10f);
        vertices[4].Color = Color.Red;
        vertices[5].Position = new Vector3(10f, -10f, -10f);
        vertices[5].Color = Color.Violet;
        vertices[ 6 ].Position = new Vector3(-10f, -10f, -10f);
        vertices[ 6 ].Color = Color.Orange;
        vertices[7].Position = new Vector3(-10f, 10f, -10f);
        vertices[7].Color = Color.Gray;
        this.vertexBuffer = new VertexBuffer(this.graphics.GraphicsDevice, typeof(VertexPositionColor), 8, BufferUsage.WriteOnly);
        this.vertexBuffer.SetData(vertices);
    }

    private void InitializeIndices()
    {
        short[] indices = new short[36]{
            0,1,2, //face devant
            0,2,3,
            3,2,4, //face droite
            3,4,5,
            5,4,7, //face arrière
            5,7,6,
            6,7,1, //face gauche
            6,1,0,
            6,0,3, //face bas
            6,3,5,
            1,7,4, //face haut
            1,4,2};
        this.indexBuffer = new IndexBuffer(this.graphics.GraphicsDevice, typeof(short), 36, BufferUsage.WriteOnly);
        this.indexBuffer.SetData(indices);
    }

    /// <summary>
    /// LoadContent will be called once per game and is the place to load
    /// all of your content.
    /// </summary>
    protected override void LoadContent()
    {
        // Create a new SpriteBatch, which can be used to draw textures.
        spriteBatch = new SpriteBatch(GraphicsDevice);

        // TODO: use this.Content to load your game content here
        this.effect = new BasicEffect(graphics.GraphicsDevice, null);
        this.effect.View = (Matrix.CreateLookAt(new Vector3(20, 30, -50), Vector3.Zero, Vector3.Up));
        this.effect.Projection = (Matrix.CreatePerspectiveFieldOfView(MathHelper.PiOver4, this.GraphicsDevice.Viewport.AspectRatio, 0.1f, 100f));
        this.effect.VertexColorEnabled = true;
    }

   /// <summary>
    /// Allows the game to run logic such as updating the world,
    /// checking for collisions, gathering input and playing audio.
    /// </summary>
    /// <param name="gameTime">Provides a snapshot of timing values.</param>
    protected override void Update(GameTime gameTime)
    {
        if (Keyboard.GetState()[Keys.Up] == KeyState.Down)
            position += Vector3.Up;
        if (Keyboard.GetState()[Keys.Down] == KeyState.Down)
            position += Vector3.Down;
        if (Keyboard.GetState()[Keys.Left] == KeyState.Down)
            position += Vector3.Left;
        if (Keyboard.GetState()[Keys.Right] == KeyState.Down)
            position += Vector3.Right;
        if (Keyboard.GetState()[Keys.PageUp] == KeyState.Down)
            size += new Vector3(0.1f, 0.1f, 0.1f);
        if (Keyboard.GetState()[Keys.PageDown] == KeyState.Down)
            size -= new Vector3(0.1f, 0.1f, 0.1f);

      // Allows the default game to exit on Xbox 360 and Windows
        if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
           this.Exit();

        float fAngle = (float)gameTime.TotalGameTime.TotalSeconds;

        //la transformation en elle même
        Matrix world = Matrix.CreateRotationY(fAngle) * Matrix.CreateRotationX(fAngle)
                            * Matrix.CreateScale(size)
                            * Matrix.CreateTranslation(position);

        this.effect.World = (world);
        base.Update(gameTime);
    }


    /// <summary>
    /// This is called when the game should draw itself.
    /// </summary>
    /// <param name="gameTime">Provides a snapshot of timing values.</param>
    protected override void Draw(GameTime gameTime)
    {
        this.graphics.GraphicsDevice.Vertices[0].SetSource(this.vertexBuffer, 0, VertexPositionColor.SizeInBytes);
        this.graphics.GraphicsDevice.Indices = this.indexBuffer;
        this.graphics.GraphicsDevice.VertexDeclaration = new VertexDeclaration(this.graphics.GraphicsDevice, VertexPositionColor.VertexElements);
        graphics.GraphicsDevice.Clear(Color.CornflowerBlue);

        // TODO: Add your drawing code here
        this.effect.Begin();

        foreach (EffectPass pass in effect.CurrentTechnique.Passes)
        {
            pass.Begin();
            this.graphics.GraphicsDevice.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, 8, 0, 12);
            pass.End();
        }

        effect.End();

        base.Draw(gameTime);
    }
}

Rien de bien compliqué ici (le code est extrait de l’article 6). La première modification est de faire hériter la classe RotatingCubeGame de l’objet Game de notre assembly et non celle de l’assembly Microsoft.Xna.Framework.Game. La seconde modification consiste à entourer les initialisations réalisées dans le constructeur de :

System.ComponentModel.DesignerProperties.GetIsInDesignMode(this)

Afin de s’assurer que notre jeu ne sera pas en partie créé dans le designer de Visual Studio. Le reste est très simple. Nous avons juste remplacé le contenu de chaque DockablePane dans le code Xaml de Window1 par un :

<Demo:RotatingCubeGame></Demo:RotatingCubeGame>

Le resultat nous donne :

Bien évidemment notre système respecte les avantage d’AvalonDock en permettant un docking puissant et ce, sans perturber nos scène 3D:

Pas mal, mais on peut faire mieux.

Intégration de Widgets

Pourquoi ne pas tenter d’afficher des widgets (bouton, label, Grid, Canvas, …) dans notre scène 3D pour faire une intégration avec WPF de manière parfaite.

Nous pourrions être tentés d’ajouter ces éléments directement à la fenêtre GameHost. Mais à l’affichage nous aurions des problèmes de scintillement (deux types d’affichages différents vectoriel et 3D à réaliser sur une même zone clip n’est pas forcement bon…). Nous allons donc simplement rajouter une nouvelle fenêtre au dessus de la fenêtre existante, sans bordure elle aussi :

Son contenu sera directement relié au contenu du panel Xna (le Canvas). La classe GameHost contiendra désormais un nouveau membre nommé _frontWindow de type Window. Elle exposera en internal une propriété nommée WPFHost donnant accès au Content de cette window :

internal object WPFHost
{
    get
    {
        return this._frontWindow.Content;
    }
    set
    {
        this._frontWindow.Content = value;
    }
}

La classe Game exposera elle-aussi le Content de cette window à l’aide d’une propriété portant le même nom :

public object WPFHost
{
    get
    {
        if (!(System.ComponentModel.DesignerProperties.GetIsInDesignMode(this)))
            return this.Window.WPFHost;
        else
            return (base.Children[0] as ContentControl).Content;
    }
    set
    {
        if (!(System.ComponentModel.DesignerProperties.GetIsInDesignMode(this)))
            this.Window.WPFHost = value;
        else
            (base.Children[0] as ContentControl).Content = value;
    }
}

Cette propriété détermine si nous sommes en mode design (sous visual studio) ou en mode runtime. En mode design nous utilisons le fonctionnement classique du Canvas dont hérite notre classe Game, en mode runtime nous ciblons directement la window. Cela nous permet en mode design de pouvoir voir l’UI de notre contrôle et de pouvoir la modifier à la souris.

En outre nous marquons la classe Game de l’attribut :

[System.Windows.Markup.ContentProperty("WPFHost")]

Permettant de mettre du contenu direct en Xaml :

La page Window1.xaml a été modifiée pour rajouter du contenu à plusieurs RotatingCubeGame comme le montre l’image ci-dessus. Nous avons ajouté des shapes et paths purs pour reproduire le personnage orange et jaune symbolisant le Xna, des boutons et label liés par des événements et un FlowDocument avec scrolling.

Conclusion

L’assembly Arcane.Xna.Presentation présente un moyen simple d’intégrer de manière professionnel du Xna à ses applications WPF. Le seul vrai défaut qu’on peut lui trouver est la création de deux fenêtre par panel Xna. Il faut savoir que le nombre de fenêtre affichable sous Windows est malheureusement limité. Le résultat fonctionne tout de même parfaitement et peut être utilisé pour des applications professionnelles :

Vous pouvez télécharger le code ici.

A bientôt sur ce Blog !

Valentin Billotte

Optimization de code pour du Xna rapide et efficace !

valentin — Sat, 28 Feb 2009 13:53:00 GMT

Je dois en omettre un grand nombre, si vous en avez d'autres n'hesitez pas à me les soumettre que je les rajoute ici !

Première optimisation, les strings :

Eviter tout indexeur à base de string s’il y’a un équivalent à base d’int.

L'instruction :

myEffect.Techniques["Precompiled"] ;

Est bien moins efficace q'un :

const int TechnikIndex = 0;

myEffect.Technique[TechnikIndex]

Eviter au maximum la class string, si on a besoin de puissance. En C# tout modification d'une string entraine la création d'une nouvelle instance et donc une allocation mémoire. Une string N EST JAMAIS MODIFIABLE et l'allocation mémoire est une opération très couteuse en temps. Il faut donc travailler un maximum avec StringBuilder.

Besoin de comprendre le string intern pool. Quand on créé une string, le clr regarde dans un pool interne si elle existe avant de la créer. (méthode statique Intern de la classe string).

Donc string jamais collectés comme les objets communs dans le GC.

Boxing/unboxing

Boxing passage d'un value type (exemple int) à une classe objet .

Par exemple :

int a = 0;

object o = (object)a;

Unboxing est l'opération inverse.

boxed = 20 fois plus de traitement CPU qu'une simple affectation de ref

unboxed = 4 fois plus

= généric autant que faire se peux (optimization en Early binding)

Pour les struct, implementer la méthode ToString (sinon il y’a boxing en objet pour chaque appel à cette méthode)

Array

Jagged Arrays > Rectangular Array ([][] > [,])

Privilegier les for au foreach (moins nécessaire depuis le .Net 3.0)

addrange plutot que add

Range Check important, exemple :

//rapide
for(int i = 0; i < myArray.Length; i++)
{
Console.WriteLine(myArray.ToString());
}
//plus lent
for(int i = 0; i < myArray.Length + y; i++)
{
Console.WriteLine(myArray[i+x].ToString());
}

Dans la seconde boucle le test ne porte pas sur la longueur du tableau traité mais sur une autre valeur, il y’a donc des tests supplémentaire ajouté en IL pour générer une exception en cas de sortir de Bounds.

Methodes :

Il y’a quelque regles simples pour que le compilateur utilise de l’inlined (suppresion à la compilation d'une méthode pour inclure son code en lieu et place de l'instruction appellant la dite méthode) :

32o d'il (8instructions) max par méthode/accesseur/mutateur à "inliner"
pas de structures conditionnelles dans le bloc à inliner
pas de type struct utilisé dans le bloc à inliner
pas de bloc Try/Catch/Finaly dans le bloc à inliner.

Si il n’y a pas besoin de rendre le code compréhensible on priviligiera les chunky call au maximum (méthodes énormes en lieu et place de myriades de petites méthodes qui s’appellent les unes les autres).

Thread

Synchroniser les thread : System.Threading.Interlocked class

Exception

retourner des enum plutot que des exception sur les méthodes critiques

Eviter ce genre de code :

public static void Main(string[] args){
int j = 0;
for(int i = 0; i < 10000; i++){
    try{
      j = i;
      throw new System.Exception();
    } catch {}
}
}

En asp.net, à eviter :

L’instruction : Response.Redirect() elle provoque un ThreadAbortException

Un throw d'exception perturbe gravement l'activité CPU associée à votre applicatif.

Objets

Utiliser au maximum les structure là ou la notion de référence n’est pas importante (besoin ponctuelle d’agrégat ordonné de données) en lieu et place d’une class

(Exemple de la structure Point, Rectangle, etc.) . La gestion en mémoire est alors bien plus efficace et rapide.

Apprecier au maximum l’attribut Fieldoffset qui permet de réaliser l’équivalent de l’Union du langage C pour optimiser la mémoire

Utiliser les weakreference notamment pour le cache, afin de ne pas surcharger la mémoire.

Framework :

Working Set : charger une assembly pour profiter d'une seule de ses méthodes c'est pas bien !

Utiliser vadump.exe pour détecter ca dans son framework

Se servir de Perfmon et de ses attributs (nb de classes chargées, nombre de méthodes, temps passé à loader, JITed, etc.)

Executables :

Précompilation avec ngen.exe pour les exes critiques. Permet de précompiler son application pour un premier lancement rapide.

SQL

connexion ouverte longtemps < multiple ouverture /fermeture de connexion

Datareader > dataset

Annuler le transaction enlistment si inutile

SqlConnection conn = new SqlConnection(

"Server=exasrv01;

Integrated Security=true;

Enlist=false");

Smart Terrain Rendering with Xna using Billod algorithm

valentin — Tue, 30 Sep 2008 12:13:00 GMT

Version Française ici.

If you're a game developer you've already worked on terrain rendering. It is, in my opinion the critical point of a game. Not because conceptually speaking it is the most important visible thing on the screen but because it is the main factor playing on the performance and quality of your application. It is therefore important to use techniques designed to minimize the burden borne by your game to view the ground while preserving its quality display. This article shows a way that attempts to answer this question in XNA.

Conducting a study of game engine designed to help game developers in the Imagine Cup competition, I naturally preferred this important aspect in seeking a way to display a 3D world unlimited real size with an acceptable level of detail.

There are many techniques for displaying world explained by interesting articles. These are often based on a compromise uncomfortable wearing a choice between the size of land or quality level. In addition, they are often prohibitive algorithms.

This article does not appear as the only possible response to the display ground XNA but would just provide an effective solution running for this technology knowing that most of the examples existing on the Web are made in DirectX and OpenGL.

We will split our study in several phases:

· First we describe the problems posed by the display of land and explain the need for optimization.

· We then describe the method used to cut our land into a QuadTree.

· We will explain how we reduce the retail field at distance while keeping up its appearance nearby.

· We will describe a more technical implementation of this technique

· Finally we will see possible optimizations offered to the reader.

The problem

Let's say we wanted to model a land about 10 km by 10km with a degree of detail about 1 meter (1 kilometer = 1000 meters). So we have (without optimization) a grid of 100000 * 100000 to show. We have to specify that that each vertex of the grid has a memory size equal to approximately 40 bytes. It reaches about 4 gigabytes of data to display. The hardware of a lambda PC cannot handle such loads memory. Another problem, such a field modeled in a grid rendering static demand of 200 million triangles per frame. This is a disaster. From the moment the size of the field becomes important and where we add the ground ingredients of usual games, as 3D models, an user interface, animations, performance of a game can no longer follow. This is here, that we have to manage a smart rendering.

It is therefore important that the CPU and / or GPU taken by the display field is as low as possible to keep processing time for other needs of the game. The virtual world offered by most modern games are huge and cannot be done with a simple static grid

The need for optimization is therefore evident. I invite readers to visit http://ww.vterrain.org to discover some presentations techniques other than that presented here.

If we had a specification to comply, we would have:

· Keep the appearance of the ground up by reducing as much as possible the burden with its display.

· Make the management of land by the code clean and accessible.

· Using a technique efficient, simple and fast.

· Respecting a QuadTree to optimize performance and meet the needs of treatment games.

Keep appearance with 100 times less resources, is a beautiful goal!.

The QuadTree

The first step is to manage our future terrain through a QuadTree.

A QuadTree is a data type tree in which each node can have up to four children. The Quadtrees are most often used to split a two-dimensional (3D abscissa and depth) by recursively subdivided into four knots. Each node has 4 children and so on. The route of such a tree is simple and takes on average the same time : for each level, there is a maximum of 4 tests to be "allowed" to navigate into lower level. This is important given the task before us here: "Show ground with maximum details using minimal resources.". The goal is to minimize the course of such a tree through its hubs in making these tests smart and simple.

Principle

The QuadTree (often used for rendering the field) provides an intelligent answer to the problem of optimization. First it loads the data only when needed. Then, the burden caused by the representation of a node on the screen depends on the depth of the node in the tree. Therefore, the sooner it is estimated that a node not be displayed in the course of a tree, the greater the optimization of display is realized (we limit the same time the number of triangles to display ). We will explain it all over this article.

More on sinking into the tree, more precision displayed with refined detail.

The real question to be asked to optimize the display of our tree is "what tests should be performed to determine the appropriateness of displaying a node on the screen”. We will see this as soon as possible. For now let us concentrate on how we manage the tree in our code.

Display the tree

Initially our terrain is only rendered by a single node (see picture above). The node size will be equals to the size of the terrain. A node on the screen corresponds to a surface composed of 9 square vertices:

1. Nord North

2. Nord Est North East

3. Est East

4. Sud Est South East

5. Sud South

6. Sud Ouest South West

7. Ouest West

8. Nord Ouest North West

9. Centre Center

A node is composed of 9 vertices

The QuadTree will be based on a heightfield (a two-dimensional array containing all the heights of each vertex Y on the screen). Each vertex of each node in the QuadTree has a height whose value is drawn from the heightfield.

Initially, only the corner of a node are visible, namely: North East, South East, North West, South West. Its rendering is similar to the following picture:

The shaded vertices are visible vertices

These four vertices displayed allow us to draw two triangles form the surface of square knot. For each update of the terrain, for each node currently visible, we calculate the visibility of each of the vertices. Each update of a node is accompanied by a redrawing of triangles that make it up. he following picture explicit some possible configurations for a node:

The algorithm for this part would be:

/ / For each of the vertices North, East, South, West

If ( !Vertex.Visible && VertexTest())

Vertex.Visible = true ;

Else if (Vertex.Visible && !VertexTest())

Vertex.Visible = false;

The test of this algorithm takes into account the distance of the vertex from the camera and the growing need for detail as the camera approached it. We will see the nature of this test later.

In a second step it is necessary to calculate the visibility of children of current node. A node consists of four children as the next picture shows:

Here we have shown the North East of child root node, then the child South East of it, then the child of the South East last child finally North West of it.

The more one penetrates deep into the QuadTree over the mesh tightens and will display a more detailed terrain.

The algorithm for this part at this stage of our study would be:

// For each of the four children North West, North East, South West, South East

If ( !Child.Visible && ChildTest())

Child.Visible = true ;

Else if (Child.Visible && ! ChildTest())

Child.Visible = false;

Once again, the test of this algorithm takes into account the distance to which the child and the growing need for detail as the camera approached it. We will see the nature of this test later.

When a child is exposed, its vertices and his own children are subject to two algorithms that we have just seen. We are therefore in a principle of recursion.

We compute the triangles that’s makes a node by not taking into account the parts overshadowed by children:

We note here that the vertices North and East of the parent shared with the vertices North West and South West of the child. We will see that later.

The basic principle of the Billod algorithm is relatively simple. Vertices et enfants à afficher sont soumis à chaque mise à jour du terrain à un ensemble de tests qui déterminent leur visibilité. Vertices and children are subjected, at each updated of the terrain, to a set of tests that determine their visibility. The display of a node node is a recursive set of instructions that goes through the QuadTree along the root node to each leaf node of each branch.

Improvements

We talked previously shared vertices between a child and a parent. The previous image illustrates this point. This may cause an unpleasant graphic bug illustrated by the image below:

Or, with wireframe:

This problem is due to the non-activation of a vertex in the neighboring node. The nodes affected by this bug are:

So in reality:

The West vertex of the child red is activated but not the vertex of the yellow child. There is therefore a delta between the two sides of the two children. To resolve this bug simply validate the vertex of the child is yellow:

Finally we get a perfect continuity:

Now imagine that the southern vertex of the yellow child becomes visible. The parent node has only two children north west and north east. Activating this vertex pose the same problem as before graph:

Unfortunately, unlike the previous case, there are no children in the South West. It is therefore necessary to create a child to this position (although the "ChildTest” of our algorithm for that child returns false) and to activate its North vertex:

The addition of southern vertex of the white child led to the creation of the Child South West and the activation of southern vertex parent node. The vertex South may itself cause the modification of neighboring nodes. There are, here, some cascading effects that are not really controllable but, fortunately, limited. The following image shows the impact of activation of several children deep into the QuadTree at the bottom right of the terrain.

We note that the nodes located at the opposite are impacted.

Managing nodes in the QuadTree

Some years ago I read an excellent article by a person named Stan Melax author of an ingenious technique for calculating a dynamic aspect of a 3D model at different levels of resolution. The articles on progressive meshes are subject to the same laws as those on land: either the reduction algorithm is too complicated or it is inappropriate. Stan Melax found a clever way to solve this problem. He studies the cost the disappearance of each vertex by studying their impact on the overall shape. He is then able to gradually reduce the resolution of the 3D model by removing vertices in a logical order with the less impact. Its strength lies in the calculation of the cost of a vertex which proves to be a simple and effective. We will proceed the same way.

The curve : Element to remember

To explain simply : We measure a terrain to its forms. We measure a form to its curves. The question is then: how to define a curve ?. Answering this question would determine the locations of the terrain where we must keep an important retail level and those that can be degraded.

There are many techniques to transform a curve into a mathematical function. We return in this case to the beginning problem: Do not overload the processor too much. We have seen, it is necessary to execute the formula found at all vertices and all children nodes. A formula that generates a lot of instructions will deteriorate application performance.

The solution is simple. We have said that our land is splitted into a set of nodes belonging to a tree. Each curve of the land therefore consists of nodes that are actually surfaces square whose size varies

The terrain is a set of curves visible on the screen. Each curve is an assembly of square knots coast to coast glued.

The normal, order of magnitude of a curve

Plus la courbe est importante, plus les nœuds qui la composent forment un angle important. The greater the curve is, the greater the angles made by its nodes are important. Take for example a curve :

It shows all nodes glued side by side. At the place where the curve is really important we find nodes that form an angle. In contrast to where there is no curve, but a simple slope, nodes coast to coast appear to belong to the same plane. We noticed even more if we show each normals nodes:

We are now close to finding the formula! All the students know that the mathematical function that measures the angle between two vectors is the dot product.

The inner product of two vectors represented by non-zero vectors A and B is the actual number ABcos (θ) if the angle θ is the angle formed between the two lines whose direction are represented by the two vectors.

The maximum angle that can be found in a curve of land as we conceive it tends to 90 degrees (90 degrees value cannot be achieved because nodes can’t overlap). Cos 90 equal 0 so we can infer that when the curve formed by the vectors is important, their dot product approach 0 (A * B * Cos (90) = A * B * 0 = 0). On the contrary if the value of inner product increases, is that the curve formed by the two nodes tend toward the "right" (A * B * Cos (0) = A * B * 1 = AB). See this picture:

The inner product between the normal parent and child will return here a value far away from 0 : we are on a surface, certainly inclined, but plane. Needless to cut the node.

Consider now a pronounced curve :

The angle between the three normals is more pronounced. The original node (symbolized by the black dotted line) should be divided into sub-nodes. We can found in this process a certain logic: a flat surface is easily modeled with few polygons. A curved surface ask for much. Here to complete the wireframe curve:

Where the curve is more pronounced, our technique uses more primitives

Activation

Child Test method should compare the normal of the children to test with the normal of the parent node to which it belongs. If the angle between the two normal exceeds a threshold when the method returns true.

Disabling

Disabling a child occurs when a series of factors are met:

· The child has no longer visible vertices

· The child has more sub-children

· The test method returns false.

Enable/Disable switch node in the vertex

Interpolated to real

La gestion de la visibilité des vertices ne suit pas la même logique que celle décrite précédemment. The management of the vertices visibility does not follow the same logic as that described above. Here there is no curves but delta. Only vertices on the sides of a node are to be tested. So the North, East, South, West vertices. When a node is created, this vertices are not visible. But they are located between two vertices on node edge and so, we can deduce their height easily. Here is an example of node viewed from the side:

It shows the vertices North West and South West enabled (visible)) and West vertex disabled.

The West vertex seems to be on the right along the two summits. In real, it may not. For now we have interpolated (deducted) its position (If South West is at a height of 10 and North West at a height of 20, it is reasonable to assume that the West vertex will be at a height of 15). Yet in reality, it is may be at another height:

There is a distance between the delta position of vertex West interpolated its actual position. This difference in height measures the degree of reality of the node currently displayed with a more detailed version.

View node with only the 4 vertices summits displayed therefore does not adequately reflect the reality on the ground displayed by the node.

Way of activation

The activation method is very simple, we only need to determine the Delta value (a simple difference of heights) and determine if it exceeds a threshold too.

Test of disabling

Disabling a vertex is only when a series of factors are met:

· The vertex is used by a child node

· The test method returns false.

Progressive Details

It was one of the prerequisites for our technology, we must optimize the display according to the camera position. At this point, our two functions tests (for vertices and children nodes) do not take into account the camera position and the position of the element to test.

We have seen in the two algorithms dedicated to the vertices and nodes, that test is performed to determine if a vertex or child should be displayed or not. The land must be displayed according to the camera position for the comfort of the player. The more an area of land is close to the camera the more it have to be detailed. It also aims to preserve up to the appearance of the terrain away with a minimum of vertices and gradually detail when the camera comes.

Detail for progressive QuadTree

For the time the testing method is based on the angle made between the normal of a child with its parent. This procedure is not necessarily relevant distance.

If a few degrees angle is visible when you are close to the nodes that make up this angle is not necessarily detectable at a distance It is not necessary to activate the child.

Here is the implementation of this test method:

private bool ChildTest(Vector3 childNormal, BoundingBox boundingBox, Vector3 cameraPosition)

{

//by default, the four childs of the root node are visible.

if (this.Depth < 1)

return true;

//get the closest point to the camera and check the distance

float distanceCameraToPoint = Vector3.Distance(GetBoundingBoxClosestPointToPoint(boundingBox, cameraPosition), cameraPosition);

//compute the dot product between parent normal and child normal

float dotprod = 1 - Vector3.Dot(childNormal, this.CenterVertex.Value.Normal);

//check with the threshold

return (distanceCameraToPoint / this.ParentTree.QuadTreeDetail) < (dotprod);

}

By default nodes at the top of the tree are made visible. We then determine the distance between the camera position and the nearest point of it in the BoundingBox encompassing child. The dot product is then calculated. We test the division of this distance by an adjustable threshold is below the dot product.

Note that this method of testing may well be adapted to submit the QuadTree to another technique optimization.

Progressive detail for the vertex

Again, the testing method for vertices does not take into account the distance to the camera. We must determine if the distance between the actual position of the vertex and its position interpolated exceeds a threshold configurable.

Here is the testing method:

public bool VertexTest(Vector3 vertexPosition, Sides side, Vector3 cameraPosition)

{

//get the distance between interpolated height position and real height position

float lengthToTest = this._realToInterpolatedVertexHeight[(int)side];

//get the distance from the camera position to the vertex position

float distanceCameraToPoint = Vector3.Distance(vertexPosition, cameraPosition);

//check with the threshold

return lengthToTest * this.ParentTree.VertexDetail > distanceCameraToPoint;

}

The delta between the two vertices (interpolated and real) is stored in memory. We then determine the distance between the vertex and the camera. A test is then conducted to determine if the Delta exceeds the threshold distance to the camera. Like earlier this test method may well be adapted to submit the vertices of each node to another technique optimization.

A field at different level of detail, from left to right: 7500, 3000, 1500, 300 150 vertices

Improvements

Our algorithm at this stage works perfectly: it displays the details where they are relevant, frees up resources and uses a quadtree.

Remember that time, the relevance of viewing a node is measured using the dot product of its normal with normal direct its parent. This is rather good, but we can improve. The following pictures illustrate a graphic unpleasant bug that modifies the appearance of ground within walking distance:

In front of us: a slight bump on the ground

The hump has been truncated

Note that the bump on the first visible image is greatly reduced by the mere fact of having moved slightly camera. But our algorithm has worked here perfectly. We simply validated a threshold requiring a node to be cut. So we need to reduce the implementation of our algorithm close to the camera. We will therefore introduce a second threshold that will represent what we mean by "proximity".

The new test function is thus as follows:

private bool ChildTest(Vector3 childNormal, BoundingBox childBoundingBox, Vector3 cameraPosition)

{

//by default, the four childs of the root node are visible.

if (this.Depth < this.ParentTree.MinimalDepth)

return true;

//get the closest point to the camera and check the distance

float distanceCameraToPoint = Vector3.Distance(GetBoundingBoxClosestPointToPoint(childBoundingBox, cameraPosition), cameraPosition);

//compute the dot product between parent normal and child normal

float dotprod = 1 - Vector3.Dot(childNormal, this.CenterVertex.Value.Normal);

//check with the threshold

return ((distanceCameraToPoint - this.ParentTree.QuadTreeDetailAtFront ) / this.ParentTree.QuadTreeDetailAtFar) < (dotprod);

}

We now have two thresholds, a threshold of visibility for “near displays” to maximize the details close to the camera and a threshold of “far display” that manages the details beyond the previous threshold according to a affine function as we did until now.

The advantage is undeniable. For proof, just take a look at the picture below:

I went to the center of the terrain, I stopped the implementation of the algorithm (similar to a pause in the Update of the QuadTree) and take some the altitude. We notice that the details seem to diminish when away from the center. This is indeed the case:

At the center of the screen near the crater, the details are at maximum. If we were on the ground, we do not see any ground near bump be changed by moving the camera. On the contrary, the far away details keeps the overall look of the land.

It's not all, we are now able to generate a climate and geographical well known: a mountain line (sorry I do not know the English term for “ligne bleue”). Look at this picture:

It is the blue line Vosges clearly visible from the north of “Franche-Comte” in France. Plus on regarde. The more one looks far more mist arises in a bluish tint. By applying our algorithm and a modified fog we are able to generate a skyline purified up to cut a new notch resources taken by the displayed terrain. Return on our field, but this time by being near the ground:

We've added a blue fog to simulate this. The remote mountains are visible thanks to the difference in color the fog gives them. Now the same view but with a threshold of visibility at distance greatly reduced:

We get a display similar but with 1300 primitives less!

Code and optimization

The code given with this article is deliberately sketchy for the sake of understanding. Son but est de tester la technique Billod Its purpose is to test the Billod technique described here with no optimization.

Description of the "business" classes

Four classes are really business:

· The terrain is naturally managed by a class called Terrain. We will return later on its possible usefulness. Terrain is a container for Quadtrees. It represents the whole ground.

· The tree is represented by an instance of QuadTree class. QuadTree represents a part of Terrain. It is a container of QuadNodes.

· The nodes of the tree are created using the QuadNode class. It is a container of TerrainVertex. QuadNode represents a node.

· Finally the 9 vertices of a node are TerrainVertex.

Most treatment is within the class QuadNode. This has two important methods: Initialize and Update. The Initialize method handles load the node with all information related to its position in the QuadTree. It makes visible its four edges, it determines the neighboring nodes (for sharing vertices). It also calculates the deltas, normals, BoundingBox. It is called once every creation of a node.

The Update method performs tests on the four vertices "sides" (North, East, South, West) and four children on the potential (North West, North East, South West, South East) to each update of the tree .

This is the class QuadTree which initializes the first node and start treatment on the tree. Every x seconds (adjustable) it launches an asynchronous update on all the nodes instantiated to update the tree depending on the position of the camera.

The instantiation of a QuadTree is achieved by specifying the size of it, its depth and its location:

QuadTree tree = new QuadTree(treeDepth, rootNodeSize, location);

The structure TerrainVertex contains the vertex to display. A vertex can be shared on multiple nodes.

The code of this four major classes has been simplified in the extreme and widely commented. If there are still black spots do not hesitate to contact me.

Update Thread

A quick and easy (dirty ?) solution has been implemented to update the field. A BackgroundWorker is launched when you start the application and handle the updating of the field asynchronously.

This procedure avoids any slowdown of the game during the update. The data displays (VertexBuffer and IndexBuffer) are stored in a stack and used in the Render method. In the example provided with this article, we do an update that every 4 seconds.

Optimizations

Apart from improvements to the code, here are some ideas to increase the quality of reporting and the power of technology Billodes.

· We do two courses of the shaft each Update (one to update the tree, the other to extract the list to display triangles). There 'may be a point to improve here.

· The updated every X seconds is not necessarily the best solution. There are several other possible avenues to update, for example when the camera is moved or predicting the movement of the player and update accordingly. Finally, it should be noted that the final status of a tree is not achieved in a single Update It may be preferable in some cases to await the final version of the tree by calling the Update method as many times as necessary. You shlould prefer update the tree by little part each frame.

· Some thresholds for activation or deactivation of a child or a vertex are very low. We can consider that they will never be activated.

· When a node is cut or merged, or when a vertex changes state (visible / hidden), the transition is visible.It may be useful to cut this transition more gradual steps to soften the visual changes.

· Relying on the Terrain class. In this sample we render only a single tree. The Terrain class field can be a serious springboard to try to manage several trees that will be linked one to another.

· We load the entire Heightfield from the start by analyzing a black and white. It is an effective way to proceed to achieve an example but not to make a game. It might be wise to store the array of heights in a file and read what the QuadTree needs at each Update.

· The source code has not been optimized for readability.

The example program

This program is just one example of a rapid implementation of the land Billodes. The business classes are quickly adaptable to individual needs. The project is XNA 3.0. Il est toutefois adaptable au 2.0. However, it is adaptable to 2.0.

Commands to interact with the world are:

· Mouse: Click to turn the camera.

· Arrow keys: moving the camera in the current direction.

· Key W: Wireframe Mode On / Off.

· Page Up / Page Down: Change the Far Threshold Test.

· Key left Shift + Page Up / Page Down: Near Threshold Test.

· Left Key Shift + arrow keys: fast move.

· Left Key Alt + arrow keys: moving slow.

To test the Billod algorithm, simply move on the ground and studying the evolution of the field.

Note that it is possible to modify some parameters affecting the display using the configuration file of the application.

You can reuse the source code as you want. I just ask to refer me in your "credits".

References / Credits

The Web site of Stan Melax: http://www.melax.com . A very pragmatic man at the root of a technical Progressive Mesh very smart on which I based my algorithm. I take this article to thank him for his kindness and his exchange at the time or I was working on progressive meshes in XNA.

"Continuous LOD Terrain Meshing Using Adaptive Quadtrees" by Thatcher Ulrich. A method quite similar to mine but more research-oriented to deltas. This is one of the few methods available on the web that can be used for a game. My algorithm has a QuadTree quite similar to his "Adaptive QuadTree" but his management heightfield is much more intelligent than mine. His details management is, in my opinion less good than mine.

The page Hugues Hoppe: http://research.microsoft.com/ ~ hoppe. One of the masters of the terrain rendering. Everything is so great but illegible for novices and not necessarily adapted to the world of video gaming.

Virtual Terrain Project: http://www.vterrain.org/ . Website with a great set of publications around the management of terrain.

And on a more personal way Mathieu Laussel, a French friend 3D modeler (engineering) with whom I realize an editor of the world and who kindly wait as I write this article. And Boris Driss student that like game development and with who, talking is very interresting.

Downloads

You can downalod the C# project here.

Annexe : Interface utilisateur en Xna

valentin — Mon, 21 May 2007 14:10:00 GMT

Retourner au sommaire des cours

L'interface utilisateur constitue le lien principal entre le joueur et le jeu. Dans l'univers Xna, la notion de widget est inexistante : le framework se veut générique et la notion de "bouton", de "TextBox" est inexistante sous une Xbox. Quiconque veut réaliser une interface est confronté à un dilemn : Soit il se branche au monde WinForm et profite de l'ensemble des contrôles de l'API .net Soit il réalise son propre système graphique.

Le premier cas limite le cadre d'utilisation de vos jeux à la plate-forme Windows. Elle demande la conciliation de deux univers graphique différents (Winform et Xna) et, de ce fait, peche par un manque de performances. Toutefois, cette méthode est sans aucun doute la plus rapide a mettre en place et la plus complète.

Le second cas ne souffre d'aucun de ces défaut mais demande un temps d'implémentation relativement conséquent.Le developpeur doit effectivement s'occuper du rendu de chaque contrôle, et ce, pour tous les états que ceux ci peuvent avoir, mais aussi du système événementiel et enfin du modèle objet sous jacent.Une interface puissante et customizée est à ce prix. Nous aborderons ce cas dans cette annexe. Vous pouvez vous reporter à l'annexe "Xna et Winform" pour apprendre à développer une interface utilisateur à l'aide du namespace System.Windows.Form.

Cette annexe est en cours d'écriture.

UI ou non ?

Le projet en téléchargement ici est en cours de développement et n'est pas terminé à ce jour.

Le projet explicité vise un seul but : offrir au développeur un moyen de développer une interface graphique aussi simplement que sous Windows avec .Net. Le principe est donc de pouvoir réaliser des instructions de type :

bouton = new Button();
bouton.Width *= 2;
bouton.Location = new Point(200, 200);
bouton.MouseDown += new MouseEventHandler(button_MouseDown);
bouton.Text = "Click on me";
contener.Controls.Add(bouton);

et de voir apparaitre un bouton à l'écran. Facile à dire, facile à mettre en oeuvre : c'est effectivement ce que nous ferons :).

Il y'a toutefois quelques nota bene à preciser avant de partir dans l'aventure la fleur au fusil. Sous Windows n'importe quel bouton de n'importe quelle application se ressemble, et pour cause : la notion de skin, d'univers graphique, de cohérence graphique n'a pas vraiment lieu d'être. Microsoft publie ainsi une documentation assimilable à une chartre graphique que tout développeur d'application Windows doit respecter. La chartre de Winsows Vista est accessible ici : http://msdn2.microsoft.com/en-us/library/aa511258.aspx. Comme on le voit, l'utilisateur y apprend la taille des boutons, les couleurs des messages, la façon dont il faut agencer les widgets (un widget est un élément graphique), il lui est même précisé comment afficher les messages d'erreur et d'alerte. Quel raison à tout cela ? l'UCO bien sûr. Sous cet acronyme se cache l'User Cost of OwnerShip. C'est à dire le coût d'aprehension d'une application par un utilisateur. Microsoft se base sur un principe simple : si toutes les applications respectent les mêmes normes alors l'utilisateur verra le cout de sa formation à un nouveau produit reduit. Nous nous en rendons compte tous les jours : nous voulons faire un copier collé ? Qui ne connait pas Ctrl +C / Ctrl + V ? Qui ne sait pas que ces commandes se trouvent dans le menu "Edition" ? Qui ne sait pas que dans le menu Fichier précédent ce menu se trouve la commande pour quitter l'application ? Qui ne sait pas que la barre d'état se trouve toujours en bas d'une fenêtre ? Quelqu'un a t'il déjà vu le bouton Annuler à gauche du bouton Ok dans une fenêtre de confirmation ?

Toutes ces normes sont importantes dans un environement qui se veut professionnel. Mais dans le monde du jeu video l'ambiance et l'univers d'un jeu oblige les développeur à créer des widgets en conformité avec l'ambiance que doit dégager un jeu. Notre projet devra ainsi permettre à l'utilisateur de pouvoir créer sa propre skin, de pouvoir donner à un bouton, une combo box ou un slider l'aspect qu'il désire. Enfin et pour terminer sur les contraintes, nous devrons faire en sorte que le projet sois maléable et que l'ajout de nouveaux type de Widget soit d'une grande simplicité. Inutile de passer 80% du développement d'un jeu à créer des controles et seulement 20% consacré à la réalisation du jeu en lui-même.

Imagineriez vous cet écran avec les boutons Winsows classiques ?

et celui-ci avec les boutons d'age of empire ?

Utilisation du projet

Jusqu'à trois projets sont nécessaires pour utiliser une interface utilisateur en Xna. Le premier projet correspond à notre API graphique. Il contient la définition des différents Widgets et la skin de base des widgets. Pour information cette skin de base est la même que le sample de l'API DirectX. Le second projet est facultatif. Il contient la définition des Widgets customisés par l'utilisateur pour son jeu ainsi que la ou les skins adaptées à l'univers du jeu développé. Le troisième projet correspond au projet principal (contenant généralement la classe héritant de Game).

Comment fonctionne le premier projet ? Il ressemble en grande partie à l'assembly System.Windows.Form (en plus simple toutefois). L'assembly repose principalement sur la classe Control dont hérite tous les Widgets. Elle contient la plupart des membres, événements et méthodes utilisés par les développeurs Winforms. La classe UIManager est responsable de la gestion de l'interface utilisateur sur la surface de rendu Xna. C'est à elle qu'on rajoute les contrôle situés sur le Z-index le plus bas. Cette classe s'occupe en interne des différents rouages qui gèrent la souris, le clavier et les interractions avec les contrôles. Le troisième élément important correspond au répertoire Configuration. Il contient le schéma définissant le fichier Xml de définition de Widget et de Skin. Il contient de même un fichier par défaut (pour l'interface et les Widgets de base). On y trouve enfin un fichier xsl. Ce fichier permet la transformation d'un fichier Xml en un ensemble de classe métier utilisable par le développeur s'occupant de l'interface graphique. Deux outils s'occupent de cette transformation : msxsl.exe et xsd.exe. Ils sont eux aussi inclus dans ce repertoire.

Fichier de configuration

Le fichier de configuration permet de réaliser des skins pour donner diverses apparences à ses objets. La définition d'un bouton se fait ainsi :

</Elements>

</Instructions>

</Event>

</Instructions>

</Event>

Désolé pour l'affichage chaotique, mais le blog ne permet plus l'ajoute de text ordonné :/

Si on analyse ce code Xml, on se rend compte que la portion de code réalise plusieurs travaux. En plus de définir un control nommé Bouton elle :

Créé un ensemble d'élément issu d'une texture donnant un aspect au bouton (la skin)
Spécifie des éléments par défaut (largeur, hauteur ...)
Créé des instructions qui repondent à des événements

Cette portion de Xml couplé à l'outil msxsl.exe et au fichier xsl génère une classe en sortie dans le fichier Widget.Designer.cs :

/// <summary>
/// <para>Defines a Button.</para>

/// </summary>

public partial class Button : Control

{

/// <summary>

/// <para>Instanciate a new <see cref="Button"/> object.</para>

/// </summary>

public Button()

{

this.Bounds = new Rectangle(0, 0, 75, 23);

}

public override void Update()

{

base.Update();

//Manage instructions for each events

if (GetState((int)States.MouseOver))

{

//add instructions

this.OffsetX = -1;

this.OffsetY = -2;

this.ForeColor = Color.Black;

}

if (GetState((int)States.Pressed))

{

//add instructions

this.OffsetX = 1;

this.OffsetY = 2;

this.ForeColor = Color.White;

}

if (GetState((int)States.Normal))

{

//add instructions

this.ForeColor = Color.Black;

}

public override void Load(Microsoft.Xna.Framework.Graphics.GraphicsDevice device)

{

base.Load(device);

//add skins

this.Elements.Add(new Element( "BackFocused", "GenericTexture", "", new Microsoft.Xna.Framework.Rectangle(0, 0, 136, 54), States.Focused, new Color((byte)255, (byte)255, (byte)255, (byte)255)));

this.Elements.Add(new Element( "FrontFocused", "GenericTexture", "", new Microsoft.Xna.Framework.Rectangle(136, 0, 116, 54), States.Focused, new Color((byte)255, (byte)255, (byte)255, (byte)255)));

this.Elements.Add(new Element( "BackNormal", "GenericTexture", "", new Microsoft.Xna.Framework.Rectangle(0, 0, 136, 54), States.Normal, new Color((byte)255, (byte)255, (byte)255, (byte)140)));

this.Elements.Add(new Element( "FrontNormal", "GenericTexture", "", new Microsoft.Xna.Framework.Rectangle(136, 0, 116, 54), States.Normal, new Color((byte)255, (byte)255, (byte)255, (byte)0)));

this.Elements.Add(new Element( "BackMouseOver", "GenericTexture", "", new Microsoft.Xna.Framework.Rectangle(0, 0, 136, 54), States.MouseOver, new Color((byte)0, (byte)0, (byte)0, (byte)255)));

this.Elements.Add(new Element( "FrontMouseOver", "GenericTexture", "", new Microsoft.Xna.Framework.Rectangle(136, 0, 116, 54), States.MouseOver, new Color((byte)255, (byte)255, (byte)255, (byte)153)));

this.Elements.Add(new Element( "BackPressed", "GenericTexture", "", new Microsoft.Xna.Framework.Rectangle(0, 0, 136, 54), States.Pressed, new Color((byte)255, (byte)255, (byte)255, (byte)217))); this.Elements.Add(new Element( "FrontPressed", "GenericTexture", "", new Microsoft.Xna.Framework.Rectangle(136, 0, 116, 54), States.Pressed, new Color((byte)0, (byte)0, (byte)0, (byte)64)));

}

Cette classe est générée à chaque build par l'intermédiaire d'un prebuild event ajouté aux propriétés du projet :

"$(ProjectDir)Configuration\msxsl.exe" "$(ProjectDir)Configuration\StandardUI.xml" "$(ProjectDir)Configuration\configuration.cs.xslt" -o "$(ProjectDir)Widgets.Designer.cs"

Pour le reste une étude du code qui reste simple vaut mieux que plusieurs milliers de lignes d'explications.

Ajouter une interface graphique

Nous voilà enfin sur le terrain pour tester notre produit. L'exercice reste simple, il nous faut d'abord ajuter une référence vers le projet Arcane.Xna.Windows.Form. Puis créer dans le contreur un UIManager (le fameux manageur de controle). Ce manager se créé à l'aide d'un objet de type GameServicesContainer :

_uiContainer = new UIManager(this.Services);

Lorsque l'objet est créé dans la méthode Initialize on le charge et on ajoute alors de la même manière qu'en Winform l'ensemble de ses contrôles :

private void InitializeUI()

{

_uiContainer.Load();

//Stream stream = Assembly.GetAssembly(typeof(Arcane.Xna.Windows.Form.Custom.Class1)).GetManifestResourceStream("Arcane.Xna.Windows.Form.Custom.Configuration.MyGameUI.xml");

//_uiContainer.LoadCustomUI(stream);

for (int i = 0; i < 15; i++)

{

Button z = new Button();z.Location = new Point(0, 23 + 23 * i);

_uiContainer.Controls.Add(z);

}

textBox = new TextBox(); textBox.BackColor = Color.DarkRed;

//t.Location = new Point(300, 300);

textBox.Bounds = new Rectangle(100, 300, 200, 30);textBox.TextChanged += new EventHandler(t_TextChanged);

_uiContainer.Controls.Add(textBox);

label = new Label();

label.Bounds = new Rectangle(400, 50, 75, 30);

label.Click +=new EventHandler(label_Click);

this._uiContainer.Controls.Add(label);

this.IsMouseVisible = true;

bouton = new Button();

bouton.Width *= 2;

bouton.Location = new Point(200, 200);

bouton.MouseDown += new MouseEventHandler(button_MouseDown);

bouton.Text = "Click on me";

_uiContainer.Controls.Add(bouton);

}

Deux étapes restent encore : l'appel à la méthode Update du manager et l'appel à la sa méthode Draw. Au final on obtient à l'affichage :

On y voit une douzaine de bouton, une texbox et un label. Une partie de ces controles interragit avec l'utilisateur par l'intermédiaire d'événements.

Vous pouvez télécharger le sample ici.

Le projet en téléchargement est en cours de développement et peux souffrir de bugs dus à l'absence d'autres composants en cours de développement où du fait que je ne peux pas penser à tout :p

Merci néanmoins de me préciser les problèmes que vous pouvez rencontrer.

Lorsque le projet sera terminé, la présente annexe sera grandement etoffée pour expliciter au mieux ce projet.

23/05/2007

TextBox

correction bug sur l'entrée de certains caractères
Ajout des propriétés SelectionStart, SelectionLength, SelectionText
Amélioration de la selection de text
Correction bug selection de text rémanente quand on tape du texte
TextBox rendue plus indépendante de Control
Selection de texte avec Shift et fleches
Ajout propriété TextLength
Ajout propriété MaxLength
Gestion touches Home et End (avec shift ou non)

UIGénérale

correction bug sur la touche Tab pour passer d'un control à un autre (et donc Shift Tab aussi)

Control

Ajout d'events FontChanged, SizeChanged, LocationChanged

Bug trouvé à corriger

Si on clique sur un control et qu'on relache sur un autre, cet autre est selectionné

24/05/2007

Label

Correction d'un bug sur le backcolor
Le label prend la taille du text qu'il contient désormais

Radiobutton

Ajout d'un nouveau controle : le RadioButton

Panel

Ajout d'un nouveau controle : le panel (obligatoire pour grouper les Radio et Check Buttons par parents communs)

General

Gestion parent/enfant améliorée
gestion de position absolute / relatif

COnfiguration

Possibilité de rajouter une description aux widgets
Les effets sont optionnels
Ajout d'un nouvel etat : None

Bug :

correction d'un bug sur la selection avec *** + fleche

Bug dans la sauvegarde du state du device corrigé

25/05/07

Checkbox

Ajout d'un nouveau controle : la Checkbox

ComboBox

Ajout d'un nouveau controle : la combobox (en cours de développement)

TextBox

Ajout de la propriété ReadOnly

Control

Ajout des méthodes protected d'accès aux events got et lost focus
Ajout d'une propriété ControlStyles pour gérer l'affichage

General

Ajout d'un nouvel evenement mouseenter et mouseleave

01/06/07

UserInterfaceManager

Nouveau non de uicontainer
Hérite de GameComponent
Simplification de la syntaxe

GameCanvas

Nouveau controle Gamecanvas
Game canvas peut être focused
Game cavas repond seul à l'évent sizechanged

ListControl

Ajout d'un nouveau control : le listcontrol, parent de combobox et de listbox

ComboBox

Gestion du texte dans la combobox
ajout propriété selectedindex
ajout propriété sorted
ajout propriété index

ScrollBox

Ajout d'un nouveau control : la scrolbox

TextBox

Ne gère plus le clavier mais ecoute le keybord manageur
Ajout d'une propriété HideSelection

Control

Ajout des méthodes protected d'accès aux events got et lost focus
Ajout d'une propriété ControlStyles pour gérer l'affichage
Ajout d'un nouvel event : DeviceLoaded
Gestion du Visible

General

Ajout d'un manageur pour Keyboard et Mouse
Gestion de l'event KeyPress
Les controls sont visibles en tant que composants possibilité d'utiliser le designer de Visual Studio
Reponse à l'event check pour le checkbox afin de cacher/afficher le panel
Meilleur gestion de l'update
Gestion d'update et Render avec ou sans GameTime en parametre.

Bug

Selection a la souris impossible
Bouton cliqué sur un control et relaché en dehors donnait le focus au control sur lequel le bouton était relaché

Retourner au sommaire des cours

Annexe : Progressive Mesh en Xna

valentin — Thu, 05 Apr 2007 14:00:00 GMT

Retourner au sommaire des cours

Avant toutes choses je tiens à remercier Stan Melax qui m'a gentiment aidé à passer son algorithme en DirectX et Xna et m'a laissé la possibilité d'utiliser pour ce cours quelque schémas qu'il avait réalisé.

L'utilisation de MRM est une véritable merveille pour accroître de manière significative les performances de ses applications. Le principe est simple : transformer un model 3D détaillé et formé de très nombreux polygones en une version allégée utilisant moins de faces mais aillant un aspect aussi similaire que possible.

Cette technique est la plupart du temps couplée avec la camera pour réduire proportionnellement la qualité du modèle 3D en fonction de la distance à laquelle il se trouve de la camera.

Au final, nous pouvons ainsi grappiller des FPS et libérer le GPU en lui évitant d’afficher des modèles détaillés au loin, là ou une version grandement allégée donne le même résultat à l’écran.

L'image suivante explicite cela :

On y voir l'affichage d'une voiture sous différentes résolutions (le poucentage indiqué au dessus de chaque modèle correspond au nombre de vertices utilisé par rapport à l'original). Le modèle à 10% reste tout à fait acceptable et similaire à l'original. Il est donc tout à fait imaginable de l'utiliser à grande distance à la place d'un modèle plus "complet" et plus lourd à manipuler.

Les MRM (multi resolution mesh) occupent une place prépondérante dans les moteurs 3D : Utilisés pricipalement pour libérer du traitement GPU sur l’affichage des objets lointains il est aussi employé dans l'occlusion culling (l'occlusion consiste à supprimer de l'affichage les objets qui sont cachés par d'autres objets nous y reviendrons dans un autre post). Nous allons donc dans ce cours chercher un moyen pour créer et utiliser des MRM dans nos applications. Ce moyen, c'est bien evidemment un algorithme qui va etre en mesure de calculer la réduction du nombre de vertices dans une forme 3D en sauvegardant au maximum son aspect général lors de cette transformation. L'algorithme

Une complexité qui rebute

Si on se tourne vers les moteurs de recherche sur le net (live.com, google.fr) à l'aide des mots clés "MRM algorithme" on trouve un grand nombre de travaux de chercheurs et de passionnés sur ce sujet. Pourtant la plupart des algorithmes qu'on y trouve sont inexploitables : soit ils sont trop gourmants en calculs et donc inexploitable en temps réel, soit le resultat change l'aspect de la forme 3D ou bien encore la complexité est telle qu'il est tout bonnement incompréhensible. Quelques pasionnés ont toutefois trouvé un moyen de réaliser des réductions de résolutions relativement simplement. Nous retiendrons ainsi la méthode utilisé par Stan Melax parce qu'à priori la meilleure et, cerise sur le gâteau, l'une des plus simples.

Réduction par Fusion de Meshs

Melax se base lui-même sur les travaux de H.Hoppes, un développer de MSR (Microsoft Research) dont est issue vraisemblablement l'algorithme se trouvant derrière la classe ProgressiveMesh de Direct3D. Cet algorithme vise a réduire la complexité d'un model 3D par l'intermédiaire de fusions de vertices. Le principe est trivial : à chaque réduction de résolution on fusionne deux vertices (que nous nommerons ici u et v).S'ensuit :

La suppression des triangles qui possèdent à la fois les vertices u et v.
La mise à jour des triangles qui utilisaient u sur l'un de leurs trois points afin qu'ils utilisent v à la place.
La suppression du vertex u.

Le schéma ci-dessus explicite tout cela. La figure A montre l'état du modèle avant la baisse de résolution. La figure B montre le même modèle après la fusion de deux de ces vertices. Le modèle garde son aspect mais en utilisant un vertex et deux faces en moins.

Ce processus est répété jusqu'à atteindre le nombre de vertices ou de faces voulu.

Choix de u et v

Cette méthode est relativement simple sur le papier et réduit effectivement sans grandes difficultés un model 3D. Il ne faut pourtant pas crier victoire trop vite : comme dit précédemment, il est primodial que le model "réduit" garde une apparence similaire au model complexe originel. Il convient donc de choisir avec intelligence les sommets u et v à fusionner afin de provoquer la plus fine modification visuelle à l'écran. L'image suivante illustre celà :

Le choix du sommet à supprimer est important pour garder une apparence aussi similaire que possible à l'original (image extraite de l'article de Stan Melax avec l'aimable autorisation de l'auteur).

C'est là ou le bat blesse : la plupart des algorithmes propose pour ce choix des calculs lourds et inutilisables en temps réel. Sur ce point, Stan Melax a montré son savoir faire. Il part d'un principe élémentaire : les surfaces coplanaires ne demandent pas autant de vertices pour être rendue à l'écran que les surfaces avec un relief prononcé (comme les courbes). Il est plus facile de réduire la complexité des premières, que celle des secondes. Le coût pour la disparition d'un sommet pourrait se traduire ainsi : c'est le résultat de la multiplication de la taille du sommet par l'importance dans la courbe sur laquelle il se trouve.

Pour la fusion uv, visant à déplacer u vers v nous avons l'algorithme :

Calculer la taille du sommet (distance u à v).
Déterminer l'ensemble des triangles qui possède à la fois u et v.
Pour chacun des triangles connectés à u :

Calculer le produit orthonormé de la normal du triangle courant avec chacun des triangles qui possèdent à la fois u et v. En extraire le plus petit produit.

Calculer le plus gros des plus petits produits : C'est la coùt de la fusion.

La formule mathématique pour calculer ce cout est la suivante est la suivante :

où Tu est l'ensemble des triangles qui possèdent u and Tuv l'ensemble des triangles qui contiennent à la fois u et v (image extraite de l'article de Stan Melax avec l'aimable autorisation de l'auteur).

Le principe peut se résumer ainsi : on parcourt tous les triangles connectés à u. Il est nécessaire, pour chacun de ces triangles, d'analyser le cout de la fusion avec v. On calcul celà en analysant l'impacte de la transformation des triangles afin de déterminer l'ampleur de la modification. Il y'a deux types de modifications : Soit les triangles sont connectés uniquement à u, et, dans ce cas ils sont modifiés pour être reliés à v, soit les triangles sont liés à u et v à la fois et doivent etre supprimés du modèle. La figure A et B au début de cette annexe illustre celà parfaitement.

Passons aux choses sérieuses

Pour l'heure la classe ProgressiveMesh que vous pouvez reprendre est industrialisable mais est encore améliorable :

Il reste à associer un poid à chaque vertex pour la transformation.
A réaliser un tris sur la liste de vertices pour classer par ordre de coût de transformation.
A réaliser des méthodes d'optimisation comme dans la classe Mesh de Direct3DX (fusionner les vertices qui sont assez proches pour ne faire qu'un).

Passons maintenant au code.

Celui-ci se trouve à l'intérieur d'une DLL nommée ArcaneEngine.Objects. Deux types de données nous interesse :

ProgressiveMesh<T>
Resolution

La création d'un mesh progressif et son affichage se fait en trois étapes.

Tout d'abord la création de l'objet (étape pouvant être asynchrone) en passant au constructeur la liste des vertices qui composent le mesh, la liste des indices pour relier les vertices et enfin les poids associés aux vertices (un tableau de booléens pour l'heure) :

ProgressiveMesh<VertexPositionNormalTexture> mesh = new ProgressiveMesh<VertexPositionNormalTexture>(vertices, ints, null);

Puis le chargement des buffers 3D lorsque le device a été créé

mesh.Load(this._device);

Enfin l'affichage du mesh

this.mesh.Render();

La gestion des MRM est beaucoup plus simple qu'avec la classe de Direct3DX.

Revenons sur la généricité de la classe. Le développeur doit indiquer un argument de spécificité a la classe générique ProgressiveMesh (ici VertexPositionNormalTexture). Il s'agit en fait de la classe utilisée pour le type de vertices.

A partir de cet argument, la classe pourra extraire les positions de chaque vertices et, avec les indices, calculer les différentes résolutions. Elle pourra en outre extraire le format des vertices pour l'affichage, elle pourra aussi renvoyer à l'utilisateur pour chaque resolution les buffers et array de vertices actuellement affichés.

Pour changer la résolution deux choix. Soit vous utilisez la propriété NumberOfVertices pour indiquer directement le nombre de vertices a afficher. Soit vous utilisez la property Resolution en donnant un membre de l'énumération :

    public enum Resolution
    {
        /// <summary>
        /// <para>No resolution : no mesh rendered.</para>
        /// </summary>
        None = 0,
        /// <summary>
        /// <para>No resolution : no mesh rendered.</para>
        /// </summary>
        Dynamic = -1,
        /// <summary>
        /// <para>Ten percents of the mesh's vertices used to render it.</para>
        /// </summary>
        Lowest = 10,
        /// <summary>
        /// <para>Twenty five percents of the mesh's vertices used to render it.</para>
        /// </summary>
        Low = 25,
        /// <summary>
        /// <para>Fivety percents of the mesh's vertices used to render it.</para>
        /// </summary>
        Medium = 50,
        /// <summary>
        /// <para>Seventy five percents of the mesh's vertices used to render it.</para>
        /// </summary>
        High = 75,
        /// <summary>
        /// <para>One hundred percents of the mesh's vertices used to render it.</para>
        /// <remarks>Full vertices are used.</remarks>
        /// </summary>
        Full = 100

}

Le changement de la résolutiond'un mesh demande un leger temps de calcul à priori invisible à l'écran.

Nous n'analyserons pas ici le code qui reste assez simple. A l'intérieur de la classe ProgressiveMesh se trouve la region "Multi resolution computing" qui contient les méthodes liées au calcul de la resolution. La méthode ComputeEdgeCostAtVertex détermine le cout de la fusion d'un vertex, la méthode Collapse réalise cette fusion et MinimumCostEdge permet de trouver le vertex ayant le coût le plus bas pour une fusion. A noter que la classe ProgressiveMesh possède deux types internes : Vertex et Triangle qui permettent d'opérer sur les vertices et les faces plus facilement.

Une analyse du code par vos propres moyens devrait eclaircir tous les points encore obscurs à vos yeux. N'hesitez pas a poster des commentaires pour toutes questions.

A l'intérieur de la classe Game1 se trouve le code qui montre comment utiliser notre classe ProgressiveMesh. L'application principale contient en outre un ensemble de classes statiques qui contiennent des ensembles de vertices et d'indices permettant de charger un MRM. Elles héritent toutes de l'interface IData qui permet une utilisation générique de ces dernières.

Les liens

Evidemment en première place le site de Stan Melax

http://www.melax.com/polychop/

Ensuite le site de Hugues Hoppes

http://research.microsoft.com/~hoppe/

(déprimant parcequ'on voit qu'il fait des trucs super, mais on comprend rien)

Sample

Vous pouvez télécharger les trois samples ici.

Conclusion

L'application au final se présente ainsi :

L'interface graphique est rudimentaire mais nous l'améliorerons avec l'arrivée de l'annexe portant sur l'UI. Les touches Page Haut et Page Bas permettent de passer d'une résolution à une autre. Les touches + et - permettent de modifier la resolution plus finnement en changeant le nombre de vertices affichés. La souris permet de déplacer la camera autour du mesh affiché. Enfin la touche espace permet de changer de modèle. L'application affiche 6 modèles :

Beethoven
Fourmi
Un terrain
Porsche
Vache
Lapin

A noter que le modèle terrain sert à voir l'utilité du tableau de poids passé au constructeur. Sans ce poid, la portion de terrain "s'arrondit" au fil de la réduction de résolution en perdant ainsi tout son aspect. Notez de même que le modèle fourmi montre les limites de notre système sur les formes 3D disposant de peu de vertices ...

A bientôt sur ce Blog !

Valentin Billotte

N'hesitez surtout pas à me faire part de vos incomprehensions afin de pemettre d'améliorer ce cours pour le rendre plus accessible aux autres (trèèèès important)!

Vous pouvez télécharger les trois samples ici.

Retourner au sommaire des cours