Direct3d에서 오목 다각형을 그리는 효율적이고 쉬운 방법이 있습니까?

StackOverflow https://stackoverflow.com/questions/91202

  •  01-07-2019
  •  | 
  •  

문제

C#과 directx를 사용하여 다각형을 그리려고 합니다.

내가 얻는 것은 파일에서 정렬된 점 목록뿐이며 3D 세계에서 평면 다각형을 그려야 합니다.

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

이는 다각형이 매우 오목한 경우(그럴 수도 있음) 분명히 잘못된 결과를 초래합니다.

나는 이 문제와 씨름하는 유일한 사람이라고는 상상할 수 없습니다(나는 gfx/directx 초보자입니다. 내 배경은 gui\windows 응용 프로그램 개발에 있습니다).

누구든지 나에게 도움이 될 수 있는 간단한 리소스\튜토리얼\알고리즘을 알려줄 수 있습니까?

도움이 되었습니까?

해결책

Direct3D는 삼각형만 그릴 수 있습니다(물론 선과 점도 그릴 수 있지만 이는 점과는 다릅니다).따라서 삼각형보다 더 복잡한 모양을 그리려면 해당 모양과 동일한 접촉 삼각형을 많이 그려야 합니다.

귀하의 경우에는 오목 다각형 삼각측량 문제입니다.여러 정점이 주어지면 그대로 유지할 수 있으며 "인덱스 버퍼"(가장 간단한 경우 삼각형이 어떤 정점을 사용하는지 알려주는 삼각형당 3개의 인덱스)를 계산하면 됩니다.그런 다음 정점/인덱스 버퍼에 넣거나 DrawUserPrimitives를 사용하여 그립니다.

단순한(볼록하거나 오목하지만 자체교차나 구멍이 없는) 다각형을 삼각측량하기 위한 일부 알고리즘은 다음과 같습니다. V지형 사이트.

나는 과거에 Ratcliff의 코드를 사용한 적이 있습니다.매우 간단하고 잘 작동합니다.VTerrain에는 데드 링크가 있습니다.코드를 찾을 수 있습니다 여기.C++이지만 이를 C#으로 포팅하는 것은 간단합니다.

아, 그리고 삼각형 팬을 사용하지 마세요.사용이 매우 제한적이고 비효율적이며 곧 사라질 예정입니다(예:Direct3D 10에서는 더 이상 지원하지 않습니다.)그냥 삼각형 목록을 사용하세요.

다른 팁

삼각측량은 분명한 답이지만 견고한 삼각측량기를 작성하는 것은 어렵습니다.두 달 동안 낭비할 시간이 없다면 시도조차 하지 마세요.

도움이 될 수 있는 몇 가지 코드가 있습니다.

GPC 라이브러리.사용하기는 매우 쉽지만 라이센스가 마음에 들지 않을 수 있습니다.

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

삼각형도 있습니다:

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

그리고 주먹:

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

또 다른 (그리고 내가 선호하는) 옵션은 GLU 테셀레이터를 사용하는 것입니다.DirectX 프로그램에서 GLU 라이브러리를 로드하고 사용할 수 있습니다.이를 사용하기 위해 OpenGL 컨텍스트가 필요하지 않으며 모든 Windows 시스템에 사전 설치되어 있습니다.소스를 원할 경우 SGI 참조 구현에서 삼각측량 코드를 해제할 수 있습니다.한 번 해봤는데 두 시간 정도 걸렸어요.

지금까지는 삼각측량을 위한 것이었습니다.다른 방법도 있습니다:스텐실 트릭을 사용할 수 있습니다.

일반적인 알고리즘은 다음과 같습니다.

  1. 색상 및 깊이 쓰기를 비활성화합니다.스텐실 쓰기를 활성화하고 현재 스텐실 값을 반전시키도록 스텐실 버퍼를 설정합니다.스텐실 1비트면 충분합니다.아 - 스텐실 버퍼도 지워져야 합니다.

  2. 화면에서 임의의 지점을 선택합니다.누구나 할 것입니다.이 지점을 앵커라고 부르세요.

  3. 다각형의 각 가장자리에 대해 가장자리와 앵커를 구성하는 두 꼭지점에서 삼각형을 만듭니다.그 삼각형을 그려보세요.

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

앵커를 다각형 중앙에 배치하고 다각형의 경계 상자만큼 큰 직사각형을 그리는 것이 좋습니다.그러면 약간의 채우기 속도가 절약됩니다.

그런데 스텐실 기술은 자체 교차하는 다각형에도 적용됩니다.

도움이되기를 바랍니다

스텐실 버퍼를 사용할 수 있다면 어렵지 않을 것입니다.일반적인 알고리즘은 다음과 같습니다.

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의 권리"란 v[i] 위에 서 있고 v[i+1]을 바라보는 사람의 관점을 의미합니다.이는 교차곱을 사용하여 테스트할 수 있습니다.

cross(v0 - v[i], v[i+1] - v[i]) > 0

프로젝트 때문에 이 일을 해야 했어요.제가 찾은 가장 간단한 알고리즘은 "Ear Clipping"입니다.이에 대한 훌륭한 논문은 여기에 있습니다: TriangulationByEarClipping.pdf

무차별 대입 버전을 구현하는 데 약 250줄의 C++ 코드와 4시간이 걸렸습니다.다른 알고리즘의 성능이 더 좋지만 이는 구현하고 이해하기가 간단했습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top