News | Forum | People | FAQ | Links | Search | Register | Log in
GL_POLYGON And Triangulation - Q1
(Since I wasn't outright kicked from the forums last time I asked something technical, I'm assuming this is the right place. Apologies if it isn't.)

In order to speed things up with my vanilla Q1 port to OpenGL ES, I decided to implement the rendering of GL_POLYGON primitives as GL_TRIANGLE_FAN. To that effect, I created a GL_Triangulate() function to build an index list; however, all that function does is triangle-fanning (for now).

The thing is, in all the (arguably few) tests I've been doing with the original ID1 pakfiles (not counting the mission packs) I haven't found any evidence of polygons with more than 5 vertices in them, be in brushes or alias models. Also, they all *seem* to be convex; I haven't yet found any visual distortions caused by triangle fanning my polygons in the engine. Which is too odd for my liking; I still think I'm missing something important here.

Should I actually start thinking on implementing a for-real triangulation algorithm for these cases, or am I worrying too much? As engine and map modders, what has been your experience so far?
Modding Thread Or Engine Thread?? 
 
 
You can feed the exact same data into GL_TRIANGLE_FAN as you feed into GL_POLYGON; there's no need to do any conversion.

You can actually go ahead and take a vanilla Q1 codebase, change glBegin (GL_POLYGON) to glBegin (GL_TRIANGLE_FAN), making no other change whatsoever, and it will render the same.

The difference is if you're using glPolygonMode (..., GL_LINE) - GL_POLYGON will give you an outlined polygon; GL_TRIANGLE_FAN will outline each triangle composing the fan.

Aside from this, both GL_POLYGON and GL_TRIANGLE_FAN are also equivalent to GL_QUADS provided 4 verts are used.

There may also be invariance issues in the specs, but this should only arise if you're drawing co-planar polygons with the same verts but different primitive types.

Brush model polygons are allowed to have up to 64 vertices and that limit is allowed/enforced by the QBSP tool. So you'd better allow the same limit, otherwise at some point in time you will come across a map that breaks your observed limit of 5.

Modified QBSPs might bump that limit. Basically what I'm saying is that it's wiser to not design around a specific finite limit.

Brush model polygons are IIRC guaranteed to be convex.

Indexing for a triangle fan is 0|1|2, 0|2|3, 0|3|4, 0|4|5, etc. Number of triangles is numverts - 2. Number of indices is (numverts - 2) * 3.

Alias models are composed of multiple strips or fans. I posted code over 6 years ago for converting the original MDL data to something suitable for use with vertex arrays, which handles each MDL in a single draw call, and which should work well with ES. It's still available on InsideQC here: http://forums.insideqc.com/viewtopic.php?f=12&t=1931 and might be a good starting point.

Indexing for a strip is 0|1|2, 1|3|2, 2|3|4, 3|5|4, etc. There are other valid patterns; the observables are that the triangle winding order flips for each new triangle, that each triangle reuses two indices from the prior triangle and adds one new one, and that each triangle uses 3 consecutive verts. Number of triangles and number of indices are the same as for a fan.

I'm not sure about ES but in desktop GL the optimal path is glDrawElements (GL_TRIANGLES, ..., preferring 16-bit indices (for double the post-transform vertex cache size). 8-bit indices are unlikely to be supported in hardware so don't use them. Stripping and degenerate triangles are 1998-era techniques and should be avoided on any GL 2.0/D3D9 + hardware. Primitive restart is about 50/50 if you have the hardware support. glDrawElements with indices is going to be faster than glMultiDrawArrays without indices. If you have dynamic data it might be preferable to use client-side arrays than updating a buffer object. Unless you're using glDrawElements you don't have a post-transform vertex cache - at all. Depending on what type of data you're drawing, this may or may not be a big deal. 
Shambler 
Engine thread. 
Scrub That - Should Go In Coding Help 
engine thread is about existing engines i guess 
All BSP Polygons Are Convex 
It's part of the nature of the BSP format; spatial partitioning can only be done in a binary way when all spatial representations (brushes and polygons) are convex.

All points inside of a convex space can be reached by a straight line. This is where the "binary" in "binary space partition" comes from; either the whole area should be considered, or none of it should.

The empty/non-solid space in a BSP is also like this, and that's what makes the visibility preprocessing possible. Empty space is composed of several empty convex areas connected to each other, and the visibility preprocessing determines how far can a straight line go through all of them. 
You must be logged in to post in this thread.
Website copyright © 2002-2024 John Fitzgibbons. All posts are copyright their respective authors.