טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentKatz Sagi
SubjectOn the Visibility of Point Sets
DepartmentDepartment of Electrical Engineering
Supervisor Professor Ayellet Tal
Full Thesis textFull thesis text - English Version


Abstract

In the last decade, an alternative to meshes, in the form of a point-based representation (a point cloud), has gained increasing popularity. Point clouds are 3D positions, which can be considered a sampling of a continuous surface. This representation is extremely simple and flexible. Moreover, it offers the additional advantage of avoiding connectivity information and topological consistency.


This work investigates visibility of point clouds. One way to compute visibility of a point cloud is to reconstruct the surface and determine visibility based on the reconstructed triangular mesh. Reconstruction, however, is a difficult problem, both theoretically and practically, which often requires additional information, such as normals and sufficiently dense input.


The key question that this work attempts to answer is how the visibility information can be directly extracted from a point cloud. Evidently, points cannot occlude one another (unless they accidentally fall along the same ray from the viewpoint), and therefore no point is actually hidden. We investigate a new operator, the Hidden Point Removal (HPR), and its generalization. The operator is simple, fast, and can be easily implemented. Moreover, it can calculate visibility for dense as well as sparse point clouds. In addition, the correctness of the operator is proved in the limit and theoretical guarantees are provided for finite sampling. Finally, a key result of this work is the proved link between the convex hull operator and visibility. It also shows a relation to the class of empty-region graphs.


Our operator is shown to be powerful in a variety of applications, including mesh segmentation, visualization, shadow casting, as well as view-dependent reconstruction and stippling-style drawings of point sets.