GPU-Accelerated Delaunay Refinement: Efficient Triangulation Algorithm

Computing Delaunay Refinement
Computing Delaunay Refinement
Using the GPU
Using the GPU
 
Feb. 26, 2017
Zhenghai CHEN, Meng QI and Tiow-Seng TAN
1
Outline
Introduction
Literature Review
Our Algorithm: gQM
Proof of Termination
Experiment Results
2
Introduction
 
Delaunay refinement problem:
    Input: 
a planar straight line graph (PSLG) and an angle 𝛳
    Output:
 a constrained Delaunay triangulation (CDT) with
                 no angles smaller than 𝛳
                  
(by adding Steiner vertices where needed)
3
 
Two Issues
Process has to terminate
Manage number of Steiner points
Introduction - 
contributions
 
The first
 GPU Delaunay refinement algorithm with PSLG
as input.
 
A few times to an order of magnitude faster
 than the best
CPU implementation, 
Triangle 
[Shewchuk 96]
.
 
Output by our algorithm is of 
a similar size
 to that by
Triangle
.
4
Literature Review
Two famous sequential algorithms
Ruppert’s (1995)
Chew’s     (1993)
Two software
Triangle (CPU, by Shewchuk, 1996)
Galois    (GPU, by Nasre, 2013)
Current work extends on our previous ones:
gDel2D      I3D 2012
Flipflop      I3D 2013
5
Literature Review
 
6
 
Ruppert’s algorithm (1995) : two main steps
1.
Split 
encroached
 (input) segments.
 
 
 
 
 
2.
Split 
bad triangles
. Insert and 
reject
 points.
Literature Review
 
Chew’s algorithm (1993) : two main steps
1.
Split bad triangles. Insert and 
reject
 points.
2.
Split 
segments
 and remove 
redundant
 points.
c
 is circumcenter 
of bad triangle  
t
redundant points
indicated as hollow
a
b
a
b
Literature Review
 
8
Triangle (CPU, by Shewchuk, 1996)
1.
The fastest CPU Delaunay mesh generator.
2.
Unify Ruppert’s and Chew’s to a certain extent.
Galois (GPU, by Nasre, 2013)
Handle point set as input
Diametral len for
Chew’s mode
Diametral disk for
Ruppert’s mode
a
b
Our Algorithm: gQM
gQM (GPU) and Triangle (CPU) differ in three aspects
besides parallel vs sequential:
Unify Ruppert's and Chew's fully
Adapt neatly 
FlipFlop
 algorithm 
[I3D 2013]
 to discover  encroachment
and to remove redundant Steiner points
Before insertion, selective in 
inserting
 
Steiner
 
points
 to avoid roll back
9
Our Algorithm: gQM
10
gQM  (GPU)
1.
Split encroached segments and
remove redundant points
2.
Split bad triangles with
“independent” points
Triangle  (CPU)
1.
Split encroached segments.
Under Chew's mode
, remove
redundant points
2.
Split bad triangles. Insert
circumcenters and 
reject
encroaching points
The only difference of two modes:
Ruppert’s:  Diametral disk
Chew’s:  Diametral len
Our Algorithm: gQM
11
gQM
1.
Split encroached segments and
remove redundant points
Triangle
1.
Split encroached segments.
Under Chew's mode
, remove
redundant points
b
 
a
Our Algorithm: gQM
12
gQM
1.
Split encroached segments and
remove redundant points
Triangle
1.
Split encroached segments.
Under Chew's mode
, remove
redundant points
b
a
Our Algorithm: gQM
13
gQM
1.
Split encroached segments and
remove redundant points
Triangle
1.
Split encroached segments.
Under Chew's mode
, remove
redundant points
b
a
Our Algorithm: gQM
14
gQM
2.
Split bad triangles with
“independent” points
Filter points:
Point location
Compute Delaunay “independent”
points
Triangle
2.
Split bad triangles. Insert
circumcenters and 
reject
encroaching points
Ruppert’s
Chew’s
a
b
a
b
Our Algorithm: gQM
15
gQM
2.
Split bad triangles with
“independent” points
Always insert these points
regardless whether encroaching or not
Triangle
2.
Split bad triangles. Insert
circumcenters and 
reject
encroaching points
 
F
l
i
p
F
l
o
p
:
to maintain CDT
and mark
encroached segments
Our Algorithm: gQM
16
Flipflop 
[Gao: I3D2013]
Flip to Delaunay; flop to remove point
Maintain CDT, remove redundant points and update encroachment
situation using 
parallel flipping
Proof of Termination
17
Never introduce an edge shorter than some constant (feature size)
Every iteration inserts at least one point
Finite underlying space
of the triangulation
Terminate
No more bad triangles
Experiment Results
Intel i7-6700 3.4GHz CPU and  GTX980 Ti graphics card
Generate random PSLGs on the uniform, Gaussian, disk and circle
distributions
The number of points ranges from 50,000 to 100,000
Number of segments ranges from 10 to 50% of number of points
Minimum allowable angle  
𝜃
 
= 15
°
, 20
°
, 25
°
18
Experiment Results
19
Output samples of synthetic data
all points lie
inside a disk
points lie in the
ring formed by
two circles
Input segments in red
Steiner points in blue
Experiment Results
20
The 
speedup
 of gQM over Triangle for 100K input points
and 10K to 50K input segments
Ruppert’s
Chew’s
Experiment Results
21
The percentage of 
extra points 
in the output mesh of 
gQM compared to Triangle with 100K input points and 10K to 50K segments.
Ruppert’s
Chew’s
Experiment Results
22
non-synthetic data:
P
r
o
j
e
c
t
 
