Forums Houdini Indie and Apprentice Resample curve by density ramp [it was: Exponential points displacement, with no overlaps. What's the math behind?]

Resample curve by density ramp [it was: Exponential points displacement, with no overlaps. What's the math behind?]

   2494   3   0
User Avatar
Andr
Member
900 posts
Joined: Feb. 2016
Offline
 
Starting from a base line with evenly spread points (in green), I managed to displace them along the axis with this simple code:
float mult = ch("mult");
float baseIncr =  1 - (@ptnum / (@numpt*1.0));
float powerIncr = pow(baseIncr, 2); // exponent=2

// with exponent 2 and Mult > .583, point order is messed up
@P.x += powerIncr*mult;
(then I re-fit all the values in 0-1 space, not shown in the above code)

I'd like now to find the max range for Mult so that no overlaps occur with higher value of Mult.
When a point travels along the axis, it should not go past the next point.
Can't use for-loops/solvers.
Need to find the mathematical trick to link Mult and the Exponent(that can vary).
Edited by Andr - Feb. 14, 2019 03:53:59

Attachments:
Q_exp_ptDisplace.hiplc (148.2 KB)
expDisplace.JPG (17.0 KB)

 Report
User Avatar
Aizatulin
Member
476 posts
Joined: July 2005
Offline
 
Hi,

for this special case you can solve this problem with the following equation:

x0 + powerIncr0 * mult = x1 + powerIncr1 * mult, since the speed difference between x0 and x1 will be the highest.
So the result will be mult = (x0 - x1) / (powerIncr1 - powerIncr0). Putting in your values, you will have
(0 - 1/9) / ((9/10)^2 - 1) = 100 / 171 ~ 0.585.
But this solution will not work for every case … .

Have you tried to transform the u-values directly?
Edited by Aizatulin - Feb. 9, 2019 10:28:08

Attachments:
point_shift.hipnc (81.6 KB)

 Report
User Avatar
Andr
Member
900 posts
Joined: Feb. 2016
Offline
 
Hello Aizatulin,
thanks for the brush up of high school math, very much needed here eheh

I looked at your example, and you guessed right, I was indeed trying to find a general approach to resample a curve based on a density ramp.
Unfortunately it seems still occurring the mess up with the point overlapping.

I really wanted to find a mathematical solution to the problem, trying to link a function (in our case the ramp) to the resolution of a line. I guess there's some calculus involved?
Anyway, after lots of trial and error, I gave up to do it in a pure mathematical fashion (but still super curious about it!!), and went full brute-force

I ended up with an approach that seems to give pretty solid results: even if I'm not sure about the mathematical correctness of it, the point distribution seems to follow nicely the ramp, without overlapping.
So far I noticed 2 short comings:
  1. it's brute force, it works with exponential amount of your desired point resolution (exponent depend on the precision you need)so you can't have a high target resolution
  2. especially when you work with low points, it seems that the first point is missing. That's because of the final downsampling technique involved (delete points in 1 of 2 points step * n amounts of times). This could be fixed, I guess, by restoring the original ends point of the curve.
  3. Could anybody validate the correctness of the feedback loop inside? I have the feeling that sometimes it would loop only 1 time, regardless of how you set the value of the “precision” parameter that should drive the number of iterations of the loop. I'm pretty sure that I have seen a undesired final amount of points ( > than the set resolution that I set). But I can't really reproduce this behavior.


Thanks again for your supervision, cheers
Edited by Andr - Feb. 14, 2019 07:12:59

Attachments:
adn_curve_resample_by_density.hdalc (13.7 KB)

 Report
User Avatar
Aizatulin
Member
476 posts
Joined: July 2005
Offline
 
Hi,

it looks like, that your approach is working very nice and even fast. I'm afraid that there is no exact mathematical (analytical) solution for your problem. The only way to solve it is with numerical techniques. In my opinion the only downside of your approach is, that you have to start with randomly scattered points (you can't transform fixed points). Your loop seems to work.
If interested here is another approach using the “inverse transform sampling”. The problem here is, that you have to calculate the distribution function and its inverse numerically. So the solution will be potentially slow and/or not very precise. I usually try to avoid using the density, but instead drawing the inverse directly as ramp.

ps: I've just figured out, that the speed (of my alternative method) can be greatly increased by saving the distribution values to an array, which can be easily evaluated as function.
Edited by Aizatulin - Feb. 15, 2019 13:56:16

Attachments:
density_resample.hipnc (82.3 KB)
density_resampleX.hipnc (93.9 KB)

 Report
  • Quick Links