[WS2021] Homework 2 Discussion

[changkun]

This thread is open for the discussion of homework 2.

[torantie]

I have a question regarding the Halfedge Datastructure. In the lecture slides (Slide 68: https://docs.google.com/presentation/d/1k9Y2vSu9t-9rYNAIddGBSd6NZ2x0hODhCP_bbhF1SWE/edit#slide=id.ga62e3d440e_0_90) there is no explicit mention of an Edge in the Halfedge Datastructure. Is there a reason why the Edge class was added to the code skeleton? And if yes why does it only have one halfedge vaariable? Shouldn't it be two?

[changkun]

@torantie Good question.

The short answer is: There is a reason. However, in this project, you can choose not to use Edge, whereas using Edge will bring more long-term benefits.

The long answer is: Edge is a higher-level abstraction, and Halfedge is a detail of the implementation layer. If you only want to build a Halfedge representation, then Edge is not that important in the implementation, because Halfedge can already represent the concept of an edge.
But when users use these APIs, they will have to understand the APIs related to the interaction with Halfedge. On the contrary, Edge as a high-level abstraction can hide implementation details from users. For example, if there is a method face.adjacentEdges(), it will return all connected half edges instead of an intuitive edge, and user will have to think about which halfedge they should use to loop the boundary of a face.
In this way, whenever you want to switch from the halfedge representation to other representations in the future, the user code that uses Edge, Face, and Vertex APIs (that does not expose halfedge) will not need to be affected, and there is no need to modify any usage details.

why does it only have one halfedge variable? Shouldn't it be two?

Because a halfedge can access its opposite/twin, it is not entirely necessary to wrap two of them.

[torantie]

A okay i understand the abstraction point. Thank you^^

Because a halfedge can access its opposite/twin, it is not entirely necessary to wrap two of them.

Hm i guess i am still a little confused why it is then called Halfedge and why it has that "twin" as information. The name kind of implies that it is a unidirectional edge (the picture of the slides also implies that), while the "Edge" implies that its bidirectional.

[changkun]

why it is then called Halfedge and why it has that "twin" as information. Name the kind of implies that it is a unidirectional edge (the picture of the slides also implies that), while the "Edge" implies that it's bidirectional.

Your understanding is correct. Halfedge is unidirectional, but Edge is more on the conceptual side which is bidirectional.
To access the underlying data of an edge, you need to access either edge.halfedge or edge.halfedge.twin.
Note that halfedge.face and halfedge.twin.face are two different faces, depending on how you construct the representation. Normally we assume counter clockwise for the direction of a halfedge, that means: For example, given a triangle, halfedge.edge, halfedge.next.edge, halfedge.next.next.edge are the three conceptual edges of the triangle. Additionally, halfedge.twin.edge also points to halfedge.edge, but halfedge.twin.next.edge and halfedge.next.edge are two different edges.

[torantie]

Took some time but i think i kind of get it now. Thank you for the explanation.^^
Unfortunately i am back with another question
const idxs = new Uint32Array(this.internal.mesh.faces.length*3) this.internal.mesh.faces.forEach(f => { f.vertices((v, i) => { idxs[3 * f.idx + i] = v.idx }) })

The call of the vertices function throws an error since there is no function vertices in the class Face . Face just has an idx and a reference to a Halfedge.

`
class Face {
constructor() {
this.halfedge = null // Halfedge
this.idx = -1 // Number
}

// NOTE: you can add more methods if you need here

}
`

Since there is only a note in the class to add functions if needed iam not sure if the missing function/field is intended or not.

[changkun]

Oppos.. the f.vertices actually reveals that you need to implement a vertices method in the Face class (as a hint):

class Face {
  constructor() {
    this.halfedge = null // Halfedge
    this.idx      = -1   // Number
  }
  
  // vertices visit all vertices of the given face, and 
  // fn is a callback that receives the visited vertices
  // and order index. For example, the usage could be:
  //
  //    f.vertices((vertex, orderIdx) => {
  //      ... // do something for the vertex
  //    })
  //
  // if one does not need to access the order index,
  // one can simply call the function as follows:
  //
  //    f.vertices(v => { ... })
  //
  vertices(fn) {
    ... // should call fn(v, i) for all vertices of the face, where v is a vertex and i is its order index.
  }
  ...

[torantie]

Ah okay. I thought the Note
// NOTE: you can add more methods if you need here
means that methods for the Face class are optional and we should only focus on the TODO sections. Thank you for clearing that up^^

[changkun]

No problem and sorry for the confusion. Actually, the project does not very strictly force you to not change the code skeleton (but I would not suggest change too much). So basically if you submit runnable code that does what was required in the project description (i.e. visualizes the normals and curvatures), it is still considered a successful delivery :)

[vseup]

Hi :-) How exactly is the homework graded? Is it a problem if the construction of the half edge structure takes relatively long? (around 1.5 minutes)

[changkun]

@vseup Performance is not the primary goal, getting things right is better than getting things faster in this course. Clean and clear implementation is preferred, if you have extra time, performance optimization will be a plus (not bonus :) The project description does not require anything related to runtime performance.

