そこで、 http://www.tiac.net/~sw/2008/10/Hilbert/moore/hilbert.cから Doug Moore コードを取得し、実装に関する修士論文で使用するために Java に変換した問題を次に示します。フォトン マップ レイ レーサーにフォトンを保存するための LSH メソッド。しかし、ここに問題があります。プロセスの後半でヒルベルト インデックスを利用しているため、しきい値が使用されています。しかし、しきい値がヒルベルト曲線の亀裂と一致しており、最終的な画像にアーティファクトが発生しています。私が行った調査によると、これに対する解決策は、主軸を中心にヒルベルト曲線空間をわずかに回転させることですが、これを達成する方法についての手がかりがありません。誰かがこれについて考えているなら、私は現時点で非常に立ち往生しており、助けを求めることができます.
temp = photonsBH[i].key = h.hilbert_c2i(THREE, SIXTEEN, coord); この行は、ヒルベルト関数を呼び出す方法です。1 つ目は次元数、2 つ目はビット数、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];
}
}