Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Can't cut half sphere out of a shape in NURBS #652

Closed
xzcvczx opened this issue Jul 14, 2020 · 18 comments
Closed

Can't cut half sphere out of a shape in NURBS #652

xzcvczx opened this issue Jul 14, 2020 · 18 comments
Milestone

Comments

@xzcvczx
Copy link
Contributor

xzcvczx commented Jul 14, 2020

System information

SolveSpace version: 3.0-c4ca4be9

Operating system: kiss linux

Expected behavior

extrude cube, new sketch on a face, draw closed half circle, revolve, difference

cube with a half sphere cut out

Actual behavior

doesn't make the cut

Additional information

spherecut.zip

@whitequark
Copy link
Contributor

whitequark commented Jul 14, 2020

@phkahler PTAL

@phkahler
Copy link
Member

phkahler commented Jul 14, 2020

@xzcvczx and @whitequark It works if you check "force NURBS surfaces to triangle mesh" on the lathe group. I tried "Intersection" and that also worked for triangle mesh but not NURBS. So this looks like a typical NURBS issue. Then I decided to use "Revolve" instead of Lathe. Added a construction line perpendicular to the rotation axis (from the middle to the midpoint of the arc) so there would be a handle to drag. I constrained a point to the cube surface to set the angle to 180 degrees. This worked slightly better. NURBS Intersection actually worked correctly, but difference still did not. Triangle mesh worked fine of course. That doesn't help if you want to export STEP though.

This is another nice test case for the NURBS code and will have to wait for the next deep dive into that stuff.

@phkahler
Copy link
Member

phkahler commented Jul 14, 2020

Also for fun I replaced the arc with a rectangle. Lathe worked fine with difference and intersection. Tried the rectangle with Revolve and the NURBS had issues with both boolean operations. There seems to be more than one bug lurking in there.

@phkahler
Copy link
Member

phkahler commented Aug 13, 2020

@xzcvczx Update. Since we just merged #673 to master, you will be able to work around this problem with the attached.
spherecut2.zip

It still doesn't like curves coincident with the top of the box but it's fine that the sphere center is on the top. Just keep the arc more than 90 degrees and less than 180.
spherecut

@Christoph-D
Copy link
Contributor

Christoph-D commented Sep 20, 2020

For me, lathe difference with a triangle fails in the same way:
triangle
triangle.slvs.zip

Same behavior with circles, arcs, bezier curves. Rectangles work for some reason.

So the problem doesn't seem to be restricted to circles or arcs.

@phkahler
Copy link
Member

phkahler commented Sep 20, 2020

This may be related to #354

Here the triangle works if you draw the sketch in a plane not coincident with or perpendicular to the cube face. It's still OK if the rotation axis is on the face. It does not work if the rotation axis is coincident with the face AND is one of the sketch line.

One thing about rectangles - any face that is swept out by a line perpendicular to the rotation axis is recognized as a flat/planar surface and is converted to one. Every other surface created by lathe/revolve has order 2 by N where N is the order of the swept curve.

@Christoph-D
Copy link
Contributor

Christoph-D commented Sep 22, 2020

After playing around a bit more, I suspect the numeric intersection part in SSurface::IntersectAgainst in surfinter.cpp may not be quite right.

The code seems to assume that at least one trim curve of one shell and at least one surface of the other shell need to intersect, and tangents don't count. But shells can intersect without any curves intersecting any surfaces.

I constructed an example of a non-empty shell intersection where none of the trim curves intersect a surface of the other shell. And indeed, the setup shows the same bug, boolean operations don't work. The setup:
lathe-union
Difference doesn't work:
lathe-difference
lathe-intersection.slvs.zip

In the original case of this bug, I assume the same thing happens, because

  • none of the curves of the box intersect the lathe object
  • none of the curves of the lathe object properly intersect the surfaces of the box (the intersecting curves are either coincident or intersect only in one of their endpoints).

Still only a theory and I'm also not really familiar with NURBS, so this may be wrong.