W
e
b
s
i
t
e
http://www.comp.nus.edu.sg/~tants/gqm.html
23
Q & A
Q & A
Slide Note
Embed
Share

This study presents a novel approach for computing Delaunay refinement using GPU acceleration. The algorithm aims to generate a constrained Delaunay triangulation from a planar straight line graph efficiently, with improvements in termination handling and Steiner point management. By leveraging GPU processing, the proposed method achieves significantly faster performance compared to traditional CPU implementations while maintaining similar output quality. The research builds upon existing sequential algorithms and extends GPU-based refinement techniques to enhance computational speed and accuracy.


Uploaded on Sep 08, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Computing Delaunay Refinement Using the GPU Zhenghai CHEN, Meng QI and Tiow-Seng TAN Feb. 26, 2017 1

  2. Outline Introduction Literature Review Our Algorithm: gQM Proof of Termination Experiment Results 2

  3. Introduction Delaunay refinement problem: Input: a planar straight line graph (PSLG) and an angle ? Output: a constrained Delaunay triangulation (CDT) with no angles smaller than ? (by adding Steiner vertices where needed) Two Issues Process has to terminate Manage number of Steiner points 3

  4. Introduction - contributions The first GPU Delaunay refinement algorithm with PSLG as input. A few times to an order of magnitude faster than the best CPU implementation, Triangle [Shewchuk 96]. Output by our algorithm is of a similar size to that by Triangle. 4

  5. Literature Review Two famous sequential algorithms Ruppert s (1995) Chew s (1993) Two software Triangle (CPU, by Shewchuk, 1996) Galois (GPU, by Nasre, 2013) Current work extends on our previous ones: gDel2D I3D 2012 Flipflop I3D 2013 5

  6. Literature Review Ruppert s algorithm (1995) : two main steps 1. Split encroached (input) segments. a p a p a p d c c b b b 2. Split bad triangles. Insert and reject points. b a a b 6 Reject encroaching point Split bad triangle t

  7. Literature Review Chew s algorithm (1993) : two main steps 1. Split bad triangles. Insert and reject points. 2. Split segments and remove redundant points. a a b b redundant points indicated as hollow c is circumcenter of bad triangle t

  8. Literature Review Triangle (CPU, by Shewchuk, 1996) 1. The fastest CPU Delaunay mesh generator. 2. Unify Ruppert sand Chew s to a certain extent. a b Diametral len for Chew s mode Diametral disk for Ruppert s mode Galois (GPU, by Nasre, 2013) Handle point set as input 8

  9. Our Algorithm: gQM gQM (GPU) and Triangle (CPU) differ in three aspects besides parallel vs sequential: Unify Ruppert's and Chew's fully Adapt neatly FlipFlop algorithm [I3D 2013] to discover encroachment and to remove redundant Steiner points Before insertion, selective in inserting Steiner points to avoid roll back 9

  10. Our Algorithm: gQM gQM (GPU) Triangle (CPU) 1. Split encroached segments and remove redundant points 1. Split encroached segments. Under Chew's mode, remove redundant points 2. Split bad triangles with independent points 2. Split bad triangles. Insert circumcenters and reject encroaching points The only difference of two modes: Ruppert s: Diametral disk Chew s: Diametral len 10

  11. Our Algorithm: gQM gQM Triangle 1. Split encroached segments and remove redundant points 1. Split encroached segments. Under Chew's mode, remove redundant points a a a b b b 11

  12. Our Algorithm: gQM gQM Triangle 1. Split encroached segments and remove redundant points 1. Split encroached segments. Under Chew's mode, remove redundant points a b 12

  13. Our Algorithm: gQM gQM Triangle 1. Split encroached segments and remove redundant points 1. Split encroached segments. Under Chew's mode, remove redundant points a b 13

  14. Our Algorithm: gQM gQM Triangle 2. Split bad triangles with independent points 2. Split bad triangles. Insert circumcenters and reject encroaching points b a Filter points: a Point location Compute Delaunay independent points b Ruppert s Chew s 14

  15. Our Algorithm: gQM gQM Triangle 2. Split bad triangles with independent points 2. Split bad triangles. Insert circumcenters and reject encroaching points Always insert these points regardless whether encroaching or not FlipFlop: to maintain CDT and mark encroached segments a a b b 15

  16. Our Algorithm: gQM Flipflop [Gao: I3D2013] Flip to Delaunay; flop to remove point Maintain CDT, remove redundant points and update encroachment situation using parallel flipping 16

  17. Proof of Termination Never introduce an edge shorter than some constant (feature size) Every iteration inserts at least one point Finite underlying space of the triangulation Terminate No more bad triangles 17

  18. Experiment Results Intel i7-6700 3.4GHz CPU and GTX980 Ti graphics card Generate random PSLGs on the uniform, Gaussian, disk and circle distributions The number of points ranges from 50,000 to 100,000 Number of segments ranges from 10 to 50% of number of points Minimum allowable angle ? = 15 , 20 , 25 18

  19. Experiment Results Output samples of synthetic data Input segments in red Steiner points in blue points lie in the ring formed by two circles all points lie inside a disk 19

  20. Experiment Results The speedup of gQM over Triangle for 100K input points and 10K to 50K input segments Ruppert s Chew s 20

  21. Experiment Results The percentage of extra points in the output mesh of gQM compared to Triangle with 100K input points and 10K to 50K segments. Ruppert s Chew s 21

  22. Experiment Results non-synthetic data: 22

  23. Project Website http://www.comp.nus.edu.sg/~tants/gqm.html Q & A 23

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#