PDA

View Full Version : Front/back Triangles of the selected region



iris_raj
08-09-2011, 11:05 PM
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.

carsten neumann
08-14-2011, 02:53 PM
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.

_x57_
08-16-2011, 03:48 AM
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.

iris_raj
08-16-2011, 08:59 AM
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.

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,Intersectionpoint s);
end
end
end

Are there any optimization strategies.

_x57_
08-17-2011, 05:39 AM
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.