Archived

This topic is now archived and is closed to further replies.

CSG-based map editor ------ how?

This topic is 5081 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have written a weak-portal engine (uses a simplified, manually placed portal set, with optionally concave sectors), but runs *very* fast on HW T&L/VP... Unfortunately, and engine is not much, if you have to define your maps by hand, in a hex editor. I want to write an editor that allows the user to create maps for this engine using csg "brushes", a la Valve Hammer Editor/Worldcraft, QuArK, UnrealEd. My brushes need to be clippable, and are restricted to convex shapes. I have figured out that I can represent these as a set of clipping planes on 3 axes, plus an additional rotation matrix which is pos-applied to the clipped volume to produce a final "brush" which can be "finalized" into triangles in the sector structure. Once a brush has been finalized, it need not be editable, other than texture coordinate transformations. I need to support addition and subtraction of these brushes. Is this the right way to implement brushes? Has anyone [willing to share knowledge] done it before? Obviously, Valve are not very forthcoming with the internals of their editor technology. Particularly, how do I convert the plane-set representation into a set of triangles, and how do I determine how to integrate it into the sector''s triangle set.

Share this post


Link to post
Share on other sites
Well as you mentioned, you can represent brushes as a set of clipping planes. All the planes will intersect to form a solid, convex polyhedra.

The actual conversion of these clipping planes into the convex polygon sides of the brush isn''t too difficult. What you do is take one of the clipping planes, and turn it into a physical polygon. This is done by creating a really big triangle or quad on that plane, preferably as big as the dimensions of the game world. You then take the other clipping planes, and clip that triangle using the other clipping planes. When you are done, you have one of the brush''s sides. Repeat this process for each clipping plane (making each one into a large polygon and clipping with all the other planes), and you will generate all the sides of the brush.

Share this post


Link to post
Share on other sites
thanks Zipster.......That''s a better way of doing it than I had thought of....cool thanks.

how do I combine the set of polygons with the existing ones so I dont get overlaps, and can ''cut out'' pieces of the space?
in this regard, is it better to keep the entire map as a plane-set representation, and then generate polys from it as a final step?

Share this post


Link to post
Share on other sites
quote:
Original post by Qatal
in this regard, is it better to keep the entire map as a plane-set representation, and then generate polys from it as a final step?

Well, on a per-brush basis you want to keep a list of the face polygons so you can render them in your map editor, but that's all. Store the plane-set representation when exporting to the data format. This is what programs like Valve Hammer Editor do, and it's the job of the notorious compile tools to take this plane-set representation of brushes and turn them into BSP data.

quote:
Original post by Qatal
how do I combine the set of polygons with the existing ones so I dont get overlaps, and can 'cut out' pieces of the space?


When you're just rendering them in the editor, don't worry about overlaps. All you're doing with the data is rendering. But otherwise, you're dealing with inner face removal. This really isn't too difficult a theory, and implementation can be simplified given the right amount of preconsideration with other data structures.

You have inner faces when two brushes are touching, and the surface between the two brushes needs to be removed because it virtually doesn't exist. More technically, this means that a side of one brush shares the same plane as a side on another brush, only the normals are opposite. The converse isn't necessarily true (that there is an inner surface given the above condition), but in terms of the algorithm it doesn't matter.

The method is a slight spin-off of the technique I told you about earlier, regarding finding the face using clipping planes. Here, when we have the two touching sides, we do the same thing. However, we don't "throw away" what we don't want like we did before. We maintain front and back lists. We take the side in question of brush A, and use the clipping planes from brush B to clip this side (don't use the touching side as one of the clipping planes, since it's coplanar with what you're clipping). Every time you clip, you retain what was in front, and what was in back. Essentially this is the same process I described earlier, so what you are left with is a polygon. This polygon is the surface that's inside, and can be discarded. Those parts that were "thrown away" before are what is left, on the outside, and replace the face throw away. To get a better idea of this method, picture a simple pillar-esque brush touching a floor brush, and image the surface between the pillar and the floor as what we want to discard, and the rest of the floor as what we want to keep.

[edited by - Zipster on January 9, 2004 6:29:45 AM]

Share this post


Link to post
Share on other sites
Shameless self plug, but I wrote the tutorial for this purpose.


Here''s a tutorial I wrote on doing more or less what you''re wanting to do.

http://www.3dtechdev.com/tutorials/illegalgeometry/illegalgeometrytut.html



-=[ Megahertz ]=-

Share this post


Link to post
Share on other sites
Cool. Implemented, and going.

A few more questions though:

1. How do you generate portal polygons using BSP?

2. I am inverting Megahertz''s solution because my game uses
negative space to simplify the BSP generation. How do I do addition (what you people call subtraction) with brushes?
(Megahertz doesnt cover this)

3. Ive heard that automatic portal generation works like crap on
large outdoor terrains, seeing as it uses CSG. I thought maybe I
could get around this by tagging brushes as "terrain" and then
cutting them into a regular grid of portals? Would this work?

Chris

Share this post


Link to post
Share on other sites