Comments (15)
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 [email protected]
on 27 Jan 2010 at 11:11
- Changed state: Accepted
from carve.
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 [email protected]
on 28 Jan 2010 at 11:29
from carve.
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 [email protected]
on 29 Jan 2010 at 2:32
from carve.
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 [email protected]
on 29 Jan 2010 at 11:55
Attachments:
from carve.
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 [email protected]
on 30 Jan 2010 at 9:47
Attachments:
from carve.
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 [email protected]
on 5 Feb 2010 at 5:16
Attachments:
from carve.
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 [email protected]
on 6 Mar 2010 at 10:55
Attachments:
from carve.
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 [email protected]
on 9 Mar 2010 at 12:26
from carve.
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 [email protected]
on 10 Mar 2010 at 5:00
Attachments:
from carve.
Thanks, the cube test passes all the time now! There is only an occasional
failure on
the cylinders case left.
Original comment by [email protected]
on 11 Mar 2010 at 8:49
from carve.
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 [email protected]
on 12 Mar 2010 at 3:13
Attachments:
from carve.
OK, the new output is attached!
Original comment by [email protected]
on 18 Mar 2010 at 10:23
Attachments:
from carve.
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 [email protected]
on 19 Mar 2010 at 5:37
from carve.
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 [email protected]
on 19 Mar 2010 at 10:34
Attachments:
from carve.
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 [email protected]
on 27 Aug 2013 at 6:52
from carve.
Related Issues (20)
- Dynamic flip edges to remove flat triangles
- Patch for /include/carve/mesh_simplify.hpp
- carve 1.4.0 - error building with gcc4.4.6
- Patch for /lib/triangle_intersection.cpp
- Build error due to undefined symbols on linux using freeglut when using CARVE_WITH_GUI=ON
- Bug in mergeCoplanarFaces?
- Another case with error message 'UNEXPECTED face loop with size!=1'
- Wrong results by A_MINUS_B
- Any good method to imprint B's surface polygons onto A?
- How to build with VS2012? HOT 3
- Another case Carve can't work
- Another case Carve can't work
- Surface mesh simplification by Carve crashed
- Another boolean operation error case HOT 1
- Patch for /include/carve/mesh_impl.hpp
- Another boolean operation error case-unclosed result
- Redefinition errors - Can't compile - CMAKE and VS2013
- Another boolean operation error case-unclosed result
- Another case Carve calculate wrong result
- Patch for /lib/convex_hull.cpp
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from carve.