Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!lavaca.uh.edu!nntppost
From: jet@karazm.math.uh.edu (J. Eric Townsend)
Newsgroups: comp.graphics
Subject: Building octrees around discrete objects
Message-ID: <1990Sep17.073033.10458@lavaca.uh.edu>
Date: 17 Sep 90 07:30:33 GMT
Sender: nntppost@lavaca.uh.edu (NNTP Posting Service)
Organization: University of Houston -- Department of Mathematics
Lines: 39



Well, maybe discrete isn't the right word, but it sounds good... :-)

I have objects built from triangle lists (currently unsorted,
could spatially sort if I cared).  Each triangle is described by
it's vertexes.  (Vertexi?)

The question is, how to quickly build octrees around these.  I'm
currently writing my  code to do the following:
1. Determine if triangle intersects with cube.  Do six plane-plane
tests, if any intersections exist check for intersection point to be
within a wall of the box.
2.  Check for abitrary point on triangle to be within box.

If 2, but not 1, then the triangle is completely within the box.
If 1 and 2, then the triangle intersects with the box.  This will
be a terminal node.

I've not figured out a way to determine if the box is within the triangle,
so I stop subdividing when I hit an intersection of box and triangle.

Is there a quicker way to do this?

I'm interested in speed because I suspect (but don't know for sure)
that it's quicker to manipulate the triangles (movement, shape munging,
etc) than to screw around with transforming big octrees.  (If I'm
wrong, feel free to let me know. :-)  I plan on comparing the speeds
of (build octree + trace) and (build spherical bounding volumes and trace).

Thx for any help.

[Obligatory non-seq:  Hey Glassner, nice book.  Worth the $$$ for the
biblio alone.]
--
J. Eric Townsend -- University of Houston Dept. of Mathematics (713) 749-2120
Internet: jet@uh.edu
Bitnet: jet@UHOU
Skate UNIX(r)