[WS2021] Individual Projects Discussion

[changkun]

This thread is open for the discussion of individual projects.

[torantie]

Hello,
i just realized that the proposal of the individual projects is already due tomorrow. Unfortunately i don't have an idea for a project yet and thought it may be good idea to talk about possible projects in/after the next lecture (11.1). Or maybe shift the proposal deadline 1 week since the programming tasks were also delayed.

[changkun]

@torantie Hmm. That's actually a valid reason. Since there are no submissions yet, I am assuming that this message is going to be read by others who are working on or planning to work on the proposal. Does anyone else have objections to an improved proposal based on Micheal's that "postpone the individual project proposal deadline for two weeks (14.01.2021)"? Thumbs up to agree or comment on your arguments below to explain your objections.

I will post the decision below at mid-night based on the reactions.

[krasnor]

I have the same problem, I just can't find an (good) project idea.

[changkun]

Happy new year!

Sorry, I totally forgot that I promised to announce the decision at midnight. I hope you had a great New Year's Eve celebration.
The first great news in 2021: Based on the reaction, the project proposal deadline is extended for two weeks (14.01.2021), and enjoy the rest of your winter break :)

[torantie]

I thought of some ideas for my project but iam not sure if the complexity would be to high or low. Currently i am thinking about doing:

1. extending the halfedge representation with quads and implementing the Laplacian smooth for it
2. extending the halfedge representation with quads and implementing a different smooth algorithm (parallelogram smoothing, https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwj_1eOX45juAhWGqaQKHVs3DCwQFjACegQIAhAC&url=https%3A%2F%2Flink.springer.com%2Fcontent%2Fpdf%2F10.1007%252F11758525_32.pdf&usg=AOvVaw2uBfdp0o3C3UrK_F-97Mec)
3. extending the halfedge representation with quads and implementing the Laplacian smooth with mean value weights (if that makes sense)
   
4. implement up-sampling with Loop Subdivide (not sure but i think i also need an adjacency list representation for that not halfedge) https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/thesis-10.pdf
5. implementing face based connectivity
   

My favorite is currently 3 since i like the result of the mean value weights, but i don't know if the mean value weight can be used for smoothing a quad mesh.

[krasnor]

I thought about my project ideas, but am still unsure if they are suitable.
Currently have the following project ideas:

1. Mesh Deformation
   I would implement a mesh deformation algorithm in JS where you could "twist" a mesh (similar to Blenders "Simple Deform"-Modifier), but in Javascript for the Half-Edge Mesh.
   Basically all vertices would be rotated around an arbitrary point and axis.
   Parameters such as rotation axis and rotation center would be adjustable.
   
   With this Project I'm not sure if it is too simple?

2. Implement Laplacian Smooth for Quad Mesh

3. Up-sampling: Implement Loop Subdivision
   Features would be
   ability to import own .obj file,
   display of statistics such as count of vertices, edges, faces
   and a side by side view, to compare up-sampled mesh with original version

4. Down-sampling: Implement Edge Collapse / Decimate

5. Mesh-Surface Roughness Visualization
   Implement an existing algorithm to calculate and visualize mesh-surface roughness.
   Similar to Homework 2 where we calculated and visualized the surface curvature.
   At the moment I'm still exploring different papers.
   
   But so far this is my least favorite project idea.

Currently my favorite project ideas are 3 (Loop Subdivision) and 1("Twist"), because I like the concept of manipulating geometry with algorithms, but I'm not sure if the complexity is suitable for the Project.

[changkun]

@torantie @krasnor Thanks for posting a list of your ideas here! I just got time to review all of the listed ideas of projects.

