ตำแหน่งและเวลาของการกระแทกสำหรับจุดเคลื่อนที่และส่วนของเส้นตรงที่เคลื่อนที่ (การตรวจจับการชนอย่างต่อเนื่อง)

Aug 19 2020

ฉันกำลังทำงานกับระบบคอลไลเดอร์ 2 มิติที่แบ่งรูปทรงออกเป็นหนึ่งในแบบดั้งเดิมที่เป็นไปได้: เซ็กเมนต์ที่ไม่สามารถยอมรับได้ซึ่งกำหนดโดยจุดสองจุด ในการตรวจจับการชนกันสำหรับระบบนี้ฉันใช้วิธีการตรวจจับการชนกันแบบคงที่ซึ่งคำนวณระยะห่างระหว่างขอบของส่วนหนึ่งและส่วนที่จัดการในปัจจุบัน (ระยะจุด / เส้น) หนึ่งครั้งทุกเฟรม หากระยะห่างน้อยเกินไปจะเกิดการชนกันระหว่างเฟรมนั้น วิธีนี้ใช้งานได้ดี แต่มีปัญหาในการขุดอุโมงค์หากร่างอย่างน้อยหนึ่งตัวแสดงความเร็วสูง ดังนั้นฉันกำลังหาทางเลือกอื่น

ตอนนี้ฉันต้องการแนะนำการตรวจจับการชนกันอย่างต่อเนื่อง (CCD) ที่ทำงานบนจุดไดนามิก / ส่วนแบบไดนามิก ปัญหาของฉันคือฉันไม่รู้ว่าเป็นอย่างไร ฉันรู้วิธีการชนอย่างต่อเนื่องระหว่างจุดเคลื่อนที่สองจุดจุดเคลื่อนที่และส่วนคงที่ แต่ไม่ใช่วิธีการทำ CCD ระหว่างจุดเคลื่อนที่ (กำหนดโดยจุด P) และส่วนที่เคลื่อนที่ (กำหนดโดยจุด U และ V ทั้งสองอย่างทำได้ เคลื่อนไหวได้อย่างอิสระอย่างสมบูรณ์)

ภาพประกอบปัญหา

ฉันเคยเห็นคำถามที่คล้ายกันที่ถูกถามบน SO และแพลตฟอร์มอื่น ๆ แต่ไม่ใช่กับข้อกำหนดที่แน่นอนเหล่านี้:

ทั้งจุดและส่วนกำลังเคลื่อนที่
ส่วนสามารถหมุนและยืดได้ (เนื่องจาก U และ V เคลื่อนที่ได้อย่างอิสระ)
ต้องพบเวลาการชนและจุดชนอย่างแม่นยำระหว่างสองเฟรม (CCD ไม่มีการทดสอบการชนกันแบบคงที่)
ฉันชอบ Solutiuon ที่สมบูรณ์แบบทางคณิตศาสตร์ถ้าเป็นไปได้ (ไม่มีอัลกอริธึมการประมาณแบบวนซ้ำปริมาณการกวาด)
หมายเหตุ: รูปร่างของเส้นกวาดจะไม่เป็นรูปหลายเหลี่ยมนูนเสมอไปเนื่องจากจุด U, V มีอิสระ ( ดูภาพ )
หมายเหตุ: การทดสอบการชนกับการทดสอบปริมาตรแบบกวาดไม่ถูกต้องเนื่องจากจุดชนกับรูปหลายเหลี่ยมไม่ได้หมายถึงจุดชนในการเคลื่อนที่จริง ( ดูภาพจุดจะออกจากรูปหลายเหลี่ยมเมื่อส่วนจริงข้ามวิถีของ ประเด็น)

ดังนั้นไกลฉันขึ้นมาด้วยวิธีการดังต่อไปนี้ให้สิทธิ์แก่ :

sP (P ที่จุดเริ่มต้นของเฟรม),
eP (P ที่ส่วนท้ายของเฟรม)
sU (U ที่จุดเริ่มต้นของเฟรม)
eU (U ที่ส่วนท้ายของเฟรม)
sV (V ที่จุดเริ่มต้นของเฟรม),
eV (V ที่ส่วนท้ายของเฟรม)

คำถาม : พวกเขาจะชนกันหรือไม่? ถ้าใช่เมื่อไรและที่ไหน?

