1 /* 2 * Copyright (c) 2003-2009 jMonkeyEngine 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 package jme3tools.converters.model.strip; 34 35 import java.util.Arrays; 36 37 /** 38 * To use, call generateStrips method, passing your triangle index list and 39 * then construct geometry/render resulting PrimitiveGroup objects. 40 * Features: 41 * <ul> 42 * <li>generates strips from arbitrary geometry. 43 * <li>flexibly optimizes for post TnL vertex caches (16 on GeForce1/2, 24 on GeForce3). 44 * <li>can stitch together strips using degenerate triangles, or not. 45 * <li>can output lists instead of strips. 46 * <li>can optionally throw excessively small strips into a list instead. 47 * <li>can remap indices to improve spatial locality in your vertex buffers. 48 * </ul> 49 * On cache sizes: Note that it's better to UNDERESTIMATE the cache size 50 * instead of OVERESTIMATING. So, if you're targetting GeForce1, 2, and 3, be 51 * conservative and use the GeForce1_2 cache size, NOT the GeForce3 cache size. 52 * This will make sure you don't "blow" the cache of the GeForce1 and 2. Also 53 * note that the cache size you specify is the "actual" cache size, not the 54 * "effective" cache size you may have heard about. This is 16 for GeForce1 and 2, 55 * and 24 for GeForce3. 56 * 57 * Credit goes to Curtis Beeson and Joe Demers for the basis for this 58 * stripifier and to Jason Regier and Jon Stone at Blizzard for providing a 59 * much cleaner version of CreateStrips(). 60 * 61 * Ported to java by Artur Biesiadowski <abies (at) pg.gda.pl> 62 */ 63 public class TriStrip { 64 65 public static final int CACHESIZE_GEFORCE1_2 = 16; 66 public static final int CACHESIZE_GEFORCE3 = 24; 67 68 int cacheSize = CACHESIZE_GEFORCE1_2; 69 boolean bStitchStrips = true; 70 int minStripSize = 0; 71 boolean bListsOnly = false; 72 73 /** 74 * 75 */ 76 public TriStrip() { 77 super(); 78 } 79 80 /** 81 * If set to true, will return an optimized list, with no strips at all. 82 * Default value: false 83 */ 84 public void setListsOnly(boolean _bListsOnly) { 85 bListsOnly = _bListsOnly; 86 } 87 88 /** 89 * Sets the cache size which the stripfier uses to optimize the data. 90 * Controls the length of the generated individual strips. This is the 91 * "actual" cache size, so 24 for GeForce3 and 16 for GeForce1/2 You may 92 * want to play around with this number to tweak performance. Default 93 * value: 16 94 */ 95 public void setCacheSize(int _cacheSize) { 96 cacheSize = _cacheSize; 97 } 98 99 /** 100 * bool to indicate whether to stitch together strips into one huge strip 101 * or not. If set to true, you'll get back one huge strip stitched together 102 * using degenerate triangles. If set to false, you'll get back a large 103 * number of separate strips. Default value: true 104 */ 105 public void setStitchStrips(boolean _bStitchStrips) { 106 bStitchStrips = _bStitchStrips; 107 } 108 109 /** 110 * Sets the minimum acceptable size for a strip, in triangles. All strips 111 * generated which are shorter than this will be thrown into one big, 112 * separate list. Default value: 0 113 */ 114 public void setMinStripSize(int _minStripSize) { 115 minStripSize = _minStripSize; 116 } 117 118 /** 119 * @param in_indices 120 * input index list, the indices you would use to render 121 * @return array of optimized/stripified PrimitiveGroups 122 */ 123 public PrimitiveGroup[] generateStrips(int[] in_indices) { 124 int numGroups = 0; 125 PrimitiveGroup[] primGroups; 126 //put data in format that the stripifier likes 127 IntVec tempIndices = new IntVec(); 128 int maxIndex = 0; 129 130 for (int i = 0; i < in_indices.length; i++) { 131 tempIndices.add(in_indices[i]); 132 if (in_indices[i] > maxIndex) 133 maxIndex = in_indices[i]; 134 } 135 136 StripInfoVec tempStrips = new StripInfoVec(); 137 FaceInfoVec tempFaces = new FaceInfoVec(); 138 139 Stripifier stripifier = new Stripifier(); 140 141 //do actual stripification 142 stripifier.stripify(tempIndices, cacheSize, minStripSize, maxIndex, tempStrips, tempFaces); 143 144 //stitch strips together 145 IntVec stripIndices = new IntVec(); 146 int numSeparateStrips = 0; 147 148 if (bListsOnly) { 149 //if we're outputting only lists, we're done 150 numGroups = 1; 151 primGroups = new PrimitiveGroup[numGroups]; 152 primGroups[0] = new PrimitiveGroup(); 153 PrimitiveGroup[] primGroupArray = primGroups; 154 155 //count the total number of indices 156 int numIndices = 0; 157 for (int i = 0; i < tempStrips.size(); i++) { 158 numIndices += tempStrips.at(i).m_faces.size() * 3; 159 } 160 161 //add in the list 162 numIndices += tempFaces.size() * 3; 163 164 primGroupArray[0].type = PrimitiveGroup.PT_LIST; 165 primGroupArray[0].indices = new int[numIndices]; 166 primGroupArray[0].numIndices = numIndices; 167 168 //do strips 169 int indexCtr = 0; 170 for (int i = 0; i < tempStrips.size(); i++) { 171 for (int j = 0; j < tempStrips.at(i).m_faces.size(); j++) { 172 //degenerates are of no use with lists 173 if (!Stripifier.isDegenerate(tempStrips.at(i).m_faces.at(j))) { 174 primGroupArray[0].indices[indexCtr++] = tempStrips.at(i).m_faces.at(j).m_v0; 175 primGroupArray[0].indices[indexCtr++] = tempStrips.at(i).m_faces.at(j).m_v1; 176 primGroupArray[0].indices[indexCtr++] = tempStrips.at(i).m_faces.at(j).m_v2; 177 } else { 178 //we've removed a tri, reduce the number of indices 179 primGroupArray[0].numIndices -= 3; 180 } 181 } 182 } 183 184 //do lists 185 for (int i = 0; i < tempFaces.size(); i++) { 186 primGroupArray[0].indices[indexCtr++] = tempFaces.at(i).m_v0; 187 primGroupArray[0].indices[indexCtr++] = tempFaces.at(i).m_v1; 188 primGroupArray[0].indices[indexCtr++] = tempFaces.at(i).m_v2; 189 } 190 } else { 191 numSeparateStrips = stripifier.createStrips(tempStrips, stripIndices, bStitchStrips); 192 193 //if we're stitching strips together, we better get back only one 194 // strip from CreateStrips() 195 196 //convert to output format 197 numGroups = numSeparateStrips; //for the strips 198 if (tempFaces.size() != 0) 199 numGroups++; //we've got a list as well, increment 200 primGroups = new PrimitiveGroup[numGroups]; 201 for (int i = 0; i < primGroups.length; i++) { 202 primGroups[i] = new PrimitiveGroup(); 203 } 204 205 PrimitiveGroup[] primGroupArray = primGroups; 206 207 //first, the strips 208 int startingLoc = 0; 209 for (int stripCtr = 0; stripCtr < numSeparateStrips; stripCtr++) { 210 int stripLength = 0; 211 212 if (!bStitchStrips) { 213 int i; 214 //if we've got multiple strips, we need to figure out the 215 // correct length 216 for (i = startingLoc; i < stripIndices.size(); i++) { 217 if (stripIndices.get(i) == -1) 218 break; 219 } 220 221 stripLength = i - startingLoc; 222 } else 223 stripLength = stripIndices.size(); 224 225 primGroupArray[stripCtr].type = PrimitiveGroup.PT_STRIP; 226 primGroupArray[stripCtr].indices = new int[stripLength]; 227 primGroupArray[stripCtr].numIndices = stripLength; 228 229 int indexCtr = 0; 230 for (int i = startingLoc; i < stripLength + startingLoc; i++) 231 primGroupArray[stripCtr].indices[indexCtr++] = stripIndices.get(i); 232 233 //we add 1 to account for the -1 separating strips 234 //this doesn't break the stitched case since we'll exit the 235 // loop 236 startingLoc += stripLength + 1; 237 } 238 239 //next, the list 240 if (tempFaces.size() != 0) { 241 int faceGroupLoc = numGroups - 1; //the face group is the last 242 // one 243 primGroupArray[faceGroupLoc].type = PrimitiveGroup.PT_LIST; 244 primGroupArray[faceGroupLoc].indices = new int[tempFaces.size() * 3]; 245 primGroupArray[faceGroupLoc].numIndices = tempFaces.size() * 3; 246 int indexCtr = 0; 247 for (int i = 0; i < tempFaces.size(); i++) { 248 primGroupArray[faceGroupLoc].indices[indexCtr++] = tempFaces.at(i).m_v0; 249 primGroupArray[faceGroupLoc].indices[indexCtr++] = tempFaces.at(i).m_v1; 250 primGroupArray[faceGroupLoc].indices[indexCtr++] = tempFaces.at(i).m_v2; 251 } 252 } 253 } 254 return primGroups; 255 } 256 257 /** 258 * Function to remap your indices to improve spatial locality in your 259 * vertex buffer. 260 * 261 * in_primGroups: array of PrimitiveGroups you want remapped numGroups: 262 * number of entries in in_primGroups numVerts: number of vertices in your 263 * vertex buffer, also can be thought of as the range of acceptable values 264 * for indices in your primitive groups. remappedGroups: array of remapped 265 * PrimitiveGroups 266 * 267 * Note that, according to the remapping handed back to you, you must 268 * reorder your vertex buffer. 269 * 270 */ 271 272 public static int[] remapIndices(int[] indices, int numVerts) { 273 int[] indexCache = new int[numVerts]; 274 Arrays.fill(indexCache, -1); 275 276 int numIndices = indices.length; 277 int[] remappedIndices = new int[numIndices]; 278 int indexCtr = 0; 279 for (int j = 0; j < numIndices; j++) { 280 int cachedIndex = indexCache[indices[j]]; 281 if (cachedIndex == -1) //we haven't seen this index before 282 { 283 //point to "last" vertex in VB 284 remappedIndices[j] = indexCtr; 285 286 //add to index cache, increment 287 indexCache[indices[j]] = indexCtr++; 288 } else { 289 //we've seen this index before 290 remappedIndices[j] = cachedIndex; 291 } 292 } 293 294 return remappedIndices; 295 } 296 297 public static void remapArrays(float[] vertexBuffer, int vertexSize, int[] indices) { 298 int[] remapped = remapIndices(indices, vertexBuffer.length / vertexSize); 299 float[] bufferCopy = vertexBuffer.clone(); 300 for (int i = 0; i < remapped.length; i++) { 301 int from = indices[i] * vertexSize; 302 int to = remapped[i] * vertexSize; 303 for (int j = 0; j < vertexSize; j++) { 304 vertexBuffer[to + j] = bufferCopy[from + j]; 305 } 306 } 307 308 System.arraycopy(remapped, 0, indices, 0, indices.length); 309 } 310 311 } 312
