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!

Normalen neu berechnen nach Edge Collapse

Werbeanzeige

Superwayne

Treue Seele

  • »Superwayne« ist der Autor dieses Themas

Beiträge: 242

Beruf: Student & App Entwickler (Xamarin)

  • Private Nachricht senden

1

30.08.2016, 23:46

Normalen neu berechnen nach Edge Collapse

Hallo zusammen,

ich arbeite aktuell an einem Plugin zur Reduzierung der Polygonen Anzahl in einem (3D-)Mesh.
Dazu wandle ich das mesh in die Directed Half Edge Struktur um und iteriere dann über die Half Edges um die Kante mit dem geringsten Fehler zu entfernen (also um die Kante zu entfernen, die das Mesh am wenigsten "verfälscht").
Soweit funktioniert alles, nur weiß ich nicht, wie ich die Normalen nach einem Edge Collapse neu berechnen soll.

Ich habe einmal ein wunderschönes Bild in Paint angefertigt, um das Problem zu illustrieren:


Die orangene Kante soll entfernt werden. An beiden Enden der Kante befinden sich jeweils 4 Vertices mit der gleichen Position aber unterschiedlichen Normalen. Die Vertices a, d, f und g verschwinden durch den Edge Collapse. Die übrigen Vertices werden zu einer gemeinsamen Position auf der entfernten Kante zusammengefasst.
Wie kann ich an dieser Stelle die Normalen neu berechnen?

Meine Idee dazu war, die Normalen für die Faces zu berechnen und für die Vertices einsetzen. Das Problem ist dann, wenn die Vertex Normale beim ursprünglichen Mesh von der Face Normale unterscheidet.

Vielleicht hat ja jemand eine Idee dazu? :)

PS: Wenn wir schon beim Thema sind, muss ich die UV Koordinaten auch anpassen, oder behält man da die originalen UV's und nimmt eine Verzerrung der Textur in Kauf?

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

2

31.08.2016, 09:47

Wenn du wirklich diese Kante entfernen willst, hast du eh ein Problem. Das gibt beim Rendern Fehler-Pixel. Du darfst niemals ein T-Stück bauen (Vertex liegt mitten auf einer fremden Kante). Die Lücken, die in meinem Bild absichtlich eingezeichnet sind, wirst du auch beim Rendering bekommen. Nicht so stark, aber es werden immer einige Pixel dazwischen entstehen können. Dazu kommen Fehler bei der Licht-Interpolation bedingt durch unpassende Normalen (die Kante hat an der Stelle ja gar keine festlegbare Normale, der T-Vertex aber schon!)
»BlueCobold« hat folgendes Bild angehängt:
  • Polys.png
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

3

31.08.2016, 14:52

Zitat von »BlueCobold«

Wenn du wirklich diese Kante entfernen willst, hast du eh ein Problem.


Edge Collapse bedeutet, das der zentrale Vertex an den Würfeleckpunkt hochrutscht, so entstehen an der Vorderseite zwei Dreiecke und kein T-Stück.

Zitat von »Superwayne«

Meine Idee dazu war, die Normalen für die Faces zu berechnen und für die Vertices einsetzen. Das Problem ist dann, wenn die Vertex Normale beim ursprünglichen Mesh von der Face Normale unterscheidet.


Da gibt es viele Ansätze. Ein einfacher wäre z.B. alle Face-Normalen der, an den zu betrachtenden Vertex, angrenzenden Dreiecke zu mitteln.

Edit:

Weitere Infos:
- Such mal "A Comparison of Algorithms for Vertex Normal Computation" in Google für eine Übersicht
- mikktspace.c von Morten S. Mikkelsen
@D13_Dreinig

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »David_pb« (31.08.2016, 15:11)

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

4

31.08.2016, 16:09

Zitat von »BlueCobold«

Wenn du wirklich diese Kante entfernen willst, hast du eh ein Problem. Das gibt beim Rendern Fehler-Pixel. Du darfst niemals ein T-Stück bauen (Vertex liegt mitten auf einer fremden Kante). Die Lücken, die in meinem Bild absichtlich eingezeichnet sind, wirst du auch beim Rendering bekommen. Nicht so stark, aber es werden immer einige Pixel dazwischen entstehen können. Dazu kommen Fehler bei der Licht-Interpolation bedingt durch unpassende Normalen (die Kante hat an der Stelle ja gar keine festlegbare Normale, der T-Vertex aber schon!)

