présentation

Curveball est un outil de génération de courbes pour Neverball, un jeu open-source. Il est disponible en ligne et son code source est accessible sur Github.

fondements techniques

Les niveaux de Neverball sont constitués de « brushes », qui sont des pièces de géométrie définies par des intersections d'espaces demi-ouverts. Chaque brush est défini par des points dans un plan, qui doivent être dans un certain ordre pour éviter de couper la mauvaise partie de l'univers.

{
   "classname" "worldspawn"
   // brush 0
   {
   ( 0 0 64 ) ( 0 64 64 ) ( 64 0 64 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0
   ( 0 0 0 ) ( 0 0 64 ) ( 64 0 64 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0
   ( 0 0 64 ) ( 0 0 0 ) ( 0 64 64 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0
   ( 64 0 64 ) ( 64 64 64 ) ( 64 64 0 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0
   ( 64 64 0 ) ( 64 64 64 ) ( 0 64 64 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0
   ( 0 0 0 ) ( 64 0 0 ) ( 64 64 0 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0
   }
   }

convexité et algorithmes

Les brushes doivent être convexes, mais la plupart des courbes ne le sont pas. Pour résoudre ce problème, Curveball utilise un algorithme de convex hull pour générer des courbes à partir de points. L'algorithme de convex hull est implémenté à l'aide de la crate chull en Rust.

extrusions et orientation

Curveball utilise une abstraction appelée extrusion pour générer des courbes. L'extrusion consiste à définir un profil 2D qui est extrudé dans l'espace 3D. Le profil est copié plusieurs fois le long d'un chemin, et les sommets sont traités par l'algorithme de convex hull pour produire des brushes. L'orientation du profil le long du chemin est également prise en compte, en utilisant des techniques comme les formules de Frenet-Serret.

Voici la signature de la fonction d'extrusion : 

pub fn extrude<PRF, PTH>(
       n: u32,
       profile: &PRF,
       path: &PTH,
       profile_orientation: ProfileOrientation,
   ) -> CurveResult<Vec<Brush>>
   where
       PRF: Profile,
       PTH: Path,