Wiki du LAMA (UMR 5127) - Contributions [fr]

Surfaces polygonales et surfaces de subdivision

2024-05-20T19:03:49Z

Vstoll : /* Définitions */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

=== Surface polygonale ===

Donnée d'un ensemble de polygône dans l'espace s'intersectant deux à deux suivant des arêtes

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définit n[f] : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2 * n[f] demies arêtes, on ajoute 1 point par face et on ajoute n[f]-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n[f] de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== Subdivision √3 ====

La subdivision √3 est utilisée sur des surfaces triangulées, c'est à dire une surface composée uniquement de faces triangles.

On commence par définir un point central sur chaque face, qu'on relie à tous les autres points du triangle.

On supprime ensuite les arêtes qu'il y avait à la base si elles ne sont pas au bord et on relie les nouveaux points avec leurs voisins (les nouveaux points des faces adjacentes) par une arête.

Cette subdivision multiplie les faces par 3, créée 1 points par face et créée 3 arêtes par face.

Donc si f est le nombre de face qu'il y avait à la base on a :

nombre de faces += 2f

nombre de points += f

nombre d'arêtes += 3f

Surfaces polygonales et surfaces de subdivision

2024-05-19T16:21:20Z

Vstoll : /* Subdivision √3 */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définit n[f] : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2 * n[f] demies arêtes, on ajoute 1 point par face et on ajoute n[f]-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n[f] de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== Subdivision √3 ====

La subdivision √3 est utilisée sur des surfaces triangulées, c'est à dire une surface composée uniquement de faces triangles.

On commence par définir un point central sur chaque face, qu'on relie à tous les autres points du triangle.

On supprime ensuite les arêtes qu'il y avait à la base si elles ne sont pas au bord et on relie les nouveaux points avec leurs voisins (les nouveaux points des faces adjacentes) par une arête.

Cette subdivision multiplie les faces par 3, créée 1 points par face et créée 3 arêtes par face.

Donc si f est le nombre de face qu'il y avait à la base on a :

nombre de faces += 2f

nombre de points += f

nombre d'arêtes += 3f

Surfaces polygonales et surfaces de subdivision

2024-05-19T16:15:53Z

Vstoll : /* Subdivision √3 */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définit n[f] : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2 * n[f] demies arêtes, on ajoute 1 point par face et on ajoute n[f]-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n[f] de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== Subdivision √3 ====

La subdivision √3 est utilisée sur des surfaces triangulées, c'est à dire une surface composée uniquement de faces triangles.

On commence par définir un point central sur chaque face, qu'on relie à tous les autres points du triangle.

On supprime ensuite les arêtes qu'il y avait à la base si elles ne sont pas au bord et on relie tous les nouveaux points par des arêtes.

Cette subdivision multiplie les faces par 3, créée 1 points par face et créée 3 arêtes par face.

Donc si f est le nombre de face qu'il y avait à la base on a :

nombre de faces += 2f

nombre de points += f

nombre d'arêtes += 3f

Surfaces polygonales et surfaces de subdivision

2024-05-19T16:14:48Z

Vstoll : /* Subdivision √3 */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définit n[f] : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2 * n[f] demies arêtes, on ajoute 1 point par face et on ajoute n[f]-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n[f] de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== Subdivision √3 ====

La subdivision √3 est utilisée sur des surfaces triangulées, c'est à dire une surface composée uniquement de faces triangles.

On commence par définir un point central sur chaque face, qu'on relie à tous les autres points du triangle.

On supprime ensuite les arêtes qu'il y avait à la base si elles ne sont pas au bord et on relie tous les nouveaux points par des arêtes.

Si la surface n'a pas de bord, cette subdivision multiplie les faces par 3, créée 1 points par face et créée 3 arêtes par face.

Donc si f est le nombre de face qu'il y avait à la base on a :

nombre de faces += 2f

nombre de points += f

nombre d'arêtes += 3f

Surfaces polygonales et surfaces de subdivision

2024-05-19T15:57:58Z

Vstoll : /* Partie 2 - subdivision des faces */

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:58:26Z

