Ray shooting, depth orders and hidden surface removal (Q1309673)

The book is about effective solutions to three problems that arise in computer graphics when one wants to display the view of a three- dimensional scene on a screen, that is preprocess a set of polyhedra in such a way as to be able to quickly determine the first polyhedron that is hit by a query ray -- ray shooting sort a set of polyhedra according to their distance to a given view point -- depth orders for a given view point compute which parts of the polyhedron from a given set of polyhedra are visible -- hidden surface removal. The book is divided into four parts. The first one -- part A -- is devoted to the introduction, terminology, definitions and basic tools used later in the book. Part B deals with the ray shooting problem. It begins with the description of a general strategy to answer ray shooting queries, and then continues with sections on ray shooting from a fixed point, ray shooting into a fixed direction, and ray shooting with arbitrary rays. Part C is devoted to the problem of computing depth orders, and contains sections on depth orders in the plane, and on depth orders in three dimensions. Part D deals with the problem of hidden surface removal through computing of visibility maps. Here in separate sections instances of non-intersecting polyhedra, intersecting polyhedra, and dynamization of the problem are discussed and solved. Each problem is thoroughly studied and efficient data structures and algorithms to solve it are described and analyzed. At the end of each part of the book a summary of its result is presented and open problems and ideas for future research are outlined. Due to the well-written introductory part the book is appropriate and interesting reading also for those who do not consider themselves specialists in computational geometry.