0
$\begingroup$

I have a triangulated surface that I want to work with. In order to optimize certain quantities related to this surface I want to find all points which are accessible from a given direction. To be more precise, let's denote by $S_h$ the surface and by $B$ the body enclosed by $S_h$. Given a direction $\vec d \in \Bbb{R}^3$ I want to find all points $x \in S_h$ such that the semi-line starting at $x$ going in the direction of $\vec d$ does not intersect $S_h$ a second time. An analogue way of saying this is given a direction $\vec d$ I want to find all the points which can be "seen" looking at $S_h$ from that direction.

I have the feeling that this could be something which is known in the field of computational geometry, but maybe I don't know the right terminology in order to find relevant references.

Is there an algorithm which is not too costly to implement in order to find all "visible points" from a certain direction? Do you know references dealing with efficient algorithmical implementation?

$\endgroup$
  • 2
    $\begingroup$ Every computer graphics program has to solve this sort of problem. Have you looked at computer graphics or CGI books? Specifically, I believe that that's what the Z-Buffer is used for. $\endgroup$ – Wolfgang Bangerth Mar 11 '18 at 1:48
  • $\begingroup$ It's called "backface culling" or "occlusion culling". A simple alternative could be to "iterate" through all vertices or triangles and verify that the angle between the surface normal and the view direction is less than 90 degrees. $\endgroup$ – André Mar 14 '18 at 10:10
  • $\begingroup$ @André: Thank you for mentioning the terminology. The version with the angle between the normal and the view direction only works for convex shapes. You can imagine that if a hole is present, looking only at normals may say that some regions are visible, while they are not... $\endgroup$ – Beni Bogosel Mar 14 '18 at 10:11
3
$\begingroup$

As far as I understand, you are looking at some variation of ray tracing algorithm. Such problems will be very common for geometrical optics to determine the direct line of sight. Example:visible surface ray tracing (ray casting)

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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