frontpage.
newsnewestaskshowjobs

Made with ♥ by @iamnishanth

Open Source @Github

Open in hackernews

A fast 3D collision detection algorithm

https://cairno.substack.com/p/improvements-to-the-separating-axis
167•OlympicMarmoto•9h ago
I discovered this collision detection algorithm during COVID and finally got around to writing about it.

github repo: https://github.com/cairnc/sat_blog

Comments

double051•8h ago
Hey that's Ascension from Halo 2. Cool test case!
chickenzzzzu•6h ago
Real OGs know :) I used to love all of the super bounces and out of bounds tricks, though I think Ascension didn't really have many of the latter
reactordev•7h ago
This is novel indeed! What about non-spherical shapes? Do we assume a spherical bounds and just eat the cost? Either way, narrow phase gets extremely unwieldy when down to the triangle level. Easy for simple shapes but if you throw 1M vertices at it vs 1M vertices you’re going to have a bad time.

Any optimization to cut down on ray tests or clip is going to be a win.

bruce343434•7h ago
Most likely this can be preceded by testing branches of some spatial hierarchy datastructure, 1 million squared is a lot to compute no matter the algorithm
reactordev•7h ago
Without optimizations of the vertices buffer, correct, it’s a 1T loop. But we can work on faces and normals so that reduces it by a factor of 3. We can octree it further as well spatially but…

There’s a really clever trick Unreal does with their decimation algorithm to produce collision shapes if you need to. I believe it requires a bake step (pre-compute offline).

I’d be fine with a bake step for this.

OlympicMarmoto•6h ago
Do you mean non-convex shapes? You can do a convex decomposition and then test all pairs. Usually games accelerate this with a BVH.
andrewmcwatters•5h ago
Usually you have a render model and a physical model which is a degenerate version of the viewed object, with some objects tailored for picking up, or allowing objects to pass through a curved handle, etc.

I would assume using this algorithm wouldn't necessarily change that creation pipeline.

reactordev•3h ago
I’m trying to find a way to NOT have hull models included in my games. Saving players potentially GBs of disk space.

Constructing Bvh’s on the fly from the high fidelity models we use. Without incurring a performance penalty like we are. So we can improve collision detection instead of clipping due to low res hull models.

The OP’s source code builds a Bvh but it still does so in a way that we’re able to clog it with 34M vertices. Sadly, we’re still going to have to explode geometry and rebuild a hierarchy in order to iterate over collisions fast. I do like the approach OP took but we both suffer from the same issues.

bob1029•4h ago
> Do we assume a spherical bounds and just eat the cost?

We pick the bounding volume that is most suitable to the use case. The cost of non-spherical bounding volumes is often not that severe when compared to purely spherical ones.

https://docs.bepuphysics.com/PerformanceTips.html#shape-opti...

Edit: I just noticed the doc references this issue:

https://github.com/bepu/bepuphysics2/issues/63

Seems related to the article.

reactordev•2h ago
Yeah triangle-triangle is really dependent on number of triangles.

I noticed that issue is 6 years old, what’s the current state?

msteffen•6h ago
I'm trying to work through the math here, and I don't understand why these two propositions are equivalent:

1) min_{x,y} |x-y|^2

   x ∈ A

   y ∈ B
2) = min_{x,y} d

   d ≥ |x-y|^2

   x ∈ A

   y ∈ B
What is 'd'? If d is much greater than |x-y|^2 at the actual (x, y) with minimal distance, and equal to |x-y|^2 at some other (x', y'), couldn't (2) yield a different, wrong solution? Is it implied that 'd' is a measure or something, such that it's somehow constrained or bounded to prevent this?
mathgradthrow•5h ago
I can't read substack on my phone, so I can't see the article, but the correct statement that is closest to what you have written is just that d is any real number satisfying this inequality. We define a subset U of AxBxR by

U={(a,b,x):x>|a-b|^2}

and then were looking for the infimum of (the image of) U under the third coordinate function

d(a,b,x)=x

Jaxan•4h ago
But why would d be much greater. The problem asks to minimise d, and so it cannot be greater than the smallest |x-y|^2.
OlympicMarmoto•4h ago
This is the epigraph form of the problem. You try to find the point with the lowest height in the epigraph.

https://en.wikipedia.org/wiki/Epigraph_(mathematics)

markisus•2h ago
I think you are missing that d, x, and y are variables that get optimized over. Any choice of d lower than the the solution to 1) is infeasible. Any d higher than the solution to 1) is suboptimal.

edit: I see now that the problem 2) is missing d in the subscript of optimization variables. I think this is a typo.

