베 지어 삼각형을 어떻게 테셀 레이트하는가?

Question

내 관심사는 렌더링을 위해 모방하려고하는 2 차 베 지어 트라이앵글입니다.

필자는 위키피디아 페이지에서 설명한 것처럼 삼각형을 재귀 적으로 세분화하여 구현할 수있었습니다. 세분화에 더 많은 정교함을 얻고 싶습니다. 문제는 알고리즘을 반복 할 때마다 표면의 양이 두 배가되기 때문에 너무 적은 수의 하위 분할 또는 너무 많은 분할을 얻게된다는 것입니다.

특히 가장자리에서 세그먼트의 양을 정의 할 수있는 적응 형 테셀레이션 알고리즘이 필요합니다. 나는 내가 그것을 얻을 수 있는지 확신 할 수 없기 때문에 나는 또한 uniform tesselation technique에 대해 듣고 싶다.

가장 어려운 문제 베 지어 표면의 점에 대한 법선을 계산하는 데 어려움이 있습니다. 필요한지 여부는 확실하지 않지만 해결하려고합니다.

Answer 1

적응 형 테셀레이션. 이 알고리즘에는 많은 알고리즘이 있습니다. 그러나 여기에 하나가 있습니다 :

def line_angle((x0,y0),(x1,y1)): 
    return atan2(y1-y0,x1-x0) 

def adaptive_bezier(p0,p1,p2,lev=32): 
    p01 = midpoint(p0,p1) 
    p12 = midpoint(p1,p2) 
    m = midpoint(p01, p12) 
    da = abs(line_angle(p0,p1) - line_angle(p1,p2)) 
    if da <= max_tolerance or lev <= 0: 
     yield m 
    else: 
     for p in adaptive_bezier(p0,p01,m,lev-1): yield p 
     for p in adaptive_bezier(m,p12,p2,lev-1): yield p 

이런 식으로 삼각 분할을 할 경우 문제가 복잡합니다. 가장자리 베 지어 각도에 따라 적응 형 테셀레이터 알고리즘을 구동해야합니다. 3 가지 방법으로 테셀레이션 할 때 삼각형을 분할 할 수 있습니다.

2 edges  one edge  3 edges  
--------  --------- -------- 
\ ...//  \ | / \/\/
\/___/  \ |/ \____/ 
    \/  \ |/  \/
    \/   \|/   \/ 

이러한 패턴에 대한 테셀레이션 결과를 정의하면 잘 처리됩니다. 위키 피 디아 (Wikipedia) 기사에서는 한 모서리 만의 테셀레이션 만 설명합니다.

두 개의 다른 테셀레이션 결과는 하나의 에지 분할의 경우를 연구하여 얻을 수 있습니다.

"2 에지"는 첫 번째 에지를 분할 한 다음 다른 에지를 분할하여 곧바로 얻을 수 있습니다.

"3 가장자리"는 알아 내야 할 일입니다. 그러나 당신은 "2 개의 가장자리"를 볼 수 있습니다. 2 차 베 지어 삼각형의 경우 그곳에 나타나는 다이아몬드의 평균 합계입니다.

--------  /\ 
\ / /\ 
\____/  -____- 
    \/  \/
    \/   \/