Curvature Beziers

De Bezier-curve is een standaardonderdeel van CAD en computergraphics. Net als Bic-pennen is het ontwerp decennia oud en is het overal aanwezig. Je vindt ze vaak als de standaard- of enige keuze in diverse illustratie- en animatietools.

De Bezier-curve werd in 1959 bedacht door Paul de Casteljau en in de jaren 60 verfijnd door Pierre Bézier bij Renault. De blijvende aantrekkingskracht van de Bezier-curve ligt in de eenvoud. Hoewel er geavanceerdere curves zijn uitgevonden en er voortdurend nieuwe worden voorgesteld, blijven deze beperkt tot specifieke domeinen, zoals high-precision CAD of wegenontwerp. In algemeen gebruik weigert de Bezier-curve koppig om troonsafstand te doen, ondanks de tekortkomingen.

Hierdoor zijn Bezier-curves een stukje 'legacy tech' waar we aan vast lijken te zitten. Als software engineer is mijn vraag dan ook: kunnen we Beziers verbeteren zonder alle technologie die erop en ermee is gebouwd ongeldig te maken?

Het antwoord is ja.

Lineaire interpolatie (Lerp-a-derp)

Het tekenen van een Bezier-curve is een verrassend eenvoudig en lineair proces.

Uitgaande van een reeks controlepunten verbinden we deze met lijnen. We bewegen vervolgens gelijktijdig langs deze lijnen om nieuwe punten te genereren, die vervolgens weer met elkaar verbonden kunnen worden. Dit proces wordt herhaald tot er één enkel punt overblijft, dat op de curve ligt.

Deze constructie maakt Beziers veel regelmatiger dan ze op het eerste gezicht lijken. De lineaire interpolaties (ook wel 'lerps' genoemd) kunnen worden samengevat in één compacte formule, bijvoorbeeld voor vier controlepunten $(A, B, C, D)$:

$$ \gamma(t) = A \cdot (1 - t)^3 + B \cdot 3(1 - t)^2 t + C \cdot 3(1 - t) t^2 + D \cdot t^3 $$

De regel is simpel: dalende machten van $(1 - t)$, stijgende machten van $t$, met coëfficiënten afkomstig uit de n-de rij van de driehoek van Pascal:

$$ \begin{array}{ccccccccccccc} &&&&&& 1 \\ &&&&& 1 && 1 \\ &&&& 1 && 2 && 1 \\ &&& 1 && 3 && 3 && 1 \\ && 1 && 4 && 6 && 4 && 1 \\ &1 && 5 && 10 && 10 && 5 && 1 \\ ... &&&&&& ... &&&&&& ... \\ \end{array} $$

Voor curves in 2D en 3D wordt de formule toegepast op de individuele X-, Y- of Z-coördinaten.

Hoewel Beziers geconstrueerd kunnen worden voor elk aantal controlepunten, is het gebruikelijk om alleen kubieke Beziers met vier controlepunten te gebruiken. Dit komt omdat de curve alleen gegarandeerd door het eerste en het laatste controlepunt gaat, wat hogere-orde Beziers moeilijker vormgeefbaar maakt.

Grotere curves worden in plaats daarvan geconstrueerd door meerdere kubieke Bezier-segmenten aan elkaar te koppelen, waarbij de raaklijnen (tangenten) worden uitgelijnd om een gesegmenteerde curve te creëren die er vloeiend uitziet.

Dit is de kubieke Bezier-spline, zoals deze gewoonlijk wordt begrepen. Het precieze "pen-instrument" in de meeste tekentools bestaat dan ook uit het tekenen en bewerken van de controlepunten, in plaats van het direct tekenen van curves.

Een wijdverspreide leugen

Pen-tools hebben doorgaans een paar verschillende modi voor de controlepunten. Intuïtief vertegenwoordigen deze verschillende gradaties van vloeiendheid. Symmetrische tangenten worden aangeboden als de meest vloeiende optie, waarbij bepaalde kwaliteiten van vloeiendheid verloren gaan naarmate de beperkingen worden versoepeld.

In werkelijkheid is dit volledig onjuist, en dat is eenvoudig aan te tonen. Bezier-curves kunnen exact gesplitst worden door de nieuwe controlepunten af te lezen uit het interpolatiediagram. De linker- en rechtersegmenten zijn 100% identiek aan de oorspronkelijke curve en sluiten altijd perfect aan op de naad. Toch zullen de tangenten in het midden asymmetrisch zijn, behalve bij één specifieke splitsing nabij het midden. Dit kan worden bevestigd met behulp van een krommingskam (curvature comb), die de (inverse) krommingsstraal op elk punt weergeeft.

