ผู้ใช้:Ph156/กระบะทราย

จากวิกิพีเดีย สารานุกรมเสรี

ขั้นตอนวิธีการตรวจสอบการชน[แก้]

ขั้นตอนวิธีการตรวจสอบการชน (อังกฤษ: Collision detection)เป็นขั้นตอนวิธีที่ใช้จำลองการชนกันของวัตถุตั้งแต่ 2 ชิ้นขึ้นไป โดยส่วนมากจะพบได้ในวิดีโอเกมหรือการจำลองระบบของวัตถุ และยังใช้ในวิทยาการหุ่นยนต์ด้วย ในการตัดสินใจว่าวัตถุสองชิ้นชนกันหรือไม่นั้น ขั้นตอนวีธีการตรวจสอบการชนจะต้องคำนวณเวลาที่จะเกิดการชน (time of impact-TOI) และสามารถระบุพิกัดส่วนที่ชนกันได้ (contact manifold) การจำลองการชนกันของวัตถุโดยหลักแล้วจะใช้คอนเซปต์ของพีชคณิตเชิงเส้น(linear algebra) และเรขาคณิตเชิงคำนวณ(computational geometry)

การอธิบายขั้นตอนวิธี[แก้]

โดยส่วนมากการจำลองการชนกันของระบบของวัตถุจะเกิดขึ้นในสองลักษณะคือ การชนนั้นถูกตรวจพบหลังจากที่มีการชนเกิดขึ้นจริง(posteriori, discrete) และการชนที่ถูกตรวจพบก่อนที่มีการชนเกิดขึ้น(priori, continuous)

  • ในระบบ posteriori จะปล่อยให้วัตถุต่างๆเคลื่อนที่ไปในระยะเวลาอันสั้น แล้วเช็คว่ามีวัตถุสองชิ้นใดๆหรือไม่ที่ชนกัน(การอินเตอร์เซคกันของวัตถุ) หรือวัตถุอาจอยู่ใกล้กันมากจนถือว่าเกิดการชนขึ้น ในแต่ละขั้นของการจำลองเหตุการณ์ จะมีรายการของวัตถุที่อินเตอร์เซคกัน ซึ่งตำแหน่งและวิถีการเดินทางของวัตถุเหล่านี้จะถูกกำหนดไว้อย่างแน่นอนแล้วสำหรับการคำนวณการชน เราเรียกระบบนี้ว่า posteriori เพราะว่าส่วนมากเราจะพลาดการชนกันของวัตถุจริงๆไป แล้วค้นพบการชนหลังจากที่การชนนั้นเกิดขึ้นจริง
  • ในระบบ priori นั้นเป็นขั้นตอนวิธีการตรวจสอบการชนที่สามารถพยากรณ์วิถีการเดินทางและเวลาขณะที่เกิดการชนของวัตถุได้อย่างแม่นยำ วัตถุเหล่านั้นจะไม่เคลื่อนที่ผ่านกันจริงๆ(interpenetrate) เราเรียกระบบนี้ว่า priori เพราะว่าเราสามารถคำนวณเวลาขณะที่เกิดการชนของวัตถุได้ก่อนที่จะปรับข้อมูลของวัตถุนั้นๆ


คอมพิวเตอร์จะมองวัตถุเป็นรูปหลายเหลี่ยม(polygons) การจะค้นหาว่ามีรูปหลายเหลี่ยมสองรูปชนกันหรือไม่นั้นทำได้ยากและเสียเวลา หนึ่งในวิธีที่ง่ายและมีประสิทธิภาพมากกว่าคือ กำหนดทรงกลมล้อมที่รอบรูปหลายเหลี่ยมได้พอดี แล้วตรวจสอบว่าทรงกลมสองอันทับซ้อนกันหรือไม่ ด้วยการคำนวณว่าระยะห่างระหว่างจุดศูนย์กลางทรงกลมสองอันน้อยกว่ารัศมีของทรงกลมทั้งสองบวกกันหรือไม่ ((x1-x2)2 + (y1-y2)2 + (z1-z2)2 ≤ r12 + r22) เท่านั้น ถ้าน้อยกว่าแสดงว่ามีการชนเกิดขึ้น แต่การแทนวัตุทั้งก้อนด้วยทรงกลมนั้นทำให้เกิดความคลาดเคลื่อนค่อนข้างมาก เมื่อตรวจพบว่าทรงกลมสองอันใดๆชน(อินเตอร์เซค)กัน วัตถุนั้นอาจไม่ได้ชนกันจริงๆ เพื่อความแม่นยำมากขึ้นจึงแบ่งทรงกลมที่ล้อมรอบวัตถุทั้งก้อน เป็นทรงกลมเล็กๆที่มีขนาดใกล้เคียงกับวัตถุนั้นๆ แล้วตรวจสอบแต่ละอันว่าอินเตอร์เซคกันอีกหรือไม่ ถ้าพบว่ามีการชนเกิดขึ้น(อินเตอร์เซคกัน) ก็อาจแบ่งทรงกลมให้เล็กลงไปอีก เพื่อตรวจสอบการชน(อินเตอร์เซค)ต่อไป ทั้งนี้ขึ้นอยู่กับว่าต้องการความแม่นยำมากแค่ไหน ซึ่งก็ต้องแลกมาด้วยเวลาเช่นกัน