เพื่อตอบคำถาม "if" ฉันพบว่าเอกสารนี้มีประโยชน์: https://www.cs.ubc.ca/~rbridson/docs/brochu-siggraph2012-ccd.pdf(หัวข้อ 3.1) แต่ฉันไม่สามารถหาคำตอบของ "เมื่อ" และ "ที่ไหน" ได้ ฉันยังพบคำอธิบายทางเลือกของปัญหาที่นี่:http://15462.courses.cs.cmu.edu/fall2018/article/13 (คำถามที่ 3)

วิธีแก้ไข :

สร้างแบบจำลองวิถีชั่วคราวของแต่ละจุดระหว่างเฟรมเป็นการเคลื่อนที่เชิงเส้น (วิถีเส้นสำหรับ0 <= t <= 1 )

P (เสื้อ) = sP * (1 - t) + eP * t
U (เสื้อ) = sU * (1 - t) + eU * t
V (เสื้อ) = sV * (1 - t) + eV * t

( 0 <= a <= 1แทนตำแหน่งบนเซ็กเมนต์ที่กำหนดโดย U และ V):

UV (a, t) = U (t) * (1 - a) + V (t) * ก

การชนกันของโมเดลโดยการหาจุดสมการและสมการเซ็กเมนต์:

P (เสื้อ) = UV (a, t)
P (เสื้อ) = U (เสื้อ) * (1 - ก) + V (เสื้อ) * ก

รับฟังก์ชันสำหรับเวกเตอร์จากจุด P ไปยังจุดบนเซ็กเมนต์ ( ดูรูปของ F ):

F (a, t) = P (เสื้อ) - (1 - ก) * U (t) - a * V (t)

ตอนนี้พบว่าการปะทะกันซึ่งเป็นหนึ่งในความต้องการที่จะหาและเสื้อเพื่อให้F (A, t) = (0, 0)และที่เสื้อใน [0, 1] สิ่งนี้สามารถจำลองเป็นปัญหาการค้นหารูทที่มี 2 ตัวแปร

แทรกสมการวิถีชั่วคราวลงในF (a, t) :

F (a, t) = (sP * (1 - t) + eP * t) - (1 - ก) * (sU * (1 - t) + eU * t) - a * (sV * (1 - t ) + eV * t)

แยกสมการวิถีชั่วคราวตามมิติ (x และ y):

Fx (a, t) = (sP.x * (1 - t) + eP.x * t) - (1 - ก) * (sU.x * (1 - t) + eU.x * t) - ก * (sV.x * (1 - ท) + eV.x * t)
Fy (a, t) = (sP.y * (1 - t) + eP.y * t) - (1 - ก) * (sU.y * (1 - t) + eU.y * t) - ก * (sV.y * (1 - ท) + eV.y * t)

ตอนนี้เรามีสองสมการและสองตัวแปรที่เราต้องการแก้ปัญหา ( Fx, Fyและa , tตามลำดับ) ดังนั้นเราควรจะสามารถใช้ตัวแก้เพื่อหาaและt ได้จากนั้นตรวจสอบว่ามันอยู่ภายใน [0, 1] .. ใช่ไหม?

เมื่อฉันเสียบสิ่งนี้เข้ากับ Python sympy เพื่อแก้ปัญหา:

from sympy import symbols, Eq, solve, nsolve

def main():

    sxP = symbols("sxP")
    syP = symbols("syP")
    exP = symbols("exP")
    eyP = symbols("eyP")

    sxU = symbols("sxU")
    syU = symbols("syU")
    exU = symbols("exU")
    eyU = symbols("eyU")

    sxV = symbols("sxV")
    syV = symbols("syV")
    exV = symbols("exV")
    eyV = symbols("eyV")

    a = symbols("a")
    t = symbols("t")

    eq1 = Eq((sxP * (1 - t) + exP * t) - (1 - a) * (sxU * (1 - t) + exU * t) - a * (sxV * (1 - t) + exV * t))
    eq2 = Eq((syP * (1 - t) + eyP * t) - (1 - a) * (syU * (1 - t) + eyU * t) - a * (syV * (1 - t) + eyV * t))

    sol = solve((eq1, eq2), (a, t), dict=True)

    print(sol)

