Skip to main content
gamedev.net
🔒 Locked

Rendering algorithm Optimization

Started by CPPNick May 10, 2009 at 4:41 PM 27 replies 4.3k views
Original Post
CPPNick
CPPNick
Hello again! throughout my last post, the subject changed a little as my project advanced. With the help of stonemonkey, krypt0n and a few others I was able to make some major improvements to this triangle rendering algorithm. I have had a few other suggestions, like doing some sorting, but I'm not sure that it will help this case. Below is the output from AMD Code Analyst. The output that lines 379, 380 and 383 are taking a lot more time than the rest of the code. I have expanded the assembly for the lines that are problematic. I am wondering if the few commands that are taking so much longer than the rest are due to memory latency problems, cache misses, or if the output that I am getting is simply because of Code Analyst giving me inaccurate readings? Any advice on this would be much appreciated =) thanks 

void GEOM::RenderFragment(UINT16 &index, VERTEX4 &lefttop, VERTEX4 &righttop, VERTEX4 &leftbot, VERTEX4 &rightbot, BYTE TOPBOT) 	                   	0             	
 	0x402910 	315  	      	{	                                                                                                                              	                   	0             	
 	0x402913 	316  	      		dy = 1.f / (leftbot.pos.y - lefttop.pos.y);                                                                                    	                   	0             	
 	         	317  	      		                                                                                                                               	                   	0             	
 	0x40291f 	318  	      		textr = &textures[index];                                                                                                      	                   	0             	
 	         	319  	      		widsub1 = UINT(textr->bm.bmWidth - 1);                                                                                         	                   	0             	
 	         	320  	      		hgtsub1 = UINT(textr->bm.bmHeight - 1);                                                                                        	                   	0             	
 	         	321  	      	                                                                                                                                	                   	0             	
 	0x402923 	322  	      		LX =  int(lefttop.pos.x * 0x10000);                                                                                            	                   	0.02          	
 	         	323  	      		LDX = int(((leftbot.pos.x - lefttop.pos.x) * dy) * 0x10000);                                                                   	                   	0             	
 	0x402911 	324  	      		LU =  int(lefttop.tex.u*widsub1 * 0x400000);//                                                                                 	                   	0.03          	
 	0x4029ce 	325  	      		LDU = int(((leftbot.tex.u*widsub1 - lefttop.tex.u*widsub1) * dy) * 0x400000);//                                                	                   	0             	
 	0x4029ee 	326  	      		LV =  int(lefttop.tex.v*hgtsub1 * 0x400000);//                                                                                 	                   	0.01          	
 	0x402a12 	327  	      		LDV = int(((leftbot.tex.v*hgtsub1 - lefttop.tex.v*hgtsub1) * dy) * 0x400000);//                                                	                   	0.01          	
 	0x402a32 	328  	      		LW =  int(lefttop.pos.w * 0x40000000);                                                                                         	                   	0.01          	
 	0x402a53 	329  	      		LDW = int(((leftbot.pos.w - lefttop.pos.w) * dy) * 0x40000000);                                                                	                   	0             	
 	0x402912 	330  	      		LS =  int(lefttop.shade * 0x40000000);                                                                                         	                   	0             	
 	         	331  	      		LDS = int(((leftbot.shade - lefttop.shade) * dy) * 0x40000000);                                                                	                   	0             	
 	         	332  	      		                                                                                                                               	                   	0             	
 	0x402a78 	333  	      		RX =  int(righttop.pos.x * 0x10000);                                                                                           	                   	0             	
 	0x402a7c 	334  	      		RDX = int(((rightbot.pos.x - righttop.pos.x) * dy) * 0x10000);                                                                 	                   	0.01          	
 	0x402ad2 	335  	      		RU =  int(righttop.tex.u*widsub1 * 0x400000);//                                                                                	                   	0             	
 	0x402ae8 	336  	      		RDU = int(((rightbot.tex.u*widsub1 - righttop.tex.u*widsub1) * dy) * 0x400000);//                                              	                   	0.01          	
 	0x402b0e 	337  	      		RV =  int(righttop.tex.v*hgtsub1 * 0x400000);//                                                                                	                   	0             	
 	0x402b24 	338  	      		RDV = int(((rightbot.tex.v*hgtsub1 - righttop.tex.v*hgtsub1) * dy) * 0x400000);//                                              	                   	0.01          	
 	0x402b4a 	339  	      		RW =  int(righttop.pos.w * 0x40000000);                                                                                        	                   	0             	
 	0x402b5d 	340  	      		RDW = int(((rightbot.pos.w - righttop.pos.w) * dy) * 0x40000000);                                                              	                   	0             	
 	0x402b79 	341  	      		RS =  int(righttop.shade * 0x40000000);                                                                                        	                   	0.01          	
 	0x402b8c 	342  	      		RDS = int(((rightbot.shade - righttop.shade) * dy) * 0x40000000);                                                              	                   	0             	
 	0x402ba8 	343  	      		if(TOPBOT == TRI_TOP)                                                                                                          	                   	0             	
 	         	344  	      		{                                                                                                                              	                   	0             	
 	0x402bb4 	345  	      			dx = 1.f / (rightbot.pos.x - leftbot.pos.x);                                                                                  	                   	0             	
 	0x402bc0 	346  	      			HDU = int(((rightbot.tex.u*widsub1  - leftbot.tex.u*widsub1) * dx) * 0x400000);                                               	                   	0.01          	
 	0x402beb 	347  	      			HDV = int(((rightbot.tex.v*hgtsub1 - leftbot.tex.v*hgtsub1) * dx) * 0x400000);                                                	                   	0             	
 	0x402c0e 	348  	      			HDW = int(((rightbot.pos.w - leftbot.pos.w) * dx) * 0x40000000);                                                              	                   	0             	
 	0x402c2a 	349  	      			HDS = int(((rightbot.shade - leftbot.shade) * dx) * 0x40000000);                                                              	                   	0             	
 	         	350  	      		}                                                                                                                              	                   	0             	
 	0x402c39 	351  	      		else if(TOPBOT == TRI_BOT)                                                                                                     	                   	0             	
 	         	352  	      		{                                                                                                                              	                   	0             	
 	0x402c42 	353  	      			dx = 1.f / (righttop.pos.x - lefttop.pos.x);                                                                                  	                   	0             	
 	0x402c4e 	354  	      			HDU = int(((righttop.tex.u*widsub1 - lefttop.tex.u*widsub1) * dx) * 0x400000);                                                	                   	0.02          	
 	0x402c79 	355  	      			HDV = int(((righttop.tex.v*hgtsub1 - lefttop.tex.v*hgtsub1) * dx) * 0x400000);                                                	                   	0.01          	
 	0x402c9c 	356  	      			HDW = int(((righttop.pos.w - lefttop.pos.w) * dx) * 0x40000000);                                                              	                   	0             	
 	0x402cb8 	357  	      			HDS = int(((righttop.shade - lefttop.shade) * dx) * 0x40000000);                                                              	                   	0.01          	
 	         	358  	      		}                                                                                                                              	                   	0             	
 	0x402cd8 	359  	      		for(sy = int(lefttop.pos.y + 0.5f); sy < int(leftbot.pos.y + 0.5f); sy++)                                                      	                   	0.01          	
 	         	360  	      		{                                                                                                                              	                   	0             	
 	0x402d10 	361  	      			HU = LU;                                                                                                                      	                   	0.01          	
 	         	362  	      			HV = LV;                                                                                                                      	                   	0             	
 	         	363  	      			HW = LW;                                                                                                                      	                   	0             	
 	         	364  	      			HS = LS;                                                                                                                      	                   	0             	
 	         	365  	      			                                                                                                                              	                   	0             	
 	         	366  	      			_lx = (LX + 32768)>>16;                                                                                                       	                   	0             	
 	         	367  	      			_rx = (RX + 32768)>>16;                                                                                                       	                   	0             	
 	         	368  	      	                                                                                                                                	                   	0             	
 	0x402d16 	369  	      			pix = bit(_lx, sy);                                                                                                           	                   	0.01          	
 	0x402d22 	370  	      			screen_ptr = p_bits + pix;                                                                                                    	                   	0.14          	
 	0x402d6d 	371  	      			zbuff_ptr = z_buffer + pix;                                                                                                   	                   	0.04          	
 	         	372  	      	                                                                                                                                	                   	0             	
 	0x402d82 	373  	      			for(sx = _lx; sx < _rx; sx++)                                                                                                 	                   	0.07          	
 	         	374  	      			{                                                                                                                             	                   	0             	
 	0x402db0 	375  	      				if(HW > *zbuff_ptr)                                                                                                          	                   	5.19          	
 	         	376  	      				{                                                                                                                            	                   	0             	
 	0x402dc4 	377  	      					*zbuff_ptr = HW;                                                                                                            	                   	0.05          	
 	         	378  	      					_HW = HW>>8;                                                                                                                	                   	0             	
 	0x402dc6 	379  	      					pixel_x = (HU / _HW) & widsub1;                                                                                             	                   	19.84         	

 	0x402dc6 	     	      	mov eax,[ecx+00000540h] 	8B 81 40 05 00 00  	0.02          	
 	0x402dcc 	     	      	mov esi,[ecx+00000550h] 	8B B1 50 05 00 00  	0.72          	
 	0x402dd2 	     	      	sar esi,08h             	C1 FE 08           	0.03          	
 	0x402dd5 	     	      	cdq                     	99                 	0.03          	
 	0x402dd6 	     	      	idiv esi                	F7 FE              	0.67          	
 	0x402dd8 	     	      	mov [ecx+00000568h],esi 	89 B1 68 05 00 00  	18.37         	
 	0x402dde 	     	      	mov edi,eax             	8B F8              	0.01          	

 	0x402de0 	380  	      					pixel_y = (HV / _HW) & hgtsub1;                                                                                             	                   	15            	

 	0x402de0 	     	      	mov eax,[ecx+00000548h] 	8B 81 48 05 00 00  	0.56          	
 	0x402de6 	     	      	cdq                     	99                 	0.17          	
 	0x402de7 	     	      	idiv esi                	F7 FE              	0             	
 	0x402de9 	     	      	and edi,[ecx+000004cch] 	23 B9 CC 04 00 00  	13.77         	
 	0x402def 	     	      	mov [ecx+0000056ch],edi 	89 B9 6C 05 00 00  	0.04          	
 	0x402df5 	     	      	mov ebp,eax             	8B E8              	0.46          	

 	0x402df7 	381  	      					shade = HS / _HW;                                                                                                           	                   	8.13          	
 	0x402e06 	382  	      					texbit = textr->bits[pixel_y * textr->bm.bmWidth + pixel_x];                                                                	                   	2.05          	
 	0x402e25 	383  	      					*screen_ptr = ((((texbit & 0xff00) * shade) & 0xff0000)|(((texbit & 0xff00ff) * shade) & 0xff00ff00))>>8;                   	                   	40.63         	

 	0x402e25 	     	      	mov esi,edx             	8B F2              	32.26         	
 	0x402e27 	     	      	and esi,ffff00ffh       	81 E6 FF 00 FF FF  	0.79          	
 	0x402e2d 	     	      	mov edi,edx             	8B FA              	0.74          	
 	0x402e2f 	     	      	imul esi,eax            	0F AF F0           	0.23          	
 	0x402e32 	     	      	and edi,0000ff00h       	81 E7 00 FF 00 00  	2.07          	
 	0x402e38 	     	      	imul edi,eax            	0F AF F8           	0.09          	
 	0x402e3b 	     	      	mov [ecx+000005c0h],edx 	89 91 C0 05 00 00  	0.71          	
 	0x402e41 	     	      	and edx,00ff00ffh       	81 E2 FF 00 FF 00  	0.3           	
 	0x402e47 	     	      	imul edx,eax            	0F AF D0           	0             	
 	0x402e4a 	     	      	mov eax,[ecx+24h]       	8B 41 24           	0.44          	
 	0x402e4d 	     	      	xor esi,edi             	33 F7              	0.31          	
 	0x402e4f 	     	      	and esi,00ff0000h       	81 E6 00 00 FF 00  	0.06          	
 	0x402e55 	     	      	xor esi,edx             	33 F2              	0.55          	
 	0x402e57 	     	      	shr esi,08h             	C1 EE 08           	1.06          	
 	0x402e5a 	     	      	mov [eax],esi           	89 30              	1.03        

 	         	384  	      				}                                                                                                                            	                   	0             	
 	         	385  	      				zbuff_ptr++;                                                                                                                 	                   	0             	
 	         	386  	      				screen_ptr++;                                                                                                                	                   	0             	
 	0x402e5c 	387  	      				HU += HDU;                                                                                                                   	                   	0.84          	
 	         	388  	      				HV += HDV;                                                                                                                   	                   	0             	
 	0x402e68 	389  	      				HW += HDW;                                                                                                                   	                   	4.73          	
 	0x402e94 	390  	      				HS += HDS;                                                                                                                   	                   	2.42          	
 	         	391  	      			}                                                                                                                             	                   	0             	
 	0x402eb2 	392  	      			LX += LDX;                                                                                                                    	                   	0.08          	
 	0x402ebe 	393  	      			LU += LDU;                                                                                                                    	                   	0.03          	
 	0x402eca 	394  	      			LV += LDV;                                                                                                                    	                   	0.07          	
 	0x402ed6 	395  	      			LW += LDW;                                                                                                                    	                   	0.04          	
 	0x402ee2 	396  	      			LS += LDS;                                                                                                                    	                   	0.04          	
 	0x402eee 	397  	      			RX += RDX;                                                                                                                    	                   	0.02          	
 	0x402efa 	398  	      			RU += RDU;                                                                                                                    	                   	0.06          	
 	0x402f06 	399  	      			RV += RDV;                                                                                                                    	                   	0.01          	
 	0x402f12 	400  	      			RW += RDW;                                                                                                                    	                   	0.05          	
 	0x402f1e 	401  	      			RS += RDS;                                                                                                                    	                   	0.3           	
 	         	402  	      		}                                                                                                                              	                   	0             	
 	0x402f4d 	403  	      	}                                                                                                                               	                   	0
