Archived

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

coreyw

getting outside boundary of overlapping wireframes

Recommended Posts

Hi All, I've got a series of (possibly) overlapping wireframed rectangles. Can anyone refer me to any code snippets that I can use to be able to draw the resulting outline of the writeframes (as viewed from 'above')? This reeks of hidden line removal of the 'internal' borders and an application of the Painter's Algorithm, but I'm only interested in the outlying boundary of the combined rectangles. I know the z-order of the rectangles so that helps. I thought I would just iterate through all the rectangle sides (against each other) to find out which sides intersect then use that to determine 'a' boundary - but not 'the' boundary I need. But this seems to simple to apply here. Thanks for any advise. Corey. [edited by - coreyw on October 16, 2003 7:37:04 PM]

Share this post


Link to post
Share on other sites
Corey,

If all you''re looking to do is draw the outline then your question is best posted to the OpenGL or Direct3D forums. They will be able to help devise a pure rendering approach.

Given that your geometry is flat, you wouldn''t be able to use some of the clever NPR shading techniques. There are some clever techniques there, but they kind of need smooth, curved geometry to find the edges.

My take is that you can use the stencil buffer. This approach will work (I think---haven''t tested it) if and only if the pixels where the outline is to be drawn have only been filled once by rectangles. Something like this:

1. enable stencil test.

2. first pass. clear stencil buffer. set stencil operation to *increment* the stencil value at a pixel that is drawn. Set it up to increment on pass only. And setup the stencil test to pass always. Now draw your filled rectangles. When you''re done, pixels for those bits of rectangles that fall along the edges will have a stencil value of 1. Overlapping areas will have stencil > 1, and noncovered areas will have stencil = 0.

3. second pass. set stencil test function to pass when the stencil value is exactly equal to 1. Set the stencil operation to keep the existing stencil value. now, draw *lines* around *all* of the rectangles. Full rectangle outlines for everything. You''ll only get the outlines since only those pixels around the outlines will have stencil values = 1.

Now, this isn''t perfect. It fails if any part of the real outline is covered by more than 1 rectangle. This can be the case of two identical rectangles one on top of the other. You will also be missing pixels at concave corners in the outline.

But, at least this is a start. Take it to the graphics forums to get a better solution.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Thanks Graham,

Sorry, I should have been more explicit. I'm not drawing the outline to 'a display', I need to build the outline as a series of line segments and write it out for a separate presentation program to render it.

If OpenGL, etc., has an API that takes these guys in and allows me to get the results out, which I can send down the line, that would be great. Please let me know if this is the case.

Corey.

[edited by - coreyw on October 17, 2003 5:01:02 PM]

Share this post


Link to post
Share on other sites
Can the rectangles be roatated, or are they always aligned with the axis? If they always intersect at 90 deg then I think an optimized routine could be done pretty easy. Also - can we assume that one is never contained totally within another? Any other assumptions can simplify the process.

Share this post


Link to post
Share on other sites
getting the overlaping regions of two rectangle/triangle/convex shape is pretty straight forward (standard clipping techniques). You use on of the shape (lets call it the clipper), and cut the other polygon with infinte lines passing through the edges of the clipper. You do the edge cutting one by one (as many as there are edges in the clipper) recursively, and you should end up with the overlaping region(s).

now, for the silhouette, instead of discarding the edges outside the clipping region, you store them into a bin. As you cut what's left of polygon B with planes from polyogn A, you keep storing which fragments have been rejected. In the end, you'll end up with segments for the silhouette of polygon B from outside polygon A.

Then you do the same process, now using polygon B as the clipper, and the edges of segment A. that will give you the silhoutte of polygon A from outside polygon B.

the two lists of segments should give you the outline of both triangles, without the overlapping bits.

[edited by - oliii on October 17, 2003 8:51:51 PM]

Share this post


Link to post
Share on other sites
Thanks again for the replies people. Please forgive me as I'm not a graphics hack, but a very experienced software engineer.

MaggotX: all the rectangles may or may not be overlapping. They can't be rotated without losing their 'meaning' with respect to each other.

Oliii: maybe I didn't understand your reply, but the end result has to be a list of line segments defining the silhouette. Does what you describe still accomplish that?

Let me try and share what I have worked out already:

Essentially, I have a series of rectanges with coordinates defined for all 4 corners in an x-y plane. What I have tried to work out is that if they are defined sequentially, I've used the ordinality of the definition as a 'furthest-to-closest' position in the z-plane.

Then I started 'at the back', and do a simple line intersection calculation of all of the intersecting edges between the current rect and the next one 'up' in the stack. Armed with the 2 rects endpoints, and the intersection points (and which two lines make up the intersection) I can derive a silhouette of line segments.

The combined 'shape' is then taken as whole and re-evaluated in the same way the to the next rectangle in the stack. And so on...

