NMO - 1 year ago 66

C# Question

I need to triangulate a 3D polygon (a planar set of ordered vertices). To do this, I rotate the polygon into the X/Z plane and apply an ear clipping algorithm to the rotated vertices. After that, I rotate the vertices back and have a triangulated polygon.

However, I seem to have an error in my rotation.

To rotate my polygons into the X/Z plane, I do the following:

First, I take the normal vector of the polygon and create an inverse rotation matrix out of it

`internal static Matrix4 CreateInverseRotationMatrix(Vector3 up) // up is normal vector of polygon`

{

Vector3 right;

// take the longer axis and calculate a normal vector

if (up.X.AbsoluteValue > up.Z.AbsoluteValue)

right = up.Cross(new Vector3(0, 0, 1));

else

right = up.Cross(new Vector3(1, 0, 0));

// create the third vector of the matrix

var backward = right.Cross(up);

// create inverse rotation matrix

Matrix4<Rational> m = new Matrix4<Rational>(right.X, right.Y, right.Z, 0, up.X, up.Y, up.Z, 0, backward.X, backward.Y, backward.Z, 0, 0, 0, 0, 1);

return m;

}

After that, I multiply each vertex with the inverse rotation matrix:

`private List<Vector2> CreateRotatedVertexList(List<Vertex3> contourVertices, Vector3 up)`

{

var matrix = Matrix4.CreateInverseRotationMatrix(up);

List<Vector2> points = new List<Vector2>();

foreach (var vertex in contourVertices)

{

var rotatedVertex = Matrix4.Multiply(matrix, vertex.Vector3);

var point = new Vector2m(rotatedVertex.X, rotatedVertex.Z);

points.Add(point);

}

return points;

}

The Matrix4.Multiply looks like this:

`public static Vector3 Multiply(Matrix4 m, Vector3 vec4)`

{

Vector3 res = Vector3.Zero();

res.X = m.M11 * vec4.X + m.M12 * vec4.Y + m.M13 * vec4.Z + m.M14;

res.Y = m.M21 * vec4.X + m.M22 * vec4.Y + m.M23 * vec4.Z + m.M24;

res.Z = m.M31 * vec4.X + m.M32 * vec4.Y + m.M33 * vec4.Z + m.M34;

var w = m.M41*vec4.X + m.M42*vec4.Y + m.M43*vec4.Z + m.M44;

return res;

}

I have drawn an example polygon in Blender. For example, the polygon P ={(-1 1 1), (-0.5 1 0.5), (0 1 0), (0.5 0.5 0), (1 0 0), (1 -0.5 0.5), (1 -1 1)}

And the rotated polygon PR = {(0 1 -4) (0,5 1 -2,5) (1 1 -1) (0,5 1 0,5) (0 1 2) (-1 1 2) (-2 1 2)}.

The y-components of the rotated vertices are all 1, so the polygon lies in the X/Z plane, thats correct. But the shape of the rotated polygon looks clearly different, compared to the unrotated polygon and I don't know why.

Answer Source

I have forgotten to normalize the basis vectors. So it should be:

```
internal static Matrix4 CreateInverseRotationMatrix(Vector3 up) // up is normal vector of polygon
{
Vector3 right;
up = up.Unit();
// take the longer axis and calculate a normal vector
if (up.X.AbsoluteValue > up.Z.AbsoluteValue)
right = up.Cross(new Vector3(0, 0, 1));
else
right = up.Cross(new Vector3(1, 0, 0));
right = right.Unit();
// create the third vector of the matrix
var backward = right.Cross(up);
// create inverse rotation matrix
Matrix4<Rational> m = new Matrix4<Rational>(right.X, right.Y, right.Z, 0, up.X, up.Y, up.Z, 0, backward.X, backward.Y, backward.Z, 0, 0, 0, 0, 1);
return m;
}
```