001/** 002 * Copyright (c) 2008-2014 Ardor Labs, Inc. 003 * 004 * This file is part of Ardor3D. 005 * 006 * Ardor3D is free software: you can redistribute it and/or modify it 007 * under the terms of its license which may be found in the accompanying 008 * LICENSE file or at <http://www.ardor3d.com/LICENSE>. 009 */ 010 011package com.ardor3d.extension.model.util.nvtristrip; 012 013import java.util.ArrayList; 014import java.util.List; 015 016final class NvStripInfo { 017 NvStripStartInfo _startInfo; 018 List<NvFaceInfo> _faces = new ArrayList<>(); 019 int _stripId; 020 int _experimentId; 021 022 boolean _visited; 023 024 int _numDegenerates; 025 026 // A little information about the creation of the triangle strips 027 NvStripInfo(final NvStripStartInfo startInfo, final int stripId) { 028 this(startInfo, stripId, -1); 029 } 030 031 NvStripInfo(final NvStripStartInfo startInfo, final int stripId, final int experimentId) { 032 _startInfo = startInfo; 033 _stripId = stripId; 034 _experimentId = experimentId; 035 _visited = false; 036 _numDegenerates = 0; 037 } 038 039 /** 040 * @return true if the experiment id is >= 0 041 */ 042 final boolean isExperiment() { 043 return _experimentId >= 0; 044 } 045 046 /** 047 * @param faceInfo 048 * the face info 049 * @return <code>true</code> if it's in the strip 050 */ 051 final boolean IsInStrip(final NvFaceInfo faceInfo) { 052 if (faceInfo == null) { 053 return false; 054 } 055 056 return _experimentId >= 0 ? faceInfo._testStripId == _stripId : faceInfo._stripId == _stripId; 057 } 058 059 /** 060 * 061 * @param faceInfo 062 * the face info 063 * @param edgeInfos 064 * the edge infos 065 * @return <code>true</code> if the input face and the current strip share an edge 066 */ 067 boolean sharesEdge(final NvFaceInfo faceInfo, final List<NvEdgeInfo> edgeInfos) { 068 // check v0->v1 edge 069 NvEdgeInfo currEdge = NvStripifier.findEdgeInfo(edgeInfos, faceInfo._v0, faceInfo._v1); 070 071 if (IsInStrip(currEdge._face0) || IsInStrip(currEdge._face1)) { 072 return true; 073 } 074 075 // check v1->v2 edge 076 currEdge = NvStripifier.findEdgeInfo(edgeInfos, faceInfo._v1, faceInfo._v2); 077 078 if (IsInStrip(currEdge._face0) || IsInStrip(currEdge._face1)) { 079 return true; 080 } 081 082 // check v2->v0 edge 083 currEdge = NvStripifier.findEdgeInfo(edgeInfos, faceInfo._v2, faceInfo._v0); 084 085 if (IsInStrip(currEdge._face0) || IsInStrip(currEdge._face1)) { 086 return true; 087 } 088 089 return false; 090 } 091 092 /** 093 * take the given forward and backward strips and combine them together 094 * 095 * @param forward 096 * the forward strips 097 * @param backward 098 * the backward strips 099 */ 100 void combine(final List<NvFaceInfo> forward, final List<NvFaceInfo> backward) { 101 // add backward faces 102 int numFaces = backward.size(); 103 for (int i = numFaces - 1; i >= 0; i--) { 104 _faces.add(backward.get(i)); 105 } 106 107 // add forward faces 108 numFaces = forward.size(); 109 for (int i = 0; i < numFaces; i++) { 110 _faces.add(forward.get(i)); 111 } 112 } 113 114 /** 115 * @param faceVec 116 * the face list 117 * @param face 118 * the face 119 * @return <code>true</code> if the face is "unique", i.e. has a vertex which doesn't exist in the faceVec 120 */ 121 boolean unique(final List<NvFaceInfo> faceVec, final NvFaceInfo face) { 122 boolean bv0, bv1, bv2; // bools to indicate whether a vertex is in the faceVec or not 123 bv0 = bv1 = bv2 = false; 124 125 for (int i = 0; i < faceVec.size(); i++) { 126 if (!bv0) { 127 if (faceVec.get(i)._v0 == face._v0 || faceVec.get(i)._v1 == face._v0 128 || faceVec.get(i)._v2 == face._v0) { 129 bv0 = true; 130 } 131 } 132 133 if (!bv1) { 134 if (faceVec.get(i)._v0 == face._v1 || faceVec.get(i)._v1 == face._v1 135 || faceVec.get(i)._v2 == face._v1) { 136 bv1 = true; 137 } 138 } 139 140 if (!bv2) { 141 if (faceVec.get(i)._v0 == face._v2 || faceVec.get(i)._v1 == face._v2 142 || faceVec.get(i)._v2 == face._v2) { 143 bv2 = true; 144 } 145 } 146 147 // the face is not unique, all its vertices exist in the face vector 148 if (bv0 && bv1 && bv2) { 149 return false; 150 } 151 } 152 153 // if we get out here, it's unique 154 return true; 155 } 156 157 /** 158 * If either the faceInfo has a real strip index because it is already assign to a committed strip OR it is assigned 159 * in an experiment and the experiment index is the one we are building for, then it is marked and unavailable 160 * 161 * @param faceInfo 162 * the face info 163 * @return <code>true</code> if the face is marked 164 * 165 */ 166 boolean isMarked(final NvFaceInfo faceInfo) { 167 return faceInfo._stripId >= 0 || isExperiment() && faceInfo._experimentId == _experimentId; 168 } 169 170 /** 171 * Marks the face with the current strip ID 172 * 173 * @param faceInfo 174 * the face info 175 */ 176 void markTriangle(final NvFaceInfo faceInfo) { 177 assert !isMarked(faceInfo); 178 if (isExperiment()) { 179 faceInfo._experimentId = _experimentId; 180 faceInfo._testStripId = _stripId; 181 } else { 182 faceInfo._experimentId = -1; 183 faceInfo._stripId = _stripId; 184 } 185 } 186 187 /** 188 * Builds a strip forward as far as we can go, then builds backwards, and joins the two lists 189 * 190 * @param edgeInfos 191 * the edge infos 192 * @param faceInfos 193 * the face infos 194 */ 195 void build(final List<NvEdgeInfo> edgeInfos, final List<NvFaceInfo> faceInfos) { 196 // used in building the strips forward and backward 197 final List<Integer> scratchIndices = new ArrayList<>(); 198 199 // build forward... start with the initial face 200 final List<NvFaceInfo> forwardFaces = new ArrayList<>(); 201 final List<NvFaceInfo> backwardFaces = new ArrayList<>(); 202 forwardFaces.add(_startInfo._startFace); 203 204 markTriangle(_startInfo._startFace); 205 206 final int v0 = _startInfo._toV1 ? _startInfo._startEdge._v0 : _startInfo._startEdge._v1; 207 final int v1 = _startInfo._toV1 ? _startInfo._startEdge._v1 : _startInfo._startEdge._v0; 208 209 // easiest way to get v2 is to use this function which requires the 210 // other indices to already be in the list. 211 scratchIndices.add(v0); 212 scratchIndices.add(v1); 213 final int v2 = NvStripifier.getNextIndex(scratchIndices, _startInfo._startFace); 214 scratchIndices.add(v2); 215 216 // 217 // build the forward list 218 // 219 int nv0 = v1; 220 int nv1 = v2; 221 222 NvFaceInfo nextFace = NvStripifier.findOtherFace(edgeInfos, nv0, nv1, _startInfo._startFace); 223 while (nextFace != null && !isMarked(nextFace)) { 224 // check to see if this next face is going to cause us to die soon 225 int testnv0 = nv1; 226 final int testnv1 = NvStripifier.getNextIndex(scratchIndices, nextFace); 227 228 final NvFaceInfo nextNextFace = NvStripifier.findOtherFace(edgeInfos, testnv0, testnv1, nextFace); 229 230 if (nextNextFace == null || isMarked(nextNextFace)) { 231 // uh, oh, we're following a dead end, try swapping 232 final NvFaceInfo testNextFace = NvStripifier.findOtherFace(edgeInfos, nv0, testnv1, nextFace); 233 234 if (testNextFace != null && !isMarked(testNextFace)) { 235 // we only swap if it buys us something 236 237 // add a "fake" degenerate face 238 final NvFaceInfo tempFace = new NvFaceInfo(nv0, nv1, nv0, true); 239 240 forwardFaces.add(tempFace); 241 markTriangle(tempFace); 242 243 scratchIndices.add(nv0); 244 testnv0 = nv0; 245 246 ++_numDegenerates; 247 } 248 249 } 250 251 // add this to the strip 252 forwardFaces.add(nextFace); 253 254 markTriangle(nextFace); 255 256 // add the index 257 // nv0 = nv1; 258 // nv1 = NvStripifier.GetNextIndex(scratchIndices, nextFace); 259 scratchIndices.add(testnv1); 260 261 // and get the next face 262 nv0 = testnv0; 263 nv1 = testnv1; 264 265 nextFace = NvStripifier.findOtherFace(edgeInfos, nv0, nv1, nextFace); 266 267 } 268 269 // tempAllFaces is going to be forwardFaces + backwardFaces 270 // it's used for Unique() 271 final List<NvFaceInfo> tempAllFaces = new ArrayList<>(); 272 for (int i = 0; i < forwardFaces.size(); i++) { 273 tempAllFaces.add(forwardFaces.get(i)); 274 } 275 276 // 277 // reset the indices for building the strip backwards and do so 278 // 279 scratchIndices.clear(); 280 scratchIndices.add(v2); 281 scratchIndices.add(v1); 282 scratchIndices.add(v0); 283 nv0 = v1; 284 nv1 = v0; 285 nextFace = NvStripifier.findOtherFace(edgeInfos, nv0, nv1, _startInfo._startFace); 286 while (nextFace != null && !isMarked(nextFace)) { 287 // this tests to see if a face is "unique", meaning that its vertices aren't already in the list 288 // so, strips which "wrap-around" are not allowed 289 if (!unique(tempAllFaces, nextFace)) { 290 break; 291 } 292 293 // check to see if this next face is going to cause us to die soon 294 int testnv0 = nv1; 295 final int testnv1 = NvStripifier.getNextIndex(scratchIndices, nextFace); 296 297 final NvFaceInfo nextNextFace = NvStripifier.findOtherFace(edgeInfos, testnv0, testnv1, nextFace); 298 299 if (nextNextFace == null || isMarked(nextNextFace)) { 300 // uh, oh, we're following a dead end, try swapping 301 final NvFaceInfo testNextFace = NvStripifier.findOtherFace(edgeInfos, nv0, testnv1, nextFace); 302 if (testNextFace != null && !isMarked(testNextFace)) { 303 // we only swap if it buys us something 304 305 // add a "fake" degenerate face 306 final NvFaceInfo tempFace = new NvFaceInfo(nv0, nv1, nv0, true); 307 308 backwardFaces.add(tempFace); 309 markTriangle(tempFace); 310 scratchIndices.add(nv0); 311 testnv0 = nv0; 312 313 ++_numDegenerates; 314 } 315 316 } 317 318 // add this to the strip 319 backwardFaces.add(nextFace); 320 321 // this is just so Unique() will work 322 tempAllFaces.add(nextFace); 323 324 markTriangle(nextFace); 325 326 // add the index 327 // nv0 = nv1; 328 // nv1 = NvStripifier.GetNextIndex(scratchIndices, nextFace); 329 scratchIndices.add(testnv1); 330 331 // and get the next face 332 nv0 = testnv0; 333 nv1 = testnv1; 334 nextFace = NvStripifier.findOtherFace(edgeInfos, nv0, nv1, nextFace); 335 } 336 337 // Combine the forward and backwards stripification lists and put into our own face vector 338 combine(forwardFaces, backwardFaces); 339 } 340}