September 9, 2018

NCH: finding a metric for point removal

Introduction The objective of my thesis is to find ways to remove points from the input point cloud to NCH, while managing to guarantee that the error incurred is not too big. Clearly, the last sentence is far from specific: I haven’t defined a metric, nor said what “too big” means. Before we begin, let’s recap on what the definition of the NCH function looks like: $$ f(x) = \max_{1 \leq i \leq N} f_i(x) $$ Read more

August 21, 2018

NCH: closing the gap

Introduction Following up with my last post on NCH being roto-translation invariant, the idea of this one is to cover what I consider the most important gaps left by the original brief paper. My expectation is that doing this will help understand better why NCH works, and hopefully gain some insight into how to improve it. Equivalence of formulations Equation (4) in the paper says: $$f_i^{r_i} (x) = \frac{1}{2 r_i} (r_i^2 - || x - (p_i + r_i n_i) ||^2)$$ Read more

August 20, 2018

NCH is roto-translation invariant

Introduction I have recently started my thesis on 3D surface reconstruction. One way to do so is to define a surface as the zero level set of a function $f : \mathbb{R}^3 \to \mathbb{R}$, and then find some way to build this function out of a set of points $\mathcal{P} \subset \mathbb{R}^3$. NCH is a method that allows you to define such a function starting from a point cloud along with their normals, which tell you which way is the inside of the surface. Read more

June 2, 2018

Processing Trees with Recursion Schemes

A long time ago, I was in touch with a production system whose purpose was to run a piece of data through a decision tree. At every step, the output could be Good, Bad, Move Left, or Move Right; there were no leaves, since at the end you were supposed to always have returned either Good or Bad (this means it would be an error for you to get there). Read more

May 2, 2018

Understanding Modulo Bias

It is often said that this code: unsigned int randomNumber = rand() % k; is a bad idea, at least if you are expecting a uniform distribution. I’m going to try and explore this topic in a more formal fashion than I have seen so far. The reason why it is bad is pretty elementary and easy to understand: imagine you have a random generator that outputs values between \(0\) and \(9\) (i. Read more