3D frustum selection

OpenGL OpenGL: Advanced Coding
1

Hi All,

We have just improved our selection algorithm.

Before we did:

  1. project all the triangles on screen
  2. check for pickbox intersection with 2D triangles and for mutual vertex inside (pickbox vertex inside the triangle and triangle vertex inside the pickbox)

The limitation:

In perspective mode, triangles with a vertex behind the viewer got weird 2D coordinates invalidanting the complete selection operation.

New algorithm:

  1. Get a 3D frustum composed by 6 planes
  2. Check first if the object bounding sphere intersects the frustum
  3. In case of intersection, loop over object’s triangles to check if the triangles sides cross the frustum
  4. If no intersection is found, check for ray-triangle intersection for all 4 frustum sides (near to far)

The problem:

Speed. The new algorithm is accurate but slow. Intersection checks for triangles sides and furstum planes and ray-triangle intersections are slow processing a mesh of 50.000 triangles.

Is there any way to speed up the new algorithm?

Thanks,

Alberto

2

Have you tried to use http://sourceforge.net/projects/coldet/ ?

3

idea 1) octrees or any spatial division (rather heavy preprocessing). Coldet does such stuff, I bet.
idea 2) semi-bruteforce asm optimizations. Bounding-boxes and spheres checked against frustum, heavy SSE in SOA arrangement, working in clipspace instead of worldspace. (very light preprocessing, or no preprocessing). 50k triangles can easily be made to take less than 1ms to process.

4

Or use tricks… calculate center for each triangle and project it on screen. Then just search for points instead of whole triangles. This is done in Maya.

In your new algorithm stage 3 looks way too complex. Fist of all, triangles shares vertices, so testing triangle-frustum collision involve testing is vertex in frustum. Use additional memory to cache already tested vertices from surrounding triangles.

You can calc sphere around each triangle (use some quick and dirty calc) and test ray-sphere or frustum-sphere collision. If it fails discard triangle from further test. If it hit then test more with ray-triangle.

Also… depending on your geometry and how its freq. changed, you can use additional memory to store data related to selection and picking.

btw… do you need to pick just one triangle or you need to select multiple triangles with 2D selection rect?

5

yooyo,

Do you mean to check if the triangle center is inside frustum? What if the center is outside the frustum and one vertex is inside?

I was thinking also to compute a connectivity table to test triangles sides only once, but it would take too much time.

Only one, once we get one we select the whole object.

Thanks,

Alberto

6

Maya have one point in triangle center and if that point is in selection rectangle then triangle is selected. This is most simplest and fastest solution, but it require from user to be more precise.

How do you test triangle-frustum intersection? For each triangle vertex check its distance from frustum planes and side (positive or negative distance) and then test edges. Isn’t there too much math?
My suggestion is to calc sphere around whole triangle and then calc distance from sphere center to all frustum planes. If smallest distance is less than sphere radius or sphere center is inside frustum then this triangle could be candidate for ray-triangle intersection. Worst case is when camera is very close to object so triangles becomes huge.

Whole trick is to discard as many triangles as you can using cheapest method before you send them to expensive ray-triangle intersection check.

7

Maya have one point in triangle center and if that point is in selection rectangle then triangle is selected. This is most simplest and fastest solution, but it require from user to be more precise.

Nice idea yooyo, this can be an additional imprecise and more fast approach…