Pad door Coördinaten Versoepelen

Roberto Molvado

Ik zit met een wiskundig probleempje. Het is alleen meer gerelateerd aan programmeren, maar hier kan vast iemand mij helpen!

Ik programmeer voor games. Iets wat ik geregeld wil, is iets dat een pad volgt (ik noem de resulterende vector p). Dat pad bestaat dan uit een reeks aan coördinatoren (v_i) en ik kan dan op een constante wijze interpoleren tussen twee opeenvolgende punten:

p = x * v_j + (1-x) * v_j+1

x wordt dan langzaam verhoogd, totdat x = 1, dan x := 0 en j := j + 1.

Dit werkt prima, maar voor een soepel pad zijn heel veel punten nodig.
Mijn vraag dus: is het mogelijk een soort van versoepelde interpolatie van die punten te maken?

Dit zal een beetje vaag klinken, dus bijgevoegd een afbeelding die het hopelijk beter uitlegt. De gestippelde lijn is dan waar ik naar zoek.

Alvast hartelijk bedankt!

xansid

Zoek op 'splines' of 'B-splines'. Weet er verder niet heel veel van af maar volgens mij is dat precies wat je zoekt

Roberto Molvado

Dank voor je reactie.

Als ik het goed begrijp gaat het hier over het gebruik van een polynoom om een soepele lijn te krijgen, toch? Het punt is dat een functie voor mij niet kan
werken, omdat mijn paden met zich zelf kunnen snijden en in het algemeen alle kanten op kunnen.

EDIT:
Oeps, ik reageer te snel. Het gaat geloof ik om één polynoom tussen twee punten, waar zowel de functiewaarde als zijn afgeleide op de knooppunten overeenkomen met de volgende polynoom. Nog steeds is dat lastig te te passen, zeker in 3D.

xansid

Ik denk ook niet dat er een makkelijke manier om dit te doen is Roberto. Je zou nog naar radiale basis functies (RBF interpolation) kunnen kijken voor 3D, dat is misschien iets makkelijker te implementeren.
Ik heb zelf echt maar minimale ervaring met dit soort technieken dus ik kan je helaas niet veel verder helpen dan dit.

Marko

Het kan prima met splines. Je moet de verschillende punten (x,y,z) zien als 3 aparte sets: eentje met x als functie van t, eentje met y (t) en eentje met z (t)

Misschien heb je daadwerkelijke tijd-waardes die bij deze coördinaten horen, anders definieer je dat het eerste punt t=1 is, tweede punt t=2 enzovoort.

Vervolgens kun je dus 3 setjes maken, met een tijd-coördinaat en een x (of y of z) coördinaat.

Die 3 sets kun je ieder voor zich interpoleren met splines, waarna je 3 nieuwe sets hebt met meer punten erin, maar die ook elk dezelfde t-coördinaten hebben.

Tenslotte kun je voor elk tijdstip de bijbehorende x, y en z opzoeken en gebruiken.

Roberto Molvado

Oké, dat klinkt goed.
Hoe zou ik die x(t), y(t) en z(t) functies opstellen? Want het enige dat ik heb zijn de punten.
En wat nu als bijvoorbeeld y(t) een lijn is (het pad is dan even verticaal bv.)? Daar heeft een polynoom geen oplossing voor.

Marko

Die functies hoef je niet op te stellen. Je hebt een verzameling punten, bijvoorbeeld

P1: (X,Y,Z) = (1,1,1)
P2: (X,Y,Z) = (2,3,4)
P3: (X,Y,Z) = (3,2,3)

enzovoort.

Wat je nu doet is deze verzameling punten omzetten in 3 verzamelingen met coördinaten:

X = {1,2,3,...}
Y = {1,3,2,...}
Z = {1,4,3,...}

En je maakt een verzameling tijdstippen aan:

t = {0,1,2,,....}

Nu ga je interpoleren, eerst de X-waardes t.o.v. t

Dit kun je visualiseren als een grafiek met een t-as en een X-as. In die grafiek zie je de punten (0,1); (1,2); (2;3) enzovoort

Hetzelfde doe je voor een interpolatie van Y t.o.v. t: Dan gaat het om punten (0,1); (1,3); (2,2), ...
En tenslotte voor Z