แต่เนื่องจากวัตถุส่วนใหญ่ในวิดีโอเกมเป็นรูปสี่เหลี่ยม จึงอาจจะใช้รูปสี่เหลี่ยมแทนทรงกลมในการประมาณรูปร่างของวัตถุ เรียกวิธีการนี้ว่า กล่องล้อมรอบที่จัดเรียงตามแนวแกน (axis-aligned bounding boxes-AABBs) หรือ ออคทรีส์ (octrees) "จัดเรียงตามแนวแกน" หมายความว่ากล่องนั้นขนานกับแกนในระบบพิกัดฉากสามมิติ หรือแต่ละด้านของกล่องตั้งฉากกับแกนหนึ่งๆ

จากนั้นเราจึงนำ AABBs ของแต่ละวัตถุไปสร้างเป็น ต้นไม้AABBs เพื่อใช้เป็นตัวตรวจสอบว่าเกิดการชนขึ้นหรือไม่ ด้วยการเทียบกล่องในปมรากของต้นไม้สองต้น ว่าอินเตอร์เซคกันหรือไม่ ถ้าใช่ก็มีโอกาสที่วัตถุจะชนกัน จึงทำการตรวจสอบต่อไปด้วยการเรียกซ้ำลงไปตามต้นไม้จนถึงใบของมัน เพื่อหาว่าส่วนไหนที่เหลื่อมล้ำกัน ด้วยการโปรเจคกล่องทั้งสองลงบนแกนหนึ่งๆ แล้วตรวจสอบว่ามีช่วงที่ซ้อบทับกันหรือไม่ วิธีการนี้เรียกว่าทฤษฎีบทการแยกจากกันบนแกน (Separating Axis Theorem) จากทฤษฎีบทนี้ทำให้ทราบว่า มีการแยกจากกันบนแกนเพียง 15 แบบเท่านั้น ถ้าการเหลื่อมล้ำกันเกิดขึ้นในทุกๆการแยกจากกันบนแกน หมายความว่ากล่องทั้งสองนั้นอินเตอร์เซคกัน หมายความว่ามีการชนเกิดขึ้นนั่นเอง

ปัญหาที่เราพิจารณาอยู่นี้เกี่ยวข้องกับการเกิดการชนกันของวัตถุในช่วงเวลาที่กำหนดหรือไม่ ถ้าใส่ความเร็วให้กับโปรเจคชันของกล่อง แล้วเกิดการเหลื่อมล้ำกันครบทั้ง 15 แบบ แสดงว่ามีการชนกันเกิดขึ้น อีกทั้งยังสามารถใช้โครงสร้างข้อมูลที่คล้ายคลึงกับต้นไม้AABBs เพื่อแยกกลุ่มของสิ่งที่ชนออกจากกลุ่มของสิ่งที่ถูกชน แล้วตรวจสอบว่ามีโอกาสหรือไม่ที่จะเกิดการชนกัน การคำนวณตามลักษณะนี้สามารถคัดแยกวัตถุที่ไม่เกิดการชนได้อย่างรวดเร็ว ซึ่งมีประสิทธิภาพการทำงานอยู่ที่ O(NlogN)

ขั้นตอนวิธีที่เกี่ยวข้อง[แก้]

ขั้นตอนวิธีต่างๆที่เกี่ยวข้องกับขั้นตอนวิธีการตรวจสอบการชนโดยส่วนมาก จะเป็นขั้นตอนวิธีที่ใช้ตรวจสอบเพิ่มเติมเพื่อให้การตรวจสอบการชนเป็นไปอย่างแม่นยำที่สุด (Optimization) ดังนี้

  • การใช้ประโยชน์จากการอยู่ติดกันอย่างชั่วคราวของวัตถุ (Exploiting temporal coherence)
  • การคัดกรองคู่วัตถุใดๆ (Pairwise pruning)
  • การตรวจสอบการชนของคู่วัตถุหนึ่ง (Exact pairwise collision detection)
  • การคัดกรองก่อนตรวจสอบ (A priori pruning)
  • การแบ่งโดยพื้นที่ (Spatial partitioning)

