Point ordering differs between runs

[GoogleCodeExporter]

What steps will reproduce the problem?

Running any boolean operation. The simplest case was the difference between
two cubes.

What is the expected output? What do you see instead?

Visually, the result is OK and identical between runs. Structurally, the
ordering of the points is different between runs, i.e. a point with a given
position will not always have the same index in the vertices vector. The
ordering of points in a face loop also seems to differ.

What version of the product are you using? On what operating system?

Latest hg version (changeset 45070ee2dab0) on Ubuntu Karmic 32 bit.

Please provide any additional information below.

I am trying to integrate CARVE support into the K-3D modeler. A dashboard
test showing the effect can be found at:
http://www.k-3d.org/cdash/testDetails.php?test=634693&build=3043
In the diff, the points array should correspond exactly to the CARVE
polyhedron vertices vector.

A visual comparison can be seen on my blog:
http://k-3d.org/blogs/barche/2010/01/27/first-carve-boolean-results/

The ordering of components is important in K-3D, due to the pipelined
nature where subsequent steps may depend on the index of selected
components, i.e. "extrude face 3".

Original issue reported on code.google.com by bar...@gmail.com on 27 Jan 2010 at 9:28

[GoogleCodeExporter]

As an interim measure, You can call polyhedron->canonicalize() on the CSG to 
ensure that the vertex and 
face orderings are consistent between runs. This involves sorting, so it's not 
an ideal solution, but it'll get you 
further in your testing.

I agree that ideally the result from successive runs should be the same not 
only spatially but in terms of 
representation and ordering.

There are a number of places where Carve uses stl unordered maps and sets 
containing pointers, and 
obviously this means that the ordering of elements in the collection is 
dependent on the heap environment, 
making this a potentially hard problem to fix.

Original comment by tobias.s...@gmail.com on 27 Jan 2010 at 11:11

• Changed state: Accepted

[GoogleCodeExporter]

Ah, many thanks, that is a big improvement. Only one test with intersecting 
edges is
still failing, details are posted on
http://k-3d.org/blogs/barche/2010/01/27/first-carve-boolean-results/

The canonicalize operation does not seem to be a big performance hit, it is 32 
times
faster than the boolean op itself, so if this can be used to guarantee 
consistency,
that seems fine to me. See
http://www.k-3d.org/cdash/testDetails.php?test=637163&build=3063 for a 
breakdown of
the timings.

I'll experiment some more, one optimization I still have to do is to only 
triangulate
when necessary, i.e. on non-planar faces and faces with holes.

Original comment by bar...@gmail.com on 28 Jan 2010 at 11:29

[GoogleCodeExporter]

For faces with holes, you only need to link the holes to the face loop, which 
is the first step of most triangulation 
algorithms in any case. Are you using the GLU triangulator, or some other 
method?

If you could, it would be useful if you could attach the objects (preferably in 
.ply format, but anything will do) 
that constitute the failing case, and I'll take a look at why canonicalize() 
isn't returning a unique result.

I'm also curious as to what you're using for your testing for k3d. it looks 
like a pretty nice system - is it open 
source?

Original comment by tobias.s...@gmail.com on 29 Jan 2010 at 2:32

[GoogleCodeExporter]

We use the GLU triangulator, the attached archive contains input A and B after
triangulation, as well as two different outputs from K-3D after doing A minus 
B. I
can't reproduce the difference using the intersect command line tool, though.

The tests are part of our CDash dashboard, which is provided by the CMake build
system. It's open source, see http://www.cmake.org/

Original comment by bar...@gmail.com on 29 Jan 2010 at 11:55

Attachments:

• carve_cylinders.tar.gz

[GoogleCodeExporter]

I've made an updated testcase, writing PLY files at different steps using the 
CARVE 
writePLY function, to exclude any K-3D influence. The file contains the inputs 
and 
outputs from two different runs. Inputs are identical, the results show the two 
switched points.

Original comment by bar...@gmail.com on 30 Jan 2010 at 9:47

Attachments:

• ply.tar.gz

[GoogleCodeExporter]

I've taken a further look, including adding some heap randomization code to the 
intersect binary to try and 
trigger differences between runs, and I'm not getting anywhere. The results 
that you have show one of the 
intersection points moving slightly, and I can't see how the determination of 
the intersection points can be order 
dependent.

If you can reliably reproduce a difference in successive runs, could you please 
apply the attached changeset 
(better debug output) and compile with -DCARVE_DEBUG, and send me the debug 
logs for the two cases? The 
changeset should apply cleanly against the current head.

