SYNAPS (SYmbolic Numeric ApplicationS) » Geometry

Subdivision methods for implicit curves in 3D

In this section, we describe a subdivision method, for computing the topology of a curve $\mathcal{C}$ , defined by two implicit equations $f (x, y, z) = 0$

, where $f, g \in \mathbbm{R}[x, y]$ . It uses the representation of polynomials in the Bernstein basis of a domain $D = [a, b] \times [c, d] \times [e, f] \subset \mathbbm{R}^3$ :

$f (x, y, z) = \sum_{0 \leqslant i \leqslant d_1, 0 \leqslant j \leqslant d_2, 0 \leqslant k \leqslant d_3} c_{i, j} B^i_{d_1} (x ; a, b) B^j_{d_2} (y ; c, d) B^k_{d_3} (z ; e, f)$

where $(B^i_d (x ; u, v))_{i = 0, \ldots, d}$ is the Bernstein basis in degree $d$ , on the interval $[u, v]$ . The subdivision algorithm is also based on a criterion for detecting the regularity of the curve $\mathcal{C}$ , in the domain $D$ .

Implementation

void topology::assign(point_graph<C> & g, MPol<T>& p1, MPol<T>& p2,
         TopSbdCurve3d<C> mth, 
         C x0, C x1, C y0, C y1, C z0, C,z1);

It computes a graph of points g of type topology::point_graph<C>, which is isotopic to the curve defined by the polynomial p1, p2, in the box . The coordinates of the points in g are of type C. The implementation is designed for C=double.

The input coefficients of p are of type T. During the computation, they are rounded to double number types. If the topology in the box can be certified from this approximation, a graph of points connecting the intersection of the curve with the boundary of is computed. Otherwise the box is subdivided into subboxes and the test is applied recursively.

If the curve has singular points, the subdivision will continue until the size of the box is smaller than the precision $\varepsilon$ specified by the class TopSbdCurbe3d<C>. The default value is $10^{- 3}$ .

See synaps/topology/TopSbdCurve3d.h

Example

#include <synaps/arithm/gmp.h>
#include <synaps/topology/TopSbdCurve3d.h>
#include <synaps/base/io/geomview.h>

int main(int argc, char** argv) 
{
  MPol<double> 
    p1("x^4+y^4+z^4-4*x^2-4*y^2*z^2-4*y^2-4*z^2*x^2-4*z^2-4*x^2*y^2+20.7846*x*y*z+1",
       Variables("x y z")),
    p2("4*x^3-8*x-8*x*z^2-8*x*y^2+20.7846*y*z", Variables("x y z"));

  topology::point_graph<double> g;
  topology::assign(g, p1,p2, TopSbdCurve3d<double>(), 
                   -2.1,2.,-2.15,2.1,-2.1,2.2);

  geomview::ostream os("tmp.off");os<<g;os.view();

}

Here is a picture of the corresponding result:

SYNAPS DOCUMENTATION