Subject:
|
Re: Checking for bowtie quads?
|
Newsgroups:
|
lugnet.cad.dev
|
Date:
|
Thu, 30 Mar 2000 03:27:56 GMT
|
Viewed:
|
1706 times
|
| |
|
|
In lugnet.cad.dev, Don Heyse writes:
> In lugnet.cad.dev, Fredrik Glöckner writes:
> > "Don Heyse" <dheyse@hotmail.spam.go.away.com> writes:
> >
> > > Lar's L3Input.cpp is in the latest ldglite source (which is
> > > available at the usual place). It contains the bowtie checking
> > > code and is quite nice.
> >
> > Thanks, I've got it! I didn't know the check was that involved,
> > though...
>
> Yeah, I tried to think of a simpler way to do it myself. But all my
> ideas required converting the quad from 3D coords to 2D coords first so
> my feeble brain could handle it. :^)
Wow, I'm glad I revisited this since I think I can save some rendering
time by saving the vertex normals from the bowtie checks for the
OpenGl lighting phase in LdGLite.
Here is the algorithm I came up with before I decided to use the L3
code as is. I had kinda given up on it since I only had it figured
out for 2D screen coords. The trick of using the dot product to
determine if the cross product vectors pointed in the opposite
direction eluded me until I saw Lars' code. (You don't need it in 2D
since the normals have only a z component and it's sign determines the
direction of the turn).
I think this is pretty similar to the method in L3.
Calculate the normal vector for each vertex in the quad using the
cross product. (We can use these again later for lighting, cool!)
Eliminate colinear points (i = j = k = 0 in the normal). Make a
triangle if only one. Discard the quad if more than one. Either way
you're done if you found any colinear points.
For each vertex calculate the dot product of its normal with the
normal of the first vertex. The sign determines whether the
turn at that vertex is clockwise or counterclockwise.
If you get 3 similar turns and 1 opposite turn then you have a concave
point at the oddball turn. Split the quad into 2 triangles at that
point and you're done.
If you have 2 clockwise and 2 counterclockwise turns then you have
a bowtie. Find the first two adjacent vertices with the same turn,
swap them, and you're done.
Otherwise you must have 4 similar turns and an nice simple convex
quad.
Pretty neat, eh? And it's not all that complicated after all...
Don
|
|
Message has 1 Reply:
 | | Re: Checking for bowtie quads?
|
| It's funny but two weeks ago, I developed exactly this method, the one with the cross products, and all the findings you got, too. (...) Isn't 3D math a wonderfull thing P.S. Maybe if I would have look at someone elses code or book, my life could (...) (25 years ago, 30-Mar-00, to lugnet.cad.dev)
|
Message is in Reply To:
| | Re: Checking for bowtie quads?
|
| (...) Yeah, I tried to think of a simpler way to do it myself. But all my ideas required converting the quad from 3D coords to 2D coords first so my feeble brain could handle it. :^) Don (25 years ago, 29-Mar-00, to lugnet.cad.dev)
|
8 Messages in This Thread:
 
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