[Edited by - CPPNick on May 13, 2009 10:18:31 AM]
MortenB
MortenB
That looks pretty much like I'd expect. The spikes don't show until the oop hardware runs out of options, so it's kind of hard to read these things sometimes.
E.g. the spike from 379 looks like it's caused by the read/write on 375/377.

-Morten-
CPPNick
CPPNick
Quote:
Original post by MortenB
the spike from 379 looks like it's caused by the read/write on 375/377.
-Morten-


I read that writing to memory non-sequentially is a bad thing. Is this an example of that problem? Could anyone elaborate on this a little bit?

edit- if the memory writing is the problem, would using push/pop to the stack with variables rather than writing to memory speed things up? how much of a gain is actually attainable if I were to rewrite this procedure in assembly to streamline it?


EDIT-
I find this one particularly troubling(an excerpt from the compiler generated assembly):
00402DC6   . 8B8E 50050000  MOV ECX,DWORD PTR DS:[ESI+550]   ;<---- read in once00402DCC   . 3B08           CMP ECX,DWORD PTR DS:[EAX]00402DCE   . 0F8E 9A000000  JLE 3d.00402E6E00402DD4   . 8908           MOV DWORD PTR DS:[EAX],ECX00402DD6   . 8B86 40050000  MOV EAX,DWORD PTR DS:[ESI+540]00402DDC   . 8B8E 50050000  MOV ECX,DWORD PTR DS:[ESI+550]   ;<---read in again....shouldn't it still be there?


