chiralbehaviors / voronoi-3d Goto Github PK

when I run main method in class OrientedFaceInspector,have an error
Exception in thread "main" java.lang.UnsatisfiedLinkError: no J3D in java.library.path

Hi I downloaded this and built and ran it fine. But I played around with it and it failed for some simple types of input, particularly regular grids of points. The crashes stopped when I randomly jiggled the points around a little before giving them to the algorithm.

I boiled this down to a very simple test case: A tetrahedralization of a set of two points, at <0, 0, 0> and <1, 1, 1>, caused the Inspector to crash.

I delved until I found the specific problem: The two input points are perfectly collinear with one of the four far-off points added to bound the entire point set, and the point <1, 1, 1> was being added right atop an edge stretching from <0, 0, 0> to that far-off point. During the ensuing flip, two flat tetrahedra were produced, facing in opposite directions around the axle formed by the newly broken edge. These are supposed to be flipped away. One of them was getting flipped around the "axle", leaving behind it a set of correctly placed, non-degenerate tetrahedra. Eventually it would meet with the other of the two, overlapping it perfectly and also becoming adjacent to it. These two degenerate flat tetrahedra were correctly marked as having TWO neighbor links to one another, because each of them shared two faces with the other (which of course is only possible for flat tetrahedra). They were found not to violate one another's Delaunay conditions, since each one had all its vertices on the surface of the degenerate half-plane "sphere" about the vertices of the other polyhedron--on it, and not inside it. Even if a violation HAD been found, I don't know how any further flips could have removed the two flat tetrahedra. A flip2to3 would only have turned the two flat shapes into three flat shapes.

I don't know what's supposed to happen there. I read the Ledoux paper, "Computing the 3D Voronoi Diagram Robustly: An Easy Explanation", that was referred to in the source code. It covered this case but did not fully explain how flipping the flat tetrahedron around the broken edge was supposed to eventually remove it. The paper just says that the stack-based flipping strategy irons out all degeneracies eventually; it does not say exactly how in every case. Nor could I find any way in which your code was failing to correctly follow the pseudocode presented in the paper.

I gave up and just fixed the bug straightforwardly, by adding code that would detect the case in which two degenerate tetrahedra become double-neighbors with one another and then delete both of them. I thought it through and this seems to capture and correctly fix the problem; I don't think there is anything wrong with it. It may not fix all flipping-related problems of this sort but I think it correctly fixes this one.

I'll paste my added code below.

At the end of OrientedFace.flip2to3() I added some code:

    public Tetrahedron[] flip2to3() {
       ...all the old code except the return statement...

        t0.removeAnyDegenerateTetrahedronPair();
        t1.removeAnyDegenerateTetrahedronPair();
        t2.removeAnyDegenerateTetrahedronPair();

        if (t0.isDeleted())
        	if (t1.isDeleted())
        		if (t2.isDeleted())
        			return new Tetrahedron[]{};
        		else
        			return new Tetrahedron[]{t2};
        	else
        		if (t2.isDeleted())
        			return new Tetrahedron[]{t1};
        		else
        			return new Tetrahedron[]{t1, t2};
        else
        	if (t1.isDeleted())
        		if (t2.isDeleted())
        			return new Tetrahedron[]{t0};
        		else
        			return new Tetrahedron[]{t0, t2};
        	else
        		if (t2.isDeleted())
        			return new Tetrahedron[]{t0, t1};
        		else
        			return new Tetrahedron[]{t0, t1, t2};
    }

In Tetrahedron, I added two functions:

	public void removeAnyDegenerateTetrahedronPair()
	{
		if (nA != null)
		{
			if (nA == nB) { removeDegenerateTetrahedronPair(V.A, V.B, V.C, V.D); return; }
			if (nA == nC) { removeDegenerateTetrahedronPair(V.A, V.C, V.B, V.D); return; }
			if (nA == nD) { removeDegenerateTetrahedronPair(V.A, V.D, V.B, V.C); return; }
		}

		if (nB != null)
		{
			if (nB == nC) { removeDegenerateTetrahedronPair(V.B, V.C, V.A, V.D); return; }
			if (nB == nD) { removeDegenerateTetrahedronPair(V.B, V.D, V.A, V.C); return; }
		}

		if (nC != null)
			if (nC == nD) { removeDegenerateTetrahedronPair(V.C, V.D, V.A, V.B); return; }
	}

	private void removeDegenerateTetrahedronPair(V ve1, V ve2, V vf1, V vf2)
	{
		Tetrahedron nE = getNeighbor(ve1);
		Tetrahedron nF1_that = nE.getNeighbor(getVertex(vf1));
		Tetrahedron nF2_that = nE.getNeighbor(getVertex(vf2));

		patch(vf1, nF1_that, nF1_that.ordinalOf(nE));
		patch(vf2, nF2_that, nF2_that.ordinalOf(nE));

		Vertex e1 = getVertex(ve1);
		Vertex e2 = getVertex(ve2);
		Vertex f1 = getVertex(vf1);
		Vertex f2 = getVertex(vf2);
		
		delete();
		nE.delete();

		e1.freshenAdjacent(nF1_that);
		f2.freshenAdjacent(nF1_that);
		e2.freshenAdjacent(nF2_that);
		f1.freshenAdjacent(nF2_that);
	}

In Vertex, I added one function:

    public void freshenAdjacent(Tetrahedron tetrahedron)
    {
    	if (adjacent == null || adjacent.isDeleted())
    		adjacent = tetrahedron;
    }

I dunno maybe this was all my mistake somehow or maybe nobody will care about it anyway, but oh well I spent a day on it and I may as well publish the result somewhere.