🥚 🈲 🦐 Est-il possible de rendre des images réalistes sans nombres à virgule flottante? 🏇🏻 🚑 🔵

Présentation

"Que se passe-t-il si nous remplaçons les nombres à virgule flottante par des nombres rationnels et essayons de rendre l'image?"

Je me suis posé cette question après avoir pensé au tweet d'un chercheur et professeur d'infographie Morgan McGwire. Il a expliqué à quel point les étudiants en informatique sont surpris lorsqu'ils découvrent pour la première fois que pour stocker les nombres à virgule flottante familiers dans les ordinateurs modernes, des compromis doivent être faits. Et ces compromis rendent les tâches simples difficiles, par exemple, vérifier si un point appartient à un triangle. Le problème, bien sûr, est que la vérification de quatre points dans le même plan (coplanarité) en utilisant un déterminant ou une sorte de multiplication vectorielle (mais en fait c'est la même chose) ne donnera jamais une valeur exactement égale à zéro, ce qui est requis ce sont des méthodes mathématiques. Même si les vrais calculs d'être sur le même plan étaient exacts, les mêmes compromis avec une précision de près de 1,0 donneraient la réponse que les quatre points eux-mêmes ne sont pas coplanaires.

Cela a donné naissance à l'idée en moi - si nous supposons que toutes les données de rendu entrantes (coordonnées des sommets, transformations 3D, etc.) étaient définies comme des nombres rationnels, alors elles créeraient toutes les opérations, de la création d'un rayon, en traversant la structure accélératrice jusqu'à l'intersection les rayons avec des triangles ne sont que des nombres rationnels? Si tel était le cas, nous pourrions alors effectuer un test de coplanarité exactement! Vous vous demandez peut-être pourquoi une scène 3D exprimée en nombres rationnels ne devrait donner des résultats qu'en nombres rationnels ...

Une scène simple, le tracé de chemin dans lequel est effectué par l'arithmétique rationnelle. Il utilise un système de nombres à virgule flottante, pas un nombre à virgule flottante.

Premièrement, un nombre rationnel est un nombre qui peut être exprimé comme le rapport de deux entiers, par exemple 1/2 ou 355/113. Deuxièmement, les «opérations de rendu normales», telles que les tests de boîte englobante, la vérification de l'intersection d'un rayon avec un triangle, la réflexion d'un rayon, etc., sont basées sur des produits vectoriels et scalaires, ainsi que sur la division scalaire (cela inclut transformation de coordonnées et inversion matricielle, quaternions, etc.), qui à leur tour reposent sur quatre opérations de base: addition, soustraction, multiplication et division. Lors de l'addition, de la soustraction, de la multiplication et de la division des nombres rationnels, des nombres rationnels sont également obtenus. Le mathématicien dirait que de nombreux nombres rationnels forment un champ qui est fermé sous quatre opérations arithmétiques de base. Pour nous, cela signifie que si nous adhérons à des nombres exclusivement rationnels, nous pouvons réellement passer des données d'entrée de la scène 3D à une image entièrement rendue sans quitter le monde des nombres rationnels.

