Hülle einer kalligrafischen Beziér-Kurve ermitteln

[Flocke]

Habe folgendes Problem:

Ich möchte eine kubische Beziér-Kurve (aka Spline) mit einer Art kalligrafischem Pinsel zeichnen. In diesem speziellen Fall hat der Pinsel die Form einer gekippten Ellipse, auf jeden Fall handelt es sich um eine konvexe Form, die auch über Beziérs angenähert werden könnte.

Jetzt kann ich mir natürlich eine Funktion ähnlich wie LineDDA schreiben, die die "Einzelpunkte" der Kurve durchgeht und dort jeweils den Pinselumriss zeichnet. Allerdings wäre das wohl nicht sonderlich performant und ein Metafile wäre dann riesig und nicht geräteunabhängig, da ich dafür ja eigentlich die Einzelpixel-Auflösung brauche.

Im Internet habe ich zu diesem Problem nichts gefunden.

Daher meine Frage, ob Jemand von euch sich bereits einmal mit dieser oder einer ähnlichen Frage beschäftigt hat und weiß, ob und wie man dieses Problem mathematisch lösen kann. Ideal wäre als Ergebnis eine neue, geschlossene Beziér-Kurve, deren Inneres die Hülle beschreibt, die durch den Pinsel entsteht.

Ich hoffe ihr versteht was ich meine. Hier mal ein ganz einfaches Beispiel mit Geraden:

Code:

Kurve     Pinsel    Ergebnis

          +---+     +----------+
------+   |   |     |          |
      |   +---+     +------+   |
      |                    |   |
      |                    |   |
                           +---+

Schon mal vielen Dank im voraus für eure Anregungen...

[negaH]

Ich würde es so anpacken:

Du erzeugst ein Canvas und zeichnest mit den Windows API Funktionen BeginPath(), EndPath() alle Zeichenausgaben auf. Du zeichnest also an deiner Spline mit FillEllipse() deine kalligraphische Figur. Mit ExtCreatePen() kannst du Stifte dafür erzeugen die beliebige Regionen -> hRgn als Grundlage ihrer Form besitzen. Eine solche Region kannst du aber auch aus einem Path erzeugen -> PathToRegion(), also alles was zwischen BeginPath() und EndPath() als Path gezeichnet wurde. So das Entscheidende ist es das du einen solchen Path in eine geschlossene Figur umwandeln kanst -> CloseFigure(), also die Hülle ermitteln. Den Path selber kannst du als Vektor betrachten und dementsprechend auch skalieren -> WiddenPath().

Wenn du diese Region -> PathToRegion() hast dann ist das eine Hülle die du nun direkt in deinem Metafile Canvas mit FillRgn() benutzen kannst. Der Brush der dafür benutzt wird kann wiederum ein Muster enthalten.

Edit:

wo ich's jetzt lese sehe ich das es wohl ein bischen verworren ist ;)

Also: Ziel ist es erstmal in einem temporären Canvas deine Figur zu zeichnen. Das dauert ja seine Zeit und produziert sehr große Datenmengen, da ja an jedem Slinepunkt zb. FillRect(), FillElipse() oä. aufgerufen wird. Vor dieser Zeichenoperation wird BeginPath() aufgerufen und nach dieser Zeichnung EndPath(). Das GDI hat nun alle deine Operationen in einem "Path" aufgezeichnet, sowas ähnliches wie in den Metafiles.
Nun wandeln wird die gezeichnete Figur, die ja viele Pixelüberschneidungen, quasi ein breiter gefüllter Strich darstellt, in eine Region um. EIne Region beschreibt dann nur noch die Hüllkurve deiner Zeichnung.

Diese Region-> hRgn wird nun als geschlossene Figur in dein Metafile gezeichnet, mit FillRgn() und wohl stinknormalem Brush -> TBrush.Style := bsSolid und .Color := clBlack.

Dein Metafile enthält dann nur die Vekrotdaten zu dieser Region = Hüllkurve.

ABER! vielleicht musst du es garnicht so umständlich anpacken ;)
Schau dir mal ExtCreatePen() genauer an. Er müsste PS_GEOMETRIC, aus einer Bitmap -> DibSection erzeugt sein die die Form und Größe deines kalligraphischen Stiftes aufweist und dann einfach die Spline mit diesem Stift zeichnen.

Gruß Hagen

[Flocke]

Danke für die Antwort.

Zu ExtCreatePen: ich sehe dort keine Möglichkeit, einen beliebig großen Pinsel zu erzeugen. Aus einer Region überhaupt nicht (laut MSDN) und aus einer DIB werden nur max. 8x8 Pixel genommen.

