Source code: com/trapezium/vrml/node/space/SpaceStructure.java
1 /*
2 * @(#)SpaceStructure.java
3 *
4 * Copyright (c) 1998 by Trapezium Development LLC. All Rights Reserved.
5 *
6 * The information in this file is the property of Trapezium Development LLC
7 * and may be used only in accordance with the terms of the license granted
8 * by Trapezium.
9 *
10 */
11 package com.trapezium.vrml.node.space;
12
13 import com.trapezium.util.CompositeObject;
14 import com.trapezium.util.TypedObject;
15 import com.trapezium.util.GlobalProgressIndicator;
16 import com.trapezium.util.QSort;
17 import java.util.Vector;
18 import java.io.FileOutputStream;
19 import java.io.PrintStream;
20 import java.util.BitSet;
21 import java.util.Hashtable;
22
23 /** The SpaceStructure keeps track of vertices, edges, and faces in a somewhat fluid
24 * manner. There are three sets of objects, corresponding to vertices, edges, and
25 * faces, but these sets can be mixed, and relationships created between these sets.
26 * This is done to allow transformations of one type into another.
27 *
28 * A SpaceEntitySet represents a set of SpacePrimitive objects used by a particular
29 * space structure. The Strategy field "primitiveHandler" indicates the current
30 * visualization of a space entity and its surrounding entities.
31 *
32 * Relationships between the sets are created as needed, only r1 is known at the
33 * time the SpaceStructure is first created.
34 *
35 * The possible relationships are:
36 *
37 * r1. F ---* V
38 * The set of vertices surrounding each face,
39 * created when an IndexedFaceSet is loaded
40 * r2. V ---* F V,r2: requires r3()
41 * The set of faces surrounding each vertex,
42 * derived from r3
43 * r3. F ---* E F,r3: requires r1()
44 * The set of edges surrounding each face,
45 * derived from r1
46 * r4. E ---2 F E,r4:
47 * The set of faces (usually 2) surrounding each edge
48 * r5. V ---* E V,r5
49 * The set of edges surrounding each vertex
50 * r6. E ---2 V E,r6: E() creates this relationship
51 * The set of vertices (always 2) making up each edge
52 *
53 * The methods r1(), r2(), r3(), r4(), r5(), r6() create these relationships.
54 *
55 * A SpaceStructure is made up of three SpaceEntitySet objects, each of which is
56 * a set of SpacePrimitive objects. The type (vertex, edge, face) is kept as an
57 * attribute of the SpaceEntitySet to simplify the transformation of one type
58 * into another, and to simplify merging separate sets.
59 */
60 //
61 // For example, when the dual relationship is calculated, this approach simplifies the
62 // transformation. The dual relationship requires relationship #2.
63 // Vertices are converted to faces by changing the base type of the
64 // vertex space entity vector to SpacePrimitive.Face, and changing the base type of the
65 // face space entity vector to SpacePrimitive.Vertex. When this change is made, the
66 // strategy is also converted.
67 //
68 // To derive all single connected structures requires the stellation/trunction operations,
69 // plus the diagonlize/normalize operations. The diagonalize operation is an operation
70 // that can only occur on four sided faces (or on two adjacent triangles). For four sided
71 // faces, this is just drawing a diagonal. For adjacent triangular faces, this involves
72 // rotating the common edge 90 degrees.
73 //
74 // At the entire SpaceStructure level, the diagonalize operation is done only on 4 sided
75 // faces, according to an algorithm which includes a vertex of the diagonal at most once.
76 //
77 // My initial pass on this has the edges directionless. This I think is a mistake,
78 // because of the ccw face definition and because of efficiency. It is faster to
79 // have direction and allow the same edges to be added many times.
80 //
81
82 //
83 // It seems now this should possibly be two classes. The first should be
84 // a largely directionless listing of relationships. This allows for a fast
85 // implementation, and is useful for many cases.
86 //
87 // The second implementation should be what this started out to be... keeping
88 // track of all entities in ordered lists. This allows for operations on the
89 // space structure, such as all variations on truncations and stellations.
90 //
91 public class SpaceStructure {
92 // complete set of space primitives
93 SpaceEntitySet v1;
94 SpaceEntitySet v2;
95 SpaceEntitySet v3;
96
97 // complete set of prior space primitive sets, context for methods which may need prior
98 // set
99 SpaceEntitySet prevV1;
100 SpaceEntitySet prevV2;
101 SpaceEntitySet prevV3;
102
103 // new sets for reprocessing
104 SpaceEntitySet appendedV1;
105 SpaceEntitySet appendedV2;
106 SpaceEntitySet appendedV3;
107
108 // used for building single face
109 int[] singleFaceCoords;
110 int[] singleTexCoords;
111 int[] singleNormalCoords;
112 int[] singleColorCoords;
113 int singleFaceCoordIdx;
114
115 /* static final double DefaultTransparency = 0.0;
116 double transparency = DefaultTransparency;
117
118 static final double DefaultEmissiveColor = 0.0;
119 double rEmissive = DefaultEmissiveColor;
120 double gEmissive = DefaultEmissiveColor;
121 double bEmissive = DefaultEmissiveColor;
122
123 public void setEmissiveColor( double r, double g, double b ) {
124 rEmissive = r;
125 gEmissive = g;
126 bEmissive = b;
127 }
128
129 public void setTransparency( double t ) {
130 transparency = t;
131 System.out.println( "Just set transparency to " + transparency );
132 }*/
133
134 static int idCounter = 1;
135 int id;
136
137 /** Class constructor */
138 public SpaceStructure() {
139 v1 = new SpaceEntitySet( new Strategy( this, SpacePrimitive.Vertex ), this );
140 v2 = new SpaceEntitySet( new Strategy( this, SpacePrimitive.Edge ), this );
141 v3 = new SpaceEntitySet( new Strategy( this, SpacePrimitive.Face ), this );
142 initArrays();
143 }
144
145 /** internal array and id initialization, used only by constructors */
146 void initArrays() {
147 id = idCounter++;
148 singleFaceCoords = new int[200];
149 singleTexCoords = new int[200];
150 singleNormalCoords = new int[200];
151 singleColorCoords = new int[200];
152 singleFaceCoordIdx = 0;
153 }
154
155 /** Copy constructor */
156 public SpaceStructure( SpaceStructure original ) {
157 v1 = new SpaceEntitySet( original.getEntitySet( SpacePrimitive.Vertex ));
158 v2 = new SpaceEntitySet( original.getEntitySet( SpacePrimitive.Edge ));
159 v3 = new SpaceEntitySet( original.getEntitySet( SpacePrimitive.Face ));
160 initArrays();
161 }
162
163 /** Copy entities from
164
165 public void dump() {
166 dump( "JJ" );
167 }
168
169 public void dump( String s ) {
170 System.out.println( s );
171 SpaceEntitySet.debug = true;
172 SpaceEntitySet v = getEntitySet( SpacePrimitive.Vertex );
173 v.dump( "Vertices" );
174 SpaceEntitySet e = getEntitySet( SpacePrimitive.Edge );
175 e.dump( "Edges" );
176 SpaceEntitySet f = getEntitySet( SpacePrimitive.Face );
177 f.dump( "Faces" );
178 SpaceEntitySet.debug = false;
179 }
180
181 /** Get the number of entities in the set of the given type.
182 *
183 * @param type SpacePrimitive.Vertex, SpacePrimitive.Edge, or SpacePrimitive.Face
184 *
185 * @return the number of vertices, edges, or faces in the structure.
186 */
187 public int getNumberEntities( int type ) {
188 SpaceEntitySet ses = getEntitySet( type );
189 return( ses.getNumberEntities() );
190 }
191
192 public void summarize() {
193 SpaceEntitySet v = getEntitySet( SpacePrimitive.Vertex );
194 SpaceEntitySet e = getEntitySet( SpacePrimitive.Edge );
195 SpaceEntitySet f = getEntitySet( SpacePrimitive.Face );
196 int triangleCount = 0;
197 for ( int i = 0; i < f.getNumberEntities(); i++ ) {
198 SpacePrimitive face = f.getEntity( i );
199 int count = f.getCount( face, SpacePrimitive.Vertex );
200 if ( count == 3 ) {
201 triangleCount++;
202 }
203 }
204 if ( f.getNumberEntities() == 0 ) {
205 System.out.println( "Warning! No faces!...." + v.getNumberEntities() + " vertices" );
206 } else if ( f.getNumberEntities() == triangleCount ) {
207 System.out.println( "Faces all triangles. " + f.getNumberEntities() + " faces, " + v.getNumberEntities() + " vertices, " + e.getNumberEntities() + " edges." );
208 } else {
209 System.out.println( v.getNumberEntities() + " vertices, " + e.getNumberEntities() + " edges, " + f.getNumberEntities() + " faces." );
210 System.out.println( "There are " + triangleCount + " triangles" );
211 }
212 }
213
214 //
215 // The polygon reduction algorithm tests for edges to remove and merges adjacent faces
216 //
217 int mergeCount = 0;
218 public int getMergeCount() {
219 return( mergeCount );
220 }
221
222 int[] faceToMergeWith;
223
224 public int coplanarTriToQuad( int ifsNumber ) {
225 return( coplanarTriToQuad( 0.0000000001, ifsNumber ));
226 }
227
228 /** The set of faces removed by "edgeRemovalPolygonReduction" or "coplanarTriToQuad" */
229 BitSet faceRemovalCandidateSet = null;
230
231 /** The number of bits in the "removedFaceSet" above */
232 int faceBitCount = 0;
233 public BitSet getFaceBits() {
234 return( faceRemovalCandidateSet );
235 }
236 public int getFaceBitCount() {
237 return( faceBitCount );
238 }
239
240 /** Connectivity sections */
241 Vector connectivityList;
242
243 /** Create the connectivity sections for this structure */
244 public void markConnectivity() {
245 connectivityList = new Vector();
246 r5();
247 r3();
248 SpaceEntitySet faces = getEntitySet( SpacePrimitive.Face );
249 SpaceEntitySet edges = getEntitySet( SpacePrimitive.Edge );
250 int numberEdges = edges.getNumberEntities();
251 int numberFaces = faces.getNumberEntities();
252 System.out.println( "createFtoE" );
253 createFtoE( edges, faces, numberFaces );
254
255 // keep going until all faces are placed in a connectivity group
256 BitSet edgeConnectivity = new BitSet( numberEdges );
257 System.out.println( "marking connectivity" );
258 while ( true ) {
259 int startEdge = getStartEdge( edgeConnectivity, numberEdges );
260 if ( startEdge == numberEdges ) {
261 break;
262 }
263 System.out.println( "startEdge is " + startEdge + " of " + numberEdges );
264 BitSet faceConnectivity = new BitSet( numberFaces );
265 markConnectivity( edgeConnectivity, edges, startEdge, faces, faceConnectivity );
266 connectivityList.addElement( faceConnectivity );
267 }
268 System.out.println( "done." );
269 }
270
271 /** Get the number of connectivity sections */
272 public int numberConnectivity() {
273 return( connectivityList.size() );
274 }
275
276 /** Get the connectivity section number for a particular face */
277 public int getConnectivity( int faceNo ) {
278 int clistSize = connectivityList.size();
279 for ( int i = 0; i < clistSize; i++ ) {
280 BitSet b = (BitSet)connectivityList.elementAt( i );
281 if ( b.get( faceNo )) {
282 return( i );
283 }
284 }
285 return( -1 );
286 }
287
288 int getStartEdge( BitSet edgeConnectivity, int numberEdges ) {
289 for ( int i = 0; i < numberEdges; i++ ) {
290 if ( !edgeConnectivity.get( i )) {
291 return( i );
292 }
293 }
294 return( numberEdges );
295 }
296
297 int[] nextToCheckList;
298 int nextToCheckIdx;
299 int maxToCheck;
300 int getNextEdgeToCheck( BitSet edgesToCheck, int numberEdges ) {
301 if ( nextToCheckIdx >= maxToCheck ) {
302 fillNextToCheckList( edgesToCheck, numberEdges );
303 }
304 if ( nextToCheckIdx >= maxToCheck ) {
305 return( -1 );
306 }
307 int result = nextToCheckList[ nextToCheckIdx ];
308 nextToCheckIdx++;
309 return( result );
310 }
311
312 void fillNextToCheckList( BitSet edgesToCheck, int numberEdges ) {
313 int idx = 0;
314 nextToCheckIdx = 0;
315 maxToCheck = 0;
316 for ( int i = 0; i < numberEdges; i++ ) {
317 if ( edgesToCheck.get( i )) {
318 nextToCheckList[ maxToCheck ] = i;
319 maxToCheck++;
320 }
321 if ( maxToCheck >= 100 ) {
322 break;
323 }
324 }
325 }
326
327 /** Mark connectivity for a set of faces linked to a single start edge */
328 void markConnectivity( BitSet edgeConnectivity, SpaceEntitySet edges, int startEdge, SpaceEntitySet faces, BitSet faceConnectivity ) {
329 int numberEdges = edges.getNumberEntities();
330 BitSet edgesToCheck = new BitSet( numberEdges );
331 if ( nextToCheckList == null ) {
332 nextToCheckList = new int[100];
333 nextToCheckIdx = 0;
334 maxToCheck = 0;
335 }
336 edgesToCheck.set( startEdge );
337 int count = 0;
338 while ( true ) {
339 startEdge = getNextEdgeToCheck( edgesToCheck, numberEdges );
340 if ( startEdge == -1 ) {
341 break;
342 }
343 markEdge( edgeConnectivity, startEdge, edges, faces, faceConnectivity, edgesToCheck );
344 count++;
345 if (( count % 100 ) == 0 ) {
346 System.out.println( "marked " + count + " edges" );
347 }
348 }
349 int ecount = 0;
350 for ( int i = 0; i < numberEdges; i++ ) {
351 if ( edgeConnectivity.get( i )) {
352 ecount++;
353 }
354 }
355 System.out.println( "marked " + ecount + " of " + numberEdges + " edges" );
356 }
357
358 /** mark edges associated with a single edge.
359 *
360 * @param edgeConnectivity BitSet indicating which edges have been marked for connectivity
361 * @param startEdge offset of the edge we are checking
362 * @param edges SpaceEntitySet of edges for this structure
363 * @param faces SpaceEntitySet of faces for this structure
364 * @param faceConnectivity set of faces marked for connectivity
365 * @param edgesToCheck working set of edges that remain to be checked
366 */
367 void markEdge( BitSet edgeConnectivity, int startEdge, SpaceEntitySet edges,
368 SpaceEntitySet faces, BitSet faceConnectivity, BitSet edgesToCheck ) {
369 edgesToCheck.clear( startEdge );
370 if ( !edgeConnectivity.get( startEdge )) {
371 edgeConnectivity.set( startEdge );
372 SpacePrimitive edge = edges.getEntity( startEdge );
373 markFace( edges.getValue( edge, SpacePrimitive.Face, 0 ), faces, faceConnectivity, edgesToCheck, edgeConnectivity );
374 markFace( edges.getValue( edge, SpacePrimitive.Face, 1 ), faces, faceConnectivity, edgesToCheck, edgeConnectivity );
375 }
376 }
377
378 /** mark the face in its connectivity set, add edges to check list */
379 void markFace( int fidx, SpaceEntitySet faces, BitSet faceConnectivity, BitSet edgesToCheck, BitSet edgeConnectivity ) {
380 if ( fidx != -1 ) {
381 if ( !faceConnectivity.get( fidx )) {
382 faceConnectivity.set( fidx );
383 SpacePrimitive face = faces.getEntity( fidx );
384 int numberEdges = faces.getCount( face, SpacePrimitive.Edge );
385 for ( int i = 0; i < numberEdges; i++ ) {
386 int edge = faces.getValue( face, SpacePrimitive.Edge, i );
387 if ( !edgeConnectivity.get( edge )) {
388 edgesToCheck.set( edge );
389 }
390 }
391 }
392 }
393 }
394
395 /** The set of edges that are removed */
396 BitSet normalMergeSet = null;
397
398 /** Get the index of the face merged with a particular face.
399 *
400 * @param faceIdx face that continues to exist
401 * @return index of face that is merged with faceIdx, -1 if none
402 */
403 public int getMergeFace( int faceIdx ) {
404 if ( normalMergeSet == null ) {
405 return( -1 );
406 }
407 SpaceEntitySet faces = getEntitySet( SpacePrimitive.Face );
408 SpacePrimitive face = faces.getEntity( faceIdx );
409 int eCount = faces.getCount( face, SpacePrimitive.Edge );
410 for ( int i = 0; i < eCount; i++ ) {
411 int eval = faces.getValue( face, SpacePrimitive.Edge, i );
412 if ( normalMergeSet.get( eval )) {
413 SpaceEntitySet edges = getEntitySet( SpacePrimitive.Edge );
414 SpacePrimitive edge = edges.getEntity( eval );
415 int fCount = edges.getCount( edge, SpacePrimitive.Face );
416 for ( int j = 0; j < fCount; j++ ) {
417 int fval = edges.getValue( edge, SpacePrimitive.Face, j );
418 if ( fval != faceIdx ) {
419 return( fval );
420 }
421 }
422 }
423 }
424 return( -1 );
425 }
426
427 /** Merge coplanar polygons.
428 * @param limit coplanar triangles detected by a getting area defined by
429 * normals to each triangle. Zero means they are coplanar, the "limit"
430 * parameter is a zero equivalent, any area less than this is treated
431 * as zero.
432 */
433 public int coplanarTriToQuad( double limit, int ifsNumber ) {
434 // Generate edges
435 SpaceEntitySet vertices = getEntitySet( SpacePrimitive.Vertex );
436 int numberVertices = vertices.getNumberEntities();
437 GlobalProgressIndicator.activateAlternateProgressIndicator( 0 );
438 GlobalProgressIndicator.setUnitSize( numberVertices*2, 4 );
439 E();
440
441 // generate the faces surrounding each edge
442 SpaceEntitySet edges = getEntitySet( SpacePrimitive.Edge );
443 int numberEdges = edges.getNumberEntities();
444 r4();
445
446 // Test each edge for removal by seeing if its surrounding faces are coplanar
447 SpaceEntitySet faces = getEntitySet( SpacePrimitive.Face );
448 boolean[] edgeCanBeRemoved = new boolean[ numberEdges ];
449 faceBitCount = faces.getNumberEntities();
450 faceRemovalCandidateSet = new BitSet( faceBitCount );
451 for ( int i = 0; i < numberEdges; i++ ) {
452 GlobalProgressIndicator.markProgress();
453 edgeCanBeRemoved[i] = false;
454 SpacePrimitive edge = edges.getEntity( i );
455 SpacePrimitive v1 = edges.getEntity( edge, SpacePrimitive.Vertex, 0 );
456 SpacePrimitive v2 = edges.getEntity( edge, SpacePrimitive.Vertex, 1 );
457 if (( v1 == null ) || ( v2 == null )) {
458 continue;
459 }
460 if ( v1.equalTo( v2 )) {
461 continue;
462 }
463 int v1offset = edges.getValue( edge, SpacePrimitive.Vertex, 0 );
464 int v2offset = edges.getValue( edge, SpacePrimitive.Vertex, 1 );
465 SpacePrimitive f1 = edges.getEntity( edge, SpacePrimitive.Face, 0 );
466 SpacePrimitive f2 = edges.getEntity( edge, SpacePrimitive.Face, 1 );
467 if (( f1 == null ) || ( f2 == null )) {
468 continue;
469 }
470 // only do this operation for coplanar triangles
471 if ( faces.getCount( f1, SpacePrimitive.Vertex ) != 3 ) {
472 continue;
473 }
474 if ( faces.getCount( f2, SpacePrimitive.Vertex ) != 3 ) {
475 continue;
476 }
477 SpacePrimitive v3 = null;
478 SpacePrimitive v4 = null;
479
480 // v3 is an f1 vertex other than v1 and v2
481 int v3offset = -1;
482 for ( int j = 0; j < faces.getCount( f1, SpacePrimitive.Vertex ); j++ ) {
483 SpacePrimitive v = faces.getEntity( f1, SpacePrimitive.Vertex, j );
484 if (( v != v1 ) && ( v != v2 )) {
485 // equalTo tests required because we see 3DS Max output making degenerate
486 // triangular faces
487 if ( v.equalTo( v1 )) {
488 continue;
489 }
490 if ( v.equalTo( v2 )) {
491 continue;
492 }
493 v3 = v;
494 v3offset = faces.getValue( f1, SpacePrimitive.Vertex, j );
495 break;
496 }
497 }
498 if ( v3 == null ) {
499 continue;
500 }
501
502 // v4 is an f2 vertex other than v1 and v2
503 int v4offset = -1;
504 for ( int j = 0; j < faces.getCount( f2, SpacePrimitive.Vertex ); j++ ) {
505 SpacePrimitive v = faces.getEntity( f2, SpacePrimitive.Vertex, j );
506 if ( v.equalTo( v1 )) {
507 continue;
508 } else if ( v.equalTo( v2 )) {
509 continue;
510 } else if ( v.equalTo( v3 )) {
511 continue;
512 } else {
513 v4 = v;
514 v4offset = faces.getValue( f2, SpacePrimitive.Vertex, j );
515 break;
516 }
517 }
518
519 if ( v4 == null ) {
520 continue;
521 }
522
523 if ( coplanar( v1, v2, v3, v4, limit )) {
524 // System.out.println( "Edge " + i + " can be removed" );
525 // here we have to check that the faces have the same
526 // per vertex data for the edge v1->v2 and edge v2->v1
527 Object f1attachment = f1.getAttachedObject();
528 Object f2attachment = f2.getAttachedObject();
529 if (( f1attachment != null ) && ( f2attachment != null )) {
530 TypedObject f1data = (TypedObject)((TypedObject)f1attachment).getObject( PerVertexData.Texture );
531 TypedObject f2data = (TypedObject)((TypedObject)f2attachment).getObject( PerVertexData.Texture );
532 if (( f1data != null ) && ( f2data != null )) {
533 PerVertexData f1vdata = (PerVertexData)f1data.getObject( PerVertexData.Texture );
534 PerVertexData f2vdata = (PerVertexData)f2data.getObject( PerVertexData.Texture );
535 if (( f1vdata != null ) && ( f2vdata != null )) {
536 if (( f1vdata.getValue( v1offset ) == f2vdata.getValue( v1offset )) &&
537 ( f1vdata.getValue( v2offset ) == f2vdata.getValue( v2offset ))) {
538 edgeCanBeRemoved[i] = true;
539 }
540 } else {
541 edgeCanBeRemoved[i] = true;
542 }
543 } else {
544 edgeCanBeRemoved[i] = true;
545 }
546 } else {
547 edgeCanBeRemoved[i] = true;
548 }
549 // } else {
550 // System.out.println( "Edge " + i + " cannot be removed" );
551 }
552 }
553
554 // for each face, if face has any edge marked for removal, see if face can be
555 // removed, note that this marks ALL faces adjacent to removed edge as removable,
556 // when in face, one of those faces has to remain. This is handled by the face
557 // merge algorithm
558 int numberFaces = faces.getNumberEntities();
559 faceToMergeWith = new int[ numberFaces ];
560 mergeCount = 0;
561 GlobalProgressIndicator.replaceHalfUnit( numberFaces );
562 for ( int i = 0; i < numberFaces; i++ ) {
563 GlobalProgressIndicator.markProgress();
564 faceToMergeWith[ i ] = -1;
565 SpacePrimitive face = faces.getEntity( i );
566 for ( int j = 0; j < faces.getCount( face, SpacePrimitive.Edge ); j++ ) {
567 int edge = faces.getValue( face, SpacePrimitive.Edge, j );
568 if ( edgeCanBeRemoved[ edge ] ) {
569 faceRemovalCandidateSet.set( i );
570 // System.out.println( "face " + i + " is a removal candidate" );
571 SpacePrimitive fedge = edges.getEntity( edge );
572 int f1value = edges.getValue( fedge, SpacePrimitive.Face, 0 );
573 int f2value = edges.getValue( fedge, SpacePrimitive.Face, 1 );
574 if ( i == f1value ) {
575 faceToMergeWith[ i ] = f2value;
576 } else {
577 faceToMergeWith[ i ] = f1value;
578 }
579 break;
580 }
581 }
582 }
583 // for ( int i = 0; i < numberFaces; i++ ) {
584 // if ( faceRemovalCandidateSet.get( i )) { // if ( faceCanBeRemoved[i] ) {
585 // System.out.println( "Face " + i + " can merge with face " + faceToMergeWith[ i ] );
586 // } else {
587 // System.out.println( "Face " + i + " cannot be removed.." );
588 // }
589 // }
590
591 // Face merging algorithm. For now, we only merge two faces (a simplification
592 // of the general problem).
593 //
594 // 1. select face to merge with. If this face indicates current face, merge can
595 // continue. If not, merge has already taken place.
596 // 2.
597 SpaceEntitySet newFaces = new SpaceEntitySet( new Strategy( this, SpacePrimitive.Face ), this );
598 newFaces.validate( SpacePrimitive.Vertex );
599 int[] offsets = new int[200];
600
601 // array of faces that are removed
602 BitSet facesRemoved = new BitSet( numberFaces );
603 GlobalProgressIndicator.endGame( numberFaces );
604 for ( int i = 0; i < numberFaces; i++ ) {
605 SpacePrimitive face = faces.getEntity( i );
606 if ( faceRemovalCandidateSet.get( i ) ) {
607 // if the face we are marked to merge with is already removed,
608 // can't do anything
609 int disappearingFace = faceToMergeWith[i];
610 if ( facesRemoved.get( disappearingFace )) {
611 // System.out.println( "face " + i + " merge partner " + faceToMergeWith[i] + " already removed" );
612 continue;
613 } else if ( facesRemoved.get( i )) {
614 // System.out.println( "face " + i + " already removed" );
615 continue;
616 } else if ( faceRemovalCandidateSet.get( disappearingFace )) {
617 // merge face with the other one
618 // System.out.println( "Merging face " + i + " with " + disappearingFace );
619 mergeCount++;
620 facesRemoved.set( disappearingFace );
621 faceRemovalCandidateSet.clear( disappearingFace );
622 faceRemovalCandidateSet.clear( i );
623 SpacePrimitive f2 = faces.getEntity( disappearingFace );
624 faceToMergeWith[ disappearingFace ] = i;
625
626 // get the values of the two shared points
627 int v1shared = -1;
628 int f1v1offset = -1;
629 int f1v2offset = -1;
630 int v2shared = -1;
631 int f2v1offset = -1;
632 int f2v2offset = -1;
633 int offsetIdx = 0;
634 for ( int j = 0; j < faces.getCount( face, SpacePrimitive.Vertex ); j++ ) {
635 int testv1 = faces.getValue( face, SpacePrimitive.Vertex, j );
636 for ( int k = 0; k < faces.getCount( f2, SpacePrimitive.Vertex ); k++ ) {
637 int testv2 = faces.getValue( f2, SpacePrimitive.Vertex, k );
638 if ( testv1 == testv2 ) {
639 if ( v1shared == -1 ) {
640 v1shared = testv1;
641 f1v1offset = j;
642 f2v1offset = k;
643 break;
644 } else if ( v2shared == -1 ) {
645 v2shared = testv2;
646 f1v2offset = j;
647 f2v2offset = k;
648 break;
649 }
650 }
651 }
652 if ( v2shared != -1 ) {
653 break;
654 }
655 }
656
657 if (( v1shared == -1 ) || ( v2shared == -1 )) {
658 System.out.println( "Didn't find shared values between faces!!!" );
659 } else {
660 // For f1, what is first offset past the two shared points
661 if ( f1v1offset > f1v2offset ) {
662 int t = f1v1offset;
663 f1v1offset = f1v2offset;
664 f1v2offset = t;
665 }
666 // at this point, f1v1offset < f1v2offset
667 int f1scan = -1;
668 if ( f1v1offset == 0 ) {
669 if ( f1v2offset == 1 ) {
670 f1scan = 2;
671 } else {
672 f1scan = 1;
673 }
674 } else {
675 f1scan = f1v2offset + 1;
676 if ( f1scan == faces.getCount( face, SpacePrimitive.Vertex )) {
677 f1scan = 0;
678 }
679 }
680 int fcount = faces.getCount( face, SpacePrimitive.Vertex );
681 for ( int j = 0; j < ( fcount - 1 ); j++ ) {
682 offsets[ offsetIdx ] = faces.getValue( face, SpacePrimitive.Vertex, ( j + f1scan ) % fcount );
683 offsetIdx++;
684 }
685
686 // For f2, what is first offset past the two shared points
687 if ( f2v1offset > f2v2offset ) {
688 int t = f2v1offset;
689 f2v1offset = f2v2offset;
690 f2v2offset = t;
691 }
692 // at this point, f1v1offset < f1v2offset
693 int f2scan = -1;
694 if ( f2v1offset == 0 ) {
695 if ( f2v2offset == 1 ) {
696 f2scan = 2;
697 } else {
698 f2scan = 1;
699 }
700 } else {
701 f2scan = f2v2offset + 1;
702 if ( f2scan == faces.getCount( f2, SpacePrimitive.Vertex )) {
703 f2scan = 0;
704 }
705 }
706 fcount = faces.getCount( f2, SpacePrimitive.Vertex );
707 for ( int j = 0; j < ( fcount - 1 ); j++ ) {
708 offsets[ offsetIdx ] = faces.getValue( f2, SpacePrimitive.Vertex, ( j + f2scan ) % fcount );
709 offsetIdx++;
710 }
711 SpacePrimitive newFace = new SpacePrimitive( offsets, offsetIdx );
712 Object faceAttachment = face.getAttachedObject();
713 Object f2Attachment = f2.getAttachedObject();
714 if (( faceAttachment != null ) && ( f2Attachment != null )) {
715 if ( faceAttachment instanceof CompositeObject ) {
716 if ( f2Attachment instanceof CompositeObject ) {
717 Object f1obj = ((CompositeObject)faceAttachment).getObjectA();
718 Object f2obj = ((CompositeObject)f2Attachment).getObjectA();
719 newFace.attachObject( new PerVertexData( f1obj, f2obj ));
720 f1obj = ((CompositeObject)faceAttachment).getObjectB();
721 f2obj = ((CompositeObject)f2Attachment).getObjectB();
722 newFace.attachObject( new PerVertexData( f1obj, f2obj ));
723 }
724 } else {
725 newFace.attachObject( new PerVertexData( face.getAttachedObject(), f2.getAttachedObject() ));
726 }
727 }
728 newFaces.addEntity( newFace );
729 }
730 }
731 } else if ( !facesRemoved.get( i )) {
732 // System.out.println( "Preserving face " + i );
733 int offsetIdx = faces.getCount( face, SpacePrimitive.Vertex );
734 for ( int j = 0; j < offsetIdx; j++ ) {
735 offsets[j] = faces.getValue( face, SpacePrimitive.Vertex, j );
736 }
737 SpacePrimitive newFace = new SpacePrimitive( offsets, offsetIdx );
738 if ( face.getAttachedObject() != null ) {
739 newFace.attachObject( face.getAttachedObject() );
740 }
741 newFaces.addEntity( newFace );
742 }
743 }
744 faceRemovalCandidateSet = facesRemoved;
745 // for ( int i = 0; i < numberFaces; i++ ) {
746 // if ( faceRemovalCandidateSet.get( i )) { // if ( faceCanBeRemoved[i] ) {
747 // System.out.println( "Face " + i + " merged with face " + faceToMergeWith[ i ] );
748 // } else {
749 // System.out.println( "Face " + i + " remains.." );
750 // }
751 // }
752 replaceSet( SpacePrimitive.Face, newFaces );
753 GlobalProgressIndicator.deactivateAlternateProgressIndicator();
754 return( mergeCount );
755 }
756
757 public boolean coplanar( SpacePrimitive v1, SpacePrimitive v2, SpacePrimitive v3, SpacePrimitive v4, double limit ) {
758 double v1x = v1.getX();
759 double v1y = v1.getY();
760 double v1z = v1.getZ();
761 double v2x = v2.getX() - v1x;
762 double v2y = v2.getY() - v1y;
763 double v2z = v2.getZ() - v1z;
764 double v3x = v3.getX() - v1x;
765 double v3y = v3.getY() - v1y;
766 double v3z = v3.getZ() - v1z;
767 double v4x = v4.getX() - v1x;
768 double v4y = v4.getY() - v1y;
769 double v4z = v4.getZ() - v1z;
770 double result = 0.0;
771 result += v2x * v3y * v4z;
772 result += v3x * v4y * v2z;
773 result += v4x * v2y * v3z;
774 result -= v2x * v4y * v3z;
775 result -= v3x * v2y * v4z;
776 result -= v4x * v3y * v2z;
777 // System.out.println( "result is " + result );
778 if ( result < 0 ) result = -1* result;
779 if ( result <= limit ) {
780 // if ( result != 0 ) {
781 // System.out.println( "non zero result " + result );
782 // }
783 return( true );
784 } else {
785 return( false );
786 }
787 }
788
789 /** Multiply each vertex by a factor */
790 public void expand( float factor ) {
791 SpaceEntitySet vertices = getEntitySet( SpacePrimitive.Vertex );
792 vertices.setCenterLocation();
793 for ( int i = 0; i < vertices.getNumberEntities(); i++ ) {
794 SpacePrimitive v = vertices.getEntity( i );
795 v.expand( factor );
796 }
797 }
798
799 public void createSet( SpaceEntitySet obsoleteSet, int type ) {
800 if ( obsoleteSet == v1 ) {
801 v1 = new SpaceEntitySet( new Strategy( this, type ), this );
802 } else if ( obsoleteSet == v2 ) {
803 v2 = new SpaceEntitySet( new Strategy( this, type ), this );
804 } else if ( obsoleteSet == v3 ) {
805 v3 = new SpaceEntitySet( new Strategy( this, type ), this );
806 }
807 }
808
809 int preAppendCount = 0;
810 public void appendSet( int type, SpaceEntitySet newSet ) {
811 SpaceEntitySet s = getEntitySet( type );
812 preAppendCount = s.getNumberEntities();
813 if ( s == v1 ) {
814 appendedV1 = newSet;
815 s.appendSet( newSet );
816 } else if ( s == v2 ) {
817 appendedV2 = newSet;
818 s.appendSet( newSet );
819 } else if ( s == v3 ) {
820 appendedV3 = newSet;
821 s.appendSet( newSet );
822 }
823 }
824
825 public void replaceSet( int type, SpaceEntitySet newSet ) {
826 SpaceEntitySet obsoleteSet = getEntitySet( type );
827 if ( obsoleteSet == v1 ) {
828 prevV1 = v1;
829 v1 = newSet;
830 } else if ( obsoleteSet == v2 ) {
831 prevV2 = v2;
832 v2 = newSet;
833 } else if ( obsoleteSet == v3 ) {
834 prevV3 = v3;
835 v3 = newSet;
836 }
837 }
838
839 public void invalidate( int type ) {
840 SpaceEntitySet newSet = new SpaceEntitySet( new Strategy( this, type ), this );
841 replaceSet( type, newSet );
842 }
843
844
845 /** Get the SpaceEntitySet for the vertices, edges, or faces.
846 *
847 * @param type either SpacePrimitive.Vertex, SpacePrimitive.Edge, or
848 * SpacePrimitive.Face
849 *
850 * @return the SpaceEntitySet of the given type, or null if none exists
851 * for that type.
852 */
853 public SpaceEntitySet getEntitySet( int type ) {
854 if ( v1.getBaseType() == type ) {
855 return( v1 );
856 } else if ( v2.getBaseType() == type ) {
857 return( v2 );
858 } else if ( v3.getBaseType() == type ) {
859 return( v3 );
860 } else {
861 return( null );
862 }
863 }
864
865 public SpaceEntitySet getPrevEntitySet( int type ) {
866 if (( prevV1 != null ) && ( prevV1.getBaseType() == type )) {
867 return( prevV1 );
868 } else if (( prevV2 != null ) && ( prevV2.getBaseType() == type )) {
869 return( prevV2 );
870 } else if (( prevV3 != null ) && ( prevV3.getBaseType() == type )) {
871 return( prevV3 );
872 } else {
873 return( null );
874 }
875 }
876
877 public SpaceEntitySet getAppendedSet( int type ) {
878 if (( appendedV1 != null ) && ( appendedV1.getBaseType() == type )) {
879 return( appendedV1 );
880 } else if (( appendedV2 != null ) && ( appendedV2.getBaseType() == type )) {
881 return( appendedV2 );
882 } else if (( appendedV3 != null ) && ( appendedV3.getBaseType() == type )) {
883 return( appendedV3 );
884 } else {
885 return( null );
886 }
887 }
888
889
890 /** Set the center location for each SpacePrimitive by averaging location of surrounding entities.
891 *
892 * @param baseType the SpacePrimitive type whose locations are to be calculated.
893 * @param avgType the type of surrounding SpacePrimitive to use in the average calculations.
894 */
895 public void setLocation( int baseType, int avgType ) {
896 setLocation( baseType, avgType, false, 0, 0, 0, 0 );
897 }
898
899 public void setLocation( int baseType, int avgType, float cx, float cy, float cz, float distance ) {
900 setLocation( baseType, avgType, true, cx, cy, cz, distance );
901 }
902
903 void setLocation( int baseType, int avgType, boolean setDistance, float cx, float cy, float cz, float distance ) {
904 SpaceEntitySet s = getEntitySet( baseType );
905 s.dump( "This is base set" );
906 SpaceEntitySet ref = getEntitySet( avgType );
907 ref.dump( "This is surrounding set" );
908 for ( int i = 0; i < s.getNumberEntities(); i++ ) {
909 SpacePrimitive sp = s.getEntity( i );
910 float xSum = 0;
911 float ySum = 0;
912 float zSum = 0;
913 int count = s.getCount( sp, avgType );
914 for ( int j = 0; j < count; j++ ) {
915 int index = s.getValue( sp, avgType, j );
916 SpacePrimitive spref = ref.getEntity( index );
917 xSum += spref.getX();
918 ySum += spref.getY();
919 zSum += spref.getZ();
920 }
921 xSum = xSum/count;
922 ySum = ySum/count;
923 zSum = zSum/count;
924 sp.setLocation( xSum, ySum, zSum );
925
926 if ( setDistance ) {
927 // get the distance from center
928 s.setDistance( sp, distance );
929 }
930 }
931 }
932
933 /** Add a vertex to the SpaceEntitySet for vertices.
934 * This is used to initially create the vertex set when an IndexedFaceSet
935 * is encountered.
936 */
937 public void addVertex( float x, float y, float z ) {
938 getEntitySet( SpacePrimitive.Vertex ).addEntity( new SpacePrimitive( x, y, z ));
939 }
940
941 //
942 // Need to replace this all with FaceBuilder internal class
943 // FaceBuilder attributes are: singleTexCoords, singleNormalCoords,
944 // singleColorCoords, createTexObject, createNormalObject,
945 // createColorObject.
946 //
947 boolean createTexObject = false;
948 public void addTexCoord( int value ) {
949 singleTexCoords[ singleFaceCoordIdx ] = value;
950 createTexObject = true;
951 }
952
953 boolean createNormalObject = false;
954 public void addNormalCoord( int value ) {
955 singleNormalCoords[ singleFaceCoordIdx ] = value;
956 createNormalObject = true;
957 }
958
959 boolean createColorObject = false;
960 public void addColorCoord( int value ) {
961 singleColorCoords[ singleFaceCoordIdx ] = value;
962 createColorObject = true;
963 }
964
965 /** Add another coord to the face being built one coord at a time */
966 public void addFaceCoord( int value ) {
967 if ( value == -1 ) {
968 addFace();
969 } else {
970 singleFaceCoords[ singleFaceCoordIdx ] = value;
971 singleFaceCoordIdx++;
972 }
973 }
974
975 /** Add a face that has been collected on coord at a time */
976 SpacePrimitive newlyAddedFace;
977 public void addFace() {
978 SpacePrimitive sp = new SpacePrimitive(
979 singleFaceCoords, singleFaceCoordIdx );
980 if ( createTexObject ) {
981 sp.attachObject( new PerVertexData( singleFaceCoords,
982 singleTexCoords, singleFaceCoordIdx, PerVertexData.Texture ));
983 createTexObject = false;
984 }
985 if ( createNormalObject ) {
986 sp.attachObject( new PerVertexData( singleFaceCoords,
987 singleNormalCoords, singleFaceCoordIdx, PerVertexData.Normal ));
988 createNormalObject = false;
989 }
990 if ( createColorObject ) {
991 sp.attachObject( new PerVertexData( singleFaceCoords,
992 singleColorCoords, singleFaceCoordIdx, PerVertexData.Color ));
993 createColorObject = false;
994 }
995 getEntitySet( SpacePrimitive.Face ).addEntity( sp );
996 getEntitySet( SpacePrimitive.Face ).validate( SpacePrimitive.Vertex );
997 singleFaceCoordIdx = 0;
998 newlyAddedFace = sp;
999 }
1000
1001 /** Hack, since I don't use face location, don't want to make
1002 * SpacePrimitive too big...
1003 */
1004 public void setFaceColor( int value ) {
1005 newlyAddedFace.setLocation( value, value, value );
1006 }
1007
1008
1009 //
1010 // Diagonalize an entire structure according to the following algorithm.
1011 // 1. diagonalize the first square face
1012 // 2. for each face that includes a point in a previously diagonalized face,
1013 // diagonalize the face so that the diagonal does not include a vertex in
1014 // any previous diagonal
1015 //
1016 public void diagonalize() {
1017 SpaceEntitySet faces = getEntitySet( SpacePrimitive.Face );
1018 int originalFaceCount = faces.getNumberEntities();
1019 DiagonalizeInfo d = new DiagonalizeInfo();
1020 for ( int i = 0; i < originalFaceCount; i++ ) {
1021 SpacePrimitive face = faces.getEntity( i );
1022 if ( faces.getCount( face, SpacePrimitive.Vertex ) == 4 ) {
1023 faces.diagonalize( face, d );
1024 }
1025 }
1026 }
1027
1028 float max1;
1029 float max2;
1030 float max3;
1031 void initMaxes() {
1032 max1 = max2 = max3 = 0;
1033 }
1034
1035 void markMax( float d ) {
1036 if ( max1 == 0 ) {
1037 max1 = max2 = max3 = d;
1038 } else if ( d > max1 ) {
1039 max3 = max2;
1040 max2 = max1;
1041 max1 = d;
1042 } else if ( d > max2 ) {
1043 max3 = max2;
1044 max2 = d;
1045 } else if ( d > max3 ) {
1046 max3 = d;
1047 }
1048 }
1049
1050
1051 /** Parallel edge joining algorithm.
1052 */
1053 public int parallelEdgePolygonReduction( float threshold ) {
1054 SpaceEntitySet vertices = getEntitySet( SpacePrimitive.Vertex );
1055 int numberVertices = vertices.getNumberEntities();
1056 GlobalProgressIndicator.activateAlternateProgressIndicator( 0 );
1057 GlobalProgressIndicator.setUnitSize( numberVertices*2, 3 );
1058 r5();
1059 r3();
1060 SpaceEntitySet edges = getEntitySet( SpacePrimitive.Edge );
1061 BitSet vertexCandidates = new BitSet( numberVertices );
1062 BitSet verticesRuledOut = new BitSet( numberVertices );
1063 Hashtable joinTo = new Hashtable();
1064 int count = 0;
1065 GlobalProgressIndicator.endGame( numberVertices );
1066 for ( int i = 0; i < numberVertices; i++ ) {
1067 GlobalProgressIndicator.markProgress();
1068 if ( !verticesRuledOut.get( i )) {
1069 if ( checkVertex( i, edges, vertices, verticesRuledOut, vertexCandidates, threshold, joinTo )) {
1070 count++;
1071 }
1072 }
1073 }
1074 GlobalProgressIndicator.deactivateAlternateProgressIndicator();
1075 return( count );
1076 }
1077
1078 /** Check all edges from a vertex, if two are parallel,
1079 * mark vertex as a candidate
1080 */
1081 float[] dxes;
1082 float[] dyes;
1083 float[] dzes;
1084 int[] vno;
1085 boolean checkVertex( int candidate, SpaceEntitySet edges, SpaceEntitySet vertices, BitSet verticesRuledOut, BitSet vertexCandidates, float threshold, Hashtable joinTo ) {
1086 SpacePrimitive v = vertices.getEntity( candidate );
1087 int numberEdges = vertices.getCount( v, SpacePrimitive.Edge );
1088
1089 // create a set of normalized vectors around each vertex
1090 if ( dxes == null ) {
1091 dxes = new float[ 10 ];
1092 dyes = new float[ 10 ];
1093 dzes = new float[ 10 ];
1094 vno = new int[10];
1095 }
1096 if ( numberEdges > 10 ) {
1097 numberEdges = 10;
1098 }
1099 for ( int i = 0; i < numberEdges; i++ ) {
1100 SpacePrimitive e = edges.getEntity( vertices.getValue( v, SpacePrimitive.Edge, i ));
1101 int v1no = edges.getValue( e, SpacePrimitive.Vertex, 0 );
1102 vno[i] = -1;
1103 if ( v1no != candidate ) {
1104 if ( !verticesRuledOut.get( v1no )) {
1105 SpacePrimitive v1 = vertices.getEntity( v1no );
1106 dxes[i] = v.getX() - v1.getX();
1107 dyes[i] = v.getY() - v1.getY();
1108 dzes[i] = v.getZ() - v1.getZ();
1109 vno[i] = v1no;
1110 }
1111 } else {
1112 v1no = edges.getValue( e, SpacePrimitive.Vertex, 1 );
1113 if ( v1no != candidate ) {
1114 if ( !verticesRuledOut.get( v1no )) {
1115 SpacePrimitive v1 = vertices.getEntity( v1no );
1116 dxes[i] = v.getX() - v1.getX();
1117 dyes[i] = v.getY() - v1.getY();
1118 dzes[i] = v.getZ() - v1.getZ();
1119 vno[i] = v1no;
1120 }
1121 }
1122 }
1123 }
1124 // check for parallel
1125 for ( int i = 0; i < numberEdges - 1; i++ ) {
1126 if ( vno[i] == -1 ) continue;
1127 dxes[i] *= -1;
1128 dyes[i] *= -1;
1129 dzes[i] *= -1;
1130 for ( int j = i + 1; j < numberEdges; j++ ) {
1131 if ( vno[j] == -1 ) continue;
1132 float diff = Math.abs( dxes[i] - dxes[j] ) +
1133 Math.abs( dyes[i] - dyes[j] ) + Math.abs( dzes[i] - dzes[j] );
1134 if ( diff < threshold ) {
1135 markCandidate( candidate, vno[i], vno[j], verticesRuledOut, vertexCandidates );
1136 SpacePrimitive vto = vertices.getEntity( vno[i] );
1137 // join by moving point to be identical, v in center
1138 v.setLocation( vto.getX(), vto.getY(), vto.getZ() );
1139 return( true );
1140 }
1141 }
1142 }
1143 return( false );
1144 }
1145
1146 void markCandidate( int candidate, int bro1, int bro2, BitSet verticesRuledOut, BitSet vertexCandidates ) {
1147 verticesRuledOut.set( bro1 );
1148 verticesRuledOut.set( bro2 );
1149 vertexCandidates.set( candidate );
1150 }
1151
1152
1153 /** Small triangle removal polygon reduction algorithm.
1154 *
1155 * @param minimumNumberFaces the smallest number of faces that have to
1156 * exist for this algorithm to occur
1157 * @param percentThreshold % of triangles to consider as removal
1158 * candidates
1159 * @param preserveColorBoundaries when true, edges between faces with
1160 * different colors are not affected by this algorithm.
1161 *
1162 * @return true if anything changed in the structure, otherwise false
1163 */
1164 public boolean smallTrianglePolygonReduction( int minimumNumberFaces, int percentThreshold, boolean preserveColorBoundaries ) {
1165 SpaceEntitySet vertices = getEntitySet( SpacePrimitive.Vertex );
1166 int numberVertices = vertices.getNumberEntities();
1167 GlobalProgressIndicator.activateAlternateProgressIndicator( 0 );
1168 GlobalProgressIndicator.setUnitSize( numberVertices*2, 5 );
1169 r5();
1170 r3();
1171 SpaceEntitySet faces = getEntitySet( SpacePrimitive.Face );
1172 SpaceEntitySet edges = getEntitySet( SpacePrimitive.Edge );
1173 int numberEdges = edges.getNumberEntities();
1174 int faceCount = faces.getNumberEntities();
1175 if ( faceCount > minimumNumberFaces ) {
1176 System.out.println( "Removing polygons, " + faceCount + " faces." );
1177 createFtoE( edges, faces, faceCount );
1178 float[] faceSize = new float[ faceCount ];
1179 int markedCount = 0;
1180 int numberToMark = faceCount * ( 100 - percentThreshold )/100;
1181 initMaxes();
1182 GlobalProgressIndicator.endGame( faceCount*3 + numberEdges );
1183 for ( int i = 0; i < faceCount; i++ ) {
1184 GlobalProgressIndicator.markProgress();
1185 SpacePrimitive face = faces.getEntity( i );
1186 int offsetIdx = faces.getCount( face, SpacePrimitive.Vertex );
1187 // keep all non-triangle faces
1188 if ( offsetIdx != 3 ) {
1189 faceSize[i] = -1;
1190 markedCount++;
1191 } else {
1192 SpacePrimitive v1 = faces.getEntity( face, SpacePrimitive.Vertex, 0 );
1193 SpacePrimitive v2 = faces.getEntity( face, SpacePrimitive.Vertex, 1 );
1194 SpacePrimitive v3 = faces.getEntity( face, SpacePrimitive.Vertex, 2 );
1195 // estimate face size by summing edge length
1196 float dx12 = v1.getX() - v2.getX();
1197 if ( dx12 < 0 ) dx12 = dx12*-1;
1198 float dx13 = v1.getX() - v3.getX();
1199 if