Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

trzy

Eliminating discontinuities (T-junctions) in BSP?

This topic is 5247 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I''ve asked about this topic here in the past but I''ve never found a sufficient answer and I''ve been sidetracked for the last year or 2 with other unrelated projects. To get to the point: When building a BSP world out of an arbitrary set of polygons (3, 4, or even more vertices), discontinuities result between some of the edges of my software renderer. These are due to T-junctions that are inevitably formed during the polygon splitting process. Is there an easy way of dealing with this? Triangulation won''t solve the problem. Inserting extra vertices at the junctions will fix the problem but determining when this should be done is time consuming. How would a BSP tool (such as id''s tools for Quake 2 and 3 maps) ensure that the resulting polygons for a BSP map do not create discontinuities when rendered? One simple solution I''ve thought of is to arrange the input geometry such that each edge of a polygon only touches at most one other edge (ensuring T-junctions in coplanar polygons cannot occur) and that edges of polygons never touch another polygon without sharing vertices. Perhaps 3D modelling and mapping tools can export such geometry but for arbitrary lists of polygons, these conditions cannot be guaranteed. Do BSP packages simply ignore the issue of discontinuities and assume the input geometry is structured such that they won''t occur no matter what kind of splitting occurs? ---- Bart

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Some years ago I did a contract work job for some engine to fix the T-junction problem for meshes resulting from CSG operations.

If I remember correctly I solved it by first building connectivity information, so that I knew what edges where connected to what other edges etc.

Then you can iterate through all edges to see if there is any edge that doesn''t have its end points at the end points of the neighbor edge. If that is the case, you have a T-Junction.

I solved it by adding a vertex on the other edge as well, sharing the same position. So basically splitting / triangulating the other triangle. But that can also create T-Junctions again, there are some tricky situations. But after handling this they get all fixed.

Anyway, hope this info helped Let me know if you can''t figure it out, then maybe I can see if I can remember exactly what I did

Share this post


Link to post
Share on other sites
quote:
Original post by trzy
How would a BSP tool (such as id's tools for Quake 2 and 3 maps) ensure that the resulting polygons for a BSP map do not create discontinuities when rendered?

Faces in Quake maps have associated plane information. Thus, when you find two coplanar faces that are in opposite directions, it knows there is a potentially junction.

What happens next is actually quite clever. It takes one of the solids. It uses each face on that solid, excluding the one involved in the junction, as a splitter into face on the other solid that was involved in the junction. To be technically accurate, it's not the faces that are the splitters, but rather their associated planes. Since all solids in Quake BSPs are convex, and all planes associated with faces face outward, once the junction face has been split by the other solid, you have two entities. One is a list of faces that constitute a surface, minus the discontinuity. And the other entity is the discontinuity itself. The discontinuity is discarded, and the face list takes the place of the original face. The process is then applied in reverse on the other face with the other solid, although technically there won't be any splits because since one face is smaller than the other it will only work one direction. The reason is does it twice though is because it doesn't know which solid has the smaller junction face, ans which one has the larger.

That is actually the generic algorithm used for all hidden surface removal in the CSG process. The beauty of it is that if there really isn't a junction (even if two faces share a plane it doesn't mean they touch), the math is structured in such a way that it can implicitly detect and handle such circumstances. I recommend you take a look at the tool source code. It's a lot easier to see it in code than to listen to me

However this algorithm is very lazy. It will just start splitting away until the hidden face is removed. This can lead to a huge increase in faces if your geometry is complex. Mappers should be advised to avoid creating junctions whenever possible.

EDIT: Just to add. When you replace one face with a list of faces, all those faces now become part of the solid. It can lead to more junction situations, but since the algorithm is performed on a per-solid, per-face basis, and the faces are updated per-junction, it works iteratively to get rid of them all eventually.

