3d point sits on a 3d line?

OpenGL
1

I’ve just read the Redbook’s hint on averaging approximated surface normals on a point. The trick is to calculate the normal on the faces that are adjacent to the point and average them.

Finding faces adjacent to a point isn’t too hard if that point sits on the corner of every of its adjacent faces… but should it be calculated if that point is on the tip of one or two triangles, but on the edge of another one?

if so, then I have to evaluate if a given point sits on a line.
Calculating if a 2d point sits on a 2d line is easy, but doing so in 3d is quite harder. Am I right to believe I can achieve that by calculating that as if one 3d line was a combination of three 2d lines? (i.e. compare the slope of the xy component, compare xz, compare yz, if the point lies on all three slopes, then it lies on the 3d line)?

If that works, I should be able to find efficient algorithms to quickly find adjacent faces.

2

Hi Setzer,

This geometric situation is often called a t-junction, since the intersection of one edge with another resembles a T. This problem is illustrated graphically in the RedBook (a diamond with a T in the middle).

Whether you should calculate normals at these t-junctions depends largely on what you’re rendering and to what degree your object relies on vertex adjacency. For instance, if your’re using per-vertex lighting, and you have a coarse subdivision in your model, then interpolation artifacts could be severe. To make matters worse, cracks can appear in the rasterization between these problem edges. You might therefore consider fixing the t-juctions, which is related to your second question.

Finding the distance of a point to a line is easily determined with a little vector arithmetic.

 
           o V
          /|
         / |
        /  |
       /   | D
      /    |
     /     |
  A o--->--o-------------------------o B
        E

Here, A and B are two end-points of an edge; V is some vertex on another edge we’re testing for a t-junction; D is the distance from V to the line segment AB; and E is the normalized edge direction (B - A) / length(B - A).

If V is on the edge AB, then D = 0, so we need only solve for D:

D = length(V - (A + E * dot(V - A, E)) ).

Due to floating-point math, this calculation will seldom yield a 0, so you might consider anything within a small epsilon to be on the edge. For example, if D is lest than 0.1, then insert the vertex V between A and B. If V is between A and B, then dot(V - A, E) is greater than -e, and dot(V - A, E) is less than length(B - A) + e, where e is some small value to account for floating-point error. It’s also important to snap vertices consistently so as to avoid creating gaps where you intend to remove them.

Note that if you’re using per-pixel lighting, then normals may not be a problem, but the cracks could continue to be a specter. It all really depends on your particulars.

I hope this helps.