Hello! I'm currently trying to put together a BSP/PVS engine, but I'm facing some wicked problems, and I really hopes someone has some answers... #1 problem: When creating the BSP tree from a set of convex polygons (I'm not using same approach as Quake (no brushes, no .MAP files etc)) I loses a lot of precision.... Most simple levels compile without any problems, but as soon as things get more advanced the program crashes or illegal polygons are created. I'm sure it's a problem with the precision - but both when the episilon value is very small and when it is quite large, the problems occur (different problems, though). I'm really lost And I don't know how to do. So what I'd like to know is: How are that problem usually solved? What is the best way to keep precision high? Any articles which looks at how to actually implement BSP/PVS, and not just cover the theory? #2 problem: This is when determining the PVS of a leaf (to find out whether a portal is visible from another portal) - Currently I creates a "bounding cylinder" from the first portal to the last, and then checks if all the other portals between them are touching the cylinder... It works fine, buts how is it done the real way? -- Rasmus Neckelmann Edited by - kadaf on July 25, 2001 3:36:21 PM

The precision problem would not be solved if you use a more precise math lib. You will have to create algorithms that are "robust" in that sense that they are able to detect precision problems and avoid it.
To compare double values, introduce a constant EPSILON. Instead of checking equality between to double d1 and d2 with:
if (d1 == d2)
use
if (fabs(d1 - d2) < EPSILON)
This method avoids most equality precision problems.
When you cut a polygon, you will have to be aware of all degenerated cases (polygon on the clipping plane, one edge of the polygone is on the plane, etc ...) and choose an arbitrary solution. For an example, in my BSP compiler I choose to treat all polygon that are on the clipping plane as back-side polygons.

To compute PVS visibilty in a more precise way, you can use edges of both portals to compute a set of plans that define the visibility area.

If you don''t use brushes, how do you know if a "portal" is in front of a wall or is a real "transparent" portal ?
Is your PVS determination time consumming ? (compared to the pvs utility of Quake - mine is sloooow).

Bye,


Orcan
http://www.aracknea.net
"The reasonable man adapts himself to the world;
the unreasonable man persists to adapt the world to himself.
Therefore, all progress depends on the unreasonable."
George Bernard Shaw

I''m already using an epsilon value when comparing doubles, the problem for me is to pick a perfect epsilon value... THAT problem I solved earlier today - I examined the QBSP source, and found out that the ID guys use two different epsilon values: One for testing if something is on a plane, and another for comparing two numbers. I can see that solves some of my problems (the epsilon value should be smaller when comparing). ... But my BSP is still messed up You''re right in the fact that I should try to make everything 100% robust - But I think my code is quite robust, it takes care of all special cases I could come up with.... The real problem is when too small polygons are created and they conflict with the epsilon...

>>"To compute PVS visibilty in a more precise way, you can use edges of both portals to compute a set of plans that define the visibility area."

Yeah, that also appeared to me as the most logical approach. But what happens when one portal is 3 sided and the other one is 5 sided?

>>"If you don''t use brushes, how do you know if a "portal" is in front of a wall or is a real "transparent" portal ?"

Hmm, I''m not exactly sure on what you means (In fact, I don''t know what a brush is! . When I want to look for portals, I first define a solid block for each leaf - then I finds out which leaves are touching each other (one of the polygons in their "solid block" are coplanar with a polygon in the other leaf''s "solid block") Then I simply defines the portal as the area shared by the two polygons. It works perferctly, but, again, there''s probably a lot smarter way of doing it....

>>"Is your PVS determination time consumming ?"
Don''t know . As said earlier, only simple levels compile probably, and THEY runs through very fast. I don''t know about larger levels...

I didn''t have such a problem with small polygons. I should admit that all my polygons where significantly greater than the EPSLION value.

>> But what happens when one portal is 3 sided and the other one is 5 sided?
If you have two portals A and B, plans will be build with one edge of A and one vertex of B, and with one edge of B and one vertex of A.
So for each edge of A (or B) you have to find the "best" point of B (or A) to build a plan (ie. a point so as the plan don''t cut A or B). One way to do that is to project the portal on their midplane (the plane between A and B) and to choose a point of B that is on the "outside" of the A edge (is that understable ? ... i''m not sure) "outside" means the side where there are no other A vertex).
On a small picture it''s obvious, but quite difficult to explain with words.

Your method to look for portal seems to be time consumming. Under the constraint of using brushes (convex 3d area) you can create portals during BSP computation (at first I used a method similar to yours (I think) to retrieve portals after BSP computation - but after some nights trying to improve the speed, I looked QBSP Carmack code and discover why they are using brushes ).

Since I wrote the previous post, I''ve decided to rewrite everything, trying to make everything AS MUCH LIKE QBSP/etc as POSSIBLE (limited by my inferior programming skills, ofcourse )

Unfortunately when using brushes from .MAP files I also has to look at CSG which is a pain But, hey, nothing is easy.

I understands the stuff you explained on portals - I''ll come to coding that soon. I think.

Btw, I really think that Carmack & Co are doing some kind of bizarre black magic to speed up their code...

Thank you for your help.

I''m sure that ID signed up a contract with obscur forces to produce such a good code ) - in fact no, they just are really good coder - and we''re just learning (perhaps one day ...)

So, to speak more seriously, you don''t have to CSG brushes. If you do, it''s better because it reduces polygon splitting and the number of portals (that''s very important: if you''ve got less portals, PVS computation is faster).

I''m currently having some trouble with CSG due to difficult cases to solve. If you look at ID''s code, you will see that they have a really good data structure where you can directly access surfaces from plans, fragments form surfaces and so one. This is one reason of the efficiency of their bsp compilator. I don''t have such a data structure but my BSP compilator is still efficient. The problem is in PVS computation. I implemented quite the same algorithm as ID''s one (I did the same as you: throw my slow code, read the Master''s ideas and rewrite entirely my code ... and it''s still slower. I''m sure I forgot some "black magic" optimisation, as you said .


To be continued ... (after my vacations )

Orcan
http://www.aracknea.net
"The reasonable man adapts himself to the world;
the unreasonable man persists to adapt the world to himself.
Therefore, all progress depends on the unreasonable."
George Bernard Shaw

Ahh. Right now I''m a very happy guy! I''ve just finished the first prototype of a level compiler and it WORKS (ok, it''s not fully tested, I''ll do that later).
I did the PVS thing you suggested and it is really efficient - the main speed problem is the CSG part: It works perfectly, but it''s extremely (EXTREMELY) slow. Even the simplest level (4 wall brushes, 1 floor brush, and 1 ceiling brush) takes about 3 seconds to CSG - then try to imagine how long time it takes on larger levels. But it WORKS, and that''s the main point, right?

You''re right about it is important to have a good data structure - but it can be quite difficult to implement such a thing, you really has to keep your tongue straight in your mouth, otherwise you''ll slam your head right into a wall, and realize everything you''ve written is useless! Buuut until now I''m very happy with my code.

Now, I''ll look at radiosity, as the simple raytraced lightmaps I''m using now looks kindof boring..

Later.