À l’époque où les cartes graphiques n’existaient pas, un ingénieux développeur, John Carmack, travaillait sur des techniques de rendus 3D sur des ordinateurs qui, à l’époque, ne géraient pas ce type de calcul. Outre son génie pour accélérer certains calculs (racine carrée et racine inverse par exemple), il développa Wolfenstein 3D en utilisant la technique de Raycasting. C’est cette technique que nous allons étudier et réussir à intégrer dans une page Web via la balise canvas.

N’ayez craintes, il ne faudra pas avoir un diplôme supérieur de mathématique pour comprendre. Dans notre cas nous n’allons utiliser que des connaissances de 2de en trigonométrie, nous ne nous pencherons pas sur les optimisations possibles pour le moment. L’idée est de savoir afficher un objet en “pseudo-3D” en gérant les perspectives.

Avant de commencer à travailler sur la balise canvas, nous verrons ce qu’elle propose et quelles sont ses limites. Après cela nous tenterons de regarder comment va se passer notre travail pour simuler la 3D en gérant un axe “z” en plus d’une longueur focale indispensable au rendu 3D.

Tout cela sera étudier avec une seule face pour le moment.

Enfin, nous étudierons comment procéder à une rotation d’objet sur les 3 axes pour enfin implémenter cela dans notre moteur 3D.

Nous verrons comment travailler avec plusieurs faces pour afficher un objet composé et nous répondrons à des problème d’ordre d’affichage.

Enfin, nous tenterons de simuler un effet de lumière basique qui ne prendra pas trop de temps de calcul.

Canvas et la 3D

Introduite depuis quelques années dans les navigateurs “modernes”, la balise canvas fera partie de la norme HTML5. Déjà supportée par Firefox, Safari (et webkit), Opera… elle permet de dessiner des formes “primitives” sur une zone donnée. Seul Internet Explorer ne supporte pas cette balise, mais le projet “ex-canvas” permet une conversion assez optimal d’un canvas en VML (le langage verctoriel de Microsoft) avec tout de même quelques lacunes.

Un projet de support 3D (via openGL) dans cette balise existe mais n’est pas encore très bien implémenté. D’ailleurs, le support de la 3D dans la balise Canvas ne fonctionne qu’avec une extension sur Firefox en version beta à l’heure où j’écris ces ligne (firefox 3.5 beta).

Pour l’heure donc, la balise Canvas ne gère que deux axes, en l’occurrence: x et y. Cela suffit aisément pour dessiner des formes simples, des dégradés, etc… mais pour simuler de la 3D nous avons besoin d’un axe supplémentaire: “z”.

Cet axe permet de gérer la profondeur. Il va donc falloir simuler la gestion de cet axe.

Le Raycast

Le terme “Raycast” signifie à quelque chose près “lancer de rayon”. La méthode consiste à lancer un rayon en direction de la caméra et de savoir où il apparait sur les axes x et y.

Le rayon part de son origine, traverse la lentille et va en direction du “point de focal”. Ce que nous devons afficher se trouve sur la lentille. Donc tous les rayons filent vers le points de focal.

Les rayons coupent la “lentille” qui est en fait ce que nous cherchons à afficher:

Regardons vue du dessus ce que cela donne, c’est à dire sur l’axe Y:

vous pouvez repérer deux triangles inscrits. ABC et ADE. Le théorème de Thalès nous dit: AD/AB = AE/AC = DE/BC

Or, le point C est connu, nous connaissons ses coordonnées (x,z). Nous avons donc: -BC qui vaut “x” -DB qui vaut “z” -la longueur focale AD

et nous cherchons simplement le point E. Donc: -AB = AD + DB = focale + z -donc AD/AB = focale / (focale + z) -DE/BC = DE/x

On applique le théorème, on dit que Cx est l’abscisse x sur la Caméra du point à dessiner: -DE/x = focale / (focal+z) -donc Cx = DE = x * focale / (focale+z)

DE étant l’abscisse (Cx) que nous devons trouver pour le dessiner sur la canvas.

On peut reporter cela en se plaçant sur l’axe x pour trouver le points d’intersection Cy:

Cy = y * focale / (focale+z)

Nous savons désormais trouver les coordonnées du point d’intersection du rayon vers notre caméra connaissant: -les coordonnées du points de la forme -la longueur focale de la caméra

Reste désormais à l’appliquer sur le canvas.

Fonctionnement du canvas

Créons un simple document avec à l’intérieur:

