java - 如何在希尔伯特曲线空间上绕主轴进行旋转

Question

所以这是我从 http://www.tiac.net/~sw/2008/10/Hilbert/moore/hilbert.c 获取 Doug Moore 代码的问题并将其转换为 java，以便在我的硕士论文中使用，该论文是关于实现在光子映射射线赛车中存储光子的 LSH 方法。但问题就出在这里。由于我稍后在流程中使用希尔伯特索引的方式，因此使用了阈值。但阈值与希尔伯特曲线中的裂缝对齐，并在我的最终图像中造成伪影。根据研究，我完成的解决方案是围绕主轴稍微旋转希尔伯特曲线空间，但我不知道如何实现这一点。如果有人对此有任何想法，我现在陷入了困境，需要一些帮助。

temp = photonsBH[i].key = h.hilbert_c2i(三、十六、坐标);这条线是我如何调用希尔伯特函数的，它需要 3 个参数，第一个是维度数，第二个是位数，第三个是通过以下方程发送的点，以保持精度并将点移为正值。

xi = (int) (EPSILONSHIFT * photonsBH[i].pos[0]) + XYZ_shift[0];
yi = (int) (EPSILONSHIFT * photonsBH[i].pos[1]) + XYZ_shift[1];
zi = (int) (EPSILONSHIFT * photonsBH[i].pos[2]) + XYZ_shift[2];
coord[0] = new BigInteger("" + xi);
coord[1] = new BigInteger("" + yi);
coord[2] = new BigInteger("" + zi);

来自 hilbert.java 的代码

public class hilbert
{
    // BigInteger bitmask_t;
    // BigInteger halfmask_t;

    public int  size;

    public hilbert(int s)
    {
        size = s;
    }

    /*
     * #define adjust_rotation(rotation,nDims,bits) \ do { \ // rotation =
     * (rotation + 1 + ffs(bits)) % nDims; \ bits &= -bits & nd1Ones; \ while
     * (bits) \ bits >>= 1, ++rotation; \ if ( ++rotation >= nDims ) \ rotation
     * -= nDims; \ } while (0)
     */

    public BigInteger adjust_rotation(BigInteger rotation, BigInteger nDims,
            BigInteger bits, BigInteger nd1Ones)
    {

        bits = bits.and(nd1Ones.and(bits.negate()));
        while (bits.signum() > 0)
        {
            bits = bits.shiftRight(1);
            rotation = rotation.add(BigInteger.ONE);
        }
        if ((rotation = rotation.add(BigInteger.ONE)).compareTo(nDims) >= 0)
        {
            rotation = rotation.subtract(nDims);
        }

        return rotation;
    }

    // #define ones(T,k) ((((T)2) << (k-1)) - 1)
    public BigInteger ones(BigInteger k)
    {
        BigInteger r = new BigInteger("2");
        r = r.shiftLeft(k.subtract(BigInteger.ONE).intValue());
        r = r.subtract(BigInteger.ONE);
        // System.out.println("r:" + r);
        return r;
    }

    // #define rdbit(w,k) (((w) >> (k)) & 1)

    public BigInteger rdbit(BigInteger w, BigInteger k)
    {
        BigInteger r = w;
        r = r.shiftRight(k.intValue());
        r = r.and(BigInteger.ONE);
        return r;
    }

    // #define rotateRight(arg, nRots, nDims) ((((arg) >> (nRots)) | ((arg) <<
    // ((nDims)-(nRots)))) & ones(bitmask_t,nDims))
    public BigInteger rotateRight(BigInteger arg, BigInteger nRots,
            BigInteger nDims)
    {
        BigInteger r1 = arg.shiftRight(nRots.intValue());
        BigInteger r2 = nDims.subtract(nRots);
        BigInteger r3 = arg.shiftLeft(r2.intValue());
        BigInteger r4 = r1.or(r3);
        BigInteger r5 = r4.and(ones(nDims));
        return r5;
    }

    // #define rotateLeft(arg, nRots, nDims) ((((arg) << (nRots)) | ((arg) >>
    // ((nDims)-(nRots)))) & ones(bitmask_t,nDims))

    public BigInteger rotateLeft(BigInteger arg, BigInteger nRots,
            BigInteger nDims)
    {
        BigInteger r1 = arg.shiftLeft(nRots.intValue());
        BigInteger r2 = nDims.subtract(nRots);
        BigInteger r3 = arg.shiftRight(r2.intValue());
        BigInteger r4 = r1.or(r3);
        BigInteger r5 = r4.and(ones(nDims));
        return r5;
    }

