Jump to content

  • Log In with Google      Sign In   
  • Create Account

Math terms for NURBS


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 cephalo   Members   -  Reputation: 542

Like
0Likes
Like

Posted 27 November 2013 - 02:13 PM

I have an application that uses bezier triangle patches to define a hexagonal game board. I am finding that in certain situations the lack of local control provided by bezier surfaces is creating unacceptable visual artifacts. I am now hoping to experiment with triangular NURBS surfaces to see if I can solve some of these issues.

 

I found a paper that seems rather thorough on the subject here, but I'm have trouble understanding some of the math terminology with my lack of formal math training. Here are a list of things from section 2.2 in that paper that I don't understand.

 

In the first paragraph of section 2.2 it says "Let T = {(delta?)(i) = [r,s,t] | i = (i0,i1,i2) (thing that looks like an E) Z3+". I assume that r,s,t are the triangle vertices and that the index i is a number combo like 300, 030, 003 etc. If anyone can explain some of these symbols I would be grateful. I don't know what the vertical line means either.

 

After that there is a knot sequence, which I understand is what is called a knot vector elsewhere, and is just a sequence of increasing numbers like {0,0,1,1,2,2} etc.

 

Then it says we define a convex hull, and the beta symbol seems to be sort of like the index, I don't know what the 'absolute value' lines mean in this context but that symbol seems to have 3 components that add up to the 'order' of the triangle. I am unsure how the index and this beta symbol should be combined to get the desired number sequence.

 

Then it defines a multivariate simplex spline M(u | Vibeta). The u is a two component coordinate (u,v), but I don't know what the line means.

 

Then it defines the basis function with that line again, then a lower case d, with the triangle vertices without the indices but with the beta thingies in parenthesis, 'lined' against the M(u | Vibeta). What does that line mean anyway? The lower case d is also unexplained.

 

Then we have the unweighted B-spline surface. The Sigma operator is something i always have trouble with, but I interpret this as the sum of every index combo multiplied by the point and the basis function and multiplied again with the sum of all the beta combos multiplied by the point and basis function. However, I do not understand what is meant exactly by Pi,|beta|. Pi would be P300, P030, P003 etc, but I don't know what the beta subscript does to that interpretation.

 

Finally, there are arbitrary weights that can be set, and once I understand the indexing system, I think I understand this part as a weighted mean of the above.

 

If anyone can help me make sense of this I would be super grateful.



Sponsor:

#2 LorenzoGatti   Crossbones+   -  Reputation: 2694

Like
2Likes
Like

Posted 28 November 2013 - 05:36 AM

I have an application that uses bezier triangle patches to define a hexagonal game board. I am finding that in certain situations the lack of local control provided by bezier surfaces is creating unacceptable visual artifacts. I am now hoping to experiment with triangular NURBS surfaces to see if I can solve some of these issues.
 
I found a paper that seems rather thorough on the subject here, but I'm have trouble understanding some of the math terminology with my lack of formal math training. Here are a list of things from section 2.2 in that paper that I don't understand.

Congratulations for picking an egregiously terse and badly explained paper with unusual notation. Don't blame your lack of training too much.

In the first paragraph of section 2.2 it says "Let T = {(delta?)(i) = [r,s,t] | i = (i0,i1,i2) (thing that looks like an E) Z3+". I assume that r,s,t are the triangle vertices and that the index i is a number combo like 300, 030, 003 etc. If anyone can explain some of these symbols I would be grateful. I don't know what the vertical line means either.

T is a set of triangles; i is an index consisting of 3 non-negative integers; r,s and t are vertices of the triangulation.

The vertical bar inside the braces of a set definition, here and everywhere else, means "such that": T is the set of triangles such that their indices are three positive integers, abusing for a stealth definition what should be a notation for predicates.

Other vertical bars include projection onto some subspace (used along with the set-definition vertical bar for Ax in section 2.1) and separation between the main function argument and "parameters" such as spline control points (used for M all over section 2.1).

After that there is a knot sequence, which I understand is what is called a knot vector elsewhere, and is just a sequence of increasing numbers like {0,0,1,1,2,2} etc.

No, the knots are points. For each vertex v in the triangulation, we choose n knots (one of which is v).

Then it says we define a convex hull, and the beta symbol seems to be sort of like the index, I don't know what the 'absolute value' lines mean in this context but that symbol seems to have 3 components that add up to the 'order' of the triangle. I am unsure how the index and this beta symbol should be combined to get the desired number sequence.

Here the bars are a completely superfluous absolute value, and there is no "number sequence": V is the convex hull of n knots associated with the vertices of triangle i.

Then it defines a multivariate simplex spline M(u | Vibeta). The u is a two component coordinate (u,v), but I don't know what the line means.

M is the spline that has a 2D variable u (we are restricting ourselves to a surface, but similar definitions would hold for higher-dimensional or lower-dimensional manifolds) and V as its set of n knots, adapted from section 2.1.

Then it defines the basis function with that line again, then a lower case d, with the triangle vertices without the indices but with the beta thingies in parenthesis, 'lined' against the M(u | Vibeta). What does that line mean anyway? The lower case d is also unexplained.

Actually, d is one of the few simple and commonplace definitions: the area of a triangle with the three given vertices. There are a factor of 2 and an absolute value as an artifact of practical computation (for 3D points computing the area becomes a matrix determinant).

Then we have the unweighted B-spline surface. The Sigma operator is something i always have trouble with, but I interpret this as the sum of every index combo multiplied by the point and the basis function and multiplied again with the sum of all the beta combos multiplied by the point and basis function. However, I do not understand what is meant exactly by Pi,|beta|. Pi would be P300, P030, P003 etc, but I don't know what the beta subscript does to that interpretation.

The sum is over all triangles and over all choices of beta for that triangle, i.e. over all basis functions N for the whole triangulation T. Indexing of the arbitrary control points p matches that of the N functions.

Finally, there are arbitrary weights that can be set, and once I understand the indexing system, I think I understand this part as a weighted mean of the above.

Yes, it's the usual weighting and normalization of any kind of NURBS.

If anyone can help me make sense of this I would be super grateful.

I've found a less general but vastly clearer basic explanation of triangular NURBS surfaces in http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5361 and there should be other better references.
Produci, consuma, crepa

#3 cephalo   Members   -  Reputation: 542

Like
0Likes
Like

Posted 28 November 2013 - 08:30 AM

Thanks so much! I will look at that paper and see if that makes more sense. I have a couple of questions.

 

When you said 'set of triangles', is that triangles within the patch or neighbor triangles?

 

Also, from what you can tell, how similar are triangular nurbs surfaces to rectangular ones? I can probably find better explanations of the rectangular ones, hopefully with pictures, but I wanted to get right into the thing I need.



#4 cephalo   Members   -  Reputation: 542

Like
0Likes
Like

Posted 29 November 2013 - 10:17 AM

These papers would be so much more useful if they had some example code. English is a very ambiguous language for describing mathematical concepts.

 

I'm looking at the paper linked by LorenzoGatti, Triangular NURBS Surface Modeling of Scattered Data and I'm trying to understand the calculation of the basis functions.

 

In section 2, they describe how many knots are needed per vertex and how they can be shared among adjacent triangles, then they take 5 of the 9 knots, and arrange them in 6 configurations which seems to be every possibility of a combination of 5 knots. They say nothing of how the extra knots are discarded or if that matters. Each of the 6 scenarios requires a basis function defined from each 5 knot set K as:

 

B(u|K) = a0B(u|K\v0) + a1B(u|K\v1) + a2B(u|K\v2)

 

'u' is a point in the 2D domain (cartesian or barycentric?) and 'a' is related? to the barycentric coords. In the context of an arbitrary collection of multiple triangles, I don't know what that means. Then there is a bit about how the last term in the above equation can either be 1 if the 'u' point are in the triangle formed by the three vertex knots and 0 if it is not. 

 

I can't begin from this to understand how to put this in code.

 

EDIT: by the way, for some context regarding my intentions, my surface patch is a triangle with 10 control points forming 9 sub-triangles like so:

np2.gif



#5 RobTheBloke   Crossbones+   -  Reputation: 2342

Like
1Likes
Like

Posted 29 November 2013 - 04:53 PM

Take my post with a big pinch of salt, I may be entirely wrong here (and welcome anyone to correct me entirely!)

 

First thing to note: in the paper they are using quadratic splines, not cubic ones. As a result the numbers of their control points and knots won't match the configuration you have above. 

 

I 'think' this is their equivalent of their cox-de-boor (ish) for a triangle. I'm guessing the 3 terms on the right [B(u|K\v0), B(u|K\v1), and B(u|K\v2)] are simply the standard cox-de-boor algorithms? 

 

B(u|K) = a0B(u|K\v0) + a1B(u|K\v1) + a2B(u|K\v2)

 

If a0, a1, and a2 are just the barycentric coordinates of the point being tessellated, then I am assuming the 3 basis functions would look something like this:
 

Untitled
 
where:
 
a0 = u
a1 = v
a2 = 1 - a0 - a1
 
That makes sense to me anyway, since the blend weights in that configuration should still sum to one?
 
Then there is a bit about how the last term in the above equation can either be 1 if the 'u' point are in the triangle formed by the three vertex knots and 0 if it is not. 
 
Which is why it sounds a lot like the cox-de-boor (which always terminates the recursion by returning 0 or 1 depending on whether the point affects a given 'u' value).
 
I think that talk about knot configurations is possibly a red herring. I don't think (buy may be wrong) that it has anything to do with the algorithm, just the knots chosen in the respective directions. Mind you, I might well have accidentally just defined a Tensor-Product spline by accident (I can understand NURBS just fine, but those papers make my head hurt!)

Edited by RobTheBloke, 29 November 2013 - 05:00 PM.


#6 cephalo   Members   -  Reputation: 542

Like
0Likes
Like

Posted 02 December 2013 - 02:36 PM

When you say that the paper is using quadradic splines, you mean that the entirety of the basis function has only to do with the sub triangles, correct? My patch is currently based on a cubic bezier, where moving any point alters the entire patch, but since NURBS offer local control, I can treat the sub triangle basis functions separately correct? What is mean by quadratic and cubic in this case?



#7 cadjunkie   Members   -  Reputation: 1294

Like
0Likes
Like

Posted 03 December 2013 - 08:50 AM

Wow...a paper that combines computational geometry, Lagrangian mechanics, and finite element theory. That's impressive. Anyway, it's hard to decipher what's actually going on through the math. I can't see how the basis functions are constructed from the paper. 

 

Have you tried creating a regular square NURBS surface but making all of the control points along one edge the same point in 3D space? The parameter space would be square, but geometrically it will be triangular. That would be a simpler way to do it, IMHO.



#8 cephalo   Members   -  Reputation: 542

Like
0Likes
Like

Posted 03 December 2013 - 10:22 AM

Well, I'm getting to the point where I think I just have to start implementing to the best of my understanding, and find out how to do it experimentally. Then once I understand how to get the positions, I have to find the partial derivatives to get the normal. Blegh!






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS