triangle module

This is a collection of procedures for performing computations on a Bézier triangle.

Note

In most of the procedures below both the number of nodes \(N\) and the degree \(d\) of a Bézier triangle are provided. It is redundant to require both as arguments since \(N = \binom{d + 2}{2}\). However, both are provided as arguments to avoid unnecessary re-computation, i.e. we expect the caller to know both \(N\) and \(d\).

Procedures

void BEZ_compute_area(const int *num_edges, const int *sizes, const double *const *nodes_pointers, double *area, bool *not_implemented)

This computes the area of a curved polygon in \(\mathbf{R}^2\) via Green’s theorem. In order to do this, it assumes that the edges

  • form a closed loop

  • have no intersections with another edge (including self)

  • are oriented in the direction of the exterior

Parameters:
  • num_edges (const int*) – [Input] The number of edges \(N\) that bound the curved polygon.

  • sizes (const int*) – [Input] An array of the size (i.e. the number of nodes) of each of the \(N\) edges.

  • nodes_pointers (const double *const*) – [Input] An array of \(N\) pointers. Pointer \(j\) points to the start of the edge \(E_j\) along the boundary of the curved polygon. (This is a const array of const pointers, i.e. the double** pointer array cannot be modified and the underlying double* arrays pointed to by each element cannot be modified.)

  • area (double*) – [Output] The computed area of the curved polygon. If not_implemented is TRUE, then this is undefined.

  • not_implemented (bool*) – [Output] Indicates if a Green’s theorem implementation exists for each of the edges. (Currently, the only degrees supported are 1, 2, 3 and 4.)

Signature:

void
BEZ_compute_area(const int *num_edges,
                 const int *sizes,
                 const double* const* nodes_pointers,
                 double *area,
                 bool *not_implemented);
void BEZ_compute_edge_nodes(const int *num_nodes, const int *dimension, const double *nodes, const int *degree, double *nodes1, double *nodes2, double *nodes3)

Extracts the edge nodes from the control net of a Bézier triangle. For example, if the control net of a quadratic triangle is:

\[\left[\begin{array}{c c c c c c} v_{2,0,0} & v_{1,1,0} & v_{0,2,0} & v_{1,0,1} & v_{0,1,1} & v_{0,0,2} \end{array}\right] = \left[\begin{array}{c c c c c c} a & b & c & d & e & f \end{array}\right]\]

then the edges are

\[\begin{split}\begin{align*} E_1 &= \left[\begin{array}{c c c} a & b & c \end{array}\right] \\ E_2 &= \left[\begin{array}{c c c} c & e & f \end{array}\right] \\ E_3 &= \left[\begin{array}{c c c} f & d & a \end{array}\right]. \end{align*}\end{split}\]
Parameters:
  • num_nodes (const int*) – [Input] The number of nodes \(N\) in the control net of the Bézier triangle.

  • dimension (const int*) – [Input] The dimension \(D\) such that the triangle lies in \(\mathbf{R}^D\).

  • nodes (const double*) – [Input] The actual control net of the Bézier triangle as a \(D \times N\) array. This should be laid out in Fortran order, with \(D N\) total values.

  • degree (const int*) – [Input] The degree \(d\) of the Bézier triangle.

  • nodes1 (double*) – [Output] The control points of the first edge Bézier curve as a \(D \times (d + 1)\) array, laid out in Fortran order.

  • nodes2 (double*) – [Output] The control points of the second edge Bézier curve as a \(D \times (d + 1)\) array, laid out in Fortran order.

  • nodes3 (double*) – [Output] The control points of the third edge Bézier curve as a \(D \times (d + 1)\) array, laid out in Fortran order.

Signature:

void
BEZ_compute_edge_nodes(const int *num_nodes,
                       const int *dimension,
                       const double *nodes,
                       const int *degree,
                       double *nodes1,
                       double *nodes2,
                       double *nodes3);
void BEZ_de_casteljau_one_round(const int *num_nodes, const int *dimension, const double *nodes, const int *degree, const double *lambda1, const double *lambda2, const double *lambda3, double *new_nodes)

