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:

splineform

TangentsEstimation
Problem: what magnitudes should have the tangents such as the curve best fit the original points?

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?

TangentsEstimationErrors
Errors between original curve and interpolated one.

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.

Sum

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.

partialderivatives

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:

TangentsEstimationTransformation
Another parametrization perhaps?

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:

sumofdist

SumOfDist2

so in order to minimize the error:

partialsBig

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 ;)

hand written equiations
Substitutions of substitutions…

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.

Before
Before
After: new algorithm
After: new algorithm

Quad strips

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.

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.

No hay peor astilla que la del mismo palo.

stop-sign

No acostumbro a escribir de politica, pero hay un tema que me causa comezon:
La Ley de Ajuste Cubano y la reaccion que causa entre mis congeneres.
Jamas veran a un italiano o un frances discutir o quejarse de esa ley, por supuesto porque no les incumbe, pero uno creeria que una ley que le brinda beneficios a personas de un pais en cualquier otro pais seria vista con buenos ojos. Uno se equivoca a menudo.

Es increible el EGOISMO que muestran los que se manifiestan en contra de esta ley, la GRAN mayoria CUBANOS tambien, pero no Cubanos del oficialismo, que va! Cubanos que YA se beneficiaron con ella o descendientes de Cubanos que se beneficiaron con ella.

Exponen cualquier cantidad de sinrazones para justificar su egoismo: que si se abusa de ella (les retuerce la bilis ver a cubanos viajando de vuelta a cuba al año y pico de acojerse a esta ley, se olvidan como duele dentro la partida, la ruptura y ese primer año es critico, porque es el mas doloroso para ti y tu familia que se quedo alla, o por la causa que sea, el asunto es que les retuerce la bilis…)

Que si abusan de los beneficios (que beneficios? los quilos que dan? por favor! el pais mas rico del mundo que gasta billones en armamento y se vienen a quejar por los quilos que le dan a los inmigrantes? a que no protestan por eso? ah no, a quejarse de la vecina de al lado que pare como una curiela y tiene que sobrevivir con 700$ de beneficios, en el mejor de los casos! que los contribuyentes pagan, la gran mayoria de las veces solo dan $100 y gracias… pues a mucha honra, Si no les dieran esos beneficios seguirias pagando lo mismo en contribuciones y fueran a parar a otra parte menos altruista tal vez.)

Otros dicen que no mandan ni un quilo a Cuba para enriquecer al sistema: eso tiene solo dos causas, o tienes a tu familia, la que te importa, fuera de Cuba, o eres un tacaño escrito con todas sus letras, Punto. La excusa de que no enriqueces al castrismo es cuando menos absurda, el dinero es una corriente, un flujo, no algo estatico que tu decides en que se gasta y se invierte. Como las corrientes marinas, una vez que sale de tu bolsillo, no importa que sea en un Wallmart , una ONG, o un diezmo … recorre el mundo. Asi que muy a pesar tuyo, parte de lo que pagas va a Cuba tambien y a Corea, y a Rusia y a China. Protesta contra eso si puedes….
En cualquier caso se reduce al “pienso como vivo” Como no tengo padres ancianos ni enfermos en Cuba me creo que todo el que manda para alla es un comunista. Una de las mayores economias del mundo tiene recursos para aguantar 10 Cubas y aun ni se lo siente, asi que de que falta de recursos me van a hablar?

Y al final , todo, TODO, se reduce a ese sentimiento tan mezquino y bajo como la ENVIDIA, que es endemica en Cuba y que por mucho que se hagan mas americanos que los mismos americanos, importamos desde Cuba: -que te IMPORTA la vida del vecino? que te importa que viaje 15 veces al mes a Cuba o a Haiti? que te importa lo que hace con su dinero si lo quema, lo gasta en un carro o se lo manda a su hermana/hermano/padre/madre/hijos/esposa en Cuba? QUE TE IMPORTA…?

Vive y deja vivir por Dios! eso fue lo que viniste buscando cuando saliste de Cuba! (…o tus padres)

