Paper: NURBS with Extraordinary Points: ... Non-uniform, Rational Subdivision

tjc, any chance of you contributing this bit of mesh magic to blender’s code as another option in addition to catmull-clark and “simple subdiv” under the subsurf modifier? Please, pretty please?

Great work, regardless! Kudos!

@Tjc

Thanks for clarifying theses Nurbs concept

and i find it very interesting - mind you i’m not really in math
but know a little about it

i hope this can be added to Blender as a new tool - look very interesting !

now would you be able to summaryse the difference between the different type of curves we have in blender

Like – Bezier - Poly - Nurbs - and also the other one like Spline and B spline
amd this new type Nurbs with Star-points

but not too deep in math please - more in simple layman terms if possible

Thanks

Happy blendering

Yes thank you. That does clear it up a bit. So to be brutally reductionist it’s NURBS with subdivision-ish bits?

I don’t know that much about NURBS. Most of my experience is with flat poly representatons. Going all the way back to using graph paper and having to type the numbers into Videoscape3D.

Congratulations on getting into SIGGRAPH.

So to be brutally reductionist it’s NURBS with subdivision-ish bits?
Sure. In exactly the same way, actually, that Catmull-Clark subdivision is “uniform bicubic B-splines with subdivision-ish bits”. In fact, in both cases the subdivision-ish bits are made up of an infinite number of B-spline patches, so to be even more reductionist:

• Catmull-Clark subdivision is “uniform bicubic B-splines, with a way of generating smoothly-joining uniform bicubic B-spline patches around extraordinary points”
• The new surfaces are “NURBS, with a way of generating smoothly-joining NURBS patches around extraordinary points”

@RickyBlender, I suspect the Blender documentation wiki would do a better job of explaining your list than I could!

@el_diablo, The new surfaces can handle trims and uv maps in exactly the same way as existing subdivision surfaces (or, in regular parts of the surface, exactly the same way as NURBS). I don’t think Blender has any trimming capabilities for NURBS or subdivision surfaces, but there’s no technical barrier here. UV maps are a way of assigning a parametrization to a surface, and the paper does talk briefly about the impact that our method has on the natural parametrization that comes directly from the surface definition (see Figure 13 in the paper).

Sure. In exactly the same way, actually, that Catmull-Clark subdivision is “uniform bicubic B-splines with subdivision-ish bits”. In fact the subdivision-ish bits are made up of B-spline patches as well, so to be completely reductionist:

• Catmull-Clark surfaces are “uniform bicubic B-splines, with a way of generating smoothly-joining uniform bicubic B-spline patches around extraordinary points”,
• the new surfaces are “NURBS, with a way of generating smoothly-joining NURBS patches around extraordinary points”

@RickyBlender: I suspect the Blender documentation wiki would give a better explanation than I could here!

@el_diablo: Trimming curves can work for subdivision surfaces in almost exactly the same way as NURBS. Most modelling applications don’t support trimming curves for subdivision, but there’s no thereotical challenge here. As for UV mapping, that works in just the same way as current subdivision surfaces. In fact UV mapping is a way of allocating a 2D “parametrization” to the surface, and we do talk briefly in the paper (see Figure 13) about the impact that our method can have on the “natural parametrization” that comes from the definition of the surface (i.e. without having to do any UV unwrapping).

Right, okay. I can’t help thinking that part of the confusion here is caused by how one usually interacts with these surfaces when modelling. That and a lack of maths.

Subdivision surfaces, especially the way they’re usually implemented, just look like a way of dividing up the geometry of a poly mesh. If you had the time you could build them manually. I don’t think there is an awareness that you’re actually dealing with curves. You only ever experience it as approximating a curve, the more you divide it up. If when you added subdivision to a cube, BAM, a sphere popped up the link would be clear.

As for patches, hmm, well the NURBS guys talk about them a lot. I thought they referred to joining separate curves. Looking at Wikipedia’s description of the Catmull-Clark recursive evaluation algorithm there isn’t any mention of taking different action at extraordinary points. So I assume the algorithm inherently produces these patches?:spin:

thats because the current sub-surf modifier in blender does not really turn your poly mesh into a full sub-division surface…

At least from what I’ve understood anyway’s.

Blender, Lightwave, Modo, or C4D all use what we call Subdivision Surfaces with Catmull Clark.

Maya on the flipside has a different subD system which works different. Instead of global subdivision
like in Blender with levels you can make local subdivision of just a face or selected faces.
This gives locally more points to work with.

This system works actually similar to multires because you can switch forward and backwards in the
levels. However Mayas SDS system only I think has 3 levels. However they ALWAYS result in 100% smooth surfaces.

What is Subsurf in Blender is something like SmoothProxy in Maya.
Maybe this is also why Maya converts SDS right into NURBS.

I could be wrong (often am) but that sounds like just a more sophisticated way of controling it.

However they ALWAYS result in 100% smooth surfaces.
Right. As far as I’m aware Maya uses Exact Evaluation. Whereas Catmull-Clark is a recursive algorithm (been looking stuff up). Blender’s implementation requires you to set the level of recursion. It’s that which disguises the fact you’re dealing with curves.

What I was actually confused about is the patches bit.

have you seen a good definition of patches?

like to see it and better understand it !

Thanks

Ah, well er, no not really.

If you check Wikipedia’s Nurbs entry, then you get the definition you get from the Nurbs modelling guys. It’s a separately modelled piece of an object that you want joined together. It goes on to discuss different types of join.

This is all very well but I can’t reconcile it with CC subdivision. But if you look at this definition from a 3D scanning company you get something that makes more sense. Only the definition itself is poorly worded and ambiguous in meaning.

It states that this use is specific to them but it’s not clear if that just refers to that paragraph or the whole thing. It then goes on to say that Patch doesn’t mean the same in CAD and CGI. Does that mean that CAD uses a different definition to CGI, or both use a different one to the one they’ve just defined?

So still confused.

ok i’v seen thsi wiki definition
and still not clear if the pieces to joint have the same qty of isolines for instance
or what about dimensions can it be like doing a bottle neck ?

it’s still a vague definition - it’s 2 pieces but what are the limitations if any ?

Thanks

In the context of Catmull-Clark subdivision, there is a B-spline patch corresponding to almost every quadrilateral face. These all join together smoothly (“C2”, or “with curvature continuity”).

The exception is the faces next to extraordinary points. Here subdivision works by introducing a new ring of B-spline patches at every subdivision step. These all join smoothly to the patches in the regular part of the surface, and also to each other.

I’ll try to explain how this works: it’ll be easier to understand if you draw yourself a diagram which includes five (say) quadrilateral faces that all meet at one point. Now at each subdivision step, imagine taking each face which lies next to an extraordinary point and splitting it into four. Three of the four quarters in each face are no longer adjacent to an extraordinary point. So these faces will now become B-spline patches. At each subdivision step, a ring occupying roughly three quarters of the faces next to an extraordinary point gets filled with smoothly-joining B-spline surface.

So the ‘hole’ surrounding an extraordinary point shrinks to about a quarter of the size at each subdivision step. Now imagine iterating the same process a few times. The hole quickly becomes very small. This is how the mathematics of subdivision surfaces works, for both Catmull-Clark and the new surfaces.

that’s beginning to give a good description

please can you show a little dwg of this

seems very intersting - annd pic is worth 1000 words

Thanks & appy blendering

I’ll take a crack at clearing up some confusion (hopefully I won’t add to it):

1. Subdivision surfaces are not just polygons subdivided a whole bunch. Subdivision surfaces are actually the surface you get if you subdivide an infinite number of times, leading to a genuinely smooth surface. But like other smooth surface representations (including nurbs) they generally have to be tessellated into polygons. Subdivision surfaces are convenient to tessellate because of how they are calculated: the “infinite” subdividing can simply be stopped early (say at 3 itterations), and the result is a reasonable polygonal approximation of the surface. With NURBS you would have to tessellate more directly.

