ThaiGameDevX - Thai Game Developers eXchange Forums
27 September 2017, 08:39:43 AM *
Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
News: หากมาครั้งแรก เชิญอ่าน ประกาศเจตนารมณ์ของ ThaiGameDevX และ กติกา ข้อตกลงในการใช้เว็บบอร์ด ครับ
 
   Home   Help Search Calendar Login Register  
Pages: [1]   Go Down
  Print  
Author Topic: FAQ: การตรวจจับการชนกันของ ตัวละคร วัตถุ และ ฉาก  (Read 17369 times)
0 Members and 1 Guest are viewing this topic.
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« on: 27 September 2005, 02:43:03 AM »

หลังจากล้างข้อมูลบอร์ดเก่าไปแล้ว เราลืมคุยเรื่องหัวข้อสำคัญไปได้ยังไงล่ะนี่� �;)
ขอวิธีการตรวจจับการชนกันของ ตัวละคร วัตถุ และ ฉาก หน่อยครับ ใครใช้วิธีไหนกันบ้างครับ� Grin

วิธีที่ 1 ตรวจการชนโดยใช้ระยะห่าง

ถ้าหาระยะห่างระหว่างของสองอันเช่น A,B ถ้าอยู่ใกล้กันเดินค่าๆ นึง ก็ถือว่าชนกันครับ

