Sign in to follow this  
rgirard413

Octree/Polygon splitting

Recommended Posts

Im not sure if this is the right forum. My question is, how would i go about implementing a way to split a polygon that goes through a node of an octree, but the vertices arent actually in that node. Or any case where you might be testing one particular node, and dont want to miss a triangle because of geometry ending up in another node. Thanks for any insight

Share this post


Link to post
Share on other sites
I don't know how to split a polygon. But in an octree, when a triangle is in more than 1 node, you can simply duplicate the triangle to include in each node. There will be fewer triangles added.

Share this post


Link to post
Share on other sites
Quote:
Original post by paic
when a triangle is in more than 1 node, you can simply duplicate the triangle to include in each node.

This is a bad solution for any modern engine. Sure it may be easy to implement but it will cause sou much trouble in the long run. Just think about blending/transparency.


@rgirard413:
You either split it in nodes or use a bit different spatial structure like loose octrees or ABTs.

Share this post


Link to post
Share on other sites
Splitting produces a lot of tris : for 1 initial tri, you end up with 3 tris in 99.99% of the cases. Whereas when you inlclude the tri in both nodes, you end up with only 2 tris (one in each node) It may not be much in small octrees, but if you have a big environment, and a fine octree, you create a lot more faces than needed when you split your tris.

Now, it's true than not splitting tris might cause problems. Alpha blending is one of them. My advice would be to avoid as much splitting as possible and to use it only for those tris that really need it (alpha blended tris should be split)

Now, after a quick google search, and to answer the OP question, I found that :
ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html#8.txt

Share this post


Link to post
Share on other sites
my problem is that the triangle isnt in the node that im in, however i still need to detect a collision against it. There are cases where the vertices will be in another node(s) however the triangle intersects through the current node im in. THink of a cube where a triangle cuts a corner off. HOw do i prevent against such case.

Share this post


Link to post
Share on other sites
@rgirard413: Looks like your problem is in creation of octree nodes. You should never have triangles that are outside the node intersecting it. You'll have to modify box-triangle collision/intersection routine so it finds such cases as described. Searching Google for AABB-triangle should give some nice results.

@paic: We all know splitting triangles is bad. That's why I suggest him to look at the spatial structures that minimize the number of splits needed. Going for octree to loose-octree can simply reduce number of splits by over 90% with only a few % overgrowth.

Share this post


Link to post
Share on other sites
Compare two vertices in a triangle/polygon. Check if the two vertices lie in different cube. If yes,use line equation to split them. The newly created vertex wud lie on the border(or say axis) of the two cubes for which u are checking. You wud end with either three vertices on 1 side(no split required), or 1 verices against 2 (which will force one triangle to be split into two or three triangles). Line Equation will help in determing new vertices for a split and a simple logic will help in creating triangles from it.

Well, I hope this helps

Share this post


Link to post
Share on other sites
If a triangle intersects a plane, you should have two intersection points... you could check the 3 edges of the triangle to find the intersection points and as ebikhan said, simple logic will help in creating triangles..

This page contains some explanation of intersection on lines and planes...

http://softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm#Line-Plane%20Intersection


[Edited by - _GLoom_ on December 5, 2005 5:08:36 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this