Frustum.intersects with Polygon and Polyhedron about silenceengine HOT 9 CLOSED

I don't understand what you are trying to say Kai, what I'm trying to do with these is to only render the visible entities in the scene. So I get the frustum, and I check if the polygon or polyhedron intersects, that is, at least one vertex of the collision shape is inside the frustum volume.

public boolean intersects(Polygon polygon)
{
    boolean intersects = false;

    Vector3 temp = Vector3.REUSABLE_STACK.pop();

    for (Vector2 v : polygon.getVertices())
    {
        temp.set(v.x, v.y, planeNear.z).addSelf(polygon.getPosition(), 0);

        intersects = isPointInside(temp);

        if (intersects)
            break;
    }

    Vector3.REUSABLE_STACK.push(temp);

    return intersects;
}

I was checking every vertex, and if one vertex intersects the frustum, I simply break the loop and say that the polygon is intersecting. Could you please elaborate what you mean? Do you mean that I should first assume that it is intersecting and check if there was a vertex that does not intersect, like the SAT test?

from silenceengine.

I mean, provided the following two statements:

• A: there exists a polygon's vertex which is inside the view frustum
• B: the polygon is visible

then the following holds:
A -> B
while the reverse is not! true:
B -> A (this is a false implication)

Or in other words: A polygon can still be visible even if no vertex is inside the frustum, because the frustum cuts one or more faces of the polygon, while at the same time not containing a vertex of it!

from silenceengine.

Okay I'd like to clarify it a bit, in this engine, a polygon has only one face, it is a 2D shape, where as a polyhedron is a 3D shape. So it is not possible for the polygon to be visible when there is no vertex inside the frustum.

But that can happen with Polyhedrons as you said, since they have many faces, so how should I be dealing polyhedrons in this context? I see that this may only happen in 3D, as 2D is just flat.

from silenceengine.

It can still happen with 2D shapes, even if they are oriented or axis-aligned.
Just imagine a large (even axis-aligned) square where no vertex is inside the view frustum, but the camera still looks at it.
Have a look at the first picture in this post: http://manski.net/2011/05/rectangle-intersection-test-with-csharp/
(imagine your view frustum being the red oriented rectangle and the polygon to test being the green axis-aligned rectangle)
There you see that the frustum (the red rectangle) does not contain any of the green rectangle's vertices, but green is visible.

from silenceengine.

About how to solve this: I think this is far from being easy.

Some academic papers discuss algorithms for doing this.
In the 2D case, you essentially need to look for solutions of the problem "rectangle polygon intersection", where your view frustum can be thought of as a rectangle.

In the 3D case it is much more elaborate, and I think we reach into the realms of physics engines here.
Might have a look at Bullet's code of how they solve "convex polyhedron and polyhedron intersection" tests, or if maybe that can be simplified a bit to account for the frustum's near and far planes being parallel.

Or you make it simple and do a conservative test by building the axis-aligned bounding box of a polyhedron and then say, if the AABB is visible, well then the polyhedron is also visible.

from silenceengine.

I really can't see that to occur, I mean, even if the shapes are rotated, the vertices of the shape are also rotated, they are no longer the original vertices. So I'm always checking the vertices which I directly pass to the shaders.

Assuming the view itself is rotated, in 2D it's only rotated on the Z axis. And then, the frustum planes are updated too, as I'm using proj * view as the frustum matrix. Even then, the checking is right, if a vertex is in view, then the whole polygon should be rendered.

Now considering the case of 3D, it can be rotated on any axis, and also the vertices of the polyhedron are. So assuming that one face just coincides exactly with a plane (it can't be coinciding with every other plane), there are two cases. If it intersects with any other plane, then it is completely rendered, and if not, it is completely discarded. Since a plane is the edge of the visible volume, I think that is completely fine.

And I do convex polyhedron vs polyhedron collisions in this engine, I use the SAT algorithm in both 2D and 3D. I will do a test with how this renders with Blox (the 3D game I'm making with this engine) as it has very large levels which will only be partly visible.

from silenceengine.

I know that you always would of course check the finally transformed vertices. And of course would you also update the frustum's planes if the camera rotates.
Have you looked at this image, which I posted above? http://manski.net/2011/05/rectangle-intersection-test-with-csharp/
(imagine your view frustum, with updated frustum planes and everything, being the red oriented rectangle and the polygon to test being the green rectangle, also with fully final transformed vertex positions, of course)
There you see that the frustum (the red rectangle) does not contain any of the green rectangle's vertices, but green is visible.

from silenceengine.

Okay, I get it now. Maybe it is better if I could check for every plane of the polygon with every plane of the frustum. I'll now try to find a way around this, maybe assuming the frustum as a collision volume. Thanks for pointing this out.

from silenceengine.

This issue is now fixed. I took JOML for reference in calculating the frustum corners, so thanks Kai for implementing that into JOML.

from silenceengine.