Petite question que je me pose par curiosité : Comment est géré l´affichage des "tranches" de murs (d´un pixel de large donc) dans un ray caster ?

Mon idée :

Une texture possède une taille fixe, par exemple 64*64 pixels.

On calcule la hauteur du mur tel qu´il sera affiché sur l´écran, on trouve par exemple 47 pixels.

On mesure le rapport 64/47 = 1.36... qui donnera "l´incrément de lecture" de la texture source lors de l´affichage du mur (pour le scaling de la texture quoi) et on affiche la texture, en incrémentant l´index de texture (gardé en flottant) de 1.36... à chaque fois.

S´agit-il de la démarche effectivement suivie dans les ray caster ? Y a-t-il des optimisations particulières ?
En fait, j´ai une petite idée pour créer un moteur avec des murs non orthogonnaux de taille quelconque (un peu comme doom quoi) et j´aimerai savoir si l´algo que j´ai en tête est plus rapide que celui cité précédement employé das les ray casters (comme le FAT engine sur cette machine pour ceux qui connaissent)...

par "tranche de mur" je suppose que tu entends "bande verticale/horizontale d´un pixel de large, faisant parti d´un plan texture" :-?

mais oui, la methode que tu proposes est valide ; tu interpoles betemenet tes UVs sur les triangles, et tu obtiens un affichage.... degueux

les deux soucis de ton approche :
- c´est du nearest point : pour un pixel a l´ecran tu ne prends qu´un seul texel. Ca donne une tres forte distorsion du signal, avec un SNR pourri. (essaye de reduire ou rotater une image sans filtrer sous photoshop, c´est ignoble)
- tu as deformation non-lineaire de ta texture avec la profondeur : il faut interpoler en W et non en Z pour corriger la perspective

pour ameliorer :
- filter a la volee ; par en bilineaire, tu as une relation barycentrique entre 4 texels pour calculer la couleur d´un seul pixel a l´ecran. Ca filtre passe-bas et rend l´affichage bcp plus "lisse". Tu peux aller au dela, en sortant des noyaux de convolutions gaussiens, de l´anisotropic, etc.
- faire du supersampling ; en rendant l´image a une taille 2*W x 2*H par exemple, puis la encore en filtrant passe bas lorsque tu downsize en W*H. Avec un premier rendu rapide et une analyse de l´image (notamment contour, zones de forte variations en W, etc), tu peux supersampler plus ou moins precisement selon les zones, et donc mieux repartir les calculs
- faire la correction de perspective en interpolant en 1/Z

voila voila,qq idees generiques ; pour bien saisir tout le contexte et les implications du filtrage d´image, les spectres, les SNR, le disto, etc., je te conseille fortement de jeter un oeil a des cours de traitement du signal applique en 2D (ca fait un peu peur au debut, mais ca se fait tres bien)

"- tu as deformation non-lineaire de ta texture avec la profondeur : il faut interpoler en W et non en Z pour corriger la perspective"

Tu veux parler de l´effet eye fish bowl ?
Ci tel est le cas, j´avais pas détaillé la prise en compte de ce problème avant

Sinon le problème avec toutes les méthodes évoquées précédement, c´est que le moteur est prévu pour fonctionner sur une... calculette. Pas question de filtrage ou autres alors (d´autant plus que je n´utilise aucune API)
Ceci dit aucun effet de rotation ne sera effectué : le rendu ressemblera à celui que l´on trouve dans doom, avec des murs ortogonnaux aux sol/plafond.

"Tu veux parler de l´effet eye fish bowl ?"

non, pas tout a fait.

suppose que tu aies un plan vertical, mappe avec une texture faite de 3 lignes verticales : a gauche, et milieu, et a droite.
On regarde ce plan avec une camera telle qu´il soit incline (ie, un mur lateral dans un couloir pour un FPS) ; le plan apparait donc sous forme trapezoide.
Du fait de la perspective, chaque tranche du plan ne represente pas le meme surface a l´ecran (les bandes les plus proches couvrent bcp de l´ecran, alors que les lointaines, tres peu). Si tu projettes tes vertices et interpoles naivemrent tes UV, l´interpolation est lineaire et peut se voir comme une interpolation dans l´espace ecran APRES projection. Donc la texture va s´etaler uniformement sur le trapeze PROJETE, creant par la meme une deformation.
Pour supprimer cette distorsion, il faut interpoler les UV en W=1/Z (espace projectif) : c´est la correction de perspective. De cette maniere, la texture s´etale sur le trapeze en accord avec la projection.

"Pas question de filtrage"

le filtrage des raytracer se fait en software ; de plus le traitement du signal est qqch de tres generique et ne demande aucune specificite materielle. L´acceleration fournie par les cartes 3D n´est qu´un plus, mais on sait bien sur filtrer sans ca.

