Centrale Informatique MP-PC-PSI 2021

Corrigé

(c'est payant, sauf le début) : - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


FF

te Informatique
___"" MP, PC, PSI, TSI

CONCOURS CENTRALE-SUPÉLEC 3 heures Calculatrice autorisée

Lancer de rayons

2021

Et qu'au contraire les chats voient de nuit par le moyen des rayons qui tendent 
de leurs yeux
vers les objets.
-- René Descartes, Discours de la méthode - La dioptrique(1637)

Le sujet présente une méthode de génération d'images en deux dimensions 
représentant des objets dans l'espace,
éclairés par des sources lumineuses. Cette technique appelée lancer de rayons 
s'appuie sur les lois de propagation
de la lumière, ce qui lui confère une grande qualité de rendu, au prix d'un 
temps de calcul souvent élevé.
L'augmentation de la puissance des processeurs devrait bientôt pouvoir rendre 
cette technique compatible avec
les jeux vidéo.

Figure 1 Boite en bois et boules!

Ce sujet propose d'illustrer les principales caractéristiques de la méthode, en 
se limitant à des scènes ne com-
portant que des sphères et des sources lumineuses ponctuelles.

De nombreuses questions sont indépendantes, il est toutefois demandé de les 
traiter dans l'ordre.

Les seuls langages informatiques autorisés dans cette épreuve sont Python et 
SQL. Pour répondre à une question,
il est possible, et souvent souhaitable, de faire appel aux fonctions définies 
dans les questions précédentes.

Les modules math et numpy ont été rendus accessibles grâce à l'instruction
import math, numpy as np

Dans tout le sujet, le terme « liste » désigne une valeur de type list. Le 
terme « tableau » désigne une valeur
de type np.ndarray. Enfin le terme « séquence » désigne une suite finie 
indiçable et itérable.

-- Indiçable signifie que les éléments sont accessibles par des indices, seq[0] 
désignant le premier élément de
la séquence seq.

Exemple fourni avec le logiciel libre de lancer de rayons POV-Ray. Fichier 
woodbox.pov, POV-Ray scene file by Dan Farmer, sous
licence Creative Commons Attribution-ShareAlike 3.0

1007/2021-03-23 10:08:26 Page 1/8 CIEL
-- [térable signifie que la séquence peut être parcourue dans une boucle par 
for element in seq:

Un tuple d'entiers, une liste d'entiers et un tableau d'entiers sont trois 
exemples de « séquence d'entiers ».

Les entêtes des fonctions demandées sont annotés pour préciser les types des 
paramètres et du résultat. Ainsi,
def uneFonction(n:int, X:[float]l, c:str, u) -> (np.ndarray, int):

signifie que la fonction uneFonction prend quatre paramètres n, X, c et u, où n 
est un entier, X une liste de

nombres à virgule flottante, c une chaine de caractères et le type de u n'est 
pas précisé. Cette fonction renvoie
un couple constituée d'un tableau et d'un entier.

Il n'est pas demandé aux candidats d'annoter leurs fonctions, la rédaction 
pourra commencer par

def uneFonction(n, X, c, u):

De façon générale, une attention particulière sera portée à la lisibilité, la 
simplicité et la clarté du code proposé.
L'utilisation d'identifiants significatifs, l'emploi judicieux de commentaires 
seront appréciés.

Une liste de fonctions potentiellement utiles est fournie à la fin du sujet.

I Géométrie

Dans tout le sujet, l'espace est muni d'un repère (O,ü,,ü,, d,) orthonormé 
direct. [ü| désigne la norme eucli-
dienne du vecteur v. Le produit scalaire de deux vecteurs v, et v, est noté U, 
- ,, leur produit terme à terme
(produit de Hadamard) est noté %, © % : V1 © Vo = Vi Vog dy + ViyVoydy + Vie 
Vos Use
Tout point ou vecteur de l'espace est représenté en Python par le tableau de 
ses trois coordonnées cartésiennes,
de type float. Pour faciliter la compréhension, un tel tableau est considéré de 
type point quand il désigne un
point et de type vecteur quand il désigne un vecteur : np.array([0.,0.,0.1) est 
considéré de type point
quand il représente le point © et de type vecteur quand il représente le 
vecteur nul.

Beaucoup d'opérations classiques sur les vecteurs se transposent simplement 
dans la syntaxe de numpy. Si ü.,
v, sont 2 vecteurs et & un réel, représentés respectivement par vi, v2 et t, 
alors Ü, + os, Ü, -- WU, Ü, O U et tÜ,
peuvent être calculés simplement par v1 + v2, vi - v2, vi *x v2et t * vi.

Quand il n'y a pas de confusion possible, un objet mathématique est assimilé à 
sa représentation en Python.
Ainsi, par exemple, « la fonction f prend en paramètre le vecteur ü, » signifie 
que la fonction f accepte des
valeurs de type vecteur représentant le vecteur ü..

On rappelle que la valeur du cosinus de l'angle formé par deux vecteurs 
unitaires correspond à la valeur de leur
produit scalaire. Aïnsi, si ü, et ü, sont deux vecteurs unitaires, cos(d1, do) 
-- Ü, : U. Par ailleurs, si à est un
vecteur unitaire et ü un vecteur quelconque, le projeté du vecteur ü dans la 
direction à est donné par (ü - d) ü.

Q 1. Écrire une fonction d'entête

def vec(A:point, B:point) -> vecteur:

qui prend deux points en paramètre et renvoie le vecteur AB.
Q 2. Écrire une fonction d'entête
def ps(vl:vecteur, v2:vecteur) -> float:
qui prend en paramètres deux vecteurs 4, et vw, et qui renvoie la valeur de 
leur produit scalaire V, : %.
Q 3. Écrire une fonction d'entête
def norme(v:vecteur) -> float:
qui prend en paramètre un vecteur vw et qui renvoie |ü|, la valeur de sa norme 
euclidienne.
Q 4. Écrire une fonction d'entête

def unitaire(v:vecteur) -> vecteur:

1 ne
qui prend en paramètre un vecteur v non nul et qui renvoie El le vecteur 
unitaire correspondant.
Ü

On utilise dans ce sujet le modèle du rayon lumineux de l'optique géométrique. 
Un rayon lumineux issu du point
S est une demi-droite d'origine $S. Ce rayon est représenté en Python par le 
couple (S,ü), où S'est le point de
départ du rayon et ü le vecteur unitaire donnant la direction de propagation du 
rayon lumineux. Tout point M
du rayon est tel que SM = tü, avec t EUR R'. Un tel couple est désignée dans la 
suite par le type rayon.

Ainsi, en définissant 0 = np.array([0., O0., 0.1] et u = np.array([0, 0.6, 
0.8], le couple (0, u) repré-
sente le rayon issu de O dans la direction 3üù,, + Au,

Q 5. Que font les fonctions pt, dir et ra ci-dessous ?

1 def pt(r:rayon, t:float) -> point:
2 assert t >= 0

3 (S, u) =r

4 return 9S +t *xu

1007/2021-03-23 10:08:26 Page 2/8 (cc) BY-NC-SA
5 def dir(A:point, B:point) -> vecteur:
6 return unitaire(vec(A, B))

7 def ra(A:point, B:point) -> rayon:

8 return À, dir(A, B)

Comme toutes les fonctions définies dans ce sujet, les fonctions pt, dir et ra 
peuvent être utilisées dans la suite.

Une sphère de centre Cet de rayon r > 0 est l'ensemble des points de l'espace 
situés à la distance r du point C!
Ici, elle est représentée en Python par le couple (C,r). Un tel couple est 
désigné par le type sphère.

Q 6. Écrire une fonction d'entête
def sp(A:point, B:point) -> sphère:
qui renvoie la sphère de centre À passant par B.

Q 7. Montrer qu'une droite passant par le point À de vecteur directeur à et une 
sphère (C',r) sont sécantes
si et seulement si l'équation d'inconnue t

82 + 2%4(ù . CA) + |CA? -- r? = 0 (1)

possède deux solutions réelles, éventuellement confondues.
Q 8. Écrire une fonction d'entête
def intersection(r:rayon, s:sphère) -> (point, float) or None:

qui renvoie le premier point de la sphère s frappé par le rayon lumineux r et 
la distance entre ce point et l'origine
du rayon. La fonction renvoie None si le rayon ne coupe pas la sphère. On 
suppose que l'origine du rayon n'est
pas située à l'intérieur de la sphère.

II Optique

Les couleurs seront représentées par des tableaux de 3 nombres flottants, 
associés dans la suite au type couleur.
Les trois composantes codent respectivement le niveau de rouge, vert et bleu de 
la couleur considérée (com-
posantes RVB). Chaque composante est comprise entre 0 et 1. Plus la valeur est 
élevée, plus la composante
contribue fortement à la couleur. Aïnsi, (1, 1, 1) correspond au blanc, (0, 0, 
0) au noir, (0.5, 0.5, 0.5) désigne
un gris moyen et (0.6, 1, 0.6) un vert pastel.

Pour toute la suite, on a défini les variables globales

noir = np.array([0., O., O.])
blanc = np.array([1., 1., 1.])

IT. À -- Visibilité
Q 9. Une source lumineuse ponctuelle S ne peut être vue d'un point P d'une 
sphère (C',r) que si la source est

au-dessus de l'horizon de P, défini ici comme le plan tangent à la sphère en P. 
Donner une condition géométrique
pour que la source soit au-dessus de l'horizon.

Q 10. Écrire une fonction booléenne, d'entête

def au_dessus(s:sphère, P:point, src:point) -> bool:
qui détermine si la source située en src est au-dessus de l'horizon du point P 
de la sphère s.
Q 11. On considère une scène contenant plusieurs sphères et une source 
lumineuse. Pour que la source soit
visible d'un point P d'une sphère particulière, il faut que cette source soit 
au-dessus de l'horizon et qu'aucune
autre sphère ne la cache. Ecrire une fonction booléenne d'entête

def visible(obj:{sphère], j:int, P:point, src:point) -> bool:
où le paramètre obj est une liste contenant les sphères de la scène et src 
l'emplacement de la source lumineuse.
Cette fonction détermine si la source est visible du point P, appartenant à la 
sphère obj[;jl1.

IT.B -- Diffusion

On considère un point P, à la surface d'une sphère, éclairé sous l'incidence 0 
par une source lumineuse S
ponctuelle de couleur C, = (R,,V,,B,). On note N le vecteur unitaire normal à 
la sphère en P, dirigé vers
l'extérieur de la sphère, et u le vecteur unitaire du rayon lumineux qui 
éclaire P en provenance de la source. On
considère que le point P diffuse la lumière de la source de manière isotrope 
dans tout le demi-espace délimité
par le plan tangent à la sphère en P qui contient la source (figure 2). 
Autrement dit, le point P diffuse la lumière
de la source dans toutes les directions w telles que w : N >0 (les vecteurs ü, 
w et N ne sont pas forcément
coplanaires) et la lumière diffusée ne dépend pas de la direction d'observation 
w, en particulier elle ne dépend
pas de 0".

1007/2021-03-23 10:08:26 Page 3/8 (cc) BY-NC-SA

Figure 2 Parcours de la lumière de la source à l'oeil

La faculté d'un objet à diffuser la lumière est modélisée par ses coefficients 
de diffusion k,,, k4, et ka qui
mesurent son aptitude à réémettre les composantes rouge, verte et bleue. Chaque 
coefficient est un nombre
à virgule flottante compris entre 0 et 1. On représente les coefficients de 
diffusion d'un objet par un triplet
ki = (kr: Ka: Kb) de type couleur. La couleur C, = (R,y, V,, B;) de la lumière 
diffusée par le point P éclairé
par la source $ suit alors la loi de Lambert :

Cy=(kaOC,)cos0 soit  (Ry, Vi, By) = (kyR, cos 0, ka, V.cos0, kB. cos Ü). (2)

Ecrire une fonction d'entête

Q 12.

def couleur _diffusée(r:rayon, Cs:couleur, N:vecteur, kd:couleur) -> couleur:
qui renvoie la couleur de la lumière diffusée par le point P éclairé par un 
rayon lumineux r en provenance d'une
source ponctuelle de couleur Cs. Les paramètres N et kd représentent 
respectivement le vecteur unitaire normal
à l'objet en P et les coefficients de diffusion de l'objet (figure 2). La 
source S'est supposée visible de P.

II.C --- Réflexion
Si la surface de l'objet est réfléchissante, au phénomène de diffusion s'ajoute 
le phénomène de réflexion. Lorsqu'un
rayon lumineux (S',ü) issu d'un point source S' atteint un point P de la 
surface, il donne naissance au rayon
réfléchi (P,w). Les lois de la réflexion de Descartes stipulent que, avec les 
notations de la figure 2,

-- ü, w et N sont coplanaires :

-->

-- (ü +%w):N = 0, ce qui correspond à 0" = 6.

Q 13.

def rayon_réfléchi(s:sphère, P:point, src:point ) -> rayon:

Ecrire une fonction d'entête

qui renvoie le rayon réfléchi par le point P de la sphère s en provenance de la 
source S' placée en src. Le résultat
est le couple (P,w) représentant le rayon émergent. La source S'est supposée 
visible de P.

IIT Enregistrement des scènes
Les différentes scènes à représenter sont enregistrées dans une base de données 
relationnelle. La figure 3 donne
sa structure physique.

Objet Scene Source
sc_1id|integer sc_1id integer sc_1id|integer
ob_1d|integer sc_creation |timestamp so_1id|integer---
ob_x float sc_modif timestamp SO_X float
ob_y float Sc_nom text SO_Yy float
ob_z float SO_Z float

Sphere Couleur Ponctuelle
--+ sp_1d integer co_id integer po_id |integer--
sp_rayon) float TT co_rouge| float EE co_id |integer
sp_kd integer co_vert float po_nom text
sp_kr float co_bleu float

Figure 3 Structure physique de la base de données des scènes

Page 4/8 CITES

1007/2021-03-23 10:08:26
Cette base comporte les six tables listées ci-dessous avec la description de 
leurs colonnes :
-- la table Scene répertorie les scènes
e sc_id identifiant (entier arbitraire) de la scène (clé primaire)
e sc_creation date de création de la scène
e sc modif date de dernière modification de la scène
e sc_nom nom de la scène
-- la table Couleur définit les couleurs utilisées
e co_id identifiant (entier arbitraire) de la couleur (clé primaire)
e co_rouge valeur de la composante rouge (dans l'intervalle [0, 1])
e co_vert valeur de la composante verte (dans l'intervalle [0, 1])
e co_bleu valeur de la composante bleue (dans l'intervalle [0, 1]|)
-- la table Sphere liste les sphères utilisées pour construire les scènes
e sp_id identifiant (entier arbitraire) de la sphère (clé primaire)
e sp_rayon rayon de la sphère
e sp_kd coefficients de diffusion de la sphère (référence dans la table Couleur)
e sp_kr coefficient de réflexion de la sphère (cf. partie V)
-- Ja table Ponctuelle répertorie les sources ponctuelles disponibles
e po_id identifiant (entier arbitraire) de la source ponctuelle (clé primaire)
e co_id couleur de la source (référence dans la table Couleur)
e po_nom nom de la source

-- la table Objet fait le lien entre les scènes et les objets qu'elles 
contiennent, ses deux premières colonnes
constituent sa clé primaire

e sc_id identifiant de la scène
e ob_id identifiant de l'objet
e ob_x, ob_y, ob_z coordonnées du centre de l'objet dans la scène considérée

-- la table Source indique quelles sont les sources qui éclairent chaque scène, 
ses deux premières colonnes
constituent sa clé primaire

e sc_id identifiant de la scène

e so _id identifiant de la source

e So_x, So_y, so_z coordonnées de la source dans la scène considérée
Q 14. Écrire une requête SQL qui donne le nom des scènes créées au cours de 
l'année 2021.
Q 15. Écrire une requête SQL qui donne, pour chaque scène, son identifiant et 
le nombre de sources qui
l'éclairent.

Q 16. Écrire une requête SQL qui liste l'identifiant, les coordonnées du centre 
et le rayon de toutes les sphères
contenues dans la scène dont le nom est woodbox. On suppose qu'une seule scène 
possède ce nom.

Il est possible en SQL de définir des fonctions utilisateur qui s'utilisent 
comme les fonctions SQL pré-définies.

On dispose d'une fonction utilisateur booléenne de signature OCCULTE(sc_id, 
objr_id, so_id, objo_id) où
sc_id, objr_id, so_id et objo_id sont les identifiants respectifs d'une scène, 
d'un objet de cette scène dit
« récepteur », d'une source de cette scène et d'un autre objet de la scène dit 
« occultant ». La fonction renvoie
TRUE si l'objet occultant projette son ombre sur l'objet récepteur lorsqu'il 
est éclairée par la source considérée.

Q 17. Écrire une requête SQL qui, pour la scène woodbox. renvoie tous les 
triplets objr_id, so_id, objo_id
pour lesquels l'objet d'identifiant objo_id occulte la source d'identifiant 
so_id pour l'objet d'identifiant objr_id.

IV Lancer de rayons

Cette partie implante l'algorithme qui génère l'image 2D de la scène 3D à 
visualiser. Pour représenter une scène
en Python, on utilise les quatre variables globales suivantes :

-- Objet est une liste des n,, objets (sphères de type sphère) contenues dans 
la scène à représenter :

-- KdObj est une liste de n, tableaux de type couleur représentant les 
coefficients de diffusion des sphères,
Kd0bj[il est associé à la sphère Objet [il] :

-- Source est une liste de n, points (de type point) donnant l'emplacement des 
n, sources lumineuses (ponc-
tuelles) qui éclairent la scène à représenter :

-- ColSrc est une liste de n, couleurs, ColSrclil représente la couleur de la 
source placée en Sourcelil].

Pour des raisons d'efficacité, il est d'usage de construire le parcours de la 
lumière de l'oeil vers les sources : on
« lance » des rayons. Cela est possible grâce au principe du retour inverse de 
la lumière : un rayon parcourt le

1007/2021-03-23 10:08:26 Page 5/8 (cc) BY-NC-SA
même chemin pour joindre 2 points À et B, qu'il aille de B vers À ou de À vers 
B. Dans la suite, les vecteurs
unitaires caractérisant les rayons sont donc orientés dans le sens opposé au 
sens réel de propagation de la lumière.

Q) ü

À

Figure 4 Une scène avec 3 sphères et 2 sources ponctuelles

Un écran translucide est placé dans le plan (O, ü,. dy). Le point © coïncide 
avec le centre de l'écran.
Il sépare les objets de la scène, placés dans le demi espace z < 0, de l'oeil Q placé de l'autre côté : za > 0.

IV.A - Écran

L'écran est un carré de côté 6, divisé en N x N cases (N pair) qui représentent 
les pixels de l'image finale. Les
variables globales Delta et N contiennent respectivement les valeurs de 6 et N.

Q 18. Écrire une fonction d'entête
def grille(i:int, j:int) -> point:
qui renvoie les coordonnées cartésiennes du point E, centre de la case repérée 
par les indices (à, j) de la grille
(figure 4).
Q 19. Écrire une fonction d'entête
def rayon_écran(omega:point, i:int, j:int) -> rayon:

qui renvoie le rayon issu du point omega et passant par ÆE{(i, j).

IV.B --- Couleur d'un pixel

Dans un premier temps, les objets de la scène à représenter sont supposés 
parfaitement mats, ils se contentent
de diffuser la lumière des sources sans la réfléchir.

On considère un point P d'un objet de la scène atteint par un rayon issu de 
l'oeil. On note E le point de l'écran
coupé par ce rayon allant de l'oeil au point P. La couleur C, = (R;,, Va, B;) 
diffusée par P est la somme des
couleurs diffusées par ce point, dues à l'éclairement des sources visibles du 
point P.

Ch = > (ka O C,,) cos 6;. (3)

S,; visibles

On suppose que les couleurs ne saturent pas : toutes les composantes de C", 
restent inférieures à 1. La couleur
C', est affectée au point E de l'écran.

Q 20. Écrire une fonction d'entête
def interception(r:rayon) -> (point, int) or None:

qui prend en paramètre un rayon r et qui renvoie le premier point matériel de 
la scène atteint par ce rayon
ainsi que l'indice de la sphère concernée dans la liste Objet. Si le rayon 
n'intercepte aucune sphère, la fonction
renvoie None.

Q 21. Écrire une fonction d'entête
def couleur _diffusion(P:point, j:int) -> couleur:

qui renvoie la couleur diffusée par le point P appartenant à la sphère 
Objet[j]. Si aucune source n'éclaire P, la
fonction renvoie noir.

IV.C --- Constitution de l'image

L'image de la scène que l'on souhaite obtenir est construite dans un tableau à 
3 dimensions, de taille N X N X3,
associé au type image. L'affectation de la couleur c de type couleur au pixel 
(i,j) de l'image im s'écrira
simplement imli, j] = c.

1007/2021-03-23 10:08:26 Page 6/8 (cc) BY-NC-SA
Q 22. Écrire une fonction d'entête
def lancer(omega:point, fond:couleur) -> image:

qui génère l'image associée à la scène. Si un rayon n''intercepte aucun objet, 
le pixel correspondant est de couleur
fond.

IV.D --- Complexités

Les complexités asymptotiques seront exprimées en fonction du nombre N de 
lignes de l'image, du nombre n,
d'objets et du nombre n., de sources.

Q 23. Calculer la complexité temporelle de la fonction lancer dans le meilleur 
des cas en caractérisant la
situation correspondante.

Q 24. Calculer la complexité temporelle de la fonction lancer dans le pire des 
cas en caractérisant la situation
correspondante.

V Améliorations

V.A --- Prise en compte de la réflexion

Désormais les sphères sont supposées au moins partiellement réfléchissantes. Un 
rayon issu de l'oeil peut alors
se réfléchir successivement sur plusieurs sphères.

Q 25. Écrire une fonction d'entête
def réflexions(r:rayon, rmax:int) -> [(point, int)]l:

qui renvoie une liste de couples (P,,1i,) correspondant aux points 
successivement rencontrés par le rayon r au
fur et à mesure de ses réflexions. Dans chaque couple, P, est le point où a 
lieu la (4 + 1)°"® réflexion et i, est
l'indice de l'objet contenant P,. Le résultat comporte au plus rmax éléments, 
les éventuelles réflexions ultérieures
ne sont pas prises en compte.

Le pouvoir réfléchissant d'un objet est caractérisé par un coefficient de 
réflexion k,. propre à chaque objet,
0 < k, < 1. Les coefficients de réflexion des objets de la scène (de type float) sont stockés dans une liste globale Kr0bj à n, éléments, telle que Kr0bj [li] est le coefficient de réflexion de l'objet Objet [il]. En tenant compte des phénomènes de diffusion et de réflexion, la couleur EUR, = (R,, V,, B,) du point P, vaut Cr = Car + krCry (4) où C'y désigne la couleur diffusée par le point P, (cf. IV.B) et C, vaut noir si k est supérieur au nombre de réflexions considérées. Q 26. Écrire une fonction d'entête def couleur _perçue(r:rayon, rmax:int, fond:couleur) -> couleur:

qui renvoie la couleur du premier point de la scène rencontré par le rayon r en 
tenant compte d'au maximum
rmax réflexions de ce rayon. Si le rayon ne rencontre aucun objet, la fonction 
renvoie la couleur fond.

Q 27. Écrire une fonction d'entête

def lancer _complet(omega:point, fond:couleur, rmax:int) -> image:
qui construit l'image de la scène en tenant compte des diffusions et des 
réflexions.
Q 28.  Exprimer la nouvelle complexité dans le pire cas.

V.B - Une optimisation
On construit, à partir de la base de données, les deux listes globales :
-- Id0bj telle que Id0bj [il soit l'identifiant dans la base de données (ob_id) 
de la sphère Objet Li] :

-- IdSrc telle que IdSrclil soit l'identifiant dans la base de données (so_id) 
de la source Sourceli].

Q 29. Écrire la fonction d'entête

def table risque(risque:[lint, int, intl) -> [[lintl]]l:
qui prend en paramètre une liste de triplets correspondant au résultat de la 
requête SQL de la question 17 et
construit une liste de listes de listes d'entiers telle que, si res est le 
résultat de la fonction, res[il[j] donne
la liste (éventuellement vide) des indices des objets susceptibles de masquer 
la source Sourcel[j] pour un point
de l'objet Objet[il.
Q 30. Le résultat de la fonction table_risque est conservé dans la variable 
globale TableRisque. Écrire la
fonction visible _opt d'entête

def visible _opt(j:int, k:int, P:point) -> bool:
qui prend en paramètres l'indice j d'une source, l'indice k d'une sphère et un 
point P de cette sphère et qui,
comme la fonction visible de la question 11, détermine si la source Sourcelj]l 
est visible à partir du point P.

1007/2021-03-23 10:08:26 Page 7/8 (cc) BY-NC-SA
Opérations et fonctions disponibles en Python et en SQL

Constantes

math.inf, np.inf correspondent à +co, n'importe quel nombre est strictement 
inférieur à cette valeur.

Fonctions Python diverses

range (n) itérateur sur les n premiers entiers (]0,n --1]).

list(range(5)) -- [0, 1, 2, 3, 4].

range(d, f, p) où d, f et p sont des entiers, itérateur sur les entiers (r, = 
d+ip|r, < f);en si p > 0 et
(r, = d+iplr; > fh;en si p < 0. Le paramètre p est optionnel avec une valeur par défaut de 1. list(range(1, 5)) -- [1, 2, 3, 4]: list(range(20, 10, -2)) -- [20, 18, 16, 14, 12]. math.sqrt(x) calcule la racine carrée du nombre x. Opérations sur les listes len(L) donne le nombre d'éléments de la liste L. Li + L2 construit une liste constituée de la concaténation des listes L1 et L2. e in Let e not in L déterminent si l'objet e figure dans la liste L. Ces opérations ont une complexité temporelle en O(l1en(L)). L.append(e) ajoute l'élément e à la fin de la liste L. L.index(e) renvoie le plus petit entier i tel que Li] == e. Lève l'exception ValueError si l'élément e n'apparait pas dans la liste. Cette opération à une complexité temporelle en O(len(L)). L.sort() trie en place la liste L (qui est donc modifiée) en réordonnant ses éléments dans l'ordre croissant. Opérations sur les tableaux (np.ndarray) np.array(s, dtype) crée un nouveau tableau contenant les éléments de la séquence s. La taille de ce tableau est déduite du contenu de s. Le paramètre optionnel dtype précise le type des éléments du tableau crée. np.empty(n, dtype), np.empty((n, m), dtype) crée respectivement un tableau à une dimension de n éléments et un tableau à n lignes et m colonnes dont les éléments, de valeurs indéterminées, sont de type dtype. 5i le paramètre dtype n'est pas précisé, il prend la valeur float. np.zeros(n, dtype), np.zeros((n, m), dtype) fonctionne comme np.empty en initialisant chaque élé- ment à la valeur zéro pour les types numériques ou False pour les types booléens. np.sum(a) ou a.sum() renvoie la somme des éléments du tableau a. np.inner(a, b) calcule la somme des produits terme à terme dans le cas où a et b sont deux tableaux à une dimension de même taille. np.all(a) vaut True si tous les éléments du tableau a ont une valeur logique « vrai ». np.any(a) vaut True si au moins un des éléments du tableau a a une valeur logique « vrai ». SQL SELECT ... FROM t1 JOIN t2 ON ... effectue une requête sur le résultat du produit cartésien entre les tables ti et t2 restreint par la condition indiquée. Par exemple t1.a = t2.b permet de limiter le résultat aux lignes pour lesquelles la colonne a de la table t1 est égale à la colonne b de la table t2. SELECT ... FROM t AS t1 JOIN t AS t2 ON ... effectue une requête sur le résultat du produit cartésien de la table &t avec elle-même restreint par la condition indiquée. Le premier exemplaire de la table &t est désigné par ti et le second par t2. La fonction EXTRACT (part FROM t) extrait un élément de t, expression de type date, time, timestamp (jour et heure) ou interval (durée). part peut prendre les valeurs year, month, day (jour dans le mois), doy (jour dans l'année), dow (jour de la semaine), hour, etc. Les fonctions d'agrégation SUM(e), AVG(e), MAX(e), MIN(e), COUNT(e), COUNT(*) calculent respectivement la somme, la moyenne arithmétique, le maximum, le minium, le nombre de valeurs non nulles de l'expression e et le nombre de lignes pour chaque groupe de lignes défini par la cause GROUP BY. Si la requête ne comporte pas de clause GROUP BY le calcul est effectué pour l'ensemble des lignes sélectionnées par la requête. ee erFINee.e 1007/2021-03-23 10:08:26 Page 8/8 (cc) BY-NC-SA

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique MP-PC-PSI 2021 -- Corrigé
Ce corrigé est proposé par Cyril Ravat (professeur en CPGE) ; il a été relu par
Julien Dumont (professeur en CPGE) et Benjamin Monmege (enseignant-chercheur
à l'université).

Ce sujet a pour objectif la réalisation d'une image en deux dimensions 
représentant une scène simple, composée de plusieurs sources lumineuses et de 
plusieurs
objets, choisis sphériques pour simplifier le problème. Il permet d'aborder une 
technique très efficace de fabrication d'images virtuelles et demandant peu de 
ressources.
Les structures manipulées sont des tableaux numpy et des fonctions sont données 
pour
en faciliter l'usage.
· La partie I permet la construction des fonctions élémentaires de géométrie et
des premiers objets optiques tels que rayons, sphères et intersections des deux.
· Dans la partie II, l'étude évolue vers la problématique de la visibilité d'une
source lumineuse depuis un point d'une sphère et de la couleur obtenue compte
tenu de la lumière de la source et de l'incidence du rayon lumineux.
· La partie III, indépendante du reste de l'énoncé, demande de traiter 
l'enregistrement des données relatives à une scène (positions et couleurs des 
objets et
des sources) au sein d'une base de données. C'est l'occasion de poser quatre
questions de langage SQL d'un niveau très progressif.
· L'étude entre dans le vif du sujet à la quatrième partie, avec la modélisation
du « lancer de rayons », considération physiquement fausse mais compatible
avec la réalité qui consiste à imaginer que les rayons lumineux partent de 
l'oeil.
On modélise ces rayons et leur première intersection avec les objets de la 
scène,
puis on étudie la couleur vue et la projection de cette même scène sur un écran
en deux dimensions.
· La partie V, plus difficile que les précédentes, demande de ne pas se perdre 
dans
les notations et le concept de rayon lumineux se réfléchissant d'une surface à
l'autre. Les deux dernières questions portent sur une optimisation qui reste
quelque peu théorique par rapport au reste du sujet.
Ce sujet donne une bonne idée de ce que l'on peut faire avec des outils 
informatiques, sur le thème assez pratique de la réalisation d'images de 
synthèse. Il est
globalement bien mené et progressif, tous les concepts sont parfaitement 
définis.
Il ne contient que de la manipulation assez simple de tableaux numpy, 
accessible dès
la première année. Il a le grand intérêt de faire produire quasiment l'ensemble 
du
code nécessaire à la mise en oeuvre : le lecteur intéressé pourra rapidement 
s'amuser
à créer lui-même des images. La fin du sujet réserve des questions plus 
délicates pour
les candidats plus à l'aise.

Indications
Partie I
1 Bien lire les paragraphes précédant la question, notamment à propos de la 
représentation des points et des vecteurs.
2 Lire attentivement l'annexe et les fonctions du module numpy autorisées.
5 Le mot-clé assert permet la vérification de la condition donnée et arrête 
l'exécution si elle n'est pas vérifiée.
8 Il faut résoudre l'équation précédente. On peut remarquer que les deux 
solutions
possibles doivent obligatoirement être positives.
Partie II
10 Faire un dessin en deux dimensions et regarder les vecteurs présents.
11 Il faut chercher les intersections du rayon partant de la source lumineuse 
et passant par P. Ne pas oublier que les sphères plus éloignées de la source 
que P
n'interviennent pas.
12 Le code à produire est très court, il suffit de traduire la relation (2) de 
l'énoncé.
Le cosinus de  peut être obtenu d'après le schéma par un produit scalaire.

-
-
13 Faire un schéma en deux dimensions et décomposer 
u sur l'axe de N et l'axe
orthogonal.
Partie III
14 Pour récupérer l'année, utiliser une fonction donnée en annexe.
16 Regarder où se trouvent les données permettant la sélection et celles 
nécessaires
à la projection, puis déterminer comment joindre les tables concernées.
17 La fonction OCCULTE demande deux identifiants d'objets indépendants, il faut
donc joindre deux fois la table Objet en les renommant.
Partie IV
18 Déterminer le lien entre x et j, puis entre y et i. Pour cela, faire un 
schéma représentant les cases et le centre de la figure, pour une valeur de N 
faible. Attention,
sur la figure de l'énoncé i et j ne sont pas en face de E(i, j).
20 Pour retourner le point d'intersection le plus proche et l'indice de l'objet 
correspondant, il est nécessaire de récupérer toutes les intersections avec la 
distance à
l'oeil, le point de contact et l'indice de l'objet afin de conserver les bonnes 
valeurs.
21 Le calcul de couleur diffusée depuis une source par un point de sphère a 
déjà été
fait à la question 12. Il suffit d'ajouter les couleurs correspondant aux 
différentes
sources, sans oublier de vérifier si elles sont bien visibles.
Partie V
25 Une boucle while ou for est possible. À chaque itération, si l'interception 
du
rayon existe, on la stocke et on continue.
26 La relation donnée dans l'énoncé implique que l'on doit parcourir le tableau 
des
réflexions en partant de la fin.
27 Reprendre la fonction lancer et regarder ce que couleur_perçue y modifie.
29 Créer l'ensemble des triplets {objr_id, so_id, objo_id}. Utiliser 
l'opérateur in
pour vérifier leur présence dans la liste risque.
30 Reprendre la fonction visible et l'adapter. Attention à l'ordre des 
arguments.

I. Géométrie
-
1 La fonction vec calcule les composantes du vecteur AB en soustrayant les 
coordonnées du point A à celles du point B.
def vec(A, B):
return B - A
L'énoncé dit explicitement que retrancher deux vecteurs est réalisé par 
l'opération v1 - v2 et que les vecteurs, comme les points, sont représentés par
des tableaux. Il fallait donc éviter d'écrire une boucle ici.
2 La fonction ps calcule le produit scalaire de deux vecteurs, somme des 
produits
terme à terme de leurs composantes, ce que fait précisément la fonction 
np.inner.
def ps(v1, v2):
return np.inner(v1, v2)
La méthode inner du module numpy est donnée dans l'annexe et sa description 
correspond exactement au produit scalaire. Il est néanmoins possible
de réaliser cette opération autrement, notamment en faisant la somme des
composantes du produit de Hadamard des deux vecteurs :
def ps(v1, v2):
return np.sum(v1 * v2)
La réalisation de ce calcul par une boucle, demandant beaucoup plus
d'écriture, a certainement été acceptée par les correcteurs, mais ce n'est 
visiblement pas la réponse attendue. On peut écrire par exemple
def ps(v1, v2):
somme = 0
for i in range(len(v1)):
somme += v1[i] * v2[i]
return somme
3 La fonction norme calcule la racine carrée du produit scalaire du vecteur par
lui-même.
def norme(v):
return math.sqrt(ps(v, v))
4 La fonction unitaire retourne le vecteur unitaire correspondant à l'argument,
en utilisant le produit d'un scalaire et d'un vecteur.
def unitaire(v):
return (1/norme(v)) * v
5

Le mot-clé assert n'est pas au programme et sa présence dans un code
d'une des premières questions du sujet a pu décontenancer un certain nombre
d'étudiants. Cette instruction correspond à la vérification de la condition
donnée, à savoir est-ce que t est positif ou non. Si c'est le cas, l'instruction
ne fait rien. Si non, elle lève une erreur, et l'utilisateur obtient alors le 
message
AssertionError avant un arrêt immédiat de l'exécution.

-
La fonction pt permet de calculer, pour un rayon lumineux r = (S, 
u ) et un
-

-
entier t donnés, la position du point M du rayon tel que SM = t u . Elle ne 
fonctionne,
comme indiqué dans la description donnée dans l'énoncé, que pour t > 0, car t 
est la
-
distance séparant M de la source, dans la direction définie par 
u.
-
La fonction dir définit le vecteur unitaire associé au vecteur AB, donc au rayon
passant par les points A et B et allant de A vers B.
La fonction ra définit le rayon lumineux partant du point A et passant par B.
6 La fonction sp crée la représentation de la sphère de centre A et passant par 
B.
def sp(A, B):
return A, norme(vec(A, B))
7 On considère un point M appartenant à la droite passant par le point A et de
-
vecteur directeur 
u . Cela signifie qu'il existe un réel t tel que
--
-
AM = t 
u
Ce point M appartient à la sphère de centre C et de rayon r si et seulement si 
la
--
-- --
distance MC vaut r, soit kMCk2 = MC · MC = r2 . Or,
-- --
- -- - --
MC · MC = CA + AM · CA + AM
- - -- --
- --
= CA · CA + AM · AM + 2 CA · AM

-- --
-
-
-
MC · MC = kCAk2 + t2 + 2 CA · t 
u
On trouve ainsi que

-
-
-
t2 + 2 t 
u · CA + kCAk2 - r2 = 0

Cette équation est un trinôme du second degré. Si son discriminant est 
strictement positif, elle a deux solutions réelles correspondant aux deux 
intersections de la
droite et de la sphère. Un discriminant nul indique une unique solution réelle 
double,
correspondant à une droite tangente à la sphère. Enfin, dans le cas d'un 
discriminant
strictement négatif, les solutions ne sont pas réelles, la droite et la sphère 
ne sont
alors pas sécantes.
8 L'équation déterminée ci-dessus a des solutions réelles si

-2
-
-
=4 
u · CA - 4 kCAk2 - r2 > 0
De plus, avec A à l'extérieur de la sphère, le schéma
ci-contre montre que les deux solutions doivent
être positives. Il faut donc que leur produit et leur
somme soient positifs. Dans un trinôme de la forme
a x2 + b x + c = 0, le produit des racines vaut c/a
et la somme -b/a. La condition sur le produit est
déjà réalisée si A est à l'extérieur de la sphère. Celle
sur la somme rend nécessaire la condition
-

-
u · CA < 0 - u A C Si c'est le cas, il faut alors retourner la plus petite solution des deux, soit - - t = - u · CA - 2