Register FAQ / Rules Forum Spy Search Today's Posts Mark Forums Read
 MacRumors Forums B Spline interpolation

 Aug 2, 2010, 12:29 PM #1 Duke Leto macrumors regular   Join Date: Mar 2008 B Spline interpolation I'm trying to implement de Boor's algorithm for B splines, but I'm having some issues. The rest of the code contains the control points, and it creates a uniform integer knot vector {0, 1, 2, 3, .... } It goes through the knots and calculates the point on the spline for that point. After that, it creates a .png file using the results from the de Boor algorithm. Code: ```Point coxDeBoor(float* u, Point* pts, const float x, const int n, int d) { // u is the knot vector // pts contains the control points // x is the parameter we're calculating for // n is the number of control points // d is the degree int i, l, j = 0; // find the knot span that x is in for(i=d-1; i<=n+1; i++) { if (x>=u[i] && x
 Aug 2, 2010, 02:02 PM #2 Sander macrumors 6502   Join Date: Apr 2008 I know this has nothing to do with your question, but it looks like you're leaking memory in this function... __________________ Computer Programming: An Introduction for the Scientifically Inclined So how much does an iPhone developer make? My iPhone games: Sjoelen, Mazer (free) 0
 Aug 2, 2010, 03:05 PM #3 ncl macrumors member   Join Date: Aug 2008 I am not familiar with this but there is something wrong in your initialization. Shouldn't Code: `P[i] = malloc(sizeof(Point)*i);` be Code: `P[i] = malloc(sizeof(Point)*d);` ? And testPt is not initialized. Also, it looks like pts and l aren't used in this function. And finally, P is never freed. If I understand correctly the wikipedia article, P[*][0] should be initialized with the control points in l-d…l and the "for j" loop should go from l-d+i to l. 0
 Aug 2, 2010, 03:24 PM #4 lloyddean macrumors 6502a   Join Date: May 2009 Location: Des Moines, WA And the parameter 'pts' is never referenced within the function. 0
 Aug 2, 2010, 03:38 PM #5 Duke Leto Thread Starter macrumors regular   Join Date: Mar 2008 Yes, I am leaking memory, but I am not too worried about that at the moment. In the original code, I used the pts parameter to set testPoint so that I could see it. That is where the initialization occurs. I accidentally changed it in this code. Similarly, the second array did go to d, not i. That was a change I made to test something. __________________ Gravita - a gravity simulation. Available for Mac at http://www.thebluekoala.com 0
Aug 3, 2010, 07:32 AM   #6
MrFusion
macrumors 6502a

Join Date: Jun 2005
Location: West-Europe
Quote:
 Originally Posted by Duke Leto ...it goes past the control points, instead of staying well inside.
That doesn't surprise me. At least not if it is a third order, which I am most familiar with. If you calculate the third order (by hand if you are so inclined), you will see that there are 4 additional points required to complete the recursion. Depending on the definition of your control point, it is either 4 points after your last knot point, or two before the first and two after the last one. These four points have to be defined on the knot axis, but don't require a value for the control point.

Can you also post the recursive formula in math notation? Your implementation differs from the formula I have.
Also, x can be any value in the range you want to plot. The spline curve is a function of x, how can you then calculate it inside the loop?
__________________
24" iMac, 13" MacBook, iPod Touch. iPod mini and PowerPC Mac Mini gathering dust somewhere.
0
 Aug 3, 2010, 09:48 AM #7 Duke Leto Thread Starter macrumors regular   Join Date: Mar 2008 I have the extra knot values. The control points are supposed to be a convex hull for the spline, so they must stay inside. There are n+d knot values, and x ranges from d to n. I have fixed a good bit by changing the tau calculation to: Code: ``` ii = j+l-d+1; u1 = u[ii]; u2 = u[ii+d-i+1]; tau = (x-u1)/(u2-u1);``` However, there are gaps. Whenever x passes a knot value, the spline point skips a bit. __________________ Gravita - a gravity simulation. Available for Mac at http://www.thebluekoala.com 0
Aug 3, 2010, 01:03 PM   #8
MrFusion
macrumors 6502a

Join Date: Jun 2005
Location: West-Europe
I see that you calculate only 1 tau, and x as well.
The B-splines as I am familiar with them look like in the attachments.
That is why I was asking you to post your formula in math notation.
Attached Files
 B-spline-iteration.pdf (92.5 KB, 96 views) bspline-curve.pdf (92.5 KB, 91 views)
__________________
24" iMac, 13" MacBook, iPod Touch. iPod mini and PowerPC Mac Mini gathering dust somewhere.
0
 Aug 3, 2010, 08:57 PM #9 Duke Leto Thread Starter macrumors regular   Join Date: Mar 2008 I'm using deBoor's algorithm. Anyway, its all fixed now, so if you want to see a sample (I made this today from boredom), then here's a download. Its a GLUT application. n to add a point (in the location of the mouse) d t delete a point click/drag to move them -/= to decrease/increase resolution 2-9 to change the degree p to toggle viewing the control polygon I'll post the code if its requested. __________________ Gravita - a gravity simulation. Available for Mac at http://www.thebluekoala.com 0
Aug 4, 2010, 04:01 AM   #10
MrFusion
macrumors 6502a

Join Date: Jun 2005
Location: West-Europe
Quote:
 Originally Posted by Duke Leto I'm using deBoor's algorithm.
I am not a mathematician nor a computer scientist. I don't know deBoor's algorithm. I am sure there are other people here who also don't know deBoor's algorithm. That doesn't mean we are not capable of finding an error in your code if you had also provided the algorithm.

Quote:
 I'll post the code if its requested.
That would be nice for anyone stumbling on to this thread who has the same problem.
__________________
24" iMac, 13" MacBook, iPod Touch. iPod mini and PowerPC Mac Mini gathering dust somewhere.
0
 Aug 4, 2010, 07:52 AM #11 Duke Leto Thread Starter macrumors regular   Join Date: Mar 2008 deBoor: http://en.wikipedia.org/wiki/De_Boor's_algorithm http://www.idav.ucdavis.edu/educatio...alculation.pdf ^^ The second link is better at explaining, the first gives you a general idea. Code: Code: ```struct pt { float x; float y; }; typedef struct pt Point; void generateRegularBSpline(const int n, Point* controlPts, const int d, Point* splinePts, int numSplinePts) { float*u = malloc(sizeof(float)*(n+d)); int i; for(i=0; i=u[i] && x
Jan 20, 2011, 01:34 PM   #12
little gauss
macrumors newbie

Join Date: Jan 2011
Location: Germany
Highlighting and dragging points with GLUT

Quote:
 Originally Posted by Duke Leto I'm using deBoor's algorithm. Anyway, its all fixed now, so if you want to see a sample (I made this today from boredom), then here's a download. Its a GLUT application. n to add a point (in the location of the mouse) d t delete a point click/drag to move them -/= to decrease/increase resolution 2-9 to change the degree p to toggle viewing the control polygon I'll post the code if its requested.
I'd be very keen and grateful to learn from you how to highlight and drag rectangular points or similar in OpenGL-GLUT code as you have very nicely demonstrated in your Spline Creator application. I'd be most grateful if you would send me your GLUT code or post it somewhere accessible for my personal study and experimentation. Many thanks and best regards and wishes in advance!
0

 MacRumors Forums

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules

 Similar Threads thread Thread Starter Forum Replies Last Post R0b0t Mac Programming 8 May 31, 2008 05:04 PM

All times are GMT -5. The time now is 06:47 AM.

Mac Rumors | Mac | iPhone | iPhone Game Reviews | iPhone Apps
 Contact Us - MacRumors Forums - Archive - Privacy Statement / DMCA Agent - Top

Mobile Version | Fixed | Fluid | Fluid HD