通过 Renderscript 加速处理 Low Poly

Question

什么是 Low Poly？

德劳内

我在 java 中实现了 Delaunay 算法；但它很慢。在我的电脑中，将位图处理为低多边形大约需要 4-9 秒。在 android 移动设备中更糟。即使 if 我调整输入位图的大小也需要大约 1-2 分钟。

实施

 final class Delaunay {


private static int[][] supertriangle(List<int[]> vertices) {
    int xMin = Integer.MAX_VALUE;
    int yMin = Integer.MAX_VALUE;
    int xMax = Integer.MIN_VALUE;
    int yMax = Integer.MIN_VALUE;

    float dx, dy, dmax, xmid, ymid;


    for (int i = vertices.size() - 1; i >= 0; i--) {
        int[] p = vertices.get(i);
        if (p[0] < xMin) xMin = p[0];
        if (p[0] > xMax) xMax = p[0];
        if (p[1] < yMin) yMin = p[1];
        if (p[1] > yMax) yMax = p[1];
    }

    dx = xMax - xMin;
    dy = yMax - yMin;

    dmax = Math.max(dx, dy);

    xmid = (xMin + dx * 0.5f);
    ymid = (yMin + dy * 0.5f);

    return new int[][]{{(int) (xmid - 20 * dmax), (int) (ymid - dmax)},
            {(int) xmid, (int) (ymid + 20 * dmax)},
            {(int) (xmid + 20 * dmax), (int) (ymid - dmax)}};
}

private static Circumcircle circumcircle(List<int[]> vertices, int i, int j, int k) {
    int x1 = vertices.get(i)[0];
    int y1 = vertices.get(i)[1];
    int x2 = vertices.get(j)[0];
    int y2 = vertices.get(j)[1];
    int x3 = vertices.get(k)[0];
    int y3 = vertices.get(k)[1];


    int fabsy1y2 = Math.abs(y1 - y2);
    int fabsy2y3 = Math.abs(y2 - y3);

    float xc, yc, m1, m2, mx1, mx2, my1, my2, dx, dy;


    if (fabsy1y2 == 0) {
        m2 = -((float) (x3 - x2) / (y3 - y2));
        mx2 = (x2 + x3) / 2f;
        my2 = (y2 + y3) / 2f;
        xc = (x2 + x1) / 2f;
        yc = m2 * (xc - mx2) + my2;
    } else if (fabsy2y3 == 0) {
        m1 = -((float) (x2 - x1) / (y2 - y1));
        mx1 = (x1 + x2) / 2f;
        my1 = (y1 + y2) / 2f;
        xc = (x3 + x2) / 2f;
        yc = m1 * (xc - mx1) + my1;
    } else {
        m1 = -((float) (x2 - x1) / (y2 - y1));
        m2 = -((float) (x3 - x2) / (y3 - y2));
        mx1 = (x1 + x2) / 2f;
        mx2 = (x2 + x3) / 2f;
        my1 = (y1 + y2) / 2f;
        my2 = (y2 + y3) / 2f;
        xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
        yc = (fabsy1y2 > fabsy2y3) ?
                m1 * (xc - mx1) + my1 :
                m2 * (xc - mx2) + my2;
    }

    dx = x2 - xc;
    dy = y2 - yc;

    return new Circumcircle(i, j, k, xc, yc, (dx * dx + dy * dy));
}

private static void dedup(ArrayList<Integer> edges) {
    int a, b, m, n;
    for (int j = edges.size(); j > 0; ) {
        while (j > edges.size()) {
            j--;
        }
        if (j <= 0) {
            break;
        }
        b = edges.get(--j);
        a = edges.get(--j);

        for (int i = j; i > 0; ) {
            n = edges.get(--i);
            m = edges.get(--i);

            if ((a == m && b == n) || (a == n && b == m)) {
                if (j + 1 < edges.size())
                    edges.remove(j + 1);
                edges.remove(j);
                if (i + 1 < edges.size())
                    edges.remove(i + 1);
                edges.remove(i);
                break;
            }
        }
    }
}

static List<Integer> triangulate(final List<int[]> vertices) {
    int n = vertices.size();

    if (n < 3) {
        return new ArrayList<>();
    }

    Integer[] indices = new Integer[n];

    for (int i = n - 1; i >= 0; i--) {
        indices[i] = i;
    }


    Arrays.sort(indices, new Comparator<Integer>() {
        @Override
        public int compare(Integer lhs, Integer rhs) {
            return vertices.get(rhs)[0] - vertices.get(lhs)[0];
        }
    });
    int[][] st = supertriangle(vertices);

    vertices.add(st[0]);
    vertices.add(st[1]);
    vertices.add(st[2]);

    ArrayList<Circumcircle> open = new ArrayList<>();
    open.add(circumcircle(vertices, n, n + 1, n + 2));

    ArrayList<Circumcircle> closed = new ArrayList<>();

    ArrayList<Integer> edges = new ArrayList<>();

    for (int i = indices.length - 1; i >= 0; i--) {

        int c = indices[i];

        for (int j = open.size() - 1; j >= 0; j--) {

            Circumcircle cj = open.get(j);
            int[] vj = vertices.get(c);

            float dx = vj[0] - cj.x;
            float dy = vj[1] - cj.y;

            if (dx > 0 && dx * dx + dy * dy > cj.r) {
                closed.add(cj);
                open.remove(j);
                continue;
            }


            if (dx * dx + dy * dy - cj.r > 0) {
                continue;
            }

            edges.add(cj.i);
            edges.add(cj.j);
            edges.add(cj.j);
            edges.add(cj.k);
            edges.add(cj.k);
            edges.add(cj.i);

            open.remove(j);
        }

        dedup(edges);

        for (int j = edges.size(); j > 0; ) {
            int b = edges.get(--j);
            int a = edges.get(--j);

            int x1 = vertices.get(a)[0];
            int y1 = vertices.get(a)[1];
            int x2 = vertices.get(b)[0];
            int y2 = vertices.get(b)[1];
            int x3 = vertices.get(c)[0];
            int y3 = vertices.get(c)[1];

            boolean hasCircumcircle = true;
            if ((x1==x2)&&(x1==x3) || ((y1==y2)&&(y1==y3))){
                hasCircumcircle = false;
            }
            if (hasCircumcircle) {
                open.add(circumcircle(vertices, a, b, c));
            }
        }

        edges.clear();

    }

    for (int i = open.size() - 1; i >= 0; i--) {
        closed.add(open.get(i));
    }

    open.clear();

    ArrayList<Integer> out = new ArrayList<>();

    for (int i = 0; i <closed.size(); i++) {
        Circumcircle ci = closed.get(i);
        if (ci.i < n && ci.j < n && ci.k < n) {
            out.add(ci.i);
            out.add(ci.j);
            out.add(ci.k);
        }
    }
    return out;
}

private static class Circumcircle {
    public int i, j, k;
    float x, y, r;

    public Circumcircle(int i, int j, int k, float x, float y, float r) {
        this.i = i;
        this.j = j;
        this.k = k;
        this.x = x;
        this.y = y;
        this.r = r;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Circumcircle){
            Circumcircle circumcircle = (Circumcircle) obj;
            if (x==circumcircle.x && y==circumcircle.y && r==circumcircle.r)
                return true;
        }
        return super.equals(obj);
    }
}


}

C 中的 Delaunay 库

delaunay

这个库是用 C 写的。所以我认为它比 java 快。

我的问题

我想使用 RenderScript 来加速 processing.How 我可以输入一些点并得到三角形（只是输入点的索引）吗？

Answer 1

总结：你至少应该试试C版，看看效果如何。

RenderScript 是关于并行化问题，以便 CPU 或 GPU 上的许多不同工作单元可以处理数据。不过，这意味着您要在 RenderScript 中实现的算法必须最大限度地减少循环和条件。只看上面的代码就可以看到许多循环和 if 语句，在我看来这些语句不能很好地移植到 RenderScript。

快速搜索会显示许多关于并行化 Delaunay 的学术论文，因此尽管您可能必须研究什么对您的输入集有意义或什么是可接受的权衡。

通过 Renderscript 加速处理 Low Poly

Accelerate processing Low Poly by Renderscript

java

android

bitmap

renderscript

什么是 Low Poly？

德劳内

实施

C 中的 Delaunay 库

我的问题