Bitgeometrie und konforme Dreiecke

Eine Integeradresse beschreibt ein Dreieck, aber noch kein Rechengitter. Erst die Auswahl aktiver Blätter und ein konformer Abschluss machen aus der Hierarchie ein geeignetes Finite-Volumen-Gitter.

1. Eine festgelegte geometrische Hierarchie

CFK steht für Coxeter–Freudenthal–Kuhn. Unser Ausgangspunkt ist eine kompatible Simplexzerlegung; die konkrete führende Eins, Eckreihenfolge und Kindnummerierung sind Konventionen dieses Projekts. Sie sind nicht die einzig mögliche CFK-Codierung. Der Bezug zur adaptiven Bisektion folgt dem Manuskript von Persiano, Comba und Barbalho [1].

Wir beginnen mit einem rechtwinklig-gleichschenkligen Wurzeldreieck. Die geordneten Ecken werden gegen den Uhrzeigersinn durchlaufen; an A liegt der rechte Winkel.

\[T_1=\operatorname{conv}\{(0,0),(2,0),(0,2)\},\qquad |T_1|=2.\]

Für ein Dreieck mit Ecken (A,B,C) liegt M in der Mitte der Hypotenuse. Die feste Kindregel lautet:

\[M=\frac{B+C}{2},\qquad T_{2k}=(M,A,B),\quad T_{2k+1}=(M,C,A).\]

Beide Kinder haben die halbe Fläche. Sie überdecken den Elternbereich, überlappen sich aber nur auf ihrer gemeinsamen Kante AM. Rechtwinkligkeit und gleiche Katheten bleiben erhalten: Mit u=B−A und v=C−A gilt u·v=0 und |u|=|v|. Damit ist (−u−v)·(u−v)=0. Das beweist den rechten Winkel eines Kindes; die gleiche Rechnung gilt für das andere.

Alle Winkel bleiben 45°, 45°, 90°. Es entstehen keine immer spitzeren Zellen. Das ist ein geometrischer Vorteil, aber noch kein Beweis isotroper Fehler oder einer bestimmten Genauigkeitsordnung des Hydrocodes.

2. Der Pfad steckt im Bitmuster

\[k=(1b_1\ldots b_d)_2,\quad d=\operatorname{bitlength}(k)-1,\quad \operatorname{parent}(k)=k\mathbin{\texttt{>>}}1.\]

Die erste Eins bezeichnet die Wurzel. Jedes weitere Bit wählt eines der Kinder: 0 das linke, 1 das rechte. Die Codes sind geometrische Adressen und keine unveränderlichen Arraypositionen.

Beispiel einer adressierten Verfeinerung
Dezimal	Binär	Tiefe	Bedeutung
1	`1`	0	Wurzel
4	`100`	2	Zweimal Kind 0
8	`1000`	3	Kind 0 von 4
9	`1001`	3	Kind 1 von 4
7	`111`	2	Hypotenusenpartner von 4

Ein Code a ist Vorfahr von k, wenn sein Pfad ein Präfix des längeren Pfades ist. Nach Kürzen auf dieselbe Tiefe genügt ein Integervergleich:

\[d(a)\le d(k),\qquad k\mathbin{\texttt{>>}}(d(k)-d(a))=a.\]

Auf einer festen zusätzlichen Tiefe r liegen die Nachfahren von k im Integerintervall [2ʳk, 2ʳ(k+1)−1]. Bei unterschiedlichen Tiefen ist numerisches Sortieren dagegen keine räumliche Tiefensuchreihenfolge. Ein gemeinsames Präfix ist auch kein genauer Abstand: Zwei Zellen aus früh getrennten Teilbäumen können eine Kante gemeinsam haben.

3. Was lässt sich vorausberechnen?

Eine Teilung halbiert die Fläche und skaliert die Längen mit 1/√2. Auf Tiefe d folgen daher unabhängig von der Position:

\[A_d=2^{1-d},\quad \ell_d=2^{1-d/2},\quad D_d=2^{3/2-d/2}.\]

Hier bezeichnet ℓ die Kathete, D die Hypotenuse und zugleich den Durchmesser des Dreiecks. Diese Werte können für alle zulässigen Tiefen als Compile-Zeit-Tabelle gespeichert werden. Lage und Orientierung benötigen zusätzlich den Pfad; eine reine Tiefentabelle reicht dafür nicht.

Ecken entstehen aus Halbierungen und sind dyadisch rational. Der Flächenschwerpunkt ist dagegen x̄=(A+B+C)/3 und muss wegen der Division durch drei nicht dyadisch sein. Für eine positiv orientierte Kante P→Q mit Differenz (Δx,Δy) gilt:

\[\boldsymbol n=\frac{(\Delta y,-\Delta x)}{\sqrt{\Delta x^2+\Delta y^2}}.\]

In dieser 2D-Hierarchie treten nur acht gerichtete Einheitsnormalen auf: die vier Achsenrichtungen und die vier Diagonalrichtungen. Richtungstabellen können wiederholte Normierungen ersetzen. Die Auswahl muss dennoch zur tatsächlichen Orientierung der jeweiligen Kante passen. Für einzelne Geometrieabfragen kann Decodierung nützlich sein; für einen vollständigen Baum ist die Wiederverwendung von Elterngeometrie oft günstiger. Das wurde separat gemessen.

4. Warum ein vollständiger Baum nicht genügt

