Z-index (depth buffer) is broken for shape with different sizes

[rambip]

It seems that there is an error in the depth calculation of the shapes.
Indeed, in some situations, shapes closer to the camera are drawn UNDER shapes further away from the camera.
This happens in unpredictable situations, and thus I would bet on a miscalculation.

Example 1: no bug

2 squares separated by a small distance, the 2 squares are the same size.

#import "@preview/cetz:0.4.2": canvas, draw

#set page(height: auto, margin: 1cm)

#let debug-figure(y-rot) = {
  canvas(length: 1cm, {
    draw.ortho(
      x: 20deg,
      y: y-rot,
      z: 0deg,
      sorted: true,
      {
        // Square 1: Further back (z = 0.5), Blue
        draw.on-xy(z: 0.5, {
          draw.rect((0, 0), (3, 3), fill: blue.transparentize(20%), stroke: black)
        })

        // Square 2: Closer to camera (z = 0), Red
        draw.on-xy(z: 0, {
          draw.rect((0.0, 0.0), (3.0, 3.0), fill: red.transparentize(20%), stroke: black)
        })

        draw.content((1.25, -0.5), [#y-rot])
      }
    )
  })
}

#grid(
  columns: (1fr, 1fr, 1fr, 1fr),
  gutter: 0.5cm,
  ..range(0, 36).map(i => {
    let rot = -10deg * i
    debug-figure(rot)
  })
)

Result:

Example 2: bug

2 squares separated by a small distance, the red square is smaller

#import "@preview/cetz:0.4.2": canvas, draw

#set page(height: auto, margin: 1cm)

#let debug-figure(y-rot) = {
  canvas(length: 1cm, {
    draw.ortho(
      x: 20deg,
      y: y-rot,
      z: 0deg,
      sorted: true,
      {
        // Square 1: Further back (z = 0.5), Blue
        draw.on-xy(z: 0.5, {
          draw.rect((0, 0), (3, 3), fill: blue.transparentize(20%), stroke: black)
        })

        // Square 2: Closer to camera (z = 0), Red
        draw.on-xy(z: 0, {
          draw.rect((0.0, 0.0), (3.0, 3.0), fill: red.transparentize(20%), stroke: black)
        })

        draw.content((1.25, -0.5), [#y-rot])
      }
    )
  })
}

#grid(
  columns: (1fr, 1fr, 1fr, 1fr),
  gutter: 0.5cm,
  ..range(0, 36).map(i => {
    let rot = -10deg * i
    debug-figure(rot)
  })
)

Results:

The smaller, red squares pops in front of the blue one, for no reason.

[johannes-wolf]

The sorting is very naive:

cetz/src/draw/projection.typ

Line 44 in 1120422

#let _sort-by-distance(drawables) = {

It uses the maximum (transformed) z component of all points of a shape as the final z-index which results in the behavior shown.

[rambip]

The sorting is very naive:

cetz/src/draw/projection.typ

Line 44 in 1120422
#let _sort-by-distance(drawables) = {

It uses the maximum (transformed) z component of all points of a shape as the final z-index which results in the behavior shown.

Naively, I would say it makes more sense to sort on average instead of max. Max is arbitrary (it could be min), so I think average is better in most cases (here, it would work perfectly). For circles, rects, polygons (maybe all the shapes in fact ?) the average can be computed. You can fallback to max, min or average between min and max if you can't

One other idea would be so sort on max z, then to traverse the shapes on min z (Kosaraju's style, I can elaborate on that), to find groups of shapes whose bounding box intersect. Then, draw each group one after another, and do something smarter inside groups.