Moving on ... Polygon Triangulation Progress
I've finally moved on from the polygon expansion code, which works very well now.* My new challenge has been to create a polygon triangulation service.
For those in the know, triangulation is a useful process for creating 3D meshes. Models tend to be built from triangular faces, so, in order to create 3D models for RoomBuilder, it is important to be able to move from the 2D to 3D world. The triangulation code does this. Essentially, it divides a polygon into non overlapping triangles to create a solid face.
There are many different ways of approaching triangulation, most of which are concerned with either speed or mesh quality. It is possible to implement very efficient, scalable solutions for convex polygons, however, reflex verticies make the triangulation process more difficult.
At the moment, I am not so concerned about speed. I would rather have a reasonably efficient, robust routine that can be easily debugged, than something more esoteric and potentially harder to maintain. I therefore chose to adopt the standard ear-clipping technique (technically, I am reimplementing my C++ solution in .Net, so had some code lying around). This technique is easy to understand and copes with both convex and concave polygons. However, it does not support polygons which contain holes. I therefore had to write an additional routine which is used to split a polygon with N holes into N+1 polygons.
For now, here's a diagram of the process for a complex shape, showing the various processing stages.
[1] This is the initial shape. It is composed of a square with five circular holes, represented by bezier curves.
[2] The first processing stage linearises the bezier curves, essentially approximating the outline using straight lines.
[3] The code then splits the polygon into several shapes which do not contain holes.
[4] Finally, each split polygon is processing by the ear clipping routine. The union of the shapes is the triangulation of the shape in 2.
It's worth making a few observations.
Firstly, the linearisation routine is pretty crude and uses simple, recursive subdivision. At some stage I will write a more efficient and accurate routine. Note, there is a slight problem with a missing point. This needs fixing.
Secondly, some care is required when splitting the polygon, since it is possible that some holes have no direct line of sight to the outline - as in the case of the inner circular hole in this example.
Finally, the ear-clipping routine does not add any additional vertices to the mesh. Some routines will do this to improve the output. While the mesh is correctly triangulated and the holes are preserved, constraining the output to produce fewer 'tall and thin' triangles could be useful. Particularly for some 3D rendering engines.
Next, I'll be looking into the first of the 3D routines - making bevelled shapes. For the moment I'm looking at my existing code and trying to work out how much I need to rewrite and compared to how much use I can make of the WPF 3D classes. Fingers crossed.
* Well, there's always one edge case that gives problems. Oh well...
For those in the know, triangulation is a useful process for creating 3D meshes. Models tend to be built from triangular faces, so, in order to create 3D models for RoomBuilder, it is important to be able to move from the 2D to 3D world. The triangulation code does this. Essentially, it divides a polygon into non overlapping triangles to create a solid face.
There are many different ways of approaching triangulation, most of which are concerned with either speed or mesh quality. It is possible to implement very efficient, scalable solutions for convex polygons, however, reflex verticies make the triangulation process more difficult.
At the moment, I am not so concerned about speed. I would rather have a reasonably efficient, robust routine that can be easily debugged, than something more esoteric and potentially harder to maintain. I therefore chose to adopt the standard ear-clipping technique (technically, I am reimplementing my C++ solution in .Net, so had some code lying around). This technique is easy to understand and copes with both convex and concave polygons. However, it does not support polygons which contain holes. I therefore had to write an additional routine which is used to split a polygon with N holes into N+1 polygons.
For now, here's a diagram of the process for a complex shape, showing the various processing stages.
[1] This is the initial shape. It is composed of a square with five circular holes, represented by bezier curves.
[2] The first processing stage linearises the bezier curves, essentially approximating the outline using straight lines.
[3] The code then splits the polygon into several shapes which do not contain holes.
[4] Finally, each split polygon is processing by the ear clipping routine. The union of the shapes is the triangulation of the shape in 2.
It's worth making a few observations.
Firstly, the linearisation routine is pretty crude and uses simple, recursive subdivision. At some stage I will write a more efficient and accurate routine. Note, there is a slight problem with a missing point. This needs fixing.
Secondly, some care is required when splitting the polygon, since it is possible that some holes have no direct line of sight to the outline - as in the case of the inner circular hole in this example.
Finally, the ear-clipping routine does not add any additional vertices to the mesh. Some routines will do this to improve the output. While the mesh is correctly triangulated and the holes are preserved, constraining the output to produce fewer 'tall and thin' triangles could be useful. Particularly for some 3D rendering engines.
Next, I'll be looking into the first of the 3D routines - making bevelled shapes. For the moment I'm looking at my existing code and trying to work out how much I need to rewrite and compared to how much use I can make of the WPF 3D classes. Fingers crossed.
* Well, there's always one edge case that gives problems. Oh well...
Comments