Przecięcie siatki z parametryczną powierzchnią

Question

Zastanawiam się, jak można zapisać dokładny algorytm obliczania granicy powierzchni przecięcia między parametryczną powierzchnią f : R^2 --> R^3 a siatką trójkątów.

myślałem pierwszego podejścia:

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 

Algorytm ten jest bardzo prosty, ale powolny (n^3) i nie zachowuje się uwagę, że topografia siatki trójkątów jest oparty na tak punkty wyjściowe są punktami siatki, a nie punktami obliczonymi z wykorzystaniem przecięcia powierzchni z trójkątami i są silnie zależne od tolerancji, którą należy ustawić.

Czy ktoś ma lepszy pomysł, czy może mnie do tego celu doprowadzić do odpowiedniej biblioteki?

Answer 1

Chciałbym powtórzyć nad każdym trójkątem i obliczyć punkt przecięcia trójkąta z powierzchnią. Chciałbym użyć modułu cieniującego geometrii, który przyjmuje trójkąty jako dane wejściowe i wyprowadza paski linii. Dla każdego wierzchołka w trójkącie oblicz odległość podpisaną na powierzchni. Następnie wykonaj iterację po krawędziach: jeśli istnieją dwa wierzchołki, w których h ma różne znaki, krawędź między tymi wierzchołkami przecina się z powierzchnią. Choć jestem pewien, że dokładny punkt przecięcia można obliczyć, najprostszym rozwiązaniem byłoby interpolować liniowo, tzn

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

Następnie wyjście każdym skrzyżowaniu jako wierzchołek swojego odcinka linii.

Kod, który wysłałem pod numer here może Ci pomóc. Jeśli chcesz tylko narysować wynik, prawdopodobnie napotkasz ten sam problem, który opisałem w tym pytaniu. Jeśli potrzebujesz wierzchołków na kliencie, możesz użyć transform feedback.

Edytuj: Właśnie zrobiłem mały test. Jako funkcji odległości użyłem

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

Ponieważ nie ma wewnątrz/na zewnątrz, a funkcja ta odległość idzie od -90 ° do 90 °, można emitować tylko wierzchołki jeśli znak idzie z minusem na niewielki dodatni lub vice versa, a nie kiedy zmienia się z 90 ° na -90 °. Tu po prostu odsączony odległości gdzie ABS (dist)> 45 °:

Czyste rozwiązaniem byłoby, aby określić wskaźnik najbliższego obrotu. Na przykład. [-pi, pi] będzie rewolucją 0, [pi, 3pi] = obrót 1, itd. Będziesz wtedy emitował tylko wtedy, gdy dwie odległości odnoszą się do tego samego obrotu.

Answer 2

Jeśli powierzchnia jest zawsze helicoid, można spróbować wystawać wszystko na cylindrze wokół osi Y.

Powierzchnia helicoid składa się z linii prostopadłych do powierzchni tego cylindra i po projekcji dostaniesz spiralę . Po rzucie siatki trójkąta 3D na ten cylinder otrzymasz siatkę trójkątów 2D (zwróć uwagę, że niektóre obszary mogą być pokryte kilkoma warstwami trójkątów).

Tak więc zadaniem staje się znalezienie trójkątów w siatce trójkąta 2D, która przecina spiralę, co jest prostsze. Jeśli jesteś w porządku z przybliżeniami, możesz posegmentować tę spiralę i użyć jakiegoś drzewa, aby znaleźć trójkąty przecinające spiralę.

Gdy trójkąt przecina się z częścią spiralną, jego przecięcie będzie segmentem, można po prostu przeliczyć współrzędne 3D segmentu, a zestaw tych segmentów to linia przecięcia.