은 Direct3D를

Question

나는 C# 및 다이렉트를 사용하여 다각형을 그리려고에 오목 다각형을 그릴 수있는 효율적인 \ 쉬운 방법이 있나요

내가 할 모든 파일에서 포인트의 정렬 된 목록은 내가 그릴 필요 3D 세계에서 평평한 다각형.

점을로드하고 삼각형 팬과 drawuserprimitives를 사용하여 볼록한 모양을 그릴 수 있습니다.

이것은 분명히 다각형이 매우 오목한 경우 잘못된 결과를 가져옵니다.

내가이 문제를 해결할 유일한 사람이라고 상상할 수 없다. (나는 gfx/directx 신참이다. 내 배경은 gui \ windows 응용 프로그램 개발에있다.)

나를 도와 줄 수있는 리소스 \ 튜토리얼 \ 알고리즘을 따르는 사람이 누구를 가리킬 수 있습니까?

Answer 1

Direct3D는 삼각형 만 그릴 수 있습니다 (물론, 선과 점도 그릴 수 있지만, 그 점을 제외하고는). 삼각형보다 더 복잡한 모양을 그리려면 그 모양과 동등한 삼각형을 만져야합니다.

경우에 따라 오목한 다각형 삼각형 문제입니다. 한 묶음의 정점이 주어지면 그대로 유지할 수 있습니다. 가장 간단한 경우 삼각형이 사용하는 꼭지점을 나타내는 삼각형 당 세 개의 인덱스 인 "인덱스 버퍼"를 계산하면됩니다. 그런 다음 정점/인덱스 버퍼에 넣거나 DrawUserPrimitives를 사용하여 그립니다.

간단한 (볼록 또는 오목하지만 자기 교차점 또는 구멍이없는) 다각형을 삼각형 화하기위한 알고리즘은 VTerrain site입니다.

나는 Ratcliff의 코드를 과거에 사용했다. 아주 간단하고 잘 작동합니다. VTerrain에는 죽은 링크가 있습니다. 코드는 here입니다. 그것은 C++입니다. 그러나 C#으로 이식하는 것은 간단해야합니다.

아, 삼각형 팬을 사용하지 마세요. 그것들은 매우 제한적으로 사용되며 비효율적이며 곧 사라질 것입니다 (예 : Direct3D 10이 더 이상 지원하지 않습니다). 그냥 삼각형 목록을 사용하십시오.

Answer 2

삼각 측량은 명백한 해답이지만 견고한 삼각 측량기를 작성하는 것은 어렵습니다. 2 달 동안 낭비하지 않는 한 그것을 시도하지 마십시오.

GPC에 도서관 :

당신에게 도움이 될 코드의 몇 가지가 있습니다.

http://www.cs.cmu.edu/~quake/triangle.html

그리고 주먹 :

http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

또 다른 (또한 삼각형

http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

있다 : 아주 사용하기 쉬운, 그러나 당신이 좋아하지 않을 수는 라이센스입니다 GLU tesselator를 사용하는 것이 좋습니다. DirectX 프로그램의 GLU 라이브러리를로드하여 사용할 수 있습니다. OpenGL 컨텍스트가 필요하지 않으며 모든 Windows 시스템에 사전 설치되어 있습니다. 소스를 원하면 SGI 참조 구현에서 삼각 측량 코드를 해제 할 수 있습니다. 나는 그것을 한 번했고 그것은 단지 두 시간이 걸렸다.

지금까지 삼각 측량의 경우. 다른 방법이 있습니다. 스텐실 트릭을 사용할 수 있습니다.

일반적인 알고리즘은 다음과 같이 진행됩니다

1. 해제 색 -와 깊이 씁니다. 스텐실 쓰기를 활성화하고 스텐실 버퍼를 설정하면 현재 스텐실 값이 반전됩니다. 하나의 스텐실로 충분합니다. 오 - 스텐실 버퍼도 지워 져야합니다.

2. 화면에서 임의의 점을 선택하십시오. 누구나 할 것이다. 이 점을 앵커라고 부르세요.

3. 다각형의 각 모서리에 대해 모서리와 앵커를 만드는 두 개의 정점에서 삼각형을 만듭니다. 그 삼각형을 그립니다.

4. 모든 삼각형을 그렸으면 스텐실 쓰기를 끄고 스텐실 테스트를 켜고 색 쓰기를하고 선택한 색상으로 전체 화면 쿼드를 그립니다. 그러면 볼록 다각형 내부의 픽셀 만 채워집니다.

앵커를 다각형의 중앙에 배치하고 다각형의 경계 상자만큼 큰 사각형을 그리는 것이 좋습니다. 그것은 약간의 fillrate를 저장합니다.

Btw - 스텐실 기법은 자체 교차 폴리곤에도 적용됩니다.

는 스텐실 버퍼를 사용할 수있는 경우 닐스

Answer 3

, 할 어렵지 않을해야 희망이 도움이. 여기서 일반적인 알고리즘이다 :

Clear the stencil buffer to 1. 
Pick an arbitrary vertex v0, probably somewhere near the polygon to reduce floating-point errors. 
For each vertex v[i] of the polygon in clockwise order: 
    let s be the segment v[i]->v[i+1] (where i+1 will wrap to 0 when the last vertex is reached) 
    if v0 is to the "right" of s: 
     draw a triangle defined by s, v[i], v[i+1] that adds 1 to the stencil buffer 
    else 
     draw a triangle defined by s, v[i], v[i+1] that subtracts 1 from the stencil buffer 
end for 
fill the screen with the desired color/texture, testing for stencil buffer values >= 2. 

"S의 오른쪽"저자 I는 V에 [I]과 대향 V [내가 + 1] 서 사람의 관점에서 의미한다. 이것은 크로스 제품을 사용하여 테스트 할 수 있습니다 :

크로스 (V0 - V [I]를, V [I + 1] - V [I])> 0

Answer 4

난 그냥 프로젝트를 위해이 작업을 수행했다 . 가장 간단한 알고리즘은 "귀 클리핑 (Ear Clipping)"입니다. 그것에 대한 훌륭한 논문은 여기에 있습니다 : TriangulationByEarClipping.pdf

저는 약 250 줄의 C++ 코드와 4 시간의 brute force 버전을 구현했습니다. 다른 알고리즘은 성능이 뛰어나지 만 구현하기 쉽고 이해하기 쉽습니다.