Wenn ich das richtig verstanden hab, will er einen Edge-Collapse durchführen. Ein Edge-Collapse kann niemals ein T-Stück erzeugen da dabei nicht einfach nur die Kante entfernt wird (sowas würde wenig Sinn machen, da ein Dreiecksnetz dabei in allgemeine Vielecke degeneriert ohne dass irgendwas gewonnen würde), sondern die Vertices an beiden Enden der Kante zusammengezogen werden bis die Kante Länge 0 hat und durch einen fused Vertex ersetzt werden kann (hence the name; die inverse Operation wäre ein Vertex-Split).

Zitat von »Superwayne«

Die orangene Kante soll entfernt werden. An beiden Enden der Kante befinden sich jeweils 4 Vertices mit der gleichen Position aber unterschiedlichen Normalen.

Nun, das ist ein Problem für das es keine absolute Lösung gibt. Erstens einmal würde ich die Datenstruktur im Allgemeinen so bauen, dass Dreiecke wie die in deinem Beispiel mit dem Würfel ihren gemeinsamen Vertex teilen, also tatsächlich auf ein und den selben Vertex verweisen (Half-Edge enthält Vertex Index anstatt direkt die Vertexdaten; ich nehme an, dass bei dir im Moment vermutlich letzteres der Fall ist). Damit könntest du zumindest einmal scharfe Würfelkanten modellieren und es sollte möglich sein, basierend auf diesen Informationen bis zu einem gewissen Grad auch beim Edge-Collapse zu entscheiden, welche Vertices welche Normalen bekommen. Weiterführend gibt es dann so Dinge wie Crease-Flags und Smoothing-Groups. Und wenn du's ganz allgemein willst, dann schaut dir mal Wedges an: http://hhoppe.com/efficientpm.pdf

Zitat von »Superwayne«

PS: Wenn wir schon beim Thema sind, muss ich die UV Koordinaten auch anpassen, oder behält man da die originalen UV's und nimmt eine Verzerrung der Textur in Kauf?

Ich würde mal meinen das hängt davon ab wie genau dein Edge-Collapse funktioniert. Ziehst du beide Vertices der Kante zum gemeinsamen Zentroid hin oder lässt du einen Vertex fix und ziehst den anderen zu dessen Position!? In ersterem Fall wirst du die UVs sinnvollerweise anpassen wollen. In letzterem Fall nicht.
m4studios

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »dot« (31.08.2016, 16:18)

Superwayne

Treue Seele

  • »Superwayne« ist der Autor dieses Themas

Beiträge: 242

Beruf: Student & App Entwickler (Xamarin)

  • Private Nachricht senden

5

01.09.2016, 00:11

Richtig, die beiden Vertices der Kante sollen vereinigt werden (aktuell in der Mitte, später anhand einer Berechnungsfunktion irgendwo auf der Kante, so dass das Mesh möglichst wenig "verfälscht" wird). Entschuldigung für die Verwirrung @BlueCobold, das Wort "entfernen" habe ich verwendet, weil "Kante zusammen fallen lassen" so eine lange Beschreibung für einen Edge Collapse ist.

Zitat von »dot«

Erstens einmal würde ich die Datenstruktur im Allgemeinen so bauen, dass Dreiecke wie die in deinem Beispiel mit dem Würfel ihren gemeinsamen Vertex teilen, also tatsächlich auf ein und den selben Vertex verweisen (Half-Edge enthält Vertex Index anstatt direkt die Vertexdaten; ich nehme an, dass bei dir im Moment vermutlich letzteres der Fall ist).

Ich arbeite tatsächlich schon mit Indices. Allerdings haben mehrere Half Edges niemals den gleichen Index, da sich dich Vertices einer Half Edge zwar die Position teilen, jedoch meistens verschiedene Normalen und UV Koordinaten besitzen. Durch den Aufbau der Datenstruktur kann ich aber zu allen Vertices navigieren, die auf einem Eckpunkt liegen.
Aktuell werden beim Collapse die Vertices der Faces links und rechts von der Kante entfernt (Beim vorherigen Bild a, c, f und g). Die Positionen der anderen Vertices (b, c, e und h) am Anfang/Ende der Kante werden auf die Mitte der Kante verschoben. Somit müssen keine Indices aktualisiert werden.

Der Algorithmus funktioniert auch soweit, die Positionen werden neu berechnet. Nur die Beleuchtung stimmt danach nicht, weil die Normalen nicht angepasst werden. So sieht das ganze aktuell aus (ohne Schatten mit türkisenem Licht):


Links ist das Original und rechts die vereinfachte Version. Wie man sieht, sind die Seiten genau gleich beleuchtet wie vorher, auch wenn sich die Ausrichtung der verbliebenen Faces geändert hat.

Ich werde mir die Links bzw. Suchbegriffe morgen mal anschauen, vielen Dank dafür.

Zitat von »dot«

Ich würde mal meinen das hängt davon ab wie genau dein Edge-Collapse funktioniert. Ziehst du beide Vertices der Kante zum gemeinsamen Zentroid hin oder lässt du einen Vertex fix und ziehst den anderen zu dessen Position!? In ersterem Fall wirst du die UVs sinnvollerweise anpassen wollen. In letzterem Fall nicht.

Wie oben beschrieben werden die Vertices irgendwo auf der Kanto zusammen gezogen. Wie ich die UV's dabei anpassen muss/kann ist mir allerdings momentan schleierhaft.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

6

01.09.2016, 10:43

Zitat von »Superwayne«

Zitat von »dot«

Ich würde mal meinen das hängt davon ab wie genau dein Edge-Collapse funktioniert. Ziehst du beide Vertices der Kante zum gemeinsamen Zentroid hin oder lässt du einen Vertex fix und ziehst den anderen zu dessen Position!? In ersterem Fall wirst du die UVs sinnvollerweise anpassen wollen. In letzterem Fall nicht.

Wie oben beschrieben werden die Vertices irgendwo auf der Kanto zusammen gezogen. Wie ich die UV's dabei anpassen muss/kann ist mir allerdings momentan schleierhaft.

Nun, ich würde mal versuchen, ob man nicht generell für die Vertex Attribute einer kollabierten Edge einfach die entsprechend entlang der ursprünglichen Edge interpolierten Attribute der ursprünglichen zwei Vertices nehmen sollte; wenn du also einfach den Mittelwert der Vertex Position nimmst, dann auch einfach den Mittelwert der UVs/Normalen/etc. nehmen (nicht vergessen, die Normalen zu renormalisieren).
m4studios

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »dot« (01.09.2016, 10:51)

Superwayne

Treue Seele

  • »Superwayne« ist der Autor dieses Themas

Beiträge: 242

Beruf: Student & App Entwickler (Xamarin)

  • Private Nachricht senden

7

01.09.2016, 12:15

Die Idee klingt gut, nur woher weiß ich, welche Vertices zusammen gehören? Es ist ja zum Beispiel auch möglich, dass auf einer Seite der Kante 3 Vertices (gleiche Position, unterschiedliche Normalen/UVs) liegen und auf der anderen 4 oder mehr. Da wird die Zuordnung dann kompliziert.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

8

01.09.2016, 13:33

Deiner Beschreibung nach hast du im Fall von geteilten Vertices mit unterschiedlichen Attriuten ja bereits Half-Edges mit separaten Vertices, die lediglich die selbe Position haben. Um den Edge Collapse durchzuführen, musst du ja bereits alle entsprechenden Half-Edges und die daran hängenden Vertices auffinden und deren Position anpassen (basierend auf der Nachbarschaftsinfo kannst du ja durch alle Half-Edges, die an einer Ecke ankommen bzw. von der Ecke weglaufen, wandern). Wenn wir einfach mal davon ausgehen, dass ein Vertex genau dann dupliziert wird, wenn eine oder mehrere der am Vertex ankommenden Kanten eine scharfe Kante sein soll und ansonsten alles glatte Kanten sind, dann kannst du basierend auf dieser Information die Normalen der kollabierten Vertices (entfernen kannst du ja maximal nur die Vertices der zwei kollabierten Half-Edges) einfach neu berechnen:
  1. Setze alle Normalen der Vertices an deiner Ecke auf 0
  2. Wandere reih um durch alle Dreiecke die an der Ecke zusammenkommen, berechne die Dreiecksnormale und addiere die Normale zur entsprechenden Vertexnormale
  3. Normalisiere alle Normalen der Vertices an der Ecke
Ganz allgemein geht's dann natürlich nur mit z.B. Wedges...
m4studios

Superwayne

Treue Seele

  • »Superwayne« ist der Autor dieses Themas

Beiträge: 242

Beruf: Student & App Entwickler (Xamarin)

  • Private Nachricht senden

9

01.09.2016, 17:54

Ah, jetzt verstehe ich, was du mit glatten bzw. scharfen Kanten meinst. Bei einer glatten Kante würden alle Normalen der Vertices an einem Punkt in die selbe Richtung zeigen, um einen weichen Übergang der Beleuchtung zu erzeugen, richtig? Und bei scharfen Kannten entspricht die Normale der Face-Normalen. Gibt es auch (sinnvolle) Mischformen, die ich berücksichtigen müsste?
Zum Einsatz kommt das Programm hauptsächlich für Low-Poly Terrain-Meshes. Da würde vermutlich es vermutlich reichen, die Face-Normale zu nehmen?

Das das navigieren über alle Kanten, die von einem Punkt ausgehen, mache ich bereits, um die Position zu aktualisieren. An der stelle steht gerade ein "//vertex.normal = ?" :D

Werbeanzeige

Ähnliche Themen