Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Datenreduktion in 3D-Mesh

Werbeanzeige

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

1

13.09.2016, 08:42

Datenreduktion in 3D-Mesh

Hi,

ich habe eine 3D-Mesh (Wireframe), dessen Faces ausschließlich aus Dreiecken bestehen und bei dem die Koordinaten als double gespeichert sind. Dieses Objekt ist jetzt für das gewählte ausgabegerät viel zu komplex, d.h. es enthält Faces, die kleiner sind als das ,was darstellbar ist.

Aus diesem Grund würde ich die Daten jetzt gerne reduzieren und die zu kleinen Faces komplett entfernen - das allerdings ohne an den entsprechenden Stellen Löcher entstehen zu lassen. Deswegen zwei Fragen:

1. Gibt es eine (schlanke) Bibliothekt, die sowas kann?

2. Welche Strategie für eine schnelle Datenreduktion wäre sinnvoll? Aktuell fällt mir nur ein, sämtliche Faces durchzuehen, wenn eines zu klein ist, dieses auf einen Punkt zu reduzieren. Problem dabei: es sind Vergleiche mit double-Datentypen notwendig, die nicht immer klappen und immer wenn ich ein Face gefunden und entfernt habe, muss ich die Koordinatenpunkte sämtlicher anderen Faces noch mal durchsehen um festzustellen, ob diese an das Entfernte angrenzen und deswegen ebenfalls verändert werden müssen.

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

2

13.09.2016, 10:31

Zitat von »Elmi«

Welche Strategie für eine schnelle Datenreduktion wäre sinnvoll?

Muss es wirklich schnell gehen? Möchtest du die Daten beim laden reduzieren? An sich könntest du das doch vorher tun und die Modelle reduziert ausliefern.

Zitat von »Elmi«

Aktuell fällt mir nur ein, sämtliche Faces durchzuehen, wenn eines zu klein ist, dieses auf einen Punkt zu reduzieren.

Da gibt es weitere Möglichkeiten. So gibt es Ansätze bei welchen Faces zusammen gefügt werden. Programme wie 3ds Max haben solche Funktionen. Nach kurzer Suche bei Google habe ich raus gefunden dass der Blender Decimate Modifier im Prinzip dafür geeignet sein sollte. Allgemein zu dem Thema und Blender gibt es hier einen Beitrag der hilfreich aussieht. Damit könntest du dann dein Modell in Blender reduzieren und wie gesagt dann direkt angepasst ausliefern.

Wenn es warum auch immer zur Laufzeit sein muss müssen wir wissen um welche Sprache es sich handelt. An sich kannst du aber auch einfach mal selbst bei Google gucken. Stichworte wie "reduce mesh algorithm" haben bei mir zum Beispiel diese beiden Seiten aufgebracht:
http://dev.gameres.com/program/visual/3d…onReduction.pdf
http://www.cs.mtu.edu/~shene/COURSES/cs3…plification.pdf
Das könnte vielleicht weiter helfen. Aber wie gesagt, der Ansatz mit Blender wäre meiner Meinung nach am sinnvollsten.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

3

14.09.2016, 07:37

Zitat von »Schorsch«

Muss es wirklich schnell gehen? Möchtest du die Daten beim laden reduzieren? An sich könntest du das doch vorher tun und die Modelle reduziert ausliefern.


Ja es muss schnell gehen und passiert beim Laden. Ich liefere keine Modelle aus, der Anwender lädt eigene Modelle jeweils selbst.

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

4

14.09.2016, 08:30

Zitat von »Schorsch«

Wenn es warum auch immer zur Laufzeit sein muss müssen wir wissen um welche Sprache es sich handelt. An sich kannst du aber auch einfach mal selbst bei Google gucken. Stichworte wie "reduce mesh algorithm" haben bei mir zum Beispiel diese beiden Seiten aufgebracht:
http://dev.gameres.com/program/visual/3d…onReduction.pdf
http://www.cs.mtu.edu/~shene/COURSES/cs3…plification.pdf
Das könnte vielleicht weiter helfen. Aber wie gesagt, der Ansatz mit Blender wäre meiner Meinung nach am sinnvollsten.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Superwayne

Treue Seele

Beiträge: 242

Beruf: Student & App Entwickler (Xamarin)

  • Private Nachricht senden

5

16.09.2016, 12:09

"Mesh Simplification" wäre ein weiteres Stichwort. Ich bin mir nicht sicher, ob eine fertige Bibliothek deine Ansprüche erfüllt. Die meisten Algorithmen gehen davon aus, das Mesh auf eine bestimmte Anzahl an Polygonen bzw. um einen prozentualen Anteil zu reduzieren.

Allgemein kannst du dein Problem auch anders sehen: Statt nicht darstellbare Dreiecke, kannst du nicht darstellbare Kanten betrachten (die wiederum zu nicht darstellbaren Dreiecken führen).
Was funktionieren sollte, ist ein Edge-Collapse Algorithmus, der als Bewertungsfunktion die Länge der Kanten nimmt und solange Vertices zusammenfügt, bis die kleinste vorhandene Kante im Mesh wieder Darstellbar ist.

Zera

Treue Seele

Beiträge: 133

  • Private Nachricht senden

6

23.09.2016, 02:30

Es gibt eine relativ schlanke C++ Bibliothek für mesh simplification, boundingmesh. (Disclaimer: Ich hab einen Großteil davon implementiert).

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

7

28.09.2016, 14:03

Klingt gut. Kommt die Bibliothek auch mit Löchern im Ursprungs-Mesh klar?

Zera

Treue Seele

Beiträge: 133

  • Private Nachricht senden

8

29.09.2016, 15:33

Sollte kein Problem sein, von den Beispielmeshes hat z.b. das Bunny ein Loch auf der Unterseite, und die Teekanne besteht eh nur aus mehreren Flächen (und keine geschlossenen Körper).

RolandK

Frischling

Beiträge: 6

Wohnort: Weiden i. d. Opf.

Beruf: Softwareentwickler

  • Private Nachricht senden

9

01.10.2016, 08:08

@Zera: Die in der Readme.md veriesenen Bilder werden aktuell nicht dargestellt.
Bin grad drauf gestoßen, weil würde mich auch interessieren.
www.rolandk.de/wp/ Mein Blog
GitHub/FrozenSky Multimedia Framework für .Net/C# (3D-Rendering, 2D-Rendering, etc.)

Zera

Treue Seele

Beiträge: 133

  • Private Nachricht senden

10

02.10.2016, 23:44

Oh, danke für den Hinweis - bei mir liegen die anscheinend noch im Cache und wurden angezeigt, in einem anderen Browser fehlen sie dann bei mir auch.
Ich bin aus dem Projekt schon seit einer Weile draußen, werde es aber weiterleiten.

Derweil die Bilder fürs README: imgur mirror

Edit: README auf github sollte gefixt sein.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Zera« (11.10.2016, 10:17)

Werbeanzeige

Ähnliche Themen