// Le rasterizer par subdivision récursive de Quake; affiche tous le pixels
// d'un triangle qui ne correspondent pas aux sommets en partageant un côté
// pour former un nouveau point, affiche ce point, et traite récursivement
// les deux nouveaux triangles dont le nouveau point est un sommet. Résultat
// moins précis que par mapping linéaire ou mapping perspectivement correct,
// et les frontières entre polygones ne sont pas aussi précises que celles
// rendues par un algorithme de rendu spécialisé, même si elles sont consistantes
// entre deux polygones adjacents rendus par cette technique.
//
// Inventée et implémentée par John Carmack d'Id Software.

void D_PolysetRecursiveTriangle (int *lp1, int *lp2, int *lp3)
{
  int    *temp;
  int    d;
  int    new[6];
  int    z;
  short  *zbuf;

// Essayer de trouver un côté qui soit long de plus d'un pixel
  d = lp2[0] - lp1[0];
  if (d < -1 || d > 1)
    goto split;
  d = lp2[1] - lp1[1];
  if (d < -1 || d > 1)
    goto split;
  d = lp3[0] - lp2[0];
  if (d < -1 || d > 1)
    goto split2;
  d = lp3[1] - lp2[1];
  if (d < -1 || d > 1)
    goto split2;
  d = lp1[0] - lp3[0];
  if (d < -1 || d > 1)
    goto split3;
  d = lp1[1] - lp3[1];
  if (d < -1 || d > 1)
  {
split3:
  // Faire tourner les points de sorte que le premier côté soit le côté à découper
    temp = lp1;
    lp1 = lp3;
    lp3 = lp2;
    lp2 = temp;
    goto split;
  }

  return;         // no pixels left to fill in triangle

split2:
// Faire tourner les points de sorte que le premier côté soit le côté à découper
  temp = lp1;
  lp1 = lp2;
  lp2 = lp3;
  lp3 = temp;

split:
// Partager les coordonnées écran x et y, les coordonnées de texture s et z et la
// coordonnée z pour former le nouveau point. L'illumination (index 4) est
// ignorée. La différence entre une illumination par interpolation et une
// illumination générale n'est pas notable pour de petits triangles. Nous
// utilisons donc l'illumination du premier point du triangle original (qui a
// été utilisée durant l'initialisation pour d_colormap, utilisé ici pour
// illuminer les texels)
  new[0] = (lp1[0] + lp2[0]) >> 1;        // split screen x
  new[1] = (lp1[1] + lp2[1]) >> 1;        // split screen y
  new[2] = (lp1[2] + lp2[2]) >> 1;        // split texture s
  new[3] = (lp1[3] + lp2[3]) >> 1;        // split texture t
  new[5] = (lp1[5] + lp2[5]) >> 1;        // split z

// Afficher le point si nous découpons un côté montant
  if (lp2[1] > lp1[1])
    goto nodraw;
  if ((lp2[1] == lp1[1]) && (lp2[0] < lp1[0]))
    goto nodraw;


  z = new[5]>>16;

// Pointer sur l'entrée du point dans le z-buffer, en recherchant l'adresse de
// départ de la ligne en nous basant sur la coordonnée écran y et en y ajoutant la
// coordonnée écran x
  zbuf = zspantable[new[1]] + new[0];

// Rendre le point découpé s'il n'est pas caché par quelque chose de plus proche
// comme l'indique le z-buffer
  if (z >= *zbuf)
  {
    int     pix;
    
  // Affecter la distance du point à l'entrée du z-buffer
    *zbuf = z;

  // Récupérer le texel du bitmap de la peau du modèle, comme l'indique les
  // coordonnées s et t de texture, et le traduire en une couleur via la table
  // d'illumination. s et t sont tous deux au format 16.16
    pix = d_pcolormap[skintable[new[3]>>16][new[2]>>16]];

  // Rendre le pixel, en recherchant l'adresse de départ de la ligne de l'écran
  // en nous basant sur la coordonnée écran y et en y ajoutant la coordonnée
  // écran x
    d_viewbuffer[d_scantable[new[1]] + new[0]] = pix;
  }

nodraw:
// Rendre récursivement les deux nouveaux triangles que nous avons générés
  D_PolysetRecursiveTriangle (lp3, lp1, new);
  D_PolysetRecursiveTriangle (lp3, new, lp2);
}