I like to understand the basics of BSP tree rendering.

I am looking to the doom source code also to understand the simplest form from the beginning.

Maybe i can write a win32 program with drawing pixels and lines to see how it works.

I dont know how the doom code works just by looking at it, i cant even find the part where they draw a pixel.

Also intrested in how to implement your own BSP tree in dirextX,

how do i use the vertexbuffer for that ?

Do you need to replace all vertices from the vertex buffer for every frame ?, aint that slow ?

I need if for unlimited lights, in the fixed pipeline i have only 8 light sources available.

I also dont understand how you make your own pipeline ?, how does it work in combination with a video card ?,

i dont wanto code asm or shader language or something : C++ only, is it possible ?
 

Anyone has undestandable info about the simplest BSP tree or non fixed pipeline ?

thanks

7 minutes ago, the incredible smoker said:

BSP tree in dirextX

What has a BSP tree to do with DirectX? Or stated differently, how would it differ from other applications like ray tracing or database searches?

To learn about BSP in Doom, read the chapter in Michael Abrashs Black Book, which is online everywhere.

But i did not find the source code and hope it's ok to attach it here.

(It's OpenGL or software rasterizer but i guess it still compiles)

BSP has nothing to do with graphics API or shaders anyways. Doom uses BSP for front to back sorted rendering of level geometry and frustum culling. The idea is to generate small chunks of geometry by cutting space in two halfs recursively. Those chinks are static and ther is no need to touch vertexbuffers at runtime.

Edit: Why do you think you need BSP nowadays?

ddjbsp2.zip

Hi, i like to know how i can get unlimited lights in my DX engine, now i only have 8 lights.

This is a good reason to have some BSP tree without fixed pipeline ?, or has pipeline nothing to do with BSP ?

I also making hardware, i bought a 320x240 full color LCD display, i dont know if it will be fast enough framerate on these 50MHz chips ?

Before writing code for hardware i go test on win32 application, saves a lot of re-flashing the chip.

Basic stuff is also nice to know for this reason.

So i have 2 reasons : PC game ( DX9 ) and full color hardware LCD display drawing lines.

BSP trees are mostly used for the initial partitioning (typically done beforehand as a preprocess step), or runtime for visibility or collision detection.  Your vertices don't change during rendering, you just have a set of data per leaf of the BSP that, when determined to be visible, is pushed to your rendering system.  So in answer to your question, BSP has nothing to do with the rendering pipeline.  It's simply a way of partitioning the world into more manageable spaces, and how to determine spatial relationships between these spaces.  If you look at engines that used BSP like Quake, it also used during preprocessing to determine if the world was closed or had gaps, and at runtime to get correct front2back and back2front sorting of faces, and to do collision detection by checking if you're going from an empty area to a solid area or vice versa.

7 minutes ago, the incredible smoker said:

Hi, i like to know how i can get unlimited lights in my DX engine, now i only have 8 lights.

You can lift that limitation in two ways:

1. Do per pixel shading with shaders (the modern approach  )

2. Implement your own vertex lighting and submit lit vertex colors to DX.

If you still want hardware Lighting from fixed function GPU for more than 8 lights, you can make sure any triangle is lit by only 8 at max and change lights accordingly while rendering. Partititioning geometry will be usefull for this, but you can use any method you want. BSP is static, so it may not be the best choice here.

Doom / Quake had hidden surface removal (HSR) on top of BSP sorted drawing order to reduce overdraw (can achieve zero overdraw for static scenes). The combination of those things made BSP so attractive and efficient back the days. But GPU can't do HSR. They still profit from front to back order due to early Z, but a less restricted and more flexible way of sorting makes more sense for GPU.

I recommend you read the chapters, it's interesting anyways, and also the chapters about baked radiosity (with that 8 dynamic lights should suffice!)

Hi, thanks for the reply`s all.

@ Joe : with the shaders ?, do i need to program shader language or asm ?

If i go change vertex colors, and dont add lighting in the vertices, is it the same as with default pipeline ?, very intresting btw.

Is HSR an array with a bit for each pixel ?, sounds logical, if there is enough memory, i dont understand how else you can do that.

@xycsiscys : sounds intresing that you can use collision detection also with bsp, is it very different then the checkintersect function from directx ?

What i also dont understand about the doom rendering, dont it takes a lot of math functions ?, i guess not since it was playable on 486 computers.

Dont you need at least sinus and cosinus for the rotation ?

So i made this win32 app showing a square with a line, if i make it bigger or smaller it looks like it is going further or closer,

how do i implement Z position without heavey math ?,

and what about rotating the camera ( i,m not rotating the square yet, need the positioning first ).

Ofcourse i also need to rotate the square, how would i do all that without calling math functions ?

thanks

Just now, the incredible smoker said:

Hi, thanks for the reply`s all.

 

@ Joe : with the shaders ?, do i need to program shader language or asm ?

If i go change vertex colors, and dont add lighting in the vertices, is it the same as with default pipeline ?, very intresting btw.

Is HSR an array with a bit for each pixel ?, sounds logical, if there is enough memory, i dont understand how else you can do that.

 

@xycsiscys : sounds intresing that you can use collision detection also with bsp, is it very different then the checkintersect function from directx ?

 

What i also dont understand about the doom rendering, dont it takes a lot of math functions ?, i guess not since it was playable on 486 computers.

Dont you need at least sinus and cosinus for the rotation ?

 

So i made this win32 app showing a square with a line, if i make it bigger or smaller it looks like it is going further or closer,

how do i implement Z position without heavey math ?, so that it would be correct.

and what about rotating the camera ( i,m not rotating the square yet, need the positioning first ).

Ofcourse i also need to rotate the square, how would i do all that without calling math functions ?

thanks

 

Math is necessary its just a matter of how much.  What is your goal exactly?

a software renderer like the original wolfenstein?

a software renderer like in doom?

a software renderer for wireframe rendering?

a hardware accelerated wireframe renderer?

a hardware accelerated game like halflife?

depending on what exactly you want to do the advice will be different.

4 hours ago, the incredible smoker said:

@ Joe : with the shaders ?, do i need to program shader language or asm ?

If i go change vertex colors, and dont add lighting in the vertices, is it the same as with default pipeline ?, very intresting btw.

Is HSR an array with a bit for each pixel ?, sounds logical, if there is enough memory, i dont understand how else you can do that.

In DirectX you code shaders in HLSL which is like C. DirectX translates this to bytecode, and the driver to ASM (each vendor and GPU has different instruction set). There are different shaders to process vertices or pixels, so a minimal vertex shader transforms vertices by madel and camera matrices, and a typical pixel shader has access to interpolated values (UVs, vertex colors, custom data) and ouputs final color for each pixel. You can still do lighting in the vertex shader like fixed function pipeline did, but any GPU is poweful enough to do it per pixel.

I you are happy with vertex lighting, yes you can do it on CPU yourself using vertex colors to get around the 8 lights limit.

HSR per pixel is what GPUs do using Z-Buffer. Software rasterizer (Quake / Doom) can do it e.g. per span (a scanline from a triangle), which is much less work than per pixel. But GPUs have lots of parallel processing power and work efficient HSR algorithms are hard to parallelize. Also triangles baecame much smaller so ZBuffer wins on GPU. 

Using GPUs you don't care about fine grained HSR, but you may want to avoid rendering one half of the level if it is hidden behind a wall. Here BSP can be used in combination with a precomputed Potentially Visible Set (PVS): Each cell of the BSP knows what other cells may be visible if the camera is inside. This idea works also with other data structures but is limited to static geometry (and it's hard, so see how far you can get without a need for such things).

