[WS2021] Homework 5 Discussion

[changkun]

This thread is open for the discussion of homework 5.

[torantie]

Hi since I am again stuck after a pretty decent time investment i thought its time for a few questions again. :D Since i already struggled in the lecture with the QEM it's probably not surprising that I am still a little confused.^^

If i understood correctly the first part to calculate the quadric error and the position of the target vector was to calculate the vertex quadrics. I assumed this means I have to sum the vertex quadric for every face attached to a vertex.
The lecture slides description of the algorithm explains that next the edge quadrics should be calculated and stored in a priority queue.

I honestly do not know what "edge quadrics" means but i assumed that this is the quadric error. Based on the slides the quadric error can be calculated when i solve the linear equation:

So assuming that i understood everything correctly thus far, the quadric error calculation is where i am stuck. This leaves me with several questions:

1. Is my assumption to calculate the vertex quadrics by summing Qi of every face attached to the vertex correct (see code below) ?
2. Is "edge quadrics" == quadric error ?
3. How can i solve the linear equation programmatically ? Hints would be appreciated.^^

  simplify(reduceRatio) {
    // TODO: implement the QEM simplification
    const pq = new PriorityQueue( (a, b) => a.halfedge.quadricError > b.halfedge.quadricError)

    let vertexQuadricsSum = new Array(this.vertices.length)

    for(let i = 0; i < this.vertices.length; i++){
      let vertex = this.vertices[i]

      //calculate the sum of all neighbouring faces
      let QSum = new Matrix()
      vertex.faces((face) => {
        QSum.add(this.calculateQi(vertex, face))
      })
      vertexQuadricsSum[vertex.idx] = QSum
    }

    for(let j = 0; j < this.vertices.length; j++){
      let vertex = this.vertices[j]
      
      //compute edge quadrics?
      vertex.halfedges((halfedge) =>{
        let nextVertex = halfedge.next.vertex
        halfedge.quadricError = vertexQuadricsSum[vertex.idx] + vertexQuadricsSum[nextVertex.idx]
      })
    }

    //TODO
    this.halfedges.forEach(e => pq.enqueue(e))

    for(let k = 0; k < reduceRatio; k++){
      const halfedge = pq.dequeue()

    }
  }


  calculateQi(vertex, face) {
    //unit face normal
    let uFN = face.normal().unit()
    let negatedUnitFaceNormal = uFN.scale(-1)

    //h = -ni^T * xi. Last Dimension for the homogeneous normal vector (x,y,z,h)
    let h = vertex.position.x * negatedUnitFaceNormal.x
        + vertex.position.y * negatedUnitFaceNormal.y
        + vertex.position.z * negatedUnitFaceNormal.z
    //Qi=ni*ni^T vertex Quadrics
    let Qi = new Matrix(
        uFN.x * uFN * x, uFN.x * uFN.y, uFN.x * uFN.z, uFN.x * h,
        uFN.y * uFN * x, uFN.y * uFN.y, uFN.y * uFN.z, uFN.y * h,
        uFN.z * uFN * x, uFN.z * uFN.y, uFN.z * uFN.z, uFN.z * h,
        h * uFN * x, h * uFN.y, h * uFN.z, h * h)
    return Qi;
  }

[changkun]

You don't need any additional library. Inverting a 4x4 matrix is already provided in the mat.js.

I'll be honest i am still not completely sure how to implement this

Ok, here is one more hint:

class Edge {
  bestV() { // find the target vertex
    const q = this.quadric() // edge quadrics
    if (Math.abs(q.det()) > 1e-3) { // if the matrix is invertable
      // if you verify Q' and b' mentioned in above, then you will realize that Q' is the edge quadrics and b' is a zero vector.
      const v = q.inv().mulpos(new Vector()) 
      if (v.x !== NaN && v.y !== NaN && v.z != NaN) {
        return v
      }
    }

    // if not invertable, then greedy search directly on the edge
    const n = 16
    const a = this.halfedge.vertex.position
    const b = this.halfedge.next.vertex.position
    const d = b.sub(a)
    let beste = -1.0
    let bestv = new Vector()
    for (let i = 0; i <= n; i++) {
      const t = i / n
      const v = a.add(d.scale(t))
      const e = q.quadricError(v) // you need implement this yourself, which is calculating v^T q v :)
      if (beste < 0 || e < beste) {
        beste = e
        bestv = v
      }
    }
    return bestv
  }

[torantie]

That is a big hint xD. I honestly thought i needed more than the provided matrix operations.
Thank you for the help.

[changkun]

@torantie maybe you could try to think and try to submit your solution with a different strategy that deals with the case where the edge quadric is not invertible. The provided hint is just one possible way (which not entirely efficient, situation out of the theory :).

[torantie]

Good to know thanks i will try to come up with a different solution.

[changkun]

... where you learned analytical solution from high school

@torantie It just came to my mind that this sentence might be perceived in a very negative way, which I wrote it like "you don't know about high school knowledge". If this is the way you feel it, I must apologize and I absolutely didn't mean it in that way. I should rephrase the sentence to something like "where you have enough background knowledge but need some insights, maybe think more about this and that.. " since my original intention was to express that the equation is not that difficult when you figured it out, as you already did in your submission :)

[torantie]

I have another question is the edge error always lower or equal to zero?

[torantie]

one value is -0.43427315013730605 for example

[changkun]

they are close to 0 but that is like you mentioned probably because of the small modell

@torantie I think you don't fully get the numerical issue. We mentioned several times in the session about implementing these projects: relativity is important. What I mean by close is that compared to those positive values, if negative happens, then it is to compare them and see if it is just floating-point stability or real ones.

one value is -0.43427315013730605 for example

Then there must be an implementation error other than floating point issue.

[changkun]

one value is -0.43427315013730605 for example

I just tested a simple cube from my implementation, the error is expected to 2.666666666. As always, don't work directly on large meshes, always start from simple ones...

[krasnor]

I just tested a simple cube from my implementation, the error is expected to 2.666666666.

Is 2.66 the max error or should all vertices have this error?
Did the tested cube have all its sides closed?

If I use a fully closed cube (12 faces) then the error will always be 1.
When trying it with the cube.obj from Homework 4 (the one where one side is left open),
the results seem to go in the right direction (not quite sure about the 0 error value, I'll have to take a closer look tomorrow):

[changkun]

@krasnor I don't remember the detail of the 2.66 but I think I did the following for the quick test:

1. a single cube created from Blender, then applied a triangulation modifier
2. export the triangle mesh as obj file
3. set reduction ratio as 0.5 then all decimated edges have an error of 2.66

Since the edge error might be different after edge collapse depends on the order of decimation for those edges that have the same error, but your first collapse should have 2.66 for the cube and others might be different.

[krasnor]

I'm not sure if it is intentional, but in Matrix.add() x30 and x01 seem not to be calculated correctly?

Shouldn't this be the following?

    mm.x30 = this.x30 + m.x30
    mm.x01 = this.x01 + m.x01 

After changing it, the results did not change much for me (seem to still have somewhere else an error)

[changkun]

Oppos. This is super embarrassing.. might cause by vim bindings... Sorry again

[krasnor]

No problem :)
Small typos can always happen

[changkun]

Close due to the end of the submission period.