diff options
Diffstat (limited to 'extern/carve/include')
| -rw-r--r-- | extern/carve/include/carve/aabb.hpp | 6 | ||||
| -rw-r--r-- | extern/carve/include/carve/aabb_impl.hpp | 17 | ||||
| -rw-r--r-- | extern/carve/include/carve/csg.hpp | 16 | ||||
| -rw-r--r-- | extern/carve/include/carve/debug_hooks.hpp | 4 | ||||
| -rw-r--r-- | extern/carve/include/carve/face_impl.hpp | 4 | ||||
| -rw-r--r-- | extern/carve/include/carve/geom.hpp | 4 | ||||
| -rw-r--r-- | extern/carve/include/carve/geom2d.hpp | 4 | ||||
| -rw-r--r-- | extern/carve/include/carve/geom3d.hpp | 77 | ||||
| -rw-r--r-- | extern/carve/include/carve/geom_impl.hpp | 47 | ||||
| -rw-r--r-- | extern/carve/include/carve/interpolator.hpp | 309 | ||||
| -rw-r--r-- | extern/carve/include/carve/mesh.hpp | 1 | ||||
| -rw-r--r-- | extern/carve/include/carve/mesh_impl.hpp | 93 | ||||
| -rw-r--r-- | extern/carve/include/carve/polyhedron_impl.hpp | 33 | ||||
| -rw-r--r-- | extern/carve/include/carve/polyline_decl.hpp | 4 | ||||
| -rw-r--r-- | extern/carve/include/carve/polyline_impl.hpp | 6 | ||||
| -rw-r--r-- | extern/carve/include/carve/rtree.hpp | 12 | ||||
| -rwxr-xr-x | extern/carve/include/carve/win32.h | 2 |
17 files changed, 467 insertions, 172 deletions
diff --git a/extern/carve/include/carve/aabb.hpp b/extern/carve/include/carve/aabb.hpp index 20ee028aa45..c2fb2f6075f 100644 --- a/extern/carve/include/carve/aabb.hpp +++ b/extern/carve/include/carve/aabb.hpp @@ -120,6 +120,12 @@ namespace carve { template<unsigned ndim> std::ostream &operator<<(std::ostream &o, const aabb<ndim> &a); + template<unsigned ndim> + double distance2(const aabb<3> &a, const vector<ndim> &v); + + template<unsigned ndim> + double distance(const aabb<3> &a, const vector<ndim> &v); + template<unsigned ndim, typename obj_t> diff --git a/extern/carve/include/carve/aabb_impl.hpp b/extern/carve/include/carve/aabb_impl.hpp index ccdddef160b..9564885ea2a 100644 --- a/extern/carve/include/carve/aabb_impl.hpp +++ b/extern/carve/include/carve/aabb_impl.hpp @@ -316,6 +316,23 @@ namespace carve { return o; } + template<unsigned ndim> + double distance2(const aabb<3> &a, const vector<ndim> &v) { + double d2 = 0.0; + for (unsigned i = 0; i < ndim; ++i) { + double d = ::fabs(v.v[i] - a.pos.v[i]) - a.extent.v[i]; + if (d > 0.0) { + d2 += d * d; + } + } + return d2; + } + + template<unsigned ndim> + double distance(const aabb<3> &a, const vector<ndim> &v) { + return ::sqrt(distance2(a, v)); + } + template<> inline bool aabb<3>::intersects(const ray<3> &ray) const { vector<3> t = pos - ray.v; diff --git a/extern/carve/include/carve/csg.hpp b/extern/carve/include/carve/csg.hpp index b098cd86cef..92b03a4c33f 100644 --- a/extern/carve/include/carve/csg.hpp +++ b/extern/carve/include/carve/csg.hpp @@ -87,6 +87,11 @@ namespace carve { const meshset_t::face_t * /* orig_face */, bool /* flipped */) { } + virtual void edgeDivision(const meshset_t::edge_t * /* orig_edge */, + size_t /* orig_edge_idx */, + const meshset_t::vertex_t * /* v1 */, + const meshset_t::vertex_t * /* v2 */) { + } virtual ~Hook() { } @@ -103,11 +108,13 @@ namespace carve { RESULT_FACE_HOOK = 0, PROCESS_OUTPUT_FACE_HOOK = 1, INTERSECTION_VERTEX_HOOK = 2, - HOOK_MAX = 3, + EDGE_DIVISION_HOOK = 3, + HOOK_MAX = 4, RESULT_FACE_BIT = 0x0001, PROCESS_OUTPUT_FACE_BIT = 0x0002, - INTERSECTION_VERTEX_BIT = 0x0004 + INTERSECTION_VERTEX_BIT = 0x0004, + EDGE_DIVISION_BIT = 0x0008 }; std::vector<std::list<Hook *> > hooks; @@ -125,6 +132,11 @@ namespace carve { const meshset_t::face_t *orig_face, bool flipped); + void edgeDivision(const meshset_t::edge_t *orig_edge, + size_t orig_edge_idx, + const meshset_t::vertex_t *v1, + const meshset_t::vertex_t *v2); + void registerHook(Hook *hook, unsigned hook_bits); void unregisterHook(Hook *hook); diff --git a/extern/carve/include/carve/debug_hooks.hpp b/extern/carve/include/carve/debug_hooks.hpp index 9ef7fc83573..d942a823371 100644 --- a/extern/carve/include/carve/debug_hooks.hpp +++ b/extern/carve/include/carve/debug_hooks.hpp @@ -35,11 +35,11 @@ void map_histogram(std::ostream &out, const MAP &map) { } hist[n]++; } - int total = map.size(); + int total = (int)map.size(); std::string bar(50, '*'); for (size_t i = 0; i < hist.size(); i++) { if (hist[i] > 0) { - out << std::setw(5) << i << " : " << std::setw(5) << hist[i] << " " << bar.substr(50 - hist[i] * 50 / total) << std::endl; + out << std::setw(5) << i << " : " << std::setw(5) << hist[i] << " " << bar.substr((size_t)(50 - hist[i] * 50 / total)) << std::endl; } } } diff --git a/extern/carve/include/carve/face_impl.hpp b/extern/carve/include/carve/face_impl.hpp index 771ba761111..e1a9ed306a2 100644 --- a/extern/carve/include/carve/face_impl.hpp +++ b/extern/carve/include/carve/face_impl.hpp @@ -42,7 +42,9 @@ namespace carve { template<unsigned ndim> template<typename iter_t> Face<ndim> *Face<ndim>::init(const Face<ndim> *base, iter_t vbegin, iter_t vend, bool flipped) { - vertices.reserve(std::distance(vbegin, vend)); + CARVE_ASSERT(vbegin < vend); + + vertices.reserve((size_t)std::distance(vbegin, vend)); if (flipped) { std::reverse_copy(vbegin, vend, std::back_inserter(vertices)); diff --git a/extern/carve/include/carve/geom.hpp b/extern/carve/include/carve/geom.hpp index 421083e3e3c..360f14f2607 100644 --- a/extern/carve/include/carve/geom.hpp +++ b/extern/carve/include/carve/geom.hpp @@ -138,6 +138,9 @@ namespace carve { template<unsigned ndim, typename iter_t, typename adapt_t> void bounds(iter_t begin, iter_t end, adapt_t adapt, vector<ndim> &min, vector<ndim> &max); + template<unsigned ndim, typename iter_t> + void centroid(iter_t begin, iter_t end, vector<ndim> &c); + template<unsigned ndim, typename iter_t, typename adapt_t> void centroid(iter_t begin, iter_t end, adapt_t adapt, vector<ndim> &c); @@ -300,6 +303,7 @@ namespace carve { aabb<ndim> getAABB() const; + tri() { } tri(vector_t _v[3]); tri(const vector_t &a, const vector_t &b, const vector_t &c); diff --git a/extern/carve/include/carve/geom2d.hpp b/extern/carve/include/carve/geom2d.hpp index 731e22919b6..ef10b68725e 100644 --- a/extern/carve/include/carve/geom2d.hpp +++ b/extern/carve/include/carve/geom2d.hpp @@ -347,7 +347,7 @@ namespace carve { PolyInclusionInfo pointInPoly(const std::vector<T> &points, adapt_t adapt, const P2 &p) { P2Vector::size_type l = points.size(); for (unsigned i = 0; i < l; i++) { - if (equal(adapt(points[i]), p)) return PolyInclusionInfo(POINT_VERTEX, i); + if (equal(adapt(points[i]), p)) return PolyInclusionInfo(POINT_VERTEX, (int)i); } for (unsigned i = 0; i < l; i++) { @@ -358,7 +358,7 @@ namespace carve { std::min(adapt(points[i]).y, adapt(points[j]).y) - EPSILON < p.y && std::max(adapt(points[i]).y, adapt(points[j]).y) + EPSILON > p.y && distance2(carve::geom::rayThrough(adapt(points[i]), adapt(points[j])), p) < EPSILON2) { - return PolyInclusionInfo(POINT_EDGE, i); + return PolyInclusionInfo(POINT_EDGE, (int)i); } } diff --git a/extern/carve/include/carve/geom3d.hpp b/extern/carve/include/carve/geom3d.hpp index faeb565b922..fda43cc2b88 100644 --- a/extern/carve/include/carve/geom3d.hpp +++ b/extern/carve/include/carve/geom3d.hpp @@ -45,56 +45,57 @@ namespace carve { template<typename iter_t, typename adapt_t> bool fitPlane(iter_t begin, iter_t end, adapt_t adapt, Plane &plane) { - Vector centroid; - carve::geom::centroid(begin, end, adapt, centroid); - iter_t i; + std::vector<Vector> p; + for (; begin != end; ++begin) { + p.push_back(adapt(*begin)); + } - Vector n = Vector::ZERO(); - Vector v; - Vector p1, p2, p3, c1, c2; - if (begin == end) return false; + if (p.size() < 3) { + return false; + } - i = begin; - p1 = c1 = adapt(*i); if (++i == end) return false; - p2 = c2 = adapt(*i); if (++i == end) return false; + Vector C; + carve::geom::centroid(p.begin(), p.end(), C); -#if defined(CARVE_DEBUG) - size_t N = 2; -#endif - do { - p3 = adapt(*i); - v = cross(p3 - p2, p1 - p2); - if (v.v[largestAxis(v)]) v.negate(); - n += v; - p1 = p2; p2 = p3; -#if defined(CARVE_DEBUG) - ++N; -#endif - } while (++i != end); + Vector n; + + if (p.size() == 3) { + n = cross(p[1] - p[0], p[2] - p[0]); + } else { + const size_t N = p.size(); + + n = cross(p[N-1] - C, p[0] - C); + if (n < Vector::ZERO()) n.negate(); + for (size_t i = 1; i < p.size(); ++i) { + Vector v = cross(p[i] - C, p[i-1] - C); + if (v < Vector::ZERO()) v.negate(); + n += v; + } + } - p1 = p2; p2 = p3; p3 = c1; - v = cross(p3 - p2, p1 - p2); - if (v.v[largestAxis(v)]) v.negate(); - n += v; + double l = n.length(); - p1 = p2; p2 = p3; p3 = c2; - v = cross(p3 - p2, p1 - p2); - if (v.v[largestAxis(v)]) v.negate(); - n += v; + if (l == 0.0) { + n.x = 1.0; + n.y = 0.0; + n.z = 0.0; + } else { + n.normalize(); + } - n.normalize(); plane.N = n; - plane.d = -dot(n, centroid); + plane.d = -dot(n, C); + #if defined(CARVE_DEBUG) - if (N > 3) { - std::cerr << "N = " << N << " fitted distance:"; - for (i = begin; i != end; ++i) { - Vector p = adapt(*i); - std::cerr << " {" << p << "} " << distance(plane, p); + if (p.size() > 3) { + std::cerr << "N-gon with " << p.size() << " vertices: fitted distance:"; + for (size_t i = 0; i < N; ++i) { + std::cerr << " {" << p[i] << "} " << distance(plane, p[i]); } std::cerr << std::endl; } #endif + return true; } diff --git a/extern/carve/include/carve/geom_impl.hpp b/extern/carve/include/carve/geom_impl.hpp index 044655b6c07..c4b6a9d5491 100644 --- a/extern/carve/include/carve/geom_impl.hpp +++ b/extern/carve/include/carve/geom_impl.hpp @@ -26,13 +26,26 @@ namespace carve { template<unsigned ndim> double vector<ndim>::length2() const { return dot(*this, *this); } + template<unsigned ndim> double vector<ndim>::length() const { return sqrt(dot(*this, *this)); } template<unsigned ndim> - vector<ndim> &vector<ndim>::normalize() { *this /= length(); return *this; } + vector<ndim> &vector<ndim>::normalize() { +#if defined(CARVE_DEBUG) + CARVE_ASSERT(length() > 0.0); +#endif + *this /= length(); + return *this; + } + template<unsigned ndim> - vector<ndim> vector<ndim>::normalized() const { return *this / length(); } + vector<ndim> vector<ndim>::normalized() const { +#if defined(CARVE_DEBUG) + CARVE_ASSERT(length() > 0.0); +#endif + return *this / length(); + } template<unsigned ndim> bool vector<ndim>::exactlyZero() const { @@ -289,24 +302,24 @@ namespace carve { template<unsigned ndim> int smallestAxis(const vector<ndim> &a) { - int x = 0; - double y = fabs(a[0]); + int idx = 0; + double lo = fabs(a[0]); for (unsigned i = 1; i < ndim; ++i) { - double z = fabs(a[i]); - if (z <= y) { y = z; x = i; } + double val = fabs(a[i]); + if (val <= lo) { lo = val; idx = (int)i; } } - return x; + return idx; } template<unsigned ndim> int largestAxis(const vector<ndim> &a) { - int x = 0; - double y = fabs(a[0]); + int idx = 0; + double hi = fabs(a[0]); for (unsigned i = 1; i < ndim; ++i) { - double z = fabs(a[i]); - if (z > y) { y = z; x = i; } + double val = fabs(a[i]); + if (val > hi) { hi = val; idx = (int)i; } } - return x; + return idx; } template<unsigned ndim> @@ -365,11 +378,19 @@ namespace carve { } } + template<unsigned ndim, typename iter_t> + void centroid(iter_t begin, iter_t end, vector<ndim> &c) { + c.setZero(); + int n = 0; + for (; begin != end; ++begin, ++n) { c += *begin; } + c /= double(n); + } + template<unsigned ndim, typename iter_t, typename adapt_t> void centroid(iter_t begin, iter_t end, adapt_t adapt, vector<ndim> &c) { c.setZero(); int n = 0; - while (begin != end) { c += adapt(*begin++); ++n; } + for (; begin != end; ++begin, ++n) { c += adapt(*begin); } c /= double(n); } diff --git a/extern/carve/include/carve/interpolator.hpp b/extern/carve/include/carve/interpolator.hpp index e1555105435..f8162e52f39 100644 --- a/extern/carve/include/carve/interpolator.hpp +++ b/extern/carve/include/carve/interpolator.hpp @@ -89,6 +89,8 @@ namespace carve { return result; } + + template<typename iter_t, typename adapt_t, typename val_t, @@ -113,6 +115,8 @@ namespace carve { return mod(v); } + + template<typename iter_t, typename adapt_t, typename val_t> @@ -124,6 +128,8 @@ namespace carve { double y) { return interp(begin, end, adapt, vals, x, y, identity_t<val_t>()); } + + template<typename vertex_t, typename adapt_t, @@ -138,6 +144,8 @@ namespace carve { return interp(poly.begin(), poly.end(), adapt, vals, x, y, mod); } + + template<typename vertex_t, typename adapt_t, typename val_t> @@ -149,6 +157,8 @@ namespace carve { return interp(poly.begin(), poly.end(), adapt, vals, x, y, identity_t<val_t>()); } + + template<typename val_t, typename mod_t> val_t interp(const std::vector<carve::geom2d::P2> &poly, @@ -166,6 +176,8 @@ namespace carve { return mod(v); } + + template<typename val_t> val_t interp(const std::vector<carve::geom2d::P2> &poly, const std::vector<val_t> &vals, @@ -174,90 +186,122 @@ namespace carve { return interp(poly, vals, x, y, identity_t<val_t>()); } + + class Interpolator { public: - virtual void interpolate(const carve::mesh::MeshSet<3>::face_t *new_face, - const carve::mesh::MeshSet<3>::face_t *orig_face, - bool flipped) =0; - - Interpolator() { - } + typedef carve::mesh::MeshSet<3> meshset_t; - virtual ~Interpolator() { - } + protected: + friend struct Hook; - class Hook : public carve::csg::CSG::Hook { + struct Hook : public carve::csg::CSG::Hook { + const carve::csg::CSG &csg; Interpolator *interpolator; - public: - virtual void resultFace(const carve::mesh::MeshSet<3>::face_t *new_face, - const carve::mesh::MeshSet<3>::face_t *orig_face, + + virtual unsigned hookBits() const { + return carve::csg::CSG::Hooks::RESULT_FACE_BIT; + } + virtual void resultFace(const meshset_t::face_t *new_face, + const meshset_t::face_t *orig_face, bool flipped) { - interpolator->interpolate(new_face, orig_face, flipped); + interpolator->resultFace(csg, new_face, orig_face, flipped); + } + virtual void processOutputFace(std::vector<carve::mesh::MeshSet<3>::face_t *> &new_faces, + const meshset_t::face_t *orig_face, + bool flipped) { + interpolator->processOutputFace(csg, new_faces, orig_face, flipped); + } + virtual void edgeDivision(const meshset_t::edge_t *orig_edge, + size_t orig_edge_idx, + const meshset_t::vertex_t *v1, + const meshset_t::vertex_t *v2) { + interpolator->edgeDivision(csg, orig_edge, orig_edge_idx, v1, v2); } - Hook(Interpolator *_interpolator) : interpolator(_interpolator) { + Hook(Interpolator *_interpolator, const carve::csg::CSG &_csg) : interpolator(_interpolator), csg(_csg) { } virtual ~Hook() { } }; + virtual Hook *makeHook(carve::csg::CSG &csg) { + return new Hook(this, csg); + } + + virtual void resultFace(const carve::csg::CSG &csg, + const meshset_t::face_t *new_face, + const meshset_t::face_t *orig_face, + bool flipped) { + } + + virtual void processOutputFace(const carve::csg::CSG &csg, + std::vector<carve::mesh::MeshSet<3>::face_t *> &new_faces, + const meshset_t::face_t *orig_face, + bool flipped) { + } + + virtual void edgeDivision(const carve::csg::CSG &csg, + const meshset_t::edge_t *orig_edge, + size_t orig_edge_idx, + const meshset_t::vertex_t *v1, + const meshset_t::vertex_t *v2) { + } + + public: + + Interpolator() { + } + + virtual ~Interpolator() { + } + void installHooks(carve::csg::CSG &csg) { - csg.hooks.registerHook(new Hook(this), carve::csg::CSG::Hooks::RESULT_FACE_BIT); + Hook *hook = makeHook(csg); + csg.hooks.registerHook(hook, hook->hookBits()); } }; + + template<typename attr_t> class FaceVertexAttr : public Interpolator { + public: + typedef std::pair<const meshset_t::face_t *, unsigned> key_t; protected: - struct fv_hash { - size_t operator()(const std::pair<const carve::mesh::MeshSet<3>::face_t *, unsigned> &v) const { + struct key_hash { + size_t operator()(const key_t &v) const { return size_t(v.first) ^ size_t(v.second); } }; - typedef std::unordered_map<const carve::mesh::MeshSet<3>::vertex_t *, attr_t> attrvmap_t; - typedef std::unordered_map<std::pair<const carve::mesh::MeshSet<3>::face_t *, unsigned>, attr_t, fv_hash> attrmap_t; + typedef std::unordered_map<const meshset_t::vertex_t *, attr_t> attrvmap_t; + typedef std::unordered_map<key_t, attr_t, key_hash> attrmap_t; attrmap_t attrs; - public: - bool hasAttribute(const carve::mesh::MeshSet<3>::face_t *f, unsigned v) { - return attrs.find(std::make_pair(f, v)) != attrs.end(); - } - - attr_t getAttribute(const carve::mesh::MeshSet<3>::face_t *f, unsigned v, const attr_t &def = attr_t()) { - typename attrmap_t::const_iterator fv = attrs.find(std::make_pair(f, v)); - if (fv != attrs.end()) { - return (*fv).second; - } - return def; - } - - void setAttribute(const carve::mesh::MeshSet<3>::face_t *f, unsigned v, const attr_t &attr) { - attrs[std::make_pair(f, v)] = attr; - } - - virtual void interpolate(const carve::mesh::MeshSet<3>::face_t *new_face, - const carve::mesh::MeshSet<3>::face_t *orig_face, - bool flipped) { + virtual void resultFace(const carve::csg::CSG &csg, + const meshset_t::face_t *new_face, + const meshset_t::face_t *orig_face, + bool flipped) { std::vector<attr_t> vertex_attrs; attrvmap_t base_attrs; vertex_attrs.reserve(orig_face->nVertices()); - for (carve::mesh::MeshSet<3>::face_t::const_edge_iter_t e = orig_face->begin(); e != orig_face->end(); ++e) { - typename attrmap_t::const_iterator a = attrs.find(std::make_pair(orig_face, e.idx())); + for (meshset_t::face_t::const_edge_iter_t e = orig_face->begin(); e != orig_face->end(); ++e) { + typename attrmap_t::const_iterator a = attrs.find(key_t(orig_face, e.idx())); if (a == attrs.end()) return; vertex_attrs.push_back((*a).second); base_attrs[e->vert] = vertex_attrs.back(); } - for (carve::mesh::MeshSet<3>::face_t::const_edge_iter_t e = new_face->begin(); e != new_face->end(); ++e) { - const carve::mesh::MeshSet<3>::vertex_t *vertex = e->vert; + for (meshset_t::face_t::const_edge_iter_t e = new_face->begin(); e != new_face->end(); ++e) { + const meshset_t::vertex_t *vertex = e->vert; typename attrvmap_t::const_iterator b = base_attrs.find(vertex); if (b != base_attrs.end()) { - attrs[std::make_pair(new_face, e.idx())] = (*b).second; + attrs[key_t(new_face, e.idx())] = (*b).second; } else { carve::geom2d::P2 p = orig_face->project(e->vert->v); attr_t attr = interp(orig_face->begin(), @@ -266,11 +310,28 @@ namespace carve { vertex_attrs, p.x, p.y); - attrs[std::make_pair(new_face, e.idx())] = attr; + attrs[key_t(new_face, e.idx())] = attr; } } } + public: + bool hasAttribute(const meshset_t::face_t *f, unsigned v) { + return attrs.find(key_t(f, v)) != attrs.end(); + } + + attr_t getAttribute(const meshset_t::face_t *f, unsigned v, const attr_t &def = attr_t()) { + typename attrmap_t::const_iterator fv = attrs.find(key_t(f, v)); + if (fv != attrs.end()) { + return (*fv).second; + } + return def; + } + + void setAttribute(const meshset_t::face_t *f, unsigned v, const attr_t &attr) { + attrs[key_t(f, v)] = attr; + } + FaceVertexAttr() : Interpolator() { } @@ -280,44 +341,165 @@ namespace carve { }; + template<typename attr_t> - class FaceAttr : public Interpolator { + class FaceEdgeAttr : public Interpolator { + public: + typedef std::pair<const meshset_t::face_t *, unsigned> key_t; protected: - struct f_hash { - size_t operator()(const carve::mesh::MeshSet<3>::face_t * const &f) const { - return size_t(f); + typedef std::pair<const meshset_t::vertex_t *, const meshset_t::vertex_t *> vpair_t; + + struct key_hash { + size_t operator()(const key_t &v) const { + return size_t(v.first) ^ size_t(v.second); + } + }; + struct vpair_hash { + size_t operator()(const vpair_t &v) const { + return size_t(v.first) ^ size_t(v.second); } }; - typedef std::unordered_map<const carve::mesh::MeshSet<3>::face_t *, attr_t, f_hash> attrmap_t; + typedef std::unordered_map<key_t, attr_t, key_hash> attrmap_t; + typedef std::unordered_map<vpair_t, key_t, vpair_hash> edgedivmap_t; attrmap_t attrs; + edgedivmap_t edgediv; + + struct Hook : public Interpolator::Hook { + public: + virtual unsigned hookBits() const { + return + carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT | + carve::csg::CSG::Hooks::EDGE_DIVISION_BIT; + } + Hook(Interpolator *_interpolator, const carve::csg::CSG &_csg) : Interpolator::Hook(_interpolator, _csg) { + } + virtual ~Hook() { + } + }; + + virtual Interpolator::Hook *makeHook(carve::csg::CSG &csg) { + return new Hook(this, csg); + } + + virtual void edgeDivision(const carve::csg::CSG &csg, + const meshset_t::edge_t *orig_edge, + size_t orig_edge_idx, + const meshset_t::vertex_t *v1, + const meshset_t::vertex_t *v2) { + key_t k(orig_edge->face, orig_edge_idx); + typename attrmap_t::const_iterator attr_i = attrs.find(k); + if (attr_i == attrs.end()) return; + edgediv[vpair_t(v1, v2)] = k; + } + + virtual void processOutputFace(const carve::csg::CSG &csg, + std::vector<carve::mesh::MeshSet<3>::face_t *> &new_faces, + const meshset_t::face_t *orig_face, + bool flipped) { + edgedivmap_t undiv; + + for (meshset_t::face_t::const_edge_iter_t e = orig_face->begin(); e != orig_face->end(); ++e) { + key_t k(orig_face, e.idx()); + typename attrmap_t::const_iterator attr_i = attrs.find(k); + if (attr_i == attrs.end()) { + continue; + } else { + undiv[vpair_t(e->v1(), e->v2())] = k; + } + } + + for (size_t fnum = 0; fnum < new_faces.size(); ++fnum) { + const carve::mesh::MeshSet<3>::face_t *new_face = new_faces[fnum]; + for (meshset_t::face_t::const_edge_iter_t e = new_face->begin(); e != new_face->end(); ++e) { + key_t k(new_face, e.idx()); + + vpair_t vp; + if (!flipped) { + vp = vpair_t(e->v1(), e->v2()); + } else { + vp = vpair_t(e->v2(), e->v1()); + } + typename edgedivmap_t::const_iterator vp_i; + if ((vp_i = undiv.find(vp)) != undiv.end()) { + attrs[k] = attrs[vp_i->second]; + } else if ((vp_i = edgediv.find(vp)) != edgediv.end()) { + attrs[k] = attrs[vp_i->second]; + } + } + } + } public: - bool hasAttribute(const carve::mesh::MeshSet<3>::face_t *f) { - return attrs.find(f) != attrs.end(); + + bool hasAttribute(const meshset_t::face_t *f, unsigned e) { + return attrs.find(std::make_pair(f, e)) != attrs.end(); } - attr_t getAttribute(const carve::mesh::MeshSet<3>::face_t *f, const attr_t &def = attr_t()) { - typename attrmap_t::const_iterator i = attrs.find(f); - if (i != attrs.end()) { - return (*i).second; + attr_t getAttribute(const meshset_t::face_t *f, unsigned e, const attr_t &def = attr_t()) { + typename attrmap_t::const_iterator fv = attrs.find(std::make_pair(f, e)); + if (fv != attrs.end()) { + return (*fv).second; } return def; } - void setAttribute(const carve::mesh::MeshSet<3>::face_t *f, const attr_t &attr) { - attrs[f] = attr; + void setAttribute(const meshset_t::face_t *f, unsigned e, const attr_t &attr) { + attrs[std::make_pair(f, e)] = attr; + } + + FaceEdgeAttr() : Interpolator() { + } + + virtual ~FaceEdgeAttr() { + } + }; + + + + template<typename attr_t> + class FaceAttr : public Interpolator { + public: + typedef const meshset_t::face_t *key_t; + + protected: + struct key_hash { + size_t operator()(const key_t &f) const { + return size_t(f); + } + }; + + typedef std::unordered_map<key_t, attr_t, key_hash> attrmap_t; + + attrmap_t attrs; + + virtual void resultFace(const carve::csg::CSG &csg, + const meshset_t::face_t *new_face, + const meshset_t::face_t *orig_face, + bool flipped) { + typename attrmap_t::const_iterator i = attrs.find(key_t(orig_face)); + if (i != attrs.end()) { + attrs[key_t(new_face)] = (*i).second; + } + } + + public: + bool hasAttribute(const meshset_t::face_t *f) { + return attrs.find(key_t(f)) != attrs.end(); } - virtual void interpolate(const carve::mesh::MeshSet<3>::face_t *new_face, - const carve::mesh::MeshSet<3>::face_t *orig_face, - bool flipped) { - typename attrmap_t::const_iterator i = attrs.find(orig_face); + attr_t getAttribute(const meshset_t::face_t *f, const attr_t &def = attr_t()) { + typename attrmap_t::const_iterator i = attrs.find(key_t(f)); if (i != attrs.end()) { - attrs[new_face] = (*i).second; + return (*i).second; } + return def; + } + + void setAttribute(const meshset_t::face_t *f, const attr_t &attr) { + attrs[key_t(f)] = attr; } FaceAttr() : Interpolator() { @@ -325,7 +507,6 @@ namespace carve { virtual ~FaceAttr() { } - }; } diff --git a/extern/carve/include/carve/mesh.hpp b/extern/carve/include/carve/mesh.hpp index 202337b64d3..115f4bf10f4 100644 --- a/extern/carve/include/carve/mesh.hpp +++ b/extern/carve/include/carve/mesh.hpp @@ -688,6 +688,7 @@ namespace carve { void cacheEdges(); + int orientationAtVertex(edge_t *); void calcOrientation(); void recalc() { diff --git a/extern/carve/include/carve/mesh_impl.hpp b/extern/carve/include/carve/mesh_impl.hpp index 56fb6788b62..0748f394219 100644 --- a/extern/carve/include/carve/mesh_impl.hpp +++ b/extern/carve/include/carve/mesh_impl.hpp @@ -606,33 +606,78 @@ namespace carve { template<unsigned ndim> + int Mesh<ndim>::orientationAtVertex(edge_t *e_base) { +#if defined(CARVE_DEBUG) + std::cerr << "warning: vertex orientation not defined for ndim=" << ndim << std::endl; +#endif + return 0; + } + + + + template<> + inline int Mesh<3>::orientationAtVertex(edge_t *e_base) { + edge_t *e = e_base; + vertex_t::vector_t v_base = e->v1()->v; + std::vector<vertex_t::vector_t> v_edge; + + if (v_edge.size() < 3) { + return 0; + } + + do { + v_edge.push_back(e->v2()->v); + e = e->rev->next; + } while (e != e_base); + + const size_t N = v_edge.size(); + + for (size_t i = 0; i < N; ++i) { + size_t j = (i + 1) % N; + + double o_hi = 0.0; + double o_lo = 0.0; + + for (size_t k = (j + 1) % N; k != i; k = (k + 1) % N) { + double o = carve::geom3d::orient3d(v_edge[i], v_base, v_edge[j], v_edge[k]); + o_hi = std::max(o_hi, o); + o_lo = std::max(o_lo, o); + } + + if (o_lo >= 0.0) return +1; + if (o_hi <= 0.0) return -1; + } + + return 0; + } + + + + template<unsigned ndim> void Mesh<ndim>::calcOrientation() { if (open_edges.size() || !closed_edges.size()) { is_negative = false; - } else { - edge_t *emin = closed_edges[0]; - if (emin->rev->v1()->v < emin->v1()->v) emin = emin->rev; - for (size_t i = 1; i < closed_edges.size(); ++i) { - if (closed_edges[i]->v1()->v < emin->v1()->v) emin = closed_edges[i]; - if (closed_edges[i]->rev->v1()->v < emin->v1()->v) emin = closed_edges[i]->rev; - } + return; + } - std::vector<face_t *> min_faces; - edge_t *e = emin; - do { - min_faces.push_back(e->face); - CARVE_ASSERT(e->rev != NULL); - e = e->rev->next; - CARVE_ASSERT(e->v1() == emin->v1()); - CARVE_ASSERT(e->v1()->v <= e->v2()->v); - } while (e != emin); - - double max_abs_x = 0.0; - for (size_t f = 0; f < min_faces.size(); ++f) { - if (fabs(min_faces[f]->plane.N.x) > fabs(max_abs_x)) max_abs_x = min_faces[f]->plane.N.x; - } - is_negative = max_abs_x > 0.0; + edge_t *emin = closed_edges[0]; + + if (emin->rev->v1()->v < emin->v1()->v) emin = emin->rev; + + for (size_t i = 1; i < closed_edges.size(); ++i) { + if (closed_edges[i]->v1()->v < emin->v1()->v) emin = closed_edges[i]; + if (closed_edges[i]->rev->v1()->v < emin->v1()->v) emin = closed_edges[i]->rev; + } + + int orientation = orientationAtVertex(emin); + +#if defined(CARVE_DEBUG) + if (orientation == 0) { + std::cerr << "warning: could not determine orientation for mesh " << this << std::endl; } +#endif + + is_negative = orientation == -1; } @@ -747,7 +792,9 @@ namespace carve { std::vector<vertex_t *> v; size_t p = 0; for (size_t i = 0; i < n_faces; ++i) { - const size_t N = face_indices[p++]; + CARVE_ASSERT(face_indices[p] > 1); + + const size_t N = (size_t)face_indices[p++]; v.clear(); v.reserve(N); for (size_t j = 0; j < N; ++j) { diff --git a/extern/carve/include/carve/polyhedron_impl.hpp b/extern/carve/include/carve/polyhedron_impl.hpp index de61324140d..0aadc56aefe 100644 --- a/extern/carve/include/carve/polyhedron_impl.hpp +++ b/extern/carve/include/carve/polyhedron_impl.hpp @@ -59,18 +59,18 @@ namespace carve { for (size_t i = 0; i != N; ++i) { vout.push_back(*vptr[i]); - vmap[vertexToIndex_fast(vptr[i])] = &vout[i]; + vmap[(size_t)vertexToIndex_fast(vptr[i])] = &vout[i]; } for (size_t i = 0; i < faces.size(); ++i) { face_t &f = faces[i]; for (size_t j = 0; j < f.nVertices(); ++j) { - f.vertex(j) = vmap[vertexToIndex_fast(f.vertex(j))]; + f.vertex(j) = vmap[(size_t)vertexToIndex_fast(f.vertex(j))]; } } for (size_t i = 0; i < edges.size(); ++i) { - edges[i].v1 = vmap[vertexToIndex_fast(edges[i].v1)]; - edges[i].v2 = vmap[vertexToIndex_fast(edges[i].v2)]; + edges[i].v1 = vmap[(size_t)vertexToIndex_fast(edges[i].v1)]; + edges[i].v2 = vmap[(size_t)vertexToIndex_fast(edges[i].v2)]; } vout.swap(vertices); @@ -89,7 +89,6 @@ namespace carve { int r = 1; for (size_t i = 0; i < f->nEdges(); ++i) { - const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(f->edge(i))]; const face_t *f2 = connectedFace(f, f->edge(i)); if (f2) { r += _faceNeighbourhood(f2, depth - 1, (*result)); @@ -114,7 +113,7 @@ namespace carve { tagable::tag_begin(); int r = 0; - const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)]; + const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[(size_t)edgeToIndex_fast(e)]; for (size_t i = 0; i < edge_faces.size(); ++i) { const face_t *f = edge_faces[i]; if (f && f->manifold_id == m_id) { r += _faceNeighbourhood(f, depth, &result); } @@ -129,7 +128,7 @@ namespace carve { tagable::tag_begin(); int r = 0; - const std::vector<const face_t *> &vertex_faces = connectivity.vertex_to_face[vertexToIndex_fast(v)]; + const std::vector<const face_t *> &vertex_faces = connectivity.vertex_to_face[(size_t)vertexToIndex_fast(v)]; for (size_t i = 0; i < vertex_faces.size(); ++i) { const face_t *f = vertex_faces[i]; if (f && f->manifold_id == m_id) { r += _faceNeighbourhood(f, depth, &result); } @@ -142,7 +141,7 @@ namespace carve { // accessing connectivity information. template<typename T> int Geometry<3>::vertexToEdges(const vertex_t *v, T result) const { - const std::vector<const edge_t *> &e = connectivity.vertex_to_edge[vertexToIndex_fast(v)]; + const std::vector<const edge_t *> &e = connectivity.vertex_to_edge[(size_t)vertexToIndex_fast(v)]; std::copy(e.begin(), e.end(), result); return e.size(); } @@ -151,7 +150,7 @@ namespace carve { template<typename T> int Geometry<3>::vertexToFaces(const vertex_t *v, T result) const { - const std::vector<const face_t *> &vertex_faces = connectivity.vertex_to_face[vertexToIndex_fast(v)]; + const std::vector<const face_t *> &vertex_faces = connectivity.vertex_to_face[(size_t)vertexToIndex_fast(v)]; int c = 0; for (size_t i = 0; i < vertex_faces.size(); ++i) { *result++ = vertex_faces[i]; ++c; @@ -163,7 +162,7 @@ namespace carve { template<typename T> int Geometry<3>::edgeToFaces(const edge_t *e, T result) const { - const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)]; + const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[(size_t)edgeToIndex_fast(e)]; int c = 0; for (size_t i = 0; i < edge_faces.size(); ++i) { if (edge_faces[i] != NULL) { *result++ = edge_faces[i]; ++c; } @@ -174,7 +173,7 @@ namespace carve { inline const Geometry<3>::face_t *Geometry<3>::connectedFace(const face_t *f, const edge_t *e) const { - const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)]; + const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[(size_t)edgeToIndex_fast(e)]; for (size_t i = 0; i < (edge_faces.size() & ~1U); i++) { if (edge_faces[i] == f) return edge_faces[i^1]; } @@ -185,7 +184,7 @@ namespace carve { inline void Polyhedron::invert(int m_id) { std::vector<bool> selected_manifolds(manifold_is_closed.size(), false); - if (m_id >=0 && (unsigned)m_id < selected_manifolds.size()) selected_manifolds[m_id] = true; + if (m_id >=0 && (size_t)m_id < selected_manifolds.size()) selected_manifolds[(size_t)m_id] = true; invert(selected_manifolds); } @@ -198,7 +197,7 @@ namespace carve { inline bool Polyhedron::edgeOnManifold(const edge_t *e, int m_id) const { - const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)]; + const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[(size_t)edgeToIndex_fast(e)]; for (size_t i = 0; i < edge_faces.size(); ++i) { if (edge_faces[i] && edge_faces[i]->manifold_id == m_id) return true; @@ -207,7 +206,7 @@ namespace carve { } inline bool Polyhedron::vertexOnManifold(const vertex_t *v, int m_id) const { - const std::vector<const face_t *> &f = connectivity.vertex_to_face[vertexToIndex_fast(v)]; + const std::vector<const face_t *> &f = connectivity.vertex_to_face[(size_t)vertexToIndex_fast(v)]; for (size_t i = 0; i < f.size(); ++i) { if (f[i]->manifold_id == m_id) return true; @@ -219,7 +218,7 @@ namespace carve { template<typename T> int Polyhedron::edgeManifolds(const edge_t *e, T result) const { - const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)]; + const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[(size_t)edgeToIndex_fast(e)]; for (size_t i = 0; i < (edge_faces.size() & ~1U); i += 2) { const face_t *f1 = edge_faces[i]; @@ -230,14 +229,14 @@ namespace carve { else if (f2) *result++ = f2->manifold_id; } - return edge_faces.size() >> 1; + return (int)(edge_faces.size() >> 1); } template<typename T> int Polyhedron::vertexManifolds(const vertex_t *v, T result) const { - const std::vector<const face_t *> &f = connectivity.vertex_to_face[vertexToIndex_fast(v)]; + const std::vector<const face_t *> &f = connectivity.vertex_to_face[(size_t)vertexToIndex_fast(v)]; std::set<int> em; for (size_t i = 0; i < f.size(); ++i) { diff --git a/extern/carve/include/carve/polyline_decl.hpp b/extern/carve/include/carve/polyline_decl.hpp index 5934dd25a34..0d64365610a 100644 --- a/extern/carve/include/carve/polyline_decl.hpp +++ b/extern/carve/include/carve/polyline_decl.hpp @@ -60,10 +60,10 @@ namespace carve { struct PolylineEdge : public tagable { Polyline *parent; - unsigned edgenum; + size_t edgenum; Vertex *v1, *v2; - PolylineEdge(Polyline *_parent, int _edgenum, Vertex *_v1, Vertex *_v2); + PolylineEdge(Polyline *_parent, size_t _edgenum, Vertex *_v1, Vertex *_v2); carve::geom3d::AABB aabb() const; diff --git a/extern/carve/include/carve/polyline_impl.hpp b/extern/carve/include/carve/polyline_impl.hpp index 3c17980a9af..067701acc65 100644 --- a/extern/carve/include/carve/polyline_impl.hpp +++ b/extern/carve/include/carve/polyline_impl.hpp @@ -19,7 +19,7 @@ namespace carve { namespace line { - inline PolylineEdge::PolylineEdge(Polyline *_parent, int _edgenum, Vertex *_v1, Vertex *_v2) : + inline PolylineEdge::PolylineEdge(Polyline *_parent, size_t _edgenum, Vertex *_v1, Vertex *_v2) : tagable(), parent(_parent), edgenum(_edgenum), v1(_v1), v2(_v2) { } @@ -102,11 +102,11 @@ namespace carve { PolylineEdge *e; if (begin == end) return; - size_t v1 = (int)*begin++; + size_t v1 = (size_t)*begin++; if (begin == end) return; while (begin != end) { - size_t v2 = (int)*begin++; + size_t v2 = (size_t)*begin++; e = new PolylineEdge(this, edges.size(), &vertices[v1], &vertices[v2]); edges.push_back(e); v1 = v2; diff --git a/extern/carve/include/carve/rtree.hpp b/extern/carve/include/carve/rtree.hpp index 65d46e5a48d..cc85b68180e 100644 --- a/extern/carve/include/carve/rtree.hpp +++ b/extern/carve/include/carve/rtree.hpp @@ -346,8 +346,10 @@ namespace carve { std::vector<size_t>::iterator begin, std::vector<size_t>::iterator end, size_t part_size) { + CARVE_ASSERT(begin < end); + partition_info best(std::numeric_limits<double>::max(), 0); - const size_t N = std::distance(begin, end); + const size_t N = (size_t)std::distance(begin, end); std::vector<double> rhs_vol(N, 0.0); @@ -375,7 +377,9 @@ namespace carve { size_t part_size, std::vector<size_t> &part_num, size_t &part_next) { - const size_t N = std::distance(begin, end); + CARVE_ASSERT(begin < end); + + const size_t N = (size_t)std::distance(begin, end); partition_info best; partition_info curr; @@ -406,8 +410,8 @@ namespace carve { } } - for (size_t j = 0; j < best.partition_pos; ++j) part_num[begin[j]] = part_curr; - for (size_t j = best.partition_pos; j < N; ++j) part_num[begin[j]] = part_next; + for (size_t j = 0; j < best.partition_pos; ++j) part_num[begin[(ssize_t)j]] = part_curr; + for (size_t j = best.partition_pos; j < N; ++j) part_num[begin[(ssize_t)j]] = part_next; ++part_next; if (best.partition_pos > part_size) { diff --git a/extern/carve/include/carve/win32.h b/extern/carve/include/carve/win32.h index 8b5021cf2fb..5f8ce3b3bf6 100755 --- a/extern/carve/include/carve/win32.h +++ b/extern/carve/include/carve/win32.h @@ -37,7 +37,7 @@ typedef unsigned long uintptr_t; #if defined(_WIN32) && !defined(__MINGW32__) /* The __intXX are built-in types of the visual complier! So we don't need to include anything else here. - This typedefs should be in sync with types from BLI_sys_types.h */ + This typedefs should be in sync with types from MEM_sys_types.h */ typedef signed __int8 int8_t; typedef signed __int16 int16_t; |