ใข้สูตร euclidean distance นะครับ (ref: http://mathworld.wolfram.com/Distance.html )

ระยะห่างระหว่างจุดสองจุด� d =� ( (x1-x2)2 + (y1-y2)2 + (z1-z2)2 )0.5

Code:
ให้ข้อมูล A เป็นตำแหน่งของตัวละครแรก ( A.x = xxx ; A.y = yyy ;� A.z = zzz )
ให้ข้อมูล B เป็นตำแหน่งของตัวละครอีกอันนึง ( B.x = xxx2 ; B.y = yyy2 ;� B.z = zzz2 )

d = sqrt ( sqr (A.x - B.x ) + sqr (A.y - B.y ) + sqr (A.z - B.z ) )

if (d<r)� �{
� �// ชน
} else {
� // ไม่ชน
}

ทีนี้ถ้าสมมติมีวัตถุ 100 ชิ้นล่ะ จะดูว่าชิ้นไหนชนกันมั่ง ก็ต้องวนรอบ (loop) เปรียบเทียบ
ชิ้น 1 กับ 2
ชิ้น 1 กับ 3
ชิ้น 1 กับ ..
ชิ้น 1 กับ 100

จากนั้น ก็
ชิ้น 2 กับ 3 (เพราะ 1 กับ 2 คำนวนไปแล้วในรอบที่แล้ว)
ชิ้น 2 กับ 4
ชิ้น 2 กับ 5
ชิ้น 2 กับ ..
ชิ้น 2 กับ 100

..

จากนั้น ก็ ..
ชิ้น 98 กับ 99 (เพราะ 98 กับ 97 คำนวนไปแล้วในรอบที่แล้ว)
ชิ้น 98 กับ 100

และสุดท้าย ..
ชิ้น 99 กับ 100

คิดว่าแปลงเป็นโค๊ดเองคงไม่ยากนะครับ Cheesy
Logged

..
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #1 on: 28 September 2005, 12:57:21 AM »

ดูภาพประกอบนะครับ
d>Ar+Br วัตถุทั้งสองไม่ชนกัน
d<Ar+Br วัตถุทั้งสองชนกัน
d=Ar+Br วัตถุทั้งสองแตะกันพอดี

* collision_sph.jpg (22.85 KB - downloaded 1060 times.)
Logged

..
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #2 on: 28 September 2005, 01:36:01 AM »

วิธีที่ 2 ตรวจการชนโดยใช้ระยะห่างแบบสี่เหลี่ยม

ให้ A:(x1,y1,z1) และ B:(x2,y2,z2) เป็นจุดกึ่งกลางของวัตถุสี่เหลี่ยมใดๆ ที่มีด้าน 3 ด้าน ตั้งฉากกับแนวแกน x,y,z
ให้ Aw, Ah, As เป็นความกว้างของวัตถุ A ในแนวแกน x,� ความสูงของวัตถุ A ในแนวแกน y,� ความลึกของวัตถุ A ในแนวแกน z,� ตามลำดับ
ให้ Bw, Bh, Bs เป็นความกว้างของวัตถุ B ในแนวแกน x,� ความสูงของวัตถุ B ในแนวแกน y,� ความลึกของวัตถุ B ในแนวแกน z,� ตามลำดับ

dw=|x2-x1|
rw=(Aw+Bw)/2

dh=|y2-y1|
rh=(Ah+Bh)/2

ds=|z2-z1|
rs=(As+Bs)/2

จากภาพแสดงว่า วัตถุสี่เหลี่ยม A,B จะไม่เกิดการชนกัน ถ้า (dw>rw) หรือ (dh>rh) หรือ (ds>rs)
และเกิดการชนกัน ก็ต่อเมื่อ (dw<rw) และ (dh<rh) และ (ds<rs)

*อ่านแล้วต้องกลับมาแก้ เพราะเขียนนิยามผิดไปนิดนึงครับ� Cheesy

* collision_rect.jpg (37.8 KB - downloaded 1001 times.)
« Last Edit: 28 September 2005, 05:42:35 PM by yod » Logged

..
นายตาหวาน (Mr.Tawan)
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +61/-36
Offline Offline

Gender: Male
Posts: 1,591


« Reply #3 on: 28 September 2005, 01:50:07 AM »

เห็นกันชัด ๆ เลยนะครับว่า แบบ Sphere นั้นใช้การคำนวนมากกว่า (เพราะว่าใช้ Squre Root เข้ามาคำนวนด้วย)
Logged

Are you feeling fine?
眠れない夜には君の幻が...
She said, "Loving you made me happy everyday"
kingkong
Approved Member
Full Member
*

จำนวน ชม/ไม่พอใจ: +6/-1
Offline Offline

Posts: 122


« Reply #4 on: 28 September 2005, 07:20:54 AM »

+1 อย่างไม่ต้องสงสัยครับ ^_^
Logged
mak
Approved Member
Full Member
*

จำนวน ชม/ไม่พอใจ: +10/-1
Offline Offline

Gender: Male
Posts: 113



« Reply #5 on: 28 September 2005, 10:20:49 AM »

+1  Grin

โอ้ มีภาพประกอบด้วย ทำให้เห็นภาพได้ง่ายดีครับ
Logged
Hoo
Administrator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +52/-0
Offline Offline

Posts: 597


« Reply #6 on: 28 September 2005, 11:10:36 AM »

น่าย้ายไปเป็นบทความนะเนี่ย
Smiley
Logged

You ask for Freedom of Speech
or
Freedom of Lies???
visualC++
Guest
« Reply #7 on: 18 October 2005, 08:20:55 PM »

ค่ะ หนูก็ว่าน่าจะย้ายกระทู้ดีๆ แบบนี้ไปไว้เป็นบทความเลยค่ะ เพราะว่า มีภาพชัดเจน แล้วก็ทำแบบว่า ใครมีข้อสงสัยเรื่องนี้ก็ถามได้ที่บอร์ดนั้นเลย ดีๆๆ ค่ะ พี่ yod กับพี่ตาหวาน นี่เก่ง จังเลยค่ะ อยากให้มีคนแบบพี่สองคนนี้เยอะ จัง

*** ถ้าใครอยากเป็นคนดีของสังคม ช่วยตอบกระทู้เยอะ แบบนี้หน่อยนะค่ะ
Logged
chanon
Administrator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +26/-1
Offline Offline

Posts: 738


« Reply #8 on: 04 November 2005, 11:12:42 AM »

ขอเสริม link บทความเจ๋งมากในเรื่องนี้ครับ:
http://www.harveycartel.org/metanet/tutorials/tutorialA.html
มีภาพ flash เป็น interactive ให้ดูด้วย เจ๋งมาก

ว่างๆ อยากเขียนบทความเรื่อง vector จัง แต่ไม่ว่าง เหอๆๆๆๆๆๆ
Logged
noky
Approved Member
Full Member
*

จำนวน ชม/ไม่พอใจ: +3/-0
Offline Offline

Gender: Male
Posts: 131



« Reply #9 on: 25 January 2006, 07:34:40 AM »

โอ้ว มีความรุ้มากๆเลยคับ +1 ขอบคุณคับพี่ งี้ถ้ามีวัตถุเพียบเลยใน ซีนหนึ่ง ในหนึ่งแฟรม มันจะไม่คำนวนมากมาย จนทำให้ เฟรมเรต ตกหร๋อคับ การเช็คแบบนี้มัน คือ n^2 เลยนะ ความเร็วขนาดนี้ยอมรับได้หร๋อ

ทุกครั้งที่มีการปรียบเทียบ 2 วัตถุ จะต้องคำนวนสมการนี้  d = sqrt ( sqr (A.x - B.x ) + sqr (A.y - B.y ) + sqr (A.z - B.z ) ) ซึ่งมันจะไม่ทำให้โค้ดช้าลงหร๋อคับ ยิ่งใช้คำสั่ง sqrt ด้วย มันทำงานช้ากว่า + มากอยู่

แค่การวาดเส้นตรง (วิชาคอมกราฟฟิก) อัลกอลิทึม การวาด เส้นตรงแบบง่ายๆ ที่ใช้สมการเส้นตรงคำนวนหา ตำแหน่ง x y ทุกครั้งที่มีการ pos จุด อาจารย์ยังไม่ค่อยอยากให้ใช้เลย ให้ไปใช้ อัลกอที่ ไม่คำนวนมาก เช็ค if 4 อันเอา โดยแรกเป็นกรณีๆ(integerDDA)
« Last Edit: 02 August 2012, 08:06:49 PM by noky » Logged
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #10 on: 25 January 2006, 09:13:02 AM »

ที่เขียนให้ดูนี่คือ math ล้วนๆ ครับ ส่วนนักเขียนโปรแกรมคอมพิวเตอร์ต้องเป็นคนเอามา"ประยุกต์ใช้"ให้เป็นครับ

"การเช็คแบบนี้มัน คือ n^2" ....
ถูกต้องครับ ในการแก้ไขถึงต้องมีวิชา data structure & algorithm ยังไงล่ะครับ เพื่อลดการคำนวนที่ไม่จำเป็น เช่นเก็บข้อมูลใน quad tree หรือ bsp เพื่อแบ่งข้อมูลเป็นกลุ่มย่อยๆ ก่อนจะเข้าไปเรียก function ทดสอบที่ใช้งานหนักๆ

"ยิ่งใช้คำสั่ง sqrt ด้วย มันทำงานช้ากว่า" ....
ใช่ครับ FSQRT ใช้ 70 clock
http://www.singlix.org/trdos/pentium.txt

สนใจอย่างนี้ ถามอย่างนี้ น่าจะลงเรียนวิชา computer architecture + optimization, assembly programming อีกซักนิดนะครับ Wink

ส่วนใหญ่เราจะมีวิธีคำนวนที่เร็วกว่านั้น นั่นคือใช้ look-up table
http://www.df.lth.se/~john_e/gems/gem0034.html
http://www.nvidia.com/object/fast_math_routines.html

หรือเราสามารถใช้ความรู้ U,V pipe ใน FPU ทำให้การคำนวนเร็วขึ้นอีกนิด
http://www.geisswerks.com/ryan/FAQS/fpu.html

ข่าวดีก็คือตอนนี้เราสามารถย้ายไปใช้ floating-point parallel computing บน GPU ใน 3d card กันแล้วครับ
http://wwwcg.in.tum.de/Research/Publications/UberFLOW

ps. GPU Computing มันคือสิ่งที่'เกมเมอร์'เรียกมันว่า shader นั่นล่ะครับ ..แต่สามารถเอาไปใช้ได้อีกเพียบ และเป็นมาตรฐานใหม่ไปแล้วเรียบร้อย นี่คือสิ่งที่ผมบ่นช่วง 2-3 ปีนี้ว่าเมื่อไหร่เราจะตามเทคโนโลยีทันฝรั่งกะเค้าบ้าง ...� Huh
Logged

..
นายตาหวาน (Mr.Tawan)
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +61/-36
Offline Offline

Gender: Male
Posts: 1,591


« Reply #11 on: 25 January 2006, 09:21:56 PM »

มอง GPU ให้เหมือนกับเป็น Vector Floating-Point Processor ตัวนึงสินะครับ Cheesy

[Edit]Floating-Pointer มีที่ไหนฟะ ?[/Edit]
« Last Edit: 26 January 2006, 05:03:17 AM by นายตาหวาน » Logged

Are you feeling fine?
眠れない夜には君の幻が...
She said, "Loving you made me happy everyday"
kero
Approved Member
Jr. Member
*

จำนวน ชม/ไม่พอใจ: +3/-0
Offline Offline

Posts: 56


« Reply #12 on: 25 January 2006, 11:58:34 PM »

ต่อไป ผมว่าในการ์ด 3D มันคงมี Colision Detect เตรียมไว้ให้เราเลยแหงๆ
Logged
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #13 on: 26 January 2006, 05:47:41 AM »

มอง GPU ให้เหมือนกับเป็น Vector Floating-Point Processor ตัวนึงสินะครับ <--- ใช่เลยครับ
ต่อไป ผมว่าในการ์ด 3D มันคงมี Colision Detect เตรียมไว้ให้เราเลยแหงๆ <--- ใกล้แล้วครับแต่ยังไม่ถึงขั้น real-time
http://www.cs.unc.edu/~geom/QCULLIDE/ Wink
ต้องรอดูว่าคนจะคิดชนะเครื่อง (คือคิด algorithm เจ๋งๆ ได้) หรือ hardware มันจะวิ่งกระโดดไปทำงานเร็วจนถึงขั้นนั้น(คืออัด pipe ไปเยอะๆ 1 pixels/1 pipe) หรือทั้งสองอย่างวิ่งมาชนกัน� Grin

ต่อไปภาพจาก 3D card จะสวยกว่านี้อีก สุดท้ายข้อจำกัดจะไปหยุดที่จินตนาการแทน Cheesy
ต้องรอ 3D display ที่ละเอียด+ถูกกว่านี้ด้วยครับ

เห็นบอร์ดช่วงนี้ว่างๆ เลยมีปัญหามาถาม� Grin เผื่อใครสนใจลองคิดดูสนุกๆ

1. ให้จุด (x1,y1) และ (x2,y2) และใช้ DDA algorithm ในการลากเส้นตรง ถามว่า algorithm นี้ทำงานทั้งหมดเป็นจำนวนกี่รอบ (คำตอบอยู่ในรูปของตัวแปร x1,y1,x2,y2)

2. ถ้าเป็นการคำนวนแบบขนาน (1 จุด ต่อ การคำนวน 1 รอบ แบบ GPU, สมมติว่า GPU สามารถคำนวน fn (+,-,*,/,sqr,sqrt,dot,swap,abs,max(a,b)) ได้ใน 1 clock/cycle และอ่าน look-up table สำหรับ sincos ได้ใน 1 clock) แล้ว ควรใช้ DDA หรือไม่ เหตุผลคือ ? และถ้าไม่ควร ควรใช้ algorithm แบบใด (คิด algorithm อันใหม่ เองก็ได้นะ)

ตอบข้อแรกได้ แสดงว่าเข้าใจ algorithm ตอบข้อสองได้แสดงว่าเข้าใจวิธีคิดแบบขนาน
.. ไม่จำเป็นต้องเฉลยมั้ง� Cheesy
Logged

..
AAG_th4
Approved Member
Hero Member
*

จำนวน ชม/ไม่พอใจ: +42/-7
Offline Offline

Gender: Male
Posts: 601


Fighter/Attack Pilot


WWW
« Reply #14 on: 26 January 2006, 09:55:35 PM »

ไม่แน่ใจนะครับว่าอนาคตของPPU (Physic Processing Unit) Card นี้จะไปด้วยกันกับ 3D Card ยุคต่อไปด้วยหรือไม่ ไม่ว่าจะเป็นแบบที่เป็น Card เดียวเอามาเสียบเพิ่ม หรืออาจจะมีประเภทรวมใน 3D Card เลยก็ได้ครับ

Logged

ประเทศไทยขณะนี้ต้องการผู้เสียสละ มิใช่ผู้ที่จะคอยตักตวงผลประโยชน์

"Rig for Sillent Running"
noky
Approved Member
Full Member
*

จำนวน ชม/ไม่พอใจ: +3/-0
Offline Offline

Gender: Male
Posts: 131



« Reply #15 on: 27 January 2006, 10:23:37 AM »

อ่า จริงๆก็ไม่ได้สนใจเรื่อง วิเคราะห์ อัลกออะไรหรอกครับ (ไม่ค่อยชอบด้วยซ้ำ แต่มันก็ต้องเรียนพึ่งทำให้โค้ดเรามันดีขึ้น) หลังจากเรียนแล้วก็เป็นโรควิตก ขึ้นมาก กลัวว่าจะช้าไปซะหมด link ความรู้มากมายที่พี่ให้มาผมขอไปศึกษาก่อนนะคับ
« Last Edit: 02 August 2012, 08:07:53 PM by noky » Logged
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #16 on: 27 January 2006, 11:23:18 AM »

อ่อ อ่านไม่รู้เรื่องไม่เป็นไรครับ .. link นั่นมันขั้น advance ลืมไปๆ ขอโทษด้วยครับ ^^'

อืม เขียนให้อ่านง่ายขึ้นนะ

เวลา check ที่นี้ถ้าไม่อยากให้เป็นกรณี O(n^2) เราจะทำอะไรกับมันได้บ้าง
 วิธีนึงคือ bucket โยนใส่ถัง หรือสร้าง hash ขึ้นมาตัวนึง ซึ่งเป็นที่รวมกลุ่ม แล้วก็ check เฉพาะกลุ่มตัวเองและกลุ่มข้างๆ

เช่น สมมติว่ามีตำแหน่งแบบนี้: (1,1) (5,7) (10,5) (15,8) (20,30) (24,1) (27,19) (41,7)� (58,55)
เราก็ให้กฏว่า
กลุ่ม 1: 0<=x<10 : (1,1) (5,7)
กลุ่ม 2: 10<=x<20 : (10,5), (15,8)
กลุ่ม 3: 20<=x<30 : (24,1) (27,19)
กลุ่ม 4: 30<=x<40 : (41,7)
กลุ่ม 5: 40<=x<50 : ไม่มี
กลุ่ม 6: 50<=x<60 : (58,55)
จะได้ 6 กลุ่ม

(ที่ให้ดูนี้คือแบ่งตามค่า หารด้วย 10 หรือจะใช้ hash อย่างอื่นก็ได้นะ)
เวลาทดสอบ สมมติหยิบ (24,1) ขึ้นมาดู
ก็ดูก่อนว่า (24,1) อยู่ในกลุ่มเท่าไหร่
ซึ่งมันคือกลุ่ม 3 ดังนั้น เราก็จะตรวจ เฉพาะ ตำแหน่งที่อยู่ในกลุ่ม 3 และกลุ่มข้างเคียง (กลุ่ม 2 กับ 4)
คือเฉพาะ
(10,5), (15,8)� (24,1) (27,19) (41,7)
ที่เหลือไม่จำเป็น
 Smiley

ส่วน look-up table มันคือการคำนวนค่าไปเก็บไว้ใน array ก่อน แล้วเอามาใช้ทีหลัง
เช่น sin( ) กิน CPU มาก สมมติว่าเราต้องการใช้แค่จำนวน 0..359 ของค่า sine
เราก็คำนวนไว้ก่อนแบบนี้
Code:
float sin_table[360];
for (i=0; i<360; i++) sin_table[ i ]= sin(i*pi/180);

เวลาใช้ก็
Code:
dir_x =� cos_table[ angle % 360 ]� * speed;
dir_y =� sin_table[ angle % 360 ]� * speed;
เวลาที่ใช้ก็จะคิดที่ การlook-up + การคูณ เท่านั้นเอง

ส่วน link ข้างบนนั้นมันยุ่งยากเพราะว่า เราต้องการ look-up ของ sqrt ทุกค่า (แต่ lost precision ไปบ้าง) และก็ต้องมีการคำนวนผสมด้วย
 Cheesy

เค้าว่า space & time มันขัดแย้งกัน 
.. space (เนื้อที่สำหรับทำlook-up)เยอะ ใช้ time (เวลาสำหรับคำนวน)น้อย
.. space (เนื้อที่สำหรับทำlook-up)น้อย ใช้ time (เวลาสำหรับคำนวน)เยอะ
มันเป็นมิตินึง แบบ กว้างxยาว หน่ะครับ ของมีปริมาตรเท่ากัน จะไปยืดมิติไหนก็เลือกเอา
Logged

..
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #17 on: 27 January 2006, 11:45:44 AM »

ต่ออีกนิด 
ว่ากันว่า .. ใน pentium รุ่นแรกๆ ที่มีบัก การคำนวนเกิดขึ้นเพราะค่าใน look-up table มันผิดไปหน่ะครับ Cheesy

U,V pipe ใน CPU และ FPU
คือ Processor ปัจจุบันสามารถทำงานแบบขนาดได้บางคำสั่ง เช่น
ถ้าสั่ง คำสั่ง บวก ติดๆ กัน (.. โดย addr ที่อ้างถึงไม่เป็นผลลัพธ์ของอีกอันและข้อกำหนดจิปาถะอื่นๆ ฯลฯ  Cheesy)
a=a+b
c=b+d
จะถือว่าสามารถรวมได้ ใน 1 cycle

คร่าวๆ เท่านี้ก่อนครับ ถ้ามีเวลาว่างๆ จะลองเขียนถึงสถาปัตยกรรม Processors แบบต่างๆ ถ้าสนใจนะ  Tongue
http://arstechnica.com/articles/paedia/cpu/pentium-m.ars/2
http://en.wikipedia.org/wiki/SIMD
http://arstechnica.com/articles/paedia/cpu/cell-1.ars
Logged

..
noky
Approved Member
Full Member
*

จำนวน ชม/ไม่พอใจ: +3/-0
Offline Offline

Gender: Male
Posts: 131



« Reply #18 on: 28 January 2006, 09:52:07 AM »

อ้า เข้าใจแล้วครับ ขอบคุณครับพี่ กระทู้ที่อุดมไปด้วยคามรู้ เด็กมือใหม่ที่แวะเวียนมาก็จะได้ความรู้ไปด้วย ขอให้พี่รวยๆ จะได้มีเวลาเยอะๆมาให้ความรู้อีก ^_^
Logged
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #19 on: 28 January 2006, 09:01:27 PM »

ขอบคุณครับ ^^'
ถ้าผมรวยเมื่อไหร่คงจะสร้างห้องสมุดซักที่นึงสำหรับเก็บ collection หนังสือสร้างเกมทั่วโลก และความรู้ที่เกี่ยวข้อง และที่สำคัญก็คือ service ฟรี� หุหุ

 Cheesy
Logged

..
pit
Jr. Member
**

จำนวน ชม/ไม่พอใจ: +6/-0
Offline Offline

Posts: 85


« Reply #20 on: 22 May 2008, 08:31:04 PM »

กระทู้นี้ก็นานแล้ว แต่ขอเพิ่มเติมส่วนที่ยังไม่มีให้ครับ

การ detect collision ของ sphere 2 อัน มันมีวิธีอื่นครับ

1. อันนี้ต้องลองอ่านเรื่องการเก็บ floating point ดูครับ ผมแค่ guide ให้คร่าวๆ ในหนังสือ game programming ธรรมดาก็มี
แล้วใช้มหาศาลมากในการเขียนระบบ physic

floating point (float 4 bytes) มันเก็บข้อมูลประมาณนี้ครับ
bit ที่ 31    เป็น sign bit (S)
bit ที่ 30-23 เป็น exponent (E)
bit ที่ 22-0  เป็น mantissa (M) (จำนวน bit อาจจะไม่ถูกนะครับ ลองหาอ่านเองอีกที )

ดังนั้นค่าของ floating point มันก็คือ (-1)*S +2^(E-127)+(1+M/(2^23)) ประมาณนี้

ยกตัวอย่างง่ายๆ

กำหนดให้ f คือค่า float แล้ว i คือ integer = *(int *)&f (ก็คือค่า integer ที่มองบน float)
จะพิจารณาว่าค่า float เนี่ยมันน้อยกว่า 0 หรือเปล่า ก็ (i & 0x80000000)
จะคูณเลข 2^n กับ float ก็คือ i + (1<<(22+n))

มันมีสมการง่ายๆ ครับ sqrt(1.M) จะมีค่าประมาณ M/2 เลย
เมื่อ M เป็น mantissa ลองกดเครื่องคิดเลขดูก็ได้
หา sqrt ก็สบายแล้วครับ
ก็แค่ shift right ค่า float
ค่า Exponent ที่โดน shift right -> ก็จะมีค่าเท่ากับ sqrt ในส่วนของ exponent
ค่า Mantissa ใน float ก็คือ Mantissa/2 ตามสูตรข้างบน
sign bit ก็ต้องมีค่าเป็นบวกเสมอ
ถ้าไม่เข้าใจ ผมว่าใน google ก็มี source code ลอกได้เลยครับ
วิธีนี้ช่วยหา sqrt ในเวลาที่เร็วขึ้นบาน ก็เอาไปใช้ได้ในการตรวจ sphere หรืออย่างอื่น

ถ้าถามว่า ในเมื่อเค้าก็มี trick floating point นี่แล้ว ทำไม compiler มันไม่จัดการให้เรา
คำตอบคือ วิธีที่กล่าวมามันไม่แม่นยำเท่าไหร่ครับ มันมี limit ของมันบ้าง แต่ work ใน case ทั่วๆ ไป


2. อีกวิธีอย่าใช้ sqrt เลยสิครับ
ก็อย่าเก็บค่ารัศมีของวงกลม แต่เก็บค่า รัศมี^2 ของวงกลมแทน

ให้ n1=รัศมีวงกลม1^2 และ n2=รัศมีวงกลม2^2
ดังนั้น เราก็พิจารณาแค่ (x1-x2)^2+(y1-y2)^2+(z1-z2)^2<(n1+n2))
ให้ยิ่งแจ๋วกว่านี้อีก x1-x2,y1-y2,z1-z2 ก็ใช้ SIMD ช่วยอีก


