An approach for line clipping against a convex polyhedron
Line clipping operation is a bottleneck in most of computer graphics applications. There are situations when millions of line segments need to be clipped against convex polyhedrons with millions of facets. An algorithm to clip line segments against a convex polyhedron is proposed in this work. The s...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Ruhuna
2016-11-01
|
| Series: | Ruhuna Journal of Science |
| Subjects: | |
| Online Access: | https://rjs.sljol.info/articles/10.4038/rjs.v7i1.15/galley/20/download/ |
| _version_ | 1811194716500262912 |
|---|---|
| author | K. R. Wijeweera S. R. Kodituwakku |
| author_facet | K. R. Wijeweera S. R. Kodituwakku |
| author_sort | K. R. Wijeweera |
| collection | DOAJ |
| description | Line clipping operation is a bottleneck in most of computer graphics applications. There are situations when millions of line segments need to be clipped against convex polyhedrons with millions of facets. An algorithm to clip line segments against a convex polyhedron is proposed in this work. The salient feature of the proposed algorithm is that it minimizes the number of computations by ignoring unnecessary intersection calculations. The other advantage of the proposed algorithm is that it needs minimum details about the convex polyhedron; the equations of the facets and the centroid. Therefore, it improves the efficiency of the algorithm. The line segment may have zero length (a point) or positive length. When line segment is just a point which is outside with respect to at least one facet, it should be rejected as the line segment is outside the convex polyhedron. When the line segment is parallel to a facet and one of its end points is outside, that line segment is also completely outside and it should also be rejected. Unless the line segment belongs to none of the above two cases, it should be pruned against each facet in a certain order. In this case, the intersection points with only some of the facets need to be computed and some other intersection calculations can be ignored. If the line segment is completely outside then it becomes a single point. That means the two end points coincide. But due to the precision error they do not exactly coincide. Therefore, approximate equality should be tested. By using this property, completely outside line segments can be identified. Having two end points outside does not necessarily keep the line segment completely outside. The widely used Cyrus Beck algorithm computes all the intersection points with each facet of the polyhedron while the proposed algorithm successfully avoids some of the intersection point calculations. In the best case; it is capable of avoiding all the unnecessary intersection calculations. An experimental comparison between the Cyrus Beck algorithm and the proposed algorithm was carried out. Random polyhedrons were created with different number of facets. Random points were generated and they were considered as end points of line segments. For a given polyhedron, the number of clock cycles consumed to clip 108 number of line segments was computed using the Cyrus Beck algorithm and the proposed algorithm. For a polyhedron with four vertices, the proposed algorithm is 1.02 times faster than the Cyrus Beck algorithm. For a polyhedron with nine vertices, the proposed algorithm is 1.16 times faster than the Cyrus Beck algorithm. When the number of facets is large, then the performance of the proposed algorithm is significantly faster since more intersection calculations are avoided. The Skala algorithm is also an efficient algorithm which requires the order of facets also as the input to the algorithm. The proposed algorithm is faster than Skala algorithm when the number of facets of the polyhedron is less than 100 according to the experimental results. The proposed approach could be very useful for applications where large number of lines to be clipped. It can also be applied in linear programming as well since it can be extended to arbitrary dimensions. |
| first_indexed | 2024-04-12T00:31:22Z |
| format | Article |
| id | doaj.art-ccac2f1bf24e481286037aea2bcc8753 |
| institution | Directory Open Access Journal |
| issn | 1800-279X |
| language | English |
| last_indexed | 2024-04-12T00:31:22Z |
| publishDate | 2016-11-01 |
| publisher | University of Ruhuna |
| record_format | Article |
| series | Ruhuna Journal of Science |
| spelling | doaj.art-ccac2f1bf24e481286037aea2bcc87532022-12-22T03:55:20ZengUniversity of RuhunaRuhuna Journal of Science1800-279X2016-11-0171122010.4038/rjs.v7i1.15An approach for line clipping against a convex polyhedronK. R. Wijeweera0S. R. Kodituwakku1Department of Computer Science, Faculty of Science, University of Ruhuna; Postgraduate Institute of Science, University of PeradeniyaDepartment of Statistics and Computer Science, Faculty of Science, University of PeradeniyaLine clipping operation is a bottleneck in most of computer graphics applications. There are situations when millions of line segments need to be clipped against convex polyhedrons with millions of facets. An algorithm to clip line segments against a convex polyhedron is proposed in this work. The salient feature of the proposed algorithm is that it minimizes the number of computations by ignoring unnecessary intersection calculations. The other advantage of the proposed algorithm is that it needs minimum details about the convex polyhedron; the equations of the facets and the centroid. Therefore, it improves the efficiency of the algorithm. The line segment may have zero length (a point) or positive length. When line segment is just a point which is outside with respect to at least one facet, it should be rejected as the line segment is outside the convex polyhedron. When the line segment is parallel to a facet and one of its end points is outside, that line segment is also completely outside and it should also be rejected. Unless the line segment belongs to none of the above two cases, it should be pruned against each facet in a certain order. In this case, the intersection points with only some of the facets need to be computed and some other intersection calculations can be ignored. If the line segment is completely outside then it becomes a single point. That means the two end points coincide. But due to the precision error they do not exactly coincide. Therefore, approximate equality should be tested. By using this property, completely outside line segments can be identified. Having two end points outside does not necessarily keep the line segment completely outside. The widely used Cyrus Beck algorithm computes all the intersection points with each facet of the polyhedron while the proposed algorithm successfully avoids some of the intersection point calculations. In the best case; it is capable of avoiding all the unnecessary intersection calculations. An experimental comparison between the Cyrus Beck algorithm and the proposed algorithm was carried out. Random polyhedrons were created with different number of facets. Random points were generated and they were considered as end points of line segments. For a given polyhedron, the number of clock cycles consumed to clip 108 number of line segments was computed using the Cyrus Beck algorithm and the proposed algorithm. For a polyhedron with four vertices, the proposed algorithm is 1.02 times faster than the Cyrus Beck algorithm. For a polyhedron with nine vertices, the proposed algorithm is 1.16 times faster than the Cyrus Beck algorithm. When the number of facets is large, then the performance of the proposed algorithm is significantly faster since more intersection calculations are avoided. The Skala algorithm is also an efficient algorithm which requires the order of facets also as the input to the algorithm. The proposed algorithm is faster than Skala algorithm when the number of facets of the polyhedron is less than 100 according to the experimental results. The proposed approach could be very useful for applications where large number of lines to be clipped. It can also be applied in linear programming as well since it can be extended to arbitrary dimensions.https://rjs.sljol.info/articles/10.4038/rjs.v7i1.15/galley/20/download/Computational GeometryConvex AnalysisComputer Graphics ProgrammingCoordinate GeometryLinear Programming |
| spellingShingle | K. R. Wijeweera S. R. Kodituwakku An approach for line clipping against a convex polyhedron Ruhuna Journal of Science Computational Geometry Convex Analysis Computer Graphics Programming Coordinate Geometry Linear Programming |
| title | An approach for line clipping against a convex polyhedron |
| title_full | An approach for line clipping against a convex polyhedron |
| title_fullStr | An approach for line clipping against a convex polyhedron |
| title_full_unstemmed | An approach for line clipping against a convex polyhedron |
| title_short | An approach for line clipping against a convex polyhedron |
| title_sort | approach for line clipping against a convex polyhedron |
| topic | Computational Geometry Convex Analysis Computer Graphics Programming Coordinate Geometry Linear Programming |
| url | https://rjs.sljol.info/articles/10.4038/rjs.v7i1.15/galley/20/download/ |
| work_keys_str_mv | AT krwijeweera anapproachforlineclippingagainstaconvexpolyhedron AT srkodituwakku anapproachforlineclippingagainstaconvexpolyhedron AT krwijeweera approachforlineclippingagainstaconvexpolyhedron AT srkodituwakku approachforlineclippingagainstaconvexpolyhedron |