    public BigInteger bitTranspose(BigInteger nDims, BigInteger nBits,
            BigInteger inCoords)
    {
        BigInteger nDims1 = nDims.subtract(BigInteger.ONE);
        BigInteger inB = nBits;
        BigInteger utB;
        BigInteger inFieldEnds = BigInteger.ONE;
        BigInteger inMask = ones(inB);
        BigInteger coords = BigInteger.ZERO;

        while ((utB = (inB.divide(new BigInteger("2")))).compareTo(BigInteger.ZERO) != 0)
        {
            BigInteger shiftAmt = nDims1.multiply(utB);
            BigInteger utFieldEnds = inFieldEnds.or((inFieldEnds.shiftLeft((shiftAmt.add(utB)).intValue())));
            BigInteger utMask = utFieldEnds.shiftLeft(utB.intValue()).subtract(utFieldEnds);
            BigInteger utCoords = BigInteger.ZERO;
            BigInteger d;

            if ((inB.and(BigInteger.ONE)).compareTo(BigInteger.ZERO) > 0)
            {
                BigInteger inFieldStarts = inFieldEnds.shiftLeft((inB.subtract(BigInteger.ONE)).intValue());
                BigInteger oddShift = shiftAmt.multiply(new BigInteger("2"));

                for (d = BigInteger.ZERO; d.compareTo(nDims) < 0; d = d.add(BigInteger.ONE))
                {
                    BigInteger in = inCoords.and(inMask);
                    inCoords = inCoords.shiftRight(inB.intValue());
                    BigInteger x1 = in.and(inFieldStarts);
                    BigInteger x3 = x1.shiftLeft(oddShift.intValue());
                    oddShift = oddShift.add(BigInteger.ONE);
                    coords = coords.or(x3);
                    in = in.and(inFieldStarts.not());
                    in = (in.or(in.shiftLeft(shiftAmt.intValue()))).and(utMask);
                    utCoords = utCoords.or(in.shiftLeft((d.multiply(utB)).intValue()));
                }
            }
            else
            {
                for (d = BigInteger.ZERO; d.compareTo(nDims) < 0; d = d.add(BigInteger.ONE))
                {
                    BigInteger in = inCoords.and(inMask);
                    inCoords = inCoords.shiftRight(inB.intValue());
                    in = (in.or(in.shiftLeft(shiftAmt.intValue()))).and(utMask);
                    utCoords = utCoords.or(in.shiftLeft((d.multiply(utB)).intValue()));
                }
            }
            inCoords = utCoords;
            inB = utB;
            inFieldEnds = utFieldEnds;
            inMask = utMask;
        }
        coords = coords.or(inCoords);
        return coords;

    }

    /*****************************************************************
     * hilbert_i2c
     * 
     * Convert an index into a Hilbert curve to a set of coordinates. Inputs:
     * nDims: Number of coordinate axes. nBits: Number of bits per axis. index:
     * The index, contains nDims*nBits bits (so nDims*nBits must be <=
     * 8*sizeof(bitmask_t)). Outputs: coord: The list of nDims coordinates, each
     * with nBits bits. Assumptions: nDims*nBits <= (sizeof index) *
     * (bits_per_byte)
     */

    public double[] hilbert_i2c(BigInteger nDims, BigInteger nBits,BigInteger index)
    {
        double[] coord = new double[3];
        if (nDims.intValue() > 1)
        {
            BigInteger coords;
            BigInteger nbOnes = ones(nBits);

            if (nBits.compareTo(BigInteger.ONE) > 0)
            {
                BigInteger nDimsBits = nDims.multiply(nBits);
                BigInteger ndOnes = ones(nDims);
                BigInteger nd1Ones = ndOnes.shiftRight(1);
                BigInteger b = nDimsBits;
                BigInteger rotation = BigInteger.ZERO;
                BigInteger flipBit = BigInteger.ZERO;
                BigInteger nthbits = ones(nDimsBits).divide(ndOnes);
                index = index.xor((index.xor(nthbits).shiftRight(1)));
                coords = BigInteger.ZERO;

                do
                {
                    BigInteger bits = index.shiftRight((b = b.subtract(nDims)).intValue()).and(ndOnes);
                    coords = coords.shiftLeft(nDims.intValue());
                    coords = coords.or(rotateLeft(bits, rotation, nDims).xor(flipBit));
                    flipBit = (BigInteger.ONE).shiftLeft(rotation.intValue());
                    rotation = adjust_rotation(rotation, nDims, bits, nd1Ones);
                } while (b.intValue() > 0);
                for (b = nDims; b.compareTo(nDimsBits) < 0; b = b.multiply(new BigInteger("2")))
                {
                    BigInteger c1 = coords.shiftRight(b.intValue());
                    coords = coords.xor(c1);
                }
                coords = bitTranspose(nBits, nDims, coords);
            }
            else
            {
                coords = index.xor(index.shiftRight(1));
            }

            for (int i = 0; i < coord.length; i++)
            {
                coord[i] = coords.and(nbOnes).doubleValue();
                coords = coords.shiftRight(nBits.intValue());
            }
        }
        else
        {
            coord[0] = index.doubleValue();
        }

        return coord;
    }

    /*****************************************************************
     * hilbert_c2i
     * 
     * Convert coordinates of a point on a Hilbert curve to its index. Inputs:
     * nDims: Number of coordinates. nBits: Number of bits/coordinate. coord:
     * Array of n nBits-bit coordinates. Outputs: index: Output index value.
     * nDims*nBits bits. Assumptions: nDims*nBits <= (sizeof bitmask_t) *
     * (bits_per_byte)
     */

