Jump to content
  • Advertisement
Sign in to follow this  
schupf

Spline solving with Tridiagonal Matrix

This topic is 3414 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello! this posting is rather long, but the content is fairly simple, so please keep on reading;) I want to program a system for camera paths with cubic hermite splines. The spline is composed of piecewise hermite curves, where each hermite curves is constructed from 2 Points and the corresponding tangents. To create the whole spline the user just specifies n points and the first tangent P1' (the tangent of point P1) and the last tangent Pn' (of point Pn). So this is what I have: Points P1, P2, ..., Pn Tangents P1', Pn' The only thing that is missing are the inner tangents P2', P3', ..., Pn-1' I can compute the tangents with this system of linear equations: This has the form A*x = d, where A is a constant matrix, x are the missing tangents I want to compute and d is only composed of the known points. According to the author of the book where I got formula 5.7 from, matrix A is a tridiagonal matrix and thus can easily be solved with the Thomas Algorithm. I think this is wrong, because only square matrices can be tridiagonal and matrix A is obviously NOT square (its a (n-2) x n matrix). But since the user specifies the first and last tangent P1' and Pn' we basically have 2 additional equations and thus I can add the row (1, 0, 0, ..., 0) at the top of matrix A, row (0, 0, ..., 1) at the bottom of matrix A and P1' at the top of d and Pn' at the bottom of d. So basically I just added the trivial equations P1'=P1' and Pn'=Pn' to the system. Now matrix A's dimension is n x n and tridiagonal and I can use the tridiagonal algorithm. Now comes my problem: I also want to program a natural (or relaxed) spline, where the user does NOT have to specify the first and last tangents. A natural spline just has this additional condition: The second derivatives in the first and last points are zero. This leads to this system of linear equations: This is almost the same as formula 5.7. The only difference is that P1' and Pn' are not given and have to be calculated by equations. According to the author you solve this in the following way: 1. Solve for the inner tangents P2' to Pn-1' and then use P2' to calculate P1' and use Pn-1' to calculate Pn'. This sounds logical but again I have the problem that A is NOT square and thus NOT tridiagonal. Unfortunately I can't use the little trick I used for formula 5.7 (adding the (1,...,0) and (0,..,1) rows), because this time I don't know P1' and Pn'. Does anyone have an idea how I can make matrix A from equation 5.10 tridiagonal? Thanks! [Edited by - schupf on May 20, 2009 12:36:29 PM]

Share this post


Link to post
Share on other sites
Advertisement
Something is incorrect in your Equation (5.10). You have indicated that the left-hand-side matrix has n-2 rows, but I count n rows. The right-hand-side column has n-2 rows. There is a mismatch in sizes.

In fact, your Equation (5.7) appears to have the same problem. The matrix is marked as having n-2 rows, but the column next to it has n rows, P[1]' through P[n]'.

Perhaps you meant that column to be P[2]' through P[n-1]', in which case you have a tridiagonal matrix of size (n-2)x(n-2), and the system can be solved directly for P[2]' through P[n-1]'. When P[1]' and P[n]' are specified, you do not need to expand the matrix to (n)x(n). When P[1]'' = 0 and P[n]'' = 0, solve the (n-2)x(n-2) system for P[2]' through P[n-2]' and then use the formulas you mention to estimate P[1]' and P[n]'.

Share this post


Link to post
Share on other sites
Dave, I think you are not reading it right. The matrix has n-2 rows and the right-hand side is a column with n-2 elements in both equations...

As for the original problem, since there are only n-2 variables to determine (the intermediate tangents), I am sure the right fix is to remove two columns (first and last) from the matrix and move the known values to the right-hand side. In the second equation, you'll have to modify the rows corresponding to P2' and P{n-1}' as well.

In both cases, you'll be left with a tridiagonal matrix of size (n-2)x(n-2).

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Dave, I think you are not reading it right. The matrix has n-2 rows and the right-hand side is a column with n-2 elements in both equations...


Quite right. Too early in the morning to be posting :)

Share this post


Link to post
Share on other sites
Hi,
In the OP You said that you already have P1' and PN', they are not unknowns. You have to rewrite equation (5.1) as to remove P1' and PN' from the left hand side.
[EDIT]
Ooops! what a shame! I'll write 10000 times "read carefully the question before answering" :O)
Sorry for my extreme stupidity. I keep this message as a reminder.

[Edited by - knighty on August 3, 2009 8:29:38 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!