[Bf-committers] New Booleans & Smooth Meshes (maybe I need math help, maybe a shading glitch)

[Ted Schundler]

I've been working on improved booleans for Blender. There were some
short comings in my initial approach, so it's still in its python
script testing phase. (Anyone interested in testing it out can check
out the thread on Elysiun)

One problem that I had with the current booleans is with performing
operations on smooth objects. It tends to have not very smooth shading
of the subdivided faces.

I initially thought this was due to the way it adds random extra
verticies and edges of adjacent faces end up not actually being
completely shared. So, bad interpolation for smooth faces makes sense.
My boolean operations don't do that, but they still have problems with
smooth objects. Here's an example (left image):
http://astro.scu.edu/~ted/oss/blender/boolean/smoothboolproblem.jpg

And for futher experiments, I built this test case:
http://astro.scu.edu/~ted/oss/blender/boolean/sb_nh.jpg
If you look at towards the middle bottom you can see the shading is
not smooth along of the edges.

So, my best guess is that somehow normals aren't getting computed
correctly. I suspected this is because the new verticies are based on
intersecting flat faces. So, I decided to calculate intersections
based in implied smooth geometry, (more on this described below) and
it made things worse:
http://astro.scu.edu/~ted/oss/blender/boolean/sb_sh.jpg

And now I don't really know what to do. Personally getting this to
yield good results with smooth objects is important. Using the
relatively new "Rotate Edge" function (useful little function,
thanks), sometimes the effect can be improved, but not always.
However, thinking about it more, the problem doesn't really make
sense. Smooth shading is accomplished by interpolating vertex normals,
right? So, shouldn't it be impossible to have discontinuity in shading
along an edge? The vertex normals should be the same for both faces
since it is smooth, so the only effect would be somewhat awkward
shading, not the sharp contrast along edges in the images.

So, I'm wondering if this is a bug in Blender's shading, or if anyone
has other ideas for addressing this issue.



----------------------------------------------
Notes:
For the flat mesh boolean operations, the intersection points are
calculated by testing intersections between edges and faces and a
ray->plane intersection. There are also special tests for intersecting
edges as it because necessary to deal with some special cases.

For the smooth intersections, the same idea was used - intersecting
edges with faces. However the edges are bezier curves, and the face is
still a plane. In the test, a sphere is cut by a plane, so all the
intersection points are along the sphere's edges and lie in the face
of that one plane. There is no need (for this test) to actually
calculate the smooth faces, just edges.
The curves for the edges are cubic bezier curves. The length of the
tangents is 1/3 the length of the edge (that values seemed to produce
nice results). The direction of the tangents are determined by
crossproducts with the vertex normal and direction of the edge to
produce a vector in the right direction along the edge that is also
perpendicular to the vertex normal. To test this, I had it generate a
new mesh of only edges representing the smooth edges:
http://astro.scu.edu/~ted/oss/blender/boolean/sb_wire_top_l.png

The blue circle is a circle of radius 1 made of 98 verticies. The
orange is a low resolution (7x7) UV sphere. Having an odd number of
rings, there is no middle ring (so it doesn't touch the blue circle).
And the pink is the new interpolated version. As you can see, is comes
quite close to what the actual geometry should be. (thanks to luke for
colored meshes)

For finding the intersection, here's how the math works:
There are three cubic equations genetated Fx(u),Fy(u),Fz(u).
The plane can be defined as Ax+By+Cz+D=0. 
So the intersection is A*Fx(u)+B*Fy(u)+C*Fz(u)+D=0.
The resulting cubic equation in terms of u is solved. The first
rational solution found is used. For these tests the other 2 solutions
don't matter.




Ted