Search Unity

  1. Improved Prefab workflow (includes Nested Prefabs!), 2D isometric Tilemap and more! Get the 2018.3 Beta now.
    Dismiss Notice
  2. The Unity Pro & Visual Studio Professional Bundle gives you the tools you need to develop faster & collaborate more efficiently. Learn more.
    Dismiss Notice
  3. Let us know a bit about your interests, and if you'd like to become more directly involved. Take our survey!
    Dismiss Notice
  4. Improve your Unity skills with a certified instructor in a private, interactive classroom. Watch the overview now.
    Dismiss Notice
  5. Want to see the most recent patch releases? Take a peek at the patch release page.
    Dismiss Notice

Seal complex mesh faces algorithm?

Discussion in 'Scripting' started by elseforty, Sep 15, 2018.

  1. elseforty

    elseforty

    Joined:
    Apr 3, 2018
    Posts:
    64
    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 ,
     
  2. neoshaman

    neoshaman

    Joined:
    Feb 11, 2011
    Posts:
    3,540
    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.
     
  3. neoshaman

    neoshaman

    Joined:
    Feb 11, 2011
    Posts:
    3,540
    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).
     
  4. elseforty

    elseforty

    Joined:
    Apr 3, 2018
    Posts:
    64
    @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
     
  5. Kurt-Dekker

    Kurt-Dekker

    Joined:
    Mar 16, 2013
    Posts:
    2,773
  6. elseforty

    elseforty

    Joined:
    Apr 3, 2018
    Posts:
    64
    @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
     
  7. neoshaman

    neoshaman

    Joined:
    Feb 11, 2011
    Posts:
    3,540
    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.
     
  8. elseforty

    elseforty

    Joined:
    Apr 3, 2018
    Posts:
    64
    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




     
  9. Suddoha

    Suddoha

    Joined:
    Nov 9, 2013
    Posts:
    2,064
    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?
     
  10. elseforty

    elseforty

    Joined:
    Apr 3, 2018
    Posts:
    64
    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
     
  11. Suddoha

    Suddoha

    Joined:
    Nov 9, 2013
    Posts:
    2,064
    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.
     
    Kurt-Dekker likes this.
  12. elseforty

    elseforty

    Joined:
    Apr 3, 2018
    Posts:
    64
    thanx alot for the advice, i appreciate that and will check the article back again
     
  13. neoshaman

    neoshaman

    Joined:
    Feb 11, 2011
    Posts:
    3,540
    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.
     
  14. elseforty

    elseforty

    Joined:
    Apr 3, 2018
    Posts:
    64
    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

     
    neoshaman likes this.
  15. elseforty

    elseforty

    Joined:
    Apr 3, 2018
    Posts:
    64
    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
     
    Suddoha, neoshaman and Kurt-Dekker like this.
  16. Kurt-Dekker

    Kurt-Dekker

    Joined:
    Mar 16, 2013
    Posts:
    2,773
    Ha! That looks awesome. Nice work man...
     
    elseforty likes this.
  17. neoshaman

    neoshaman

    Joined:
    Feb 11, 2011
    Posts:
    3,540
    Glad you found something that worked for you! :D
     
    elseforty likes this.