Voronoi calculation gives unrelated output

[fcturan20]

1. Hi, I'm using libqhullcpp to generate voronoi diagrams of my input point clouds but I'm having trouble on getting the voronoi vertexes right. I'm using my own renderer and I would like to visualize the outputs of the qhull myself. Here's the code I have to get the voronoi vertices:

std::vector<vec3> CreateVoronoiDiagram(PointCloud* CLOUD) 
{
	orgQhull::Qhull x;
	static constexpr unsigned int Dim = 3;
	double* points = new double[CLOUD->PointCount * Dim];
	for (unsigned int i = 0; i < CLOUD->PointCount; i++) {
		points[(i * 3)] = CLOUD->PointPositions[i].x;
		points[(i * 3) + 1] = CLOUD->PointPositions[i].y;
		points[(i * 3) + 2] = CLOUD->PointPositions[i].z;
	}
	x.runQhull("", Dim, CLOUD->PointCount, points, "v o Qz");                                                                   
	bool isLower;
	int VertexCount;
	x.prepareVoronoi(&isLower, &VertexCount);
	int voronoiDimension = x.hullDimension() - 1;
	int numfacets = x.facetCount();
	size_t numpoints = x.points().size();

	// Gather Voronoi vertices
	std::vector<std::vector<double> > voronoiVertices;
	std::vector<double> vertexAtInfinity;
	for (int i = 0; i < Dim; ++i) {
		vertexAtInfinity.push_back(qh_INFINITE);
	}
	voronoiVertices.push_back(vertexAtInfinity);
	// for(QhullFacet facet : qhull.facetList())
	orgQhull::QhullLinkedListIterator<orgQhull::QhullFacet> j(x.facetList());
	while (j.hasNext()) {
		orgQhull::QhullFacet facet = j.next();
		if (facet.visitId() && facet.visitId() < numfacets) {
			voronoiVertices.push_back(facet.getCenter().toStdVector());
		}
	}
	std::cout << ("Number of voronoi vertices: " + std::to_string(voronoiVertices.size())) << std::endl;

	//0th voronoi vertex is infinity, so skip that
	vector<vec3> finalVertices;
	finalVertices.resize(voronoiVertices.size() - 1);
	for (unsigned int i = 0; i < finalVertices.size() - 1; i++) {
		finalVertices[i] = vec3(voronoiVertices[i + 1][0], voronoiVertices[i + 1][1], voronoiVertices[i + 2][2]);
	}
	return finalVertices;
}

For example, I'm using a point cloud of hemisphere and this is the result:

2. My main purpose to use voronoi diagram is to calculate power crust shape, so voronoi cell volumes and edges are necessary to me but I wanted to visualize voronoi vertices first. In the end, I couldn't find how to find voronoi edges too so I'd be very grateful for a help on that. But the main issue here is to visualize voronoi vertices, so we can forget about that.

[cbbarber]

Furkan, Can you duplicate the sample using qvoronoi or user_eg3_r.cpp? That may help identify the problem. It also helps to start with a small example where you can work out the result by hand.

The code looks like a fair copy of qvoronoi_o() in user_eg3_r.cpp. You will need to debug the problem. Please let me know if there is something wrong with the sample code in user_eg3_r.cpp.

[cbbarber]

For an individual region, the Voronoi edges are the facets of the convex hull of the Voronoi vertices.
http://www.qhull.org/html/qvoronoi.htm#graphics

See option 'Fv' to retrieve the Voronoi vertices of each Voronoi ridge (in 2-d, an edge). It describes limitations. The edges are not oriented. Please report further limitations that you discover. http://www.qhull.org/html/qh-optf.htm#Fv2

[fcturan20]

Furkan, Can you duplicate the sample using qvoronoi or user_eg3_r.cpp? That may help identify the problem. It also helps to start with a small example where you can work out the result by hand.

The code looks like a fair copy of qvoronoi_o() in user_eg3_r.cpp. You will need to debug the problem. Please let me know if there is something wrong with the sample code in user_eg3_r.cpp.

At final part, I was accessing the wrong z value and I wasn't accessing last element of voronoi vertices. After fixing it, vertices seems more reasonable (Only one of the point clouds still gives bad results but I suppose it's because it's a vertical plane in 3D).

For an individual region, the Voronoi edges are the facets of the convex hull of the Voronoi vertices. http://www.qhull.org/html/qvoronoi.htm#graphics

See option 'Fv' to retrieve the Voronoi vertices of each Voronoi ridge (in 2-d, an edge). It describes limitations. The edges are not oriented. Please report further limitations that you discover. http://www.qhull.org/html/qh-optf.htm#Fv2

As I checked in user_eg3, 'Fv' command is cool but command processor seems a little bit complicated than usual so couldn't find where Voronoi ridge info is stored. Can you help?

[cbbarber]

A vertical plane is a degenerate input to Qhull. Qhull should report an error.

The voronoi ridge information is not stored in Qhull. It is derived via qh_markvoronoi and qh_printvdiagram (io_r.c). Voronoi ridges are not oriented. See 'http://www.qhull.org/html/qh-optf.htm#Fv2' for limitations.