Die hypot-Funktion

Written by Stephan Michels on 8. Januar 2012. Posted in Cocoa, Computergrafik

In diversen Fällen ist mir aufgefallen, dass nur Wenige die Funktion hypot („euclidean distance function“) kennen. Mit dieser Funktionen lässt sich elegant der Abstand zwischen zwei Punkten berechnen anstatt die Quadratwurzel aus dem Abstandsquadrat zu berechnen, welcher über den Satz von Pythagoras berechnet wurde.

NSPoint p1, p2;
CGFloat dx = p2.x - p1.x;
CGFloat dy = p2.y - p1.y;

CGFloat length = sqrtf(dx * dx + dy * dy);

Der Abstand lässt sich leichter und wie ich finde weniger fehleranfällig wie folgt berechnen:

CGFloat length = hypotf(dx, dy);

In meinen Verständnis hatte ich immer angenommen, dass die Funktion schneller sein könnte. Und um dies zu überprüfen habe ich ein kleines Programm (git://gist.github.com/1579069.git) geschrieben. Ich musste allerdings feststellen, dass tatsächlich die Funktion hypot langsamer war. Da der Unterschied wie ich finde minimal ist, werde ich weiterhin die Funktion hypot bevorzugen.

Result 1273819835.661994 in 14.537325 seconds (Sqrt)

Result 1273819836.367576 in 19.332056 seconds (Hypot)

 

Teilkurven von Bezier-Splines

Written by Stephan Michels on 8. Januar 2012. Posted in Cocoa, Computergrafik

 

Ich hatte folgendes Problem: Ich hatte eine Kurve, dargestellt durch ein Bezier-Spline, an deren Enden jeweils ein Pfeil angezeigt werden sollte. Nun sollte aber die Kurve nicht jeweils um die Länge der Pfeilspitzen verlängert werden, sondern die Kurve sollte um die Länge der Spitzen verkürzt werden.

 

Als Beispiel wurde hier ein Bezier-Spline mit den beiden Knotenpunkten p1 und p4, sowie mit den Kontrollpunkten p2 und p3 dargestellt. Die Idee ist nun eine Teilkurve zu finden, welche von Start bis End geht.

Nun lassen sich Teile von Splines nicht einfach berechnen wie z.B. bei geraden Linien, weil Splines parametrisierte Kurven sind. Selbst die Länge von Bezier-Splines lässt sich nicht ohne weiteres berechnen. Bei der Suche nach einer Lösung bin auf den wundervollen Artikel „Adaptive Subdivision of Bezier Curves“ von Maxim Shemanarev gestoßen.

Dieser Artikel handelt hauptsächlich von der Berechnung der Länge von Bezier-Splines. Seine Lösung benutzt eine ganze besondere Eigenschaft von Bezier-Splines, bei der von Bezier-Splines zwei Bruchstücke einfach über Trigonometrie berechnen werden können.

In der Darstellung wird gezeigt, dass wir zwei neue Kurven erhalten mit jeweils p1 und p1234 bzw. p1234 und p4 als Knotenpunkte, sowie p12 und p123 bzw. p234 und p34 als Kontrollpunkte.

Mit Hilfe von Intervallschachtelung lassen sich nun die Bruchstücke immer weiter verkleinern. Dabei werden die Bruchstücke dahingehend unterschieden, ob sich die Bruchstücke in dem gewünschten Intervall befinden oder nicht.

Auch hier hab ich ein kleines Demo-Programm geschrieben, um den Algorithmus auszuprobieren. Der Algorithmus ist als Kategorie von NSBezierPath wegen der einfachen Wiederverwendbarkeit implementiert. Auch um die Kategorie universell zu gestalten, habe ich darauf geachtet, dass der Algorithmus mit Linien-Segmenten und auch mit unterbrochen Segmenten umgehen kann. Der Code ist wieder zu finden auf Github.

Blobular Nachbau

Written by Stephan Michels on 4. Januar 2012. Posted in Cocoa, Computergrafik

Vor einiger Zeit bin ich auf ein ganz interessantes Javascript Demo gestoßen. Und zwar geht es um die Darstellung von zwei Kreisen mit einer Kontaktfläche, ähnlich zu zwei Tropfen, welche sich durch die Oberflächenspannung bei geringer Distanz verbinden.

Um diese Grafik zu erzeugen wird mit Hilfe einer Probe Volumen, dessen Radius die Krümmung kontrolliert, die Kontaktfläche modelliert. Im folgenden Schema wird hoffentlich verdeutlich wie ich dabei vorgegangen bin.

Zuerst wird die Position der Probe Volumen (c1, c2) mit Hilfe der Positionen der Kreise (b1, b2) und der Radien (r1, r2) bestimmt. Dabei werden die Schnittpunkte der beiden Kreise durch die Positionen der Kreise der Radien und des Radius des Probevolumens (rp) bestimmt (grün dargestellt).

Der Radius der grünen Kreise ist dabei einmal r1+ rp und entsprechend für den anderen Kreis r2 + rp.

Wie die Schnittpunkte von zwei Kreisen berechnet werden wird ganz gut von dem Artikel „Intersection of two circles“ von Paul Bourke beschrieben.

Die Schnittpunkte bilden nun die Positionen der Probe-Volumen und mit den Winkeln zwischen Positionen der Kreise lassen sich die Winkel bestimmen, mit welchen die verschiedenen Bögen berechnet werden können.

Jetzt gibt es noch einen Spezialfall, wenn beide Kreise weiter voneinander entfernt sind, dann fangen die Probe-Volumen an sich zu überlappen. Als Folge erhalte ich nun zwei getrennte Flächen. Dabei bilden die beiden Schnittpunkte der Probe-Volumen (m1, m2) weitere Stützpunkte für die resultierenden Flächen.

Für Interessierte ist der Code zu finden auf Github. Die Kreise lassen sich per Maus verschieben und der Radius des Probe-Volumen lässt sich über das Menü steuern. Eine interessante Erweiterung für eine zukünftige Version wäre z.B. mehr als zwei Kreise zu haben.