Polygon Triangulation [2] - Ear Clipping Implementation in Code
HTML-код
- Опубликовано: 16 сен 2024
- How to implement ear clipping polygon triangulation. Here we write the actual code for triangulating convex and concave polygons!
GitHub Flat Engine source code: github.com/two...
Polygon Triangulation only source: github.com/two...
![Polygon Triangulation [1] - Overview of Ear Clipping](http://i.ytimg.com/vi/QAdfkylpYwc/mqdefault.jpg)
![Polygon Triangulation [1] - Overview of Ear Clipping](/img/tr.png)
Excellent video, both of them. It's so well explained and the walk-through helped me debug a couple precision problems that I had. Keep it up!
Thanks a lot for the support! Glad these videos were useful!
This was a great help. I translated it to a computer shader in unity after implementing it in a script. Now I can generate tens of thousands of instances in seconds.
This is fucking amazing. Implemented today in Unity. THANK YOU VERY MUCH.
I'm going to try making some more performance boosts, e.g. manually implementing dot product (to cancel all zeros) or implementing some longer but faster is-in-triangle algo.
Small tip for future generations: If you want to implement it directly in unsafe code, first make sure that your 'unsafe list' works before blaming bad algorithm xD
I've been wanting a good tutorial on this for years now. Thank you very much for this
Sure thing! Glad it was useful.
Excellent explanation with appropriate visual representation.
ty, bending my brain back into math mode after 10years no math, it's helpful :).
Fantastic walkthrough!
Excellent videos, both demonstration and implementation
Awesome video! It was informative and everything was explained so well. Really enjoyed the walk-through. Thank you for making these videos. Subbbedd!!
You're welcome! Glad you enjoyed it.
Thank you, very informative! Subscribing and looking forward to see you implementing the winding order determination :)
I am currently looking to make some shorter videos that go into specific algorithms. That would be one of them.
thanks for the algorithm. Now im able to display face of the polygon in three.js
Awesome tutorial, mine implementation works flawlessly! Thank you very much!
Thanks for you video, really helped me! Why don't you make some videos about different triangulation algorithms? or you could make video with information how to triangulate polygons with holes using Ear Clipping algorithm. Thanks!
Your welcome! I will look into doing that. One possibility for polygons with holes is to divide the polygon into multiple concave polygons by connecting two of the "outer" polygon vertices with two of the "inner" or "hole" polygon vertices to create two concave polygons instead of an "outer" and "inner" polygon.
@@two-bitcoding8018 I am also interested in a video about polygons with holes, or different algorithms like Delaunay triangulation
@@Xan9999 Hi! Not sure if that is something a can do soon but I will look into it. Thanks for the interest!
Thanks, these 2 videos were just what I was looking for and really well explained! Now I just need to try and get this working with holes - I see that in theory you can just link the hole to the outer loop effectively creating one big concave polygon that wraps around the hole/holes.. just not sure on how to go about finding the best vertices to link together?
hi! Thanks for watching! I don't know enough right now to talk about automatically finding the concave polygons when holes are included. I does seem like the "hole" polygon vertices would have to be in the opposite winding order of the surrounding "outer" polygon vertices. Can you manually describe all of your polygons as concave polygons and just have some vertices from one polygon on top of the vertices from another polygon giving the appearance of "holes"?
@@two-bitcoding8018 & @MatthewMawman Coming from the GIS space, "donut" polygons is a problem that should be pretty well solved. You're right in that the hole vertices will be in the opposite direction as the outer vertices. It gets to be a real friggin headache when you have polygons that intersect themselves or when there is a "donut hole" inside of a donut hole. Anyway, in GIS the polygon (aka. feature) has the notion of "parts" or "rings". (Think of the State of Michigan which has 2 separate pieces to it). You might find some good stuff relating to this if you google "GIS" along with your search terms. Maybe checkout PostGIS which is the open source GIS plugin to Postgres which likely has these algorithms nailed down. (I doubt they use polygon triangulation... but who knows!)
Thank you very much for the tutorial, it was very helpful!
Thank you for your sharing.
Hey Thanks for the explanation.It helped me a lot. Also can you please update your github repo code so that we an go through how you implemented greens algorithm to determine the winding order
Yes. Sorry I haven't updated the code yet online. I am working on that.
Awesome, and thanks a ton!!
Very cool... No part 3? Also, did you happen to finish the code in your GitHub?
Do you have the next video?
Sorry, not yet. Stay tuned!
Nice explaintation. Thx! )
Your welcome!
Great Video! You should consider running some Udemy courses about it! Thx for your work!🏆
nice video help a lot thanks
Your welcome. Glad I could help!
hmm, this code assumes that the last 3 vertixes creates a valid triangle? would it not be better to validate the last 3 vertixes? cuz when u try to triangulate a polygon that is not valid, you often noticde that at the last 3 vertixes.
well, you do some validation at the start but still feelz like an check in the end is needed to confirm that everything is OK.
I think the way we verify that the original vertices define a simple polygon indicates that the last 3 vertices must be the final triangle.
Hi,
I have implemented your algorithm in Lua. After replace "if cross1 > 0 or cross2 > 0 or cross3 > 0 then" (code in Lua) with "if cross1 < 0 or cross2 < 0 or cross3 < 0 then" in isPointInTriangle function output correct list of triangles. Can you check that? Have a nice day:)
Yes. Good catch. I could have clarified this a little more. It will depend totally on the coordinate system you are using and the winding order that the vertices of the triangle are provided in. I am using positive "X" is to the right, positive "Y" is up, and positive "Z" is out of the screen. I am also using a clockwise winding order for the triangles.
Math is fun!
How can I make it work counterclockwise?
Hello, I tried using this algorithm with a polygon with holes but at some point cross(AB, AC) is always negative and makes the loop infinite.
I combined the polygons by connecting one point of the polygon's hole and one point of the outer polygon (the ones with the minimum distance from each other).
Maybe the problem is that the 2 points are duplicated and this algorithm doesnt support that?
I think you are probably right. The algorithm definitely does not support "holes" out of the box. You would have to manually cut the polygons with holes into concave simple polygons and then join them together. But I don't know.. maybe it could be modified to support that feature if you could find the correct vertex order and determine which vertices are "interior" and which vertices are "exterior".
When the reminder is 0 and you add the array length, it overflows...
Hi, I want to know how to implement Triangulate in 3D space, how to compute the CrossProduct with (X,Y,Z) . My coordinate system is positive "X" is in the screen, positive "Y" is to the right.and positive "Z" is up.
I would look into the Marching Cubes algorithm for what you're looking to achieve
good
How might you do subtraction? Such as a polygon inside a polygon which acts like a hole in the mesh, that's what I'm trying to implement but have no idea how to do it
You just do the same but don't allow comparing points that are defined as internal to form triangle inside them
when are you gonna continue this? :(
Can you please zoom in a bit? The text is barely readable at 480p
This code is buggy. Use 4 vertexes like a rectangle. p1(0,0), p2(0,100), p3(100,100), p4(0,100). Debug a,b,c ... The first triangle index order is 0,3,2... this result is not clockwise and cause issues if your continue working with triangles. Each time the for loop index is 0 or max, then the order must be changed to have a consistency in triangle winding.
Hi, Thanks for watching! I noticed that p2 is the same as p4. Was that intentional or just a typo?
I'm not saying the code is infallible but I tried it with those vertices except with p4(100, 0) and it seemed to work.
@@two-bitcoding8018 Yes sorry (was a typo): Did you have the code as text file?
I have some serious problems to port the code into another programming language. Thank you.
@@rogercabo5545 Sure. I will put a link to the source code in the video description.