The general purpose of proposing an individual project idea is not inventing a new algorithm or implement it because this requires a tremendous amount of work as I can imagine (but if you are interested in doing this we could do a thesis, initiate an Einzelpraktikum, or start a research project :). Instead, a good fit for this practical course is to demonstrate how you combine and transfer/extend the knowledge you learned from here to anywhere and demonstrate comparable results from your project (think about the QEM project, that we compare QEM with three.js's version. Can your project be able to compare to something already existed?).

If I read all of the ideas correctly, here is a summary and general feedbacks from my quick mind:

• halfedge+quads+laplacian smooth
• halfedge+quads+parallelogram smooth
• halfedge+quads+mean value weights

As I mentioned in the session this Monday, the above three are roughly similar and the only difference is the smoothing algorithm itself, although the major complexity comes to the adaptation for quad meshes because the switch from cotan weights to mean value weights can be simply done with few lines of code change. Nevertheless, I like the idea of getting quad support, and smoothing is a plus to it :)

Regarding the sampling:

• up-sampling loop subdivision+adjacency list
• down-sampling: edge collapse

If you wanted to do a subdivision for quads, then you definitely need to check the Catmull-Clark subdivision. For edge collapse, this is covered in the QEM coding project, I am not fully sure what you mean by this idea at the moment. So I won't encourage you to pursue these two. However, if you are interested in re-sampling (although we didn't cover too much regarding how to do it exactly, but you can read from the book we recommended from the beginning of the course), this could be more interesting for me :)

Regarding the deformation and visualization:

• halfedge+simple deform modifier
• roughness visualization

All of these two are great. If they are turned into project, then this question is important:

• How exactly your project can do things (slight) differently? Demonstrate the difference.

For example, if you'd like to do roughness visualization, then you might want to implement in a way that your project can show multiple visualization simoutainously since you can easily add support for at least two different type of visualizations (via small change to the metric).

[torantie]

Thanks for the reply i think i will try to do the "halfedge+quads+mean value weights" project. Since the original/second submission deadline for the proposal was today, is it possible to extend it to monday (18.01.2021), since i had work today and have an appointment tomorrow.

[changkun]

@torantie Sure, that's a feasible extend.

[torantie]

thank you^^

[krasnor]

Yes an extension would be helpful.

Thanks for the feedback.

• Regarding "Edge-Collapse": I forgot that it is already covered in the homework.
• "Roughness Visualization": From the papers I found, the implementations are partly very complex so I probably will not do a Roughness Visualzation project.

I currently am thinking about doing one of these two projects:

• "Up-Sampling": If Loop-Algorithm is too complex, then I will look into the Catmull-Clark subdivision (not sure how complex this one is)
  But if I would do this project should Quad-Mesh be implemented too?
  Edit: I looked into Catmull-Clark Algorithm and noticed that quad support would have to be implemented, as the algorithm can produce quads.
  The Idea would then be to implement "halfedge+quads+Catmull-Clark".
  For a better comparison of the result, the original mesh would be displayed next to the subdivided mesh, also some information about both meshes (vertex count, etc.) would be displayed.
• "halfedge+Twist modifier"
  • It is mostly just vertex manipulation (no Halfedge-manipulation) so I'm not sure if it is too simple
  • Biggest difference would be that for the Twist modifier the whole rotation axis could be defined (not just a fixed X-,Y- and Z-Axis), but I'm not sure if this would be enough

[changkun]

@krasnor "halfedge+quads+Catmull-Clark" might be better than "halfedge+twist modifier". In this case, @torantie and you share a common part of your projects, which is supporting quads, then you two can work together in the beginning and branch out once you two have finished the quad support, with a little bit of extra work, i.e. adding smoothing and subdivision.

[nico778]

@changkun My proposal shows up in my old pull request, is that okay? To be honest I still feel like an idiot when using git

[changkun]

You need to send your proposal as a separate pull request.

[nico778]

i tried to do that, but that sends me to my old pull request

[changkun]

You will need to create a different branch then send your pull request from that newly created branch.

[nico778]

thank you, i was not aware of the branches thing

[torantie]

Hello i am looking for some advice what i could be doing wrong with my meanValueWeights smoothing

I am currently using this code to calculate the mean value weights based on the formula above, but i only receive a deformed mesh:

meanValueWeight(){
    if (this.onBoundary) {
      return 0
    }

    const gamma = this.getAngle()
    const delta = this.twin.next.getAngle()
    const weight =Math.tan(gamma/2) + Math.tan(delta/2)
    //||vi - v0||
    const viMv0 = this.next.vertex.position.sub(this.vertex.position).norm()

    return weight / viMv0
  }

In the lecture formula it's ||fi -fj|| (here ||vi -v0|| based on the naming in the research paper) but i think that is a typo based and shopuld be ||fj -fi||. But to be sure i tested both versions. I also tried just leaving it out of the equation.
For the Mass Matrix i used the identity Matrix, since laplacian smooth should work without a specific mass matrix and because nothing specific was mentioned in the research paper (or maybe i just didn't find it).

Laplace/Weight matrix construction is unchanged. I only added the mean value case and calculated the formula for each halfedge and summing the result:

 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

      vert.forEachHalfEdge(h => {
        let w = 0

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

        sum += w
        weightTriplet.addEntry(w, i, h.twin.vertex.idx)
      })
      weightTriplet.addEntry(-sum, i, i)
    }

    let weightMatrix = SparseMatrix.fromTriplet(weightTriplet)

    return weightMatrix
  }

I also tried the algorithm both for a triangular mesh and for a quad mesh and both did not seem to work. Is there something else i can test? Because i am kind of out of ideas. ^^

[changkun]

opps 🤦‍♂️, i should update the document too. since we had extended the deadline for proposal, your coding time is shorter than planned, thus the code submission is automatically extended too. In the last session I only talked about the presentation day is not extended, and ask you if you need any more time to extend that time. Since no one request, i assume that all deadlines are converged to the presentation day..

[changkun]

Just updated the document, sorry again (and again, and again...) for causing so much confusion over the semester, orz

[torantie]

no problem we should have just asked if the final code submission date is still valid. Thank you for updating us though^^

[torantie]

I tried using the implementation of getAngle that was provided in the smoothing solution:

getAngle() {
   const a = this.prev.getVector().unit()
   const b = this.next.getVector().scale(-1).unit()
   let angle = Math.acos(Math.max(-1, Math.min(1, a.dot(b))))

   return angle
 }

At least for the triangulated sphere it seems to provide a different result

With old version:

getAngle() {
    let a = this.getVector()
    let b = this.prev.twin.getVector()
    let dot = a.unit().dot(b.unit())
    let angle = Math.acos(dot)
    return angle
  }

Is there a reason why the getAngle() (originally just called angle()). Does the dot product between vector next and previous?
In my opinion get angle makes only sense when it either takes the angle between this.getVector() and this.prev.twin.getVector() or this.getVector() and this.twin.next.getVector.
This is not intended to criticize the provided solution, i am just trying to eliminate potential errors i could have made since i am out of ideas what could still be wrong in my implementation.

[changkun]

@torantie I have few things in mind at the moment:

1. It might be problematic if you apply two types of laplacians in different orders (not sure if your current quad mesh implementation keeps the original mesh, as I remember my supplied reference solution have the issue in several nitch cases, reason undiscovered yet. Anyway, it might be easier to just compare versions by refreshing your browser page and only apply smooth operator once)

2. The following version only applicable for triangle meshes and computes the opposite angle of the halfedge (as for the convenience of computing cotan Laplacian, and it is necessary to change the implementation for quad meshes):

   const a = this.prev.getVector().unit()
   const b = this.next.getVector().scale(-1).unit()
   let angle = Math.acos(Math.max(-1, Math.min(1, a.dot(b))))
   return angle

Whereas the following version, computes a different angle:

    let a = this.getVector()
    let b = this.prev.twin.getVector()
    let dot = a.unit().dot(b.unit())
    let angle = Math.acos(dot)
    return angle

I think this is the reason that produces different results as if you use the later one for cotan weights, will give you incorrect calculation.

3. Keep your calculation bounded. It is always a good idea to keep the result bounded so that you can safely compute the acos:

Math.acos(Math.max(-1, Math.min(1, a.dot(b))))

[changkun]

Close due to the end of the submission period.