Subdivison mit Normalen

Für Fragen zu Grafik APIs wie DirectX und OpenGL sowie Shaderprogrammierung.
Antworten
dronus
Establishment
Beiträge: 114
Registriert: 11.01.2010, 01:53

Subdivison mit Normalen

Beitrag von dronus »

Ho,

ich verfeinere einen Mesh in dem ich eine Kante halbiere und dort einen neuen Vertex einführe. Er bekommt erstmal eine Normale gemittelt. Jetzt möchte ich ihn entlang der Normale "raussschieben", so dass eine schöne Oberfläche entsteht. Etwa so:

Code: Alles auswählen

v1=(pos1, normal1)
v2=(pos2, normal2)

Vektor normal_neu=normalisiere(normal1+normal2)

float erhebung=tolleFunktion(v1, v2)

Vektor pos_neu=(pos1+pos2) /2   +   normal_neu * erhebung
nur wie sieht die tolleFunktion aus? Mir fällt nur ein Anhaltspunkt ein: Wenn normal1 und normal2 je in einem 45-Grad Winkel an der Linie pos1-pos2 stehen, insgesamt also 90 Grad, dann sollte pos_beu genau auf dem Viertelkreis der durch die beiden Normalen definiert ist liegen. Damit würde jedes gleichseitige Vieleck zum Kreis, wenn man es immer wieder unterteilt und dass klingt doch sinnig.

Was ich im Netz so zu Mesh Subdivision gesehen hat immer mit mehr Informationen gearbeitet, meistens werden angenzenden Kontrollpunkte in die Rechnung einbezogen.. ich möchte aber nur die Normalen verwenden.
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Subdivison mit Normalen

Beitrag von joeydee »

Du könntest eine quadratische Bezierkurve benutzen:
http://de.wikipedia.org/wiki/Bezierkurv ... 28n.3D2.29

Deine Meshpunkte seien P0 und P2. Bilde die Senkrechten deiner beiden Normalen und ermittle den Schnittpunkt, dann hast du P1. Berechne den Kurvenpunkt bei t=0.5: Die Normale dort ist die Senkrechte auf der Linie zwischen (P0+P1)*0.5 und (P1+P2)*0.5. Der neue Meshpunkt liegt auf der Hälfte dieser Linie.

Damit allein wirst du aber wahrscheinlich nicht glücklich werden. Jedenfalls hat es schon seinen Sinn, warum bei den populären Algorithmen mehr mit einbezogen wird.

EDIT (Aramis): Link korrigiert (é macht scheinbar Probleme)
dronus
Establishment
Beiträge: 114
Registriert: 11.01.2010, 01:53

Re: Subdivison mit Normalen

Beitrag von dronus »

joeydee hat geschrieben:Du könntest eine quadratische Bezierkurve benutzen:
Deine Meshpunkte seien P0 und P2. Bilde die Senkrechten deiner beiden Normalen und ermittle den Schnittpunkt, dann hast du P1. Berechne den Kurvenpunkt bei t=0.5: Die Normale dort ist die Senkrechte auf der Linie zwischen (P0+P1)*0.5 und (P1+P2)*0.5. Der neue Meshpunkt liegt auf der Hälfte dieser Linie.
Ok, das scheint cool zu sein. Aber nur in 2d, in 3d schneiden sich die Normalen fast nie... hmm.
EyDu
Establishment
Beiträge: 100
Registriert: 24.08.2002, 18:52
Wohnort: Berlin
Kontaktdaten:

Re: Subdivison mit Normalen

Beitrag von EyDu »

Hallo!

Ich weiß nicht, ob es zu meiner Idee schon ein Paper gibt, aber das Suchen überlasse ich einfach mal dir ^^ Ich würde einfach mal versuche, über alle Punkte des Mesh ein Voronoi-Diagramm aufbauen. Zu jedem Dreieck des Mesh solltest du eine Kante des Diagramms erhalten. Man betrachte nun diese Kante und nehme den am weitesten von der Fläche entfernten Voronoi-Punkt entgegengesetzt der gemittelten Normalen des Dreiecks. Je länger diese Strecke ist, desto weniger gekrümmt ist das Mesh an dieser Stelle um so weniger musst du den zu erzeugenden Punkt nach außen schieben (hier kluge Funktion einfallen lassen ;-) ). Man müsste eventuell noch einige Sonderfälle betrachten: was passiert zum Beispiel, wenn die Strecke auf der Voronoi-Kante entlang der Normalen kürzer ist als in die Gegenrichtung?.

Ach ja: Die verwendete Voronoi-Kante währe dann wohl die Richtung des hinzugefügten Punkts.

Das Ergebnis fände ich auf jeden Fall interessant, vielleicht kennt ja von euch jemand ein Paper, welches in diese Richtung geht.

Sebastian

Edit: Zwei Minuten länger drüber nachgedacht: Biege einfach immer in die Richtung des Voronoi-Punkts mit der weitesten Entfernung (ggf. auch ins unendliche).
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Subdivison mit Normalen

Beitrag von Schrompf »

Ich habe vor Ewigkeiten mal ausgeformelt, wie weit man den neuen Punkt verschieben muss, damit er zusammen mit den alten Punkten einen Kreis ergibt. Ich finde die Herleitung jetzt nicht mehr, aber im Code sieht das bei mir so aus:

