Flexibles Quad zuverlässig unterteilen

[Schrompf]

Moin Loite,

ich möchte mal wieder ein Quad unterteilen. Also ein Polygon mit 4 Ecken, oft ein Quadrat, manchmal aber sind Seiten verkürzt oder eine Seite komplett degeneriert und es ist ein Dreieck geworden. Beispiele:

subdiv.png (3.89 KiB) 269 mal betrachtet

Ich hab nun einen ganzen Strudel Wünsche:

a) ich will ne angepasste Unterteilung je nach echter Weite an dieser Stelle.
b) ich will ne regelmäßige Unterteilung, keine sprunghafte Verdopplung an bestimmten Grenzwerten
c) ich will ne absolut verlässliche Unterteilung der Kanten, so dass Nachbar-Quads für die selbe Kante auch die selben Zwischenpunkte produzieren

Habt ihr da ne Idee? Ich hab Sloppy gefragt und die hatte mir zumindest ne Idee eingeimpft, dass ich nicht "entlang einer Kante" denken sollte, sondern "entlang eines abstrakten Faktor [0..1]". Aber ihre Idee, wie ich das dann adaptiv machen könnte, war nur "rekursiv bis zum Erreichen eines Grenzwerts", und das wollte ich mit Wunsch b) oben eigentlich vermeiden. Kann aber sein, dass das am Ende die einzige Option ist, die mir c) gibt.

Und c) ist wichtig für die numerische Stabilität des Gesamt-Konstrukts. Ich habe ja ne Welt aus ganz vielen solcher Quads und Tris. Das Unterteilen ist der erste Schritt, danach laufen noch viele weitere Funktionen über den Mesh. Und wenn die aus der Weltpos irgendwelche Verschiebungen errechnen, zerreist es mir die Welt an den Kanten, die nicht absolut identisch unterteilt wurden.

[Schrompf]

Und ich glaube, ich muss das früher oder später auf Fixpoint umbauen. Also zumindest die Subdivision. Nach meinem Verständnis von FloatingPoint müsste es auch mit float deterministisch hinzukriegen sein, aber mein Bauchgefühl meint, Integer wären verlässlicher.

[Schrompf]

Ich beantworte mir hier beim Aufdröseln meines Problems selbst die Frage, glaube ich. Aber mir dämmerte gerade: wenn ich Bedingung b) (das kontinuierliche Aufteilen) aufgebe, dann könnte es einfach werden:

- ich nehme einfach das Quad unverändert in jeder Form, auch degeneriert
- ich halbiere es an jeder Kante (die länger als Threshold X ist)
- ich rekursiere, bis ein Teilstück an jeder Kante kurz genug ist.

Dann ist die Unterteilung an jeder Außenkante verlässlich, weil das Subdiv-Kriterium nur von den Werten dieser Kante abhängt. Und die Form des Quads ist mir vollkommen wurscht, verkürzte Kanten werden dann einfach weniger unterteilt und 0-Kanten gar nicht. Fertsch.

[edit] Äh... außer dass ich die Halbierende irgendwie noch clever behandeln muss. Also der Mittelpunkt eines Quads, der bei nem Dreieck ja weg oder doch irgendwie in der Mitte sein könnte. Hm.

[joeydee]

- ich nehme einfach das Quad unverändert in jeder Form, auch degeneriert
- ich halbiere es an jeder Kante (die länger als Threshold X ist)
- ich rekursiere, bis ein Teilstück an jeder Kante kurz genug ist.

Kannst du mal eine Unterteilung in jeden deiner Quad-Fälle einzeichnen wie sie denn idealerweise sein sollte? (Ohne an einen spezifischen Algorithmus, geschweige denn Zahlenformate, zu denken?)

Spontan ein paar Gedanken dazu:
- Wenn man jede Kante unterschiedlich rekursiert (sprich, die linke Kante bricht z.B. früher die Rekursion ab, da sie deutlich kürzer ist als die rechte), fehlt mir die Vorstellung, wie dann eine Fläche möglichst trivial unterteilt werden soll.
- Wenn man strikt alle Kanten des Quads rekursiv gleichermaßen unterteilt, bis z.B. die längste das Abbruchkriterium erfüllt, werden Nachbarn nicht gleich unterteilt. Was bei Quad A die längste Kante ist, ist bei Quad B vielleicht die kürzeste.
- Gefühlt muss man sich glaube ich mit sauberer Quadmesh-Topologie aus dem Modeling-Bereich auseinandersetzen, wie man bestimmte Pol-Fälle löst (wo unterschiedliche Unterteilungen aus unterschiedlichen Richtungen aufeinandertreffen).
- Ein ganz anderer Ansatz wären wohl Continuous LOD Algorithmen, wie früher als jeder was mit Heightfields machen wollte.

[Jonathan]

Die Skizze mit den Beispielquads ist nett, aber ein paar Skizzen zu guten und schlechten Unterteilungen wären echt hilfreich.

a) ich will ne angepasste Unterteilung je nach echter Weite an dieser Stelle.
b) ich will ne regelmäßige Unterteilung, keine sprunghafte Verdopplung an bestimmten Grenzwerten
c) ich will ne absolut verlässliche Unterteilung der Kanten, so dass Nachbar-Quads für die selbe Kante auch die selben Zwischenpunkte produzieren

Ich weiß noch nicht, ob diese Wünsche wirklich sinnvoll sind. Was genau meint b)? Dass es komplett kontinuierlich sein soll? Subdivision ist ja inhärent diskret, du kannst ja nichts in 1.34 Quads unterteilen - da muss es ja irgendwo irgendwelche Sprünge geben. Oder ich versteh die Anforderung nicht so ganz (Skizze würde wie gesagt helfen).