Les exceptions à la règle «les actions sur les nombres rationnels donnent des nombres rationnels» sont les racines carrées et les fonctions trigonométriques / transcendantales. Quant à ce dernier, je dis toujours que si vous deviez effectuer des calculs trigonométriques dans les intérieurs géométriques de votre moteur de rendu, alors vous faites probablement quelque chose de mal (et j'ai montré comment corriger les cas les plus standards ). En ce qui concerne les racines carrées, à l'exception des sections coniques (sphères, cylindres, etc.) et de l'ombrage / DFOS / coloration, il n'est pas nécessaire de normaliser les rayons et la normale aux surfaces aussi souvent que d'habitude. Il n'est certainement pas nécessaire de le faire pour créer un rayon, son passage, son intersection, ses réflexions, etc. Malheureusement, très souvent, je vois que les programmeurs normalisent les valeurs sans autre raison que "eh bien, je ne sais pas, je le fais pour pouvoir jouer en toute sécurité." En pratique, dans la partie du rendu où la géométrie est tracée, il est très rarement nécessaire de normaliser les valeurs, donc j'avais l'espoir qu'il serait possible de tracer toute la scène sans quitter le monde des nombres rationnels - c'est ce que j'appellerais le "rendu rationnel".

Pour mettre cela en pratique, je dois créer un système numérique basé sur des nombres rationnels qu'un ordinateur pourrait utiliser. Ensuite, j'ai pu implémenter les algorithmes de traçage de chemin habituels, calculer des images sans perte de précision, effectuer des vérifications de coplanarité qui ont des réponses précises et rendre tous les étudiants étudiant l'infographie heureux.

Cet article est une histoire de deux nuits de recherche sur le réalisme d'une telle idée. Je vais parler des nombreux aspects que j'ai appris, de ce que j'ai trouvé et de quelques surprises que j'ai découvertes au cours du processus. L'article est écrit dans un ordre plus ou moins chronologique de mon travail. De plus, il a été écrit dans mon style inhabituellement informel et très peu scientifique (dont je suis fier). L'image ci-dessus est une sorte de spoiler, mais lisez l'article à la fin, car je vais parler du bon et du mauvais.

La préparation

La première chose que j'ai faite a été d'implémenter dans Shadertoy un traceur minimalement limité pour une scène extrêmement simple composée d'un plan, d'une sphère, d'un parallélépipède rectangle et d'un triangle - les blocs de construction de véritables moteurs de rendu. Ensuite, j'ai copié le code dans un fichier C ++ et, après avoir apporté quelques modifications mineures, je l' ai compilé à l'aide de mon framework piLibs . Donc, à titre de comparaison, j'ai obtenu une image tracée rendue au processeur en utilisant des nombres réguliers selon la norme IEEE754 avec une virgule flottante. J'ai également supprimé toute normalisation des rayons du code de trace, car, comme mentionné ci-dessus, aucune d'entre elles n'est réellement nécessaire. Permettez-moi de vous rappeler qu'une racine carrée est requise pour la normalisation et que les nombres rationnels ne sont pas conservés lorsqu'elle est utilisée (la racine carrée d'un nombre rationnel n'est pas un nombre rationnel). Un peu plus tard, nous verrons qu'appliquer des racines carrées, bien sûr, est toujours possible, je voulais juste rendre le code aussi mathématiquement propre que possible pour voir jusqu'où je peux aller avec l'arithmétique exacte des nombres rationnels sans arrondir.

La dernière étape préparatoire - j'ai pris toutes les classes vec3, mat4x4 et autres classes d'algèbre / mathématiques de base, puis je les ai modifiées pour qu'elles utilisent rationnel au lieu de flottant. Comme ma structure rationnelle surcharge tous les opérateurs standard (add, sub, mul, div, inversion de signe, comparaisons, etc.), le remplacement s'est produit sans problème. J'ai rapidement implémenté les opérations habituelles restantes (abs, signe, mod, fract, floor, sqrt, etc.), ce qui était théoriquement suffisant pour obtenir de beaux rendus rationnels.

Test 1 - La solution naïve

Mais voyons à quoi ressemblait cette première implémentation. Au début, j'essaie toujours le plus simple, puis je regarde les résultats. Et la manière la plus simple d'implémenter des valeurs rationnelles était d'utiliser deux entiers. Comme le nom de la section l'indique, ce ne sera pas ma décision finale, mais pour la première tentative, c'était une décision raisonnable. Ainsi, chaque nombre x doit être représenté comme le numérateur N et le dénominateur D , formant la valeur N / D. La valeur x est approximée par la meilleure paire N / D possible (dans la profondeur de bits spécifiée), qui est la plus proche de la vraie valeur x . J'ai décidé que les deux nombres doivent être positifs, et le signe du nombre doit être stocké dans un bit séparé afin de simplifier le travail et de se débarrasser des ambiguïtés, bien que ce ne soit pas très important. À ce stade, les numérateurs et les dénominateurs étaient de type non signé. Mais même en séparant le signe, N / D avait beaucoup de redondance: par exemple, 1/4 et 7/28 désignent le même nombre, mais ont des représentations binaires complètement différentes. Nous y reviendrons plus tard, mais pour l'instant, ne concentrons pas notre attention et voyons à quoi ressemblent les quatre opérations arithmétiques de base sous cette forme rationnelle.

Tout d'abord, notez que la soustraction de a - b est simplement l'addition de a et la valeur opposée à b , c'est-à-dire a + ( -b ), où -b peut être calculé en changeant simplement le signe de b . De même, diviser a / b équivaut à multiplier a et l'inverse de b . Ou, en d'autres termes, a / b = a · (1 / b ), où (1 / b ) peut être calculé en changeant simplement les places du numérateur b _n et du dénominateur b _{d du} nombre b . Donc, voici la première propriété intéressante de l'arithmétique rationnelle - la division et la multiplication ont les mêmes coûts, par conséquent, contrairement au rendu en virgule flottante habituel, dans lequel les divisions sont généralement évitées, retardées ou cachées sous les retards des demandes de texture lentes, il n'est pas nécessaire d'avoir peur de ces opérations en arithmétique rationnelle .

Nous passons à l'addition avec multiplication: nous savons que les valeurs opposées et inverses sont trivialement simples à calculer, nous obtenons donc:

La préservation des signes pendant la multiplication est triviale, c'est juste xor, car deux valeurs positives donnent un résultat positif, ainsi que deux négatives. L'enregistrement d'un signe pour l'ajout est un processus plus compliqué, et pour une solution rapide, je l'ai implémenté à travers trois branches (l'ajout est trivial si les signes a et b coïncident, mais lorsqu'ils ne correspondent pas, vous devez sélectionner un plus petit nombre et le soustraire du plus grand - dans l'article, je ne le fais pas Je vais décrire ces petits détails plus en détail, mais il suffit de disposer le code source quelque part).

