NURBS

[MasseGuillaume]

I have some spare time.

@mrdoob is it something you want in three.js ?

On CPU: http://cgit.freedesktop.org/mesa/mesa/tree/src/glu/sgi/libnurbs/interface/glinterface.cc?h=8.0 ( restrictive license ) https://svn.blender.org/svnroot/bf-blender/trunk/blender/source/blender/blenkernel/intern/curve.c ( GPL ) http://www.nar-associates.com/nurbs/c_code.html ( copyright, non commercial reuse ok )

On GPU: http://kingkong.me.berkeley.edu/~adarsh/Papers/CAD09.pdf 10 X faster but high setup cost

[mrdoob]

Oh, how would this affect the current code?

[MasseGuillaume]

There is already Spline in the core package ( a Quadric Spline ). I will create curves and surfaces in the extra package.

strikeout: I'm currently implementing Bezier curve and surface just to get started.

I will push Bezier curve and surface with exemples. Let's take small step.

[alteredq]

Could you reimplement it so that we would have MIT License (like everything else in the lib)?

NURBs are definitely interesting, especially in the context of WebGL where you need to care about asset sizes.

[MasseGuillaume]

@mrdoob I found a Cubic and Quadratic Bezier implementation in Extra/Core/Curve.js. I think those clases are missing exemples.

@alteredq do you prefer the cpu or the gpu implementation ? Do we need trimmed NURBS ?

[alteredq]

How does this GPU method work?

Is it something like in GLSL sandbox - a single screen facing quad and then everything is done just in fragment shader?

Or do you send to GPU some highly tessellated grid mesh and then you displace vertices?

First option would be of very limited use, second one would be interesting if surface was supposed to be animated. Otherwise static mesh generation on JS side seems to be more useful (and usable also for other renderers).

[MasseGuillaume]

@alteredq I contacted the author M. Adarsh Krishnamurthy for source code. This is what I understand from their algorithm:

Most of the action take place in the texture buffer.

Take a look at the algorithm schema: http://bit.ly/JomL6q

Nurbs Surface:

Input:

• u knot vector
• v knot vector
• control points
  • x
  • y
  • z
  • weight
• trim curve ( optionnal = no trim )
• order ( optionnal = 4 )

Parameters

• u
• v

Algorithm:

1. Knot array texture
   • for u knot vector
   • a knot array texture has the value of u in the first column;
   • it has dimensions of width 2 * order + 1 and height equal to the number of control points.
   • The remaining columns have the 2 * order knot values for the evaluation of the corresponding non-zero basis function values for a particular control point
   • same for v knot vector
2. Basis functions
   • First order: step function
     • create a texture with [ 0 ( order - 1 times ) 1 0 ] on all lines for all control points
     • store the texture tex1 in the gpu texture buffer
   • Second order
     • from tex1 and knot array texture using fragment program 1 implementing B-spline basis ( equation 2)
     • render result in another texture: tex2
   • k-order
     • use tex1 and tex2 to render until k = order function is computed
     • last column will always be 0
3. Curve evaluation
   • Create an array of width order and x, y, z and weight in channels
   • Multiply that array with basis function using fragment program 2
   • sum the result of this operation using fragment program 3
   • same for v
4. Curve trimming
   • with alpha blending using fragment program 4

[MasseGuillaume]

@alteredq yes take a look at chapter 6.1

Or do you send to GPU some highly tessellated grid mesh and then you displace vertices?

[sntx]

Hello, I have actually been working for some months on implementing NURBS for three.js for a school project. So far I got non uniform bsplines curves and surfaces working. I haven't included a weight vector yet so rational curves and surfaces are not possible. I have been fixing some errors lateley but I think that everything will be working pretty well by May 2 (the submission date of my project). It's all CPU based though.

Here is an application that uses the classes: http://lirius.org/proj03/ (note: I'm constantly updating this so it might not be working some times...)

I will clean up my code a little bit and then uploaded it to github.

[sntx]

Some instructions and notes on the application:

1) When WebGL is enabled shapes are not being updated correctly (TODO) 2) Click on 'Load / Save' 3) click on the surfaces or the curves folder and then click on some of the files inside 4) Note: rotation surfaces are not working very well right now

[MasseGuillaume]

@sntx great job. maybe we can work together to implement the gpu version.

[sntx]

@MasseGuillaume sounds very interesting, I don't have much experience with glsl though, but I can learn, after all the math part will be pretty similar.

