OpenGL game

Triangulation algorithm.

Triangulation algorithm.

Download engine sources (1748kB)


Triangulation algorithm triangulate vertex array to the convex polyhedron

1) Triangulate vertex array.
void K3dTriangulation::Triangulate ( const TVertexArray &_rvVertex )
2) Create polyhedron from input vertex array.
K3dPolyObj *K3dConvex::CreatePolyFromVertexArray(const TVertexArray &_rvVertex)
3) Delete duplicated vertices from vertex array.
void K3dVertexWork::DeleteDupVerts(TVertexArray &_rvVertex)
4) Get arbitrary three vertices from vertex array and create planes.
void K3dConvex::CreateConvexPlane(const K3dVector3Obj &_rkV0,const K3dVector3Obj &_rkV1,const K3dVector3Obj &_rkV2)
5) Compare plane with plane array if plane doesnt`t exists in plane array.
bool K3dPlaneWork::ComparePlane ( K3dPolyPlane *_pPlane,const TPolyPlaneArray &_rPlaneArray )
6) If plane is convex plane then add plane to the plane array. Convex plane has vertices on plane or back side of the plane.
bool K3dConvex::CheckConvexPlane()
7) Create polyhedron edges from vertex array.
void K3dConvex::CreateEdgesFromVertexArray()
8) Create edges from on plane vertices.
void K3dConvex::CreateOnPlaneEdges()
9) Test edge. If all other vertices are on front or back edge plane side, than add edge to the edge array. Edge plane is plane which contains both edge points and it is perpendicular to polyhedron plane.
void K3dConvex::CheckEdge(const K3dVector3Obj *_pV0,const K3dVector3Obj *_pV1)
10) Delete duplicated edges from edge array.
void K3dLineWork::DeleteDupLines(TLineArray &_rvLine)
11) Compare vertex array with all edges and if vertex is equal with one of the edge origin or direction vector add this vertex to the result vertex array.
void K3dConvex::CreateResultVertexArray()
12) Triangulate polyhedron.
void K3dTriangulation::TriangulatePoly ( K3dPolyObj *_pPoly )
13) Triangulate polyhedron planes. Triangulation algorithm is (0,1,2 -> 0,2,3 -> 0,3,4 -> etc.).
void K3dTriangulation::TriangulatePolyPlane ( K3dPolyPlane *_pPolyPlane )
14) Sort vertex array by angle.
void K3dTriangulation::SortVector3ArrayByAngle ( K3dPolyPlane *_pPolyPlane )
15) Calculate vertex array centre.
void K3dVector3Work::CalcVectorArrayCentre(K3dVector3Obj &_rkVCentre, const TVector3Array &_rvVector)
16) Go through all on plane vertices and calculate angle between vertex toward to vertex array centre.
float K3dVector3Work::AngleBetweenVectors ( const K3dVector3Obj &_rkV0,const K3dVector3Obj &_rkV1, const K3dVector3Obj &_rkCentre )
17) Calculate direction vector between first vertex in vertex array and centre of vertex array. Calculate direction vector between next vertex in vertex array and centre of vertex array. Calculate angle between direction vectors.
float K3dVector3Work::AngleBetweenVectors ( const K3dVector3Obj &_rkV0,const K3dVector3Obj &_rkV1 )
18) Normalize vertex vectors and calculate angle between normal vectors.
float K3dVector3Work::AngleBetweenNormals ( const K3dVector3Obj &_rkNormal0,const K3dVector3Obj &_rkNormal1 )
19) Go through all sorted on plane vertices and create new triangle.
void K3dTriangulation::CreateNewTriangle ( K3dVector3Obj *_pV0, K3dVector3Obj *_pV1, K3dVector3Obj *_pV2, const K3dVector3Obj *_pNormal )

home / opengl game

Valid XHTML 1.0 Transitional