This topic is now archived and is closed to further replies.


Finding the largest rectangle...

Recommended Posts

ShmeeBegek    196
I am currently trying to work out a solution to a problem that really has me scratching my head. I have a height-map sort of thing, and I am trying to "optimize" it by turning (relatively) flat areas into large quads. So what I need to do is find the largest rectangle that fits on a (relatively) flat part of the map, save it, and repeat untill all squares are inside of rectangles. I have been pondering it for a while now and I really can't even come up with a mediocre solution, I would appreciate all input on this. Thanks, ~SPH Edit: By 'flat' I do not mean parallel with the base of the height map, I mean having the same slope. [edited by - ShmeeBegek on March 20, 2004 10:19:43 PM]

Share this post

Link to post
Share on other sites
lonesock    807
I''m guessing this does not have to happen realtime?

OK, here''s an idea:

* compute the normals of each point on the map
* each point also has a "used me already" flag
* start with a seed point (random, or try them all for a nasty brute force approach, or every other one [checkerboard style], etc.)
* you now have a 1x1 rectangle
* going through each edge consecutively (North E S W N E...)
--see if that edge can be extended (all points are within an error of the seed point''s normals: use a dot product, and the points should not have been useed already)
--if the edge can be expanded, then do so (i.e. if North (N) was OK, then you now have a 1x2 rectangle)
--keep repeating these two steps until no more edges can be added
* now you could use the area of the resulting rectangle as a score for a given seed point.
* at this point you mark all the points within the rectangle as used, store the quad, and move on.
* you may want to reject or stop when the best rectangle falls below a threshold)

Note: you could do multiple samples at each stage, then just pick the best seed point before proceding

another alternative is to just use some standard automatic mesh reduction algo, but then you are probably dealing with tris instead of quads.

BTW, this seems like the kind of thing the image compression people do all day long, so some of their resources might be handy.


Piranha are people too.

Share this post

Link to post
Share on other sites
haro    502
This is a fairly typical form of LOD or level of detail. If you want to go full scale then you can google for ROAM or Realtime Optimally Adapting Meshes. Anyhow, for what you want to do: It is view dependant. If you are extremely far away from a series of points, those points will often appear to be a relatively straight line, even if they are quit jagged. So, it might make more sense to do this real time.

One easy test is to project the object space coordinates of a specific group of points, into screen coordinates. Check the distance between the furthest points.. in screen space coordinates. This will tell you how many pixels the points will represent in screen space. If it is fewer than some constant you define, then you could convert the series of points into a higher level abstraction. IE- turning 2 tri''s into a quad, turning 2 tri''s into a single tri, etc..

Share this post

Link to post
Share on other sites