MeshLib C++ Docs
Loading...
Searching...
No Matches
MRPolylineTopology.h
Go to the documentation of this file.
1#pragma once
2
3#include "MRMeshFwd.h"
4#include "MRVector.h"
5#include "MRId.h"
6// for template implementation:
7#include "MRBitSet.h"
8
9namespace MR
10{
11
15{
16public:
20 template<typename T, typename F1, typename F2>
21 void buildFromContours( const std::vector<std::vector<T>> & contours, F1 && reservePoints, F2 && addPoint );
22
25 MRMESH_API void buildOpenLines( const std::vector<VertId> & comp2firstVert );
26
28 template<typename T, typename F>
29 [[nodiscard]] std::vector<std::vector<T>> convertToContours( F&& getPoint, std::vector<std::vector<VertId>>* vertMap = nullptr ) const;
30
32 [[nodiscard]] MRMESH_API EdgeId makeEdge();
35 MRMESH_API EdgeId makeEdge( VertId a, VertId b );
37 [[nodiscard]] MRMESH_API bool isLoneEdge( EdgeId a ) const;
39 [[nodiscard]] MRMESH_API EdgeId lastNotLoneEdge() const;
41 [[nodiscard]] size_t edgeSize() const { return edges_.size(); }
43 [[nodiscard]] size_t undirectedEdgeSize() const { return edges_.size() >> 1; }
45 [[nodiscard]] MRMESH_API size_t computeNotLoneUndirectedEdges() const;
47 void edgeReserve( size_t newCapacity ) { edges_.reserve( newCapacity ); }
49 [[nodiscard]] bool hasEdge( EdgeId e ) const { assert( e.valid() ); return e < (int)edgeSize() && !isLoneEdge( e ); }
51 MRMESH_API void deleteEdge( UndirectedEdgeId ue );
53 MRMESH_API void deleteEdges( const UndirectedEdgeBitSet & es );
55 [[nodiscard]] MRMESH_API size_t heapBytes() const;
56
61 MRMESH_API void splice( EdgeId a, EdgeId b );
62
64 [[nodiscard]] EdgeId next( EdgeId he ) const { assert(he.valid()); return edges_[he].next; }
66 [[nodiscard]] VertId org( EdgeId he ) const { assert(he.valid()); return edges_[he].org; }
68 [[nodiscard]] VertId dest( EdgeId he ) const { assert(he.valid()); return edges_[he.sym()].org; }
69
72 MRMESH_API void setOrg( EdgeId a, VertId v );
73
75 [[nodiscard]] const Vector<EdgeId, VertId> & edgePerVertex() const { return edgePerVertex_; }
79 [[nodiscard]] EdgeId edgeWithOrg( VertId a ) const { assert( a.valid() ); return a < int(edgePerVertex_.size()) && edgePerVertex_[a].valid() ? edgePerVertex_[a] : EdgeId(); }
81 [[nodiscard]] bool hasVert( VertId a ) const { return validVerts_.test( a ); }
83 [[nodiscard]] MRMESH_API int getVertDegree( VertId a ) const;
85 [[nodiscard]] int numValidVerts() const { return numValidVerts_; }
87 [[nodiscard]] MRMESH_API VertId lastValidVert() const;
89 [[nodiscard]] VertId addVertId() { edgePerVertex_.push_back( {} ); validVerts_.push_back( false ); return VertId( (int)edgePerVertex_.size() - 1 ); }
91 MRMESH_API void vertResize( size_t newSize );
93 MRMESH_API void vertResizeWithReserve( size_t newSize );
95 void vertReserve( size_t newCapacity ) { edgePerVertex_.reserve( newCapacity ); validVerts_.reserve( newCapacity ); }
97 [[nodiscard]] size_t vertSize() const { return edgePerVertex_.size(); }
99 [[nodiscard]] size_t vertCapacity() const { return edgePerVertex_.capacity(); }
101 [[nodiscard]] const VertBitSet & getValidVerts() const { return validVerts_; }
103 [[nodiscard]] const VertBitSet & getVertIds( const VertBitSet * region ) const { return region ? *region : validVerts_; }
104
106 [[nodiscard]] MRMESH_API EdgeId findEdge( VertId o, VertId d ) const;
107
109 [[nodiscard]] MRMESH_API VertBitSet getPathVertices( const EdgePath & path ) const;
110
115 MRMESH_API EdgeId splitEdge( EdgeId e );
116
120 MRMESH_API EdgeId makePolyline( const VertId * vs, size_t num );
121
125 VertMap * outVmap = nullptr, WholeEdgeMap * outEmap = nullptr );
127 MRMESH_API void addPartByMask( const PolylineTopology& from, const UndirectedEdgeBitSet& mask,
128 VertMap* outVmap = nullptr, EdgeMap* outEmap = nullptr );
129
132 MRMESH_API void pack( VertMap * outVmap = nullptr, WholeEdgeMap * outEmap = nullptr );
133
135 MRMESH_API void write( std::ostream & s ) const;
136 MRMESH_API bool read( std::istream & s );
137
139 [[nodiscard]] bool operator ==( const PolylineTopology & b ) const { return edges_ == b.edges_; }
140 [[nodiscard]] bool operator !=( const PolylineTopology & b ) const { return edges_ != b.edges_; }
141
143 [[nodiscard]] MRMESH_API bool isConsistentlyOriented() const;
151 [[nodiscard]] MRMESH_API bool isClosed() const;
152
153private:
155 void setOrg_( EdgeId a, VertId v );
156
158 struct HalfEdgeRecord
159 {
160 EdgeId next;
161 VertId org;
162
163 bool operator ==( const HalfEdgeRecord& b ) const
164 {
165 return next == b.next && org == b.org;
166 }
167 HalfEdgeRecord() noexcept = default;
168 explicit HalfEdgeRecord( NoInit ) noexcept : next( noInit ), org( noInit ) {}
169 };
170
172 Vector<HalfEdgeRecord, EdgeId> edges_;
173
175 Vector<EdgeId, VertId> edgePerVertex_;
176 VertBitSet validVerts_;
177 int numValidVerts_ = 0;
178};
179
180template<typename T, typename F1, typename F2>
181void PolylineTopology::buildFromContours( const std::vector<std::vector<T>> & contours, F1 && reservePoints, F2 && addPoint )
182{
183 *this = {};
184 size_t size = 0;
185 std::vector<bool> closed;
186 closed.reserve( contours.size() );
187 int numClosed = 0;
188 for ( const auto& c : contours )
189 {
190 const auto csize = c.size();
191 if ( csize > 2 )
192 {
193 closed.push_back( c.front() == c.back() );
194 }
195 else
196 {
197 closed.push_back( false );
198 }
199 if ( csize < 2 )
200 continue; // ignore contours with 0 or 1 points because of no edges in them
201 size += c.size();
202 if ( closed.back() )
203 ++numClosed;
204 }
205
206 reservePoints( size - numClosed );
207 vertResize( size - numClosed );
208
209 for ( int i = 0; i < contours.size(); ++i )
210 {
211 const auto& c = contours[i];
212 if ( c.size() < 2 )
213 continue; // ignore contours with 0 or 1 points because of no edges in them
214 const auto e0 = makeEdge();
215 const auto v0 = addPoint( c[0] );
216 setOrg( e0, v0 );
217 auto e = e0;
218 for ( int j = 1; j + 1 < c.size(); ++j )
219 {
220 const auto ej = makeEdge();
221 splice( ej, e.sym() );
222 const auto vj = addPoint( c[j] );
223 setOrg( ej, vj );
224 e = ej;
225 }
226 if ( closed[i] )
227 {
228 splice( e0, e.sym() );
229 }
230 else
231 {
232 const auto vx = addPoint( c.back() );
233 setOrg( e.sym(), vx );
234 }
235 }
236 assert( isConsistentlyOriented() );
237 assert( edgePerVertex_.size() == size - numClosed );
238}
239
240template<typename T, typename F>
241std::vector<std::vector<T>> PolylineTopology::convertToContours( F&& getPoint, std::vector<std::vector<VertId>>* vertMap ) const
242{
243 std::vector<std::vector<T>> res;
244
245 UndirectedEdgeBitSet linesUsed;
246 linesUsed.autoResizeSet( UndirectedEdgeId{ undirectedEdgeSize() } );
247 linesUsed.flip();
248 for ( EdgeId e0 : linesUsed )
249 {
250 if ( isLoneEdge( e0 ) )
251 continue;
252
253 EdgeId curLine = e0;
254 while ( curLine != next( curLine ) )
255 {
256 curLine = next( curLine ).sym();
257 if ( curLine == e0 )
258 break;
259 }
260
261 linesUsed.set( curLine.undirected(), false );
262
263 EdgeId e = curLine;
264 std::vector<T> cont;
265 std::vector<VertId> map;
266 auto orgV = org( e );
267 cont.push_back( getPoint( orgV ) );
268 if ( vertMap )
269 map.push_back( orgV );
270 for ( ;; )
271 {
272 e = e.sym();
273 cont.push_back( getPoint( org( e ) ) );
274 e = next( e );
275 if ( !linesUsed.test_set( e.undirected(), false ) )
276 break;
277 }
278 res.push_back( std::move( cont ) );
279 if ( vertMap )
280 vertMap->push_back( std::move( map ) );
281 }
282
283 return res;
284}
285
288{
291
294 EdgeId start( VertId v )
295 {
296 assert( !e0_ && !eLast_ );
297 e0_ = eLast_ = topology.makeEdge();
298 topology.setOrg( e0_, v );
299 return e0_;
300 }
303 EdgeId proceed( VertId v )
304 {
305 assert( eLast_ );
306 const auto ej = topology.makeEdge();
307 topology.splice( ej, eLast_.sym() );
308 topology.setOrg( ej, v );
309 return eLast_ = ej;
310 }
312 void close()
313 {
314 assert( e0_ && eLast_ );
315 topology.splice( e0_, eLast_.sym() );
316 e0_ = eLast_ = {};
317 }
319 void finishOpen( VertId v )
320 {
321 assert( eLast_ );
322 topology.setOrg( eLast_.sym(), v );
323 e0_ = eLast_ = {};
324 }
325
326private:
327 EdgeId e0_, eLast_;
328};
329
330} // namespace MR
#define MRMESH_API
Definition MRMesh/MRMeshFwd.h:79
Definition MRPolylineTopology.h:15
MRMESH_API int getVertDegree(VertId a) const
returns 0 if given vertex does not exist, 1 if it has one incident edge, and 2 if it has two incident...
MRMESH_API void deleteEdges(const UndirectedEdgeBitSet &es)
calls deleteEdge for every set bit
MRMESH_API void addPart(const PolylineTopology &from, VertMap *outVmap=nullptr, WholeEdgeMap *outEmap=nullptr)
size_t undirectedEdgeSize() const
returns the number of undirected edges (pairs of half-edges) including lone ones
Definition MRPolylineTopology.h:43
MRMESH_API bool isLoneEdge(EdgeId a) const
checks whether the edge is disconnected from all other edges and disassociated from all vertices (as ...
MRMESH_API VertId lastValidVert() const
returns last valid vertex id, or invalid id if no single valid vertex exists
MRMESH_API EdgeId makePolyline(const VertId *vs, size_t num)
void vertReserve(size_t newCapacity)
sets the capacity of vertices vector
Definition MRPolylineTopology.h:95
bool hasVert(VertId a) const
returns true if given vertex is present in the mesh
Definition MRPolylineTopology.h:81
EdgeId edgeWithOrg(VertId a) const
returns valid edge if given vertex is present in the mesh
Definition MRPolylineTopology.h:79
EdgeId next(EdgeId he) const
next (counter clock wise) half-edge in the origin ring
Definition MRPolylineTopology.h:64
MRMESH_API size_t computeNotLoneUndirectedEdges() const
computes the number of not-lone (valid) undirected edges
MRMESH_API EdgeId splitEdge(EdgeId e)
MRMESH_API void computeValidsFromEdges()
computes numValidVerts_ and validVerts_ from edgePerVertex_
MRMESH_API bool isConsistentlyOriented() const
returns true if for each edge e: e == e.next() || e.odd() == next( e ).sym().odd()
MRMESH_API void setOrg(EdgeId a, VertId v)
const VertBitSet & getValidVerts() const
returns cached set of all valid vertices
Definition MRPolylineTopology.h:101
MRMESH_API void vertResize(size_t newSize)
explicitly increases the size of vertices vector
MRMESH_API EdgeId makeEdge()
creates an edge not associated with any vertex
MRMESH_API EdgeId makeEdge(VertId a, VertId b)
MRMESH_API EdgeId findEdge(VertId o, VertId d) const
finds and returns edge from o to d in the mesh; returns invalid edge otherwise
MRMESH_API EdgeId lastNotLoneEdge() const
returns last not lone edge id, or invalid id if no such edge exists
MRMESH_API bool read(std::istream &s)
MRMESH_API size_t heapBytes() const
returns the amount of memory this object occupies on heap
MRMESH_API void pack(VertMap *outVmap=nullptr, WholeEdgeMap *outEmap=nullptr)
MRMESH_API void flip()
changes the orientation of all edges: every edge e is replaced with e.sym()
size_t vertCapacity() const
returns the number of allocated vert records
Definition MRPolylineTopology.h:99
size_t edgeSize() const
returns the number of half-edge records including lone ones
Definition MRPolylineTopology.h:41
MRMESH_API void buildOpenLines(const std::vector< VertId > &comp2firstVert)
const Vector< EdgeId, VertId > & edgePerVertex() const
for all valid vertices this vector contains an edge with the origin there
Definition MRPolylineTopology.h:75
VertId org(EdgeId he) const
returns origin vertex of half-edge
Definition MRPolylineTopology.h:66
MRMESH_API bool checkValidity() const
verifies that all internal data structures are valid
MRMESH_API void splice(EdgeId a, EdgeId b)
const VertBitSet & getVertIds(const VertBitSet *region) const
if region pointer is not null then converts it in reference, otherwise returns all valid vertices in ...
Definition MRPolylineTopology.h:103
size_t vertSize() const
returns the number of vertex records including invalid ones
Definition MRPolylineTopology.h:97
void edgeReserve(size_t newCapacity)
sets the capacity of half-edges vector
Definition MRPolylineTopology.h:47
void buildFromContours(const std::vector< std::vector< T > > &contours, F1 &&reservePoints, F2 &&addPoint)
Definition MRPolylineTopology.h:181
MRMESH_API Vector< VertId, EdgeId > getOrgs() const
for all edges this vector contains its origin
int numValidVerts() const
returns the number of valid vertices
Definition MRPolylineTopology.h:85
MRMESH_API VertBitSet getPathVertices(const EdgePath &path) const
returns all vertices incident to path edges
VertId dest(EdgeId he) const
returns destination vertex of half-edge
Definition MRPolylineTopology.h:68
VertId addVertId()
creates new vert-id not associated with any edge yet
Definition MRPolylineTopology.h:89
MRMESH_API void deleteEdge(UndirectedEdgeId ue)
given edge becomes lone after the call, so it is un-spliced from connected edges, and if it was not c...
MRMESH_API void addPartByMask(const PolylineTopology &from, const UndirectedEdgeBitSet &mask, VertMap *outVmap=nullptr, EdgeMap *outEmap=nullptr)
appends polyline topology (from) in addition to the current topology: creates new edges,...
std::vector< std::vector< T > > convertToContours(F &&getPoint, std::vector< std::vector< VertId > > *vertMap=nullptr) const
converts this topology into contours of given type using the functor returning point by its Id
Definition MRPolylineTopology.h:241
MRMESH_API bool isClosed() const
returns true if the polyline does not have any holes
bool hasEdge(EdgeId e) const
returns true if given edge is within valid range and not-lone
Definition MRPolylineTopology.h:49
bool operator!=(const PolylineTopology &b) const
Definition MRPolylineTopology.h:140
bool operator==(const PolylineTopology &b) const
comparison via edges (all other members are considered as not important caches)
Definition MRPolylineTopology.h:139
MRMESH_API void vertResizeWithReserve(size_t newSize)
explicitly increases the size of vertices vector, doubling the current capacity if it was not enough
MRMESH_API void write(std::ostream &s) const
saves and loads in binary stream
std::vector<T>-like container that requires specific indexing type,
Definition MRMesh/MRVector.h:19
std::size_t size() const
Definition MRMesh/MRVector.h:41
std::size_t capacity() const
Definition MRMesh/MRVector.h:49
void reserve(size_t capacity)
Definition MRMesh/MRVector.h:50
void push_back(const T &t)
Definition MRMesh/MRVector.h:108
Definition MRCameraOrientationPlugin.h:8
ImVec2 size(const ViewportRectangle &rect)
Definition MRViewport.h:29
std::vector< EdgeId > EdgePath
Definition MRMesh/MRMeshFwd.h:135
constexpr NoInit noInit
Definition MRMesh/MRMeshFwd.h:90
Definition MRMesh/MRMeshFwd.h:89
simplifies construction of connected polyline in the topology
Definition MRPolylineTopology.h:288
EdgeId start(VertId v)
Definition MRPolylineTopology.h:294
void finishOpen(VertId v)
finishes the polyline adding final vertex in it
Definition MRPolylineTopology.h:319
void close()
closes the polyline
Definition MRPolylineTopology.h:312
PolylineTopology & topology
Definition MRPolylineTopology.h:289
PolylineMaker(PolylineTopology &t)
Definition MRPolylineTopology.h:290
EdgeId proceed(VertId v)
Definition MRPolylineTopology.h:303