[edited by - Zipster on June 8, 2004 7:32:31 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
I solved it by adding a vertex on the other edge as well, sharing the same position. So basically splitting / triangulating the other triangle. But that can also create T-Junctions again, there are some tricky situations. But after handling this they get all fixed.



This would work. I was thinking of taking this approach but building the connectivity information and then performing the tests would be extremely time consuming. It could be sped up somewhat with some sort of geometric hashing, but it''s still a complicated solution. If all else fails, I''ll probably do this.

quote:
Original post by Anonymous Poster
Faces in Quake maps have associated plane information. Thus, when you find two coplanar faces that are in opposite directions, it knows there is a potentially junction.



Hmm, are you sure we''re talking about the same kind of discontinuities? It sounds like you''re talking about entire polygons in a solid surface disappearing. T-junctions usually occur on faces which are coplanar and facing the _same_ direction, in my experience.



----
Bart

Share this post


Link to post
Share on other sites
quote:
Original post by trzy
Hmm, are you sure we''re talking about the same kind of discontinuities? It sounds like you''re talking about entire polygons in a solid surface disappearing. T-junctions usually occur on faces which are coplanar and facing the _same_ direction, in my experience.

We''re talking about the same thing, just looking at it from a different perspective Here''s a quick little diagram, for reference:


C
-----+------
|
A | B
|

Ok, we have polygons A, B, and C forming a T-junction at ''+''.

The way the split algorithm would work, is it would take the side shared by both A and B, and split the mutually shared side on C. This would cause C to be split, an extra polygon to form, and a vertex to be created at ''+'':


C | D
|
-----+-----
|
A | B
|

The way to think about the algorithm is to only picture two polygons being processed at a time. With a T-junction, the significance would be on either polygon A and C, or polygon B and C, as that is the condition in which a split would occur in polygon C. If polygons A and B were being processed, there wouldn''t be a split.

Once all the splitting is done, a welding algorithm is usually applied so that multiple vertexes that are really close together are merged. This takes care of any final artifacts.

In short, it''s really just a general hidden surface remove algorithm that also solves the problem of T-junctions.

Share this post


Link to post
Share on other sites
quote:
Original post by Zipster
Ok, we have polygons A, B, and C forming a T-junction at ''+''.

The way the split algorithm would work, is it would take the side shared by both A and B, and split the mutually shared side on C. This would cause C to be split, an extra polygon to form, and a vertex to be created at ''+'':



Right, I follow so far. This is definitely what has to occur to eliminate the T-junction. What I don''t understand is how you would detect the presence of the junction to begin with, or how you would perform the BSP splitting process so that they get eliminated automatically.

Since polys A, B, and C are coplanar, there would be no way that polygon C would ever be split by the edge between A and B. Unless you think of splitting planes differently than I do. I create splitting planes by choosing a polygon and then finding the plane it lies in. That becomes the splitting plane. Do you instead make splitting planes out of connecting edges somehow?



----
Bart

Share this post


Link to post
Share on other sites
Another thing you might try is to create a half-edge structure for the scene. It stores each edge along with the next edge in the polygon and its reverse. Edges that don''t have a reverse are boundary edges. A T-junction is basically a "zero" sized hole in the mesh. If you find three boundary edges in a cycle, then you have a hole in the mesh. Fixing the hole is only a matter of inserting another half-edge into the graph.
The disadvantage of this is that you have to convert to and from a half-edge structure. About how many tris. are you working with?

karg

Share this post


Link to post
Share on other sites
quote:
Original post by trzy
Right, I follow so far. This is definitely what has to occur to eliminate the T-junction. What I don't understand is how you would detect the presence of the junction to begin with, or how you would perform the BSP splitting process so that they get eliminated automatically.

The algorithm doesn't really detect T-junctions. Their removal is really just a beneficial byproduct of how the algorithm works.

quote:

Since polys A, B, and C are coplanar, there would be no way that polygon C would ever be split by the edge between A and B. Unless you think of splitting planes differently than I do. I create splitting planes by choosing a polygon and then finding the plane it lies in. That becomes the splitting plane. Do you instead make splitting planes out of connecting edges somehow?

Depends if you're in 2D or 3D. If you want to think of the polygons in 2D, then A and B share an edge, and the splitting plane is created perpendicular to *all* the faces (extending into the Z dimension), but also along the edge. Thus if you're working in two dimensions, you create splitting planes that don't have any corresponding faces. If in 3D, then A, B, and C aren't really polygons, but convex polyhedron. You can think of them as boxes seen from a top-down view in this example. Then A and B share a common face, and the plane this face is on is used to split with. In both cases, the splitting plane extends "out" from the page and is perpendicular to what we need to split.

I really wish I could explain how the algorithm worked to you, but there's so much involved that any poor explanation I provide will only serve to confuse even more. What I can do, though, is give you a link to what is known as Zoner's Half-Life compiler tools. These are basically the compile tools used to build Half-Life BSP maps, which are based off the Quake 1 tools. Source code is provided, and what you want to check out is the HLCSG project. In the file named qcsg.cpp look for the function CSGBrush. It contains the hidden surface removal algorithm, as well as the splitting code. Admittedly, it might be a difficult to understood because the application uses it's own internal data structures, but if you have any questions I can help the best I can. The algorithm can easily be adapted to remove T-junctions (as I just realized that it doesn't automatically do it already). But if you split the adjacent faces as well, it should create the extra vertex.