if __name__ == "__main__":
    main()

ฉันได้รับโซลูชันที่มีขนาดใหญ่มากและใช้เวลาประมาณ 5 นาทีในการประเมิน ฉันไม่สามารถใช้นิพจน์ที่ยิ่งใหญ่เช่นนี้ในรหัสเครื่องยนต์จริงของฉันได้และการแก้ปัญหานี้ดูเหมือนจะไม่เหมาะกับฉัน

สิ่งที่ฉันอยากรู้คือฉันพลาดอะไรไปหรือเปล่า? ฉันคิดว่าปัญหานี้ดูเหมือนจะเข้าใจง่าย แต่ฉันไม่สามารถหาวิธีที่ถูกต้องทางคณิตศาสตร์ในการหาเวลา ( t ) และจุด ( a ) ของวิธีแก้ปัญหาผลกระทบสำหรับจุดไดนามิก / ส่วนไดนามิก ความช่วยเหลือใด ๆ ที่ได้รับการชื่นชมอย่างมากแม้ว่าจะมีคนบอกฉันว่าเป็นไปไม่ได้ที่จะทำเช่นนั้น

คำตอบ

1 Blindman67 Aug 20 2020 at 02:52

TLDR

ฉันอ่าน"... เช่น 5 นาทีในการประเมิน ... "

ไม่นานเกินไปนี่เป็นวิธีแก้ปัญหาแบบเรียลไทม์สำหรับหลายบรรทัดและหลายจุด

ขออภัยนี่ไม่ใช่คำตอบที่สมบูรณ์ (ฉันไม่ได้หาเหตุผลเข้าข้างตนเองและทำให้สมการง่ายขึ้น) ซึ่งจะหาจุดสกัดกั้นที่ฉันฝากไว้ให้คุณ

นอกจากนี้ฉันสามารถเห็นวิธีการแก้ปัญหาหลายวิธีเมื่อมันหมุนรอบสามเหลี่ยม (ดูภาพ) ซึ่งเมื่อแบนคือคำตอบ วิธีการร้องหาจุดในเวลาที่ด้านยาวของสามเหลี่ยมเท่ากับผลรวมของสองอันที่สั้นกว่า

การแก้ปัญหาสำหรับคุณ (เวลา)

สิ่งนี้สามารถทำได้เป็นกำลังสองอย่างง่ายโดยมีสัมประสิทธิ์ที่ได้มาจากจุดเริ่มต้น 3 จุดเวกเตอร์ตามเวลาหน่วยของแต่ละจุด การแก้ปัญหาสำหรับคุณ

ภาพด้านล่างให้รายละเอียดเพิ่มเติม

จุดPคือจุดเริ่มต้นของจุด
จุดL1 , L2คือจุดเริ่มต้นของจุดสิ้นสุดของบรรทัด
เวกเตอร์V1สำหรับจุดช่วงเวลาหน่วย (ตามเส้นสีเขียว)
เวกเตอร์V2 , V3ใช้สำหรับเส้นที่สิ้นสุดในช่วงเวลาหนึ่งหน่วย
คุณคือหน่วยเวลา
Aคือจุด (สีน้ำเงิน) และBและCคือจุดสิ้นสุดของบรรทัด (สีแดง)

นอกจากนี้ (อาจ) จุดในเวลาUที่อยู่ในสายB , C ณ เวลานี้ความยาวของเส้นAB (เป็นa ) และAC (เป็นc ) จะรวมกันเท่ากับความยาวของเส้นBC (เป็นb ) (เส้นสีส้ม)

นั่นหมายความว่าเมื่อb - (a + c) == 0จุดอยู่บนเส้น ในภาพจุดจะถูกยกกำลังสองเนื่องจากทำให้ง่ายขึ้นเล็กน้อย ข² - (ก² + ค² ) == 0

ที่ด้านล่างของภาพที่เป็นสมการ (กำลังสอง) ในแง่ของU, P, L1, L2, V1, V2, V3

สมการนั้นจำเป็นต้องจัดเรียงใหม่เพื่อให้คุณได้(???) u ² + (???) u + (???) = 0

