[WS2021] Homework 4 Discussion

[changkun]

This thread is open for the discussion of homework 4.

[torantie]

Hey i am currently trying to calculate the boundary u v coordinates and iam stuck. Currently not even the checkerboard texture is being rendered.

At the start i thought it wouldn't render because of an error (u v coordniates were not initialized). So i at least gave them a value so i could see the checkerboard texture.

Unfortunately that didn't work (could still not see the checkerboard). So i thought i would just try to implement the flatten algorithm so that maybe the checkerboard texture would show up.

  flatten(boundaryType, laplaceWeight) {
    // TODO: implement the Tutte's barycentric embedding algorithm.
    //
    // Hint:
    // 1. check if the mesh contains a boundary
    let boundaryHalfEdgesLength = this.boundaries.length
    if(boundaryHalfEdgesLength == 0)
      return
    // 2. compute boundary uv coordinates depending on the boundary type
    switch (boundaryType) {
      case "disk":

      case "rect":
        let pointDistance = 400/boundaryHalfEdgesLength
        let prevX = 0
        let prevY = 0
        for(let i = 0; i<boundaryHalfEdgesLength; i++){
          if(prevX < 100 && prevY == 0){
            this.boundaries[i].vertex.uv.x= prevX + pointDistance
            this.boundaries[i].vertex.uv.y= 0
          }
          else if(prevX >= 100 && prevY < 100){
            this.boundaries[i].vertex.uv.x= prevX
            this.boundaries[i].vertex.uv.y= prevY + pointDistance
          }else if(prevX >= 100 && prevY >= 100){
            this.boundaries[i].vertex.uv.x= prevX - pointDistance
            this.boundaries[i].vertex.uv.y= prevY
          }else{
            this.boundaries[i].vertex.uv.x= prevX
            this.boundaries[i].vertex.uv.y= prevY - pointDistance
          }
          prevX = this.boundaries[i].vertex.uv.x
          prevY = this.boundaries[i].vertex.uv.y
        }

        break;
    }
    let numberOfVertices = this.vertices.length
    let u = DenseMatrix.zeros(numberOfVertices, 1)
    let v = DenseMatrix.zeros(numberOfVertices, 1)
    for(let i = 0; i < this.boundaries.length; i++){
      let h = this.boundaries[i];
      u.set(h.vertex.uv.x, h.vertex.idx, 0)
      v.set(h.vertex.uv.y, h.vertex.idx, 0)
    }

    // 3. compute matrix depending on the laplacian weight type
    let L = this.laplaceMatrix(laplaceWeight)

    let luDecomposition = L.lu()

    // 4. solve linear equation and assing computed uv as vertex uv
    let solvedSquareU= luDecomposition.solveSquare(u)
    let solvedSquareV= luDecomposition.solveSquare(v)

    for (let i = 0; i < numberOfVertices; i++) {
      let resultU = solvedSquareU.get(i, 0)
      let resultV = solvedSquareV.get(i, 0)
      let currentUV = this.vertices[i].uv
      if(!this.vertices[i].halfedge.onBoundary){
        currentUV.x = resultU
        currentUV.y = resultV
      }
    }
  }

  laplaceMatrix(weightType) {
    const numberOfVertices = this.vertices.length
    let weightTriplet = new Triplet(numberOfVertices, numberOfVertices)

    for (const vert of this.vertices) {
      const i = vert.idx
      let sum = 1e-8 // Tikhonov regularization to get strict positive definite
      if(!vert.halfedge.onBoundary){
        vert.halfedges(h => {
          let w = 0

          switch (weightType) {
            case 'uniform':
              w = 1
              break
            case 'cotan':
              w = (h.cotan() + h.twin.cotan())/2
          }

          sum += w
          //console.log("Value: "+w+" Position: ("+ i+","+h.twin.vertex.idx +")")
          weightTriplet.addEntry(w, i, h.twin.vertex.idx)
        })
        weightTriplet.addEntry(-sum, i, i)
        //console.log("Value: "+-sum+" Position: ("+ i+","+i +")")
      }
      else{
        weightTriplet.addEntry(1, i, i)
      }

    }

    let weightMatrix = SparseMatrix.fromTriplet(weightTriplet)

    return weightMatrix
  }

Unfortunately i couldn't find anything in the slides that explains how to calculate the boundary vertices so i just searched for the code in main that calculates the checker texture so i could calculate the boundary vertices for the boundary type rectangle (see code above, in case "rect"). I basically tried to uniformly distribute the vertices (that are at the boundary of the mesh) at the boundary of a 100*100 rectangle.

 checkboardTexture() {
    const h = 100
    const w = 100
    let data = new Uint8Array(h * w * 3)
    for (let i = 0; i < h; i++) {
      for (let j = 0; j < w; j++) {
        let c = (((i & 0x8) === 0) ^ ((j & 0x8) === 0)) * 255
        if (c === 0) {
          c = 155
        }
        data[3*(w*i+j)+0] = c
        data[3*(w*i+j)+1] = c
        data[3*(w*i+j)+2] = c
      }
    }
    const tex = new DataTexture(data, h, w, RGBFormat)
    tex.wrapS = RepeatWrapping
    tex.wrapT = RepeatWrapping
    tex.generateMipmaps = true
    tex.needsUpdate = true
    return tex
  }

I found this function in main and thought the rectangle for the uv coordinates is 100*100 (for the circle r=50 but i didn't try to implement it yet). Unfortunately my implementation still doesn't show anything (not even the boundary vertices), but also runs without an error.

So i basically have these questions:

• When is the checkerboard texture rendered? Does it need uv Coordinates, so that it will show?
• How do i calculate the boundary vertices? Is the assumption correct that the boundary for the uv points has a height and width of 100?

[changkun]

The highlighted sentence of Tutte's embedding points to how you might need to compute the boundary:

Given a triangulated surface homeomorphic to a disk, if the (u, v) coordinates at the boundary vertices lie on a convex polygon in order, and if the coordinates of the internal vertices are a convex combination of their neighbors, then the (u, v) coordinates from a valid parameterization.

I remember (?) spend a little bit of time in the class and discussed the way to compute boundary coordinates, but not detailly written in the slides simply because there are many different ways to compute them, as the most important: lies on a convex polygon in order.

This means: In the disk case, you will have to assume all boundary vertices lie on the disk's boundary, e.g. starting from (0.5, 0), then the next with a counter-clockwise rotation of 2pi/N from the starting point where N is the number of boundary edges.
More specifically:

    let U = DenseMatrix.zeros(this.vertices.length) // right hand side of the linear equation you plan to solve.
    let V = DenseMatrix.zeros(this.vertices.length)
    const r = 0.5 // disk radius
    switch (boundaryType) {
    case 'disk':
      boundariesEdges.forEach((edge, i) => {
        U.set(r*Math.cos(2*Math.PI*i/N), edge.halfedge.vertex.idx) // N is the number of boundary edges
        V.set(r*Math.sin(2*Math.PI*i/N), edge.halfedge.vertex.idx)
      })
      break
    ...

So, answer to your questions:

When is the checkerboard texture rendered? Does it need uv Coordinates, so that it will show?

If and only if you compute the UV coordinates of the mesh coorectly.

How do i calculate the boundary vertices? Is the assumption correct that the boundary for the uv points has a height and width of 100?

The UV coordinates are always in range [0, 1]. Thus you see the radius of the disk is 0.5, I just saw @nico778 answered you correctly, thanks :)
You don't need to know how checkboardTexture works, it is irrelevant to to UV computation process.

Personally, I would suggest you make disk case work first (probably easier for most of us), then figure out how to do it right with rectangle boundary.

[torantie]

ah ok thank you for the explanation. the coordinates lying between 0 and 1 makes more sense^^

[torantie]

Sorry i am back with questions after a lot of trying around. The version with the disk seems to (kind of) work but it looks like the uv plain is very zoomed in (the disk is not in the square).

So i tried to make the radius smaller by a factor of 10 (r=0.05) to make it visible and got this.

So it seems it is not centered and not even a circle. Like you suggested i am using:

  case "disk":
        const r = 0.5 // disk radius
        for(let i = 0; i<boundaryHalfEdgesLength; i++){
          this.boundaries[i].vertex.uv.x= r*Math.cos(2*Math.PI*i/boundaryHalfEdgesLength)
          this.boundaries[i].vertex.uv.y= r*Math.sin(2*Math.PI*i/boundaryHalfEdgesLength)
          u.set(this.boundaries[i].vertex.uv.x, this.boundaries[i].vertex.idx, 0)
          v.set(this.boundaries[i].vertex.uv.y, this.boundaries[i].vertex.idx, 0)
        }

        break;

to set the uv coordinates for the vertex at the boundary. I really don't know what else to try. I am not doing anything different from your suggestion except that i set the boundary coordinates immediately. Even if i don't do that and set them later i get the same result.

[torantie]

Took some more time but i found that the coordinates of the circle have to be moved (+0.5 for x and y). Seems like something is wrong with my code when i calculate the matrix and solve the linear equation.

[changkun]

Sorry for the late response. indeed the solved coordinates need translate 0.5 along x and y, if you set the boundary on a disk where centered at origin with radius 0.5. This is because the UVs are in range [0, 1]. Thus if you use a different boundary, the translation will be gone.

From what I saw in your picture, it seems that the boundaries are still not correct and therefore the interior vertices wouldn’t be computed to the right position too. As you self realized, it might be your linear equation is not formalized properly. Might need another look on how was constructed 😀

[torantie]

So i think i found the problem but it just doesn't make any sense to me that it doesn't work. When i construct the laplace matrix I check if the vertex halfedges are on the boundary and if they are only put a 1 at their index in the matrix column(see Slide 9 lecture 4). I made some console logs and found that this:

!vertex.halfedge.twin.next.onBoundary && !vertex.halfedge.prev.twin.onBoundary && !vertex.halfedge.onBoundary

only finds 69 boundary vertices. I know from:

 this.boundaries.forEach((edge, i) =>{
          let x = (r*Math.cos(2*Math.PI*i/boundaryHalfEdgesLength))
          let y = (r*Math.sin(2*Math.PI*i/boundaryHalfEdgesLength))
          edge.vertex.uv.x= x
          edge.vertex.uv.y= y
          u.set(x, edge.vertex.idx, 0)
          v.set(y, edge.vertex.idx, 0)
        })

that i have 80 boundary vertices. I am currently using the halfedge structure that is provided in the solutions so i assume nothings wrong with the halfedge structure itself. How do i find all boundary vertices?

[torantie]

and funnily enough i only find boundary halfedges with !vertex.halfedge.twin.next.onBoundary && !vertex.halfedge.prev.twin.onBoundary.
!vertex.halfedge.onBoundary doesn't find anything

[changkun]

Now I see where it might be wrong. As you already realized, it is all about finding the right boundary vertices.

In the third class, when I was revealing the solution of the second exercise, I mentioned a small trick: when constructing halfedge representation, we can use a dummy Face to represent a "hidden" boundary face, then we can use an additional array to contain all these hidden faces as boundary faces. Then whenever we need access boundary edges, we can do:

// `boundaries` is an array of Face, the edges of Face are the boundary edges of a given mesh
this.boundaries[0].edges(e => { 
    ... // deal with all boundary edges
}) 

This trick enables us to cache all boundaries of a given mesh. When it comes to parameterization, we can choose different boundaries of a given mesh.

Maybe you could try to export a cube from Blender, which one face is removed so that the cube contains exactly one boundary. Try to get this simple model work then test with the provided bunny model. After all, a cube is homeomorphic to the bunny

[torantie]

boundaries is described as this.boundaries= [] // an array of boundary loops so it should contain halfedges not faces correct?
since the provided solution already collects all boundary i only set this.boundaries = bcycle to collect all boundary edges. There shouldn't be any mistake in this i am just collecting the already calculated boundary edges.

Full code passage for reference:

for (let i = 0; i < indices.length; i++) {
      const he = this.halfedges[i]
      if (hasTwin.get(he)) {
        continue
      }

      // handle halfedge that has no twin
      const f = new Face() // hidden face
      let bcycle = []      // boundary cycle
      let current = he
      do {
        const bhe = new Halfedge() // boundary halfedge
        this.halfedges[hidx] = bhe
        hidx++
        bcycle.push(bhe)

        // grab the next halfedge along the boundary that does not
        // have a twin halfedge
        let next = current.next
        while (hasTwin.get(next)) {
          next = next.twin.next
        }

        // set the current halfedge's attributes
        bhe.vertex = next.vertex
        bhe.edge = current.edge
        bhe.onBoundary = true

        // point the new halfedge and face to each other
        bhe.face = f
        f.halfedge = bhe

        // point the new halfedge and twin to each other
        bhe.twin = current
        current.twin = bhe

        current = next
      } while(current != he)

      // link the cycle of boundary halfedges together
      const n = bcycle.length
      for (let j = 0; j < n; j++) {
        bcycle[j].next = bcycle[(j+n-1)%n]
        bcycle[j].prev = bcycle[(j+1)%n]
        hasTwin.set(bcycle[j], true)
        hasTwin.set(bcycle[j].twin, true)
      }

      this.boundaries = bcycle
    }

[changkun]

so it should contain halfedges not faces correct?

No, this.boundaries= [] should contain faces, and each face is actually a boundary loop (a polygon represented b boundary edges)

since the provided solution already collects all boundary i only set this.boundaries = bcycle to collect all boundary edges.

Yes, you realized that the trick is already revealed in the second provided solution, but you should not assign bcycle to boundaries directly, instead:

const f = new Face() // hidden face
this.boundaries.push(f)
...

This is only a "reference" solution, might not be ideal. It would be great if you could think about a different approach other than mine :)

[nico778]

@changkun Because I could not do the first 2 homeworks due to work issues I based my HW4 on your HW2 solution and the HW4 skeleton. Is this way of getting the boundary loop ok?
`let boundaryHalfedges = []

for(let he of this.halfedges) {
  if(he.onBoundary == true) {
    boundaryHalfedges.push(he)
  } else {
    continue
  }
}

console.log(boundaryHalfedges.length)

let boundaryLoop = []

for(let i = 0; i < boundaryHalfedges.length; i++) {
  for(let j = 0; j < boundaryHalfedges.length; j++) {
    if(boundaryHalfedges[i] == boundaryHalfedges[j]) {
      continue
    } else if(boundaryLoop.includes(boundaryHalfedges[j])) {
      continue
    } else if(boundaryHalfedges[i].next == boundaryHalfedges[j]) {
      boundaryLoop.push(boundaryHalfedges[i])
      boundaryLoop.push(boundaryHalfedges[j])
      break
    } else {
      continue
    }
  }
}`

my approach for the disk parameterization looks also a bit different to your suggestion

radius = boundaryLength / (2 * Math.PI)
for(let bv of boundaryVertices) {
let i = bv.idx
uComponent = radius * Math.cos(counter/radius) + 0.5
vComponent = -radius * Math.sin(counter/radius) + 0.5
uCoo.set(uComponent, i)
vCoo.set(vComponent, i)
itc++
counter = itc / boundaryVertices.length * 2 * Math.PI * radius
}

[nico778]

my result does look a bit strange

[changkun]

@nico778 One of the key concerns of constructing a boundary loop remains to maintain halfedge representation, which means you can loop over a boundary loop using halfedge.next reference.

I am not fully sure how you cached all this.halfedges, based on what you posted in the above thread, there might be an issue if your boundary loop does not establish the in order requirement from Tutte's embedding: because boundaryHalfedges is not guaranteed boundaryHalfedges[0].next is boundaryHalfedges[1], etc. Maybe I overlooked it here, you probably need to think more about it to make sure it works as to how you intended.

Similarly, your parameterization might also need some adjustment to guarantee the in order. So far it seems to be the boundary coordinates are not done correctly. Note that you are looping vertices instead of edges, which might result in inappropriate coordinates.

[nico778]

thanks for the quick response, i will try that

[nico778]

the disk parameterization is working(i think), the rectangle one not completely. To be honest I'm struggling to set up a forked repository. I uploaded the 2 relevant files to an empty public repository of mine. As a one-off, is this accepted instead of a pull request?

[changkun]

Sending a pull request is not complicated as you think, you just have to go through the process then everything will be very smooth later. Here is an official tutorial from GitHub about how to send a pull request: https://docs.github.com/en/free-pro-team@latest/github/collaborating-with-issues-and-pull-requests/creating-a-pull-request

Because commit time can be overwritten locally (rebase) which we cannot recognize as the submission time, this basically becomes the fundamental reason that it is necessary to send your submission in a pull request format.

Also see: #2 (comment)

[nico778]

thanks for the link, i got a little bit confused with the git commands. I´m still at work, but I try to do it as soon as possible.

[changkun]

Close due to the end of the submission period.