CODEWITHSUNDEEP
algorithmgeometrycomputational-geometrymesh
Megidd
Megidd

Reputation: 7962

3D mesh direction detection

I have a 3D mesh consisting of triangle polygons. My mesh can be either oriented left or right:

Direction 0

Direction 1

I'm looking for a method to detect mesh direction: right vs left.

So far I tried to use mesh centroid:

But the problem is that the centroid and b-box center don't have a reliable difference in most cases.

I wonder what is a quick algorithm to detect my mesh direction.

Update

An idea proposed by @collapsar is ordering Convex Hull points in clockwise order and investigating the longest edge:

Upward: longest edge

Downward: longest edge

UPDATE

Another approach as suggested by @YvesDaoust is to investigate two specific regions of the mesh:

Investigating two regions

Upvotes: 0

Views: 447

Answers (2)

user1196549
user1196549

Reputation:

Count the vertices in two predefined regions of the bounding box. This is a fairly simple O(N) procedure.

Unless your dataset is sorted in some way, you can't be faster than O(N). But if the point density allows it, you can subsample by taking, say, every tenth point while applying the procedure.

enter image description here

You can as well keep your idea of the centroid, but applying it also in a subpart.

enter image description here

Upvotes: 1

collapsar
collapsar

Reputation: 17238

The efficiency of an algorithm to solve your problem will depend on the data structures that represent your mesh. You might need to be more specific about them in order to obtain a sufficiently performant procedure.

The algorithms are presented in an informal way. For a more rigorous analysis, math.stackexchange might be a more suitable place to ask (or another contributor is more adept to answer ...).

The algorithms are heuristic by nature. Proposals 1 and 3 will work fine for meshes whose local boundary's curvature is mostly convex locally (skipping a rigorous mathematical definition here). Proposal 2 should be less dependent on the mesh shape (and can be easily tuned to cater for ill-behaved shapes).

Proposal 1 (Convex Hull, 2D)

Let M be the set of mesh points, projected onto a 'suitable' plane as suggested by the graphics you supplied.

  1. Compute the convex hull CH(M) of M.
  2. Order the n points of CH(M) in clockwise order relative to any point inside CH(M) to obtain a point sequence seq(P) = (p_0, ..., p_(n-1)), with p_0 being an arbitrary element of CH(M). Note that this is usually a by-product of the convex hull computation.
  3. Find the longest edge of the convex polygon implied by CH(M).
    Specifically, find k, such that the distance d(p_k, p_((k+1) mod n)) is maximal among all d(p_i, p_((i+1) mod n)); 0 <= i < n;
  4. Consider the vector (p_k, p_((k+1) mod n)). If the y coordinate of its head is greater than that of its tail (ie. its projection onto the line ((0,0), (0,1)) is oriented upwards) then your mesh opens to the left, otherwise to the right.

Step 3 exploits the condition that the mesh boundary be mostly locally convex. Thus the convex hull polygon sides are basically short, with the exception of the side that spans the opening of the mesh.

Proposal 2 (bisector sampling, 2D)

  1. Order the mesh points by their x coordinates int a sequence seq(M).
  2. split seq(M) into 2 halves, let seq_left(M), seq_right(M) denote the partition elements.

  3. Repeat the following steps for both point sets.
    3.1. Select randomly 2 points p_0, p_1 from the point set.
    3.2. Find the bisector p_01 of the line segment (p_0, p_1).
    3.3. Test whether p_01 lies within the mesh.
    3.4. Keep a count on failed tests.

  4. Statistically, the mesh point subset that 'contains' the opening will produce more failures for the same given number of tests run on each partition. Alternative test criteria will work as well, eg. recording the average distance d(p_0, p_1) or the average length of (p_0, p_1) portions outside the mesh (both higher on the mesh point subset with the opening). Cut off repetition of step 3 if the difference of test results between both halves is 'sufficiently pronounced'. For ill-behaved shapes, increase the number of repetitions.

Proposal 3 (Convex Hull, 3D)

For the sake of completeness only, as your problem description suggests that the analysis effectively takes place in 2D.

Similar to Proposal 1, the computations can be performed in 3D. The convex hull of the mesh points then implies a convex polyhedron whose faces should be ordered by area. Select the face with the maximum area and compute its outward-pointing normal which indicates the direction of the opening from the perspective of the b-box center.

The computation gets more complicated if there is much variation in the side lengths of minimal bounding box of the mesh points, ie. if there is a plane in which most of the variation of mesh point coordinates occurs. In the graphics you've supplied that would be the plane in which the mesh points are rendered assuming that their coordinates do not vary much along the axis perpendicular to the plane.

The solution is to identify such a plane and project the mesh points onto it, then resort to proposal 1.

Upvotes: 0

Related Questions