Montando las abarrotadas guaguas (autobuses) en Cuba me di cuenta de una cosa, a lo que llamo El principio de la Guagua: Mientras estan en el tumulto abajo luchando por subir gritan:

-Caballero un pasito mas que el fondo esta vacio!   (si, Caballero sin la s aunque sea plural)

y en cuanto se montan y se encuentran seguros dentro, se viran para los que tienen detras que quieren seguir montando y dicen:

-Oye no aprieten que esto no da maaaas!!

RShell polished

Shell only selected elements
Shell only selected elements

Hi

Polished a bit more RShell by adding the option to extrude only selected vertices/edges/faces.

The default behavior makes a shell of current whole retopo mesh, but if user wants to make a shell of a part only, it can use now the selectOnly feature. Notice that of the seletced element has a boundary it will automatically create the rim , so islands if are fully selected will have a proper rim after extrusion.

A known issue is the way retopo handles normals because, unlike other rooms, retopo enforce and override faces normals, flipping them and preventing to change them. Is something I will try to modify, but at later stages to avoid breaking legacy functionality.

Improving the contour detection algorithm

Hi

contour (1)One of the core algorithm of the QuadPaint tool estimates the amount of closed contours that can be extracted from an arbitrary set of strokes, which can be treated as graphs.

In my first development attempt I successfully implemented an algorithm that extracted the minimum path loops first. It worked very well but soon realized that the condition had very common ill cases:

In the above figure, the minimum path for the outer loops overlaps the inner loop, causing messed geometry in latter stages of the pipeline:

prevSo I must carefully find another solution, another condition that adjacent loops should met:

Filled loops should not overlap , but that term is a bit tricky because we are talking of 3D meshes so some sort of projection or volume intersection test needs to be implemented, and we all know those arbitrary precision intersection mesh calculations are very heavy for close to real-time performance.

I eventually found a very elegant solution: Filled contour areas, non overlapping adjacent contours have minimum area compared to the overlapped ones, In terms of a Set theory, overlapping is equivalent to a Union and non overlapping to a Difference.

And that’s it! after implement that condition, arbitrary graph sets can be decomposed in  minimum area loops or adjacent non overlapping sets.

contour (2)

 

 

Alpha QuadPaint tool

Hi

multiloops

Just wanted to early share a possible workflow of a work in progress tool named QuadPaint in the Retopo room. It will be a quite versatile and powerful semi automatic retopology allowing to quadrangulate arbitrary user defined (by stroking or painting) patches. Strokes can intersect defining sub-patches for further control and have different linear densities and in the future more means of quadrangulation control can be added like guide lines or control points of some sort.

My current efforts are focused on bring this tool to a production level state. There’s still many things to improve: from better quadrangulation, to auto snapping and smoothing (which I do manually for this video but once implemented you should see similar results) , adding few more things and to solve several instability bugs latter too.

This new tool shares the quadrangulation code base with QuadFill and CloseHolesRtool (man I should name it better ;) ) so once I improve this the rest will be improved too.

Raul

stroke

Currently I’m working in several tools that share a common code base, and one of the core algorithm of such tools is the procedure to extract closed contour loops from a set of arbitrary oriented and intersecting hand drawn strokes.

This tools are work in progress and more on alpha stages but progressing very well. I show you the internal debug information from the algorithm output.

RShell tool

Hi :)

As stated by this request report by AbnRanger:

It can be incredibly hard to create some thickness or a shell, in 3D Coat without a tool that gives us that ability, in the Retopo Room. You can see from the video, we currently have to send a one-sided mesh out to another app that has the tool, or spend needless time trying to replicate that, in 3D Coat.

Seems soon will no longer be the case ;)

 

Raw subdivision

raw

Some time ago as requested by an artist, I have implemented a subdivision type useful for low polygon models or hard edges geometry. At that time I was in Cuba and by some reason I can’t remember seems that code wont get into the main trunk. Since I have left all my previous work “behind” I had to re-implement again. but like a painter, the second time you do your artwork it will be different, now I have more experience so the rewrote feature is way better than the lost functionality :) Hope you like it.