This performs a single round of the de Casteljau algorithm for evaluation in barycentric coordinates \(B(\lambda_1, \lambda_2, \lambda_3)\). This reduces the control net \(v_{i, j, k}^d\) to a lower degree control net

\[v_{i, j, k}^{d - 1} = \lambda_1 v_{i + 1, j, k}^d + \lambda_2 v_{i, j + 1, k}^d + \lambda_3 v_{i, j, k + 1}^d.\]
Parameters:
  • num_nodes (const int*) – [Input] The number of nodes \(N\) in the control net of the Bézier triangle.

  • dimension (const int*) – [Input] The dimension \(D\) such that the triangle lies in \(\mathbf{R}^D\).

  • nodes (const double*) – [Input] The actual control net of the Bézier triangle as a \(D \times N\) array. This should be laid out in Fortran order, with \(D N\) total values.

  • degree (const int*) – [Input] The degree \(d\) of the Bézier triangle.

  • lambda1 (const double*) – [Input] The first barycentric parameter along the reference triangle.

  • lambda2 (const double*) – [Input] The second barycentric parameter along the reference triangle.

  • lambda3 (const double*) – [Input] The third barycentric parameter along the reference triangle.

  • new_nodes (double*) – [Output] The newly-formed degree \(d - 1\) control net. This will be a \(D \times (N - d - 1)\) array.

Signature:

void
BEZ_de_casteljau_one_round(const int *num_nodes,
                           const int *dimension,
                           const double *nodes,
                           const int *degree,
                           const double *lambda1,
                           const double *lambda2,
                           const double *lambda3,
                           double *new_nodes);
void BEZ_evaluate_barycentric(const int *num_nodes, const int *dimension, const double *nodes, const int *degree, const double *lambda1, const double *lambda2, const double *lambda3, double *point)

Evaluates a single point on a Bézier triangle, with input in barycentric coordinates: \(B(\lambda_1, \lambda_2, \lambda_3)\).

Parameters:
  • num_nodes (const int*) – [Input] The number of nodes \(N\) in the control net of the Bézier triangle.

  • dimension (const int*) – [Input] The dimension \(D\) such that the triangle lies in \(\mathbf{R}^D\).

  • nodes (const double*) – [Input] The actual control net of the Bézier triangle as a \(D \times N\) array. This should be laid out in Fortran order, with \(D N\) total values.

  • degree (const int*) – [Input] The degree \(d\) of the Bézier triangle.

  • lambda1 (const double*) – [Input] The first barycentric parameter along the reference triangle.

  • lambda2 (const double*) – [Input] The second barycentric parameter along the reference triangle.

  • lambda3 (const double*) – [Input] The third barycentric parameter along the reference triangle.

  • point (double*) – [Output] A \(D \times 1\) array, will contain \(B(\lambda_1, \lambda_2, \lambda_3)\).

Signature:

void
BEZ_evaluate_barycentric(const int *num_nodes,
                         const int *dimension,
                         const double *nodes,
                         const int *degree,
                         const double *lambda1,
                         const double *lambda2,
                         const double *lambda3,
                         double *point);
void BEZ_evaluate_barycentric_multi(const int *num_nodes, const int *dimension, const double *nodes, const int *degree, const int *num_vals, const double *param_vals, double *evaluated)

Evaluates many points on a Bézier triangle, with input in barycentric coordinates: \(\left\{B(\lambda_{1,j}, \lambda_{2,j}, \lambda_{3,j})\right\}_j\).

Parameters:
  • num_nodes (const int*) – [Input] The number of nodes \(N\) in the control net of the Bézier triangle.

  • dimension (const int*) – [Input] The dimension \(D\) such that the triangle lies in \(\mathbf{R}^D\).

  • nodes (const double*) – [Input] The actual control net of the Bézier triangle as a \(D \times N\) array. This should be laid out in Fortran order, with \(D N\) total values.

  • degree (const int*) – [Input] The degree \(d\) of the Bézier triangle.

  • num_vals (const int*) – [Input] The number of points \(k\) where \(B\) is being evaluated.

  • param_vals (const double*) – [Input] A \(k \times 3\) array of \(k\) triples of barycentric coordinates, laid out in Fortran order. This way, the first column contains all \(\lambda_1\) values in contiguous order, and similarly for the other columns.

  • evaluated (double*) – [Output] A \(D \times k\) array of all evaluated points on the triangle. Column \(j\) will contain \(B(\lambda_{1,j}, \lambda_{2,j}, \lambda_{3,j})\).