Je vais également sauter l'implémentation de fract () et floor (); si vous décidez d'essayer de les mettre en œuvre vous-même, vous verrez leur simplicité et leur beauté. Il convient également de prêter attention aux opérateurs de comparaison. Après avoir pris soin des signes et en supposant que a et b sont positifs, nous obtenons

Il est important de noter ici que même pour la comparaison, nous avons besoin de quelques opérations de multiplication, ce qui peut conduire à la transition vers la taille de mot suivante et sera un peu plus faible.

Enfin, nous regardons les racines carrées dans une section distincte, sachant que pour la plupart nous n'en avons pas besoin (sauf pour la sphère de ce premier test).

Cela a suffi pour exécuter le premier rendu et tracer la scène de test (plan + sphère + triangle + boîte rectangulaire) pour voir ce qui en est sorti. J'ai généreusement utilisé des nombres rationnels de 65 bits pour ce premier test, qui représente en fait une grande quantité de données (comparable au type de données "double"): 32 bits sont pris par le numérateur, 32 bits sont le dénominateur et un autre bit est le signe. La première est l'image obtenue avec cette approche naïve, la seconde est l'image réalisée à l'aide de nombres à virgule flottante (référence):

Nombres rationnels de 65 bits "naïfs"

Référence en virgule flottante

Le résultat était plutôt mauvais, la boîte et le triangle n'apparaissaient même pas sur le rendu, et la sphère et le plan du sol étaient trop bruyants. Le problème, bien sûr, était que chaque fois que mes nombres rationnels effectuaient une opération arithmétique de base à l'une des étapes algorithmiques du rendu, le numérateur et le dénominateur devenaient de plus en plus incontrôlables, car une multiplication entière était utilisée. Pensez à ce qui suit: si les unités de notre monde initial étaient des mètres et que nous lierions la géométrie source (sommets et caméra) à une précision millimétrique, alors seules les données source occuperaient un volume de 16 bits pour une scène plutôt petite. Dans le même temps, avec une résolution d'écran HD standard et un lissage 4X, les nombres de direction de faisceau rationnels nécessiteraient facilement 12 bits. C'est-à-dire que lors de la première interaction du faisceau et de la géométrie, l'opération arithmétique la plus simple, utilisant les deux ensembles de données d'entrée, transformerait le résultat en longueurs de 28 bits - assez près de la limite de 32 bits que je me suis fixée dans cette première implémentation. Et c'est avant même d'avoir réalisé le tout premier produit vectoriel ou scalaire. Au moment où le produit scalaire est terminé, le moteur de rendu aurait besoin de nombres rationnels de centaines de bits pour représenter les nombres. Bien sûr, c'est le pire des cas, mais le cas moyen serait proche de cela. Étant donné que je n'ai alloué qu'une capacité de 32 bits pour le numérateur et le dénominateur, il est facile de comprendre à quelle vitesse les valeurs dépassent les limites de ce test - il n'est pas surprenant que presque rien ne soit visible, sauf pour le plan d'étage et une partie de la sphère.

Test 2 - Réduction par le plus grand facteur commun

