mmorse1217

Wow thats very clever with much better constants; thanks for this! I will need to give this a try.

Discretize the AABB with a certain length proportional to the morton code grid size so that each sample point will land in a distinct but continuous sequence of morton codes enclosing the AABB, compute the hash of each of those points, then dump all of those morton codes into the sort and reverse lookup the other AABBs with the same morton code :)

The problem comes at scale, when you have many AABBs with different sizes. Memory pressure can be punishing and you are bottlenecked by the network for distributed solutions. Is there a faster way with fewer points? I would love to know!

Yikes, that was too real

Hey Jeff, wherever you are: this is awesome work! I’ve wanted to try something like this for a while and was very excited for the RDMA over thunderbolt news.

But I mostly want to say thanks for everything you do. Your good vibes are deeply appreciated and you are an inspiration.

Your comment motivated me to also comment :) I agree: Bézier curves and b-splines have a lot of rich geometry baked it, so it makes sense to use it, especially if you can avoid second derivatives. I think I misunderstood your comment about the extra control point work to find an initial guess. It looks like we’re saying something pretty close though: you can split the curve smartly to remove the single crossing in this case, which skips all the recursion that I’m suggesting, which is probably better.

Yes the real trouble is true optimality guarantees. I remember that there were edge cases of the above approach needed that a lot of subdivision steps to succeed for general degree curves, so it might end up worse than a more rigorously justified approach in these cases.

This is a pretty good foundational reference for Bézier curves and b-splines https://www.sciencedirect.com/book/9780122490521/curves-and-...

The trick is that you only solve Newton on a single subcurve: you recursively find the closest control point on all subcurves, split that subcurve and repeat until the closest control point doesn’t move much, or just however many subdivision steps work in practice. So the last curve that you apply Newton to should be smooth enough to succeed. I think there are edge cases with cusps, but I can’t exactly remember the theoretical guarantees anymore.

I think this is the main reference for this algorithm (should be able to search for the pdf): https://www.sciencedirect.com/science/article/abs/pii/S01678...

Hey, thanks for the nice post. I really enjoyed reading it; it’s good see this kind of thing on the front page.

Since you’re interested in doing this on GPU, an approach that might be interesting to you (although not necessarily more efficient) would be to leverage the intrinsic properties of Bezier curves to feed a near-optimal initial guess to Newton. Some useful facts about Bezier curves: i) Bezier control points form a convex hull of the curve they define ii) Bezier curves defined on [0,1] can be split into two bezier curves, each defined on [0,t] and [t,1] that define the same curve, with a tighter control polygon. iii) This Bezier curve splitting can be done using repeated linear combinations of Bezier control points, so you can skip evaluating Bernstein polynomials directly. iv) there is a mapping from Bezier control points to their corresponding value in the [0,1] parameter space (the term for this for B-Splines is greville abcissae, I’m not sure that there is an explicit name for the equivalent for Bezier curves, but basically the preimage of control point b_i of a degree d curve is i/d, i=0,…,d+1).

These things together sort of imply an algorithm: 1. Subdivide the Bezier curve c into 2 or 3 curves c_1, c_2, c_3 2. Find the closest control point b_j to the target point x 3. Choose the curve c_i corresponding to b_j: this subcurve contains the closest point to x 4. Go to step 1 and repeat this loop several times with c = c_i 5. Then, compute the preimage of the closest control point b_j to x on c (j/d plus some shift and rescaling). This value, t’, will be the initial guess to Newton’s method. 6. Solve for the closest point on the selected subcurve c to x with Newton’s method; this should converge in very few steps because your initial guess is so good, quadratic convergence, blah, blah blah.

The break-even point for this kind of algorithm vs. a derivative based algorithm is very unclear on CPU. But, for GPU, I think the computation can be structured in an architecture friendly way; since computing the euclidean distance between x with all control points and the bezier curve splitting can written in a vectorizable manner, you will probably see a decent speed up. I’ve only really worked with CUDA though, so I’m not sure if this idea maps very cleanly to GLSL.

Here’s an example of the algorithm above for CPU if you are interested: https://github.com/qnzhou/nanospline/commit/5ac97722414dbc75...

Probably vision language models.

“There are no facts, only interpretations.” - Nietzsche

This site is pretty helpful for me with this sort of thing. The style is more technical though.

https://www.acsu.buffalo.edu/~adamcunn/probability/probabili...

Thanks for these references; I've been going down the research rabbit hole :)

I check my A1C every six months and I'm ok. I'm in decent shape also: regularly powerlifting, running, etc. I have a suspicion that there is a genetic component for me; there are some autoimmune issues in my family that haven't been attributed to a particular disorder and there is a chance of an underlying condition causing these autoimmune-like symptoms.

I don't think I've noticed facial numbness, but my limbs fall asleep quickly and my hands fall asleep if I am reading my phone/book while lying on my back after a couple minutes. I also drink a TON of water when drinking alcohol and am hungover for days afterwards. Since my electrolyte revelation, I started knocking back pedialyte before sleeping which helped a ton.

Sorry for the late reply, I pick up 99mg potassium + 200mg magnesium and had an unbelievable night's sleep and many symptoms improved dramatically. The second night was confounded by an evening workout, which can mess with electrolyte levels, but you have given me hope again. I just want to thank you again for continuing the tradition of changing someone's life with an innocuous HN comment :)

I see what you mean regarding the electrolyte measurements. After reading a bit about the disorders that you mentioned, it seems like they test for serum and excreted electrolyte levels to make a diagnosis. But based on your point above, these tests can be inconclusive. Were there certain diagnostic tests that were helpful to you in coming to your conclusion, or was it largely trial and error based on symptom management?

Thank you so much for sharing your experience and your research in the other comment. I understand that it's just a hypothesis, but I had almost given up and believed that this is just how life is now. I went to the ER for heart palpitations and told the doctors to check electrolyte levels and they flat out refused and discharged me. Between this and the potential renal issues, I at least have another avenue to try to address the underlying problem.

I'll try the potassium supplements and report back. Around how much are you supplementing each day? People shy away from potassium supplementation because it can cause heart palpitations, but I already have those, similar to yours, and RDA of potassium is over 3000mg, so it's only up from here :) Thanks again.

I have every single one of your symptoms and arrived at almost the same conclusion: taking electrolytes tablets intended for workout recovery (just sodium, magnesium and potassium, no sugar) improves alleviates almost all of my symptoms and gives me energy I haven't had since I was 12. I haven't been able to get a doctor to take me seriously for ten years. I will try the potassium + magnesium tablets at night instead of a generic multivitamin. Thank you so much for your comment.

Do you have any additional information about this relationship between CSF and electrolyte deficiency? Do you know anything about possible upstream causes of electrolyte deficiency? Any pointers would be super helpful.

Awesome book; great reference in grad school.

This implementation and associated paper improve the cache locality to make the algorithm more competitive https://github.com/dmalhotra/pvfmm

They compare solving toy problems with different methods here https://arxiv.org/pdf/1408.6497.pdf

But as you mention, this is just fiddling with constants, and it still may be too costly for your problem