leomccormack / convhull_3d Goto Github PK

it cannot work when there exist many duplicate vertices

I have a case where sometimes my incoming points (~1000 points) are on a regularly spaced grid. When this happens the plane_3d function in the main loop of convhull_3d_build (in sub-loop with the comment: "Add faces connecting horizon to the new point") can return wildly varying values for cfi and dfi.

This appears to propagate (probably because I have so many colinear points) and eventually causes the program to fail. This failure is intermittent since, strangely, I can do:

std::vector< ch_vertex > vertices;
int *faceIndices= NULL;
int nFaces;
...
convhull_3d_build( &vertices[0], vertices.size(), &faceIndices, &nFaces); //Succeeds
convhull_3d_build( &vertices[0], vertices.size(), &faceIndices, &nFaces); //Fails
convhull_3d_build( &vertices[0], vertices.size(), &faceIndices, &nFaces); //Succeeds
...

So it's possible that something stranger is going on. This fail, succeed, fail, pattern continues even if I free faceIndices between each run.

EDIT:

Additionally, I can shake up the pattern by running

std::vector< ch_vertex > easy_vertices;
std::vector< ch_vertex > vertices;
int *faceIndices= NULL;
int nFaces;
...
convhull_3d_build(&easy_vertices[0], easy_vertices.size(), &faceIndices, &nFaces); //Succeeds
convhull_3d_build( &vertices[0], vertices.size(), &faceIndices, &nFaces); //Fails
convhull_3d_build( &vertices[0], vertices.size(), &faceIndices, &nFaces); //Succeeds
convhull_3d_build( &vertices[0], vertices.size(), &faceIndices, &nFaces); //Fails
...

where easy_vertices is some collection of points without any co-linear points.

Thanks for your work on this algorithm and for making it available.

Have you considered modifying the implementation to use robust geometric predicates?

The hope would be that it would allow you to avoid the random perturbation of points by CH_NOISE_VAL.

The comments indicate that the perturbation is needed to avoid problems with coincident points. If I guarantee that I do not pass any coincident points to convhull, should it be guaranteed to work? (I.e. is it sensitive to other kinds of degeneracies -- co-linear points, or co-planar points?)

I ran into issue where calling function convhull_3d_build multiple times with the same input causes different results. The bug exist only when used with CONVHULL_3D_USE_SINGLE_PRECISION.

Repro:

#include <stdlib.h>

#define CONVHULL_3D_ENABLE
#define CONVHULL_3D_USE_SINGLE_PRECISION /* optional */
#include "../convhull_3d.h"

int main(int argc, const char * argv[])
{
	ch_vec3 vert[] =
	{
		{  4.243597,  2.029179, -0.815667 },
		{  4.417669,  0.039982, -0.928770 },
		{ -2.428492,  1.198822,  3.519505 },
		{ -2.254420, -0.790374,  3.406402 },
		{  3.153918,  2.029179, -2.492747 },
		{  3.327990,  0.039982, -2.605850 },
		{ -3.518171,  1.198822,  1.842424 },
		{ -3.344099, -0.790374,  1.729321 },
	};

	for (int ii = 0; ii < 10; ++ii)
	{
		printf("%d\n", ii);
		int* indices = NULL;
		int numFaces;
		convhull_3d_build(vert, 8, &indices, &numFaces);
		free(indices);
	}

	return 0;
}

Program hits this assert:

> gcc bug.c -lm -o bug; and ./bug
0
1
2
bug: ../convhull_3d.h:923: convhull_3d_build: Assertion `detA>0.0' failed.

It looks like 6f61a29 changes the output of the test code due to the difference in the random numbers. the committed files haven't been updated in some time (there's something creating a minor accuracy difference in one file before that, but this seems very minor)

I expected that the difference might just be in terms of ordering, but in convhull_airboat.obj the first change looks quite large (in that the first two values stay the same, but the Z value changes radically:

-v 7.711631 -1.639892 -2.027359
+v 7.711631 -1.639892 2.043359

I couldn't find the old value of z ==-2.027359 or anything particularly close to it elsewhere in the new file (there are also many other changes, so tracing all of them is not viable). Intuitively that doesn't seem right, but I tested rnd() and it is producing values in the range 0-1 as I'd expect, and I can't see how it could be affecting values to this degree.

I'm not sure if this needs investigating. It's simple enough to commit the results if they are valid (which would be useful as changes (or not) in the repo can then be used to verify further changes to the codebase), but I didn't want to make a PR for this without raising the issue of the changed values first.

At first, thanks for this simple drop in library.
Works well mostly, but some edge (not very) cases were found.
Sometimes it randomly runs into long or even infinite loop; likely in case of odd points, located precisely on resulting faces
+ using 30-50Mb of memory during this with just a handful of points.
It's simply reproducible with such geometry:

(merging its vertices)

Noticeable things are:

• axially aligned planes
• points are on integer grid (same rotated geometry runs well)
• it's height is just 1unit (using ~100 makes things better) (likely volume proportions matter)
• bug hardening after moving objects to greater coordinates

Further playing around also has shown consistency issue:
this:

randomly turns into this:

while should be this:

Same happens with the first example (losing one or more of vertices), but infinite loop is more probable.

Use specs

• compiling as c++ with gcc under win32 and win64
• precision is double; using float makes named issues to happen way more often; using long double haven't improved the state
• CBLAS is not used
  Trying to tune noise value just shown, that current value is well ballancing in between of these two issues.