Generation of constrained voronoi grid in a plane

Details Generation of constrained voronoi grid in a plane Generation of constrained voronoi grid in a plane

2011-04-26

2011-04-26

Repko, Jason M (Department: 2628)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C703S010000

Reexamination Certificate

active

07932904

ABSTRACT:
A method for generating constrained Voronoi grids in a plane with internal features and boundaries is disclosed. The disclosed method generally includes approximation of internal features and boundaries with polylines based on plane geometry. Protected polygons or points are generated around the polylines, and Delaunay triangulation of protected points or protected polygon vertices is constructed. Delaunay triangulation that honors protected polygons or points is generated in the rest of the gridding domain. The constrained Voronoi grid is then generated from the Delaunay triangulation, which resolves all of the approximated features and boundaries with the edges of Voronoi cells. Constrained Voronoi grids may be generated with adaptive cell sizes based on specified density criterion.

REFERENCES:
patent: 5740342 (1998-04-01), Kocberber
patent: 6018497 (2000-01-01), Gunasekera
patent: 6078869 (2000-06-01), Gunasekera
patent: 6106561 (2000-08-01), Farmer
patent: 6173075 (2001-01-01), Collins
patent: 6373489 (2002-04-01), Lu et al.
patent: 6393159 (2002-05-01), Prasad et al.
patent: 6421052 (2002-07-01), McGuire
patent: 6810370 (2004-10-01), Watts, III
patent: 6826520 (2004-11-01), Khan et al.
patent: 6907392 (2005-06-01), Bennis et al.
patent: 6928399 (2005-08-01), Watts, III et al.
patent: 7006959 (2006-02-01), Huh et al.
patent: 7047165 (2006-05-01), Balaven et al.
patent: 7096122 (2006-08-01), Han
patent: 7307629 (2007-12-01), Srivastava et al.
patent: 7382685 (2008-06-01), Ferber et al.
patent: 7428514 (2008-09-01), Jin et al.
patent: 2005/0093862 (2005-05-01), Boier-Martin et al.
patent: 2005/0140670 (2005-06-01), Wu et al.
patent: 2005/0273303 (2005-12-01), Flandrin et al.
patent: 2006/0235667 (2006-10-01), Fung et al.
patent: 2006/0277011 (2006-12-01), Tardy et al.
patent: 2007/0058865 (2007-03-01), Li et al.
patent: WO2005/121840 (2005-12-01), None
patent: WO2008/150325 (2008-12-01), None
Bern et al. Quadrilateral Meshing by Circle Packing. Aug. 2000, International Journal of Computational Geometry & Applications vol. 10, No. 4, pp. 347-360.
Du et al. Anisotropic Centroidal Voronoi Tessellations and their Applications. 2005, SIAM Journal of Scientific Computing, vol. 26, Issue 3, pp. 737-761.
Fang et al. Algorithm for Constrained Delaunay Triangulation. May 1994, the Visual Computer, vol. 10, No. 5, pp. 255-265.
G.J. Filatovs. Delaunay-Subgraph Statistics of Disc Packings. Jan. 1998, Materials Characterization, vol. 40, No. 1, pp. 27-35.
Joe et al. Duality of constrained Voronoi diagrams and Delaunay triangulations. Feb., 1993, Algorithmica, vol. 9, No. 2, pp. 142-155.
Beckner, B.L. et al (2001) “EMpower: New Reservoir Simulation System”, SPE Middle East Oil Show held in Bahrain. Mar. 17-20, 2001 SPE 68116, Society of Petroleum Engineers, Inc.
Boehm, G et al. (1995) “Getting rid of the grid”,65TH Annu. SEG INT. MTG.(Houston, Oct. 8-13, 1995)Expanded Tech. Program ABSTR. BIOGR. pp. 655-658, 1995. (ISSN 1052-3812; Pap. No. PP4.15; 3 refs).
Bohm, G et al. (2000) “3D adaptive tomography using Delaunay triangles and Voronoi polygons”, 58thEAGE Conference—Geophysical Division, Amsterdam, The Netherlands Jun. 1996, Received Jun. 1999, revision accepted Jan. 2000.
Bowyer, A. (1981) “Computing Dirichlet tessellations”,The Computer Journal, vol. 24, No. 2, pp. 162-166, 1981.
Branets, L.V. et al (2008) “Challenges and Technologies in Reservoir Modeling”,Commun. Comput. Phys., 6 (2009), pp. 1-23.
Chew, L.P., “Constrained Delaunay triangulation”, Algorithmica, vol. 4, pp. 97-108, 1989.
Cunha, A, et al. (1997) “Automatic boundary sizing for 2D and 3D meshes”, AMD-vol. 220 Trends in Unstructured Mesh Generation, ASME, pp. 65-72, 1997.
Du, Q et al (2002)Grid generation and optimization based on centroidal Voronoi tessellations, Appl. Math. Comput., v. 133, pp. 591-607, 2002.
Guzman, H. F . et al. (2001) “Automatic unstructured mesh generation around two-dimensional domains described by B-spline curves”,Proceedings of Detc. Asme. Design Engineering Technical Conferences and Computers and Information in Engineering Conference, vol. 1, Sep. 12, 2001 pp. 395-400 XP008085522.
Hale, D. (2002) “Atomic Meshes—From Seismic Imaging to Reservoir Simulation”, 8thEuropean Conference on the Mathematics of Oil Recovery—Freiberg, Germany, Sep. 3-6, 2002.
Hu, C. (2006) “Voronoi Cell Based Staggered Grid SH Wave Numerical Simulation”, 76thAnnual SEG International Meeting (New Orleans, LA, Oct. 1-6, 2006) Technical Program pap. No. SM P1-6, 2006.
Kalbacher, et al (2005) “Development and application of a CAD interface for fractured rock”Environmental Geology; International Journal of Geosciences, Springer-Verlag vol. 47, No. 7 May 1, 2005 XP019332265.
Lawson, C.L., (1977) “Software for C1 surface interpolation”, Mathematical Software III, 1977, pp. 161-194.
Lohner, R., et al (2000) “Generation of non-isotropic unstructured grids via directional enrichment”,International Journal for Numerical Methods in Engineering, vol. 49, pp. 219-232, 2000.
Miller, G.L., et al (2003) “When and why Ruppert's algorithm works”,Proceedings of the 12thInternational Meshing Roundtable, pp. 91-102, 2003.

Affiliated with

Also associated with

Rating

Generation of constrained voronoi grid in a plane does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Generation of constrained voronoi grid in a plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generation of constrained voronoi grid in a plane will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2655768