-
Notifications
You must be signed in to change notification settings - Fork 35
/
ProposeMipmaps.java
304 lines (281 loc) · 11 KB
/
ProposeMipmaps.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
/*
* #%L
* BigDataViewer core classes with minimal dependencies.
* %%
* Copyright (C) 2012 - 2024 BigDataViewer developers.
* %%
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
* #L%
*/
package bdv.export;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import mpicbg.spim.data.generic.sequence.AbstractSequenceDescription;
import mpicbg.spim.data.generic.sequence.BasicViewSetup;
import mpicbg.spim.data.sequence.VoxelDimensions;
/**
* Propose number of mipmap levels, as well subsampling factors and chunk size
* for each level.
*
* <p>
* Choice of proposed chunksize is not based on any hard benchmark data
* currently. Chunk sizes are proposed such that chunks have power-of-two side
* lengths, are roughly square in world space, and contain close to (but not
* more than) a specified number of elements (4096 by default). It is very
* likely that more efficient choices can be found by manual tuning, depending
* on hardware and use case.
*
* @author Tobias Pietzsch
*/
public class ProposeMipmaps
{
/**
* Propose number of mipmap levels as well subsampling factors and chunk
* size for each level, for each setup of the given sequence.
*
* @param seq
* @return map from setup id to proposed mipmap settings
*/
public static Map< Integer, ExportMipmapInfo > proposeMipmaps( final AbstractSequenceDescription< ?, ?, ? > seq )
{
final HashMap< Integer, ExportMipmapInfo > perSetupExportMipmapInfo = new HashMap<>();
for ( final BasicViewSetup setup : seq.getViewSetupsOrdered() )
perSetupExportMipmapInfo.put( setup.getId(), proposeMipmaps( setup ) );
return perSetupExportMipmapInfo;
}
/**
* Propose number of mipmap levels as well subsampling factors and chunk
* size for each level, based on the image and voxel size of the given
* setup. Chunks contain close to (but not more than) 4096 elements.
*
* @param setup
* @return proposed mipmap settings
*/
public static ExportMipmapInfo proposeMipmaps( final BasicViewSetup setup )
{
return proposeMipmaps( setup, 4096 );
}
/**
* Propose number of mipmap levels as well subsampling factors and chunk
* size for each level, based on the image and voxel size of the given
* setup. Chunk sizes are proposed such that chunks have power-of-two side
* lengths, are roughly square in world space, and contain close to (but not
* more than) {@code maxNumElements}.
*
* @param setup
* @param maxNumElements
* @return proposed mipmap settings
*/
public static ExportMipmapInfo proposeMipmaps( final BasicViewSetup setup, final int maxNumElements )
{
final VoxelDimensions voxelSize = setup.getVoxelSize();
final double[] voxelScale = new double[ 3 ];
voxelSize.dimensions( voxelScale );
normalizeVoxelSize( voxelScale );
final int[] res = new int[] { 1, 1, 1 };
final long[] size = new long[ 3 ];
final ArrayList< int[] > resolutions = new ArrayList<>();
final ArrayList< int[] > subdivisions = new ArrayList<>();
// for ( int level = 0;; ++level )
while ( true )
{
resolutions.add( res.clone() );
setup.getSize().dimensions( size );
long maxSize = 0;
for ( int d = 0; d < 3; ++d )
{
size[ d ] = Math.max( 1, size[ d ] / res[ d ] );
maxSize = Math.max( maxSize, size[ d ] );
}
subdivisions.add( suggestPoTBlockSize( voxelScale, size, maxNumElements ) );
// System.out.println( " level " + level );
// System.out.println( " res: " + net.imglib2.util.Util.printCoordinates( res ) );
// System.out.println( " subdiv: " + net.imglib2.util.Util.printCoordinates( subdivisions.get( level ) ) );
// System.out.println( " size: " + net.imglib2.util.Util.printCoordinates( size ) );
// System.out.println( " voxelScale: " + net.imglib2.util.Util.printCoordinates( voxelScale ) );
// System.out.println( " vmax = " + vmax );
// System.out.println( " 4 vmax / 32 = " + ( 4 * vmax / 32 ) );
// System.out.println( " 1 / vmax = " + ( 1 / vmax ) );
if ( maxSize <= 256 )
break;
boolean anyDimensionChanged = false;
for ( int d = 0; d < 3; ++d )
{
if ( voxelScale[ d ] <= 2.0 && size[ d ] > 1 )
{
res[ d ] *= 2;
voxelScale[ d ] *= 2;
anyDimensionChanged = true;
}
}
if ( !anyDimensionChanged )
{
for ( int d = 0; d < 3; ++d )
res[ d ] *= 2;
}
normalizeVoxelSize( voxelScale );
}
return new ExportMipmapInfo( resolutions.toArray( new int[ 0 ][ 0 ] ), subdivisions.toArray( new int[ 0 ][ 0 ] ) );
}
/**
* Format {@code in[][]} array, such as resolutions or chunksizes
* definition, as a String (to be used in export dialog textfields).
*/
public static String getArrayString( final int[][] resolutions )
{
final StringBuilder sb = new StringBuilder();
sb.append( "{ " );
boolean first = true;
for ( final int[] res : resolutions )
{
if ( first )
first = false;
else
sb.append( ", " );
sb.append( String.format( "{%d,%d,%d}", res[ 0 ], res[ 1 ], res[ 2 ] ) );
}
sb.append( " }" );
return sb.toString();
}
/**
* Adjust voxelSize such that the smallest dimension is 1.0
*
* @param size
*/
public static void normalizeVoxelSize( final double[] size )
{
double minVoxelDim = Double.POSITIVE_INFINITY;
for ( int d = 0; d < 3; ++d )
minVoxelDim = Math.min( minVoxelDim, size[ d ] );
for ( int d = 0; d < 3; ++d )
size[ d ] /= minVoxelDim;
}
/**
* Propose block size such that
* <ol>
* <li>each dimension is power-of-two,</li>
* <li>number of elements is as big as possible, but not larger than
* {@code maxNumElements}</li>
* <li>and the block (scaled by the {@code voxelSize}) is as close to square
* as possible given constraints 1 and 2.</li>
* </ol>
*/
public static int[] suggestPoTBlockSize( final double[] voxelSize, final int maxNumElements )
{
return suggestPoTBlockSize( voxelSize, null, maxNumElements );
}
/**
* Propose block size such that
* <ol>
* <li>each dimension is power-of-two,</li>
* <li>number of elements is as big as possible, but not larger than
* {@code maxNumElements}</li>
* <li>and the block (scaled by the {@code voxelSize}) is as close to square
* as possible given constraints 1 and 2.</li>
* </ol>
* Additionally, the full {@code size[]} of the image limits the number of bits
* spent in a particular dimension. For example, if {@code size[2] = 3},
* then resulting block size will not exceed 4 in the Z dimension.
*/
public static int[] suggestPoTBlockSize( final double[] voxelSize, final long[] size, final int maxNumElements )
{
final int n = voxelSize.length;
final double[] bias = new double[ n ];
Arrays.setAll( bias, d -> 0.01 * ( n - d ) );
return suggestPoTBlockSize( voxelSize, size, maxNumElements, bias );
}
/**
* Propose block size such that
* <ol>
* <li>each dimension is power-of-two,</li>
* <li>number of elements is as big as possible, but not larger than
* {@code maxNumElements}</li>
* <li>and the block (scaled by the {@code voxelSize}) is as close to square
* as possible given constraints 1 and 2.</li>
* </ol>
*
* Determination works by finding real PoT for each dimension, then rounding
* down, and increasing one by one the PoT for dimensions until going over
* maxNumElements. Dimensions are ordered by decreasing fractional remainder
* of real PoT plus some per-dimension bias (usually set such that X is
* enlarged before Y before Z...)
*
* Optionally, if the full {@code size[]} of the image can be provided (
* {@code size != null}), this will limit the number of bits spent in a particular
* dimension. For example, if {@code size[2] = 3}, then resulting block size will
* not exceed 4 in the Z dimension.
*/
private static int[] suggestPoTBlockSize( final double[] voxelSize, final long[] size, final int maxNumElements, final double[] bias )
{
final int n = voxelSize.length;
final double[] shape = new double[ n ];
double shapeVol = 1;
for ( int d = 0; d < n; ++d )
{
shape[ d ] = 1 / voxelSize[ d ];
shapeVol *= shape[ d ];
}
final double m = Math.pow( maxNumElements / shapeVol, 1. / n );
final double sumNumBits = Math.log( maxNumElements ) / Math.log( 2 );
final double[] numBits = new double[ n ];
Arrays.setAll( numBits, d -> Math.log( m * shape[ d ] ) / Math.log( 2 ) );
final int[] intNumBits = new int[ n ];
Arrays.setAll( intNumBits, d -> Math.max( 0, ( int ) numBits[ d ] ) );
final int[] fullSizeBits = new int[ n ];
if ( size != null )
{
// fullSizeBits[d] contains the number of bits needed to fit the full size in dimension d
// (rounded up to next full bit)
Arrays.setAll( fullSizeBits, d -> Math.max( 0, ( int ) ( Math.log( size[ d ] - 1 ) / Math.log( 2 ) ) + 1 ) );
// if this is more than the (rounded down) number of bits allocated to block size in d,
// use the fullSizeBits[d] instead.
Arrays.setAll( intNumBits, d -> Math.min( intNumBits[ d ], fullSizeBits[ d ] ) );
}
for ( int sumIntNumBits = Arrays.stream( intNumBits ).sum(); sumIntNumBits + 1 <= sumNumBits; ++sumIntNumBits )
{
double maxDiff = Double.NEGATIVE_INFINITY;
int maxDiffDim = 0;
for ( int d = 0; d < n; ++d )
{
// if full image size was specified and we already fit the full image
// in dimension d, skip to the next dimension.
// Note that if we skip all dimensions in this way (because the block already fits the full image),
// we have maxDiffDim==0 and just keep increasing the X block size until we hit the limit.
if ( size != null && intNumBits[ d ] >= fullSizeBits[ d ] )
continue;
final double diff = numBits[ d ] - intNumBits[ d ] + bias[ d ];
if ( diff > maxDiff )
{
maxDiff = diff;
maxDiffDim = d;
}
}
++intNumBits[ maxDiffDim ];
}
final int[] blockSize = new int[ n ];
for ( int d = 0; d < n; ++d )
blockSize[ d ] = 1 << intNumBits[ d ];
return blockSize;
}
}