Output polyhedron differs on repeated runs

[GoogleCodeExporter]

Sorry, forgot to attach the examples.  Found two more examples (aa.obj and
bb.obj) that have the same problem using UNION, except sometimes it also hangs.

Original issue reported on code.google.com by ken.l.hu...@gmail.com on 6 Jun 2009 at 3:01

Attachments:

• error.tgz

[GoogleCodeExporter]

Thanks for these test cases. I've just committed a change that appears to fix 
both. Could you please check?

Also, as a general rule it's a good idea to use the rescaler to maximise the 
number of available bits of precision.

Original comment by tobias.s...@gmail.com on 9 Jun 2009 at 1:23

• Changed state: Started

[GoogleCodeExporter]

Put the code back in blender to test and still get random hangs when using 
quads and
triangulate.

What exactly does the rescale do?  What params does it need?

Original comment by ken.l.hu...@gmail.com on 9 Jun 2009 at 7:12

[GoogleCodeExporter]

Can you get me another example, possibly?

The rescaler shifts and scales coordinates to be as close as possible to the 
unit cube without losing any 
information. The transformation, followed by the inverse transformation on any 
points in the model results in 
the same point, however in the transformed values, uninformative high bits in 
the floating point value are 
shifted off (as far as possible) and replaced with low bits that improve the 
precision of the calculation.

The rescaler just needs to know the bounds of the objects taking part in the 
CSG operation:

        carve::poly::Polyhedron *l, *r; // these are the two CSG inputs.
        carve::geom3d::Vector min, max; // these need to be set to the bounds of l and r.

        carve::rescale::rescale scaler(min.x, min.y, min.z, max.x, max.y, max.z);

        carve::rescale::fwd fwd_r(scaler);
        carve::rescale::rev rev_r(scaler);

        l->transform(fwd_r);
        r->transform(fwd_r);

        carve::poly::Polyhedron *result = csg.compute(l, r, op, NULL, classify_type);

        result->transform(rev_r);

Original comment by tobias.s...@gmail.com on 9 Jun 2009 at 11:56

[GoogleCodeExporter]

Here's the files I tested with; they should be the same as ones I posted before 
but
I'm not completely sure.  It doesn't always hang when running intersect from the
command line, but maybe 20% of the time.

intersect --triangulate --obj a.obj A_MINUS_B b.obj

Original comment by ken.l.hu...@gmail.com on 10 Jun 2009 at 11:04

Attachments:

• error2.tar.bz2

[GoogleCodeExporter]

Issue 8 has been merged into this issue.

Original comment by tobias.s...@gmail.com on 11 Jun 2009 at 4:29

[GoogleCodeExporter]

I can't reproduce this. Over 1000 runs with that command line, I get no hangs.

Could you please get a stack trace so that I can see where the hang is 
occurring? Is this a 32 or a 64 bit 
executable?

Original comment by tobias.s...@gmail.com on 11 Jun 2009 at 4:36

[GoogleCodeExporter]

This is the 32-bit version, compiled with CFLAGS=CXXFLAGS="-g -O0" using gcc 
(Ubuntu
4.3.3-5ubuntu4) 4.3.3.

Backtrace below. Seems it's caught in an infinite loop, so printed some of the 
values
being examined.

Program received signal SIGINT, Interrupt.
0xb7fcb28d in carve::geom::operator==<2u> (a=@0x966ad30, b=@0x966ad50)
    at ../include/carve/geom.hpp:259
259       for (unsigned i = 0; i < ndim; ++i) { if (a[i] != b[i]) return false; 
}
(gdb) bt
#0  0xb7fcb28d in carve::geom::operator==<2u> (a=@0x9removeDegeneracies66ad30,
b=@0x966ad50)
    at ../include/carve/geom.hpp:259
#1  0xb8075cb7 in removeDegeneracies (begin=@0xbfad23dc, result=@0xbfad2448)
    at triangulator.cpp:299
#2  0xb8077476 in carve::triangulate::triangulate (poly=@0xbfad2454, 
    result=@0xbfad2448) at triangulator.cpp:651
#3  0x08063a36 in carve::csg::CarveTriangulator::processOutputFace (
    this=0x9669900, faces=@0xbfad252c, orig=0x966d040, flipped=true)
    at ../include/carve/csg_triangulator.hpp:46
#4  0xb8008174 in carve::csg::CSG::Hooks::processOutputFace (this=0xbfad2a08, 
    faces=@0xbfad252c, orig_face=0x966d040, flipped=true) at intersect.cpp:301
#5  0xb7fd1897 in REV (this=0x966c7c0, orig_face=0x966d040, 
    vertices=@0x9677434, normal=
            {<carve::geom::base<3u>> = {{v = {0, 0, 1}, {x = 0, y = 0, z = 1}}}, <No
data fields>}, poly_a=false, face_class=carve::csg::FACE_IN, 
    hooks=@0xbfad2a08) at csg_collector.cpp:90
#6  0xb7fd1a0b in collect (this=0x966c7c0, orig_face=0x966d040, 
    vertices=@0x9677434, normal=
            {<carve::geom::base<3u>> = {{v = {-0, -0, -1}, {x = -0, y = -0, z =
-1}}}, <No data fields>}, poly_a=false, face_class=carve::csg::FACE_IN, 
    hooks=@0xbfad2a08) at csg_collector.cpp:285
#7  0xb7fd0ac1 in collect (this=0x966c7c0, grp=0x966a978, hooks=@0xbfad2a08)
    at csg_collector.cpp:150
