• Advertisement

3D optimization in barycentric technique of rasterisation

Recommended Posts

 

I am coding the rasterization of triangles by the baricentric coordinate method.

Look a lot of code and tutorials that are on the web about the optimization of this algorithm.

I found a way to optimize it that I did not see it anywhere.

I Only code the painting of triangles without Zbuffer and without textures. I am not comparing speeds and I am not interested in doing them, I am simply reducing the amount of instructions that are executed in the internal loop.

The idea is simple, someone must have done it before but he did not publish the code or maybe in hardware it is already that way too.

It should be noted that for each horizontal line drawn, of the three segments, you only need to look at one when going from negative to positive to start drawing and you only need to look at one when it goes from positive to negative when you stop drawing.

I try it and it works well, now I am implementing a regular version with texture and zbuffer to realize how to add it to this optimization.

Does anyone know if this optimization is already done?

The code is in https://github.com/phreda4/reda4/blob/master/r4/Dev/graficos/rasterize2.txt

From line 92 to 155

 

Share this post


Link to post
Share on other sites
Advertisement
46 minutes ago, pabloreda said:

It should be noted that for each horizontal line drawn, of the three segments, you only need to look at one when going from negative to positive to start drawing and you only need to look at one when it goes from positive to negative when you stop drawing.

Are you talking about halfspaces?  and by segment you mean the edges of the triangle?

46 minutes ago, pabloreda said:

or maybe in hardware it is already that way too.

Hardware is done more like this: http://forum.devmaster.net/t/advanced-rasterization/6145

Share this post


Link to post
Share on other sites

yes, the halfspaces.

the code in inner loop is

   for(int x = minx; x < maxx; x++)
        {
            if(Cx1 > 0 && Cx2 > 0 && Cx3 > 0)
            {
                colorBuffer[x] = 0x00FFFFFF;<< // White
            }

            Cx1 -= Dy12;
            Cx2 -= Dy23;
            Cx3 -= Dy31;
        }

don't need calculate the 3 vars, only one, when you know, for example x1 for in and x2 for out

			  while (Cx1<0) 
			  { Cx1-=Dy12;Cx2-=Dy23;pVideo++; }
			  while (Cx2>0)
			  { Cx2-=Dy23;*pVideo++=Color; }

 

Edited by pabloreda

Share this post


Link to post
Share on other sites

Your optimization moves complexity to the outer loop, similar to the sorting of edges to walk them along for classical scanline conversation. This likely makes your algorithm equivalent to it, you just got there from another point of view. If you would optimize your first while away (you should - it just counts until real work can be started), then it boils down to classical scanline conversation inner loop, and outer loop should be similar to the edge setup / sorting we see in classical scanline conversation.

