Source code: com/trapezium/attractor/AttractorReductionAlgorithm.java
1 /*
2 * @(#)AttractorReductionAlgorithm.java
3 *
4 * Copyright (c) 1998-1999 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.space.*;
14 import com.trapezium.vrml.node.space.BoundingBox;
15 import java.util.BitSet;
16 import java.util.Enumeration;
17 import java.util.Hashtable;
18
19 /** The attractor based polygon reduction algorithm.
20 *
21 * @author Johannes N. Johannsen
22 * @version 1.0, 7 Oct 1998
23 *
24 * @since 1.0
25 */
26
27 public class AttractorReductionAlgorithm {
28 // attractor fields
29 boolean attractorNeedsInit;
30 boolean attractorNeedsRescale;
31
32 SpaceStructure attractorSpaceStructure;
33 SpaceEntitySet attractorVertices;
34 int numberAttractorVertices;
35
36 SpaceStructure dualSpaceStructure;
37 SpaceEntitySet dualVertices;
38 int numberDualVertices;
39
40 // floater fields
41 boolean floaterNeedsInit;
42
43 SpaceStructure floaterSpaceStructure;
44 SpaceEntitySet floaterVertices;
45 int numberFloaterVertices;
46
47 // bitmap of the floater coordinates that remain after the algorithm
48 // has completed.
49 BitSet preservedFloaterVertices;
50
51 // generator fields
52 CoordAttractor nearCoords;
53 CoordAttractor farCoords;
54
55 // the magical reduced result
56 SpaceEntitySet magicCoords;
57 CoordAttractor magicAttractor; // may not be necessary...
58
59 // mapping from the magic coords to their original coordinate offsets
60 // offset = new coordinate offset, value = original coordinate offset
61 int[] newToOldMapping;
62
63 /** Class constructor */
64 public AttractorReductionAlgorithm() {
65 }
66
67 /** Get the new coordinate results */
68 public SpaceEntitySet getNewCoords() {
69 return( magicCoords );
70 }
71
72 /** Get mapping between magic coords and original offsets */
73 public int[] getNewToOldMapping() {
74 return( newToOldMapping );
75 }
76
77 /** Get the BitSet indicating which original coordinates are preserved */
78 public BitSet getPreservedFloaters() {
79 return( preservedFloaterVertices );
80 }
81
82 /** The attractor reduction algorithm requires one SpaceStructure
83 * to function as the attractor, and one SpaceStructure to be reduced
84 * (called the floater). This method sets the attractor.
85 *
86 * @param attractor the SpaceStructure to use as the attractor
87 */
88 public void setAttractor( SpaceStructure attractor ) {
89 if ( attractorSpaceStructure != attractor ) {
90 attractorSpaceStructure = attractor;
91 attractorNeedsInit = true;
92 attractorNeedsRescale = true;
93 }
94 }
95
96 /** The attractor reduction algorithm requires one SpaceStructure
97 * to function as the attractor, and one SpaceStructure to be reduced
98 * (called the floater). This method sets the floater.
99 *
100 * @param floater the SpaceStructure to use as the floater
101 */
102 public void setOriginal( SpaceStructure floater ) {
103 if ( floaterSpaceStructure != floater ) {
104 floaterSpaceStructure = floater;
105 floaterNeedsInit = true;
106 attractorNeedsRescale = true;
107 }
108 }
109
110 /** Get the original SpaceStructure */
111 public SpaceStructure getOriginal() {
112 return( floaterSpaceStructure );
113 }
114
115 /** The main algorithm, requires the attractor and floater already
116 * be set by setAttractor and setOriginal. If these are not set
117 * the algorithm does nothing.
118 */
119 public void reduce() {
120 if (( attractorSpaceStructure != null ) &&
121 ( floaterSpaceStructure != null )) {
122 initAttractorFields();
123 initFloaterFields();
124 rescaleAttractor();
125 createMagicCoords();
126 }
127 }
128
129 /** Enumerate structures which can be used to generate coordIndex of
130 * the reduced face set.
131 */
132 public Enumeration enumerateFaces() {
133 return( new FaceGenEnumerator( attractorSpaceStructure, nearCoords, farCoords ));
134 }
135
136 /** Get the reduced vertices, which is really the original floater set.
137 * We rely on the cleaners to detect the duplicates and unused ones.
138 */
139 public SpaceEntitySet getFloaterVertices() {
140 return( floaterVertices );
141 }
142
143 /** Utility methods for the algorithm */
144
145 /** Extracts and generates all the attractor based fields required by
146 * the algorithm. These fields are just the attractor and dual
147 * vertices.
148 */
149 void initAttractorFields() {
150 if ( attractorNeedsInit ) {
151 attractorNeedsInit = false;
152 dualSpaceStructure = new SpaceStructure( attractorSpaceStructure );
153 dualSpaceStructure.r2();
154 attractorVertices = attractorSpaceStructure.getVertices();
155 numberAttractorVertices = attractorVertices.getNumberEntities();
156 dualVertices = dualSpaceStructure.getVertices();
157 numberDualVertices = dualVertices.getNumberEntities();
158 }
159 }
160
161 /** initialize all the fields associated with the floater */
162 void initFloaterFields() {
163 if ( floaterNeedsInit ) {
164 floaterNeedsInit = false;
165 floaterVertices = floaterSpaceStructure.getVertices();
166 numberFloaterVertices = floaterVertices.getNumberEntities();
167 preservedFloaterVertices = new BitSet( numberFloaterVertices );
168 }
169 }
170
171 /** rescale the attractor so its bounding box is same as floater */
172 void rescaleAttractor() {
173 if ( attractorNeedsRescale ) {
174 attractorNeedsRescale = false;
175 EntitySetScaler attractorScaler = new EntitySetScaler(
176 attractorVertices );
177 EntitySetScaler dualScaler = new EntitySetScaler( dualVertices );
178 BoundingBox floaterBounds = floaterSpaceStructure.getBoundingBox();
179 attractorScaler.scaleTo( floaterBounds );
180 dualScaler.scaleTo( floaterBounds );
181 }
182 }
183
184 /** Create the set of coordinates in the floater that all other coordinates
185 * map to during the reduction.
186 */
187 void createMagicCoords() {
188 // Create the attractor objects for attracting nearest and farthest
189 // coordinates in each subset of coordinates, perform the attraction
190 // operation, keeping result in "preservedFloaterVertices" BitSet
191 nearCoords = new NearPreservingCoordAttractor( attractorVertices );
192 farCoords = new FarPreservingCoordAttractor( dualVertices );
193 nearCoords.attract( floaterVertices, preservedFloaterVertices );
194 farCoords.attract( floaterVertices, preservedFloaterVertices );
195
196 // create the set of coords that get preserved, then attract to them
197 // so that the location of the attracted set can be set to their
198 // corresponding preserved location.
199 magicCoords = new Vertices();
200 newToOldMapping = new int[ preservedFloaterVertices.size() ];
201 float[] preservedCoord = new float[3];
202 int newOffset = 0;
203 for ( int i = 0; i < numberFloaterVertices; i++ ) {
204 if ( preservedFloaterVertices.get( i )) {
205 floaterVertices.getLocation( i, preservedCoord );
206 newToOldMapping[ newOffset++ ] = i;
207 magicCoords.add3f( preservedCoord );
208 }
209 }
210
211 magicAttractor = new CoordAttractor( magicCoords );
212 magicAttractor.attract( floaterVertices );
213
214 // To be removed, only for reference until functionality is moved elsewhere
215 // set the location of each floater vertex to be identical to the
216 // magic coordinate it was attracted to
217 /* for ( int i = 0; i < numberFloaterVertices; i++ ) {
218 int nearest = magicAttractor.getAttractorOffset( i );
219 SpaceEntity magic = magicCoords.getEntity( nearest );
220 SpaceEntity floater = floaterVertices.getEntity( i );
221 floater.setLocation( magic.x, magic.y, magic.z );*/
222 // set the texture, color, normal as well...
223 // requires these to be stored in SpacePrimitive
224 // }
225 }
226 }
227