A scene I have been working on has a number of objects that lie randomly on an
uneven surface.  I created some SDL code, customized to the objects in question
to place them so that all points of the bottom surface of the object are on or
above the corresponding points of the surface.  After getting the code to work
fairly well, I went down a rabbit hole and decided to make it generic for all
objects and surfaces and add the code to my libraries.

The basic idea is to first generate a set of triangles that represent the bottom
(y axis pointing up) surface of the object.  With the current iteration, I
subdivide the bounding box for the object, (in the XZ plane only) a specified
number of times, (depending on how accurate you want the results to be and how
non-flat the bottom is), and then generate triangles using all subdivisions of
the bounding box.  I generate triangles from each combination of 3-corners of
the bounding boxes, and triangles from each combination of 2 corners and the
center of the box.

Since the shape does not have to be rectangular, when generating triangles, the
corners and center of the bounding box are used to scan the bottom of the object
to determine the "height" of the object at that point, or if it doesn't hit the
object at all.  If it doesn't hit the object, the corners are adjusted, (within
a given tolerance) until they do hit the object or you reach the center.
Triangles are only created if they are valid, (i.e. all 3 sides are non-zero and
result in a valid normal).

The triangles get generated in a breadth-first pattern based on the bounding box
levels.  This ensures the list of triangles starts with the largest ones that
span the whole object, and end with the smaller details.  I found that in my
initial tests, the placement algorithm converges more quickly and accurately
this way.

The placement algorithm then iterates over all of the triangles, testing to see
if any of their vertices would lie below the height of the surface.  If so, a
plane is calculated by lifting the vertex that is below the surface so it lies
at the height of the surface, along with the other two vertices of the triangle,
and a transform is created to orient the object on that plane.  As you continue
with the remaining vertices of the triangle and the remaining triangles, the
object-bottom points are transformed with this plane-transform first before
comparing to the surface.

Once you have gone through all of the triangles, if any transform has been
created, you go back and run through them again to ensure that later transforms
didn't push earlier triangles below the surface.  I added some logic to ensure
that the y-offset for new planes was monotonically increasing, which decreased
the flailing about immensely, and probably obviates running through the
triangles again.  However, this can leave the object hovering over the surface,
so I added one more check to ensure that at least one point touches the surface.

The result of all of this is a dictionary representation of a transform that I
have written, along with code for writing it to a file so you can generate all
of the transforms before you start rendering the scene.  Depending on the size
and complexity of your object and surface, and the level of detail, this can be
time-consuming, so I ensure I can run it once, generate the transforms, and then
just include them in the scene for rendering.

The code needs a lot more testing before I put documentation and official
examples into the GitHub repo with my libraries, but I thought I'd share the
idea in case there are comments, (like "someone has already done this...") :-)

-- Chris R

Post a reply to this message

Attachments:
Download 'libcollide_test.png' (142 KB)

Preview of image 'libcollide_test.png'

hi,

"Chris R" <car### [at] comcastnet> wrote:
> A scene I have been working on has a number of objects that lie randomly on an
> uneven surface.  I created some SDL code, customized to the objects in question
> to place them so that all points of the bottom surface of the object are on or
> above the corresponding points of the surface.  After getting the code to work
> fairly well, I went down a rabbit hole and decided to make it generic for all
> objects and surfaces and add the code to my libraries.
> ...
> The result of all of this is a dictionary representation of a transform that I
> have written, along with code for writing it to a file so you can generate all
> of the transforms before you start rendering the scene.  Depending on the size
> and complexity of your object and surface, and the level of detail, this can be
> time-consuming, so I ensure I can run it once, generate the transforms, and then
> just include them in the scene for rendering.
>
> The code needs a lot more testing before I put documentation and official
> examples into the GitHub repo with my libraries, but I thought I'd share the
> idea in case there are comments, (like "someone has already done this...") :-)

that does sound very nice and _useful_, I can think of two or three projects in
the past where I'd have liked having "supporting code" for planting (then
"vegetation") or placing objects.


> ... (in the XZ plane only) ...

I posted a usable quad-tree a few years back, fwiw.  no ref but will "dig it up"
if thought useful.


regards, jr.

Post a reply to this message