Vstoll :

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définit n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== Subdivision √3 ====

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:47:38Z

Vstoll : /* Subdivision \sqrt */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définit n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== Subdivision √3 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:46:51Z

Vstoll : /* Subdivision */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définit n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== Subdivision <math>\sqrt</math> ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:46:24Z

Vstoll : /* Autres aglorithmes */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définit n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== Subdivision <math> ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:37:50Z

Vstoll : /* Partie 2 - subdivision des faces */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définit n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:37:28Z

Vstoll : /* Partie 2 - subdivision des faces */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créé 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:37:00Z

Vstoll : /* Partie 1 - subdivision des demies arêtes */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = l'indice du nouveau point.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:36:30Z

Vstoll : /* Définitions des coordonnées des points */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 points de faces des 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:35:59Z

Vstoll : /* Définitions des coordonnées des points */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 nouveaux points créés pour les 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>.

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:35:32Z

Vstoll : /* Définitions des coordonnées des points */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points de faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points d'arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 nouveaux points créés pour les 2 faces associées à l'arête.

Pour les coordonnées des points originaux P, on commence par définir F la moyenne des n points de faces touchant P, R la moyenne du milieu des n arêtes touchants P (le milieu d'une arête étant la moyenne des 2 points de l'arête).
Les nouvelles coordonnées de P sont alors <math>\frac{F + 2R + (n-3)P}{n}</math>

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T20:23:52Z

Vstoll : /* Surface */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

Une surface est un ensembles de points sur lequel il est localement possible de se repérer à l'aide de deux coordonnées réelles.

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points créés pour les faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points créés pour les arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 nouveaux points créés pour les 2 faces associées à l'arête.

Les coordonnées des points originaux sont le barycentre // PAS FINI

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-18T15:25:13Z

Vstoll : /* Définitions des coordonnées des points */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

Les points créés pour les faces ont pour coordonnées la moyenne de tous les points originaux de la face.

Les points créés pour les arêtes ont pour coordonnées la moyenne des 2 points de l'arête et des 2 nouveaux points créés pour les 2 faces associées à l'arête.

Les coordonnées des points originaux sont le barycentre // PAS FINI

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Fichier:Cube subdivision.gif

2024-05-11T18:50:38Z

Vstoll :

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:50:07Z

Vstoll : /* Exemples */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube_subdivision.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:49:57Z

Vstoll : /* Exemples */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

Un cube avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:cube.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Fichier:Lemming.gif

2024-05-11T18:37:46Z

Vstoll :

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:37:35Z

Vstoll : /* Exemples */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

