Project 4: Booleans

CS7491, Spring 2008

This is a team project (2 people per team). Deliverables: Project wep age with running demo applet, link to source code, and a very short PDF report clearly explaining your solution to the various problems and arguing when they are correct. Your report should also include some review pf prior art, performance analysis, and suggestions for improvement. The proposed project is devised into 3 phases. Two alternatives are also offered.

PHASE 1 (slow and inaccurate):

Extend the 3D mesh viewer program so that it can load and visualize 2 meshes simultaneously.

Provide some simple GUI for changing the position, scale, and orientation of each meshes.

Implement a robust edge/triangle intersection procedure that detects whether they do intersect and if so, produce the parameter to the intersection. By robust, I mean that it should correctly compute the parity of the number of intersections of the edge E with two adjacent triangles when the E stabs their union close to their common edge.

Detect all hit triangles and all hit edges. With each hit edge (or with its two opposite corners) associate the parameter that defines the hit point (or -1 if no hit). If there are two hits for an edge, store each with one corner (assuming an orientation of the half-edge). For example, with corner c, you should store the parameter (between 0 and 1) to the first hit point when walking the edge from v(n(c)) to v(p(c)). We will not store more than 2 such hits per edge. Most edges have zero or one hit.

In each mesh, A, when the other one is called B, identify 5 different groups of triangles and display them with different colors :

Gin - Triangles of A that are in (the solid bounded by) B and are not stabbed and not bounded by a stabbing edge

Gout - Triangles of A that are outside of (the solid bounded by) B and are not stabbed and not bounded by a stabbing edge

Gstab - Trianngles of A that are stabbed but not bounded by a stabbing edge

Gbouded - Triangles of A that are not stabbed but are bounded by a stabbing edge

Gboth - Trianngles of A that are stabbed and also bounded by a stabbing edge

Show these colors for each mesh (showing the mesh alone) and also showing the two meshes together.

Let the user select to render mesh A, mesh B, or both.

Let the user select Gin or Gout independently for mesh A and mesh B.

This selections corresponds to the Boolean operators A+B (union), AB (Intersection), A-B (difference) and B-A.

For the rest of the explanation, we assume that the user has selected A+B.

Delete all the triangles that are not in Gout of both meshes and clean up the corner table to ensure that you know what are the border corners.

Compute the set C of chamfer triangles that each connect a border edges of one mesh to a vertex of the other, so that the union of C with Gout of A and with Gout of B forms a manifold mesh without boundary and that the chamfer tirangles are small (using a greedy algorithm). A demo version (not debugged) of the code for computing these chamfer triangles (when there is only one mesh with two border loops) is posted on Dril Hole. You are welcome to use it as an inspiration but need to modify it so that it works for two meshes and for multiple triangles. Ensure that the resulting mesh is manifold and correctly oriented.

In the report, explain how you robustly compute the edge/triangle intersection, how you select the Gin set, and how you compute the chamfer tirangles. Show images for various positions of the two meshes and various Booleans (A-B, B-A, AB, A+B).

PHASE 2 (slow but more accurate):

Before computing the chamfer triangles C, split the Gbounded triangles using the intersection point parameters stored with their corners and with the opposite corners. Keep the correct triangles (depending on the Boolean operation and the classification of the vertices of the triangle or the orientations of the triangles stabbed by these edges. Use examples of a mesh with few large triangles to show that this works well. In your report, explain how you compute the refined triangles and how you decide which ones to keep. Discuss (on paper) why this approach is not exact and outline what one would need to do to make it exact.

PHASE 3 (faster):

Discuss the performance of your algorithm (assymptotic complexity, accuracy, topological limitations). Propose (at a high level in the report) several ideas for improving the accuracy and the performance of this algorithm. Use references to published articles on the subject and for each idea clearly state how it impacts accuracy and performance. Implement at least one simple acceleration technique which on average will speed up your algorithm. Report performance improvements.

ALTERNATIVE 1 (CREATIVE SOLUTION TO THE BOOLEAN):

ALTERNATIVE 2 (FULL SKIP&PRAY COMPRESSION):

Improve Skip&Pray by not sending a skip symbol for gates whose neighbors (along the border loop) have not changed.

Improve the encoding of the information needed for meshes with higher genus.

Combine Skip&Pray with the Delphi predictor for geometry and connectivity.

Report frequencies of all symbols (as a ratio of their occurences over the number of triangles).

Use entropy encoding of the symbols and report the resulting number of bits per tirangle for several meshes.

Incorporate the above with vertex normalization, quantization, coding, and decoding.

Describe the file format and use binary encoding/decoding for the files.

Provide a compress and decompress command.

Report file sizes and vertex counts.