I just remembered now that my professor actually implemented bezier surfaces construction inside the tesselletor in OpenGL 4, I will ask him about it and get back to you.

Also, NURBS construction in the CPU is still absent in three.js, isn't it?

[alteredq]

Cool, cool. CPU version would be useful. You may also want to check with @zz85, he is our procedural geometries guru ;)

I just remembered now that my professor actually implemented bezier surfaces construction inside the tesselletor in OpenGL 4, I will ask him about it and get back to you.

There are no geometry shaders / GPU tessellations in WebGL unfortunately :S

That's kinda why I was asking about how that paper was implemented as we would need to pre-tessellate mesh on JS side.

[sntx]

So we would need a CPU NURBS construction scheme for non-WebGL rendering and if WebGL is available, we would need a CPU/GPU construction scheme, is that right?

[alteredq]

More like:

• universal CPU side NURBSGeometry (that would be for static geometries both with and without WebGL, exactly like our other procedural geometries)
• and then optional, if you would like to animate / modify NURBs in runtime, some other hybrid CPU / GPU solution (yet to be figured out how to exactly implement it, maybe some new type of geometry for generating static tessellation / connectivity and then special ShaderMaterial for displacement).

[zz85]

erm... correction, mr.noob the graphics noob here =P

could anyone please tell me what do people use nurbs these days for?

any quick glance at the paper -> "evaluation timings show more than 40 times improvement over evaluation on the CPU for large inputs".

so i guess that's if you have a huge nurbs mesh to calculate in realtime very quickly, then a GPU version might accelerate the calculations, but to start off with a JS/CPU version should be fine for a start. somedays we should do calculate our spline calculations in the shaders, but right now CPU has been sufficient for me.

and i haven't worked on nurbs yet. see if you could use parametric surfaces for that and give it a go :)

[mrdoob]

could anyone please tell me what do people use nurbs these days for?

I guess it can be a way of saving meshes in a pretty compressed way, no?

[alteredq]

I guess it can be a way of saving meshes in a pretty compressed way, no?

That's what I was after in my first comment :)

I think in these recent demoscene unvelings somebody mentioned they used either NURBs or something similar for their ultra-small demos.

Their pipeline was such that designers did everything in their tool and exported only parameters for procedural shapes so that real meshes existed only in runtime.

[zz85]

just noticed the front of the threads too.

@MasseGuillaume example: http://mrdoob.github.com/three.js/examples/webgl_geometry_shapes.html

another noob qn: what are the difference between patches (http://prideout.net/blog/?p=46) and nurbs?

[MasseGuillaume]

@zz85

1. I think a GPU version would be like 2 order of magniture faster that js/cpu version. The author was comparing with openGL.
2. if you take a look at Chapter 6.1 we can generate a mesh to displace with the level of detail required. One texture buffer store the exact awnser to nurbs equation.

Glad you guys like the idea. I hope the author will provide some code. If it's not the case, it would be a one month task: understand more the algo and the cpu-gpu communication, 5 shader programs, integration with THREE, etc

Meanwhile we will have @sntx cpu implementation.

[sntx]

I just created a repository with what I have so far: https://github.com/sntx/NURBSForTHREE also, I got an example running at http://lirius.org/proj03/ I'll include the example later on

[sntx]

I am working on creating a NURBSGeometry class right now, how do geometry objects work in three.js? I'm looking at THREE.SphereGeometry and trying to mimic what's happening there.

1) In what order do I store vertices? (in this.vertices...) 2) What about faces and faceVertexUvs... 3) What's the bare minimum I need to be able to render my geometry?

Thanks

[zz85]

1. don't think it matters, but faces are follows the vertices indices clockwise, so it make sense to order vertices that fashion
2. faces are required. faceVertexUvs are for UVs.
3. the minimal to render a geometry is to have vertices and faces.

[marcbourlon]

Hi guys, my two cents. Back in 1993 (ouch!), I decided to create a 3D modeler in NURBS for my Master project. It was in GFA Basic on Atari Falcon. Why does it matter? Because it was a 68030 CPU @16Mhz, and the basic was interpreted, not compiled. I let you imagine speed issues... I kept two versions of the code, which dealt with NURBS patches, and allowed creation of several patches which joined together well. The first version is simple implementation of the formulas of 2D NURBS, extended to deal with patches (using the interpolated points of the first dimension as control points for the second dimension curves), and deals with, as far as I remember, NURBS of any degree. The second version is highly optimized (about 6 times faster): I considered that quadratic degree NURBS were nice enough to look at, and rewrote the calculations with as much integer calculations as possible. I think you guys already have enough to deal with, but in case, just know that the code (though in GFA Basic, it's not spaghetti basic, it was, say, close to some Turbo Pascal, functional, one instruction per line, no line number, etc.) is yours if you're interested. Or if you have questions and are interested in some of the things I described, please ask. Best. Note: it doesn't deal with textures.

[mrdoob]

@marcbourlon did you forgot to add a link to the code? :S

[marcbourlon]

Hey MrDoob. No, no, but I have it only in this GFA Basic flavor right now. In needed to know if you guys were interested, in which case I would rewrite it in js before posting. I guess this question means: "We are interested" :-D Ok, doing asap ;-)

[zz85]

i've starting to read up a little about nurbs...

http://docs.happycoders.org/orgadoc/graphics/nurbs/article-en.pdf

and watching a little videos on them...

http://www.youtube.com/watch?v=tv40aawZAY4

now for more noob questions - what is the typical workflow of using nurbs? nurbs usage seems a little complex even with good GUI - what would it be done in pure code? how then would the API for nurbs in threejs be?

[zz85]

so miaumiau did a pretty good nurbs demo in flash/as3. i'm kind of assuming that's what NurbsGeometry is going to do here, or more? http://www.miaumiau.cat/2010/04/nurbs-in-flash-part-2/

[sntx]

Hi Everyone,

It seems that you overlooked my previous message, I already completed a working NURBS implementations for three.js: https://github.com/sntx/NURBSForTHREE

also, I got an example running at http://lirius.org/proj03/

@mrdoob Do you think this could be merged with three.js once all the errors are fixed and evaluation is optimized?

Notes for NURBSForTHREE:

1) NURBS surface geometry only draws vertices for now, need to draw faces and compute normals 2) NURBS surface evaluation is not optimized yet

Notes for http://lirius.org/proj03/

1) Click on 'Load / Save' , then click on 'surfaces' folder , then click on one of the files 2) The surfaces and curves' control points can then be interactively moved by clicking and dragging. 3) Note that dragging is really not working well at all right now... TODO

Overall Notes 1) the code is filled with TODO's so it should be easy to know what to do if you want to contribute

[marcbourlon]

Hi @sntx ! I didn't overlook, which is why I initially said that I thought you were already with everything needed ;-) But since my optimization was not bad (at that time, maye calculation loops working with integer values), may this could make you guys interested. This said, I just went to see your demo, and... not sure you need faster version! Good job! I'll definitely check the TODO's :-)

[zz85]

@sntx opps. didn't see that. nice work to start off with. just one note: we no longer require new THREE.Vertex for r49 :)

[marcbourlon]

Hi! Well... Not sure I can optimize anything here: as I said, my biggest optimization at that time was in specializing the algorithm for quadratic NURBS, thus making me able to move some calculations to integer, which was way faster than float at that time. Not sure it still matters, especially in JavaScript? Another thing I noticed while reading my source comments, was that I duplicated the code for the two dimensions of the patch, this specialization allowing me to save a multiplication which led to a division in the other dimension, in the weight calculation. Does it ring any bell for you?

[marcbourlon]

Hi @sntx ! I just replied to your emails, and described one of the optimizations I did which may apply to your code. Cheers.

[sntx]

Hi @marcbourlon What you are saying about weights seems to relate to the idea of storing the weights as an extra dimension. This is usually done to simplify the evaluation and representation of rational b-splines. Rational b-splines associate a weight to each control point, this weight is stored in the extra dimension and the coordinates are represented as divided by the weight.

For example:

Let's say one control point is at (x, y, z) = (1, 1, 2) and has a weight of w = 0.7

Then, this point could be represented as: (wx, wy, wz, w) = (0.7, 0.7, 1.4, 0.7) = (x, y, z, 1) * w

This whole thing relates to the idea of projective spaces, we use n+1 dimensions to represent n dimensions; a quite interesting concept and ideal theme for a sci-fi movie. Does this ring any bells?

[marcbourlon]

Hello, yes, a bit let me translate/develop a bit my past comments (take your own code almost 20 years later and you understand all these 'good coding' rules):

