Intersection of three planes and precision of computing

computational geometrylinear algebramachine precision

I have a simple 3D object made of a triangle mesh.
Here is a rendering of the mesh.
I would like to make a 'coat' which is another mesh over the primary one, where all new faces have equal distance from their primary faces. (shift in the direction of the normal vector)
I would like to calculate new vertices of new faces.

I proceeded following way:

  1. The vertices of the primary faces were shifted by this formula:

    new_point = primary_vertex + normalized_normal_vector * distance

  2. The new points of a face create a plane.

  3. I assume that intersection of these three planes – which have a mutual primary vertex – will be a position of the new vertex. (coat vertex)
  4. I assume that new edges will be parallel to the primary edges

I created a program in python to calculate the new mesh.
When I rendered the new mesh I was surprised by some new vertices which were in slightly different positions as I have expected. They don't create parallel edges.

There is not much to investigate on vertices which connect 3 faces. But for vertices, which connect more faces/planes, I can choose theoretically any combination of three planes to get the same vertex. Correct?

Following log snippet shows variation of results for vertex no.6:

coat point 6 = [319.3252516094884, 319.3252516094884, 326.87705891391334] C:(0, 1, 2)
coat point 6 = [319.3252516094907, 319.28274879320054, 326.8345560976249] C:(0, 1, 3)
coat point 6 = [319.3252516094907, 317.7371439521034, 325.28895125652684] C:(0, 1, 4)
coat point 6 = [319.3252516094907, 312.44819269557485, 319.9999999999999] C:(0, 1, 5)
coat point 6 = [319.0702347117457, 319.0702347117457, 327.6421096071429] C:(0, 2, 3)
coat point 6 = [320.1193054381856, 320.1193054381856, 324.49489742783106] C:(0, 2, 4)
coat point 6 = [321.6176045807944, 321.6176045807944, 319.99999999999994] C:(0, 2, 5)
coat point 6 = [320.0386076899993, 319.87721219362436, 324.57559517602044] C:(0, 3, 4)
coat point 6 = [321.4835324824246, 321.0813161873143, 320.0000000000022] C:(0, 3, 5)
coat point 6 = [324.61420286601555, 333.6039977216814, 319.9999999999999] C:(0, 4, 5)
coat point 6 = [319.1658660484023, 319.0702347117457, 327.7377409437999] C:(1, 2, 3)
coat point 6 = [319.79234209695875, 320.0725963894359, 324.3547702815919] C:(1, 2, 4)
coat point 6 = [320.59878103799315, 321.3628986950939, 319.99999999999994] C: (1, 2, 5)
coat point 6 = [319.7467802025177, 319.84478691723285, 324.44589407047033] C:(1, 3, 4)
coat point 6 = [320.531349744366, 320.89087963969985, 319.9999999999999] C:(1, 3, 5)
coat point 6 = [321.96972723775326, 330.9595220934171, 319.9999999999999] C:(1, 4, 5)
coat point 6 = [312.77581035312386, 319.0702347117469, 321.34768524851955] C:(2, 3, 4)
coat point 6 = [311.4281251046011, 319.0702347117457, 319.99999999999994] C: (2, 3, 5)
coat point 6 = [309.63121143990963, 318.62100629557546, 319.9999999999999] C:(2, 4, 5)
coat point 6 = [309.7435185439568, 318.73331339961675, 320.00000000000216] C:(3, 4, 5)

Notice for example the variation of x-coordinates: from 309.63 to 324.61
I need at least 0.1 precision.

I use following procedure http://www.ambrsoft.com/TrigoCalc/Plan3D/3PlanesIntersection_.htm for the intersections calculation.

I suspect that the problem is the precision limit of a computer calculation.

My questions:

a) are my assumptions correct?

b) is this really a problem of a computational precision?

c) any suggestions how to deal with that?

d) is there a way how to get a vector which moves the primary vertex to a new position?

thank you

Adding Openscad visualzation

  • magenta edges – original mesh
  • yellow edges – edges of the offset mesh
  • green triangles – offset faces
  • blue spheres – calculated intersection points

The point 6 is in the middle. Blue spheres show the different results of the computing. I suppose, in the ideal case, they should be fully aligned.

Best Answer

Using a 2D problem as an example, you can see that if three lines meet at a point, and you offset the lines by a fixed amount, the resulting lines won't meet at a single point. Each combination of two lines meets at a point.

Here is a visualization with three lines

OffsetLines1

The three dashed lines meet at a point. I offset the lines by the same amount (shown with circles) to create three solid blue lines. The three solid lines do not meet at a single point.

Something similar is going on in 3D, where the planes do not meet at a single point. It is not a numeric artifact, but a result of the geometry.

So now you have to make a decision on how to handle this situation. Each, three planes defines a vertex, and so you can define capping geometry by the number of vertices you have.

For example, four planes result in two vertices and thus can be capped with a line. An example is shown below of this.

FourPlanes1

This is as far as I can go with this at this point. You need to choose how to proceed. In my opinion, deriving points, lines, and planes from other points, lines, and planes is done easiest with homogeneous coordinates.

$$ \begin{aligned} \mbox{Point} & = \left( \matrix{ \overrightarrow{\mbox{position}} \\ 1 } \right) & \mbox{Plane} & = \left[ \matrix{ \overrightarrow{\mbox{normal}} \\ -\mbox{distance} } \right] & \mbox{Line} & = \left\{ \matrix{ \overrightarrow{\mbox{direction}} \\ \overrightarrow{\mbox{position}} \times \overrightarrow{\mbox{direction}} } \right\} \end{aligned} $$

The operations between these constructs are very well explained in Foundations of Game Engine Development, Volume 1: Mathematics, page 129, in the section named "Plucker Coordinates".

Related Question