1 /* 2 * Copyright (c) 2009-2010 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 /** 36 * 37 */ 38 class StripInfo { 39 40 StripStartInfo m_startInfo; 41 FaceInfoVec m_faces = new FaceInfoVec(); 42 int m_stripId; 43 int m_experimentId; 44 45 boolean visited; 46 47 int m_numDegenerates; 48 49 StripInfo(StripStartInfo startInfo,int stripId, int experimentId)50 public StripInfo(StripStartInfo startInfo,int stripId, int experimentId) { 51 52 m_startInfo = startInfo; 53 m_stripId = stripId; 54 m_experimentId = experimentId; 55 visited = false; 56 m_numDegenerates = 0; 57 } 58 isExperiment()59 boolean isExperiment() { 60 return m_experimentId >= 0; 61 } 62 isInStrip(FaceInfo faceInfo)63 boolean isInStrip(FaceInfo faceInfo) { 64 if(faceInfo == null) 65 return false; 66 67 return (m_experimentId >= 0 ? faceInfo.m_testStripId == m_stripId : faceInfo.m_stripId == m_stripId); 68 } 69 70 71 /////////////////////////////////////////////////////////////////////////////////////////// 72 // IsMarked() 73 // 74 // If either the faceInfo has a real strip index because it is 75 // already assign to a committed strip OR it is assigned in an 76 // experiment and the experiment index is the one we are building 77 // for, then it is marked and unavailable isMarked(FaceInfo faceInfo)78 boolean isMarked(FaceInfo faceInfo){ 79 return (faceInfo.m_stripId >= 0) || (isExperiment() && faceInfo.m_experimentId == m_experimentId); 80 } 81 82 83 /////////////////////////////////////////////////////////////////////////////////////////// 84 // MarkTriangle() 85 // 86 // Marks the face with the current strip ID 87 // markTriangle(FaceInfo faceInfo)88 void markTriangle(FaceInfo faceInfo){ 89 if (isExperiment()){ 90 faceInfo.m_experimentId = m_experimentId; 91 faceInfo.m_testStripId = m_stripId; 92 } 93 else{ 94 faceInfo.m_experimentId = -1; 95 faceInfo.m_stripId = m_stripId; 96 } 97 } 98 99 unique(FaceInfoVec faceVec, FaceInfo face)100 boolean unique(FaceInfoVec faceVec, FaceInfo face) 101 { 102 boolean bv0, bv1, bv2; //bools to indicate whether a vertex is in the faceVec or not 103 bv0 = bv1 = bv2 = false; 104 105 for(int i = 0; i < faceVec.size(); i++) 106 { 107 if(!bv0) 108 { 109 if( (faceVec.at(i).m_v0 == face.m_v0) || 110 (faceVec.at(i).m_v1 == face.m_v0) || 111 (faceVec.at(i).m_v2 == face.m_v0) ) 112 bv0 = true; 113 } 114 115 if(!bv1) 116 { 117 if( (faceVec.at(i).m_v0 == face.m_v1) || 118 (faceVec.at(i).m_v1 == face.m_v1) || 119 (faceVec.at(i).m_v2 == face.m_v1) ) 120 bv1 = true; 121 } 122 123 if(!bv2) 124 { 125 if( (faceVec.at(i).m_v0 == face.m_v2) || 126 (faceVec.at(i).m_v1 == face.m_v2) || 127 (faceVec.at(i).m_v2 == face.m_v2) ) 128 bv2 = true; 129 } 130 131 //the face is not unique, all it's vertices exist in the face vector 132 if(bv0 && bv1 && bv2) 133 return false; 134 } 135 136 //if we get out here, it's unique 137 return true; 138 } 139 140 141 /////////////////////////////////////////////////////////////////////////////////////////// 142 // Build() 143 // 144 // Builds a strip forward as far as we can go, then builds backwards, and joins the two lists 145 // build(EdgeInfoVec edgeInfos, FaceInfoVec faceInfos)146 void build(EdgeInfoVec edgeInfos, FaceInfoVec faceInfos) 147 { 148 // used in building the strips forward and backward 149 IntVec scratchIndices = new IntVec(); 150 151 // build forward... start with the initial face 152 FaceInfoVec forwardFaces = new FaceInfoVec(); 153 FaceInfoVec backwardFaces = new FaceInfoVec(); 154 forwardFaces.add(m_startInfo.m_startFace); 155 156 markTriangle(m_startInfo.m_startFace); 157 158 int v0 = (m_startInfo.m_toV1 ? m_startInfo.m_startEdge.m_v0 : m_startInfo.m_startEdge.m_v1); 159 int v1 = (m_startInfo.m_toV1 ? m_startInfo.m_startEdge.m_v1 : m_startInfo.m_startEdge.m_v0); 160 161 // easiest way to get v2 is to use this function which requires the 162 // other indices to already be in the list. 163 scratchIndices.add(v0); 164 scratchIndices.add(v1); 165 int v2 = Stripifier.getNextIndex(scratchIndices, m_startInfo.m_startFace); 166 scratchIndices.add(v2); 167 168 // 169 // build the forward list 170 // 171 int nv0 = v1; 172 int nv1 = v2; 173 174 FaceInfo nextFace = Stripifier.findOtherFace(edgeInfos, nv0, nv1, m_startInfo.m_startFace); 175 while (nextFace != null && !isMarked(nextFace)) 176 { 177 //check to see if this next face is going to cause us to die soon 178 int testnv0 = nv1; 179 int testnv1 = Stripifier.getNextIndex(scratchIndices, nextFace); 180 181 FaceInfo nextNextFace = Stripifier.findOtherFace(edgeInfos, testnv0, testnv1, nextFace); 182 183 if( (nextNextFace == null) || (isMarked(nextNextFace)) ) 184 { 185 //uh, oh, we're following a dead end, try swapping 186 FaceInfo testNextFace = Stripifier.findOtherFace(edgeInfos, nv0, testnv1, nextFace); 187 188 if( ((testNextFace != null) && !isMarked(testNextFace)) ) 189 { 190 //we only swap if it buys us something 191 192 //add a "fake" degenerate face 193 FaceInfo tempFace = new FaceInfo(nv0, nv1, nv0); 194 195 forwardFaces.add(tempFace); 196 markTriangle(tempFace); 197 198 scratchIndices.add(nv0); 199 testnv0 = nv0; 200 201 ++m_numDegenerates; 202 } 203 204 } 205 206 // add this to the strip 207 forwardFaces.add(nextFace); 208 209 markTriangle(nextFace); 210 211 // add the index 212 //nv0 = nv1; 213 //nv1 = NvStripifier::GetNextIndex(scratchIndices, nextFace); 214 scratchIndices.add(testnv1); 215 216 // and get the next face 217 nv0 = testnv0; 218 nv1 = testnv1; 219 220 nextFace = Stripifier.findOtherFace(edgeInfos, nv0, nv1, nextFace); 221 222 } 223 224 // tempAllFaces is going to be forwardFaces + backwardFaces 225 // it's used for Unique() 226 FaceInfoVec tempAllFaces = new FaceInfoVec(); 227 for(int i = 0; i < forwardFaces.size(); i++) 228 tempAllFaces.add(forwardFaces.at(i)); 229 230 // 231 // reset the indices for building the strip backwards and do so 232 // 233 scratchIndices.clear(); 234 scratchIndices.add(v2); 235 scratchIndices.add(v1); 236 scratchIndices.add(v0); 237 nv0 = v1; 238 nv1 = v0; 239 nextFace = Stripifier.findOtherFace(edgeInfos, nv0, nv1, m_startInfo.m_startFace); 240 while (nextFace != null && !isMarked(nextFace)) 241 { 242 //this tests to see if a face is "unique", meaning that its vertices aren't already in the list 243 // so, strips which "wrap-around" are not allowed 244 if(!unique(tempAllFaces, nextFace)) 245 break; 246 247 //check to see if this next face is going to cause us to die soon 248 int testnv0 = nv1; 249 int testnv1 = Stripifier.getNextIndex(scratchIndices, nextFace); 250 251 FaceInfo nextNextFace = Stripifier.findOtherFace(edgeInfos, testnv0, testnv1, nextFace); 252 253 if( (nextNextFace == null) || (isMarked(nextNextFace)) ) 254 { 255 //uh, oh, we're following a dead end, try swapping 256 FaceInfo testNextFace = Stripifier.findOtherFace(edgeInfos, nv0, testnv1, nextFace); 257 if( ((testNextFace != null) && !isMarked(testNextFace)) ) 258 { 259 //we only swap if it buys us something 260 261 //add a "fake" degenerate face 262 FaceInfo tempFace = new FaceInfo(nv0, nv1, nv0); 263 264 backwardFaces.add(tempFace); 265 markTriangle(tempFace); 266 scratchIndices.add(nv0); 267 testnv0 = nv0; 268 269 ++m_numDegenerates; 270 } 271 272 } 273 274 // add this to the strip 275 backwardFaces.add(nextFace); 276 277 //this is just so Unique() will work 278 tempAllFaces.add(nextFace); 279 280 markTriangle(nextFace); 281 282 // add the index 283 //nv0 = nv1; 284 //nv1 = NvStripifier::GetNextIndex(scratchIndices, nextFace); 285 scratchIndices.add(testnv1); 286 287 // and get the next face 288 nv0 = testnv0; 289 nv1 = testnv1; 290 nextFace = Stripifier.findOtherFace(edgeInfos, nv0, nv1, nextFace); 291 } 292 293 // Combine the forward and backwards stripification lists and put into our own face vector 294 combine(forwardFaces, backwardFaces); 295 } 296 297 298 /////////////////////////////////////////////////////////////////////////////////////////// 299 // Combine() 300 // 301 // Combines the two input face vectors and puts the result into m_faces 302 // combine(FaceInfoVec forward, FaceInfoVec backward)303 void combine(FaceInfoVec forward, FaceInfoVec backward){ 304 305 // add backward faces 306 int numFaces = backward.size(); 307 for (int i = numFaces - 1; i >= 0; i--) 308 m_faces.add(backward.at(i)); 309 310 // add forward faces 311 numFaces = forward.size(); 312 for (int i = 0; i < numFaces; i++) 313 m_faces.add(forward.at(i)); 314 } 315 316 317 /////////////////////////////////////////////////////////////////////////////////////////// 318 // SharesEdge() 319 // 320 // Returns true if the input face and the current strip share an edge 321 // sharesEdge(FaceInfo faceInfo, EdgeInfoVec edgeInfos)322 boolean sharesEdge(FaceInfo faceInfo, EdgeInfoVec edgeInfos) 323 { 324 //check v0.v1 edge 325 EdgeInfo currEdge = Stripifier.findEdgeInfo(edgeInfos, faceInfo.m_v0, faceInfo.m_v1); 326 327 if(isInStrip(currEdge.m_face0) || isInStrip(currEdge.m_face1)) 328 return true; 329 330 //check v1.v2 edge 331 currEdge = Stripifier.findEdgeInfo(edgeInfos, faceInfo.m_v1, faceInfo.m_v2); 332 333 if(isInStrip(currEdge.m_face0) || isInStrip(currEdge.m_face1)) 334 return true; 335 336 //check v2.v0 edge 337 currEdge = Stripifier.findEdgeInfo(edgeInfos, faceInfo.m_v2, faceInfo.m_v0); 338 339 if(isInStrip(currEdge.m_face0) || isInStrip(currEdge.m_face1)) 340 return true; 341 342 return false; 343 344 } 345 346 347 348 349 350 351 352 353 354 355 } 356