mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Splinekurve mit Hardware berechnen


Autor: G. B. (geri)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen

Der Titel sagt schon alles. Kennt jemand von Euch Hardware, die in der
Lage ist die Geometrie einer Splinekurve (in der x-y-Ebene) zu
berechnen. Ich stelle mit vor, ich schreibe in ein Ram 10 Stützpunkte,
führe den Algorithmus aus und kann durch Übergabe des x-Wertes den
y-Wert auslesen. Die Berechnung des Splines sollte eben in 5us
erfolgen:)
Das ganze sollte auf ein single board computer board rauf passen:) und
noch von Hand lötbar sein - also minimale Pin-Abstände ähnlich einem
LPC2148.

Falls ihr langsamere Möglichkeiten kennt, dann bin aber auch daran
interessiert.

Beste Grüsse und vielen Dank für Eure Rückmeldung

Geri

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ähm, hab ich das richtig verstanden:

Du hast 10 Stützpunkte, an denen Du x/y Wertepaare vorgibst. Jetzt
möchtest Du zu beliebigen x Werten aus diesem Intervall y Werte mit
Splines interpolieren, und das innerhalb von 5us ?

Wie ist denn die Darstellung und Genauigkeit der x-Werte und y - Werte
(float, integer, wieviel Bit ?) und, sehr wichtig, welche Ordnung soll
Dein Spline denn haben ? Hast Du Platz und Zeit, um die
Polynomkoeffizienten der Splines vorzubereiten?

Fragen über Fragen
Cheers
Detlef

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kein Problem, nimm eine FPGA.

Autor: G. B. (geri)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Detlef

Vielen Dank für Deine Rückmeldung.

Ja, genau. Ich habe 10 Stützpunkte, Verfügbar hätte ich dazu noch die
Tangenten an den Stützpunkten, falls es der Sache dienen könnte.

Ja, die Werte sollen dann in dem Intervall liegen, in dem die
Stützpunkte vorkommen.

Die Berechnung der Kurve sollte in 5us erfolgen - falls halbwegs
einfach realisierbar.

Super wäre, wenn der Algorithmus mit Integer-Werten möglich wäre (32
Bit). Die Kurve könnte man zur Erhöhung der Genauigkeit auch skalieren.

Bzgl. Ordnung kann ich leider keine Aussage machen. Die Kurvenform ist
nicht allzu tragisch. Wichtig wäre, dass die Geschwindigkeit des
Algorithmus hoch ist.

Ich hoffe, es bringt mehr Licht in die Sache und vielen Dank für Deine
Mühe

Geri

Autor: G. B. (geri)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo  Unbekannter

Vielen Dank für Deinen Tipp. Diese Überlegung habe ich auch schon
angestellt. Wie würdest du hier aber bitte vorgehen? Algorithmus in c
entwicklen und dann auf einen FPGA flashen? Hast du hier einen
Favoriten als FPGA, bei dem du sagen würdest man kann es mit ihm
realisieren und man noch genügend freie Kapazität für weitere
Berchnungen hat? (Ich weiss, letztere Aussage ist nicht gerade
aufschlussreich, da ich aber keine Erfahrungen mit der
Leistungsfähigkeit von FPGAS habe kann ich nicht einschätzen welche
Funktionen man noch auf so ein Teil verlagern könnte:)

Beste Grüsse

Geri

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>  Die Kurvenform ist nicht allzu tragisch. <<

Dann nimm zum Interpolieren Geradenstücke oder allenfalls Parabeln, das
schafft im Zweifel so mancher uC, z.B. wahrscheinlich nen 20Mhz
getakteter AVR, der multiplizieren kann.

gute Nacht
Detlef

Autor: G. B. (geri)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Detlef

Vielen Dank für Deine Rückmeldung. Ja, ich möchte es schon gerne mit
einem Spline versuchen:) Mit nicht so tragisch wolle ich die
Möglichkeiten für schnelle Spline-Algorithmen nicht einschränken.


Beste Grüsse

Geri

