why not look at the quake 3 source code to see how it tesselates bezier patches? 

My raw understanding of the patches (and C/C++) is very limited, but I will likely have to do that. Right now I'm working on rendering multi-patch faces without any tessellation, just the reference points. I can render single-patch faces, but I'm working on how to extract the 9 reference points from the face, and making an individual patch out of that when there is more than one patch in the face.

Once that is done and references are rendering correctly, the only piece of code that will need changing to have beziers 100% working will be the method that takes those control points and fills the patches vertex and triangle strip data. Getting closer. 

well if your problem is the theory behind it, maybe i can help a little bit.

First, quake3 patches use bezier curves, which are parametric equations. This means that to generate a point on the surface you need to input a parameter. The parameter can go from zero to one, and as it moves from zero to one the point generated moves along the curve from the start to the end. The parameter is usually called "t".

Second, quake3 patches use quadratic curves, not cubic curves (which are more common i think), so that means they have 3 points to define a curve instead of 4. The three points are startpoint, control point, endpoint.

Third, how to solve a quadratic curve? First, look at this picture:

http://upload.wikimedia.org/wikipedia/commons/2/2d/Bezier_2_big.gif

P0,P1, and P2 are the three control points. Green stuff is intermediate calculations, and the red line is the final curve.

So to solve for the black point (a point on teh curve) you first find a point on the line from p0 to p1, call that A, then find a point on P1 to p2, call that B, then find a point on the (green) line from A to B, that point is your solution (black dot.) In all three cases, when you "find a point" you are finding the point using t -- if t is 0.5, find the halfway point. if t is 0.25, find the point 1 quarter of the way from the first point to the second point.

Okay, assuming you understand all that... the quake 3 patches are 2-dimentional surfaces, not just single lines. So instead of 3 points, they have 9. To solve it you need to do multiple tasks like the one above (solving a simple 3-point curve.) Since it's two-dimensional, to find a point you need two parameters instead of 1 -- instead of t, you need s & t.

Imagine the 9 points are arranged in a 3x3 grid. First row is 1,2,3, second row is 4,5,6, last row is 7,8,9. First solve three horizontal curves using s -- 123 is the first curve, 456 is the second curve, and 789 is the third. Each uses s as the input parameter. Each gives you one new point -- A,B,C. Now solve curve ABC with parameter t. Now you have found a point!

Okay, so now you can find any point on the surface of the patch using s,t coordinates. How to render a patch? What you do is divide the patch into a grid of quads. The vertexes of the quads are determined by inputting s & t. If you want N * M quads, you need (N+1) * (M+1) points. The first point is 0,0 and the last point is 1,1. Intermediate points are evenly spaced in between. 

That helped me so much, that using that info, some time and study, and some patience I have perfected parsing, tessellating, and rendering (with textures!) Quake 3's bezier patches. Huzzah!

http://imgur.com/a/i470V

Textures that are provided by shaders in Quake 3 aren't working for obvious reasons. I also need to debug lightmap ripping/application, but those are pretty minor issues. Unity's realtime and baked lights look better anyway.

Thanks a ton. 

Here is a link to the github of the project. It's free to do with as you please.

https://github.com/mikezila/uQuake

Don't want to keep mucking up the coding help thread, so if/when I make videos and take screenshots to show it off I'll probably make a new thread. 

Nice, you got it working! Glad to help. 

Is this a quake 1 engine?? 

The engine itself is Unity3D, which is a freely available engine that you can use for almost anything. I've built a reader for .bsp files, and a "renderer" that creates the level as Unity gameobjects. It's not a "true" bsp engine because only the geometry is used, things like leafs, nodes, the bsp tree itself, and vis data is not used. Unity handles those things on its own at runtime.

Right now it only supports Quake 3 maps, but I want very much to add support for Quake 1 maps. Once I get lightmaps working on Quake 3 maps I'll set to support Quake 1 maps. My original goal was actually Quake 1 maps, but extracting the geometry from them is a little more complex than Quake 3 maps, so I did this first as a warm up and to see if it was possible. 

nice work figuring it out! 

Alrighty, Quake 3 lightmap support is done. The colors aren't as vibrant as they should be because Unity's RGB lightmap shaders are lame, but the data is ripped and applied correctly. I also replace shader-modified textures with non-shader versions at runtime. Like on the strange flesh-spire and lava here.

http://imgur.com/tO3SSUP

But like the title says, it's time for Quake 1 support. The most comprehensive guide to the Q1 .bsp specs is here:

http://www.gamers.org/dEngine/quake/spec/quake-spec34/qkspec_4.htm#CBSPG

Is this still current? It's really old, and says it matches the .bsp version used in Quake shareware. Is there a more detailed or updated guide on the .bsps produced by modern compilers? 

q3 has overbrighting. the lightmap scales between logical rgb values of 0 to 4 rather than 0 to 1. The lazy way to deal with that is to just multiply the values by 4 and clamp to 255. The real way to deal with it is to scale your vertex colours by 4 instead, or to put the same scaling in glsl.
This nonsense allows bright areas to oversaturate textures, thus textures which are grey colours can brighten up to become more white in bright areas.
Software vanilla Quake has a similar feature. vanilla glquake just clamps.

Check some engine's bspfile.h, like that markv_bsp2 zip I hacked together recently if you're after bsp2 support. Otherwise bsp29 is still the same bsp29 that's documented in your link. 

Was studying the BSP29 document some, and I realize that nowhere is there a list of triangles for any of the faces. Is there something I'm not seeing, or does it fall to me to figure that out using sorcery? 

Works like that. It's the .map file that has that info and that is then compiled into a scrambled file? 

When I was reading the Q3 .bsp into Unity my process was like this.

Take a face. A face has a list of vertices, and a list of triangle indexes into that faces vertex list. So to make a mesh out of a face all I had to do was make a mesh, and set it's vertex and triangle arrays to the data I pulled out of the face. Each vertex object has data about it's position, texture coords, color, and lightmap coords. The whole process was actually pretty slick.

In Quake 1 it seems like every surface has a list of edges, and each edge has two vertices. Using some simple rules and maths getting a list of verts and the texture mapping info for those verts doesn't seem too hard. So I make a mesh and add the verts and texture coords. But how do I form triangles? In Quake 3 that data was provided for me, but here it's not.

Is each face only going to be three verts? That doesn't seem right. Are the faces always going to specify their verts in the order needed to form triangles out of every three verts? 

Noesis can load bsp files, you might be able to find well readable code in there. http://oasis.xentax.com 

you have to triangulate it yourself, i think. All the faces are convex polygons, so it shouldn't be too hard to triangulate them. Only down side is there may be some degenerate triangles due to extra verts added for tjunctions. I guess you should keep these because otherwise you may get visible cracks. 

Dang, really? The renderer back in the day mashed out the tris for the whole map each time it loaded? That's unreal. 

actually the software renderer directly rasterized polygons, so it never needed triangles. Later opengl versions would use GL_POLYGON primitive type, so they didn't need triangles either. 

I guess since every poly is going to be convex I can just ham-hand it and make tris using a pivot point and casting to each other vertex. 0-1-2, 0-2-3, 0-3-4, etc. It's the least efficient way possible, but I guess it's sure to cover the full face. Come to think of it when I r_showtris in some engines it looks like that's what it's doing. 

How is this "least efficient"? I don't see a more efficient way to generate triangles from convex polygons. 

Honestly I just assumed it was the least efficient/elegant way since it was the first solution I thought of. Probably because it's simple. I just figured there'd be a more complex, "better" way. 

each edge has two sides. pick one vertex from each edge based upon the side of the edge you're using. side is determined by whether the edge index is negative or not. this will get you a convex polygon (aka: a triangle fan). more modern renderers can trivially generate triangles from that.
the whole thing is just triangle fans. software kept it like that because its easier to clip+frustum cull, which is part of how it managed to avoid all overdraw from bsps.
remember, these face polygons are never concave. there's no holes or anything. its pretty trivial because of that. 

Strictly speaking there may be an inefficiency there in rendering>/i> those triangle fans. According to a half-remembered article I read a while back, long, thin triangles are slightly less efficient to render than evenly proportioned ones. I'd hazard a guess that's due to better cache-coherence properties of the latter.

I wouldn't worry about it though, primarily because it's a tiny difference. Also because almost all the polygons in quake maps will be 6 sides or less, so there's not a great deal of difference between the best and worst choices. 

This is where I've had the nagging thought that I'll bet modern engines could just create large, texture sorted buckets of triangles representing the entire level and just throw it at the video card. Odds are that on even a mid-level machine, it would run fine.

Keep the BSP for collision checks and line-of-sight stuff, but in terms of raw rendering I wonder if parsing through the VIS data is actually a detriment these days. 

Brute forcing winning over the elegance of a BSP traversal algorithm always felt like an aesthetic unfairness to me.

Not that I mind scraping the vis times.