search

alecjacobson / geometry-processing-introduction

Introductory assignment for Geometry Processing course
Mozilla Public License 2.0
116 stars 131 forks source link

Slow edges implementation #67

Open chanlenn opened 4 years ago

chanlenn commented 4 years ago

Hi. I'm pretty new to this Eigen library and I implemented edges, but it uses nested loops and takes around 30 seconds to complete. I compared it to the igl implementation and that takes less than a second. I heard in tutorial that you won't be marking us on runtime, except if it's too slow.

Is this slow implementation okay or am I in the wrong track? Are there any tips or hints on how to implement this faster? Are matrix operations the way to do it?

otmanon commented 4 years ago

Yeah i'd like an answer to this too. Specifically my code can take like 45 secs running in debug but less than 5 in release

chanlenn commented 4 years ago

After researching Eigen and IGL more, I was able to make a fast implementation. I think the question still needs to be answered for other people though.

alecjacobson commented 4 years ago

Aim for the correct asymptotic runtime performance. Determining what the correct asymptotic runtime performance is is implicitly part of the assignment.

cuppajoeman commented 4 years ago

I was also thinking about this. If we naively just check if an edge we want to add is already in the matrix by iterating until we do (or don't) find it, I think the runtime would be O(n^2) (which doesn't seem good, n being the number of edges). Are we suppose to use a hash table or something like that to lower the cost of checking if an edge is already in the matrix?

rikingurditta commented 4 years ago

There are tradeoffs between time and space too though. My current implementation could be made asymptotically faster if I required it to use asymptotically greater space. Should I prioritize time over space?

cuppajoeman commented 4 years ago

There is a property about the edges so that you don't have to use different data structures and it runs quickly. (If you find it, I don't think you have to check for the edge through the matrix anymore)