Although ultimately, if your goal is just to remove T-junctions, I think you'd better stick with calculating connectivity data. Adapting an HSR algorithm is just extra work.

[edited by - Zipster on June 8, 2004 2:21:27 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by trzy
This would work. I was thinking of taking this approach but building the connectivity information and then performing the tests would be extremely time consuming. It could be sped up somewhat with some sort of geometric hashing, but it''s still a complicated solution. If all else fails, I''ll probably do this.


This is the approach I took, and it isn''t really that time consuming. This is how I did it: iterate through all faces, and add each edge from each face to a list (an edge contains the two vertices, and a link to the parent face). You''ll have faceCount*3 edges in the list at the end of this step. The complexity is O(N).

Now sort the edge list using the both edge vertex IDs as sorting rule, so that equivalent edges lie beside each other in the list. Using Quicksort, this step is generally O(N log N).

Finally, iterate through the sorted list, and compare the entries: if you have two equivalent ones next to each other, you have a closed edge. Ignore it. If you have more than two equivalent ones, you have a degenerate edge, which shouldn''t be a problem either (for rendering at least). Single edges without equivalent partners are either open edges, or T-junctions. This step is O(N).

Now that you identified possible candidates, all you have to do is to differentiate between real open edges and T-edges. This is done by a proximity compare of edges connected by at least one vertex: if both line segments are almost parallel, their distance to each other is below some threshold, and theyx share at least one common vertex, then you have a T-junction.

This algorithm is pretty fast, stable, and detects all T-junctions within the threshold limit (ie. it can differentiate between T''s and actual holes). It consumes memory for the edge list, but that shouldn''t be too bad.

Share this post


Link to post
Share on other sites
quote:
Original post by Zipster
If in 3D, then A, B, and C aren''t really polygons, but convex polyhedron. You can think of them as boxes seen from a top-down view in this example. Then A and B share a common face, and the plane this face is on is used to split with. In both cases, the splitting plane extends "out" from the page and is perpendicular to what we need to split.



I think I understand what you''re talking about now. In 3D, you''re picturing each of A, B, C as objects made up of at least 3 polygons (faces), though you only show 2 for A and B respectively and 1 for C. I''m thinking of it as 3 polygons that are all coplanar and facing us directly. The lines are their edges, not faces in a polyhedron.

quote:
These are basically the compile tools used to build Half-Life BSP maps, which are based off the Quake 1 tools. Source code is provided, and what you want to check out is the HLCSG project.



Thanks, I''ll take a look at them!

quote:

Although ultimately, if your goal is just to remove T-junctions, I think you''d better stick with calculating connectivity data. Adapting an HSR algorithm is just extra work.



This is probably what I''ll do. I''m not certain where I want to go with my BSP builder just yet. I''ll probably use it for both a real-time software renderer (in which case T-junction elimination is critical to eliminate cracks between polygons) as well as for a raytracer in which case the T-junctions probably won''t cause any harm at all.

quote:
Original post by Yann L
Now that you identified possible candidates, all you have to do is to differentiate between real open edges and T-edges. This is done by a proximity compare of edges connected by at least one vertex: if both line segments are almost parallel, their distance to each other is below some threshold, and theyx share at least one common vertex, then you have a T-junction.




There''s also one more case to consider, but I guess it''s not really a "T-junction" per se:


+----------------------+
| |
| A |
| |
| |
+----+--------+--------+
| |
| B |
| |
+--------+


That''ll cause a crack in the shared edge. The solution is to add 2 vertices to polygon A and I think with some modifications, your algorithm can handle this as well. I don''t think I''ll be searching for these unless it becomes a real problem.



----
Bart

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!