Gouraud 음영을위한 삼각형 집합에서 정점 법선을 계산하는 가장 효율적인 알고리즘

Question

우리는 삼각형 집합을받습니다. 각 삼각형은 삼중 항입니다. 각 점은 실수의 삼중 항입니다. 각 삼각형의 표면 법선을 계산할 수 있습니다. 그러나 Gouraud 음영의 경우 꼭지점 법선이 필요합니다. 그러므로 우리는 각 꼭지점을 방문하여 그 꼭지점을 공유하고 그 표면 법선을 평균화하는 삼각형을보고 꼭지점 법선을 얻어야합니다.

이것을 달성하기위한 가장 효율적인 알고리즘과 데이터 구조는 무엇입니까? 보다 효율적인 방법은

MAP = dict() 
for T in triangles: 
    for V in T.vertices: 
    key = hash(V) 
    if MAP.has(key): 
     MAP[key].append(T) 
    else: 
     MAP[key] = [] 
     MAP[key].append(T) 

VNORMALS = dict() 
for key in MAP.keys(): 
    VNORMALS[key] = avg([T.surface_normal for T in MAP[key]]) 

있습니까 :

본래의 접근법은이 (의사 파이썬 코드)인가?

Answer 1

각 삼각형을 방문하여 각 삼각형의 법선을 계산하고 각 삼각형의 꼭지점 법선에 추가합니다.
그런 다음 끝에 각 정점의 법선을 정규화합니다.

적어도 삼각형을 한 번만 트래버스하면 일반/정점 하나만 저장됩니다.

Answer 2

각 정점은 하나 이상의 얼굴 (일반적으로 삼각형, 때로는 쿼드 -이 답변에서는 삼각형을 사용합니다)에 속합니다.

다른 삼각형에 연결되지 않은 삼각형은 '부드럽게'할 수 없습니다. 평평하다. 얼굴에 이웃이있는 경우에만 함께 부드럽게하는 것이 좋습니다.

여러면이 만나는 정점의 경우 각면의 법선을 계산하십시오. 두 벡터의 교차 곱은 우리가 원하는 직각 벡터를 반환합니다.

A --- B 
    \/
    C 

v1 = B - A 
v2 = C - A 
normal = v1 cross v2 

이러한 벡터를 모든면에서 일관되게 계산해야합니다. 그렇지 않으면 법선이 원하는 방향으로 음수가 될 수 있습니다.

그래서 여러면이 만나는 정점에서면의 법선을 합계하고 결과 벡터를 정규화 한 다음 정점에 적용합니다.

때로는 그 일부가 매끄럽게되고 다른 일부는 매끄럽지 않은 메시가 있습니다. 그림을 그리기 쉽도록 삼각형으로 만든 실린더가 있습니다. 원통의 둥근면은 잘 매끄 럽지 만 날카로운 산등성이의 꼭지점에서 평평한 끝에서 삼각형을 보면 이상하게 보입니다. 이를 방지하기 위해 계산중인 얼굴의 법선에서 너무 벗어나는 법선을 무시하는 규칙을 도입 할 수 있습니다.

EDIT 실제로는 video showing technique for calculating Gourad shading이지만 실제로 알고리즘은 설명하지 않습니다.

Three.js의 소스를보고 싶을 수도 있습니다. 특히 computeVertexNormals 함수입니다. 날카로운 모서리 유지를 지원하지 않습니다. 알고리즘의 효율성은 프리미티브를 모델링하는 방식에 크게 좌우됩니다.