ขออภัยการทำด้วยตนเองนั้นน่าเบื่อมากและมีแนวโน้มที่จะผิดพลาดได้ง่าย ฉันไม่มีเครื่องมือในการทำเช่นนั้นและฉันไม่ได้ใช้ python ดังนั้น lib ทางคณิตศาสตร์ที่คุณใช้จึงไม่เป็นที่รู้จักสำหรับฉัน อย่างไรก็ตามมันควรจะสามารถช่วยคุณหาวิธีคำนวณค่าสัมประสิทธิ์ของ(???) u ² + (???) u + (???) = 0

อัปเดต

ละเว้นส่วนใหญ่ข้างต้นเนื่องจากฉันทำผิดพลาด ข - (A + c) == 0คือไม่เหมือนกับข² - (หนึ่ง² + C ² ) == 0 อันแรกคือสิ่งที่จำเป็นและนั่นคือปัญหาเมื่อจัดการกับอนุมูล (โปรดทราบว่ายังมีวิธีแก้ปัญหาโดยใช้จำนวนจินตภาพอยู่a + bi == sqrt(a^2 + b^2)ที่ไหนi)

อีกวิธีหนึ่ง

ดังนั้นฉันจึงสำรวจตัวเลือกอื่น ๆ

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

ดังนั้นเมื่อพบผลลัพธ์ให้ทดสอบโดยการหารผลคูณจุดของจุดที่พบและส่วนของเส้นตรงด้วยกำลังสองของความยาวส่วนของเส้นตรง ดูฟังก์ชันisPointOnLineในตัวอย่างข้อมูลการทดสอบ

เพื่อแก้ปัญหาฉันใช้ข้อเท็จจริงที่ว่าผลคูณไขว้ของเส้นBCและเวกเตอร์จากBถึงAจะเป็น 0 เมื่อจุดอยู่บนเส้น

การเปลี่ยนชื่อบางอย่าง

การใช้ภาพด้านบนฉันเปลี่ยนชื่อตัวแปรเพื่อให้ทำบิตที่ยุ่งเหยิงทั้งหมดได้ง่ายขึ้น

/*
point P is  {a,b}
point L1 is  {c,d}
point L2 is  {e,f}
vector V1 is {g,h}
vector V2 is {i,j}
vector V3 is {k,l}

Thus for points A,B,C over time u    */
Ax = (a+g*u)
Ay = (b+h*u)
Bx = (c+i*u)
By = (d+j*u)
Cx = (e+k*u)
Cy = (f+l*u)

/* Vectors BA and BC at u */
Vbax = ((a+g*u)-(c+i*u))
Vbay = ((b+h*u)-(d+j*u))
Vbcx = ((e+k*u)-(c+i*u))
Vbcy = ((f+l*u)-(d+j*u))

/*
   thus Vbax * Vbcy - Vbay * Vbcx == 0 at intercept 
*/

สิ่งนี้ทำให้กำลังสอง

0 = ((a+g*u)-(c+i*u)) * ((f+l*u)-(d+j*u)) - ((b+h*u)-(d+j*u)) * ((e+k*u)-(c+i*u))

เราได้รับการจัดเรียงใหม่

0 = -((i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j)*u* u -(d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j))*u +(c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b

ค่าสัมประสิทธิ์จึงเป็น

 A = -((i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j)
 B = -(d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j))
 C = (c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b

เราสามารถแก้ได้โดยใช้สูตรกำลังสอง (ดูภาพบนขวา)

โปรดทราบว่าอาจมีสองวิธี ในตัวอย่างฉันไม่สนใจโซลูชันที่สอง อย่างไรก็ตามเนื่องจากข้อแรกอาจไม่อยู่ในส่วนของเส้นตรงคุณจึงต้องเก็บโซลูชันที่สองไว้หากอยู่ในช่วง0 <= u <= 1ในกรณีที่ข้อแรกล้มเหลว คุณต้องตรวจสอบความถูกต้องของผลลัพธ์นั้นด้วย

การทดสอบ

เพื่อหลีกเลี่ยงข้อผิดพลาดฉันต้องทดสอบวิธีแก้ปัญหา

ด้านล่างนี้คือตัวอย่างข้อมูลที่สร้างคู่ของเส้นสุ่มแบบสุ่มจากนั้นสร้างเส้นสุ่มจนกว่าจะพบการสกัดกั้น