Gemeinsame Algorithmus Frage

Question

Angenommen, wir haben einige Mesh (siehe das Bild von CorelDraw, die die gleiche Technik in "Mesh fill" Instrument) verwendet.

alt text http://www.sonic.net/mnitepub/pccafe/reviews/coreldraw9/meshfill.jpg

Offensichtlich ist diese Art von Gitter durch eine Reihe von Punkten dargestellt wird und Linien zwischen ihnen tatsächlich, dass die Menge von Punkten bestimmt unter Verwendung von (wahrscheinlich interpoliert irgendwie). Dieses Instrument hat auch Tasten , um die Netzauflösung zu erhöhen.

Meine Frage ist die folgende - wie werden solche Dinge berechnet? Angenommen, ich habe einige Punkte, die tatsächlich ein Netz darstellen (für den einfachen Fall nehmen wir sogar an, dass Punkte auf der "Grenze" statisch sind und sich nicht bewegen können). Und ich möchte die Mesh-Auflösung zum Beispiel in 4 mal erhöhen (so dass die Anzahl der Mesh-Punkte tatsächlich 4 * initial_points_count wird).

Wie sollte ich die Positionen neuer Punkte berechnen, wenn die einzigen Daten, die ich habe, diese Anfangspunktmatrix sind?

Die schnellste (sogar näherungsweise) Methode würde mir passen, aber ich weiß nicht, wo zu suchen oder wie solche Art von Algorithmus zu entwickeln.

Vielen Dank.

Answer 1

I durch Zugabe von halb Punkte auf allen Linien beginnen würde durch Interpolation (die Kurven in der Abbildung sind wahrscheinlich Bézier curves von irgendeiner Art, so würde ich sie als solche interpolieren, oder verwenden Sie biliniear Interpolation wie Mau vorgeschlagen) und neue Punkte auf halbem Weg zwischen den alten, die mir 3 Mal die Auflösung geben. Ich würde dann zwischen diesen neuen Punkten interpolieren (beide Wege, wenn Präzision der Schlüssel ist) und einen neuen Punkt an der Kreuzung (oder halbwegs) platzieren. Siehe "Abbildung" unten.

Initial state => Interpolate => Place points => Interpolate => Final state 
    x  x   x-------x  x x x   x x x  x x x 
        |  |        |  
        |  |  x  x   x---+---x  x x x 
        |  |        | 
    x  x   x-------x  x x x   x x x  x x x 

Answer 2

Klingt wie ein Job für Bilinear Interpolation (wo das Koordinatensystem auf der Kugeloberfläche ist).

Answer 3

Haben Sie sich subdivision angesehen? Sollte für das Verfeinern solcher Netze arbeiten.

Answer 4

Was Sie suchen, ist ein Mesh glatt Algorithmus. Leider habe ich keine Ressourcen zur Hand, daher kann ich nur vorschlagen, nach "Mesh Smoothing" zu googeln. Das ist ein riesiges Feld.

EDIT

Hier ist eine schöne, kurze, Roundup von ein paar Methoden/Algorithmen Netzglättung zu erreichen: http://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_surf3.pdf

Answer 5

Kommentare zu vorhandenen Antworten:

Es scheint mir, dass Mau und Antwort des martient mit polygon mesh eine Lösung für das Problem der Annäherung eine bekannte Form beschreiben (und Sie haben nicht eine bekannte Form) .

Algorithmus, den Dave erwähnt, würde jede Form glätten, aber nicht unbedingt in der beabsichtigten Weise.

Wenn Sie sich Ihre Antwort ansehen, werden Sie sehen, dass die neuen Punkte aus der linearen Interpolation zwischen den Punkten kommen, und wenn das gut genug für Sie ist, sind alle Lösungen vergleichbar (außer Daves).

Solch eine Erhöhung der Maschendichte wird nicht machen das resultierende Netz aussehen irgendwie 'netter' - mehr Ähnlichkeit mit der ursprünglichen Form. Wenn das nicht gut genug ist, müssen Sie zuerst entscheiden, was die tatsächliche Form/Form ist, die Sie mit dem Netz darstellen wollen (wenn Sie Ihr Beispiel erweitern könnten, wäre es vielleicht etwas offensichtlicher; erzeugt dieses Werkzeug nur Kreisnetze) oder es kann irgendeine Form annehmen und es "mesh füllen"?

Auch sollten Sie beachten, dass Sie nicht mit einem Polygonnetz arbeiten, sondern mit einem Netz von Kurven (wahrscheinlich bezier), was ein weiterer Grund ist, warum einige der Antworten nicht direkt auf Ihr Problem zutreffen.

EDIT: Nach genauerem Hinsehen auf, wie corel dies tut und unter der Annahme, dass Sie tatsächlich die Kurven kennen nicht nur die Punkte (!):

• Sie beginnen mit einem Satz von Kurven, und es scheint, für mich, dass Sie horizontale und vertikale Kurven haben mit
• zu beginnen Wenn Sie die Auflösung (zum Beispiel horizontale Auflösung) erhöhen möchten, könnten Sie zwei aufeinander folgende vertikale Kurven nehmen und jedes Segment der horizontalen Kurven, die sie durchlaufen bei Mitte Punkt damit erstellen ein eine Menge von Punkten, die die neue Kurve definieren; Sie könnten auch den Winkel interpoliert bei dem die Kurve

alt text http://img706.imageshack.us/img706/5693/path5818.png

Die oben (manuell gezeichnet) Bild versucht durch den Punkt der neuen Kurve Zugabe a) zu veranschaulichen zeigt (rot), die würden Sie auf diese Weise generieren. b) Zugabe des linear interpoliert Linienzug (blau), das Polygonnetz Ansatz geht mehr in Richtung (so können Sie beurteilen, ob das für Sie akzeptabel ist)

Hinweis: Je nach Algorithmus, für die Sie das Netz vorbereiten Sie können oder sollten möglicherweise keine Vorteile darin haben, die Netzlinien als Kurven zu betrachten (der Unterschied zwischen roten und blauen Lösungen kann für bestimmte Algorithmen vernachlässigbar und für andere wichtig sein). Wenn der Algorithmus einfach Punkte erwartet, sollten Sie sich auch ansehen, wie Sie Bezierkurven mit Punkten annähern (das Lesen durch this könnte helfen, obwohl Sie keine Pixelgenauigkeit benötigen).

Für höchste Präzision/beste Ergebnisse sollten Sie zunächst die Dichte der Kurven erhöhen und diese mit Linien annähern.