Stroking improvements

To accurately shape a stroke in QuadPaint, the user can create new pinned vertices with double click, in the future more powerful curve controls will be implemented.  Today I’ve improved the implementation by allowing the deformation to be independent from stroke density. (unlike previous algorithm) and I’ve solved a bug that prevented to simultaniously deform linked strokes.



Stroking improvements

QuadPaint control keys



This is the current main hot keys and actions to control the strokes of QuadPaint, and by changing the boundary you can control the inner quadrangulation.

Right click a vertex allows to smooth and move the stroke.

Hovering a vertex and pressing DEL , remove the vertices.

Double Click a vertex, will pin it so you basically created a new edge freely to move.

Double Click a segment, between 2 vertices will insert a new point, provided that the radius is smaller than the segment, otherwise will capture the closest vertex an pin it.

Ctrl + Click a vertex will split the stroke into 2 strokes.

Pressing +(plus) over a stroke will increase vertices count by 2. (some manual smoothing will be required to make vertices more even, will improve soon)

Pressing – (minus) will decrease by 2

Overlapping 2 vertices will merge them on mouse release.

Overlapping segments will be intersected on mouse up.

The numerical hint tells the number of vertices between 2 pinned points (inclusive), updated at mouse up.

Moving a vertices very far, after release will insert new divisions, moving them too close will merge them to maintain an average distance.

Sometimes the preview snap to surface incorrectly, but the final result will be much better because more smoothing and post process is used at execution time.


PS: seems I had some ghosts at my side because the room was completely silent and I got those eerie sounds Bouhahahaha

QuadPaint control keys

QuadPaint: your personal footprint.



Recently I’ve added two preview modes for QuadPaint:

Realtime: Where you can see changes continuously, is better suited for experimentation and small to medium patches.

Performance: Update is done at the end of every change, ideal for medium to large patches.

Off: No preview, use only if the patches have lots of self intersections and vertices count.

In every stroke, new vertices can be added, removed and pinned. Strokes can be cut and weld too. Strokes defines the boundary and also the internal polygon flow.

There are three quadrangulation algorithms as well:

Direct, it will find the optimal way to connect the existing boundary directly.

Paving: Will try to find an optimal tiling based on the boundary

Hybrid: A new algorithm that combines the best of both.

Hope you like it!

Video music: Guts and Bourbon, Kevin MacLeod.
QuadPaint: your personal footprint.

QuadPaint preview



Recently I have ironed out QuadPaint and improved lots of things under the hood. So far it is shaping into an awesome and fast retopology sketch tool.  Strokes also did allow to add, remove, collapse and split vertices for finer control over the output but is still not exposed to the GUI, I will add it soon. I’m considering also live previews so artists can have instant feedback over stroke changes. More importantly is the possibility to be the base of interesting new tools.

Hope you like it!

QuadPaint preview

Arbitrary contour retopology


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 )



Arbitrary contour retopology

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:


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?

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.


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:

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:



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 😉

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 🙂


Spline fitting

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.

After: new algorithm
After: new algorithm
Improving contour partitioning

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.

Quad strips

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.

SimpleStroke polish

RShell polished

Shell only selected elements
Shell only selected elements


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.

RShell polished

Improving the contour detection algorithm


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)



Improving the contour detection algorithm

Alpha QuadPaint tool



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.


Alpha QuadPaint tool