Ein konformes Gitter besitzt keine hängenden Knoten: Zwei Zellen treffen sich entweder gar nicht, in einer gemeinsamen Ecke oder in einer ganzen Kante beider Zellen. Teilt man nur eine Seite einer gemeinsamen Hypotenuse, entsteht genau ein unerlaubter hängender Mittelpunkt.

Code 4 wird geteilt; erst die zusätzliche Teilung von Code 7 beseitigt den hängenden Knoten. — Links: uniforme Tiefe 2. Mitte: unvollständiger Abschluss. Rechts: konformer Abschluss. Abbildung aus Kapitel 2 der Arbeit.

Sei I die Menge geteilter Knoten. Sie muss alle notwendigen Vorfahren und zu jeder inneren geteilten Hypotenuse ihren gleich tiefen Partner enthalten. In unserer festen Hierarchie genügt dazu folgende Arbeitsliste:

I = leere Menge
Arbeit = anfängliche Teilungsanforderungen
solange Arbeit nicht leer:
    k = entnehme(Arbeit)
    falls k in I: weiter
    füge k in I ein
    falls k nicht Wurzel: merke Elternteil(k) vor
    falls Hypotenusenpartner existiert: merke ihn vor

Jede Einfügung ist eine zwingende Folge einer Anforderung. Dadurch entsteht der kleinste zulässige Abschluss in dieser Hierarchie, nicht die kleinste denkbare Triangulierung unter allen Verfahren. Mit N als Knotenmenge und L als Blattmenge gelten:

\[|L|=|I|+1,\qquad |N|=2|L|-1,\qquad \sum_{k\in L}2^{1-d(k)}=2.\]

Diese Zahlen- und Flächenidentitäten allein beweisen keine Konformität. Auch ein vollständiger, aber nichtkonformer Baum erfüllt sie. Für die parallele Konstruktion ist zusätzlich wichtig: Der Abschluss einer Vereinigung von Anforderungen ist hier gleich der Vereinigung ihrer vollständigen globalen Abschlüsse. Das erlaubt unabhängige Teilungslisten, setzt aber voraus, dass keine gebietsübergreifende Anforderung fehlt.

5. Teilchen zuordnen, ohne Toleranzsuche

Ein Punkt wird baryzentrisch als p=(1−b−c)A+bB+cC beschrieben. Für b≥c wählen wir Kind 0, sonst Kind 1. Gleichheit gehört immer zu Kind 0 und macht die Besitzregel auf Trennkanten eindeutig.

\[(b',c')=\begin{cases}(1-b-c,b-c),&b\ge c,\\(c-b,1-b-c),&b<c.\end{cases}\]

Schreibt man b=B/D und c=C/D, bleiben alle Operationen ganzzahlig bei konstantem Nenner D. Aus (B,C) wird entweder (D−B−C,B−C) oder (C−B,D−B−C). Gruppen werden nur so lange geteilt, bis höchstens ein Teilchen pro Blatt bleibt. Identische Punkte lassen sich nicht durch weitere Teilung trennen; der Code muss sie ablehnen.

„Exakt“ bedeutet dabei exakt für die gespeicherten Eingabewerte. Eine bereits gerundete Dezimaleingabe wird durch Integerarithmetik nicht nachträglich genauer.

6. Kanten und Ecksterne

Ein gleich tief berechneter Nachbarcode ist nicht zwingend ein aktives Blatt. Die Suche muss den Code auf das aktuelle Blattgitter auflösen. Für konforme Zellen mit gemeinsamer Kante unterscheiden sich die Tiefen höchstens um eins: Eine Kante kann Kathete oder Hypotenuse sein; aus gleichen Kantenlängen folgt diese lokale Schranke.

Ein Eckstern enthält alle Zellen an einer Ecke, auch solche ohne gemeinsame Kante zur Ausgangszelle. Er wird über die Kantenkontakte und lokale Ecknummern durchlaufen. Der kleinste Winkel ist 45°; deshalb liegen an einer inneren Ecke höchstens acht Dreiecke. Diese Nachbarn helfen bei der Gradientenrekonstruktion, erzeugen jedoch keinen zusätzlichen Fluss über einen Punkt.

Bei Verfeinerung und Vergröberung ist die konservative Restriktion durch die Flächen gewichtet:

\[\overline U_K=\frac{1}{A_K}\sum_{J\subset K}A_J\overline U_J.\]

Die Präfixbeziehung liefert die Zuordnung ohne geometrische Überlappungssuche. Die umgekehrte Operation, Prolongation, benötigt eine zusätzliche Rekonstruktionsregel.

Quellen und Nachweise

Persiano, Comba, Barbalho: An Adaptive Triangulation Refinement Scheme and Construction. Das Erscheinungsjahr wird nicht aus dem Dateinamen abgeleitet.
Die hier dargestellten Konventionen, Herleitungen und Grenzen: Arbeit 0.3, Kapitel 2.
Geometrieversuche im Archiv; die Bucket-Serie untersucht die effiziente Umsetzung der Präfixpartitionierung.

Die Nutzung der Integercodierung für Geometrie und Nachbarn wurde von Pascal Bauer eingebracht. Konkrete Konventionen, Herleitungen und Code wurden im Dialog mit ChatGPT ausgearbeitet. Verwandte bitcodierte Simplexverfahren existieren; diese Seite erhebt keinen allgemeinen Neuheitsanspruch.