[go: up one dir, main page]

KR101265810B1 - 프로시저 기하 개체의 삼각화 - Google Patents

프로시저 기하 개체의 삼각화 Download PDF

Info

Publication number
KR101265810B1
KR101265810B1 KR1020077029774A KR20077029774A KR101265810B1 KR 101265810 B1 KR101265810 B1 KR 101265810B1 KR 1020077029774 A KR1020077029774 A KR 1020077029774A KR 20077029774 A KR20077029774 A KR 20077029774A KR 101265810 B1 KR101265810 B1 KR 101265810B1
Authority
KR
South Korea
Prior art keywords
triangles
meshes
sampling
mesh
triangulation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR1020077029774A
Other languages
English (en)
Other versions
KR20080022551A (ko
Inventor
브라이언 케이. 귄터
마르셀 가브릴리우
Original Assignee
마이크로소프트 코포레이션
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 마이크로소프트 코포레이션 filed Critical 마이크로소프트 코포레이션
Publication of KR20080022551A publication Critical patent/KR20080022551A/ko
Application granted granted Critical
Publication of KR101265810B1 publication Critical patent/KR101265810B1/ko
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G06T17/10—Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T15/00—3D [Three Dimensional] image rendering
    • G06T15/10—Geometric effects

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Geometry (AREA)
  • Computer Graphics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Image Generation (AREA)

Abstract

복합 프로시저 표면이 프리미티브 프로시저 표면들 상에 수행되는 소정의 CSG 연산에 기초하여 표현될 수 있다. 복합 프로시저 표면의 변역 기반 표현은 음함수 교집합 곡선들을 포함한다. 사전 처리 동안, 삼각화될 변역 기반 표현의 부분들은 먼저 음함수 곡선 및 곡선 가시성 삼각형들의 파라미터화된 영역들과 관련된 에지에 의해 어떠한 변에서도 한정되지 않는 단순 삼각형들로 세분된다. 거친 사전 처리된 삼각화 메쉬는 나중에 거친 메쉬를 더 세분하여 곡선 기반 에지들 및 비곡선 기반 에지들을 갖는 삼각형들을 추가함으로써 실행 시간 동안 정교화되어, 샘플링 삼각형들의 메쉬를 생성하게 된다. 보다 정교화된 샘플링 삼각형 메쉬는 기하학 인스턴싱을 적용하여 적절한 인스턴스 메쉬들을 적절한 샘플링 삼각형들로 맵핑함으로써 더 정교화되어, 렌더링을 위해 실행 시간에 훨씬 더 정교화된 삼각화 메쉬를 생성하게 된다.
컴퓨터 그래픽, 렌더링, 프로시저 기하 개체, 삼각화, 메쉬

Description

프로시저 기하 개체의 삼각화{TRIANGULATING PROCEDURAL GEOMETRIC OBJECTS}
본 발명은 컴퓨터 그래픽에 관한 것이다. 구체적으로, 본 발명은 컴퓨터 표시 장치 상에서의 컴퓨터 생성 이미지의 렌더링에 관한 것이다.
CSG(Constructive Solid Geometry)는 그래픽 표면들을 모델링함으로써 보다 복잡한 표면들을 보다 간단한 표면들의 조합으로서 모델링하는 방법이다. 예를 들어, 컴퓨터 그래픽에서, CSG는 단순한 원통 및 단순한 구와 같은 보다 낮은 지너스(genus)의 표면들로부터 보다 높은 지너스의 표면들(예를 들어, 구멍을 구비한 구)을 정의하기 위한 강력한 방법을 제공한다. 원통 및 구와 같은 프리미티브를 포함하는 CSG 컴포넌트들은 소정 수의 파라미터를 수용하는 프로시저 또는 함수의 형태로 기술될 수 있다. 예를 들어, 3차원(3D) 구면은 그의 중심의 좌표 및 그의 반경의 값에 의해 프로시저 방식으로 정의될 수 있다. 이어서, 이러한 프로시저 개체들을 이용하여 수행되는 CSG 연산을 통해 보다 복잡한 개체들이 모델링될 수 있다.
3D 표면의 프로시저 모델들은 많은 바람직한 특성을 갖는다. 예를 들어, 이들은 다각형 메쉬 또는 다항식 표면 패치(예를 들어, 스플라인(spline))보다 간결하고, 레졸루션-독립적(resolution independent)이며, 적은 수의 파라미터를 변경 함으로써 실행 시간에 수정될 수 있다. 간결성(compactness)은 많은 이유에서 중요하다. 예를 들어, 간결한 표현의 저장은 메모리와 관련하여 적은 비용이 든다. 또한, 실행 시간에 간결한 표현을 처리하기 위해 훨씬 더 많은 계산이 요구되는 경우에도, 간결한 표현은 복잡한 표현보다 훨씬 빠르게 렌더링될 수 있다.
표시를 위해 이러한 프로시저 표면들을 렌더링하는 한 가지 방법에 있어서, 프로시저 표면 표현은 상호 연결된 삼각형들의 메쉬로 변환된다. 이러한 컴퓨터 그래픽 처리 단계는 일반적으로 예를 들어 삼각화 또는 삼각 분할로 지칭된다. 삼각형들은 이들의 매우 간단한 표현 및 이들의 렌더링 적합성으로 인해 선호된다. 그러나 프로시저 표면들의 삼각화 및 삼각화된 표면 모델을 기술하는 데이터 구조의 저장 또한 메모리를 소비하며, 이 때문에 비용을 증가시킬 수 있다. 결과적으로, 표시 장치로의 렌더링 바로 전에 실행 시간에 삼각화와 관련된 보다 많은 태스크를 수행하여, 프로시저 표면들의 삼각화된 표현과 관련된 데이터의 저장 및 검색과 연관된 비용을 회피하는 것이 바람직하다.
<발명의 요약>
프리미티브 프로시저 표면들을 표현하는 데이터를 이용하여 CSG 연산을 수행함으로써 적어도 부분적으로 형성된 복합 프로시저 표면들을 렌더링하기 위한 방법 및 시스템이 본 명세서에서 설명된다. CSG 연산은 음함수들에 의해 정의되는 음함수 교집합 곡선들을 생성한다. 음함수들은 복수의 변역 변수를 포함하며, 음함수 교집합 곡선들은 복수의 파라미터화 영역으로 분할된다. 다른 양태에서, 복합 프로시저 표면의 변역 기반 표현은 변역 내에 거친(coarse) 삼각화 메쉬를 생성하도록 정적으로 사전 처리된다. 거친 삼각화 메쉬는 메모리에 저장되고, 실행 시간에 추가적인 세분에 의해, 그리고 기하학 인스턴싱을 적용함으로써 더 정교해진다.
또 다른 양태에서, 거친 삼각화 메쉬는 CSG 연산에 의해 생성되는 음함수 교집합 곡선들의 파라미터화 영역들의 소정의 중간 포인트들은 물론 엔드 포인트들을 연결하는 제한 에지들을 추가함으로써 적어도 부분적으로 생성된다. 또 다른 양태에서, 변역의 거친 삼각화 메쉬 내의 얇은 조각 삼각형들의 발생을 최소화하기 위해 델라우나이 삼각화 방법이 이용된다. 델라우나이 삼각화 방법에 의해 삼각화 메쉬는 곡선 가시성 삼각형들을 생성함으로써 더욱 개선된다.
일 양태에서, 곡선 가시성 삼각형은 정점을 포함하는데, 이 정점에서 대응 제한 에지들로 그려진 선분들은 한 곳에서만 대응 음함수 교집합 곡선과 교차한다. 하나의 다른 양태에서, 정적으로 생성된 거친 삼각화 메쉬는 범용 컴퓨터 시스템의 중앙 처리 장치(CPU)에 의해 생성되어 후속 이용을 위해 저장된다.
또 다른 양태에서, 정적으로 생성된 거친 삼각화 메쉬는, 적어도 파라미터화 영역들의 엔드 포인트들에 중간인 곡선 포인트들에 관련된 에지들을 추가하고 사용자 정의 파라미터 길이 제한에 매칭되도록 거친 메쉬의 비 곡선 기반 단순 삼각형들을 세분함으로써 보다 정교한 샘플링 삼각형 메쉬를 생성하기 위해 실행 시간에 더 세분된다.
하나의 다른 양태에서, 샘플링 삼각형 메쉬는 기하학 인스턴싱을 적용함으로써 더 정교화된다. 기하학 인스턴싱을 적용하는 한 가지 방법은 샘플링 삼각형 유형의 분류에 적어도 부분적으로 기초하여 적절한 인스턴스 메쉬를 선택하는 단계 및 샘플링 삼각형 내에서 인스턴스 메쉬를 맵핑하는 단계를 포함한다. 하나의 또 다른 양태에서, 기하학 인스턴싱의 적용은 실행 시간에 그래픽 처리 장치(GPU) 상에서 구현된다. 또 다른 양태에서, 샘플링 삼각형 메쉬의 삼각형들의 정점 데이터가 샘플링 삼각형들을 다양한 유형으로 분류하는 데이터와 함께 GPU에 의해 수신된다. 샘플링 삼각형들의 분류 데이터에 적어도 부분적으로 기초하여, 적절한 인스턴스 메쉬가 샘플링 삼각형들 내에 맵핑되도록 선택된다. 한 가지 맵핑 방법에 있어서, 메쉬로부터 동일하게 분류된 샘플링 삼각형들은 적절한 인스턴스 메쉬를 이용하여 함께 그룹화되고 맵핑된다. 일 양태에서, 맵핑은 샘플링 삼각형 메쉬의 삼각형들의 정점 데이터에 관한 인스턴스 메쉬의 중심 좌표를 이용하여 달성된다.
적어도 일부 실시예들의 적어도 일부 특징들이 위에 열거되어 있다. 추가적인 특징들 및 이점들은 첨부 도면들을 참조하여 진행하는 아래의 실시예들에 대한 상세한 설명으로부터 명확해질 것이다.
도 1A는 2개의 예시적인 프로시저 표면 프리미티브를 나타내는 블록도이다.
도 1B는 도 1A에 도시된 프리미티브 표면들 상에 예시적인 CSG 연산을 수행함으로써 생성되는 예시적인 복합 프로시저 표면을 나타내는 블록도이다.
도 2는 삼각화를 통해 복합 프로시저 표면들을 렌더링하기 위한 전반적인 방법을 설명하는 흐름도이다.
도 3은 프로시저 표면들을 나타내기 위한 삼각화 메쉬를 생성하기 위한 전반적인 방법의 흐름도이다.
도 4는 렌더링할 표면들을 나타내는 삼각화 메쉬에 기초하여 프로시저 표면들을 포함하는 그래픽 개체들을 렌더링하기 위한 예시적인 그래픽 처리 시스템의 적어도 일부 컴포넌트를 나타내는 블록도이다.
도 5는 복수의 표면이 서로 교차하는 음함수 교집합 곡선들을 포함하는 예시적인 표면들의 예시적인 변역 기반 표현을 나타내는 블록도이다.
도 6은 음함수 교집합 곡선들을 가진 프로시저 표면들의 변역 기반 표현들을 나타내는 거친 삼각화 메쉬를 정적으로 생성하기 위한 예시적인 전반적인 방법을 나타내는 흐름도이다.
도 7A는 프로시저 표면의 변역 기반 표현에서 음함수 교집합 곡선들에 대한 예시적인 제한을 나타내는 블록도이다.
도 7B는 파라미터화된 교집합 곡선들이 제한 에지들을 가진 적어도 일부 삼각형들로 제한되고 삼각화되는 예시적인 변역을 나타내는 블록도이다.
도 8A는 제한 에지들의 적어도 일부가 서로 충돌하는 하나의 예시적인 제한 에지들의 세트를 가진 음함수 교집합 곡선들을 나타내는 블록도이다.
도 8B는 곡선의 파라미터화 영역들의 적어도 일부가 각각의 제한 에지들 간의 충돌을 피하도록 더 세분되는 다른 하나의 예시적인 제한 에지들의 세트를 가진 음함수 교집합 곡선들을 나타내는 블록도이다.
도 9는 상이한 삼각화 메쉬들의 예시적인 가장 얇은 조각 삼각형들을 나타내는 블록도로서, 델라우나이 삼각화에 따라 가장 덜 얇은 조각 삼각형을 가진 메쉬가 선택됨을 나타내는 도면이다.
도 10은 적어도 하나의 곡선 가시성 삼각형을 포함하는 예시적인 삼각화된 변역을 나타내는 블록도이다.
도 11은 음함수 미분에 의해 예시적인 음함수 교집합 곡선에 대한 접선들을 계산하는 방법을 나타내기 위한 블록도이다.
도 12는 예시적인 CSG 음함수 교집합 곡선 선분에 대응하는 변역 내의 예시적인 곡선 가시성 영역들을 나타내는 블록도이다.
도 13A는 예시적인 곡선 가시성 삼각형을 나타내는 블록도로서, 제1 음함수 곡선과 연관된 곡선 가시성 삼각형이 제2 곡선과 충돌함을 나타내는 도면이다.
도 13B는 곡선 가시성 삼각형들을 나타내는 블록도로서, 상이한 음함수 곡선들의 곡선 가시성 삼각형들이 서로 충돌하지 않음을 나타내는 도면이다.
도 14는 단순 변역 삼각형들 및 곡선 가시성 삼각형들의 소정 조합을 생성하도록 사전 처리 동안 정적으로 삼각화된 변역의 적어도 일부를 나타내는 블록도이다.
도 15는 정적으로 생성된 거친 삼각화 메쉬를 정교화함으로써 변역을 실행 시간 삼각화하기 위한 예시적인 전반적인 방법을 나타내는 흐름도이다.
도 16은 실행 시간에 정적으로 생성된 거친 삼각화 메쉬를 정교화하여 보다 정교화된 샘플링 삼각형들의 메쉬를 생성하기 위한 예시적인 방법을 나타내는 흐름도이다.
도 17A는 음함수 교집합 곡선을 따라 추가된 추가 에지들에 대응하도록 곡선 가시성 삼각형들을 추가함으로써 더 세분된 정적으로 삼각화된 거친 메쉬의 적어도 일부를 나타내는 블록도이다.
도 17B는 곡선 기반 에지들에 의해 한정되지 않은 단순 샘플링 삼각형들 내에 에지들을 추가함으로써 더 세분된 정적으로 삼각화된 거친 메쉬의 적어도 일부를 나타내는 블록도이다.
도 17C는 샘플링 삼각형들의 보다 정교한 메쉬를 생성하기 위해 실행 시간 생성 곡선 가시성 삼각형들 내에 에지들을 추가함으로써 더 세분된 정적으로 삼각화된 거친 메쉬의 적어도 일부를 나타내는 블록도이다.
도 18은 실행 시간 생성 샘플링 삼각형 메쉬를 더 정교화하기 위해 기하학 인스턴싱을 적용하는 예시적인 방법을 나타내는 흐름도이다.
도 19는 샘플링 삼각형 메쉬의 적절한 삼각형들에 대한 다양한 유형의 기하학 인스턴스 메쉬들의 예시적인 맵핑을 나타내는 블록도이다.
도 20은 대응하는 중심 좌표들을 포함하는 상이한 유형의 기하학 인스턴스 메쉬들의 예시적인 세트를 나타내는 블록도이다.
도 21은 적절한 샘플링 삼각형 유형 내에서 적절히 선택된 기하학 인스턴스 메쉬들을 맵핑하기 위한 예시적인 방법을 나타내는 리스트이다.
도 22는 프로시저 기하 개체들을 삼각화하는 방법들을 구현하기 위한 예시적인 컴퓨팅 환경을 나타내는 블록도이다.
예시적인 CSG 연산
도 1A는 예를 들어 2차원 변역 평면에서 소정의 함수들 f1(u1, v1) 및 f2(u2, v2) 각각의 프로시저의 형태로 기술될 수 있는 양 원통 표면들인 예시적인 프로시저 표면들 S1(110) 및 S2(120)를 나타낸다. 도 1B는 표면들 S1(110) 및 S2(120)를 수반하는 CSG 연산의 결과를 나타낸다. 구체적으로, 도 1B는 보다 큰 표면 S1(110)으로부터 보다 작은 표면 S2(120)를 감산함으로써 얻어지는 부울 차의 결과를 나타낸다. 도시된 연산 및 표면들은 예시적이다. 구, 회전면 또는 다항식 패치와 같은 다양한 표면의 교집합 및 합집합과 같은 다른 연산들도 가능하다.
f1(u1, v1) 및 f2(u2, v2)로서 기술되는 3D 표면들 S1(110) 및 S2(120)는 다음과 같이 정의될 수 있다.
Figure 112007091563140-pct00001
또한, 표면들 S1(110) 및 S2(120)의 교집합 곡선들(예를 들어, 도 1B의 130 및 135에서)은 소정의 함수 F=f1(u1, v1) - f2(u2, v2)=[0x,0y,0z]로서 묵시적으로 정의된다. 프리미티브들 S1(110) 및 S2(120)는 변역 변수들 (u1, v1) 및 (u2, v2)의 함수에 의해 프로시저 방식으로 정의되므로, 음함수 교집합 곡선들을 기술하는 함수 F는 4개의 변역 변수의 함수 F(u1, v1, u2, v2)이다.
예시적인 프로시저 표면의 렌더링
CSG 연산을 수행함으로써 생성되는 복합 프로시저 표면들이 스크린 상에 표시되도록 선택될 수 있다. 이러한 복합 프로시저 표면들의 표현들에 삼각화를 적용하는 것은 스크린 또는 표시 장치 상에 표면들을 렌더링하는 한 가지 방법이다. 도 2는 임의의 음함수 교집합 곡선들을 포함하는, 도 1B의 150과 같은 복합 프로시저 표면들을 렌더링하기 위한 전반적인 방법(200)을 제공한다. 먼저, 단계(210)에서, 컴퓨터 그래픽 처리 시스템(예를 들어, 도 4의 400)이 프리미티브들(예를 들어, 도 1A의 110 및 120)의 모델들을 수신하며, 단계(220)에서 CSG 연산(예를 들어, 도 1B에 도시됨)을 수행하여 도 1B의 150과 같은 복합 프로시저 표면을 생성한다. 이어서, 단계(230)에서, 수행된 CSG 연산을 암시적으로 설명하는 CSG 프로시저 표면들의 2D 변역 기반 표현들(예를 들어, 도 5의 500 및 550)이 선택된 삼각화 프로세스를 통해 삼각형들의 메쉬로 분해된다.
2D 메쉬들은 표면들의 변역들 내에 있다. 복합 CSG 프로시저 표면에 기여하는 표면마다 2D 메쉬가 존재한다. 2개의 프로시저 표면 사이에 하나의 CSG 연산이 존재하는 경우, 분해될 2개의 메쉬가 존재할 것이다. 3개의 메쉬 사이에 2개의 CSG 연산이 존재하는 경우, 분해될 3개의 메쉬가 존재하는 등등일 것이다.
단계(240)에서, 2D 평면에서 3D 평면으로의 맵핑에 의해 프리미티브 프로시저 표면들의 변역 기반 2D 메쉬들(예를 들어, 500 및 550)의 컴포넌트들로부터 최종 복합 프로시저 표면의 3D 메쉬가 생성된다. 맵핑은 예를 들어 적절한 표면에 대한 표현식 또는 프로시저를 이용하는 정점 쉐이더 프로그램에 의해 GPU(예를 들어, 도 4의 430) 상에서 행해진다. 단계(250)에서, 이 3D 메쉬는 표시 장치 상에 이미지를 생성하도록 렌더링된다.
도 3은 CSG 프로시저 표면들과 관련된 변역 기반 표현들에 삼각화를 적용하기 위한 예시적인 방법(230)을 나타낸다. 단계(310)에서, CSG 프로시저 표면들과 관련된 변역 기반 표현들은 사전 처리 동안 거친 삼각형들의 메쉬로 정적으로 분해된다. 이어서, 단계(320)에서, 정적 삼각화 데이터가 메모리에 저장된다. 단계(330)에서, 정적 삼각화는 표면의 복잡성을 더 상세히 표현하기 위해 보다 미세한 삼각화 메쉬를 생성하도록 실행 시간에 더 정교화된다. 렌더링 전에 최종 삼각화를 달성하기 위한 실행 시간의 추가 처리는 표시될 CSG 프로시저 표면들의 복합 삼각 메쉬들과 관련된 데이터 구조를 저장하고 검색하는 데 필요한 자원들의 비용을 줄이는 이점을 갖는다. 이것은 또한 예를 들어 CSG 연산 후에 표시될 CSG 프로시저 표면들의 일부들만을 삼각화하는 것과 같은 추가적인 유연성을 제공한다.
프로시저 표면의 렌더링을 위한 예시적인 그래픽 처리 시스템
도 4는 사용자에게 그래픽을 표시하기에 적절한 방식으로 컴퓨터 생성 그래픽과 관련된 데이터를 처리하기 위한 컴포넌트를 포함하는 예시적인 그래픽 처리 시스템(400)을 나타낸다. 시스템은 프로그램가능한 범용 중앙 처리 장치(CPU)(410)를 포함한다. 메모리(420)는 CPU(410) 및 그래픽 처리 장치(GPU)(430)에 의해 액세스될 수 있다. 일 실시예에서, 거친 삼각화에 의해 CSG 프로시저 표면들의 변역들을 정적으로 분해하는 단계(310)는 바람직하게도 사전 처리 동안 CPU(410)에서 이루어지고, 메모리(420)에 정적 삼각화 데이터(425)로서 저장된다. GPU(430)는 표시 장치(470) 상에 CSG 프로시저 표면들을 렌더링하기 전에 추가 처리를 위해 정적 삼각화 데이터(425)를 수신할 수 있다.
예시적인 GPU(430)는 정적 삼각화 데이터(425)로부터 도출되는 삼각화 메쉬의 정점 데이터를 처리하기 위한 정점 처리 유닛(435)(VPU)을 포함한다. 처리는 CSG 프로시저 표면들의 추가 변환을 포함할 수 있다. 예를 들어, VPU(435)는 통상적으로 정점 쉐이더 프로그램을 이용하여, 거친 변역 삼각화는 물론, 통상의 3D 변환으로부터 CSG 표면들의 3D 메쉬들을 동적으로 생성한다. 래스터화기(440)는 일련의 벡터 형태의 정점 데이터를 수신하고, 이들을 표시용 픽셀들에 대응하는 픽셀 데이터로 변환한다. 이어서, 픽셀 처리 유닛(445)은 표시 장치(470)의 픽셀들에 대한 최종 칼라를 생성할 수 있다(예를 들어, 조명 및 음영의 조정을 통해). Z 버퍼(450)는 통상적으로 심도 데이터를 추가하며, 따라서 표시 장치(470)에서, 렌더링된 장면의 요소들은 사용자에게 심도에 있어서 서로 상대적으로 표시된다. 시스템(400) 및 그의 컴포넌트들은 단지 예시적이다. 다른 컴포넌트들이 추가될 수 있으며, 도시된 컴포넌트들 중 일부가 제거될 수도 있다.
음함수 교집합 곡선들의 예시적인 파라미터화
예시적인 표면들 S1(110) 및 S2(120)의 변역 기반 표현들이 도 5에 500 및 550으로 각각 도시되어 있다. 곡선들(510, 545, 560, 585)은 2개의 표면 S1(110) 및 S2(120)가 교차하는 2개의 변역(예를 들어, 도 1의 130 및 135) 각각 내의 포인트들을 나타낸다. 각각의 변역들(500, 550)의 (u1, v1) 및 (u2, v2)의 포인트 값들의 나머지는 각각의 표면들 S1(110) 및 S2(120)의 포인트들의 나머지를 나타낸다. 변역들(500, 550)은 함께, 프리미티브들 S1(110) 및 S2(120)에 CSG 연산을 적용함으로써 형성되는 임의의 복합 프로시저 표면의 변역 기반 표현을 나타낼 수 있다.
변역 기반 표현들(500, 550)의 분해의 단계(230)(도 2)은 교집합 곡선들(510, 545, 560, 585) 각각의 파라미터화 영역을 결정하는 것으로부터 시작된다. 전술한 바와 같이 프로시저 함수 F(u1, v1, u2, v2)가 주어지고, 이때 F(x)=F(u1, v1, u2, v2)는
Figure 112007091563140-pct00002
가 4D 변역 변수들 (u1, v1, u2, v2)의 값들의 치역인 함수이며, xp 및 xd가 변수들 x의 벡터를 파라미터화 변수들(독립 변수로도 알려짐)의 벡터 및 종속 변수들의 벡터 각각으로 분할하는 함수인 함수 FP(xp)=xd가 존재하는 것으로 가정한다. F(x)가 F:Rm -> Rn인 함수인 경우, 수치 m-n은 변환에서의 파라미터화 변수들의 수를 나타낸다. 따라서, 함수 FP(xp)는 종속 변수들 xd가 독립 또는 파라미터화 변수들 xp의 항으로 표현되는 것을 가능하게 한다. 따라서, 음함수를 파라미터화하는 능력은 그러한 함수의 표현을 저장하는 데 필요한 메모리를 줄이는 직접적인 이점을 갖는데, 이는 종속 변수들의 값들이 독립 또는 파라미터화 변수들의 값들로부터 도출될 수 있기 때문이다. 함수 F:Rm -> Rn에서 n개 변수에 비교되는 m개 변수의 실제 수는 변경될 수 있다. 예를 들어, 4 -> 3 변환이 CSG에서 하나의 대표적인 변환이다.
파라미터화를 결정하기 위한 예시적인 방법
교집합 곡선들(예를 들어, 510, 560)을 기술하는 함수와 같은 음함수를 파라미터화하는 것이 항상 가능한 것은 아닐 수 있다. 구체적으로, 음함수의 모든 변수가 표현식에서 함수의 다른 변수들을 표현하기 위해 파라미터화 변수로서 사용될 수 있는 것은 아니다. 음함수의 임의의 변역 변수에 의한 파라미터화의 가능성을 검증하는 한 가지 방법은 간단한 형태의 음함수 정리를 이용하여, 이러한 함수의 다양한 종속 도함수 행렬 중 어느 것이 비특이성(non-singular)에 접근하는지를 결정하는 것이다. 예를 들어, 전술한 예에서, F는 4개의 변역 변수 및 3개의 치역 변수를 가진 F:R4 ->R3인 함수이고, F(u1, v1, u2, v2)=F(fx, fy, fz)는 아래와 같은 도함수 행렬을 생성할 것이다.
Figure 112007091563140-pct00003
독립 변수로서 u1을 갖는 종속 도함수 행렬이 다음과 같다고 가정한다.
Figure 112007091563140-pct00004
간단한 형태의 음함수 정리에 따르면, 상기 종속 도함수 행렬이 비특이성을 가지며, 따라서 이 행렬의 어떠한 하나의 열도 다른 열들의 가중 합으로 표현될 수 없는 경우, 이 예에서 음함수는 u1을 파라미터화 또는 독립 변수로서 이용하여 파라미터 형태로 표현될 수 있다. 다른 변수들에 기초하는 종속 도함수 행렬들도 비특이성을 가질 수 있으며, 따라서 이들 다른 변수에 기초하는 함수의 파라미터화의 가능성을 나타내며, 따라서 이들 변수는 파라미터화 변수로도 기능할 수 있게 된다.
그러나 곡선의 다른 부분들(예를 들어, 510 및 560)에서, 곡선의 다른 부분들을 파라미터화하기 위하여 하나의 변수를 다른 변수들에 대한 파라미터화 변수로서 선택하는 이익이 존재한다. 도 5에 도시된 바와 같이, 예를 들어, (u1, v1)과 같은 2D 변역 내에서, 관련 종속 도함수 행렬들의 비특이성에 기초하여 파라미터화 영역들이 선택될 수 있다. 도 5에서, 515(P3)에서 u1이 파라미터화 변수인 반면, 520(P2)에서는 v1이 보다 나은 선택이다. 이것은 영역 515(P3) 내에서 파라미터화 변수 u1의 모든 값이 종속 변수 v1의 단 하나의 대응 값을 갖도록 보증된다는 사실에 적어도 부분적으로 의존한다. 그러나 전체 교집합 곡선(510)을 살펴 보면, 어떠한 하나의 파라미터화 변수 u1 또는 v1도 곡선 상의 이들 값 각각이 다른 변수의 단일 값에 대응하게 하는 것으로 보증되지 않는다. 결과적으로, 곡선(510)은 예시적인 파라미터화 영역들 P1(525), P2(520), P3(515) 및 P4(530)로 분할된다. 영역들 P1(525) 및 P3(515)에서, 파라미터화 변수는 u1인 반면, 영역들 P2(520) 및 P4(530)에서 파라미터화 변수는 v1이다. 표면 S2의 변역(550) 내의 예시적인 교집합 곡선(560)의 유사한 분할(예를 들어, 565, 570, 575, 580)도 가능하다. 또한, 도 4에 도시된 2D 파라미터화 영역들은 단지 예시적이며, 다른 파라미터화 영역들도 가능하다. 곡선들(545, 585)의 파라미터화 영역들은 도시되어 있지 않다. 그러나 이들 곡선(545, 585)은 전술한 방식으로 분할될 수도 있다. 보다 높은 차원을 갖는 변역들에 대해서도 동일한 원리가 적용된다.
변역들의 정적 삼각화에 의한 프로시저 표면들의 변역들의 예시적인 분해
CSG 프로시저 표면의 변역 기반 표현(예를 들어, 500, 550)이 파라미터화 영역들(예를 들어, 515, 520, 525, 530)로 분할되면, 변역은 도 6의 방법(600)에 설명되는 바와 같은 사전 처리 동안의 삼각화 프로세스를 통해 정적으로 더 분해된다. 삼각화는 변역 공간을 연결된 삼각형들의 메쉬로 분할한다. 단계(610)에서, 파라미터화 영역들은 제한 에지들을 추가하도록 제한되며, 단계(620)에서, 제한된 파라미터화 영역들에 델라우나이 삼각화를 적용하여, 예를 들어 도 7B에 750으로 도시된 바와 같은 변역을 삼각화하는 제1 세트의 거친 삼각형들을 생성한다. 이어서, 단계(630)에서, 델라우나이 삼각화로부터 결과된 삼각형 세트를 더 정교화하기 위해 곡선 가시성 삼각형들이 결정된다. 단계(640)에서, 결과적인 삼각화 메쉬는 (전술한 바와 같은) 사전 처리 동안 저장되어, 당해 CSG 프로시저 표면들을 포함하는 장면을 렌더링하기 전에 실행 시간에 더 정교화된다.
파라미터화 영역들에 대한 예시적인 제한
도 7A는 파라미터화된 음함수 교집합 곡선(710)이 제한되는(단계(610)) 예시적인 변역(700)을 나타낸다. 예시적인 제한은 파라미터화 영역들(P1, P2, P3, P4)의 포인트들(예를 들어, 엔드 포인트들)을 단순히 연결하는 에지들(예를 들어, 715, 720, 725, 730)이다. 일단 제한되면, 삼각화의 최초 프로세스는 도 7B의 750으로 도시된 바와 같이 변역(700)을 삼각화하는데, 제한들(예를 들어, 715, 720, 725, 730)은 최초의 거친 삼각형들의 세트의 밑변으로서 기능한다. 이러한 제한들은 임의의 삼각화 스킴이 제한 에지들(예를 들어, 715, 720, 725, 730)을 포함할 것을 보증한다. 그러나 제한 에지들(예를 들어, 715, 720, 725, 730)은 예시적이며, 다른 제한들도 가능하다.
예를 들어, 소정 스킴의 제한 에지들은 서로 충돌할 수 있다(예를 들어, 교차를 통해). 도 8A는 이러한 충돌을 나타낸다. 예시적인 변역(800)은 다수의 교집합 곡선(805, 810)을 가질 수 있다. 그러나 파라미터화 영역들이 주의 깊게 선택되지 않을 경우, 곡선(805)의 한 세트의 에지들(815)은 곡선(810)의 한 세트의 에지들(820)과 충돌할 수 있다. 이 경우, 도 8A에서 분명한 충돌을 피하는 한 세트의 제한 에지들(예를 들어, 도 8B의 830 및 825)을 생성하도록 파라미터화 영역들을 더 세분함으로써 도 8B에 도시된 방식으로 파라미터화 영역들에 비충돌 제한들이 적용된다.
예시적인 델라우나이 삼각화
비충돌 제한 에지들(830, 825)의 세트들이 결정되면(단계(610)), 이러한 제한된 변역 공간에 델라우나이 삼각화가 적용된다(단계(620)). 전산 기하학에 있어서, 델라우나이 삼각화 또는 델론 삼각화(때로는 공지되어 있는 바)는 주어진 변역 공간을 삼각화하고 있는 삼각형들의 세트의 최소 각도를 최대화하여 너무 얇은 조각 삼각형들을 피하는 프로세스이다. 얇은 조각 삼각형들은 삼각형의 높이와 폭 간에 상당한 차이가 있는 하나의 양태로서 정의된다. 이러한 얇은 조각 삼각형들은 계산에 있어서 불안정하며, 회피되어야 한다. 일반적으로, n 차원 유클리드 공간 내의 한 세트의 포인트들 P에 대해, 델라우나이 삼각화는 P의 삼각화 DT(P)인데, 이 DT(P) 내의 임의의 심플렉스(simplex)의 외접반구(circum-hemisphere) 내측에는 P 중의 어떠한 포인트도 존재하지 않게 된다. 델라우나이 삼각화를 적용하는 한 가지 방법은 한 번에 하나의 정점을 반복해서 추가하고 그래프의 영향받은 부분들을 다시 삼각화하는 것을 필요로 한다. 정점이 추가될 때, 새로 추가된 정점을 포함하는 외접원을 갖는 모든 삼각형에 대한 검색이 행해진다. 이어서, 이러한 삼각형들이 제거되고, 그래프의 해당 부분이 다시 삼각화된다.
도 9는 델라우나이 삼각화의 개념을 나타낸다. 변역의 상이한 삼각화를 포함하는 상이한 삼각형 세트들이 이들의 높이와 폭의 차이로서 정의되는 이들의 가장 얇은 조각 삼각형으로서 삼각형들(910, 920, 930, 940)을 각각 갖는 것으로 가정하면, 940에서와 같이 너무 얇은 조각 삼각형을 피하도록 델라우나이 삼각화를 달성하기 위해 930을 가장 얇은 조각 삼각형으로서 제공하는 삼각화 스킴이 선택될 것이다.
곡선 가시성 삼각형들을 계산하는 예시적인 방법
델라우나이 삼각화 프로세스가 완료되면, 변역은 가시성 삼각형들을 추가하도록 더 분해된다(도 6의 단계(630)). 이것을 행하기 위하여, 예를 들어 델라우나이 삼각화로부터 결과된 삼각형들을 검색하여, 예를 들어 곡선의 파라미터화 영역들(예를 들어, P1, P2, P3, P4) 중 하나에 대응하는 밑변(1021)을 갖는 삼각형들을 결정한다. 도 10은 파라미터화 영역들 중 하나(P3)에 대응하는 밑변을 가진 그러한 하나의 삼각형을 1010으로 나타내고 있다. 그러나 이러한 몇몇 삼각형들(예를 들어, 1010)은 삼각형의 변들 중 하나 이상이 예를 들어 1020으로 도시된 바와 같은 둘 이상의 곳에서 음함수 교집합 곡선(1025)과 교차하는 정점(1015)을 가질 수 있다. 그러나 1040에 정점을 갖는 새로운 삼각형(1030)이 변역(750)을 더 세분하도록 추가되어, 교집합 곡선들(1025)은 곡선(1025)과 관련된 에지(1021)에 의해 한 변 상에서 한정된 삼각형에 의해 둘 이상의 곳에서 교차하지 않게 될 수 있다. 즉, 곡선 가시성 삼각형들(예를 들어, 1030)은 정점(예를 들어, 1040)을 갖는데, 이 정점(예를 들어, 1040)에서 파라미터화 영역(예를 들어, P3) 내의 곡선(1025) 상의 포인트들로의 투명한 경로(clear path)가 존재하게 된다. 이러한 프로세스는 S나머지 파라미터화 영역들(예를 들어, P1, P2, P3)에 대해 반복될 수 있다.
도 11 및 12는 가시성 삼각형들(예를 들어, 1030)을 계산하는 예시적인 방법들을 나타낸다. 1110과 같은 음함수 교집합 곡선 상의 파라미터화 영역이 주어지면, 도 11에 도시된 바와 같이 엔드 포인트들(c1과 c2) 간의 곡선(1110)의 파라미터화 변수의 간격(
Figure 112007091563140-pct00005
)에 대해 곡선을 정의하는 음함수의 음함수 미분에 의해 곡선에 대한 접선들이 계산된다. 이것은 상이한 기울기 값을 가진 접선들(예를 들어, 1111-1114)의 치역을 산출한다. 접선들(예를 들어, 1111-1114)의 치역으로부터, 최대 기울기 값을 가진 접선 Tmax(예를 들어, 1111에서) 및 최소 기울기 값을 가진 접선 Tmin(예를 들어, 1114에서)이 식별된다.
도 12에 도시된 바와 같이, 1111에서의 Tmax와 1114에서의 Tmin 사이의 각도 차(1115)는 곡선(1110)의 파라미터화 변수의 간격(
Figure 112007091563140-pct00006
)에 대한 접선들의 기울기들의 치역을 정의한다. 치역(1115)에 기초하여, 곡선들의 교차점들 Vp1(1120) 및 Vp2(1130)가 결정된다. 결과적으로, 영역들(1140, 1150) 내의 임의의 포인트가 곡선 가시성 삼각형의 정점(예를 들어, 1120, 1130)이 되도록 선택될 수 있으며, 곡선(1110) 상의 임의의 포인트가 정점에 연결되어 라인을 형성할 수 있는데, 이러한 라인은 어느 다른 곳에서도 곡선(1110)과 교차하지 않게 된다.
도 11-12의 예는, 곡선이 최대 기울기 접선 Tmax 및 최소 기울기 접선 Tmin이 곡선(1110)의 파라미터화 영역의 엔드 포인트들(c1 및 c2)과 일치하는 그러한 곡선인 간단한 경우를 나타낸다. 곡선에 따라, 이것은 항상 그런 것만은 아닐 수도 있다. 예를 들어, 접선들 Tmax 및 Tmin 중 하나 또는 양자는 곡선(1110)의 엔드 포인트들이 아닌 다른 포인트들에 대응할 수 있다. 그럼에도, 곡선 가시성 영역들(예를 들어, 1140, 1150)은 엔드 포인트들(c1 및 c2)에 대한 접선들을 병진 이동시켜 접선들 Tmax 및 Tmin의 교점을 발견함으로써 결정된다. 또한, 곡선 가시성 삼각형들은 곡선 가시성 영역들(1140, 1150) 내의 임의의 포인트를 정점으로서 가질 수 있다. 이것은 교차점들 Vp1(1120) 및 Vp2(1130)일 필요가 없다.
곡선 가시성 삼각형의 정점 위치의 선택에 있어서, 하나의 다른 고려 사항이 도 13A 및 13B를 참조하여 설명된다. 예를 들어, 도 13A에서 곡선 가시성 삼각형(1310)의 정점 vp1(1320)은 음함수 곡선(1315)에 대응하지만, 정점의 위치가 vp1(1320)에 있으므로 곡선 가시성 삼각형(1310)은 제2 음함수 곡선(1305)와 교차하게 되는데, 이는 바람직하지 않다. 이러한 충돌은 도 13A의 파라미터화 영역 P0를 도 13B의 영역들 P3 및 P4로 세분하여 대응하는 곡선 가시성 삼각형들(1325, 1330)이 제2 음함수 곡선(1305)과 충돌하지 않게 함으로써 피할 수 있다. 또한, 도 13B에서, 곡선(1305)과 연관된 곡선 가시성 삼각형들(1340, 1350)은 파라미터화 영역들 P1 및 P2가 세분되게 하여, 음함수 곡선(1315)과 충돌하지 않게 된다.
정적 삼각화의 예시적인 결과
도 14는 세 변 모두에 비곡선 기반 변역 에지들을 가진 단순 변역 삼각형(1410) 및 세 변 중 적어도 한 변에 제한 에지(1420)를 가진 곡선 가시성 삼각형(1415)을 포함하는 예시적인 정적 삼각화(예를 들어, 도 6의 방법(600)에 의함) 후의 변역의 적어도 일부(1400)를 나타낸다. 제한 에지(1420)는 엔드 포인트들(c1, c2)과 같은 음함수 교집합 곡선(1425) 상의 포인트들을 연결한다. 단순 변역 삼각형(예를 들어, 1410) 및 곡선 가시성 삼각형(예를 들어, 1415)의 꼭지점과 관련된 데이터가 저장되고(도 6의 단계(640)), 삼각화를 더 정교화하기 위해 나중에 실행 시간 동안에 검색된다.
예시적인 실행 시간 삼각화
정적 삼각화가 완료되면, 거친 삼각화 메쉬(예를 들어, 1400)는 보다 정교한 메쉬를 생성하도록 실행 시간에 더 정교화된다. 실행 시간에 보다 정교한 삼각화 메쉬를 생성함으로써, 렌더링을 위해 상세한 메쉬를 저장하고 검색하는 것과 연관된 비용을 방지한다. 도 15는 CPU(1510) 및 GPU(1520) 양자에 의한 실행 시간 삼각화를 위한 전반적인 방법(1500)을 나타낸다. 실행 시간 삼각화의 일부(1505)는 CPU(1510)에 의해 수행된다. 단계(1515)에서, CPU(1510) 상에서 실행되는 삼각화 프로그램이 사전 처리 동안에 수행된 정적 삼각화(예를 들어, 도 6의 방법(600))와 관련된 데이터를 수신한다. 데이터는 적어도 표시될 CSG 표면들의 변역들을 삼각화하는 거친 삼각형들의 세트(예를 들어, 1400)와 연관된 꼭지점 데이터를 포함한다. 예를 들어, 이러한 데이터는 전술한 정적 삼각화 방법으로부터 결과되는 단순 삼각형(예를 들어, 도 14의 1410)의 꼭지점 및 곡선 가시성 삼각형(예를 들어, 1415)의 꼭지점의 변역 기반 좌표들을 가진 데이터를 포함한다. 단계(1525)에서, 이러한 정적 삼각화는, 변역 내에 에지들을 추가하여 임의의 단순 삼각형들(예를 들어, 1410)을 세분하고 곡선 가시성 삼각형들(예를 들어, 1415)을 더 세분함으로써 더 정교화된다. 이러한 세분은 에지들의 사용자 정의 파라미터 길이가 삼각형의 변들을 형성할 때까지 계속될 수 있다.
정적 삼각화 메쉬를 정교화하는 한 가지 방법(1525)이 도 16을 참조하여 설명된다. 단계(1610)에서, 정적 삼각화로부터 결과된 곡선 가시성 삼각형들(예를 들어, 1415)은 음함수 곡선의 파라미터화 영역들 상의 추가 포인트들에 추가 에지들을 추가함으로써 더 세분된다. 도 17A는 이러한 하나의 세분을 나타내는데, 여기서 곡선 가시성 삼각형(1710)은, 파라미터화 영역 곡선(1715)의 엔드 포인트들(c1 및 c2)에 중간인 c3 및 c4에서의 추가 곡선 포인트들을 연결하는 에지들을 추가함으로써 삼각형들(1725, 1730, 1735)로 더 세분된다. 변역의 좌표들로 지정되는 이러한 곡선 포인트들(예를 들어, c1, c2, c3, c4)은 메모리로부터 검색될 수 있다. 이러한 포인트들은 또한 음함수 교집합 곡선(1715)을 정의하는 음함수를 풂으로써 실행 시간에 계산될 수 있다. 단계(1630)에서, 단순 삼각형들(예를 들어, 도 17B에 도시)은 또한, 예를 들어 도 17B에 도시된 바와 같은 1740 및 1745에서의 보다 많은 삼각형을 생성하도록 에지들(예를 들어, 1750)을 추가함으로써 더 세분된다. 이러한 세분은 메쉬의 세분된 삼각형들의 변들을 형성하는 에지들에 대한 사용자 정의 임계 파라미터 길이에 적어도 부분적으로 기초한다.
1740 및 1745에서 세분된 단순 삼각형들을 생성하도록 추가된 에지들(예를 들어, 1750)에 기초하여, 세분된 삼각형들(예를 들어, 도 17B의 1730, 1740 및 1745) 간의 공유 에지들이 일치하지 않는 것을 보증하기 위해 새로운 에지(1755)가 추가된다. 하나의 삼각형의 에지들이 다른 삼각형의 공유 에지들과 일치되지 않을 때 불일치가 발생한다. 예를 들어, 에지(1750)가 에지(1755)와 만나지 않은 경우, 불일치가 발생하게 된다. 이러한 불일치는, 삼각화 메쉬에 의해 표현되는 표면이 스크린 상에 최종 렌더링될 때 그 표면 상에 원하지 않는 균열을 초래할 수 있다. 이러한 불일치를 최소화하는 것은 렌더링되는 이미지의 전체 품질을 향상시키게 된다.
예를 들어, 사용자 설정 파라미터 임계 길이 요건을 만족시키기 위해 추가 에지들(1756)이 또한 추가된다. 따라서, 도 17C의 새로운 삼각형들(1760, 1770, 1775)은 도 17B의 곡선 가시성 삼각형(1730)에 의해 최초로 표현된 변역의 일부를 표현하도록 추가된다. 에지들(예를 들어, 1756)의 추가는 도 17B의 인접 삼각형들(1725, 1735)이 1785 및 1780과 같은 삼각형들을 추가하도록 더 세분되게 한다. 이러한 세분은 샘플링 삼각형들의 인스턴스로서 지칭되는 도 17C에 도시된 바와 같은 삼각형들의 조합을 초래한다. 이러한 실행 시간 세분된 샘플링 삼각형들의 조합의 꼭지점들에 관한 데이터는 단계(1640)에서 저장된다.
도 15를 다시 참조하면, 전술한 바와 같이 단계(1525)에서 결정된 샘플링 삼각형들은 그 형상, 크기 및 교집합 곡선에 대한 위치와 같은 특성들에 기초하여 분류된다. 예를 들어, 이러한 분류는 정적 삼각화(예를 들어, 도 6의 방법(600)에 의함) 동안 결정된 최초의 가시성 삼각형(예를 들어, 도 14의 1415)을 세분함으로써 생성된 교집합 곡선(1715) 상의 포인트들을 연결하는 에지에 의해 한 변 상에서 한정된 실행 시간 세분된 곡선 가시성 삼각형(예를 들어, 도 17B의 1775)을 포함하지만 이에 제한되는 것은 아니다. 다른 분류는 또한 교집합 곡선(예를 들어, 1715)과 관련된 에지에 의해 어떠한 변에서도 한정되지 않는 비곡선 기반 단순 삼각형(예를 들어, 도 17B의 1740 및 1745)을 포함한다. 또 다른 분류는 정적 삼각화(예를 들어, 도 6의 방법(600)에 의함) 동안 결정된 최초의 곡선 가시성 삼각형(예를 들어, 도 14의 1415)을 세분함으로써 생성된 1760, 1770, 1780 및 1785와 같은 비곡선 기반 삼각형들을 포함한다. 이러한 분류와 관련된 데이터는 실행 시간 삼각화(1525)로부터 결과되는 샘플링 삼각형들(도 17C) 각각과 연관된 분류를 식별하기 위한 별칭(예를 들어, 영숫자)을 추가함으로써 유지될 수 있다.
다시 도 15를 참조하면, 또한 실행 시간에, GPU(1520)는 단계(1540)에서 삼각화를 더 정교화하는 다른 하나의 방법(1535)을 구현한다. 방법(1535)에 따르면, 단계(1540)에서, GPU는 샘플링 삼각형들(예를 들어, 도 17C에서와 같음)의 꼭지점 데이터 및 삼각형들을 상이한 유형의 샘플링 삼각형들로 분류하는 데이터를 수신한다. 이어서, 단계(1545)에서, 분류에 기초하여, GPU(1520)는 기하학 인스턴싱을 적용하여 샘플링 삼각형들에 추가 에지를 추가함으로써, 단계(1550)에서 정교화된 메쉬를 렌더링하기 전에, 삼각화 메쉬를 더 정교화한다(예를 들어, 도 17C). 이러한 방식으로, 실행 시간에 추가 삼각화가 구현되어, 복합 메쉬들을 정의하는 복잡한 데이터 구조를 저장할 필요 없이 임의의 교집합 곡선을 포함하는 CSG 프로시저 표면의 상세를 더 정의할 수 있다. 기하학 인스턴싱을 적용하는 예시적인 방법(1545)은 후술된다.
정교화된 삼각화에 대한 기하학 인스턴싱의 예시적인 방법
도 18은 기하학 인스턴싱을 적용하는 예시적인 방법(1800)을 나타낸다. 단계(1810)에서, 도 17C에 도시된 메쉬를 형성하는 것들과 같은 샘플링 삼각형들의 꼭지점 데이터가 예를 들어 GPU(예를 들어, 도 15의 1520) 상에서 실행되는 꼭지점 쉐이더 프로그램에 의해 수신된다. 꼭지점 데이터 외에, 샘플링 삼각형들을 상이한 유형의 삼각형들로 분류하기 위한 데이터도 수신된다. 단계(1820)에서, 샘플링 삼각형들의 분류에 적어도 부분적으로 기초하여, 샘플링 삼각형들 중 적어도 일부에 대해 적절한 정규 기하학 인스턴싱 메쉬가 선택된다. 이어서, 단계(1830)에서, 샘플링 삼각형들 중 적어도 일부에 대해, 샘플링 삼각형들의 꼭지점 데이터 및 이와 연관된 기하학 인스턴싱 메쉬의 중심 좌표에 기초하여, 인스턴스 메쉬 내에 표현된 삼각형들이 샘플링 삼각형들로 맵핑된다.
기하학 인스턴싱 메쉬들을 샘플링 삼각형들로 맵핑하는 예시적인 방법
도 19는 예시적인 맵핑을 나타낸다. 샘플링 삼각형 메쉬(1900)는 인스턴스 메쉬들(예를 들어, 1910, 1920, 1930)을 적절히 맵핑함으로써 더 삼각화된다. 도 20은 중심 좌표를 포함하는 보다 상세한 인스턴스 메쉬 유형들의 3개 예(1910, 1920, 1930)를 나타낸다. 특정 유형의 샘플링 삼각형으로 맵핑될 적절한 인스턴스 메쉬를 선택하기 위한 예시적인 기준들의 세트에서, 도 19의 1915와 같은 실행 시간 세분된 단순 샘플링 삼각형이 1910에서의 삼각형과 같은 NNN 유형 삼각형으로 맵핑된다. 1935와 같은 실행 시간 세분된 곡선 가시성 삼각형은 1930에서의 메쉬와 같은 NN1 유형의 인스턴스 메쉬로 맵핑된다. 마지막으로, 정적 곡선 가시성 삼각형(예를 들어, 도 14의 1415)의 실행 시간 세분으로부터 결과되는 비곡선 기반 삼각형(1925)은 1920에서의 삼각형과 같은 NN2N 유형 삼각형으로 맵핑되며, 인접 삼각형들의 구성에 따라, 이러한 비곡선 기반 삼각형들은 NN1으로 맵핑될 수도 있다.
기호 N은 정규 인스턴스 메쉬(예를 들어, 1910, 1920, 1930)와 연관된 중심 포인트들 사이(예를 들어, 도 20의 2011과 2012의 사이)의 선분들의 적절한 수를 나타낸다. 예를 들어, 1910에서는, 삼각형 메쉬(1910)의 각 변 상의 중심 포인트들에 대응하는 에지들의 수가 각 변에서 2이므로, N은 2이다. 마찬가지로, 1920에서 NN2N 메쉬는 밑변 2021을 따라 4개의 선분 및 다른 두 변(2022, 2023)을 따라 2개의 선분을 갖는다. 삼각형 메쉬(1930)는 NN1 유형이며, 이 예에서는 밑변(2031)이 하나의 선분만을 갖는 반면, 다른 두 변(2032, 2033)이 2개의 선분을 가지므로, N은 또한 2이다. 예에서와 같이, 다양한 유형의 기하학 인스턴스 메쉬들(예를 들어, 1910, 1920, 1930) 각각에 대해 N을 동일하게 하는 것은 기하학 인스턴싱 후에 정교화된 실행 시간 삼각화 메쉬가 불일치 에지를 갖지 않는 것을 보증한다.
인접한 삼각형들을 따른 불일치 에지들은 또한 선택된 샘플링 삼각형에 맵핑할 적절한 유형의 인스턴스 메쉬(예를 들어, 1910, 1920, 1930)를 선택함으로써 피해진다. 예를 들어, 도 17C에서는, NNN 유형(도 19의 1910) 메쉬로 맵핑될 인접 삼각형들(1740, 1745)과의 불일치 에지들을 피하기 위하여, 최초의 곡선 가시성 삼각형(예를 들어, 도 14의 1415)을 세분함으로써 생성된 1760 및 1770과 같은 비곡선 기반 삼각형들이 NN2N 유형(도 19의 1920) 대신에 NN1 유형(도 19의 1930)의 인스턴스 메쉬로 맵핑된다. 또한, 도 17C의 샘플링 삼각형들(1760, 1770)은 이들의 인접 샘플링 삼각형들(예를 들어, 1745, 1775)의 에지들과의 일치를 보증하기 위하여 NN2N 메쉬 대신에 NN1 메쉬로 맵핑된다.
2로 예시된 N의 값들 및 대응하는 중심 포인트들을 갖는 삼각형들(1910, 1920, 1930)은 단지 예시적이며, 따라서 삼각화되는 특정 변역 및 원하는 삼각화의 범위 및 심도와 같은 다른 인자에 기초하여 변경될 수 있다. 삼각화 메쉬의 공유 에지들 간의 불일치를 최소화하는 것은 결국 렌더링된 픽처의 품질을 보다 향상시킬 것이다.
삼각형 인스턴스 메쉬를 샘플링 삼각형으로 맵핑하기 위한 예시적인 알고리즘
중심 좌표는 도 20에서 2017에서의 계수(예를 들어, (0,1,0)), 2016에서의 계수(.5,.5,0) 및 2014에서의 계수(0,0,1)의 세트에 기초하는 정규 삼각형 메쉬의 변들을 따르는 포인트들을 정의한다. 이러한 계수 유형의 중심 좌표 값들에 기초하여, 이들 포인트들을 나타내기 위한 선택된 변역 내의 실제 좌표들이 메쉬들의 적절한 샘플링 삼각형(예를 들어, 1900에서 나타낸 바와 같음)으로의 맵핑 동안에 계산된다. 중간 중심 포인트들(예를 들어, 도 20의 2016)에 대한 실제 변역 좌표들은 꼭지점들 p0(u0,v0)(2012), p1(u1,v1)(2013) 및 p2(u2,v2)의 변역 좌표들 내의 공지된 좌표 값들과 관련하여 계산된다.
도 21은 인스턴스 메쉬를 샘플링 삼각형으로 맵핑하는 프로세스를 설명하는 예시적인 알고리즘의 리스트(2100)이다. 이 방법에 따르면, (x,y,z) 형태의 계수들의 형태의 중심 좌표들(2115) 및 꼭지점들(p0, p1, p2)에 대한 2120에서의 2D 변역 좌표들 (u,v)의 입력에 기초한다. 2130에서, 중심 포인트들에 대한 변역 좌표들 (u,v)은 이들의 계수 값들 및 꼭지점들(p0, p1, p2)의 공지된 변역 좌표 값들에 기초하여 계산된다. 리스트 내의 알고리즘은 예시적이다. 기하학 인스턴싱에 기초하여 삼각화 메쉬의 꼭지점 데이터를 표현하기 위해 표면의 변역 표현 상의 포인트들을 결정하기 위해 다른 방법들이 사용될 수 있다.
예시적인 컴퓨팅 환경
도 22 및 아래의 설명은 개시되는 기술이 구현될 수 있는 예시적인 컴퓨팅 환경의 간단하고 일반적인 설명을 제공하기 위한 것이다. 요구되지는 않았지만, 개시되는 기술은 일반적으로 퍼스널 컴퓨터(PC)에 의해 실행되는 프로그램 모듈과 같은 컴퓨터 실행가능 명령들과 관련하여 설명되었다. 일반적으로, 프로그램 모듈은 특정 태스크를 수행하거나 특정 추상 데이터 유형을 구현하는 루틴, 프로그램, 개체, 컴포넌트, 데이터 구조 등을 포함한다. 더욱이, 개시되는 기술은 핸드-헬드 장치, 멀티프로세서 시스템, 마이크로프로세서 기반 또는 프로그램가능한 가전제품, 네트워크 PC, 미니 컴퓨터, 메인프레임 컴퓨터 등을 포함하는 다른 컴퓨터 시스템 구성을 이용하여 구현될 수도 있다. 개시되는 기술은 또한 통신 네트워크를 통해 연결되어 있는 원격 처리 장치들에 의해 태스크들이 수행되는 분산 컴퓨팅 환경에서 구현될 수도 있다. 분산 컴퓨팅 환경에서, 프로그램 모듈들은 로컬 및 원격 메모리 저장 장치 둘다에 위치할 수 있다.
도 22는 설명되는 실시예들이 구현될 수 있는 적절한 컴퓨팅 환경(2200)의 일반화된 예를 나타낸다. 본 발명은 많은 범용 또는 특수 목적의 컴퓨팅 환경에서 구현될 수 있으므로, 컴퓨팅 환경(2200)은 본 발명의 용도 또는 기능성의 범위에 관해 어떤 제한도 암시하고자 하는 것이 아니다.
도 22와 관련하여, 컴퓨팅 환경(2200)은 적어도 하나의 중앙 처리 장치(2210) 및 메모리(2220)를 포함한다. 도 22에서, 이러한 가장 기본적인 구성(2230)은 점선 내에 포함되어 있다. 중앙 처리 장치(2210)는 컴퓨터 실행가능 명령들을 실행하며, 실제 또는 가상 프로세서일 수 있다. 환경(2200)은 꼭지점 맵핑, 픽셀 처리, 렌더링 및 텍스처 맵핑과 같은 그래픽 연산을 실행하기 위한 그래픽 처리 장치(GPU; 2215)를 더 포함한다. 다중 처리 시스템에서는, 다수의 처리 장치가 컴퓨터 실행가능 명령들을 실행하여 처리 능력을 향상시키며, 따라서 GPU 및 CPU가 동시에 동작할 수 있다. 메모리(2220)는 휘발성 메모리(예를 들어, 레지스터, 캐시, RAM), 비휘발성 메모리(예를 들어, ROM, EEPROM, 플래시 메모리 등), 또는 이 둘의 소정 조합일 수 있다. 메모리(2220)는 프로시저 기하 개체들을 삼각화하는 설명되는 방법들을 구현하는 소프트웨어(2280)를 저장한다. 컴퓨팅 환경은 추가 특징을 가질 수 있다. 예를 들어, 컴퓨팅 환경(2200)은 저장 장치(2240), 하나 이상의 입력 장치(2250), 하나 이상의 출력 장치(2260), 및 하나 이상의 통신 접속(2270)을 포함한다. 버스, 제어기 또는 네트워크와 같은 상호접속 메커니즘(도시되지 않음)이 컴퓨팅 환경(2200)의 컴포넌트들을 상호접속시킨다. 통상적으로, 운영 체제 소프트웨어(도시되지 않음)는 컴퓨팅 환경(2200)에서 실행되는 다른 소프트웨어에 대한 운영 환경을 제공하며, 컴퓨팅 환경(2200)의 컴포넌트들의 액티비티를 조정한다.
저장 장치(2240)는 이동식 또는 비이동식일 수 있으며, 자기 디스크, 자기 테이프 또는 카세트, CD-ROM, CD-RW, DVD, 또는 정보를 저장하는 데 사용할 수 있고 컴퓨팅 환경(2200) 내에서 액세스될 수 있는 임의의 다른 매체를 포함한다. 저장 장치(2240)는 프로시저 기하 개체들을 삼각화하는 방법들을 구현하는 소프트웨어(2280)의 명령들을 저장한다.
입력 장치(들)(2250)는 키보드, 마우스, 펜 또는 트랙볼과 같은 터치 입력 장치, 음성 입력 장치, 스캐닝 장치, 또는 컴퓨팅 환경(2200)에 입력을 제공하는 다른 장치일 수 있다. 오디오에 대해, 입력 장치(들)(2250)는 아날로그 또는 디지털 형태의 오디오 입력을 수신하는 사운드 카드 또는 유사 장치, 또는 컴퓨팅 환경에 오디오 샘플을 제공하는 CD-ROM 판독기일 수 있다. 출력 장치(들)(2260)는 표시 장치, 프린터, 스피커, CD 기록 장치, 또는 컴퓨팅 환경(2200)으로부터 출력을 제공하는 다른 장치일 수 있다.
통신 접속(들)(2270)은 통신 매체를 통한 다른 컴퓨팅 엔티티로의 통신을 가능하게 한다. 통신 매체는 피변조 데이터 신호 내의 컴퓨터 실행가능 명령들, 압축된 그래픽 정보, 또는 다른 데이터와 같은 정보를 운반한다.
컴퓨터 판독가능 매체는 컴퓨팅 환경 내에서 액세스될 수 있는 임의의 이용가능 매체이다. 예를 들어, 컴퓨팅 환경(2200)에서 컴퓨터 판독가능 매체는 메모리(2220), 저장 장치(2240), 통신 매체, 및 상기한 임의 것들의 조합을 포함하지만 이에 제한되는 것은 아니다.
실시예들을 참조하여 본 발명의 원리를 설명하고 예시하였지만, 실시예들은 그러한 원리를 벗어나지 않고 배열 및 상세에 있어서 변경될 수 있음을 인식할 것이다. 소프트웨어로 나타낸 실시예들의 요소들은 하드웨어로 구현될 수 있고, 그 반대도 마찬가지이다. 또한, 임의의 예로부터의 기술들은 다른 예들 중 임의의 하나 이상에 설명되는 기술들과 조합될 수 있다.
본 발명의 원리가 적용될 수 있는 많은 가능한 실시예에 비추어, 실시예들은 본 발명의 예일 뿐, 발명의 범위에 대한 제한으로서 간주되지 않아야 한다는 것을 인식해야 한다. 예를 들어, 본 명세서에 설명되는 시스템 및 도구의 다양한 컴포넌트는 기능 및 용도에서 조합될 수 있다. 따라서, 본 출원인은 청구범위의 범위 및 사상 내에 있는 모든 내용을 본 발명으로서 청구한다.

Claims (20)

  1. 복수의 프리미티브 그래픽 개체들(primitive graphical objects)에 CSG(constructive solid geometry) 연산을 적용함으로써 적어도 부분적으로 형성되는 복합 그래픽 개체의 삼각화된 메쉬 표현(triangulated mesh representation)을 생성하기 위한 컴퓨터 구현 방법으로서,
    상기 복수의 프리미티브 그래픽 개체들의 그래픽 모델들을 표현하는 데이터를 수신하는 단계;
    상기 복수의 프리미티브 그래픽 개체들에 기초하여 CSG 연산을 수행하여 상기 복합 그래픽 개체의 변역 기반 표현(domain based representation)을 생성하는 단계;
    상기 복합 그래픽 개체의 상기 변역 기반 표현을 분해하여, 상기 복합 그래픽 개체를 표현하는 2차원의 거친 정적 삼각화 메쉬들(coarse statically triangulated two-dimensional meshes)을 생성하는 단계;
    상기 2차원의 거친 정적 삼각화 메쉬들을 저장하는 단계; 및
    실행 시간에(at runtime), 상기 2차원의 거친 정적 삼각화 메쉬들에 기하학 인스턴싱(geometry instancing)을 적용하여, 상기 복합 그래픽 개체를 표시 장치에 렌더링하기 위해 3차원의 실행 시간 정교화된 삼각화 메쉬들(refined runtime three-dimensional triangulated meshes)을 생성하는 단계
    를 포함하는,
    삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  2. 제1항에 있어서,
    상기 복합 그래픽 개체의 상기 변역 기반 표현은 상기 복수의 프리미티브 그래픽 개체들에 대해 수행되는 상기 CSG 연산에 적어도 부분적으로 기초하여 음함수(implicit function)에 의해 적어도 부분적으로 정의되는 음함수 교집합 곡선들(implicit curves of intersection)을 포함하는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  3. 제2항에 있어서,
    상기 2차원의 거친 정적 삼각화 메쉬들을 생성하는 단계는,
    상기 음함수 교집합 곡선들 내의 복수의 파라미터화 영역들을 결정하는 단계;
    상기 복수의 파라미터화 영역들에 제한 에지들(constraining edges)을 추가하는 단계;
    상기 제한 에지들로 상기 복합 그래픽 개체의 상기 변역 기반 표현을 삼각화하여, 상기 복합 그래픽 개체의 상기 변역 기반 표현의 델라우나이 삼각화(Delaunay triangulation)를 결정하는 단계; 및
    꼭지점들(vertices)을 추가함으로써 상기 델라우나이 삼각화를 더 삼각화하여, 밑변(base)으로서 대응되는 제한 에지들을 갖는 곡선 가시성 삼각형들을 생성하는 단계
    를 포함하는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  4. 제3항에 있어서,
    상기 복합 그래픽 개체의 상기 변역 기반 표현은 적어도 복수의 음함수 교집합 곡선들을 포함하고, 상기 방법은,
    상기 복수의 음함수 교집합 곡선들의 상이한 곡선들에 대응하는 상기 제한 에지들이 서로 교차하는지를 결정하는 단계; 및
    상기 교차하는 제한 에지들이 더 이상 서로 교차하지 않을 때까지 상기 교차하는 제한 에지들에 대응하는 상기 파라미터화 영역들 중 적어도 하나를 세분(sub-dividing)하는 단계
    를 더 포함하는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  5. 제3항에 있어서,
    상기 곡선 가시성 삼각형들이 정점(apex)을 포함하되, 상기 정점에서 상기 제한 에지들 중 대응하는 에지 상의 임의의 포인트까지의 직선 선분이 상기 음함수 곡선들 중 대응하는 곡선과 한 번 이하로 교차하는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  6. 제3항에 있어서,
    상기 곡선 가시성 삼각형들을 생성하는 단계는, 대응하는 파라미터화 영역들과 연관된 독립 변수들의 값들의 치역(range)에 대해 상기 음함수 곡선들 중 대응하는 곡선을 정의하는 상기 음함수의 음함수 미분을 계산함으로써 상기 대응하는 파라미터화 영역들에 대한 접선들의 치역(range of tangents)을 결정하는 단계를 포함하는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  7. 제6항에 있어서,
    상기 접선들의 치역은 최대값 기울기를 갖는 최대 접선 및 최소값 기울기를 갖는 최소 접선을 포함하고, 상기 곡선 가시성 삼각형들은 가시성 영역에서 정점을 선택함으로써 생성되는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  8. 제7항에 있어서,
    상기 가시성 영역은 제1 선분 및 제2 선분에 의해 한정되는 상기 변역 내의 영역을 결정함으로써 결정되고, 상기 제1 선분은 상기 최대 기울기를 가지며, 상기 대응하는 파라미터화 영역의 제1 엔드 포인트로부터 연장하고, 상기 제2 선분은 상기 최소 기울기를 가지며, 상기 대응하는 파라미터화 영역의 제2 엔드 포인트로부터 상기 제1 및 제2 선분들이 서로 교차하는 상기 변역 내의 한 포인트를 지나서 연장하는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  9. 제8항에 있어서,
    상기 곡선 가시성 삼각형들의 상기 정점들이 되도록 선택되는 상기 가시성 영역 내의 상기 포인트들은 상기 곡선 가시성 삼각형들 간의 충돌(interference)을 피하도록 선택되는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  10. 제1항에 있어서,
    실행 시간에, 상기 거친 정적 삼각화 메쉬들의 삼각형들을 샘플링 삼각형들의 실행 시간 세분된 메쉬들로 더 세분하는 단계를 더 포함하는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  11. 제10항에 있어서,
    샘플링 삼각형 분류 유형들에 따라 상기 샘플링 삼각형들의 분류를 결정하는 단계를 더 포함하고, 상기 샘플링 삼각형 유형들은 비곡선 기반 단순 샘플링 삼각형, 곡선 가시성 삼각형을 세분함으로써 생성되는 비곡선 기반 삼각형 및 곡선 기반 실행 시간 곡선 가시성 삼각형으로 이루어진 그룹으로부터 선택되는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  12. 제11항에 있어서,
    상기 거친 정적 삼각화 메쉬에 기하학 인스턴싱을 적용하여 상기 실행 시간 정교화된 삼각화 메쉬를 생성하는 단계는,
    상기 샘플링 삼각형들로 맵핑될 기하학 인스턴스 메쉬들을, 이들에 대응하는 샘플링 삼각형 분류 유형에 적어도 부분적으로 기초하여 선택하는 단계; 및
    상기 기하학 인스턴스 메쉬들의 중심 좌표들(barycentric coordinates)에 적어도 부분적으로 기초하여 상기 기하학 인스턴스 메쉬들을 상기 샘플링 삼각형들로 맵핑하는 단계
    를 포함하는, 삼각화된 메쉬 표현을 생성하기 위한 컴퓨터 구현 방법.
  13. 복수의 프리미티브 프로시저 표면들(primitive procedural surfaces)을 이용하여 수행되는 CSG 연산에 적어도 부분적으로 기초하여 형성된 복합 프로시저 표면을 렌더링하기 위한 컴퓨터 시스템으로서,
    복합 그래픽 개체의 변역 기반 표현을 사전 처리하여 상기 복합 그래픽 개체를 표현하는 거친 정적 삼각화 메쉬들을 생성하고, 실행 시간에 상기 정적 삼각화 메쉬들 중 적어도 일부의 삼각형들을 세분함으로써 상기 정적 삼각화 메쉬들을 정교화하여 샘플링 삼각형들의 메쉬들을 생성하기 위해 동작할 수 있도록 프로그래밍된 범용 중앙 처리 장치; 및
    상기 샘플링 삼각형들의 메쉬들과 관련된 꼭지점 데이터 및 상기 샘플링 삼각형들의 분류와 관련된 데이터를 수신하고, 상기 샘플링 삼각형들의 상기 분류에 적어도 부분적으로 기초하여 상기 샘플링 삼각형들 내에 맵핑될 기하학 인스턴싱 메쉬들을 선택함으로써 표시 장치 상에 렌더링하기 위해 실행 시간 정교화된 삼각화 메쉬들을 생성하기 위하여 동작할 수 있도록 프로그래밍된 그래픽 처리 장치
    를 포함하는,
    컴퓨터 시스템.
  14. 제13항에 있어서,
    상기 복합 그래픽 개체는 복수의 프리미티브 프로시저 개체들을 이용하여 수행되는 상기 CSG 연산에 의해 적어도 부분적으로 생성되는 적어도 하나의 음함수 교집합 곡선을 포함하고, 상기 범용 중앙 처리 장치는 상기 음함수 곡선들의 파라미터화 영역들을 결정하도록 더 동작할 수 있는, 컴퓨터 시스템.
  15. 제14항에 있어서,
    상기 정적 삼각화 메쉬들을 정교화하여 상기 샘플링 삼각형들의 메쉬들을 생성하는 것은 상기 음함수 교집합 곡선들 상의 포인트들을 계산하고, 추가 에지들을 추가하여 곡선 가시성 삼각형들을 세분함으로써 상기 정적 삼각화 메쉬들을 적어도 부분적으로 형성하는 것을 포함하는, 컴퓨터 시스템.
  16. 제13항에 있어서,
    상기 샘플링 삼각형들의 상기 분류는 비곡선 기반 단순 샘플링 삼각형, 곡선 가시성 삼각형을 세분함으로써 생성되는 비곡선 기반 삼각형 및 곡선 기반 실행 시간 곡선 가시성 삼각형으로 이루어진 그룹으로부터 선택되는 분류 유형을 포함하는, 컴퓨터 시스템.
  17. 제16항에 있어서,
    상기 샘플링 삼각형들 내에 맵핑될 상기 기하학 인스턴싱 메쉬들을 선택함으로써 실행 시간 정교화된 삼각화 메쉬들을 생성하는 것은, 곡선 기반 실행 시간 곡선 가시성 삼각형의 분류 유형을 가진 샘플링 삼각형들로 맵핑될 NN1 유형 인스턴스 메쉬를 선택하는 것을 포함하는, 컴퓨터 시스템.
  18. 제16항에 있어서,
    상기 샘플링 삼각형들 내에 맵핑될 상기 기하학 인스턴싱 메쉬들을 선택함으로써 실행 시간 정교화된 삼각화 메쉬들을 생성하는 것은, 비곡선 기반 단순 샘플링 삼각형의 분류 유형을 가진 샘플링 삼각형들로 맵핑될 NNN 유형 인스턴스 메쉬를 선택하는 것을 포함하는, 컴퓨터 시스템.
  19. 제16항에 있어서,
    상기 샘플링 삼각형들 내에 맵핑될 상기 기하학 인스턴싱 메쉬들을 선택함으로써 실행 시간 정교화된 삼각화 메쉬들을 생성하는 것은, 상기 거친 정적 삼각화 메쉬들의 곡선 가시성 삼각형을 세분함으로써 생성되는 비곡선 기반 삼각형의 분류 유형을 가진 샘플링 삼각형들로 맵핑될 NN2N 유형 인스턴스 메쉬를 선택하는 것을 포함하는, 컴퓨터 시스템.
  20. 복수의 프리미티브 프로시저 표면들을 이용하여 수행되는 CSG 연산에 적어도 부분적으로 기초하여 형성된 복합 프로시저 표면들을 렌더링하는 방법을 수행하기 위한 컴퓨터 실행가능 명령들을 저장한 적어도 하나의 컴퓨터 판독가능 기록 매체로서,
    상기 방법은,
    상기 복합 프로시저 표면들의 정적 삼각화된 표현의 적어도 일부의 삼각형들과 관련된 꼭지점 데이터를 수신하는 단계;
    상기 복합 프로시저 표면들의 상기 정적 삼각화된 표현의 적어도 일부의 삼각형들의 분류에 적어도 부분적으로 기초하여, 상기 복합 프로시저 표면들의 상기 정적 삼각화된 표현의 적어도 일부의 상기 삼각형들로 맵핑될 기하학 인스턴싱 메쉬들을 선택하는 단계;
    상기 기하학 인스턴싱 메쉬들의 중심 좌표들에 적어도 부분적으로 기초하여, 상기 복합 프로시저 표면들의 상기 정적 삼각화된 표현의 적어도 일부의 상기 삼각형들 내에 상기 기하학 인스턴싱 메쉬들을 맵핑하는 단계를 포함하는,
    컴퓨터 판독가능 기록 매체.
KR1020077029774A 2005-06-30 2006-06-28 프로시저 기하 개체의 삼각화 Expired - Fee Related KR101265810B1 (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US11/172,653 US7408548B2 (en) 2005-06-30 2005-06-30 Triangulating procedural geometric objects
US11/172,653 2005-06-30

Publications (2)

Publication Number Publication Date
KR20080022551A KR20080022551A (ko) 2008-03-11
KR101265810B1 true KR101265810B1 (ko) 2013-05-20

Family

ID=37588889

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020077029774A Expired - Fee Related KR101265810B1 (ko) 2005-06-30 2006-06-28 프로시저 기하 개체의 삼각화

Country Status (5)

Country Link
US (1) US7408548B2 (ko)
EP (1) EP1899854B1 (ko)
KR (1) KR101265810B1 (ko)
CN (1) CN100583084C (ko)
WO (1) WO2007005537A2 (ko)

Families Citing this family (39)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100172554A1 (en) * 2007-01-23 2010-07-08 Kassab Ghassan S Image-based extraction for vascular trees
CN101383047B (zh) * 2007-09-03 2011-05-04 鸿富锦精密工业（深圳）有限公司 曲面网格化方法
TWI386864B (zh) * 2007-09-14 2013-02-21 Hon Hai Prec Ind Co Ltd 曲面網格化方法
US8773432B2 (en) * 2008-04-18 2014-07-08 Adobe Systems Incorporated Triangulation for accelerated multi-resolution rendering of stroked paths
GB0818277D0 (en) 2008-10-06 2008-11-12 Advanced Risc Mach Ltd Graphics processing system
GB0818280D0 (en) 2008-10-06 2008-11-12 Advanced Risc Mach Ltd Graphics processing systems
GB0818278D0 (en) 2008-10-06 2008-11-12 Advanced Risc Mach Ltd Graphics processing systems
GB0818279D0 (en) * 2008-10-06 2008-11-12 Advanced Risc Mach Ltd Graphics processing systems
US8749552B2 (en) * 2008-10-17 2014-06-10 Imagination Technologies Limited Synthetic acceleration shapes for use in ray tracing
TW201020974A (en) * 2008-11-26 2010-06-01 Inst Information Industry Triangulation processing systems and methods, and computer program products thereof
CN101872488B (zh) * 2009-04-27 2012-05-16 鸿富锦精密工业（深圳）有限公司 曲面渲染系统及方法
CN101582173B (zh) * 2009-06-24 2012-07-11 中国石油天然气集团公司 复杂地质构造块状模型构建方法
EP2400410B1 (en) * 2010-05-25 2014-01-08 Dassault Systèmes Computing of a resulting closed triangulated polyhedral surface from a first and a second modeled object
US20110310102A1 (en) * 2010-06-17 2011-12-22 Via Technologies, Inc. Systems and methods for subdividing and storing vertex data
DE112012003243T5 (de) 2011-08-05 2014-04-30 Caustic Graphics, Inc. Systeme und Verfahren für die Erzeugung und Aktualisierung für 3D-Szenenbeschleunigungsstrukturen
EP2600315B1 (en) * 2011-11-29 2019-04-10 Dassault Systèmes Creating a surface from a plurality of 3D curves
CN107403461B (zh) * 2012-01-16 2020-12-22 英特尔公司 使用随机光栅化生成随机采样分布的采样设备和方法
CN102682476B (zh) * 2012-05-15 2015-11-25 深圳市旭东数字医学影像技术有限公司 三角网格数据的布尔运算方法及其系统
CN102800119B (zh) * 2012-06-13 2014-08-13 天脉聚源(北京)传媒科技有限公司 一种三维曲线的动画展示方法和装置
CN103345771B (zh) * 2013-06-28 2016-08-10 中国科学技术大学 一种基于建模的图像高效渲染方法
US9305370B2 (en) 2013-07-31 2016-04-05 Qualcomm Incorporated Graphical rendering with implicit surfaces
US10242493B2 (en) * 2014-06-30 2019-03-26 Intel Corporation Method and apparatus for filtered coarse pixel shading
CN104063903B (zh) * 2014-07-08 2016-09-14 清华大学 三维实体模型的四面体网格生成方法和装置
WO2017193013A1 (en) * 2016-05-06 2017-11-09 Zhang, Yunbo Determining manufacturable models
ES2812176T3 (es) * 2016-05-24 2021-03-16 E Ink Corp Método para representar imágenes en color
KR102787157B1 (ko) * 2016-12-07 2025-03-26 삼성전자주식회사 셀프 구조 분석을 이용한 구조 잡음 감소 방법 및 장치
JP6708117B2 (ja) * 2016-12-26 2020-06-10 カシオ計算機株式会社 図形描画装置、図形描画方法、サーバ装置、プログラム、及びプログラムを送信する方法
US10373365B2 (en) 2017-04-10 2019-08-06 Intel Corporation Topology shader technology
US10706554B2 (en) * 2017-04-14 2020-07-07 Adobe Inc. Three-dimensional segmentation of digital models utilizing soft classification geometric tuning
CN110235182A (zh) * 2017-09-07 2019-09-13 西门子产品生命周期管理软件公司 用于轻量精确3d视觉格式的系统和方法
US10388045B2 (en) * 2018-01-04 2019-08-20 Adobe Inc. Generating a triangle mesh for an image represented by curves
CN108665538A (zh) * 2018-05-18 2018-10-16 天津流形科技有限责任公司 一种三维模型拟合方法、装置、计算机设备及介质
CN109949420B (zh) * 2019-02-15 2023-03-14 山东师范大学 适用于GPU的Delaunay三角剖分网格细化方法、GPU及系统
JP7333801B2 (ja) * 2021-03-18 2023-08-25 Ｍｈｉｎｓエンジニアリング株式会社 データ変換プログラム、データ変換方法及びデータ変換装置
CN113920275B (zh) * 2021-09-30 2023-04-04 广州极飞科技股份有限公司 三角网格构建方法、装置、电子设备及可读存储介质
CN113888720A (zh) * 2021-10-26 2022-01-04 清华大学 一种基于细分算法的空间曲面编织网格的生成方法
CN114359527B (zh) * 2021-12-31 2024-06-21 广东三维家信息科技有限公司 一种图形数据的三角化处理方法及系统
CN115359209B (zh) * 2022-07-14 2024-01-19 安徽九韶信息科技有限公司 图像处理的装置和方法
CN118964409B (zh) * 2024-10-17 2024-12-20 山东省科学院海洋仪器仪表研究所 提高移动计算平台高分辨率海岸线数据库显示速度的方法

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6525727B1 (en) 1999-10-29 2003-02-25 Intel Corporation Rendering 3D surfaces through limit surface projections
US20040263516A1 (en) 2003-06-30 2004-12-30 Microsoft Corporation Hardware-accelerated anti-aliased graphics

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TW335466B (en) 1995-02-28 1998-07-01 Hitachi Ltd Data processor and shade processor
US6100893A (en) * 1997-05-23 2000-08-08 Light Sciences Limited Partnership Constructing solid models using implicit functions defining connectivity relationships among layers of an object to be modeled
US6285372B1 (en) * 1998-05-08 2001-09-04 Lawrence C. Cowsar Multiresolution adaptive parameterization of surfaces
US6300958B1 (en) 1998-07-17 2001-10-09 T-Surf Corp. Global constrained parameterization of triangulated surfaces
US6356263B2 (en) * 1999-01-27 2002-03-12 Viewpoint Corporation Adaptive subdivision of mesh models
US6462738B1 (en) * 1999-04-26 2002-10-08 Spatial Technology, Inc. Curved surface reconstruction
WO2002089066A1 (en) 2001-04-26 2002-11-07 Koninklijke Philips Electronics N.V. Approximating an implicit surface
US6975317B2 (en) 2002-03-12 2005-12-13 Sun Microsystems, Inc. Method for reduction of possible renderable graphics primitive shapes for rasterization
KR100819960B1 (ko) 2002-11-06 2008-04-07 지오메트릭 인포매틱스 인코퍼레이티드 등각 구조에 의한 기하학적 표면의 분석 방법
US7194125B2 (en) 2002-12-13 2007-03-20 Mitsubishi Electric Research Laboratories, Inc. System and method for interactively rendering objects with surface light fields and view-dependent opacity
KR100506822B1 (ko) 2003-11-08 2005-08-10 엘지전자 주식회사 3차원 다각형의 화면 표시방법

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6525727B1 (en) 1999-10-29 2003-02-25 Intel Corporation Rendering 3D surfaces through limit surface projections
US20040263516A1 (en) 2003-06-30 2004-12-30 Microsoft Corporation Hardware-accelerated anti-aliased graphics

Also Published As

Publication number Publication date
WO2007005537A3 (en) 2007-04-12
CN101189600A (zh) 2008-05-28
EP1899854B1 (en) 2017-10-11
WO2007005537A2 (en) 2007-01-11
EP1899854A2 (en) 2008-03-19
EP1899854A4 (en) 2011-07-13
KR20080022551A (ko) 2008-03-11
US20070002043A1 (en) 2007-01-04
CN100583084C (zh) 2010-01-20
US7408548B2 (en) 2008-08-05

Similar Documents

Publication Publication Date Title
KR101265810B1 (ko) 프로시저 기하 개체의 삼각화
EP1074946B1 (en) Detail-directed hierarchical distance fields for object modelling
Sud et al. DiFi: Fast 3D distance field computation using graphics hardware
Jones The production of volume data from triangular meshes using voxelisation
US7289119B2 (en) Statistical rendering acceleration
EP1074947B1 (en) Sculpturing objects using detail-directed hierarchical distance fields
US6483518B1 (en) Representing a color gamut with a hierarchical distance field
US20100271369A1 (en) Curved surface rendering system and method
KR20050086463A (ko) 다해상도 표면 분석을 위해 도메인 분해를 수행하는 시스템및 방법
Michikawa et al. Multiresolution interpolation meshes
CN102184522A (zh) 顶点数据储存方法、图形处理单元及细化器
Frisken et al. Designing with distance fields
US8605991B2 (en) Method for generating visual hulls for 3D objects as sets of convex polyhedra from polygonal silhouettes
Hurtado et al. Enveloping CAD models for visualization and interaction in XR applications
Kang et al. Mesh-based morphing method for rapid hull form generation
US11605200B2 (en) System for optimizing a 3D mesh
Vyatkin Method of binary search for image elements of functionally defined objects using graphics processing units
Linsen et al. Fan clouds-an alternative to meshes
Glander et al. Techniques for generalizing building geometry of complex virtual 3D city models
US7289117B2 (en) Process for providing a vector image with removed hidden lines
Baer et al. Hardware-accelerated Stippling of Surfaces derived from Medical Volume Data.
Chen An accurate sampling-based method for approximating geometry
Choudhury et al. Generalised curvature estimation using geometric measure theory with a feature detection application in computer vision
US20250191120A1 (en) Motion vector field generation for frame interpolation
Kim et al. Multiresolution model generation with geometry and texture

Legal Events

Date Code Title Description
PA0105 International application

St.27 status event code: A-0-1-A10-A15-nap-PA0105

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

A201 Request for examination
P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

R17-X000 Change to representative recorded

St.27 status event code: A-3-3-R10-R17-oth-X000

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U12-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R13-asn-PN2301

St.27 status event code: A-5-5-R10-R11-asn-PN2301

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R11-asn-PN2301

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R14-asn-PN2301

FPAY Annual fee payment

Payment date: 20160419

Year of fee payment: 4

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

FPAY Annual fee payment

Payment date: 20170420

Year of fee payment: 5

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 5

FPAY Annual fee payment

Payment date: 20180417

Year of fee payment: 6

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 6

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

FPAY Annual fee payment

Payment date: 20190417

Year of fee payment: 7

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 7

R17-X000 Change to representative recorded

St.27 status event code: A-5-5-R10-R17-oth-X000

PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20200514

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20200514