De krommingskam blijft continu, zonder sprongen. Dit betekent dat het wel of niet gelijk zijn van de lengte van aangrenzende tangenten (symmetrie) volledig irrelevant is. Proberen vloeiende en intuïtieve Bezier-curves op deze manier te tekenen is een zinloze opgave.

Een eenvoudige manier om dit te verbeteren is om de tangenten als relatief in plaats van absoluut te behandelen. We kunnen ze bijvoorbeeld proportioneel maken aan de afstand tussen het begin- en eindpunt van elk segment. Deze spline is gemakkelijker te bewerken, omdat de aangrenzende segmenten zich natuurlijk aanpassen wanneer je een curvepunt verplaatst. Er ontstaan zo veel minder knikken (cusps). Het bewerken van de tangenten blijft hetzelfde.

Als we echter opnieuw de kromming plotten, zien we dat dit geen ideale oplossing is. Het proportioneel schalen van tangenten garandeert niet dat de kromming behouden blijft tijdens het bewerken, noch blijft de kromming continu van het ene segment naar het volgende.

Dit laat ook zien dat het aanbieden van een krommingskam-visualisatie als "behulpzame tool" eigenlijk nogal wreed is: het aanpassen van de kromming aan de ene kant beïnvloedt ook de andere kant, waardoor herhaaldelijke aanpassingen heen en weer nodig zijn totdat het dicht genoeg bij het gewenste resultaat ligt.

Voorzichtig omgaan met handles

Een veel effectievere strategie is om direct met kromming (curvature) te werken. Hoewel dit in het algemeen een moeilijk probleem is, blijken er enkele verrassende relaties te zijn die we direct kunnen observeren.

Beschouw de kromming aan het begin van segment $A-B-C-D$. Deze wordt alleen beïnvloed door de posities van $A$, $B$ en $C$. Punt $D$ kan vrij worden bewogen als het is losgekoppeld van $C$. Bovendien, omdat de tangent $A-B$ horizontaal is, doet alleen de verticale positie van $C$ ertoe. Dit is een resultaat van de onderliggende lineaire interpolaties, die veel termen in de formules opheffen.

De kromming bij $A$ wordt dus alleen beïnvloed door de lengte van $A-B$ en de loodrechte afstand van $C$ tot $A-B$. Hetzelfde geldt voor $D$ aan de andere kant met $C-D$ en $B$.

Op zichzelf is dit niet erg nuttig. Wanneer we een curvepunt ($A$ of $D$) verplaatsen, wordt gewoonlijk het aangrenzende controlepunt ($B$ of $C$) ook verplaatst om de tangent te behouden. En wanneer we een symmetrische of asymmetrische tangent draaien, wordt de aangrenzende tangent in het volgende segment onder dezelfde hoek gedraaid, wat de kromming aan die zijde verandert.

Toch laat dit zien dat het behouden van de kromming geen krankzinnig idee is en simpelweg kan worden gedaan door de tangenten passend te schalen. De regels zouden eenvoudig zijn:

• Wanneer we een curvepunt verplaatsen, moeten we de start- en eindkromming in de aangrenzende segmenten behouden.
• Wanneer we een tangent draaien, moeten we de kromming aan het tegenovergestelde uiteinde van het huidige segment behouden, cũng als aan beide zijden van het aangrenzende segment.

Dit zou een bewerkingservaring moeten opleveren waarbij de curve daadwerkelijk je intentie respecteert. Behalve dat het niet helemaal zo werkt: het verplaatsen van curvepunten werkt geweldig, maar bij het draaien van een tangent is de lengte van die tangent op zichzelf een slechte weergave van de intentie van de gebruiker. Kleine wijzigingen kunnen enorme verschuivingen in kromming veroorzaken, waardoor de curve onverwacht kan springen of "exploderen" terwijl hij probeert een passende oplossing te vinden.

Daarom is het beter om te werken met krommings-handles, waarbij de lengte direct correspondeert met de kromming. In tegenstelling tot de krommingskam is de lengte van de handles de niet-geïnverteerde krommingsstraal, wat een natuurlijkere keuze is.

Deze handles zijn zeer stabiel en kunnen just-in-time worden omgezet in klassieke Bezier-controlepunten, zonder dat er heen-en-weer conversies tussen de twee representaties nodig zijn. Dit voorkomt bovendien numerieke drift.

De wiskundige oplossing (Goldilocks)

