OPT: LodGenerator - replace ArrayList sort with PriorityQueue #751
Description
LodGenerator can be improved by using PriorityQueue instead of ArrayList and sorting. Following code is without logging. So cannot be used without modification.
computeLods - uses PriorityQueue. Add/Remove are log N
computeEdgeCollapseCost - prefilters triangles from inner loop in last section
New code takes about 40% of original computeLods duration. Depends on input data.
private static final Comparator<Vertex> COLLAPSE_COMPARATOR = (o1, o2) -> Float.compare(o1.collapseCost, o2.collapseCost);
private Queue<Vertex> collapseCostSet = new PriorityQueue<>(COLLAPSE_COMPARATOR);
private Triangle[] triangles = null;
public VertexBuffer[] computeLods(TriangleReductionMethod reductionMethod, float... reductionValues) {
int tricount = triangleList.size();
int lastBakeVertexCount = tricount;
int lodCount = reductionValues.length;
VertexBuffer[] lods = new VertexBuffer[lodCount + 1];
int numBakedLods = 1;
lods[0] = mesh.getBuffer(VertexBuffer.Type.INDEX);
for (int curLod = 0; curLod < lodCount; curLod++) {
int neededTriCount = calcLodTriCount(reductionMethod, reductionValues[curLod]);
while (neededTriCount < tricount) {
Vertex v = collapseCostSet.poll();
if (v == null) break;
if (v.collapseCost < collapseCostLimit) {
if (!collapse(v)) {
System.out.printf("Couldn't collapse vertex%s%n", v.index);
}
} else {
break;
}
tricount = triangleList.size() - nbCollapsedTri;
}
boolean outSkipped = (lastBakeVertexCount == tricount);
if (!outSkipped) {
lastBakeVertexCount = tricount;
lods[curLod + 1] = makeLod(mesh);
numBakedLods++;
}
}
if (numBakedLods <= lodCount) {
VertexBuffer[] bakedLods = new VertexBuffer[numBakedLods];
System.arraycopy(lods, 0, bakedLods, 0, numBakedLods);
return bakedLods;
} else {
return lods;
}
}
private float computeEdgeCollapseCost(Vertex src, Edge dstEdge) {
// This is based on Ogre's collapse cost calculation algorithm.
Vertex dest = dstEdge.destination;
// Check for singular triangle destruction
// If src and dest both only have 1 triangle (and it must be a shared one)
// then this would destroy the shape, so don't do this
if (src.triangles.size() == 1 && dest.triangles.size() == 1) {
return NEVER_COLLAPSE_COST;
}
// Degenerate case check
// Are we going to invert a face normal of one of the neighbouring faces?
// Can occur when we have a very small remaining edge and collapse crosses it
// Look for a face normal changing by > 90 degrees
for (Triangle triangle : src.triangles) {
// Ignore the deleted faces (those including src & dest)
if (!triangle.hasVertex(dest)) {
// Test the new face normal
Vertex pv0, pv1, pv2;
// Replace src with dest wherever it is
pv0 = (triangle.vertex[0] == src) ? dest : triangle.vertex[0];
pv1 = (triangle.vertex[1] == src) ? dest : triangle.vertex[1];
pv2 = (triangle.vertex[2] == src) ? dest : triangle.vertex[2];
// Cross-product 2 edges
tmpV1.set(pv1.position).subtractLocal(pv0.position);
tmpV2.set(pv2.position).subtractLocal(pv1.position);
//computing the normal
Vector3f newNormal = tmpV1.crossLocal(tmpV2);
newNormal.normalizeLocal();
// Dot old and new face normal
// If < 0 then more than 90 degree difference
if (newNormal.dot(triangle.normal) < 0.0f) {
// Don't do it!
return NEVER_COLLAPSE_COST;
}
}
}
float cost;
// Special cases
// If we're looking at a border vertex
if (isBorderVertex(src)) {
if (dstEdge.refCount > 1) {
// src is on a border, but the src-dest edge has more than one tri on it
// So it must be collapsing inwards
// Mark as very high-value cost
// curvature = 1.0f;
cost = 1.0f;
} else {
// Collapsing ALONG a border
// We can't use curvature to measure the effect on the model
// Instead, see what effect it has on 'pulling' the other border edges
// The more colinear, the less effect it will have
// So measure the 'kinkiness' (for want of a better term)
// Find the only triangle using this edge.
// PMTriangle* triangle = findSideTriangle(src, dst);
cost = 0.0f;
Vector3f collapseEdge = tmpV1.set(src.position).subtractLocal(dest.position);
collapseEdge.normalizeLocal();
for (Edge edge : src.edges) {
Vertex neighbor = edge.destination;
//reference check intended
if (neighbor != dest && edge.refCount == 1) {
Vector3f otherBorderEdge = tmpV2.set(src.position).subtractLocal(neighbor.position);
otherBorderEdge.normalizeLocal();
// This time, the nearer the dot is to -1, the better, because that means
// the edges are opposite each other, therefore less kinkiness
// Scale into [0..1]
float kinkiness = (otherBorderEdge.dot(collapseEdge) + 1.002f) * 0.5f;
cost = Math.max(cost, kinkiness);
}
}
}
} else { // not a border
// Standard inner vertex
// Calculate curvature
// use the triangle facing most away from the sides
// to determine our curvature term
// Iterate over src's faces again
cost = 0.001f;
Triangle[] triangles = this.triangles;
if (triangles == null || triangles.length < src.triangles.size()) {
triangles = new Triangle[src.triangles.size() + 16];
this.triangles = triangles;
}
int count = 0;
for (Triangle triangle2 : src.triangles) {
if (triangle2.hasVertex(dest)) {
triangles[count++] = triangle2;
}
}
for (Triangle triangle : src.triangles) {
float mincurv = 1.0f; // curve for face i and closer side to it
for (int index = 0; index < count; index++) {
Triangle triangle2 = triangles[index];
// Dot product of face normal gives a good delta angle
float dotprod = triangle.normal.dot(triangle2.normal);
// NB we do (1-..) to invert curvature where 1 is high curvature [0..1]
// Whilst dot product is high when angle difference is low
mincurv = Math.min(mincurv, (1.002f - dotprod) * 0.5f);
}
cost = Math.max(cost, mincurv);
}
}
// check for texture seam ripping
if (src.isSeam) {
if (!dest.isSeam) {
cost += meshBoundingSphereRadius;
} else {
cost += meshBoundingSphereRadius * 0.5;
}
}
// assert (cost >= 0);
return cost * src.position.distanceSquared(dest.position);
}
private static boolean find(Collection<Vertex> set, Vertex v) {
return set.contains(v);
}