Ensuite, j'ai amélioré le système en utilisant la propriété que j'ai brièvement mentionnée ci-dessus - des nombres rationnels différents peuvent signifier le même montant. Et en fait, 6/12 est la même valeur que 1/2, mais il utilise beaucoup plus de bits que le dernier. Par conséquent, l'idée était la suivante: si après chaque opération arithmétique de base (ou après) j'extrayais tous les diviseurs communs du numérateur et des dénominateurs, et ramènerais la fraction à sa forme la plus simple, alors je serais peut-être en mesure de tout garder sous contrôle et de continuer les opérations plus longtemps avec une arithmétique exacte sans perte de précision. Peut-être pouvez-vous le faire assez longtemps pour obtenir des images propres et rendues? Je vais prendre une petite digression pour montrer un autre exemple: 588/910 peut être simplifié en 42/65, car 14 est un diviseur de 588 et 910. Mais pour stocker 42/65, évidemment, moins de bits sont nécessaires que 588/910. Trouver le plus grand nombre possible qui divise simultanément les deux autres nombres peut être fait en utilisant l'algorithme Great Common Divisor (GCD), des implémentations efficaces que vous pouvez trouver n'importe où (je l'ai personnellement copié directement à partir de Wikipedia et l'ai accéléré un peu en effectuant l'étape de numérisation bits utilisant des opérations internes x64). Ainsi, armée de l'algorithme GCD, ma classe rationnelle devrait constamment simplifier les fractions générées au cours du processus de rendu. Cela pourrait se faire de deux manières:

La première consiste à convertir le résultat intermédiaire des opérateurs d'addition et de multiplication vers le type de données de bit suivant (dans ma solution naïve actuelle, c'est uin64_t), recherchez GCD dans ce type de données plus volumineux, puis réduisez le résultat à la longueur de bit d'origine (32). La deuxième façon consiste à analyser comment a _n , a _d , b _n et b _d sont combinés les uns avec les autres dans les deux opérateurs arithmétiques et d'en extraire des diviseurs communs avant d'effectuer la multiplication. La deuxième approche a essentiellement éliminé le besoin de grandes longueurs de bits. Sachant qu'il pourrait être nécessaire de les utiliser de toute façon, j'ai décidé de choisir la première méthode, car elle était plus facile à mettre en œuvre et elle m'a permis d'accélérer mon travail (la soirée s'envole très vite). Après avoir fait tout cela, voyons quel rendu je peux créer maintenant:

Nombre rationnel de 65 bits réduit par GCD

Référence en virgule flottante

Bien mieux! Jusqu'à présent, loin d'être idéal, bien sûr, mais cela semble prometteur. J'ai fait apparaître la boîte et le triangle, et la sphère semble maintenant beaucoup plus volumineuse. Cependant, un artefact drôle est apparu dans le coin supérieur droit, et les nombres rationnels pour de nombreux pixels dépassent toujours les limites, ce qui conduit à de nombreux points dans l'image. Cependant, il convient de noter que pour certains (nombreux) pixels, j'ai commencé à obtenir des résultats précis et parfaits! Autrement dit, le traceur a trouvé des intersections mathématiquement précises de points et de distances, ce qui était la cause première de l'utilisation de nombres rationnels.

Avant de passer à l'étape suivante du processus de preuve de l'applicabilité des nombres rationnels, je souhaite brièvement m'arrêter et partager mes conclusions concernant la GCD et la réduction des nombres rationnels.

La première découverte est liée au volume de bits des nombres rationnels. Même si je ne peux toujours pas rendre de belles images et cela est plus important que de se soucier de l'optimisation des volumes de données, et bien que cette première implémentation utilisait toujours un grand nombre de bits (1 + 32 + 32), je pensais déjà aux déchets mentionnés plus tôt bits sous forme de fractions en excès. En particulier, après avoir ajouté une étape avec un GCD, les combinaisons de bits comme 2/4 ne sont plus applicables, car elles sont automatiquement réduites à 1/2 avant d'écrire dans un registre ou une variable. Autrement dit, sur les 2 ⁶⁴ combinaisons de bits qui pourraient être le numérateur et le dénominateur, beaucoup restent inutilisées. Et vous ne pouvez pas gaspiller des morceaux comme ça. Ou est-ce possible? Combien d'espace ai-je réellement perdu? J'ai fait une petite digression pour explorer cette question.

Digression - sur des nombres mutuellement premiers

Les illustrations ci-dessous montrent l'utilisation de bits pour les nombres rationnels en 5/5 bits et 7/7 bits. Les axes horizontal et vertical des graphiques représentent les valeurs du numérateur et du dénominateur de tous les nombres rationnels possibles ayant des numérateurs et des dénominateurs jusqu'à 5 bits (31) et 7 bits (127). Les pixels noirs sont des combinaisons inutilisées et les pixels blancs sont des fractions utilisées. Par exemple, toute la diagonale est noire, à l'exception du pixel 1/1, car toutes les fractions de la forme n / n sont réduites à 1/1.

Utilisation de bits pour 5/5 rationnel

Utilisation de bits pour 7/7 rationnel

