blender
/
blender
133
398
Fork 579
Code Issues 6.3k Pull Requests 748 Projects 19 Wiki Activity

Update Carve to upstream version be054bc7ed86

This commit is contained in:
Sergey Sharybin 2013-11-28 13:51:17 +06:00
parent 1c14ead46f
commit a628ca9ebe
20 changed files with 511 additions and 195 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

6
extern/carve/include/carve/aabb.hpp vendored
View File

@ -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>

17
extern/carve/include/carve/aabb_impl.hpp vendored
View File

@ -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;

16
extern/carve/include/carve/csg.hpp vendored
View File

@ -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);

4
extern/carve/include/carve/debug_hooks.hpp vendored
View File

@ -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;
}
}
}

4
extern/carve/include/carve/face_impl.hpp vendored
View File

@ -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));

4
extern/carve/include/carve/geom.hpp vendored
View File

@ -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);

4
extern/carve/include/carve/geom2d.hpp vendored
View File

@ -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);
}
}

77
extern/carve/include/carve/geom3d.hpp vendored
View File

@ -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;
p1 = p2; p2 = p3; p3 = c1;
v = cross(p3 - p2, p1 - p2);
if (v.v[largestAxis(v)]) v.negate();
n += v;
if (p.size() == 3) {
n = cross(p[1] - p[0], p[2] - p[0]);
} else {
const size_t N = p.size();
p1 = p2; p2 = p3; p3 = c2;
v = cross(p3 - p2, p1 - p2);
if (v.v[largestAxis(v)]) v.negate();
n += v;
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;
}
}
double l = n.length();
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;
}

47
extern/carve/include/carve/geom_impl.hpp vendored
View File

@ -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);
}

325
extern/carve/include/carve/interpolator.hpp vendored
View File

@ -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,11 +186,70 @@ 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;
typedef carve::mesh::MeshSet<3> meshset_t;
protected:
friend struct Hook;
struct Hook : public carve::csg::CSG::Hook {
const carve::csg::CSG &csg;
Interpolator *interpolator;
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->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, 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() {
}
@ -186,78 +257,51 @@ namespace carve {
virtual ~Interpolator() {
}
class Hook : public carve::csg::CSG::Hook {
Interpolator *interpolator;
public:
virtual void resultFace(const carve::mesh::MeshSet<3>::face_t *new_face,
const carve::mesh::MeshSet<3>::face_t *orig_face,
bool flipped) {
interpolator->interpolate(new_face, orig_face, flipped);
}
Hook(Interpolator *_interpolator) : interpolator(_interpolator) {
}
virtual ~Hook() {
}
};
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 {
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<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 meshset_t::face_t *f, unsigned e) {
return attrs.find(std::make_pair(f, e)) != attrs.end();
}
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 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<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;
attrmap_t attrs;
public:
bool hasAttribute(const carve::mesh::MeshSet<3>::face_t *f) {
return attrs.find(f) != attrs.end();
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;
}
}
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);
public:
bool hasAttribute(const meshset_t::face_t *f) {
return attrs.find(key_t(f)) != attrs.end();
}
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()) {
return (*i).second;
}
return def;
}
void setAttribute(const carve::mesh::MeshSet<3>::face_t *f, const attr_t &attr) {
attrs[f] = attr;
}
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);
if (i != attrs.end()) {
attrs[new_face] = (*i).second;
}
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() {
}
};
}

1
extern/carve/include/carve/mesh.hpp vendored
View File

