2

I have two samples of 3D point cloud of human face. The blue point cloud denote target face and the red point cloud indicates the template. The image below shows that the target and template face are aligned in different directions (target face roughly along x-axis, template face roughly along y-axis).

Figure 1: enter image description here The region around the nose is displayed in Figure 1.

I want to rotate my target face (blue face) with nasal tip as the center of rotation (I translated the target to the template prior to Figure1 so that the tip of nose, i.e., the centerpt, for both faces are superimposed) to grossly align with the template face (red face). I rotated the target face with the following MATLAB code:

% PCA for the target face
targetFaceptfmt = pointCloud(targetFace); % Convert to point cloud format
point = [templateFace(3522, 1), templateFace(3522, 2), templateFace(3522, 3)]; % The 3522th point in the templateFace is the nasal tip point used as center of rotation later on
radius = 20; % 20mm
[NNTarIndex, NNTarDist] = findNeighborsInRadius(Locationptfmt, point, radius); % Find all vertices within 20 of the nasal tip point on the target face
NNTar = select(Locationptfmt, NNTarIndex); % Select the identified points for PCA
[TarVec,TarSCORE,TarVal] = pca(NNTar.Location); % Do PCA for target face using vertices close to the nasal tip

% PCA for the template face
templateFaceptfmt = pointCloud(templateFace); % Convert to point cloud format
[NNTemIndex, NNTemDist] = findNeighborsInRadius( templateFaceptfmt, point, radius); % Find all vertices within 20 of the nasal tip point on the template
NNTem = select(templateFaceptfmt, NNTemIndex); % Select the identified points for PCA
[TemVec,TemSCORE,TemVal] = pca(NNTem.Location); % Do PCA for template face using vertices close to the nasal tip

% Rotate target face with nasal tip point as the center of rotation
targetFace_r = R * (targetFace-cenertpt)' + centerpt';
targetFace_new = targetFace_r';

where targetFace and templateFace contains coordinates for the unrotated target face and the template face, respectively. The targetFace_r contains coordinates for the target face after rotation around nasal tip, R is the rotation matrix calculated through PCA (See here for source of formula for rotation), and centerpt is the nasal tip point which is used as the center of rotation. I then plotted the transposed targetFace_r, i.e., the targetFace_new, with normals added to each vertex:

Figure 2: enter image description here

Before rotation, the normals for the target face and template face are generally pointing toward similar directions (Figure 1). After rotation, the target and template face are both aligned along the y-axis (which is what I want), however, normals for the target face and template face point toward opposite directions. Bearing in mind that no changes were made to the template face, I realized that normals of the target face calculated after rotation are flipped. But I do not know why. I used the checkFaceOrientation function of the Rvcg package in R to check if expansion along normals increases centroid size. I was returned TRUE for the template face but FALSE for the target face, which confirms that vertex normals for the target face are flipped.

Vertex normals were calculated in MATLAB as follows:

TR = triangulation(Faces, Vertices); % Triangulation based on face and vertex information
VN = vertexNormal(TR); % Calculate vertext normal

where Faces contains face information, i.e., the connectivity list, and Vertices contains coordiantes for vertices. For target face before rotation, target face after rotation, and template face, vertex normals were calcuated separately. I used the same Faces data for calculation of vertex normal before and after rotating the target face.

The flipped vertex normals resulted in errors for some further analyses. As a result, I have to manually flip the normals to make them pointing similarly to normals of the template face.

Figure 3: enter image description here Figure 3 shows that after manually flip the normals, normals of the target and template face are generally pointing similarly in direction.

My question is why does the normals of the target face calculated after rotation flipped? In what case does rotation of 3D point cloud result in flipping of vertex normals?

Some further informaiton that may be useful: the rotation matrix R I obtained is as follows for your reference:

0.0473096146726546  0.867593376108813   -0.495018720950670
0.987013081649028   0.0355601323276586  0.156654567895508
-0.153515396665006  0.496001220483328   0.854643675613313

