• ### What is your GameDev Story?

#### Archived

This topic is now archived and is closed to further replies.

# Dividing polygons into triangles automatically

This topic is 5351 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm working on a 3d-engine that uses maps similar to the doom engine (original, not doom III). I create sectors in a map program and define the floor height, ceiling height and lighting value for the sector. Then the map is converted into 3d-geometry to be rendered. the walls are easy because they are just quads (x1, floorheight, z1) to (x2, floorheight, z2) to (x1, ceilingheight, z1) to (x2, ceilingheight, z2). Pretty simple. The problem is the floor and ceiling geometry. since each sector can be made out of any number of vertices, it's nolonger a simple matter to divide the floor and ceiling polygons into triangles automatically so that they can be rendered in direct3d. I could always make a way to divide it manually in the map editor but I'd really like to be able to figure out some kind of algorithm that could divide the polygons into triangles automatically. Does any have any ideas or know of any resources where I could get some information on this matter? thanks [edited by - KevinCoyle on April 12, 2004 7:22:19 PM]

##### Share on other sites
Google for "triangulation", "Delaunay Triangulation", "splitting Polygons"!

##### Share on other sites
Hi Kevin,

I have actually created a similar engine of yours, you can find out the executable at my web page:
Doomviewer Page

Note: This application is using original Doom/Doom2/Hexen/Heretic/Strife wad files and make 3D preview of theese maps using Direct3D. Internal it converts the sectors to triangles. The application is written using Borland Delphi. If you are interesting in the source code that split the sectors to triangles please contact me.

Jim Valavanis.

[edited by - Jimmy Valavanis on May 26, 2004 8:33:43 AM]

##### Share on other sites
I doesn't sound too hard. If you have a 3 point floor, that's 1 triangle. If it's 4 points, that's 2 triangles. If it's 5 points that's 3 triangles and so on. So the number of triangles you need is very easy to obtain. It's the number of vertices in your polygon minus 2.

How to divide those vertices into polygons... I would do it like this.

Determine a clockwise or counterclockwise ordering of the points of the polygon (as if you were trying to find a convex hull using the gram scan alg.). If you have this clockwise or counterclockwise ordering, then you can just take the first point in the ordering and every pair of points aftewards to get your triangles.

So for a six sided convex sector: with clockwise ordered points (0,0) (1,1) (1,2) (0,3) (-1,2) and (-1,1) your triangles would all contain (0,0) as the first point and the other two points would be each following pair:

(0,0) (1,1) (1,2)
(0,0) (1,2) (0,3)
(0,0) (0,3) (-1,2)
(0,0) (-1,2) (-1,1)

That's six minus two = four triangles.

To sort the points clockwise or counterclockwise, just choose the lowest y value and translate all the points so that this lowest y value is now at the origin. Calculate the polar angle of each coordinate from the y axis and sort using this angle.

Here's some code (though I would suggest not copy/pasting it as you'll need to provide a lot of hookups anyway and I modified a few things without testing it to make it easier to read)

     //Find the point with minimum y value, easy  lowest = points[0].y;  minlocation = 1;  for(i = 0; i < points.length; i++)    if (points[i].y < lowest) {         lowest = points[i].y;      minlocation = i;    }    //Swap the first value in your polygons point array with the min y point  swap(points, 0, minlocation);    //Calculate the polar angles  for (i = 1; i < points.length; i++) {      //These temp values represent the points translated towards the origin    tempX  = (points[i].x - points[0].x);    tempY  = (points[i].y - points[0].y);    if (points[i].x == points[0].x)      angles[i] = PI/2;    else if (points[i].x > points[0].x)      angles[i] = atan(tempY/tempX);    else // (points[i].x < points[0].x)      angles[i] = PI + atan(tempY/tempX);  }  angles[0] = 0; // the angle of P0 is effectively 0 for sorting purposes though it is                 // technically undefined

Now just run a sort alg on the angles array and select your triangles as I suggested above.

Btw, this would work for any arbitrary polygon anywhere in three space, it would just take a little more effort to sort your points into a clockwise ordering (maybe translate/rotate the polygon onto the XY plane and then use this same algorithm).

Hah, just noticed that the original post was from early april. Well, maybe someone will find this useful. Hell, I didn't even know how to break an arbitrary polygon up into triangles until I was forced to think about it. The problem of calculating the texture coordinates at each vertex remains, but that shouldn't be difficult.

[edited by - DavidST on May 3, 2004 5:03:06 PM]

##### Share on other sites
If you''re drawing a convex polygon, it''s easy - a triangle fan will do the job. You just pick a start vertex, and feed in all the rest in order. The fan fills out the poly.

