1 /* 2 * Copyright (c) 2010, 2014, Oracle and/or its affiliates. 3 * All rights reserved. Use is subject to license terms. 4 * 5 * This file is available and licensed under the following license: 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * - Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * - Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the distribution. 16 * - Neither the name of Oracle Corporation nor the names of its 17 * contributors may be used to endorse or promote products derived 18 * from this software 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 22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 24 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 package com.javafx.experiments.importers; 33 34 import java.util.ArrayList; 35 import java.util.Arrays; 36 import java.util.BitSet; 37 import java.util.HashMap; 38 import java.util.Iterator; 39 import java.util.LinkedList; 40 import java.util.List; 41 import java.util.Map; 42 import java.util.Queue; 43 import com.sun.javafx.geom.Vec3f; 44 import javafx.scene.shape.TriangleMesh; 45 46 /** Util for converting Normals to Smoothing Groups */ 47 public class SmoothingGroups { 48 private BitSet visited, notVisited; 49 private Queue<Integer> q; 50 51 private int[][] faces; 52 private int[][] faceNormals; 53 private float[] normals; 54 55 private Edge[][] faceEdges; 56 57 public SmoothingGroups(int faces[][], int[][] faceNormals, float[] normals) { 58 this.faces = faces; 59 this.faceNormals = faceNormals; 60 this.normals = normals; 61 visited = new BitSet(faces.length); 62 notVisited = new BitSet(faces.length); 63 notVisited.set(0, faces.length, true); 64 q = new LinkedList<Integer>(); 65 } 66 67 // edge -> [faces] 68 private List<Integer> getNextConnectedComponent(Map<Edge, List<Integer>> adjacentFaces) { 69 int index = notVisited.previousSetBit(faces.length - 1); 70 q.add(index); 71 visited.set(index); 72 notVisited.set(index, false); 73 List<Integer> res = new ArrayList<Integer>(); 74 while (!q.isEmpty()) { 75 Integer faceIndex = q.remove(); 76 res.add(faceIndex); 77 for (Edge edge : faceEdges[faceIndex]) { 78 List<Integer> adjFaces = adjacentFaces.get(edge); 79 if (adjFaces == null) { 80 continue; 81 } 82 Integer adjFaceIndex = adjFaces.get(adjFaces.get(0).equals(faceIndex) ? 1 : 0); 83 if (!visited.get(adjFaceIndex)) { 84 q.add(adjFaceIndex); 85 visited.set(adjFaceIndex); 86 notVisited.set(adjFaceIndex, false); 87 } 88 } 89 } 90 return res; 91 } 92 93 private boolean hasNextConnectedComponent() { 94 return !notVisited.isEmpty(); 95 } 96 97 private void computeFaceEdges() { 98 faceEdges = new Edge[faces.length][]; 99 for (int f = 0; f < faces.length; f++) { 100 int[] face = faces[f]; 101 int[] faceNormal = faceNormals[f]; 102 int n = face.length/2; 103 faceEdges[f] = new Edge[n]; 104 int from = face[(n-1) * 2]; 105 int fromNormal = faceNormal[n-1]; 106 for (int i = 0; i < n; i++) { 107 int to = face[i * 2]; 108 int toNormal = faceNormal[i]; 109 Edge edge = new Edge(from, to, fromNormal, toNormal); 110 faceEdges[f][i] = edge; 111 from = to; 112 fromNormal = toNormal; 113 } 114 } 115 } 116 117 private Map<Edge, List<Integer>> getAdjacentFaces() { 118 Map<Edge, List<Integer>> adjacentFaces = new HashMap<Edge, List<Integer>>(); 119 for (int f = 0; f < faceEdges.length; f++) { 120 for (Edge edge : faceEdges[f]) { 121 if (!adjacentFaces.containsKey(edge)) { 122 adjacentFaces.put(edge, new ArrayList<Integer>()); 123 } 124 adjacentFaces.get(edge).add(f); 125 } 126 } 127 for (Iterator<Map.Entry<Edge, List<Integer>>> it = adjacentFaces.entrySet().iterator(); it.hasNext(); ) { 128 Map.Entry<Edge, List<Integer>> e = it.next(); 129 if (e.getValue().size() != 2) { 130 // just skip them 131 it.remove(); 132 } 133 } 134 return adjacentFaces; 135 } 136 137 Vec3f getNormal(int index) { 138 return new Vec3f(normals[index * 3], normals[index * 3 + 1], normals[index * 3 + 2]); 139 } 140 141 private static final float normalAngle = 0.9994f; // cos(2) 142 143 private static boolean isNormalsEqual(Vec3f n1, Vec3f n2) { 144 if (n1.x == 1.0e20f || n1.y == 1.0e20f || n1.z == 1.0e20f 145 || n2.x == 1.0e20f || n2.y == 1.0e20f || n2.z == 1.0e20f) { 146 //System.out.println("unlocked normal found, skipping"); 147 return false; 148 } 149 Vec3f myN1 = new Vec3f(n1); 150 myN1.normalize(); 151 Vec3f myN2 = new Vec3f(n2); 152 myN2.normalize(); 153 return myN1.dot(myN2) >= normalAngle; 154 } 155 156 private Map<Edge, List<Integer>> getSmoothEdges(Map<Edge, List<Integer>> adjacentFaces) { 157 Map<Edge, List<Integer>> smoothEdges = new HashMap<Edge, List<Integer>>(); 158 159 for (int face = 0; face < faceEdges.length; face++) { 160 for (Edge edge : faceEdges[face]) { 161 List<Integer> adjFaces = adjacentFaces.get(edge); 162 if (adjFaces == null || adjFaces.size() != 2) { 163 // could happen when we skip edges! 164 continue; 165 } 166 int adjFace = adjFaces.get(adjFaces.get(0) == face ? 1 : 0); 167 Edge[] adjFaceEdges = faceEdges[adjFace]; 168 int adjEdgeInd = Arrays.asList(adjFaceEdges).indexOf(edge); 169 if (adjEdgeInd == -1) { 170 System.out.println("Can't find edge " + edge + " in face " + adjFace); 171 System.out.println(Arrays.asList(adjFaceEdges)); 172 continue; 173 } 174 Edge adjEdge = adjFaceEdges[adjEdgeInd]; 175 176 if (edge.isSmooth(adjEdge)) { 177 if (!smoothEdges.containsKey(edge)) { 178 smoothEdges.put(edge, adjFaces); 179 } 180 } 181 } 182 } 183 return smoothEdges; 184 } 185 186 private List<List<Integer>> calcConnComponents(Map<Edge, List<Integer>> smoothEdges) { 187 //System.out.println("smoothEdges = " + smoothEdges); 188 List<List<Integer>> groups = new ArrayList<List<Integer>>(); 189 while (hasNextConnectedComponent()) { 190 List<Integer> smoothGroup = getNextConnectedComponent(smoothEdges); 191 groups.add(smoothGroup); 192 } 193 return groups; 194 } 195 196 private int[] generateSmGroups(List<List<Integer>> groups) { 197 int[] smGroups = new int[faceNormals.length]; 198 int curGroup = 0; 199 for (int i = 0; i < groups.size(); i++) { 200 List<Integer> list = groups.get(i); 201 if (list.size() == 1) { 202 smGroups[list.get(0)] = 0; 203 } else { 204 for (int j = 0; j < list.size(); j++) { 205 Integer faceIndex = list.get(j); 206 smGroups[faceIndex] = 1 << curGroup; 207 } 208 if (curGroup++ == 31) { 209 curGroup = 0; 210 } 211 } 212 } 213 return smGroups; 214 } 215 216 private int[] calcSmoothGroups() { 217 computeFaceEdges(); 218 219 // edge -> [faces] 220 Map<Edge, List<Integer>> adjacentFaces = getAdjacentFaces(); 221 222 // smooth edge -> [faces] 223 Map<Edge, List<Integer>> smoothEdges = getSmoothEdges(adjacentFaces); 224 225 //System.out.println("smoothEdges = " + smoothEdges); 226 List<List<Integer>> groups = calcConnComponents(smoothEdges); 227 228 return generateSmGroups(groups); 229 } 230 231 private class Edge { 232 int from, to; 233 int fromNormal, toNormal; 234 235 public Edge(int from, int to, int fromNormal, int toNormal) { 236 this.from = Math.min(from, to); 237 this.to = Math.max(from, to); 238 this.fromNormal = Math.min(fromNormal, toNormal); 239 this.toNormal = Math.max(fromNormal, toNormal); 240 } 241 242 public boolean isSmooth(Edge edge) { 243 boolean smooth = (isNormalsEqual(getNormal(fromNormal), getNormal(edge.fromNormal)) && isNormalsEqual(getNormal(toNormal), getNormal(edge.toNormal))) || 244 (isNormalsEqual(getNormal(fromNormal), getNormal(edge.toNormal)) && isNormalsEqual(getNormal(toNormal), getNormal(edge.fromNormal))); 245 return smooth; 246 } 247 248 @Override 249 public int hashCode() { 250 int hash = 7; 251 hash = 41 * hash + this.from; 252 hash = 41 * hash + this.to; 253 return hash; 254 } 255 256 @Override 257 public boolean equals(Object obj) { 258 if (obj == null) { 259 return false; 260 } 261 if (getClass() != obj.getClass()) { 262 return false; 263 } 264 final Edge other = (Edge) obj; 265 if (this.from != other.from) { 266 return false; 267 } 268 if (this.to != other.to) { 269 return false; 270 } 271 return true; 272 } 273 } 274 275 /** 276 * Calculates smoothing groups for data formatted in PolygonMesh style 277 * @param faces An array of faces, where each face consists of an array of vertex and uv indices 278 * @param faceNormals An array of face normals, where each face normal consists of an array of normal indices 279 * @param normals The array of normals 280 * @return An array of smooth groups, where the length of the array is the number of faces 281 */ 282 public static int[] calcSmoothGroups(int[][] faces, int[][] faceNormals, float[] normals) { 283 SmoothingGroups smoothGroups = new SmoothingGroups(faces, faceNormals, normals); 284 return smoothGroups.calcSmoothGroups(); 285 } 286 287 /** 288 * Calculates smoothing groups for data formatted in TriangleMesh style 289 * @param flatFaces An array of faces, where each triangle face is represented by 6 (vertex and uv) indices 290 * @param flatFaceNormals An array of face normals, where each triangle face is represented by 3 normal indices 291 * @param normals The array of normals 292 * @return An array of smooth groups, where the length of the array is the number of faces 293 */ 294 public static int[] calcSmoothGroups(TriangleMesh mesh, int[] flatFaces, int[] flatFaceNormals, float[] normals) { 295 int faceElementSize = mesh.getFaceElementSize(); 296 int[][] faces = new int[flatFaces.length/faceElementSize][faceElementSize]; 297 for (int f = 0; f < faces.length; f++) { 298 for (int e = 0; e < faceElementSize; e++) { 299 faces[f][e] = flatFaces[f * faceElementSize + e]; 300 } 301 } 302 int pointElementSize = mesh.getPointElementSize(); 303 int[][] faceNormals = new int[flatFaceNormals.length/pointElementSize][pointElementSize]; 304 for (int f = 0; f < faceNormals.length; f++) { 305 for (int e = 0; e < pointElementSize; e++) { 306 faceNormals[f][e] = flatFaceNormals[f * pointElementSize + e]; 307 } 308 } 309 SmoothingGroups smoothGroups = new SmoothingGroups(faces, faceNormals, normals); 310 return smoothGroups.calcSmoothGroups(); 311 } 312 }