...
<body>
    <canvas width="500" height="500" id="myscene"></canvas>
</body>

Nous nous servirons de cette base pour tout nos exemples. La balise étant créée dans notre corps de page enregistrée, nous pouvons afficher cette page dans Firefox, Opera, etc…

Le principe est simple, il suffit de créer un script javascript qui va: -récupérer la balise canvas avec getElementById par exemple -récupérer le context 2D de la balise canvas -dessiner avec les méthodes prévues à cet effet (moveTo, lineTo, stroke, fill…)

Une animation consistera à faire: -récupérer la balise canvas avec getElementById par exemple -récupérer le context 2D de la balise canvas -en boucle, toutes les N milisecondes -aller en 0,0 (haut du canvas à gauche, l’origine du repère) -effacer le canvas -dessiner avec les méthodes prévues à cet effet (moveTo, lineTo, stroke, fill…) -etc…

Notez bien, l’origine du repère orthonormé est en haut à gauche. X évolue vers la droite et Y vers le **bas**, il faudra donc inverser Y lors de nos calculs.

comme il est peu pratique de travailler depuis le coin du canvas, nous déplacerons le repère au centre du canvas avant de dessiner.

Premier raycaster simple

Nous allons commencer avec un simple polygone. Le principe étant de dessiner les 4 points qui définissent une face. On va le définir avec 4 listes de points x,y,z: var squarePoints = [ {x: -100, y: -100, z:0}, {x: 100, y: -100, z: -50}, {x: 100, y: 100, z: -50}, {x: -100, y: 100, z: 0} ];

Notre polygone est donc légèrement orienté puisque nous utilisons l’axe z

Pour l’afficher, il suffit de dessiner des traits entre chaque points et de demander au canvas de remplir la forme (path) ainsi créée: ` window.onload = function (){

//prepare square
var squarePoints =  [
    {x: -100, y: -100, z:0},
    {x: 100, y: -100, z: -50},
    {x: 100, y: 100, z: -50},
    {x: -100, y: 100, z: 0}
];


var canvas = document.getElementById('myscene');
var ctx = canvas.getContext('2d');
ctx.fillStyle="#AAAAAA";
ctx.strokeStyle="#AA6666";    
    
//on va au centre du canvas
ctx.translate(canvas.width/2, canvas.height/2);

//on se place au premier point
ctx.moveTo(squarePoints[0].x,squarePoints[0].y);

//et pour chaque point qui suit... on fait une ligne
//jusqu'à ce dernier
for(i=1; i<squarePoints.length; i++){
    ctx.lineTo(squarePoints[i].x,squarePoints[i].y);
}
//on ferme la forme, on rempli de la couleur et on dessine les traits
ctx.lineTo(squarePoints[0].x,squarePoints[0].y);
ctx.fill(); 
ctx.stroke();

} `

Jusqu’ici tout va bien sauf que nous n’utilisons toujours pas l’axe “z”… La preuve, on ne remarque pas l’orientation:

Utilisons ce que nous avons trouvé lors de la première partie, à savoir le calcul selon la focal et z pour retrouver x et y: `

function getZ (point,focal){ point.x = ( focal / (focal + point.z) ) * point.x; point.y = - ( focal / (focal + point.z) ) * point.y; } `

Remarquez que j’inverse “y” à partir de maintenant puisque, comme je vous l’ai expliqué, l’axe des ordonnées est dirigé vers le bas.

Appliquons maintenant notre fonction:

` window.onload = function (){

var focal = 300;

//prepare square
var squarePoints =  [
    {x: -100, y: -100, z:50},
    {x: 100, y: -100, z: 50},
    {x: 100, y: 100, z: 0},
    {x: -100, y: 100, z: 0}
];


var canvas = document.getElementById('myscene');
var ctx = canvas.getContext('2d');
ctx.fillStyle="#AAAAAA";
ctx.strokeStyle="#AA6666";    
    
//go to center of canvas and place new center here
ctx.translate(canvas.width/2, canvas.height/2);

//go to first point and draw x,y,z coord
getZ(squarePoints[0],focal);

ctx.moveTo(squarePoints[0].x,squarePoints[0].y);
for(i=1; i<squarePoints.length; i++){
    getZ(squarePoints[i],focal);
    ctx.lineTo(squarePoints[i].x,squarePoints[i].y);
}
ctx.closePath(); ctx.fill(); ctx.stroke();

}

function getZ (point,focal){ point.x = ( focal / (focal + point.z) ) * point.x; point.y = - ( focal / (focal + point.z) ) * point.y; } `

