Page 22 - 中国仿真学会通讯2020第1期

Ｃ ＝ （ｐｘ ＋ ａ） （ ｐｚ４ － ｐｚ１ ） ＋ ｐｘ（ ｐｚ２ － ｐｚ３ ） ，
ａ２

Ｄ ＝ ｐｘ ｐｙ（ ｐｚ３ － ｐｚ２ ＋ ｐｚ１ － ｐｚ４ ） ＋ ａ［ ｐｘ（ ｐｚ１ － ｐｚ２ ） ＋ ｐｙ（ ｐｚ３ － ｐｚ２ ） － ａｐｚ２ ］ ．
ａ２

Ｂａｓｅｄ ｏｎ ｔｈｅ ｅｑｕａｔｉｏｎｓ ｏｆ ｔｈｅ ＬｏＳ ｓｅｇｍｅｎｔ ｋｇｎ ３． Ａｌｇｏｒｉｔｈｍ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｎ ＧＰＵ
ａｎｄ ｔｅｒｒａｉｎ ｓｕｒｆａｃｅ， ｔｈｅ ｓｉｍｕｌｔａｎｅｏｕｓ ｅｑｕａｔｉｏｎ ｏｆ

ｉｎｔｅｒｓｅｃｔｉｏｎ ｐｏｉｎｔｓ ｃａｎ ｂｅ ｄｅｒｉｖｅｄ ａｓ Ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｐａｒａｌｌｅｌｉｓｍ ｏｆ ＧＰＵ ｔｈｒｅａｄｓ，

Ｍ（ ｋ ｎ ） ２ ＋ Ｎｋ ｎ ＋ Ｔ ＝ ０， ｔｈｅ ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ｃｏｍｐｕｔｉｎｇ ｉｎ ｅｖｅｒｙ ＲＳＧ ｃａｎ ｂｅ
ｇ ｇ ｅｘｅｃｕｔｅｄ ｃｏｎｃｕｒｒｅｎｔｌｙ ｉｎ ａ ｋｅｒｎｅｌ ｆｕｎｃｔｉｏｎ ｃａｌｌｅｄ

ｗｈｅｒｅ

Ｍ ＝ Ａ（ ｘ ｎ － ｘ１ｎ ） （ ｙ２ｎ － ｙ ｎ ） ， ｂｙ ａｌｌ ｔｈｒｅａｄｓ ａｆｔｅｒ ｃｏｍｐｕｔｉｎｇ ａｌｌ ｏｆ ｉｎｔｅｒｓｅｃｔｉｏｎ
２ １ ｐｏｉｎｔｓ ａｓ ｆｏｒｍａｌ ｐａｒａｍｅｔｅｒｓ ｏｆ ｔｈｅ ｋｅｒｎｅｌ ｆｕｎｃｔｉｏｎ．
Ｂｅｆｏｒｅ ｅｘｅｃｕｔｉｎｇ ｋｅｒｎｅｌ ｆｕｎｃｔｉｏｎ， ｔｈｅ ｍｅｍｏｒｉｅｓ ｏｆ
Ｎ ＝ Ａ［ （ ｘ２ｎ － ｘ１ｎ ） ｙ１ｎ ＋ （ ｙ２ｎ － ｙ１ｎ ） ｘ１ｎ ］ ｔｈｅｓｅ ｉｎｔｅｒｓｅｃｔｉｏｎ ｐｏｉｎｔｓ ｓｈｏｕｌｄ ｂｅ ａｌｌｏｃａｔｅｄ ｆｉｒｓｔｌｙ
ａｎｄ ｔｈｅｎ ｃｏｐｉｅｄ ｔｏ ＧＰＵ（ ｄｅｖｉｃｅ ｅｎｄ） ｆｒｏｍ ＣＰＵ
＋ Ｂ（ ｘ ｎ － ｘ１ｎ ） ＋ Ｃ（ ｙ ｎ － ｙ１ｎ ） － （ ｚ ｎ － ｚ１ｎ ） ， （ ｈｏｓｔ ｅｎｄ ） ｕｓｉｎｇ ｃｕｄａＭａｌｌｏｃ ｆｕｎｃｔｉｏｎ ａｎｄ
２ ２ ２ ｃｕｄａＭｅｍｃｐｙ ｆｕｎｃｔｉｏｎ ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｔｗｏ
ｐａｒａｍｅｔｅｒｓ ｄｅｓｃｒｉｂｅｄ ｂｙ ｔｈｅ ｓｙｍｂｏｌ ｏｆ “ ＜ ＜ ＜ ＞ ＞
Ｔ ＝ Ａｘ１ｎ ｙ１ｎ ＋ Ｂｘ１ｎ ＋ Ｃｙ ｎ ＋ Ｄ － ｚ１ｎ ． ＞” ｉｎｄｉｃａｔｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｂｌｏｃｋｓ ａｎｄ ｔｈｅ ｎｕｍｂｅｒ
１ ｏｆ ｔｈｒｅａｄｓ ｐｅｒ ｂｌｏｃｋ． Ｔｈｅ ｐｓｅｕｄｏ⁃ｃｏｄｅ ｏｆ ＣＵＤＡ
ｐａｒａｌｌｅｌ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ａｌｇｏｒｉｔｈｍ
Ｔｈｅ ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ｏｆ ｏｎｅ ＲＳＧ ｃａｎ ｂｅ ｇｏｔ ｂｙ ｉｓ ｓｈｏｗｎ ｉｎ Ｆｉｇｕｒｅ ２．

ｓｏｌｖｉｎｇ ｔｈｉｓ ｓｉｍｕｌｔａｎｅｏｕｓ ｅｑｕａｔｉｏｎ． Ｔｈｅ ｒｅｓｕｌｔ ｉｓ

ｎｏｔ ｉｎｔｅｒｖｉｓｉｂｌｅ ｗｈｅｎ ｋ ｎ ∈ （ ０，１ ） ａｎｄ Ｍ ＝ ０∨Ｎ２
ｇ

≥４ＭＴ ｗｈｉｌｅ ｉｓ ｉｎｔｅｒｖｉｓｉｂｌｅ ｉｎ ｏｔｈｅｒ ｃａｓｅｓ． Ｔｈｅ

ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ｏｆ ｏｎｅ ＧＣＳ ｔｉｌｅ ｃａｎ ｂｅ ａｃｑｕｉｒｅｄ ｂｙ

ｍｅｒｇｉｎｇ ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ＲＳＧｓ ｉｎ ｔｈｉｓ ＧＣＳ ｔｉｌｅ．

Ｓｉｍｉｌａｒｌｙ， ｔｈｅ ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ｏｆ ｔｈｅ ＬｏＳ ｃａｎ ｂｅ

ａｃｑｕｉｒｅｄ ｂｙ ｍｅｒｇｉｎｇ ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ＧＣＳ ｔｉｌｅｓ ｅｉｔｈｅｒ．

Ｆｉｇ．２． Ｔｈｅ ｐｓｅｕｄｏ⁃ｃｏｄｅ ｏｆ ＣＵＤＡ ｐａｒａｌｌｅｌ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｉｎｔｅｒｖｉｓｉｂｉｌｉｔｙ ａｌｇｏｒｉｔｈｍ．

１９