I’m implementing a mesh hole patch algorithm and there’s a case I can’t find a graceful way to handle.
My hole is defined as a series of indices within my vertex array that form a closed loop. When I get the angle between two points, 9/10 times its correct, but that one case where the angle is > 180 degrees throws off my calculation because the algorithm incorrectly assumes the angle is small and in the wrong direction. See blue triangle and associated angle in screenshot:
I need a way to robustly determine angles that are INNER to my hole. Can anyone suggest a solution?
Assuming you use vertex v1, v2 and v3 and want to determine the angle between vector (v1,v2) and vector (v2,v3):
Construct a plane which contains vector (v1,v2) (ie. the vector lies in that plane). Now if the point v3 is in front of the plane then the angle between the vectors will be > 180 degree, otherwise it will be < 180 degree.
Let’s assume you know how your vertices are ordered around this ‘hole’.
Compute edge vectors and outward pointing normals as follows:
For edges: E1=V2-V1, E2=V3-V2, E3=V4-V3, where the V vectors are simply the coordinates of each vertex.
Normal vectors are 90 deg rotations of edge vectors if the vertices are ordered clockwise (CW) and -90 deg rotations for counterclockwise (CCW) winding. When I say ‘rotations’, I mean rotations about the Z axis (assuming the vertices are defined in the XY plane). Since you’re working in 2D you don’t have to do real rotations (i.e. matrix multiplications). You can use the negative reciprocal rule. Say an edge vector has components (u,v). It’s normal would be (-v,u) for CW and (v,-u) for CCW.
For each edge take the dot product (DP) of the edge vector with the NEXT edge’s normal vector.
If DP >= 0.0 you are o.k.
If DP < 0.0 you have an edge turning outward.
An outward turning edge means you have a concave polygon.
I haven’t actually coded this up, but I think it works.
I thought of this. I was hoping to avoid being dependant on the winding direction, but I suppose I must.
My only problem is that this actually is in 3D, so my edge vectors are 3x1’s. How would the normals to just a single 3D vector be defined? I could project them like they’re shown here, but I want this to work arbitrarily for any arrangement of a 3D hole.
There is an infinite number of normals to a single 3D vector, all lying in the plane perpendicular to the vector. You need two vectors to get a normal. The normal is the cross product of the two vectors. In your case, you could take the cross product of two successive edge vectors to get a normal.
Fair enough, but that normal will be essentially perpendicular to the hole right? I need something that tells me whether or not I’m within the hole or not. I guess the fact that this is 3D and not 2D is messing with my mind.
If you can be clearer about what you’re starting with and what you want, I might be able to help. It sounds like you have a set of co-planar points in 3-space that you want to think of as the boundary points of a polygon. Correct? Do you know how the vertices are ordered around the polygon? Do you know about convex hulls? The hull of your set of points would be the polygon formed IGNORING all the inward vertices (which make dents in the poly). Could this be what you want? If so, Google ‘Convex Hulls’.
The points are not co-planar, nor can that assumption be made. Essentially I’m trying to implement is in the link to the paper above. Its an arbitrary gap filling algorithm for any kind of would-be closed 3D object.
The paper mentioned nothing of needing a convex hull nor winding direction, but most academic papers intentionally leave out those kind of details.
If you just want to fill the hole, without any consideration to the smoothness and quality of the patch, then you need to check the references:
“…the advancing front mesh (AFM) technique [10] to generate an initial patch mesh over the hole.
This method can always patch the hole, whatever its shape [10], and guarantee the robustness of our algorithm.”
George, L.P., Seveno, E.: The advancing-front mesh generation method revisited. Int. J. Numer. Methods Eng.
37(7), 3605-3619 (1994)
This is what they use to fill it. The rest of the paper uses complex math to make the hole look “pretty”.
Okay so surprisingly, after finally getting ahold of that reference, it turns out its implemented only for 2D!!!
What I’m doing is this. Using 3D principal component analysis to extract the first two eigenvectors of the hole. This will help me fit an optimal plane from the two vectors to project the hole onto, thus making it a 2D problem, then I can find out what is “inner” and “outer” to my hole.