Since trace(R) = 1 + 2cos(alpha), I calcualted alpha through acos((trace(R)-1)/2)*180/pi, which yielded an angle of rotation of 91.7904, relative to the nasal tip point.

Patrick
  • 1,057
  • 9
  • 23
  • Some times, when the rotation angle is about 180°, rotation matrix calculated using PCA or SVD might have negative determinant, which means that it is not a rotation but a reflection. That might cause this type of error. – Mauricio Cele Lopez Belon Apr 29 '19 at 20:47
  • 1
    Do you simply transform the normals using the rotation or do you re-calculate them somehow? The PCA method will produce a valid rotation (without reflection) if you make sure that the two eigen systems have the correct handedness. – Nico Schertler Apr 30 '19 at 01:03
  • Hi Belon, I provided more detail on how rotation was performed. I actually aligned nasal tip point of both face first, after which R was calculated based on PCA. Rotation was then performed with R and with nasal tip point (not the origin) as the center of rotation. I calcualted the angle of rotation to be 91.8 degrees. Does this mean a rotation greater than 90 degree will result in flipping of the normals? – Patrick Apr 30 '19 at 02:41
  • Hi @Schertler, normals were calculated separately before and after rotating the target face. I did not transform the normals, instead, they were calculated based on the coordinate data and face information. I also added more information on PCA in my post. – Patrick Apr 30 '19 at 03:12
  • 2
    I don't know matlab internals, but the usual way to calculate normals aims for consistency with the direction in which triangles are specified, e.g. if you look in the direction of the normal all triangles will be specified in a clockwise direction. But your data appears to be a set of points, so the triangulation is equally valid in either direction, and triangulation algorithms will not always pick the same direction. – user2554330 Apr 30 '19 at 12:57

2 Answers2

4

If I'm understanding everything correctly, it looks like your rotation matrix is actually encoding a rotation plus a reflection. If your matrix is approximately:

 0.04  0.86  -0.49
 0.98  0.03   0.15
-0.15  0.49   0.85

Then the image of each unit vector pointing along the positive axes are:

x = [ 0.04 0.98 -0.15]
y = [ 0.86 0.03  0.49]
z = [-0.49 0.15  0.85]

However, if you take the cross-product of x and y (cross(x, y)), you get approximately [0.49 -0.15 -0.85], which is the negation of z, which implies that the matrix is encoding both a rotation and a reflection. Naturally, multiplying a mesh's vertices by a reflection matrix will reverse the winding order of its polygons, yielding inverted normals.

In the slides that you referenced, it states that the PCA method of generating a rotation matrix should only be considering four different combinations of axes in the 3D case, to ensure that the output matrix obeys the right-hand rule. If all combinations of axes were checked, that would allow PCA to consider both rotated and reflected spaces when searching for a best match. If that were the case, and if there some noise in the data such that the left half of the template is a slightly better match to the right half of the target and vice versa, then the PCA method might generate a reflection matrix like the one you observe. Perhaps you might want to reexamine the logic of how R is generated from the PCA results?

