Class template that determines the implicit equation det $\left(\mathbf{M}_xX+\mathbf{M}_yY+\mathbf{M}_c\right)=0$ of a planar spline of arbitrary degree and computes intersections with other splines of also arbitrary degree. More...

#include <PlanarSplineImplicitization.h>

Collaboration diagram for model::PlanarSplineImplicitization< polyDegree >:

Public Member Functions
	PlanarSplineImplicitization (const Eigen::Matrix< double, 2, polyCoeff > &coeffs_in)
template<short unsigned int otherPolyDegree>
std::set< std::pair< double, double > >	intersectWith (const Eigen::Matrix< double, 2, otherPolyDegree+1 > &otherCoeffs) const

Public Attributes
const Eigen::Matrix< double, 2, polyCoeff >	coeffs
const MatrixPolyDeg	Mx
const MatrixPolyDeg	My
const MatrixPolyDeg	Mc

Static Public Attributes
static double	compTol
static double	physTol

Detailed Description

template<short unsigned int polyDegree>
class model::PlanarSplineImplicitization< polyDegree >

Class template that determines the implicit equation det $\left(\mathbf{M}_xX+\mathbf{M}_yY+\mathbf{M}_c\right)=0$ of a planar spline of arbitrary degree and computes intersections with other splines of also arbitrary degree.

Adapted from "Algorithms for Intersecting Parametric and Algebraic Curves", Manocha, 1994.

Definition at line 32 of file PlanarSplineImplicitization.h.

Constructor & Destructor Documentation

◆ PlanarSplineImplicitization()

template<short unsigned int polyDegree>

model::PlanarSplineImplicitization< polyDegree >::PlanarSplineImplicitization ( const Eigen::Matrix< double, 2, polyCoeff > & coeffs_in )

inline

Consider a planar spline in explicit form:

\[ \left[\begin{array}{c} X\\ Y \end{array}\right]=\sum_{i=0}^P \left[\begin{array}{c} a_i\\ b_i\\ \end{array}\right]t^i \]

where P is the degree of the spline. In order to derive the corresponding implicit equation of the spline, consider the polynomials:

\[ \begin{array}{l} F(t)=a_it^i-X\\ G(s)=b_is^i-Y \end{array} \]

and observe that each point $(X,Y)$ on the spline makes $F(t_0)$ and $G(s_0)$ vanish for some common root $t_0=s_0$. Now consider the bivariate polynomial:

\[ P(t,s)\frac{F(t)G(s)-F(s)G(t)}{t-s}=s^i\left(M_{xij}X+M_{yij}Y+M_{0ij}\right)t^j \]

If $t_0$ is a common root then $P(t_0,s)=0$ $\forall s$. This is possible only if $\left(M_{xij}X+M_{yij}Y+M_{0ij}\right)t_0^j=0$. Therefore for non-trivial solutions we need:

\[ det\left(\mathbf{M}_xX+\mathbf{M}_yY+\mathbf{M}_c\right)=0 \]

which is the implicit equation of the spline.

We show that $P(t,s)\frac{F(t)G(s)-F(s)G(t)}{t-s}=s^i\left(M_{xij}X+M_{yij}Y+M_{0ij}\right)t^j$ and give expressions for $M_{xij}$, $M_{yij}$ and $M_{cij}$. Substituting the expressions for $F_{t}$ and $G_{s}$:

\[ P(t,s)=X\sum_{j=0}^Pb_j\frac{t^j-s^j}{t-s}+Y\sum_{i=0}^Pa_i\frac{s^i-t^i}{t-s}+\sum_{i=0}^P\sum_{j=0}^P\frac{a_ib_jt^is^j-a_ib_js^it^j}{t-s} \]

Noticing that some terms vanish identically:

\[ P(t,s)=X\sum_{j=1}^Pb_j\frac{t^j-s^j}{t-s}+Y\sum_{i=1}^Pa_i\frac{s^i-t^i}{t-s}+a_0\sum_{j=1}^P\frac{b_js^j-b_jt^j}{t-s} +b_0\sum_{i=1}^P\frac{a_it^i-a_is^i}{t-s}+\sum_{i=1}^P\sum_{j=1}^P\frac{a_ib_jt^is^j-a_ib_js^it^j}{t-s} \]

Now, recalling that $t^j-s^j=(t-s)\sum_{k=0}^{j-1}t^{j-1-k}s^k$, we obtain, for the first term:

\[ X\sum_{j=1}^Pb_j\frac{t^j-s^j}{t-s}=X\sum_{j=1}^Pb_j\sum_{k=0}^{j-1}t^{j-1-k}s^k=X\sum_{l=0}^{P-1}b_{l+1}\sum_{k=0}^{l}t^{l-k}s^k =X\sum_{k=0}^{P-1}\sum_{l=k}^{P-1}b_{l+1}t^{l-k}s^k=X\sum_{k=0}^{P-1}\sum_{m=0}^{P-1-k}b_{m+k+1}t^{m}s^k=X\sum_{k=0}^{P-1}\sum_{m=0}^{P-1}b_{m+k+1}t^{m}s^k \]

where in the last step we used $b_{k}=0$ for $k>N$. Analogously:

\[ a_0\sum_{j=1}^P\frac{b_js^j-b_jt^j}{t-s}=-a_0\sum_{k=0}^{P-1}\sum_{m=0}^{P-1}b_{m+k+1}t^{m}s^k \]

\[ b_0\sum_{i=1}^P\frac{a_it^i-a_is^i}{t-s}=b_0\sum_{k=0}^{P-1}\sum_{m=0}^{P-1}a_{m+k+1}t^{m}s^k \]

\[ P(t,s)=s^i\left(M_{xij}X+M_{yij}Y+M_{0ij}\right)t^j \]

We now give explicit expression for the matrices

\[ \mathbf{M}_x= \left[\begin{array}{llll} b_1&b_2&\ldots&b_n\\ b_2&\ddots&b_n&0\\ \vdots&b_n&0&0\\ b_n&0&0&0 \end{array}\right] \hspace{2cm} M_{xij}= \left\{\begin{array}{ll} b_{i+j+1}& i+j+1\le N\\ 0& i+j+1 > N \end{array}\right. \]

\[ \mathbf{M}_y=- \left[\begin{array}{llll} a_1&a_2&\ldots&a_n\\ a_2&\ddots&a_n&0\\ \vdots&a_n&0&0\\ a_n&0&0&0 \end{array}\right] \hspace{2cm} M_{yij}= \left\{\begin{array}{ll} -a_{i+j+1}& i+j+1\le N\\ 0& i+j+1 > N \end{array}\right. \]

\[ \mathbf{M}_c=-a_0 \left[\begin{array}{llll} b_1&b_2&\ldots&b_n\\ b_2&\ddots&b_n&0\\ \vdots&b_n&0&0\\ b_n&0&0&0 \end{array}\right] +b_0 \left[\begin{array}{llll} a_1&a_2&\ldots&a_n\\ a_2&\ddots&a_n&0\\ \vdots&a_n&0&0\\ a_n&0&0&0 \end{array}\right] \]

PlanarSplineImplicitization: HERE WE SHOULD ASSER THAT THIS SPLINE IS NOT DEGENERATE !!!!!!

Definition at line 78 of file PlanarSplineImplicitization.h.

Member Function Documentation

◆ intersectWith()

template<short unsigned int polyDegree>

template<short unsigned int otherPolyDegree>

std::set< std::pair< double, double > > model::PlanarSplineImplicitization< polyDegree >::intersectWith ( const Eigen::Matrix< double, 2, otherPolyDegree+1 > & otherCoeffs ) const

inline

Computes the intersection points between the implicitized spline and another spline defined by the coefficients otherCoeffs.

Parameters

[in] otherCoeffs the matrix of coefficients of the other spline

\textbf{Theoretical Background}. Assume that the other spline has degree Q. The 2xQ coefficient matrix of the other spline defines the curve:

\[ \left[\begin{array}{c} X\\ Y \end{array}\right]=\sum_{i=0}^Q \left[\begin{array}{c} c_i\\ d_i\\ \end{array}\right]s^i \]

Substituting in the implicit form of the original spline we obtain:

\[ det\left(\mathbf{M}_x\sum_{i=0}^Qc_is^i+\mathbf{M}_y\sum_{i=0}^Qd_is^i+\mathbf{M}_c\right)=0 \]

or, grouping powers of s:

\[ det\left[\left(c_0\mathbf{M}_x+d_0\mathbf{M}_y+\mathbf{M}_c\right)+\sum_{i=1}^Q\left(c_i\mathbf{M}_x+d_i\mathbf{M}_y\right)s^i\right] =det\left[\mathbf{M}_0+\sum_{i=1}^Q\mathbf{M}_is^i\right]=0 \]

where we defined $\mathbf{M}_0=c_0\mathbf{M}_x+d_0\mathbf{M}_y+\mathbf{M}_c$ and $\mathbf{M}_i=c_i\mathbf{M}_x+d_i\mathbf{M}_y$. Intersection points are therefore the roots of the above equation. We now transform the root finding problem into and eigenvalue problem. For this observe that if $det\left[\mathbf{M}_0+\sum_{i=1}^Q\mathbf{M}_is^i\right]=0$ then

\[ \left[\mathbf{M}_0+\sum_{i=1}^Q\mathbf{M}_is^i\right] \mathbf{v}_0=\mathbf{0} \]

has non-trivial solution. We now introduce the vectors $\mathbf{v}_{i-1}=s^{i-1}\mathbf{v}_0$ and obtain:

\[ -\mathbf{M}_0\mathbf{v}_0 = s\sum_{i=1}^Q\mathbf{M}_i\mathbf{v}_{i-1} \]

which, together with the recursive relation for the $\mathbf{v}_i$'s, leads to the generalized eigenvalue problem:

\[ \left[\begin{array}{cccc} -\mathbf{M}_0& \mathbf{0}& \ldots& \mathbf{0}\\ \mathbf{0}& \mathbf{I}& \ldots& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \ddots& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \ldots& \mathbf{I} \end{array}\right] \left[\begin{array}{c} \mathbf{v}_0\\ \mathbf{v}_1\\ \vdots\\ \mathbf{v}_{N-1}\\ \end{array}\right]=s \left[\begin{array}{cccc} \mathbf{M}_1& \mathbf{M}_2& \ldots& \mathbf{M}_N\\ \mathbf{I}& \mathbf{0}& \ldots& \mathbf{0}\\ \mathbf{0}& \mathbf{I}& \ddots& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \mathbf{I}& \mathbf{0} \end{array}\right] \left[\begin{array}{c} \mathbf{v}_0\\ \mathbf{v}_1\\ \vdots\\ \mathbf{v}_{N-1}\\ \end{array}\right] \]

So we obtained the generalized eigenvalue problem:

\[ \mathbf{A}\mathbf{x}=\lambda\mathbf{B}\mathbf{x} \]

where:

\[ \mathbf{A}=\left[\begin{array}{cccc} -\mathbf{M}_0& \mathbf{0}& \ldots& \mathbf{0}\\ \mathbf{0}& \mathbf{I}& \ldots& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \ddots& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \ldots& \mathbf{I} \end{array}\right] \]

is a symmetric matrix (since it's a linear combination of symmetric matrices) and

\[ \mathbf{B}=\left[\begin{array}{cccc} \mathbf{M}_1& \mathbf{M}_2& \ldots& \mathbf{M}_N\\ \mathbf{I}& \mathbf{0}& \ldots& \mathbf{0}\\ \mathbf{0}& \mathbf{I}& \ddots& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \mathbf{I}& \mathbf{0} \end{array}\right] \]

Note that $det(\mathbf{B})=det(\mathbf{M}_N)$ and that

\[ \mathbf{B}^{-1}=\left[\begin{array}{cccc} \mathbf{0}& \mathbf{I}& \ldots& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \mathbf{I}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \mathbf{0}& \mathbf{I}\\ \mathbf{M}_N^{-1}& -\mathbf{M}_N^{-1}\mathbf{M}_1& \ldots& -\mathbf{M}_N^{-1}\mathbf{M}_{N-1} \end{array}\right] \]

Therefore if $\mathbf{M}_N$ one can also solve:

\[ \mathbf{C}\mathbf{x}=\lambda\mathbf{x} \]

where:

\[ \mathbf{C}=\mathbf{B}^{-1}\mathbf{A}=\left[\begin{array}{cccc} \mathbf{0}& \mathbf{I}& \ldots& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \mathbf{I}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \mathbf{0}& \mathbf{I}\\ -\mathbf{M}_N^{-1}\mathbf{M}_0& -\mathbf{M}_N^{-1}\mathbf{M}_1& \ldots& -\mathbf{M}_N^{-1}\mathbf{M}_{N-1} \end{array}\right] \]

Algorithm is: 1- Assemble the generalized eigenvalue problem At=sBt

2- Solve generalized eigenvalue problem At=sBt

4- Return the intersections

Definition at line 214 of file PlanarSplineImplicitization.h.