# Arbitrary contour retopology

Hi

Finally I’ve made quite a breakthrough in semiautomatic retopology. What initially started as a prototype tool is evolving into a quite powerful new way to retopologize models in 3DCoat. Giving artists the freedom to experiment in an intuitive way by just drawing patches, arbitrary patches that will be optimally filled with quads.

Artist is not limited to certain number of edges , flatness or any other constraint. Just draw. I’ve also added the possibility to save and load the strokes along with the model.

The core is done, remaining now is the usability and the workflow of the tool, adding a realtime preview among other details. I’m investigating several variants and further optimizations.

I suspect this core quadrangulator algorithm will span many interesting new tools.But wait, I’m saving the real breakthrough for later 😉

PS: Could you suggest me a good (fast, high quality) screen capture program? I’ve tried CamStudio but cannot get +30fps recording  at 1080p 😦  preferably one that is HW accelerated. (using an NVIDIA GT 560M )

Cheers!

# Spline fitting

Hermite Spline Tangent estimation for curve fitting.

Hi all

Dataset fitting? it must be trough the Least squares method! I keep banging in my head for few days refusing to dive into it because for anything but the trivial function

f(x) = A + Bx

it can easily overflow the brain cache and is a heavy calculation for realtime purposes… So I attempted several heuristics that failed for arbitrary datasets (user strokes in this case) and that was a non negotiable requirement for me.

So what’s the problem about? basically you have a stroke between 2 end points, actually just a set of points given because if I knew the stroke equation there would not be problem at all! And I needed to approximate that curve with a 3D Hermite spline of the form:

Where P0 and P1 are the known endpoints. So I need to find the tangents at each of those points M0 and M1 such the resulting spline was the closest possible to that curve.
Finally I decided to get my hands dirty with pen and paper (you thougth programming happens only at a keyboard and in front of a computer? that’s typing or implementing, programming is actually thinking and it happens even when you load the brain with a complex problem and go to sleep!)

I’m posting this mainly for me, so when I find a similar problem in the future and I have flushed my current memory of this, I will remember, I don’t want to struggle again with Google and Stackoverflow to find nothing related there. (or I did a wrong search 😉 ).

How the least squares method works?

You have some datasets {P0, P1 ,… Pi} you want to fit with a mathematical function F(…). That means that the sum of the approximation errors of that function should be as little as possible, ideally 0 so would be a perfect fit. And the error can be calculated as the sum of all the tiny errors for each evaluated point of the dataset squared, because we don’t want errors canceling each other on both sides of the original curve.

Easy no? well, in order to minimize that error we should take the partials derivatives of that function and set it to 0 for every unknown we want to estimate. In this case we have 2 unknown tangents.
And here’s where the heavy stuff start showing.

I needed to substitute the equations with the original forms but this brings another problem: it has 3D vectors! and the solution is not as easy as solving the least square for every component (trust me, I even attempted that!) I had to flatten it to a scalar problem.

A coordinate system transformation could have done the trick or a different parametrization:

But equations where already large and complex enough once substituted and it doesn’t account the case where in the new parametric form 2 or more values could correspond to the same parameter (remember user strokes can be like Brownian motion :P) and perhaps I can explore it once I find a more canonical solution.

And then I realized I could minimize the error LENGTH (scalar) instead of the vector difference. And went back to the beginning rewriting the least square functions:

so in order to minimize the error:

Wow, three times longer than before, take into account that each of those terms are a full equation on their own! look at this sample of my pen work 😉

Is it correct? the reasoning was correct… so I blindly continue developing the solution, calculating the derivatives (Thanks Wolfram Alpa!) and then organize it into Matrix form (AX = B) to finally calculate the solution vector with the tangents magnitude… and crossed my fingers….

Wow, just wow, it worked flawlessly and finally integrate it into my branch of 3DCoat QuadStrips. Is mathematically heavy for realtime but it only runs once at the creation of the spline so performance here is not an issue.
The harder the problem the greater the self satisfaction I get 🙂

Cheers!

# Improving contour partitioning

At the heart of several tools that I have developed in the past lays a contour partitioning algorithm. It was robust and could handle arbitrary contour shapes, but recently I got a bug report assigned related to CloseHoles tool, and after a careful debugging I found that the partition was indeed robust, but not “clean” enough, it could sometimes create fan like splits which was actually undesired.
What started as a routine bug hunt ended up improving greatly the code for a much more neat contour partition algorithm.

An incredible powerful and yet conceptually simple tool are quad strips. highly requested by our community! Is on the way 🙂

Using strokes artist can easily create, place and modify full strips of quads with incredible flexibility. I’m still improving the tool flow but will  have auto welding, size control and real-time or near real-time feedback as well.

# Simple Stroke test 2

Recently added cut , auto welding,  automatic level of detail… important enhancement to this stroking tool. Also adjusted the tension level to make it more intuitive.

# SimpleStroke polish

Unlike spline based retopo strokes, this new class is oriented for more direct stroke control and manipulation: it supports splitting/reducing of divisions. Moving and smoothing etc. It is actively used in QuadPaint tool.

Control + RMB move closest stroke point
SHIFT + LMB splits the closest segment
SHIFT + RMB removes the closest point.