Signature:

void
BEZ_evaluate_barycentric_multi(const int *num_nodes,
                               const int *dimension,
                               const double *nodes,
                               const int *degree,
                               const int *num_vals,
                               const double *param_vals,
                               double *evaluated);
void BEZ_evaluate_cartesian_multi(const int *num_nodes, const int *dimension, const double *nodes, const int *degree, const int *num_vals, const double *param_vals, double *evaluated)

Evaluates many points on a Bézier triangle, with input in cartesian coordinates: \(\left\{B(s_j, t_j)\right\}_j\). Each input \((s, t)\) is equivalent to the barycentric input \(\lambda_1 = 1 - s - t\), \(\lambda_2 = s\) and \(\lambda_3 = t\).

Parameters:
  • num_nodes (const int*) – [Input] The number of nodes \(N\) in the control net of the Bézier triangle.

  • dimension (const int*) – [Input] The dimension \(D\) such that the triangle lies in \(\mathbf{R}^D\).

  • nodes (const double*) – [Input] The actual control net of the Bézier triangle as a \(D \times N\) array. This should be laid out in Fortran order, with \(D N\) total values.

  • degree (const int*) – [Input] The degree \(d\) of the Bézier triangle.

  • num_vals (const int*) – [Input] The number of points \(k\) where \(B\) is being evaluated.

  • param_vals (const double*) – [Input] A \(k \times 2\) array of \(k\) pairs of cartesian coordinates, laid out in Fortran order. This way, the first column contains all \(s\)-values in contiguous order, and similarly for the other column.

  • evaluated (double*) – [Output] A \(D \times k\) array of all evaluated points on the triangle. Column \(j\) will contain \(B(s_j, t_j)\).

Signature:

void
BEZ_evaluate_cartesian_multi(const int *num_nodes,
                             const int *dimension,
                             const double *nodes,
                             const int *degree,
                             const int *num_vals,
                             const double *param_vals,
                             double *evaluated);
void BEZ_jacobian_both(const int *num_nodes, const int *dimension, const double *nodes, const int *degree, double *new_nodes)

Computes control nets for both cartesian partial derivatives of a Bézier triangle \(B_s(s, t)\) and \(B_t(s, t)\). Taking a single (partial) derivative lowers the degree by 1.

Parameters:
  • num_nodes (const int*) – [Input] The number of nodes \(N\) in the control net of the Bézier triangle.

  • dimension (const int*) – [Input] The dimension \(D\) such that the triangle lies in \(\mathbf{R}^D\).

  • nodes (const double*) – [Input] The actual control net of the Bézier triangle as a \(D \times N\) array. This should be laid out in Fortran order, with \(D N\) total values.

  • degree (const int*) – [Input] The degree \(d\) of the Bézier triangle.

  • new_nodes (double*) – [Output] The combined control nets \(B_s\) and \(B_t\) as a \((2D) \times (N - d - 1)\) array, laid out in Fortran order. The first \(D\) columns contain the control net of \(B_s\) and final \(D\) columns contain the control net of \(B_t\).

Signature:

void
BEZ_jacobian_both(const int *num_nodes,
                  const int *dimension,
                  const double *nodes,
                  const int *degree,
                  double *new_nodes);
void BEZ_jacobian_det(const int *num_nodes, const double *nodes, const int *degree, const int *num_vals, const double *param_vals, double *evaluated)

Computes \(\det(DB)\) at many points \((s_j, t_j)\). This is only well-defined if \(\det(DB)\) has two rows, hence the triangle must lie in \(\mathbf{R}^2\).

