point inside convex quad, using only integers?

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

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 on other sites
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 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 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;
}


• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 15
• 14
• 46
• Forum Statistics

• Total Topics
634067
• Total Posts
3015323
×