เรื่อง O(n^2) ในการพิจารณาวัตถุที่ชนกัน เค้ามีชื่อเรียกการทำงานส่วนนี้ในระบบ physic ว่า broad phase
วิธีการที่ผมคิดว่าดี คือใช้ ส่วน scene management ที่มีอยู่แล้วในระบบ 3d engine เช่น bsp, octree ...อื่นๆ
ช่วยในการตัดส่วนที่ไม่ชนแน่ๆออกไป แต่ถ้าเราไม่มี scene management ก็มีวิธี O(nlogn) ครับ

เรื่องการใช้ hashing ช่วยตามวิธีคุณ yod เค้าไม่ได้ทำเป็น chain อย่างคุณ yod ทีเดียว  เค้าก็ใช้ double hashing เหมือนเดิมครับ
แต่ key เป็น function ของ x,y,z ออกมาเป็น grid มันเรียกวิธีนี้ว่า spatial hashing ยังไง concept ของ double hashing มันดีกว่าทำ hash เป็น chain
อยู่แล้วครับ เพราะกินเนื้อที่น้อยกว่า ไม่เปลือง linklist วิธีนี้จะดีเมื่อ object มันมี size ใกล้ๆ กัน แต่ถ้า object มี size ต่างกันมาก มันจะมีปัญหา
ในการวิ่งหา grid รอบๆ ที่มีโอกาสชนกันครับ   แล้วในการสร้าง function ของ x,y,z บน grid เราจำเป็นต้องรู้ boundary ของ
object เราว่ามันขนาดไหนก่อนคิดออกมาเป็น funtion  ผมมีความเห็นว่าวิธีนี้ยังไม่ practical เท่าไหร่ครับ

