Phát Hiện Va Chạm Bằng Thuật Toán QuadTree C++

Phát Hiện Va Chạm Bằng Thuật Toán QuadTree C++ | Đồ Họa Máy Tính Cơ Bản

Рет қаралды 7,538

Күн бұрын

ĐỒ HOẠ MÁY TÍNH CƠ BẢN: VA CHẠM GIỮA HAI HÌNH TRÒN VÀ TỐI ƯU BẰNG QUADTREE
Mình rất hay chơi game và đa phần là các game đồ hoạ và gameplay rất hay (microsoft flight sim 2020, euro truck sim, cs2, gta v,…). Trong suốt qua trình chơi những tựa game, mình đã ấn tượng và tò mò bởi các hiệu ứng vật lý, logic,… có trong game. Vì thế mình đã bắt đầu tìm hiểu thêm về đồ hoạ máy tính và biết được các khái niệm cơ bản về va chạm và các thuật toán tối ưu.
Đây là video chỉ thuật toán đầu tay nên sẽ còn nhiều sai sót. Những video sau mình sẽ học thêm thư viện vẽ của 3blue1brown.
Tài liệu:
Truyền cảm hứng: • Building Collision Sim...
Thư viện SFML: sfml-dev.org
Verlet: algorithm-arch...
Va chạm đàn hồi hai hình tròn: imada.sdu.dk/u...
Github: github.com/lds...

Пікірлер: 57

@mannguyenduy8168 8 ай бұрын

Ko biết cách này có dư thừa ko nhưng ở đoạn 5:34, để tách 2 hình tròn ra 1 cách chính xác hơn, giả sử ở frame đầu khi 2 hình tròn chưa chồng lên nhau, gọi thời điểm này là t = 0, frame kế tiếp khi chúng đã chồng nhau rồi, gọi thời điểm này là t = 1, thì mình có thể tính đc thời điểm t' khi chúng mới vừa chạm nhau ( 0 < t' < 1 ), bằng cách viết phương trình tính khoảng cách giữa 2 hình tròn theo thời điềm t, sẽ là 1 ptrinh bậc 2, giải ptrinh bậc 2 đó sẽ ra đc 2 nghiệm là 2 thời điểm mà 2 hình tròn đó chạm sát nhau ( khoảng cách = tổng bán kính 2 htron)

@lds8455 8 ай бұрын

Dạ đúng rồi ạ, trong link dưới phần mô tả “truyền cảm hứng” tác giả có nói đó là nội suy gì đó để có thể tính chính xác hơn khi bị lặp ạ. Em chưa học toán nhiều nên ưu tiên xử lí bằng Tin

@tăng-phú-quý.lê 3 ай бұрын

Anh edit video đỉnh thật sự! Rất trực quan và dễ hiểu luôn ạ.

@lds8455 3 ай бұрын

@@tăng-phú-quý.lê mình thấy bạn làm bên claoj nè mình admin claoj á :>

@tăng-phú-quý.lê 3 ай бұрын

Ui em cũng mới thấy anh ở CLA. Anh admin web đấy cùng bạn Minh Nhựt phải không ạ. Ngưỡng mộ anh quá

@lds8455 3 ай бұрын

@@tăng-phú-quý.lê anh Nhựt lớn hơn mình 2 tủi ạ :> hình như mình nhỏ hơn bạn lun á

@khoa2008-j6f 7 ай бұрын

Ngài đỉnh quá orz

@merbingamer6951 2 ай бұрын

Hay quá ạ, bạn cho mình hỏi chút, việc tạo ra quadtree mới mỗi frame có làm ảnh hưởng hiệu suất quá không, tại sao mình không tạo ra quadtree 1 lần và update nó nhỉ. Các tree con sẽ được loại bỏ khi tree cha đủ khả năng chứa các entity bên trong, Kết lại mình muốn hỏi là khoảng 60fps với entity là khoảng 1000 point thì nên lựa chọn việc tạo quadtree mỗi frame cho đơn giản hay tạo 1 lần và update liên tục sau đó. Cảm ơn b😊

