Front/back Triangles of the selected region

OpenGL OpenGL: Advanced Coding
1

Suppose I have a mesh, I select the rectangle region using the mouse. How can I get the triangles of the mesh,which are inside four corners of rectangular region and also triangles which are occluded behind the rectangular region.

I need triangles which are both completely inside the region and those intersecting the region.

PLease help.Thanks in advance.

2

Use the projection and view matrix to turn your window space rectangle into a world space frustum. Then use each objects model matrix to turn the world space frustum into a model space frustum.
Iterate over all triangles in the current object and test them against the planes of the frustum. Triangles that are inside all six half spaces are inside the frustum (this gives you triangles fully inside the frustum).
For triangles that are partially inside the frustum you could test if at least one triangle vertex is inside, but that won’t cover all cases. One alternative that is more precise is to intersect the triangle edges with the frustum planes and check if the intersection point is inside the frustum.

3

If you are testing vertices only against the frustum you might want to use glProject to project them and test them in window coordinates instead of doing it all by hand.

4

Thanks. So it is going to be brute force algorithm


for each triangle in the mesh
  for each edge in this triangle
     for each plane in  the frustum
        Intersectionpoints = FindIntersection(plane,edge); 
     end
     for each plane in the frustum
        TestInsidePointInsidePlane(plane,Intersectionpoints);
     end 
  end
end

Are there any optimization strategies.

5

Since it seems that you do not want to test against the near and far planes but select the triangles regardless of distance from the camera position i would really try and do it in 2d.

Just glProject every triangle vertex and test it against the selected rectangle in screen/window coordinates. This has the advantages that

  • most likely you get the 2d-rectangle corners free (mouse click positions) and need not to compute plane equations
  • your projected vertices can be tested agains axis parallel rectangles and you only have to test for x_min <= vertex_x <= x_max and the same for y instead of evaluating four plane equations per vertex (saves 3 mults and 3adds per vertex)

Also for testing edges against a 2d rectangle you could use the simple and efficient Cohen Sutherland algorithm (see wikipedia)… but if it is worth implementing might depend on your geometry.