My aim is to smooth the terrain in a video game. Therefore I contrived an algorithm that makes use of Bézier curves of different orders. But this algorithm is defined in a two dimensional space for now.

To shift it into the third dimension I need to somehow combine the Bézier curves. Given two curves in each two dimensions, how can I combine them to build a surface?

I thought about something like a curve of a curve. Or maybe I could multiply them somehow. How can I combine them to cause the wanted behavior? Is there a common approach?

input and output of the working algorithm in 2d

In the image you can see the input, on the left, and the output, on the right, of the algorithm that works in a two dimensional space. For the real application there is a three dimensional input.

The algorithm relays only on the adjacent tiles. Given these it will define the control points of the mentioned Bézier curve. Additionally it marks one side of the curve as inside the terrain and the other as outside.

  • $\begingroup$ I am not so sure Bézier curves would be easy to fit. Easier would be some interpolation scheme, like cubic interpolation. I would try an inverse discrete wavelet transform interpreting as low-low-low frequency band. Potentially with applying some regularization. Or you could just build a big equation system where you push function values towards the edges and regularize for first and second order differentials. The last method is so powerful you can fuse the solution it to parametric functions like polynomials if you want to. $\endgroup$ – mathreadler Aug 19 '18 at 8:02

You can define a bezier-area by $$x(\lambda,\mu) = \sum^m_{i=0}\sum^n_{j=0}B_{im}(\lambda)B_{jn}(\mu)p_{ij}$$

with $\lambda,\mu\in[0,1]$, $B_{im}$ are the Bernstein polynomials and $p_{ij}$ are the given points.

Note: For this approach you need a grid of points.


I would not use Bezier curves for this. Too much work to find the end-points and you end up with a big clumsy polynomial.

I would build a linear least squares problem minimizing the gradient (smoothing the slopes of hills).

First let's split each pixel into $6\times 6$ which will give the new smoothed resolution (just an example, you can pick any size you would like).

Now the optimization problem $${\bf v_o} = \min_{\bf v} \{\|{\bf D_x(v+d)}\|_F^2+\|{\bf D_y(v+d)}\|_F^2 + \epsilon\|{\bf v}\|_F^2\}$$

where $\bf d$ is the initial pixely blocky surface, and $\bf v$ is the vector of smoothing change you want to do.

Already after 2 iterations of a very fast iterative solver we can get results like this:

enter image description here

After clarification from OP, I realized it is more this problem we have ( but in 3D ).

enter image description here

Now the contours (level sets) to this smoothed binary function can be used to create an interpolative effect: enter image description here

  • $\begingroup$ Hey, thanks for the interesting answer after such a long time. I'm still sometimes thinking about this problem because I didn't come up with a satisfactory solution yet. One motivation of only considering the 26 neighboring cells for the shape of each block was that it will give make it easier for users to still infer the underlying block structure. It would also allow to precompute the meshes for common situations (for many of the $2^{26}$ possible neighborhoods the inner block is not visible). Could you think of a way to incorporate this constraint into your approach? $\endgroup$ – danijar Aug 25 '18 at 13:46
  • $\begingroup$ Oh wow, I did not even look at the date when I posted but I see now. Yes I should maybe not have expected you were still looking for an answer. Ah so you have real 3D with three dimensional blocks and not just the height values for a surface of some solid object? Well you could apply the same approach in 3D, I think. Refine the mesh where you copy the values from the bigger mesh, and then minimize a 3D gradient and then threshold the result. $\endgroup$ – mathreadler Aug 25 '18 at 13:57
  • $\begingroup$ Well, glad you posted! Yes, I have a 3D grid of binary values. My questions was if you can think of a way for the resulting mesh of each cell to only depend on the adjacent cells. This would be useful for many reasons. For example, it allows loading additional chunks once they come into view, without having to change the smoothing of the existing parts. I also suspect that a global optimization will be too slow for millions of blocks as used in the game. $\endgroup$ – danijar Aug 25 '18 at 14:09
  • 1
    $\begingroup$ Ah ok. Yes for an exact solution it will be too slow. But this is computer graphics for entertainment and not safety critical software for medicine or something like that. Which means you can cheat with approximation as much you want as long as the result looks good ;) All iterative solvers will only be dependent on local values, you will need a maximum of a few iterations and they will basically be as fast as a couple of convolutions which is definitely fast enough. $\endgroup$ – mathreadler Aug 25 '18 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.