vtkBlockSortHelper needs more documentation
vtkBlockSortHelper could use more documentation. Here is some text etc that may help.
vtkBlockSortHelper is a helper class designed to sort blocks into back to front ordering as is typically required for correct translucent object compositing. This can be a tricky problem which in the general case may not have a solution without changing the underlying geometry (such as with three translucent triangles that each overlap one other triangle and are overlapped by one other). This class will not modify the geometry but tries to produce an ordering that will work. One approach would be to use the distance from camera to block center but this can produce incorrect orderings. Consider the example below
assume the blocks A and C are the same in both cases and only block B is changing. The correct rendering order between A and C can only be determined with knowledge of block B's geometry. Using centroids (or closest point to camera) would not work. This class is designed to handle the case above, but does not handle the case of fully disconnected blocks.
The basic algorithm is as follows
- put all blocks into the working vector
- loop over the working vector -> it
- loop over the working vector -> it2
- compare it and it2 where the results can be -1 first closer, +1 second closer, 0 unknown order
- if no value of it2 is in front of it then we know it is the front-most of what is remaining in the working vector, so add it to the results vector and remove it from the working vector and restart, otherwise move to the next it
- loop over the working vector -> it2
- reverse copy the result vector to get back to front ordering and return
The comparison operator is critical to this working correctly and works as follows
- compute the projection of block A onto block B
- compute the projection of block B onto block A
- determine the dimensionality of the projection
- 3 dimensions overlap = volume
- 2 dimensions overlap = plane
- 1 dimension overlaps = line
- 0 dimensions overlap = no overlap
- for 3 dimension overlap take the two largest dimensions and use them to collapse down to a 2d overlap
- for 1 or 0 dimensions of overlap that means the two blocks cannot share a surface so return 0 = unknown ordering
- compute the distance between the two projections, if they are not adjacent then return 0 = unknown ordering
- at this point we have a shared plane where the two blocks touch, we compare this plane to the camera model to determine which side of the plane is in front, and return -1 or +1 based on which block is on the front side of the plane
So this algorithm works only when all the blocks are connected at least transitively to each other by some amount of face connectivity. The drawing up above also shows why the comparison operator cannot determine a correct ordering of A and C without knowledge of B (or in more complex cases many intermediate blocks).
There are other ways to write this algorithm (such as providing the working set to the comparison operator) which would yield the same results.
It is also possible to improve this helper to handle disconnected blocks to varying degrees. Such as
- examine the blocks and break them into a vector of vectors of connected blocks (each vector only contains face connected blocks)
- Sort each vector of connected blocks as is currently done
- compute the overall bounding box of each vector
- sort the vectors based on their bounding boxes using the same algorithm but without the requirement that the blocks must be touching. e.g. you could just define the plane as the mid-point on the line connecting the centers of the two blocks that is perpendicular to the line.
There are other completely different approaches as well. You could convert all the blocks into 2d hexagons with z values corresponding to camera depth and then do some sort of ordering from that, etc.