• • Remarque**: j’ai volontairement supprimé le signe “-” pour recalculer la coordonnée “y” des points pour que getZ inverse lui même la valeur. Cela restera plus pratique.

Vous voyez aussi que j’utilise désormais une nouvelle variable nommée “focal”. Elle contiendra la valeur focale (ici 300) pour calculer la réduction selon z.

Cette fois, ça fonctionne. Nous voyons un segment plus court qui nous donne une illusion de profondeur.

Nous allons maintenant passer à quelque chose d’un peu plus complexe, à savoir la rotation selon 3 axes des points. Cela nous mènera tout droit à une animation de rotation de forme.

Rotation selon 3 axes

Encore une fois, il nous faut réviser nos cours de Mathématiques du lycée pour retrouver nos repères. On pose cette figure:

Petit rappel, en trigonométrie la rotation est anti-horaire, c’est à dire dans le sens inverse des aiguilles du montre. Connaissant theta ø, on peut retrouver les coordonnées d’un point après rotation.

On a: -x’ = x cos(ø) - y sin(ø) -y’ = x sin (ø) + y cos (ø)

Dans notre cas, il faudra appliquer ces transformations sur les 3 axes les un après les autres. Là où il peut y avoir confusion c’est dans la marche à suivre… En fait, à chaque axe utilisé nous devons trouver les coordonnées des axes qui définissent le point.

En l’occurence, quand nous tournons sur -x il faut trouver (y,z) -y il faut trouver (x,z) -z il faut trouver (x,y)

C’est ainsi que nous allons faire une méthode qui sache gérer une rotation.

` function rotatePoint(point,rotation) {

var cz = Math.cos(rotation.z);
var sz = Math.sin(rotation.z);

var cx = Math.cos(rotation.x);
var sx = Math.sin(rotation.x);

var cy = Math.cos(rotation.y);
var sy = Math.sin(rotation.y);

var x = point.x;
var y = point.y;
var z = point.z;

//around x
var xy = cx*y - sx*z;
var xz = sx*y + cx*z;

//around y
var yz = cy*xz - sy*x;
var yx = sy*xz + cy*x;

//around z
var zx = cz*yx - sz*xy;
var zy = sz*yx + cz*xy;

//retourne les dernières valeurs trouvée pour x, y et z donc 
// zx, zy et yz
return {x: zx, y: zy, z: yz};

} `

Bien, reprenons notre exemple et modifions le code pour gérer une rotation:

` window.onload = function (){

var focal = 600;

var rotation = {
    x: 0.4,
    y: 0,
    z: 0
};


//prepare square
var squarePoints =  [
    {x: -100, y: 0, z: -100},
    {x: 100, y: 0, z: -100},
    {x: 100, y: 0, z: 100},
    {x: -100, y: 0, z: 100}
];


var canvas = document.getElementById('myscene');
var ctx = canvas.getContext('2d');
ctx.fillStyle="#AAAAAA";
ctx.strokeStyle="#AA6666";    

//go to center of canvas and place new center here
ctx.translate(canvas.width/2, canvas.height/2);
ctx.beginPath()

//go to first point and draw x,y,z coord
var p0 = rotatePoint(squarePoints[0],rotation);
p0 = getZ(p0,focal);                    
ctx.moveTo(p0.x,p0.y);    
//for each following points, get coords and draw a line to it
for(i=1; i<squarePoints.length; i++){
    var p = rotatePoint(squarePoints[i],rotation);
    console.debug(p)
    p = getZ(p,focal);
    console.debug(p)           
    ctx.lineTo(p.x,p.y);
}

//close shape
ctx.lineTo(p0.x,p0.y);
//fill and draw edges
ctx.fill(); ctx.stroke();

}

function getZ (point,focal){ x = ( focal / (focal + point.z) ) * point.x; y = - ( focal / (focal + point.z) ) * point.y; return {x: x, y: y, z: point.z} }

function rotatePoint(point,rotation) {

var cz = Math.cos(rotation.z);
var sz = Math.sin(rotation.z);

var cx = Math.cos(rotation.x);
var sx = Math.sin(rotation.x);

var cy = Math.cos(rotation.y);
var sy = Math.sin(rotation.y);

var x = point.x;
var y = point.y;
var z = point.z;

//around x
var xy = cx*y - sx*z;
var xz = sx*y + cx*z;

//around y
var yz = cy*xz - sy*x;
var yx = sy*xz + cy*x;

//around z
var zx = cz*yx - sz*xy;
var zy = sz*yx + cz*xy;

//retourne les dernières valeurs trouvée pour x, y et z donc 
// zx, zy et yz
return {x: zx, y: zy, z: yz};

} `