@Christoph-D
Copy link
Contributor

Christoph-D commented Sep 22, 2020

As @phkahler said, revolution/lathe of a rectangle produces planes. Intersections of two planes are special cased in SSurface::IntersectAgainst, which explains why the bug shows up only in the general case.

@phkahler
Copy link
Member

phkahler commented Sep 22, 2020

@Christoph-D Thanks for looking into this, the NURBS code is fairly exotic and not many understand it. The most recent improvement was here: #673

First off, I think you're right but there's more.

Some background:

All "solids" in SolveSpace are shells made of NURBS surfaces. each surface consists of a surface defined by MxN control points and weights, and a set of trim curves. When you extrude a sketch, the top and bottom of that solid are simply flat NURBS surfaces with the sketch curves used as trim curves. The lengthwise surface are formed formed 1 per sketch curve and are trimmed on the ends by that curve (and it's copy) and by 1st order lines along the 2 edges.

For Lathe objects each sketch curve sweeps out 4 nurbs surfaces of 90 degrees each similar to how extrusions work, but they are 2nd degree in the "around the circle" direction and control points are added. This creates 4 "seams" between the 90 degree sections. Each section is trimmed by 2 seams that are copies of the original sketch curve and 2 seams that are just 90 degree arcs. So a torus has 16 surface patches (the base circle in a sketch produces 4 90 degree curves in the sketch plane).

Revolve does a combination of sections like Lathe but adds the end caps like Extrude. Helix is just lathe with appropriate displacement along the rotation axis and can have any number of surface patches (90 degrees or less) because you can twist it until your machine dies.

Everything I've described above creates trim curves that are flagged as "exact" in the code. There is a boolean for each surface patch, as well as an optional Rational curve definition that can be up to 3rd order. Every surface created by those tools produces Exact trim curves. In addition to that, each curve has a PWL (piecewise linear) representation. The PWL is refined until it falls within the chord tolerance setting - the straight line segment doesn't deviate from the actual curved surface by more than the chord tolerance (CT). When arbitrary surfaces intersect, the curve along the intersection can be of much higher order than 3 and exact curves are often not possible so only the PWL representation is used in those cases.

Every curve is SolveSpace joins 2 surfaces. This is very important.

There is a whole bunch of code that I haven't studied fully to deal with coincident surfaces. Say you extrude something and then something else with one end co-planar with the first. In some cases those surfaces will be merged into one and the trim curves will be handled (reassigned?) somehow.

I suspect when a surface is coincident with the seams of a Lahte or similar shape, there is simply a failure to handle that case. You have 2 surfaces joined by a curve, with that curve lying in the plane of a surface from the cutting extrusion. If you move the intersection plane a tiny bit a new intersection curve is created where there was nothing before and everything works out OK. I'm not sure what to do when the seam lies on the intersecting plane. The trim curve on the seam wants to be reconnected to the flat surface cutting the seam, but that's not right either because it's possible that only a part of that curve needs to be reassigned to the cutting surface. Imagine a box intersecting a donut along the seams, but part of a seam is inside and part outside the box. This is a case that I'm almost certain was never handled in the code and I think it's what is happening in this issue as well as another one. I think we might need to make a new copy of the exact curve.

Having said all that, I did look at the surface-surface intersection code quite a bit to make sure we can run it in parallel. I recall wondering if it was actually capable of handling the case you describe where no trim curves from either surface intersect the other surface. For me personally I consider that a "for later" thing to deal with, but you are more than welcome to dig in to whichever parts you like. We have a shortage of people who can do this AND have an interest in SolveSpace.

There are some other problems with coincident surfaces that are probably easier to figure out. If you make a helix and constrain the flat end against a flat surface (a box) it will tend to produce naked edges unless the axial displacement of the helix is constrained to zero (making it basically a revolve). It's strange because it should be the same as other coincident surfaces apart from the sides being helical which has nothing to do with the flat parts.

Anyway, that's my blurb about surfaces, seams, intersections and NURBS. I'm happy to answer any questions I can about this stuff. Was also thinking about writing a document about this for developer_docs so maybe this is starting material.

Thanks!

@phkahler
Copy link
Member

phkahler commented Sep 22, 2020

Oh, one more thing. When you Lathe around a sketch line - like in your example that won't find any intersection, the NURBS surfaces end up with a degenerate edge. The edge that would form a small arc around the axis becomes so short that both ends and the control point are coincident and lie on the axis. Like at the poles of planet where the lines of latitude converge and the longitude line at 90 degrees is just a point. This may have implications for NURBS intersections too, because the trim curves are all stored in 3D and part of the boolean process is to convert them to UV coordinates where they form a trim polygon in 2D U,V space. I'm not sure what happens in this case, how it's handled, or what bugs may lurk there.

@Christoph-D
Copy link
Contributor

Christoph-D commented Sep 22, 2020

This code

// This is a line on the axis of revolution; it does
// not contribute a surface.
revs[j].v = 0;
seems to handle this case by not creating degenerated surfaces that lie on the axis of revolution. Or is this something else?

@phkahler
Copy link
Member

phkahler commented Sep 22, 2020

@Christoph-D Oh that's another thing. When you revolve around a sketch line... If the axis is away from a line perpendicular to it, that line will sweep out a cylinder. If the radius is reduced to zero as when you lathe on a sketch line, the surface is not created at all. that's the code fragment you've found. The top and bottom surfaces don't need to share a trim curve with that missing surface for the same reason - that trim curve would have length zero. There are no trim curves generated by that line either (the one on the rotation axis).

For Revolve, the surface is also not created but the trim curve is, and it has to be shared by both end faces. For a helix, if you revolve it around a sketch line you will almost certainly get nake edges because the connectivity between surfaces is completely dependent on all sorts of things - the surfaces are correct but the trim curves are not handled correctly and would need to be broken into pieces to do so. I thought about writing an algorithm to fix those trims, but a better and more general solution would also handle issue #171.

@phkahler
Copy link
Member

phkahler commented Sep 22, 2020

Oh another odd detail I forgot. For a PWL curve that has no "exact" polynomial representation, the curve is actually defined precisely but not conveniently. It is defined as the intersection of the 2 surfaces the PWL curve trims. For that reason, the PWL points do not need to be super accurate, although we do compute them to lie on both surfaces. But again, the curve is well defined between consecutive points - it is the surface-surface intersection.

@phkahler
Copy link
Member

phkahler commented Sep 22, 2020

Now that I think of it.... A curve weather it is exact or not has a series of points in the PWL. Some of those are flagged as a Vertex. Obviously the start and end, but also if an edge gets a section taken out of it by a boolean operation, two new verticies may be added at the start and end of the region cut by surfaces in the other shell. Not that this does not change the connectivity - both remaining segments of the curve still trim the same two surfaces, as does the mid section that is discarded. You can see some of that in SCurve::MakeCopySplitAgainst().

I'm still haven't completely digested the terminology, but in addition to PWL "edges" there is something else (also called edges?) that is sections of PWL edges that go from one "choosing point" to another. They are called choosing points in the code, but I suspect they are almost always the same as a vertex.

I have been considering writing code to make a list of all verticies in a shell and then making sure every vertex is present in every curve that it coincides with. I suspect this is not happening and is causing some of the NURBS issues, but we can't really know until its tried. This should be easy at least for exact curves because we already have a function SBezier::ClosestPointTo() if the closest point coincides with a vertex then we should make sure it's in the PWL representation as a Vertex, regardless of where it came from I think.

@phkahler
Copy link
Member

phkahler commented Oct 11, 2020

With recent changes to SovleSpace the original problem reported here works intermittently if you unconstrain the diameter of the circle and drag it (while viewing the last group). One issue has been fixed, or at least worked around, but there is another problem where one segment of the circle goes missing and it fails sometimes.

@phkahler phkahler linked a pull request Oct 12, 2020 that will close this issue
@ruevs
Copy link
Member

ruevs commented Oct 12, 2020

PrismConeNURBSNormalsTangents.zip
Attached is a simplified version of triangle.slvs above that still fails on master - just start dragging the cone.
Approaches that could fix it are discussed in #734 . This ugly hack in particular "fixes" it.

@phkahler
Copy link
Member

phkahler commented Oct 12, 2020

@ruevs, The cone currently fixed if the lathe axis is away from the edge of the triangle. I'll check out your fix. By changing the tangents you're affecting other parts of the code that use them directly and not just the normal. Maybe that's what's needed for a better fix.

@ruevs
Copy link
Member

ruevs commented Oct 12, 2020

Mine was just a quick and dirty hack to check if the theory was correct, not intended as a proper fix.

I think we should shift u or v inwards only when they are on a degenerate/pinched point on the surface. I could not figure of how to check it, I was trying something with trim[x].start and end but did not have time to dig into it enough...

ruevs added a commit to ruevs/solvespace that referenced this issue Oct 13, 2020
ruevs added a commit to ruevs/solvespace that referenced this issue Oct 13, 2020
This avoids zero length normals.

Sometimes NURBS patches have a "degenerate" (zero length/to a point)
edge/side. In this case the tangent(s) on points "along" that "edge"
become zero length.

A normal `n` at a point (u.v) on a NURBS surface is calculated by calculating
the tangents `tu` and `tv` at that point and taking the cross product.
However when an edge is "degenerate" (for example a cone created by lathing
a triangle) then `tv` (and possibly `tu`) becomes zero and `n` becomes zero.
This causes a problems with NURBS booleans.

To solve this problem the tangent calculation is changed to shift `u` or `v` inwards
if they are on a degenerate/pinched point on the surface.

Fixes: solvespace#652
Alternative to: solvespace#734
ruevs added a commit to ruevs/solvespace that referenced this issue Oct 14, 2020
This avoids zero length normals.

Sometimes NURBS patches have a "degenerate" (zero length/to a point)
edge/side. For example lathed surfaces with a point on the lathe axis.
In this case the tangent(s) on points "along" that "edge" become zero
length.

A normal `n` at a point (u.v) on a NURBS surface is calculated by calculating
the tangents `tu` and `tv` at that point and taking the cross product.
However when an edge is "degenerate" then `tv` (or possibly `tu`) becomes
zero and `n` becomes zero.
This causes a problems with NURBS booleans when the seams are in-plane with
another surface.

To solve this problem the tangent calculation is changed to shift `u` or `v`
inwards if they are on a degenerate/pinched point on the surface.

Fixes: solvespace#652
Alternative to: solvespace#734
ruevs added a commit to ruevs/solvespace that referenced this issue Oct 16, 2020
This avoids zero length normals.

Sometimes NURBS patches have a "degenerate" (zero length/to a point)
edge/side. For example lathed surfaces with a point on the lathe axis.
In this case the tangent(s) on points "along" that "edge" become zero
length.

A normal `n` at a point (u.v) on a NURBS surface is calculated by calculating
the tangents `tu` and `tv` at that point and taking the cross product.
However when an edge is "degenerate" then `tv` (or possibly `tu`) becomes
zero and `n` becomes zero.
This causes a problems with NURBS booleans when the seams are in-plane with
another surface.

To solve this problem the tangent calculation is changed to shift `u` or `v`
inwards if `tu` or `tv` is shorter than a threshold value.

Fixes: solvespace#652
Alternative to: solvespace#736 solvespace#734
@phkahler phkahler added this to the 3.0 milestone Oct 16, 2020
phkahler added a commit to phkahler/solvespace that referenced this issue Oct 17, 2020
phkahler added a commit to phkahler/solvespace that referenced this issue Oct 17, 2020
phkahler added a commit to phkahler/solvespace that referenced this issue Oct 18, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants