5 ms·

What the heck...!?! I would really love for someone to explain how something like this happens.

by nkoren 10y ago

artursapek 10y ago
Me too. It's constructing some polynomial, but the rest is lost on me.
- T-hawk 10y ago
  Looks like what you would get if you wrote out all the operations for matrix multiplication? It must be related to expressing the coordinates of the nodes as matrices. I would guess the factors of 3 and 6 arise from derivatives of the cubics: x^3 derives to 3x^2 derives to 6x.
  - wnissen 10y ago
    The intersection of two NURBS (Non-uniform Rational B-Spline) surfaces has a degree into the hundreds. Those are the surface types used in virtually all CAD modelers. For that reason the intersection is not calculated exactly but approximated to a geometric tolerance. It is harder, mathematically and algorithm-wise to calculate the approximation, but much faster to evaluate afterwards. It's amazing what magic lurks below the surface of even something as simple as "find the intersection of two polynomial functions".
    - surement 10y ago
      > NURBS (Non-uniform Rational B-Spline) I believe NURBS stands for Nobody Understands Rational B-Splines [0] :) [0] http://www.springer.com/productFlyer_978-3-540-61545-3.pdf?SGWID=0-0-1297-1491853-0 http://www.springer.com/productFlyer_978-3-540-61545-3.pdf?S... (pdf)
phkahler 10y ago
It happens because the curves are not polynomials in the normal sense. The parameter t that ranges from [0..1] is not the same between the two curves, so it is not equivalent to setting two polynomials equal to each other and solving for x, or t in this case. A solution to the intersection is equivalent to solving for the t parameter of both curves simultaneously and IIRC that ends up having an order that is the product of the orders of the curves (9th order for 2 cubics?). On second thought it's not the product, but it is definitely much higher order. That is the reason people use the matrix representations, once you get a feel for that the complexity tends to get hidden by representing an entire matrix of Nth order polynomials by a letter like B. If anyone is really interested in this stuff and wants to make a major contribution to open source software... First study these and then move on to NURBS, surfaces, and then trimmed NURBS surfaces. These are the core of all CAD software and a clean library for trimmed NURBS is sorely lacking. There are two that I'm aware of, the one in OpenCascade which is a huge ball of mud (but works) and the one in SolveSpace which doesn't scale well and has some other limitations - that is the one I feel is most worthy of someones time.
- Klapaucius 10y ago
  There is GoTools (https://github.com/SINTEF-Geometry/GoTools https://github.com/SINTEF-Geometry/GoTools) and SISL (https://github.com/SINTEF-Geometry/SISL https://github.com/SINTEF-Geometry/SISL). These are open-source geometry libraries for parametric surface modeling, that include NURBS surfaces and intersections and trimmings of such. Intersections are computed approximatively within some prescribed geometrical tolerance, and intersection curves are "marched out".
  - phkahler 10y ago
    Thanks. The links have been forwarded to people who may be interested. BTW they don't explicitly say "trimmed NURBS" but doing boolean operations implies that is the case ;-)
- blt 10y ago
  NLib is the gold standard in closed-source, right?
  - colomon 10y ago
    Disclaimer: I am financially tied to NLib's current distributor. NLib has a lot of sophisticated NURBS math tools. It was literally written by one of the men who wrote The NURBS Book. As far as I know, it doesn't do anything much for trimmed NURBS surfaces, in the sense of a surface trimmed by an arbitrary series of curves. (Might be a tessellation routine for that case?) Basically it is mostly geometry, with only very limited topology support. There are lots of products which provide geometry & topology support: SMLib, SOLIDS++, Acis, and Parasolid come to mind. The first two are built on NLib. I don't think any of them have as sophisticated NURBS geometry tools as NLib does. (Except to the extent that you can call NLib routines directly with the first two.) I'm not aware of any commercial product which directly competes with NLib at all. Which doesn't mean one doesn't exist! I'd be interested if anyone has experience with other libraries.
  - phkahler 10y ago
    No, that would be Parasolid: https://en.wikipedia.org/wiki/Parasolid https://en.wikipedia.org/wiki/Parasolid Look at the list of applications that use it.

What the heck...!?! I would really love for someone to explain how something like this happens.

by nkoren 10y ago

What the heck...!?! I would really love for someone to explain how something like this happens.

artursapek 10y ago

Me too. It's constructing some polynomial, but the rest is lost on me.

T-hawk 10y ago
Looks like what you would get if you wrote out all the operations for matrix multiplication? It must be related to expressing the coordinates of the nodes as matrices. I would guess the factors of 3 and 6 arise from derivatives of the cubics: x^3 derives to 3x^2 derives to 6x.
- wnissen 10y ago
  The intersection of two NURBS (Non-uniform Rational B-Spline) surfaces has a degree into the hundreds. Those are the surface types used in virtually all CAD modelers. For that reason the intersection is not calculated exactly but approximated to a geometric tolerance. It is harder, mathematically and algorithm-wise to calculate the approximation, but much faster to evaluate afterwards. It's amazing what magic lurks below the surface of even something as simple as "find the intersection of two polynomial functions".
  - surement 10y ago
    > NURBS (Non-uniform Rational B-Spline) I believe NURBS stands for Nobody Understands Rational B-Splines [0] :) [0] http://www.springer.com/productFlyer_978-3-540-61545-3.pdf?SGWID=0-0-1297-1491853-0 http://www.springer.com/productFlyer_978-3-540-61545-3.pdf?S... (pdf)

phkahler 10y ago

It happens because the curves are not polynomials in the normal sense. The parameter t that ranges from [0..1] is not the same between the two curves, so it is not equivalent to setting two polynomials equal to each other and solving for x, or t in this case. A solution to the intersection is equivalent to solving for the t parameter of both curves simultaneously and IIRC that ends up having an order that is the product of the orders of the curves (9th order for 2 cubics?). On second thought it's not the product, but it is definitely much higher order. That is the reason people use the matrix representations, once you get a feel for that the complexity tends to get hidden by representing an entire matrix of Nth order polynomials by a letter like B. If anyone is really interested in this stuff and wants to make a major contribution to open source software... First study these and then move on to NURBS, surfaces, and then trimmed NURBS surfaces. These are the core of all CAD software and a clean library for trimmed NURBS is sorely lacking. There are two that I'm aware of, the one in OpenCascade which is a huge ball of mud (but works) and the one in SolveSpace which doesn't scale well and has some other limitations - that is the one I feel is most worthy of someones time.

Klapaucius 10y ago
There is GoTools (https://github.com/SINTEF-Geometry/GoTools https://github.com/SINTEF-Geometry/GoTools) and SISL (https://github.com/SINTEF-Geometry/SISL https://github.com/SINTEF-Geometry/SISL). These are open-source geometry libraries for parametric surface modeling, that include NURBS surfaces and intersections and trimmings of such. Intersections are computed approximatively within some prescribed geometrical tolerance, and intersection curves are "marched out".
- phkahler 10y ago
  Thanks. The links have been forwarded to people who may be interested. BTW they don't explicitly say "trimmed NURBS" but doing boolean operations implies that is the case ;-)
blt 10y ago
NLib is the gold standard in closed-source, right?
- colomon 10y ago
  Disclaimer: I am financially tied to NLib's current distributor. NLib has a lot of sophisticated NURBS math tools. It was literally written by one of the men who wrote The NURBS Book. As far as I know, it doesn't do anything much for trimmed NURBS surfaces, in the sense of a surface trimmed by an arbitrary series of curves. (Might be a tessellation routine for that case?) Basically it is mostly geometry, with only very limited topology support. There are lots of products which provide geometry & topology support: SMLib, SOLIDS++, Acis, and Parasolid come to mind. The first two are built on NLib. I don't think any of them have as sophisticated NURBS geometry tools as NLib does. (Except to the extent that you can call NLib routines directly with the first two.) I'm not aware of any commercial product which directly competes with NLib at all. Which doesn't mean one doesn't exist! I'd be interested if anyone has experience with other libraries.
- phkahler 10y ago
  No, that would be Parasolid: https://en.wikipedia.org/wiki/Parasolid https://en.wikipedia.org/wiki/Parasolid Look at the list of applications that use it.