c++ sorting by depth using only a matrix. Possible?

Question

If I have a std::vector of objects containing a rotated / translates matrix, is there a way I can use that matrix to calculate a Z position so that I can sort the objects by depth?

Answer 1

Define the desired ordering and then use std::sort as in this example.

UPDATE BASED ON COMMENT:

The central issue you seem to be asking is how to define the ordering that you use as the basis for the sort. If your objects are single points, then you apply the corresponding transformation (if you haven't precomputed / momoized it) and sort on the Z component of resulting vector.

It becomes more difficult if your objects are comprised of multiple points. In that case you will need to define a suitable surrogate single point location associated with each object that you can then use as the basis for your sort. Since the objects are multi-point in nature, any surrogate single point representation will probably provide poor results under some circumstances. However, if the objects are all simple, planar polygons, that do not intersect each other except along edges or vertices, then you could average each polygon's vertex location to a single point that serves as a suitable surrogate. This method extends well also to non-intersecting convex polyhedra as well. If the objects become too complicated, then you'll either have to decompose them into non-intersecting regular polygons or convex polyhedra and sort those, or accept not always getting it right.

Answer 2

Taking a guess at what you're asking:

If you have a vector of transformation (i.e. 4x4) matrices, then the Z component is in the translation component of the matrix. It should be (row,col) = 2,3 or 3,2 depending on your convention.

E.g:

1 0 0 0  <-- x position
0 1 0 0  <-- y position
0 0 1 0  <-- z position
0 0 0 1

Answer 3

If I understand, you can probably do this with a predicate on the sort.

Matrix transMatrix;

struct DepthSorter
{
    DepthSorter(const Matrix& matrix) : matrix_(matrix) {}
    bool operator()(const Obj& obj1, const Obj& obj2) { return matrix_->translate(obj1) < matrix_->translate(obj2); }
};

std::vector<Obj> objs;

std::sort(objs.begin(), objs.end(), DepthSorter(transMatrix));

Answer 4

Short answer :

sort along matrix[3][2], which is the z position (in world space) of your object's center.

Long answer :

In homogeneous coordinates, a position is (x,y,z,1) ( as opposed to a direction which is (x,y,z,0), as we will see later )

To transform your point from one space to another, you multiply it by the transformation matrix. So if you want to transform the object's center, which is thus (0,0,0,1) by a matrix, the only remaining term is the right column of the matrix. The z component is the third.

With a direction, w=0, so the right column (which holds translation) will be multiplied by 0. This means : translating a direction does not change the direction, which makes sense.

Obviously, if you sort object's centers, two close objects may overlay.