The Experts below are selected from a list of 5367 Experts worldwide ranked by ideXlab platform
Stefan Langerman - One of the best experts on this subject based on the ideXlab platform.
-
The Clique Problem in Ray Intersection Graphs
Discrete & Computational Geometry, 2013Co-Authors: Sergio Cabello, Jean Cardinal, Stefan LangermanAbstract:Ray Intersection graphs are Intersection graphs of Rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a Ray Intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment Intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochvil and Nesetřil (Comment Math Univ Carolinae 31(1):85---93, 1990).
-
The Clique Problem in Ray Intersection Graphs
arXiv: Computational Geometry, 2011Co-Authors: Sergio Cabello, Jean Cardinal, Stefan LangermanAbstract:Ray Intersection graphs are Intersection graphs of Rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a Ray Intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment Intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochv\'il and Ne\v{s}et\v{r}il.
Sergio Cabello - One of the best experts on this subject based on the ideXlab platform.
-
The Clique Problem in Ray Intersection Graphs
Discrete & Computational Geometry, 2013Co-Authors: Sergio Cabello, Jean Cardinal, Stefan LangermanAbstract:Ray Intersection graphs are Intersection graphs of Rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a Ray Intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment Intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochvil and Nesetřil (Comment Math Univ Carolinae 31(1):85---93, 1990).
-
The Clique Problem in Ray Intersection Graphs
arXiv: Computational Geometry, 2011Co-Authors: Sergio Cabello, Jean Cardinal, Stefan LangermanAbstract:Ray Intersection graphs are Intersection graphs of Rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a Ray Intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment Intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochv\'il and Ne\v{s}et\v{r}il.
Tor M Aamodt - One of the best experts on this subject based on the ideXlab platform.
-
Intersection prediction for accelerated gpu Ray tracing
International Symposium on Microarchitecture, 2021Co-Authors: Lufei Liu, Wesley Chang, Francois Demoullin, Yuan Hsi Chou, Mohammadreza Saed, David Pankratz, Tyler Nowicki, Tor M AamodtAbstract:Ray tracing has been used for years in motion picture to generate photorealistic images while faster raster-based shading techniques have been preferred for video games to meet real-time requirements. However, recent Graphics Processing Units (GPUs) incorporate hardware accelerator units designed for Ray tracing. These accelerator units target the process of traversing hierarchical tree data structures used to test for Ray-object Intersections. Distinct Rays following similar paths through these structures execute many redundant Ray-box Intersection tests. We propose a Ray Intersection predictor that speculatively elides redundant operations during this process and proceeds directly to test primitives that the Ray is likely to intersect. A key aspect of our predictor strategy involves identifying hash functions that preserve enough spatial information to identify redundant traversals. We explore how to integrate our Ray prediction strategy into existing GPU pipelines along with improving the predictor effectiveness by predicting nodes higher in the tree as well as regrouping and scheduling traversal operations in a low cost, judicious manner. On a mobile class GPU with a Ray tracing accelerator unit, we find the addition of a 5.5KB predictor per streaming multiprocessor improves performance for ambient occlusion workloads by a geometric mean of 26%.
I. Garcia - One of the best experts on this subject based on the ideXlab platform.
-
Reliable algorithms for Ray Intersection in computer graphics based on interval arithmetic
16th Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2003), 2003Co-Authors: J.f. Sanjuan-estrada, L.g. Casado, I. GarciaAbstract:We study the reliability and performance of interval arithmetic for Ray tracing implicit surfaces. We analyze when and how to use interval arithmetic as an alternative to the methods used in POV-Ray for Ray Intersection. Interval methods are applied as robust approaches for solving the Ray-surface Intersection problem; i.e. to find the minimal root in a set of analytic functions. POV-Ray is able to solve this problem efficiently for relatively simple objects (objects that can be bounded in a box). Interval based algorithms can speed up the rendering process for scenes with some infinite implicit surfaces, including nondifferentiable ones, where the automatic bounding box cannot be applied. Interval methods have the advantage of not needing to provide the interval guess of the maximum gradient, as recursive subdivision equipotential methods (used by POV-Ray) does. Experimental results were obtained from the evaluation of our interval algorithms and the methods used in POV-Ray in scenes with single objects and in complex scenes with several objects.
Zhenzhou Wang - One of the best experts on this subject based on the ideXlab platform.
-
active stereo vision three dimensional reconstruction by rgb dot pattern projection and Ray Intersection
Measurement, 2021Co-Authors: Yongcan Shuang, Zhenzhou WangAbstract:Abstract Active stereo vision is important in reconstructing objects without obvious textures. However, it is still very challenging to extract and match the projected patterns from two camera views automatically and robustly. In this paper, we propose a new pattern extraction method and a new stereo vision matching method based on our novel structured light pattern. Instead of using the widely used 2D disparity to calculate the depths of the objects, we use the Ray Intersection to compute the 3D shapes directly. Experimental results showed that the proposed approach could reconstruct the 3D shape of the object significantly more robustly than state of the art methods that include the widely used disparity based active stereo vision method, the time of flight method and the structured light method. In addition, experimental results also showed that the proposed approach could reconstruct the 3D motions of the dynamic shapes robustly.
-
rgb line pattern based stereo vision matching for single shot 3 d measurement
IEEE Transactions on Instrumentation and Measurement, 2021Co-Authors: Zhenzhou WangAbstract:Active stereo vision has been used for real-time measurement in both academic and industrial fields. Currently, it is still very challenging for active stereo vision to achieve the continuous and robust measurement of a dynamic object due to the lack of a robust pattern extraction and matching method. In this article, we introduce a novel red green blue (RGB) line pattern with coarse-to-fine features in which the intervals between the adjacent green lines are largest and the intervals between the adjacent red lines are smallest. The large interval represents the coarse feature of the pattern and the small interval represents the fine feature of the pattern. Accordingly, we propose a matched pixel difference modeling (MPDM) method to model the matching relationship between two camera views based on the designed pattern. The line pattern is extracted in the hue saturation value (HSV) color space by slope difference distribution (SDD)-based threshold selection. The coarse green lines in two camera views are matched according to the minimum distance principle after the centroid-based alignment. The matching relationship is then modeled based on the matched green lines by least squares (LS) method. With the matching model, the fine blue lines and the fine red lines are matched successively. After stereo matching, the 3-D point on the measured object is computed by the Ray Intersection method. Experimental results showed that the proposed method is robust in measuring the dynamic objects by single-shot.
