Open GoogleCodeExporter opened 9 years ago
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
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
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
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:
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:
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:
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:
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
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:
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
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:
OK, the new output is attached!
Original comment by bar...@gmail.com
on 18 Mar 2010 at 10:23
Attachments:
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
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:
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
Original issue reported on code.google.com by
bar...@gmail.com
on 27 Jan 2010 at 9:28