leoqa•6h ago
Aside: I learned the Sep Axis Theorem in school and often use it for interviews when asked about interesting algorithms. It's simple enough that you can explain it to non-technical folks. "If I have a flashlight and two objects, I can tell you if they're intersected by shining the light on it". Then you can explain the dot product of the faces, early-exit behavior and MTV.
Animats•5h ago
Nice. It's definitely an optimization problem. But you have to look at numerical error.

I had to do a lot of work on GJK convex hull distance back in the late 1990s. It's a optimization problem with special cases.

Closest points are vertex vs vertex, vertex vs edge, vertex vs face, edge vs edge, edge vs face, and face vs face. The last three can have non-unique solutions. Finding the closest vertices is easy but not sufficient. When you use this in a physics engine, objects settle into contact, usually into the non-unique solution space. Consider a cube on a cube. Or a small cube sitting on a big cube. That will settle into face vs face, with no unique closest points.

A second problem is what to do about flat polygon surfaces. If you tesselate, a rectangular face becomes two coplanar triangles. This can make GJK loop. If you don't tesselate, no polygon in floating point is truly flat. This can make GJK loop. Polyhedra with a minimum break angle between faces, something most convex hullers can generate, are needed.

Running unit tests of random complex polyhedra will not often hit the hard cases. A physics engine will. The late Prof. Steven Cameron at Oxford figured out solutions to this in the 1990s.[1] I'd discovered that his approach would occasionally loop. A safe termination condition on this is tough. He eventually came up with one. I had a brute force approach that detected a loop.

There's been some recent work on approximate convex decomposition, where some overlap is allowed between the convex hulls whose union represents the original solid. True convex decomposition tends to generate annoying geometry around smaller concave features, like doors and windows. Approximate convex decomposition produces cleaner geometry.[2] But you have to start with clean watertight geometry (a "simplex") or this algorithm runs into trouble.

[1] https://www.cs.ox.ac.uk/stephen.cameron/distances/

[2] https://github.com/SarahWeiii/CoACD

OlympicMarmoto•3h ago
> But you have to look at numerical error.

Yeah I agree, the error analysis could be many blogs in and of itself. I kinda got tired by the end of this blog. I would like to write a post about this in the future. For global solvers and iterative.

> Finding the closest vertices is easy but not sufficient.

As I'm sure you are aware, most GJK implementations find the closest features and then a one shot contact manifold can be generated by clipping the features against each other. When GJK finds a simplex of the CSO, each vertex of the simplex keeps track of the corresponding points from A and B.

> A second problem is what to do about flat polygon surfaces

Modern physics engines and the demo I uploaded do face clipping which handle this. For GJK you normally ensure the points in your hull are linearly independent.

CamperBob2•3h ago
There's been some recent work on approximate convex decomposition, where some overlap is allowed between the convex hulls whose union represents the original solid.

I wonder if it would be smart to restate the problem in just those terms -- managing bounding-volume overlap rather than interpenetration at the geometric level.

If everything is surrounded by bounding spheres, then obviously collision detection in the majority of cases is trivial. When two bounding spheres do intersect, they will do so at a particular distance and at a unique angle. There would then be a single relevant quantity -- the acceptable overlap depth -- that would depend on the angle between the BV centers, the orientation of the two enclosed objects, and nothing else. Seems like something that would be amenable to offline precomputing... almost like various lighting hacks.

Ultimately I guess you have to deal with concavity, though, and then the problem gets a lot nastier.

MortyWaves•5h ago
I’m getting sick of the number of links submitted to HN blasting me with cookie spam bullshit.
EGreg•3h ago
Nice to see this! I was writing about this topic 25 years ago: https://www.flipcode.com/archives/Theory_Practice-Issue_01_C...

And part two: https://www.flipcode.com/archives/Theory_Practice-Issue_02_C...

socalgal2•2h ago
Related? This was posted a few days ago

https://news.ycombinator.com/item?id=44334403

OlympicMarmoto•1h ago
No AVBD is a solver, they use standard collision detection routines.

Biomni: A General-Purpose Biomedical AI Agent

https://github.com/snap-stanford/Biomni
115•GavCo•4h ago•24 comments

Tree Borrows

https://plf.inf.ethz.ch/research/pldi25-tree-borrows.html
385•zdw•9h ago•60 comments

MCP-B: A Protocol for AI Browser Automation

https://mcp-b.ai/
27•bustodisgusto•1h ago•8 comments

Show HN: FlopperZiro – A DIY open-source Flipper Zero clone

https://github.com/lraton/FlopperZiro
155•iraton•6h ago•42 comments

