Public Types | |
| enum class | Kind { Uninitialized , Triangles3d , Edges3d , Edges2d } |
Public Member Functions | |
| Envelope (bool exact=true) | |
| void | set_max_threads (int n) |
| How many threads one triangle query may use. 1, the default: every sample is checked on the calling thread. | |
| virtual void | init (const std::vector< Eigen::Vector3d > &m_ver, const std::vector< Eigen::Vector3i > &m_faces, const double) |
| void | init (const std::vector< Eigen::Vector3d > &m_ver, const std::vector< Eigen::Vector2i > &m_edges, const double) |
| void | init (const std::vector< Eigen::Vector2d > &m_ver, const std::vector< Eigen::Vector2i > &m_edges, const double) |
| void | init (const Eigen::MatrixXd &V, const Eigen::MatrixXi &F, const double eps) |
| Same, from Eigen matrices, dispatching on the column counts. | |
| virtual bool | is_outside (const std::array< Eigen::Vector3d, 3 > &tris) const |
| bool | is_outside (const std::array< Eigen::Vector3d, 2 > &edge) const |
| virtual bool | is_outside (const std::array< Eigen::Vector2d, 2 > &edge) const |
| virtual bool | is_outside (const Eigen::Vector3d &pts) const |
| virtual bool | is_outside (const Eigen::Vector2d &pts) const |
| double | nearest_point (const Eigen::Vector3d &pts, Eigen::Vector3d &result) const |
| double | nearest_point (const Eigen::Vector2d &pts, Eigen::Vector2d &result) const |
| double | nearest_point_feature (const Eigen::Vector2d &p, Eigen::Vector2d &result, bool &on_corner, Eigen::Vector2d &seg_normal, int &feature_id) const |
| double | nearest_point_feature (const Eigen::Vector3d &p, Eigen::Vector3d &result, int &feature_dim, Eigen::Vector3d &dir, long long &feature_id) const |
| bool | initialized () |
| Kind | kind () const |
| double | squared_distance (const Eigen::Vector3d &p) const |
| double | squared_distance (const Eigen::Vector2d &p) const |
| void | primitives_in_box (const Eigen::Vector3d &lo, const Eigen::Vector3d &hi, std::vector< int64_t > &ids) const |
| The ids of every primitive whose bounding box meets the closed box [lo, hi], ascending, each once. | |
| void | primitives_in_box (const Eigen::Vector2d &lo, const Eigen::Vector2d &hi, std::vector< int64_t > &ids) const |
| The 2D counterpart, for Edges2d: the same tree, which holds the 2D input lifted to z = 0. | |
| double | primitive_distance (int64_t id, const Eigen::Vector3d &p, Eigen::Vector3d *grad=nullptr, Eigen::Matrix3d *hess=nullptr) const |
The distance d from p to primitive id alone, with its gradient and Hessian when asked for (nullptr = not wanted). | |
| double | primitive_distance (int64_t id, const Eigen::Vector2d &p, Eigen::Vector2d *grad=nullptr, Eigen::Matrix2d *hess=nullptr) const |
| double | primitive_triangle_distance (int64_t id, const std::array< Eigen::Vector3d, 3 > &tri) const |
The distance between the triangle tri and primitive id alone. | |
| double | primitive_segment_distance (int64_t id, const std::array< Eigen::Vector2d, 2 > &seg) const |
The 2D counterpart, for Edges2d: the distance between the segment seg and primitive id alone – a 2D front edge where the 3D query takes a front face. | |
Public Attributes | |
| double | eps2 = 1e-6 |
| double | eps2_edge = 1e-6 |
| double | sampling_dist = 1e-3 |
| bool | use_exact = true |
| bool | disabled = false |
Private Member Functions | |
| void | require_primitive_query (int dim, const char *query) const |
| void | require_primitive (int64_t id, int dim, const char *query) const |
| void | require_exact_kind (Kind expected, const char *query) const |
| void | require_exact_3d (const char *query) const |
| void | require_exact_built (const char *query) const |
| template<typename VertexList > | |
| void | init_exact_edges (const VertexList &V, const std::vector< Eigen::Vector2i > &F, const double _eps) |
| bool | samples_outside_parallel (const std::vector< Eigen::Vector3d > &ps) const |
The sampled triangle query's loop over ps, split among idle workers. | |
Private Attributes | |
| std::vector< int > | geo_vertex_ind |
| std::vector< int > | geo_face_ind |
| std::vector< Eigen::Vector2d > | m_v2 |
| Input copies backing nearest_point_feature (filled by the matching init only). | |
| std::vector< Eigen::Vector2i > | m_e2 |
| std::vector< Eigen::Vector3d > | m_v3 |
| std::vector< Eigen::Vector3i > | m_f3 |
| std::vector< Eigen::Vector2i > | m_e3 |
| std::shared_ptr< SimpleBVH::BVH > | m_bvh |
| fastEnvelope::FastEnvelope | exact_envelope |
| Serves both Triangles3d and Edges3d: FastEnvelope has an init() for each. | |
| fastEnvelope::FastEnvelope2D | exact_envelope_2d |
| Edges2d only. A separate class upstream, not an overload. | |
| Kind | m_kind = Kind::Uninitialized |
| bool | m_exact_built = false |
| int | m_max_threads = 1 |
Member Enumeration Documentation
◆ Kind
|
strong |
Which of the three init() overloads built this envelope.
The sampled path does not need it – every overload ends up in the same BVH, and a 2D query is answered by lifting to z = 0. The exact path does: a triangle-built and an edge-built FastEnvelope are different objects, a 2D envelope is a different class again, and only init() knows which one was filled in. Without this, is_outside(Vector2d) would lift to 3D and query a FastEnvelope that was never initialized, which answers "outside" for everything rather than failing.
Constructor & Destructor Documentation
◆ Envelope()
|
inline |
Exact by default. The sampled predicate tests points laid along the query against a shrunk radius and still cannot see between two samples; the exact one decides containment in the full eps-neighbourhood. A caller that wants the cheaper sampled test asks for it with exact = false.
Member Function Documentation
◆ init()
| void wmtk::Envelope::init | ( | const Eigen::MatrixXd & | V, |
| const Eigen::MatrixXi & | F, | ||
| const double | eps | ||
| ) |
Same, from Eigen matrices, dispatching on the column counts.
V Nx3, F Mx3 -> a 3D triangle envelope V Nx3, F Mx2 -> a 3D edge envelope V Nx2, F Mx2 -> a 2D edge envelope
Marshals into the vector form above. Most callers already hold matrices and were each writing the same ten-line copy loop; this is that loop, once.
◆ init_exact_edges()
|
private |
Build the exact edge envelope, when there is one to build and anything will ask for it.
Unlike the triangle overload, this is conditional on use_exact. The triangle envelope has to carry both structures because callers flip the flag on an already-initialized envelope – tetwild does that around its simplification, simwild around its insertion – but every one of those toggles is on a triangle envelope. Building the hexahedra or rectangles for a sampled edge envelope is pure cost: it added ~12% to the integration suite when this was unconditional. A toggle that arrives afterwards anyway is caught by m_exact_built rather than silently answering "outside" against an empty structure.
The rule for eps <= 0 is the triangle overload's: such an envelope serves nearest queries only, and a containment query against it refuses, through require_exact_built(). A zero epsilon is a legitimate way to ask for an envelope that will only ever be used for nearest_point() – triwild's Delaunay seeding does it, to reject grid points that fall too close to the input curves – and with use_exact the default, that request arrives here in exact mode. There is no such thing as a zero-width exact envelope: the 2D construction asserts on it, and a containment query against one would answer "outside" for everything not exactly on the input. So skip the build rather than throw at init, which refused the nearest-only use too, and let a containment query fail rather than quietly reject everything.
◆ is_outside()
|
virtual |
Four containment queries are VIRTUAL – the 3D triangle, the 3D point, the 2D segment and the 2D point – so a containment-only composite over several envelopes can answer them. They are exactly what the 3D and the 2D containment paths ask. The 3D segment query is not virtual. See the composites in wmtk/envelope/CompositeEnvelopes.hpp, and the invariant stated there: a composite must never reach the NON-virtual queries, whose BVH it does not have.
Reimplemented in wmtk::IntersectionEnvelope, and wmtk::UnionEnvelope.
◆ nearest_point_feature() [1/2]
| double wmtk::Envelope::nearest_point_feature | ( | const Eigen::Vector2d & | p, |
| Eigen::Vector2d & | result, | ||
| bool & | on_corner, | ||
| Eigen::Vector2d & | seg_normal, | ||
| int & | feature_id | ||
| ) | const |
Nearest point plus which feature of the input carries it, for the TRUE Hessian of the squared distance: within each closest-feature region the distance to a piecewise- linear input is exactly quadratic, and the region's kind decides the Hessian's rank.
2D polylines: on_corner reports a polyline-vertex foot; seg_normal is the segment's unit normal (valid when !on_corner, sign arbitrary); feature_id is the polyline vertex index or the segment index – canonical, so two queries compare as "did the closest feature change".
◆ nearest_point_feature() [2/2]
| double wmtk::Envelope::nearest_point_feature | ( | const Eigen::Vector3d & | p, |
| Eigen::Vector3d & | result, | ||
| int & | feature_dim, | ||
| Eigen::Vector3d & | dir, | ||
| long long & | feature_id | ||
| ) | const |
3D counterpart, for triangle envelopes AND edge (curve) envelopes. feature_dim: 2 = face interior, 1 = edge/segment interior, 0 = vertex. dir is the face normal (dim 2) or the edge direction (dim 1), unit length, sign arbitrary. feature_id is canonical across adjacent primitives (face index / sorted vertex pair packed as min * n_vertices + max / vertex index).
◆ primitive_distance() [1/2]
| double wmtk::Envelope::primitive_distance | ( | int64_t | id, |
| const Eigen::Vector2d & | p, | ||
| Eigen::Vector2d * | grad = nullptr, |
||
| Eigen::Matrix2d * | hess = nullptr |
||
| ) | const |
The 2D counterpart, for Edges2d: the same segment foot and the same derivatives in 2D, where a segment's interior has Hessian 0 – d is affine there, I - u u^T - e e^T vanishing with u and e orthonormal – as EuclideanOffsetPotential<2>::hessian() has it; (I - u u^T)/d at an endpoint or a point.
◆ primitive_distance() [2/2]
| double wmtk::Envelope::primitive_distance | ( | int64_t | id, |
| const Eigen::Vector3d & | p, | ||
| Eigen::Vector3d * | grad = nullptr, |
||
| Eigen::Matrix3d * | hess = nullptr |
||
| ) | const |
The distance d from p to primitive id alone, with its gradient and Hessian when asked for (nullptr = not wanted).
The derivatives are those of the distance to the feature the foot point lies on: gradient u = (p - foot)/d; Hessian 0 when the foot is inside a triangle, (I - u u^T - e e^T)/d when it is on a triangle's edge or inside a segment (e the unit edge direction), (I - u u^T)/d at a triangle's vertex, a segment's endpoint or a point primitive. At d = 0 both are reported as 0.
The triangle foot is Ericson's (Real-Time Collision Detection 5.1.5). The same arithmetic compiled with EIGEN_DONT_VECTORIZE agrees with it only to rounding, because it sums the dot products in another order (see Envelope.cpp). The segment foot is nearest_point_feature()'s, clamped at both ends.
◆ primitive_segment_distance()
| double wmtk::Envelope::primitive_segment_distance | ( | int64_t | id, |
| const std::array< Eigen::Vector2d, 2 > & | seg | ||
| ) | const |
The 2D counterpart, for Edges2d: the distance between the segment seg and primitive id alone – a 2D front edge where the 3D query takes a front face.
0 when the two cross, each one's endpoints strictly on the two sides of the other's line, by exact orientation signs as in 3D. Otherwise the segment-segment distance (Ericson 5.1.9), whose closest pair for disjoint segments has an endpoint of one; a contact without a crossing (an endpoint on the other segment, or collinear overlap) is such an endpoint at 0. A point primitive gives its distance to seg.
◆ primitive_triangle_distance()
| double wmtk::Envelope::primitive_triangle_distance | ( | int64_t | id, |
| const std::array< Eigen::Vector3d, 3 > & | tri | ||
| ) | const |
The distance between the triangle tri and primitive id alone.
0 when an edge of one crosses the other (a segment primitive: when it crosses tri) – its endpoints strictly on the two sides of the other's plane, by exact orientation signs. Otherwise, against a triangle primitive, the min of the 6 corner-to-other-triangle distances and the 9 edge-edge distances (Ericson 5.1.9); against a segment, the min of its 2 endpoint-to-tri distances and its 3 distances to the edges of tri; against a point, its distance to tri. Two disjoint convex primitives' closest pair has a corner of one, or a point on an edge of each; two that meet without such a crossing (a corner on the other's plane, or coplanar) have one of those at 0.
The same arithmetic compiled with EIGEN_DONT_VECTORIZE agrees only to rounding, as above.
◆ primitives_in_box()
| void wmtk::Envelope::primitives_in_box | ( | const Eigen::Vector3d & | lo, |
| const Eigen::Vector3d & | hi, | ||
| std::vector< int64_t > & | ids | ||
| ) | const |
The ids of every primitive whose bounding box meets the closed box [lo, hi], ascending, each once.
A wrapper of SimpleBVH::BVH::intersect_box, which already maps its leaves back to input ids (nearest_facet does not – see nearest_point_feature()) and visits each leaf once, so the result has no duplicates; but it lists them in the BVH's own Morton order, so they are sorted here. The boxes are the primitives' exact bounding boxes (the BVH is built with zero padding), compared closed: a box that only touches [lo, hi] counts. A caller that needs every primitive within r of a point passes the point's box grown by r, padded by its own rounding allowance.
◆ require_exact_3d()
|
private |
The 3D point and segment queries work against either 3D envelope, so they check only that this is not the 2D one – and that its exact structure actually exists.
◆ require_exact_kind()
|
private |
An exact query must be answered by the structure the matching init() built.
Getting this wrong is silent and dangerous rather than noisy: a default-constructed FastEnvelope has no prisms, and a query against no prisms answers "outside" for every point – so a mismatched envelope does not crash, it just vetoes every operation and looks like an optimization that cannot move.
◆ require_primitive_query()
|
private |
The checks of the per-primitive queries: an initialized envelope of dimension dim, and for the second an id in range.
◆ set_max_threads()
|
inline |
How many threads one triangle query may use. 1, the default: every sample is checked on the calling thread.
A triangle many times longer than eps samples to thousands of points, and its query costs milliseconds. Above n = 1, such a query splits its samples among idle workers of the thread pool, up to n threads in all, counting the caller. It takes only workers that are idle at that moment and waits for none, so in a parallel pass that keeps every thread busy nothing changes; the queries left running at the end get the threads that ran out of work. The answer is the same either way.
Member Data Documentation
◆ disabled
| bool wmtk::Envelope::disabled = false |
Debug escape hatch: when set, every is_outside() answers "inside".
The envelope is the only thing that can reject an operation for geometric rather than combinatorial reasons, so turning it off tells you whether a stalled optimization is blocked by the envelope or by the mesh itself. It removes the containment guarantee entirely – the output is not usable, only diagnostic.
Note nearest_point() is unaffected, so EnvelopeEnergy still pulls surface vertices toward the input while smoothing. Only the veto goes away, which is the point: it separates "the optimizer cannot move because the envelope forbids it" from "the optimizer cannot move at all".
◆ eps2
| double wmtk::Envelope::eps2 = 1e-6 |
Per-sample acceptance radius, squared, for POINT and TRIANGLE queries.
eps shrunk by the covering radius of sampleTriangle's lattice, sampling_dist/sqrt(3). A point query needs no shrink at all and is therefore merely conservative here; it is left as it is because every 3D operation goes through it and widening it would change tetwild's behaviour everywhere, which belongs in its own change.
◆ eps2_edge
| double wmtk::Envelope::eps2_edge = 1e-6 |
The same, for EDGE queries, where the covering radius is different.
is_outside(edge) samples the segment at N+1 evenly spaced points with N = floor(L/sampling_dist) + 1 > L/sampling_dist, so the spacing is L/N < sampling_dist and every point of the segment lies within sampling_dist/2 of a sample. Distance to a set is 1-Lipschitz, so "every sample within r" implies "every point within r + sampling_dist/2"; for that to imply containment in eps,
r = eps - sampling_dist / 2 (= eps/2, since sampling_dist = eps)
The lattice constant eps - sampling_dist/sqrt(3) belongs to sampleTriangle and is simply the wrong figure here: it is 0.4226*eps against the correct 0.5*eps, so using it made the edge test 18% stricter than the geometry requires. That is safe on its own – but it also made the simplification's own guarantee (r_s + sampling_dist_s/2 = eps_s) exceed the acceptance threshold of the coarser envelope the optimizer checks against, so a correctly simplified input could be rejected by the init sanity check. It was, once in 15665 models.
◆ m_exact_built
|
private |
Whether the edge/2D exact structure was actually built. Always false for Triangles3d, which builds its exact envelope unconditionally and is checked by kind alone.
◆ m_max_threads
|
private |
The documentation for this class was generated from the following files:
- src/wmtk/envelope/Envelope.hpp
- src/wmtk/envelope/Envelope.cpp
