Callbacks

[Madrich]

Hi, I'd like to use CDT for meshing a terrain. I have a 2d elevation map (matrix), so all the time a triangle is inserted or created by flip I need to recalculate the costs of that triangle and provide a new vertex candidate list. To make things easier, a callback function would be great. If you like, I can make patch for that. Let me know. So far, you make a great Job. Cheers

[artem-ogre]

I think I understand what you mean, Are you implementing something similar to https://github.com/heremaps/tin-terrain? I find this topic very interesting. At some point I would like to implement such algorithm myself. Is your work closed source?

As for your request: I would love to see what you suggest. The callbacks can be added if they will not affect the existing mainstream use cases. Ideally they should be opt-in extension points with zero overhead when callbacks are not used.

[Madrich]

The overhead will be just a single if statement per vertex inserted and per flip. I am going to implementing it right now. One can turn it of by a cmake option. Using the callback we have a perfect decoupling of the problem statement and I can process huge terrain models as I use a out of core strategy for the high memory consumption elevation map. It is closed source unfortunately. My own current delauney is currently just to slow. Your seams to be much cleaner and faster. Will provide a merge request in some days.

[LeoPizzo1]

Ciao, I went out to a similar need, for the case of the insertion of new vertices on the boundaries, via CDT::IntersectingConstraintEdges::TryResolve parameter. As far as now it is not possible to get the added vertices, as well as the edges interested by the split. I understand the concern of @artem-ogre about the overhead, anyway. To resolve this problem, it is possible to use the CRTP pattern.

What is needed, is to add a furthermore template parameter to the Triangulation class, i.e

template <typename T, typename TNearPointLocator = LocatorKDTree<T>, typename TCallbacks>
class CDT_EXPORT Triangulation
{
...

and in the code use it like this:

static_cast<TCallbacks*>(this)->callbackFunction( parameters );

This has no overhead, since the resolution is done at compile time, and no extra binary code is added. There is no virtual (so no overhead for the virtual table), no if, no store of function pointers, etc...

To let the class to compile is necessary to provide a default argument for the TCallbacksparameter.

My test was declaring the default parameter like this:

template<typename T>
class TriangulationCallbacks
{
public:
  inline void vertexAdded( const V2d<T> newV, const VertInd iNewVert, const Edge edge1, const Edge edge2 ) { __noop; }
};

template <typename T, typename TNearPointLocator = LocatorKDTree<T>, typename TCallbacks = TriangulationCallbacks<T> >
class CDT_EXPORT Triangulation
{
...

The code in Triangulation.hpp file, around line 600, becomes like this:

        case IntersectingConstraintEdges::TryResolve: {
            if(!fixedEdges.count(Edge(iVL, iVR)))
                break;
            // split edge at the intersection of two constraint edges
            const V2d<T> newV = detail::intersectionPosition(
                vertices[iA], vertices[iB], vertices[iVL], vertices[iVR]);
            const VertInd iNewVert =
                splitFixedEdgeAt(Edge(iVL, iVR), newV, iT, iTopo);
            // TODO: is it's possible to re-use pseudo-polygons
            //  for inserting [iA, iNewVert] edge half?
            remaining.push_back(Edge(iA, iNewVert));
            remaining.push_back(Edge(iNewVert, iB));
            static_cast<TCallbacks*>(this)->vertexAdded( newV, iNewVert, edge, Edge( iVL, iVR ) );
            return;

Who needs to implement the callback simply needs to derive a class from Triangulation, implement the callback functions and pass itself as a template parameter:

template < typename T >
class LocalTriangulation:
  public CDT::Triangulation<T, CDT::LocatorKDTree<T>, LocalTriangulation<T>>
{
  using BaseClass = CDT::Triangulation<T, CDT::LocatorKDTree<T>, LocalTriangulation<T>>;
public:
  LocalTriangulation(
    CDT::VertexInsertionOrder::Enum vertexInsertionOrder,
    CDT::IntersectingConstraintEdges::Enum intersectingEdgesStrategy,
    T minDistToConstraintEdge ):
    BaseClass( vertexInsertionOrder, intersectingEdgesStrategy, minDistToConstraintEdge )
  {
  }
  LocalTriangulation(
    CDT::VertexInsertionOrder::Enum vertexInsertionOrder):
    BaseClass( vertexInsertionOrder)
  {
  }

  LocalTriangulation( ):
    BaseClass( )
  {
  }

  void vertexAdded( const CDT::V2d<T> newV, const CDT::VertInd iNewVert, const CDT::Edge edge1, const CDT::Edge edge2 )
  {
    newIndexes.emplace_back( iNewVert );
    edges.emplace_back( edge1, edge2  );
    newVertices.emplace_back( newV );
  }

protected:

  std::vector< CDT::V2d<T> > newVertices;
  std::vector< CDT::VertInd> newIndexes;
  std::vector<std::pair<CDT::Edge, CDT::Edge > > edges;
};

In addition to other benefits, since the callback implementation is done in the derived class, you have access to protected data of the base class, if needed.

If you prefer I can prepare a pull request with my sample, so then @Madrich you can enrich it with all your needs.

[artem-ogre]

@Madrich Can you give an example of how you are using the callbacks in your PR? Is 'new vertex' callback really needed?

@LeoPizzo1 I think if I were to introduce callbacks in CDT I would implement them similarly to STL: taking a template functor.

[LeoPizzo1]

Thanks @artem-ogre : good idea.

From my point of view the callback for the new vertex insertion is mandatory to use the intersection edges resolver. I have a 1-1 relationship to the vertices and a data structure where I keep the real 3d point, that in some cases I can't re-evaluate it from the original parametric surface. If a new point is inserted, I need to compute the corresponding data structure and insert in the right position to let my further steps to work flawlessy.