3
$\begingroup$

NB please : executable use cases are available at the end of this question. I begin this question by showing you the problems of my program, then I explain how the latter works, and finally I end up with these both executable use cases.

What I want to do

I want to draw the bottom face of a cube. To do that, I interpolate between the 4 vertices of this face. I use two kinds of interpolation :

  1. Linear

  2. Cosine

I know it's typically the aim of GPUs, but I wanted to implement it myself to learn and try the "deep" mechanisms of 3D rendering.

Results

Each point of the following both pictures are interpolated between the 4 vertices of the bottom face (except the 8 vertices of my cube).

With linear interpolation

It's OK, no problem.

enter image description here

With cosine interpolation

Error. As you can see, there is some weird problem : face's points are inclined towards left.

enter image description here

How do I interpolate between 4 points ?

I test all the combinations of interpolation's weights and, if the sum of the weights equals 1, I draw the resulting point. I know this method is not very good (a lot of consumption of CPU and RAM), and there are P duplicates. But this problem is (1) secondary and (2) out of the range of this StackOverflow question.

In other words : the definition of the interpolation between 4 points is : P = aA + bB + cC + dD. a + b + c + d must equals 1 to draw P, otherwise it's not drawn. (a;b;c;d) \in [0;1]^4 by the way.

A concrete example is (step = 1) :

P = 0a + 0b + 0c + 0d is NOT drawn

P = 0a + 0b + 0c + 1d is drawn

P = 0a + 0b + 1c + 0d is drawn

P = 0a + 0b + 1c + 1d is NOT drawn

etc. ("I test all the combinations"). (Last is : P = 1a + 1b + 1c + 1d, which is not drawn).

To test all these combinations, I iterates on the weights, with a step, using recursion.

Case of the linear interpolation

The above definition doesn't change : P = aA + bB + cC + dD.

Case of the cosine interpolation

The above definition does change : P = aA + bB + cC + dD becomes P = a'A + b'B + c'C + d'D, with : a' = 0.5(1 - cos(a * \pi)) and the idea is the same for the three other weights.

This new definition is not random, I could explain how I found it, but it's out of the range of this topic (in résumé : a simple remap of the cosine function).

Question

Why does it works well with the linear interpolation, and not the cosine one ? Indeed, the cosine face's points are inclined towards left.

By the way : interpolations between two points work well

Linear and cosine interpolations both work very well when used between two points, as you can see below.

Linear interpolation

It's OK, no problem.

enter image description here

Cosine interpolation

It's OK, no problem.

enter image description here

Implementation and Executable

I wrote the program in Scala. First I show you the functions, then two use cases you can execute along with the given functions.

Tests all the combinations of interpolations between n points of k coordinates

def computeAllPossibleInterpolatedPoints(step : Double, points : Seq[Seq[Double]], transform: (Double) => Double) : Seq[Seq[Double]] = {
  var returned_object : Seq[Seq[Double]] = Seq.empty[Seq[Double]]
  recursiveInterpolation(0, Seq.empty[Double])

  def recursiveInterpolation(current_weight_id : Int, building_weights : Seq[Double]) : Unit = {

    (.0 to 1.0 by step).foreach(current_step => {
      if (current_weight_id < points.size - 1) {
        recursiveInterpolation(current_weight_id + 1, building_weights :+ current_step)
      } else {
        val found_solution = building_weights :+ current_step
        if(BigDecimal(found_solution.sum).setScale(5, BigDecimal.RoundingMode.HALF_UP).toDouble == 1.0) {
          returned_object = returned_object :+ interpolation(found_solution, points, transform)
        }
      }
    })
  }

  returned_object
}

Interpolates between n points of k coordinates

def interpolation(weights: Seq[Double], points: Seq[Seq[Double]], transform: (Double) => Double) : Seq[Double] = {
  if(BigDecimal(weights.sum).setScale(5, BigDecimal.RoundingMode.HALF_UP).toDouble != 1) {
    println("ERROR : `SUM(weights) != 1`. Returning `null`.")
    return null
  }
  if(weights.exists(weight => BigDecimal(weight).setScale(5, BigDecimal.RoundingMode.HALF_UP).toDouble < 0)
    ||
    weights.exists(weight => BigDecimal(weight).setScale(5, BigDecimal.RoundingMode.HALF_UP).toDouble > 1)) {
    println("ERROR : `EXISTS(weight) / weight < -1 OR weight > 1`. Returning `null`.")
    return null
  }

  weights.map(transform).zip(points).map(
    weight_point => weight_point._2.map(coordinate => weight_point._1 * coordinate)
  ).reduce((point_a : Seq[Double], point_b : Seq[Double]) => point_a.zip(point_b).map(coordinate_points => coordinate_points._1 + coordinate_points._2))
}

Interpolation functions

def linear(weight : Double) : Double = {
  weight
}

def cosine(weight : Double) : Double = {
  (1 - Math.cos(weight * Math.PI)) * 0.5
}

Two use cases : between 2 points, each made of 2 coordinates (first use case : linear interpolation, second use case : cosine interpolation)

Note that you can add 2 new points to each of the following functions, to interpolate a face instead of a segment (for now, the below code indeed interpolates points of a segment).

val interpolated_points : Seq[Seq[Int]] = interpolator.computeAllPossibleInterpolatedPoints(0.05, Seq(Seq(22, 22), Seq(33, 33)), interpolator.linear).map(_.map(_.intValue()))

val interpolated_points : Seq[Seq[Int]] = interpolator.computeAllPossibleInterpolatedPoints(0.05, Seq(Seq(22, 22), Seq(33, 33)), interpolator.cosine).map(_.map(_.intValue()))
$\endgroup$
0

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.