@lds8455 2 ай бұрын

@@merbingamer6951 theo mình nghĩ việc bạn thay đổi 1 node này cũng sẽ đụng chạm nhiều node khác. Lúc này sẽ dẫn đến cài rất khó. Nếu được mình nghĩ sẽ tốt hơn nlogn một tí nhưng mình nghĩ không đáng lắm. Nó sẽ là hiệu ứng la truyền một tí kiểu thằng này bỏ vùng này ohair dẫn đến thằng kia… nên mình nghĩ tốt hơn vẫn xây lại á vì dù gì bạn check cũng phải qua N vật và truy vấn logN tạo nên NlogN, việc build cây chỉ làm thanh 2NlogN thôi. Mình nghĩ thế ạ

@merbingamer6951 2 ай бұрын

@ cảm ơn bạn nhiều ạ

@thai643 8 ай бұрын

Share kiến thức rất hay 👍

@lds8455 8 ай бұрын

Mình cảm ơn ạaa

@hungnguyenthai5537 8 ай бұрын

Bổ ích quá anh ơi ❤

@lds8455 8 ай бұрын

Mình cảm ơn ạaa

@kienbuitrung7555 8 ай бұрын

Đỉnh thật sự , cảm ơn anh đã chia sẻ😁

@lds8455 8 ай бұрын

Mình cảm ơn ạa

@jirotaurus7457 8 ай бұрын

Quá hay bạn ơi, ủng hộ bạn làm thêm các vid chất lượng hơn!

@lds8455 8 ай бұрын

Mình cảm ơn ạaa

@eCircuit-Code 8 ай бұрын

video rất bổ ích

@lds8455 8 ай бұрын

Mình cảm ơn ạaa

@uocthanh8830 8 ай бұрын

Mong anh ra thêm nhiều video nữa ❤

@lds8455 8 ай бұрын

Mình cảm ơn bạn ạ

@bachgia6871 8 ай бұрын

Đỉnh đỉnh, bạn học trường gì mà giỏi thế

@lds8455 8 ай бұрын

Ôi bạn ơi mình học trường Purdue Indy nhé Thúc đẩy sự phát triển mang tính chuyển đổi, khuôn viên đô thị toàn diện đầu tiên của Đại học Purdue sẽ mang đến những cơ hội đặc biệt cho sinh viên và giảng viên của Boilermaker. Chúng tôi sẽ mở rộng tuyển sinh. Chúng tôi sẽ xây dựng các công ty khởi nghiệp. Chúng ta sẽ tạo ra kiến thức mới.Chúng tôi sẽ kết nối tài năng và ngành công nghiệp. Chúng tôi sẽ phát huy tối đa những thế mạnh độc đáo của Indy như thể thao và công nghệ y sinh. Các cơ sở ở Purdue hiện nằm gần Hành lang Công nghệ Cứng: 65 dặm nối Indy và West Lafayette với Khu Đổi mới LEAP ở điểm giữa. Chúng ta sẽ cùng nhau tạo ra nhân tài, việc làm và sự đổi mới ở trung tâm nước Mỹ!

@poxgaming9663 8 ай бұрын

video rất hay, mong anh ra nhiều video như thế nữa ạ

@lds8455 8 ай бұрын

Cảm ơn bạn ạ!!

@dungtien3705 8 ай бұрын

vid khá hay mong bạn ra nhiều vid như này

@lds8455 8 ай бұрын

Mình cảm ơn nhiều ạaa

@28_vovanthinh75 8 ай бұрын

Video hay quá ạ cảm ơn a đã chia sẻ 😊

@lds8455 8 ай бұрын

Cảm ơn bạn nhiềuu ạ!

@giangnguyentbk 8 ай бұрын

Đồng môn CLA, chào bạn. Great works 👍 Mình LK14, cũng lâu lắm rồi chưa về lại trường.