Si vous comptez les pixels, comme je l'ai fait, vous pouvez rapidement comprendre que la proportion de pixels utiles avec une augmentation du nombre de bits tend à 60,8%. Une petite recherche en ligne m'a montré que ce rapport se révèle être exactement 6 / π ² , car c'est aussi la probabilité d'être relativement premier (n'ayant pas de diviseurs communs) pour deux nombres aléatoires. Vous pouvez demander, d'où vient le pi?Il s'avère que «six par pi au carré» est une valeur égale à l'unité divisée par la fonction zêta de Riemann calculée au point 2, 1 / ζ (2). Cela ne devrait pas nous surprendre beaucoup, car la fonction zêta de Riemann apparaît souvent dans des problèmes impliquant des nombres premiers et mutuellement premiers.

Quoi qu'il en soit, à mon avis rationnel, j'ai gaspillé environ 40% des combinaisons de bits. Et même si cela semble être un grand nombre, j'ai décidé de le regarder comme s'il était en fait un peu moins ... grâce auquel je n'ai pas pu être très contrarié. Dans cet esprit, j'ai décidé de passer à autre chose, en utilisant d'autres approches complètement différentes, au lieu d'essayer d'optimiser ce problème localement. Cependant, néanmoins, j'ai brièvement appris sur les arbres Stern-Brokaw et Calkin-Wilf, ce qui pourrait me permettre d'utiliser pleinement tous les bits disponibles, mais l'intervalle de valeurs obtenues avec leur aide est très petit, j'ai donc rapidement abandonné cette idée et je suis passé à autre chose. Je pense qu'à ce stade, je dois exprimer ma gratitude envers Wikipédia en tant que source constante de mes connaissances.

Revenons à l'analyse de ce que nous avons obtenu: je peux rendre des images avec des distorsions, mais cela dépend beaucoup de la distribution des nombres premiers dans les calculs. Cela dépend de ces nombres premiers si l'algorithme GCD peut simplifier l'expression - dès qu'un nombre premier ou un multiple tombe dans l'un des nombres de rendu (vecteurs, scalaires, matrices), il "pollue" tous les nombres qui le suivent dans d'autres manipulations arithmétiques, et y demeure pour toujours. Par conséquent, progressivement tout est garanti pour commencer à croître, ce n'est qu'une question de temps. En plus du fait que cela est inévitable, il est également nécessaire, car ce sont des diviseurs mutuellement simples qui portent des informations sur la valeur d'un nombre. Mais en même temps, les grands nombres premiers cassent tout très rapidement. Il y a donc un conflit.

La dernière chose à noter est que j'utilisais toujours deux fois plus de bits que le nombre à virgule flottante standard, donc il n'y a aucun avantage réel jusqu'ici. Bien sûr, j'ai essayé d'utiliser des nombres rationnels 16/16 bits, ce qui serait une comparaison plus honnête avec les vraies exigences de l'arithmétique à virgule flottante, mais avec une précision de 16/16, le système que j'ai écrit avec le numérateur + dénominateur + GCD a créé des images complètement illisibles.

Test 3 - Normalisation des nombres rationnels

Donc, à ce stade, j'avais besoin de quelque chose de vraiment significatif. Il semblait que pour empêcher les nombres de sortir des limites, il fallait commencer à les couper et à perdre en précision. Toute mon expérience a commencé avec l'idée de rechercher un rendu précis , mais à ce moment-là, j'ai senti que j'étais prêt à abandonner cette idée et continuer à explorer d'autres domaines, ne serait-ce que pour le plaisir, et voir à quoi cela me mènerait (l'idée initiale stimulant le processus de recherche "C'est exactement l'idée de commencer le processus, et après cela, vous vous retrouvez souvent dans un endroit complètement inattendu. Ou, comme John Cleese l'a dit une fois, les mauvaises idées peuvent conduire à de bonnes idées, le processus créatif n'est pas toujours toujours edovatelnostyu ou logiquement vraie progression des étapes).

Quoi qu'il en soit, j'ai décidé de vérifier ce qui arriverait aux rendus si je protégeais en quelque sorte le numérateur et le dénominateur des débordements. La manière la plus simple serait de décaler le numérateur et le dénominateur, si nécessaire, d'un nombre suffisant de bits vers la droite, jusqu'à ce qu'ils réapparaissent dans l'espace binaire qui leur est alloué. En fait, cela signifie une division entière du numérateur et du dénominateur par une valeur, ce qui signifie que la valeur du nombre reste approximativement inchangée. Et ici, je me suis écarté du but initial de l'expérience.

Dans ma première implémentation, j'ai regardé le nombre de bits nécessaires pour le numérateur et le dénominateur, pris le maximum pour les deux et décalé les deux par ce nombre de bits (arrondi à l'entier le plus proche). Lorsque cela a été implémenté dans les opérateurs d'addition et de multiplication, tout a commencé à sembler tout à fait acceptable:

Nombres rationnels 65 bits réduits par GCD et normalisation

Norme à virgule flottante

Puisque tout semblait plutôt bien, à ce stade, j'ai procédé à la résolution du problème d'une grande quantité de bits utilisés dans l'implémentation actuelle. J'ai essayé d'utiliser 16/16 (33 bits) au lieu de 32/32 (65 bits), et les images se sont révélées étonnamment bonnes! J'ai encore vu que sur certains bords de la sphère il y a de petits trous, et dans la figure de la texture du triangle il y a de petits trous. Mais ce n'est pas mauvais pour des quantités suffisamment proches des nombres à virgule flottante. Cela m'a donné de l'énergie pour apprendre de nouvelles idées.

Test 4 - Slash flottant

À ce stade, j'ai décidé de me distraire et d'arrêter de chercher des excuses - si je veux trouver quelque chose d'intéressant pour le rendu en nombres rationnels, alors ils devraient occuper 32 bits et pas plus. Il vaut mieux trouver une bonne idée ou s'arrêter, et s'arrêter là (c'était au début de la deuxième soirée d'expériences).

Au début, je pensais que cela valait la peine de s'en tenir aux idées de GCD et de normalisation, mais il était plus sage d'aborder le stockage et l'utilisation des bits. La première chose qui m'est venue à l'esprit est que même si le numérateur et le dénominateur peuvent devenir volumineux, cela ne se produit souvent pas. Ou, du moins, cela ne se produit pas simultanément. Par conséquent, lorsque le numérateur est petit, vous pouvez laisser le dénominateur être grand et vice versa. Les bits inutilisés de l'une des deux valeurs entières peuvent être utilisés pour représenter des valeurs plus grandes. Puis je me suis rendu compte que de la même manière, un nombre à virgule flottante est essentiellement un format à virgule fixe, où le point «fixe» est rendu variable. Je peux prendre mes nombres rationnels et également faire la disposition des bits de la variable de fraction de fraction. Autrement dit, il n'est pas difficile de définir la fraction sur 16/16, mais de permettre à la même variable 32 bits d'être parfois 16/16,et parfois 5/27 ou 13/19, au besoin.

Cela valait la peine de vérifier. Quoi qu'il en soit, quelques lignes de code d'emballage / déballage dans les setters et les getters internes peuvent être écrites rapidement. Le schéma le plus logique pour moi semblait 1 | 5 | 26, c'est-à-dire:

1 bit: signe
5 bits: position de la ligne de fraction (B)
26 bits: données combinées numérateur et dénominateur; le numérateur est le bit 26-B supérieur, le dénominateur est le bit B inférieur,

où la barre de fraction (B) détermine la taille du dénominateur. Par exemple, le nombre 7/3 sera écrit comme

7/3 = 0 00010 000000000000000000000111 11,

où le signe 0 signifie une valeur positive, la ligne de la fraction 2 désigne le dénominateur (numéro 3), qui nécessite 2 bits pour représenter, et le reste des bits va au numérateur.

Les lecteurs qui ont travaillé avec la norme IEEE754 peuvent trouver cette observation familière: la représentation binaire du dénominateur commence toujours par «1», car le numéro de ligne de fraction le tronque toujours à la représentation la plus courte. Autrement dit, le premier bit du dénominateur est facultatif. Dans ce cas, le nombre «3» ne peut être représenté que par la valeur binaire «1» et la valeur de la ligne de fraction «1»:

7/3 = 0 00001 00000000000000000000001111 1

Cette astuce m'a non seulement sauvé un bit précieux, mais a également un excellent effet secondaire: lorsque la valeur du trait de fraction est nulle, cela signifie naturellement en même temps que le dénominateur est 1 et qu'aucun espace n'est nécessaire pour le stocker. Cela signifie que ma représentation rationnelle des nombres s'est avérée soudainement complètement compatible avec la représentation entière et l'arithmétique habituelles, jusqu'à ce que les valeurs des nombres dépassent 2 ²⁶c'est-à-dire à un seuil suffisamment grand. Quelle merveilleuse surprise! C'est-à-dire que théoriquement, je peux utiliser exactement le même type de données, «rationnel», pour effectuer des opérations de rendu et d'ombrage standard, mais aussi effectuer toute la logique et les tâches du flux de commandes dans le traceur de chemin - je n'ai plus besoin d'utiliser deux types de données, car cela se produit dans la plupart des moteurs de rendu ("int" et "float") et effectuez des conversions dans un sens et dans un autre! Cependant, le temps étant compté pour moi, je n'ai pas changé tous les indices de boucle de «int» à «rationnel». La soirée touchait à sa fin, et je devais encore vérifier beaucoup de choses pour améliorer la qualité des rendus.

