
Advertisement
Winograd
Member
Content Count
381 
Joined

Last visited
Community Reputation
380 NeutralAbout Winograd

Rank
Member

Regular Expressions help needed
Winograd replied to Scet's topic in General and Gameplay Programming
Quick googling showed up that .NET in fact has the possibility of handling balanced matching by something called balancing groups: http://blogs.pingpoet.com/overflow/archive/2005/03/16/1376.aspx 
Measuring performance of GPU and CPU
Winograd replied to rosicky2005's topic in Graphics and GPU Programming
There is always some overhead associated with each draw. The best way IMHO to do these kind of measurements is to use sweeps. That is, constantly increase some property of your draw (such as the number of triangles) and measure the time of that draw. Plotting these measurements gives you a much better understanding on how the system (cpu and gpu) behaves than just a single measurement. 
Compression algorithm with a fast "region of interest" decompression algo
Winograd replied to paic's topic in General and Gameplay Programming
There is some basic introductory chapters to compression in general and image compression in my thesis on lossless image compression. You can skip the remote imaging part, the techniques are universally applicable. 
Quote:Original post by Trenki I have finished my vertex and clipping pipeline, so I could do some speed tests with my rasterizer. I recommend you to run some simple sweep tests. For example, keep the total rasterized pixels constant by rectangular area with strip of triangles. Vary the number of triangles per frame linearly, starting from 1 or 2 and going up. Notice that you will first be fill limited, and thus increasing triangle count does not have much effect. When the graph starts to climb linearly you are geometry limited and the slope gives you your peak triangle rate. In second test, keep the triangle count constant, but vary the number of rasterized pixels. The slope will give you the peak pixel rate. You can calculate the approximate number clks used per pixel basis and overhead caused by geometry processing. Ideally geometry would be processed in parallel with rasterization.

Quote:Original post by C0D1F1ED Quote:Original post by Winograd Basicly, you don't need frustum clipping if you use homogenous rasterizer. That's a nice property for a hardware implementation, but in software clipping is quite simple and fast. The homogenous rasterizer needs extra work per pixel, which makes it less attractive for software. Clipping is quite fast on hardware also ;) Well I guess your point is that on hardware there is no extra per pixel cost except in the number of gates. I haven't implemented such rasterizer but at quick glance it seems one could apply "DDA"like algorithm which would account to basicly 4 additions per pixel of which one is used for perspective division.

Have you looked at this paper: Triangle Scan Conversion using 2D Homogenous Coordinates It dodges quite nicely many problems related to projection of 3D triangles to 2D, such as, w component being 0. Basicly, you don't need frustum clipping if you use homogenous rasterizer. I definitely recommend you to at least read the paper. Also one idea worth investigating is using hierarchical zbuffer, which may improve performance especially in case of high depth complexity scenes.

