Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2006-04-18
2006-04-18
Nguyen, Kimbinh T. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000, C700S246000, C382S153000
Reexamination Certificate
active
07030875
ABSTRACT:
A method of representing spatial relations among objects in the environment uses a Delaunay triangulation as the data structure to store the spatial relations when the objects are represented in the form of simplified objects such as cuboids. The method receives image data corresponding to the environment and recognizes the objects in the image data, and updates the Delaunay triangulation so that the Delaunay triangulation is consistent with the recognized objects. Furthermore, a proximity query can be carried out using the Delaunay triangulation.
REFERENCES:
patent: 5036474 (1991-07-01), Bhanu et al.
patent: 5564004 (1996-10-01), Grossman et al.
patent: 6031540 (2000-02-01), Golin et al.
patent: 6097381 (2000-08-01), Scott et al.
patent: 6133921 (2000-10-01), Turkiyyah et al.
patent: 6304675 (2001-10-01), Osbourn et al.
patent: 6734849 (2004-05-01), Dimsdale et al.
patent: 07-085136 (1995-03-01), None
patent: 11-073526 (1999-03-01), None
Sheehy et al. “Computing the Medial Surface of a solid from a Domain Delaunay Triangulation”, ACM 1995, pp. 201-212.
Bras-Mehlman, E. Le et al., “How the Delaunay Triangulation Can Be Used for Representing Stereo Data,” IEEE International Conference on Computer Vision (2nd), 1988, pp. 54-63, ISBN 0-8186-0883-8.
Gao, Jie et al., “Efficient Proximity Search for 3-D Cuboids,” Lecture Notes in Computer Science, May 2003, vol. 2669, pp. 817-826.
Gross, Eric M., “Function Learning Enhancement with Delaunay Linear Interpolation and K-D Tree Nearest Neighbor Retrieval,” Proceedings of the American Control Conference, Jun. 1995, vol. 5, pp. 3791-3795.
Jones, Christopher B. et al., “Proximity Search with a Triangulated Spatial Model,” The Computer Journal, 1998, vol. 41, No. 2, pp. 71-83.
Zeta, Dan et al., “Data Input Model for Virtual Reality-Aided Facility Layout,” IIE Transactions, Jul. 1998, vol. 30, No. 7, pp. 597-620.
International Search Report dated Oct. 14, 2003, for International Application No. PCT/JP03/10943, filed on Aug. 28, 2003.
Agarwal, P.K., et al., “Box-trees and R-trees with Near-Optimal Query Time,” Proceedings of the 17thACM Symposium on Computational Geometry (SoCG 01') (Jun. 2001), pp. 124-133.
Agarwal, Pankaj K., et al., “Geometric Range Searching and Its Relatives,” Contemporary Mathematics (1999), vol. 23, pp. 1-56, American Mathematical Society Press, Providence, RI.
Attali, D., et al., “A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces,” submitted to ACM Solid Modeling (2002).
Aurenhammer, F., “Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys (Sep. 1991), vol. 23, No. 3, pp. 345-405.
Byers, John A., “Dirichlet Tessellation of Bark Beetle Spatial Attack Points,” Journal of Animal Ecology (1992), vol. 61, pp. 759-768.
Edwards, Geoffrey, et al., “Toward the Simulation of Spatial Mental Images Using the Voronoi Model,” Representation and Processing of Spatial Expressions (1997), pp. 163-184, edited by Patrick Olivier and Klaus-Peter Gapp.
Erickson, J., “Dense Point Sets Have Sparse Delaunay Triangulations,” 13thSIAM Conference Discrete Algorithms (2002), pp. 125-134.
Erickson, J., “Nice Point Sets Can Have Nasty Delaunay Triangulations,” 17thACM Symposium Computational Geometry (2001), pp. 96-105.
Fortune, Steven, “Voronoi Diagrams and Delaunay Triangulations,” Computing in Euclidean Geometry (1992), pp. 193-223, World Scientific Publ.
Gilbert, E.G., et al., “A Fast Procedure for Computing the Distance Between Complex Objects in Three-Dimensional Space,” IEEE Journal of Robotics and Automation (Apr. 1988), vol. 4, No. 2, pp. 193-203.
Howarth, Richard J., “On Seeing Spatial Expressions,” Representation and Processing of Spatial Expressions (1997), pp. 37-56, edited by Patrick Olivier and Klaus-Peter Gapp.
Lawrence, Craig, et al., “User's Guide for CFSQP Version 2.5: A C Code for Solving (Large Scale) Constrained Nonlinear (Minimax) Optimization Problems, Generating Iterates Satisfying All Inequality Constraints,” Institute for Systems Research TR-94-16R1, University of Maryland, College Park (Apr. 1997).
McAllister, Michael, et al., “A Compact Piecewise-Linear Voronoi Diagram For Convex Sites in the Plane,” IEEE Symposium on Foundations of Computer Science (1993), pp. 573-582.
Nayar, Shree K., et al., “Real-Time 100 Object Recognition System,” Proc. Of IEEE International Conference on Robotics and Automation (1996), pp. 2321-2325.
Nygards Mikael, et al., “Three-Dimensional Periodic Voronoi Grain Models and Micromechanical FE-Simulations of a Two-Phase Steel,” Computational Materials Science (2002), vol. 24, pp. 513-519.
Panier, Eliane R., et al., “On Combining Feasibility, Descent and Superlinear Convergence in Inequality Constrained Optimization,” Mathematical Programming (1993), vol. 59, pp. 261-276.
Samet, H., “Spatial Data Structures,” in Modern Database Systems, The Object Model, Interoperability and Beyond (1995) pp. 361-385, W. Kim, ed., ACM Press and Addison-Wesley.
Veltkamp, Remco C., et al., “State-of-the-Art in Shape Matching,” Technical Report UU-CS-1999-27 (1999), pp. 1-26, Utrecht University, The Netherlands.
“Feasible Sequential Quadratic Programming,” [online], Mar. 28, 1996 [retrieved on Jul. 24, 2002]. Retrieved from the Internet: <URL: http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/Continuous/constrained
onlin.
Gao Jie
Gupta Rakesh
Fenwick & West LLP
Honda Motor Company Ltd.
Nguyen Kimbinh T.
LandOfFree
Environmental reasoning using geometric data structure does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Environmental reasoning using geometric data structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Environmental reasoning using geometric data structure will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3618415