4 hours ago, the incredible smoker said:

Dont you need at least sinus and cosinus for the rotation ?

No. Only if you need to work with angles. You need trig for a first person camera once per frame, but you can animate a chracter and transform its entire skeleton hierarchy without trig. You mostly use dot and cross product instead sin and cos.

4 hours ago, the incredible smoker said:

So i made this win32 app showing a square with a line, if i make it bigger or smaller it looks like it is going further or closer,

how do i implement Z position without heavey math ?, so that it would be correct.

and what about rotating the camera ( i,m not rotating the square yet, need the positioning first ).

Ofcourse i also need to rotate the square, how would i do all that without calling math functions ?

Probably your hardware can do much more math than you think.

You use one matrix for the camera, and one matrix for each dynamic object. By multiplying both matrices you need to transform each vertex with only one matrix and do the perspective projecton to get screen coords (DirectX does this for you). However, Both CPU and GPU are built to do math on data - no need to avoid it. Today it's more important to optimize for efficient memory access than to limit math work.

I'd like to add your target hardware to Infinisearchs list

If you haven't already, you might want to look into Chocolate Doom (https://github.com/chocolate-doom/chocolate-doom).

It's a pretty clean and straightforward port of the original Id source. I think it uses SDL, the last time I looked into it.

Likewise, for another good deep dive into how the Doom engine worked, and how it used BSPs, Fabian Sanglard's website is fantastic (http://fabiensanglard.net/doomIphone/doomClassicRenderer.php)