Voronoi 3D and degenerate faces

I’ve been experimenting with Voronoi and DynamicMesh, so I wrote the following code:

void AGeneratedDestructibleActor::ApplyVoronoi()
{
	// Sites
	TArray<FVector> Sites;
	Sites.Add({50.f, 50.f, 25.f});
	
	// Bounding box for Voronoi
	FVector InMin {0.f, 0.f, 0.f};
	FVector InMax {100.f, 100.f, 100.f};

	FBox Bounds {InMin,InMax};
	
	TArray<FVoronoiCellInfo> AllCells{};
	
	// Calculate Voronoi Diagram
	Diagram.Initialize(Sites, Bounds, 0.0, 0.0);
	Diagram.ComputeAllCells(AllCells);

	int CurrentCellIdx{0};
	int NumVerticesPrevCells{0};
	FDynamicMesh3 NewMesh{};

	for (auto CellInfo : AllCells)
	{
		UE_LOG(LogTemp, Warning, TEXT("Cella-%d"), CurrentCellIdx);

		int CurrentVertexIdx = 0;
		
		for (auto CellVertex : CellInfo.Vertices)
		{
			UE_LOG(LogTemp, Warning, TEXT("\tVertex %d: (%.2f, %.2f, %.2f)"), CurrentVertexIdx, CellVertex.X, CellVertex.Y, CellVertex.Z);

			// TODO: some vertices can be duplicated
			NewMesh.AppendVertex({CellVertex.X, CellVertex.Y, CellVertex.Z});
			CurrentVertexIdx++;
		}
		
		
		int faceIdx = 0;
		
		UE_LOG(LogTemp, Warning, TEXT("\tNum Face indices %d"), CellInfo.Faces.Num());

		for (int firstVertexIdx = 0; firstVertexIdx <= CellInfo.Faces.Num()-3; firstVertexIdx += 3)
		{
			// vertex indices of the current face
			int vIdx0{CellInfo.Faces[firstVertexIdx]};
			int vIdx1{CellInfo.Faces[firstVertexIdx+1]};
			int vIdx2{CellInfo.Faces[firstVertexIdx+2]};
			// each cell has vertex indices zero-based, but the same vertex in newMesh is shifted by the number of vertices in the previous cells
			int vIdx0_seq{vIdx0 + NumVerticesPrevCells};
			int vIdx1_seq{vIdx1 + NumVerticesPrevCells};
			int vIdx2_seq{vIdx2 + NumVerticesPrevCells};
			
			UE_LOG(LogTemp, Warning, TEXT("\tFace %d/%d: [%d, %d, %d]"), faceIdx, (CellInfo.Faces.Num()/3)-1, vIdx0_seq, vIdx1_seq, vIdx2_seq);

			NewMesh.AppendTriangle(vIdx0_seq, vIdx1_seq, vIdx2_seq);
			faceIdx++;
		}
		CurrentCellIdx++;
		NumVerticesPrevCells += CurrentVertexIdx;
	}

	this->DynamicMeshComponent->GetMesh()->Clear();
	this->DynamicMeshComponent->SetMesh(FDynamicMesh3{NewMesh});
}

It computes the Voronoi diagram and use the faces and vertices of each Voronoi cell to populate the DynamicMesh, so I can see the result in the editor. With only one site, I expect the result to be a cube. However, I’m encountering an issue where the generated cube has a hole (a missing triangle). I’ve used debugging and logging and found out that the mesh has some degenerate triangles.

Warning      LogTemp                   Cella-0
Warning      LogTemp                   	Vertex 0: (0.00, 0.00, 0.00)
Warning      LogTemp                   	Vertex 1: (100.00, 0.00, 0.00)
Warning      LogTemp                   	Vertex 2: (0.00, 100.00, 0.00)
Warning      LogTemp                   	Vertex 3: (100.00, 100.00, 0.00)
Warning      LogTemp                   	Vertex 4: (0.00, 0.00, 100.00)
Warning      LogTemp                   	Vertex 5: (100.00, 0.00, 100.00)
Warning      LogTemp                   	Vertex 6: (0.00, 100.00, 100.00)
Warning      LogTemp                   	Vertex 7: (100.00, 100.00, 100.00)
Warning      LogTemp                   	Num Face indices 30
Warning      LogTemp                   	Face 0/9: [4, 1, 3]
Warning      LogTemp                   	Face 1/9: [2, 0, 4]
Warning      LogTemp                   	Face 2/9: [1, 5, 7]
Warning      LogTemp                   	Face 3/9: [3, 4, 1]
Warning      LogTemp                   	Face 4/9: [0, 4, 5]
Warning      LogTemp                   	Face 5/9: [4, 2, 6]
Warning      LogTemp                   	Face 6/9: [4, 0, 4]
Warning      LogTemp                   	Face 7/9: [2, 3, 7]
Warning      LogTemp                   	Face 8/9: [6, 4, 4]
Warning      LogTemp                   	Face 9/9: [6, 7, 5]

(see Face 6/9 and Face 8/9)
Why does this happen? Any help or insights would be greatly appreciated.

Note that when I add one more site, every Voronoi cell exhibits degenerate 7th and 9th faces.

2 Likes