The output of the frustum culling algorithm should be a list of visible objects. These objects are then processed further (for example, some of them will be rendered).
However, we can't say what an "object" is, yet. Since frustum culling tests visibility, an object has to be something that has an extent (a bounding box). We currently have two structures that meet these requirements:
Meshes: They have an AABB that can be calculated from their prototype's AABB and their transformation matrix (so their rotation, scaling, translation)
Lights: Although not directly visible, we have to cull lights to save performance. To do that, their "influence" has to be measured via an AABB. For point lights, this is the AABB enclosing the sphere in which they still emit some light. Directional lights are always visible (they're not part of frustum culling) and spot lights have a well-defined cone that has an AABB (although it's difficult to calculate).
So essentially, an object is a variant<mesh,light>. This is what's stored in the bounding volume hierarchy, and we can define a function that returns a AABB for this variant (as in rect get_aabb(variant<mesh,light>) { ... }). However, since the bounding volume hierarchy doesn't cache the bounding boxes, making a (fairly complex) function call each time we want to access the AABB isn't wise. Also, we don't want to store the meshes and lights directly, just references to them. Taking thsi into consideration, we define a node in the tree as:
typedef
pair<variant<mesh&,light&>,rect>
node;
This way, we can easily access the rectangle, and care about the underlying object type later (later, instead of adding new types to the variant, we might have a base class; the variant is then replaced by "object::base &").
The scene::manager gets the whole scene in the ctor (via the scene's prototype class), so it's possible to build the bvh in the constructor as well. (For dynamic scenes, we have to build the bvh each frame or use some clever mechanism to detect changes). We create the nodes and the AABBs and insert them to the tree.
The culling algorithm
To implement culling, we need to traverse the bvh tree representation and throw away nodes that are outside all frustum planes. So we need a function to extract the frustum planes from the projection matrix. TODO:
Extract frustum planes from projection matrix (I already have that, but for a right-handed coordinate system - does that matter?)
Write "intersection" test AABB <-> plane
Traverse tree representation, produce list of node structures (see typedef above), or, better yet, just variant<mesh&,light&> structures.
Iterate the resulting sequence, activate lights, construct render list (#65).
Motivation
The output of the frustum culling algorithm should be a list of visible objects. These objects are then processed further (for example, some of them will be rendered).
However, we can't say what an "object" is, yet. Since frustum culling tests visibility, an object has to be something that has an extent (a bounding box). We currently have two structures that meet these requirements:
So essentially, an object is a
variant<mesh,light>. This is what's stored in the bounding volume hierarchy, and we can define a function that returns a AABB for this variant (as inrect get_aabb(variant<mesh,light>) { ... }). However, since the bounding volume hierarchy doesn't cache the bounding boxes, making a (fairly complex) function call each time we want to access the AABB isn't wise. Also, we don't want to store the meshes and lights directly, just references to them. Taking thsi into consideration, we define a node in the tree as:This way, we can easily access the rectangle, and care about the underlying object type later (later, instead of adding new types to the variant, we might have a base class; the variant is then replaced by "object::base &").
The scene::manager gets the whole scene in the ctor (via the scene's prototype class), so it's possible to build the bvh in the constructor as well. (For dynamic scenes, we have to build the bvh each frame or use some clever mechanism to detect changes). We create the nodes and the AABBs and insert them to the tree.
The culling algorithm
To implement culling, we need to traverse the bvh tree representation and throw away nodes that are outside all frustum planes. So we need a function to extract the frustum planes from the projection matrix. TODO:
nodestructures (see typedef above), or, better yet, justvariant<mesh&,light&>structures.Related issues
Issue #72, issue #65.