Show HN: MCP server for searching and downloading documents from Anna's Archive

https://github.com/iosifache/annas-mcp
37•iosifache•2h ago•20 comments

Jank Programming Language

https://jank-lang.org/
184•akkad33•3d ago•37 comments

A Typology of Canadianisms

https://dchp.arts.ubc.ca/how-to-use
22•gnabgib•1h ago•5 comments

Multi-Region Row Level Security in CockroachDB

https://www.cockroachlabs.com/blog/fine-grained-access-control-row-level-security/
14•rusticwizard•1h ago•0 comments

A fast 3D collision detection algorithm

https://cairno.substack.com/p/improvements-to-the-separating-axis
167•OlympicMarmoto•9h ago•23 comments

HyAB k-means for color quantization

https://30fps.net/pages/hyab-kmeans/
17•ibobev•2h ago•6 comments

Configuring Split Horizon DNS with Pi-Hole and Tailscale

https://www.bentasker.co.uk/posts/blog/general/configuring-pihole-to-serve-different-records-to-different-clients.html
64•gm678•6h ago•16 comments

Linda Yaccarino is leaving X

https://www.nytimes.com/2025/07/09/technology/linda-yaccarino-x-steps-down.html
346•donohoe•8h ago•513 comments

White Noise – secure and private messenger

https://www.whitenoise.chat/
19•onhacker•2h ago•3 comments

Archaeologists unveil 3,500-year-old city in Peru

https://www.bbc.co.uk/news/articles/c07dmx38kyeo
112•neversaydie•2d ago•27 comments

Understand CPU Branch Instructions Better

https://chrisfeilbach.com/2025/07/05/understand-cpu-branch-instructions-better/
19•mfiguiere•3d ago•3 comments

Would You Like an IDOR With That? Leaking 64m McDonald's Job Applications

https://ian.sh/mcdonalds
31•samwcurry•4h ago•18 comments

Ruby 3.4 frozen string literals: What Rails developers need to know

https://www.prateekcodes.dev/ruby-34-frozen-string-literals-rails-upgrade-guide/
192•thomas_witt•3d ago•99 comments

Making Explainable Minesweeper

https://sublevelgames.github.io/blogs/2025-07-06-making-explainable-minesweeper/
12•greentec•3d ago•7 comments

The most otherworldly, mysterious forms of lightning on Earth

https://www.nationalgeographic.com/science/article/lightning-sprites-transient-luminous-events-thunderstorms
46•Anon84•3d ago•13 comments

An ambitious vision of a city built from lava

https://www.cnn.com/2025/07/03/style/lava-material-architecture-venice-biennale
3•dabinat•2d ago•0 comments

Most RESTful APIs aren't really RESTful

https://florian-kraemer.net//software-architecture/2025/07/07/Most-RESTful-APIs-are-not-really-RESTful.html
273•BerislavLopac•16h ago•441 comments

QRS: Epsilon Wrangling

https://www.tbray.org/ongoing/When/202x/2025/07/07/Epsilon-Wrangling
10•zdw•3h ago•0 comments

Nuclear Waste Reprocessing Gains Momentum in the U.S.

https://spectrum.ieee.org/nuclear-waste-reprocessing-transmutation
83•rbanffy•8h ago•71 comments

Bootstrapping a side project into a profitable seven-figure business

https://projectionlab.com/blog/we-reached-1m-arr-with-zero-funding
783•jonkuipers•2d ago•208 comments

Phrase origin: Why do we "call" functions?

https://quuxplusone.github.io/blog/2025/04/04/etymology-of-call/
239•todsacerdoti•19h ago•168 comments

Memory-Level Parallelism: Apple M2 vs. Apple M4

https://lemire.me/blog/2025/07/09/memory-level-parallelism-apple-m2-vs-apple-m4/
22•zdw•2h ago•2 comments

Why LLMs Can't Write Q/Kdb+: Writing Code Right-to-Left

https://medium.com/@gabiteodoru/why-llms-cant-write-q-kdb-writing-code-right-to-left-ea6df68af443
170•gabiteodoru•1d ago•116 comments

Evolution Mail Users Easily Trackable

https://www.grepular.com/Evolution_Mail_Users_Easily_Trackable
95•mike-cardwell•6h ago•53 comments

7-Zip for Windows can now use more than 64 CPU threads for compression

https://www.7-zip.org/history.txt
248•doener•2d ago•169 comments

I Ported SAP to a 1976 CPU. It Wasn't That Slow

https://github.com/oisee/zvdb-z80/blob/master/ZVDB-Z80-ABAP.md
125•weinzierl•2d ago•56 comments