A concave polygon is more of a problem, though. You could either:

1) Place a restriction in the editor which prevents people from creating non-convex sectors (i.e. limit the angles at each vertex so they are less than 180 degrees), so that a large sector gets split up. This would mean a bit more of a headache for your artists.

2) Algorithmically split sectors up into convex ones - so the artists create concave ones, but ''invisible'' sector boundaries are added by the editor so that the sectors are secretly convex.

I''d recommend the second approach, as it''s a one-time thing (one-time bit of coding) rather than the first approach which will hinder your artists throughout development.

I''m not totally sure how you''d go about splitting the concave polygon into convex ones, but I do know this: A split will have to occur at every vertex where the angle between the walls is greater than 180 (i.e. a reflexive angle). You may be able to do something like finding all reflexive vertices in a sector, and connecting each one to the nearest (but not adjacent) vertex to split into two sectors. Then you process each sector seperately, and keep going until everything is convex.

##### Share on other sites
The method I described is essentially a polygon fan as you can clearly see if you draw the algorithm out on paper. And yes it only works on convex polygons/sectors. I forgot to mention that little restriction.

I would point out that the convex requirement of level editors is a very common one, though thinking back, I think Doom allowed concave sectors. I never found it cumbersome to use convex brushes in the 3d games though (which all of them required). In fact, the alternative would make it possible to sculpt any object from a single brush which may be very error prone. One little error with the brush and your entire concave brush model is gone (happened from time to time with the convex brush models in world craft).

There is also the "complex" breed of sector/polygon to worry about (ones with holes in them). If sectors aren''t limited to convex only, then they can have holes and also overlap themselves.

http://www.it.uu.se/edu/course/homepage/grafik1/p4v04/Lectures/L02/LinePolygon/x_polyd.htm

A quick Google search reveals that it is indeed a very complex problem. Some guy made a relatively efficient algorithm for it to get his doctorate in 1985.

If you''re going to allow concave sectors, then you would be wise to look up an algorithm on the problem.

If you''re going to restrict the sectors to convex, then just use the triangle fan I described above.

I''m tempted to try and develop my own algorithm for breaking a concave polygon into a minimum number of convex ones (to which a triangle fan could be applied). I''m sure it won''t compete with the fastest available, but it would be fun. Alternatively, I could convert the concave sector directly into triangles which may be faster or easier.

If I come up with anything I''ll let you know. In the meantime, I would suggest google.

##### Share on other sites
The method I use is called "ear clipping" and works on convex and non-convex polygons.

Find the vertex n with the smallest distance between n and n+2.
Make a triangle from n, n+1, n+2.
Cut off the triangle (delete n+1 from the vertex list).
Repeat until there are only 2 points left.

It probably isn''t the quickest way, but is easy.

tm.

##### Share on other sites
There's a paper on ear clipping for more details

http://www.magic-software.com/Documentation/TriangulationByEarClipping.pdf

By the way, I don't think it would work as you described it. Just take a really large cube, and then take a tiny triangle out of the bottom in the very middle. Make sure the triangle is taller than it is wide. With this, the point n with shortest distance to point n+2 would definitely give you that triangle that I just mentioned... except that is a triangle that is NOT in the polygon.

The article explains the algorithm well enough (follow the example, don't try and read the poor description). Basically, start with a list of the convex edges, the reflexive edges and the ears by checking edge vertex.

Then you chop off an ear (already determined by your ear list). Now that you modified the polygon by chopping off an ear, you have to recalculate whether or not the two vertices next to the ear were changed by removing it (i.e. one might have gone from reflexive to convex). Then you just repeat this, choosing enother ear fromthe list at you go along.

As you guessed, the speed isn't great. O(n^3) for the easy implementation, O(n^2) for a better one. The very best you can get is O(n log n). However since this is being pre calculated, you can probably get away with this alg. Doesn't look too hard to code either.

[edited by - DavidST on May 4, 2004 2:08:04 AM]

##### Share on other sites
Oops, sorry about that. You are right.

The first step should be to find the triangle with the minimum distance between n and n+2 that has the points in the correct order.

In my code I test if n+2 is on the correct side of the line from n to n+1. This will teach me not to try and do this from memory.

tm

##### Share on other sites
There are probably a number of ways to do it, but I would follow this paper very closely because they provide an O(N^2) alg. when the typical implementation is O(N^3)

But yeah, working from memory and working without research is always a bad idea in computer graphics. I''ve made that mistake a few times.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634089
• Total Posts
3015460
×