Joe Lee
  • 506
  • 3
  • 6
  • I calculated the rotation matrix through `R = TemVec * TarVec'`, where `TemVec` is the matrix of eigenvectors for the template face and `TarVec` is the matrix of eigenvectors for the target face. It is strange why cross-product of `x` and `y` yielded a vector opposite to the direction of normals for z-axis from the above formula. Do I have to transform `R` to constrain it to one of the four combinations. But a further question would be which one of the four to choose? – Patrick Apr 30 '19 at 19:02
  • 1
    Basically, you want to do the stuff on slide 20. I believe "fix the orientation of the source axes" means precisely "recalculate one of the rotation columns from the cross-product of the other two", as above. You'd want to do this for both `TemVec` and `TarVec`. Then, for a `TarVec` with columns `x`, `y`, and `z` (i.e. equal to `[x;y;z]'`), you'd want to try calculating R with a `TarVec` of each of `[x;y;z]', [-x;-y;z]', [-x;y;-z]', [x;-y;-z]'`, choosing the one that yields the smallest rotation, as evaluated using the trace. – Joe Lee Apr 30 '19 at 19:43
  • I followed your method and the code and results I got are stored in the Determine R.m file in https://github.com/Patricklv/Determine-rotation-matrix. My results showed the [x; y; z]' of TarVec, i.e., the same one as before, had the largest trace, hence the smallest angle of rotation. Anything wrong in my code? – Patrick May 01 '19 at 08:05
  • If I repeat the cross-product test for each of the matrices in your output, I can see that each is still encoding a reflection. *None* of the four matrices should be encoding a reflection if they were generated after "fixing the orientation of the source axes", so I assume you are still not doing that step. Again: After you get `TemVec` and `TarVec` from the PCA process, you must update their third columns to be the result of the cross-product of their first two columns. This will remove any reflection, leaving you with just the rotation. – Joe Lee May 01 '19 at 17:47
2

As alluded to in the comments, the direction of your vertex normals will depend on how you've ordered the triangular facets in your Faces matrix. This will follow a right-hand rule, where your fingers follow the vertex order around the triangle and your thumb indicates the surface normal direction. Here's a simple example to help illustrate:

Vertices = [0 0; 0 1; 1 1; 1 0];  % Points clockwise around a unit square in x-y plane
Faces = [1 2 3; 1 3 4];           % Two triangular facets, clockwise vertex ordering
TR = triangulation(Faces, Vertices);
VN = vertexNormal(TR)

VN =

     0     0    -1
     0     0    -1
     0     0    -1
     0     0    -1

In this example, Vertices contains the 4 vertices of a unit square in the x-y plane, ordered clockwise if you're looking down from positive z. Two triangular facets are defined in Faces, and the order of the indices in each row traces along the vertices in a clockwise fashion as well. This results in a surface normal for each face that points in the negative z direction. When the vertex normals are computed, they are pointing in the negative z direction as well.

What happens when we flip the order of one triangle so that its points are counter-clockwise?...

Faces = [1 2 3; 1 4 3];  % Second facet is 1 4 3 instead of 1 3 4
TR = triangulation(Faces, Vertices);
VN = vertexNormal(TR)

VN =

     0     0     0
     0     0    -1
     0     0     0
     0     0     1

The surface normal of the second triangle will now point in the positive z direction. The vertices that are only used by one triangle (rows 2 and 4) will have vertex normals that match the surface normals, while the vertices shared by each (rows 1 and 3) will have vertex normals of 0 (the two surface normals cancel).

How will this help you with your problem? Well, it's hard to say since I don't know exactly how you are defining Faces and Vertices. However, if you know for certain that every vertex normal in your mesh is pointing in the wrong direction, you can easily flip them all by swapping two columns in your Faces matrix before computing the normals:

Faces = [1 2 3; 1 3 4];  % Clockwise-ordered vertices
TR = triangulation(Faces(:, [1 3 2]), Vertices);  % Change to counter-clockwise
VN = vertexNormal(TR)

VN =

     0     0     1  % Normals are now pointing in positive z
     0     0     1
     0     0     1
     0     0     1
gnovice
  • 125,304
  • 15
  • 256
  • 359
  • Thank you for your answer. I agree that the automatic flipping of vertex normals is most likely due to rotation that changed the order of vertices. I calculated from the rotation matrix that the targe face was rotated 91.7904 degrees. Do you think it safe to conclude that once the angle of rotation was greater than 90 degrees, the vertex normals will be flipped? BTW, how should I conceptualize the 91.7904 degrees in 3D, which axis is it relative to? – Patrick Apr 30 '19 at 15:58