T-Splines
T-Splines

Current version

Download the current version.

Autodesk T-Splines Plug-in for Rhino v3.4 Download
Autodesk tsElements v1.2 Download

Featured threads

The links below lead to some of our favorite forum threads.

052775 052099

29164 052640

29164 29164

052346 052775


See more featured threads.

Webinars

Date Topics  
7/09 Creating stunning jewelry designs with T-Splines View
5/07 How to approach modeling with T-Splines View
3/07 Carl Bass reintroduces T-Splines for Rhino View
6/21 Transitioning from NURBS to T-Splines View
12/07 Footwear modeling with T-Splines 3.3 for Rhino View
11/29 New T-Splines reverse engineering tools View
10/28 How T-Splines changed my aproach to making jewelry in CAD View
09/29 Modeling a water gun View
09/07 Car modeling:
Parts 1, 2, & 3
View
07/06 tsElements intro
hosted by Novedge
View
06/22 Free-form Architecture View
06/15 TS Pipe command View
06/08 T-Splines for Rhino intro View

T spline local refinement

Discuss academic questions related to T-Splines and geometric surface modeling.

T spline local refinement

Postby QLong » Sun Feb 22, 2009 11:38 am

Hello,
I 'm studying the paper T spline Simplification and Local Refinement. I have a question about the example in Section 4.3.
In the example, we only changed the blending function centered at [s2, t2]. What does the algorithm do if we move on to look at the blending function at [s4, t2]? Do we have to insert t3 to the t knot vector of this blending function?

If so, then imagine we have first changed the blending function at [s4, t2] (we dont need P3), then we will come back to the blending function again, because we will need P3 when we change the blending function at [s2, t2]?

Thank you very much!
Quan
QLong
Poster
 
Posts: 2
Joined: Sun Feb 22, 2009 11:23 am

Re: T spline local refinement

Postby Nicholas North » Mon Feb 23, 2009 12:37 pm

QLong wrote:Do we have to insert t3 to the t knot vector of this blending function?


The short answer is No. I'll do my best to explain a bit more.

To help, I've attached an image of Figure 9 from the paper. I'll go through the steps illustrated in Figure 9 and explain what is happening.

a. This is the starting T-Spline. It is valid -- there are no violations.

b. We wish to insert point P2, but this causes violations in the blending functions centered at (s1,t2), (s2,t2), (s4,t2) and (s5,t2) which all lack a knot at s3.

c. After inserting s3 into the four blending functions they all become valid. Figure 9.c. shows the new (valid) blending function centered at (s2,t2).

d. However, the newly created blending function for P2, centered at (s3,t2), does not match the mesh. The is because the contributions received from the blending functions centered at (s1,t2) and (s2,t2) contained a knot at t3.

e. We cannot make the blending function match the mesh, so we make the mesh match the blending function. To do this, we insert the new point shown in Figure 9.e., centered at (s3,t3).

f. The insertion of the point in Figure 9.e. fixes one violation, but a new one arises in the blending functions centered at (s1,t3) and (s2,t3) since these blending functions do not contain a knot at s3 so they no longer match the mesh. Inserting into these blending functions resolves the violations.

After Figure 9.f. there are no more violations. Every blending function know matches the mesh.

You specifically asked about the blending function centered at (s4,t2). This blending function had a violation after the insertion of P2, but this was remedied by inserting a knot at s3. If you follow the knot like in the t direction then you will see that there is no control point at t3. As long as there is no control point at t3 then this blending function cannot have a knot at t3. It must match the mesh.

We may elect to add a control point at (s4,t3) if we prefer not to have L-junctions (and, in practice, this might be a good idea), but this is not required. As long as we don't add a new point centered at (s4,t3) then we don't need a knot at t3 in the blending function centered at (s4,t2).

I hope this helps.

-- Nick
Attachments
Figure9.png
Figure 9 from "T-Spline Simplification and Local Refinement"
User avatar
Nicholas North
Employee
 
Posts: 627
Joined: Wed Sep 19, 2007 10:38 am
Location: Utah

Re: T spline local refinement

Postby QLong » Tue Feb 24, 2009 3:04 pm

Hi Nick,
Thanks you very much for your detailed explanation.
I think I understand the spliting of blending function at P1 and the reason there should be a new point at [s3, t3].

But I still dont understand the splitting of blending function at [s4,t2]. To be more specific, the original knot vector of [s4,t2] is [s1 s2 s4 s5 s6] and [t0 t1 t2 t4 t5]. After the insertion of knot s3, the original blending function at [s4,t2] must be splitted into two blending functions, which are centered at [s4 t2] with knot vectors [s2 s3 s4 s5 s6], [t0 t1 t2 t4 t5] and [s3, t2] with knot vectors
[s1 s2 s3 s4 s5 ], [t0 t1 t2 t4 t5] (have the same position with P2). However, in Figure f point P2's knot vector is defined as [s1 s2 s3 s4 s5 ], [t0 t1 t2 t3 t4] . Is it possible to have two sets of knot vectors at the same point?
:(
QLong
Poster
 
Posts: 2
Joined: Sun Feb 22, 2009 11:23 am

Re: T spline local refinement

Postby Nicholas North » Tue Feb 24, 2009 4:23 pm

QLong wrote:Is it possible to have two sets of knot vectors at the same point?
:(


As an intermediate state, yes, logically there may be multiple blending functions (with different knot vectors) at given point at once. Once all of these blending functions have matching knot vectors then we can just sum them together to get a single blending function for that point. This is implied, but not specifically stated in the paper (as far as I can tell).

Lets look at our example:

As you said, the addition of P2 requires that we insert s3 into the blending function at [s4,t2]. The portion of this blending function that is "donated" to P2 has knot vectors [s1 s2 s3 s4 s5 ], [t0 t1 t2 t4 t5].

On the other side of P2 we have the blending function centered at [s2,t2]. After inserting s3, a blending function with knot vectors [s1 s2 s3 s4 s5], [t0 t1 t2 t3 t4] is contributed to the blending function at P2.

So we have two types of blending functions that are donated to the blending function at P2, one with t knot vector [t0 t1 t2 t4 t5] and one with [t0 t1 t2 t3 t4]. To make these compatible, we must insert t3 into the blending function that lacks it. This gives rise to the required extra point at [s3,t3] (via Violation 2).

Figure 9.d. shows the compatible blending function at [s3,t2]. Once t3 has been inserted into the blending function with t knot vector [t0 t1 t2 t4 t5] then we can sum the blending functions together to create a single blending function located at P2. Summing blending functions together to yield a single blending function at each point is required to have a valid mesh.

Hopefully this helps. :)

-- Nick
User avatar
Nicholas North
Employee
 
Posts: 627
Joined: Wed Sep 19, 2007 10:38 am
Location: Utah

Re: T spline local refinement

Postby Genesis84 » Thu May 14, 2009 5:15 am

Thank you very much. This exact problem has been bugging my mind for months now without ever finding an answer. It's hard to get hold of people with in-depth knowledge of T-splines.

Of course, the answer to this problem is still somewhat undefined. Since we have started to include t5 as a knot, then the figure should display this as well. I guess it is to be understood that every knot on the top row (t4) is connected to t5, but this is not a necessity in case of T-splines. One could have the case that (s5,t4) is connected to (s5,t5) while (s4,t4) is connected to (s4,t6). This is not really a question since I see that the algorithm would then proceed with the insertion of even more knots until there are no more violations.

Based on what I've read in here I do feel that one could have elaborated a bit more around the example connected to Figure 9. This is without doubt the single thing which has caused me the most headache while trying to read through the articles.
User avatar
Genesis84
Poster
 
Posts: 17
Joined: Thu May 14, 2009 3:50 am

Re: T spline local refinement

Postby Nicholas North » Thu May 14, 2009 8:39 am

I'm glad this discussion has been helpful. :D The technology section of this forum is probably the best place to discuss T-Spline theory openly. We're always happy to help if you wanted to email us as well.

You're absolutely right about t5: it's implied in the posted figure. We probably could have included t5 to be a bit more complete... but, as you said, it doesn't really affect things much as you just continue on with the algorithm regardless of how points on the top row connect.

-- Nick
User avatar
Nicholas North
Employee
 
Posts: 627
Joined: Wed Sep 19, 2007 10:38 am
Location: Utah

Re: T spline local refinement

Postby jiangwen84 » Mon Nov 14, 2011 11:58 pm

Figure 9.d. shows the compatible blending function at [s3,t2]. Once t3 has been inserted into the blending function with t knot vector [t0 t1 t2 t4 t5] then we can sum the blending functions together to create a single blending function located at P2. Summing blending functions together to yield a single blending function at each point is required to have a valid mesh.


I still cannot understand how to sum the blending functions to create a single one. Could you explain it again? Thanks.
jiangwen84
Poster
 
Posts: 2
Joined: Tue Nov 01, 2011 10:26 am

Re: T spline local refinement

Postby jiangwen84 » Tue Nov 15, 2011 12:38 pm

Nicholas North wrote:
QLong wrote:Is it possible to have two sets of knot vectors at the same point?
:(


As an intermediate state, yes, logically there may be multiple blending functions (with different knot vectors) at given point at once. Once all of these blending functions have matching knot vectors then we can just sum them together to get a single blending function for that point. This is implied, but not specifically stated in the paper (as far as I can tell).

Lets look at our example:

As you said, the addition of P2 requires that we insert s3 into the blending function at [s4,t2]. The portion of this blending function that is "donated" to P2 has knot vectors [s1 s2 s3 s4 s5 ], [t0 t1 t2 t4 t5].

On the other side of P2 we have the blending function centered at [s2,t2]. After inserting s3, a blending function with knot vectors [s1 s2 s3 s4 s5], [t0 t1 t2 t3 t4] is contributed to the blending function at P2.

So we have two types of blending functions that are donated to the blending function at P2, one with t knot vector [t0 t1 t2 t4 t5] and one with [t0 t1 t2 t3 t4]. To make these compatible, we must insert t3 into the blending function that lacks it. This gives rise to the required extra point at [s3,t3] (via Violation 2).

Figure 9.d. shows the compatible blending function at [s3,t2]. Once t3 has been inserted into the blending function with t knot vector [t0 t1 t2 t4 t5] then we can sum the blending functions together to create a single blending function located at P2. Summing blending functions together to yield a single blending function at each point is required to have a valid mesh.

Hopefully this helps. :)

-- Nick


Nick, could you tell me what will the final single blending functions at P2 looks like after you sum blending functions with t knot vector[t0 t1 t2 t4 t5] and [t0 t1 t2 t3 t4] together. Thanks.
jiangwen84
Poster
 
Posts: 2
Joined: Tue Nov 01, 2011 10:26 am

Re: T spline local refinement

Postby oliver » Tue Nov 22, 2011 11:26 am

Hi
I'm currently trying to implement the local refinement method but having some big issues...

Concernig the 2004 paper (T spline Simplification and Local Refinement) chapter 4.3:
I understood that after adding P2, P1 is guilty of a violation and this is why I have to add [s3,t3] as a new knot...but why do I not have to add [s4,t3] and then [s5,t3]. I know that this would be the "older" algorithm from the paper before. Applying the blending function refinement to [s4,t2] gives me two different local knot vectors in t direction.

So in Fig.9c)+d) if we consider [s3,t2] and [s4,t2] instead of [s2,t2] and [s3,t2] everything is fine without adding [s3,t3]; no violation, like the paper says.
But after adding [s3,t3], [s4,t2] is guilty of a violation, is that correct?

