Projecting a line segment onto a polygon mesh

1
votes

I am working on a 3d application and am currently looking for a way to project a line segment defined by two points in screen-space onto a three-dimensional polygonal mesh (in my case a triangle mesh). The goal is to find the intersection points in world-space of the line segment with the edges of the mesh.

I can only think of two ways to do this, but neither is ideal. The first is to sample the line segment (in screen-space) at small intervals and ray trace at those intervals to find the world-space coordinates where the ray hits the mesh, but this does not easily give me the intersection points of the line segment with the mesh edges.

The other way I can think of is to somehow back-project the mesh into screen-space, find the intersections there (in 2d) and then project those intersection points back to 3d. The problem with this is that the screen-space coordinate system may change between the selection of the first and second endpoints of the line segment (due to moving the camera).

If any of that was confusing, then here is an image that approximately shows what I'm trying to do (the white dots indicate the points that I want to find). However, in my case the yellow curve is simply a line segment.

enter image description here [Yunjin Lee, et al. "Mesh scissoring with minima rule and part salience." 2005]

Any help is very much appreciated.

1
graphics3dgeometrycomputational-geometryprojection
Can you project the screen line into a plane in world space and then intersect the plane with the mesh? – Gareth Rees
@GarethRees Yes, that should be possible, but I want to avoid intersections with edges 'on the other side' of the mesh. – mhjlam
Use a Z-buffer-like approach to keep only the front-most intersections. – Gareth Rees
Hm, can you elaborate on that? Do I need to store the two intersections with the mesh at every pixel, then discard the back-most intersections, and then discard the front-most intersections that do not lie on an edge? – mhjlam
It's not necessary to rasterize it. The front-most set of intersections is piecewise-linear so you can represent it as a sorted sequence of points (the points you are trying to calculate, in fact) together with the Z value at each point. – Gareth Rees

1 Answers

1
votes

Here's my suggestion:

  1. Project the screen line into world space (getting a plane in world space).

  2. Intersect the plane with the triangles in the mesh, getting a set of edges.

  3. Add the edges to a data structure that keeps only the parts of the edges that are closest to the camera plane (see the diagram below, in which the red line segments and their endpoints are the ones we want to keep). This is like building up an image via a Z-buffer, except that because we know that this set is piecewise linear, we don't have to rasterize it, we can just maintain a sorted list of endpoints.

enter image description here