    public BigInteger hilbert_c2i(BigInteger nDims, BigInteger nBits,BigInteger[] coord)
    {
        if (nDims.compareTo(BigInteger.ONE) > 0)
        {
            BigInteger index;
            BigInteger nDimsBits = nDims.multiply(nBits);
            BigInteger d;
            BigInteger coords = BigInteger.ZERO;

            for (int i = nDims.intValue(); i > 0; i--)
            {
                coords = coords.shiftLeft(nBits.intValue());
                coords = coords.or(coord[i - 1]);
            }

            if (nBits.compareTo(BigInteger.ONE) > 0)
            {
                BigInteger ndOnes = ones(nDims);
                BigInteger nd1Ones = ndOnes.shiftRight(1);
                BigInteger b = nDimsBits;
                BigInteger rotation = BigInteger.ZERO;
                BigDecimal rotation2 = new BigDecimal(""+ (-45.0 * (Math.PI/180))); 
                BigInteger flipBit = BigInteger.ZERO;
                BigInteger nthBits = ones(nDimsBits).divide(ndOnes);
                coords = bitTranspose(nDims, nBits, coords);
                coords = coords.xor(coords.shiftRight(nDims.intValue()));
                index = BigInteger.ZERO;

                do
                {
                    BigInteger bits = coords.shiftRight((b = b.subtract(nDims)).intValue()).and(ndOnes);
                    bits = rotateRight((flipBit.xor(bits)), rotation, nDims);
                    index = index.shiftLeft(nDims.intValue());
                    index = index.or(bits);
                    flipBit = (BigInteger.ONE).shiftLeft(rotation.intValue());
                    rotation = adjust_rotation(rotation, nDims, bits, nd1Ones);
                } while (b.compareTo(BigInteger.ZERO) > 0);

                index = index.xor(nthBits.shiftRight(1));
            }
            else
            {
                index = coords;
            }
            for (d = BigInteger.ONE; d.compareTo(nDimsBits) < 0; d = d.multiply(new BigInteger("2")))
            {
                index = index.xor((index.shiftRight(d.intValue())));
            }
            return index;
        }
        else
            return coord[0];
    }
}

Answer 1

嗯。好吧，我有一个想法，但我不确定这是否是你所要求的 - 它基本上看起来太简单了。我可能严重误解了你的问题。但是，在我看来，如果您想围绕主轴旋转空间(我假设第一个坐标是主轴)，您可以更改第一个代码块:

xi = (int) (EPSILONSHIFT * photonsBH[i].pos[0]) + XYZ_shift[0];
yi = (int) (EPSILONSHIFT * photonsBH[i].pos[1]) + XYZ_shift[1];
zi = (int) (EPSILONSHIFT * photonsBH[i].pos[2]) + XYZ_shift[2];
coord[0] = new BigInteger("" + xi);
coord[1] = new BigInteger("" + yi);
coord[2] = new BigInteger("" + zi);

进入以下其中一项。

我不确定你是否希望它在移动之前旋转，或者什么，或者你希望它围绕哪个点移动，但如果你在移动之前围绕原点旋转它，你可以使用

double theta = 0.1; // in radians
xi = (int) (EPSILONSHIFT * photonsBH[i].pos[0]) + XYZ_shift[0];
yi = (int) (EPSILONSHIFT * ((Math.cos(theta) * photonsBH[i].pos[1])-(Math.sin(theta) * photonsBH[i].pos[2]))) + XYZ_shift[1];
zi = (int) (EPSILONSHIFT * ((Math.sin(theta) * photonsBH[i].pos[1])+(Math.cos(theta) * photonsBH[i].pos[2]))) + XYZ_shift[2];
coord[0] = new BigInteger("" + xi);
coord[1] = new BigInteger("" + yi);
coord[2] = new BigInteger("" + zi);

我基本上只是应用 https://en.wikipedia.org/wiki/Rotation_%28mathematics%29 中的矩阵(或方程) 。 theta 是您想要的旋转程度(以弧度为单位)。请记住，当您转换回来时，您需要向后旋转。就像，这是我撤消上述功能的方法:

xi = coord[0].intValue();
yi = coord[1].intValue();
zi = coord[2].intValue();
photonsBH[i].pos[0] = (int)((xi - XYZ_shift[0]) / EPSILONSHIFT);
double yt = (yi - XYZ_shift[1]) / EPSILONSHIFT;
double zt = (zi - XYZ_shift[2]) / EPSILONSHIFT;
photonsBH[i].pos[1] = (int)((Math.cos(theta) * yt)+(Math.sin(theta) * zt));
photonsBH[i].pos[2] = (int)((-Math.sin(theta) * yt)+(Math.cos(theta) * zt));

我不知道四舍五入会如何影响您的结果。我也不知道你是否希望它在移动之前旋转，或者什么。事实上，我什至不知道这是否是您正在寻找的。也许它只会使你的代码崩溃。如果您想要一个在移位后旋转的版本，或者围绕某个点或其他东西旋转的版本，请告诉我。