[DiscordArchive] I decided to start by trying to implement it for vmaps (I guess it's harder than grid maps) since th
[DiscordArchive] I decided to start by trying to implement it for vmaps (I guess it's harder than grid maps) since th
Original source
I decided to start by trying to implement it for vmaps (I guess it's harder than grid maps) since the original issue occurred in a dungeon, and I think vmaps are currently the only option left.
Today, I learned that vmaps use the Bounding Interval Hierarchy (BIH) data structure. It's a type of tree optimized for ray tracing.
The first challenge is finding all the required triangles.
I initially hoped that when using the intersectRay function, it would traverse the tree and visit nearby triangles. Sometimes, it works that way, but other times, it doesn’t (I visualized two scenarios of triangles traversal).
So, this approach is not a reliable way to find all the triangles we are interested in.
However, what it does well is finding a single triangle.
Because of this, I was thinking of building a Triangle Adjacency List when creating the vmaps group model.
As a result, if I have a single triangle, I could efficiently find its neighbors.
But I’m unsure if this approach would work and how much additional RAM would it require.
Also which triangles should we consider? Only those within the sphere's radius, or just neighbors of the hit by ray triangle?
![[Image: Screenshot_2025-02-21_at_21.55.15.png?ex...af81a5085&]](https://cdn.discordapp.com/attachments/284323424032129024/1342607489245511733/Screenshot_2025-02-21_at_21.55.15.png?ex=690c68e9&is=690b1769&hm=d97f70fcf72e4c1074eb02e2b44b298e24e15572496051db26ae2fbaf81a5085&)
![[Image: Screenshot_2025-02-21_at_21.58.12.png?ex...dacffa4cd&]](https://cdn.discordapp.com/attachments/284323424032129024/1342607489618808854/Screenshot_2025-02-21_at_21.58.12.png?ex=690c68e9&is=690b1769&hm=ce82631a080bf05aaf8a9bf1c2d00f9b061ab30f18cea2cfac9af33dacffa4cd&)
rektbyfaith
02-21-2025, 09:22 PM #1Archived author: walkline • Posted: 2025-02-21T21:22:50.022000+00:00
Original source
I decided to start by trying to implement it for vmaps (I guess it's harder than grid maps) since the original issue occurred in a dungeon, and I think vmaps are currently the only option left.
Today, I learned that vmaps use the Bounding Interval Hierarchy (BIH) data structure. It's a type of tree optimized for ray tracing.
The first challenge is finding all the required triangles.
I initially hoped that when using the intersectRay function, it would traverse the tree and visit nearby triangles. Sometimes, it works that way, but other times, it doesn’t (I visualized two scenarios of triangles traversal).
So, this approach is not a reliable way to find all the triangles we are interested in.
However, what it does well is finding a single triangle.
Because of this, I was thinking of building a Triangle Adjacency List when creating the vmaps group model.
As a result, if I have a single triangle, I could efficiently find its neighbors.
But I’m unsure if this approach would work and how much additional RAM would it require.
Also which triangles should we consider? Only those within the sphere's radius, or just neighbors of the hit by ray triangle?
Original source
Are you sure about BIH ? I was remerber that was one of possibility to build Vmap but not used by TC/Mangos framework since many years because it not more precise than another data structure of WoW maps (I don’t remember all details of TC discuss about it. But I’m maybe wrong)
rektbyfaith
02-21-2025, 09:40 PM #2Archived author: Deleted User • Posted: 2025-02-21T21:40:59.344000+00:00
Original source
Are you sure about BIH ? I was remerber that was one of possibility to build Vmap but not used by TC/Mangos framework since many years because it not more precise than another data structure of WoW maps (I don’t remember all details of TC discuss about it. But I’m maybe wrong)
Original source
(nothing said, I’m wrong. I did a quick research and It’s inversed we use BIH but not BSP)
rektbyfaith
02-21-2025, 09:49 PM #3Archived author: Deleted User • Posted: 2025-02-21T21:49:08.717000+00:00
Original source
(nothing said, I’m wrong. I did a quick research and It’s inversed we use BIH but not BSP)
Original source
wtf that's not paint
rektbyfaith
02-21-2025, 10:00 PM #4Archived author: Bench • Posted: 2025-02-21T22:00:19.526000+00:00
Original source
wtf that's not paint
Original source
must be Paint 3D
rektbyfaith
02-21-2025, 10:02 PM #5Archived author: Kitzunu • Posted: 2025-02-21T22:02:14.305000+00:00
Original source
must be Paint 3D
Original source
So I must confess that I'm not very familiar with BIHs, I was hoping that extracting the relevant triangles that might have an intersection would be easy. Hold on let me check with my good friend o3
rektbyfaith
02-21-2025, 10:17 PM #6Archived author: Pursche • Posted: 2025-02-21T22:17:38.350000+00:00
Original source
So I must confess that I'm not very familiar with BIHs, I was hoping that extracting the relevant triangles that might have an intersection would be easy. Hold on let me check with my good friend o3
Original source
ALLEGEDLY, we can do collision resolving (which is the generic term used for trying to place a shape, in this case a sphere, at a position and then have it pushed away so it doesn't clip into geometry) directly against a BIH like this: https://chatgpt.com/share/67b8fc80-2cc8-...02fdfe255f
I bet it would require a bit of adapting to fit with the way the VMAP represents the BIH though.
[Embed: ChatGPT - Sphere BIH Collision Resolve]
Shared via ChatGPT
https://chatgpt.com/share/67b8fc80-2cc8-...02fdfe255f
rektbyfaith
02-21-2025, 10:23 PM #7Archived author: Pursche • Posted: 2025-02-21T22:23:50.936000+00:00
Original source
ALLEGEDLY, we can do collision resolving (which is the generic term used for trying to place a shape, in this case a sphere, at a position and then have it pushed away so it doesn't clip into geometry) directly against a BIH like this: https://chatgpt.com/share/67b8fc80-2cc8-...02fdfe255f
I bet it would require a bit of adapting to fit with the way the VMAP represents the BIH though.
[Embed: ChatGPT - Sphere BIH Collision Resolve]
Shared via ChatGPT
https://chatgpt.com/share/67b8fc80-2cc8-...02fdfe255f
Original source
Pinging <@261790372743610368> for visibility.
rektbyfaith
02-21-2025, 10:24 PM #8Archived author: Pursche • Posted: 2025-02-21T22:24:14.866000+00:00
Original source
Pinging <@261790372743610368> for visibility.
Original source
I think it would be some kind of bruteforce approach. I would prefer an approach that finds the triangle using ray casting and then locates its neighbors. In that case should we search neighbors in sphere radius?
rektbyfaith
02-21-2025, 10:45 PM #9Archived author: walkline • Posted: 2025-02-21T22:45:00.138000+00:00
Original source
I think it would be some kind of bruteforce approach. I would prefer an approach that finds the triangle using ray casting and then locates its neighbors. In that case should we search neighbors in sphere radius?
Original source
But we can't be sure that the triangles we might intersect is adjacent to the one you get from raycasting straight down.
rektbyfaith
02-21-2025, 11:07 PM #10Archived author: Pursche • Posted: 2025-02-21T23:07:56.606000+00:00
Original source
But we can't be sure that the triangles we might intersect is adjacent to the one you get from raycasting straight down.
1 Guest(s)
1 Guest(s)