Robustness issue?

[kvdijken]

In most cases where i use QuickHull3D in CHBG (https://github.com/kvdijken/CHBG) QuickHull3D works excellent. In one case however it crashes with this stacktrace:

Exception in thread "main" InternalErrorException: face 1002892 1002889 1002812 1002809: half edge 1002809-1002892 reflected by 1002892-1002923
at Face.checkConsistency(Face.java:403)
at Face.mergeAdjacentFace(Face.java:487)
at QuickHull3D.doAdjacentMerge(QuickHull3D.java:1125)
at QuickHull3D.addPointToHull(QuickHull3D.java:1262)
at QuickHull3D.buildHull(QuickHull3D.java:1287)
at QuickHull3D.build(QuickHull3D.java:490)
at QuickHull3D.build(QuickHull3D.java:461)
at Main.main(Main.java:19)

running from this little test program (note that no triangulation is asked for):

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;

public class Main {

public static void main(String[] args) {
    List<String> lines;
    try {
        // read 1004093 3d points
        lines = Files.readAllLines(Paths.get("coord.txt"));
        double[] points = new double[lines.size()];
        int j = 0;
        for (String line : lines)
            points[j++] = Double.parseDouble(line);

        QuickHull3D hull = new QuickHull3D();
        hull.build(points);

        System.out.println("Vertices:");
        Point3d[] vertices = hull.getVertices();
        for (int i = 0; i < vertices.length; i++) {
            Point3d pnt = vertices[i];
            System.out.println(pnt.x + " " + pnt.y + " " + pnt.z);
        }

        System.out.println("Faces:");
        int[][] faceIndices = hull.getFaces();
        for (int i = 0; i < vertices.length; i++) {
            for (int k = 0; k < faceIndices[i].length; k++) {
                System.out.print(faceIndices[i][k] + " ");
            }
            System.out.println("");
        }
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
}

}

and using the 1004093 coordinates (that makes 3012279 doubles) from the attached coord.txt file

Regards,
Koen van Dijken

coord.txt

[micycle1]

For visibility (for others), my fork of the project introduces robust geometric predicates, which fixes this particular case.

Furthermore the original implementation does not handle inputs when the magnitude of the x/y/z plane differs lots (mixed magnitude coordinates).