• Create Account

# pinknation

Member Since 19 Apr 2007
Offline Last Active Aug 14 2012 10:25 PM

### Triangulation of Sliced Triangle Hull, and some good algorithms.

09 August 2012 - 12:45 AM

So, I have a picture here that will help a lot with my question:

excuse the poor drawing if possible, anyways, the point here is that if I have a convex hull such as in Diagram 1, the teapot, and I slice on on that red line, from the top-down view, the slice points(otherwise the inverse of the plane) will look like that in 2D. is there any good triangulation algorithms which can a) support holes, and b) support edges/points seperated from each other creating sub polygons, but all within the same triangulation sweep;

this is important, and any information would be great, I am capable of learning, but looking for something more open-source that i can try and understand better then a PDF, but anything will do

### GLSL Problems...

26 January 2010 - 01:27 PM

// wave functions ///////////////////////
struct Wave {
float freq;  // 2*PI / wavelength
float amp;   // amplitude
float phase; // speed * 2*PI / wavelength
vec2 dir;
};

#define NWAVES 2
Wave wave[NWAVES] = {
{ 1.0, 1.0, 0.5, vec2(-1, 0) },
{ 2.0, 0.5, 1.3, vec2(-0.7, 0.7) }
};

float evaluateWave(Wave w, vec2 pos, float t)
{
return w.amp * sin( dot(w.dir, pos)*w.freq + t*w.phase);
}

// derivative of wave function
float evaluateWaveDeriv(Wave w, vec2 pos, float t)
{
return w.freq*w.amp * cos( dot(w.dir, pos)*w.freq + t*w.phase);
}

// sharp wave functions
float evaluateWaveSharp(Wave w, vec2 pos, float t, float k)
{
return w.amp * pow(sin( dot(w.dir, pos)*w.freq + t*w.phase)* 0.5 + 0.5 , k);
}

float evaluateWaveDerivSharp(Wave w, vec2 pos, float t, float k)
{
return k*w.freq*w.amp * pow(sin( dot(w.dir, pos)*w.freq + t*w.phase)* 0.5 + 0.5 , k - 1) * cos( dot(w.dir, pos)*w.freq + t*w.phase);
}

uniform float time = .0;
uniform float waveAmp = .15;
uniform float waveFreq = .5;

void main()
{
wave[0].freq = waveFreq;
wave[0].amp = waveAmp;

wave[1].freq = waveFreq*2.0;
wave[1].amp = waveAmp*0.5;

vec4 P = vec4(gl_Vertex);
P.y = 0.0;
float ddx = 0.0, ddy = 0.0;
for(int i=0; i<NWAVES; i++)
{
P.y += evaluateWave(wave[i], P.xz, time);
float deriv = evaluateWaveDeriv(wave[i], P.xz, time);
ddx += deriv * wave[i].dir.x;
ddy += deriv * wave[i].dir.y;
}

vec3 B = vec3(1, ddx, 0);
vec3 T = vec3(0, ddy, 1);
vec3 N = vec3(-ddx, 1, -ddy);

gl_TexCoord[0]  = gl_TextureMatrix[0] * gl_MultiTexCoord0;
gl_TexCoord[1] = gl_TextureMatrix[0] * gl_MultiTexCoord0;

gl_Position = gl_ModelViewProjectionMatrix * P;
}

sampler2D TextureUnit0;
sampler2D TextureUnit1;
float scale = 5.0;

void main()
{
vec4 c1 = tex2D(TextureUnit0, gl_TexCoord[0].st * scale);
gl_FragColor = c1;
}

If i was to change "gl_FragColor = c1;" in my fragment shader to "gl_FragColor = vec4(1, 0, 1, 1);" the waters' surface, as this shader simulates, will become animated, however, without changing that line to some hard-coded color(not obtaining the color from texture2D), it becomes frozen, and doesn't move.

[Edited by - pinknation on January 27, 2010 1:00:59 PM]

### NN-Search Problems for Fluid Dynamics / Collision

08 October 2009 - 05:33 PM

