Painter's algorithm problem

[vectozavr]

For now I use average z of triangle to sort them in correct order:

double z1 = t1[0].z + t1[1].z + t1[2].z; double z2 = t2[0].z + t2[1].z + t2[2].z; return z1 > z2;

where t1 and t2 - two triangles to compare.

But anyway we have glitches when some triangles wrongly overlap other triangles. Example:

[vectozavr]

If you use average distance instead of average Z component, the result will be much better, but problem still exists:

[vectozavr]

@Neirokan:

Мне кажется, точно определить порядок двух непересекающихся треугольников можно только проверив положение одного относительно плоскости другого, но тут целых 3 проблемы:

1. Вычисление плоскости затратно, скорее всего фпс сильно упадёт.
2. Есть вырожденные треугольники, то есть трудности с определением плоскости.
3. Такая проверка нетранзитивна когда проекции треугольников не пересекаются, то есть std::sort не сработает. У меня только следующие мысли:
4. Кеширование плоскостей снизит затраты, но вряд ли спасёт.
5. Тут 2 варианта: 2.1. Определять тип (точка/отрезок/треугольник) и по разному сравнивать разные сочетания. 2.2. Пытаться слегка смещать точки, но так можно получать пересечение треугольников.
6. Самое сложное, так как требует выбрать другой способ сортировки. У меня есть 3 мысли: 3.1. Каждый кадр строить BSP-дерево сцены. Интернет говорит, это дорого + принуждает использовать решение 2.2, но работает даже при взаимном перекрытии и пересечении треугольников. 3.2. Строить BSP-деревья объектов. Тоже принуждает использовать решение 2.2, но затраты на постройку проявляются только при создании объекта. Ломается при взаимном перекрытии объектов (например, два звена цепи отдельными объекта). 3.3. В этом варианте я не уверен, потому что он единственный не нагуглен: создать quadtree, каждый лист которого хранит свою очередь отрисовки, и делить его вместе с содержимым каждый раз, когда проявляется нетранзитивность. А чтобы уменьшить количество проверок, я думаю стоит сделать sort(maxZ) вместо sort(avgZ), и проходя по массиву отрисовывать и выбрасывать все элементы quadtree, у которых minZ больше maxZ текущего элемента.

[vectozavr]

This problem can be solved in the following way:

1. We sort triangles by finding separation planes. In this case one triangle is drawn first than the other if all points of it are farther away than all points of the second triangle. That was done before. But there are triangles that cannot be compared in such a way: some points of the first triangle might be farthest, but some might not. Example: two intersected triangles. Therefore, we have to resolve this problem.
2. Perform triangle subdivision by doing clipping between conflicting triangles.
3. Sort all triangles. Now we can do this step because we resolved all the conflicts on the step 2.