Het maakt voor de interpolatie niet uit of de waardes toenemen, afnemen, sterk toenemen of gelijkblijven.

De functies kun je opstellen volgens de methode die hier staat beschreven:

http://en.wikipedia.org/wiki/Spline_interpolation

Roberto Molvado

Ik kom er toch niet uit hoe die polynomen opstelt aan de hand van de pad-punten.

Wat ik wel ben tegengekomen is de 'Catmull-Rom interpolation'. Op deze manier kun je tussen vier punten een spline maken. Door steeds de vier gekozen punten één plekje op te schuiven, kun je tussen alle punten iets tekenen.
Deze methode heeft alleen wel twee nadelen: van een verzameling kun je niets tekenen naar de buitenste twee punten, maar dat heb ik opgelost door automatisch twee extra punten toe te voegen aan de verzameling, die bestaan uit het eerste punt plus het verschil tussen het eerste en tweede punt (en hetzelfde voor het allerlaatste punt). Het tweede nadeel is dat je 'cups' en 'self-intersections' kunt krijgen. Dat zou opgelost moeten kunnen worden door gebruik te maken van 'centripetal parameterization': http://stackoverflow.com/questions/9489736/catmull-rom-curve-with-no-cusps-and-no-self-intersections/19283471#19283471
...Maar ik krijg het niet voor elkaar dat te gebruiken. Iemand enig idee wat dat inhoudt?

xansid

je tweede link doet het niet, ik denk door het hekje

Roberto Molvado

Kan ik oudere posts nog wijzigen?

De juiste link: http://stackoverflow.com/questions/9489736/catmull-rom-curve-with-no-cusps-and-no-self-intersections

xansid

Er staat in dat onderwerp op stackoverflow een duidelijk antwoord met voorbeeldcode en zelfs plaatjes erbij. Wat wil je precies nog meer weten?

Roberto Molvado

Ik zie je punt.
Wat ik bedoel is dat het verschil niet snap tussen de standaard Catmull-Rom en de 'parameterized' variant. Verder is de gegeven code in Java, wat ik niet ken, en die snap ik niet.

descheleschilder

Ik heb geen enkele link gelezen, maar misschien kan je de punten V₁, V₂, etc. als punten in het x-y vlak zien en tussen twee opeenvolgende punten i.p.v. een functie van een rechte lijn als benadering als de daarna eenvoudigste (?) benadering een deel van een parabool (de stippellijn) kunnen nemen: ax²+bx+c. In ieder punt V_n moeten de waarden (y) en de waarden van de afgeleiden van de twee parabolen gelijk zijn (je zou bijvoorbeeld ook cirkeldelen kunnen nemen, y=√(r-x²)+c, maar ik ben niet helemaal zeker of de afgeleiden gelijk kunnen worden in alle punten, ten behoeve van een continue kromme). Of het een dal- of berg-parabool is hangt af van de het volgende punt (V_n⇒V_n+1). Zou in jouw voorbeeld, zeg V₃, meer naar linksonder liggen (zodat de lijnstukken V₁V₂ en V₂V₃ een grotere hoek dan 180 graden vormen) heb je een berg-parabool nodig. Het is duidelijk dat in jouw figuur de eerste twee parabolen dal-parabolen zijn en de derde een berg-parabool is.
Het grootste probleem is Natuurlijk het bepalen van de functies. Ik heb zo´n idee dat daarover wel het een en ander in bovenstaande links te lezen is.
Ciao, Roberto!

Roberto Molvado

Dank je voor je reactie.

Wat je hier beschrijft is inderdaad min of meer waar die 'cubic spline interpolation' op neer komt, alleen wordt er dan een derde machts polynoom gebruikt, omdat je een kwadratische formule (inderdaad) niet overal passend krijgt.

Ik ben er nog steeds niet uit hoe die formules vind. Ik ga nog eens zoeken.

descheleschilder

Ik zou je graag verder helpen, maar in ieder geval veel succes!
Groetjes dss (Marco Barbieri)

Wetenschapsforum

Laatste berichten

Nieuwsberichten

Pad door Coördinaten Versoepelen

Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co

Re: Pad door Co