[World] Slicier and Dicier

Daniel Phillips phillips at phunq.net
Fri Jun 15 22:44:03 PDT 2012


Progress marches onward at a stately pace. Here is not the sexiest of screen 
shots, but an important one, as boundary edges of open meshes start to be 
integrated into the mix. The tetrahedron is cut by a flat surface of three 
triangles. The cut starts at a boundary edge and ends on the same boundary 
edge on a different plane. Somehow, the arc tracing algorithm is able to find 
its way through the forest of edges and planes from. It seems a little magical 
that it can do this reliably given the number of opportunities for wrong 
turns. I am sure that not all the details are correct yet, but it is getting 
there.

This is not a boolean solid operation because one of the objects is clearly 
not solid. It is something else, that may or may not be useful in modeling, 
but is definitely a case that needs to be handled. For one thing, the plan for 
handling coplanar faces depends on being able to intersect arbitrary open 
meshes.

Speaking of coplanar faces, that problem is starting to crack. I struggled for 
a while with the concept of finding coplanar domains by searching outward to 
neighbours of coplanar faces, or parts of them, and that approach was just 
getting very messy and hard to understand. Then it occurred to me that I 
shouldn't be trying to join up groups of faces, instead I should just be 
searching for boundaries of those domains. Such boundaries form open and 
closed arcs just like the intersections of non-coplanar faces we are already 
seeing. In fact, those arcs can be traced out by a method that is remarkably 
similar to finding arcs of intersection. The main thing that changes is, 
instead of finding edge/face intersections we are must look for the endpoints 
of certain face/face intersections. I haven't gone into much more detail than 
that, but it seems like a breakthrough. I am pretty sure now there is an 
elegant and general algorithm in there, as opposed to the messy hack that it 
easily could be.

I now have a rough idea of how complex the coplanar face extraction phase of 
the algorithm will be: roughly as complex as the other five steps put together. 
In other words, totally nontrivial. But well worth doing because it will 
complete this work. It now looks like the full, usable boolean combination 
algorithm will come in at not much more than a thousand lines, making it an 
order of magnitude smaller than libcarve, which is in turn much tighter than 
something like CGAL. I shudder to think what kind of code base 3D Max must 
have for this.

So where this is going in the near future is... hopefully we are going to pop 
the stack and get back to some higher level modeling. I can actually see 
modeling up the much anticipated (by me) catapult, complete with its beams, 
axle holes and other mechanical structure, as a demonstration.

Actually, I could have done that long ago just using ring modeling, but that 
would require a bit too much cleverness for my taste. Ring modeling has a lot 
of promise for scripting up modeling algorithms, but as a way to work 
interactively, it could get boring. Fast. Better than shooting individual 
triangles, but not much.

Boolean combination eliminates the requirement for cleverness. We just say: 
here is a horizontal beam and a couple of vertical ones, you figure out where 
they intersect, and please cut them up appropriately then glue them together 
and don't bug me about it. If we want a diagonal cross brace, we just provide 
a beam object of approximately the right length and let the boolean 
combination algorithms figure out how to cut it up to fit exactly with the other 
beams. Making a perfectly clean axle hole in a wheel is a matter of 
subtracting a cylinder from it, and hole in the superstructure for the 
throwing arm pivot is done in exactly the same way. So boolean combination is 
a way to let the designer be lazy and not think hard. Which is why I am 
putting so much effort into it, so somebody else can be lazy. It always seems 
to be that way with computers.

Regards,

Daniel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://phunq.net/pipermail/world/attachments/20120615/b01943f3/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solid12.png
Type: image/png
Size: 140039 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120615/b01943f3/attachment-0001.png>


More information about the World mailing list