A working submission before the corresponding deadline gets a PASS and receives the full 10%.
Later submissions are downgraded by their delay time which can be calculated based on the late policy.

[changkun]

How's everyone's implementation status? Considering there is a huge gap (14.12.2020 - 11.01.2021) between the Christmas break, we could consider drifting the current submission deadline(s) a little bit to give you some more extra time to work on the coding project 1 and 2 (homework 2 and homework 3). Thumbs up on this message if you like it, and we could discuss the change in our next session if there are a considerable amount of requests. Otherwise, we just stick to the original plan :)

[vseup]

Hi, I'm curious how everyone is doing with the tasks of homework 2.

To be honest it's quite challenging for me - until now I edited/completed all tasks, but not without mistakes.

As I already invested a lot of time and neglected other courses for this too much I consider handing in a unfinished solution.
I'm not sure if I will be able to spend more time on it later before the postponed deadline, but is it possible to change the solution after a first submission?

[changkun]

@vseup Good point. You can send your pull requests as early as possible even if you are not finished, but if you want to submit incremental commits, then you must comment on your pull request and state which version (by the commit hash) should be recognized as your final version. The grade for the project will be calculated according to the time of that commit and subtracted by the delay time (if it is delayed).

So far, I think it is likely to extend the deadline of homework 2 and 3 by a week, which leaves more room for all of you to have more time to really understand the most important / foundation of this practical course.

We can discuss more on tomorrow's session :)

[vseup]

okay, thank you :-)

[torantie]

I was working on the Gaussian curvature implementation and unfortunately am kind of stuck. This is what i got so far.

I have honestly no idea what could be wrong or where i should search for an error. Would really appreciate a tip how this can happen.

curvature(method = 'Mean') {
        switch (method) {
            case 'Mean':
            // TODO: compute mean curvature
            case 'Gaussian':
                let start = true
                var sum = 0
                for (let currentHalfEdge = this.halfedge; start || currentHalfEdge != this.halfedge; currentHalfEdge = currentHalfEdge.twin.next) {
                    if(currentHalfEdge === null || currentHalfEdge === undefined)
                        break;

                    sum += currentHalfEdge.vertex.getAngle()
                    start = false

                }

                return (2 * Math.PI) - sum
            case 'Kmin':
            // TODO: compute principal curvature and return Kmin
            case 'Kmax':
            // TODO: compute principal curvature and return Kmax
            default: // undefined
                return 0
        }
    }


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

[changkun]

@torantie Interesting result. So far your snippet looks good to me. But I am wondering are you absolutely sure your halfedge construction is correct? A possible way to debug your implementation and verify the result is to start from a simple model, such as a cube, or a tetrahedron.

[torantie]

The halfedge structure seems to work.

Luckily i got the solution. my getAngle function was located in the vertex class and always calculated the same angle for every for loop. i just moved it to the Halfedge class and now it works. Took me only 3 hours to find out :D

Sorry for the late night question ^^

[krasnor]

Hi, I have trouble reproducing the reference image of the mean curvature.
Mine is always red but without the "blue parts".

If I have understood the colormap code in the template correctly, it will only use blue tones for negative curvature values.
I then looked at the formula I use (the one frome the slides), and it seems that only values from 0 to infinity will be produced because of the vector norm in the end.
(the few blue dots in my image are artifacts, as sometimes a negative area is returned by the lectures voronoiCell code)

Now I think I might be using the wrong formula or missing a step to calculate the curvature.
But I can't figure out what is missing.
Do you maybe have a tip on what I'm doing wrong?

Below are the keyparts of my code:

// veretx
// ...
curvature(method = 'Mean') {
        let H = this.calcMean();
        let K = this.calcGauss();
        let k1 = H - Math.sqrt(H * H - K);
        let k2 = H + Math.sqrt(H * H - K);

        switch (method) {
            case 'Mean':
                return H;   // (k1 + k2)*0.5; // no "blue areas" will be rendered
            case 'Gaussian':
                return K;   // return k1*k2; // works
            case 'Kmin':
                return k1;
            case 'Kmax':
                return k2;
            default: // undefined
                return 0;
        }
    }

    calcMean() {
        let outHfEdges = this.getAllOutgoingHalfedges(); // this method returns all outgoing edges in a list

        let area = 0; // calc area sum in separate loop
        for (let h of outHfEdges.values()) {
            // area_sum += hfe.face.getArea()/3; // area approximation

            // voronoi vertex area
            const u = h.prev.getVector().norm();
            const v = h.getVector().norm();
            area += (u * u * h.prev.cotan() + v * v * h.cotan()) / 8
        }

        let c_sum = new Vector();
        for (let hfe of outHfEdges.values()) {
            //     O--------i
            //      \ A   /  \
            //       \   hfe  \
            //        \ /     B\
            //         J--------O

            let fac = hfe.cotan() + hfe.twin.cotan();

            c_sum = c_sum.sub(  hfe.getVector().scale(fac)  );
        }

        let H = c_sum.norm() * 0.5 / area; // by using this variant from the slides there are 9 negative outliers (area negative)
        // if(H <0)
        //     return 0; // negative values are not possible -> return lowest possible value
        return H;
        // return 0.5 * c_sum.scale( 1/(2*area)).norm(); // using this version does not result in much visual change, but outliers are now dark red
    }