[[Fichier:lemming.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:37:14Z

Vstoll : /* Exemples */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

==== Exemples ====

Voici l'exemple d'un modèle d'un lemming fait main sur blender avec 0, 1, 2 et 3 subdivisions Catmull-Clark :

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:27:21Z

Vstoll : /* Catmull-Clark */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

==== Exemples ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:20:16Z

Vstoll : /* Partie 2 - subdivision des faces */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision,

P = P + A/2 + F

A = 2A + 2N

F = N

==== Définitions des coordonnées des points ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:20:00Z

Vstoll : /* Partie 2 - subdivision des faces */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

On définie n(f) : nombre de points de la face avant la subdivision.

Lors de cette deuxième partie de la subdivision pour chaque face on ajoute 2n(f) demies arêtes, on ajoute 1 point par face et on ajoute n(f)-1 faces.

On définie P : nombre de points, A : nombre de demies arêtes, F : nombre de faces et N : somme de n(f) de chaque face.

Donc après les 2 parties de la subdivision, P = P + A/2 + F, A = 2A + 2N et F = N

==== Définitions des coordonnées des points ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:11:08Z

Vstoll : /* Partie 2 - subdivision des faces */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

Lors de cette deuxième partie de la subdivision on double encore les demies arêtes, on ajoute 1 point par face et on ajoute n-1 faces avec n le nombre de points qu'il y avait .

==== Définitions des coordonnées des points ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:05:56Z

Vstoll : /* Partie 2 - subdivision des faces */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

Lors de cette deuxième partie de la subdivision on double encore les demies arêtes, on ajoute 1 point par face et on ajoute (n/2)-1 faces avec n le nombre de demies arêtes.

==== Définitions des coordonnées des points ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T18:03:14Z

Vstoll : /* Partie 1 - subdivision des demies arêtes */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

==== Définitions des coordonnées des points ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T17:59:36Z

Vstoll : /* Catmull-Clark */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

==== Définitions des coordonnées des points ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Fichier:Subdivision face.gif

2024-05-11T17:55:58Z

Vstoll :

Surfaces polygonales et surfaces de subdivision

2024-05-11T17:53:19Z

Vstoll : /* Partie 2 - subdivision des faces */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

[[Fichier:subdivision_face.gif|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T17:52:51Z

Vstoll : /* Partie 2 - subdivision des faces */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

Pour la subdivision des faces on parcourt toutes les faces avec w_face et on créer 1 point et autant de faces qu'il y avait de points sur la face avant toute subdivision.

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T17:29:20Z

Vstoll : /* Partie 1 - subdivision des demies arêtes */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T17:28:47Z

Vstoll : /* Partie 1 - subdivision des demies arêtes */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T17:28:30Z

Vstoll : /* Partie 1 - subdivision des demies arêtes */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:35:45Z

Vstoll : /* Catmull-Clark */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

==== Partie 2 - subdivision des faces ====

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:34:29Z

Vstoll : /* Partie 1 - subdivision des demies arêtes */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

Lors de cette première partie de la subdivision on double les demies arêtes et on ajoute 1 point par paire de demies arêtes.

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:29:44Z

Vstoll : /* Catmull-Clark */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

==== Partie 1 - subdivision des demies arêtes ====

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:29:00Z

Vstoll : /* Catmull-Clark */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base et i pair

On peut voir que la demie arête opposée d'une demie arête x est égal à x+1 si x pair et x-1 si x impair, grâce à la méthode de conversion, et on va garder cette propriété tout le long de la subdivision même si elle n'est pas obligatoire.

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:25:24Z

Vstoll : /* Catmull-Clark */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]] ici n = nombre de demies arêtes qu'on avait à la base

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Fichier:Subvidision demie arete.png

2024-05-11T15:24:35Z

Vstoll :

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:24:08Z

Vstoll : /* Catmull-Clark */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

[[Fichier:subvidision_demie_arete.png|300px]]

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:23:44Z

Vstoll : /* Catmull-Clark */

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

== Définitions ==
=== Surface ===

== Structure de données demie arêtes ailées ==
=== Description ===
Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

[[Fichier:triangle_demie_ailee.png|300px]]

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

=== Conversion ===

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire).

Cette demie arête est donc la suivante de celle que l'on avait au départ.

=== Déconversion ===
La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.

[[Fichier:deconversion.gif|300px]]

== Algorithmes de subdivision de surface ==
=== Catmull-Clark ===

Pour mon implémentation de la [https://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface subdivision de surface Catmull–Clark], je l'ai décomposée en 2 parties.

La première partie s'occupe de subdiviser les arêtes tandis que la deuxième s'occupe de subdiviser les faces.

Dans la première partie, on parcourt les demies arêtes d'indice pair car on va s'en occuper par paires, comme pendant la conversion.

On aura donc besoin de créer 1 point et 2 demies arêtes par paires de demies arêtes.

[[Fichier:subvidision_demie_arete_points.png|300px]] ici n = nombre de points qu'on avait à la base et i = nombres d'itérations qu'on a faites.

=== Autres aglorithmes ===
==== algo1 ====

== Pourquoi cela donne une surface lisse ? ==

Fichier:Subvidision demie arete points.png

2024-05-11T15:22:20Z

Vstoll :

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:22:02Z

Vstoll : /* Catmull-Clark */

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:21:06Z

Vstoll : /* Catmull-Clark */

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:06:08Z

Vstoll : /* Catmull-Clark */

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:02:19Z

Vstoll : /* Catmull-Clark */

Surfaces polygonales et surfaces de subdivision

2024-05-11T15:01:55Z

Vstoll : /* Algorithmes de subdivision de surface */