[Edited by - CPPNick on May 10, 2009 11:11:24 PM]
Krypt0n
Krypt0n
Quote:
Original post by CPPNick
I am wondering if the few commands that are taking so much longer than the rest are due to memory latency problems, cache misses,

memory-latency are due to cachemisses
if you want to check if cache misses are the problem, lower the amount of your data so it fits the L1 cache (16kb probably), e.g. use an 16*16 texture.

Quote:

or if the output that I am getting is simply because of Code Analyst giving me inaccurate readings?

dont hope on this.

line 379 has an int division, that's very slow
line 383 has 3 integer muls, that's also time taking

and it's the inner loop, it's not stalling, it's just the most used part of your code, it obviously takes the most time.

regarding your twice loading to ecx, i dont see the line "00402DDC " in your ogrinal source, I guess it's some modified code and the context is to tiny to really tell you what's going on, post more code please.
CPPNick
CPPNick
I know muls and divs are expensive, but why are these one lines so expensive when they are just movs?

mov [ecx+00000568h],esi 89 B1 68 05 00 00 18.37
mov edx,ecx 8B D1 20.31
ect...
shouldn't Code Analyst read that the majority of the time was spend on the divs and muls rather than movs and "and"s ?

and the double loading is at
0x402dc6 and 0x402ddc.

as for the code, I just expanded the trouble spots, but here is everything except the initial conversions to fixed point, delta calcs, ect..

the code:
 	0x402ceb 	357  	      		for(sy = int(lefttop.pos.y + 0.5f); sy < int(leftbot.pos.y + 0.5f); sy++)                                      	                         	0.01          	 	         	358  	      		{                                                                                                              	                         	0             	 	0x402d22 	359  	      			HU = LU;                                                                                                      	                         0.01          	 	         	360  	      			HV = LV;                                                                                                      	                         0             	 	0x402d28 	361  	      			HW = LW;                                                                                                      	                         0             	 	         	362  	      			HS = LS;                                                                                                      	                         0             	 	         	363  	      			_lx = (LX + 32768)>>16;                                                                                       	                         0             	 	         	364  	      			_rx = (RX + 32768)>>16;                                                                                       	                         0             	 	         	365  	      			pix = bit(_lx, sy);                                                                                           	                         0             	 	0x402d34 	366  	      			screen_ptr = p_bits + pix;                                                                                    	                         0.09          	 	0x402d7f 	367  	      			zbuff_ptr = z_buffer + pix;                                                                                   	                         0.06          	 	0x402d94 	368  	      			for(sx = _lx; sx < _rx; sx++)                                                                                 	                         0.01          	 	         	369  	      			{                                                                                                             	                         0             	 	0x402dc0 	370  	      				if(HW > *zbuff_ptr)                                                                                          	                 5.21          	 	         	371  	      				{                                                                                                            	                 0             	 	0x402dd4 	372  	      					*zbuff_ptr = HW;                                                                                            	         0.03          	 	         	373  	      					_HW = HW>>8;                                                                                                	         0             	 	0x402dd6 	374  	      					pixel_x = (HU / _HW) & widsub1;                                                                             	         21.82         	 	0x402df0 	375  	      					pixel_y = (HV / _HW) & hgtsub1;                                                                             	         19.35         	 	0x402e07 	376  	      					shade = HS / _HW;                                                                                           	         10.7          	 	0x402e16 	377  	      					texbit = textr->bits[(pixel_y<<bshl) + pixel_x];                                                            	         2.58          	 	0x402e37 	378  	      					*screen_ptr = ((((texbit & 0xff00) * shade) & 0xff0000) | (((texbit & 0xff00ff) * shade) & 0xff00ff00))>>8; 	         30.11         	 	         	379  	      				}                                                                                                            	                 0             	 	         	380  	      				zbuff_ptr++;                                                                                                 	                 0             	 	         	381  	      				screen_ptr++;                                                                                                	                 0             	 	0x402e6e 	382  	      				HU += HDU;                                                                                                   	                 1.06          	 	0x402e7a 	383  	      				HV += HDV;                                                                                                   	                 0.78          	 	         	384  	      				HW += HDW;                                                                                                   	                 0             	 	0x402e80 	385  	      				HS += HDS;                                                                                                   	                 7.76          	 	         	386  	      			}                                                                                                             	                         0             	 	0x402ec4 	387  	      			LX += LDX;                                                                                                    	                         0.04          	 	0x402ed0 	388  	      			LU += LDU;                                                                                                    	                         0.01          	 	0x402edc 	389  	      			LV += LDV;                                                                                                    	                         0.06          	 	0x402ee8 	390  	      			LW += LDW;                                                                                                    	                         0.03          	 	0x402ef4 	391  	      			LS += LDS;                                                                                                    	                         0.03          	 	0x402f00 	392  	      			RX += RDX;                                                                                                    	                         0.01          	 	0x402f06 	393  	      			RU += RDU;                                                                                                    	                         0.03          	 	0x402f18 	394  	      			RV += RDV;                                                                                                    	                         0.02          	 	0x402f24 	395  	      			RW += RDW;                                                                                                    	                         0.01          	 	0x402f2a 	396  	      			RS += RDS;                                                                                                    	                         0.1           	 	         	397  	      		}                                                                                                              	                         	0             	 	0x402f5f 	398  	      	}                                                                                                               	                         	0


and the corresponding assembly
 	Address  	Line 	Trace 	Source                                                                                                          	Code Bytes               	Timer samples 	 	0x402ceb 	     	      	movss xmm0,[0047d088h]                                                                                          	F3 0F 10 05 88 D0 47 00  	0.01          	 	0x402cf3 	     	      	mov [esi+00000574h],ecx                                                                                         	89 8E 74 05 00 00        	0             	 	0x402cf9 	     	      	movss xmm1,[eax+04h]                                                                                            	F3 0F 10 48 04           	0             	 	0x402cfe 	     	      	addss xmm1,xmm0                                                                                                 	F3 0F 58 C8              	0             	 	0x402d02 	     	      	cvttss2si eax,xmm1                                                                                              	F3 0F 2C C1              	0.01          	 	0x402d06 	     	      	mov [esi+000004e4h],eax                                                                                         	89 86 E4 04 00 00        	0             	 	0x402d0c 	     	      	movss xmm1,[ebx+04h]                                                                                            	F3 0F 10 4B 04           	0             	 	0x402d11 	     	      	addss xmm1,xmm0                                                                                                 	F3 0F 58 C8              	0             	 	0x402d15 	     	      	cvttss2si edx,xmm1                                                                                              	F3 0F 2C D1              	0             	 	0x402d19 	     	      	cmp eax,edx                                                                                                     	3B C2                    	0             	 	0x402d1b 	     	      	jnl $+00000241h (0x402f5c)                                                                                      	0F 8D 3B 02 00 00        	0             	 	0x402d21 	     	      	push ebp                                                                                                        	55                       	0             	 	0x402d22 	     	      	mov eax,[esi+000004f8h]                                                                                         	8B 86 F8 04 00 00        	0.01          	 	0x402d28 	     	      	mov edx,[esi+00000508h]                                                                                         	8B 96 08 05 00 00        	0             	 	0x402d2e 	     	      	mov ecx,[esi+00000500h]                                                                                         	8B 8E 00 05 00 00        	0             	 	0x402d34 	     	      	mov edi,[esi]                                                                                                   	8B 3E                    	0.01          	 	0x402d36 	     	      	mov [esi+00000540h],eax                                                                                         	89 86 40 05 00 00        	0             	 	0x402d3c 	     	      	mov eax,[esi+00000510h]                                                                                         	8B 86 10 05 00 00        	0             	 	0x402d42 	     	      	mov [esi+00000550h],edx                                                                                         	89 96 50 05 00 00        	0.02          	 	0x402d48 	     	      	mov edx,[esi+000004e4h]                                                                                         	8B 96 E4 04 00 00        	0             	 	0x402d4e 	     	      	mov [esi+00000558h],eax                                                                                         	89 86 58 05 00 00        	0             	 	0x402d54 	     	      	mov eax,[esi+000004f0h]                                                                                         	8B 86 F0 04 00 00        	0.01          	 	0x402d5a 	     	      	lea edx,[edx+edx*4]                                                                                             	8D 14 92                 	0             	 	0x402d5d 	     	      	shl edx,08h                                                                                                     	C1 E2 08                 	0             	 	0x402d60 	     	      	add eax,00008000h                                                                                               	05 00 80 00 00           	0             	 	0x402d65 	     	      	sar eax,10h                                                                                                     	C1 F8 10                 	0             	 	0x402d68 	     	      	add edx,eax                                                                                                     	03 D0                    	0             	 	0x402d6a 	     	      	mov [esi+00000548h],ecx                                                                                         	89 8E 48 05 00 00        	0.01          	 	0x402d70 	     	      	mov ecx,[esi+00000518h]                                                                                         	8B 8E 18 05 00 00        	0             	 	0x402d76 	     	      	mov [esi+000005c4h],edx                                                                                         	89 96 C4 05 00 00        	0             	 	0x402d7c 	     	      	lea edx,[edi+edx*4]                                                                                             	8D 14 97                 	0.04          	 	0x402d7f 	     	      	mov edi,[esi+20h]                                                                                               	8B 7E 20                 	0             	 	0x402d82 	     	      	add ecx,00008000h                                                                                               	81 C1 00 80 00 00        	0             	 	0x402d88 	     	      	mov [esi+24h],edx                                                                                               	89 56 24                 	0.01          	 	0x402d8b 	     	      	mov edx,[esi+000005c4h]                                                                                         	8B 96 C4 05 00 00        	0             	 	0x402d91 	     	      	sar ecx,10h                                                                                                     	C1 F9 10                 	0.05          	 	0x402d94 	     	      	cmp eax,ecx                                                                                                     	3B C1                    	0             	 	0x402d96 	     	      	lea edx,[edi+edx*4]                                                                                             	8D 14 97                 	0             	 	0x402d99 	     	      	mov [esi+00000560h],eax                                                                                         	89 86 60 05 00 00        	0.01          	 	0x402d9f 	     	      	mov [esi+00000564h],ecx                                                                                         	89 8E 64 05 00 00        	0.01          	 	0x402da5 	     	      	mov [esi+000004e8h],edx                                                                                         	89 96 E8 04 00 00        	0             	 	0x402dab 	     	      	mov [esi+000004e0h],eax                                                                                         	89 86 E0 04 00 00        	0             	 	0x402db1 	     	      	jnl $+00000113h (0x402ec4)                                                                                      	0F 8D 0D 01 00 00        	0             	 	0x402db7 	     	      	jmp $+09h (0x402dc0)                                                                                            	EB 07                    	0             	 	0x402db9 	     	      	lea esp,[esp+00000000h]                                                                                         	8D A4 24 00 00 00 00     	0             	 	0x402dc0 	     	      	mov eax,[esi+000004e8h]                                                                                         	8B 86 E8 04 00 00        	0.9           	 	0x402dc6 	     	      	mov ecx,[esi+00000550h]                                                                                         	8B 8E 50 05 00 00        	0.04          	 	0x402dcc 	     	      	cmp ecx,[eax]                                                                                                   	3B 08                    	0             	 	0x402dce 	     	      	jle $+000000a0h (0x402e6e)                                                                                      	0F 8E 9A 00 00 00        	4.26          	 	0x402dd4 	     	      	mov [eax],ecx                                                                                                   	89 08                    	0.03          	 	0x402dd6 	     	      	mov eax,[esi+00000540h]                                                                                         	8B 86 40 05 00 00        	0.01          	 	0x402ddc 	     	      	mov ecx,[esi+00000550h]                                                                                         	8B 8E 50 05 00 00        	0.87          	 	0x402de2 	     	      	sar ecx,08h                                                                                                     	C1 F9 08                 	0.03          	 	0x402de5 	     	      	cdq                                                                                                             	99                       	0.01          	 	0x402de6 	     	      	idiv ecx                                                                                                        	F7 F9                    	0.76          	 	0x402de8 	     	      	mov [esi+00000568h],ecx                                                                                         	89 8E 68 05 00 00        	20.16         	 	0x402dee 	     	      	mov ebp,eax                                                                                                     	8B E8                    	0             	 	0x402df0 	     	      	mov eax,[esi+00000548h]                                                                                         	8B 86 48 05 00 00        	0.66          	 	0x402df6 	     	      	cdq                                                                                                             	99                       	0.08          	 	0x402df7 	     	      	idiv ecx                                                                                                        	F7 F9                    	0             	 	0x402df9 	     	      	and ebp,[esi+000004cch]                                                                                         	23 AE CC 04 00 00        	17.87         	 	0x402dff 	     	      	mov [esi+0000056ch],ebp                                                                                         	89 AE 6C 05 00 00        	0.13          	 	0x402e05 	     	      	mov edi,eax                                                                                                     	8B F8                    	0.6           	 	0x402e07 	     	      	mov eax,[esi+00000558h]                                                                                         	8B 86 58 05 00 00        	0.24          	 	0x402e0d 	     	      	cdq                                                                                                             	99                       	0.01          	 	0x402e0e 	     	      	idiv ecx                                                                                                        	F7 F9                    	0.57          	 	0x402e10 	     	      	and edi,[esi+000004d0h]                                                                                         	23 BE D0 04 00 00        	9.88          	 	0x402e16 	     	      	mov ecx,[esi+00000574h]                                                                                         	8B 8E 74 05 00 00        	0             	 	0x402e1c 	     	      	mov [esi+00000570h],edi                                                                                         	89 BE 70 05 00 00        	0.71          	 	0x402e22 	     	      	shl edi,cl                                                                                                      	D3 E7                    	0.13          	 	0x402e24 	     	      	mov ecx,[esi+000004ech]                                                                                         	8B 8E EC 04 00 00        	0.1           	 	0x402e2a 	     	      	add edi,ebp                                                                                                     	03 FD                    	0.72          	 	0x402e2c 	     	      	mov [esi+000004dch],eax                                                                                         	89 86 DC 04 00 00        	0.19          	 	0x402e32 	     	      	mov edx,[ecx]                                                                                                   	8B 11                    	0.01          	 	0x402e34 	     	      	mov ecx,[edx+edi*4]                                                                                             	8B 0C BA                 	0.72          	 	0x402e37 	     	      	mov edx,ecx                                                                                                     	8B D1                    	20.31         	 	0x402e39 	     	      	and edx,ffff00ffh                                                                                               	81 E2 FF 00 FF FF        	0.73          	 	0x402e3f 	     	      	mov edi,ecx                                                                                                     	8B F9                    	0.85          	 	0x402e41 	     	      	imul edx,eax                                                                                                    	0F AF D0                 	0.23          	 	0x402e44 	     	      	and edi,0000ff00h                                                                                               	81 E7 00 FF 00 00        	2.46          	 	0x402e4a 	     	      	imul edi,eax                                                                                                    	0F AF F8                 	0.17          	 	0x402e4d 	     	      	mov [esi+000005e0h],ecx                                                                                         	89 8E E0 05 00 00        	0.74          	 	0x402e53 	     	      	and ecx,00ff00ffh                                                                                               	81 E1 FF 00 FF 00        	0.56          	 	0x402e59 	     	      	imul ecx,eax                                                                                                    	0F AF C8                 	0.03          	 	0x402e5c 	     	      	mov eax,[esi+24h]                                                                                               	8B 46 24                 	0.38          	 	0x402e5f 	     	      	xor edx,edi                                                                                                     	33 D7                    	0.38          	 	0x402e61 	     	      	and edx,00ff0000h                                                                                               	81 E2 00 00 FF 00        	0.11          	 	0x402e67 	     	      	xor edx,ecx                                                                                                     	33 D1                    	0.6           	 	0x402e69 	     	      	shr edx,08h                                                                                                     	C1 EA 08                 	1.1           	 	0x402e6c 	     	      	mov [eax],edx                                                                                                   	89 10                    	1.46          	 	0x402e6e 	     	      	mov ecx,[esi+00000544h]                                                                                         	8B 8E 44 05 00 00        	1.06          	 	0x402e74 	     	      	add [esi+00000540h],ecx                                                                                         	01 8E 40 05 00 00        	0             	 	0x402e80 	     	      	mov ecx,[esi+0000055ch]                                                                                         	8B 8E 5C 05 00 00        	0             	 	0x402e86 	     	      	add [esi+00000548h],edx                                                                                         	01 96 48 05 00 00        	0.88          	 	0x402e8c 	     	      	add [esi+00000558h],ecx                                                                                         	01 8E 58 05 00 00        	1.17          	 	0x402e92 	     	      	inc dword [esi+000004e0h]                                                                                       	FF 86 E0 04 00 00        	1.23          	 	0x402e98 	     	      	mov eax,00000004h                                                                                               	B8 04 00 00 00           	0.76          	 	0x402e9d 	     	      	add [esi+000004e8h],eax                                                                                         	01 86 E8 04 00 00        	0.05          	 	0x402ea3 	     	      	add [esi+24h],eax                                                                                               	01 46 24                 	0.87          	 	0x402ea6 	     	      	mov eax,[esi+00000554h]                                                                                         	8B 86 54 05 00 00        	0.92          	 	0x402eac 	     	      	add [esi+00000550h],eax                                                                                         	01 86 50 05 00 00        	0             	 	0x402eb2 	     	      	mov edx,[esi+000004e0h]                                                                                         	8B 96 E0 04 00 00        	0.91          	 	0x402eb8 	     	      	cmp edx,[esi+00000564h]                                                                                         	3B 96 64 05 00 00        	0.91          	 	0x402ebe 	     	      	jl $-000000feh (0x100402dc0)                                                                                    	0F 8C FC FE FF FF        	0.06          	 	0x402ec4 	     	      	mov eax,[esi+000004f4h]                                                                                         	8B 86 F4 04 00 00        	0             	 	0x402eca 	     	      	add [esi+000004f0h],eax                                                                                         	01 86 F0 04 00 00        	0.04          	 	0x402ed0 	     	      	mov ecx,[esi+000004fch]                                                                                         	8B 8E FC 04 00 00        	0.01          	 	0x402ed6 	     	      	add [esi+000004f8h],ecx                                                                                         	01 8E F8 04 00 00        	0             	 	0x402edc 	     	      	mov edx,[esi+00000504h]                                                                                         	8B 96 04 05 00 00        	0.04          	 	0x402ee2 	     	      	add [esi+00000500h],edx                                                                                         	01 96 00 05 00 00        	0.01          	 	0x402ee8 	     	      	mov eax,[esi+0000050ch]                                                                                         	8B 86 0C 05 00 00        	0.03          	 	0x402eee 	     	      	add [esi+00000508h],eax                                                                                         	01 86 08 05 00 00        	0.01          	 	0x402ef4 	     	      	mov ecx,[esi+00000514h]                                                                                         	8B 8E 14 05 00 00        	0.03          	 	0x402efa 	     	      	add [esi+00000510h],ecx                                                                                         	01 8E 10 05 00 00        	0             	 	0x402f00 	     	      	mov edx,[esi+0000051ch]                                                                                         	8B 96 1C 05 00 00        	0.01          	 	0x402f06 	     	      	mov eax,[esi+00000524h]                                                                                         	8B 86 24 05 00 00        	0             	 	0x402f0c 	     	      	add [esi+00000518h],edx                                                                                         	01 96 18 05 00 00        	0.01          	 	0x402f12 	     	      	add [esi+00000520h],eax                                                                                         	01 86 20 05 00 00        	0.02          	 	0x402f18 	     	      	mov ecx,[esi+0000052ch]                                                                                         	8B 8E 2C 05 00 00        	0.02          	 	0x402f1e 	     	      	add [esi+00000528h],ecx                                                                                         	01 8E 28 05 00 00        	0             	 	0x402f24 	     	      	mov edx,[esi+00000534h]                                                                                         	8B 96 34 05 00 00        	0.01          	 	0x402f2a 	     	      	mov eax,[esi+0000053ch]                                                                                         	8B 86 3C 05 00 00        	0             	 	0x402f30 	     	      	add [esi+00000530h],edx                                                                                         	01 96 30 05 00 00        	0.01          	 	0x402f36 	     	      	add [esi+00000538h],eax                                                                                         	01 86 38 05 00 00        	0             	 	0x402f3c 	     	      	inc dword [esi+000004e4h]                                                                                       	FF 86 E4 04 00 00        	0.01          	 	0x402f42 	     	      	movss xmm1,[ebx+04h]                                                                                            	F3 0F 10 4B 04           	0.02          	 	0x402f47 	     	      	addss xmm1,xmm0                                                                                                 	F3 0F 58 C8              	0.01          	 	0x402f4b 	     	      	cvttss2si ecx,xmm1                                                                                              	F3 0F 2C C9              	0.01          	 	0x402f4f 	     	      	cmp [esi+000004e4h],ecx                                                                                         	39 8E E4 04 00 00        	0.02          	 	0x402f55 	     	      	jl $-00000233h (0x100402d22)                                                                                    	0F 8C C7 FD FF FF        	0.01          	 	0x402f5b 	     	      	pop ebp                                                                                                         	5D                       	0             	 	0x402f5c 	     	      	pop edi                                                                                                         	5F                       	0.01          	 	0x402f5d 	     	      	pop esi                                                                                                         	5E                       	0             	 	0x402f5e 	     	      	pop ebx                                                                                                         	5B                       	0 	0x402f5f 	     	      	retnd 0018h 	C2 18 00   	0
