[World] Slicier and Dicier

Daniel Phillips phillips at phunq.net
Tue Jun 12 23:35:45 PDT 2012


Here is another slight adjustment of the test polyhedra that slightly 
increases the complexity of the intersection. No doubt there are a number of 
other fundamentally different ways two tetrahedra can intersect that I haven't 
tried yet. So far so good. Just one failure discovered so far... but it fails 
on the very first arc segment,  so this is no doubt a big fat duh.

The algorithm seems to be basically right. Here it is in less summary:

	0. Remove coplanar domains
	1. Intersect edges with faces
	2. Trace out open and closed intersection arcs
	3. Section mesh(es) along arcs
	4. Assemble sections according to desired boolean result
	5. Triangulate any new non-triangular faces

with "open arcs" and "coplanar domains" not done yet, and a new final 
triangulation step added. Also, the assembly stage is rudimentary, and as I 
mentioned there is one significant performance issue and a lot of inconsistency 
handling work to be done. Other than that, it is nearly finished ;)

I did notice one unanticipated detail: when an intersection arc lies entirely 
inside a single face then it makes a hole in that face, or a hole in a hole, 
nested arbitrarily deeply. It is necessary to detect and handle those nested 
holes, that is, for each original face, collect together all the closed loops 
lying entirely inside a given face and  triangulate the polygon consisting of 
all those loops. Not very hard given that we now have a pretty good 
triangulator, but without this a lot of constructions will break. Image 
solid2.png is a simple example.

I am looking forward to having usable boolean operations in the not enormously 
distant future.

Regards,

Daniel

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://phunq.net/pipermail/world/attachments/20120612/99745c1b/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solid11.png
Type: image/png
Size: 106501 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120612/99745c1b/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solid2.png
Type: image/png
Size: 125416 bytes
Desc: not available
URL: <http://phunq.net/pipermail/world/attachments/20120612/99745c1b/attachment-0003.png>


More information about the World mailing list