Comment implémenter un octree en C#?

Question

Pour la première fois ici, mais j'ai lu le site depuis quelques années maintenant. J'essaye d'implémenter un type générique simple Octree en C# (en utilisant certains XNA inclus). J'ai fait des recherches approfondies et je comprends le concept, je n'arrive juste pas à le faire fonctionner. La recherche autour de certaines implémentations dans d'autres langues, mais ils semblent tous adaptés à une application spécifique; et je n'ai pas vraiment pu faire beaucoup de sens à partir de ceux-là. Ci-dessous est ma classe Octree jusqu'à présent, le Vector3, BoundingBox, et ContainmentType sont XNA. Je nourris en points max et min, et une liste de points qui sont dans les limites. Cependant, aucun des points n'est réellement ajouté à l'arbre. Toute aide serait grandement appréciée!

public class Octree<T> : ISerializable 
{ 
    Vector3 max; 
    Vector3 min; 
    OctreeNode head; 

    public Octree(Vector3 min, Vector3 max, List<Vector3> values) 
    { 
     this.max = max; 
     this.min = min; 
     head = new OctreeNode(min, max, values);   
    } 

    public Octree() { } 

    public Octree(SerializationInfo info, StreamingContext context) 
    { 
    } 

    public void GetObjectData(SerializationInfo info, StreamingContext context) 
    {    
    } 

    internal class OctreeNode 
    {    
     Vector3 max; 
     Vector3 min; 
     Vector3 center; 
     public Vector3 position; 
     public T data; 

     public BoundingBox nodeBox; 
     public List<OctreeNode> subNodes; 
     public OctreeNode(Vector3 min, Vector3 max,List<Vector3> coords) 
     { 
      nodeBox = new BoundingBox(min, max); 
      subNodes = new List<OctreeNode>(); 

      this.min = min; 
      this.max = max; 
      center = (min + ((max - min)/2)); 

      nodeBox = new BoundingBox(min, max); 
      if (coords.Count == 0) 
      { return; } 
      subNodes.Add(new OctreeNode(center, max)); 
      subNodes.Add(new OctreeNode(new Vector3(min.X, center.Y, center.Z), new Vector3(center.X, max.Y, min.Z))); 
      subNodes.Add(new OctreeNode(new Vector3(min.X, center.Y, max.Z), new Vector3(center.X, max.Y, center.Z))); 
      subNodes.Add(new OctreeNode(new Vector3(center.X, center.Y, max.Z), new Vector3(max.X, max.Y, center.Z))); 

      subNodes.Add(new OctreeNode(new Vector3(center.X, min.Y, center.Z), new Vector3(max.X, center.Y, min.Z))); 
      subNodes.Add(new OctreeNode(new Vector3(min.X, min.Y, center.Z), new Vector3(center.X, center.Y, min.Z))); 
      subNodes.Add(new OctreeNode(new Vector3(min.X, min.Y, max.Z), center)); 
      subNodes.Add(new OctreeNode(new Vector3(center.X,min.Y,max.Z), new Vector3(max.X,center.Y,center.Z))); 


      List<List<Vector3>> octants = new List<List<Vector3>>(); 
      for (int i = 0; i < 8; i++) 
      { 
       octants.Add(new List<Vector3>()); 
      } 
      foreach (Vector3 v in coords) 
      { 
       int i = 0; 
       foreach(OctreeNode n in subNodes) 
       { 
        ContainmentType t = n.nodeBox.Contains(v); 

        if (t.Equals(ContainmentType.Contains)) 
        { 
         octants[i].Add(v); 
        } 
        i++; 
       } 
      } 

      for (int i=0;i<subNodes.Count;i++) 
      { 
       if (octants[i].Count > 0) 
       { 
        Vector3 v = octants[i][0]; 
        octants[i].Remove(v); 
        subNodes[i] = new OctreeNode(subNodes[i].min, subNodes[i].max, octants[i]); 
       } 
      } 
     } 

     public OctreeNode(Vector3 min, Vector3 max) 
     { 
      nodeBox = new BoundingBox(min, max); 
     }    
    } 
} 

Answer 1

Je collé votre code dans un nouveau projet dans Visual Studio et débogué appeler le constructeur Octree avec un couple de valeurs de points. Voici quelques choix faciles qui devraient vous aider à faire fonctionner votre octree.

1. En OctreeNode(Vector3 min, Vector3 max, List<Vector3> coords), certains des subNodes n'ont pas raisonnable min et limites max. Par exemple, new Vector3(min.X, min.Y, max.Z), center s'étend de max.Z à center.z. La limite supérieure est toujours inférieure à la limite inférieure. Essayez la liste des nœuds systématiquement pour réduire la possibilité de telles erreurs, comme ceci:

   subNodes.Add(new OctreeNode(new Vector3(min.X, min.Y, min.Z), new Vector3(center.X, center.Y, center.Z))); 
   subNodes.Add(new OctreeNode(new Vector3(min.X, min.Y, center.Z), new Vector3(center.X, center.Y, max.Z))); 
   subNodes.Add(new OctreeNode(new Vector3(min.X, center.Y, min.Z), new Vector3(center.X, max.Y, center.Z))); 
   subNodes.Add(new OctreeNode(new Vector3(min.X, center.Y, center.Z), new Vector3(center.X, max.Y, max.Z))); 
   subNodes.Add(new OctreeNode(new Vector3(center.X, min.Y, min.Z), new Vector3(max.X, center.Y, center.Z))); 
   subNodes.Add(new OctreeNode(new Vector3(center.X, min.Y, center.Z), new Vector3(max.X, center.Y, max.Z))); 
   subNodes.Add(new OctreeNode(new Vector3(center.X, center.Y, min.Z), new Vector3(max.X, max.Y, center.Z))); 
   subNodes.Add(new OctreeNode(new Vector3(center.X, center.Y, center.Z), new Vector3(max.X, max.Y, max.Z))); 
   

2. Dans le constructeur OctreeNode(Vector3 min, Vector3 max) vous n'initialisez pas les champs min, max et center. Par conséquent, lorsque les OctreeNode finales s ont leurs limites inférieures et supérieures toujours à zéro sur la ligne

   subNodes[i] = new OctreeNode(subNodes[i].min, subNodes[i].max, octants[i]); 
   

3. Sur cette même ligne, vous passer comme noeud valeurs tous les points mais celui qui se trouve en fait dans la plage du noeud. La variable locale v est la valeur comprise dans la plage. Il est supprimé de octants, après quoi octants est passé en tant que valeurs de noeud. Les valeurs transmises au constructeur OctreeNode ne sont jamais stockées nulle part, mais le nœud créé est toujours divisé en nœuds plus petits et les valeurs sont transmises aux sous-nœuds. Par conséquent, la résolution des trois problèmes ci-dessus entraînera une récurrence infinie du code. Pour rompre la récursivité, vous devez mettre en place une condition d'arrêt. Généralement dans octrees, la condition est que s'il y a un nombre suffisamment petit de valeurs à l'intérieur d'un nœud, le nœud n'est pas divisé en sous-nœuds mais la valeur est stockée dans le nœud. Uniquement si le noeud contient suffisamment de valeurs, le noeud est divisé et ses valeurs sont réparties entre les nouveaux sous-noeuds.