center of an arbitrary set of points in 2D
Winograd replied to importer_exporter's topic in Math and Physics
Ok. Lets rewrite it a bit: f(c_x, c_y) = sum_i {(x_i  c_x)^2 + (y_i  c_y)^2} = sum_i {x_i^2 2*x_i*c_x +c_x^2 + y_i^2 2*y_i*c_y +c_y^2} This function has a single minimum and it occurs when the gradient wrt c_x and c_y of the above function is 0: grad_f(c_x, c_y) = [ sum_i {  x_i + c_x} ] = [ N*c_x  sum_i { x_i } ] = 0 [ sum_i {  y_i + c_y} ] [ N*c_y  sum_i { y_i } ] That means that minimizing the distance in least squares sense, is equal to setting: c_x = sum_i{ x_i } / N c_y = sum_i{ y_i } / N where N is the number of points. That is coordinates of the center in this sense are the average of the coordinates of the points. Confusing definition lead to trivial solution :) 
Decided to quickly implement the idea I mentioned previously in this thread: typedef struct sVertex { float x; float y; } vertex; /* Extrudes the given polygon * vin = input vertices (ordered ccw or cw) * size = count of input vertices * vout = preallocated are for output vertices (size+2) * trans = translation */ void extrude(vertex *vin, int size, vertex *vout, vertex *trans) { int minIdx = 0, maxIdx = 0; int startIdx = 1, endIdx = 1; float minC = FLT_MAX, maxC = FLT_MIN; float dot; int i, j, prev, in = 0; /* Find the min and max vertices wrt to translation */ for(i = 0; i < size; i++) { float c = vin.x*trans>y  vin.y*trans>x; if(c < minC) minC = c, minIdx = i; else if(c > maxC) maxC = c, maxIdx = i; } prev = maxIdx==0 ? size : maxIdx  1; dot = (vin[maxIdx].x  vin[prev].x) * trans>x + (vin[maxIdx].y  vin[prev].y) * trans>y; if(dot > 0) /* Starting from maxIdx preserves direction */ startIdx = maxIdx, endIdx = minIdx; else /* Starting from minIdx preserves direction */ startIdx = minIdx, endIdx = maxIdx; in = endIdx < startIdx; /* Are we already at extruded point? */ for(i = 0, j = 0; i < size; i++, j++) { if(in) /* Are we extruding? */ { vout[j].x = vin.x + trans>x; vout[j].y = vin.y + trans>y; } else vout[j] = vin; if(i == startIdx) /* Start extruding */ { j++; vout[j].x = vin.x + trans>x; vout[j].y = vin.y + trans>y; in = 1; } if(i == endIdx) /* Stop extruding */ { j++; vout[j].x = vin.x; vout[j].y = vin.y; in = 0; } } } Much of the branching can be quite easily moved out of the forloop, however, I'll let someone else to do that ;)

center of an arbitrary set of points in 2D
Winograd replied to importer_exporter's topic in Math and Physics
I should point out that the least squares solution is only one of the ways to mathematically describe a point which in some sense is at minimum distance to other points. Equally well one could wish to find the point for which the maximum of distances is minimized, which is also a way to say that a point is close to all the other points. 
center of an arbitrary set of points in 2D
Winograd replied to importer_exporter's topic in Math and Physics
With your definition there is no such point in general. Such point can be found only if the points are located on the arc of a circle. However, perhaps you want a point that minimizes the distances to all other points? Notice, that this requirement reduces to your original definition when the points _are_ on the arc of the circle. You can calculate the center by minimizing sum_i {(x_i  c_x)^2 + (y_i  c_y)^2}, where x_i and y_i are the coordinates of the ith point and c_x and c_y are the coordinates of the center to be found. Google for least squares problem. 
I may be dead wrong about this, but it would seem sufficiently simple to determine the maximum and minimum vertices of the polygon in the direction orthogonal to the translation. You could calculate c = ty*px  tx*py, where (tx,ty) is the translation and (px,py) is a vertex. Then find the maximum and the minimum c. Those will correspond to the vertices forming the two edges of the extruded polygon. In your case vertices P2 and P4 of the original polygon. After these two vertices have been identified the polygons have to be "clipped". By clipping I mean pruning out the vertices which are between the two vertices on the "inside". Inside of the first polygon is the side (tx,ty) is pointing to and for the second polygon it is the opposite direction. Now forming the polygon should be just simply connecting the end points of the pruned nonclosed polygons and thus closing the final polygon. Is this what you were looking for?

Is linear interpolation possible without dividing?
Winograd replied to codingsolo's topic in Math and Physics
Wouldn't it be far more efficient to offload the processing to GPU. Just feed the data to fragment shader as a texture and render to another texture. 
comparing matrices (little statistics experience)
Winograd replied to serratemplar's topic in Math and Physics
You lost me. You talk about distribution fields. Do you mean that you model a pixel so that the first random variable is the pixel itself and the second is the surrounding pixels and you form the 3x3 matrix by sampling the constructed probability distribution? That doesn't sound right, so could you please elaborate what you mean by those 3x3 matrices.. 
comparing matrices (little statistics experience)
Winograd replied to serratemplar's topic in Math and Physics
Based on your grossly simplified description of the problem, you are looking for matrix norm. There are numerous norms for matrices. All of these norms share common properties: Matrix norm, Mathworld Matrix norm, Wikipedia 
Drawing a 2D bezier/BSpline patch
Winograd replied to Majestik_666's topic in Graphics and GPU Programming
Scanline filler

Advertisement