Obviously, the speed of the building of the intermediate silhouette degenerates drastically as the number of rectangles increases. But, I think this will work (and the number of rectangles shouldn't exceed a few dozen).

And I still have the address the issue of the storage non-overlapping rectangles as part of the silhouette. I think what it means is that everytime I find a disconnected rectangle, I have to evaluate it as another intermediate silhouette. But, at least I think completely-hidden rectangles is covered by the above.

Please feel free to critique this approach since, as I said, I'm not a mathematician or a graphics guy, and there's probably a better way to do this.

C.


[edited by - coreyw on October 18, 2003 2:53:49 AM]

[edited by - coreyw on October 18, 2003 2:56:50 AM]

Share this post


Link to post
Share on other sites
yes, you can achieve that with the clipping algorithm, but it will add extra segments, as it is effectively a bsp partition. If the rectangles are disconnected, the silouhette will be the same two rectangles, as the clipped rectangle is rejected totally by the clipper. However, it relies on both shapes to be convex, so it sont work if you want to clip the results from, two rectangles with another rectangle.

HOWEVER if you clip each rectangles with all the other rectangles successively, you'd get the list of segments for each windows. To make the algorithm more efficient, you need a method to merge two aligned and connected segments into one long segment, because the successive slpitting will create extra small segments.

Also, the benefit of using a clipping algorithm like this is that you can also clip the final silhouette with windows that would obscure the silhouette or the parent window, so the silhouette does not get drawn outside the parent boundary. It's just a matter of specifying if the window you use for clipping should keep segments outside it or inside it.

a little drawing would help



//-----------------------------------------------------

// function

// segmments Clip(segmments B, clipper A, bool bMode)

//

// clips a list of segments with a convex clipping region

// returns the list of segments outside or inside the clipping region, depending on the mode

//-----------------------------------------------------


//-----------------------------------------------------

//

// function

// segmments Clip(segmments B, clipper A, int iEdge, bool bMode)

//

// clips a list of segments with one of the edge of the clipping region

// returns the list of segments outside or inside the clipping edge, depending on the mode

//-----------------------------------------------------


original
--------
+---------------------+
| A |
| |
| +-----|----------+
| | | B |
+---------------------+ |
| |
| |
+--------------- +


// first split B' = Clip(B, A, 1, false)

//---------------------------------------


+---------------------+
| A |
| |
| |
| |
----------------- ---------------+----- ----------+----
| B'|
| |
+--------------- +



// second split B' = Clip (B, A, 2, false)

//---------------------------------------

|
|
+---------------------+
| A |
| |
| +----------+
| | B'|
+---------------------+ |
| |
| |
+--------- +
|
|

// third split Clip (B, A, 3, false) = NULL

//---------------------------------------


---------------+---------------------+--------------
| A |
| |
| |
| |
+---------------------+

// fourth split Clip (B, A, 4, false) = NULL

//---------------------------------------


|
|
|
+---------------------+
| A |
| |
| |
| |
+---------------------+
|
|
|

// result b = B' | B' | NULL | NULL = B' | B'

//---------------------------------------------


+----------+
b |
+
| |
| |
+-----+--------- +

// merging colinear edges b' = merge(b)

//---------------------------------------


+----------+
b'|
|
| |
| |
+--------------- +





if you have a third window, you Clip(b', C, false) with that window, which should give you a smaller list of segments.

If you keep doing that with all the other windows, you'll end up with the final slihouette for B.

To get the silhouette for A, you do Clip(A, B, false), ect for all the windows. So you do that for every windows in the list.

If you have an overlapping window, overlapping the slihouette, pass its rectangle as a clipping region to the final silhouette, to stop the silhouette being rendered on top of the window.

If one of the window you test against is, say, a parent window, where the silhouette for B should not be drawn outside the window, you do a Clip(b', Parent, true). That should cut away all segments outside the parent window, instead of keeping them.

the result should be something like this

   

original
--------
+---------------------+
| A |
| |
| +-----|----------+
| | | B |
+---------------------+ |
| |
| |
+--------------- +


// result of Clip(B, A, true)

// Clip(B, A, true) = Clip(Clip(Clip(Clip(B, A, 1, true), A, 2, true), A, 3, true), A, 4, true);

//-----------------------------



+-----+
| B
+




to summarise,

Clip(A, B, false) = Merge(Clip (A, B, 1, false) | Clip (A, B, 2, false) | Clip (A, B, 3, false) | Clip (A, B, 4, false));

also

Clip(B, A, true) = Clip(Clip(Clip(Clip(B, A, 1, true), A, 2, true), A, 3, true), A, 4, true);

in the end, you should get a nice outline for your rectangles, windows that overlap the silhouette should mask the part of the silhouette that they overlap, and you can restrict the silhouette to one or several rectangular region on screen.

you can do some funk stuff like that, using other convex shapes such as triangles, hexagons, octagons, or tesselating (converting to triangle) non-convex shapes like stars and fonts, and flagging the tesselation edges as being non-renderable, but they will still be part of a clipping region. You can merge two clipped regions together, so effectively, you mask whole areas of the screen, like a 2D font package would do. You could do this on filled polygons too, but you'd have to stop using edges and tesselate the resulting polyons, as they are likely to be non-convex.

[edited by - oliii on October 18, 2003 10:44:53 PM]

Share this post


Link to post
Share on other sites