[MY - AL] Subdivision de mesh en zones

[Sebela]

Salut à tous !

Je travaille en ce moment sur un projet de gestion de planètes (Pour ceux qui l'ont pas vu => http://www.unity3d-france.com/unity/php ... 12&t=16213 )
Je me penche actuellement sur un système de subdivision en zones de ma planète. Cela me permettra entre autres de gérer le pathfinding pour les habitants de la planète.
Chaque zone possède une info sur son altitude min, son altitude max, son dénivelé.
Pour l'instant, j'ai uniquement créé des zones selon l'id du vertex : vertex 1 à 10 => zone 1, vertex 11 à 20 => zone 2 ...
Ensuite, j'indique combien de zones je souhaite avoir et mon script s'occupe du reste.




Seulement, ce serait trop simple J'essaye de trouver un moyen pour créer des zones par position dans l'espace. Dans mon exemple, on peut voir que certaines zones sont désolidarisées. Quelqu'un aurait-il une idée de comment créer des zones selon un critère de proximité ?
Ps : sinon j'ai regardé le système de navmesh de unity mais je ne sais pas s'il serait compatible avec un repère sphérique
Merci d'avance !

[djulio74]

Dis nous en un peu plus, en tout cas moi j'aimerais en savoir plus, Manipuler les mesh j'aime bien ^^

Ok aujourd'hui tes zone sont définies en fonction de l'emplacement du vertex dans l'array du mesh si j'ai bien compris.
Comment voudrais tu définir tes zones dans l'espace?
Créer de zones en fonction d'un critère de proximité.. oui mais proximité par rapport à quoi?

Tu pourrais choisir aléatoirement un certain nombre de vertex dans ton array du mesh. disons Vector3[] CentresZones
tu défini pour chacun une zone. donc autant de zone que de CentresZones.
pour chacun de vertex du mesh, tu calcul sa distance par rapport aux CentresZones. le CentresZones le plus proche définira sa propre zone au vertex testé.

[Sebela]

Hello Djulio

Oui tu as tout à fait compris ! Pour l'instant c'est l'emplacement du vertex dans l'array du mesh qui détermine la zone affectée.

Mon code :

Zone

Code : Tout sélectionner

private Vector3[] _vertices;
    private float _minHeight, _maxHeight, _meanHeight, _deltaHeight;
    private Color _col;

    public Zone(Vector3[] vertices)
    {
        _vertices = vertices;
        _col = new Color(Random.value, Random.value, Random.value);
    }

    public void SetMinHeight(Vector3 center)
    {
        float height = float.PositiveInfinity;
        foreach (Vector3 v in _vertices)
        {
            if (Vector3.Distance(v, center) < height)
            {
                height = Vector3.Distance(v, center);
            }
        }
        _maxHeight = height;
    }


    public void SetMaxHeight(Vector3 center)
    {
        float height = 0;
        foreach (Vector3 v in _vertices)
        {
            if (Vector3.Distance(v, center) > height)
            {
                height = Vector3.Distance(v, center);
            }
        }
        _minHeight = height;
    }

ZoneManager

Code : Tout sélectionner

_zones = new List<Zone>();
        _planeteMesh = GetComponent<MeshFilter>().mesh;
        _nbVertex = _planeteMesh.vertexCount;
        _nbVertexPerZone = (_nbVertex / _nbZones);
        for (int a = 0; a < _nbZones; a++)
        {
            Vector3[] vertices = new Vector3[_nbVertexPerZone];
            for (int i = 0; i < _nbVertexPerZone; i++)
            {
                vertices[i] = _planeteMesh.vertices[a * _nbVertexPerZone + i];
            }
            Zone zone = new Zone(vertices);
            zone.SetMinHeight(transform.position);
            zone.SetMaxHeight(transform.position);
            _zones.Add(zone);
        }

C'est vrai que "critère de proximité" ce n'est pas très précis ^^', j'avais pensé à prendre des vertex au hasard et à récupérer tous les vertices qui sont à une distance x de ce vertex. Mais ce que je n'ai pas précisé c'est que je cherche un moyen pour qu'il n'y ait pas d'intersection entre les zones et que tous les vertex appartiennent à une zone.
Tu vois ce que j'essaye de faire ?

[djulio74]

oui mais ça peut marcher aussi sauf que :
- au lieux que pour chaque zone tu test tout les vertex voir s'il sont plus proche d'une distance donnée, il faut que pour chaque vertex, tu récupère le centre zone le plus proche, et lui assigne sa zone.

[Sebela]

J'ai fais un dessin !
D'ailleurs, en dessinant ce que je voulais ça m'a permis de mieux voir ce que je voulais
En fait j'essaye de subdiviser mon mesh en régions selon la densité de points (genre 5 points par région) avec la contrainte que la région soit convexe (comme ci-dessous). D'où le fait que j'ai pensé à une distance au point (comme un radius) pour que la forme obtenue ne soit pas concave.


[EDIT] Je viens de voir ton message. Oui en effet tu as raison, il vaut mieux partir du point et lui affecter le centre le plus proche, je me demande juste comment définir mes centres pour qu'ils soient à une distance raisonnable les uns des autres

[djulio74]

ça ne va pas être des plus simple de définir les régions fonction de leur nombre de points. il faudrait plutôt définir le nombre de région en fonction du nombre de points dispo, ce qui te donnera une moyenne de points par région correspondante.

si tu fais ma méthode, dans tout les cas tes zones seront convexe. En fait la frontière entre deux zone sera un ligne droite. donc chaque zone s'apparentera à un polygone, au nombre de coté correspondant au nombres de zones voisines.

Je me suis permis de faire un petit test simple et en utilisant un shader définissant l'albedo par la couleur du vertex :

Code : Tout sélectionner

	int _zoneCount = 25;

	void Start () {
		Mesh mf = GetComponent<MeshFilter>().mesh;
		Vector3[] vertex = mf.vertices;
		Color[] VertexCol = new Color[vertex.Length];
		Color[] zone = new Color[_zoneCount];
		Vector3[] centerZone = new Vector3[_zoneCount];

		for ( int i = 0 ; i < _zoneCount ; i++){
			zone[i] = new Color(Random.Range(0.0f,1.0f), Random.Range(0.0f,1.0f),Random.Range(0.0f,1.0f),1);
			centerZone[i] =  vertex[Random.Range(0,vertex.Length-1)];
		}

		for ( int i = 0 ; i < vertex.Length ; i++){
			float distMin = Mathf.Infinity;
			for ( int j = 0 ; j < centerZone.Length ; j ++){
				float dist = (vertex[i] - centerZone[j]).sqrMagnitude;
				if( dist < distMin){
					VertexCol[i] = zone[j];
					distMin = dist;
				}
			}
		}
		mf.colors = VertexCol;		
	}

En fait au départ tu défini le nombre de zone, ici 25 ( le mesh de la sphère ayant 2500 vertices).
j'assigne à chaque zone une couleur aléatoire, et un point aléatoire (centerZone) parmi les vertex dispo sur le mesh.
Ensuite pour chaque vertex, je test sa distance par rapport aux centres des zones. Si le centre tester est plus proche que l'ancien, on applique la couleur de la zone au vertex.

Ensuite libre a toi, quand tu défini un centre de zone de tester avec les précédent s'il n'est pas trop proche, si c'est le cas, tu en assigne un nouveau. pour éviter un StackOverflow, il faudrait définir un nombre max de tentative. si au bout de x tentative le centre choisis est toujours trop proche d'un autre, tu l'assigne quand même.

Idem, a l'inverse tu pourrait utiliser une list plutôt qu'un array pour tes centres. quand tu ajoute un centre, s'il est trop proche ou trop loin d'un autre, tu choisis un autre vertex. pareil pour eviter les StackOverflow, définir un nombre max de tentative. si au bout de x tentative, toujours pas a la bonne distances des autres, tu arete là et commence a assigner les zones aux vertex.

PS : Exemple avec mon code : On voit que chaque zone est plus ou moins grande, c'est pas regulier

[djulio74]

Et parce que j'étais lancé, j'ai mis en application l'idée de la liste pour avoir une répartition régulière des zones :
Du coup cette fois au lieu de définir le nombre de zone, on defini la taille de celle ci via MinDist. En fait MinDist correspond au rayon de la sphere dans laquelle seront les point de la zone, s'il ne sont pas plus proche d'une autre zone.

Code : Tout sélectionner

	Vector3[] vertex;			// les vertex du mesh
	List<Vector3> centerZone; 	//la list a incrémenter de center, donc nombre de zone
	float MinDist = 1.0f; 		// la distance minimum a laquelle doivent etre 2 centre

	void Start () {

		// on initialise la liste des centre
		centerZone = new List<Vector3>();

		// on recherche le mesh du gameobject et assign se vertices a vertex
		Mesh mf = GetComponent<MeshFilter>().mesh;
		vertex = mf.vertices;

		// on fait un certain nombre de recherche de centre
		// il faut beaucoup d'itération pour etre sur que la densité des zone soitent le plus uniforme possible
		for ( int c = 0 ; c < 1000 ; c++) {
			FindCenter();
		}

		// on stock un nouvel array pour la couleur des vertex
		Color[] VertexCol = new Color[vertex.Length];
		// on stock un array de couleur, de même logueur que la liste des centres
		Color[] zoneColor = new Color[centerZone.Count];

		// pour chaque élément de zoneColor, on lui attribu une couleur aléatoire.
		for ( int i = 0 ; i < centerZone.Count ; i++){
			zoneColor[i] = new Color(Random.Range(0.0f,1.0f), Random.Range(0.0f,1.0f),Random.Range(0.0f,1.0f),1);
		}

		// pour chacun des vertex du mesh,
		for ( int i = 0 ; i < vertex.Length ; i++){
			float distMin = Mathf.Infinity;
			// on calcul sa distance par rapport aux centre.
			for ( int j = 0 ; j < centerZone.Count ; j ++){				
				float dist = (vertex[i] - centerZone[j]).sqrMagnitude;
				// si sa distance est inférieur au précedent plus proche trouvé, on lui assigne sa couleur correspondante
				if( dist < distMin){
					VertexCol[i] = zoneColor[j];
					distMin = dist;
				}
			}
		}
		// on applique enfin au messh la couleur de tout les vertices.
		mf.colors = VertexCol;		
	}

	void FindCenter(){

		// on defini aléatoirement un centre
		Vector3 CenterToAdd =  vertex[Random.Range(0,vertex.Length-1)];

		// on test avec les autre centre deja présent dans la liste
		for ( int i = 0 ; i < centerZone.Count ; i++){
			float dist = (CenterToAdd-centerZone[i]).magnitude;
			// si celui qu'on a choisis est trop proche d'un autre, on s'arrete la pour celui la
			// on passe a l'itération suivante en stoppant la fonction en cours
			if( dist < MinDist){				
				return;
			}
		}
		// si la fonction arrive jusqu'ici, c'est qu'aucun autre centre n'est trop proche
		// on ajoute donc CenterToAdd a la liste. Et on passer a l'itération suivante.
		centerZone.Add(CenterToAdd);

	}

Ce qui donne avec différentes valeur de MinDist : Cette fois les zones sont beaucoup plus reguliere

[Sebela]

Djulio.... tu surpasses toutes mes espérances !

J'étais en train de regarder ton code d'au-dessus et je me disais "whoa, c'est super chouette, il me file limite une solution clé en main !! Le seul hic c'est qu'avec cette méthode les régions auront tendance à pas être uniformes"

Et là, alors que je jubile à l'idée d'avoir une solution qui s'approche beaucoup de ce que je cherche, tu me ponds THE solution !
Un très grand merci Djulio, c'est vraiment une aide précieuse pour moi !

[djulio74]

Bah écoute avec plaisir!
Test voir ça, comment tu peut l’implanter dans ton projet, et reviens nous montrer ce que ça donne

[Sebela]

ça y est j'ai pu l'implémenter dans mon projet ^^

Voici ce que ça donne avec la première méthode (on voit que les régions sont bien convexes mais pas vraiment de même surfaces :


Puis avec ta méthode :
Distance minimale de 1.5f :


Distance minimale de .2f :


ça marche du tonnerre

Mon code (légèrement réadapté pour mon besoin) :
Classe Zone :

Code : Tout sélectionner

using System.Collections.Generic;
using UnityEngine;

public class Zone {

    private List<Vector3> _vertices;
    private Vector3 _centerZone;
    private float _minHeight, _maxHeight, _meanHeight, _deltaHeight;
    private Color _col;

    public Zone(Vector3 center)
    {
        _centerZone = center;
        _col = new Color(Random.value, Random.value, Random.value);
        _vertices = new List<Vector3>();
    }

    public void SetVertices(List<Vector3> vertices)
    {
        _vertices = vertices;
    }

    public void SetMinHeight(Vector3 center)
    {
        float height = float.PositiveInfinity;
        foreach (Vector3 v in _vertices)
        {
            if (Vector3.Distance(v, center) < height)
            {
                height = Vector3.Distance(v, center);
            }
        }
        _minHeight = height;
    }


    public void SetMaxHeight(Vector3 center)
    {
        float height = 0;
        foreach (Vector3 v in _vertices)
        {
            if (Vector3.Distance(v, center) > height)
            {
                height = Vector3.Distance(v, center);
            }
        }
        _maxHeight = height;
    }

    public Color Col
    {
        get
        {
            return _col;
        }
    }

    public List<Vector3> Vertices
    {
        get
        {
            return _vertices;
        }
    }

    public Vector3 CenterZone
    {
        get
        {
            return _centerZone;
        }
    }


}

Classe ZoneManager :

Code : Tout sélectionner

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ZoneManager : MonoBehaviour {

    private Mesh _planeteMesh;
    [SerializeField]
    private int _nbZones;
    private int _nbVertex;
    private int _nbVertexPerZone;
    private List<Zone> _zones;

    private void Start()
    {
        _zones = new List<Zone>();
        _planeteMesh = GetComponent<MeshFilter>().mesh;
        _nbVertex = _planeteMesh.vertexCount;
        _nbVertexPerZone = (_nbVertex / _nbZones);

        for (int i = 0; i < 1000; i++)
        {
            FindCenter(1.5f);
        }

        for (int i = 0; i < _nbVertex; i++)
        {
            float distMin = Mathf.Infinity;
            Zone tempZone = null;
            foreach (Zone z in _zones)
            {
                float dist = (_planeteMesh.vertices[i] - z.CenterZone).sqrMagnitude;
                if (dist < distMin)
                {
                    distMin = dist;
                    tempZone = z;
                }
            }
            tempZone.Vertices.Add(_planeteMesh.vertices[i]);
        }

    }

    private void OnDrawGizmos()
    {
        if (_zones == null)
        {
            return;
        }

        if (Camera.current == Camera.main)
        {
            Gizmos.matrix = transform.localToWorldMatrix;
            foreach (Zone z in _zones)
            {
                foreach (Vector3 v in z.Vertices)
                {
                    Gizmos.color = z.Col;
                    Gizmos.DrawSphere(v, .2f);
                }
            }
        }
    }


    private void FindCenter(float minDist)
    {
        Vector3 center = _planeteMesh.vertices[Random.Range(0, _nbVertex - 1)];
        foreach (Zone z in _zones)
        {
            float dist = (center - z.CenterZone).magnitude;
            if (dist < minDist)
            {
                return;
            }
        }
        Zone zone = new Zone(center);
        _zones.Add(zone);
    }

}

Maintenant je vais essayer d'optimiser un peu pour réduire le temps de calcul par compassion pour mon vieux pc ^^'
Encore merci Djulio !!