sponsors gamedev.net search:

Tolerance control We will only discuss the primary situations here: 1.Function CalculateSide: In this function, when we test point PT against plane PN, we use the following formula: F= PT.x*PN.A+PT.y*PN.B+PT.z*PN.C+PN.D; //we use Ax+By+Cz+D=0 as the plane's equation switch (F) { case > BSP_TOLERANCE: return point is on positive side; case < BSP_TOLERANCE return point is on negative side; default: return point is on the plane; } After a great deal of experimentation we found that a BSP_TOLERANCE value of 1e-3 provides the best trade-off in our engine. (In our modelling, we treat 1 worldspace unit as 1 meter in the real world). 2. Function TriangleIntersectPolygon: You can never trust the result of your clip function! See the image to the left. After triangle 1 clips the large portal, it seems correct to the casual observer, but if you zoom in the green circle you will find they don't match! The image below illustrates what will happen if we don't use any tolerance control: So, without tolerance control, the function will think triangle 2 intersects portal 1. Then when you use the plane of the triangle 2 to clip portal 1, you will make part of portal 1 valid as shown in figure 1, the yellow portal at the bottom. In our algorithm, we regard the triangle and polygon as intersecting only when their intersection line segament exceeds a certain degree (i.e. BSP_TOLERANCE). You can use your own methods to do this test, and you may find other situations you need to handle, but it is not difficult once you know what you really want. Last minute optimization After generating portals, you may still get a few portals thant you don't want. The obvious ones are those portals on the walls. During the automatic generation process we don't handle this problem, since it seems better to handle it at a later stage. You also need to add some other rules to automatically eliminate obvious redundant portals generated by various errors. In our implementation we use an elimination process following the genneration process to check those portals against all the rules we have defined. Another optimization we could add is to optimize the shape of the portal polygon. We should at least merge adjacent portals which have the same connection attribute and can form a single convex polygon. If the portal polygon has too many edges, you might prefer to use a simple shape such as a quadrangle to approximate the portal shape. This will increase the efficiency of rendering process. Conclusion To generate perfect portals in any environment is a very difficult problem (and is often impossible). However our goal was to make this process acceptable and save our artists' time as much as possible, which is a more reasonable goal. The quality of the models comprising the scene and the quality of the BSP tree will heavily affect the quality of the portals generated by this method. 3dsmax is not high precision software - we will always find some trivial triangles the artists' work (i.e. those triangles not worth rendering). BSP generation can also create this kind of triangle if you don't handle it carefully. So further improvements can be made in these areas; you can add a preprocessing step to optimize these triangles - elimiating them or merging them with other triangles before starting the portal generation process. Appendix Here are some screenshots from our map editor. All models were made by 3dsmax. If you have any questions or you have got some nice ideas to improve this algorithm, feel free to contact us. Huling LiZhenxiao

Contents   Introduction   A Very Simple Example   Tolerance Control   Printable version   Discuss this article