รหัสเทียมแสดงการทำงาน[แก้]

1   //Extremely Simplified Game Loop
2
3   while(1){
4   process_input();
5   update_objects();
6   render_world();
7   }
8
9   update_objects(){
10  for (each_object)
11  save_old_position();
12  calc new_object_position 
13  {based on velocity accel. etc.}
14  if (collide_with_other_objects())
15  new_object_position = old_position();
16  {or if destroyed object remove it etc.}
17  }

1   while the game is running
2	foreach entity in the world
3    	update(entity)
4
5   update(entity):
6	entity.old_position := entity.current_position
7	modify entity.current_position based on entity.velocity and other factors
8	if Colliding(entity) then entity.current_position := entity.old_position
9
10
11   Colliding(current_entity) -> bool:
12	foreach entity in the world
13   	if entity != current_entity then
14        	if Entities_Collide(current_entity, entity) then return true
15	return false
16
17   Entities_Collide(e1, e2) -> bool:
18	foreach polygon p1 in e1
19   	foreach polygon p2 in e2
20        	if polygons_intersect(p1, p2) then return true
21	return false

ตัวอย่างโค้ดในภาษาซี[แก้]

struct Polyhedron {
	List *faces;    	// All polygons contained in this object
	Point center;   	// Center of the object
	float radius;   	// Radius of its bounding sphere
	BSP_Node *bsp_tree; // BSP tree representing this object
};

enum flag_value {
	TOUCHES_POS_HALFSPACE = 0x1,
	TOUCHES_NEG_HALFSPACE = 0x2,
	SLICED = 0x3    	// Touches both halfspaces
};

struct BSP_Node {
	float a, b, c, d; // Coefficients of plane equation (ax + by + cz + d = 0)
	List *polygons;   // Polygons that are coplanar with said plane
	BSP_Node *positive, *negative;  // Contents of each halfspace
};

bool object_hits_world(BSP_Node *node, Polyhedron *solid) {
	if (node == NULL) return false;

	int status = classify(node, solid->center, solid->radius);

	if (status == SLICED) {
    	if (test_solid_against_polygons(node->polygons, solid))
        	return true;
	}

	if (status & TOUCHES_NEG_HALFSPACE) {
    	if (object_hits_world(node->negative, solid)) return true;
	}

	if (status & TOUCHES_POS_HALFSPACE) {
    	if (object_hits_world(node->positive, solid)) return true;
	}

	return false;
}

int classify(BSP_Node *node, Point center, float radius) {
	float distance = (center.x * node->a) + (center.y * node->b)
               	+ (center.z * node->c) + node->d;

	int status = 0;

	if (distance - radius <= 0.0) status |= TOUCHES_NEG_HALFSPACE;
	if (distance + radius >= 0.0) status |= TOUCHES_POS_HALFSPACE;

	return status;
}

bool test_solid_against_polygons(List *polygons, Polyhedron *solid) {
	Polygon *face1, *face2; Foreach(polygons, face1, {
    	Foreach(solid->faces, face2, {
        	if (polygons_intersect(face1, face2)) return true;
    	});
	});

	return false;
}

การวิเคราะห์ความซับซ้อนเชิงเวลา[แก้]

ขั้นตอนวิธีการตรวจสอบการชนนั้นมีประสิทธิภาพในการทำงานเชิงเวลาเป็น O(N2) เนื่องจากมีวัตถุที่ต้องตรวจสอบ N ชิ้น เลือกมา 2 ชิ้นคือ (N choose 2)=(N!)/(2!*(N-2)!) = N*(N-1)*(N-2)!/2*(N-2)! = N*(N-1)/2 ≈ N2 อย่างไรก็ตาม มีขั้นตอนวิธีที่สามารถปรับปรุงเวลาการทำงานให้ดีขึ้นได้ดังที่กล่าวไว้ในการอธิบายขั้นตอนวิธี ทำให้ได้ประสิทธิภาพการทำงานที่ดีที่สุดเป็น O(NlogN)

แหล่งอ้างอิง[แก้]

แหล่งอ้างอิง[แก้]

เข้าถึงจาก "https://th.wikipedia.org/w/index.php?title=ผู้ใช้:Ph156/กระบะทราย&oldid=4268739"