<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Finding Space -->
<!--X-From-R13: pynjerapNphc.uc.pbz -->
<!--X-Date: Tue, 19 Aug 1997 00:21:18 +0000 -->
<!--X-Message-Id: 199708190019.RAA26446#xsvr3,cup.hp.com -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 33F46159.4AD97D09#sparta,mainstream.net -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Finding Space</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:clawrenc#cup,hp.com">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00656.html">Previous</a>
| <a href="msg00658.html">Next</a>
]
Thread:
[ <a href="msg00656.html">Previous</a>
| <a href="msg00556.html">Next</a>
]
Index:
[ <A HREF="author.html#00657">Author</A>
| <A HREF="#00657">Date</A>
| <A HREF="thread.html#00657">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Finding Space</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A></LI>
<LI><em>Subject</em>: Re: [MUD-Dev] Finding Space</LI>
<LI><em>From</em>: <A HREF="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</A></LI>
<LI><em>Date</em>: Mon, 18 Aug 97 12:10:42 -0700</LI>
<LI><em>Reply-to</em>: <A HREF="mailto:claw#null,net">claw#null,net</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
In <<A HREF="msg00603.html">33F46159.4AD97D09#sparta,mainstream.net</A>>, on 08/15/97
at 10:18 AM, Michael Hohensee <michael#sparta,mainstream.net> said:
>4-----------------------------
>3------******--------**-------
>2------******-----**-**--*****
>1----*-******-----**-**-------
>0-----------------------------
> 0 2 4 6 8 1012
> 1 3 5 7 9 11
>'-' = empty space, '*' = space taken up by an object.
>For simplicity, all objects take up a cubical volume of space
>(square, in this case). Objects are held in a tree or linked list of
>structs which contain the origin point of the object, and the
>dimensions of the object. For example, the big square in the picture
>above would be Location=6,1 -- Dimensions=6,3.
>I can store anything to any location I want, but I want to avoid
>overlapping objects onto each other (it's bad), so I need to be able
>to find empty space between objects. I can't just try to place an
>object in every location, since there isn't any granularity to this
>space (I use floats instead of ints).
I'm not clear on your problem:
Do you want to determine if two objects as placed shared volume?
(ie collision detection)
or:
Do you want to determine a semi-optimal packing for shaped objects
within a space such that they don't share volumes?
The first is a standard solution is is pretty easy for regular shapes.
You may want to have a look at things like RAPID
(<A HREF="http://www.cs.unc.edu/~geom/OBB/OBBT.html">http://www.cs.unc.edu/~geom/OBB/OBBT.html</A>). They claim to be able to
rotate a 20,000 polygon torus in a 98,000 polygon landscape with full
collision detection in an average of 6.0ms on a mid-range SGI.
The latter question (filling a space) is a mess, a really really nasty
mess. I know there are partial solutions. I'm not aware of any
computationally cheap solutions.
--
J C Lawrence Internet: claw#null,net
(Contractor) Internet: coder#ibm,net
---------------(*) Internet: clawrenc#cup,hp.com
...Honorary Member Clan McFUD -- Teamer's Avenging Monolith...
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<!--X-Follow-Ups-End-->
<!--X-References-->
<UL><LI><STRONG>References</STRONG>:
<UL>
<LI><STRONG><A NAME="00603" HREF="msg00603.html">Finding Space</A></STRONG>
<UL><LI><EM>From:</EM> Michael Hohensee <michael#sparta,mainstream.net></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00656.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00658.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00656.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00556.html">[MUD-Dev] Spellcaster, or Waving Hands</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00657"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00657"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>Re: [MUD-Dev] Finding Space</STRONG>, <EM>(continued)</EM>
<ul compact>
<LI><strong><A NAME="00607" HREF="msg00607.html">Re: [MUD-Dev] Finding Space</A></strong>,
Shawn Halpenny <a href="mailto:malachai#iname,com">malachai#iname,com</a>, Fri 15 Aug 1997, 18:12 GMT
<UL>
<LI><strong><A NAME="00654" HREF="msg00654.html">Re: [MUD-Dev] Finding Space</A></strong>,
Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Mon 18 Aug 1997, 08:01 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00653" HREF="msg00653.html">Re: [MUD-Dev] Finding Space</A></strong>,
Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Mon 18 Aug 1997, 07:48 GMT
<UL>
<LI><strong><A NAME="00656" HREF="msg00656.html">Re: [MUD-Dev] Finding Space</A></strong>,
Michael Hohensee <a href="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</a>, Mon 18 Aug 1997, 19:22 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00657" HREF="msg00657.html">Re: [MUD-Dev] Finding Space</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Tue 19 Aug 1997, 00:21 GMT
</LI>
</ul>
</LI>
<LI><strong><A NAME="00556" HREF="msg00556.html">[MUD-Dev] Spellcaster, or Waving Hands</A></strong>,
Cynbe ru Taren <a href="mailto:cynbe#laurel,actlab.utexas.edu">cynbe#laurel,actlab.utexas.edu</a>, Thu 14 Aug 1997, 17:50 GMT
<UL>
<LI><strong><A NAME="00583" HREF="msg00583.html">Re: [MUD-Dev] Spellcaster, or Waving Hands</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Thu 14 Aug 1997, 22:21 GMT
<UL>
<LI><strong><A NAME="00587" HREF="msg00587.html">Re: [MUD-Dev] Spellcaster, or Waving Hands</A></strong>,
Richard Woolcock <a href="mailto:KaVir#dial,pipex.com">KaVir#dial,pipex.com</a>, Thu 14 Aug 1997, 23:06 GMT
<UL>
<LI><strong><A NAME="00612" HREF="msg00612.html">Re: [MUD-Dev] Spellcaster, or Waving Hands</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Fri 15 Aug 1997, 22:13 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
</UL>
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>