chiralbehaviors / voronoi-3d Goto Github PK
View Code? Open in Web Editor NEWIncremental 3D Delaunay Tetrahedralization
Incremental 3D Delaunay Tetrahedralization
A library for incrementally constructing 3 dimensional Delaunay tetrahedralizations. The Voronoi network - the dual of the Delaunay - can be extracted from the system. A graphical user interface for inspecting the voronoi/delaunay network is also provided. This library is licensed under the AGPL v3.0 and is built with Maven 2.x. To build, cd into the root directory and do: mvn clean install Depends on https://github.com/Hellblazer/Utils, so you'll have to check that out and make it until I get off my lazy ass and publish these in a maven repo
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.