Mit der Zusammenfassung zu Pfaden werde ich mal ausprobieren.

Ich selbst hatte inzwischen angefangen, die Bernshtein-Polynome zu den Teilsegmenten (sowohl Pinsel als auch Pfad) abzuleiten und darüber jeweils Tangenten in Richtung des Pfades an den Pinsel zu legen (um dessen äußere Hülle in Bewegungsrichtung zu ermitteln). Ist allerdings mathematisch nicht ganz trivial...

[negaH]

Hi Volker,

auf einem TForm machst du zwei TImage -> TImage1 und TImage2 (256*256 Pixel) und eine TButton. In dessen OnClick nachfolgende Methode TForm1.Button1Click().

Wir können deine Spline selber als Region erstellen OHNE Umwege über den Path des GDIs.

DrawCubicCurve() ist hier aus dem Forum abgekupfert und wurde von mir erweiteret. Nun zeichnen wir entlang einer Spline mit einem eigenen Pen der aus einer selbstgewählten Region besteht.

Im Grunde kannst du den Parameter Canvas rausnehmen da dieser nur zur Visualisierung dient. Als Ergebnis steht in Data.Region eine komplexe Hüllkurve als Region die mit der Region Data.Pen entlang einer Spline gezeichnet wurde.

Wie immer alles quick&dirty und schönmachen musst du schon selber.

Wir geben dann in zwei TImage's das aus was wir a) stück für stück gezeichnet haben und b) die erzeugte Region. Damit wir sehen das diese erzeugte Region wirklich nur aus einer Hüllkurve besteht zeichne ich diese unausgefüllt in Rot.

CreateSplineRgn() wäre nun ein Vorschlag meinerseits für eine fertige Funktion.

Für den Source der Kubischen Spline bin ich nicht verantwortlich, den habe ich wie gesagt hier aus der DP, und stellt mitnichten das dar was ich sonst als guten Source bezeichnen würde, sorry also.
Ich meine auch das es bessere Spline Routinen gibt die die Schrittweite beim Zeichnen einer Spline exakt an die Pixelauflösung anpassen können. Aber egal, fürs erste reichte der Source aus.

Gruß Hagen

Delphi-Quellcode:

function DrawCubicCurve(Canvas: TCanvas; const Points: array of TPoint; Steps: Cardinal = 1): hRgn;
type
  PData = ^TData;
  TData = packed record
    Canvas: TCanvas;
    Region: hRgn;
    Pen: hRgn;
  end;

  function Interpolate(const p1, p2, p3, p4: TPoint; t: single): TPoint;

    function cubic(v1, v2, v3, v4, t: single): single;
    begin
      result:=v2+t*((-v1+v3)+t*((2*v1-2*v2+v3-v4)+t*(-v1+v2 - v3 + v4)));
    end;

  begin
    Result.x:=round(cubic(p1.x, p2.x, p3.x, p4.x, t));
    Result.y:=round(cubic(p1.y, p2.y, p3.y, p4.y, t));
  end;

  procedure MyDrawing(X,Y: Integer; Data: PData); stdcall;
  begin
    with Data^ do
    begin
      OffsetRgn(Pen, X, Y);
      FillRgn(Canvas.Handle, Pen, Canvas.Brush.Handle);
      CombineRgn(Region, Region, Pen, RGN_OR);
      OffsetRgn(Pen, -X, -Y);
    end;
  end;

var
  i, s: integer;
  p, p1, p2, p3, p4, e: TPoint;
  Data: TData;
begin
  Assert(Steps > 0);
  Result := 0;
  if Length(Points) < 2 then Exit;
  Data.Canvas := Canvas;
  Data.Region := CreateRectRgn(0,0,0,0);
//  Data.Pen := CreateRectRgn(-5, -10, +5, +10);

  Data.Pen := CreateEllipticRgn(-5, -20, +5, +20);

  e  := Points[0];
  p2 := Points[0];
  p3 := Points[0];
  p4 := Points[1];
  for I := 0 to High(Points)-1 do
  begin
    p1 := p2;
    p2 := p3;
    p3 := p4;
    if i+2 < Length(Points) then
      p4 := Points[i+2];
    for s := 1 to Steps do
    begin
      P := Interpolate(p1, p2, p3, p4, s / Steps);
      LineDDA(E.X, E.Y, P.X, P.Y, @MyDrawing, Integer(@Data));
      E := P;
    end;
  end;
  DeleteObject(Data.Pen);
  Result := Data.Region;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Bitmap: TBitmap;
  Region: hRgn;
