• Advertisement
Sign in to follow this  

point inside convex quad, using only integers?

This topic is 750 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I'm writing an adventure game for DOS, don't ask why, its because I like to torture myself. I'm working on pathfinding and I need a way to figure out if a point is in a convex quad, but here's the catch: processors prior to the 486dx which my game targets (specifically a 286 or 386sx) had no builtin floating point support, this makes anything using floating point extremely slow, unfortunately most of the algorithms I've seen use floating point. Any know how I might do this?

 

EDIT: I should mention that this is all using 2D co-ordinates.

Edited by ic0de

Share this post


Link to post
Share on other sites
Advertisement
Fixed point math. Fixed point is just fancy integer math in different units.

For a 2’s complement 32-bit integer, you can represent the integers from 2^-32 to 2^32-1. Or, 2^0 to 2^31 with a sign bit.
A fixed float works in a similar manner, but by sliding the scale: 2^(0-N) to 2^(31-N) with a sign bit.

The math involved has a few extra steps, but it’s probably less costly than to use floating point math (on the target hardware, that is).

Share this post


Link to post
Share on other sites

For starters, have a look at something like a triangle rasterizer that uses fixed precision math.

 

That being said, I'm sure you can hack your way to an approximate result by either:

 

1) scaling the triangle up to the point where you compensate for floating point precision

2) using fixed point arithmetic that you'll have to google for

 

However, if you don't have too many test, then as a solid alternative you can essentially do an occlusion query pass: draw the triangle into a color buffer using a fixed point algorithm (your options are essentially a scanline or a barycentric approach) and test if the pixel at the point's coordinates is shaded or not.

 

Edit: you mentioned you have a convex shape, which is trivially divisible into triangles, which you'll want to deal with regardless of whether you're doing it fixed point or not.

Edited by irreversible

Share this post


Link to post
Share on other sites

So here's what I managed to do, I get the sign of the determinant for each edge and make sure all the edges have the same sign if they do then the point is in the quad. Seems to work ok so far.

bool pointInBox(quad q, point p)
{
	point* v = q.vertices;
	
	bool d0 = ((int32_t)(v[1].x - v[0].x) * (int32_t)(p.y - v[0].y)) > ((int32_t)(v[1].y - v[0].y) * (int32_t)(p.x - v[0].x));
	bool d1 = ((int32_t)(v[2].x - v[1].x) * (int32_t)(p.y - v[1].y)) > ((int32_t)(v[2].y - v[1].y) * (int32_t)(p.x - v[1].x));
	bool d2 = ((int32_t)(v[3].x - v[2].x) * (int32_t)(p.y - v[2].y)) > ((int32_t)(v[3].y - v[2].y) * (int32_t)(p.x - v[2].x));
	bool d3 = ((int32_t)(v[0].x - v[3].x) * (int32_t)(p.y - v[3].y)) > ((int32_t)(v[0].y - v[3].y) * (int32_t)(p.x - v[3].x));

	return d0 == d1 &&  d1 == d2 && d2 == d3;
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement