package Algorithms;
import Pixels.Planes;import Utils.*;import java.io.InputStream;import java.util.concurrent.ExecutionException;
public class Lee94 { public static final int MAX_BREADTH = 8;
static final int IN_PLACE_THRESHOLD = 250;
static final byte[] simplePointsLut = loadSimplePointsLut();
static final int[] eulerLut1 = new int[] { 23, 24, 14, 15, 20, 21, 12, 25, 22, 16, 13, 24, 21, 15, 17, 20, 9, 12, 18, 21, 10, 19, 22, 18, 21, 11, 13, 10, 6, 14, 7, 15, 3, 12, 4, 8, 7, 16, 15, 5, 4, 13, 0, 9, 3, 12, 1, 10, 4, 2, 1, 11, 10, 5, 4, 13 };
static final int[] eulerLut2 = new int[] { 1, -1, -1, 1, -3, -1, -1, 1, -1, 1, 1, -1, 3, 1, 1, -1, -3, -1, 3, 1, 1, -1, 3, 1, -1, 1, 1, -1, 3, 1, 1, -1, -3, 3, -1, 1, 1, 3, -1, 1, -1, 1, 1, -1, 3, 1, 1, -1, 1, 3, 3, 1, 5, 3, 3, 1, -1, 1, 1, -1, 3, 1, 1, -1, -7, -1, -1, 1, -3, -1, -1, 1, -1, 1, 1, -1, 3, 1, 1, -1, -3, -1, 3, 1, 1, -1, 3, 1, -1, 1, 1, -1, 3, 1, 1, -1, -3, 3, -1, 1, 1, 3, -1, 1, -1, 1, 1, -1, 3, 1, 1, -1, 1, 3, 3, 1, 5, 3, 3, 1, -1, 1, 1, -1, 3, 1, 1, -1 };
public static class Params implements ISliceCompute { public final IntVector finalSimplePoints; public final RefVector<IntVector> points3d; public final int[] offs;
public byte[] planes; public int width; public int height; public int breadth;
public Params() { this.finalSimplePoints = new IntVector(); this.points3d = new RefVector<IntVector>(IntVector.class); this.offs = new int[3]; }
public void setup(byte[] planes, int width, int height, int breadth) { this.planes = planes; this.width = width; this.height = height; this.breadth = breadth;
int reservedCap = Math.max(width * height / 32, 384); if (finalSimplePoints.buf == null) finalSimplePoints.buf = new int[reservedCap]; }
public void prepare(int border) { offs[0] = 0; offs[1] = 0; offs[2] = 0;
if (border == 1 || border == 2) offs[1] = ((border-1) * 2) - 1; else if (border == 3 || border == 4) offs[0] = 1 - ((border-3) * 2); else if (border == 5 || border == 6) offs[2] = 1 - ((border-5) * 2);
finalSimplePoints.size = 0; }
@Override public void initSlices(int nSlices) { points3d.resize(nSlices);
int reservedCap = Math.max(width * height / 32, 384) / nSlices; for (int i = 0; i < nSlices; i++) { if (points3d.buf[i] == null) points3d.buf[i] = new IntVector(reservedCap); points3d.buf[i].size = 0; } }
@Override public Object computeSlice(int sliceIdx, int start, int length) { IntVector vertices = points3d.buf[sliceIdx]; vertices.size = 0;
for (int y = 0; y < height; y++) { boolean yIsBorder = (y == 0 && offs[1] == -1) || (y == height-1 && offs[1] == 1);
for (int x = start; x < start+length; x++) { boolean xIsBorder = (x == 0 && offs[0] == -1) || (x == width-1 && offs[0] == 1);
for (int z = 0; z < breadth; z++) { if (((planes[x + width*y] >>> z) & 1) == 0) continue;
boolean zIsBorder = (z == 0 && offs[2] == -1) || (z == breadth-1 && offs[2] == 1);
if ( xIsBorder || yIsBorder || zIsBorder || ((planes[(x + offs[0]) + width * (y + offs[1])] >>> (z + offs[2])) & 1) == 0 ) { int neighborBits = AnalyzeSkeleton2.getBooleanNeighborBits(planes, width, height, breadth, x, y, z); if (Integer.bitCount(neighborBits) != 1 && isSimplePoint(neighborBits) == 1 && isEulerInvariant(neighborBits)) { vertices.add(x); vertices.add(y); vertices.add(z); } } } } }
return null; }
@Override public void finishSlice(ISliceCompute.Result result) { IntVector vec = points3d.buf[result.idx]; finalSimplePoints.add(vec.buf, 0, vec.size); } }
public static void skeletonize( byte[] planes, ISliceRunner runner, int maxWorkers, Object[] layersObj, int width, int height, int bitDepth, int maxSkelIterations ) throws ExecutionException { final int breadth = layersObj.length;
byte[][] layersByte = null; short[][] layersShort = null; int[][] layersInt = null; float[][] layersFloat = null;
switch (bitDepth) { case 8: layersByte = Planes.combine8(planes, width, height, layersObj); break; case 16: layersShort = Planes.combine16(planes, width, height, layersObj); break; case 24: layersInt = Planes.combineRgb(planes, width, height, layersObj); break; case 32: layersFloat = Planes.combine32(planes, width, height, layersObj); break; default: throw new RuntimeException("Unexpected bit depth (" + bitDepth + ")"); }
Params params = new Params(); params.setup(planes, width, height, breadth);
boolean anyChanged; int step = 0; do { anyChanged = false; for (int border = 1; border <= 6; border++) { boolean wasThinned = thin(params, runner, maxWorkers, border); anyChanged = anyChanged || wasThinned; } } while (anyChanged && (maxSkelIterations <= 0 || ++step < maxSkelIterations));
params = null; }
static boolean thin( Params params, ISliceRunner runner, int maxWorkers, int border ) throws ExecutionException { params.prepare(border);
runner.runSlices( params, maxWorkers, params.width, IN_PLACE_THRESHOLD - 1 );
final IntVector results = params.finalSimplePoints; final int width = params.width; final int height = params.height; final int breadth = params.breadth; final byte[] planes = params.planes;
boolean anyChange = false; for (int i = 0; i < results.size; i += 3) { int x = results.buf[i]; int y = results.buf[i+1]; int z = results.buf[i+2]; int pos = x + y*width; int simple = isSimplePoint(AnalyzeSkeleton2.getBooleanNeighborBits(planes, width, height, breadth, x, y, z));
planes[pos] = (byte)((planes[pos] & ~(1 << z)) | ((simple ^ 1) << z)); anyChange = anyChange || (simple == 1); }
return anyChange; }
static boolean isEulerInvariant(int neighborBits) { int euler = 0; int idx = 0; for (int i = 0; i < eulerLut1.length; i++) { idx = (idx << 1) | ((neighborBits >> eulerLut1[i]) & 1); if (i % 7 == 6) { euler += eulerLut2[idx]; idx = 0; } }
return euler == 0; }
static int isSimplePoint(int neighborBits) { return (simplePointsLut[neighborBits >> 3] >> (7 - (neighborBits & 7))) & 1; }
static byte[] loadSimplePointsLut() { byte[] buffer = new byte[1 << 23]; try (InputStream in = Lee94.class.getResourceAsStream("/lee94-simple-points.bin")) { if (in == null) throw new Exception("Error: could not open lee94-simple-points.bin"); int off = 0; while (off < buffer.length) { int res = in.read(buffer, off, buffer.length - off); if (res <= 0) break; off += res; } if (off < buffer.length) throw new Exception("Error: only read " + off + " / " + buffer.length + " bytes from lee94-simple-points.bin"); } catch (Exception ex) { throw new RuntimeException(ex); } return buffer; }}
