Seal complex mesh faces algorithm?

Hello,
i'm trying to create a cap hole for a spline mesh extrusion, my code works fine but once the spline gets little bit curvy and complex then i fall into this issue,


i tried to developed a piece of code in the editor as solution to this issue but it's not enough,
any idea on how i can correctly approach this ,

 

IT's a convex/concave problem, look it up

Try this, it won't solve all case, but might solve this one:
- create a center vertex that is the weighted average of all vertex to weld
- weld vertex to this one using your method.

It assume all vertices to weld are on the same plane, and that the center of weight is inside the shape, still won't work with highly concave shape.

 

Else you will have to break the shape into sub convex shape.

Try this.
- assuming all vertices are on a plane,
- calculate the angle to the next vertices,
- then iterate until the angle cross the 180° relative to the previous vertices
- basically the curve "turn the other way", if it turn left at the begining, it should keep doing that until we reach the end of the list. The moment that turn direction (left or right relative to previous) change, you have a concave inflexion.
- if you find a concave inflexion, close the shape to the first in the list, start over at the concave inflexion.
- this also should allow you to detect degenerate triangle (when the angle are too closse or are colinear, you have a degenerate triangle).

 

@neoshaman Hi,
i tried the center vertex solution before, it's good but its not perfect ,as you said it won't work for highly concave shapes ,
i'm not sure if i understood your second solution correctly , can you please provide more explanation
i did a test on 3Ds max trying to understand how it's handling this,


i created a spline and did the extrusion inside max ,export the mesh to unity because unity triangulate meshes, this is what i got ,
i can see no pattern honestly

 

This is the general case problem discussion and several example solutions:

https://en.wikipedia.org/wiki/Polygon_triangulation

 

@Kurt-Dekker thanx for the link , it helped me a bit
i'm following @neoshaman method which my brain gets somehow,
i did the part where i detect the vertex inflexion " concave or convex "


but there may me some issue like this case


how can i solve that issue, what will be the correct algorithm that will allow me to get the result bellow

 

I see, you have point inside another already close shapes, my algorithm isn't generic and it's highly local (point to point), you either avoid edge cases, or find a fix by changing algorithm or handling the exception cases.

So you would need to check if a new point is inside an already close shape, and then handle that appropriately.

 

hello @neoshaman , yes that is exactly what i need to do to get the perfect solution for this issue, at this point the result that i have achieved looks decent and it's way better that what i had at the beginning ,but i will try raise the barre a bit

 

Is your current implementaton attempt one of the algorithms that's known to solve the problem (see @Kurt-Dekker's link), or are you trying to figure this one out completely from scratch?

 

kind of trying to do this from scratch, i want to solve this by a method that my brain gets, the other methods are too complex for me to understand

 

Well, I respect that.

However, honestly speaking I'd say this is rather just good for practicing, if you're seriously looking to solve this for a project and this is just a "blocker" in your current project, I recommend to follow the step-by-step instructions in the article linked above - which is btw, also a great way to practice the implementation of algorithms so this is absolutely worth it.

The reason I say that (don't get me wrong, I'm that kind of guy who also likes to do things on his own) is that such things have already been discovered, simplified, optimized, even with mathematic proof.

I don't doubt there are other ways out there, but once you follow the article step by step, it will probably get easier and easier to understand.

 

thanx alot for the advice, i appreciate that and will check the article back again

 

Just a last observation of the algo I gave you, it assume that the "central shape" is convex and you are basically trimming "radial part from it". If you can basically check the convexity of that shape and break it further, that would clue you about were to go, if you still want to find your own way.

 

exactly , that is what i did in this third test, and i got this result which looks more interesting than the previous one now the central shape "which i had issues with last time " is adjusting it's triangulation automatically based on the convexity of its vertices , but this needs some improvement , i deeply tested this and it has issues, now sometimes i i get wrong triangulation on the surrounding shapes, i tried to subdivide them as i did for the central shape to correct them but unity freezes it must be something in my code,i'll try to find out

 

Hello again,
i'm coming back to this thread to post some new update ,i gave up on the last method that @neoshaman proposed , it didn't work perfectly specially when the shape is smooth, i couldn't figure out what was wrong with it plus it got so complex to handle,
so i had to find something else , so what i did is read @Kurt-Dekker link carfully as @Suddoha recommended and i ended up following the "Ear Cliping" method , it's the easiest compared to the other methods
the principal of this method is to find convex points "ear" and draw a triangle with the nearby points , so if point 5 is convex then the triangle will be [4,5,6] ,in the same time the triangle should not contain any other vertices from the shape to approve the triangle,
i keep doing this for all the points while removing the points that successfully met all conditions above,i keep doing this until shape is correctly triangulated

 

Ha! That looks awesome. Nice work man...

 

Glad you found something that worked for you!