[WS2122] Homework 5 Discussion

[changkun]

This thread is open for the discussion of homework 5.

Please also note that the deadline for the 5th homework project is 01.01.2022 23:59:59 (CET)

[MarlQ]

I'm having some problems with typescript, and I couldn't find a solution anywhere.
How am I supposed to circumvent this problem??

[MarlQ]

Ok, I managed to "fix" it like this:

let edges : Edge[] = [];
for(let edge of this.edges) {
  if(edge) edges.push(edge);
}
edgeQueue.push(...edges);

I hate it.

[JohannesMerkt]

You can also fix it easier:

[MarlQ]

Thanks.. (Weird. I could've sworn it didn't work like that when I tried it before...)

[JohannesMerkt]

The if statement checks if the edge is null or not. Typescript is smart enough to understand that every edge within the if statement cant be null anymore. Thats why it works

[changkun]

It is a little less elegant. But I guess that's the only way we could write it. If one could find a better way to make halfedge.edges be typed as Edge[] rather than (Edge|null)[], this problem would exist :)

[JohannesMerkt]

I have now tried multiple implementations of the "vert collapse algorithm", but so far I always get stuck in a infinite loop in a subsequent vert collapse. Either in the Vertex.faces function or in the Vertex.halfedges function. This should mean that the for loop within these functions never returns to its original halfedge where it started:

So something with the connectivity is wrong. I checked the twin and next connectivity but cant find an obvious error. now I dont know what to do. Any hints? Or has anyone managed to write a successful mesh reduction alogrithm?

[changkun]

It works for the first two collapses for the cube, afterwards, it crashes.

This sounds like a bug that I encountered before, but don't remember many details. I suspect that might be caused by incomplete collapse construction (missing an halfedge connection, or so).

Another reason might because of the invalid solution of the quadrics equation. If that happens, one could search an optimal position along the edge that is considered being removed.

[MarlQ]

I haven't really touched the quadrics yet, because I wanted to write an edge collapse that works first. I checked everything multiple times, and I'm not sure what halfedge connection I'd be missing...

[changkun]

Then that's probably the reason. I'd suggest to re-evaluate the entire code carefully as I remember last time I had such a similar bug took me quite sometime to realize what went wrong :)

[JohannesMerkt]

I ended up writing if condition all over the code to throw errors when something unexpected occurs. Then I came across a error that you might be struggling with too.

It can occur that v4 and v3 are the same vert so i skip this case for now and continue with the next edge
EDIT: btw the edge im trying to collapse in the image is e12 between v1 and v2

[JohannesMerkt]

Also after i improved the sorting algorithm for the edges to be collapsed next this error occured less often up to not anymore

[MarlQ]

I'm having trouble understanding what this vector/matrix looks like:

n_i is a vector with 3 (or 4?) entries, but -n_i^T x_i should be a number. This kind of composition is invalid, so is it supposed to be that n_i and the whole composed vector are transposed as well? Then n_i would be a normal vector with 4 (or 5) entries, which would make sense.

[changkun]

That's a good point, I don't remember if I mentioned this in the class.

The \bar{} above a 3D vector, means a homogenous coordinates, which extends 3D to 4D.

The \bar{\mathbf{n}}_i should be a column vector, therefore \mathbf{n}_i^\top \mathbf{x}_i represents a scalar, which is the 4th dimension of \bar{\mathbf{n}}_i.

The \bar{\mathbf{n}}_i is actually a column vector rather than a row vector. The correct formula should be:

[MarlQ]

For some reason, my errors are negative a lot of the time, even though I double-checked the calculation like 5 times now.
I calculate the face quadrics using n n^T , then I sum up all the face quadrics for each vert, then sum up the quadrics for the two edge verts to get Q.
Lastly, the error for v is v^T Q v
What am I doing wrong??

[JohannesMerkt]

the three js simplifier is about 25 times faster than my QEM implementation. Is that expected?

[changkun]

I think the three.js's approach (Malex's approach) is intrinsically faster than QEM as it does not require solving a linear equation.

But as performance is not our major task here, it remains acceptable if our QEM is much slower than Malex's algorithm.

[JohannesMerkt]

Ok, I think the QEM has a better result though :)

[changkun]

That's true. Because QEM collapses the edge by a best-estimated vertex but Malex's approach only does a heuristic (curvature) one.

[changkun]

Close due to the end of the submission period.