Parameters:
  • num_nodes (const int*) – [Input] The number of nodes \(N\) in the control net of the Bézier triangle.

  • nodes (const double*) – [Input] The actual control net of the Bézier triangle as a \(2 \times N\) array. This should be laid out in Fortran order, with \(2 N\) total values.

  • degree (const int*) – [Input] The degree \(d\) of the Bézier triangle.

  • num_vals (const int*) – [Input] The number of points \(k\) where \(\det(DB)\) is being evaluated.

  • param_vals (const double*) – [Input] A \(k \times 2\) array of \(k\) pairs of cartesian coordinates, laid out in Fortran order. This way, the first column contains all \(s\)-values in contiguous order, and similarly for the other column.

  • evaluated (double*) – [Output] A \(k\) array of all evaluated determinants. The \(j\)-th value will be \(\det(DB(s_j, t_j))\).

Signature:

void
BEZ_jacobian_det(const int *num_nodes,
                 const double *nodes,
                 const int *degree,
                 const int *num_vals,
                 const double *param_vals,
                 double *evaluated);
void BEZ_specialize_triangle(const int *num_nodes, const int *dimension, const double *nodes, const int *degree, const double *weights_a, const double *weights_b, const double *weights_c, double *specialized)

Changes the control net for a Bézier triangle by specializing from the original triangle \((0, 0), (1, 0), (0, 1)\) to a new triangle \(p_1, p_2, p_3\).

Parameters:
  • num_nodes (const int*) – [Input] The number of nodes \(N\) in the control net of the Bézier triangle.

  • dimension (const int*) – [Input] The dimension \(D\) such that the triangle lies in \(\mathbf{R}^D\).

  • nodes (const double*) – [Input] The actual control net of the Bézier triangle as a \(D \times N\) array. This should be laid out in Fortran order, with \(D N\) total values.

  • degree (const int*) – [Input] The degree \(d\) of the Bézier triangle.

  • weights_a (const double*) – [Input] A 3-array containing the barycentric weights for the first node \(p_1\) in the new triangle.

  • weights_b (const double*) – [Input] A 3-array containing the barycentric weights for the second node \(p_2\) in the new triangle.

  • weights_c (const double*) – [Input] A 3-array containing the barycentric weights for the third node \(p_3\) in the new triangle.

  • specialized (double*) – [Output] The control net of the newly formed Bézier triangle as a \(D \times N\) array.

Signature:

void
BEZ_specialize_triangle(const int *num_nodes,
                        const int *dimension,
                        const double *nodes,
                        const int *degree,
                        const double *weights_a,
                        const double *weights_b,
                        const double *weights_c,
                        double *specialized);
void BEZ_subdivide_nodes_triangle(const int *num_nodes, const int *dimension, const double *nodes, const int *degree, double *nodes_a, double *nodes_b, double *nodes_c, double *nodes_d)

Subdivides a Bézier triangle into four sub-triangles that cover the original triangle. See Triangle.subdivide() for more details

Parameters:
  • num_nodes (const int*) – [Input] The number of nodes \(N\) in the control net of the Bézier triangle.

  • dimension (const int*) – [Input] The dimension \(D\) such that the triangle lies in \(\mathbf{R}^D\).

  • nodes (const double*) – [Input] The actual control net of the Bézier triangle as a \(D \times N\) array. This should be laid out in Fortran order, with \(D N\) total values.

  • degree (const int*) – [Input] The degree \(d\) of the Bézier triangle.

  • nodes_a (double*) – [Output] The control net of the lower left sub-triangle as a \(D \times N\) array, laid out in Fortran order.

  • nodes_b (double*) – [Output] The control net of the central sub-triangle as a \(D \times N\) array, laid out in Fortran order.

  • nodes_c (double*) – [Output] The control net of the lower right sub-triangle as a \(D \times N\) array, laid out in Fortran order.

  • nodes_d (double*) – [Output] The control net of the upper left sub-triangle as a \(D \times N\) array, laid out in Fortran order.

Signature:

void
BEZ_subdivide_nodes_triangle(const int *num_nodes,
                             const int *dimension,
                             const double *nodes,
                             const int *degree,
                             double *nodes_a,
                             double *nodes_b,
                             double *nodes_c,
                             double *nodes_d);