-
Notifications
You must be signed in to change notification settings - Fork 0
/
TP1.html
286 lines (274 loc) · 15.4 KB
/
TP1.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
<!DOCTYPE html>
<html lang="fr" dir="ltr">
<head>
<meta charset="utf-8">
<meta name="format-detection" content="telephone=no">
<meta name="viewport" content="initial-scale=1, width=device-width">
<link rel="stylesheet" href="css/cartonboite.css">
<title>TP1 - Half Edge</title>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.0.1/styles/default.min.css">
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.0.1/highlight.min.js"></script>
<script>hljs.initHighlightingOnLoad();</script>
</head>
<body class="-flexCStart -align-ifill -align-sfill ">
<section class="-flexRBetween -align-ifill flex1 -flexWrap overflow-v">
<article class="-flexCStart -align-ifill back-clear -shadow -f-mult6 overflow-v" style="max-height: 100%;">
<div class="padding-very-long -flexCStart -align-ifill">
<div class="-flexRBetween">
<h1 class="font-h3 -boldest">Master Imagina</h1>
<div class="-flexCStart">
<img src="images/moon.svg" alt="night" class="-size-min nightImg -dark-logo pointer" onclick="document.body.classList.toggle('NIGHT')">
</div>
</div>
<h3 class="font-h5 -light">TP1 - Half Edge <span class="badge -roundest back-1">Géométrie Discrète</span></h3>
<p>Romain Saclier</p>
<div class="-flexRBetween">
<a href="TP1.html" class="btn -roundest -f-mult2 -margALL padding-min back-3">TP1</a>
<a href="TP2.html" class="btn -roundest -f-mult2 -margALL padding-min back-3">TP2</a>
<a href="TP3.html" class="btn -roundest -f-mult2 -margALL padding-min back-3">TP3</a>
</div>
<p class="-margT"><span class="padding-min back-warning -roundest -margR"></span>Tous les points peuvent être déplacés grâces à la souris</p>
<div class="-flexCStart -align-ifill -margT margin-very-long">
<p class="-bold -margV"><span class="badge -rounded back-1">1</span> Définissez et implémentez les structures HEdge , Vextex et Face</p>
<p class="-margV pointer" onclick="document.getElementById('HEDGE_STRUCTURE').classList.toggle('hide-display')">Structure HEdge (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="HEDGE_STRUCTURE"><code class="javascript">/**
* HEdge représente une demi arrête ( Half Edge )
* Il pointe vers un Vertex
* Vers sont suivant et précédent et opposé
* Et appartient à une face
*/
class HEdge {
constructor(vhead, next, prev, opposite, face){
this.vhead = vhead; // Le vertex pointé par le Half Edge
this.next = next; // Représente la HEdge suivant
this.prev = prev; // Représente la HEdge précédente
this.opposite = opposite; // Représente la HEdge opposé
this.face = face; // Représente la face auquel appartient la HEdge
}
}</code></pre>
<p class="-margV pointer" onclick="document.getElementById('VERTEX_STRUCTURE').classList.toggle('hide-display')">Structure Vertex (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="VERTEX_STRUCTURE"><code class="javascript">/**
* La Vertex représente un point du maillage
* Il possède des positions dans l'espace
* Et un pointeur vers la HEdge qui l'a en tête
*/
class Vertex {
constructor(x, y, z){
this.x = x; //La position x de la vertex
this.y = y; //La position y de la vertex
this.z = z; //La position z de la vertex
this.edge = undefined; //La Edge qui est connecté à ce vertex
}
}</code></pre>
<p class="-margV pointer" onclick="document.getElementById('FACE_STRUCTURE').classList.toggle('hide-display')">Structure Face (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="FACE_STRUCTURE"><code class="javascript">/**
* La Face représente une face d'un triangle dans le maillage
* Il pointe vers une de ses HEdge qui le compose
*/
class Face {
constructor(){
this.edge = undefined; //On initialise la Face avec un edge non défini
}
}</code></pre>
<p class="-bold -margV"><span class="badge -rounded back-1">2</span> Définissez le type maillage à partir des structures définis à la question précédente</p>
<p class="-margV pointer" onclick="document.getElementById('MESH_STRUCTURE').classList.toggle('hide-display')">Le Maillage (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="MESH_STRUCTURE"><code class="javascript">/**
* La classe Mesh représente le maillage,
* il possède une liste de vertex, une liste de HEdge et une liste de Face
*/
class Mesh {
constructor(){
this.vertices = [];
this.faces = [];
this.hedges = [];
}
getHEdge(i){ return this.hedges[i]; } //Permet d'obtenir la HEdge i
getFace(i){ return this.faces[i]; } //Permet d'obtenir la Face i
getVertex(i){ return this.vertices[i]; } //Permet d'obtenir la Vertex i
}</code></pre>
<p class="-bold -margV"><span class="badge -rounded back-1">3</span> Ajoutez à ce type les fonctions suivantes, ajout d’une face, sommets d’une face, sommets d’une arête, faces adjacentes à une arête, arêtes d’une face</p>
<p class="-margV color-danger color--clear"><span class="padding-min back-danger -roundest -margR"></span>Toutes les fonctions suivantes sont des méthodes de la classe Mesh</p>
<p class="-margV pointer" onclick="document.getElementById('ADD_VERTEX').classList.toggle('hide-display')">ajout d’une vertex (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="ADD_VERTEX"><code class="javascript">>/**
* Permet d'ajouter une vertex au maillage
*/
function addVertex(v){
this.vertices.push(v);
return this.vertices.length - 1; //On retourne la position de la vertex ajouté
}</code></pre>
<p class="-margV pointer" onclick="document.getElementById('ADD_FACE').classList.toggle('hide-display')">ajout d’une face (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="ADD_FACE"><code class="javascript">function addFace(idV0, idV1, idV2){
// 1 - On créé la nouvelle face
let face = new Face();
this.faces.push(face);
let f = this.faces.length - 1;
// 2 - On récupère la liste des HEdges incidents aux Vertex
let incidentV0 = this.incidentEdgeVertex(idV0);
let incidentV1 = this.incidentEdgeVertex(idV1);
let incidentV2 = this.incidentEdgeVertex(idV2);
// 3 - Création des variables qui contiendrons les HEdges qui relient les Vertex
// idV0 -> idV1 = e0
// idV1 -> idV2 = e1
// idV2 -> idV0 = e2
let e0, e1, e2;
// Création d'une fonction anonyme permettant, pour 2 vertex donné et leur listes de HEdges incidents respectifs
// De retourner la HEdge qui les relients, ayant pour idVertex2 comme tête
// Si celle-ci n'existe pas alors on l'a créé avec son opposé et on update les listes d'incidences
const resolveEdges = (idVertex1, idVertex2, incidentVertex1, incidentVertex2) => {
let edgeFound;
for (let i = 0; i < incidentVertex1.length; i++) {
if (this.getHEdge(incidentVertex1[i]).vhead == idVertex2) {
edgeFound = incidentVertex1[i];
break;
}
}
if (edgeFound == undefined) {
edgeFound = this.hedges.length;
let e0Hedge = new HEdge(idVertex2, undefined, undefined, edgeFound + 1, f);
let e0HedgeOpposite = new HEdge(idVertex1, undefined, undefined, edgeFound, undefined);
this.hedges.push(e0Hedge);
this.hedges.push(e0HedgeOpposite);
incidentVertex1.push(this.hedges.length - 2);
incidentVertex1.push(this.hedges.length - 1);
incidentVertex2.push(this.hedges.length - 2);
incidentVertex2.push(this.hedges.length - 1);
}
return edgeFound;
}
e0 = resolveEdges(idV0, idV1, incidentV0, incidentV1);
e1 = resolveEdges(idV1, idV2, incidentV1, incidentV2);
e2 = resolveEdges(idV2, idV0, incidentV2, incidentV0);
// 4 - On connecte les différents HEdges au sein du nouveau triangle et on ajoute les différentes liaisons
// Connexion des HEdges
this.getHEdge(e0).next = e1;
this.getHEdge(e1).next = e2;
this.getHEdge(e2).next = e0;
this.getHEdge(e0).prev = e2;
this.getHEdge(e1).prev = e0;
this.getHEdge(e2).prev = e1;
//Connexion des HEdges à la face
this.getHEdge(e0).face = f;
this.getHEdge(e1).face = f;
this.getHEdge(e2).face = f;
//Connexion de la face à une Edge quelconque
face.edges[0] = e0;
face.edges[1] = e1;
face.edges[2] = e2;
//Si un vertex ne possède pas de Edge associé alors on lui attribue un
if (this.getVertex(idV0).edge == undefined) this.getVertex(idV0).edge = e2;
if (this.getVertex(idV1).edge == undefined) this.getVertex(idV1).edge = e0;
if (this.getVertex(idV2).edge == undefined) this.getVertex(idV2).edge = e1;
// 5 - On Update les liaisons HEdges opposés si ceux-ci ne possèdent pas de face associés
// Le but est de répérer deux HEdges incidents à un Vertex et de les lier dans la bonne direction
const resolveLink = (incidents, vId) => {
let incidentsNoFace = [];
for (let i = 0; i < incidents.length; i++) {
if (this.getHEdge(incidents[i]).face == undefined) incidentsNoFace.push(incidents[i]);
}
if(incidentsNoFace.length >= 2){
let first, end;
if(this.getHEdge(incidentsNoFace[0]).vhead == vId){ first = 0; end = 1; }
else { first = 1; end = 0; }
this.getHEdge(incidentsNoFace[first]).next = incidentsNoFace[end];
this.getHEdge(incidentsNoFace[end]).prev = incidentsNoFace[first];
}
}
resolveLink(incidentV0, idV0);
resolveLink(incidentV1, idV1);
resolveLink(incidentV2, idV2);
return f;
}</code></pre>
<p class="-margV pointer" onclick="document.getElementById('SOMMET_FACE').classList.toggle('hide-display')">sommets d’une face (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="SOMMET_FACE"><code class="javascript">function getVertexFace(face){
let edges = getEdgesFace(face);
edges[0] = this.getHEdge(edges[0]).vhead;
edges[1] = this.getHEdge(edges[1]).vhead;
edges[2] = this.getHEdge(edges[2]).vhead;
return edges;
}</code></pre>
<p class="-margV pointer" onclick="document.getElementById('SOMMET_ARRETE').classList.toggle('hide-display')">sommets d’une arête (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="SOMMET_ARRETE"><code class="javascript">function vertexEdge(e) {
let vertices = [];
let edge = this.getHEdge(e);
vertices.push(edge.vhead);
vertices.push(this.getHEdge(edge.opposite).vhead);
return vertices;
}</code></pre>
<p class="-margV pointer" onclick="document.getElementById('FACE_ARRETE').classList.toggle('hide-display')">faces adjacentes à une arête (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="FACE_ARRETE"><code class="javascript">function facesAdajcentEdge(e) {
let faces = [];
let edge = this.getHEdge(e);
face1 = edge.face;
face2 = this.getHEdge(edge.opposite).face;
if (face1 != undefined) faces.push(face1);
if (face2 != undefined) faces.push(face2);
return faces;
}</code></pre>
<p class="-margV pointer" onclick="document.getElementById('ARRETE_FACE').classList.toggle('hide-display')">arêtes d’une face (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="ARRETE_FACE"><code class="javascript">function getEdgesFace(face) {
let edges = [];
let e = getFace(face).edge;
edges.push(e.edge);
edges.push(this.getHEdge(e.edge).next);
edges.push(this.getHEdge(e.edge).prev);
return edges;
}</code></pre>
<!-- EXERCICE 4 -->
<p class="-bold -margV"><span class="badge -rounded back-1">4</span> Définissez un itérateur permettant de parcourir les arêtes incidentes à un sommet</p>
<p class="-margV pointer" onclick="document.getElementById('ITERATOR_EDGES').classList.toggle('hide-display')">Itérateur (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="ITERATOR_EDGES"><code class="javascript">//Incident Iterator Vertex
function* incidentIteratorVertex(v){
let e = this.getVertex(v).edge;
let head = this.getVertex(v).edge;
do {
yield e;
e = this.getHEdge(e).opposite;
yield e;
e = this.getHEdge(e).prev;
} while(e != head);
}</code></pre>
<!-- EXERCICE 5 -->
<p class="-bold -margV"><span class="badge -rounded back-1">5</span> définisser un itérateur permettant de parcourir les faces du maillage</p>
<p class="-margV pointer" onclick="document.getElementById('ITERATOR_FACE').classList.toggle('hide-display')">Itérateur (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="ITERATOR_FACE"><code class="javascript">function* incidentIteratorFace(){
for(let i = 0; i < this.faces.length; i++){
yield i;
}
}</code></pre>
<!-- EXERCICE 6 -->
<p class="-bold -margV"><span class="badge -rounded back-1">6</span> Enfin écrivez un programme qui à l’aide de votre structure crée le maillage d’une d’une pyramide et en sortie affichez le résultat obtenu : pour chaque arête, affichez le sommet incident, l’arête suivante et l’arête précédente, l’arête opposée et la face incidente.</p>
<p class="-margV">Voir la figure suivante, les points sont draggable, vous pouvez les déplacer avec votre curseur</p>
<p class="-margV pointer" onclick="document.getElementById('INIT_MESH').classList.toggle('hide-display')">Code créateur du maillage (<span class="color-1">cliquez ici pour voir le code</span>)</p>
<pre class="prettyprint -flexCStart -align-ifill hide-display" id="INIT_MESH"><code class="javascript">//Calcul du centre
let center = new Vertex(ctx.canvas.width / 2, ctx.canvas.height / 2, 0);
//Création des vertex (on ajoute le centre pour que la figure soit centré sur la scène)
let v0 = new Vertex(-200, 0, 0).add(center);
let v1 = new Vertex(200, 0, 0).add(center);
let v2 = new Vertex(50, 100, 0).add(center);
let v3 = new Vertex(0, -200, 0).add(center);
//Création du maillage
let m = new Mesh();
//On ajoute les vertex
let iv0 = m.addVertex(v0);
let iv1 = m.addVertex(v1);
let iv2 = m.addVertex(v2);
let iv3 = m.addVertex(v3);
//Création des faces
m.addFace(iv0,iv1,iv2);
m.addFace(iv1,iv3,iv2);
m.addFace(iv1,iv0,iv3);
m.addFace(iv3,iv0,iv2);</code></pre>
</div>
</div>
</article>
<article class="-flexCStart -align-ifill -f-mult6 overflow-v" style="height: 100vh;">
<canvas id="SCENE" class="flex1"></canvas>
</article>
</section>
</body>
<script src="scripts/geometry.js" charset="utf-8"></script>
<script src="scripts/loop.js" charset="utf-8"></script>
<script src="scripts/triangulation.js" charset="utf-8"></script>
<!-- <script src="scripts/main.js" charset="utf-8"></script> -->
<script src="scripts/TPS/TP1.js" charset="utf-8"></script>
</html>