Optimization with ceiling function to determine voxel size

Question

I am trying to calculate the voxel size for a voxel grid which must enclose a $3$D object with real dimensions $\alpha$,$\beta$,$\gamma$ ($\ge 0$).

The amount of voxels may be at most $\theta$ (integer, $\gt 0$). The real cell size I am looking for is $\omega$ ($\gt 0$).

So I am looking to maximize the following function:

$$f(\omega) = \lceil {\frac {\alpha}\omega} \rceil \lceil {\frac {\beta}\omega} \rceil \lceil {\frac {\gamma}\omega} \rceil $$

Where

$$f(\omega) \le \theta$$

The dimensions ($\alpha, \beta, \gamma$) may be equal to $0$, but in this case I can just use a formula without the corresponding ceiled fraction.

Does anyone know if there is a way to calculate an exact or approximate answer to this ?

Thanks in advance for your help.

Cheers,

Ben

Answer 1

I would start by ignoring the ceilings. You can then write $$\frac {\alpha \beta \gamma}{\omega^3}=\theta\\\omega=\left(\frac {\alpha \beta \gamma}{\theta}\right)^{1/3}$$ This will be too small unless your dimensions are all multiples of the $\omega$ you find. Now compute the number of voxels in each dimension by $L=\lceil \frac \alpha \omega \rceil$ and the corresponding formulas in each other dimension, getting $H,W$. If you reduce each one by $1$ you will have $(L-1)(H-1)(W-1)$ voxels, which will be less than $\theta$, so there are eight possibilities for numbers of voxels in each dimension. Compute which ones have an acceptable number of voxels, the $\omega$ that corresponds to each, and take the smallest.

Answer 2

I didn't get around to posting the method I used, but here it is.

Problem

Minimize $cell\_size$
Subject to

$f(cell\_size, (n_n)) <= t$

Where

$f(x, (y_n)) = \prod_{i} {\lceil \frac {y_i} {x} \rceil}$

$x$ is a positive number
$y$ is a sequence of positive numbers
$t$ is a number, larger than or equal to 1

Solution

Without loss of generality, it is assumed that $(n_n)$ is monotonically increasing.

Let

$s$ be the solution to the problem
$c_i$ be $\lceil \frac {n_i} {s} \rceil$
$m_i$ be the smallest cell size for which $\lceil \frac {n_i} {m_i} \rceil = c_i$

The solution is determined by solving $\left|n\right|$ subproblems, where each step i determines $c_i$ and $m_i$.

Finally

$s = max(\{m_0,..., m_{\left|m\right|-1}\})$

Subproblem k

Find $m_k$

Solution

Let

$(n0_n) = (n_k,...,n_{\left|n\right|-1})$
$t0 = \frac {t} {\prod_{i=0}^{k-1} {c_i}}$

Solving

$\prod_{i} {\frac {n0_i} {w}} = t0$

for $w$ and clamping it to the currently known feasible region using

$w = max(w, m_0,...,m_{k-1}))$

gives us our starting value.

Using the following

$\prod_{i} {\lceil \frac {n0_i} {w} \rceil - 1} < \prod_{i} { \frac {n0_i} {w} } <= \prod_{i} {\lceil \frac {n0_i} {w} \rceil}$

And because $n0$ is monotonically increasing, it can be seen that if there exists a number $u$, where $u > w$ and maximized, subject to

$\lceil \frac {n0_0} {w} \rceil - \lceil \frac {n0_0} {u} \rceil = 1$,

this will result in

$\lceil \frac {n0_i} {w} \rceil - \lceil \frac {n0_i} {u} \rceil >= 1$

It follows that

$f(u) < t$

If such an $u$ does not exist, $\lceil \frac {n0_0} {w} \rceil = 1$ and $w$ can be increased indefinitely, decreasing $f$ until it is smaller than or equal to $t$. So in this case, $c_k$ = $\lceil \frac {n0_0} {w} \rceil$.

If such an $u$ exists, $\lceil \frac {n0_0} {w} \rceil > 1$ and $c_k$ is either $\lceil \frac {n0_0} {w} \rceil$ or $\lceil \frac {n0_0} {w} \rceil - 1$. This can be easily determined by evaluating $f$ at $v$, where $v$ is the largest value where $\lceil \frac {n0_0} {v} \rceil = \lceil \frac {n0_0} {w} \rceil$, i.e. right after the boundary between the cell size ranges corresponding to the ceiled fractions. The minimum cell size for this ceiled fraction is calculated using

$m_k = \frac {n0_k} {c_k}$