Original comment by tobias.s...@gmail.com on 5 Feb 2010 at 5:16

Attachments:

• changeset.debug

[GoogleCodeExporter]

OK, sorry for the delay, but attached is the output you requested. It contains 
both 
the cylinders testcase and a cubes testcase. In the cubes case, the edge 
linking a 
hole in one of the faces differs between runs (see the screenshots), and the 
GLU 
triangulator was not applied in K-3D before the boolean operation.

Original comment by bar...@gmail.com on 6 Mar 2010 at 10:55

Attachments:

• carve-tests.tar.gz

[GoogleCodeExporter]

Ok, I've reproduced the cube issue. It occurs in the code that links holes back 
into containing faces. I think this 
should be fixable, once I've tracked down the code that causes the problem.

The cylinder problem is more interesting. From the logs, it occurs early on in 
the process, when intersections are 
being formed. It will involve more log delving to work out what exactly differs.

Original comment by tobias.s...@gmail.com on 9 Mar 2010 at 12:26

[GoogleCodeExporter]

I just committed a patch that appears to correct the cube issue. Could you 
please test it and see if it works for 
you? There are also a bunch of changes which are partial commits of the debug 
info changes, so the debug 
changeset above is now invalid. I've attached a new patch that should be 
applied against the current head, in 
case you want to do that.

Original comment by tobias.s...@gmail.com on 10 Mar 2010 at 5:00

Attachments:

• debug.patch

[GoogleCodeExporter]

Thanks, the cube test passes all the time now! There is only an occasional 
failure on 
the cylinders case left.

Original comment by bar...@gmail.com on 11 Mar 2010 at 8:49

[GoogleCodeExporter]

Could you please apply this new patch to the current repository tip? It gives 
me a bit more information around 
the site of the problem.

Original comment by tobias.s...@gmail.com on 12 Mar 2010 at 3:13

Attachments:

• debug.patch

[GoogleCodeExporter]

OK, the new output is attached!

Original comment by bar...@gmail.com on 18 Mar 2010 at 10:23

Attachments:

• carve_ply_test.tar.gz

[GoogleCodeExporter]

Ok, I think this is what's happening:

I suspect you're doing two CSG operations, but only calling canonicalize() on 
the result. If I'm right, then the 
differing order of vertices in the intermediate result means that rounding 
errors cause edge-edge intersections 
to occur in slightly different places in the result, leading to the differences 
you observe.

I will try to make the intersection code more robust to vertex ordering 
changes, but if the above matches reality, 
could you please try calling canonicalize() on intermediate results to see if 
it fixes the problem?

Original comment by tobias.s...@gmail.com on 19 Mar 2010 at 5:37

[GoogleCodeExporter]

The test is just a boolean between the files I sent with comment 5, so no 
multiple 
ops. If I canonicalize both inputs before the op, I get a segfault, strangely 
enough. 
See attached file for the log and the backtrace.

Original comment by bar...@gmail.com on 19 Mar 2010 at 10:34

Attachments:

• carve-k3d-segfault.txt

[GoogleCodeExporter]

int main(int argc, char **argv) { 
TestScene *scene = new TestScene(argc, argv, 3);

   carve::input::PolyhedronData data;

   data.addVertex(carve::geom::VECTOR(1,1,1));
   data.addVertex(carve::geom::VECTOR(-1,1,1));
   data.addVertex(carve::geom::VECTOR(-1,-1,1));
   data.addVertex(carve::geom::VECTOR(1,-1,1));
   data.addVertex(carve::geom::VECTOR(1,1,-1));
   data.addVertex(carve::geom::VECTOR(-1,1,-1));
   data.addVertex(carve::geom::VECTOR(-1,-1,-1));
   data.addVertex(carve::geom::VECTOR(1,-1,-1));

   data.addFace(0,1,2,3);
   data.addFace(7,6,5,4);
   data.addFace(0,4,5,1);
   data.addFace(1,5,6,2);
   data.addFace(2,6,7,3);
   data.addFace(3,7,4,0);

   carve::poly::Polyhedron *p = data.create();
   glNewList(scene->draw_list_base + 1, GL_COMPILE);
   drawPolyhedron(p, .4, .6, .8, 1.0, false);
   glEndList();

   scene->run();
   delete scene;

return 0;

i can't get the cube,why?

Original comment by perryfei@gmail.com on 27 Aug 2013 at 6:52