All-in-one VR headsets have limited rendering power which limits the complexity of the virtual environments (VEs) that can be used in VR applications. This paper describes a novel visibility algorithm for making complex VEs tractable on all-in-one VR headsets. Given a view segment, the algorithm finds the set of triangles visible as a camera translates on the view segment. When run on the perimeter of a user view region, the algorithm provides a quality approximation of the visible set from inside the view region. The visibility algorithm supports static and dynamic VEs, and it solves visibility with either triangle, particle, or object granularity. The visible sets yield output frames that are virtually indistinguishable from ground truth frames rendered from the original VEs.

This article presents two from-point visibility algorithms: one aggressive and one exact. The aggressive algorithm efficiently computes a nearly complete visible set, with the guarantee of finding all triangles of a front surface, no matter how small their image footprint. The exact algorithm starts from the aggressive visible set and finds the remaining visible triangles efficiently and robustly. The algorithms are based on the idea of generalizing the set of sampling locations defined by the pixels of an image. Starting from a conventional image with one sampling location at each pixel center, the aggressive algorithm adds sampling locations to make sure that a triangle is sampled at all the pixels it touches. Thereby, the aggressive algorithm finds all triangles that are completely visible at a pixel regardless of geometric level of detail, distance from viewpoint, or view direction. The exact algorithm builds an initial visibility subdivision from the aggressive visible set, which it then uses to find most of the hidden triangles. The triangles whose visibility status is yet to be determined are processed iteratively, with the help of additional sampling locations. Since the initial visible set is almost complete, and since each additional sampling location finds a new visible triangle, the algorithm converges in a few iterations.

The key to a robust and efficient implementation of a computational geometry algorithm is an efficient algorithm for detecting degenerate predicates. We study degeneracy detection in constructing the free space of a polyhedron that rotates around a fixed axis and translates freely relative to another polyhedron. The structure of the free space is determined by the signs of univariate polynomials, called angle polynomials, whose coefficients are polynomials in the coordinates of the vertices of the polyhedra. Every predicate is expressible as the sign of an angle polynomial $f$ evaluated at a zero $t$ of an angle polynomial $g$. A predicate is degenerate (the sign is zero) when $t$ is a zero of a common factor of $f$ and $g$. We present an efficient degeneracy detection algorithm based on a one-time factoring of every possible angle polynomial. Our algorithm is 3500 times faster than the standard algorithm based on greatest common divisor computation. It reduces the share of degeneracy detection in our free space computations from 90% to 0.5% of the running time.

We present a free space computation algorithm for two planar bodies bounded by line segments and circular arcs. The computational complexity is O(((mn)2+k)log(mn)) with m and n the number of boundary curves of the two bodies, and with k the number of configurations with three pairs of curves in contact. Although k is in O((mn)3), mild input restrictions reduce it to O(mn). We develop a robust implementation that is accurate, is fast, and handles degenerate input.

We present a new approach, called controlled linear perturbation (CLP), to the robustness problem in computational geometry and demonstrate it on Minkowski sums of polyhedra. The robustness problem is how to implement real RAM algorithms accurately and efficiently using computer arithmetic. Large errors can occur when predicates are assigned inconsistent truth values because the computation assigns incorrect signs to the associated polynomials. CLP enforces consistency by performing a small input perturbation, which it computes using differential calculus. CLP enables us to compute Minkowski sums via convex convolution, whereas prior work uses convex decomposition, which has far greater complexity. Our program is fast and accurate even on inputs with many degeneracies.

