Add Advancing Front Meshing Algorithm to PCL

[Levi-Armstrong]

Hello,

I have currently implementing the Advancing Front Meshing Algorithm based on the three papers below. It currently depends heavily on the MLS library and Half Edge Mesh Library. I had to make a few enhancements to the MLS library which I would also like to push back to PCL. I will begin implementing it into the surface module of PCL based on the feedback from the PCL maintainer. I due have a few question that would help get me started.

Questions

1. I currently use the PCL type PointXYZINormal for storing my data. I use the intensity for storing the the maximum edge length allowed for a given mesh vertex. Should I create a new type or is this acceptable?

2. How should I approach storing the principle curvature within the MLS Library?

MLS Enhancements

1. The ability to cache the MLS results data. The algorithm currently accomplishes this by passing the input cloud in as a distinct cloud.
2. Added the ability to calculate the principal curvatures from the polynomial surface. Though not sure how the best way to store this information in the MLS library. I am currently over writing the pca value.
3. In order to calculate the principle curvatures the partial derivatives are required so I added a function which calculates h_u, h_v, h_uu, h_vv, and h_uv.

Advancing Front Papers

1. High-Quality Extraction of Isosurfaces from Regular and Irregular Grids J. Schreiner, C. Scheidegger, C. Silva IEEE Transactions on Visualization and Computer Graphics (Proceedings of IEEE Visualization); 2006

2. Direct (Re)Meshing for Efficient Surface Processing J. Schreiner, C. Scheidegger, S. Fleishman, C. Silva Computer Graphics Forum (Proceedings of Eurographics); 2006

3. Triangulating Point-Set Surfaces With Bounded Error C. Scheidegger, S. Fleishman, C. Silva Proceedings of the third Eurographics/ACM Symposium on Geometry Processing; 2005

[SergioRAgostinho]

Hey. I'm not so into the topic so let me start with some introductory questions.

I have currently implementing the Advancing Front Meshing Algorithm based on the three papers below. It currently depends heavily on the MLS library and Half Edge Mesh Library. I had to make a few enhancements to the MLS library which I would also like to push back to PCL.

What exactly is the MLS library? I can't get obvious first results on google. I just get hits about our MLS implementation.

Regarding the Half Edge Mesh Library, based only on the summary they provide on the front page, I'm not sure this is something we want to add as third party considering we have our own Mesh types, and so on... Need opinions by the rest on this one. How much effort would it be to enhance our mesh classes to implement the functionalities you need?

[Levi-Armstrong]

Sorry, I should of mentioned that I implemented it from scratch using the information provided in the text. I did not want to use there implementation mainly because it looked like everything was custom and I wanted to use what PCL already provided. I am currently using the MLS Library and Half Edge Mesh Library within PCL shown below.

MLS Library Polygon Mesh (Half Edge Mesh)

[SergioRAgostinho]

Cool, so there's no additional third parties 👍 So basically you're calling MLS Library the MLS class itself. I'll interpret what you wrote with this in mind then.

First answers with the disclaimer that I'm not familiar with MLS at all.

I currently use the PCL type PointXYZINormal for storing my data. I use the intensity for storing the the maximum edge length allowed for a given mesh vertex. Should I create a new type or is this acceptable?

I'm not sure I fully understand the question. Our current MLS implementation requires providing a separate clouds with XYZ data and Normal data. In your case each vertex needs to keep track of its maximum edge length. I'm not sure this would be something I would store on the point itself. If would provide that "per vertex" constraint, on a separate float vector and allow the user to use whatever XYZ point type is more useful him. We might need more feedback here.

How should I approach storing the principle curvature within the MLS Library?

Before answering this, there's something else I need to understand first.

If Advancing Front Meshing is a new algorithm on its own, it should implement its own class. If it shares a lot of algorithmic steps similar to MLS, then it should derive from MLS. You mention you want to provide some enhancements to the current MLS implementation, so I'm assuming your newly added class with take advantage of them, is this correct?

