11
$\begingroup$

enter image description here I have 3 vertices (V1, V2, V3) randomly selected on a regular triangle mesh. For these 3 vertices, I have computed the geodesic distance and the path (by using Dijkstra) among them and formed a triangle-like surface as in the above figure.

Now, I have the vertices that lie in each path and can compute geodesic distances from a given vertex.

What I want to do is to get the vertices or triangles that lies in triangle-like area. How can I do this?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Assuming that barycentric approach does what I think it does it would be quite slow with large sets. Imagine a set of 9 million vertices with only 9 vertices in the desired set. Why iterate the entire set when v1, v2, and v3 give you all the information you need. The flood fill answer would be the fastest flexible solution. Although unflexible, if you can assume you have lines like you do now in the geometry then scanline would be the fastest approach. $\endgroup$
    – Andrew Wilson
    Commented Jul 19, 2017 at 5:25
  • $\begingroup$ You're absolutely right about performance issues. I'd like to use this approach in large meshes, so what I'm looking for is an efficient method. Actually I'm not familiar with neither flood filling nor scan fill algorithms, I'll take a look at them. Thanks. $\endgroup$
    – mkocabas
    Commented Jul 19, 2017 at 5:52
  • 3
    $\begingroup$ A flood fill with a graph would start at a node, visit every neighbor node if boundary condition is met and not visited, mark it as visited, and repeat (recursion). Alteration: mark every node on path as visited and start from a node inside the set. Then simply use the visitation check as the boundary condition. $\endgroup$
    – Andrew Wilson
    Commented Jul 19, 2017 at 7:00
  • $\begingroup$ Thanks for the detailed explanation. I find flood filling algo more reasonable, but I want to implement both flood fill and scan line, then compare the performances. $\endgroup$
    – mkocabas
    Commented Jul 19, 2017 at 8:09

3 Answers 3

Reset to default
4
$\begingroup$

There is an alternative method that relies on flood filling. First arrange your edge data into a loop where the edges are forming a counterclockwise loop. Then start at an arbitrary point on the loop and pick edges joining that point. Use the outbound boundary edge and cross it with the other outbound edge, if it points in the direction of the face normal then it's an edge to be included, if not discard it. From this edge continue until you hit a boundary edge, at which point you terminate the fill. Continue at a yet to be visited boundary edge vertex.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm not familiar with flood filling algorithm. Your explanation seems a little complicated to me. Could you please provide a decent reference to look at? Thanks. $\endgroup$
    – mkocabas
    Commented Jul 19, 2017 at 5:47
3
$\begingroup$

I've already commented on the use of flood fill and how it would be better as it's more flexible but another possible solution is scanline. (I say possible because it makes a lot of assumptions about your geometry but for the particular set shown and many similar ones it would work.)

For your example with 3 points: Find the intersection vertex from the segment v1,v2 and the line that v3 lies on. (The vertex to the upper left of v2) We'll call this vertex v4. 

For every vertex pair a,b down v1,v4 and v1,v3 
    For every vertex from a to b
        Mark as in the set
For every vertex pair a,b down v3,v2 and v4,v3
    For every vertex from a to b
        Mark as in the set

enter image description here

It's called scanline because (in the image above) you go down the red and green lines simultaneously and then red and blue lines simultaneously scanning the lines in as you go.

This solution would be very fast if there is an index pattern, which is often the case. Otherwise a calculation would be needed to determine which neighboring vertex lies on the line.

Funny thing is scanline, barycentric testing (in triangle bounding box), and flood fill are all ways of drawing triangles in 3d rendering.

Improve this answer
$\endgroup$
2
$\begingroup$

I think you can calculate some surface-bound barycentric coordinates for each point on the surface, and then use them to check for inside or outside of the triangle.

I don't have an exact algorithm at hand but I found this following paper which does seem to handle exactly this kind of coordinates.

Barycentric Coordinates On Surfaces

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer and reference paper. I will try to implement the method proposed. $\endgroup$
    – mkocabas
    Commented Jul 18, 2017 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.