Application Programming Interface to TTL (API)

There are two interface channels between TTL and the application data structure: DartType and TraitsType, which are template arguments to the TTL functions.

Function templates in TTL use either DartType or both DartType and TraitsType depending on the complexity of the algorithms. DartType is used for topological queries, and TraitsType is used for topological modifiers and geometric calculations. The documentation in TTL tells which functionality is needed in DartType and TraitsType for each function template.

TTL consists of two namespaces with generic functions: ttl contains the main interface and ttl_util contains utility functions that can also be used by the application programmer. The figure below shows the (simple) architecture of an application using TTL.

In the following we explain how DartType and TraitsType must be implemented as an interface to the actual data structure. For more details see literature.

DartType

The generic functions in TTL navigates in the application data structure through a "topological element" call a dart, which must be implemented as a struct or a class by the application programmer. A dart can be considered as a unique triple d = (V, E, T), where V is a node of the edge E, and V and E is a node and an edge of the triangle T; see figure a) below where a dart is indicated as an arrow.

TTL expects that three functions, which we call alpha-iterators, are present in the dart class: alpha0(), alpha1() and alpha2(). These functions reposition the dart in the triangulation as shown in figure b) above and return a reference to the modified dart itself. Thus, alpha0(), alpha1() and alpha2() change the node, the edge and the triangle of the triple d = (V, E, T) respectively.

Note:

The dart is not part of the data structure. It is a "dynamic" element that "moves" around in the actual application data structure when the alpha-iterators are applied to it. Thus, this mechanism does not require any extra memory other than that occupied by the (few) darts that are involved in a function template of TTL that is called.

In addition to the alpha-iterators, TTL expects that standard class member functions such as constructors, assignment operators and the like are also implemented in the dart class.

The following syntax is required:

class MyDart {
  ...
public:
  // Constructors and destructors
  ...
  MyDart(const MyDart& dart) {...} // copy constructor
  MyDart& operator= (const MyDart& dart) {...} // assignment operator

  // comparing dart objects
  bool operator==(const MyDart& dart) const {...}
  bool operator!=(const MyDart& dart) const {...}

  // alpha-iterators
  MyDart& alpha0() {...; return *this;}
  MyDart& alpha1() {...; return *this;}
  MyDart& alpha2() {...; return *this;}
  };

Thus, the alpha-iterators change the content of the dart and return a reference to the dart itself.

Note:

Note that alpha2() must return the dart itself without changing its content (when checked with the == operator) if the edge associated with the dart is at the boundary of the triangulation. The source code of ttl::isBoundaryEdge illustrates this:

template <class DartType>
  bool isBoundaryEdge(const DartType& dart) {
    
  DartType dart_iter = dart;
  if (dart_iter.alpha2() == dart)
    return true;
  else
    return false;
}

Consult the definition and source code of class hed::Dart, which implements the dart class for the half-edge data structure, for a thorough example.

TraitsType

TraitsType can be a static class or a struct that contains functionality required by the functions in TTL. The purpose with TraitsType is twofold:

Let the application programmer provide topological modifiers on the actual data structure that are not resolved by TTL, e.g., remove a triangle from the triangulation,
Let the application programmer provide basic geometric calculations and thus control the level of accuracy for such calculations.

For example, assume that a function in TTL requires a scalar product between vectors in the plane, represented as darts, with the following syntax:

real_type scalarProduct2d(const DartType& d1, const DartType& d2)

Then this function must be implemented in the traits class together with the definition of real_type:

struct MyTraitsType {
  typedef double real_type;
  ...
  static real_type scalarProduct2d(const MyDart& v1, const MyDart& v2) {
    return ::my_scalarProduct2d(v1,v2);
  }
  ...
  static bool swapTestDelaunay(const MyDart& dart) {
    if (dart.getEdge().isConstrained())
      return false;
    else
      return ttl::swapTestDelaunay<MyTraitsType>(dart);
  }
};

The second function, swapTestDelaunay, implements the Delaunay swapping test. The function desides if the edge associated with the given dart should be swapped according to the circumcircle criterion (or equivalently according to the MaxMin angle criterion). In the example above, it is first examined if the edge is constrained, in which case false is returned. Then the test is directed back to TTL again since the circumcircle test is present there; see ttl::swapTestDelaunay. Of course, the user could also make his/her own implementation of the circumcircle test, e.g., by using robust schemes with exact arithmetic as Jonathan Richard Shewchuk does (http://www-2.cs.cmu.edu/~quake/robust.html).

This example also illustrates the syntax functionName<MyTraitsType>(...arguments...) when calling function templates using a traits class.

Actually, scalar product between vectors, as well as cross product and other point and vector algebra, are also present in the the namespace ttl_util. Assume that MyDart::x() and MyDart::y() deliver the coordinates in the plane of the node associated with a dart. Then the scalar product in MyTraitsType can be implementes as:

static real_type scalarProduct2d(const MyDart& v1, const MyDart& v2) {
  MyDart v10 = v1; v10.alpha0();
  Dart v20 = v2; v20.alpha0();
  return ttl_util::scalarProduct2d(v10.x()-v1.x(), v10.y()-v1.y(), 
                                   v20.x()-v2.x(), v20.y()-v2.y());
}

Consult the definition and source code of struct hed::TTLtraits, which implements the traits class for the half-edge data structure. This example shows which members that are required in the traits class for running incremental Delaunay triangulation and removing nodes in a triangulation.