begin
  Region := 0;
  Bitmap := TBitmap.Create;
  try
    Bitmap.Width := 256;
    Bitmap.Height := 256;
    Bitmap.Monochrome := True;
    with Bitmap.Canvas do
    begin
      Brush.Color := clBlack;
      Brush.Style := bsSolid;
      Pen.Style := psSolid;
      Pen.Width := 3;

      Region := DrawCubicCurve(Bitmap.Canvas, [Point(10, 50), Point(40, 50), Point(40, 90), Point(80, 50), Point(80, 50), Point(100, 150)], 100);
    end;
    Image1.Picture.Assign(Bitmap);

    with Image2, Canvas do
    begin
      Brush.Color := clWhite;
      FillRect(ClientRect);

      Brush.Color := clRed;
      FrameRgn(Handle, Region, Canvas.Brush.Handle, 1, 1);
    end;
  finally
    Bitmap.Free;
    DeleteObject(Region);
  end;
end;

Delphi-Quellcode:

function CreateSplineRgn(Pen: hRgn; const Points: array of TPoint; Steps: Cardinal = 1): hRgn;
type
  PData = ^TData;
  TData = packed record
    Region: hRgn;
    Pen: hRgn;
  end;

  function Interpolate(const p1, p2, p3, p4: TPoint; t: single): TPoint;

    function cubic(v1, v2, v3, v4, t: single): single;
    begin
      result:=v2+t*((-v1+v3)+t*((2*v1-2*v2+v3-v4)+t*(-v1+v2 - v3 + v4)));
    end;

  begin
    Result.x:=round(cubic(p1.x, p2.x, p3.x, p4.x, t));
    Result.y:=round(cubic(p1.y, p2.y, p3.y, p4.y, t));
  end;

  procedure MyDrawing(X,Y: Integer; Data: PData); stdcall;
  begin
    with Data^ do
    begin
      OffsetRgn(Pen, X, Y);
      CombineRgn(Region, Region, Pen, RGN_OR);
      OffsetRgn(Pen, -X, -Y);
    end;
  end;

var
  i, s: integer;
  p, p1, p2, p3, p4, e: TPoint;
  Data: TData;
begin
  Assert(Steps > 0);
  Assert(Pen <> 0);

  Result := 0;
  if (Length(Points) < 2) or (Pen = 0) or (Steps = 0) then Exit;

  Data.Region := CreateRectRgn(0,0,0,0);
  Data.Pen := Pen;

  e  := Points[0];
  p2 := Points[0];
  p3 := Points[0];
  p4 := Points[1];
  for I := 0 to High(Points)-1 do
  begin
    p1 := p2;
    p2 := p3;
    p3 := p4;
    if i+2 < Length(Points) then
      p4 := Points[i+2];
    for s := 1 to Steps do
    begin
      P := Interpolate(p1, p2, p3, p4, s / Steps);
      LineDDA(E.X, E.Y, P.X, P.Y, @MyDrawing, Integer(@Data));
      E := P;
    end;
  end;
  Result := Data.Region;
end;

[Flocke]

Hallo Hagen,

vielen Dank für deine Mühe, so weit funktioniert das Ganze (allerdings muss man wirklich die Interpolation noch anpassen). Für eine erste Darstellung reicht das auch.

Wie ich im ersten Beitrag schon schrieb, wäre mir eine rein mathematische Lösung natürlich lieber, da ich dadurch weiterhin mit "Kurven" arbeiten könnte - eine Region ist intern ja nur eine Liste von Vierecken. Aber für den Fall bleibt mir wohl nur der "harte" Weg über Ableitungen und Tangenten...

[negaH]

Zitat:

eine Region ist intern ja nur eine Liste von Vierecken.

da bin ich mir nicht ganz so sicher, ob dies so ist. Bei der Ausgabe der Daten zu einer Region werden zwar TRects benutzt aber das muß nicht heissen das es intern auch so ist.

Du könntest aber diese TRects zu einer Region als Inputdaten zur Ermittlung deiner Hüllkurve als Vektor benutzen.
Normalerweise müsste ja dann logisch betrachtet exakt die Eckpunkte dieser TRects diese Hüllkurve definieren, es kann ja garnicht anders sein.

Gruß Hagen

[kalmi01]

Hallo,

ich habe mal ein ähnliches Prob gehabt, welches ich so gelöst habe:

1.) Spline nach Casteljau (Hagen's "cubic") in 100 Punkte aufgelöst
2.) von den entstandenen Linien um halbe Stiftbreite senkrecht zur Linie
hoch gegangen.
3.) zwischen den benachbarten Linien-Senkrechten die Seitenhalbierende ermittelt
und ebenfalls um halbe Stiftbreite herausgezogen
4.) die beiden Hilfssenkrechten entfernt
5.) selbiges noch einmal nach Unten
Und schon hat man die Outline eines Splines.
Wenn Du jetzt noch die Lage der Elipse in die Stiftbreite einfliessen lässt und aus dem entstandenen Outlinepfad Splines generierst, hast Du was Du willst.