We present an arrangement algorithm for plane curves. The inputs are (1) continuous, compact, x-monotone curves and (2) a module that computes approximate crossing points of these curves. There are no general position requirements. We assume that the crossing module output is ε accurate, but allow it to be inconsistent, meaning that three curves are in cyclic y order over an x interval. The curves are swept with a vertical line using the crossing module to compute and process sweep events. When the sweep detects an inconsistency, the algorithm breaks the cycle to obtain a linear order. We prove correctness in a realistic computational model of the crossing module. The number of vertices in the output is V=2n+N+min(3kn,n2/2) and the running time is O(V log n) for n curves with N crossings and k inconsistencies. The output arrangement is realizable by curves that are O(ε+knε) close to the input curves, except in knε neighborhoods of the curve tails. The accuracy can be guaranteed everywhere by adding tiny horizontal extensions to the segment tails, but without the running time bound. An implementation is described for semi-algebraic curves based on a numerical equation solver. Experiments show that the extensions only slightly increase the running time and have little effect on the error. On challenging data sets, the number of inconsistencies is at most 3N, the output accuracy is close to ε, and the running time is close to that of the standard, non-robust floating point sweep.

We present a path planning algorithm for a polyhedral robot with six degrees of freedom (6DOF) and a static obstacle. The planner consists of a dual-tree RRT algorithm that uses a novel local planner. A local planner tests if two robot configurations can be connected by a simple path. Ours searches a 3DOF subspace of the robot/obstacle configuration space, whereas prior planners search the line segment that connects the two configurations. Empirical evidence suggests that the benefit of the 3DOF search outweighs the cost. Our planner outperforms prior planners on problems with narrow channels and performs comparably (shorter paths, similar running times) on other problems

Abstract We present a technique for rendering reflections on complex reflectors at interactive rates based on approximating the geometry of the reflected scene with impostors. The reflections correctly convey the distance to the reflector surface and provide motion parallax. Two types of impostors are adapted to the reflections framework: billboards and depth maps. Billboards remove most of the problems of environment mapped reflections at only a small additional cost. Second order reflections are supported by introducing reflective billboards. Higher quality reflections that provide motion parallax within a reflected object are obtained by approximating the reflective geometry with depth maps. The computation of the intersection between a reflected ray and a depth map is accelerated by leveraging epipolar constraints. Like environment mapping, our technique does not pose any restriction on the geometry of the reflector, supports dynamic scenes, and runs at interactive rates with the help of graphics hardware. Categories and Subject Descriptors (ACM CCS): I.3.3. [Computer Graphics]—Three‐Dimensional Graphics and Realism.

This paper presents sample-based cameras for rendering high quality reflections on convex reflectors at interactive rates. The method supports change of view, moving objects and reflectors, higher order reflections, view-dependent lighting of reflected objects, and reflector surface properties. In order to render reflections with the feed forward graphics pipeline, one has to project reflected vertices. A sample-based camera is a collection of BSP trees of pinhole cameras that jointly approximate the projection function. It is constructed from the reflected rays defined by the desired view and the scene reflectors. A scene point is projected by invoking only the cameras that contain it in their frustums. Reflections are rendered by projecting the scene geometry and then rasterizing in hardware.

We introduce the occlusion camera: a non-pinhole camera with 3D distorted rays. Some of the rays sample surfaces that are occluded in the reference view, while the rest sample visible surfaces. The extra samples alleviate disocclusion errors. The silhouette curves are pushed back, so nearly visible samples become visible. A single occlusion camera covers the entire silhouette of an object, whereas many depth images are required to achieve the same effect. Like regular depth images, occlusion-camera images have a single layer thus the number of samples they contain is bounded by the image resolution, and connectivity is defined implicitly. We construct and use occlusion-camera images in hardware. An occlusion-camera image does not guarantee that all disocclusion errors are avoided. Objects with complex geometry are rendered using the union of the samples stored by a planar pinhole camera and an occlusion camera depth image. Categories and Subject Descriptors (according to ACM CCS): I.3.3. [Computer Graphics]—Three-Dimensional Graphics and Realism.

