[MonoGame] Octree und "Voxelisierung" eines Meshes

  • C#
  • .NET (FX) 4.5–4.8

Es gibt 1 Antwort in diesem Thema. Der letzte Beitrag () ist von φConst.

    [MonoGame] Octree und "Voxelisierung" eines Meshes

    Hallo,
    ich habe mich mal wieder an Voxel herangetastet und wollte ein relativ simples Mesh (Teapot model) voxelisieren, also mittels Würfel approximieren.

    Ergebnis:


    Funktioniert zwar, problematisch ist jedoch die Laufzeit.

    Das Prinzip funktioniert folgendergestalt:

    Eine Klasse extrahiert die Dreiecke des Models, und fügt sie einer Liste hinzu.
    Ein Octree wird initialisiert und mittels einer relativ simplen Methode geprüft ob Dreieck und BoundingBox kollidieren.

    Dazu werden einfach die Seiten der Dreiecke als Rays, also Geraden behandelt und eben geprüft ob jeweils eines der drei Geraden im BoundingBox ist.

    Die Akkuratesse der Approximation wird bestimmt durch den Treshhold von

    a) dem Abstand der Gerade vom BoundingBox und
    b) der minimalen Größe der BoundingBox ab der dann das Octree zu Ende zerlegt wurde.

    Über eine For-Schleife prüfen ob BoundingBox des derzeitigen Octree-Childs mit irgendeinem Dreieck des Models kollidiert, falls ja
    dann: Generierung acht neuer Kinder mit der Größe / 2 und prüfen ob diese denn mit irgend einem Dreieck kollidieren, et cetera; wenn ja, füge Child hinzu zur Liste.
    Andernfalls: Schleife weiter laufen.

    Bei simplen Modellen ist die Geschwindigkeit ja noch akzeptabel, möchte man jedoch komplexere Modelle laden mit mehr als 30 000 Dreiecken kann das schon eine Weile dauern.
    Das Problem ist folgende Methode:

    C#-Quellcode

    1. public bool Run()
    2. {
    4. if (this.Size.LengthSquared() < TRESHOLD.LengthSquared())
    5. return false;
    8. for (int i = _Index; i < TriangulatedMesh.ModelTriangles.Count; i++)
    9. {
    10. var _Triangle = TriangulatedMesh.ModelTriangles[i];
    12. if (_Triangle.IntersectsBoundingBox(BoundingBox))
    13. {
    14. Vector3 _newSize = Size / 2;
    16. Octree _Child0 = new Octree(TriangulatedMesh, _newSize, Position, i);
    17. Octree _Child1 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(_newSize.X, 0, 0), i);
    18. Octree _Child2 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(0, _newSize.Y, 0), i);
    19. Octree _Child3 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(_newSize.X, _newSize.Y, 0), i);
    21. Octree _Child4 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(0, 0, _newSize.Z), i);
    22. Octree _Child5 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(_newSize.X, 0, _newSize.Z), i);
    23. Octree _Child6 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(0, _newSize.Y, _newSize.Z), i);
    24. Octree _Child7 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(_newSize.X, _newSize.Y, _newSize.Z), i);
    26. if (_Child0.Run())
    27. {
    28. Childs.Add(_Child0);
    29. FullQuadtree.Add(_Child0);
    30. }
    31. if (_Child1.Run())
    32. {
    33. Childs.Add(_Child1);
    34. FullQuadtree.Add(_Child1);
    35. }
    36. if (_Child2.Run())
    37. {
    38. Childs.Add(_Child2);
    39. FullQuadtree.Add(_Child2);
    40. }
    41. if (_Child3.Run())
    42. {
    43. Childs.Add(_Child3);
    44. FullQuadtree.Add(_Child3);
    45. }
    47. if (_Child4.Run())
    48. {
    49. Childs.Add(_Child4);
    50. FullQuadtree.Add(_Child4);
    51. }
    52. if (_Child5.Run())
    53. {
    54. Childs.Add(_Child5);
    55. FullQuadtree.Add(_Child5);
    56. }
    57. if (_Child6.Run())
    58. {
    59. Childs.Add(_Child6);
    60. FullQuadtree.Add(_Child6);
    61. }
    62. if (_Child7.Run())
    63. {
    64. Childs.Add(_Child7);
    65. FullQuadtree.Add(_Child7);
    66. }
    68. return true;
    69. }
    71. }
    73. return false;
    74. }


    Was schnell auffällt: Je weniger die Methode "Intersects" true zurückgibt, desto länger wird die Schleife fortgesetzt.
    Deswegen war meine Idee statt bei jedem Run-Aufruf von 0 anzufangen, einfach vom letzten erfolgreich Treffer-Index des Parents zu kontinuieren.

    Aber auch damit dauert es ziemlich lange (um die 30 Sekunden oder länger!).

    Deswegen war meine zweite Idee nur diejenigen Triangle zu laden, die innerhalb des Parent-BoundingBox sich befinden...
    Problem: Schon diese Operation allein würde das ganze nochmal ziemlich in die Länge ziehen.

    Ich habe Videos auf YouTube gesehen, wo das ziemlich flott vonstatten ging.
    Was tun die da, was ich nicht tu?

    Lieben Dank, und sonnige Grüße.
    _
    Und Gott alleine weiß alles am allerbesten und besser.

    Lösung Gott sei Dank gefunden:

    C#-Quellcode

    1. public bool Run()
    2. {
    4. if (this.Size.LengthSquared() < TRESHOLD.LengthSquared())
    5. return false;
    7. List<Triangle> _temporary = new List<Triangle>();
    8. if (Parent == null)
    9. _temporary = TriangulatedMesh.ModelTriangles;
    10. else _temporary = Parent.ArealTriangles;
    12. for (int i = 0; i < _temporary.Count; i++)
    13. {
    14. var _Triangle = _temporary[i];
    16. if (_Triangle.IntersectsBoundingBox(BoundingBox))
    17. {
    19. ArealTriangles = _temporary.FindAll(p => p.IntersectsBoundingBox(BoundingBox));
    21. Vector3 _newSize = Size / 2;
    23. Octree _Child0 = new Octree(TriangulatedMesh, _newSize, Position, i) { Parent = this };
    24. Octree _Child1 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(_newSize.X, 0, 0), i) { Parent = this };
    25. Octree _Child2 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(0, _newSize.Y, 0), i) { Parent = this };
    26. Octree _Child3 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(_newSize.X, _newSize.Y, 0), i) { Parent = this };
    28. Octree _Child4 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(0, 0, _newSize.Z), i) { Parent = this };
    29. Octree _Child5 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(_newSize.X, 0, _newSize.Z), i) { Parent = this };
    30. Octree _Child6 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(0, _newSize.Y, _newSize.Z), i) { Parent = this };
    31. Octree _Child7 = new Octree(TriangulatedMesh, _newSize, Position + new Vector3(_newSize.X, _newSize.Y, _newSize.Z), i) { Parent = this };
    33. if (_Child0.Run())
    34. {
    35. Childs.Add(_Child0);
    36. FullQuadtree.Add(_Child0);
    37. }
    38. if (_Child1.Run())
    39. {
    40. Childs.Add(_Child1);
    41. FullQuadtree.Add(_Child1);
    42. }
    43. if (_Child2.Run())
    44. {
    45. Childs.Add(_Child2);
    46. FullQuadtree.Add(_Child2);
    47. }
    48. if (_Child3.Run())
    49. {
    50. Childs.Add(_Child3);
    51. FullQuadtree.Add(_Child3);
    52. }
    54. if (_Child4.Run())
    55. {
    56. Childs.Add(_Child4);
    57. FullQuadtree.Add(_Child4);
    58. }
    59. if (_Child5.Run())
    60. {
    61. Childs.Add(_Child5);
    62. FullQuadtree.Add(_Child5);
    63. }
    64. if (_Child6.Run())
    65. {
    66. Childs.Add(_Child6);
    67. FullQuadtree.Add(_Child6);
    68. }
    69. if (_Child7.Run())
    70. {
    71. Childs.Add(_Child7);
    72. FullQuadtree.Add(_Child7);
    73. }
    75. return true;
    76. }
    78. }
    80. return false;
    81. }


    Erläuterung: Jedes mal wenn ein Parent mit einem Triangle kollidiert, werden diejenigen Triangles geladen, die auch innerhalb des Parent sind; das wird so fortgeführt bis jedes Child nur noch paar Durchläufe machen muss.
    Funktioniert jetzt viel besser.

    "Hochauflösende" Voxel-Repräsentation in nur 0.6 Sekunden!



    ( :
    Und Gott alleine weiß alles am allerbesten und besser.

Facebook
Telefonspende