Habe den Source leider nur in Postscript und das in einer Art programmiert (Ideenschutz), das selbst ich nach ein paar Tagen nicht mehr wusste, was im Detail wo abgeht.
Jetzt nach 15 Jahren garnicht mehr dran zu denken, das nochmal auseinander zu dröseln.
Da wär ich mit "Neumachen" schneller.

[Flocke]

@Hagen: wie eine Region intern gespeichert wird weiß ich natürlich auch nicht.

Das "unschöne" beim Ergebnis von GetRegionData ist, dass es jeweils auf ganze Pixel gerundete Koordinaten sind und eben nicht mehr Kurven.


@Kalmi: meine "mathematische" Lösung wird ähnlich funktionieren:

Voraussetzungen:
- Ich gehe aus von einer Pinselform, die über eine konvexe geschlossene Beziér-Kurve definiert ist.
- Ich zerlege den Pfad in mehrer Einzelpfade (wenige müssten reichen, muss ich noch testen), wobei ich allerdings nicht in Linien sondern in kleinere Beziér-Kurven aufteile.

1. Für jeden Teilpfad A(BC)D (A=Startpunkt, B+C=Stützpunkte, D=Endpunkt) sind die Richtungen im Start- und Endpunkt gegeben durch die Strecken (AB) und (DC).

2. Zu jeder Richtung lege ich äußere Tangenten an die Pinselkurve und durch die Berührungspunkte habe ich jeweils den "Versatz" zum Pinselmittelpunkt. Dies sollte berechnungstechnisch einfach auf die Ermittlung der Nullstellen einer quadratischen Funktion hinauslaufen.

3. Daraus berechne ich zwei neue Beziér-Kurven, die die beiden Ränder der Kurvenlinie beschreiben.

4. An den Enden setze ich jeweils die durch die Berührungspunkte aus [2] definierten Halbformen des Pinsels an.

5. "Glatte" Teilsegmente kann man direkt verbinden, bei "spitzen" muss man außen wie an den Enden ebenfalls einen Teil der Pinselkurve einsetzen und innen den Schnittpunkt ermitteln.

[negaH]

Zitat:

@Hagen: wie eine Region intern gespeichert wird weiß ich natürlich auch nicht.

Das "unschöne" beim Ergebnis von GetRegionData ist, dass es jeweils auf ganze Pixel gerundete Koordinaten sind und eben nicht mehr Kurven.

Das ist mitnichten ein Problem. Du skalierst dann einfach schon vorher die Spline Vektoren auf eine Größe die eine ausreichende Genauigkeit in "Pixeln" ergibt. Die Umwandlung der TRect Koordinaten enthält dann ein Downscaling per DIvision um den gleichen Faktor des vorherigen Upscaling. Es entstehen Fließkommavektoren für Linien mit der gewählten Auflösung. EIn Faktor von 1000 im Upsclaing würde also Vektoren erzeugen mit 3 Nachkommastellen Genauigkeit. Die Genauigkeit die du damit theoretisch erzielen kannst ist 2^48/2^32 = 2^16 = 16 Bits geringer als mit Floats, das wären bei Floats gerademal 8 Prozent bessere Genauigkeit.

Ergo: kein reales Argument.
Aber! wenn du sagst ich möchte es mathematisch erlernen und wissen dann ist das ein unschlagbares Argument ;)

Gruß Hagen

[kalmi01]

Hallo Flocke,

Zitat:

3. Daraus berechne ich zwei neue Beziér-Kurven, die die beiden Ränder der Kurvenlinie beschreiben.

Das wird nicht gehen (ausreichen).
Die Outline eines Splines kannst Du nicht mit einem einzigen Spline definieren.
Bei einer gleichmässigen Strichstärke brauchst Du min. 2, max. 3 Splines für obere Outline, dito für die Untere, oder aber NURBS.
Bei einer variierenden Strichstärke werden es 4-6 Splines je Seite.

Wenn Du es mit weniger hinkriegst, bin ich an dem Ergebnis brennendst interessiert.
Würde mich interessieren, was ich bei meinen "Forschungen" übersehen habe.

Edit:
Als Alternative kannst Du den Spline in Kreisbögen wandeln.
Um einen Spline zu beschreiben, braucht man min. 1 Kreisbogen oder 1 Linie
und max. 16 Kreisbögen und 1 Linie.
Im Mittel komme ich mit 6 Kreisbögen aus (plus eventuell 1 Linie)