• from memory, I had to "invent" how to do 3D patches in NURBS, which means that I may have done it no "the right way". But as far as I remember, I first sampled the control curves of the first dimension (say, the 'x' axis of the patch), and I used the sampled points as control points for curves of the 'y' axis. To try to make myself clear, say I have a 2x2 patch, and I sample 5 dots per segment (a segment between two control points), I would first generate 3 lines of 10 points along the x axis of my patch. Then, I have now 10 sets of control points to now iterate my real dots for my patch (final triangles vertices). Is it how you do? (I remember I couldn't find any other way of doing at that time, so let's hope you do the same)
• if yes, then the first calculation (if done with traditional NURBS algo) will divide each sampled points coordinate by the total of weights used to calculate it. But in the second calculation, always with traditional formula, you will multiply these coordinates by the weight. By splitting calculations into two separate functions, you can get rid of division in the first one, multiplication in the second.
• I precalculated the Nik(t) by using the "translation property of the splines", meaning we only need to calculate Ni0(t) (I hope you understand this sentence better than me now. I guess I understood it when I wrote it :-D) This has the advantage of being able to use integer loop index, because the floating point character of it is used only for this Nik calculation, which is therefore obsolete thanks to precalc. And it also allows to skip one step (when loop index is 0).
• I used the property of support for the splines to not calculate zero values (I saw that you do this in your code, as you wrote in comments)

Anything you can use from here?

[hedral]

I only just saw this thread. Some words of encouragement and my 2 cents worth in an ideal world, as a user of various surface modeling apps. You guys will know this stuff but its not yet captured here in one place...

@zz85 asked "could anyone please tell me what do people use nurbs these days for?"

• accurate surface modeling of free-form shapes, often leading to manufactured parts
• complex surfaces easily described with small data sets (@alteredq 's "small assets" comment)
• nurbs is an "industry standard", so identical surfaces can be generated from nurbs data, by a variety of software and platforms
• polygons are calculated from nurbs surfaces only for rendering or SLA rapid prototypes or outputing models for gaming, with choice of subdivisions (resolution)
• nurbs allows precise x,y,z calculation of any point anywhere on the surface, therefore potential for trimming intersecting surfaces cleanly (already mentioned earlier)
• complex patches generated from a set of 3 or 4 curve edges using implied tangency, for example
• possibility of control of smooth, perfect tangency across adjacent surface patches
• and more...

Some of the above may be better handled outside the package, and baby steps to start with.

I'm working on a 3D modeling app project using Three.js, so happy to contribute as an "end user" of any NURBS package. I've limited ability to help technically, still a keen learner of javascript.

Great work.

[marcbourlon]

Yep, I loved working with NURBS 20 years ago, and wanted to do more. I never understood why video games make not more heavy use of them, considering they have to deal with LOD... Btw, no news from the guy who was implementing this :-(

Marc

Le 22 mai 2012 à 00:20, hedral reply@reply.github.com a écrit :

I only just saw this thread. Some words of encouragement and my 2 cents worth in an ideal world, as a user of various surface modeling apps. You guys will know this stuff but its not yet captured here in one place...

@zz85 asked "could anyone please tell me what do people use nurbs these days for?"

• accurate surface modeling of free-form shapes, often leading to manufactured parts
• complex surfaces easily described with small data sets (@alteredq 's "small assets" comment)
• nurbs is an "industry standard", so identical surfaces can be generated from nurbs data, by a variety of software and platforms
• polygons are calculated from nurbs surfaces only for rendering or SLA rapid prototypes or outputing models for gaming, with choice of subdivisions (resolution)
• nurbs allows precise x,y,z calculation of any point anywhere on the surface, therefore potential for trimming intersecting surfaces cleanly (already mentioned earlier)
• complex patches generated from a set of 3 or 4 curve edges using implied tangency, for example
• possibility of control of smooth, perfect tangency across adjacent surface patches
• and more...

Some of the above may be better handled outside the package, and baby steps to start with.

I'm working on a 3D modeling app project using Three.js, so happy to contribute as an "end user" of any NURBS package. I've limited ability to help technically, still a keen learner of javascript.

Great work.

---

Reply to this email directly or view it on GitHub: https://github.com/mrdoob/three.js/issues/1799#issuecomment-5835313

[sntx]

Hi everyone,

Some updates, ideas and collaboration request:

I recently got an optimal implementation of NURBS from a computer graphics guru. The implementation is in C++. My implementation "NURBSForTHREE" is somewhat optimal too and fully functional, however, it lacks consistency since I wrote it at the same time I was learning NURBS and THREE.js

Anybody wants to help finishing implementing NURBSForTHREE "https://github.com/sntx/NURBSForTHREE"? I'm not as experienced as you folks when it comes to THREE.js and probably JavaScript, so your collaboration will be greatly welcomed.

Here is a roadmap of what needs to be done:

1) Create a simple set of examples with current implementation.

1.1) Display a curve
1.2) Display a surface