Looking forward to some help, thank you very much.
Oliver
oliver
Poster
 
Posts: 5
Joined: Tue Nov 22, 2011 10:53 am
Location: Germany

Re: T spline local refinement

Postby oliver » Fri Feb 10, 2012 2:00 am

Has been settled...
oliver
Poster
 
Posts: 5
Joined: Tue Nov 22, 2011 10:53 am
Location: Germany

Re: T spline local refinement

Postby Matt Sederberg » Fri Feb 10, 2012 10:21 am

oliver wrote:Has been settled...


Glad to hear. Apologies again that the approval of this post slipped through the cracks.
User avatar
Matt Sederberg
Employee
 
Posts: 1480
Joined: Wed Jul 13, 2005 11:27 am
Location: Provo, UT

Re: T spline local refinement

Postby Hoda » Wed Apr 18, 2012 4:01 am

Hello,
My master thesis is about T spline and I have a question:

I'm studing the master thesis "T spline Simplification" . in section 2.2, How do you evaluate c1 and c2 in (2.6) and (2.7)?
What about table 2.1? Can i use table 2.1 as a rule for evaluate c1 and c2?
Please introduce some references about " Blending function refinement" and "T spline local refinement".

Thank you very much!
Hoda
Hoda
Poster
 
Posts: 3
Joined: Mon Apr 16, 2012 1:16 am

Re: T spline local refinement

Postby Nicholas North » Thu Apr 26, 2012 4:22 pm

Hi Hoda,

Equations 2.6 and 2.7 are just examples for c1 and c2 taken from Figure 2.15. This example corresponds to the row labeled "d2" in the "Split Interval" column of Table 2.1, which just enumerates all of the possibilities for splitting a cubic blending function. So the short answer is Yes: Table 2.1 shows you how to calculate c1 and c2 for a given split of a cubic blending function.

Please not that Chapter 2 is just background fundamentals. Nothing is Chapter 2 of Dave Cardon's thesis is new material.

"Blending function refinement" is just a way of describing knot insertion on a NURBS Basis function. (A "blending function" is just a generic term for a "Basis function" in this case, and "refinement" just means "knot insertion".) This is a classical problem, so it's covered by pretty much any source that covers NURBS. Let me know if you need more help.

As for "T-Spline local refinement", you'll want to read the paper T-Spline Simplification and Local Refinement. You can find links to other technical papers on T-Splines here.

Hope that helps.
-- Nick
User avatar
Nicholas North
Employee
 
Posts: 627
Joined: Wed Sep 19, 2007 10:38 am
Location: Utah

Re: T spline local refinement

Postby Hoda » Fri Apr 27, 2012 7:08 am

Hi Nick,
Thank you very much for your explanation. your answer has been helpful.
I'll study more about T-Spline,and if I have questions, I'll ask you again!
Thank you so much,
Hoda
Hoda
Poster
 
Posts: 3
Joined: Mon Apr 16, 2012 1:16 am

Re: T spline local refinement

Postby TomM » Mon Feb 10, 2014 11:14 am

Hi there,
and thanks a lot for this blog. It was very helpful.

Unfortunately I'm still wondering about the cartesian coordinates of the newly inserted control-point in Figure 9.e-f

Assembling the matrix according to Eq. (15) I only get one entry in the 3rd row, which is c_4^3. That yields P3 = c_4^3 * P4
(assuming P4 is the control point right above P1)
I doubt that's correct, or is it? Am I missing something?

thanks,
Tom
TomM
Poster
 
Posts: 5
Joined: Mon Feb 10, 2014 11:05 am

Re: T spline local refinement

Postby Nicholas North » Mon Feb 10, 2014 12:50 pm

Hi Tom,

No, that's not quite right.

There is one more contribution that the paper neglects to mention, and that is from a point at (s4, t2) that I will call P5. The blending function centered at (s4, t2) was refined to add the knot s3, creating a new blending function at (s3, t2) which *lacks* a knot at t3, so it did not have a violation when the text correctly says "... the rerefinements of the
blending functions centered at (s1, t2), (s4, t2), and (s5, t2) all satisfy
Rule 1." But then control point P3 is added due to a violation of Rule 2 on another blending function. As a result of adding this control point, a new Rule 1 violation is pointed out at P4, but a Rule 1 violation on the blending function from P5 is missed and the paper incorrectly says "Inserting s3 into that knot vector fixes the problem, and there are no further violations of Rule 1." Instead, we must also insert t3 into the t knot vector of the blending function that came from P5.

In the end you should have two blending functions centered at (s3, t3) with non-zero contributions from existing control points:

1. P4 contributes to P3 when s3 is inserted to account for the addition of P3.
2. P5 contributes to P2 when s3 is inserted to account for the addition of P2. Later, when P3 is added, a new Rule 1 violation emerges and t3 must be inserted, resulting in a contribution from P5 to P3.

Note that P1 does *not* contribute to P3 because t3 already existed in P1's t knot vector. However, this leads to the insertion of P3, which causes the two violations above with the blending functions at P4 and P5.

Also, note that, in practice, the insertion of P3 is not the only solution. The plug-in, for example, tends to avoid "L-junctions" and instead would have extended one branch of the L above or to the right to create a T as they are easier to work with. That doesn't really help understand the paper, but just in case you try our software out to see the result.

Hope that helps,
-- Nick
User avatar
Nicholas North
Employee
 
Posts: 627
Joined: Wed Sep 19, 2007 10:38 am
Location: Utah

Re: T spline local refinement

Postby TomM » Tue Feb 11, 2014 2:40 am

Thanks a lot Nick, that helped.

I was not aware that intermediate blending functions must also follow the rules :roll:

the best,
Tom
TomM
Poster
 
Posts: 5
Joined: Mon Feb 10, 2014 11:05 am

Re: T spline local refinement

Postby TomM » Mon Feb 17, 2014 11:34 am

Hi again,

I've implemented violation 1 and 2 successfully, but having troubles computing the correct coefficients for the control points.

Image

The top image shows the T-spline with isoparameter lines before insertion.
The bottom image is after insertion.
The parametric distance for each edge is 0.5 and for the edges left and right of P23 the distance is 0.25.
Note that the images show cartesian space, whereas the isoparametric lines indicate the parametric domain.

The coefficients that pop up during the splitting operations are
c_4^4(0.833333)
c_4^23(0.500000)
c_5^19(0.250000)
c_5^5(1.000000)
c_12^12(1.000000)
c_12^4(0.166667)
c_19^23(0.500000) * c_23^23(0.750000) = c_19^23(0.375000)
c_19^23(0.500000) * c_23^24(0.333333) = c_19^24(0.166667)
c_19^19(0.750000)
c_10^10(0.833333)
c_10^24(0.500000)
c_13^13(1.000000)
c_13^10(0.166667)

Note how the blending function that came from P19 is consecutivly split forming the blending functions of 23 and 24.

This leads to computation of the new control points (Pn) from the old ones (P):
Pn4 = P4 * 0.833333
Pn23 = P4 * 0.500000
Pn19 = P5 * 0.250000
Pn5 = P5 * 1.000000
Pn12 = P12 * 1.000000
Pn4 += P12 * 0.166667
Pn23 += P19 * 0.375000
Pn24 = P19 * 0.166667
Pn19 += P19 * 0.750000
Pn10 = P10 * 0.833333
Pn24 += P10 * 0.500000
Pn13 = P13 * 1.000000
Pn10 += P13 * 0.166667

Note that the coefficients for Pn23 and Pn24 do not sum up to 1. Looking at the bottom image it seems that 23 and 24 are the points that are not correctly computed.

Is there still something missing? :x

Hints warmly welcome.
Tom
TomM
Poster
 
Posts: 5
Joined: Mon Feb 10, 2014 11:05 am

Re: T spline local refinement

Postby Nicholas North » Tue Feb 18, 2014 6:07 pm

Your coefficients appear to be correct to me. (I did them by hand, following your results, and they all agree so long as I count knot intervals off the mesh to be 0.)

I think the issue you are running up against is that the coefficients for Pn23 and Pn24 do not sum to 1:

Pn23 = ( P4 * 0.500000 ) + ( P19 * 0.375000 )
Pn24 = ( P10 * 0.500000 ) + ( P19 * 0.166667 )

This is correct. These points must be weighted to preserve the surface. (This happens to be a so-called "non-standard" T-spline.)

I assume all of your points in the first mesh had a weight of 1. In this case, the weight of Pn23 is 0.875 and the weight of Pn24 is 0.666667. To get the Cartesian location of each point you then have to divide out the weight. Looking at the location of Pn23 and Pn24 it doesn't look like they are in the correct Cartesian location. Pn24, for example, should have an x value that puts it 1/4 of the way between the columns of P7 and P22, and a y value that puts it 3/4 of the way between the rows of P2 and P9. (Assuming even spacing and straight rows and columns to begin with.)

Likewise, when you do calculations of the surface you have to be sure to handle the weights correctly. If you do so, and we didn't make any other mistakes, then the surfaces should match.

-- Nick
User avatar
Nicholas North
Employee
 
Posts: 627
Joined: Wed Sep 19, 2007 10:38 am
Location: Utah

Re: T spline local refinement

Postby TomM » Wed Feb 19, 2014 10:33 am

Thanks a lot Nick, that did the trick. The surfaces are now congruent :mrgreen:

the best,
Tom
TomM
Poster
 
Posts: 5
Joined: Mon Feb 10, 2014 11:05 am

Re: T spline local refinement

Postby Nicholas North » Wed Feb 19, 2014 11:24 am

Very nice!

Also, I just wanted to mention that the refined surface is actually "semi-standard" (not "non-standard" like I said). This means that you have a T-Spline with non-unity weights that produces a polynomial surface. We can see that this is the case because the original surface has weights which are all 1, and the surface is polynomial. The refinement keeps the same surface, so it must still be polynomial, but some of the new control points have weights other than 1. Just a side note, but it is an interesting point.

-- Nick
User avatar
Nicholas North
Employee
 
Posts: 627
Joined: Wed Sep 19, 2007 10:38 am
Location: Utah

Re: T spline local refinement

Postby TomM » Mon Mar 17, 2014 8:15 am

Hi Nick,
after some experiments with the local refinement algorithm I found some cases where it does not work.

That is at situations when for some reason the main diagonal of the upper square of M in Eq. (11) contains zeros. That happens if a control point of the original mesh is only used for a blending function refinement of the knot vector of another control point, and is not refined itself.
Initializing of the upper left square of M as diag(1) and then filling in (or overwriting some ones) with the corresponding c_i^j solves the problem.

cheers,
Tom
TomM
Poster
 
Posts: 5
Joined: Mon Feb 10, 2014 11:05 am

Re: T spline local refinement

Postby Nicholas North » Mon Mar 17, 2014 10:35 am

Thanks for the info Tom. This may be an area of the paper that was missing a few details? Not sure, but thanks for sharing your solution in case it helps others.

-- Nick
User avatar
Nicholas North
Employee
 
Posts: 627
Joined: Wed Sep 19, 2007 10:38 am
Location: Utah


Return to Technology

Who is online

Users browsing this forum: No registered users and 1 guest