Hi there, I've been writing a "Particle Based Hydrodynamics" engine, in C++ using SSE for optimization.. SSE increased the speed a lot, but in the end things began to slow down do to O(N^N-1) collision detection, so I've decided to implement the kd-tree, so far I've been un-able to properly write the Nearest Neighbor search, and am beginning to have issues w/ kd-tree all together, because the wikipedia doesn't describe the proper way to 'balance' the tree(because none of my tree leafs should remain static, the tree should be re-balanced every frame, for optimization); I could do this the 'brute' way which starts from the root, and balances the tree.. just like I did to build it(using axis based median sorting); though that seemed like it maybe slow?? (of course it should still be faster then re-building the entire tree.. which im currently just doing every-frame LOL) I'm wondering if anyone knows of a better solution than kd-tree, and otherwise, if someone could help explain nearest neighbor search.. my current NN-search is like this:
void find_neighbors(SSEBoundingSpheres &spheres, kdnode* node, kdnode *cnode, std::vector<int> &neighbors, float r, float min_dist = FLT_MAX)
{
if( node == 0 || cnode == 0 ) return;

if(cnode->id != node->id)
{
float dir;
if(node->axis == 0)
dir = (spheres.position_x[node->id].m[0] - spheres.position_x[cnode->id].m[0]);
else if(node->axis == 1)
dir = (spheres.position_y[node->id].m[0] - spheres.position_y[cnode->id].m[0]);
else if(node->axis == 2)
dir = (spheres.position_z[node->id].m[0] - spheres.position_z[cnode->id].m[0]);
if(dir < 0.0)
{
find_neighbors(spheres, node, cnode->left, neighbors, r);
if(dir*dir<r)
{
neighbors.push_back(cnode->id);
find_neighbors(spheres, node, cnode->right, neighbors, r);
}
} else {
find_neighbors(spheres, node, cnode->right, neighbors, r);
if(dir*dir<r)
{
neighbors.push_back(cnode->id);
find_neighbors(spheres, node, cnode->left, neighbors, r);
}
}
}
}

which is a recursive function, and doesn't appear to properly find all contacts.. actually the radius is greater than all the particles, so during the initial NN-Search I should see all of the particles as neighbors, but I don't.. ;_; thanks to anyone who can help resolve this. =]

### Optimized Collision Detection & Physics

17 August 2009 - 03:54 PM

