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!

Liste aneinander hängender Dreiecke: welchen Algorithmus?

Werbeanzeige

LukasBanana

Alter Hase

  • »LukasBanana« ist der Autor dieses Themas

Beiträge: 1 097

Beruf: Shader Tools Programmer

  • Private Nachricht senden

1

10.01.2010, 13:37

Liste aneinander hängender Dreiecke: welchen Algorithmus?

Hi,
ich suche einen Algorithmus, mit dem man - natürlich möglichst schnell - Listen erstellen kann, in denen alle Dreiecke Aufgelistet sind, die aneinander hängen.

Ascii Beispiel:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11

*-----*    *-----*
| a / |    | e / |
| / b |    | / f |
*-----*    *-----*
| c / |    | g / |
| / d |    | / h |
*-----*    *-----*

Daraus sollen zwei Listen entstehen.
1. Liste: a, b, c, d
2. Liste: e, f, g, h


Weiß jemand von euch, welchen Algorithmus dafür braucht?
Mein YouTube Channel
Mein Twitter Profil
Meine Projekte auf github.com
Meine Projekte auf bitbucket.org

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

2

10.01.2010, 13:53

Kommt drauf an in welche Form die Daten vorliegen.

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

3

10.01.2010, 13:53

Das wäre eigentlich eine schöne Idee für einen Contest.
Ich nehme mal an, dass du eine Art Vertex-Buffer hast und die Dreiecke somit aus drei Indizes bestehen.

Du kannst das Ganze als Graph auffassen. Die Dreiecke sind Knoten. Zwischen zwei Knoten besteht eine Kante, wenn die Dreiecke mindestens einen gemeinsamen Eckpunkt haben (oder zwei, je nach dem, wie du "aneinander hängen" definierst).

Dann kannst du einen klassischen Graphenalgorithmus darauf anwenden und erhältst die Zusammenhangskomponenten. Die Zusammenhangskomponenten enthalten dann die Dreiecke, die aneinander hängen.

Für weitere Erklärung und einen Algorithmus siehe:
http://de.wikipedia.org/wiki/Zusammenhang_von_Graphen
David Scherfgens Website | Konzentrationstest Polizei

LukasBanana

Alter Hase

  • »LukasBanana« ist der Autor dieses Themas

Beiträge: 1 097

Beruf: Shader Tools Programmer

  • Private Nachricht senden

4

14.01.2010, 18:22

Danke schon mal =) ich schreib gerade eine "VectorGraph" Klasse, mit der man wie bei der std::map aus der STL - nur mit Vektoren - ganz schnell die Vertizen aufspüren kann, natürlich auch mit round-error (von 1.0e-6, also 0.000001).
Wegen dem round-error geht das auch nicht mit einer einfach STL map.
mfg Lukas
Mein YouTube Channel
Mein Twitter Profil
Meine Projekte auf github.com
Meine Projekte auf bitbucket.org

Werbeanzeige