Comments (30)
We have improved
extractPlaneSections
a bit. Hope it will speed up things
It's roughly 2.5 times faster now! Super cool! For my test mesh and 0.1 interval I'm down to 4ms (screen capture slows it down a bit):
2023-07-19.17-54-56.mp4
Next step is to add the labels.
from meshlib.
Thanks for your prompt response! I'll definitely look into extractiPlaneSections
and benchmark its speed against the GLSL shader.
You correctly understand what I'm doing. Step 2 is not the bottleneck here, I am using Transform Feedback and it takes 1-2 ms to complete. The slow part is Step 3 where I'm trying to identify the line segments which belong to the same contour line (have equal Z values) and filter them based on distance to other labels.
from meshlib.
Oh sure, there is race for plane
arg
Box3f box = mesh->getBoundingBox();
float bottom = box.min.z + interval;
float contoursCount = (box.max.z - bottom) / interval;
std::vector<PlaneSections> sections(contoursCount);
ParallelFor( sections, [&]( size_t i )
{
auto localPlane = Plane3f( Vector3f::plusZ(), bottom + (i * interval) );
sections[i] = extractPlaneSections( m, localPlane );
} );
from meshlib.
Thanks @Grantim, switching to parallel execution speeds things up by 5-8x on my machine:
2023-07-19.14-20-24.mp4
I totally agree that this is a more robust way of working with labels but ideally it would be even faster than this. For my application, contour lines are 'just' an analysis mode running on top of other mesh processing operations. The overhead should be as minimal as possible.
For reference, there were some minor bugs in the code, I'm posting a working version below. I also removed the size allocation to vectors, there is no measurable difference in performance but the code looks cleaner:
const MeshPart m = MeshPart( *mesh, nullptr );
Box3f box = mesh->getBoundingBox();
float bottom = std::ceil( box.min.z / interval ) * interval;
float contoursCount = (box.max.z - bottom) / interval;
std::vector<PlaneSections> sections( (size_t)contoursCount);
ParallelFor( sections, [&] ( size_t i )
{
Plane3f plane = Plane3f( Vector3f::plusZ(), bottom + ( i * interval ) );
sections[i] = extractPlaneSections( m, plane );
} );
std::vector<float> contourCoordinates;
std::vector<int> contourLengths;
for ( const PlaneSections& contours : sections )
{
for ( const SurfacePath& contour : contours )
{
for ( const MeshEdgePoint& point : contour )
{
Vector3f pt = mesh->edgePoint( point );
contourCoordinates.push_back( pt.x );
contourCoordinates.push_back( pt.y );
contourCoordinates.push_back( pt.z );
}
contourLengths.push_back( ( uint32_t )( contour.size() * 3 ) );
}
}
from meshlib.
Thanks, we will work on extractPlaneSections
speedup!
from meshlib.
I think simple adding segments should be fine, unfortunately I don't have any other idea now. There is decimation algorithm for polylines, but casting it to polyline and decimation will most likely take more time.
from meshlib.
I'll investigate and will keep you posted. On another note, I switched to writing the results directly to the output arrays and parallelized this as well. This shaved off approx. 10-20%.
PINVOKE RawPolylineArrays CreateContours( Mesh* mesh, float interval )
{
const MeshPart m = MeshPart( *mesh, nullptr );
const Box3f box = mesh->getBoundingBox();
const float bottom = std::ceil( box.min.z / interval ) * interval;
const float contoursCount = ( box.max.z - bottom ) / interval;
std::vector<PlaneSections> sections( ( size_t )contoursCount );
ParallelFor( sections, [&] ( size_t i )
{
Plane3f plane = Plane3f( Vector3f::plusZ(), bottom + ( i * interval ) );
sections[i] = extractPlaneSections( m, plane );
} );
size_t lengthSize = 0;
size_t coordsSize = 0;
std::vector<size_t> lengthLookup;
std::vector<size_t> coordsLookup;
for ( const auto& s : sections )
{
lengthLookup.emplace_back( lengthSize );
coordsLookup.emplace_back( coordsSize );
lengthSize += s.size();
for ( const auto& path : s )
coordsSize += path.size() * 3;
}
RawPolylineArrays result = RawPolylineArrays();
result.ArrayLength = ( uint32_t )lengthSize;
result.ContourLengths = new int[result.ArrayLength];
result.ContourVertices = new float[coordsSize];
ParallelFor( sections, [&] ( size_t i )
{
size_t localCoordsStart = coordsLookup[i];
size_t localLengthStart = lengthLookup[i];
size_t j = 0;
size_t k = 0;
for ( const SurfacePath& contour : sections[i] )
{
for ( const MeshEdgePoint& point : contour )
{
Vector3f pt = mesh->edgePoint( point );
result.ContourVertices[localCoordsStart + j++] = pt.x;
result.ContourVertices[localCoordsStart + j++] = pt.y;
result.ContourVertices[localCoordsStart + j++] = pt.z;
}
result.ContourLengths[localLengthStart + k++] = ( uint32_t )( contour.size() * 3 );
}
} );
return result;
}
from meshlib.
We have added new overload of extractIsolines
function only today. Please pull the latest MeshLib.
from meshlib.
I see, ok, we will think what can be optimized more. But it will take a while.
from meshlib.
Thanks @Fedr. You guys keep delivering awesome quality code! Switching to the new function brings the total execution time down to 1-2ms for my test mesh. This is including finding label positions and copying data to managed code. This is perfect for my application.
2023-07-24.09-00-52.mp4
from meshlib.
Hello!
First of all thank you for sharing your code and the article. If I have understood your casea correctly you have following pipeline:
- Calculate horizontal sections with GPU (and draw it?)
- Transfering Geometry shader output to CPU (to find label positions)
- Find label positions
- Draw labels
Most likely second step is the slowest one, also our experience with geometry shaders shows that using it is quite slow too (compared to rendering without geometry shader)
Suggestion:
You can try using MeshLib function for extracting sections
MeshLib/source/MRMesh/MRExtractIsolines.h
Lines 15 to 16 in 5b62b6d
It can cover steps 1-2
(we can workl on it to make it faster if need)
Newer versions of OpenGl have Storage Buffer, I think it can be used to somehow eliminate 2nd step, but it will require a lot of research and OpenGl coding, and I am not sure that it will work as expected.
from meshlib.
I have trouble understanding how to work with PlaneSections
. Below you can see my attempt at retrieving the contour lines but they mostly result in invalid geometry trying to follow existing mesh edges. Any ideas what I'm doing wrong?
struct RawPolylineArrays {
float* ContourVertices;
int* ContourLengths;
int ArrayLength;
};
PINVOKE RawPolylineArrays CreateContours( Mesh* mesh, float interval)
{
const MeshPart m = MeshPart( *mesh, nullptr );
Plane3f plane;
std::vector<float> contourCoordinates;
std::vector<int> contourLengths;
Box3f box = mesh->getBoundingBox();
float bottom = box.min.z + interval;
float contoursCount = (box.max.z - bottom) / interval;
for ( size_t i = 0; i < contoursCount; i++ )
{
plane = Plane3f( Vector3f::plusZ(), bottom + (i * interval) );
PlaneSections contours = extractPlaneSections( m, plane );
for ( const SurfacePath& contour : contours )
{
for ( const MeshEdgePoint& point : contour )
{
Vector3f& pt = mesh->points[mesh->topology.org( point.e )];
contourCoordinates.push_back( pt.x );
contourCoordinates.push_back( pt.y );
contourCoordinates.push_back( pt.z );
}
contourLengths.push_back( static_cast<int>(contour.size() * 3));
}
}
RawPolylineArrays result = RawPolylineArrays();
result.ArrayLength = static_cast< int >( contourLengths.size());
result.ContourLengths = contourLengths.data();
result.ContourVertices = contourCoordinates.data();
return result;
}
from meshlib.
This block should be changed
for ( const MeshEdgePoint& point : contour )
{
--- Vector3f& pt = mesh->points[mesh->topology.org( point.e )];
--- contourCoordinates.push_back( pt.x );
--- contourCoordinates.push_back( pt.y );
--- contourCoordinates.push_back( pt.z );
+++ contourCoordinates.push_back( mesh->edgePoint( point ) )
}
Mesh edge point is internal point on edge, ant not its origin
using MeshEdgePoint = EdgePoint;
MeshLib/source/MRMesh/MREdgePoint.h
Lines 8 to 12 in 5b62b6d
from meshlib.
Thanks, this helped solve the issues! It works well now but can't beat the GLSL code on speed. In the top-left corner you can see the measured time in ms. My GLSL routine takes 2-3 ms even for very low interval values. You mentioned there is potential to speed this logic up, how far do you think this could be pushed?
2023-07-19.12-16-13.mp4
from meshlib.
First I would recommend to find sections in parallel
Box3f box = mesh->getBoundingBox();
float bottom = box.min.z + interval;
float contoursCount = (box.max.z - bottom) / interval;
std::vector<PlaneSections> sections(contoursCount);
ParalleFor( sections, [&]( size_t i )
{
plane = Plane3f( Vector3f::plusZ(), bottom + (i * interval) );
sections[i] = extractPlaneSections( m, plane );
} );
size_t coordsSize = 0;
size_t lengthSize = 0;
for ( const auto& s : sections )
{
lengthSize += s.size();
for ( const auto& path : s )
coordsSize += path.size() * 3;
}
std::vector<float> contourCoordinates;
contourCoordinates.reserve( coordsSize );
std::vector<int> contourLengths;
contourLengths.reserve( lengthSize );
for ( size_t i = 0; i < contoursCount; i++ )
{
for ( const SurfacePath& contour : contours )
{
for ( const MeshEdgePoint& point : contour )
{
Vector3f& pt = mesh->points[mesh->topology.org( point.e )];
contourCoordinates.push_back( pt.x );
contourCoordinates.push_back( pt.y );
contourCoordinates.push_back( pt.z );
}
contourLengths.push_back( static_cast<int>(contour.size() * 3));
}
}
I think it should inprove performace, also we can improve performance of single extractPlaneSections
call (we will have a look), but I am not sure that it can beat shader. Anyway I think that whole pipeline with calculating label positions can work faster with extractPlaneSections
rather than passing data back and forth and sorting it.
from meshlib.
Something is wrong with the above code. I commented everything out except for this part and it still results in a memory leak and a crash:
Box3f box = mesh->getBoundingBox();
float bottom = box.min.z + interval;
float contoursCount = (box.max.z - bottom) / interval;
std::vector<PlaneSections> sections(contoursCount);
ParallelFor( sections, [&]( size_t i )
{
plane = Plane3f( Vector3f::plusZ(), bottom + (i * interval) );
sections[i] = extractPlaneSections( m, plane );
} );
from meshlib.
Independently of speeding things up, do you have any suggestions on how to generate labels for each contour line?
There will be a user provided spacing
value (float). For each contour, I'd like to get points which are: spacing * 0.5, spacing * 1.5, spacing * 2.5, ... away from the contour start. For each of these points, I'd like to have the corresponding mesh normal vector such that I can orient the label correctly.
from meshlib.
I think it also should be done in parallel for each section:
-
find all points label positions (int the same ParallelFor loop mb). I would suggest finding it as index (index of SurfacePath, index of MeshEdgePoint) of sections (not to write geometry code to find intermediate positions). You can use
tbb::enumerable_thread_specific<T>
for acumulating data in ParallelFor (you can find examples in MeshLib code) -
normal can be found by two functions
MeshLib/source/MRMesh/MRMesh.h
Lines 128 to 130 in 5b62b6d
MeshLib/source/MRMesh/MRMesh.h
Lines 119 to 120 in 5b62b6d
MeshLib/source/MRMesh/MRMeshTriPoint.h
Line 29 in 5b62b6d
from meshlib.
find all points label positions (int the same ParallelFor loop mb). I would suggest finding it as index (index of SurfacePath, index of MeshEdgePoint) of sections (not to write geometry code to find intermediate positions)
I'm not sure I understand this. How should I accommodate for the spacing
value? Should I keep adding individual segments' lengths or is there a better way of finding points located at a specified distance from the beginning of a SurfacePath
?
from meshlib.
We have improved extractPlaneSections
a bit. Hope it will speed up things
from meshlib.
Following your suggestion @Grantim, I have implemented a first prototype of contour label display. It has a very minimal overhead and works as expected:
2023-07-19.22-47-46.mp4
Code below. I'd appreciate if you could have a look and suggest any optimizations.
struct RawPolylineArrays {
float* ContourVertices;
int* ContourVerticesLengths;
int ContourCount;
float* LabelVertices;
float* LabelNormals;
int LabelCount;
};
PINVOKE RawPolylineArrays CreateContours( Mesh* mesh, float interval, bool showLabels, float spacing)
{
const MeshPart m = MeshPart( *mesh, nullptr );
const Box3f box = mesh->getBoundingBox();
const float bottom = std::ceil( box.min.z / interval ) * interval;
const float contoursCount = ( box.max.z - bottom ) / interval;
std::vector<PlaneSections> sections( ( size_t )contoursCount );
ParallelFor( sections, [&] ( size_t i )
{
Plane3f plane = Plane3f( Vector3f::plusZ(), bottom + ( i * interval ) );
sections[i] = extractPlaneSections( m, plane );
} );
size_t lengthSize = 0;
size_t coordsSize = 0;
std::vector<size_t> lengthLookup;
std::vector<size_t> coordsLookup;
for ( const auto& s : sections )
{
lengthLookup.emplace_back( lengthSize );
coordsLookup.emplace_back( coordsSize );
lengthSize += s.size();
for ( const auto& path : s )
coordsSize += path.size() * 3;
}
RawPolylineArrays result = RawPolylineArrays();
result.ContourCount = ( uint32_t )lengthSize;
result.ContourVerticesLengths = new int[result.ContourCount];
result.ContourVertices = new float[coordsSize];
std::vector<std::vector<float>> labelPositions( sections.size() );
std::vector<std::vector<float>> labelNormals( sections.size() );
ParallelFor( sections, [&] ( size_t i )
{
size_t localCoordsStart = coordsLookup[i];
size_t localLengthStart = lengthLookup[i];
size_t j = 0;
size_t k = 0;
std::vector<float> contourLabels;
std::vector<float> contourLabelNormals;
for ( const SurfacePath& contour : sections[i] )
{
float cumulativeDist = 0;
// Add first point manually to avoid if statements in the loop
Vector3f pt = mesh->edgePoint( contour[0] );
result.ContourVertices[localCoordsStart + j++] = pt.x;
result.ContourVertices[localCoordsStart + j++] = pt.y;
result.ContourVertices[localCoordsStart + j++] = pt.z;
for ( size_t l = 1; l < contour.size(); l++ )
{
pt = mesh->edgePoint( contour[l] );
result.ContourVertices[localCoordsStart + j++] = pt.x;
result.ContourVertices[localCoordsStart + j++] = pt.y;
result.ContourVertices[localCoordsStart + j++] = pt.z;
if ( !showLabels )
continue;
Vector3f diff = pt - mesh->edgePoint( contour[l - 1] );
if ( cumulativeDist + diff.length() >= spacing )
{
contourLabels.emplace_back( pt.x );
contourLabels.emplace_back( pt.y );
contourLabels.emplace_back( pt.z );
MeshTriPoint mtp = MeshTriPoint( contour[l] );
Vector3f normal = mesh->normal( mtp );
contourLabelNormals.emplace_back( normal.x );
contourLabelNormals.emplace_back( normal.y );
contourLabelNormals.emplace_back( normal.z );
cumulativeDist = 0;
}
else
{
cumulativeDist += diff.length();
}
}
result.ContourVerticesLengths[localLengthStart + k++] = ( uint32_t )( contour.size() * 3 );
}
if ( showLabels )
{
labelPositions[i] = contourLabels;
labelNormals[i] = contourLabelNormals;
}
} );
if ( !showLabels )
return result;
size_t labelCount = 0;
for ( const auto& l : labelPositions )
{
labelCount += l.size();
}
result.LabelCount = ( int32_t )labelCount;
result.LabelVertices = new float[result.LabelCount];
result.LabelNormals = new float[result.LabelCount];
size_t k = 0;
for ( size_t i = 0; i < labelPositions.size(); i++ )
{
for ( size_t j = 0; j < labelPositions[i].size(); j++ )
{
result.LabelVertices[k] = labelPositions[i][j];
result.LabelNormals[k++] = labelNormals[i][j];
}
}
return result;
}
from meshlib.
Hello, I have a look at your sample and have ideas for minor changes:
- Instead of
const Box3f box = mesh->getBoundingBox();
better useconst Box3f box = mesh->computeBoundingBox();
getBoundingBox
takes cached box from mesh's AABBTree, but if there is no one this function will build it that can be slower than just calculating box directly.
if input mesh does not lose caches and you have some operations that require AABBTree
getBoundingBox
is OK here (extractPlaneSections
does not require the tree)
-
Looks like you calculate
diff.length()
twice: once in if condition and once in else block,length
hassqrt
inside, so it is prefered to avoid excessive calls, better call it once before if statement. -
I think you can use
std::move
here:
if ( showLabels )
{
--- labelPositions[i] = contourLabels;
--- labelNormals[i] = contourLabelNormals;
+++ labelPositions[i] = std::move( contourLabels );
+++ labelNormals[i] = std::move ( contourLabelNormals );
}
or even that way
--- std::vector<float> contourLabels;
--- std::vector<float> contourLabelNormals;
+++ auto& contourLabels = labelPositions[i];
+++ auto& contourLabelNormals = labelNormals[i];
--- if ( showLabels )
--- {
--- labelPositions[i] = contourLabels;
--- labelNormals[i] = contourLabelNormals;
--- }
- I think
std::move
can be used in the last copy block:
size_t k = 0;
for ( size_t i = 0; i < labelPositions.size(); i++ )
{
auto addition = labelPositions[i].size();
std::move( labelPositions[i].begin(), labelPositions[i].end(), result.LabelVertices[k] );
std::move( labelNormals[i].begin(), labelNormals[i].end(), result.LabelNormals[k] );
k += addition;
}
P.S. I am not sure if this changes will have any significant effort on performance, but I think they can.
from meshlib.
I think it is important to understand which part of your code takes most of the time (e.g. profile the code).
If the time of section extraction is still dominating, then we can think about more accelerations there. For example, you can make use of the fact that all planes are parallel to OXY. And instead of extractPlaneSections
call newly added function with custom lambda:
return extractIsolines( topology, [height, &points=mesh.points] ( VertId v ) { return points[v] - height; }, region );
I guess it can save some 15% time more.
More optimizations inside extractIsolines
are possible, but it is important to know whether it is still the most time consuming operation, or we need to switch our focus on other functions.
from meshlib.
Thanks @Grantim, I ported all of your suggestions except for the last move statement. It doesn't compile for some reason.
@Fedr, as you can see below, extractPlaneSections
is still the biggest offender here:
extractPlaneSections: 4.4159 ms
rest: 0.2735 ms
labels: 0.0247 ms
Could you please provide a sample on how to use the extractIsolines
function in this context?
from meshlib.
Instead of
Plane3f plane = Plane3f( Vector3f::plusZ(), bottom + ( i * interval ) );
sections[i] = extractPlaneSections( m, plane );
please try the following code:
sections[i] = extractIsolines( m.topology,
[height=bottom + ( i * interval ), &points=m.points] ( VertId v ) { return points[v] - height; } );
from meshlib.
from meshlib.
I pulled the latest source but still get these error messages:
from meshlib.
Oh, sorry, please add .z
:
sections[i] = extractIsolines( m.topology,
[height=bottom + ( i * interval ), &points=m.points] ( VertId v ) { return points[v].z - height; } );
from meshlib.
Now it worked. Here are the results:
extractPlaneSections: 4.249 ms
rest: 0.5207 ms
labels: 0.1264 ms
There is no noticeable difference. If anything it seems to be slightly slower than the previous method.
from meshlib.
Today we added one more function in MeshLib:
/// extracts all sections of given mesh with the plane z=zLevel;
/// this function works faster than general extractPlaneSections(...) for the same plane
/// if the sections cross relatively small number of mesh triangles and AABB tree has already been constructed
[[nodiscard]] MRMESH_API PlaneSections extractXYPlaneSections( const MeshPart & mp, float zLevel );
Please give it a try, it might accelerate contour lines extraction from your terrain, if the conditions in the comment are met ( 1. most plane sections are relatively small and 2. cached AABB tree is typically available).
from meshlib.
Related Issues (20)
- VSCode Autocompletion of `.so` files HOT 6
- line self-intersection HOT 2
- Local setup HOT 5
- Error while showing numpad keys in F1 menu
- Negative offsetting in offsetMesh HOT 1
- Negative offset in thickenMesh results in incorrect filling of mesh HOT 3
- Readme installation steps are incorrect for Linux HOT 4
- Installation on Linux when sudo privileges are not available HOT 1
- Python Meshlib DistanceMap Interpolation Issue HOT 2
- meshlib.mrmeshpy.uniteCloseVertices does not exist in Python HOT 4
- Plane cut HOT 2
- Minkowski Sum in python HOT 2
- Problems in refine in cylinder mesh HOT 1
- add possibility to support rectangular planes
- setup z scale as ( ScaleX + ScaleY ) / 2 for plane feature HOT 1
- Creating grid meshes based on arbitrary shape input HOT 29
- Create a 3D Mesh from a list of vertices and faces. HOT 3
- Hole & Boundary edge length in Python HOT 5
- The Angle between two vectors is 0 to pi, why not 0-2pi HOT 4
- ImportError: libpython3.11.so.1.0: cannot open shared object file: No such file or directory HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from meshlib.