@ -688,6 +688,7 @@ namespace carve {
void cacheEdges();
int orientationAtVertex(edge_t *);
void calcOrientation();
void recalc() {

95
extern/carve/include/carve/mesh_impl.hpp vendored
View File

@ -605,34 +605,79 @@ 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;
}
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;
return;
}
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) {

33
extern/carve/include/carve/polyhedron_impl.hpp vendored
View File

@ -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) {

4
extern/carve/include/carve/polyline_decl.hpp vendored
View File

@ -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;

6
extern/carve/include/carve/polyline_impl.hpp vendored
View File

@ -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;

12
extern/carve/include/carve/rtree.hpp vendored
View File

@ -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) {

2
extern/carve/include/carve/win32.h vendored
View File

@ -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;

8
extern/carve/lib/geom2d.cpp vendored
View File

@ -177,12 +177,12 @@ namespace carve {
break;
}
case INTERSECTION_PP: {
out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, e.ipoint, i + e.p2 - 2));
out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, e.ipoint, i + (size_t)e.p2 - 2));
count++;
break;
}
case INTERSECTION_LP: {
out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, e.ipoint, i + e.p2 - 2));
out.push_back(PolyIntersectionInfo(INTERSECT_VERTEX, e.ipoint, i + (size_t)e.p2 - 2));
count++;
break;
}
@ -192,7 +192,9 @@ namespace carve {
break;
}
case COLINEAR: {
int n1 = (int)i, n2 = (int)j;
size_t n1 = i;
size_t n2 = j;
P2 q1 = points[i], q2 = points[j];
if (q2 < q1) { std::swap(q1, q2); std::swap(n1, n2); }

11
extern/carve/lib/intersect.cpp vendored
View File

@ -407,6 +407,17 @@ void carve::csg::CSG::Hooks::resultFace(const meshset_t::face_t *new_face,
}
}
void carve::csg::CSG::Hooks::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) {
for (std::list<Hook *>::iterator j = hooks[EDGE_DIVISION_HOOK].begin();
j != hooks[EDGE_DIVISION_HOOK].end();
++j) {
(*j)->edgeDivision(orig_edge, orig_edge_idx, v1, v2);
}
}
void carve::csg::CSG::Hooks::registerHook(Hook *hook, unsigned hook_bits) {
for (unsigned i = 0; i < HOOK_MAX; ++i) {
if (hook_bits & (1U << i)) {

30
extern/carve/lib/intersect_face_division.cpp vendored
View File

@ -719,10 +719,6 @@ namespace {
unassigned--;
}
}
if (!removed.size())
throw carve::exception("Failed to merge holes");
for (std::set<int>::iterator f = removed.begin(); f != removed.end(); ++f) {
for (unsigned i = 0; i < containing_faces.size(); ++i) {
containing_faces[i].erase(std::remove(containing_faces[i].begin(),
@ -811,12 +807,14 @@ namespace {
*/
static bool assembleBaseLoop(carve::mesh::MeshSet<3>::face_t *face,
const carve::csg::detail::Data &data,
std::vector<carve::mesh::MeshSet<3>::vertex_t *> &base_loop) {
std::vector<carve::mesh::MeshSet<3>::vertex_t *> &base_loop,
carve::csg::CSG::Hooks &hooks) {
base_loop.clear();
// XXX: assumes that face->edges is in the same order as
// face->vertices. (Which it is)
carve::mesh::MeshSet<3>::edge_t *e = face->edge;
size_t e_idx = 0;
bool face_edge_intersected = false;
do {
base_loop.push_back(carve::csg::map_vertex(data.vmap, e->vert));
@ -830,9 +828,22 @@ namespace {
base_loop.push_back(ev_vec[k++]);
}
if (ev_vec.size() && hooks.hasHook(carve::csg::CSG::Hooks::EDGE_DIVISION_HOOK)) {
carve::mesh::MeshSet<3>::vertex_t *v1 = e->vert;
carve::mesh::MeshSet<3>::vertex_t *v2;
for (size_t k = 0, ke = ev_vec.size(); k < ke;) {
v2 = ev_vec[k++];
hooks.edgeDivision(e, e_idx, v1, v2);
v1 = v2;
}
v2 = e->v2();
hooks.edgeDivision(e, e_idx, v1, v2);
}
face_edge_intersected = true;
}
e = e->next;
++e_idx;
} while (e != face->edge);
return face_edge_intersected;
@ -1110,8 +1121,7 @@ namespace {
}
// copy up to the end of the path.
if (pos < e1_1)
std::copy(base_loop.begin() + pos, base_loop.begin() + e1_1, std::back_inserter(out));
std::copy(base_loop.begin() + pos, base_loop.begin() + e1_1, std::back_inserter(out));
CARVE_ASSERT(base_loop[e1_1] == p1.back());
std::copy(p1.rbegin(), p1.rend() - 1, std::back_inserter(out));
@ -1445,7 +1455,7 @@ namespace {
std::vector<carve::mesh::MeshSet<3>::vertex_t *> base_loop;
std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > hole_loops;
bool face_edge_intersected = assembleBaseLoop(face, data, base_loop);
bool face_edge_intersected = assembleBaseLoop(face, data, base_loop, hooks);
detail::FV2SMap::const_iterator fse_iter = data.face_split_edges.find(face);
@ -1637,9 +1647,7 @@ namespace {
* \brief Build a set of face loops for all (split) faces of a Polyhedron.
*
* @param[in] poly The polyhedron to process
* @param vmap
* @param face_split_edges
* @param divided_edges
* @param[in] data Internal intersection data
* @param[out] face_loops_out The resulting face loops
*
* @return The number of edges generated.