มันมีคนคิดวิธีที่เรียกว่า sort and sweep ซึ่ง practical กว่า ผมเห็นcode คนอื่นทำระบบ physic เค้าก็ชอบวิธีนี้กันนะ หัวใจหลักก็เหมือนใน url ที่คุณ chanon post ไว้ครับ มันใช้ก็สร้าง AABB ขึ้นมา แล้วจับแต่ละ axis มา sort ตามแกน x,y,z  แล้วก็ check ว่า อันไหน overlap กันอยู่ทั้ง 3 แกน ก็เป็นไปได้
ที่จะมีการชน แล้วมันจะทำสิ่งทีเรียกว่า narrow phase อีกที เพื่อหาจุดชน ในส่วนของ narrow phase มันจะขึ้นอยู่กับว่า object เป็นอะไร ถ้าเป็น sphere-sphere ก็ใช้วิธีข้างบนก็ได้ครับ ถ้าเป็น box-box ก็ใช้ SAT (ใน url คุณ chanon) แต่ไป apply เป็น SAT บน 3D หน่อยก็ได้ครับ (ผมก็คิดมาหลายวิธี
ยังคิดวิธีดีกว่านี้ไม่ออกเหมือนกัน)

ส่งท้ายเรื่อง look-up table ของคุณ yod อันนี้เห็นมี คนสนใจเรื่องการ optimize อยู่ครับ ก็ lookup table นี้เป็นตัวอย่างที่ดีอันนึง