2) Create an example similar to the one @zz85 posted: http://www.miaumiau.cat/2010/04/nurbs-in-flash-part-2/

3) Ideas for other examples or applications?

4) Once we have some examples working, we can move on and code the optimal implementation.

[sntx]

@marcbourlon Your points make sense, I ran into several issues when implementing NURBS. They main thing when optimizing NURBS evaluation is to only evaluate non-zero basis functions, I think this is what you were doing when you say: I precalculated the Nik(t) by using the "translation property of the splines", meaning we only need to calculate Ni0(t) (I hope you understand this sentence better than me now.

@zz85 What 3D modeling app are you working on? Let me know if you want to use NURBSForTHREE and maybe I can help out with the app you are working on also.

[hedral]

@sntx. That was me, hedral, working on the modeling app. Its an all javascript web app, very basic, and is very much in hobby mode. I'll post a link here shortly. I'm toying with your NURBSForTHREE on the side. Looks nice. I might take up your offer for help if I decide to add it to my project.

Also, I'm working on a draft curve example for NURBSForTHREE. More shortly.

I can look at a surface example in time.

[sntx]

@hedral I'm also working on a simple curve example as we speak :) What kind of modeling app are you working on? CSG?

[sntx]

I just added a NURBSForTHREE example for creating curves at: http://sntx.github.com/NURBSForTHREE/examples/curve_different_orders/index.html and here: https://github.com/sntx/NURBSForTHREE/tree/master/examples/curve_different_orders

[hedral]

@sntx That example is very nice. Much slicker than mine.

I've started more simply, mostly because I needed to get my head around NURBS theory again. This is pretty simple, but verbose and not particularly optimised.

http://www.shapeograph.com/shapeograph/Three_js/NURBSForTHREE/examples/NURBSForTHREE_2D_Curve_Example.html

Re. your earlier question, no not CSG. Its polygon primitives and polygon surface/object imported via JSON. All very Three.js.

[sntx]

@hedral You're example is great! would you mind adding it to NURBSForThree?

[hedral]

@sntx I just forked your NURBSForTHREE project, added my NURBS curve example at...

https://github.com/hedral/NURBSForTHREE/tree/master/examples/curve_different_orders_2

...and made a Pull request.

[theo-armour]

@sntx: Your demos on Lirius are smoking hot fast. I find that the way you enable moving vertices in 3D very intuitive. It might be nice to have a 3D axis icon pop up so I can see what axis I'm really moving on.

@zz85 asked "could anyone please tell me what do people use nurbs these days for?"

http://en.wikipedia.org/wiki/Non-uniform_rational_B-spline

See: http://www.rhino3d.com/ - first item highlighted in red is NURBS support. See: http://usa.autodesk.com/alias/features/ - see first item "new skin tool" See: http://usa.autodesk.com/adsk/servlet/pc/item?siteID=123112&id=18361769 - about half way down

I can't find a direct reference on the Solidworks site, but my guess is that it has NURBS as well

In other words, NURBS is the industry standard for contorted and warped things.

So if you ever have to design a holy grail, you would probably want to store the model in NURBS.

@everybody: woot! woot! on this topic.

[marcbourlon]

@sntx: no, I was not speaking about zero coefficient. My memory is not fully clear about it, but I used the fact that NURBS keep their properties by any affine transformations, so for translations. Based on this, if I remember well, I realized that we could boil down most coefficient calculations to a very small set, and reuse it at will, with minimal calculations.

[Rendolf]

Hi, Could some give an example code to create NURBS surface?

[bhouston]

I don't think NURBS was ever included in Three.js. I would suggest for now creating NURBS in a separate package, turning it into triangles and importing it as a PolyMesh/TriangleMesh into Three.js.

[Rendolf]

https://github.com/hedral/NURBSForTHREE/tree/master/examples/curve_different_orders_2 You can find here examples of creating curves, so NURBS are included but no officially.

[bhouston]

I believe that was never merged into Three.js