Spline solving with Tridiagonal Matrix

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

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 on other sites
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 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 on other sites
Quote:
 Original post by alvaroDave, 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 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]

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
5. 5
A4L
11

• 12
• 16
• 26
• 10
• 44
• Forum Statistics

• Total Topics
633767
• Total Posts
3013739
×