|
|
| Autor |
Nachricht |
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
 Verfasst am: 23 Jun 2005 - 11:01:47 Titel: Kontrollpunktberechnung bei quadratischen/kubischen Beziers |
|
|
Jo'Grüzi !
Bin bei meiner Arbeit über Bezierkurven über zwei mir unvollständige Formeln gestoßen.
Beide berechnen anhand der Ankerpunkte (am Anfang und Ende der Kurve) und einem
bzw. zwei auf der Kurve aufliegenden Punkte den bzw. die Kontrollpunkte.
Erst einmal eine Crashkurs für quadratische Bezierberechnung. Eine Quadratische
Kurve berechnet sich durch die gemittelten Werte der 2 Ankerpunkte (Start-/Endpunkt
der Kurve) und des Kontrollpunktes. Jeder Punkt der Kurve ergibt sich in folgender Formel
so durch diese Punkte und den laufenden Parameter t E[0,1].
| Code: |
| LP = (1-t)^2 * SP + 2t * (1-t) * KP + t^2 * EP |
Wobei LP der Punkt auf der Kurve, SP der Startpunkt, KP der Kontrollpunkt und EP der Endpunkt sind.
Die kubische Kurve berechnet sich mit einem Kontrollpunkt mehr in folgender Formel:
| Code: |
| LP = SP * (1-t)^3 + KP1 * 3 * (1-t)^2 * t + KP2 * 3 * (1-t) * t^2 + EP * t^3 |
Soweit dazu, Ziel ist es jedoch nicht den Punkt auf der Kurve zu ermitteln sondern den Kontrollpunkt - wobei wir beim eigentlichen Problem sind.
| Code: |
| KP = (2 * LP) - 0.5 * (SP + EP) |
Das ist die Formel für die Berechnung des Kontrollpunktes in einer quadratischen Bezierkurve.
Funktioniert soweit auch sehr gut, solang LP (der Punkt auf der Kurve) genau bei t = 0.5 steht.
Vielleicht etwas ungünstig ausgedrückt, deshalb mal eine kleine Veranschaulichung:
http://www.shofeditz.de/testQuad.swf
Hier könnt Ihr die quadratische Kurve anhand Ihrer Ankerpunkte, des Kontrollpunktes und
des Punktes auf der Kurve bearbeiten, jedoch nur solange dieser auf t = 0.5 liegt. Die Position
des Punktes ist durch die untere Leiste veränderbar.
Im Grunde gilt das gleiche für die kubische Kurve. Unterschied ist nur, dass es 2 Kontrollpunkte und auch 2 Punkte auf der Kurve gibt. Formel:
| Code: |
| KP1 = -(10 * SP - 3 * EP - 8 * (3 * LP1 - LP2)) / 9 |
| Code: |
| KP2 = (3 * SP - 10 * EP - 8 * LP1 + 24 * LP2) / 9 |
Hierbei klappt die Berechnung beider Kontrollpunkte auh nur wenn LP1 bei t=0.25 und LP2 bei t=0.75 steht.
Nun zu meiner Frage - oder eher Bitte : Wie kann ich unter einbeziehung des Parameters t
in obigen genannter Formel den Kontrollpunkt auch bei anderen Werten von t berechnen?
Bin auf eure Antworten sehr gespannt!
MfG sHo
PS.: Fairerweise sollte gesagt sein, ich nicht die große Leuchte in Mathe bin, also bitte langsam sprechen.  |
|
 |
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 23 Jun 2005 - 19:39:00 Titel: |
|
|
Weiß denn niemand einen Rat ?
Vielleicht kennt jemand den Ursprung der Formeln oder einen Tipp ?
MfG sHo |
|
|
the4
Newbie
Anmeldungsdatum: 27.05.2005
Beiträge: 15
|
| Verfasst am: 24 Jun 2005 - 11:04:13 Titel: Allgemein zu B-Splines |
|
|
Hi,
ich habe keine lust mich durch dein gesabbel durchzuarbeiten , aber ganz allgemein:
wenn man eine B-Spline Basis waehlt und und Kontrollpunkte, so ist dadurch eindeutig ein Spline gegeben. Und es gibt berechnungsvorschriften wie man an bestimmte Punkte zu einem bestimmten Parameter kommt. (Vorteil dieser Polynombasis, die Basisfunktionen haben kleinen traeger nicht wie die Monombasis)
Wenn ich dein Problem richtig verstanden habe willst du eine B-Spline Interpolation machen. Oder genauer die Formel der B-Spline Interpolation herleiten. Dies geht prinzipiell so, dass man die oben beschriebenen Vorschriften von hinten nach vorne ausrechnet. (nicht ganz so schwierig aber viel rechnerei) Und da es das schon 1000mal gibt wuerde ich mal nach kubischer/quad. B-Spline Interpolation googlen.
MfG 4
_________________
CU 4 |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 24 Jun 2005 - 13:00:27 Titel: |
|
|
Heya!
Zitat: "Wenn ich dein Problem richtig verstanden habe willst du eine B-Spline Interpolation machen." - google schon seit Tagen aber finde anscheinden nicht das richtige - B-Spline Interpolation bedeutet doch nicht viel mehr als die Kurve (oder besser die Punkte der Kurve) anhand der Anker- und Kontrollpunkte zu berechnen nicht wahr? Mein Anliegen ist jedoch die Kontrollpunkte anhand der Kurve zu berechnen. Mein Beispiel von oben sollte es an einem quadratischen Bezier veranschaulichen. Das Bsp. funktioniert auch soweit, leider aber nur wenn der Punkt auf der Kurve in der Mitte dieser sitzt (t=0.5). Bei der kubischen Kurve funktioniert es mit der anderen Formel (s.O.) auch, aber nur wenn der erste Punkt im 1/4 (t=0.25) und der zweite im 3/4 (t=0.75) der Kurve liegt. Wenn man den Parameter t - welcher mir ja gegeben ist - in obige Formeln einbauen könnte würde ich bei meiner Arbeit ein ganzes Stück vorran kommen - denn ich häng zZ. daran echt fest!
Danke aber für deine Antwort!
MfG sHo |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 26 Jun 2005 - 20:48:29 Titel: |
|
|
| Scheint so als könnt ich das abschreiben was? Na wem noch was einfällt unten is noch Platz. Chiao |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 26 Jun 2005 - 21:10:23 Titel: |
|
|
Bedenke: Leute, die auf deine Frage eine Antwort geben können wissen, was eine Bezier-Kurve ist. Denen brauchst Du die nicht beschreiben. Anstatt dessen solltest Du mehr Arbeit in die Beschreibung deines Problems aufwenden 
| Zitat: |
| in obigen genannter Formel den Kontrollpunkt auch bei anderen |
Den Kontrolpunkt gibt es ja nicht auf einer kubischen Bezierkurve. Formuliere bitte deine Aufgabenstellung präziser. Etwa
Gegeben ist: ...
Gesucht ist: ...
Z.B. Gegeben sind 3 Kontrolpunkte (zwei Anker und noch einer) und ein Punkt durch den die Kurve laufen soll. Bestimme den dritten KP, wenn es geht.
Wenn ich Zeit finde, mache ich was dann. So sehe ich nicht, was zu tun ist. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 27 Jun 2005 - 11:43:04 Titel: |
|
|
Hi Algebrafreak!
Hast vollkommen Recht! Bin bei der Beschreibung des wesentlichen wohl bisschen vom Thema abgewichen. Ich werd versuchen es deutlicher zu Bescheiben.
Gegeben sind mir in der quadratischen Kurve die beiden Ankerpunkte A,C am jeweiligen Anfang und Ende der Kurve, ein Punkt auf der Kurve D (bei T) und dadurch auch T. Berechnet werden soll der Kontrollpunkt B.
Ich habe schon eine Formel, die mir den Kontrollpunkt B schon berechnet, leider aber nur solange T = 0.5 und der punkt auf der Kurve D bei T = 0.5 steht. So ist es auch in diesem Beispiel [ http://www.shofeditz.de/testQuad.swf ] (Flash) veranschaulicht.
Darin wird beim verschieben des Punktes auf der Kurve D der Kontrollpunkt und die Kurve korrekt berechnet, solang man T (unterer schieberegler) bei 0.5 belässt.
Hier die Formel zur quadratischen Kurve :
| Code: |
| B = (2 * D) - 0.5 * (A + C) |
Vielleicht hilft euch die Formel etwas - mir leider nicht.
Genauso versuche ich diese Problematik bei einer kubischen Kurve zu lösen. Dabei sind mir die beiden Ankerpunkte A,D am jeweiligen Anfang und Ende der Kurve, zwei punkte auf der Kurve E,F und die zu den Punkten gehörenden T-Parameter TE und TF gegeben. Berechnet werden sollen jetzt aber die beiden Kontrollpunkte B und C.
Formel hab ich dazu auch schon, nur leider wieder mit dem Problem, dass diese nur bei TE = 0.25 und TF = 0.75 korrekt funktioniert.
Hier die Formeln zur kubischen Kurve:
| Code: |
B = -(10 * A - 3 * D - 8 * (3 * E - F)) / 9
C = (3 * A - 10 * D - 8 * E + 24 * F) / 9 |
Hoffe das jetzt etwas verständlicher ausgedrückt zu haben ..
Freu mich schon auf deine Antwort!
MfG sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 27 Jun 2005 - 13:45:06 Titel: |
|
|
Deine Kurve wird durch die Gleichung
x = x_0(1-u)^2 + x_1 2u(1-u) + x_2 u^2
y = y_0(1-u)^2 + y_1 2u(1-u) + y_2 u^2
beschrieben. Dabei sind x_0,y_0,x_3 und y_3 bekannt. Gesucht ist x_1 und y_1. Da die Kurve in x_1 und y_1 in beiden Anteilen linear ist, reicht es
x_1 = (x - x_0(1-u)^2 - x_2 u^2)/(2u(1-u))
y_1 = (y - y_0(1-u)^2 - y_2 u^2)/(2u(1-u))
zu berechnen. Dazu fehlt offensichtlich ein beliebiger (von den beiden Ankern verschiedener) Punkt auf der Kurve und der entsprechende Wert von u. Dann ist der Kontrollpunkt immer vorhanden.
Für u = 1/2 gibt es anscheinend für den "Mittelpunkt" der Kurve eine Formel, sodaß man beide fehlenden Werte einsetzen kann. Für den allgemeinen Ansatz reicht es nicht aus die 2 Ankerpunkte zu wissen. Bei einer kubischen Kurve ist es analog. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 27 Jun 2005 - 15:23:25 Titel: |
|
|
Oh das schaut doch schon sehr vielversprechend aus!
Neben x_0, y_0 (bei mir A) und x_3, y_3 (bei mir C) ist auch noch x,y (bei mir D) und u (bei mir t) bekannt. Somit sollte es mit deiner Formel berechenbar sein.
Ich probiers gleich mal aus!
Kannst du mir bitte noch die Formel für die kubische Kurve aufschreiben?
Danke schonmal!
MfG sHo |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 27 Jun 2005 - 15:52:42 Titel: |
|
|
Klappt super deine Formel !
Hab das Flash-Beispiel damit aktualisiert und jetzt funktionierts.
MfG sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 27 Jun 2005 - 19:35:16 Titel: |
|
|
Für kubische geht es analog:
x_2 = (x-x_0 (1-u)^3-x_1 3u(1-u)^2-x_3 u^3)/(3u^2(1-u))
y_2 = (y-y_0 (1-u)^3-y_1 3u(1-u)^2-y_3 u^3)/(3u^2(1-u))
Wenn Du beide Kontrollpunkte rauskriegen willst anhand zweier Punkte, (und u's) die Gegeben sind, so wird es auf ein lineares Gleichungssystem hinauslaufen. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 27 Jun 2005 - 22:09:48 Titel: |
|
|
Wenn ich das richtig verstehe, berechnet das nur einen von zwei in der kubischen Kurve vorhandenen Kontrollpunkte. Mit deinem letzten Satzkann ich leider nicht viel anfangen, kannst du es vielleicht genauer ausdrücken?
Ich bezweifle, das sich beide Kontrollpunkte durch zwei Ankerpunkte und nur einen Punkt auf der Kurve definieren lassen. Jetzt wird das ganze auch etwas schwieriger als mit der quadratischen Kurve. Ist es aber möglich die beiden Kontrollpunkte anhand der beiden Ankerpunkte und zwei Punkten auf der Kurve zu berechnen?
Vielen Dank
sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 27 Jun 2005 - 22:26:19 Titel: |
|
|
Ja das geht, wie ich es oben bereits erwähnt habe Die kubische Kurve ist definiert durch
x = x_0 (1-u)^3 + x_1 3u(1-u)^2 + x_2 3u^2(1-u) + x_3 u^3
y = y_0 (1-u)^3 + y_1 3u(1-u)^2 + y_2 3u^2(1-u) + y_3 u^3
Gegeben sind zwei paare (x,y,u) und (x',y',u') von (verschiedenen) Punkten auf der Kurve und entsprechende u-Werte. Gesucht sind dann x_1,x_2,y_1,y_2. Es ergibt sich durch Einsetzen das folgende LGS
x = x_0 (1-u)^3 + x_1 3u(1-u)^2 + x_2 3u^2(1-u) + x_3 u^3
y = y_0 (1-u)^3 + y_1 3u(1-u)^2 + y_2 3u^2(1-u) + y_3 u^3
x' = x_0 (1-u')^3 + x_1 3u'(1-u')^2 + x_2 3u'^2(1-u') + x_3 u'^3
y' = y_0 (1-u')^3 + y_1 3u'(1-u')^2 + y_2 3u'^2(1-u') + y_3 u'^3
Umordnen nach unbekannten ergibt
x_1 [3u(1-u)^2] + x_2 [3u^2(1-u)] = x - x_0 (1-u)^3 - x_3 u^3
y_1 [3u(1-u)^2] + y_2 [3u^2(1-u)] = y - y_0 (1-u)^3 - y_3 u^3
x_1 [3u'(1-u')^2] + x_2 [3u'^2(1-u')] = x' - x_0 (1-u')^3 - x_3 u'^3
y_1 [3u'(1-u')^2] + y_2 [3u'^2(1-u')] = y' - y_0 (1-u')^3 - y_3 u'^3
Eingeben in ein CAS ergibt:
| Code: |
>> solve({eq1,eq2,eq3,eq4},{x_1,x_2,y_1,y_2});
/ { -- 2 3 2 3 2 3
piecewise| { | x_1 = (u1 x - u1 x + u x_0 - u x_0 - u xs + u xs -
\ { --
2 3 2 2 3
u1 x_0 + u1 x_0 + 3 u u1 x_0 - 3 u u1 x_0 - 3 u u1 x_0 +
3 2 3 3 2 2 3 3 2
3 u u1 x_0 + 2 u u1 x_0 - 2 u u1 x_0 + u u1 x_3 - u u1 x_3) /
2 2 3 3 2 3 3 2
(3 u u1 - 3 u u1 - 3 u u1 + 3 u u1 + 3 u u1 - 3 u u1 ),
2 3 2 3 2 3
x_2 = - (- 2 u1 x + u1 x - 2 u x_0 + u x_0 + 2 u xs - u xs +
2 3 2
2 u1 x_0 - u1 x_0 + u1 x + u x_0 - u xs - u1 x_0 - 3 u u1 x_0 +
2 3 3 3 3
3 u u1 x_0 + 2 u u1 x_0 - 2 u u1 x_0 + u u1 x_3 - u u1 x_3 -
2 3 3 2 2 3 3 2
u u1 x_0 + u u1 x_0 - 2 u u1 x_3 + 2 u u1 x_3) /
2 2 3 3 2 3 3 2
(3 u u1 - 3 u u1 - 3 u u1 + 3 u u1 + 3 u u1 - 3 u u1 ),
2 3 2 3 2 3 2
y_1 = (u1 y - u1 y + u y_0 - u y_0 - u ys + u ys - u1 y_0 +
3 2 2 3 3
u1 y_0 + 3 u u1 y_0 - 3 u u1 y_0 - 3 u u1 y_0 + 3 u u1 y_0 +
2 3 3 2 2 3 3 2
2 u u1 y_0 - 2 u u1 y_0 + u u1 y_3 - u u1 y_3) /
2 2 3 3 2 3 3 2
(3 u u1 - 3 u u1 - 3 u u1 + 3 u u1 + 3 u u1 - 3 u u1 ),
2 3 2 3 2 3
y_2 = - (- 2 u1 y + u1 y - 2 u y_0 + u y_0 + 2 u ys - u ys +
2 3 2
2 u1 y_0 - u1 y_0 + u1 y + u y_0 - u ys - u1 y_0 - 3 u u1 y_0 +
2 3 3 3 3
3 u u1 y_0 + 2 u u1 y_0 - 2 u u1 y_0 + u u1 y_3 - u u1 y_3 -
2 3 3 2 2 3 3 2
u u1 y_0 + u u1 y_0 - 2 u u1 y_3 + 2 u u1 y_3) /
2 2 3 3 2 3 3 2 -- }
(3 u u1 - 3 u u1 - 3 u u1 + 3 u u1 + 3 u u1 - 3 u u1 ) | } if
-- }
2 2 3
- 3 u u1 + 3 u u1 - 3 u1 + 3 u1 <> 0 and u in C_ minus {0, 1},
{ -- 2 3 2 3
{ | x_1 = (x - x_0 - 3 u1 x_0 + u1 x_0 - 3 u1 x_2 + 3 u1 x_2 -
{ --
3 2 3
u1 x_3 + 3 u1 x_0) / (3 u1 - 6 u1 + 3 u1 ),
2 3 2 3
y_1 = - (y_0 - ys + 3 u1 y_0 - u1 y_0 + 3 u1 y_2 - 3 u1 y_2 +
3 2 3 -- }
u1 y_3 - 3 u1 y_0) / (3 u1 - 6 u1 + 3 u1 ) | } if
-- }
2 2 3
- 3 u u1 + 3 u u1 - 3 u1 + 3 u1 = 0 and x - xs = 0 and
y - ys = 0 and u1 <> 0 and u1 <> 1, {} if
2 2 3
(- x + xs <> 0 or y - ys <> 0) and - 3 u u1 + 3 u u1 - 3 u1 + 3 u1 =
\
0 |
/
>>
|
Dabei ist xs = x', ys = y', u1 = u'. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 27 Jun 2005 - 23:22:07 Titel: |
|
|
Ach du heilige Wildsau !
Hab mir zwar gedacht, dass es mit mehr Komponenten etwas größer wird, aber SO groß ?! Aber da kann man garantiert noch was dran machen was ?! 
Hab die Ausgabe deines CAS mal überflogen. Ich kenn mich nicht mit deinem CAS aus, aber kann es sein, dass es die Bedingungen zu den jeweiligen Berechnung nach den Berechnungen schreibt ?
MfG sHo
PS.: Kannst du mir sagen was "u in C_ minus {0, 1}" in der ersten Bedingung zu bedeuten hat? |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 27 Jun 2005 - 23:33:53 Titel: |
|
|
Ja genau. Ich drösle das mal ein wenig auf
Für den Fall, daß
| Code: |
2 2 3
- 3 u u1 + 3 u u1 - 3 u1 + 3 u1 <> 0 and u in C_ minus {0, 1},
|
C_ bedeutet u ist komplex ohne der 0 und der 1, aber das habe ich ja bereits vorausgesetzt, indem ich gesagt habe, daß die Punkte keine Ankerpunkte sein dürfen. In diesem Fall ergibt sich für die Werte:
Wert von x_1
| Code: |
/ { -- 2 3 2 3 2 3
piecewise| { | x_1 = (u1 x - u1 x + u x_0 - u x_0 - u xs + u xs -
\ { --
2 3 2 2 3
u1 x_0 + u1 x_0 + 3 u u1 x_0 - 3 u u1 x_0 - 3 u u1 x_0 +
3 2 3 3 2 2 3 3 2
3 u u1 x_0 + 2 u u1 x_0 - 2 u u1 x_0 + u u1 x_3 - u u1 x_3) /
2 2 3 3 2 3 3 2
(3 u u1 - 3 u u1 - 3 u u1 + 3 u u1 + 3 u u1 - 3 u u1 ),
|
Wert von x2:
| Code: |
2 3 2 3 2 3
x_2 = - (- 2 u1 x + u1 x - 2 u x_0 + u x_0 + 2 u xs - u xs +
2 3 2
2 u1 x_0 - u1 x_0 + u1 x + u x_0 - u xs - u1 x_0 - 3 u u1 x_0 +
2 3 3 3 3
3 u u1 x_0 + 2 u u1 x_0 - 2 u u1 x_0 + u u1 x_3 - u u1 x_3 -
2 3 3 2 2 3 3 2
u u1 x_0 + u u1 x_0 - 2 u u1 x_3 + 2 u u1 x_3) /
2 2 3 3 2 3 3 2
(3 u u1 - 3 u u1 - 3 u u1 + 3 u u1 + 3 u u1 - 3 u u1 ),
|
Wert von y_1
| Code: |
2 3 2 3 2 3 2
y_1 = (u1 y - u1 y + u y_0 - u y_0 - u ys + u ys - u1 y_0 +
3 2 2 3 3
u1 y_0 + 3 u u1 y_0 - 3 u u1 y_0 - 3 u u1 y_0 + 3 u u1 y_0 +
2 3 3 2 2 3 3 2
2 u u1 y_0 - 2 u u1 y_0 + u u1 y_3 - u u1 y_3) /
2 2 3 3 2 3 3 2
(3 u u1 - 3 u u1 - 3 u u1 + 3 u u1 + 3 u u1 - 3 u u1 ),
|
Wert von y2
| Code: |
2 3 2 3 2 3
y_2 = - (- 2 u1 y + u1 y - 2 u y_0 + u y_0 + 2 u ys - u ys +
2 3 2
2 u1 y_0 - u1 y_0 + u1 y + u y_0 - u ys - u1 y_0 - 3 u u1 y_0 +
2 3 3 3 3
3 u u1 y_0 + 2 u u1 y_0 - 2 u u1 y_0 + u u1 y_3 - u u1 y_3 -
2 3 3 2 2 3 3 2
u u1 y_0 + u u1 y_0 - 2 u u1 y_3 + 2 u u1 y_3) /
2 2 3 3 2 3 3 2 -- }
(3 u u1 - 3 u u1 - 3 u u1 + 3 u u1 + 3 u u1 - 3 u u1 ) | } if
-- }
|
Diesen, sowie den letzten Fall habe ich ausgeschlossen indem ich gesagt habe, daß die zwei Punkte verschieden sind.
| Code: |
2 2 3
- 3 u u1 + 3 u u1 - 3 u1 + 3 u1 = 0 and x - xs = 0 and
y - ys = 0 and u1 <> 0 and u1 <> 1
|
usw.
D.h. für Dich ist nur der Fall 1 relevant (oben). Der Nenner wird bei allen Lösungen wohl gleich sein (da es sich wohl um die Determinantenlösung handelt) und hoffentlich ungleich 0. Daher ist es sinnvoll den Nenner zuerst zu berechnen und dann einfach dadurch teilen. Mach mal eine ASSERTION für den Nenner = 0 und sag mir, wenn's vorkommt. Dann überlege ich mir was das bedeutet
Laut CAS gilt das für den Fall, daß die Punkte verschieden sind aber der Nenner gleich 0 ist (allerletzter case). Dann gibt es keine Lösung. Ich glaube aber, daß es eine geometrische Bedeutung hat. |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 27 Jun 2005 - 23:39:43 Titel: |
|
|
| Zitat: |
| Hab mir zwar gedacht, dass es mit mehr Komponenten etwas größer wird, aber SO groß ?! |
Ich glaube der Wachstum ist exponentiell |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 28 Jun 2005 - 00:07:25 Titel: |
|
|
| Ich glaube Du hast meine Warnung von oben nicht ganz ernstgenommen. Sowohl für den quadratischen als auch für den kubischen Fall dürfen die Punkte auf keinen Fall mit den Ankern übereinstimmen und gleich sein! Sonst passiert was ähnliches, wie jetzt in deinem Programm, wenn man mit u nach ganz rechts (1) oder ganz links (0) geht und dann versucht den Punkt zu bewegen |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 28 Jun 2005 - 22:58:08 Titel: |
|
|
| Hat's funktioniert? |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 29 Jun 2005 - 13:56:29 Titel: |
|
|
Sorry ich musst erst einmal das Wetter nutzen  .. aber jetz kanns weiter gehen! 
| Zitat: |
| Ich glaube der Wachstum ist exponentiell |
Gut, dass das Optimum zwischen Flexibilität und Rechenaufwand der Freiformkurven bei der kubischen liegt ..
Dass einer der Punkte auf der Linie (oder beide) nicht gleich den Ankerpunkten (u > 0 && u < 1) sein dürfen ist klar. Wär aber auch unlogisch sowas zu berechnen .. daher hab ich das von vorn herrein auch ausgeschlossen. Genauso wie die beiden Punkte nicht an gleicher Position (u <> u') der Kurve liegen dürfen.
Ich habe deine Formeln mal etwas übersichtlicher aufgeschrieben.
nenner = -3 * (-1 + u) * u * (u - u1) * (-1 + u1) * u1
p1 = (ps * (u - 1) * u^2 + u1^2 * (p - p * u1 + p3 * u^2 * (-u + u1)) - p0 * (u - 1) * (u1 - 1) * (u1^2 - 2 * u * u1^2 + u^2 * (2 * u1 - 1))) / nenner
p2 = (ps * (u - 1)^2 * u - p0 * (u - 1)^2 * (u - u1) * (u1 - 1)^2 - u1 * (p * (u1 - 1)^2 + p3 * u * (u1^2 - 2 * u * u1^2 + u^2 * (2 * u1 - 1)))) / nenner
wobei ich deine bezeichungen verallgemeinert habe.
p0 = x_0, y_0
p1 = x_1, y_1
p2 = x_2, y_2
p3 = x_3, y_3
p = x , y
ps = xs , ys
Eine kleine Assertion hab ich auch mal gemacht, mit dem Ergebniss: Der Nenner wird nur 0 wenn ein Punkt auf einem Ankerpunkt oder ein Punkt auf dem anderen Punkt liegt. Also wenn die oben schon ausgeschlossenen Fälle vorliegen.
Soweit klappts auch super ! Bin nur noch dabei das Programm zu optimieren.
Vielen Dank nochmal!
MfG sHo |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 29 Jun 2005 - 19:51:01 Titel: |
|
|
| Wie zeichnest Du denn die Kurve? Dein Programm fordert bei meinem 2600+ Athlon Mobile fast 100% der Systemleistung! |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 30 Jun 2005 - 00:20:35 Titel: |
|
|
Was echt? Na bin noch am experimentieren mit verschiedenen Sachen.
Mein 'Manko' nennt dich Dual-Opteron-System aber im Win auf 32bit.
Aber eigentlich sollte es nicht so krasse unterschiede geben. Vielleicht
liegts am System. Was hast du für ein OS und Flash Player?
Hier mal ein paar Code-Schnippsel.
Punkt auf Kurve berechnen :
| Code: |
function getCubicPt (p0:Object, p1:Object, p2:Object, p3:Object, t:Number) : Object {
// Formel: P(t) = P0 * (1-t)^3 + P1 * 3 * (1-t)^2 * t + P2 * 3 * (1-t) * t^2 + P3 * t
var t2 = t * t;
var t3 = t2 * t;
var t12 = (1-t) * (1-t);
var t13 = t12 * (1-t);
var x = p0.x * t13 + p1.x * 3 * t12 * t + p2.x * 3 * (1-t) * t2 + p3.x * t3;
var y = p0.y * t13 + p1.y * 3 * t12 * t + p2.y * 3 * (1-t) * t2 + p3.y * t3;
return { _x:x, _y:y };
}
// p0 = Ankerpunkt 1
// p1 = Kontrollpunkt 1
// p2 = Kontrollpunkt 2
// p3 = Ankerpunkt 2
|
Kontrollpunkte berechnen :
| Code: |
function getCubicControlPoints2(A:Object, E:Object, TE:Number, F:Object, TF:Number, D:Object):Object {
// TE^2 & TE^3
var TE2 = TE * TE;
var TE3 = TE * TE * TE;
// TF^2 & TF^3
var TF2 = TF * TF;
var TF3 = TF * TF * TF;
// nenner
var n = -3 * (TE -1) * TE * (TE - TF) * (-1 + TF) * TF;
_root.tf_n = "nenner: "+ Math.round(n*10000)/10000 +"~";
// B
var xval1 = (F.x * (-1 + TE) * TE2 + TF2 * (E.x - E.x * TF + D.x * TE2 * (-TE + TF)) - A.x * (-1 + TE) * (-1 + TF) * (TF2 - 2 * TE * TF2 + TE2 * (-1 + 2 * TF))) / n;
var yval1 = (F.y * (-1 + TE) * TE2 + TF2 * (E.y - E.y * TF + D.y * TE2 * (-TE + TF)) - A.y * (-1 + TE) * (-1 + TF) * (TF2 - 2 * TE * TF2 + TE2 * (-1 + 2 * TF))) / n;
// C
var xval2 = (F.x * ((-1 + TE)*(-1 + TE)) * TE - A.x * ((-1 + TE)*(-1 + TE)) * (TE - TF) * ((-1 + TF)*(-1 + TF)) - TF * (E.x * ((-1 + TF)*(-1 + TF)) + D.x * TE * (TF2 - 2 * TE * TF2 + TE2 * (-1 + 2 * TF)))) / n;
var yval2 = (F.y * ((-1 + TE)*(-1 + TE)) * TE - A.y * ((-1 + TE)*(-1 + TE)) * (TE - TF) * ((-1 + TF)*(-1 + TF)) - TF * (E.y * ((-1 + TF)*(-1 + TF)) + D.y * TE * (TF2 - 2 * TE * TF2 + TE2 * (-1 + 2 * TF)))) / n;
// return
return {x1: xval1, y1: yval1,
x2: xval2, y2: yval2}
// A = Ankerpunkt 1
// D = Ankerpunkt 2
// E = Punkt auf Kurve 1
// TE = t-Param fuer E
// F = Punkt auf Kurve 2
// TF = t-Param fuer F
}
|
Zeichnen :
| Code: |
function draw(mc:MovieClip, n:Number) : Boolean {
var pt = 0;
var n ++;
// zeichnen
for(var i = 0, end = this._points.length-3; i < end; i += 3) {
for(var m=0; m<=1-.0001; m+=1/n) {
if(pt==0) pt = getCubicPt(this._points[i], this._points[i+1], this._points[i+2], this._points[i+3], m);
mc.moveTo( pt._x, pt._y );
pt = getCubicPt(this._points[i], this._points[i+1], this._points[i+2], this._points[i+3], m+1/n);
mc.lineTo( pt._x, pt._y );
}
}
return true;
}
// Anker- und Kontrollpunkte sind als Objekt mit _x und _y im Array _pints gespeichert
// moveTo und lineTo sind Flash-Player-interne Zeichenfunktionen
|
Aloha! sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 30 Jun 2005 - 00:29:52 Titel: |
|
|
Ich sehe nichts böses. Das n sollte vielleicht bei größeren Bildmaßen etwas großzügiger gewählt werden.
Ich habe Linux 2.6.8 und benutze Konqueror von KDE 3.3.0. Flash-Player ist ziemlich aktuell (vor ein paar Monaten runtergeladen). Ich habe das Prog. im Vollbildmodus gestartet und ständig den Refresh-Event ausgelöst indem ich einen der Punkte bewegte. Daraufhin fängt mein Notebook-Kühler zu kochen! |
|
|
Serpico
Junior Member
Anmeldungsdatum: 12.06.2005
Beiträge: 63
|
| Verfasst am: 30 Jun 2005 - 00:54:49 Titel: |
|
|
Komme bei meinem Rechner (2.6 GHz) auf 15% bis 20% CPU Auslastung bei ständiger Bewegung eines Punktes.
(Windows XP prof).
Also alles im grünen Bereich.
lg S. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 30 Jun 2005 - 01:10:35 Titel: |
|
|
Ja, das n soll später dynamischer agieren - je nach den Ausmaßen der Kurve.
Werd mal bissel drann arbeiten. Meinungen sin herzlich Willkommen!
Aloha! sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 30 Jun 2005 - 01:55:13 Titel: |
|
|
| Zitat: |
| Komme bei meinem Rechner (2.6 GHz) auf 15% bis 20% CPU Auslastung bei ständiger Bewegung eines Punktes. |
Auch ein Notebook? |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 30 Jun 2005 - 02:05:27 Titel: |
|
|
| Also, genauer gesagt schaut es so aus. Bei halbem Bild sind es 30% für den X-Server und 20% für den nspluginviewer (d.h. flash). Im Vollbildmodus sind es 40% für X-Server und 50% für den Viewer. Daher leite ich ab, daß der Netscape-Flash-Plugin für Linux einfach Kacke ist. Abgesehen davon sollte aber das Zeichnen einer solchen Kurve überhaupt keine Anstrengung für den Prozessor (auch nicht für den direkten Zugriff auf Grafik-Speicher) sein. Der XP-Plugin wird vermutlich auf Direct-X-Basis arbeiten, sodaß er etwas schneller zeichnet. Ich habe keine HD-Unterstützung. |
|
|
Serpico
Junior Member
Anmeldungsdatum: 12.06.2005
Beiträge: 63
|
| Verfasst am: 30 Jun 2005 - 08:19:20 Titel: |
|
|
| algebrafreak hat folgendes geschrieben: |
| Zitat: |
| Komme bei meinem Rechner (2.6 GHz) auf 15% bis 20% CPU Auslastung bei ständiger Bewegung eines Punktes. |
Auch ein Notebook? |
Nein, Fujitsu Siemens Scaleo.
Habe als Browser allerdings Firefox und nicht Netscape.
lg S. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 07 Jul 2005 - 13:36:36 Titel: |
|
|
Hab jetz mal wieder Zeit gefunden das ganze zu überarbeiten und bissel zu optimieren.
Hier der Code :
| Code: |
/* method: getCubicControlPoints
* params: p0:Object, p1:Object, p2:Object, p3:Object, te:Number, tf:Number
* return: Object { x1, y1, x2, y2 }
* desc : Berechnet die Kontrollpunkte einer Kubischen Bezierkurve anhand íhrer Ankerpunkte (p0, p3),
* zwei auf der Kurve liegenden Punkte (p1, p2) und der zuhehoerigen t-Parameter (te fuer p1, tf fuer p2).
* author: Stefan Hofeditz
* date : 2005-07-07
*/
function getCubicControlPoints(p0:Object, p1:Object, p2:Object, p3:Object, te:Number, tf:Number):Object {
// te^2 & te^3
var te2 = te * te;
var te3 = te2 * te;
// tf^2 & tf^3
var tf2 = tf * tf;
var tf3 = tf2 * tf;
// te - 1 & tf - 1
var te_1 = te - 1;
var tf_1 = tf - 1;
// te_1^2 & tf_1^2
var te_12 = te_1 * te_1;
var tf_12 = tf_1 * tf_1;
//
var tef1 = te2 * (tf - te);
var tef2 = tf2 - 2 * te * tf2 + te2 * (-1 + 2 * tf);
var tef3 = te_1 * tf_1 * tef2;
var tef4 = te_12 * (te - tf) * tf_12;
// n
var n = -3 * te_1 * te * (te - tf) * tf_1 * tf;
// Kontrollpunkt 1
var xval1 = (p2.x * te_1 * te2 + tf2 * (p1.x - p1.x * tf + p3.x * tef1) - p0.x * tef3) / n;
var yval1 = (p2.y * te_1 * te2 + tf2 * (p1.y - p1.y * tf + p3.y * tef1) - p0.y * tef3) / n;
// Kontrollpunkt 2
var xval2 = (p2.x * te_12 * te - p0.x * tef4 - tf * (p1.x * tf_12 + p3.x * te * tef2)) / n;
var yval2 = (p2.y * te_12 * te - p0.y * tef4 - tf * (p1.y * tf_12 + p3.y * te * tef2)) / n;
// return
return { x1: xval1, y1: yval1,
x2: xval2, y2: yval2 }
}
|
.. an der Kommentierung arbeite ich noch! 
und hier das in Flash :
http://www.shofeditz.de/testCubic3.html
Würd mich freuen wenn in den Thread verirrte Leute kurz Ihr System und die Auslastung des Programms Preis geben oder/und vleicht sogar noch ein paar Tipps zur optimierung auf Lager haben! Rein Rechnerisch denk ich habe ich es schon auf das Minimum zusammengesaucht. Dazu habe ich ein paar oft verwendete Berechnungsegmente in Variablen ausgelagert. Sind auch ein paar nciht so rechenaufwärdige Berechnungen rein der Übersicht halber in Variablen gespeichert.
mfg sHo |
|
|
Whoooo
Valued Contributor
Anmeldungsdatum: 08.06.2005
Beiträge: 9161
|
| Verfasst am: 07 Jul 2005 - 13:45:32 Titel: |
|
|
| hab 30-40% auf nem xp2000+ 512mb ram unter win xp. |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 07 Jul 2005 - 14:30:52 Titel: |
|
|
Bei mir sind es jetzt ca. 75%. Aber es fehlt ein Vergleichskriterium zu dem, was vorher war, denn ich glaube fürher war die Bildgröße nicht eingeschränkt. Ich prüfe im Vollbildmodus.
Ich schaue mir den Code an. Mein Tipp ist es die Steigung der Kurve zu berechnen für jeden Punkt und abhängig davon und von der Größe einer Einheit (z.B. 0.01) im Bild längere bzw. kürzere Linien zu zeichnen. Z.B. Wenn Du eine Gerade hast, dann brauchst Du die nicht punktweise Zeichnen und jedes Mal die Bezier-Formel auszuwerten. Die interne line-Methode ist sowieso besser.
Um das zu bewerkstelligen brauchst Du eine Schnelle Abschätzung für S_a^b = sup{|B'(t)| | a <= t <= b}. Diese gibt dann an, wie stark die Kurve im Intervall [a,b] rumirrt. Da Du eine Kubische hast, kannst Du aus obiger Formel schließen, wie lange die Linie sein muss. Ich denke, so spart man ca. 80% der Rechen und Zeichenarbeit im Durschnitt. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 07 Jul 2005 - 14:52:33 Titel: |
|
|
Na immerhin!
Du kannst dir das ganze auf http://www.shofeditz.de/testCubic3.swf auch im Vollbild anschauen. Wobei die kleine Version die eigentliche größe ist, wenn man was SWF ohne HTML-Einbettung aufruft skaliert es sich automatisch auf die volle Fenstergröße und somit frisst es noch mehr Leistung. Ich habe zusätzlich zum code noch die FPS von erst 45 auf 20 herrabgesetzt, was auch ein klein wenig für Speed sorgt.
Deine Idee zum Zeichnen möchte ich auch noch umsetzten - danke anbei für den Ansatz - jedoch möchte ich mich in dem Thread um die Berechnung der Kontrollpunkte zuwenden.
mfg sHo |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 08 Jul 2005 - 16:29:43 Titel: |
|
|
Kannst du das 'S_a^b = sup{|B'(t)| | a <= t <= b}' bitte mal in Worten oder Quelltext ausdrücken? Mit der mathematischen Schreibweise komm ich nicht ganz klar.
mfg sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 08 Jul 2005 - 18:09:46 Titel: |
|
|
| sup{|B'(t)| | a <= t <= b} bedeutet die kleinste obere Schranke für den Betrag (in dem Fall ist es eine Norm. Z.B. euklidische) der Ableitung der Kurve zwischen den Punkten a und b. Ableitung sagt aus, wie "steil" die Kurve in einem Punkt verläuft. S_a^b sagt dann aus, wie steil maximal die Kurve in einem Intervall sein kann. Dadurch kann man z.B. durch Bisektion Intervalle rausfinden, in denen die Kurve flach verläuft. Wenn der Wert S_a^b klein genug ist, so kann man die Kurve durch eine Linie ersetzen. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 12 Jul 2005 - 00:13:17 Titel: |
|
|
Kannst du das bitte ein mal in Quelltext ausdrücken, ich versteh was du meinst, jedoch harperts am 'sup{|B'(t)| | a <= t <= b}'. Was ist z.B. sup und B'(t)? Vielleicht ein kleiner Codeschnippsel, indem das mal in etwa bechrieben ist wie sich was verhält. Aber mit Bisektion an das Problem herranzutreten ist eine sehr gute Idee, derer werd ich mich garantiert annehmen!
mfg sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 12 Jul 2005 - 10:44:22 Titel: |
|
|
| Ich schreibe Dir eine komplette Formel für die Abschätzung. Dazu muss Du Dich ein wenig gedulden, denn ich suche mal in der Literatur, ob es nicht schon so was gibt (ich bin mir da irgendwie sehr sicher, dass es der Fall ist) bevor ich anfange selbst zu rechnen. Naja, die Rechnung ist auch nicht besonders schwer. |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 12 Jul 2005 - 11:01:30 Titel: |
|
|
Ich habe für Dich noch einen "Optimierungsschritt", den ich hätte schon am Anfang posten sollen. Naja. Dein Gleichungssystem ist ja:
| Zitat: |
x_1 [3u(1-u)^2] + x_2 [3u^2(1-u)] = x - x_0 (1-u)^3 - x_3 u^3
y_1 [3u(1-u)^2] + y_2 [3u^2(1-u)] = y - y_0 (1-u)^3 - y_3 u^3
x_1 [3u'(1-u')^2] + x_2 [3u'^2(1-u')] = x' - x_0 (1-u')^3 - x_3 u'^3
y_1 [3u'(1-u')^2] + y_2 [3u'^2(1-u')] = y' - y_0 (1-u')^3 - y_3 u'^3
|
Setze nun
a_11 = 3u(1-u)^2
a_12 = 3u^2(1-u)
b_1 = x - x_0 (1-u)^3 - x_3 u^3
a_23 = 3u(1-u)^2
a_24 = 3u^2(1-u)
b_2 = y - y_0 (1-u)^3 - y_3 u^3
a_31 = 3u'(1-u')^2
a_32 = 3u'^2(1-u')
b_3 = x' - x_0 (1-u')^3 - x_3 u'^3
a_43 = 3u'(1-u')^2
a_44 = 3u'^2(1-u')
b_4 = y' - y_0 (1-u')^3 - y_3 u'^3
Dann ist den System mit diesen Bezeichnungen
a_11 x_1 + a_12 x_2 = b_1
a_23 y_1 + a_24 y_2 = b_2
a_31 x_1 + a_32 x_2 = b_3
a_43 y_1 + a_44 y_2 = b_4
Und die Lösung ist auch entsprechend kürzer:
| Code: |
> eq1 := a_11 * x_1 + a_12 * x_2 = b_1;
eq1 := a_11 x_1 + a_12 x_2 = b_1
> eq2 := a_23 * y_1 + a_24 * y_2 = b_2;
eq2 := a_23 y_1 + a_24 y_2 = b_2
> eq3 := a_31 * x_1 + a_32 * x_2 = b_3;
eq3 := a_31 x_1 + a_32 x_2 = b_3
> eq4 := a_43 * y_1 + a_44 * y_2 = b_4;
eq4 := a_43 y_1 + a_44 y_2 = b_4
> solve({eq1,eq2,eq3,eq4},{x_1,x_2,y_1,y_2});
a_23 b_4 - a_43 b_2 a_11 b_3 - a_31 b_1
{y_2 = ---------------------, x_2 = ---------------------,
a_23 a_44 - a_43 a_24 a_11 a_32 - a_31 a_12
a_24 b_4 - b_2 a_44 a_12 b_3 - b_1 a_32
y_1 = - ---------------------, x_1 = - ---------------------}
a_23 a_44 - a_43 a_24 a_11 a_32 - a_31 a_12
|
wobei diese die generische Ist. D.h. die Sonderfälle, dass die Nenner 0 sind nicht enthalten (Scheiß MuPAD, diese ist mit Maple 9.5 gerechnet worden).
Offenbar enthält obige Lösung viel weniger Additionen und Multiplikationen, also "meine" erste. Und wenn ich mich nicht verschrieben habe, müsste sie auch gehen |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 12 Jul 2005 - 21:59:05 Titel: |
|
|
Also du machst deinem Namen alle Ehre was?
Hab dein Vorschlag mal umgeschrieben, konnte dabei auch noch ein paar Elemente zusammenfassen und terminieren. Die Sonderfälle fang ich vorher schon ab, das ist kein Problem. Nur irgendwie schein ich noch ein Fehler im Script zu haben, bin aber anscheinend total blind. Vielleicht hab ich in der Variablenschieberei was durcheinander gebracht oder die falschen Variablen. Es funktioniert, aber nicht so wie es sollte. 
Aber wenn:
x_0, y_0 = Ankerpunkt 1
x, y = Punkt auf Linie 1
x', y' = Punkt auf Linie 1
x_3, y_3 = Ankerpunkt 2
u = Parameter für Punkt auf Linie 1
u' = Parameter für Punkt auf Linie 2
.. dann kann es nur an etwas anderem liegen.
Hier mal der Code :
| Code: |
function getCubicControlPoints(p0:Object, p1:Object, p2:Object, p3:Object, te:Number, tf:Number):Object {
/***** Kommentar Anfang *****
// uebersicht
x, y p1.x, p1.y // E = Punkt auf Linie 1
x', y' p2.x, p2.y // F = Punkt auf Linie 2
u te
u' tf
x_0 p0.x // A = Ankerpunkt 1
x_1 ges // B = Kontrollpunkt 1 (gesucht)
x_2 ges. // C = Kontrollpunkt 2 (gesucht)
x_3 p3.x // D = Ankerpunkt 2
// ausgangsrechnung
x_1 [3u(1-u)^2] + x_2 [3u^2(1-u)] = x - x_0 (1-u)^3 - x_3 u^3
y_1 [3u(1-u)^2] + y_2 [3u^2(1-u)] = y - y_0 (1-u)^3 - y_3 u^3
x_1 [3u'(1-u')^2] + x_2 [3u'^2(1-u')] = x' - x_0 (1-u')^3 - x_3 u'^3
y_1 [3u'(1-u')^2] + y_2 [3u'^2(1-u')] = y' - y_0 (1-u')^3 - y_3 u'^3
// Setze nun
var a_11 = 3 * u * ((1-u)*(1-u)) // #
var a_12 = ((3 * u)*(3 * u)) * (1-u) // ##
var b_1 = x - x_0 * ((1-u)*(1-u)*(1-u)) - x_3 * (u*u*u)
var a_23 = 3 * u * ((1-u)*(1-u)) // #
var a_24 = ((3 * u)*(3 * u)) * (1-u) // ##
var b_2 = y - y_0 * ((1-u)*(1-u)*(1-u)) - y_3 * (u*u*u)
var a_31 = 3 * u' * ((1-u')*(1-u')) // ###
var a_32 = ((3 * u')*(3 * u')) * (1-u') // ####
var b_3 = x' - x_0 * ((1-u')*(1-u')*(1-u')) - x_3 * (u'*u'*u')
var a_43 = 3 * u' * ((1-u')*(1-u')) // ###
var a_44 = ((3 * u')*(3 * u')) * (1-u') // ####
var b_4 = y' - y_0 * ((1-u')*(1-u')*(1-u')) - y_3 * (u'*u'*u')
a_24 b_4 - b_2 a_44 a_12 b_3 - b_1 a_32
y_1 = - ---------------------, x_1 = - ---------------------
a_23 a_44 - a_43 a_24 a_11 a_32 - a_31 a_12
a_23 b_4 - a_43 b_2 a_11 b_3 - a_31 b_1
y_2 = ---------------------, x_2 = ---------------------
a_23 a_44 - a_43 a_24 a_11 a_32 - a_31 a_12
// umgeordnet
var a_11 = 3 * u * ((1-u)*(1-u)) // #
var a_23 = 3 * u * ((1-u)*(1-u)) // #
var a_12 = ((3 * u)*(3 * u)) * (1-u) // ##
var a_24 = ((3 * u)*(3 * u)) * (1-u) // ##
var a_31 = 3 * u' * ((1-u')*(1-u')) // ###
var a_43 = 3 * u' * ((1-u')*(1-u')) // ###
var a_32 = ((3 * u')*(3 * u')) * (1-u') // ####
var a_44 = ((3 * u')*(3 * u')) * (1-u') // ####
var b_1 = x - x_0 * ((1-u)*(1-u)*(1-u)) - x_3 * (u*u*u)
var b_2 = y - y_0 * ((1-u)*(1-u)*(1-u)) - y_3 * (u*u*u)
var b_3 = x' - x_0 * ((1-u')*(1-u')*(1-u')) - x_3 * (u'*u'*u')
var b_4 = y' - y_0 * ((1-u')*(1-u')*(1-u')) - y_3 * (u'*u'*u')
// aufgeteilt in
var u3 = 3 * u;
var u'3 = 3 * u';
var u32 = u3 * u3;
var u'32 = u'3 * u'3;
var u_3 = u * u * u;
var u'_3 = u' * u' * u';
var u_12 = (1-u)*(1-u);
var u'_12 = (1-u')*(1-u');
var u_13 = u_12 * (1-u);
var u'_13 = u'_12 * (1-u');
var a_11 = u3 * u_12 // #
var a_23 = u3 * u_12 // #
var a_12 = u32 * (1-u) // ##
var a_24 = u32 * (1-u) // ##
var a_31 = u'3 * u'_12 // ###
var a_43 = u'3 * u'_12 // ###
var a_32 = u'32 * (1-u') // ####
var a_44 = u'32 * (1-u') // ####
var b_1 = x - x_0 * u_13 - x_3 * u_3
var b_2 = y - y_0 * u_13 - y_3 * u_3
var b_3 = x' - x_0 * u'_13 - x_3 * u'_3
var b_4 = y' - y_0 * u'_13 - y_3 * u'_3
***** Kommentar Ende *****/
var te3 = 3 * te;
var tf3 = 3 * tf;
var te32 = te3 * te3;
var tf32 = tf3 * tf3;
var te_3 = te * te * te;
var tf_3 = tf * tf * tf;
var te_12 = (1-te) * (1-te);
var tf_12 = (1-tf) * (1-tf);
var te_13 = te_12 * (1-te);
var tf_13 = tf_12 * (1-tf);
var a_1 = te3 * te_12 ; // a_11 & a_23
var a_2 = te32 * (1-te); // a_12 & a_24
var a_3 = tf3 * tf_12 ; // a_31 & a_43
var a_4 = tf32 * (1-tf); // a_32 & a_44
var b_1 = p1.x - p0.x * te_13 - p3.x * te_3;
var b_2 = p1.y - p0.y * te_13 - p3.y * te_3;
var b_3 = p2.x - p0.x * tf_13 - p3.x * tf_3;
var b_4 = p2.y - p0.y * tf_13 - p3.y * tf_3;
var n = a_1 * a_4 - a_3 * a_2;
// Kontrollpunkt 1
var xval1 = - (a_2 * b_3 - b_1 * a_4) / n; // x_1
var yval1 = - (a_2 * b_4 - b_2 * a_4) / n; // y_1
// Kontrollpunkt 2
var xval2 = (a_1 * b_3 - a_3 * b_1) / n; // x_2
var yval2 = (a_1 * b_4 - a_3 * b_2) / n; // y_2
// return
return { x1: xval1, y1: yval1,
x2: xval2, y2: yval2 }
} |
Oberhalb sind auskommentiert paar Schritte .. unten dann nur noch umgestellt in meine Variablen mit p0 - p3, t1,t2 usw. Vielleicht siehst du ja ein Fehler beim überfliegen. Werd mich aber dann nochma drannsetzten. Muss ja irgendwie gehen!
Achja nach was suchst du denn in deiner Literatur genau? Hat das Verfahren einen Namen oder so? Vielleicht steht im Netz schon was dazu, weiß aber net recht nach was ich schauen soll.
besten Dank!
sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 12 Jul 2005 - 22:19:03 Titel: |
|
|
| Zitat: |
| Achja nach was suchst du denn in deiner Literatur genau? Hat das Verfahren einen Namen oder so? Vielleicht steht im Netz schon was dazu, weiß aber net recht nach was ich schauen soll. |
Numerische/Differentielle Fehleranalyse bzw. Interpolations-Fehlerabschätzung bei kubischer Spline-Interpolation. Bei sowas müsste es drin stehen. Ich habe Spezialliteratur vom Lehrstuhl an dem ich arbeite. Ich denke aber, dass muss man sowieso anpassen. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 12 Jul 2005 - 22:41:33 Titel: |
|
|
Klingt nach verdammt viel Stoff für nen Mathe-Legastheniker wie mich.
Aber schon interessant, werd auch mal danach suchen. Was lehrst du denn eigentlich beruflich wenn man fragen darf?
mfg sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 12 Jul 2005 - 23:19:58 Titel: |
|
|
| Zitat: |
| Was lehrst du denn eigentlich beruflich wenn man fragen darf? |
Noch nichts. Ich habe in 3 Monaten meine letzte Diplomprüfung in Informatik/NF Mathe. Ich hoffe auf eine Stelle an der Uni im Bereich intelligente Systeme oder Computeralgebra, da diese meine Spezialisierungs-/Fachrichtungen sind. Ich habe in meinen 6 Studiumsjahren so gut, wie alle Grundlagenvorlesungen in Mathe (LA,Analysis[mittlerweile schon 5 mal],Numerik,Diskrete,Algebra,Zahlentheorie usw.), die es an unserer Uni gibt, betreut (Korrektur/Übungen im Wesentlichen). Daher kann ich mit allem ein wenig was anfangen. Hoffe nicht zu übertreiben mit meiner Lebensgeschichte |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 13 Jul 2005 - 01:04:29 Titel: |
|
|
Na so aktiv und konstruktiv wie du deine - nicht wenige - Kritik hier im Forum preis tust kann ich ruhigen Gewissens sagen : "Junge du hats echt drauf!" ! Ich kenn zwar auch noch einige Mathe-Freaks von der Uni aber du scheinst der freakigste zu sein.
mfg sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 13 Jul 2005 - 14:24:19 Titel: |
|
|
Einen habe ich.
ist nicht
| Code: |
a_12 = ((3 * u)*(3 * u)) * (1-u)
|
sondern
| Code: |
a_12 = 3 * u * u * (1-u)
|
denn ^ bindet stärker als *. |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 13 Jul 2005 - 14:27:38 Titel: |
|
|
Hab den Fehler gefunden. Es lag dran, dass ich für 3u^2 geschrieben habe ((3 * u) * (3*u))
.. was vollkommen falsch ist, mit 3 * (u * u) funktionierts jetz auch super.
Habe aber keine gravierende Veränderung der Auslastung (6-8% CPU).
Hier der Code:
| Code: |
function getCubicControlPoints(p0:Object, p1:Object, p2:Object, p3:Object, te:Number, tf:Number):Object {
var te3 = 3 * te;
var tf3 = 3 * tf;
var te_2 = te * te;
var tf_2 = tf * tf;
var te_3 = te_2 * te;
var tf_3 = tf_2 * tf;
var te_12 = (1-te) * (1-te);
var tf_12 = (1-tf) * (1-tf);
var te_13 = te_12 * (1-te);
var tf_13 = tf_12 * (1-tf);
//
var a_1 = te3 * te_12 ; // a_11 & a_23
var a_2 = 3 * te_2 * (1-te); // a_12 & a_24
var a_3 = tf3 * tf_12 ; // a_31 & a_43
var a_4 = 3 * tf_2 * (1-tf); // a_32 & a_44
var b_1 = p1.x - p0.x * te_13 - p3.x * te_3;
var b_2 = p1.y - p0.y * te_13 - p3.y * te_3;
var b_3 = p2.x - p0.x * tf_13 - p3.x * tf_3;
var b_4 = p2.y - p0.y * tf_13 - p3.y * tf_3;
// Nenner
var n = a_1 * a_4 - a_3 * a_2;
// Kontrollpunkt 1
var x_1 = - (a_2 * b_3 - b_1 * a_4) / n; // x_1
var y_1 = - (a_2 * b_4 - b_2 * a_4) / n; // y_1
// Kontrollpunkt 2
var x_2 = (a_1 * b_3 - a_3 * b_1) / n; // x_2
var y_2 = (a_1 * b_4 - a_3 * b_2) / n; // y_2
// return
return { x1: x_1, y1: y_1,
x2: x_2, y2: y_2 }
} |
Hier zum rumspielen: http://www.shofeditz.de/testCubic4.html
mfg sHo
edit: hehe zwei Dumme ein Gedanke! .. naja ein Dummer, war ja mein Fehler |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 13 Jul 2005 - 15:25:22 Titel: |
|
|
Ich habe heute gute Laune, denn ich habe heute gemeinsam mit zwei überdurchschnittlich begabten Kollegen ein Problem geknackt, was ich schon seit einem Jahr mit mir rumtrage (ein terminierendes Konklusionsableitungsystem für Formeln erster Stufe in Presburger-Arithmetik und dann auch allgemein). Die Diplomarbeit eines der Kollegen ist dadurch schön angereichert und ich habe noch einen Grund einen Artikel zu schreiben, denn es scheint neu zu sein Naja.
Ich beschreibe mal einen einfachen Weg zur Lösung des Problems mit der Bisektion.
B(u) sei die vektorwertige Bezier-Funktion mit den Komponenten Bx(u) und By(u).
B'(u) ist die Ableitung von B(u) nach u ebenfalls mit Komponenten B'x(u) und B'y(u).
Dann ist ein ordnungsäquivalenter Ausdruck für die (euklidische) Norm von B'(u):
N(u) = (B'x(u))^2+(B'y(u))^2
Dieser ist ein Polynom 4-en Grades in u, denn B'(u) ist vektorwertig polynomiell vom Grad 2 in u. Weiterhin ist N(u) positiv semidefinit (>= 0).
Gesucht ist eine Abschätzung von sup{N(u) | a <= u <= b}. Das Intervall [a,b] ist zusammenhängend und abgeschlossen. Daher liegen die Maxima von N(u) in [a,b] entweder an den Nullstellen der Ableitung von N(u) oder an den Rändern a oder b. Alles ist explizit bestimmbar, denn der Grad der vorkommenden Polynome ist kleiner gleich 4.
Würde man das so direkt implementieren (also Nullstellen von N'(u) berechnen, einsetzen, und das Maximum nehmen) so wäre es ein Overkill, denn man müsste viele Rechenoperationen durchführen. Da aber N(u) positiv definit ist, ist zur Suche nach dem Maximum jede Abschätzung nach oben erlaubt (wenn sie nicht all zu heftig ist, denn man will ja eine brauchbare haben).
Soweit so gut.
D.h. was noch fehlt ist N(u) abzuschätzen durch etwas geeignetes. Das mache ich in Kürze (heute Abend oder so), wenn ich gesehen habe, wie N(u) bzw. N'(u) aussieht.
Bitte an alle, die das mitverfolgen. Korrektur/Verbesserungsvorschläge sind gefragt und willkommen! |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 13 Jul 2005 - 21:57:03 Titel: |
|
|
Soweit, so gut.
| Code: |
>> bx := x0*(1-u)^3+x1*3*u*(1-u)^2+x2*3*u^2*(1-u)+x3*u^3;
3 3 2 2
u x3 - x0 (u - 1) + 3 u x1 (u - 1) - 3 u x2 (u - 1)
>> by := y0*(1-u)^3+y1*3*u*(1-u)^2+y2*3*u^2*(1-u)+y3*u^3;
3 3 2 2
u y3 - y0 (u - 1) + 3 u y1 (u - 1) - 3 u y2 (u - 1)
>> bxs := diff(bx,u);
2 2 2 2
3 u x3 - 3 u x2 - 3 x0 (u - 1) + 3 x1 (u - 1) - 6 u x2 (u - 1) +
3 u x1 (2 u - 2)
>> bys := diff(by,u);
2 2 2 2
3 u y3 - 3 u y2 - 3 y0 (u - 1) + 3 y1 (u - 1) - 6 u y2 (u - 1) +
3 u y1 (2 u - 2)
>> n := bxs^2+bys^2;
2 2 2 2
(3 u x2 - 3 u x3 + 3 x0 (u - 1) - 3 x1 (u - 1) + 6 u x2 (u - 1) -
2 2 2
3 u x1 (2 u - 2))^2 + (3 u y2 - 3 u y3 + 3 y0 (u - 1) -
2
3 y1 (u - 1) + 6 u y2 (u - 1) - 3 u y1 (2 u - 2))^2
|
Zuletzt bearbeitet von algebrafreak am 16 Jul 2005 - 14:31:49, insgesamt einmal bearbeitet |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 13 Jul 2005 - 22:17:01 Titel: |
|
|
Das gibt
| Code: |
>> poly(n,[u]);
2 2 4
poly(((3 x0 - 9 x1 + 9 x2 - 3 x3) + (3 y0 - 9 y1 + 9 y2 - 3 y3) ) u +
(- 2 (6 x0 - 12 x1 + 6 x2) (3 x0 - 9 x1 + 9 x2 - 3 x3) -
3
2 (6 y0 - 12 y1 + 6 y2) (3 y0 - 9 y1 + 9 y2 - 3 y3)) u +
(2 (3 x0 - 3 x1) (3 x0 - 9 x1 + 9 x2 - 3 x3) +
2
2 (3 y0 - 3 y1) (3 y0 - 9 y1 + 9 y2 - 3 y3) + (6 x0 - 12 x1 + 6 x2) +
2 2
(6 y0 - 12 y1 + 6 y2) ) u + (- 2 (3 x0 - 3 x1) (6 x0 - 12 x1 + 6 x2) -
2 (3 y0 - 3 y1) (6 y0 - 12 y1 + 6 y2)) u +
2 2
((3 x0 - 3 x1) + (3 y0 - 3 y1) ), [u])
|
Die Koeffizienten kann man nun abschätzen. Ich müsste dazu noch was wissen. Sind die x_0,...,x_3 und y_0,...,y3 positiv?
Zuletzt bearbeitet von algebrafreak am 14 Jul 2005 - 01:31:39, insgesamt einmal bearbeitet |
|
|
sHo
Newbie
Anmeldungsdatum: 05.06.2005
Beiträge: 28
Wohnort: Dresden
|
| Verfasst am: 14 Jul 2005 - 00:06:57 Titel: |
|
|
Wow! Das muss ich mir erst nochmal vier-, fünfmal durchlesen und dann bestimmt nochmal nachfragen was das sein soll.
Aber zu deiner Frage: Eigentlich sind die normalwerte alle positiv, sowohl auf x, als auch auf y. Es kann aber auch vorkommen,
das ein Punkt in den negativen Bereich verschoben wird. Wenn es der Berechnung zu viel abverlangt oder zu umständlich ist,
kann ich das aber auch schon vorher im Programm Abfangen - ist kein Problem.
mfg sHo |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 14 Jul 2005 - 01:20:43 Titel: |
|
|
Ich mache das mal in kleinen Schritten, da der Irrtum so weniger wahrscheinlich ist, wenn man Zeit zum Nachdenken hat zwischendurch.
Bemerkenswert ist, dass x0, x2, y0 und y2 stets mit positiven Koeffizienten vorkommen und x1, x3, y1 und y3 stets mit negativen. Doof ist nur, dass bei ungeraden u-Potenzen die Koeffizienten nochmal negiert werden.
D.h. bei den geraden Potenzen von u kann man x0,x2,y0 und y2 durch max{x0,x2,y0,y2} ersetzen. Analog kann man dabei x1,x3,y1 und y3 durch min{x1,x3,y1,y3} ersetzen. Die Berechnung von minima und maxima ist algorithmisch weniger anspruchsvoll, als rechenoperationen mit floats, da im Wesentlichen lexikographischer Vergleich stattfindet, der linear ist. Bei ungeraden Potenzen von u muss man max und min vertauschen.
D.h. so wie es ausschaut, braucht man nur vier Werte zunächsteinmal.
omax = max{x0,x2,y0,y2}
omin = min{x0,x2,y0,y2}
emax = max{x1,x3,y1,y3}
emin = min{x1,x3,y1,y3}
Damit läßt sich das Polynom von oben abschätzen durch
p(x) = a u^4 + b u^3 + c u^2 + d u + e
mit
a = (3 omax - 9 emin + 9 omax - 3 emin)^2 + (3 omax - 9 emin + 9 omax - 3 emin)^2 = 2 (12 omax - 12 emin)^2
b = - 2 [(6 omin - 12 emax + 6 omin)(3 omin - 9 emax + 9 omin - 3 emax) + (6 omin - 12 emax + 6 omin)(3 omin - 9 emax + 9 omin - 3 emax)] = -4 (12 omin - 12 emax)(12 omin - 12 emax) = -4 (12 omin - 12 emax)^2
c = 2(3 omax - 3 emin)(3 omax-9 emin + 9 omax -3 emin) + 2(3 omax - 9 emin + 9 omax - 3 emin) + (6 omax - 12 emin + 6 omax)^2 + (6 omax - 12 emin + 6 omax)^2 = 4 (3 omax - 3 emin)(12 omax - 12 emin) + 2 (12 omax - 12 emin)^2
d = -2 [(3 omin - 3 emax)(6 omin - 12 emax + 6 omin) + (3 omin - 3 emax)(6 omin - 12 emax + 6omin)] = -4 (3 omin - 3 emax)(12 omin - 12 emax)
e = (3 omax - 3 emin)^2 + (3 omax - 3 emin)^2 = 2 (3 omax - 3 emin)^2
Ich bitte alle, die es lesen und helfen wollen, es nachzurechnen. Ich pflege in sowas Fehler zu machen.
Das geht ja so, als ob das eine Übungsaufgabe wäre, die bedacht gestellt worden ist Man führt offenbar alles auf die Differenz omax - emin und omin - emax zurück. |
|
|
algebrafreak
Senior Member
Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau
|
| Verfasst am: 14 Jul 2005 - 01:27:11 Titel: |
|
|
Setzt man nun im obigen
v = omax-emin
w = omin-emax
so erhält man
p(x) = a u^4 + b u^3 + c u^2 + d u + e
a = 288 v^2
b = -576 w^2
c = 432 v^2
d = -144 w^2
e = 18 v^2
Was auch mehr oder weniger zu erwarten war. Ich hoffe das ist keine all zu harte Abschätzung.
Morgen (d.h. heute) geht es ein Stück weiter. Vielleicht sieht der eine oder der andere Mist darin |
|
|
|
Home
FAQ
Regeln
Suchen
Registrieren
Login
