MatthewsSam
commented
7 years ago Preprocessing, step #1 (any space partitioning technique)
- Prepare the space partitioning by chopping the static scene into sectors (trivial for regular grid, a little complicated for a quadtree, more complex for a graph)
- Assign all triangles of the static mesh to a single sector
- If a triangle overlaps many sectors, pick just one
Preprocessing, step #2 (any space partitioning technique)
- For each sector, we want to build its "visibility list" to all other sectors
- Shoot millions of rays (ray tracing) from uniform/random points within the sector
- Each ray origin should be tested to ensure it's "inside" the visible region of the sector (not under the
ground or in a mountain)
- If a ray first hits a back-facing triangle, its origin was inside something (targeting a random nearby triangle is a valid strategy, we have no usable information if the ray doesn't hit anything)
- Each ray origin should be tested to ensure it's "inside" the visible region of the sector (not under the
ground or in a mountain)
- Trace a ray for each valid origin:
- Check what other sectors it traverses prior to intersection (add sector to visibility list if not present)
- Resolve the (first) triangle intersected by the ray (add the triangle's sector to visibility list if not present)
- To ensure the visibility of large dynamic objects, rays only passing "close" to a sector should still add it
to the visibility list (rays passing within the maximum radius of dynamic objects)
- Some sectors of the visibility list can be flagged "dynamic objects only", to reduce wasteful drawing
Drawing algorithm
- Obtain the list of visible sectors from the camera's current sector (preprocessed above)
- Test each visible sector against the frustum, discard if not visible
- Sort the remaining list of sectors front-to-back (to reduce overdraw)
- Group together all the geometry requiring the same shaders and/or textures (to reduce GL state change)
- Draw all the opaque geometry, the sectors and all the objects they contain
- Ideally, figure out the proper balance of front-to-back sorting (reduce overdraw) and batching (reduce GL state change)
- Draw all the transparent geometry, the sectors and all the objects they contain (sorted back-to-front)
Object management function/methods
AddObjectToScene()
- Resolve in which sector the object resides
- Add the object to the resolved sector
- The object tracks/remembers its host sector
RemoveObjectFromScene()
- Remove the object from its host sector
MoveObjectInScene()
- Remove the object from its host sector
- Resolve the new sector for the object
- Add the object to the resolved sector
- The object tracks/remembers its host sector
Benau
deveee
won't bloat stk-code for little to no gain for now
Our render engine uses currently a scene manage which stores all objects in lists. While it was acceptable a few years ago, now due to the complexity of tracks the system needs something better.
To reduce the amount of polygon rendered we can separate the scene in objects and then compute the visibility of each objects. However, the current system must iterate the whole list at each frame in order to determine the visibility of an object which slows down when the scene have a lot of objects.
I talked about this issue in the opengl chan on freenode and a dev kindly wrote a roadmap describing what would need to be changed.
An overview of different systems of managing the scene
Space partitioning, multiple possibilities (pick one!)