(I can't read you code because i don't know that language, so i'm not 100% sure)

Note: Scanline conversation does not process 'useless' pixels outside the triangle but inside the bounding box. And it can be easily extended to polygons. If you have planar polygons that's another big win because edge setup is expensive. When not using SIMD i think it's still the fastest in general.

 

 

Share this post


Link to post
Share on other sites

JoeJ:

I don't need sort this order in every scanline, only in setup stage, then make 2 outer loop, top and bottom triangle (like clasical scanline algo)

Useless pixels outside is the other room for optimization, this algo not scan rigth useless pixels 

Share this post


Link to post
Share on other sites
37 minutes ago, pabloreda said:

JoeJ:

I don't need sort this order in every scanline, only in setup stage, then make 2 outer loop, top and bottom triangle (like clasical scanline algo)

That's what i assumed.

You could use multiple variants for different sized triangles, trading setup cost vs. per pixel cost. 

For large triangles do the sorting and complex edge setup, for tiny triangles do all per pixel, and in between your optimization might do best.

16 hours ago, pabloreda said:

Does anyone know if this optimization is already done?

Back the days when software rasterization was used triangles where large and polys dominated over triangles, so classic scanline conversation was surely faster. So even halfspace method is easier to implement, i doupt it has been used a lot or at all for games.

Today you would look for a simd implementation similar to infinisearchs link. Your idea would make sense here, for instance if you process 4*1 spans instead 2*2 blocks. I assume GPUs use 2*2 blocks because their framebuffers are tiled and Z-curved, while on CPU 4*1 spans should do much better. 

The only remaining usecase of software rasterization today i can think of is software occlusion culling. But there again you likely use large polys approximating good occluders, and more important you likely test a whole scanline vs. a spanlist instead individual pixels. I made such a system and classic non simd scanlines work best here.

Share this post


Link to post
Share on other sites

for the record.

The problem here is I need the 3 vars because this is amount of parameter in vertex (z,u,v) to calculate in every point.

then, this optimization not have future!!

thank's to all

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By Nimmagadda Subba Rao
      Hi,
         I am a CAM developer working with C++ and C# for the past 5 years. I started working on DirectX from past 6 months. I developed a touch screen control viewer using Direct2D. I am working on 3D viewer currently. I am very slow with working on Direct3D. I want to be a gaming developer. As i am new to this i want to know what are the possibilities to explore in this area. How to start developing gaming engines? Is it through tutorials? I heard suggestions from my friends that going for an MS helps. I am not sure on which path to choose. Is it better to go for higher studies and start exploring? I am currently working in India. I want to go to Canada and settle there. Are there any good universities there to learn about graphics programming? Sorry if I am asking too many questions but i want to know the options to choose to get ahead. 
    • By francoisdiy
      So I wrote a programming language called C-Lesh to program games for my game maker Platformisis. It is a scripting language which tiles into the JavaScript game engine via a memory mapper using memory mapped I/O. Currently, I am porting the language as a standalone interpreter to be able to run on the PC and possibly other devices excluding the phone. The interpreter is being written in C++ so for those of you who are C++ fans you can see the different components implemented. Some background of the language and how to program in C-Lesh can be found here:

      http://www.codeloader.net/readme.html
      As I program this thing I will post code from different components and explain.
    • By _RoboCat_
      Hi,
      Can anyone point me into good direction how to resolve this?
      I have flat mesh made from many quads (size 1x1 each) each split into 2 triangles. (made procedural)
      What i want to achieve is : "merge" small quads into bigger ones (show on picture 01), English is not my mother language and my search got no result... maybe i just form question wrong.
      i have array[][] where i store "map" information, for now i'm looking for blobs of same value in it -> and then for each position i create 1 quad. and on end create mesh from all.
      is there any good algorithm for creating mesh between random points on same plane? less triangles better. Or "de-tesselate" this to bigger/less triangles/quads?
      Also i would like to find "edges" and create "faces" between edge points (picture 02 shows what i want to achieve).
      No need for whole code, just if someone can point me in good direction would be nice.
      Thanks


    • By isu diss
      I'm trying to duplicate vertices using std::map to be used in a vertex buffer. I don't get the correct index buffer(myInds) or vertex buffer(myVerts). I can get the index array from FBX but it differs from what I get in the following std::map code. Any help is much appreciated.
      struct FBXVTX { XMFLOAT3 Position; XMFLOAT2 TextureCoord; XMFLOAT3 Normal; }; std::map< FBXVTX, int > myVertsMap; std::vector<FBXVTX> myVerts; std::vector<int> myInds; HRESULT FBXLoader::Open(HWND hWnd, char* Filename, bool UsePositionOnly) { HRESULT hr = S_OK; if (FBXM) { FBXIOS = FbxIOSettings::Create(FBXM, IOSROOT); FBXM->SetIOSettings(FBXIOS); FBXI = FbxImporter::Create(FBXM, ""); if (!(FBXI->Initialize(Filename, -1, FBXIOS))) { hr = E_FAIL; MessageBox(hWnd, (wchar_t*)FBXI->GetStatus().GetErrorString(), TEXT("ALM"), MB_OK); } FBXS = FbxScene::Create(FBXM, "REALMS"); if (!FBXS) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the scene"), TEXT("ALM"), MB_OK); } if (!(FBXI->Import(FBXS))) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to import fbx file content into the scene"), TEXT("ALM"), MB_OK); } FbxAxisSystem OurAxisSystem = FbxAxisSystem::DirectX; FbxAxisSystem SceneAxisSystem = FBXS->GetGlobalSettings().GetAxisSystem(); if(SceneAxisSystem != OurAxisSystem) { FbxAxisSystem::DirectX.ConvertScene(FBXS); } FbxSystemUnit SceneSystemUnit = FBXS->GetGlobalSettings().GetSystemUnit(); if( SceneSystemUnit.GetScaleFactor() != 1.0 ) { FbxSystemUnit::cm.ConvertScene( FBXS ); } if (FBXI) FBXI->Destroy(); FbxNode* MainNode = FBXS->GetRootNode(); int NumKids = MainNode->GetChildCount(); FbxNode* ChildNode = NULL; for (int i=0; i<NumKids; i++) { ChildNode = MainNode->GetChild(i); FbxNodeAttribute* NodeAttribute = ChildNode->GetNodeAttribute(); if (NodeAttribute->GetAttributeType() == FbxNodeAttribute::eMesh) { FbxMesh* Mesh = ChildNode->GetMesh(); if (UsePositionOnly) { NumVertices = Mesh->GetControlPointsCount();//number of vertices MyV = new XMFLOAT3[NumVertices]; for (DWORD j = 0; j < NumVertices; j++) { FbxVector4 Vertex = Mesh->GetControlPointAt(j);//Gets the control point at the specified index. MyV[j] = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); } NumIndices = Mesh->GetPolygonVertexCount();//number of indices MyI = (DWORD*)Mesh->GetPolygonVertices();//index array } else { FbxLayerElementArrayTemplate<FbxVector2>* uvVertices = NULL; Mesh->GetTextureUV(&uvVertices); int idx = 0; for (int i = 0; i < Mesh->GetPolygonCount(); i++)//polygon(=mostly triangle) count { for (int j = 0; j < Mesh->GetPolygonSize(i); j++)//retrieves number of vertices in a polygon { FBXVTX myVert; int p_index = 3*i+j; int t_index = Mesh->GetTextureUVIndex(i, j); FbxVector4 Vertex = Mesh->GetControlPointAt(p_index);//Gets the control point at the specified index. myVert.Position = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); FbxVector4 Normal; Mesh->GetPolygonVertexNormal(i, j, Normal); myVert.Normal = XMFLOAT3((float)Normal.mData[0], (float)Normal.mData[1], (float)Normal.mData[2]); FbxVector2 uv = uvVertices->GetAt(t_index); myVert.TextureCoord = XMFLOAT2((float)uv.mData[0], (float)uv.mData[1]); if ( myVertsMap.find( myVert ) != myVertsMap.end() ) myInds.push_back( myVertsMap[ myVert ]); else { myVertsMap.insert( std::pair<FBXVTX, int> (myVert, idx ) ); myVerts.push_back(myVert); myInds.push_back(idx); idx++; } } } } } } } else { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the FBX Manager"), TEXT("ALM"), MB_OK); } return hr; } bool operator < ( const FBXVTX &lValue, const FBXVTX &rValue) { if (lValue.Position.x != rValue.Position.x) return(lValue.Position.x < rValue.Position.x); if (lValue.Position.y != rValue.Position.y) return(lValue.Position.y < rValue.Position.y); if (lValue.Position.z != rValue.Position.z) return(lValue.Position.z < rValue.Position.z); if (lValue.TextureCoord.x != rValue.TextureCoord.x) return(lValue.TextureCoord.x < rValue.TextureCoord.x); if (lValue.TextureCoord.y != rValue.TextureCoord.y) return(lValue.TextureCoord.y < rValue.TextureCoord.y); if (lValue.Normal.x != rValue.Normal.x) return(lValue.Normal.x < rValue.Normal.x); if (lValue.Normal.y != rValue.Normal.y) return(lValue.Normal.y < rValue.Normal.y); return(lValue.Normal.z < rValue.Normal.z); }  
    • By Karol Plewa
      Hi, 
       
      I am working on a project where I'm trying to use Forward Plus Rendering on point lights. I have a simple reflective scene with many point lights moving around it. I am using effects file (.fx) to keep my shaders in one place. I am having a problem with Compute Shader code. I cannot get it to work properly and calculate the tiles and lighting properly. 
       
      Is there anyone that is wishing to help me set up my compute shader?
      Thank you in advance for any replies and interest!
  • Advertisement