Om dit te realiseren moeten we de lengtes $l0$ en $l1$ van de tangenten berekenen, gegeven de gewenste krommingen $k0$ en $k1$, de start-/eindpunten $A$ en $D$, en de unit-length tangenten aan het begin en einde.

Gegeven een curve $\gamma(t)$, kunnen we de unit tangent vector $\mathbf{T}(t)$ uitdrukken als de genormaliseerde afgeleide:

$$ \mathbf{T}(t) = \frac{\gamma'(t)}{|\gamma'(t)|} $$

Dit kan worden gebruikt om de krommingsvector $\mathbf{K}(t)$ te vinden via twee vector-cross-producten met behulp van de eerste en tweede afgeleide:

$$ \mathbf{K}(t) = \mathbf{T}(t) \times \frac{\gamma''(t)}{|\gamma'(t)|^2} \times \mathbf{T}(t) $$

De cross-producten zorgen ervoor dat $\mathbf{K}(t)$ loodrecht staat op $\mathbf{T}(t)$; ze extraheren dus de normale vectorcomponent van de middelste term. Nu kunnen we oplossen voor $\mathbf{K}(0) = k0$ en $\mathbf{K}(1) = k1$.

Na het uitwerken van de wiskunde eindigen we met een kwadratisch stelsel vergelijkingen in $l0$ en $l1$:

$$ \begin{cases} a0 \cdot l0^2 + b \cdot l1 + c0 = 0 \\[0.3em] a1 \cdot l1^2 + b \cdot l0 + c1 = 0 \end{cases} $$

Waarbij:

$$ \begin{array}{lcl} a0 & = & \pm|k0| \\[0.3em] a1 & = & \pm|k1| \\[0.3em] b & = & 2 \cdot |\mathbf{T}(0) \times \mathbf{T}(1)| \\[0.3em] c0 & = & 6 \cdot |\mathbf{T}(0) \times (D - A)| \\[0.3em] c1 & = & 6 \cdot |\mathbf{T}(1) \times (A - D)| \\[0.3em] \end{array} $$

Dit bevat een aantal zaken:

1. Het teken van de kromming $k_i$ bepaalt of de curve met de klok mee of tegen de klok in draait. Bij het verplaatsen van curvepunten kan de curve gedwongen worden om te flippen, vandaar dat de $\pm$ noodzakelijk is, en beide tekens onafhankelijk kunnen veranderen.
2. De koppeling tussen $l0$ en $l1$ wordt alleen beïnvloed door $b$. Als $b = 0$, dan zijn de twee vergelijkingen onafhankelijk en is het probleem triviaal op te lossen. Dit komt overeen met de situatie waarin de twee tangenten parallel lopen.
3. De constante term $ci$ wordt alleen beïnvloed door de loodrechte afstand $D - A$ (of $A - D$) tot de tangent $\mathbf{Ti}$. Dit komt overeen met de eerdere bevinding dat alleen de loodrechte afstand de kromming beïnvloedt.

Hetzelfde probleem is dus gereduceerd tot het vinden van het snijpunt van twee dubbele parabolen, één horizontaal en één verticaal. De twee zijden van elke dubbele parabool vertegenwoordigen het buigen met of tegen de klok in. We moeten vier keer oplossen, één keer voor elke tekencombinatie $(+,+)$, $(+,-)$, $(-,+)$, $(-,-)$.

Om dit systeem op te lossen, kunnen we een van de vergelijkingen herschrijven om $l1$ of $l0$ te isoleren:

$$ l1 = \frac{-a0 \cdot l0^2 - c0}{b} \\[0.5em] l0 = \frac{-a1 \cdot l1^2 - c1}{b} $$

Kies er één en kwadrateer deze om hem in de andere oorspronkelijke vergelijking in te vullen als de $l1^2$ of $l0^2$ term. Dit produceert een kwartische vergelijking in de andere variabele (respectievelijk $l0$ of $l1$), die direct kan worden opgelost met de kwartische formule.

We kunnen vervolgens de andere $l_i$ berekenen, via:

$$ l1 = \sqrt{\frac{-b \cdot l0 - c1}{a1}} \\[0.5em] l0 = \sqrt{\frac{-b \cdot l1 - c0}{a0}} $$

Niet alle oplossingen van de kwartische vergelijking zullen echter daadwerkelijke oplossingen van het systeem zijn, vanwege het kwadrateren. We moeten dus dubbel controleren of de oorspronkelijke vergelijkingen kloppen voordat we een oplossing voor $(l0, l1)$ accepteren. Ook wijzen we oplossingen af waar $l0 < 0$ of $l1 < 0$, omdat deze situaties vertegenwoordigen waarin de tangenten met 180º zijn omgedraaid.

In de meeste gevallen is er slechts één geldige oplossing, en dit werkt vrij goed. Voor hoekpunten zijn één of beide $ki$'s oneindig. Dit is eenvoudig op te lossen, aangezien de bijbehorende $li$ nul is en de andere direct berekend kan worden.

Selectie en snapping (Grouper and Snapper)

Helaas, als er meerdere oplossingen zijn, vertegenwoordigt elk een andere curve. Het zou een zeer slechte bewerkingservaring zijn als de curve zou springen terwijl je hem bewerkt, maar er is geen voor de hand liggende manier om de juiste te kiezen.

Een strategie zou zijn om de vorige $l0$ en $l1$ te onthouden tijdens het bewerken, en de oplossing te kiezen die het dichtst bij de vorige curve ligt. Dit zou echter pad-afhankelijkheid introduceren, waarbij de volgorde en richting waarin je punten verplaatst beïnvloedt welke curve je uiteindelijk krijgt. Voor een tekentool is dit frustrerend en ongewenst.

Verschillende oplossingen van de vergelijking kunnen ook plotseling verschijnen en verdwijnen, dus dit zou het 'popping'-effect niet elimineren, maar slechts verminderen. Ideaal gezien zouden de resulterende krommingen zelf altijd vloeiend moeten veranderen. Dit kan worden bereikt door een passende weging-heuristiek voor de oplossingen te ontwerpen en hun gewogen gemiddelde te berekenen.

1. De verboden regio's: Wanneer een oplossing $l0 < 0$ of $l1 < 0$ nadert, staat hij op het punt te verdwijnen, dus moet het gewicht daar naar nul gaan.
2. Instabiele parabolen: Wanneer twee tegenovergesteld buigende parabolen elkaar bijna raken, zullen twee oplossingen naar elkaar toe bewegen, om vervolgens tegelijkertijd te verdwijnen. Deze oplossingen zijn instabiel en moeten worden vermeden. Om dit te detecteren, bereken ik de gradiëntvector van elke vergelijking:

$$ \mathbf{g0} = \begin{bmatrix}2 \cdot a0 \cdot l0 & b\end{bmatrix} \\[0.3em] \mathbf{g1} = \begin{bmatrix}b & 2 \cdot a1 \cdot l1\end{bmatrix} $$ De hoek tussen hen kan worden gevonden via hun dot-product, na deling door hun respectievelijke lengtes: $$ \cos \theta = \frac{\mathbf{g0} \cdot \mathbf{g1}}{|\mathbf{g0}||\mathbf{g1}|} $$ Een waarde dicht bij $-1$ betekent twee tegenovergesteld buigende parabolen, terwijl een waarde dicht bij $1$ twee uitgelijnde parabolen betekent. Die laatste is minder erg, omdat dit duidt op veel bijna-equivalente oplossingen.

1. Lussen voorkomen: Wanneer de krommingsstraal zeer groot is in vergelijking met de Bezier zelf, is een van de mogelijke oplossingen dat de curve zichzelf kruist en een lus vormt. Dit moet worden ontmoedigd. We kunnen delen door de lengte van $|\mathbf{l}|$ (i.e. $\sqrt{l0^2 + l1^2}$), waarbij we de voorkeur geven aan oplossingen met kortere tangenten.

Alles bij elkaar genomen is de gekozen weging-heuristiek:

$$ w{heuristic}(\mathbf{l}) = \left(\frac{l0 \cdot l_1 \cdot \arccos(-\cos \theta)}{|\mathbf{l}|^2}\right)^2 $$

• Door $\arccos(-\cos \theta)$ toe te passen, mappen we het dot-product bereik $(-1..1)$ naar $(0..\pi)$, wat de instabiele oplossingen effectief neutraliseert.
• Grote $|\mathbf{l}|$'s vertegenwoordigen ongewenste oplossingen en moeten sterk worden bestraft.
• Wanneer de gehele heuristiek naar $0$ nadert, moet de invloed vloeiend verdwijnen, vandaar het kwadrateren.

Door dit als gewicht te gebruiken, veranderen de resulterende Bezier-curves altijd vloeiend, zelfs wanneer het begin- en eindpunt worden verplaatst en door elkaar heen bewegen. Maar wanneer meerdere oplossingen samen worden gemiddeld, is het resulterende $(l0, l1)$ niet noodzakelijkerwijs een oplossing van het oorspronkelijke systeem. Dit betekent dat de resulterende krommingen niet altijd exact zijn, zelfs niet wanneer er een exacte oplossing in de buurt is.

Om dit te verzachten kunnen we een extra resampling-stap toevoegen, waarbij we de oplossingen opnieuw wegen op basis van de inverse afstand tot de macht 4 tot het gewogen gemiddelde:

$$ w{sample}(\mathbf{l}) = \frac{1}{|\mathbf{l} - \mathbf{l}{average}|^4} $$

Dit zorgt ervoor dat de oplossing vloeiend 'snapt' naar exacte oplossingen wanneer deze beschikbaar zijn.

Migratie van curves

Wat vooral prettig is aan deze aanpak is dat hij grotendeels in bestaande systemen kan worden geplaatst met minimale aanpassingen. De UI voor het aanpassen en bewerken van Bezier-handles kan behouden blijven, inclusief het concept van de vier punttypes. Alleen de betekenis van de lengtes van de tangenten verandert. Het omzetten van een asymmetrisch punt naar een symmetrisch punt zal nu daadwerkelijk de kromming van de linker- en rechterkant gelijkmaken, wat is wat de gebruiker eigenlijk wil.

De interne representatie kan grotendeels hetzelfde type blijven (een reeks punten), alleen vertegenwoordigen deze punten nu krommingstangenten in plaats van Bezier-tangenten. Hoewel het beter is om de unit length tangenten en krommingen direct expliciet op te slaan, wat numeriek stabieler is.

Het splitsen van een krommings-Bezier is veel eenvoudiger dan het splitsen van een klassieke Bezier, omdat de start- en eindhandles helemaal niet veranderen en de nieuw aangemaakte handles symmetrisch zijn.

Er is echter één resterende fout. Bij het splitsen van een curve met een S-bocht zijn de splitsingen nabij de bocht niet exact. De heuristiek kiest de verkeerde curve aan één of beide zijden. Dit kan worden opgelost door de specifieke oriëntatie van de kromming te onthouden en het teken van de kromming alleen te flippen wanneer dat nodig is. Dit introduceert echter enige minimale pad-afhankelijkheid in het bewerken.

Daarom zou je dit in de UI moeten presenteren als een extra oriëntatie-toggle voor ambigue controlepunten. Dit zou ook betekenen dat de interne representatie in tangent- en getekende-krommingsvorm moet zijn om volledig stabiel te zijn, en niet slechts in krommings-handles.

Nabij de S-bocht wordt de krommingsstraal — en dus de handle-grootte — effectief oneindig, omdat $|k|$ nul wordt. De Bezier-controlepunten liggen op een rechte lijn, aangezien de loodrechte afstand tot de tangent nul is. Zelfs wanneer dit exact wordt afgehandeld, kan dit nog steeds onpraktisch grote krommings-handles creëren. Misschien is er een vijfde "Inflection"-punttype nodig voor punten met exact nul $|k|$, hoewel dergelijke punten vaak zeer instabiel zijn en soms geen oplossing bestaat.

Om een klassieke Bezier te migreren naar een krommings-Bezier, kun je de unit tangenten en kromming aan het begin en einde meten. In de overgrote meerderheid van de gevallen resulteert dit in exact dezelfde curve. Als dat niet zo is, moet de oorspronkelijke Bezier worden gesplitst om ambiguïteit te voorkomen.

Voor complexe operaties op Bezier-curves, zoals booleaanse unies of intersecties, moeten deze nog steeds in Bezier-vorm worden uitgevoerd. Dit impliceert een zekere hoeveelheid round-tripping tussen de twee representaties, wat numerieke drift zou introduceren. Echter, alleen de nieuw aangemaakte punten hoeven te worden teruggeregeld, omdat de kromming en tangenten elders gelijk blijven.

***

Dit artikel begon bij de observatie dat "symmetrische" Bezier-tangenten niet daadwerkelijk symmetrisch zijn zoals je zou verwachten. Hopelijk vond je deze verkenning verhelderend.

De praktijk om krommingskammen te tonen om problemen met splines te diagnosticeren is eigenlijk omgekeerd. Als we een krommingskam kunnen tonen, kunnen we ook een passende spline berekenen die aan de gewenste kromming voldoet.

Beziers, zoals ze gewoonlijk bestaan, zijn dus vrij ontoereikend. We kunnen een beter systeem implementeren om ze te bewerken zonder de verwachtingen van een vloeiende bewerkingservaring te doorbreken, of een nieuwe klasse curves te introduceren die heel anders zich gedraagt.

De code voor de diagrammen en de implementatie is te vinden op GitLab.