ถ้าเรากำหนดองศาใหม่เป็น 0..256 หรือ 0..512 จะดีกว่า 0..360 เพราะนั่นคือ
ตอน lookup เราก็ใช้ dir_x = cos_table[ angle & 0xFF ] แทน ซึ่ง and มันเร็วกว่า mod
ที่ผมใช้อยู่ก็ใช้ 0..256 ครับ scale มันลดลงไปไม่เยอะ ไม่พอใจก็ใช้ 0..512 ก็ได้ครับ แล้ว & 0x1FF 

cos มันจะมีค่า = sin ที่อยู่หน้ามัน quarter นึง เสมอ
ง่ายๆ ก็สร้าง cos_table ตัวเดียวไม่ต้องสร้าง sin_table
เวลาหา sin ที่ x ก็ = cos_table[(x+64) & 0xFF] ถ้าเราให้ table เรามี x เป็น 0..256 นะ
ประหยัด memory แต่ calculate เพิ่มกิน cpu นิดเดียว

2 trick หลังสุดนี่บนเครื่องปัจจุบัน จริงๆมันคงไม่มีประโยชน์อะไรแล้วครับ ram เป็น G cpu ยังทำ parallel ได้อีก
แต่เป็น idea ในการ implement ครับ เอาไป apply อย่างอื่นที่มีผลมหาศาลได้ครับ ตัวเลข power of 2 นี่
ได้ใช้เกือบทุกอย่างที่เป็น constant เลย
Logged
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #21 on: 22 May 2008, 10:40:35 PM »