Hi, my simulation is slowing down @ 200 particles, this mainly was because of the collision detection at first, where every particle, checked for collision against every other particle, meaning 200 * 199 iterations were processed each frame(along side the F = GMm/R^2 equation, which made it slower), I was able to speed this up, by implementing a spatial index grid.. which allowed me to only check for collision of neighboring particles(within the same grid cell), however the force calculations are still gathering a total(because that's most accurate.. perhaps I dont have to?) and so ending up w/ 200 * 199 iterations, still.. is there any way to speed up the math here, and any suggestions for other optimizations?

" for(int i = 0; i < particles_length; ++i)
{
if(particle.id == particles[i].id) continue;
float d_x = particles[i].p_x - particle.p_x;
float d_y = particles[i].p_y - particle.p_y;
float R = sqrt(d_x * d_x + d_y * d_y);
float F = G * particle.mass * particles[i].mass / (R * R);
if(R == 0.f || F == 0.f) continue;
particle.f_x += d_x * F / R;
particle.f_y += d_y * F / R;
}"

that adds the gravitation force of F = GMm/R^2.

my collision code is:
vector<int> idxs = grid->GetNeighbourIndex(particle);
for(unsigned int j = 0; j < idxs.size(); ++j)
{
int i = idxs[j];
if(particle.id == particles[i].id) continue;

double cNorm = atan2(particles[i].p_y - particle.p_y, particles[i].p_x - particle.p_x);
double nX = cos(cNorm);
double nY = sin(cNorm);

double a1 = DotProduct(particle.v_x, particle.v_y, nX, nY);
double a2 = DotProduct(particles[i].v_x, particles[i].v_y, nX, nY);
double optimisedP = (2.0 * (a1-a2)) / (particle.mass + particles[i].mass);

float d_x = particles[i].p_x - particle.p_x;
float d_y = particles[i].p_y - particle.p_y;
float R = sqrt(d_x * d_x + d_y * d_y);

{

// force both particles out of one anothers radius

// Reflect Velocities
particle.v_x -= (optimisedP * particles[i].mass * nX) * .5f;
particle.v_y -= (optimisedP * particles[i].mass * nY) * .5f;
particles[i].v_x += (optimisedP * particle.mass * nX) * .5f;
particles[i].v_y += (optimisedP * particle.mass * nY) * .5f;
}
}

which I hope can also be optimized in some way.. (mostly took that code from somewhere on this site I think);

Side-Question: I'm having one particular issue w/ collision detection, which is, it 'un-collides' all current collisions, though sometimes creates more 'collisions' before its unable to sweep it again, resulting in physics related issues(where the particles are to close, and blast off at some really high velocity), my order of computations is AddTotalForces, Update Particle, Collision Sweep.. any ideas how to fix this..? >.> unless I like had something recursive to constantly un-collide particles, until there are none colliding, I cannot think of any way to solve that.. so.. any suggestions here would help!

### SDL/OpenGL Texture Distortion [ bug * ]

01 April 2009 - 07:25 AM

I know that OpenGL prefers image that are a power of 2 in size, though none of the images are, they seem to be loaded, and rendered appropriately. The button texture, would be the one causing the problem. You can see for yourself in the screen-shot below: It -should- render fine, seeing as everything else does.. I don't see why the button does not. SpriteBatch Drawing Method - 2D Drawing for GUI:
void SpriteBatch::DrawImage(Texture2D img, RectF offset, RectF rectangle, Color color)
{
if(img.Surface != NULL)
{
zOrder += 0.001f;

Vector4 c = color.ToFloatRGBA();

glBindTexture( GL_TEXTURE_2D, 0);
glBindTexture( GL_TEXTURE_2D, img.TextureID );
glColor4f(c.X, c.Y, c.Z, c.W);

glTexCoord2f( offset.X, offset.Y ); // 1
glVertex3f(rectangle.X, rectangle.Y, zOrder );

glTexCoord2f( offset.X + offset.W, offset.Y); // 2
glVertex3f(rectangle.X + rectangle.W, rectangle.Y, zOrder );

glTexCoord2f( offset.X +  offset.W, offset.Y + offset.H ); // 3
glVertex3f(rectangle.X + rectangle.W, rectangle.Y + rectangle.H, zOrder );

glTexCoord2f( offset.X, offset.Y + offset.H ); // 4
glVertex3f(rectangle.X, rectangle.Y + rectangle.H, zOrder );
glEnd();
}

The fallowing code is used withen the Texture2D Class to generate a OpenGL Texture-ID: Note: Inside this code you'll see some commented out code, where I had tried resizing the image to a PowerOf2 friendly texture, before generating the ID.
void Texture2D::GenerateTextureID()
{
SDL_Surface *tmp = Surface;
bool resized = false;
/*
if ( (tmp->w & (tmp->w - 1)) != 0 || (tmp->h & (tmp->h - 1)) != 0 )
{
// Resize image to a power of 2
int w = MathHelper::NextPowerOf2(tmp->w);
int h = MathHelper::NextPowerOf2(tmp->h);
Graphics::ResizeImage(tmp, Surface, w, h);
resized = true;
ShowDebug("ImageSize { Old = (%i, %i), New = (%i, %i) } Texture.cpp Line 104;", Surface->w, Surface->h, tmp->w, tmp->h);
}
*/

// Somtimes the surface may not be initialized.. so we can just discontinue
if(tmp == NULL)
return;

GLenum texture_format;
if (tmp->format->BytesPerPixel == 4)
{
#if SDL_BYTEORDER == SDL_BIG_ENDIAN
texture_format = GL_BGRA;
#else
texture_format = GL_RGBA;
#endif
} else if (tmp->format->BytesPerPixel == 3)
{
#if SDL_BYTEORDER == SDL_BIG_ENDIAN
texture_format = GL_BGR;
#else
texture_format = GL_RGB;
#endif
} else if (tmp->format->BytesPerPixel == 1)
{
texture_format = GL_RGBA;
ShowDebug("Warning: BytesPerPixel = 1; No action taken..\n", tmp->format->BytesPerPixel);
}
else	// Shouldnt have any more of those pesky 1 BytePerPixel problems!
{
ShowDebug("Warning: Color format unrecognized; (Bytes-Per-Pixel: %d)\n", tmp->format->BytesPerPixel);
}
glGenTextures( 1, &TextureID );

glBindTexture( GL_TEXTURE_2D, TextureID );
glTexParameteri( GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR );
glTexParameteri( GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR );
glTexImage2D( GL_TEXTURE_2D, 0, tmp->format->BytesPerPixel, tmp->w, tmp->h, 0, texture_format, GL_UNSIGNED_BYTE, tmp->pixels );
if(resized)
SDL_FreeSurface(tmp);
}

Both snippets of code are vital in preparing the image, to be drawn, as well as drawing it. This method is working (from what you can see in the screen-shot) for several other images, except the last where the 'button' has become distorted. I am not understanding the problem here.. Though if I had to 'guess' it appears the SDL_Surface's width is slightly greater than the actual image width; I've checked several different possible resolutions, but neither have solved the problem I'm having. Any in-sight would be appreciated!

PARTNERS