Code: Alles auswählen

      // Position des neuen Punktes errechnen zwischen den beiden alten plus Rundungsoffset
      neupos = (pkt1.mPosition + pkt2.mPosition) * 0.5f;

      // für beide Eckpunkte getrennt die Rausschieb-Menge bestimmen, die der neue Punkt laut Neigung der Normale haben sollte
      TVektor neunorm = (pkt1.mNormale + pkt2.mNormale).Normieren();
      float rundFaktor1 = 0.0f, rundFaktor2 = 0.0f;
      if( neunorm * pkt1.mNormale < 0.999f)
        rundFaktor1 = sqrt( 1 - neunorm * pkt1.mNormale) / sqrt( 1 + neunorm * pkt1.mNormale);
      if( neunorm * pkt2.mNormale < 0.999f)
        rundFaktor2 = sqrt( 1 - neunorm * pkt2.mNormale) / sqrt( 1 + neunorm * pkt2.mNormale);

      // Falls die Normale nach innen geneigt ist, muss sich der Neupunkt in die Oberfläche rein verschieben
      if( pkt1.mNormale * (pkt2.mPosition - pkt1.mPosition) > 0.0f)
        rundFaktor1 = -rundFaktor1;
      if( pkt2.mNormale * (pkt1.mPosition - pkt2.mPosition) > 0.0f)
        rundFaktor2 = -rundFaktor2;

      float rundFaktor = (rundFaktor1 + rundFaktor2) * 0.5f;

      neupos += 0.5f * neunorm * kantenLaenge * rundFaktor; 
Ich hoffe, es hilft Dir. Alle Eingabeparameter sind Vektoren, die * - + Operationen sind also Vektoradditionen bzw. Punktprodukt. Die offizielle Formel scheint zu sein:

rausschiebEntfernung = sqrt( 1 - normPunktProdukt) / sqrt( 1 + normPunktProdukt);

Aus einem Diamanden wird dadurch eine perfekte Kugel. Ein Quader wird bedingt durch seine initiale Dreiecksstruktur aber keine Kugel, sondern irgendwas kartoffelartiges.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Subdivison mit Normalen

Beitrag von joeydee »

Nochmal zur Bezierkurve:
Du könntest alles auf die Ebene projizieren, die durch deine Kante und die gemittelte Normale geht. Ist nichtmal große Rechnerei. Aber eine Ideallösung ist das so oder so nicht, wie bereits erwähnt. Schau auch mal nach Bezier-Patches: http://www.dma.ufg.ac.at/app/link/Allge ... /sub/13439
Die Vertices wären die deines "alten" Meshes, die Tangent Handles ergeben sich aus deiner Normalen (liegen für ein weiches Mesh alle auf der Ebene durch den Vertex, senkrecht zur Normalen, und gehen entlang der Kanten). Gefühlt dürftest du mit 1/3 der Edge-Länge als Handle-Länge ganz gut fahren. Zur Subdivision von Bezier Patches müsstest du einiges im web finden.
dronus
Establishment
Beiträge: 114
Registriert: 11.01.2010, 01:53

Re: Subdivison mit Normalen

Beitrag von dronus »

Schrompf hat geschrieben:Ich habe vor Ewigkeiten mal ausgeformelt, wie weit man den neuen Punkt verschieben muss, damit er zusammen mit den alten Punkten einen Kreis ergibt. Ich finde die Herleitung jetzt nicht mehr, aber im Code sieht das bei mir so aus...
Aus einem Diamanden wird dadurch eine perfekte Kugel. Ein Quader wird bedingt durch seine initiale Dreiecksstruktur aber keine Kugel, sondern irgendwas kartoffelartiges.
Oh wow, danke! Habs mal implementiert. Der Diamant sieht tasächlich gut aus. Nur bei Gebirgen hab ich manchmal noch Ecken, aber vernutlich sind meine Normalen da kaputt.
EyDu hat geschrieben:Ich würde einfach mal versuche, über alle Punkte des Mesh ein Voronoi-Diagramm aufbauen.
Das kommt für mich leider nicht in Frage, weil ich einen Algorithmus brauche der möglichst wenig Daten hat. Das Teilen der Normalen geht nämlich schon wenn man nur drei Vertices mit drei Normalen hat, also für jedes Dreieck unabhängig.

Wenn man nur die Normalen braucht, kann man die Unterteilung für jeden Teil getrennt machen, braucht viel weniger Strukturen im RAM zu behaltn und es geht sogar im Geometrieshader wenn man will.
EyDu
Establishment
Beiträge: 100
Registriert: 24.08.2002, 18:52
Wohnort: Berlin
Kontaktdaten:

Re: Subdivison mit Normalen

Beitrag von EyDu »

Hi.
dronus hat geschrieben:Das kommt für mich leider nicht in Frage, weil ich einen Algorithmus brauche der möglichst wenig Daten hat. Das Teilen der Normalen geht nämlich schon wenn man nur drei Vertices mit drei Normalen hat, also für jedes Dreieck unabhängig.

Wenn man nur die Normalen braucht, kann man die Unterteilung für jeden Teil getrennt machen, braucht viel weniger Strukturen im RAM zu behaltn und es geht sogar im Geometrieshader wenn man will.
Wenn du das online machen willst, dann kann man meinen Vorschlag natürlich vergessen. Der vebraucht doch etwas viel CPU und Speicher.

Das eine Teilung unabhängig vorgenommen worden kann ist klar, die Frage ist natürlich, wie gut die Unterteilung ist. Sinn meines Vorschlags war ja gerade eine globalere Betrachtung um mehr Informationen zu erhalten. Wenn ich Zeit habe, werde ich es vielleicht einfach mal selber testen.

Bis dann,
Sebastian
Antworten