triangulating a triangle into a grid [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 5 years ago.

Improve this question

Is there an algorithm for dividing a triangle that may span multiple grid elements into multiple triangles, where there are no triangles that span multiple grid elements?

I've included a crappy hand-drawing of a triangle in a 2x2 grid being diced into seven smaller triangles.

Answer 1

I see it like this:

Your triangle is 3 lines closed polygon
order of points gives you winding rule (CW or CCW)

1. cut all lines by grid lines

   but still leave triangle as single closed polygon and do not change winding

2. split polygon to few line lists

   just group together all lines belonging to the same grid cell so all point is inside or on edge of the cell. Again do not change winding !!!

3. convert line lists to closed polygons

   start with first line in the first line list in its direction. If it is joining any line in actual list continue with it. If not then continue with cell edge line in the same winding direction until hit another line point or cell corner.

   Repeat this until closed polygon is formed for this cell (hit already used line/point)). Process other cells in the same way

4. now you have closed convex polygon list

   so just split it to triangles (triangle fan)

Answer 2

It's actually very refreshing to see that someone else has also attempted this at one point, besides me (I've been writing an engine in OpenGL that builds terrain off of this concept, but also puts it in 3d).

That being said, Spektre is right on the money. I have several rules my engine follows that are similiar to his:

• Stick to CW or CCW winding (I am using CW)

• It's only triangles that I am splitting into even smaller triangles, so they are all convex -- so there are no concave polygons.

• The formula for detecting the number of triangles you'll split into is N - 2, where N is the number of points in the cell. Obviously if it's 3, you have a perfect triangle (such as the blue triangle in the grid cell above)

I will try to upload some pictures for you later. Hopefully you are still working on this or at least made progress!