Krypt0n
Krypt0n
how code analyst works is:
every some time interval it reads the instruction counter.

how a cpu works is:
it reads in an struction, starts executing it and moves the instruction counter.


now, assume you have a division, that takes 40cycles.

idiv is read in, instruction counter is moved and execution is started
now the instruction counter waits for 40cycles at the next instruction till the cpu is done with the div an can read in the next instruction and move the counter...



now I try to prefetch your next question "can't code analyst just apply the counter to the previous instruction?"
no
because it doesn't know which was the previous, it might be the one above in code, but it also might be coming from some jump and there is no instruction history in your cpu.



at least that's my theory ;)


oh, and btw.
8bit divisions are faster than 16
16bit are faster than 32bit

some cpus have an 'early out' if they figure out all upper bits are 1 or all are 0, but most cpus dont.
so if you can, make those divisions 16bit instead of 32bit.
also, unsigned are slightly faster than signed.

but it's not all bad, you can split an 32 bit value to dx and ax, then divide by bx (16bit) and you'll get the result in ax (and reminder in dx).


you might also try some old school tricks
instead of

a=a/c;
b=b/d;
you can calculate
e=1/(c*d)
a=a*e*d;
b=b*e*c;

but you have to be very carefull with the ranges, especially when using fix point. but in general, int division are one of the slowest operation on cpus.

