Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Callbacks #178

Open
Madrich opened this issue May 11, 2024 · 6 comments · May be fixed by #179
Open

Callbacks #178

Madrich opened this issue May 11, 2024 · 6 comments · May be fixed by #179
Labels
enhancement New feature or request help wanted Extra attention is needed

Comments

@Madrich
Copy link

Madrich commented May 11, 2024

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 artem-ogre added enhancement New feature or request help wanted Extra attention is needed labels May 11, 2024
@artem-ogre
Copy link
Owner

artem-ogre commented May 11, 2024

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
Copy link
Author

Madrich commented May 11, 2024

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
Copy link

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 TCallbacks parameter.

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
Copy link
Owner

@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
Copy link

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.

@Madrich
Copy link
Author

Madrich commented Jul 10, 2024

Hi Artem,
sorry for the late response, busy with my company too.
The Vertex insert callback is sometimes helpful in my case for visualization.
Examples how to use the std::function callback using a lambda function is in the code documentation.
You can also bind a class member function (for vertex the same):

class MyClass
{
public:
void onTriCreated(CDT::TriInd ind, CDT::CallbackType type);
}

CDT cdt;
MyClass my;
std::function<void(CDT::TriInd ind, CDT::CallbackType type)> fnT = std::bind(&MyClass::onTriCreated, &my, std::placeholders::_1, std::placeholders::_2);
    cdt->registerTriangleCallback(fnT);
...

Does this help?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request help wanted Extra attention is needed
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants