Monday, 16 May 2016
Merging of Adjacent Coplanar Polygons
It's a fairly common geometric case: one or more polygons (N-GONS) reside upon a specific 3D Plane - the polygons are coplanar, and are effectively 2D - we know that they are all convex, and that they share some Edges, implying that they could be Welded into (possibly non-convex) polygons by eliminating the shared edges.
I decided early not to try to solve this via 2D projection onto a principle axis, but rather to take advantage of the circular nature of polygonal descriptors - find the matching edges, and describe the remaining polygon in pure 3D terms.
The first problem that I encountered is that my polygons have no defined winding order - they are based on 'super planes' which span the worldspace, and there's no particular way they should be viewed. Therefore, I needed a way to define whether two polygons have the same winding order, or the reverse order - I did not care if it was 'clockwise' or not, which only makes sense for a particular viewpoint, but I did care if they were not the same ordering given a fixed viewpoint.
Several days of research later, having investigated all manner of strange solutions including winged-structures, I came across a simple solution for discovering the surface-normal of an arbitrary planar polygon, I'll post this source here in case it's helpful to someone else.
It's incredibly stable - it works for lots of special cases, perhaps ALL special cases - and as such, I believe this to be a true Code Gem and worth sharing with the world.
Given a polygon as a circular list of vertices, this code will return the surface normal, even if the polygon is not quite coplanar, it will return a reasonable average normal, which can be construed as implying a winding order (the signed dot product of the calculated normal, with some fixed base normal, is either plus or minus, indicating counterclockwise or clockwise, I believe).
At any rate, I'm certainly one step closer to my current goal of simplifying portal geometry extracted heuristically from a triangle soup!
// Newell Brothers' Method for calculating SurfaceNormal of Arbitrary Polygon
// Works on both convex and concave planar polygons, and even works if the polygon is not quite planar,
// or the polygon has colinear edges, or other weird corner-cases - seems to work in ALL cases.
// I believe this was published in around 1990/1991
//
glm::vec3 GetNormal (PORTAL* Polygon)
{
glm::vec3 Normal(0); // initialize zero vector
for(unsigned short i=0;i<Polygon->Vertex.size();i++)
{
VERTEX& va=Polygon->Vertex[i];
VERTEX& vb=Polygon->Vertex[(i+1) % Polygon->Vertex.size()];
Normal.x += (va.y - vb.y) * (va.z + vb.z);
Normal.y += (va.z - vb.z) * (va.x + vb.x);
Normal.z += (va.x - vb.x) * (va.y + vb.y);
}
return glm::normalize(Normal); // return normalized vector
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment