Intersection of a grid with a parametric surface

Question

I am wondering how one can write down an exact algorithm to calculate the boundary of the intersection surface between a parametric surface f : R^2 --> R^3 and a triangulated mesh.

I thought of the first approach:

 nStepsU = 100 nStepsV = 100 tolerance=0.01 // pick some sensical value intersectionVertices={} for u from minU to maxU in nStepsU: for v from minV to maxV in nStepsV: for v in verticesInMesh: if euclidean distance( f(u,v), v ) < tolerance: add vertex v in a set connect the vertices in intersectionVertices with a line strip draw the vertices in intersectionVertices 

This algorithm is very simple, but slow (n ^ 3) and does not take into account that the grid topography is based on triangles, therefore, the output points are grid points, not points calculated using the intersection of the surface with triangles and are highly dependent on the tolerances that are necessary install.

Does anyone have any better idea or is it possible to take me to a suitable library for this purpose?

Answer 1

I would iterate over each triangle and calculate the intersection of the triangle with the surface. I would use a geometric shader that takes triangles as input and draws linear stripes. For each vertex in the triangle, calculate the sign distance to the surface. Then iterate over the edges: if there are two vertices where h has different signs, the edge between these vertices intersects with the surface. Although I am sure that the exact intersection can be calculated, the simplest solution would be to interpolate linearly, i.e.

 vec3 intersection = (h0 * v1 + h1 * v0) / (h0 + h1); 

Then print each intersection as the top of your line segment.

The code I posted here may help you. If you just want to draw the result, you are likely to run into the same problem that I described in this question. If you need vertices on the client, you can use convert feedback .

Edit: I just checked a little. As a function of distance, I used

 float distToHelicoid(in vec3 p) { float theta = py / 5 + offset.x / 50; float a = mod(theta - atan(pz, px), 2*PI) - PI; // [-PI, PI[ if (abs(a) > PI/2) a = mod(theta - atan(-pz, -px), 2*PI) - PI; return a; } 

Since there is no inside / outside, and this distance function goes from -90 ° to 90 °, you can only emit vertices if the sign goes from small negative to small positive or vice versa, and not when it flips from 90 ° to -90 ° . Here I just filtered out the distances where abs (dist)> 45 °:

A clean way would be to determine the index of the nearest rotation. For instance. [-pi, pi] is revolution 0, [pi, 3pi] = revolution 1, etc. You would then give up only if two distances belong to the same revolution.

Answer 2

If your surface is always helicoid, you can try to project everything onto a cylinder around the Y axis.

The surface of the helicoid consists of lines orthogonal to the surface of this cylinder, and after projecting you get a spiral. After projecting a three-dimensional triangular grid onto this cylinder, you get a two-dimensional triangular grid (note that some areas may be covered by several layers of triangles).

Thus, the task becomes finding the triangles in a 2D triangular grid intersecting the spiral, which is simpler. If you're okay with the approximations, you can segment this spiral and use some kind of tree to find the triangles crossing the spiral.

When you have a triangle crossing a part of the spiral, its intersection will be a segment, you can simply recalculate the 3D coordinates of the segment, and the set of these segments is your intersection line.