   Half-spaces vs Scanlines?(posted code)
  I have been working on a software rendering engine, and I'm getting close to the point where I am out of ideas about how to speed it up. I would post the code, but Im at work right now ;) I will post the code when I get home tonight, I just wanted to get this convo going. So far in my engine, I load the meshes, compute static per vertex lighting. Then,1. Transform Per vertex2.per triangle, backface cull, clip, and draw using traditional scan conversion with gouraud shading for the vertex lighting.3. no sorting is used, only a zbuffer.I'm pretty sure my algorithms are pretty well in order. I do use float calculations though, and plan on going to fixed point math after this.Besides gonig to fixed point math though, I'm not sure what else I could do. Biki said in another post that I should be using interpolation coefficients instead of gouraud interpolation, and i think he meant that I should be using the bounding box/half space approach. In the halfspace/bounding-box approach, I can skip clipping and triangle rasterization completely can't I? does it actually work out ot be faster than scanlines? I have heard that GPUs do it this way...is this true?any other suggestions will be much appreciated. I prefer to use SSE.Thanks =)[Edited by - CPPNick on April 25, 2009 6:06:06 PM]
  Profile, profile, profile...Apart from that, use some form of frustum/occlusion culling. The fastest object is the one not drawn at all.   ;Quote:Original post by CPPNickI do use float calculations though, and plan on going to fixed point math after this.Modern CPUs are actually really good at floating-point calculations. Especially if you use SSE there's little or nothing to gain from doing fixed-point calculations. But do avoid slow operations like division and C/C++ casts to integer. As suggested, you should profile to find the actual hotspots. I recommend CodeAnalyst.Quote:Biki said in another post that I should be using interpolation coefficients instead of gouraud interpolation, and i think he meant that I should be using the bounding box/half space approach.It sounds like he suggested computing gradients just once for the entire triangle, instead of per scanline.This is described in section 4 and 6 of Triangle Scan Conversion using 2D Homogeneous Coordinates. This is also the article that describes rasterization using half-spaces, hence probably the confusion. But computing the gradients is completely separate from rasterization so you can still use traditional scanlines if you want.Quote:In the halfspace/bounding-box approach, I can skip clipping and triangle rasterization completely can't I?You don't need explicit clipping any more, but that's not a significant advantage. Also, you're still doing rasterization, but it becomes a per-pixel calculation instead of determining scanline start- and endpoints. So it's not faster per se. It really depends on the situation what is faster. However, when you start processing pixels in parallel the half-space approach has many benefits (which is indeed why GPUs use it).   ;Quote:Original post by harveypekarProfile, profile, profile...Quote:Original post by C0D1F1ED As suggested, you should profile to find the actual hotspots. I recommend CodeAnalyst.that's what I'd also strongly suggest.so, when you get home, and show us code, prepare numbers to actually show us what functions and lines inside them take most of the time etc.beside doing that time-manner profiling, it's also very helpful to get statistical profilingse.g. - pixelcount per triangle, in average- triangles per pixel (overdraw), in average, peak and lowest- vertices/s if you dont even do any triangle setup- triangle/s with setup but without drawing any pixels- fps with massive tiny triangles vs few big trianglesi've seen you're using texture mapping, so- performance for various sampling modes- performance of big textures vs tiny textures- performance of swapped u and v coordinates (that could indicated that reorganizing texture layouts might help on speed)- performance for reduced resolution - for reduced depth accuracy (e.g. 16bit vs 32bit and int vs float)and of course, what's your target resolution, object and triangle count, fps (roughly).we dont strictly need your source to be able to spawn our ideas about optimizations, but profiling data is urgent to make usefull suggests.This way we could also tell you if some values are suspicious, compared to our rasterizers.;  Thanks for the input so far,C0D1F1ED  that article you recommended...lol...I have seen that one before..just went right over my head =/ I think I'll have to sit here with that in one window and wiki in the other, and maybe I will be able to figure it out.I do have a copy of CodeAnalyst, but so far I have only had it telling me which routine was slowest..I didnt know I could profile line by line. I'll try to figure that out too.here is the code for now, and Ill try and figure out how to get a more detailed report from CodeAnalyst. All its telling me now is that my last call "RenderFragment" is by far the slowest, and that "fastzero_I" is in second place. Also, that at a mere 4000 polys, I am already using more than my fiar share of memory =( analyst says "Invalid Heap size" and lists the number 4294967295.#include "GEOM.H"CAMERA camera;OBJECT *obj;ofstream fout;void GEOM::Render(){//memset(p_bits, 0, SIZE_BITS);memset(z_buffer, 0, SIZE_BITS);//fout.open("output.txt");cos_ax = cos(camera.angx);cos_ay = cos(camera.angy);sin_ax = sin(camera.angx);sin_ay = sin(camera.angy);mtx_t.R0C0 = cos_ay;mtx_t.R1C0 = 0;mtx_t.R2C0 = -sin_ay;mtx_t.R0C1 = -sin_ax * sin_ay;mtx_t.R1C1 = cos_ax;mtx_t.R2C1 = -sin_ax * cos_ay;mtx_t.R0C2 = cos_ax * sin_ay;mtx_t.R1C2 = sin_ax;mtx_t.R2C2 = cos_ax * cos_ay;mtx_t.R0C3 = mtx_t.R0C0 * camera.pos.x + mtx_t.R1C0 * camera.pos.y + mtx_t.R2C0 * camera.pos.z;mtx_t.R1C3 = mtx_t.R0C1 * camera.pos.x + mtx_t.R1C1 * camera.pos.y + mtx_t.R2C1 * camera.pos.z;mtx_t.R2C3 = mtx_t.R0C2 * camera.pos.x + mtx_t.R1C2 * camera.pos.y + mtx_t.R2C2 * camera.pos.z;for(o = 0; o < n_obj; o++){for(v = 0; v < obj[o].n_verts; v++){cvert = &obj[o].verts[v];tvert = &obj[o].tverts[v];tvert->pos.x = cvert->pos.x * mtx_t.R0C0 + cvert->pos.y * mtx_t.R1C0 + cvert->pos.z * mtx_t.R2C0 - mtx_t.R0C3;tvert->pos.y = cvert->pos.x * mtx_t.R0C1 + cvert->pos.y * mtx_t.R1C1 + cvert->pos.z * mtx_t.R2C1 - mtx_t.R1C3;tvert->pos.z = cvert->pos.x * mtx_t.R0C2 + cvert->pos.y * mtx_t.R1C2 + cvert->pos.z * mtx_t.R2C2 - mtx_t.R2C3;tvert->pos.w = 1.f;tvert->shade = cvert->shade;tvert->tex = cvert->tex;tvert->clip_flags = 0;if(Dot4(tvert->pos, frustrum[0]) <= 0) tvert->clip_flags |= CF_LEFT;if(Dot4(tvert->pos, frustrum[1]) <= 0) tvert->clip_flags |= CF_RIGHT;if(Dot4(tvert->pos, frustrum[2]) <= 0) tvert->clip_flags |= CF_TOP;if(Dot4(tvert->pos, frustrum[3]) <= 0) tvert->clip_flags |= CF_BOTTOM;if(Dot4(tvert->pos, frustrum[4]) <= 0) tvert->clip_flags |= CF_NEAR;if(Dot4(tvert->pos, frustrum[5]) <= 0) tvert->clip_flags |= CF_FAR;}for(f = 0; f < obj[o].n_faces; f++){if((obj[o].tverts[ obj[o].faces[f].ind[0] ].clip_flags &obj[o].tverts[ obj[o].faces[f].ind[1] ].clip_flags &obj[o].tverts[ obj[o].faces[f].ind[2] ].clip_flags)||((obj[o].faces[f].normal * (camera.pos - obj[o].verts[ obj[o].faces[f].ind[0] ].pos) < 0)))continue;num_verts = 3;if((obj[o].tverts[ obj[o].faces[f].ind[0] ].clip_flags  | obj[o].tverts[ obj[o].faces[f].ind[1] ].clip_flags  | obj[o].tverts[ obj[o].faces[f].ind[2] ].clip_flags) != 0){if((num_verts = Clip(o, f, obj[o].tverts, vbuffer_a, num_verts)) < 3)continue;}else{for(v = 0; v < num_verts; v++)Project(obj[o].tverts[obj[o].faces[f].ind[v]], vbuffer_a[v]);}for(v = 1; v < num_verts - 1; v++)RasterizeTriangle(o, vbuffer_a[0], vbuffer_a[v], vbuffer_a[v + 1]);}}SetDIBitsToDevice(hdc_render, 0, 0, SCREENWIDTH, SCREENHEIGHT, 0, 0, 0, SCREENHEIGHT, p_bits, (BITMAPINFO *)&bmi_render, DIB_RGB_COLORS);//fout.close();}UINT16 GEOM::Clip(UINT16 &oi, UINT16 &fi, VERTEX4 *verts, VERTEX4 *verts_out, UINT16 nv){vcount = 0;prev = &verts[obj[oi].faces[fi].ind[nv - 1]];dot_prev = Dot4(prev->pos, frustrum[4]);for(v = 0; v < nv; v++){dot_v = Dot4(verts[obj[oi].faces[fi].ind[v]].pos, frustrum[4]);if(dot_v > 0){if(dot_prev <= 0){t = -dot_prev / ((verts[obj[oi].faces[fi].ind[v]].pos - prev->pos) * frustrum[4]);Interpolate(prev, &verts[obj[oi].faces[fi].ind[v]], &vbuffer_b[vcount++], t);}vbuffer_b[vcount++] = verts[obj[oi].faces[fi].ind[v]];}else{if(dot_prev > 0){t = -dot_v / ((prev->pos - verts[obj[oi].faces[fi].ind[v]].pos) * frustrum[4]);Interpolate(&verts[obj[oi].faces[fi].ind[v]], prev, &vbuffer_b[vcount++], t);}}prev = &verts[obj[oi].faces[fi].ind[v]];dot_prev = dot_v;}if(vcount < 3) return 0;nv = 0;prev = &vbuffer_b[vcount - 1];dot_prev = Dot4(prev->pos, frustrum[5]);for(v = 0; v < vcount; v++){dot_v = Dot4(vbuffer_b[v].pos, frustrum[5]);if(dot_v > 0){if(dot_prev <= 0){t = -dot_prev / ((vbuffer_b[v].pos - prev->pos) * frustrum[5]);Interpolate(prev, &vbuffer_b[v], &vbuffer_a[nv], t);Project(vbuffer_a[nv++]);}vbuffer_a[nv] = vbuffer_b[v];Project(vbuffer_a[nv++]);}else{if(dot_prev > 0){t = -dot_v / ((prev->pos - vbuffer_b[v].pos) * frustrum[5]);Interpolate(&vbuffer_b[v], prev, &vbuffer_a[nv], t);Project(vbuffer_a[nv++]);}}prev = &vbuffer_b[v];dot_prev = dot_v;}if(nv < 3) return 0;vcount = 0;prev = &vbuffer_a[nv - 1];for(v = 0; v < nv; v++){if(vbuffer_a[v].pos.x >= CLIPLEFT){if(prev->pos.x < CLIPLEFT) XIntersect(*prev, vbuffer_a[v], vbuffer_b[vcount++], CLIPLEFT);vbuffer_b[vcount++] = vbuffer_a[v];}else if(prev->pos.x >= CLIPLEFT) XIntersect(vbuffer_a[v], *prev, vbuffer_b[vcount++], CLIPLEFT);prev = &vbuffer_a[v];}if(vcount < 3) return 0;nv = 0;prev = &vbuffer_b[vcount - 1];for(v = 0; v < vcount; v++){if(vbuffer_b[v].pos.x <= CLIPRIGHT){if(prev->pos.x > CLIPRIGHT) XIntersect(vbuffer_b[v], *prev, vbuffer_a[nv++], CLIPRIGHT);vbuffer_a[nv++] = vbuffer_b[v];}else if(prev->pos.x <= CLIPRIGHT) XIntersect(*prev, vbuffer_b[v], vbuffer_a[nv++], CLIPRIGHT);prev = &vbuffer_b[v];}if(nv < 3) return 0;vcount = 0;prev = &vbuffer_a[nv - 1];for(v = 0; v < nv; v++){if(vbuffer_a[v].pos.y >= CLIPTOP){if(prev->pos.y < CLIPTOP) YIntersect(*prev, vbuffer_a[v], vbuffer_b[vcount++], CLIPTOP);vbuffer_b[vcount++] = vbuffer_a[v];}else if(prev->pos.y >= CLIPTOP) YIntersect(vbuffer_a[v], *prev, vbuffer_b[vcount++], CLIPTOP);prev = &vbuffer_a[v];}if(vcount < 3) return 0;nv = 0;prev = &vbuffer_b[vcount - 1];for(v = 0; v < vcount; v++){if(vbuffer_b[v].pos.y <= CLIPBOTTOM){if(prev->pos.y > CLIPBOTTOM) YIntersect(*prev, vbuffer_b[v], verts_out[nv++], CLIPBOTTOM);verts_out[nv++] = vbuffer_b[v];}else if(prev->pos.y <= CLIPBOTTOM) YIntersect(vbuffer_b[v], *prev, verts_out[nv++], CLIPBOTTOM);prev = &vbuffer_b[v];}return nv;}void GEOM::RasterizeTriangle(UINT16 &index, VERTEX4 v1, VERTEX4 v2, VERTEX4 v3){if(v3.pos.y < v1.pos.y){v_tmp = v1;v1 = v3;v3 = v_tmp;}if(v3.pos.y < v2.pos.y){v_tmp = v2;v2 = v3;v3 = v_tmp;}if(v2.pos.y < v1.pos.y){v_tmp = v1;v1 = v2;v2 = v_tmp;}if(v1.pos.y == v3.pos.y) return;if(v1.pos.y == v2.pos.y){if(v1.pos.x < v2.pos.x)RenderFragment(index, v1, v2, v3, v3);else if(v2.pos.x < v1.pos.x) RenderFragment(index, v2, v1, v3, v3);}else if(v2.pos.y == v3.pos.y){if(v2.pos.x < v3.pos.x) RenderFragment(index, v1, v1, v2, v3);else if(v3.pos.x < v2.pos.x) RenderFragment(index, v1, v1, v3, v2);}else{YIntersect(v1, v3, v_tmp, v2.pos.y);if(v_tmp.pos.x < v2.pos.x){RenderFragment(index, v1, v1, v_tmp, v2);RenderFragment(index, v_tmp, v2, v3, v3);}else if(v2.pos.x < v_tmp.pos.x){RenderFragment(index, v1, v1, v2, v_tmp);RenderFragment(index, v2, v_tmp, v3, v3);}}}void GEOM::RenderFragment(UINT16 &index, VERTEX4 &lefttop, VERTEX4 &righttop, VERTEX4 &leftbot, VERTEX4 &rightbot){dy = leftbot.pos.y - lefttop.pos.y;ml = (leftbot.pos.x - lefttop.pos.x) / dy;mr = (rightbot.pos.x - righttop.pos.x) / dy;flx = (int)((lefttop.pos.x + 0.5f) * 65536.f);frx = (int)((righttop.pos.x + 0.5f) * 65536.f);fml = (int)(ml * 65536.f);fmr = (int)(mr * 65536.f);textr = &textures[index];widsub1 = short(textr->bm.bmWidth - 1);hgtsub1 = short(textr->bm.bmHeight - 1);m_dy = _mm_set_ps1(dy);l_uvws = _mm_setr_ps(lefttop.tex.u*(float)widsub1, lefttop.tex.v*(float)hgtsub1, lefttop.pos.w, lefttop.shade * 256); //set to top left vert valuesr_uvws = _mm_setr_ps(righttop.tex.u*(float)widsub1, righttop.tex.v*(float)hgtsub1, righttop.pos.w, righttop.shade * 256); //set to top right vert valuesl_duvws = _mm_setr_ps(leftbot.tex.u*(float)widsub1, leftbot.tex.v*(float)hgtsub1, leftbot.pos.w, leftbot.shade * 256); //set to bot left vert valuesr_duvws = _mm_setr_ps(rightbot.tex.u*(float)widsub1, rightbot.tex.v*(float)hgtsub1, rightbot.pos.w, rightbot.shade * 256); //set to bot right vert valuesl_duvws = _mm_sub_ps(l_duvws, l_uvws); //subtract to get d_uvws for leftr_duvws = _mm_sub_ps(r_duvws, r_uvws); //subtract to get d_uvws for rightl_duvws = _mm_div_ps(l_duvws, m_dy); // divide by change in yr_duvws = _mm_div_ps(r_duvws, m_dy); // divide by change in y//for(sy = int(lefttop.pos.y + 0.5f); sy < int(leftbot.pos.y + 0.5f); sy++){_lx = flx>>16;_rx = frx>>16;h_uvws = l_uvws;h_duvws = _mm_sub_ps(r_uvws, l_uvws);m_dx = _mm_set_ps1(float(_rx - _lx));h_duvws = _mm_div_ps(h_duvws, m_dx);pix = bit(_lx, sy);screen_ptr = &p_bits[pix];zbuff_ptr = &z_buffer[pix];for(sx = _lx; sx < _rx; sx++){if(h_uvws.m128_f32[2] > *zbuff_ptr){*zbuff_ptr = h_uvws.m128_f32[2];m_fin = _mm_set_ps1(h_uvws.m128_f32[2]);m_fin = _mm_div_ps(h_uvws, m_fin);pixel_x = short(m_fin.m128_f32[0]) % widsub1;pixel_y = short(m_fin.m128_f32[1]) % hgtsub1;texbit = textr->bits[pixel_y * textr->bm.bmWidth + pixel_x];shade = UINT(m_fin.m128_f32[3]);*screen_ptr=((((texbit & 0xff00) * shade) & 0xff0000)|(((texbit & 0xff00ff) * shade) & 0xff00ff00))>>8;}zbuff_ptr++;screen_ptr++;h_uvws = _mm_add_ps(h_uvws, h_duvws);}flx += fml;frx += fmr;l_uvws = _mm_add_ps(l_uvws, l_duvws);r_uvws = _mm_add_ps(r_uvws, r_duvws);}} [Edited by - CPPNick on May 1, 2009 12:20:48 PM];  OK! after a FIERCE battle with the forum, I was able to get most of the important code posted above.[Edited by - CPPNick on April 26, 2009 2:25:51 AM];  Here's a tutorial that I found much easier to follow on the half-space approach than that white paper(I personally can't stand white papers written by academics, they take too long to get to the pont!). It does not cover any of the interpolation however so you may still want to sift through that article on that. Half-Space Approach;  Thx edge, but I probably wont be switching to the halfspace function. I am actually more interested in the interpolation stuff from that article now. I know what you mean about the whitepapers though...ugh...I might as well be reading that one up there upside down..loledit- maybe I should   ;  so can anyone give me any pointers on speeding up that code that I posted?   ;  in one of your other threads I gave you already one forpixel_x = short(fin[0] * widsub1) % widsub1;pixel_y = short(fin[1] * hgtsub1) % hgtsub1;in general it's smart to precalculate as much as possible outside the inner loops.but then again, give us some timmings/profiling informations ;)   