Le résultat est concluant:

La rotation s’est faite autour de l’axe x, mais vous pouvez tester avec des valeur sur y et z… un combinaison de rotation et de focale plus courte donne : ` var focal = 300;

var rotation = {
    x: 0.4,
    y: 0.1,
    z: 0.8
};

`

Passons maintenant à quelque chose de plus sympathique, à savoir: animer la rotation.

Animation de rotation

Un canvas à le mérite de répondre rapidement à l’affichage. Nous aurons donc aucun mal à dessiner notre plan toutes les 25iéme de seconde pour simuler une rotation.

Il est important de noter une chose en ce qui concerne la balise canvas. Tout affichage se cumule à l’autre, il va falloir donc effacer son contenu à chaque fois que nous voulons afficher notre forme. Afin d’être plus clair, nous allons déporter nos lignes de dessin dans une fonction que nous nommerons “drawFace”.

`

//keep current rotation value var currentRotation={ x:0, y:0, z:0 };

function drawFace(point, rotation, focal, ctx, canvas) { currentRotation.x += rotation.x;
currentRotation.y += rotation.y; currentRotation.z += rotation.z;

ctx.clearRect(0,0,canvas.width,canvas.height);

ctx.save()
//go to center of canvas and place new center here
ctx.translate(canvas.width/2, canvas.height/2);
ctx.beginPath()
 
//go to first point and draw x,y,z coord
var p0 = rotatePoint(point[0],currentRotation);
p0 = getZ(p0,focal);                    
ctx.moveTo(p0.x,p0.y);    
//for each following points, get coords and draw a line to it
for(i=1; i<point.length; i++){
    var p = rotatePoint(point[i],currentRotation);
    p = getZ(p,focal);
    ctx.lineTo(p.x,p.y);
}

//close shape
ctx.lineTo(p0.x,p0.y);
//fill and draw edges
ctx.fill(); ctx.stroke();
ctx.restore();

//redraw in 1000/25 seconds
setTimeout(function (){
    drawFace(point, rotation, focal, ctx, canvas)
},1000/25)

} `

L’exemple est ici:

Code source javascript

Pour le moment nous avons travaillé avec une seule face de 4 points. Cela dit un objet complexe est composé de plusieurs faces. Un cube contient justement 6 faces de 4 points. Plutot que de redéfinir tous les points pour chaque faces, il est préférable de déclarer nos 8 points et ensuite de composer nos faces avec ces derniers: ` var points = [ {x:-100,y:100,z:-100}, {x:-100,y:-100,z:-100},
{x:100,y:-100,z:-100},
{x:100,y:100,z:-100}, {x:-100,y:100,z:100}, {x:-100,y:-100,z:100},
{x:100,y:-100,z:100},
{x:100,y:100,z:100} ];

var faces = [ [points[0],points[1],points[2],points[3]], [points[4],points[5],points[6],points[7]],
[points[3],points[2],points[6],points[7]], [points[0],points[1],points[5],points[4]], [points[0],points[3],points[7],points[4]], [points[1],points[2],points[6],points[5]] ]; `

Désormais il faut repenser notre façon d’afficher. Nous allons créer une méthode drawObject qui va appeler drawFace toute les 25ieme de seconde. La méthode drawFace ne va plus gérer le rafraichissement et laisser drawObject vider le canvas.

Une autre modification est le fait de ne plus enregistrer la rotation courante dans un objet à part, mais de changer directement les coordonnées des points et les garder tels quels.

Voici les deux méthodes:

` function drawObject(faces, rotation, focal, ctx, canvas){

//recalcule les points de chaque face
//selon la rotation donnée 
for(i in faces){
    for (p in faces[i]){
        faces[i][p] = rotatePoint(faces[i][p],rotation);
    }
}

//efface le canvas
ctx.clearRect(0,0,canvas.width,canvas.height);

//Pour chaque faces on dessine
for(k=0 ; k<faces.length ; k++){
    var f=faces[k]
    drawFace(f, rotation, focal, ctx, canvas)
}

//et on recommence dans 1/25ieme de seconde
setTimeout(function (){
    drawObject(faces, rotation, focal, ctx, canvas)
},1000/25)

}

function drawFace(face, rotation, focal, ctx, canvas) {

ctx.save()
//va au centre du canvas et prépare une forme
ctx.translate(canvas.width/2, canvas.height/2);
ctx.beginPath()
 
//on va au premier point
var p0 = getZ(face[0],focal);                   
ctx.moveTo(p0.x,p0.y);   

//et pour tout les points restant, on recalcul x et y selon la focale
//puis on prépare une ligne
for(i=1; i<face.length; i++){
    var p = getZ(face[i],focal);
    ctx.lineTo(p.x,p.y);
}

//et ferme la forme
ctx.lineTo(p0.x,p0.y);

//on rempli et on dessine les traits
ctx.fill(); ctx.stroke();
ctx.restore();

} `

Sauf que voilà… le résultat est presque bon mais un souci apparait:

La raison est en fait toute simple. Nous avons défini un ordre d’affichage de base pour nos faces, mais après rotation les faces du fond apparaissent en dernier et sont donc dessiner sur les faces de premier plan.

La solution est de reclasser nos faces selon z. J’ai donné une bonne méthode de classement dans mon billet traitant des tris de tableaux en javascript. Nous devons effectivement classer un tableau d’objets selon une propriété donnée.

Il suffit donc de créer une méthode simple: ` function sortZ(a,b){ var max1=0; var max2=0;

    for (i in a){
        max1 += -a[i].z 
    }
    max1 = max1/a.length;
    for (i in b){
        max2 += -b[i].z 
    }
    max2 = max2/b.length;
    
    return max1 - max2;

} `

Cette fonction regarde une face et la suivante, on calcule la profondeur moyenne de ces dernières et on regarde si la première est plus profonde que la seconde…

Cela va nous permettre de reclasser les faces selon z, il faut le faire **avant** la boucle d’appel à drawFace. Donc dans notre méthode drawObject: `

function drawObject(faces, rotation, focal, ctx, canvas){

for(i in faces){
    for (p in faces[i]){
        faces[i][p] = rotatePoint(faces[i][p],rotation);
    }
}

//on reclasse nos faces selon Z   
faces.sort(sortZ)

ctx.clearRect(0,0,canvas.width,canvas.height);
for(k=0 ; k<faces.length ; k++){
    var f=faces[k]
    drawFace(f, rotation, focal, ctx, canvas)
}

setTimeout(function (){
    drawObject(faces, rotation, focal, ctx, canvas)
},1000/30)

} `

Et le resultat nous donne:

Code source javascript

Nous pouvons simuler une lumière. Comme nous n’affichons qu’un simple cube, que nous ne voyons notre objet que depuis un point fixe, l’idée est de “faire semblant”.

La lumière part d’un point et se diffuse sur les objets. Ce qui ressemble le plus à cela dans un canvas s’appelle un “gradient”, c’est à dire un dégradé de couleur. Ici, j’utilise un gradient circulaire qui donne un meilleur résultat.

Il suffit simplement de modifier notre style de remplissage de cette manière: var lingrad = ctx.createRadialGradient(95,-130,15,80,20,500); lingrad.addColorStop(0, '#FFF'); lingrad.addColorStop(1, '#999'); ctx.fillStyle = lingrad;

Le résultat est plutôt agréable:

Code source javascript

Le raycasting peut paraître compliqué mais son application est plutôt simple. Il est très facile d’implémenter ces techniques dans Flash ou tout autre technologie permettant de dessiner des faces.

Certes, les exemples que je vous donne sont tapés “à la va vite”, j’entends par là que je n’ai opéré aucune optimisation, que je n’ai pas utilisé la notion de POO (programmation orientée objet) etc… mais je suis en train de travailler sur une librairie Javascript permettant de faire un peu mieux que cela.

Certes, mon travail sur le raycasting va certainement être mis à mal d’ici quelques mois puisque le canvas 3d va certainement devenir une révolution. En ce qui concerne mon point de vue sur la question, je vais préparer un article qui traitera du sujet “canvas, video, audio sur le HTML5”. Mais ici, l’heure était à l’étude de la création d’un raycaster.

Sachez donc que ce genre de script sur un canvas peut parfaitement être utilisé pour dessiner un histogramme en 3D provenant d’un tableau de valeur HTML, ou permettre de dessiner des pièces, des meubles ou tout autre objet dans une page “catalogue”.

J’espère que vous avez apprécié.