ขอบคุณคุณ pit นะครับ ถ้ามีอะไรก็ช่วยเสริมได้นะครับ ยินดีๆ : )

อืม สนใจเรื่อง square root ผมก็เพิ่งเห็นในนี้ คนคิดเข้าใจคิดดีแหะ
แต่เข้าใจว่าได้ผลเป็นค่าประมาณนะครับ ?
Logged

..
เจ้าชายกบ
Approved Member
Sr. Member
*

จำนวน ชม/ไม่พอใจ: +22/-3
Offline Offline

Posts: 358


« Reply #22 on: 22 May 2008, 11:41:50 PM »

มาเก็บความรู้เรื่อง square root ด้วยคนครับ
Logged
pit
Jr. Member
**

จำนวน ชม/ไม่พอใจ: +6/-0
Offline Offline

Posts: 85


« Reply #23 on: 23 May 2008, 08:56:17 AM »

ครับคุณ yod มันประมาณๆ แต่ผลลัพธ์ที่ใช้อยู่ ก็ไม่เลวนะ
 Smiley




Logged
mankjon
Approved Member
Newbie
*

จำนวน ชม/ไม่พอใจ: +0/-3
Offline Offline

Posts: 34


« Reply #24 on: 10 July 2009, 12:24:24 AM »

