Hacker News Reader

Comment by phkahler | Hacker News Reader

There is a nice C++ (GPLv3+) implementation of a lot of these algorithms in Solvespace here:

https://github.com/solvespace/solvespace/blob/master/src/srf...

I'll be having a read of this to see if we can improve on some of these. In particular I've wanting to add curve-curve intersection as in section 29:

https://pomax.github.io/bezierinfo/#curveintersection

I had already considered that exact approach, but there are cases (in CAD anyway) where portions of 2 curves may exactly overlap. In that case we'd want to identify the overlapping region and split the 2 curves into 3. These special cases might seem like corner cases and they are, but they come up in practice more than I'd like.

View on HN

They come up in practice a LOT actually. The challenge with curve/curve intersections boils down to tolerances. Visualize two circles with different radii, with the smaller circle inside the larger circle, that meet at a single point. When understanding those circles as primitives (centerpoint, radius) finding that intersection point is relatively trivial. However when simply thinking of these as arbitrary curves, we have a condition where those curves are getting progressively closer together, but it's really hard to tell if they exactly touch, and exactly where.

Of course at a point we'll get close enough to consider there to be some intersection, but do we get "close enough" for a single point? for a portion of each of the curves? Does the result change with the scale of the circles? Does it scale when the relative radius between the circles changes? Making those kinds of judgement calls within the algorithms is really a challenge, but makes a huge difference when building a geometry library and for usability (for other developers, and end users). Knowing your use cases may be helpful in determining what's the right approach for these situations.

>> we have a condition where those curves are getting progressively closer together, but it's really hard to tell if they exactly touch, and exactly where.

OMG different curves and surfaces becoming tangent at a point is a huge pain. It's tempting to say that it tends to happen at the ends and can be checked for as a special case, or an algorithm tweaked based on that assumption, but then someone will find a perfectly reasonable construction that results in tangency at some arbitrary place and the problem returns.

Reply on news.ycombinator.com