I want to be able to determine if OBBs or Triangles intersect a Frustum. Specifically, in my case, it is for selection. So I need the result to be accurate, as opposed to some rough frustum culling approximation.

I've done a bit of research, and a lot of the algorithms I have found simply test to see if all the points of the geometry are on one side of any frustum plane, if so, they assume it is outside of the frustum, else it is inside (or intersects). But this doesn't seem to really work, as you can quite easily have points that are all outside the frustum, but are not all on any one side of a frustum plane.

I have seen other techniques where they do the above test first, and then they flip the test around and use the OBB planes to then test the frustum points. I assume this will also work with the triangle case? and that I just test the plane of the triangle with the normal being rendered (if back face culling is enabled)

Or should I do these calculations in 2D space? so transform the points by the ViewProj matrix, and use SAT (something I am not familiar wih yet) to test for intersection of the OBB points in NDC space and the triangle points in NDC space?

There is always a plane on which one side all points are if the OBB does not intersect the frustrum.

There is this: https://www.iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm (never tried myself)

2D idea would still lack for front / back planes.

What would work for sure is to have a polygon clipping routine, then clip with every frustum plane. If something remains it's inside.

JohnnyCode said:

There is always a plane on which one side all points are if the OBB does not intersect the frustrum.

https://cesium.com/blog/2017/02/02/tighter-frustum-culling-and-why-you-may-want-to-disregard-it/

JoeJ said:

There is this: https://www.iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm (never tried myself)

2D idea would still lack for front / back planes.

What would work for sure is to have a polygon clipping routine, then clip with every frustum plane. If something remains it's inside.

I could check if the NDC Z is within 0-1 for the front back planes could I not?

I have thought about it and I can't see why your approach with the OBB planes and the triangle wouldn't work. I don't think you need to do the test in 2D though.

binder2 said:

JoeJ said:

There is this: https://www.iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm (never tried myself)

2D idea would still lack for front / back planes.

What would work for sure is to have a polygon clipping routine, then clip with every frustum plane. If something remains it's inside.

I could check if the NDC Z is within 0-1 for the front back planes could I not?

I guess there is a problem with vertices ending up behind the eye point of a perspective projection. Anything that tries to 'un'transform geometry so the frustum becomes a cube for easy testing might mess up the geometry in this case?

The clipping approch isn't that bad, here an example poly clipping function:

[code]

inline int32_t ClipTexmapPolygon (const TexmapPolygon *pin, const vec &plane, TexmapPolygon *pout, const int32_t space)

{

if (pout->numAvailableVertices < pin->numVertices + 1)

pout->Resize (pin->numVertices + 1);

int32_t i, curin, nextin;

float curdot, nextdot, scale;

TexmapPolygon::Vertex *pinvert, *poutvert, *nextvert;

pinvert = pin->vertices;

poutvert = pout->vertices;

curdot = pinvert->puv[space].Dot (plane);

curin = (curdot >= plane[3]);

int32_t ret = -1; // assume inside

for (i=0; i<pin->numVertices; i++)

{

nextvert = &pin->vertices[(i+1) % pin->numVertices];

// keep if inside

if (curin)

{

*poutvert++ = *pinvert;

}

nextdot = nextvert->puv[space].Dot (plane);

nextin = (nextdot >= plane[3]);

if (curin!=nextin) // add clipped vertex if plane splits edge

{

assert (fabs(nextdot - curdot) > FP_EPSILON);

ret = 1; // clipped or outside

scale = (plane[3] - curdot) / (nextdot - curdot);

for (int32_t c=0; c<3; c++)

poutvert->puv[c] = pinvert->puv[c] + (nextvert->puv[c] - pinvert->puv[c]) * scale; // puv[3]: {position, uv channel 0, uv channel 1}

poutvert++;

}

curdot = nextdot;

curin = nextin;

pinvert++;

}

pout->numVertices = int32_t(poutvert - pout->vertices);

if (pout->numVertices < 3) return 0; // outside

return ret;

}

[/code]

This approach does not test against planes but coordinates (first near/far, then x/y). Would it solve the problem of false positives ?

http://www.lighthouse3d.com/tutorials/view-frustum-culling/radar-approach-testing-points/

Green_Baron said:

This approach does not test against planes but coordinates (first near/far, then x/y). Would it solve the problem of false positives ?

http://www.lighthouse3d.com/tutorials/view-frustum-culling/radar-approach-testing-points/

The link doesn't work for me:

You don't have permission to access this resource.Server unable to read htaccess file, denying access to be safe Additionally, a 403 Forbidden error was encountered while trying to use an ErrorDocument to handle the request.

I don't think testing points instead of planes helps. I don't see what's wrong with the original approach, it should work.

Alternatively, just render the scene to a 32 bit uint render target and give each element a unique index and then just read the texture. This way you won't select things that are behind another thing.

The link did work yesterday, looks like there is a problem on that site now ...

The approach is reportedly more efficient than the plane checks, it is described in more detail "Game Programming Gems 5" and the lighthouse3d site had a tutorial page about it. It should imo work better, as near/far check leads to an early out.

Maybe it helps, it should eliminate the case of points lying inside of the planes but behind or in front of the near far planes as shown in the example. But i must admit i have never implemented the plane check version of frustum culling.

(The tangens is only computed on projection matrix changes and stored in the frustum object)

intersect_t ViewFrustum::isPointInFrustum( const omath::dvec3 &point ) const {
    // compute vector from camera position to p
    omath::dvec3 v{ point - m_cameraPosition };
    // compute and test the z coordinate
    double pcz{ omath::dot( v, m_z ) };
    if( pcz > m_farD || pcz < m_nearD )
        return OUTSIDE;
    // compute and test the m_y coordinate
    double pcy{ omath::dot( v, m_y ) };
    double aux{ pcz * m_tangensAngle };
    if( pcy > aux || pcy < -aux )
        return OUTSIDE;
    // compute and test the m_x coordinate
    double pcx{ omath::dot( v, m_x ) };
    aux *= m_ratio;
    if( pcx > aux || pcx < -aux )
        return OUTSIDE;
    return INSIDE;
}