Aber was mir noch aufgefallen ist: Dreiecke als Spezielfall klingen eklig. Aber wenn du den Mittelpunkt nimmst und mit allen Kantenmittelpunkten verbindest, wird ein Quad in 4 kleine Quads unterteilt, aber ein Dreieck wird in 3 kleine Quads unterteilt - du hast also nach einem Schritt nur noch Quads übrig, was irgendwie schonmal nett klingt.

[Schrompf]

Ich versuche mich dann mal an ner Zeichnung, aber bin gerade auf Arbeit und heute bis spät abends eingebunden, weiß noch nicht, ob und wann das wird.

Grundsätzlich meint b), dass:
- die Beispiel-Kante eines Quads wächst langsam immer länger.
- eine rekursive Unterteilung würde ab einer kritischen Länge aus 8 Unterteilungen 16 machen, dann irgendwann 32, usw.
- ich wollte eine Unterteilung, die fließend wächst: 8 Unterteilungen, dann 9, dann 10, dann 11, ...

Und so oder so: wenn mein Unterteilungskriterium nur die Länge der Kante ist, dann müssten zwei Quads an dieser gemeinsamen Kante unabhängig voneinander die selben Unterteilungs-Entscheidungen treffen und deterministisch die selben Zwischenpunkte einfügen. Und das ist mir wichtig. Ich will unbedingt verhindern, dass sich Quads untereinander absprechen müssen, das ist logistisch und performance-technisch eine Katastrophe.

[joeydee]

dann müssten zwei Quads an dieser gemeinsamen Kante unabhängig voneinander die selben Unterteilungs-Entscheidungen treffen und deterministisch die selben Zwischenpunkte einfügen.

Genau das ist was ich dann unter meinem ersten Gedankenpunkt hatte:
- Wenn die 4 Seiten dann z.B. 3, 7, 2 und 19 Unterteilungen ergeben, wie sähe dann idealerweise die Flächenunterteilung aus?
"Lösbar" evtl mit dem was ich mit Modeling-Topo meinte, z.B.: https://preview.redd.it/good-topology-v ... 9f76ff441a

P.S.:
Ich gehe dabei davon aus, dass die Unterteilung wieder aus einigermaßen kontrollierten Quads bestehen soll.

[Jonathan]

Grundsätzlich meint b), dass:
- die Beispiel-Kante eines Quads wächst langsam immer länger.
- eine rekursive Unterteilung würde ab einer kritischen Länge aus 8 Unterteilungen 16 machen, dann irgendwann 32, usw.
- ich wollte eine Unterteilung, die fließend wächst: 8 Unterteilungen, dann 9, dann 10, dann 11, ...

Ah, ja, verstehe.

Tesselation-Shader könnten einen Blick wert sein. Ein Trick da ist, dass neue Punkte nicht in der Mitte sondern ganz am Rand eingefügt werden - man hat am Anfang also eine Art super dünnes, degeneriertes Quad. Aber dadurch wird verhindert, dass wenn man langsam rein oder raus zoomt, Punkte plötzlich springen - stattdessen schwimmen Vertices zur Seite.

Ich finde gerade kein gutes Video dazu, aber hier sieht man es in der ersten 20 Serkunden ein wenig (Auch wenn hier Dreiecke statt Quads verwendet werden, ich nehme an, dass es deshalb so hässlisch ausschaut. Aber egal.) Je nachdem wann du was für Übergänge hast, könnte das eine gute Lösung für dich sein. Ich hab mir das damals, als ich Tesselation bei mir eingebaut habe, länger angeschaut, weiß aber gerade nicht, ob ich das auf die schnelle in meiner Engine noch visualisieren kann.

[Schrompf]

subdiv.png (4.85 KiB) 132 mal betrachtet

So fix mal skizziert. Das ist meine jetzige Lösung, wo ich das Quad/Dreieck umordne, bis ich die längste Kante auf +X habe. Und dann iteriere ich darüber und rechne an jeder Höhe eine "Weite" aus und daraus eine Anzahl Unterteilungen. Meine Lösung hat aber das Problem, dass durch das Umsortieren auf die längste Kante die Schrägen der Dreiecke die Primärkante werden, und die werden dann ... erratisch unterteilt, so dass die Zwischenpunkte auf den anderen Kanten dann floating-zufällig werden und nicht mehr regelmäßig deterministisch zum Nachbarn liegen.

Die neue Idee ist jetzt rekursives Subdividen. Wenn ich da eine Kante wegen Unterlänge nicht unterteilen will, schiebe ich deren Teilpunkt auf einen der existierenden Endpunkte, und es kollabieren automatisch die unnötigen Dreiecke. Das klappt mit Dreiecken bisher super, und jetzt muss ich mal rauskriegen, ob das auch mit Quad-Artigen fliegt. Und das ist ja genau dieses "Aufziehen eines anfangs extrem schmalen Dreiecks", dass Du beim GPU-Tesselieren beschrieben hast.

[Schrompf]

Ich hab jetzt echt ne Weile daran gebastelt und fand die Grenzfälle beim Subdividen von Quads echt grenzwertig. Aber dann fiel mir auf, dass ich die alle nicht habe, wenn ich stattdessen Dreiecke subdivide. Das ging jetzt ganz schnell:

Man sieht hier, wie die Punkte aller Quad-Kanten beiderseits sauber aufeinander passen. Ich hab sie jetzt nicht binär verglichen, aber aufgrund des Rechenwegs bin ich halbwegs sicher, dass sie hier noch deterministisch gleich sind. Da das jetzt rekursiv ist, gibt's natürlich nur sprunghafte Veränderungen, aber das ist ok. Und dass die sich mit steigender Kantenlänge öfter unterteilen, müsst ihr mir jetzt einfach mal so glauben.