Shadow Implementation Outline

1. Input objects converted to shells.
   • All surfaces (including those in shells) converted to open surfaces.
   • Surface boundaries introduced as unshared edges of shell.
   • All shared and unshared edges converted to piecewise linear form.
2. Contour extraction.
   • Includes surface, discontinuity, and shared edge contours.
   • Unshared boundary contours extracted in step 4.
   • Extracted contours trimmed against existing trim loops.
   • Contours oriented with occlussion to the right as seen in image space projection.
3. Extracted contours inserted as trim edges.
   • Contours linked to form segments spanning entire shell or closed loops.
   • Neighboring endpoints corrected in a variety of ways during linking.
   • New edges form new loops, or split or merge existing loops.
   • Resulting connected regions assigned back/frontfacing tag based on normal.
   • *Connected regions not seperated into distinct shells yet. See * below.
4. Unshared boundary contour extraction.
   • Extraction here avoids need to split boundary contours for correct orientation.
5. Planar projection of contours for given viewpoint.
   • Center of interest set at midpoint of bounding box enclosing extracted contours.
   • Viewpoint must be outside the bounding box to avoid projections to infinity.
   • Contours mapped to XY image plane based on viewpoint and coi.
6. Contour segmentation.
   • Contours split by angle for cusp detection and to avoid self-intersection.
   • Pairwise intersection of contours to detect T-junctures.
   • Information on juncture types and adjacencies maintained.
7. Contour classification.
   • Single raycast from viewpoint to each contour segment.
   • *Avoids costly intersections between ray and identical untrimmed shell surfaces.
   • Classes assigned based on cardinality of intersection sets along the ray.
   • Occluded region assigned to each contour based on first intersection after contour.
   • Filtering of intersection points due to instability of ray-contour intersections.
   • Correction of contour class and juncture type based on contour topology constraints.
8. Face partitioning.
   • Finishes step 3, yielding a seperate shell for each connected region.
9. Cincture formation.
   • Cinctures offer improved robustness and efficiency (See references.).
   • Constructed through consideration of contour image space topology.
10. Casting of shadow cinctures.
    • Cinctures cast as ruled surfaces for given viewpoint.
11. Shadow cinture intersection/Contour projection.
    • Projections extracted as shadow cincture-occluded region intersections.
    • Intersections linked into single segments spanning shadow cinctures.
    • Ending juncture types used to increase robustness.
12. Contour projections inserted as trim edges.
    • Follows step 3 without back/frontface tagging.
13. Region partitioning.
    • Identical to step 8.
14. Partitioned region classifications.
    • Tag regions as to whether analysis query is satisfied or not.
    • Region classification based on classification of defining (bounding) contours.
    • No additional raycasts needed for region classification.
15. Desired regions written to stdout.
    • Regions chosen based on keep option and region classification.

Further details available in:

Robust Hidden Region Partitioning of Complex Freeform Models with Shadow Cinctures , Greg Heflin and Elaine Cohen, submitted for publication.

and

Discrete and Multview Accessibility Analysis of Complex Models , Greg Heflin, Ph.D. Thesis, CS Department, University of Utah, work in progress.

Alpha_1 Developer's Manual