Getting holes in decimated surface, not sure what to try

[jmaeding]

PA2 STREET FG with Sukut.zip Here is a zip of my original obj file before decimating. Rename to .obj from .txt once open. I got really good results on many files but then some get the holes. Pic shows this: Can you advise what to adjust to deal with these? My surfaces are far from 0,0 and have coords like 6000000,2000000 for x and y. Does moving things closer to 0,0 help? The civil engineering industry lives and dies by keeping tri counts low on surfaces and no one has done as good of a job as your ported tool does. I would pay to get it working robustly if it needs that. I might just not have the settings right though. I tried about everything the readme mentioned. I almost think the indexing is getting messed up, as the tris missing are large, not thin slivers that get "rejected" as colinear tris by my prog when I import. I am using your library to make surface tools that work in autocad and bricscad and decimation is a missing ability so far.

[Whinarn]

I will have a closer look at this in the weekend, when I have more time available. It doesn't look like these holes are close to any border or seam, so it definitely looks like a bug. But I will have a closer look and then get back to you with my findings.

Thank you for reporting it!

[jmaeding]

awesome, I will also do some tests. Like I say, your tool does way better than anything I've seen. Its fast too, just a few seconds to decimate 600k tris to 50%. I forgot to mention, I tried turning off the smart linking and that caused nothing to work. That is, even after many iterations, the result was same as original. That might be a clue. Now that I know you are active on it I will look closer.

[jmaeding]

I played more, and was able to get a much smaller dataset that replicated the kinds of errors involved. Temp.zip The zip has before and after obj files. I decimated using 0.3 factor. Notice both missing tris in middle, and much around the edges. Before and after shown:

[jmaeding]

an even smaller dataset that has same kinds of issues: Temp.zip I know that sometimes half the battle is replicating the issues on small sets of data so hopefully this eases the pain a bit.

[Whinarn]

Thank you very much for these samples! It definitely helps!

I have looked into this a bit more, and I actually think that the problem is with the OBJ file parsing, not the decimation process. But I will dig deeper and see if I can confirm and also fix it.

I'll get back to you once I know more. Thanks again!

[Whinarn]

Alright, so I did find problems with the OBJ file parsing, and I reworked it in order to solve them. But that was only part of the problem. The meshes that you have provided appear to have seams in certain places, and the feature I have called "smart linking" is meant to solve this as well as it can. While this feature is enabled by default, it can be tweaked through a property on the FastQuadricMeshSimplification class called VertexLinkDistanceSqr.

Tweaking this value to 0.001 I managed to get better looking results, but saw some other artifacts appear instead. If you use the CLI provided here, then that property cannot not for the time being be controlled through there without adding an extra line after here like this (ugly code):

(algorithm as MeshDecimator.Algorithms.FastQuadricMeshSimplification).VertexLinkDistanceSqr = 0.0001;

I released version 0.3.0 (changelog), with the OBJ file parsing fix and another fix I detected a while ago but never got around to fix related to the VertexLinkDistanceSqr settings.

Below are some screenshots of the differences (your original file and 0.01 decimation factor):

Version 0.2.1

Version 0.3.0

Version 0.3.0 with modified vertex link distance

They are all very different results, and while the last one is the best it still has holes and an unwanted artifact that you can see at the top of the image.

Tweaking the VertexLinkDistanceSqr property can give you better results, but do not increase it too much since it will slow down the algorithm and start messing up your decimation results. Other than that, the algorithm generally works best if the seams that do exist share vertex positions and not just the edge of the triangles, if you understand what I mean?

While there are surely ways to fix this, one of my goals with this is for it to be as quick as possible. And to start analyzing edges additionally would reduce the speed greatly. Let me know if you have any other ideas.

I would still like to look into the artifacts that I can see. Triangles start to appear across the mesh when the VertexLinkDistanceSqr property is much lower.

Unfortunately that's as much as I can assist for now. But I hope this helps you. Please tell me how it goes.

Thanks!

[jmaeding]

awesome! thanks a bunch for your work on this, I will test today. The term "seam" you mentioned is not quite clear to me. Is that when a triangle is missing, so there is a hole? That can happen in my surfaces as I use a variety of tools to make the TIN from 3d linework and points, then I read their triangles and reject any collinear ones, thus leaving some missing. Maybe that means something else though. thx

[Whinarn]

Hello again!

Seam might not be the correct term for it. But you seem to have understood. I'm not sure how else to describe it. It's counted as borders in the algorithm when a triangle isn't sharing vertices with another triangle along a specific edge. Even though there is a triangle there, they might have their own vertices that only share the same position, but might have other vertex attributes different. This is where the smart linking feature comes in, as it tries to find vertices that are close enough to each other to be counted as the same vertex for the mesh decimation in order to prevent holes. So if adjacent triangles only share the edge and visually look fine before decimation, it will most probably introduce holes.

I made a very ugly and basic illustration that I hope makes sense:

So the green circled edge would not have a gap in the original mesh, but the edge is considered to be a border, what I previously mentioned as a seam. Where the red circle shows the problem since the lower left triangle doesn't have a vertex anywhere near it. There is currently no code that can deal with these cases, and I'm not sure it can be possible without taking a hit on performance. I would almost suggest pre-processing meshes by splitting up triangles in order to get vertices that share the same position but keep any other needed vertex attributes to not mess up the visuals of the mesh in the process.

There is a property for choosing to preserve all border edges, but as you can imagine it hugely limits the decimation process and I wouldn't recommend it unless the borders are really important.

I hope this makes sense!

[jmaeding]

I see, that is what I thought. I did try preserving seams earlier and it caused zero decimation. But will try with new version. My surfaces do have holes in them, but I think I can split them up into parts without holes, and assemble back in the end, or other approaches. The situation you show above is something I should be dealing with better. I think I will look closer at any rejected tris from the tin creation engine and heal the holes. Thanks for fast responses, I am testing your revised code now.

[jmaeding]

I tested on my larger surfaces and small ones, the new code does much better. It does have issues at edges, but maybe related to those seams I sometimes have. Working in the civil engineering world, we trade surfaces back and forth between companies using landxml format, and sometimes the software that made the tris does illegal things, like collinear tris. I need to test on a lot more, the decimator is super fast, even with the 0.0001 sq dist you mentioned. thx

[jmaeding]

did more tests today. The new code is working well with factor 0.0001 and PreserveBorders on. I feel like these tools are way underutilized. If you only knew how the GIS world can benefit from simplifying surfaces in the "optimized" (not dumb grid or random point sampling) way, there would be many more interested. In particular, the crowd trying to turn point clouds into TIN surfaces need something to tone down their huge tri counts. There are so many uses for this, I've looked for this for literally years. thx

[Whinarn]

I'm glad that you find it useful. I originally created this for a personal game project because I couldn't find any mesh decimation algorithm that worked at run-time in Unity (they only worked offline) and they were all very very slow. I never imagined that people would ever find this. I just wanted to have something public on my GitHub profile.

It's cool to see it being used in other areas than I had originally anticipated. While I appreciate that you use my library for this, I would also recommend this library which is far more advanced with many more features. I haven't measured it in terms of speed however, so I'm not sure how it compares.

Please tell me if there's anything more that I can assist you with.

[jmaeding]

Nice, I had not seen that library before. I need to be looking for those about every 6 months. I typically watch for delunay triangulation, mesh manipulation, GIS data read/write, and image manipulation. Seems you found one for me!