1 /*
2 * Copyright (c) 2010, 2015, 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.javafx.experiments.utils3d.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 }