7 ms·

Repulsive Curves

329 points by lnyan 5y ago

zokier 5y ago
This could work well for PCB trace routing optimization too? Handling multiple layers might be bit difficult, but maybe not insurmountable?
ur-whale 5y ago
Keenan Crane's [1] lab has been putting out some top notch research in recent years. In particular, their work on discrete differential geometry [2] is really worth diving into (and Mr Crane is a really good pedagogue). [1] https://www.cs.cmu.edu/~kmcrane/ https://www.cs.cmu.edu/~kmcrane/ [2] https://www.youtube.com/watch?v=mas-PUA3OvA&list=PL9_jI1bdZmz0hIrNCMQW1YmZysAiIYSSS https://www.youtube.com/watch?v=mas-PUA3OvA&list=PL9_jI1bdZm...
dieselgate 5y ago
The mobile experience is unfortunately quite repulsive so I didn’t read the article :( But wanted to..
arc-in-space 5y ago
Hold on, wasn't there a similar paper last year wrt non-intersecting shape/mesh optimization? (edit: I think it was a topology paper actually) I found this: https://arxiv.org/pdf/2201.06256.pdf https://arxiv.org/pdf/2201.06256.pdf but I don't think it's what I'm thinking of.
- thechao 5y ago
  Yes; Keenan Crane does amazing work; his book (and online video series) on Discrete Differential Geometry are really good.
- mkl 5y ago
  This shape filling curve method probably isn't what you're thinking of either, but it's neat and similar to the OP linked paper in 2D: https://news.ycombinator.com/item?id=25905534 https://news.ycombinator.com/item?id=25905534 & https://www.vidarholen.net/contents/blog/?p=1062 https://www.vidarholen.net/contents/blog/?p=1062
bwestergard 5y ago
The graph layout example is really compelling.
lewiso1 5y ago
One of the insights here is using the “tangent point energy” as part of the repulsion loss function. If anyone’s used, or knows of, a python implementation of this TPE function then please lmk!
iandanforth 5y ago
The video has some really interesting / creative examples. Using this for path planning by treating paths as curves through space-time was particularly impressive.
keenancrane 5y ago
If you liked repulsive curves, you may also enjoy repulsive surfaces: https://www.cs.cmu.edu/~kmcrane/Projects/RepulsiveSurfaces/index.html https://www.cs.cmu.edu/~kmcrane/Projects/RepulsiveSurfaces/i... Deep dive into repulsive geometry here: https://youtu.be/dtYGiCpzzbA https://youtu.be/dtYGiCpzzbA
- gfody 5y ago
  that talk made it really clear how tangent-point energy is easier to compute than mobius energy but not why it's a good proxy for it, it seems like a semihack
- infogulch 5y ago
  Nice talk! This seems like it could be an interesting tool model real phenomena. Have you considered if you can invert this to derive which constraints and energy function best match a particular sample? Say, take a video of cars entering and exiting a highway ramp, what constraints and energy functions best model the paths taken? This could be individual as well, for example a particular car may be driven "aggressively" according to humans, if you derived the constraints this way could you reliably predict humans' scoring?
- arc-in-space 5y ago
  Oh, that's actually the one I was looking for. I should have thought to check your publications page first.
- mkl 5y ago
  Hi Keenan. What do you use to generate your figures of surfaces with lines and other things drawn on them, e.g. figures 2-6 of the geodesic survey paper (http://www.cs.cmu.edu/~kmcrane/Projects/GeodesicSurvey/GeodesicSurvey.pdf http://www.cs.cmu.edu/~kmcrane/Projects/GeodesicSurvey/Geode...)? Lots of great pictures like that in the SIGGRAPH 2013 Course Notes too (https://www.cs.cmu.edu/~kmcrane/Projects/DDG/paper.pdf https://www.cs.cmu.edu/~kmcrane/Projects/DDG/paper.pdf). I have made some similar figures with TikZ, but it's a lot of work and the results aren't as nice as I'd like.
  - 5y ago
nateburke 5y ago
FWIW, Nathan Dunfield's hand drawings are typically very difficult to improve upon. This is an impressive paper. Thank you for sharing!
- ykonstant 5y ago
  His latex templates, too.
ThouYS 5y ago
Keenan Crane simply makes the most beautiful papers out there
- Olumde 5y ago
  He's a genius. A researchers best hope is that he doesn't stumble on their research subtopic.
- natly 5y ago
  He's really inspirational. He's always really helpful has a wonderful energy on twitter and the geometry discord he's part of, and seems like a really great (and very intelligent) guy all around.
cs702 5y ago
This is immediately useful for a huge number of practical real-world applications. Make sure to watch the short explanatory video (and turn the sound on) -- here's the direct link: https://www.youtube.com/watch?v=-uXFYpVumh4 https://www.youtube.com/watch?v=-uXFYpVumh4 The short video is great. The paper looks great (based on a very quick skim; this is an area in which the authors have far more expertise than me). The high-level explanations are great. The web page is great -- informative and to-the-point. Really impressive work! -- EDIT: The senior author is here at https://news.ycombinator.com/item?id=31134139 https://news.ycombinator.com/item?id=31134139 -- his comment should probably be above mine. Please upvote it.
- dwallin 5y ago
  The use as a pathfinding technique immediately stood out to me. If I'm understanding the way it works it results in variable speed, making it less useful for some game purposes. But this is super useful for animation. If you are trying to model crowd behavior your entities will seemingly speed up and slow down to allow others to pass but still arrive where you need them to at specific times.
  - cs702 5y ago
    One thoughts I had when first I skimmed the paper is that it should be straightforward to train a small, fast DNN to approximate the technique, and then use the DNN for applications that have more stringent performance requirements, including games.
lordleft 5y ago
Beautiful & compelling presentation
yowlingcat 5y ago
Wow, imagine this could be very useful for a variety of logistics/routing applications (IE train routing, assembly line optimization, self-driving cars). Perhaps this kind of stuff is in play there already and this just helps make it easier to visualize? Lovely visualizations as well. Really makes it tangible.
rland 5y ago
I can think immediately of applications: - bio engineering -- predicting (?) or designing (?) molecules that are large chains to perform some particular function - coverage path planning -- sort of a "roomba" problem -- find a continuous path, through a space, that covers the space - 3-D printing -- find the extrusion path that maximally covers some area or areas with high strength with a minimum amount of material
- cryptonector 5y ago
  I'm also wondering if this might inspire ideas for how blood vessels end up getting placed by growing bodies, etc.
shadowgovt 5y ago
The applications in particular are the piece I find most enjoyable about this publication. The robot path distance maximization, space-filling, and auto-earbud-untangler are pretty neat.

329 points by lnyan 5y ago

This could work well for PCB trace routing optimization too? Handling multiple layers might be bit difficult, but maybe not insurmountable?

ur-whale 5y ago

Keenan Crane's [1] lab has been putting out some top notch research in recent years. In particular, their work on discrete differential geometry [2] is really worth diving into (and Mr Crane is a really good pedagogue). [1] https://www.cs.cmu.edu/~kmcrane/ https://www.cs.cmu.edu/~kmcrane/ [2] https://www.youtube.com/watch?v=mas-PUA3OvA&list=PL9_jI1bdZmz0hIrNCMQW1YmZysAiIYSSS https://www.youtube.com/watch?v=mas-PUA3OvA&list=PL9_jI1bdZm...

dieselgate 5y ago

The mobile experience is unfortunately quite repulsive so I didn’t read the article :( But wanted to..

arc-in-space 5y ago

Hold on, wasn't there a similar paper last year wrt non-intersecting shape/mesh optimization? (edit: I think it was a topology paper actually) I found this: https://arxiv.org/pdf/2201.06256.pdf https://arxiv.org/pdf/2201.06256.pdf but I don't think it's what I'm thinking of.

thechao 5y ago
Yes; Keenan Crane does amazing work; his book (and online video series) on Discrete Differential Geometry are really good.
mkl 5y ago
This shape filling curve method probably isn't what you're thinking of either, but it's neat and similar to the OP linked paper in 2D: https://news.ycombinator.com/item?id=25905534 https://news.ycombinator.com/item?id=25905534 & https://www.vidarholen.net/contents/blog/?p=1062 https://www.vidarholen.net/contents/blog/?p=1062

bwestergard 5y ago

The graph layout example is really compelling.

lewiso1 5y ago

One of the insights here is using the “tangent point energy” as part of the repulsion loss function. If anyone’s used, or knows of, a python implementation of this TPE function then please lmk!

iandanforth 5y ago

The video has some really interesting / creative examples. Using this for path planning by treating paths as curves through space-time was particularly impressive.

keenancrane 5y ago

If you liked repulsive curves, you may also enjoy repulsive surfaces: https://www.cs.cmu.edu/~kmcrane/Projects/RepulsiveSurfaces/index.html https://www.cs.cmu.edu/~kmcrane/Projects/RepulsiveSurfaces/i... Deep dive into repulsive geometry here: https://youtu.be/dtYGiCpzzbA https://youtu.be/dtYGiCpzzbA

gfody 5y ago
that talk made it really clear how tangent-point energy is easier to compute than mobius energy but not why it's a good proxy for it, it seems like a semihack
infogulch 5y ago
Nice talk! This seems like it could be an interesting tool model real phenomena. Have you considered if you can invert this to derive which constraints and energy function best match a particular sample? Say, take a video of cars entering and exiting a highway ramp, what constraints and energy functions best model the paths taken? This could be individual as well, for example a particular car may be driven "aggressively" according to humans, if you derived the constraints this way could you reliably predict humans' scoring?
arc-in-space 5y ago
Oh, that's actually the one I was looking for. I should have thought to check your publications page first.
mkl 5y ago
Hi Keenan. What do you use to generate your figures of surfaces with lines and other things drawn on them, e.g. figures 2-6 of the geodesic survey paper (http://www.cs.cmu.edu/~kmcrane/Projects/GeodesicSurvey/GeodesicSurvey.pdf http://www.cs.cmu.edu/~kmcrane/Projects/GeodesicSurvey/Geode...)? Lots of great pictures like that in the SIGGRAPH 2013 Course Notes too (https://www.cs.cmu.edu/~kmcrane/Projects/DDG/paper.pdf https://www.cs.cmu.edu/~kmcrane/Projects/DDG/paper.pdf). I have made some similar figures with TikZ, but it's a lot of work and the results aren't as nice as I'd like.
- 5y ago

nateburke 5y ago

FWIW, Nathan Dunfield's hand drawings are typically very difficult to improve upon. This is an impressive paper. Thank you for sharing!

ykonstant 5y ago
His latex templates, too.

ThouYS 5y ago

Keenan Crane simply makes the most beautiful papers out there

Olumde 5y ago
He's a genius. A researchers best hope is that he doesn't stumble on their research subtopic.
natly 5y ago
He's really inspirational. He's always really helpful has a wonderful energy on twitter and the geometry discord he's part of, and seems like a really great (and very intelligent) guy all around.

cs702 5y ago

This is immediately useful for a huge number of practical real-world applications. Make sure to watch the short explanatory video (and turn the sound on) -- here's the direct link: https://www.youtube.com/watch?v=-uXFYpVumh4 https://www.youtube.com/watch?v=-uXFYpVumh4 The short video is great. The paper looks great (based on a very quick skim; this is an area in which the authors have far more expertise than me). The high-level explanations are great. The web page is great -- informative and to-the-point. Really impressive work! -- EDIT: The senior author is here at https://news.ycombinator.com/item?id=31134139 https://news.ycombinator.com/item?id=31134139 -- his comment should probably be above mine. Please upvote it.

dwallin 5y ago
The use as a pathfinding technique immediately stood out to me. If I'm understanding the way it works it results in variable speed, making it less useful for some game purposes. But this is super useful for animation. If you are trying to model crowd behavior your entities will seemingly speed up and slow down to allow others to pass but still arrive where you need them to at specific times.
- cs702 5y ago
  One thoughts I had when first I skimmed the paper is that it should be straightforward to train a small, fast DNN to approximate the technique, and then use the DNN for applications that have more stringent performance requirements, including games.

lordleft 5y ago

Beautiful & compelling presentation

yowlingcat 5y ago

Wow, imagine this could be very useful for a variety of logistics/routing applications (IE train routing, assembly line optimization, self-driving cars). Perhaps this kind of stuff is in play there already and this just helps make it easier to visualize? Lovely visualizations as well. Really makes it tangible.

rland 5y ago

I can think immediately of applications: - bio engineering -- predicting (?) or designing (?) molecules that are large chains to perform some particular function - coverage path planning -- sort of a "roomba" problem -- find a continuous path, through a space, that covers the space - 3-D printing -- find the extrusion path that maximally covers some area or areas with high strength with a minimum amount of material

cryptonector 5y ago
I'm also wondering if this might inspire ideas for how blood vessels end up getting placed by growing bodies, etc.

shadowgovt 5y ago

The applications in particular are the piece I find most enjoyable about this publication. The robot path distance maximization, space-filling, and auto-earbud-untangler are pretty neat.