---Type <return> to continue, or q <return> to quit---
#8  0xb803ba21 in 
performClassifyEasyFaceGroups<carve::csg::<unnamed>::FaceMaker1>
(group=@0xbfad288c, poly_a=0x966c380, vclass=@0xbfad2858, 
    classifier=@0xbfad2690, collector=@0x966c7c0, hooks=@0xbfad2a08)
    at intersect_classify_common_impl.hpp:146
#9  0xb803bd06 in classifyEasy (this=0xbfad27b0, a_loops_grouped=@0xbfad2894, 
    b_loops_grouped=@0xbfad288c, vclass=@0xbfad2858, poly_a=0x966c380, 
    poly_b=0x966c7d8) at intersect_classify_group.cpp:131
#10 0xb803c2b9 in
performClassifyFaceGroups<carve::csg::<unnamed>::ClassifyFaceGroups>
(a_loops_grouped=@0xbfad2894, b_loops_grouped=@0xbfad288c, 
    vclass=@0xbfad2858, poly_a=0x966c380, poly_b=0x966c7d8, 
    classifier=@0xbfad27b0, collector=@0x966c7c0, hooks=@0xbfad2a08)
    at intersect_classify_common_impl.hpp:273
#11 0xb803c879 in carve::csg::CSG::classifyFaceGroups (this=0xbfad29d8, 
    shared_edges=@0xbfad2808, vclass=@0xbfad2858, poly_a=0x966c380, 
    a_loops_grouped=@0xbfad2894, a_edge_map=@0xbfad2830, poly_b=0x966c7d8, 
    b_loops_grouped=@0xbfad288c, b_edge_map=@0xbfad281c, collector=@0x966c7c0)
    at intersect_classify_group.cpp:195
#12 0xb800df34 in carve::csg::CSG::compute (this=0xbfad29d8, a=0x966c380, 
    b=0x966c7d8, collector=@0x966c7c0, shared_edges_ptr=0x0, 
    classify_type=carve::csg::CSG::CLASSIFY_NORMAL) at intersect.cpp:1312
#13 0xb800e25b in carve::csg::CSG::compute (this=0xbfad29d8, a=0x966c380, 
    b=0x966c7d8, op=carve::csg::CSG::A_MINUS_B, shared_edges=0x0, 
    classify_type=carve::csg::CSG::CLASSIFY_NORMAL) at intersect.cpp:1347
---Type <return> to continue, or q <return> to quit---
#14 0x08063e04 in carve::csg::CSG_OPNode::evalUnscaled (this=0x966bb90, 
    is_temp=@0xbfad298f, csg=@0xbfad29d8) at ../include/carve/tree.hpp:270
#15 0x080583fc in carve::csg::CSG_OPNode::eval (this=0x966bb90, 
    is_temp=@0xbfad298f, csg=@0xbfad29d8) at ../include/carve/tree.hpp:290
#16 0x08063ee2 in carve::csg::CSG_TreeNode::eval (this=0x966bb90, 
    csg=@0xbfad29d8) at ../include/carve/tree.hpp:46
#17 0x0805732f in main (argc=6, argv=0xbfad2b74) at intersect.cpp:498
(gdb) p v->p
$3 = (const P2 &) @0x966ad30: {<carve::geom::base<2u>> = {{v = {-1, 
        0.2150430000000001}, {x = -1, 
        y = 0.2150430000000001}}}, <No data fields>}
(gdb) p v->next->p
$4 = (const P2 &) @0x966ad40: {<carve::geom::base<2u>> = {{v = {
        -0.15983542579849999, 0.21504300000000001}, {x = -0.15983542579849999, 
        y = 0.21504300000000001}}}, <No data fields>}
(gdb) p v->next->next->p
$5 = (const P2 &) @0x966ad50: {<carve::geom::base<2u>> = {{v = {-1, 
        0.2150430000000001}, {x = -1, 
        y = 0.2150430000000001}}}, <No data fields>}
(gdb) p v->convex
$8 = true
(gdb) p v->next->next->convex
$9 = true
(gdb) n
291     do {
(gdb) 
292       if (v->p == v->next->p) {
(gdb) 
299       } else if (v->p == v->next->next->p) {
(gdb) 
300         if (v->next->p == v->next->next->p ||
(gdb) 
291     do {

Original comment by ken.l.hu...@gmail.com on 11 Jun 2009 at 5:05

[GoogleCodeExporter]

Looking at that trace, I suspect that you've been using the tarball rather than 
the mercurial repository? I haven't 
been updating the tarball, as that seems like the wrong thing to do, in 
general, without bumping the revision 
number.

I've uploaded a tarball of the current development head, just in case this is 
what's happening.

Original comment by tobias.s...@gmail.com on 11 Jun 2009 at 5:27

[GoogleCodeExporter]

Could be; I used the tarball then ran the hg clone and hg update, since I had 
no luck
in generating a configuration file from just the hg clone by itself.  I'll gran 
a new
tarball and try it.

Original comment by ken.l.hu...@gmail.com on 11 Jun 2009 at 5:30

[GoogleCodeExporter]

Ok, don't get the hangs anymore.  Seems to be fixed in head.  BTW, get an error
trying to compile test_spacetree.cpp; can't find carve/spacetree.hpp.  I 
deleted the
cpp file and then it works. 

Original comment by ken.l.hu...@gmail.com on 11 Jun 2009 at 5:02