Subject:
|
Re: Implicit face winding (was: [Parts Tracker] More BFC Primitives)
|
Newsgroups:
|
lugnet.cad.dev.org.ldraw
|
Date:
|
Fri, 12 Apr 2002 06:55:17 GMT
|
Viewed:
|
1026 times
|
| |
|
|
> Tony Hafner wrote:
> > {Tony's ranting snipped by Tony}
> I aggree. I wasn't really discussing the winding of
> each polygon anymore. I think we moved on a while back.
> Steve even aggreed that once the winding of the polygons
> was known, converting the files to a standard winding
> (if one were to be selected) would be relatively easy.
> Most of the recent discussion has only been on the usage
> of INVERTNEXT not about CW vs. CCW
My bad- I guess I wasn't following the thread closely
enough.
> > Something else just occurred to me... how hard would it
> > be to write an auto-BFC program? Assuming that parts
> > don't have holes, all interior surfaces *should* be
> > sealed in. You could divide up the whole thing with a
> > BSP tree and use that info to determine which faces
> > should face which way. It wouldn't get all parts right,
> > but would certainly hit a good chunk of them. And the
> > program could at least flag most of the bad ones as such.
> > You'd just run it once on the whole library (whole parts
> > anyway- subparts aren't typically sealed) and then
> > visually inspect the results.
> Auto BFC? I've been working on that problem myself for a
> little while now. I have an aquaintance who believes he
> may be able track down some code from some gradstudent
> project he once knew of that he thought attempted to solve
> that problem.
>
> I haven't tried to code this up, but I think if you
> computed the true 'center coordinates of a part, then cast
> a 'ray' out from there towards a polygon, then the first
> polygon you pass thru should face that center, the next
> away from that center, the third toward that center, etc.
> That is unless we have parts whose walls are modeled with
> only a single polygon??
If I understand correctly, that doesn't really work for a
huge percentage of parts. Parts will often have two
surfaces in a row that both face away. Look at the
breakdown of a 2x4 brick: there is a flat surface over the
whole top, and the studs sit on top. Your ray would tag the
top inside surface as a "facing inwards" surface (correct),
the top outer surface as facing outwards (correct), then the
top of the stud as "facing inwards" (incorrect). Besides,
you have to at some point mechanically determine an inside
point.
> I need to read up more on this BSP stuff. I'm not sure how
> that would work.
{Warning: I'm not really fluent here- I get these concepts,
and am pretty sure they can apply, but I am talking somewhat
above my own head.}
Essentially, the whole 3D space that encloses the part (use
a bounding box on the overall dimensions) is divided up into
convex shapes. Where two adjacent shapes (ie they share a
common side) are not divided by a polygon, they make up a
contiguous region. Any nodes that are contiguous with the
surrounding space are "outside", and any other nodes are
"inside". Faces that are towards "outside" need to be wound
to be seen from that side. If a part truly models the real
part, there should be *very* few cases where a polygon is
visible from both sides.
The tricky part is to actually break the region into those
convex shapes.
Note that the part would have to be "sealed" properly for
this to work. To determine contiguous nodes, you have to
look from a given node at all its neighbors. If you can see
into the other node through any opening, it appears to be
on the same side. The good part about this is that both
sides of the same surface get marked as "outside", which is
clearly an error and the part can get flagged as such. As a
bonus, if both sides of the surface get marked as "inside",
you know you've got a surface that is completely buried and
can be thrown out.
I may need some pictures to make this clear, but I can't
dive into that right now. I've got a friend who knows a
good bit about the BSP guts and can tell me if I'm totally
high- I'll talk to him before I rant much more about this.
> > Not that *I* could write the program, but the actual
> > problem doesn't seem significantly different from one
> > I've dealt with before. I used to make Quake levels, and
> > they have a compile tool that determines what space is
> > inside (and can be gotten to) versus what space is outside
> > (such that you'd never be able to get there). I know a
> > bit about the guts of this, and could possibly help
> > someone who already knows how to code 3D processing stuff...
> Like I said I'm trying to write code that can do this and
> other things with the part geometry automatically right now.
> I'll let you know when I have something, maybe you can beta
> test it?
I'm interested- just let me know when you have something, and
I'll take a look if I have time at that point.
> Currently I'm focusing on searching the geometry for
> polygons that can be transformed into 'polygon strips' Most
> 3D hardware and rendering engines are designed to process
> strips of quads or triangles much faster than they can handle
> single ones. I think I may have a good handle on this problem
> already I just need to finish coding it up.
Sounds reasonable so far, though I no next to nothing about
hardware.
> It may not be fast though, so I'm hoping to maybe get it to
> write the .DAT files back out with '0 STRIP' hints. Would
> this group be interested in having those types of hints in
> the parts library? I'm guessing it would mean re-certifying
> every part in the library again right? That seems like alot
> of work from what I've read here.
Yes, that would involve recertifying the parts. I'm thinking
that isn't likely to happen any time soon.
> Another thing I'd like to do is write some code that can try
> to automatically determine which polygons in a part are
> 'inside' it and likely to be covered up by another part when
> they're connected. That's a problem for another day though.
Yes, one step at a time. But that does sound like it has a lot
of potential.
--
Tony Hafner
www.hafhead.com
|
|
Message is in Reply To:
21 Messages in This Thread:
  
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