CPPNick
CPPNick
Quote:
Original post by Krypt0n
how code analyst works is:
every some time interval it reads the instruction counter.

how a cpu works is:
it reads in an struction, starts executing it and moves the instruction counter.


now, assume you have a division, that takes 40cycles.

idiv is read in, instruction counter is moved and execution is started
now the instruction counter waits for 40cycles at the next instruction till the cpu is done with the div an can read in the next instruction and move the counter...


this is what I was thinking: because it says "time 'samples'" I figured that the code analyst checks at a fixed interval to see what the app is doing, and therefore based on that frequency, may hit anywhere in the middle of a given routine that is hangin around a lot..is this right? or are the time samples accurate all the way to each instruction? because it would mean then, that a certain BLOCK of code, rather than the one instruction is taking all the time.

Quote:
Original post by Krypt0n
now I try to prefetch your next question "can't code analyst just apply the counter to the previous instruction?"
no
because it doesn't know which was the previous, it might be the one above in code, but it also might be coming from some jump and there is no instruction history in your cpu.
at least that's my theory ;)

I guess I better just google "AMD Code Analyst Consumer Reports" lol...

Quote:
Original post by Krypt0n
oh, and btw.
8bit divisions are faster than 16
16bit are faster than 32bit

some cpus have an 'early out' if they figure out all upper bits are 1 or all are 0, but most cpus dont.
so if you can, make those divisions 16bit instead of 32bit.
also, unsigned are slightly faster than signed.

I think I can make most of the ints unsigned, but I don't think I will be able to use 16 bit numbers and still get good enough accuracy...especially for my 1/z buffer, which is never greater than 1, and had to be shifted 30 places to get an ok result.


Quote:
Original post by Krypt0n
but it's not all bad, you can split an 32 bit value to dx and ax, then divide by bx (16bit) and you'll get the result in ax (and reminder in dx).

don't quite understand this one.

Quote:
Original post by Krypt0n
you might also try some old school tricks
instead of

a=a/c;
b=b/d;
you can calculate
e=1/(c*d)
a=a*e*d;
b=b*e*c;

I tried this, but had some trouble because of the way I was doing it with fixed point...Ill give it another go and see If I can get it to work, because there are 3 divs in the middle of the inner-most loop...probably doing some serious damage.


Quote:
Original post by Krypt0n
but you have to be very carefull with the ranges, especially when using fix point. but in general, int division are one of the slowest operation on cpus.

not slower than float though right?


I seem to be getting less and less responses the further I get with this project...am I getting to far into the nitty gritty here to be expecting help at this point? I understand that this was a learning experience, and most people would have simply turned to directx and hardware a long time ago...I do find this very interesting though, and would like to see how fast I can really get this thing to go.

Thanks again Krypt0n =)
Krypt0n
Krypt0n
Quote:
Original post by CPPNick
Quote:
Original post by Krypt0n
how code analyst works is:
every some time interval it reads the instruction counter.

how a cpu works is:
it reads in an struction, starts executing it and moves the instruction counter.


now, assume you have a division, that takes 40cycles.

idiv is read in, instruction counter is moved and execution is started
now the instruction counter waits for 40cycles at the next instruction till the cpu is done with the div an can read in the next instruction and move the counter...


this is what I was thinking: because it says "time 'samples'" I figured that the code analyst checks at a fixed interval to see what the app is doing, and therefore based on that frequency, may hit anywhere in the middle of a given routine that is hangin around a lot..is this right?

it's about stochastic. it's for sure just a probability that how often it hits some instruction, but the longer you profile, the more 'hits' are counted, the more accurate it gets.
so you will have always slightly different results, but when it says that the inner loop's div is taking most, than that's the case.



Quote:
or are the time samples accurate all the way to each instruction? because it would mean then, that a certain BLOCK of code, rather than the one instruction is taking all the time.
in your case there was like 40% of the hits to the specific instruction. imagine there are several million 'hits' that were counted and 40% hit that div instruction, how big is the chances that 400 000 hits were accidently wrong? ;)

Quote:

Quote:
Original post by Krypt0n
but it's not all bad, you can split an 32 bit value to dx and ax, then divide by bx (16bit) and you'll get the result in ax (and reminder in dx).

don't quite understand this one.