ถ้าตรวจสอบการชนแบบวงรีหรือโพลิกอนอื่นละครับ ทำยังไงครับ
« Last Edit: 10 July 2009, 12:26:00 AM by mankjon » Logged
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #25 on: 10 July 2009, 01:34:53 AM »

ถ้าตรวจสอบการชนแบบวงรีหรือโพลิกอนอื่นละครับ ทำยังไงครับ

วงรี ถ้าเอาชัวร์ๆ ก็ทดสอบว่าจุดนั้น อยู่ในรี หรือ นอกวงรี
ถ้าอยู่ที่ขอบวงรี หรือ ในวงรี ก็ถือว่าชน
http://mathworld.wolfram.com/Ellipse.html

ยกตัวอย่าง วงกลมก่อนนะ สมการในรูป Cartesian coordinates  ของวงกลม (สมการที่ 11 จาก http://mathworld.wolfram.com/Circle.html)
อยู่ในรูป
(x - x0) ^2 + (y - y0) ^2 = a^2
a=รัศมี
x0,y0=จุดศูนย์กลางของวงกลม
ที่นี้ก็จะเหลือเจ้า x,y ที่ใช้แทนจุดที่จะทดสอบครับ

ถ้าแทนค่าแล้ว (x - x0) ^2 + (y - y0) ^2 < a^2 แปลว่าจุดนั้นอยู่ในวงกลม
ถ้าแทนค่าแล้ว (x - x0) ^2 + (y - y0) ^2 > a^2 แปลว่าจุดนั้นอยู่นอกวงกลม

ถ้าแทนค่าแล้ว (x - x0) ^2 + (y - y0) ^2 = a^2 แปลว่าจุดนั้นอยู่ขอบวงกลม
หรือเขียนคำนวณได้เป็น
| [ (x - x0) ^2 + (y - y0) ^2 ] - [ a^2  ] | < epsilon

ที่นี้วงรีก็ทำนองเดียวกัน จะเช็คได้ก็ต้องทำให้สมการวงรีอยู่ในรูปใช้งานได้ก่อนครับ
ซึ่งก็ต้องหาคำนวณแกนวุ่นวายเพราะวงรีมีแกนที่หมุนได้

แต่ถ้าไม่ซีเรียสมากก็ใช้วงกลมหลายๆ วงใส่ผสมกัน  Grin


สำหรับ โพลิกอนอื่นๆ ปกตินิยมใช้ line-plane collision ครับ
ซึ่งลดรูปจากสการยุ่งๆ มาเป็น dot product
http://en.wikipedia.org/wiki/Line-plane_intersection
เคยคุยกันไปแล้วใน web นี้ละครับ ลองหาดู Smiley
Logged

..
mankjon
Approved Member
Newbie
*

จำนวน ชม/ไม่พอใจ: +0/-3
Offline Offline

Posts: 34


« Reply #26 on: 10 July 2009, 04:01:44 AM »

เท่าที่ผมดูสมการวงรีนะครับคือ   X^2/a^2+Y^2/b^2=1
ผมว่าถ้าเราให้ค่า a=5 และค่า b=3 ก็จะได้ว่า
X^2/25+Y^2/9=1 แล้วก็หาค่า X Y เอามาใส่สมการนี้ดูถ้ามันมากกว่า 1 แสดงว่ามันไม่ได้อยู่ในวงรี แต่ถ้ามันน้อยกว่าหรือเท่ากับมันจะอยู่ในวงรีใช่เปล่าครับ ถ้าผิดยังไงก็ช่วยแก้ทีนะครับ
Logged
Thaina
Approved Member
Hero Member
*

จำนวน ชม/ไม่พอใจ: +29/-83
Offline Offline

Gender: Male
Posts: 810



« Reply #27 on: 10 July 2009, 04:16:28 AM »

ถูกต้องแล้วครับ

สมการเต็มคือ
((X + x0)^2/a^2) + ((Y + y0)^2/b^2) = 1

จริงๆแล้วอาจจะต้องเพิ่ม sin cos ไปด้วยนะ เพื่อเวลามันเอียง
แต่ผมลืมไปแล้วว่าใส่ยังไง

สมการนี้ใช้ เพิ่มค่า Z เข้าไปได้ด้วยนะ แต่ตอนถอดสมการกลับด้านนี่ นรกมากๆเลย
Logged
yod
Global Moderator
Hero Member
*****

จำนวน ชม/ไม่พอใจ: +150/-15
Offline Offline

Posts: 3,240


WWW
« Reply #28 on: 10 July 2009, 08:21:30 AM »

ถ้าแทนไปแบบนั้นมันแปลว่าสมการวงรีอยู่ที่จุด (0,0) นะครับ
สูตร 12 (http://mathworld.wolfram.com/Ellipse.html)

เวลาคำนวณ จะย้ายสมการทั้งหมดมากองรวมข้างนึง อีกข้างนึงเป็น 0 ก็ได้ครับ จากนั้นก็คำนวณเช็คว่า <, > หรือ = 0 สะดวกกว่าเดิมนิดนึง

.. ถ้าวงรีมันเอียงก็ตัวใครตัวมันล่ะกันนะ .. ถ้าอยากได้จริงๆ มันก็คำนวณได้ล่ะนะ ซับซ้อนนิดนึง ผมเคยคำนวณปัญหาประมาณนี้ให้เพื่อนหนนึงแล้ว เสียเวลาไป 1 ชม. ได้ solution ออกมาเป็นวิธีทำนิดเดียวเอง Smiley
Logged

..
Pages: [1]   Go Up
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2013, Simple Machines Valid XHTML 1.0! Valid CSS!