Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (799)
Games in Android Showcase (235)
games submitted by our members
Games in WIP (865)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  T-Junction Removal in BSP Trees.  (Read 1541 times)
0 Members and 1 Guest are viewing this topic.
Offline Archive
« Posted 2016-07-27 07:11:09 »

Hello, T-Junctions have been a pain for me to fix because I've only found brute force methods which take ages with a BSP tree containing over 10k nodes. Has anyone worked with this issue before and had a solution?

Offline CoDi^R
« Reply #1 - Posted 2016-07-27 10:39:52 »

I don't have practical experience with constructing BSP trees myself, but I think one solution that may work well is to work with edge lists. So, for each edge of every polygon, have some data to identify the vertices which span the edge, and a list of adjacent polygons this edge is shared with.

During BSP construction, splitting one (convex) polygon also means that up to 2 of its edges are split (if the split does not intersect exactly at one of its vertices). If that happens, search for the adjacent polygons which share those edges, and split those too (which means you insert one more vertex on their edge).

Then you "just" need to add/update edge information for the local and adjacent polygons. The local polygon is split in 2, sharing a new edge with each other. For the adjacent polygons, affected edges are subdivided and replaced by 2 new edges.

Robotality - steamworks4j - @code_disaster - codi^r @ #java-gaming
Offline Archive
« Reply #2 - Posted 2016-07-27 15:11:46 »



I will implement your idea if this other idea I had doesnt work. My idea is to "stretch" split polygons over their plane by a fixed epsilon to fill up the cracks. I was thinking about for each vertex, finding the direction towards the polygon's centroid and extrapolating backwards on the 3D line created by that direction by a certain epsilon. What do you think of that?

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CoDi^R
« Reply #3 - Posted 2016-07-27 15:26:25 »

Hm. This may work, but you'll have to try and tune the epsilon carefully. Depending on your geometry, it may cause distortions or z-fighting issues.

Robotality - steamworks4j - @code_disaster - codi^r @ #java-gaming
Offline Archive
« Reply #4 - Posted 2016-07-27 16:05:41 »

Hm. This may work, but you'll have to try and tune the epsilon carefully. Depending on your geometry, it may cause distortions or z-fighting issues.
I dont think that Z-fighting will be an issue since it's a bsp tree and a bsp tree is essentially an advanced painters algorithm

Pages: [1]
  ignore  |  Print  
 
 

 
Riven (145 views)
2019-09-04 15:33:17

hadezbladez (4701 views)
2018-11-16 13:46:03

hadezbladez (1724 views)
2018-11-16 13:41:33

hadezbladez (4952 views)
2018-11-16 13:35:35

hadezbladez (986 views)
2018-11-16 13:32:03

EgonOlsen (4299 views)
2018-06-10 19:43:48

EgonOlsen (5107 views)
2018-06-10 19:43:44

EgonOlsen (2903 views)
2018-06-10 19:43:20

DesertCoockie (3828 views)
2018-05-13 18:23:11

nelsongames (4201 views)
2018-04-24 18:15:36
Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!