1 /*
2 * @author zz85 / http://twitter.com/blurspline / http://www.lab4games.net/zz85/blog
3 *
4 * Subdivision Geometry Modifier
5 * using Catmull-Clark Subdivision Surfaces
6 * for creating smooth geometry meshes
7 *
8 * Note: a modifier modifies vertices and faces of geometry,
9 * so use geometry.clone() if original geometry needs to be retained
10 *
11 * Readings:
12 * http://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface
13 * http://www.rorydriscoll.com/2008/08/01/catmull-clark-subdivision-the-basics/
14 * http://xrt.wikidot.com/blog:31
15 * "Subdivision Surfaces in Character Animation"
16 *
17 * (on boundary edges)
18 * http://rosettacode.org/wiki/Catmull%E2%80%93Clark_subdivision_surface
19 * https://graphics.stanford.edu/wikis/cs148-09-summer/Assignment3Description
20 *
21 * Supports:
22 * Closed and Open geometries.
23 *
24 * TODO:
25 * crease vertex and "semi-sharp" features
26 * selective subdivision
27 */
28
29
30 /**@constructor*/
31 THREE.SubdivisionModifier = function( subdivisions ) {
32
33 this.subdivisions = (subdivisions === undefined ) ? 1 : subdivisions;
34
35 // Settings
36 this.useOldVertexColors = false;
37 this.supportUVs = true;
38 this.debug = false;
39
40 };
41
42 // Applies the "modify" pattern
43 THREE.SubdivisionModifier.prototype.modify = function ( geometry ) {
44
45 var repeats = this.subdivisions;
46
47 while ( repeats-- > 0 ) {
48 this.smooth( geometry );
49 }
50
51 };
52
53 /// REFACTORING THIS OUT
54
55 THREE.GeometryUtils.orderedKey = function ( a, b ) {
56
57 return Math.min( a, b ) + "_" + Math.max( a, b );
58
59 };
60
61
62 // Returns a hashmap - of { edge_key: face_index }
63 THREE.GeometryUtils.computeEdgeFaces = function ( geometry ) {
64
65 var i, il, v1, v2, j, k,
66 face, faceIndices, faceIndex,
67 edge,
68 hash,
69 edgeFaceMap = {};
70
71 var orderedKey = THREE.GeometryUtils.orderedKey;
72
73 function mapEdgeHash( hash, i ) {
74
75 if ( edgeFaceMap[ hash ] === undefined ) {
76
77 edgeFaceMap[ hash ] = [];
78
79 }
80
81 edgeFaceMap[ hash ].push( i );
82 }
83
84
85 // construct vertex -> face map
86
87 for( i = 0, il = geometry.faces.length; i < il; i ++ ) {
88
89 face = geometry.faces[ i ];
90
91 if ( face instanceof THREE.Face3 ) {
92
93 hash = orderedKey( face.a, face.b );
94 mapEdgeHash( hash, i );
95
96 hash = orderedKey( face.b, face.c );
97 mapEdgeHash( hash, i );
98
99 hash = orderedKey( face.c, face.a );
100 mapEdgeHash( hash, i );
101
102 } else if ( face instanceof THREE.Face4 ) {
103
104 hash = orderedKey( face.a, face.b );
105 mapEdgeHash( hash, i );
106
107 hash = orderedKey( face.b, face.c );
108 mapEdgeHash( hash, i );
109
110 hash = orderedKey( face.c, face.d );
111 mapEdgeHash( hash, i );
112
113 hash = orderedKey( face.d, face.a );
114 mapEdgeHash( hash, i );
115
116 }
117
118 }
119
120 // extract faces
121
122 // var edges = [];
123 //
124 // var numOfEdges = 0;
125 // for (i in edgeFaceMap) {
126 // numOfEdges++;
127 //
128 // edge = edgeFaceMap[i];
129 // edges.push(edge);
130 //
131 // }
132
133 //debug('edgeFaceMap', edgeFaceMap, 'geometry.edges',geometry.edges, 'numOfEdges', numOfEdges);
134
135 return edgeFaceMap;
136
137 }
138
139 /////////////////////////////
140
141 // Performs an iteration of Catmull-Clark Subdivision
142 THREE.SubdivisionModifier.prototype.smooth = function ( oldGeometry ) {
143
144 //debug( 'running smooth' );
145
146 // New set of vertices, faces and uvs
147 var newVertices = [], newFaces = [], newUVs = [];
148
149 function v( x, y, z ) {
150 newVertices.push( new THREE.Vector3( x, y, z ) );
151 }
152
153 var scope = this;
154 var orderedKey = THREE.GeometryUtils.orderedKey;
155 var computeEdgeFaces = THREE.GeometryUtils.computeEdgeFaces;
156
157 function assert() {
158
159 if (scope.debug && console && console.assert) console.assert.apply(console, arguments);
160
161 }
162
163 function debug() {
164
165 if (scope.debug) console.log.apply(console, arguments);
166
167 }
168
169 function warn() {
170
171 if (console)
172 console.log.apply(console, arguments);
173
174 }
175
176 function f4( a, b, c, d, oldFace, orders, facei ) {
177
178 // TODO move vertex selection over here!
179
180 var newFace = new THREE.Face4( a, b, c, d, null, oldFace.color, oldFace.materialIndex );
181
182 if (scope.useOldVertexColors) {
183
184 newFace.vertexColors = [];
185
186 var color, tmpColor, order;
187
188 for (var i=0;i<4;i++) {
189
190 order = orders[i];
191
192 color = new THREE.Color(),
193 color.setRGB(0,0,0);
194
195 for (var j=0, jl=0; j<order.length;j++) {
196 tmpColor = oldFace.vertexColors[order[j]-1];
197 color.r += tmpColor.r;
198 color.g += tmpColor.g;
199 color.b += tmpColor.b;
200 }
201
202 color.r /= order.length;
203 color.g /= order.length;
204 color.b /= order.length;
205
206 newFace.vertexColors[i] = color;
207
208 }
209
210 }
211
212 newFaces.push( newFace );
213
214 if (scope.supportUVs) {
215
216 var aUv = [
217 getUV(a, ''),
218 getUV(b, facei),
219 getUV(c, facei),
220 getUV(d, facei)
221 ];
222
223 if (!aUv[0]) debug('a :( ', a+':'+facei);
224 else if (!aUv[1]) debug('b :( ', b+':'+facei);
225 else if (!aUv[2]) debug('c :( ', c+':'+facei);
226 else if (!aUv[3]) debug('d :( ', d+':'+facei);
227 else
228 newUVs.push( aUv );
229
230 }
231 }
232
233 var originalPoints = oldGeometry.vertices;
234 var originalFaces = oldGeometry.faces;
235 var originalVerticesLength = originalPoints.length;
236
237 var newPoints = originalPoints.concat(); // New set of vertices to work on
238
239 var facePoints = [], // these are new points on exisiting faces
240 edgePoints = {}; // these are new points on exisiting edges
241
242 var sharpEdges = {}, sharpVertices = []; // Mark edges and vertices to prevent smoothening on them
243 // TODO: handle this correctly.
244
245 var uvForVertices = {}; // Stored in {vertex}:{old face} format
246
247
248 function debugCoreStuff() {
249
250 console.log('facePoints', facePoints, 'edgePoints', edgePoints);
251 console.log('edgeFaceMap', edgeFaceMap, 'vertexEdgeMap', vertexEdgeMap);
252
253 }
254
255 function getUV(vertexNo, oldFaceNo) {
256 var j,jl;
257
258 var key = vertexNo+':'+oldFaceNo;
259 var theUV = uvForVertices[key];
260
261 if (!theUV) {
262 if (vertexNo>=originalVerticesLength && vertexNo < (originalVerticesLength + originalFaces.length)) {
263 debug('face pt');
264 } else {
265 debug('edge pt');
266 }
267
268 warn('warning, UV not found for', key);
269
270 return null;
271 }
272
273 return theUV;
274
275 // Original faces -> Vertex Nos.
276 // new Facepoint -> Vertex Nos.
277 // edge Points
278
279 }
280
281 function addUV(vertexNo, oldFaceNo, value) {
282
283 var key = vertexNo+':'+oldFaceNo;
284 if (!(key in uvForVertices)) {
285 uvForVertices[key] = value;
286 } else {
287 warn('dup vertexNo', vertexNo, 'oldFaceNo', oldFaceNo, 'value', value, 'key', key, uvForVertices[key]);
288 }
289 }
290
291 // Step 1
292 // For each face, add a face point
293 // Set each face point to be the centroid of all original points for the respective face.
294 // debug(oldGeometry);
295 var i, il, j, jl, face;
296
297 // For Uvs
298 var uvs = oldGeometry.faceVertexUvs[0];
299 var abcd = 'abcd', vertice;
300
301 debug('originalFaces, uvs, originalVerticesLength', originalFaces.length, uvs.length, originalVerticesLength);
302
303 if (scope.supportUVs)
304
305 for (i=0, il = uvs.length; i<il; i++ ) {
306
307 for (j=0,jl=uvs[i].length;j<jl;j++) {
308
309 vertice = originalFaces[i][abcd.charAt(j)];
310 addUV(vertice, i, uvs[i][j]);
311
312 }
313
314 }
315
316 if (uvs.length == 0) scope.supportUVs = false;
317
318 // Additional UVs check, if we index original
319 var uvCount = 0;
320 for (var u in uvForVertices) {
321 uvCount++;
322 }
323 if (!uvCount) {
324 scope.supportUVs = false;
325 debug('no uvs');
326 }
327
328 var avgUv ;
329
330 for (i=0, il = originalFaces.length; i<il ;i++) {
331
332 face = originalFaces[ i ];
333 facePoints.push( face.centroid );
334 newPoints.push( face.centroid );
335
336 if (!scope.supportUVs) continue;
337
338 // Prepare subdivided uv
339
340 avgUv = new THREE.UV();
341
342 if ( face instanceof THREE.Face3 ) {
343
344 avgUv.u = getUV( face.a, i ).u + getUV( face.b, i ).u + getUV( face.c, i ).u;
345 avgUv.v = getUV( face.a, i ).v + getUV( face.b, i ).v + getUV( face.c, i ).v;
346 avgUv.u /= 3;
347 avgUv.v /= 3;
348
349 } else if ( face instanceof THREE.Face4 ) {
350
351 avgUv.u = getUV( face.a, i ).u + getUV( face.b, i ).u + getUV( face.c, i ).u + getUV( face.d, i ).u;
352 avgUv.v = getUV( face.a, i ).v + getUV( face.b, i ).v + getUV( face.c, i ).v + getUV( face.d, i ).v;
353 avgUv.u /= 4;
354 avgUv.v /= 4;
355
356 }
357
358 addUV(originalVerticesLength + i, '', avgUv);
359
360 }
361
362 // Step 2
363 // For each edge, add an edge point.
364 // Set each edge point to be the average of the two neighbouring face points and its two original endpoints.
365
366 var edgeFaceMap = computeEdgeFaces ( oldGeometry ); // Edge Hash -> Faces Index eg { edge_key: [face_index, face_index2 ]}
367 var edge, faceIndexA, faceIndexB, avg;
368
369 // debug('edgeFaceMap', edgeFaceMap);
370
371 var edgeCount = 0;
372
373 var edgeVertex, edgeVertexA, edgeVertexB;
374
375 ////
376
377 var vertexEdgeMap = {}; // Gives edges connecting from each vertex
378 var vertexFaceMap = {}; // Gives faces connecting from each vertex
379
380 function addVertexEdgeMap(vertex, edge) {
381
382 if (vertexEdgeMap[vertex]===undefined) {
383
384 vertexEdgeMap[vertex] = [];
385
386 }
387
388 vertexEdgeMap[vertex].push(edge);
389 }
390
391 function addVertexFaceMap(vertex, face, edge) {
392
393 if (vertexFaceMap[vertex]===undefined) {
394
395 vertexFaceMap[vertex] = {};
396
397 }
398
399 vertexFaceMap[vertex][face] = edge;
400 // vertexFaceMap[vertex][face] = null;
401 }
402
403 // Prepares vertexEdgeMap and vertexFaceMap
404 for (i in edgeFaceMap) { // This is for every edge
405 edge = edgeFaceMap[i];
406
407 edgeVertex = i.split('_');
408 edgeVertexA = edgeVertex[0];
409 edgeVertexB = edgeVertex[1];
410
411 // Maps an edgeVertex to connecting edges
412 addVertexEdgeMap(edgeVertexA, [edgeVertexA, edgeVertexB] );
413 addVertexEdgeMap(edgeVertexB, [edgeVertexA, edgeVertexB] );
414
415 for (j=0,jl=edge.length;j<jl;j++) {
416
417 face = edge[j];
418 addVertexFaceMap(edgeVertexA, face, i);
419 addVertexFaceMap(edgeVertexB, face, i);
420
421 }
422
423 // {edge vertex: { face1: edge_key, face2: edge_key.. } }
424
425 // this thing is fishy right now.
426 if (edge.length < 2) {
427
428 // edge is "sharp";
429 sharpEdges[i] = true;
430 sharpVertices[edgeVertexA] = true;
431 sharpVertices[edgeVertexB] = true;
432
433 }
434
435 }
436
437 for (i in edgeFaceMap) {
438
439 edge = edgeFaceMap[i];
440
441 faceIndexA = edge[0]; // face index a
442 faceIndexB = edge[1]; // face index b
443
444 edgeVertex = i.split('_');
445 edgeVertexA = edgeVertex[0];
446 edgeVertexB = edgeVertex[1];
447
448 avg = new THREE.Vector3();
449
450 //debug(i, faceIndexB,facePoints[faceIndexB]);
451
452 assert(edge.length > 0, 'an edge without faces?!');
453
454 if (edge.length==1) {
455
456 avg.addSelf(originalPoints[edgeVertexA]);
457 avg.addSelf(originalPoints[edgeVertexB]);
458 avg.multiplyScalar(0.5);
459
460 sharpVertices[newPoints.length] = true;
461
462 } else {
463
464 avg.addSelf(facePoints[faceIndexA]);
465 avg.addSelf(facePoints[faceIndexB]);
466
467 avg.addSelf(originalPoints[edgeVertexA]);
468 avg.addSelf(originalPoints[edgeVertexB]);
469
470 avg.multiplyScalar(0.25);
471
472 }
473
474 edgePoints[i] = originalVerticesLength + originalFaces.length + edgeCount;
475
476 newPoints.push( avg );
477
478 edgeCount ++;
479
480 if (!scope.supportUVs) {
481 continue;
482 }
483
484 // Prepare subdivided uv
485
486 avgUv = new THREE.UV();
487
488 avgUv.u = getUV(edgeVertexA, faceIndexA).u + getUV(edgeVertexB, faceIndexA).u;
489 avgUv.v = getUV(edgeVertexA, faceIndexA).v + getUV(edgeVertexB, faceIndexA).v;
490 avgUv.u /= 2;
491 avgUv.v /= 2;
492
493 addUV(edgePoints[i], faceIndexA, avgUv);
494
495 if (edge.length>=2) {
496 assert(edge.length == 2, 'did we plan for more than 2 edges?');
497 avgUv = new THREE.UV();
498
499 avgUv.u = getUV(edgeVertexA, faceIndexB).u + getUV(edgeVertexB, faceIndexB).u;
500 avgUv.v = getUV(edgeVertexA, faceIndexB).v + getUV(edgeVertexB, faceIndexB).v;
501 avgUv.u /= 2;
502 avgUv.v /= 2;
503
504 addUV(edgePoints[i], faceIndexB, avgUv);
505 }
506
507 }
508
509 debug('-- Step 2 done');
510
511 // Step 3
512 // For each face point, add an edge for every edge of the face,
513 // connecting the face point to each edge point for the face.
514
515 var facePt, currentVerticeIndex;
516
517 var hashAB, hashBC, hashCD, hashDA, hashCA;
518
519 var abc123 = ['123', '12', '2', '23'];
520 var bca123 = ['123', '23', '3', '31'];
521 var cab123 = ['123', '31', '1', '12'];
522 var abc1234 = ['1234', '12', '2', '23'];
523 var bcd1234 = ['1234', '23', '3', '34'];
524 var cda1234 = ['1234', '34', '4', '41'];
525 var dab1234 = ['1234', '41', '1', '12'];
526
527 for (i=0, il = facePoints.length; i<il ;i++) { // for every face
528 facePt = facePoints[i];
529 face = originalFaces[i];
530 currentVerticeIndex = originalVerticesLength+ i;
531
532 if ( face instanceof THREE.Face3 ) {
533
534 // create 3 face4s
535
536 hashAB = orderedKey( face.a, face.b );
537 hashBC = orderedKey( face.b, face.c );
538 hashCA = orderedKey( face.c, face.a );
539
540 f4( currentVerticeIndex, edgePoints[hashAB], face.b, edgePoints[hashBC], face, abc123, i );
541 f4( currentVerticeIndex, edgePoints[hashBC], face.c, edgePoints[hashCA], face, bca123, i );
542 f4( currentVerticeIndex, edgePoints[hashCA], face.a, edgePoints[hashAB], face, cab123, i );
543
544 } else if ( face instanceof THREE.Face4 ) {
545
546 // create 4 face4s
547
548 hashAB = orderedKey( face.a, face.b );
549 hashBC = orderedKey( face.b, face.c );
550 hashCD = orderedKey( face.c, face.d );
551 hashDA = orderedKey( face.d, face.a );
552
553 f4( currentVerticeIndex, edgePoints[hashAB], face.b, edgePoints[hashBC], face, abc1234, i );
554 f4( currentVerticeIndex, edgePoints[hashBC], face.c, edgePoints[hashCD], face, bcd1234, i );
555 f4( currentVerticeIndex, edgePoints[hashCD], face.d, edgePoints[hashDA], face, cda1234, i );
556 f4( currentVerticeIndex, edgePoints[hashDA], face.a, edgePoints[hashAB], face, dab1234, i );
557
558
559 } else {
560
561 debug('face should be a face!', face);
562
563 }
564
565 }
566
567 newVertices = newPoints;
568
569 // Step 4
570
571 // For each original point P,
572 // take the average F of all n face points for faces touching P,
573 // and take the average R of all n edge midpoints for edges touching P,
574 // where each edge midpoint is the average of its two endpoint vertices.
575 // Move each original point to the point
576
577
578 var F = new THREE.Vector3();
579 var R = new THREE.Vector3();
580
581 var n;
582 for (i=0, il = originalPoints.length; i<il; i++) {
583 // (F + 2R + (n-3)P) / n
584
585 if (vertexEdgeMap[i]===undefined) continue;
586
587 F.set(0,0,0);
588 R.set(0,0,0);
589 var newPos = new THREE.Vector3(0,0,0);
590
591 var f = 0; // this counts number of faces, original vertex is connected to (also known as valance?)
592 for (j in vertexFaceMap[i]) {
593 F.addSelf(facePoints[j]);
594 f++;
595 }
596
597 var sharpEdgeCount = 0;
598
599 n = vertexEdgeMap[i].length; // given a vertex, return its connecting edges
600
601 // Are we on the border?
602 var boundary_case = f != n;
603
604 // if (boundary_case) {
605 // console.error('moo', 'o', i, 'faces touched', f, 'edges', n, n == 2);
606 // }
607
608 for (j=0;j<n;j++) {
609 if (
610 sharpEdges[
611 orderedKey(vertexEdgeMap[i][j][0],vertexEdgeMap[i][j][1])
612 ]) {
613 sharpEdgeCount++;
614 }
615 }
616
617 // if ( sharpEdgeCount==2 ) {
618 // continue;
619 // // Do not move vertex if there's 2 connecting sharp edges.
620 // }
621
622 /*
623 if (sharpEdgeCount>2) {
624 // TODO
625 }
626 */
627
628 F.divideScalar(f);
629
630
631 var boundary_edges = 0;
632
633 if (boundary_case) {
634
635 var bb_edge;
636 for (j=0; j<n;j++) {
637 edge = vertexEdgeMap[i][j];
638 bb_edge = edgeFaceMap[orderedKey(edge[0], edge[1])].length == 1
639 if (bb_edge) {
640 var midPt = originalPoints[edge[0]].clone().addSelf(originalPoints[edge[1]]).divideScalar(2);
641 R.addSelf(midPt);
642 boundary_edges++;
643 }
644 }
645
646 R.divideScalar(4);
647 // console.log(j + ' --- ' + n + ' --- ' + boundary_edges);
648 assert(boundary_edges == 2, 'should have only 2 boundary edges');
649
650 } else {
651 for (j=0; j<n;j++) {
652 edge = vertexEdgeMap[i][j];
653 var midPt = originalPoints[edge[0]].clone().addSelf(originalPoints[edge[1]]).divideScalar(2);
654 R.addSelf(midPt);
655 }
656
657 R.divideScalar(n);
658 }
659
660 // Sum the formula
661 newPos.addSelf(originalPoints[i]);
662
663
664 if (boundary_case) {
665
666 newPos.divideScalar(2);
667 newPos.addSelf(R);
668
669 } else {
670
671 newPos.multiplyScalar(n - 3);
672
673 newPos.addSelf(F);
674 newPos.addSelf(R.multiplyScalar(2));
675 newPos.divideScalar(n);
676
677 }
678
679 newVertices[i] = newPos;
680
681 }
682
683 var newGeometry = oldGeometry; // Let's pretend the old geometry is now new :P
684
685 newGeometry.vertices = newVertices;
686 newGeometry.faces = newFaces;
687 newGeometry.faceVertexUvs[ 0 ] = newUVs;
688
689 delete newGeometry.__tmpVertices; // makes __tmpVertices undefined :P
690
691 newGeometry.computeCentroids();
692 newGeometry.computeFaceNormals();
693 newGeometry.computeVertexNormals();
694
695 };
696
nike free rn
new balance hombre baratas
cinturones gucci
ugg rebajas
cinturon gucci
ray ban baratas
nike cortez
peuterey mujer
christian louboutin madrid
mbt zapatos
gafas ray ban baratas
mbt ofertas
air max blancas
mbt barcelona
nike air max 90
woolrich barcelona
nike mujer
botas ugg
gafas de sol carrera aratas
air max 2016 baratas
oakley baratas
nike air max 2016