[질문] 배열로 online bvh 만들고 싶은데 노드 구조 어떻게 짬

[longZam(tmddnr305)]

https://github.com/longZam/DataStructure/blob/main/src%2FDataStructure%2FBVH.cs

DataStructure/src/DataStructure/BVH.cs at main · longZam/DataStructure

노드 구조체에 포인터 느낌으로 left right 인덱스 적어놓고 삽입 순서대로 배열에 집어넣고 있음. 삭제 구현하려는데 인덱스 섞고 섞고 돌리고 섞다보니 오류랑 함께 머리 터질 거 같음. 이리 짜는게 맞는건지 몰루

내가 자료를 못 찾는건지 모르겠는데 동적인 bvh는 영 찾아지질 않음

- dc official App

[익명(59.22)]

lbvh는 특성상 삭제 딱히 생각안하는 레후 ㅇㅅㅇ 실시간 렌더링할때 아주 빠르게 만들고 버리고 반복하는 용도라 실용적으로 삭제는 크게 의미없지 싶은데

[익명(59.22)]

그 뭐냐 삭제나 그런거 고려하는 방법론은 따로 있을건데 기억이 안나네

[익명(59.22)]

지금 네가 하는 짓 자체는 intrusive tree 만드는거에 가까운데 사실 그래 메모리상에 붙어있기만 해도 캐시히트에 도움되는건 맞아서 굳이 인덱스 생각 안하고 포인터만 생각해도 됨 lbvh 트리에 쓰는건 그 ps하는 애들이 세그트리 배열에 말아넣는 그런 감성이고

[longZam(tmddnr305)]

렌더링에 쓰려는 건 아니고 게임 물리학 같이 동적인 환경에다 쓰려는디 이런데에도 LBVH 쓰나

[longZam(tmddnr305)]

배열 써본 건 저번에 동적 할당에 포인터 연결하는 식으로 썼다가 브루트포스보다 느려터져서 유기한거라

[익명(211.246)]

물리엔진 오픈소스 까보자

[longZam(tmddnr305)]

[익명(59.22)]

브루트포스보다 느린건 글쎄 N이 너무 작았거나 다른데가 박살났거나 게임엔진 충돌판정 그런쪽은 잘 모르는데 box2d << 얘들이 오픈소스에 문서화 잘 해놓고 자료 많은 편이라 쟤네가 먼 짓 해놓았는지 참고하면 될 듯

[익명(59.22)]

나도 옛날에 손구현 햿을때 더 느리게 나오길래 ㅈㄴ 고민했었는데 알고보니까 바운딩박스 합치는 로직에 버그 있어서 운지했던거였음

[longZam(tmddnr305)]

[longZam(tmddnr305)]

순회 루프 수 보니까 N이 아무리 커도 N보다 한 20% 작은 수준이던데 함 확인해봐야긋다 - dc App

[ellipse(orbitalinclination)]

https://developer.nvidia.com/blog/thinking-parallel-part-iii-tree-construction-gpu/
구조상
안될 건 없는데 삭제는 안해봐서 모르겠음.
이거 구현하는거 꽤 어려움

[longZam(tmddnr305)]

[ellipse(orbitalinclination)]

직접 구현해봤는데 C++, 8코어 CPU, 10000개 바운딩 박스 기준 2밀리초 내 빌드 가능해서 삭제 없이 트리 새로 만들어도 됨. 깃허브에 예제도 많음