Parallel window propagation on mesh surfaces
The task of calculating the shortest distance with minimal curvature between two points on a mesh surface is a well-known problem in computational geometry. This paper aims to develop a effective algorithm for computing geodesics on large, complex models with fast processing times to facilitate inte...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
The University of Danang
2023-12-01
|
| Series: | Tạp chí Khoa học và Công nghệ |
| Subjects: | |
| Online Access: | https://jst-ud.vn/jst-ud/article/view/7853 |
| _version_ | 1797205705170616320 |
|---|---|
| author | Le Tien Hung Do Quoc Trinh Nguyen Huu Tho |
| author_facet | Le Tien Hung Do Quoc Trinh Nguyen Huu Tho |
| author_sort | Le Tien Hung |
| collection | DOAJ |
| description | The task of calculating the shortest distance with minimal curvature between two points on a mesh surface is a well-known problem in computational geometry. This paper aims to develop a effective algorithm for computing geodesics on large, complex models with fast processing times to facilitate interactive applications. Our contribution is developing of the parallel window propagation (PWP) algorithm, which divides the sequential MMP algorithm into four phases: front node selection, window list propagation, window list merging, and vertex update. We use two separate buffers for incoming windows on each edge to avoid data dependency and conflicts in each phase, allowing for parallel processing on a CPU. As a result, our PWP algorithm can propagate a large number of windows simultaneously and independently, leading to significant improvements in performance for real-world models. |
| first_indexed | 2024-04-24T08:55:22Z |
| format | Article |
| id | doaj.art-66212aa7888d45fab83595f4094b72a9 |
| institution | Directory Open Access Journal |
| issn | 1859-1531 |
| language | English |
| last_indexed | 2024-04-24T08:55:22Z |
| publishDate | 2023-12-01 |
| publisher | The University of Danang |
| record_format | Article |
| series | Tạp chí Khoa học và Công nghệ |
| spelling | doaj.art-66212aa7888d45fab83595f4094b72a92024-04-16T08:12:24ZengThe University of DanangTạp chí Khoa học và Công nghệ1859-15312023-12-0110110610.31130/ud-jst.2023.208ICT7847Parallel window propagation on mesh surfacesLe Tien Hung0Do Quoc Trinh1Nguyen Huu Tho2Military Technical Academy, Hanoi, VietnamMilitary Technical Academy, Hanoi, VietnamMilitary Technical Academy, Hanoi, VietnamThe task of calculating the shortest distance with minimal curvature between two points on a mesh surface is a well-known problem in computational geometry. This paper aims to develop a effective algorithm for computing geodesics on large, complex models with fast processing times to facilitate interactive applications. Our contribution is developing of the parallel window propagation (PWP) algorithm, which divides the sequential MMP algorithm into four phases: front node selection, window list propagation, window list merging, and vertex update. We use two separate buffers for incoming windows on each edge to avoid data dependency and conflicts in each phase, allowing for parallel processing on a CPU. As a result, our PWP algorithm can propagate a large number of windows simultaneously and independently, leading to significant improvements in performance for real-world models.https://jst-ud.vn/jst-ud/article/view/7853geodesics;mmp algorithmwindows propogationparallel computing |
| spellingShingle | Le Tien Hung Do Quoc Trinh Nguyen Huu Tho Parallel window propagation on mesh surfaces Tạp chí Khoa học và Công nghệ geodesics; mmp algorithm windows propogation parallel computing |
| title | Parallel window propagation on mesh surfaces |
| title_full | Parallel window propagation on mesh surfaces |
| title_fullStr | Parallel window propagation on mesh surfaces |
| title_full_unstemmed | Parallel window propagation on mesh surfaces |
| title_short | Parallel window propagation on mesh surfaces |
| title_sort | parallel window propagation on mesh surfaces |
| topic | geodesics; mmp algorithm windows propogation parallel computing |
| url | https://jst-ud.vn/jst-ud/article/view/7853 |
| work_keys_str_mv | AT letienhung parallelwindowpropagationonmeshsurfaces AT doquoctrinh parallelwindowpropagationonmeshsurfaces AT nguyenhuutho parallelwindowpropagationonmeshsurfaces |