Source code: com/trapezium/attractor/AttractorPolygonReduction.java
1 /*
2 * @(#)AttractorPolygonReduction.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.attractor;
12
13 import com.trapezium.chisel.*;
14 import com.trapezium.vrml.Scene;
15 import com.trapezium.vrml.node.Node;
16 import com.trapezium.vrml.fields.Field;
17 import com.trapezium.space.*;
18 import com.trapezium.vrmlspace.*;
19 import com.trapezium.parse.TokenTypes;
20
21 import java.util.Enumeration;
22 import java.util.Hashtable;
23
24 /** Abstract base class for all attractor reduction chisels.
25 *
26 * Attractor polygon reduction chisels use one IFS (the attractor) to reduce
27 * a second IFS (the floater). It does this by warping the first IFS
28 * onto the second. The result has the same basic polygon count as the first
29 * IFS, but the same shape as the second IFS.
30 *
31 * Actually, the resulting polygon count is the same as triangulating all
32 * faces of the attractor IFS by placing a vertex in the center of the
33 * face and connecting it to the surrounding vertices.
34 *
35 * The reduction takes place in two phases.
36 *
37 * First, the floater IFS is partitioned into sets of coordinates. Each
38 * coordinate in a set is closest to a particular attractor coordinate
39 * than to any other attractor coordinate. Within each of these sets,
40 * the coordinate nearest to the attractor is marked for preservation.
41 *
42 * Next, the dual of the attractor is created, and the coordinate sets
43 * calculated again. Within each of these sets, the coordinate farthest
44 * from the attractor is marked for preservation.
45 *
46 * The set of floater coordinates to be preserved are then merged into
47 * a single triangulated structure, with (V+F) vertices and 2*E triangle
48 * faces, where V,E,F are the number of vertices, edges, and faces in
49 * the attractor.
50 *
51 * Subclasses select specific attractors.
52 *
53 * Options: minimum number of vertices required in the floater
54 * preserve color boundaries
55 * preserve edge boundaries
56 *
57 * @author Johannes N. Johannsen
58 * @version 1.0, 7 Oct 1998
59 *
60 * @since 1.0
61 */
62
63 abstract public class AttractorPolygonReduction extends Optimizer implements IFS, SpaceCorrespondenceConstants {
64 // Option 0 - minimum number of vertices required in floater
65 // Option 1 - preserve color boundaries
66 // Option 2 - preserve edge boundaries
67 static public final int MIN_FLOATER_VERTICES = 0;
68 static public final int PRESERVE_COLOR_BOUNDARIES = 1;
69 static public final int PRESERVE_EDGE_BOUNDARIES = 2;
70
71 // option 0, actual value
72 int minFloaterVertices;
73 // option 1, actual value
74 boolean preserveColorBoundaries;
75 // option 2, actual value
76 boolean preserveEdgeBoundaries;
77
78 // keeps track of SpaceStructures available to the algorithm
79 protected SpaceStructureLoader spaceStructureLoader;
80
81 /** ReducerState is an internal class, tracks whether or not the
82 * reduction algorithm has taken place, since it can't actually occur
83 * until optimize time (due to DEF/USE of Coordinate nodes)
84 */
85 class ReducerState {
86 AttractorReductionAlgorithm theAlgorithm;
87 boolean reduced;
88
89 ReducerState( AttractorReductionAlgorithm theAlgorithm ) {
90 this.theAlgorithm = theAlgorithm;
91 reduced = false;
92 }
93
94 /** Apply the reduction algorithm if it hasn't yet been applied */
95 void reduce() {
96 if ( !reduced ) {
97 reduced = true;
98 theAlgorithm.reduce();
99 }
100 }
101
102 AttractorReductionAlgorithm getAlgorithm() {
103 return( theAlgorithm );
104 }
105 }
106
107 /** The actual parameter passed to the optimize method, uses the
108 * ReducerState above to track whether or not the reduction algorithm
109 * has occurred since it has to happen at optimize time due to DEF/USE
110 * of coordinate nodes.
111 */
112 class AttractorParam {
113 /** The IFS field type being replaced */
114 int type;
115
116 /** IFS.OnePerCoord, IFS.OnePerCoordIndex, IFS.OnePerFace -- how the
117 * texture, color, normal field corresponds to others in the IFS
118 */
119 int correspondenceType;
120
121 /** used to execute the algorithm */
122 ReducerState reducer;
123
124 /** Class constructor.
125 *
126 * @param reducer handles one-time-only reduction algorithm running
127 * @param type type of IFS field being affected.
128 */
129 AttractorParam( ReducerState reducer, int type ) {
130 this( reducer, type, -1 );
131 }
132
133 /** Class constructor.
134 *
135 * @param reducer handles one-time-only reduction algorithm running
136 * @param type type of IFS field being affected
137 * @param correspondenceType indicates the type of correpondence
138 * between the values being replaced and the coord/coordIndex
139 * fields of the IFS. Possible values are: IFS.OnePerCoord,
140 * IFS.OnePerFace, and IFS.OnePerCoordIndex. The value is -1
141 * and ignored if this is for the coord or coordIndex fields.
142 */
143 AttractorParam( ReducerState reducer, int type, int correspondenceType ) {
144 this.reducer = reducer;
145 this.type = type;
146 this.correspondenceType = correspondenceType;
147 }
148
149 /** Get the correspondence type for this parameter */
150 int getCorrespondenceIndicator() {
151 return( correspondenceType );
152 }
153
154 /** Execute the polygon reduction algorithm */
155 void reduce() {
156 reducer.reduce();
157 }
158
159 /** Get the type of field being replaced, one of the IFS.* values */
160 int getReplacementType() {
161 return( type );
162 }
163
164 AttractorReductionAlgorithm getAlgorithm() {
165 return( reducer.getAlgorithm() );
166 }
167
168 SpaceStructure getOriginalSpaceStructure() {
169 return( reducer.getAlgorithm().getOriginal() );
170 }
171 }
172
173 /** Class constructor */
174 public AttractorPolygonReduction( String reductionDescription ) {
175 super( "IndexedFaceSet", reductionDescription );
176 reset();
177 }
178
179 /** subclasses override this to provide specific attractors */
180 abstract public SpaceStructure generateAttractor();
181
182 /** subclasses override this if they have additional options */
183 public int getNumberOptions() {
184 return( 3 );
185 }
186
187 /** Get the class for an option */
188 public Class getOptionClass( int optionOffset ) {
189 Class c;
190 try {
191 if ( optionOffset == MIN_FLOATER_VERTICES ) {
192 c = Integer.TYPE;
193 } else {
194 c = Boolean.TYPE;
195 }
196 } catch (Exception e) {
197 c = null;
198 }
199 return c;
200 }
201
202 public String getOptionLabel( int offset ) {
203 switch( offset ) {
204 case MIN_FLOATER_VERTICES:
205 return( "Minimum coordinate count" );
206 case PRESERVE_COLOR_BOUNDARIES:
207 return( "Preserve color boundaries" );
208 case PRESERVE_EDGE_BOUNDARIES:
209 return( "Preserve edge boundaries" );
210 default:
211 return( "** unknown **" );
212 }
213 }
214
215 public Object getOptionValue( int offset ) {
216 switch( offset ) {
217 case MIN_FLOATER_VERTICES:
218 return( intToOptionValue(minFloaterVertices) );
219 case PRESERVE_COLOR_BOUNDARIES:
220 return( booleanToOptionValue(preserveColorBoundaries) );
221 case PRESERVE_EDGE_BOUNDARIES:
222 return( booleanToOptionValue(preserveEdgeBoundaries) );
223 default:
224 return( null );
225 }
226 }
227
228 public void setOptionValue( int offset, Object value ) {
229 switch( offset ) {
230 case MIN_FLOATER_VERTICES:
231 minFloaterVertices = optionValueToInt(value);
232 break;
233 case PRESERVE_COLOR_BOUNDARIES:
234 preserveColorBoundaries = optionValueToBoolean(value);
235 break;
236 case PRESERVE_EDGE_BOUNDARIES:
237 preserveEdgeBoundaries = optionValueToBoolean(value);
238 break;
239 default:
240 break;
241 }
242 }
243
244 public Object getOptionConstraints( int offset ) {
245 switch (offset) {
246 case MIN_FLOATER_VERTICES:
247 return( new IntegerConstraints(25, 5000, 25 ));
248 }
249 return "";
250 }
251
252 /** reset the Chisel */
253 public void reset() {
254 spaceStructureLoader = new SpaceStructureLoader();
255 }
256
257 /** Attempt optimization by creating a SpaceStructure for the node,
258 * then if optimization is possible, register the node for optimization.
259 */
260 public void attemptOptimization( Node n ) {
261 setDataSource( n );
262 SpaceStructure nSpace = spaceStructureLoader.loadSpaceStructure( n );
263 if ( optimizationOK( nSpace, n )) {
264 registerOptimization( nSpace, n );
265 }
266 }
267
268
269 /** Optimize a node.
270 *
271 * @param tp text printing destination
272 * @param param object used for optimization
273 * @param startTokenOffset first token offset in area being regenerated
274 * @param endTokenOffset last token offset in area being regenerated
275 */
276 public void optimize( TokenPrinter tp, Object param,
277 int startTokenOffset, int endTokenOffset ) {
278 if ( param instanceof AttractorParam ) {
279 AttractorParam ap = (AttractorParam)param;
280 ap.reduce();
281 int replacementType = ap.getReplacementType();
282 int correspondenceIndicator = ap.getCorrespondenceIndicator();
283 AttractorReductionAlgorithm theAlgorithm = ap.getAlgorithm();
284 SpaceEntitySet newCoords = theAlgorithm.getNewCoords();
285 int numberNewCoords = newCoords.getNumberEntities();
286 if ( replacementType == IFS.Coord ) {
287 replaceCoord( tp, theAlgorithm.getNewCoords() );
288 } else if ( replacementType == IFS.CoordIndex ) {
289 replaceCoordIndex( tp, theAlgorithm.enumerateFaces() );
290 } else if ( replacementType == IFS.TexCoord ) {
291 replaceTexCoord( tp, numberNewCoords,
292 theAlgorithm.getNewToOldMapping(), theAlgorithm.getOriginal(),
293 startTokenOffset, endTokenOffset );
294 } else if ( replacementType == IFS.TexCoordIndex ) {
295 replaceTexCoordIndex( tp, theAlgorithm.enumerateFaces(),
296 theAlgorithm.getOriginal(),
297 theAlgorithm.getNewToOldMapping() );
298 } else if ( replacementType == IFS.Color ) {
299 SpaceStructure original = theAlgorithm.getOriginal();
300 SpaceEntitySet color = original.getColor();
301 if ( color.getCorrespondenceType() == CorrespondsToV ) {
302 replaceUsingV( tp, numberNewCoords, theAlgorithm.getNewToOldMapping(),
303 original.getColor(), startTokenOffset, endTokenOffset );
304 } else {
305 replaceUsingF( tp, theAlgorithm.getNewToOldMapping(),
306 original.getFaces(), original.getColor(),
307 startTokenOffset, endTokenOffset );
308 }
309 } else if ( replacementType == IFS.ColorIndex ) {
310 SpaceStructure original = theAlgorithm.getOriginal();
311 SpaceEntitySet colorIndex = original.getColorIndex();
312 // if ( colorIndex.getCorrespondenceType() == CorrespondsToV ) {
313 // replaceColorIndex( tp,
314 // } else {
315 // replaceColorIndex( tp,
316 // }
317 } else if ( replacementType == IFS.Normal ) {
318 SpaceStructure original = theAlgorithm.getOriginal();
319 SpaceEntitySet normal = original.getNormal();
320 if ( normal.getCorrespondenceType() == CorrespondsToV ) {
321 replaceUsingV( tp, numberNewCoords, theAlgorithm.getNewToOldMapping(),
322 original.getNormal(), startTokenOffset, endTokenOffset );
323 } else {
324 replaceUsingF( tp, theAlgorithm.getNewToOldMapping(),
325 original.getFaces(), original.getNormal(),
326 startTokenOffset, endTokenOffset );
327 }
328 } else if ( replacementType == IFS.NormalIndex ) {
329 SpaceStructure original = theAlgorithm.getOriginal();
330 SpaceEntitySet normalIndex = original.getNormalIndex();
331 // if ( normalIndex.getCorrespondenceType() == CorrespondsToV ) {
332 // replaceNormalIndex( tp,
333 // } else {
334 // replaceNormalIndex( tp,
335 // }
336 }
337 }
338 }
339
340 // set dataSource if it isn't set
341 void setDataSource( Node n ) {
342 if ( dataSource == null ) {
343 Scene s = (Scene)n.getRoot();
344 dataSource = s.getTokenEnumerator();
345 }
346 }
347
348 /** Check if optimization is allowed according to the user configurable
349 * guidelines. The return value is based on whether the SpaceStructure
350 * exists and meets the minimum number of vertices requirement set by
351 * the user.
352 *
353 * @param nSpace the SpaceStructure to check for possible optimization
354 * @param n the corresponding Node (parameter not used)
355 *
356 * @return true if the SpaceStructure should be optimized, otherwise false.
357 */
358 public boolean optimizationOK( SpaceStructure nSpace, Node n ) {
359 if ( nSpace == null ) {
360 return( false );
361 }
362 SpaceEntitySet v = nSpace.getVertices();
363 if ( v == null ) {
364 return( false );
365 }
366 return( v.getNumberEntities() >= minFloaterVertices );
367 }
368
369
370 /** Register the "coord" and "coordIndex" section of the Node for
371 * replacement by this chisel. This is only done if those fields exist
372 * and the chisel successfully created an attractor SpaceStructure.
373 *
374 * @param nSpace the floater SpaceStructure to be reduced
375 * @param n the Node corresponding to the floater SpaceStructure
376 */
377 void registerOptimization( SpaceStructure nSpace, Node n ) {
378 Node coord = n.getNodeValue( "coord" );
379 Field coordIndex = n.getField( "coordIndex" );
380 SpaceStructure attractor = generateAttractor();
381 if (( coord != null ) && ( coordIndex != null ) &&
382 ( attractor != null )) {
383 AttractorReductionAlgorithm alg = new AttractorReductionAlgorithm();
384 alg.setOriginal( nSpace );
385 alg.setAttractor( attractor );
386
387 ReducerState rc = new ReducerState( alg );
388 AttractorParam coordParam = new AttractorParam( rc, IFS.Coord );
389 AttractorParam coordIndexParam = new AttractorParam( rc, IFS.CoordIndex );
390 replaceRange( coord.getFirstTokenOffset(),
391 coord.getLastTokenOffset(), coordParam );
392 replaceRange( coordIndex.getFirstTokenOffset(),
393 coordIndex.getLastTokenOffset(), coordIndexParam );
394
395 if ( nSpace.replaceTexCoord() ) {
396 Field texCoord = n.getField( "texCoord" );
397 replaceRange( texCoord.getFirstTokenOffset(), texCoord.getLastTokenOffset(),
398 new AttractorParam( rc, IFS.TexCoord ));
399 }
400 if ( nSpace.replaceTexCoordIndex() ) {
401 Field texCoordIndex = n.getField( "texCoordIndex" );
402 replaceRange( texCoordIndex.getFirstTokenOffset(),
403 texCoordIndex.getLastTokenOffset(),
404 new AttractorParam( rc, IFS.TexCoordIndex ));
405 }
406 if ( nSpace.replaceColor() ) {
407 Field color = n.getField( "color" );
408 replaceRange( color.getFirstTokenOffset(), color.getLastTokenOffset(),
409 new AttractorParam( rc, IFS.Color ));
410 }
411 if ( nSpace.replaceColorIndex() ) {
412 Field colorIndex = n.getField( "colorIndex" );
413 replaceRange( colorIndex.getFirstTokenOffset(), colorIndex.getLastTokenOffset(),
414 new AttractorParam( rc, IFS.ColorIndex ));
415 }
416 if ( nSpace.replaceNormal() ) {
417 Field normal = n.getField( "normal" );
418 replaceRange( normal.getFirstTokenOffset(), normal.getLastTokenOffset(),
419 new AttractorParam( rc, IFS.Normal ));
420 }
421 if ( nSpace.replaceNormalIndex() ) {
422 Field normalIndex = n.getField( "normalIndex" );
423 replaceRange( normalIndex.getFirstTokenOffset(), normalIndex.getLastTokenOffset(),
424 new AttractorParam( rc, IFS.NormalIndex ));
425 }
426 }
427 }
428
429
430 /** Regenerate the text for the coordinates, based on the locations
431 * provided by the SpaceEntitySet, which has by this time been modified
432 * by the reduction algorithm.
433 */
434 void replaceCoord( TokenPrinter tp, SpaceEntitySet vertices ) {
435 tp.printTo( TokenTypes.LeftBracket );
436 int numberV = vertices.getNumberEntities();
437 float[] v = new float[3];
438 for ( int i = 0; i < numberV; i++ ) {
439 vertices.getLocation( i, v );
440 tp.print3f( v );
441 }
442 tp.skipTo( TokenTypes.RightBracket );
443 tp.printTo( TokenTypes.RightBrace );
444 }
445
446 /** Regenerate the text for the faces.
447 *
448 * @param tp text print destination
449 * @param faces enumeration of all regenerated faces
450 */
451 void replaceCoordIndex( TokenPrinter tp, Enumeration faces ) {
452 if ( faces != null ) {
453 tp.printTo( TokenTypes.LeftBracket );
454 while ( faces.hasMoreElements() ) {
455 FaceGenerator fg = (FaceGenerator)faces.nextElement();
456 int numFaces = fg.getNumberFaces();
457 int[] face = new int[3];
458 for ( int i = 0; i < numFaces; i++ ) {
459 if ( fg.getFace( i, face )) {
460 tp.print3i( face );
461 tp.print( -1 );
462 }
463 }
464 }
465 tp.skipTo( TokenTypes.RightBracket );
466 tp.printTo( TokenTypes.RightBracket );
467 }
468 }
469
470 /** Regenerate the text for the texCoordIndex field.
471 *
472 * @param tp text print destination
473 * @param faces enumeration of all regenerated faces
474 */
475 void replaceTexCoordIndex( TokenPrinter tp, Enumeration faces,
476 SpaceStructure originalSpaceStructure, int[] newToOldMapping ) {
477 if ( faces != null ) {
478 tp.printTo( TokenTypes.LeftBracket );
479 while ( faces.hasMoreElements() ) {
480 FaceGenerator fg = (FaceGenerator)faces.nextElement();
481 int numFaces = fg.getNumberFaces();
482 int[] face = new int[3];
483 for ( int i = 0; i < numFaces; i++ ) {
484 if ( fg.getFace( i, face )) {
485 printTexCoordIndex( tp, face, originalSpaceStructure, newToOldMapping );
486 }
487 }
488 }
489 tp.skipTo( TokenTypes.RightBracket );
490 tp.printTo( TokenTypes.RightBracket );
491 }
492 }
493
494 /** Print the texCoordIndex values for a regenerated face.
495 * In this case, the texCoord field has not changed, so the
496 * new face coordIndex values have to be mapped into old face
497 * texCoordIndex values.
498 */
499 void printTexCoordIndex( TokenPrinter tp, int[] face, SpaceStructure original,
500 int[] newToOldMapping ) {
501 // the face index is the resulting magic coord, from this we get
502 // the original floater coord
503 for ( int i = 0; i < 3; i++ ) {
504 // get the offset of the original coord
505 int originalOffset = newToOldMapping[ face[i] ];
506 // get any offset into the original coordIndex for that coord, since
507 // the texCoordIndex has to correspond one-for-one with that coordIndex
508 int coordIndexOffset = original.getCoordIndexOffset( originalOffset );
509 // get and print the texCoordIndex value from the original at that
510 // offset, this is OK because the texCoord is not changed when this
511 // method is called, so references to the original texCoord are valid
512 tp.print( original.getTexCoordIndexValue( coordIndexOffset ));
513 }
514 tp.print( -1 );
515 }
516
517 /** Regenerate the text for the "texCoord" field, this is always
518 * one-to-one with original coords.
519 *
520 * @param tp print destination
521 * @param numberNewCoords the number of new coordinates which need corresponding texCoords
522 * @param newToOldMapping the mapping from the magic coords to the originals
523 * @param startTokenOffset first in sequence of tokens to replace
524 * @param endTokenOffset last in sequence of tokens to replace
525 */
526 void replaceTexCoord( TokenPrinter tp, int numberNewCoords,
527 int[] newToOldMapping, SpaceStructure original,
528 int startTokenOffset, int endTokenOffset ) {
529 // print up to the first number
530 tp.limitRange( startTokenOffset, endTokenOffset );
531 tp.printTo( TokenTypes.NumberToken );
532
533 // for each preserved coord, get and print the corresponding texCoord
534 // the magic mapping gives me an offset of the original preserved
535 // coordinate, in order?
536 float tc[] = new float[2];
537 for ( int i = 0; i < numberNewCoords; i++ ) {
538 int originalOffset = newToOldMapping[i];
539 original.getTexCoord( originalOffset, tc );
540 tp.print( tc[0] );
541 tp.print( tc[1] );
542 }
543 tp.skipTo( TokenTypes.RightBracket );
544 tp.print( "] }" );
545 }
546
547 /** replace the "color" field.
548 *
549 * If we are replacing the color field, it means there is no index field,
550 * in this case, the color field either corresponds to the Vertices, or
551 * corresponds to the Faces (depends on "colorPerVertex")
552 */
553
554 /** This version replaces a "color" field where each entry corresponds to a coordinate
555 *
556 * @param tp print destination
557 * @param numberNewCoords number of new coordinates
558 */
559 void replaceUsingV( TokenPrinter tp, int numberNewCoords, int[] newToOldMapping,
560 SpaceEntitySet original, int startTokenOffset, int endTokenOffset ) {
561 // print up to the first number
562 tp.limitRange( startTokenOffset, endTokenOffset );
563 tp.printTo( TokenTypes.NumberToken );
564 float tc[] = new float[3];
565 for ( int i = 0; i < numberNewCoords; i++ ) {
566 int originalOffset = newToOldMapping[i];
567 original.getLocation( originalOffset, tc );
568 tp.print( tc[0] );
569 tp.print( tc[1] );
570 tp.print( tc[2] );
571 }
572 tp.skipTo( TokenTypes.RightBracket );
573 tp.print( "] }" );
574 }
575
576 /** Replace values that originally corresponded to faces.
577 *
578 * @param tp print destination
579 * @param newToOldMapping mapping form new coordinates to old
580 * @param faces original faces
581 * @param colors original colors
582 * @param startTokenOffset first of sequence being regenerated
583 * @param endTokenOffset last of sequence being regenerated
584 */
585 void replaceUsingF( TokenPrinter tp, int[] newToOldMapping,
586 SpaceEntitySet faces, SpaceEntitySet colors,
587 int startTokenOffset, int endTokenOffset ) {
588
589 }
590 }
591
592