Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Patent
1996-12-26
1999-11-02
Jankus, Almis R.
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
G06T 1100
Patent
active
059779888
ABSTRACT:
The present invention provides a technique for mapping the intersections of line segments to machine representable points in a tiled plane. The technique provides for two mapping rules with respect to intersections that result in dividing an original line segment into a number of line segment fragments, each of which is an output machine representable line segment. The mapping rules are designed to minimize the fragmentation of an output set of machine representable line segments while still maintaining their topological consistency and geometric accuracy (i.e., closeness) with respect to the corresponding set of original input line segments. The technique provides a way for operations that manipulate line segments to be implemented in a simple manner assuming a finite precision model of computer arithmetic. Such techniques have numerous applications in the field of computer graphics including, but not limited to, hidden surface elimination, set operations on polygons, and the decomposition of complex polygons into simpler components, such as triangles, trapezoids, or monotone regions.
REFERENCES:
patent: 5506948 (1996-04-01), Onitake et al.
patent: 5793377 (1998-08-01), Moore
Daniel H. Greene and Frances F. Yao, "Finite-Resolution Computational Geometry", Proc. 27th Ann. Symp. on Foundations of Computer Science, 1986, pp. 143-152.
M. Gangnet, J-C Herve, T. Pudet and J-M Van Thong, "Incremental Computation of Planar Maps", Computer Graphics (SIGGRAPH 1989), vol. 23, No. 3, 1989, pp. 345-354.
L. Guibas and D. Marimont, "Rounding Arrangements Dynamically", Proceedings of the 11th ACM Symposium on Computational Geometry (SCG 1995), Vancouver, B. C., Jun. 1995.
Jon L. Bentley and T. A. Ottman, "Algorithms for Reporting and Counting Geometric Intersections", IEEE Transactions on Computers, vol. C-28, No. 9, Sep. 1979, pp. 643-647.
K. L. Clarkson and P. W. Shor, "Applications of Random Sampling in Computational Geometry, II", Discrete and Computational Geometry, vol. 4, 1989, pp. 387-421.
B. Chazelle and H. Edelsbrunner, "An Optimal Algorithm for Intersecting Line Segments in the Plane", Journal of the Association for Computing Machinery, vol. 39, No. 1, Jan. 1992, pp. 1-54.
Jankus Almis R.
Xerox Corporation
LandOfFree
Method for mapping line segment intersections to machine represe does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for mapping line segment intersections to machine represe, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for mapping line segment intersections to machine represe will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2142206