We describe a method for interactive modeling and visualization of room-size indoor scenes that is fast, easy, and inexpensive. We have designed a novel data acquisition device, called a ModelCamera, that consists of a video camera with an attached laser system that generates a 7x7 pattern of depth samples. The operator pans and tilts the ModelCamera around the camera's center of projection and it acquires a sequence of color and depth frames. The frames are registered in world coordinates and are merged into an evolving scene model, called a depth enhanced panorama. The model is visualized continually; the immediate feedback allows the operator to monitor the model quality and to identify missing scene surfaces. Our approach extends color panoramas to support viewpoint translation, while retaining their speed, convenience, and low cost (Figure 1). It is a practical alternative to modeling systems that provide complete models at a high cost.

This paper presents a path-planning algorithm for an articulated planar robot with a static obstacle. The algorithm selects a robot part, finds a path to its goal configuration by systematic configuration space search, drags the entire robot along the path using compliant motion, and repeats the cycle until every robot part reaches its goal. The planner is tested on 11 000 random problems, which span dozens of robot/obstacle geometries with up to 43 moving parts and with narrow channels. It solves every problem in seconds, whereas randomized algorithms appear to fail on all of them.

This paper summarizes ongoing work with a mo- bile manipulator (Mobipulator ). We describe the sys- tem architecture of the latest version of the robot, a hierarchy of robot motion commands (the Mobipula- tion library) that can be snapped together to generate complicated paths easily, a configuration space plan- ner that plans wheel motions to manipulate paper, and a visual servoing system to monitor and correct errors in robot motion.

We describe a parametric synthesis algorithm for planar mechanical systems comprised of higher kinematic pairs in which each part translates along a fixed axis or rotates around a fixed point. Kinematic function is computed from the CAD models of the parts and is represented graphically as configuration spaces. The designer uses the mouse to request changes in the configuration spaces. The program computes parameter values that achieve the changes. The computation is iterative: the program repeatedly linearizes the mapping from design parameters to kinematics around the current values, pseudo-inverts the linear mapping, and performs a small parameter modification that moves the system toward the desired kinematics. At each iteration, the program matches the current kinematics against the initial kinematics. If it detects an unintended change, it backs up, adds kinematic constraints that prevent the change, and resumes iteration.

I present a deterministic path planning algorithm for an assembly of rigid planar parts connected by joints. The part boundaries are comprised of line segments and circular arcs. The algorithm is based on configuration space computation and search. It is complete for one moving part and is heuristic for multiple parts. It is the first complete algorithm that is practical for real-world applications. It is more reliable than randomized algorithms, which are inherently incomplete. It solves problems with many parts, crowded environments, tight part fits, and closed chains.

We present the first configuration space computation algorithm for pairs of rigid parts that move along fixed spatial axes. The motivation is contact analysis for mechanical design of spatial systems and of planar systems with axis misalignment. The part geometry is specified in a parametric boundary representation using planes, cylinders, and spheres. Our strategy is to exploit the specialized part geometry and the 2D structure of the configuration space to: 1) derive low-degree algebraic contact equations in the two part motion parameters, which can readily be solved to obtain contact curves, and 2) to use a practical planar configuration space construction algorithm. We demonstrate a preliminary implementation on three representative pairs, none of which is covered by other contact analysis algorithms. We show how the program is used in answering design questions.

We are studying difficult geometric problems in computer-aided mechanical design where visualization plays a key role. The research addresses the fundamental design task of contact analysis: deriving the part contacts and the ensuing motion constraints in a mechanical system. We have automated contact analysis of general planar systems via configuration space computation. Configuration space is a geometric representation of rigid-body interaction that encodes quantitative information, such as part motion paths, and qualitative information, such as system failure modes. The configuration space dimension equals the number of degrees of freedom in the system. Three-dimensional spaces are most important, but higher-dimensions are often useful. The qualitative aspects, which relate to the topology of the configuration space, are best understood by visualization. We explain what configuration space is, how it encodes contact information, and what research challenges it poses for visualization.

We present an algorithm for functional kinematic tolerance analysis of general planar mechanical systems with parametric tolerances. The algorithm performs worst-case analysis of systems of curved parts with contact changes, including open and closed kinematic chains. It computes quantitative variations and helps designers detect qualitative variations, such as blocking and under-cutting. The algorithm constructs a variation model for each interacting pair of parts: a mapping from the part tolerances and configurations to the kinematic variation of the pair. These models generalize the configuration space representation of nominal kinematics to toleranced parts. They are composed via sensitivity analysis and linear programming to derive the system variation at a given configuration. The variation relative to the nominal system function is computed by sampling the system variation. We demonstrate the algorithm on detailed parametric models of a movie camera film advance and of a micro-mechanical gear discriminator.

We present an algorithm for dynamical simulation of rigid-body mechanical systems with changing contact topologies based on configuration spaces. The algorithm advances the state of the art in contact analysis, which is the main bottleneck in dynamical simulation. The task is to identify the touching parts and to compute the ensuing contact forces. Our algorithm computes the configuration spaces of all pairs of parts and uses them as contact models. It overcomes the limitations of mechanical systems simulators, which require precomputed contact models, and of general-body simulators, which perform contact analysis on the part models at every time step. Neither approach is practical for mechanisms with multiple contacts and complex contact geometry, such as clock escapements, chain gears, and part feeders. We describe a configuration space simulator for assemblies of planar parts with one degree of freedom apiece and demonstrate it on two mechanisms with many complex contacts.

No abstract available.

We describe the HIPAIR configuration space computation program for higher pairs and show how it automates reasoning about shape and motion for mechanism design. We describe an interactive parametric design module that combines configuration space computation with differential constraint satisfaction. HIPAIR handles pairs of 2.5D parts with two degrees of freedom, including pairs with intermittent, simultaneous, and degenerate contacts. This class contains 90% of 2.5D pairs and 80% of all higher pairs according to our survey of 2500 mechanisms. We have tested HIPAIR on over 100 pairs, including gears, cams, ratchets, and escapements. It analyzes pairs with thousands of contacts in under ten seconds. The configuration spaces encode the relations among part shapes, part motions, and overall behavior in a concise, complete, and explicit format. They help designers analyze part interactions, implement functions, identify failure modes, and modify designs.>

We evaluate the success of the qualitative physics enterprise in automating expert reasoning about physical systems. The field has agreed, in essentials, upon a modeling language for dynamical systems, a representation for behavior, and an analysis method. The modeling language consists of generalized ordinary differential equations containing unspecified constants and monotonic functions; the behavioral representation decomposes the state space described by the equations into discrete cells; and the analysis method traces the transitory response using sign arithmetic and calculus. The field has developed several reasoners based on these choices over some 15 years. We demonstrate that these reasoners exhibit severe limitations in comparison with experts and can analyze only a handful of simple systems. We trace the limitations to inappropriate assumptions about expert needs and methods. Experts ordinarily seek to determine asymptotic behavior rather than transient response, and use extensive mathematical knowledge and numerical analysis to derive this information. Standard mathematics provides complete qualitative understanding of many systems, including those addressed so far in qualitative physics. Preliminary evidence suggests that expert knowledge and reasoning methods can be automated directly, without restriction to the accepted language, representation, and algorithm. We conclude that expert knowledge and methods provide the most promising basis for automating qualitative reasoning about physical systems.

Common sense sometimes predicts events to be likely or unlikely rather than merely possible. We extend methods of qualitative reasoning to predict the relative likelihoods of possible qualitative behaviors by viewing the dynamics of a system as a Markov chain over its transition graph. This involves adding qualitative or quantitative estimates of transition probabilities to each of the transitions and applying the standard theory of Markov chains to distinguish persistent states from transient states and to calculate recurrence times, settling times, and probabilities for ending up in each state. Much of the analysis depends solely on qualitative estimates of transition probabilities, which follow directly from theoretical considerations and which lead to qualitative predictions about entire classes of systems. Quantitative estimates for specific systems are derived empirically and lead to qualitative and quantitative conclusions, most of which are insensitive to small perturbations in the estimated transition probabilities. The algorithms are straightforward and efficient.