Autor: Jinges (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Imho kommt es mit dem Aufwand auf den Grad (n) der ausgleichenden Spline
 und welchen Spline du benötigst:
- natürlicher Spline
- verallgemeinerter natürlicher kubische Spline
- vollständig kubischer Spline
- periodisch kubischer Spline
an.
Zu lösen sind dann je nach Anforderung 4n Gleichungen und 4n
Unbestimmte.

Autor: Läubi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schreib den Algorithmus doch erstmal als C Programm für den PC.
Dann kann man nämlich sehr einfach verschiedene Versionene gegeinader
vergleichen bezüglich Geschwindigkeit und Genauigkeit (stell aber am
besten das Optimierungslevel aus)

Autor: Karl heinz Buchegger (kbucheg)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und beschäftige dich erst mal mit Splines.
Das ist nämlich ein weites Feld:
Willst du
* Kubische Splines
* Bezier-Splines
* B-Splines
* ...

Den Spline gibt es nicht.

Autor: G. B. (geri)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Karl Heinz

Wie oben beschrieben ist der Typ des Splines nicht so wichtig bzw. ich
möchte hier Anfangs keine Einschränkungen und damit auch die
Lösungsmöglichkeiten einschränken.

Beste Grüsse

Geri

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Konkret: für nen spline dritter Ordnung muß Du nen kubisches Polynom
berechnen: a*x^3+b*x^2+c*x+d. Das sind ggf. 5 Multiplikationen und 4
Additionen. Die a,b,c,d sind spezifisch für das Intervall zwischen zwei
x-Werten und können offline vorberechnet werden. Bei Deinen 10
Stützstellen hast Du 9 Intervalle mit jeweils den 4 Koeffizienten. Dazu
muß Du noch feststellen, in welchen Deiner 9 Intervalle Dein x-Wert
fällt.

Bei 5us hast Du auf nem 20Mhz-AVR 100 ticks. Das kannst Du getrost
vergessen. Allenfalls lineare Interpolation könnte da mit 32 Bit
Rechnung bei hart quetschen vielleicht hinhauen.

Für nen halbwegs ernsthaften DSP ist das allerdings kein Problem, Deine
Rechenanforderung ist ca. nen MegaMAC, DSPs machen gerne auch nen
GigaMAC. Nen DSP ist allerdings nicht so schlicht zum Fliegen zu
bringen.

Cheers
Detlef

Autor: G. B. (geri)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Detlef

Vielen Dank für Deinen Lösungsweg. So etwas konstruktives gefällt mir!
Jinges hat mir den Aufwand auch schon angesprochen.

DSP klinkt auch sehr gut. Hast du schon mit einem leistungsfähigen DSP,
der im Hobbybereich bezahlbar und sinnvoll ist gearbeitet und falls ja,
bitte welchen?

Falls so ein Teil auch in C programmierbar ist, dann könnte ich sonst
auch die Sourcen erstellen, simulieren und gebe sie dann jemanden, der
ein Tool zum Compilieren hat und er mir dann ein Binärfile erstellt.

Eine meiner Meinung nach auch sehr interessante Veriante hat
"unbekannter" gebracht. Er schlägt einen FPGA vor. Ich habe gelesen,
es gäbe dafür bereits Ansi-C Compiler ..vielleicht auch eine Option...

Jedenfalls vielen Dank und beste Grüsse

Geri

Autor: Jens (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was Detlef schrieb, sind nur die Operationen, um den Spline an
Koordinate x auszuwerten. Nach deiner Beschreibung brauchst du aber die
Koeffizienten a,b,c,d innerhalb von 5us, was eine etwas aufwendigere
Rechnung ist.

Soweit ich mich erinnere, nimmt ein an einigen Stützpunkten befestigter
flexibler Stab die Form einer Splinekurve 3. Grades an. Wenn sich die
Koeffizienten langsam ändern und du trotzdem innerhalb einiger us das
Ergebnis brauchst, bietet sich folgende Lösung an: Nimm 10
Linearführungen (Nanoschrittmotoren), die die 10 Stützpunkte
nachfahren. Deren Enden verbindest du mit einem Metallstreifen.
Lasergesteuert kannst du die Position des Streifens an jeder Position
auslesen.

Autor: Karl heinz Buchegger (kbucheg)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Soweit ich mich erinnere, nimmt ein an einigen Stützpunkten
> befestigter flexibler Stab die Form einer Splinekurve 3.

Das glaube ich kaum :-)

Schon alleine deswegen, weil ich mit 10 Stützpunkten im
Stab 9 Wendepunkte erzeugen kann. Und ein Polynom 3. Grades
hat grade mal 1 Wendepunkt.
Aber ich weiss was du meinst: Du verwendest natürlich
mehrere Polynome 3. Grades, die aneinandergehängt werden.
Da hast du dann allerdings das Problem der Kontinuität. Das macht
das Erstellen der einzelnen Polynomstücke auch nicht grade einfacher.
(Ist aber auch noch keine Hexerei, wenn der µC schnell genug ist).

  0-Kontinuität: Die Splines stossen an den Punkten zusammen

  1-Kontinuität: stossen an den Punkten zusammen +
                 1. Ableitung sind gleich

  2-Kontinuität: stossen an den Punkten zusammen +
                 1. Ableitungen sind gleich +
                 2. Ableitungen sind gleich

Aber ansonsten: Ein Analogrechner. Ja, warum nicht!

Autor: G. B. (geri)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Jens

Vielen Dank für Deine Rückmeldung. Die Antwort von Detlef habe ich
schon verstanden. Die Koeffizienten liessen sich in meinem Fall offline
berechnen.

Wenn ich Deine zweite Passage richtig interpretiere...
Allg. schadet es nie, wenn man in der Phase der Ideengenerierung (vgl.
z.B. Systems Engineering:)) etwas optimistisch denkt und Ideen nicht
Überlegungen Anderer nicht im Vorfeld lächerlich macht.

