finding triangles of a mesh that are visible from a point

Question

Im trying to implement a subroutine for finding all triangles of a 3D-convex-mesh that are visible from a point without iterating over all triangles but only using connectivity of triangle with it's neighbors, mesh always has the first triangle that is visible.

I could only think of recursive methods e.g.

struct trn
    vec3 vertices[3]
    vec3 normal
    trn* neighbors[3]
    bool checked = false

func(vec3 p, trn* t, trn* output[], uint size)
    t->checked = true
    for n in t->neighbors
        if n->checked
            continue
        if dot(n->normal, p - n->vertices[0]) > 0.0
            output[size] = n
            size++
            func(p, n, output, size)

but recursive methods are slow, and this routine should be faster than iterating over all triangles.

Is there any idea or method solving this without recursion?

Thanks.

Is there a reason besides performance to traverse the mesh using connectivity? Because if performance is the main reason, I'd suggest to explore just a linear complexity algorithm which checks all triangles instead against an efficient data representation. It's very reasonable (not even amazing) on today's average sort of hardware to be able to cull hundreds of millions of triangles or more per second just checking every single triangle normal (especially if the triangle normals and vertex positions are stored in a parallel array) in CPU (I've done this a number of times). — , Nov 29 '18 at 08:26
The tricky part with traversing the mesh through a connectivity fashion even if it results in a fraction of the algorithmic iterations is that you're basically accessing memory in a very sporadic and random-access pattern, and on top of that the connectivity data often doubles the amount of memory that needs to be loaded as well as introducing a boatload of indirections. That's quite a hefty cost in terms of memory access even if the algorithmic complexity is reduced -- I'd still tend to avoid connectivity traversal as an optimization unless we're talking about reducing like [...] — , Nov 29 '18 at 08:33
[...] a quadratic complexity algorithm to linear time or something of this sort (an exponential reduction in algorithmic complexity). If you still want to traverse it in a connectivity fashion regardless for whatever reason, one thing I'd suggest is to check multiple points/cameras for backface culling at once instead of one point/camera at a time if possible. That'll increase the amount of work done per triangle to kind of compensate for the extra cost of the connectivity traversal. — , Nov 29 '18 at 08:34
@TeamUpvote: backface culling is linear in the number of faces whatever the way to enumerate the faces. And the fraction of visible faces over the back ones is very close to 0.5. So absolutely no gain in asymptotic complexity is possible, and graph traversal will be a pessimisation. — , Nov 29 '18 at 09:12
@TeamUpvote: another reason for using connectivity is it allows me to find not only faces that are visible, but edges that separate visible and invisible part of a mesh more easily, but iterating over all triangles i have to check for every edge of every triangle if inverted-edge (inverted because of CCW-winding) is in the list if so i should delete it otherwise i should add it — nulladdr, Nov 29 '18 at 10:04
@scicyb Even with the branching per triangle, I think you still have a good chance of beating a connectivity/graph traversal with a straightforward sequential memory access pattern through an array of triangles. That's not to put aside sophisticated graph traversal algorithms when they do offer a significant reduction in algorithmic complexity, but it's worth considering that you can crunch through triangles almost like pixels in an image with a tight enough rep -- easily hundreds of millions of triangles/sec in the same way simple image processing algorithms blaze through [...]. — , Nov 29 '18 at 15:08
[...] hundreds of millions of pixels/sec. It's something to keep in mind at least, perhaps if not for this particular problem if you're really set on graph traversal. Sometimes the seemingly dumb but very cache-friendly memory access pattern can rather astonishingly outperform graph traversal (which generally doesn't provide the most cache-friendly memory access patterns -- though see "Linear-Speed Vertex Cache Optimisation") unless the latter is like an exponential reduction (linear to logarithmic, quadratic to linear, etc). — , Nov 29 '18 at 15:14
@scicyb: my answer addresses that. There is an O(√F) solution. It seems that you asked an XY question. — , Nov 29 '18 at 15:18
It's a sort of mistake I used to make often earlier in my career (not saying your solution is a mistake, but at least I made this type of mistake a lot). A prominent example was one where I needed to raycast and deform triangles that intersected a ray within a certain proximity (used geodesic distance). That particular case benefited substantially from graph traversal since I could cease to broaden the graph traversal once a certain geodesic was reached. I was finding there that I could check something like tens of thousands of triangles instead of millions, hurray! Except when I finally [...] — , Nov 29 '18 at 15:20
... tried the really dumb but straightforward solution of iterating through all the triangles in the scene and just using basic euclidean distance, I was still outperforming the graph traversal even though I was checking millions of triangles instead of tens of thousands, e.g. So that came as quite a eureka moment for me and I started to appreciate that kind of ability for the hardware to sequentially plow through data when the memory access patterns are friendly to the hardware. — , Nov 29 '18 at 15:22
@YvesDaoust: as you sad an O(√F) solution doesn't tell which faces are visible and question was completely opposite — nulladdr, Nov 29 '18 at 16:03
@scicyb: I was referring to your discussion with TeamUpvote. — , Nov 29 '18 at 16:06

score 0 · Answer 1 · 2018-11-29T09:29:42.567

This looks like a very wrong idea.

Because

you'll have to visit all the triangles anyway (at least all the visible ones, see below);
connectivity alone is not sufficient; a geometric test is required anyway to take the position of the viewing point into account.

Whatever you do, the complexity has to be linear in the number of visible faces, which is also linear in the total number of faces, and you will trade a straightforward loop on the faces for a complicated graph traversal plus the same amount of geometric work. My bet is a slow down by a factor five or so.

If your surface is convex, the front and rear faces are separated by a continuous contour line. Starting from a visible face, you can "fill" the contiguous faces until you reach that separating line, using a seed fill procedure in the graph. This way, you needn't traverse the rear faces (or just those in contact with the separating line).

This is in fact the method that you describe. Seed filling is essentially a recursive procedure. You can simulate recursion with a local stack, but that will provide no speedup (merely avoid a stack overflow).

There is no way to avoid recursion for a good reason: when you fill the domain from face to face keeping connexity, you can very well end-up with the unfilled area being disconnected. No traversal order can avoid that, and it means that at some stage several regions will have to be filled independently and you need to keep a trace of them. That requires some storage and a backtracking process.

Note also, that on a convex body, there are about as many front faces as rear ones, and the benefit of skipping half of them is largely compensated by the cost of graph traversal and filling.

And if the surface is concave, you may need several starting faces (which I doubt you can efficiently find), as there can be several contours.

Final remark: in the case of a convex surface, you can maybe find the separating contour by starting from the initial face, marching in a direction opposite to the viewing point until you reach some border face and following the contour by tracking the separating edges. The number of faces to visit will be roughly proportional to the number of faces seen during the march to the first contour face, plus the contour length.

For a mesh of F faces, the workload will be of order O(√F). But this still doesn't tell you which are the visible faces.

finding triangles of a mesh that are visible from a point

1 Answers1