2. Catmul clark subdivision surfaces are actually equivelant to bezier surfaces, if I recall correctly, excepting that subd surfaces can have arbitrary cage toplogy. But basically they’re just a different way to calculate bezier.

3. It then follows that NURBS would likely also be possible to calculate using a subdivision surface scheme, just using different subdivision rules, bringing NURBS the benefits of subdivision modeling (or subdivision modeling the benefits of NURBS… same thing, really). But of course the maths are very difficult.

Many thanks to Tom and his colleagues for doing the hard work to figure out how to do it!

Thanks Cessen, for bringing in a voice of educated reason on this topic! I have found your consice explanations of this confusing topic in other similar threads to be very helpful, as is this one. Any chance that you’re willing to drop this bit of juicy geometry deliciousness into blender’s codebase as a supplement to the subdiv modifier? I don’t know if you’re one of blender’s devs, but maybe you know of one who’s in need of a lil’ ol’ project to spice up 2.5 even further? :yes: ?

@Cessen - Thanks for that. But whenever I think I’m getting a grasp on this someone pops up to say something which causes more confusion (but I’ll ignore the NURBs integration thread for now).

Okay one more time. Catmull-Clark sub-division; each control face defines a B-spline patch; unless it is part of an extraordinary point. Each time you subdivide the geometry you get closer to the actual curve. At infinite subdivison you reach the curve.

These sub-division NURBs define actual NURB curves, and in a simillar way the geometry gets closer to the actual curve the more you sub-divide it.

@tjc

Right, extraordinary points. Neither system can actually deal with them. So instead smaller curve patches are produced with each sub-dividion, shrinking the problem point, indefinitly postponing having to deal with it.

I’m a bit unclear here. Is the problem with extraordinary points constructing the geometry? Or is it in constructing the curves mathematically? I guess what I’m saying is when you construct C.C. Subdiv. extraoridnary points in Blender the polys seem to meet up and don’t have the apperance of a hole. Is the problem hidden?

Well, that’s how they deal with them :). But yes, you’ve got it.

Mathematically, the problem is that the underlying smooth surface type (for Catmull-Clark, it’s uniform bicubic B-splines) needs a certain number of points (for Catmull-Clark, a 4x4 grid of 16 points) in order to be able to define any single patch. Next to extraordinary points the rectangular grid has broken down, so we haven’t got the required number of points to create a surface patch (or “don’t know where to get them from”, if that’s easier to think about). Subdivision gets around that problem by creating new points.

Yes, in effect. Cessen’s post was pretty accurate (the only real quibble I have is about the distinction between Bezier and B-spline surfaces, but leaving that aside), so I’ll quote him:

In Blender, you don’t see the hole because you’re not looking at the “infinitely subdivided” smooth surface. You’re looking at a control mesh that has been subdivided a few times; and the control mesh doesn’t have a hole around extraordinary points. If, instead, Blender drew “the smooth surface it could create without subdividing”, you’d see the hole. Then if we subdivided the control mesh, you’d also see the hole shrinking.

To bring this full circle, I’ve noticed that some other threads talk about Maya’s subdivision surfaces, which always look smooth. That’s because Maya doesn’t render the control mesh (as Blender does). Maya’s evaluation is closer to the “B-spline surface with holes” concept that I’ve just been describing. The difference is that Maya also uses a large number of subdivision steps to fill in the hole. They keep the computation efficient using a technique called exact evaluation (which is mentioned in our paper in the caption to Figure 12, and was originally introduced by Jos Stam).

A-ha! I think I have got it. Well the basic outline anyway.

Well, quite :). Very Zen.

Then if we subdivided the control mesh, you’d also see the hole shrinking.
The poles have holes. I’m going to think of this every time I see one.

They keep the computation efficient using a technique called exact evaluation (which is mentioned in our paper in the caption to Figure 12, and was originally introduced by Jos Stam).