@lds8455 8 ай бұрын

Em chào anh ạ, em là Đạt đến từ THPT Đức Hoà em có luyện tuyển qg ở CLA và có tham gia media các clb ở CLA ạ

@quanguocnguyen3125 8 ай бұрын

video rất hay và bổ ích :D cảm ơn bạn đã chia sẻ

@lds8455 8 ай бұрын

Mình cảm ơn ạaa

@Cesium1809 7 ай бұрын

bạn có thể gợi ý 1 vài cách để tăng tốc độ xử lí khác ngoài QuadTree đc không? Mình có suy nghĩ khá nhiều về cái này nhưng vẫn đang gặp chút khó khăn! video rất hay ạ, rất mong bậnmf nhiều hơn về code

@lds8455 7 ай бұрын

stackoverflow.com/questions/7107231/best-algorithm-for-efficient-collision-detection-between-objects bạn có thể search rất nhiều tài liệu trên mạng, tùy vào nhu cầu mà bạn chọn 1 algo phù hợp, ngoài ra còn có niều cách tăng performance bằng cắc chia dữ liệu ra process song song bằng gpu chả hạn, nếu ko nhầm thì đó là Cuda programming

@kc8879 8 ай бұрын

Đỉnh qué ❤

@lds8455 8 ай бұрын

Mình cảm ơn ạa

@WildlifeAnimalsful 8 ай бұрын

hi, nice video, what software do you use for editing video?

@lds8455 8 ай бұрын

I used after effects but i highly recommend 1brown3blue python library

@hocgamede_unity 8 ай бұрын

Sebastian Lague phiên bản Việt Nam, quá tuyệt vời! 😄😄

@lds8455 8 ай бұрын

Mình cảm ơn nhiều ạaa!!

@tinvotrong1260 8 ай бұрын

Tuyệt vời! Mình thích cách bạn giải thích về việc phát hiện va chạm bằng quadtree một cách dễ hiểu. Video rất hữu ích và thú vị. Chúc mừng bạn đã có video thật sự chất lượng! Mình tin rằng kênh của bạn sẽ phát triển nhanh chóng. Đã đăng ký kênh và chờ đợi video tiếp theo!

@longtranha8695 8 ай бұрын

Ui trời, một trong những khó khăn nhất của học thuật toán chính là khả năng edit của các giảng viên trong trường :)) . Cảm ơn kênh rất nhiều nha, dễ hình dung mà còn đầy đủ

@lds8455 8 ай бұрын

mình cảm ơn bạn nhiều ạaa

@quyphanang6354 8 ай бұрын

cảm ơn bạn videos rất hữu ích nếu mình ứng dụng quadtree vào hình ảnh 3D (ví dụ như các khối cầu) thì không biết độ phức tạp của thuật toán vẫn là O(nlogn) ko vậy. Srrr do mình không chuyên bên máy tính mà ứng dụng hiện tại của mình thì lại là tráng va chạm trên trên 3D nên không biết ứng dụng thuật toán này có ổn không

@lds8455 8 ай бұрын

mình cũng không rõ, nhưng bạn có thể xem ở đây stackoverflow.com/questions/13487953/difference-between-quadtree-and-kd-tree Quadtree phụ thuộc vào không gian nên 3d sẽ rất nặng thời gian, mặt khác KD-Tree không phụ thuộc quá về không gian nên mình nghĩ sẽ tố ưu hơn (theo mình biết thì KD sẽ tìm median của 1 tập hợp điểm rồi chia vùng)

@lds8455 8 ай бұрын

tuy nhiên mình nghĩ đa số trường hợp ứng dụng thực tế o(n^2) là đủ, các phần mềm còn nhiều cách tối ưu hơn là làm thuật toán, như phân vùng gpu để xử lí song song,...

@lds8455 8 ай бұрын

github.com/shawnchin/kd3 mình thấy link này rất hay

@quyphanang6354 8 ай бұрын

@@lds8455 cảm ơn bạn