Après avoir créé l'implémentation, j'ai pu le vérifier:

Nombres rationnels fractionnaires 32 bits (1 | 5 | 26)

standard 32 bits flottant -point

O-oh, eh bien! J'ai encore des artefacts dans la sphère, que je vais pour l'instant blâmer pour ma mauvaise mise en œuvre de la racine carrée, mais la boîte et le triangle sont devenus vraiment propres. Le nombre de pixels d'image résolus avec précision a également augmenté. Je pense qu'en raison du fait qu'avant le débordement du dénominateur ou du numérateur, plus de nombres ont le temps d'apparaître, j'ai augmenté la probabilité que le GCD trouve des diviseurs communs et effectue une réduction. C'est-à-dire que la ligne flottante de la fraction a non seulement augmenté l'intervalle des nombres représentés et a reporté le moment de normalisation (avec perte de précision) causée par le débordement, mais a également franchi l'étape suivante dans l'amélioration de la qualité en augmentant la probabilité de réductions.

À ce stade, j'étais prêt à effectuer un test plus sérieux (mais toujours expérimental - le système est encore loin d'être prêt à fonctionner). J'ai implémenté un traceur de chemin avec un ensemble minimal de fonctions (pas nécessairement physiquement précises ou même en tenant compte de la physique) et créé une scène avec plusieurs parallélépipèdes rectangulaires et deux sources lumineuses, dont l'implémentation de référence sur le GPU est ici: https://www.shadertoy.com/view/Xd2fzR .

J'ai à nouveau converti la scène en framework C ++, supprimé à nouveau certaines normalisations de rayons inutiles et exécuté le rendu. Voici ce que j'ai obtenu:

Nombres rationnels fractionnaires 32 bits

Flottante de 32 bits standards Point

Wow, c'est vraiment bon! Bien que les fuites de lumière soient clairement visibles dans les coins où les bords du sol et du plafond sont connectés. Regardez-les dans l'approximation:

elles sont peut-être causées par un problème dans ma mise en œuvre de l'intersection d'un rayon et d'une boîte rectangulaire, qui ne s'exprime qu'en nombres rationnels; Je ne serais pas surpris. Ou peut-être que je suis tombé sur les limites de ce dont les nombres rationnels sont capables. Quoi qu'il en soit, je suis très content. De plus, j'ai d'autres changements et expériences que je voulais tester pour le peu de temps restant:

Quelques autres expériences

Arithmétique précise en 64 bits

L'idée de l'arithmétique exacte ne peut être réalisée ni en nombres rationnels naïfs 64 bits ni en nombres rationnels 32 bits (1 | 5 | 26) avec une fraction de ligne flottante. Et les nombres à virgule flottante 64 bits d'une fraction fonctionneront-ils?

J'ai rapidement implémenté des nombres rationnels 1 | 6 | 57 (même si j'ai dû apprendre de nouveaux mécanismes internes x64 pour décaler les bits). Ces 57 bits de numérateur / dénominateur ont permis de tracer un intervalle de distance beaucoup plus grand. J'ai vraiment été en mesure de retracer la scène avec plusieurs triangles avec tout précisarithmétique (pas la scène mentionnée ci-dessus avec des parallélépipèdes rectangulaires et un éclairage global, mais juste quelques triangles devant la caméra). Et le succès m'attendait! Cependant, le test de coplanarité, que j'ai implémenté pour vérifier l'exactitude, a nécessité plusieurs opérations de produits scalaires et vectoriels, ce qui a commencé à normaliser les nombres. Par conséquent, même si je savais que le rendu était précis, je ne pouvais pas le «prouver» expérimentalement. Quelle ironie. En général, cela signifie que 64 bits étaient suffisants pour plusieurs triangles, mais des scènes plus complexes s'effondreront toujours. Cependant, cela m'a fait réfléchir à une autre question: existe-t-il un algorithme qui peut être utilisé pour tester la coplanarité, basé non pas sur des valeurs absolues, mais sur une arithmétique modulaire? Je supposeen arithmétique modulaire, les nombres rationnels ne devraient pas «exploser» en taille? Je n'ai pas eu le temps d'examiner tout cela et je ne suis pas un expert en théorie des nombres.

Racines carrées