look at some assembly documentation, the x86 is doing the division by moving the higher 16bit into the DX register and the lower into AX and then dividing by BX (in case of 32 bit it's EDX, EAX and EBX). so you can still divide some 32Bit number by a 16bit one (not just 32bit by 32bit), that's sometimes enough, but be carefull to not get any overflow (if you divide 65536 by 1, the result won't fit into 16 bit and you'd get an overflow).


Quote:

Quote:
Original post by Krypt0n
you might also try some old school tricks
instead of

a=a/c;
b=b/d;
you can calculate
e=1/(c*d)
a=a*e*d;
b=b*e*c;

I tried this, but had some trouble because of the way I was doing it with fixed point...Ill give it another go and see If I can get it to work, because there are 3 divs in the middle of the inner-most loop...probably doing some serious damage.
yeah, this trick was mostly used with floats where you can't avoid them.


Quote:

Quote:
Original post by Krypt0n
but you have to be very carefull with the ranges, especially when using fix point. but in general, int division are one of the slowest operation on cpus.

not slower than float though right?

isn't it kinda weak to optimize code just based on your own assumption? you should check everything, or check it twice, otherwise you will never know if something is good or bad for performance and if you get the optimum or if there is still speed to gain.
on min google:
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF
idiv 42cycles
fdiv 20cycles, fidiv 18cycles
divps 33cycles (4divs at a time -> one div is ~8cycles)

Quote:

I seem to be getting less and less responses the further I get with this project...am I getting to far into the nitty gritty here to be expecting help at this point? I understand that this was a learning experience, and most people would have simply turned to directx and hardware a long time ago...I do find this very interesting though, and would like to see how fast I can really get this thing to go.

so, how many triangle to you push in what resolution? we could compare ;)



CPPNick
CPPNick
Quote:

so, how many triangle to you push in what resolution? we could compare ;)


its not really about that just yet..
I'm trying to get my prj to 30FPS+ at 1280x800, and sitting at about 10-15 right now. I can put up to 3000-4000 triangles before it starts to slow down because of them. My fill rate is what I need to improve.

and you're saying that here:
0x402dd6 idiv esi F7 FE 0.67
0x402dd8 mov [ecx+00000568h],esi 89 B1 68 05 00 00 18.37

the time taken could actually be that div rather than the mov right?

thx for the AMD article too..looks like good reading. I found another about assembly optimization too.
CPPNick
CPPNick
And this piece is entitled, "Disco Underflow"



			if(HW > *zbuff_ptr)			{				*zbuff_ptr = HW;				_HW = 0x400000 / (HW>>8);				pixel_x = (HU>>22 * _HW) & widsub1;				pixel_y = (HV>>22 * _HW) & hgtsub1;				shade = (HS>>22 * _HW);				texbit = textr->bits[(pixel_y<<bshl) + pixel_x];				*screen_ptr = ((((texbit & 0xff00) * shade) & 0xff0000) | (((texbit & 0xff00ff) * shade) & 0xff00ff00))>>8;			}

lolz..
Krypt0n
Krypt0n
Quote:

and you're saying that here:
0x402dd6 idiv esi F7 FE 0.67
0x402dd8 mov [ecx+00000568h],esi 89 B1 68 05 00 00 18.37

the time taken could actually be that div rather than the mov right?
that would I would guess. but again, dont reply on guessing ;), hardcode the ouput index to be always the same and if you get no performance improvement (and the assembly looks damn similar), it's the idiv.

CPPNick
CPPNick
It's kinda becoming a pain now trying to get the right accuracy with fixed point...I really under estimated the usefullness of the floating point.
but on that subject, my far clipping plane in my rasterizer is at 2000 units. about how far does the far clipping plane usually sit in the average engine? Is there a standard maximum extent for meshes like +/- 100 X/Y/Z or something?
Krypt0n
Krypt0n
there is no real relation between farclipping and rasterizer, as the rasterizer is usually set after the projections, so your Z/W is always between 0. and 1.f
it's kinda like an 0.32 fixed point format (or 0.24 for hardware as they use 8bit stencil).

meshes vary also a lot, depends on how ppl interpret float, some say 1.0 is one km, some say it's cm and others dont care as long as the level fits.

but again, your rasterizer shouldn't care, it's after all transformation is done and transformations shall be done in float ;)
CPPNick
CPPNick
Ok, I guess I can make my own mesh rules then and scale things down to make the situation more friendly to my fixed point stuff. When i convert 1/z to fixed, I am shifting 30 bits left to get good enough accuracy, but the mesh extents and farplane are too large and makes complications(under/overflow) when I try to multiply or divide. So Ill probably scale things down and bring my far plane way in. I hear about "stencil" a lot too...I am gonna look that up and see if its of any use to me. Annnywho, besides hand coding the thing in assembly, incorporating some sorting, or trying to figure out how pixomatic does the thing with the 16 pixel spans, I don't see how I can really make this thing much faster without SSE.

Erik Rufelt
Erik Rufelt
I haven't read any of your previous posts so forgive me if I'm saying something not applicable. =)

Do you need/want a z-buffer?
If not, sorting your polygons back-to-front and rendering without depth-testing can often give better results for software rendering.

Also, do you really need three divisions by _HW?
Interpolating 1/_HW and multiplying in fixed point might be better, unless this is what you refer to when you say fixed point isn't accurate enough?

In addition I think that the floating point unit and integer unit of the processor work somewhat in parallell, so it's often possible to do that one division in floating point, while carrying out other integer instructions at the same time, resulting in a much cheaper division.
Same thing with memory latencies, putting reads and writes next to non-dependent calculations can make the latency a non-issue since other instructions are executed during the wait.
ddn3
ddn3
It does sound like your memory bound, the time it takes to fetch and write data is the bottle neck. Have you tried something like this?

http://www.devmaster.net/forums/showthread.php?t=10125

Texture swizzling was developed to improve cache performance for accessing textures. It interleaves texture pixels so they are closer together in memory reducing cache misses, at the cost of increased complexity in the uv calculations.

Good Luck!

-ddn
CPPNick
CPPNick
Quote:
Original post by Erik Rufelt
Do you need/want a z-buffer?
If not, sorting your polygons back-to-front and rendering without depth-testing can often give better results for software rendering.

Ugh..I'm dreading the thought of implementing a BSP and restructuring everything again...but I may just have to. I do use a zbuffer, with no sorting...lazy, I know..but I dont have very complex scenes right now so its not that important yet.

Quote:
Original post by Erik Rufelt
Also, do you really need three divisions by _HW?
Interpolating 1/_HW and multiplying in fixed point might be better, unless this is what you refer to when you say fixed point isn't accurate enough?

here is the problem with that: I tried to make it 1/(1/z) to get z, but let me show you my code so you will see the problem:
//HU and HV start out as 10.22 fixed point, and 1/z(HW) starts out as 1.31 fixed //point._HW = 0x40000000 / HW; // so when i try this here, 1/(1/z), I lose all accuracy, //because for me to keep the accuracy, I have to divide a number that is 8 bits //bigger than HW, which is 1.31, so if I use any bigger numbers, it will then be //doing __int64 math, and I fear that will do more bad then good. Alternatively, //I could bring the far plane in so that 1/z wont be so small, and maybe then I //can get away with 8.24 fixed point or something for 1/z. Then I would have//that extra room and not have "Z" but "Z<<8" after the 1/z divide. Right now I //have pure integer Z multiplied by HU which turns anything at less than 45 //degrees to the camera into an ugly hatched mess. Im sure you can imaging..lolpixel_x = (HU * _HW)>>22 & widsub1;pixel_y = (HV * _HW)>>22 & hgtsub1;shade = (HS * _HW)>>22;




Quote:
Original post by Erik Rufelt
Same thing with memory latencies, putting reads and writes next to non-dependent calculations can make the latency a non-issue since other instructions are executed during the wait.

I thought about this but wasn't sure if it would actually work. I'll give it a go.

Quote:
Original post by ddn3
It does sound like your memory bound

thanks for the link, will check that one out. Me and Krypt0n couldn't decide if it was actually code analyst being inacurrate and puting the time samples on the mov rather than the div or not.

Thx guys, nite
Erik Rufelt
Erik Rufelt
If you remove the z-buffer you also don't have to be at all that accurate with your z-values, so depending on your coordinate system you could probably have z in integer only, or 24.8 or something, which opens for that 1/z optimization.

Do you divide by z every pixel?
Often you can get away with only doing perspective correction every 8 or 16 pixels, and do affine texture mapping in between. If you view triangles at extreme angles there can be some distortion, but it's rare. I would definitely recommend this if possible. You can also check the viewing angle for the triangle, and pick which renderer to use on the fly, so that triangles viewed head on don't even use perspective correction, but just switching to that 8 pixel per perspective correction will probably give quite the speedup without too many artifacts.

I'm not entirely sure how it will work with the shading, I think you are using gouraud shading with a color per vertex or something?
You could skip that for now and get a fast texture mapper first, then try adding lightmaps, which can give you some more control over your lighting, and it might even be faster.

How large textures do you want to support?
If you have for example 256x256 textures, and don't need all too high precision, you can easily have both your U and V coordinates in the same 32-bit variable, one in the upper and one in the lower 16 bits, in 8.8 fixed point. Then interpolate over that, and get the final texture pixel as texture[(uv>>16)&0xff00 + (uv>>8)&0xff], skipping both one whole texture coordinate calculation, and in this particular case the multiplication for the texture lookup.
Stonemonkey
Stonemonkey
This is just my opinion and some discussion on this could be interesting but I don't really agree with some of that Erik Rufelt.

Discarding the z buffer and sorting from back to front:

In doing that, you have the problem that sorting alone is never perfect and will often result in errors, not only in intersecting triangles but also if you have varying sizes of triangles within a scene. Also, it will increase the number of texture lookups and shading calcs required.
Sorting from front to back while using a 1/z buffer can greatly reduce the number of texture lookups and shading calcs and no divide is required for any pixel that fails the depth test.

perspective correction every 8 or 16 pixels:

ok, so it reduces the number of divides for a triangle that is visible, but with triangles that are not visible you still have to do those divides whereas as i mentioned before if you divide by pixel the divide is only done when the pixel passes the depth test and when used with a 1/z buffer and front to back sorting you can greatly reduce the number of pixels that pass the depth test.
There will also be some amount of extra setup and tests required for those 8 or 16 pixel spans and to get them to fit in with the triangle spans.

Lightmaps:

More memory map lookups which is where software rendering struggles, it still involves some interpolation and shading calcs and would probably require bi linear filtering too. It could be good visually but I can't see how it could improve speed.

Interpolate u and v in a single variable:

I don't think that can be done with perspective correction (interpolating u/z and v/z) unless you mean to do it in the 8 or 16 pixel spans but then that's even more setup for the spans.

As I said, that's all just my opinion and I'm not saying what is right or wrong and would be happy to discuss any of it.
CPPNick
CPPNick
Quote:
Original post by Erik Rufelt
If you remove the z-buffer you also don't have to be at all that accurate with your z-values, so depending on your coordinate system you could probably have z in integer only, or 24.8 or something, which opens for that 1/z optimization.

I may not be understanding correctly, but if you meant this as a solution to this line:
Quote:
_HW = 0x40000000 / HW;"

It still wont work. I still need the precision in 1/z because it can be as small as 1/(z of farplane) which is 2000, so 1/2000 = 0.0005
I have squeezed it down to 4.28...but I can't go any lower without really bad underflow. using 1.31 would be fine, except that when I try to get the reciprocal again in fixed point, I would have to divide by a number much larger than 32 bits to get enough accuracy with the Z that I use to multiply back out my U and V.

Quote:
Original post by Erik Rufelt
Do you divide by z every pixel?
Often you can get away with only doing perspective correction every 8 or 16 pixels, and do affine texture mapping in between. If you view triangles at extreme angles there can be some distortion, but it's rare. I would definitely recommend this if possible. You can also check the viewing angle for the triangle, and pick which renderer to use on the fly, so that triangles viewed head on don't even use perspective correction, but just switching to that 8 pixel per perspective correction will probably give quite the speedup without too many artifacts.


I was probably concidering this more than other options because pixomatic actually claims to use it:
Quote:
Originally from http://www.radgametools.com/pixomain.htm
the pixel pipeline, works by generating a list of spans to be drawn for each triangle; each span is no longer than 16 pixels, with floating-point perspective-correct texture calculations performed at each end. The pixel pipeline then draws each span in turn, interpolating linearly from one end to the other, producing results indistinguishable from performing the perspective divide for every pixel, but with much better performance.



Quote:
Original post by Erik Rufelt
I'm not entirely sure how it will work with the shading, I think you are using gouraud shading with a color per vertex or something?
You could skip that for now and get a fast texture mapper first, then try adding lightmaps, which can give you some more control over your lighting, and it might even be faster.

I suppose its possible, because in Quake III Team Arena, there are two lighting options: 1. Vertex Lighting 2. Lightmaps
I guess this means one of them is supposed to be faster or better than the other?


Quote:
Original post by Erik Rufelt
How large textures do you want to support?
If you have for example 256x256 textures, and don't need all too high precision, you can easily have both your U and V coordinates in the same 32-bit variable, one in the upper and one in the lower 16 bits, in 8.8 fixed point. Then interpolate over that, and get the final texture pixel as texture[(uv>>16)&0xff00 + (uv>>8)&0xff], skipping both one whole texture coordinate calculation, and in this particular case the multiplication for the texture lookup.


I think I agree with Stonemonkey on this one because I pre-multiply the U and V with the textures height and width, and that means in using 8.8 fixed point, I get 1.0 * 256 texture = 8 bits, So It would either make my max texture size much much smaller or force me to wrap no more than once per tri. Also, I am using textures up to 512. I probably could use smaller ones with more loops, or just use bilinear filtering. I would LIKE to use bilinear filtering, but I actually had some problems with it last time I tried to implement it:
a picture of the error
I was never able to figure out why this was happening =/ I have that same texture rotated and filtered in a visual basic test project, and it doesn't look like that no matter which angle its at..So Im stumped. I think it may have something to do with the fact that in 3D, it may be actually rendering as if it were moving sideways accross the triangle, in which case the (x+1)(y) pixel would actually need to be (x)(y+1) or something...know what I mean? anyways..not important right now.

Quote:
Original post by Stonemonkey
Discarding the z buffer and sorting from back to front:

Aren't Half Life 2 maps name *.BSP? doesn't that have something to do with them having binary tree data incorporated into the file? I vaguely remember reading that Half Life 2 uses some combination of a BSP tree and ZBuffer at the same time.


edit- I clocked the framerate today using the following, then just outputting whatever is in FPS when the app exits.
frame_start = clock();//frametime = clock() - frame_start;FPS = int(1000.f / frametime);


Results on a 1.6Ghz Gateway M3707 Laptop, expanded memory to 2GB(PC667(5300))

1585 polys @ 640x480 = 33fps
1585 polys @ 800x600 = 27fps
1585 polys @ 1280x800 = 13fps

4084 polys @ 640x480 = 33fps
4084 polys @ 800x600 = 24fps
4084 polys @ 1280x800 = 12fps



[Edited by - CPPNick on May 14, 2009 2:27:50 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.