Как выполнить вращение в пространстве кривой Гильберта вокруг первичной оси
Итак, вот проблема, я взял код Дуга Мура с http://www.tiac.net/~sw/2008/10/Hilbert/moore/hilbert.c и преобразовал его в Java для использования в моей магистерской диссертации по реализации метод LSH для хранения фотонов в гонщике Photon Mapped Ray. Но здесь кроется проблема. Из-за способа, которым я использую индексы Гильберта позже, в моем процессе используются пороги. Но пороги выровнены с трещинами на кривой Гильберта и вызывают артефакты на моем окончательном изображении. В соответствии с исследованиями, которые я сделал, решение этой проблемы состоит в том, чтобы слегка повернуть пространство кривой Гильберта вокруг первичной оси, но я понятия не имею, как этого добиться. Если у кого-то есть какие-либо мысли по этому поводу, я чрезвычайно застрял на данный момент и мог бы помочь
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];
}
}
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));
Я не знаю точно, как округление повлияет на ваши результаты. Также я не знаю, хотите ли вы, чтобы он был повернут перед сдвигом, или как. На самом деле, я даже не знаю, действительно ли это то, что вы ищете. Может быть, это просто сломает ваш код. Дайте мне знать, если вы хотите версию, которая вращается после сдвига, или вращается вокруг определенной точки или чего-то еще.