Lors de la dernière (deuxième) soirée de recherche, j'ai décidé de m'arrêter brièvement sur ce sujet et d'étudier de nouvelles informations. Je voulais implémenter la meilleure fonction de racine carrée possible pour les nombres rationnels. Ma décision naïve actuelle ( mauvaise ) a pris la racine carrée entière du numérateur (avec l'arrondissement correspondant), puis a fait de même avec le dénominateur. Puisque la racine carrée d'une fraction est une fraction des racines carrées du numérateur et du dénominateur, en général, cette approche donne des résultats décents, pas trop différents de la meilleure réponse. Mais il ne renvoie certainement pas la meilleure approximation rationnelle de la racine carrée d'un nombre rationnel. Il effectue deux approximations au lieu d'une seule.

J'ai essayé ce qui suit: à la fin, nous recherchons ici deux entiers x y , ,

() («» , ):

Après avoir recherché Wikipédia, j'ai trouvé que cette équation particulière est la soi-disant «équation de Pell modifiée». Il existe des algorithmes qui trouvent les plus petites valeurs x et y pour résoudre cette équation. Malheureusement, mon attention s'est rapidement déplacée vers d'autres mathématiques diophantiennes curieuses, et je n'ai procédé à la mise en œuvre d'aucun de ces algorithmes.

Réduction plus efficace

Dans les dernières minutes de la soirée, j'ai pensé à explorer l'idée d'utiliser plusieurs membres qui se combinent dans des opérateurs géométriques complexes, par exemple, dans un produit vectoriel. Disons que le premier composant d'un produit vectoriel était

en supposant que sy = a / b, tz = c / d, ty = e / f, sz = g / h

Cela signifie que maintenant je peux essayer de trouver des diviseurs communs, par exemple, entre a et d, ou e et h, et les utiliser pour une réduction préliminaire.

J'ai eu une autre idée: si à un moment donné la vitesse de rendu devient un problème, vous pouvez complètement désactiver les étapes de recherche de GCD et appliquer uniquement la normalisation. Une vérification rapide a montré que dans ce cas, les rendus d'image restent toujours acceptables et fonctionnent bien à une vitesse beaucoup plus élevée. Cependant, dans ce cas, bien sûr, nous obtenons moins de résultats arithmétiquement précis.

Comme compromis, vous pouvez refuser de mettre en œuvre une procédure ou un schéma GCD, et utiliser à la place quelque chose de mathématiquement simple, codé en dur dans le code et efficace, déterminant la divisibilité uniquement par 2, 3 et 5. Bien que de cette façon, nous ne trouvions pas un nombre exhaustif de diviseurs, par en pratique, cela conduirait à trouver un grand nombre d'abréviations. Pensez-y - la divisibilité par 2 se produit trois fois plus souvent que la divisibilité par 7, et 20 fois plus souvent que la divisibilité par 41!

Conclusion

Après cette expérience, j'ai commencé à croire qu'il est tout à fait possible qu'une représentation des nombres soit basée sur des nombres rationnels, semblable à ce que j'appelle la «fraction de ligne flottante». Une représentation compatible avec les entiers et capable d'effectuer de nombreuses opérations en arithmétique exacte pour de nombreuses tâches (à condition que les données d'entrée soient présentées sous une forme rationnelle). La version 64 bits (1 | 6 | 57) a un grand potentiel, bien que la version 32 bits (1 | 5 | 26) crée déjà des rendus intéressants.

Si ce n'était pas une expérience pour deux soirées, mais quelque chose de professionnel créé dans un studio ou une entreprise, alors à l'avenir, les mesures suivantes pourraient être prises:

* Obtenez un histogramme du nombre de pixels tracés avec précision et pas exactement (en d'autres termes, la fréquence d'exécution de normalisation)
* Essayez d'implémenter une réduction codée en dur sur les séparateurs 2, 3 et 5 et mesurez le pourcentage de pixels exacts perdus
* Afficher la différence en pixels entre le rendu en virgule flottante et le rendu en virgule flottante fraction
* Trouvez des façons ingénieuses d'utiliser les valeurs inutilisées du format binaire "fractions de ligne flottante", par exemple, pour désigner Inf et NaN
* Implémenter la détection de NaN, Inf, underflow, overflow.

Dans l'ensemble, c'était une étude fascinante. Au cours du processus, j'ai découvert quelques surprises, j'ai trouvé une petite invention et j'ai beaucoup appris sur l'équation de Pell, les racines carrées, le GCD, les mécanismes internes x86_64, la fonction zêta de Riemann et certains autres aspects. J'en suis très content!

Est-il possible de rendre des images réalistes sans nombres à virgule flottante?