Freundliche Grüsse

Geri

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>>DSP klinkt auch sehr gut. Hast du schon mit einem leistungsfähigen
DSP, der im Hobbybereich bezahlbar und sinnvoll ist gearbeitet und
falls ja, bitte welchen? <<

Nein, seit Jahren nicht mehr, dort habe ich keinen Überblick mehr. Aber
die Audio-freaks sind ja bei 96kHz Abtastrate, das ist von Deinen 200kHz
nur schlappe Faktor 2 weg. Da gibts bestimmt prima DSP evalboards die
200kHz können und sicher auch das MegaMAC schaffen, weil filtern und
damit multiplizieren wollen die Audiophilen ja auch.

Ne Nummer einfacher aber geeignet sind wahrscheinlich diese ARMs von
Philips oder auch Atmel, kenn ich aber auch nicht.

Das dritte, das ich nicht kenne, sind diese FPGA-evalboards.('Mit dem,
was du nicht weiß, könnte man ganze Bibliotheken füllen', ist aus
irgend nem Film) Die schaffen das von der Leistung sicher, wird aber
dauern wenn Du keine Erfahrung hast.

Autor: G. B. (geri)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Halloi Detlef

Vielen Dank für Deine Rückmeldung. Ich arbeite akutell mit einem ARM7
mit LPC2148. Gesehen habe ich aber auch bereits ARM9-Boards, die mit
200MHz getaktet sind und eine Menge Ram zur Verfügung stellen. Ich habe
ausserdem ein interessantes Board mit ARM9 und einem FPGA - names Cyclon
II - für ca. 220 Euro gefunden. Das scheint mit ein guter Preis zu
sein.

FPGA-Entwicklung habe ich mir schon mal etwas näher angesehen. Schön
wäre aber wenn sich so ein Teil in c programmieren liesse.

Jedenfalls nochmals vielen Dank und beste Grüsse

Geri

Autor: andi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Geri

wenn sich die 10 Stützpunkte nicht schnell ändern, kannst du die Spline
auch offline berechnen und eine Tabelle mit z.B. 1000 Stützpunkten
erzeugen. Dann sollte es reichen dazwischen linear zu interpolieren.

andi

Autor: G. B. (geri)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hall Andi

Es ist so, dass sich die gesamte Kurve, die zu beschreiben ist schnell
mal 5000 Knoten haben kann. Aus Gründend er Effizienz werden aber
vorausschauend immer nur 10 Punkte betrachtet und für ein Intervall
herangezogen.

Beste Grüsse

Geri

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.