Giao điểm của lưới có bề mặt tham số

Question

Tôi tự hỏi làm thế nào để có thể viết một thuật toán chính xác để tính toán biên giới của bề mặt giao nhau giữa một bề mặt tham số f : R^2 --> R^3 và lưới tam giác.

Tôi đã nghĩ đến một cách tiếp cận thứ nhất:

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 

thuật toán này, rất đơn giản nhưng chậm (n^3) và không giữ trong tài khoản đó địa hình của lưới được dựa trên hình tam giác để các điểm đầu ra là các điểm của lưới và không phải là điểm tính toán khai thác giao điểm của bề mặt với các hình tam giác và phụ thuộc nhiều vào sự khoan dung mà ta phải đặt ra.

Có ai đó có ý tưởng hay hơn hoặc có thể đưa tôi đến một thư viện phù hợp cho mục đích này không?

Answer 1

Tôi sẽ lặp qua từng hình tam giác và tính toán giao điểm của hình tam giác với bề mặt. Tôi sẽ sử dụng một shader hình học mà có hình tam giác như đầu vào, và đầu ra dải dòng. Đối với mỗi đỉnh trong tam giác, tính toán khoảng cách đã ký với bề mặt. Sau đó lặp lại qua các cạnh: Nếu có hai đỉnh nơi h có các dấu hiệu khác nhau, cạnh giữa các đỉnh này giao nhau với bề mặt. Trong khi tôi chắc chắn ngã tư chính xác có thể được tính toán, giải pháp đơn giản nhất sẽ được nội suy tuyến tính, ví dụ:

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

Sau đó, sản lượng mỗi ngã tư như một đỉnh của đoạn thẳng của bạn.

Mã tôi đã đăng here có thể giúp bạn bắt đầu. Nếu bạn muốn vẽ kết quả, có thể bạn sẽ gặp phải vấn đề tương tự mà tôi đã mô tả trong câu hỏi đó. Nếu bạn cần các đỉnh trên máy khách, bạn có thể sử dụng transform feedback.

Chỉnh sửa: Tôi vừa làm một bài kiểm tra nhỏ. Như chức năng khoảng cách tôi đã sử dụng

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; 
} 

Vì không có bên trong/bên ngoài, và chức năng khoảng cách này đi từ -90 ° đến 90 °, bạn chỉ có thể phát ra các đỉnh nếu dấu hiệu đi từ nhỏ đến tiêu cực nhỏ tích cực hay ngược lại, không phải khi nó lật từ 90 ° đến -90 °. Ở đây tôi chỉ đơn giản là lọc ra khoảng cách nơi abs (quận)> 45 °:

Cách sạch sẽ là để xác định các chỉ số của các cuộc cách mạng gần nhất. Ví dụ. [-pi, pi] sẽ là cuộc cách mạng 0, [pi, 3pi] = cuộc cách mạng 1, v.v. Sau đó, bạn sẽ chỉ phát ra nếu hai khoảng cách tham chiếu đến cùng một cuộc cách mạng.

Answer 2

Nếu bề mặt của bạn luôn luôn là helicoid, bạn có thể thử để chiếu tất cả mọi thứ trên một xi lanh quanh trục Y.

Bề mặt của helicoid gồm đường vuông góc với bề mặt của hình trụ đó và sau khi chiếu bạn sẽ nhận được một xoắn ốc . Sau khi chiếu lưới tam giác 3D vào hình trụ đó, bạn sẽ nhận được lưới tam giác 2D (lưu ý rằng một số khu vực có thể được phủ một vài lớp hình tam giác).

Vì vậy, nhiệm vụ trở nên tìm hình tam giác trong lưới tam giác 2D giao nhau với hình xoắn ốc đơn giản hơn. Nếu bạn đồng ý với xấp xỉ, bạn có thể phân đoạn xoắn ốc đó và sử dụng một số loại cây để tìm hình tam giác giao nhau với hình xoắn ốc.

Khi bạn có một hình tam giác giao cắt một phần của hình xoắn ốc, giao lộ của nó sẽ là một đoạn, bạn có thể tính toán lại tọa độ 3D của phân đoạn và tập hợp các phân đoạn này là đường giao nhau của bạn.