In theory, this principle curvature (at this point I have no idea what this is, I just assume it's a parameter you make use) will go into your new class as a parameter.

[Levi-Armstrong]

Thank you for the help so far.

MLS Class Desired Changes

• The ability to cache the mls_results with out having to specify a distinct cloud shown here and it would also need to be updated here. Possible add a new method setCacheMLSResults which sets a flag that also get checked at the two provided locations.
  • The second change is an improvement on the projection method. The current projection on to the MLS surface is what I would call a simple projection. It projects the point on to the mls plane to get the uv coordinates they calculates the polynomial height at the uv coordinates. This is not the closest point on the mls surface. In areas of high curvature this projection method has larger error resulting in a rough mesh. I add the ability to project the point orthogonal to the MLS surface which improving the mls projection in areas of higher curvature. I was planning on adding a new method setProjectionMethod where the default would be the simple but you could use the other for better results if need.
  • I have also added the ability to calculate the Principle Curvatures from the mls polynomial, but this does not have to be in the mls class. I thought it would be nice since I have seen that other developers were looking for a way to get the Principle Curvatures from a point cloud. As part of the Advancing Front Mesher I could easily expose a static method that would calculate these given the the mls_results and point cloud.

If Advancing Front Meshing is a new algorithm on its own, it should implement its own class. If it shares a lot of algorithmic steps similar to MLS, then it should derive from MLS. You mention you want to provide some enhancements to the current MLS implementation, so I'm assuming your newly added class with take advantage of them, is this correct?

In the current implementation to address the items above I did just what you mentioned. I created a separate class that inherits from MLS and adds the additional capability. I do thinks some of the change would be of value to other developers that use the MLS class.

New Advancing Front Mesher

• Sorry the Point Type question was in reference to the Meshing class. I original was using existing point types (PointXYZINormal) within PCL for storing vertex data during the meshing process. I have since moved away from this an I have created two new types to allow for storing more information at the vertex level which allowed me to optimize the algorithm further and a 25% speed improvement. Will this be an issue? They can be full contained within the class and I there should not be any need for them to be used outside the class.

[taketwo]

:+1: for the addition of caching and a new projection method to MLS. If this new method is strictly better, then we can make it the default.

As to where the Principle Curvatures calculation should belong is not so clear to me. Maybe a standalone function?

Regarding point types, I think it makes sense to create your own. Its not awfully wide-spread in PCL, but there are some cases (e.g. in ImplicitShapeModel and tracking). And if it needs not be a part of the public interface, then all the better, just make it fully contained implementation detail.

[Levi-Armstrong]

:+1: for the addition of caching and a new projection method to MLS. If this new method is strictly better, then we can make it the default.

It is better the only draw back is it is an optimization problem and it take roughly two iteration per request to converge. I have not tested the speed penalty but I will and post the results.

As to where the Principle Curvatures calculation should belong is not so clear to me. Maybe a standalone function?

I do like the standalone option, I would just need to expose a way to get the mls_results out of the mls class. Would you be open to adding a new methods below?

std::vector<MLSResult> getMLSResults() const
MLSResult getMLSResult(const int index) const

Regarding point types, I think it makes sense to create your own. Its not awfully wide-spread in PCL, but there are some cases (e.g. in ImplicitShapeModel and tracking). And if it needs not be a part of the public interface, then all the better, just make it fully contained implementation detail.

Sounds Good. I will make them fully contained within the class.

I will start working on a PR today to start the review process.

[taketwo]

Disclaimer: as Sergio, I'm not actually familiar with the MLS algorithm. But from the comment I see that the vector of MLSResults is only populated for some upsampling methods. What will happen if it is not? Also, this structure is in the protected section, so a standalone function won't be able to use it, unless we promote it to public. So reconsidering my initial answer, maybe a member method will be more appropriate?

I will start working on a PR today to start the review process.

Let's keep the updates for MLS in a separate PR to ease reviewing.

[Levi-Armstrong]

Disclaimer: as Sergio, I'm not actually familiar with the MLS algorithm. But from the comment I see that the vector of MLSResults is only populated for some upsampling methods. What will happen if it is not? Also, this structure is in the protected section, so a standalone function won't be able to use it, unless we promote it to public. So reconsidering my initial answer, maybe a member method will be more appropriate?

Yea the the comment is a little misleading. All items that are used to create the MLSResult object are calculated regardless of the upsampling methods, but only in the case of DISTICT_CLOUD and VOXEL_GRID_DILATION do they actual create a MLSResult object here

Let's keep the updates for MLS in a separate PR to ease reviewing.

I agree. I will create a PR that first adds the ability to cache the MLS results. Once that has been addressed I will create another PR that add the new Projection Method followed by a PR for adding the Meshing Algorithm. I should have the first PR submitted in a few hours.

[Levi-Armstrong]

Just created the first PR #1952

[Levi-Armstrong]

I am working on the a new branch integrating the new projection method and noticed that the upsampling methods appear to only work if you are using a polynomial fit. I would of assumed it would of just upsampled using a the mls plane as the surface instead. Is this the intended behavior to only up sample if a polynomial fit was enabled?

[Levi-Armstrong]

Also are there any unit test for MLS? If not where should they be located; I will create some when adding the new projection method?

[taketwo]

There is a unit test for MLS here.

Regarding the first question I'm afraid I can not say anything.

[SergioRAgostinho]

Closing, since #1996 is already under review.