Principe d´un filtrage bilineaire :
tes UVs sont des flottants, tu les interpoles sur les triangles projetes. Imagine qu´en un pixel qqcq, le calcul te donne le mapping (U0 = 0.654, V0 = 0.412).
A ce stade, il te faut faire qqch pour aller regarder dans la texture la couleur a utiliser.
Solution batarde, le nearest point : tu castes tes UV floats en int, obtenant donc les coordonnees d´un seul pixel de la texture. C´est fini.
Meilleure facon : tu scales tes UVs pour travailler en coordonnes textures, et tu obtiens par ex (669.696, 421.888) pour une texture 1024*1024. La, tu vas pouvoir prendre 4 pixels : (669, 421), (670, 421), (669, 422) et (670, 422). Tu ponderes alors les couleurs de chacun en fonction de la distance par rapport a l´UV de base, et tu obtiens une superbe relation barycentrique prenant en compte 4 couleurs : c´est du filtrage bilineaire.
En condiderant plus de pixels, tu peux filtrer en splines/bezier, etc. Existe aussi l´anisotropic, qui la depend de l´orientation des choses a filtrer.. Plus complique.

Bref, ca marche aussi sur une calcultette, il suffit de faire le calcul pour ne pas utiliser qu´un seul pixel de ta texture.

Si c´est pour une calculette, je me permet d´ajouter ce que je fais sur amiga pour optimiser un peu tout lorsque on parle de raycaster:

-persp correction: tu n´est pas oblige de toujours l´appliquer. Les gros triangles qui font face a la cam ne necessitent pas forcement de la persp correction. J´utilise donc un thresold base sur les points dans la camera view pour determiner le renderer adequat. Si c´est plus rapide, deux drawbacks apparaissent: un petit flickering sur la texture, et un fps tres varialble.

-casting: tu peux downsampler (utiliser une grille plus large) et resampler lorsque tes rayons font des hits sur des objets differents. Par contre, ca amene au suuuuper effet qu´on appelle heaven-7 artefact, a savoir le haut des spheres qui disparaissent ou sont mal interpollees. Une solution que j´utilise, est, pour les objets chiants, d´avoir une bouding box, et d´utiliser sa 2d projection pour resubdiviser ta grille.

/kUfa

/me se reveille, il a entendu le mot "convolution"

encore des complements :D

pour la correction de perspective, un bon exemple est le jeu Tomb Raider 1 ; avec certains angles de camera, les textures du sol, qui ne sont pas corrigees, s´etirent affreusement.
Comme dit kufa, un threshold sur critere exprime dans l´espace ecran (comme du mipmapping par ex.) me semble une bonne idee.
Maintenant il faut voir si le raycaster est prevu pour du temps reel ou pas ; si non, autant privilegier la qualite, c´est quand meme le but du raytracing. Si oui... ermm... faaaakes & hacksssss :D

Kufa : pour la subdivision adaptative, ce ne serait pas plus simple de le faire dans l´espace world plutot qu´ecran, avec un bon vieil octree ou dans le genre ?

Merci à tous pour les réponses fournies
J´ai déjà une petite ébauche de truc, mais les perfs sont assez mauvaises (sur une machine cadencée à 12 MHz aussi...)

20MHz je crois mais le proco est under-clocké pour économiser les piles.

Mais on trouve sur le net, des procédures pas très compliquées pour débrider la machine. Il suffit sur certain modèle de court circuiter une résistance.

Bon, sur ma machine j´essayerais pas de le faire, mais ça peut peut-être t´intéresser.

Oui mais hors de question de toucher à la machine en harware

J´ai jeté un oeil sur les sources du FAT engine (sachant que ce que je voulais faire est un peu plus complexe vu que la géométrie des niveaux est plus libre que dans un ray caster) : une bonne partie des sources sont en asm 68k et certaines routines sont super optimisées...

Tiens, suite des complemenents (lorsque j ai ecris le poste j etais au tel, j ai oublie ca et c´est pourtant bien important):
si tu fais comme un doom (pour les mvts de cam), tu as des scanlines *verticales* a z-constant, ca aide BCP et ca va bcp plus vite lorsque tu veux de la persp correction. cf blackbook

LGV: ben la subdivision de la grille ce fait dans un espace 2d, sur le plan de projection. Bien entendu un bsp/octree est utilise avant; j´utilise perso des aabb pour les nodes, comme ca la subdivision est bcp plus rapide, meme si au niveau qualite c´est pas le mieux.
Grosso modo mon process c´est frustum culling via le bsp/octree, prendre et projeter les bb des objets visible pour subdiviser la grille, tracer.
Est-ce que j´ai repondu a la question?

/kUfa