Convex Hull in three dimensions: an incremental algorithm
hook up to the horizon and the hull expands
This incremental algorithm begins with the convex hull of four nonplanar points: a tetrahedron. Each successive point is tested to see if the new point lies within the previous hull. If it does, nothing more need be done. If it does not, then the new point must become a vertex of the new hull. From the point of view of the new point, determine which facets of the old hull are visible. The edges of visible facets shared by an invisible facet comprise the "horizon" as seen from the new point. The visible facets must be removed, and new facets constructed. The new facets include an edge of the horizon and the new point.
Virtual Reality Movies
To improve understanding of algorithms in three-dimensional computational geometry, virtual reality (VR) "object movies" of some scenes within the algorithm have been constructed. The user may manipulate these VR movies as if he were handling a real object and turning it in his hands. After the viewer has "handled" the scene, he may continue to play the time-line movie to complete the algorithm.
Movies which include both timeline and VR portions cannot be viewed easily with the usual QuickTime player. A unique player is constructed which allows the user to move from timeline to VR seamlessly. This idea is presented here as an experiment. Please write for further information.
Movies showing the computation of the convex hull in three dimensions are available for seven, ten, twenty, fifty and one hundred points. VR movies are available for seven and twenty points. The seven-point VR movie pauses after the first horizon has been drawn so that the viewer may manipulate the scene in a VR movie; the 20-point VR movie pauses once to show the faces visible to the target point, and once to show the horizon. The composite movies, combining both two or more conventional time movie and one or more VR movies, are available only as "stuffed" archives, which you should unstuff with StuffIt. The result will be a parent movie and a folder, containing the children. The parent movie and the folder must be kept together, or the parent will not be able to find the children!
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Download and unzip: three timeline movies above and two VR movies below, 25.9 Mb
|
|
|
|
|
|