// ...

// halfedge
// ...
    getVector() {
        let v_start = this.vertex.position;
        let v_end = this.twin.vertex.position;
        return v_end.sub(v_start);
    }

    cotan() {
        //       2
        //     /   \
        //    / cot \
        //   e2     e1
        //  /         \
        // 0 --e0---> 1
        // (e0 = this hf_edge)

        // if (this.onBoundary) {
        if (this.next === null || this.next === undefined
            || this.prev === null || this.prev === undefined
        )
            return 0; // called 208 times (as much as bunny has boundraries edges)

        const u = this.prev.getVector();
        const v = this.next.getVector().scale(-1);

        return u.dot(v) / u.cross(v).norm();
    }
// ...

[changkun]

@krasnor Oppos. This seems to be an implementation issue. So far you implemented everything correct, except the color encoding. The mean curvature is always positive for sure, the problem is how we should visualize it. Notice that mean curvature is the amount of normal direction: with the provided color bar (from blue to red), if the angle defect is greater than zero (meaning concave), then we have the mean curvature on the normal direction, otherwise it is a convex we have an opposite direction. The text might not easy to understand but the following code should be easy to read:

meanCurvature() {
  const clb = this.cotanLaplaceBeltrami() // assume this returns || (Δf)i ||
  if (this.angleDefect() < 0) {
    return -clb
  }
  return clb
}

[krasnor]

Ah thank you :)
I first thought that the cotanLaplaceBeltrami() should be returned unaltered.
With this change now it renders correctly.

[torantie]

I am still confused. I get this picture if i use the angle Defect:

I still get red spots in the blue outlines. which makes sense considering the angle defect which approximates the Gaussian Curvature produces this picture where the blue lines also have red dots:

I am not sure why my gaussian curvature bunny is this ligthly coloured, but even if we look at the reference picture, it shows blue lines with red dots.

In summary i am not sure how using the angle defect to change the sign of the Cotan Laplace Beltramy alone can produce the picture:

Relevant code:

class Vertex {
    calculateGaussianCurvature() {
        let sum = 0
        this.forEachHalfEdge((currentHalfEdge) => {
            sum += currentHalfEdge.getAngle();
        })

        return (2 * Math.PI) - sum
    }

    calculateVoronoiArea() {
        let area = 0

        this.forEachHalfEdge((currentHalfEdge) => {
            let u = currentHalfEdge.prev.getVector().norm()
            let v = currentHalfEdge.getVector().norm()
            area += (Math.pow(u, 2) * currentHalfEdge.prev.cotan() + Math.pow(v, 2) * currentHalfEdge.cotan()) / 8
        })

        return area
    }

    forEachHalfEdge(fn) {
        let start = true
        let i = 0

        for (let currentHalfEdge = this.halfedge; start || currentHalfEdge != this.halfedge; currentHalfEdge = currentHalfEdge.twin.next) {
            if (currentHalfEdge === null || currentHalfEdge === undefined)
                return;
            fn(currentHalfEdge, i)
            start = false
            i++
        }
    }

    calculateMeanCurvature() {
        let clb = this.cotanLaplaceBeltrami()
        let angleDefect = this.calculateGaussianCurvature()

        if (angleDefect < 0) {
            return -clb
        }
        return clb
    }

    cotanLaplaceBeltrami() {
        const area = this.calculateVoronoiArea()
        let sum = new Vector()
        this.forEachHalfEdge(currentHalfEdge => {
            sum = sum.add(currentHalfEdge.getVector().scale(currentHalfEdge.cotan() + currentHalfEdge.twin.cotan()))
        })
        let cotanLaplaceBeltrami = sum.norm() * 0.5 / area

        return cotanLaplaceBeltrami
    }
}
class Halfedge {
    getVector() {
        return this.twin.vertex.position.sub(this.vertex.position)
    }

    cotan() {
        if (this.onBoundary) {
            return 0
        }
        const u = this.prev.getVector()
        const v = this.next.getVector().scale(-1)
        return u.dot(v) / u.cross(v).norm()
    }
}

[changkun]

@torantie This is only about color mapping, which is not considered as wrong. If you take a look at how curvature is mapped to color, you will see the reason: https://github.com/mimuc/gp-ws2021/blob/f052bf48ab3918756a0a4d959841898b4e08d3f2/homeworks/2-ddg/src/main.js#L145

To reproduce exactly the same visualization, you will need to adapt a little bit to that (which I forgot to mark it as a TODO in the skeleton, sorry...). Overall, I won't suggest you spend more effort working on reproducing exactly the same color encoding. From what you have so far, the computation is correct (think about the relativity of values between vertices).

[torantie]

Thank you for the feedback. Good to know that the calculation at least is correct :D

[changkun]

Close due to the end of the submission period.